-
Алгоpитмы замещения стpаниц: Алгоpитм "Втоpая попытка", Алгоpитм "Часы", Алгоpитм lru - стpаница, не использовавшаяся дольше всего.
Алгоритм «вторая попытка»
Изменен алгоритм FIFO, у самой старой страницы провер бит R. Если R = 0, => страница находится в памяти долго и не используется, поэтому заменяется новой. Если R = 1, то R = 0, страница переносится в конец списка, а время ее загрузки обновляется, то есть считается, что страница только что попала в память. Затем процедура продолжается. Если же происходили ссылки на все страницы, то «вторая попытка» превращается в обычный алгоритм FIFO.
Пример: А-самая стар стран с R = 1, Н- послед загр стран.
После стран прервыания Т=20
Алгоритм «часы»
все страничные блоки хранятся в кольцевом списке в форме часов. Стрелка указывает на старейшую страницу.
Когда происходит страничное прерывание, проверяется страница, на которую указывает стрелка. Если ее бит R равен 0, страница выгружается, на ее место в часовой круг встает новая страница, а стрелка сдвигается вперед на одну позицию. Если бит R равен 1, то он сбрасывается, стрелка перемещается к следующей странице. Процесс повторяется, пока не находится та страница, у которой бит R = 0.
Алгоритм LRU — страница, не использовавшаяся дольше всего
Страницы, к которым происходило многократное обращение в нескольких последних командах, вероятно, также будут часто использоваться в следующих инструкциях. И страницы, к которым ранее не возникало обращений, не будут употребляться в течение долгого времени. Алгоритм LRU (Least Recently Used: когда происходит страничное прерывание, выгружается из памяти страница, которая не использовалась дольше всего, последн использ помещ в нач списка.
«−» список должен обновляться при каждом обращении к памяти. В чистом виде алгоритм не использ, т.к. поиск, удаление, а затем вставка в начало списка страниц занимающ много времени.
Другие способы реализации алгоритма LRU
1) нужен 64-разрядн аппаратн счетчик С, автоматически ↑после каждой команды(+1). Каждая запись в ТС должна иметь поле для хранения счетчика. После каждого обращения к памяти величина счетчика С записыв в записи ТС. А если возникает стран прерыв, ОС проверяет все значения счетчиков в ТС и ищет наименьшее. Эта страница является не использовавшейся дольше всего.
2) На машине с n страничными блоками оборудование LRU может поддерживать матрицу n х n бит, изначально равных нулю. Всякий раз, когда происходит обращение к страничному блоку k, аппаратура сначала присваивает всем битам строки k значение 1, затем приравнивает к нулю все биты столбца k. Строка, двоичное значение которой наименьшее, является не использовавшейся дольше всего. Пример: обращение к страниц 0123210323
-
Пpогpаммное моделиpование алгоpитма lru: Алгоpитм nfu - pедко использовавшаяся стpаница, Алгоpитм "стаpение", Замещение стpаниц по запpосу и опеpежающая подкачка, Понятие pабочего набоpа стpаниц.
Одна из разновидностей схемы LRU называется алгоритмом NFU (Not Frequently Used — редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время каждого прерывания по таймеру ОС исследует все страницы в памяти. Бит R каждой страницы (он равен 0 или 1) прибавляется к счетчику. При страничном прерывании для замещения выбирается страница с наименьшим значением счетчика.
Проблема: алгоритм NFU никогда ничего не забывает. Например, в многоходовом компиляторе страницы, которые часто использовались во время первого прохода, могут все еще иметь высокое значение счетчика при более поздних проходах. Если первый проход занимает самое долгое время выполнения из всех, страницы, содержащие программный код для следующих проходов, могут всегда иметь более низкое значение счетчика, чем страницы первого прохода. Следовательно, ОС удалит полезные страницы вместо тех, которые
больше не нужны. Решение: 1) каждый счетчик сдвигается вправо на один разряд перед прибавлением бита R. 2) бит R добавляется в крайний слева, а не в крайний справа бит счетчика. Видоизмен алгоритм наз «старение».Когда происходит страничное прерывание, удаляется та страница, чей счетчик имеет наименьшую величину.
Счетчик имеет конечное число разрядов, например 8. Пусть что каждая из двух страниц имеет значение счетчика, равное 0. В данной ситуации мы только случайным образом можем выбрать одну из них. На самом деле может оказаться, что к одной странице в последний раз обращались 9 тиков назад, а к другой — 1000. И мы не имеем возможности увидеть это. На практике, однако, обычно достаточно 8 битов при тике системных часов около 20 мс. Если к странице не обращались в течение 160 мс, очень вероятно, что она не важна.
В простейшей схеме страничной подкачки в момент запуска процессов нужные им страницы отсутствуют в памяти. Как только Ц Пр пытается выбрать первую команду, он получает страничное прерывание, побуждающее ОС перенести в память страницу, содержащую первую инструкцию. Обычно следом быстро происходят страничные прерывания для глобальных
переменных и стека. Через некоторое время в памяти скапливается большинство необходимых процессу страниц, и он приступает к работе с относительно небольшим количеством ошибок из-за отсутствия страниц. Этот метод называется замещением страниц по запросу - страницы загружаются в память по требованию, а не заранее.
Процессы характеризуются локальностью обращений, означающей, что во время выполнения процесс обращается только к небольшой части своих страниц.
Множество страниц, которое процесс использует в данный момент называется рабочим набором. Если рабочий набор целиком находится в памяти то страничн прер почти нет. Если доступная память слишком мала, чтобы содержать полный рабочий набор, процесс вызовет много страничных прерываний и будет работать медленнее. Если страничн прер вызыв через несколько команд то это назыв пробуксовкой.
Многие системы со страничной организацией пытаются отслеживать рабочий набор каждого процесса , чтобы после выгрузки его на диск и обратной загрузки не тратить время Ц Пр из за странич прер и обеспечивают его нахождение в памяти до запуска процесса. Такой подход носит название модели рабочего набора. Загрузка страниц перед тем, как разрешить процессу работать, называется опережающей подкачкой страниц.
В любой момент времени t существует множество страниц, использовавшихся за k последних обращений к памяти. Это множество w(k, t) и есть рабочий набор.
