4. Стратегии подкачки страниц.

Когда происходит страничное прерывание, операционная система должна выбрать страницу для удаления из памяти, чтобы освободить место для страницы, которую нужно туда перенести. Если удаляемая страница была изменена за время своего присутствия в памяти, ее необходимо переписать на диск, чтобы обновить копию, хранящуюся там. Однако если страница не была модифицирована (например, она содержит текст программы), копия на диске уже является самой новой и ее не надо переписывать. Тогда страница, которую надо прочитать, просто считывается поверх выгружаемой.

Хотя, в принципе, можно при каждом страничном прерывании выбирать случайную страницу для удаления, производительность системы заметно повышается, когда предпочтение отдается редко используемой странице. Если выгружается страница, обращения к которой происходят часто, велика вероятность, что вскоре опять потребуется ее возврат в память, что даст в результате дополнительные издержки. Теме разработки алгоритмов замены страницы было посвящено много работ, как теоретических, так и экспериментальных. Ниже мы опишем некоторые из наиболее важных алгоритмов.

Наилучший из возможных алгоритмов замещения страниц легко описать, но не-возможно реализовать. Он действует так. В тот момент, когда происходит страничное прерывание, в памяти находится некоторый набор страниц. К одной из этих страниц будет обращаться следующая команда процессора (к странице, содержащей требуемую команду). На другие страницы, возможно, не будет ссылок в течение следующих 10, 100 или даже 1000 команд. Каждая страница может быть помечена количеством команд, которые будут выполняться перед первым к ней обращением.

Оптимальный страничный алгоритм просто сообщает, что должна быть выгружена страница с наибольшей меткой. Если одна страница не будет использоваться в течение 8 млн команд, а другая — в течение 6 млн команд, удаление первой отодвинет в будущее на возможно максимальный срок страничное прерывание, которое вернет ее назад. Компьютеры, подобно людям, пытаются отложить неприятные события настолько, насколько это возможно.

С этим алгоритмом связана только одна проблема: он невыполним. В момент страничного прерывания операционная система не имеет возможности узнать, когда произойдет следующее обращение к каждой странице. (Мы рассматривали аналогичную ситуацию раньше, когда обсуждали алгоритм планирования «кратчайшая задача — первая»: как система может сказать, какая из задач самая короткая?) Тем не менее, выполняя программу на модели и следя за всеми обращениями к страницам, оптимальную замену можно осуществить при втором запуске, опираясь на информацию о ссылках на страницы, собранную во время первого запуска.

Алгоритм NRU – неиспользовавшаяся в последнее время страница. Чтобы дать возможность операционной системе собирать полезные статистические данные о том. какие страницы используются, а какие — нет, большинство компьютеров с виртуальной памятью поддерживают два статусных бита, связанных с каждой страницей. Бит R (от Referenced — обращения) устанавливается всякий раз, когда происходит обращение к странице (чтение или запись). Бит М (от Modified — изменение) устанавливается, когда страница записывается (то есть изменяется). Биты содержатся в каждом элементе таблицы страниц, как показано на рис. 4.11. Важно реализовать обновление этих битов при каждом обращении к памяти, поэтому необходимо, чтобы они задавались аппаратно. Если однажды бит был установлен в 1, то он остается равным 1 до тех пор, пока операционная система программно не вернет его в состояние 0.

Алгоритм FIFO – первый пришел, первый обслужен. Чтобы проиллюстрировать его работу, рассмотрим универсам, па полках которого можно выставить ровно k различных продуктов. Он предлагает новую удобную пишу: растворимый, «глубоко замороженный», экологически чистый йогурт, который можно мгновенно приготовить в микроволновой печи. Покупатели тут же обратили внимание на этот продукт, и наш ограниченный в размерах супермаркет, для того чтобы продавать новинку, должен избавиться от одного из старых товаров.

Контрольные задания для СРС (тема 5) [(3;67-99),(1;402-449)(4;162-212)]

1. Средства вызова процедур и команд.

2. Сегментно-страничный способ реализации виртуальной памяти.

3. Алгоритмы «вторая попытка», «часы», LRU и «рабочий набор»

Рекомендуемая литература

1. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows

2. Столингс Операционные системы

3. Гордеев А.В, Молчанов А.Ю. Системное программное обеспечение.

4. Олифер В.Г.,Олифер Н.А. Сетевые ОС