Глава 4 (1085728), страница 7
Текст из файла (страница 7)
А
лгоритм «вторая попытка» ищет в списке самую старую страницу, к которой не было обращений в предыдущем временном интервале. Если же происходили ссылки на все страницы, то «вторая попытка» превращается в обычный алгоритм FIFO. Представьте, что у всех страниц на рис. 4.15, а бит R равен 1. Одну за другой передвигает операционная система страницы в конец списка, очищая бит R каждый раз, когда она перемещает страницу в хвост. Наконец, она вернется к странице A, но теперь уже ее биту R присвоено значение 0. В этот момент страница А выгружается из памяти. Таким образом, алгоритм всегда успешно завершает свою работу.
То есть устанавливается на 0.
Алгоритм «часы».
Хотя алгоритм «вторая попытка» является корректным, он слишком неэффективен, потому что постоянно передвигает страницы по списку. Поэтому лучше хранить все страничные блоки в кольцевом списке в форме часов, как показано на рис. 4.16. Стрелка указывает на старейшую страницу.
К
огда происходит страничное прерывание, проверяется та страница, на которую направлена стрелка. Если ее бит R равен 0, страница выгружается, на ее место в часовой круг встает новая страница, а стрелка сдвигается вперед на одну позицию. Если бит R равен 1, то он сбрасывается, стрелка перемещается к следующей странице. Этот процесс повторяется до тех пор, пока не находится та страница, у которой бит R = 0. Неудивительно, что этот алгоритм называется <<часы>>. Он отличается от алгоритма «вторая попытка» только своей реализацией.
Алгоритм LRU — страница, не использовавшаяся дольше всего
В основе этой неплохой аппроксимации оптимального алгоритма лежит наблюдение, что страницы, к которым происходило многократное обращение в нескольких последних командах, вероятно, также будут часто использоваться в следующих инструкциях. И наоборот, можно полагать, что страницы, к которым ранее не возникало обращений, не будут употребляться в течение долгого времени. Эта идея привела к следующему реализуемому алгоритму: когда происходит страничное прерывание, выгружается из памяти страница, которая не использовалась дольше всего. Такая стратегия замещения страниц называется LRU (Least Recently Used — <<менее недавно>>, то есть наиболее давно использовавшаяся страница).
Хотя алгоритм LRU теоретически реализуем, он не является дешевым. Для полного осуществления алгоритма LRU необходимо поддерживать связный список всех содержащихся в памяти страниц, где последняя использовавшаяся страница находится в начале списка, а та, к которой дольше всего не было обращений, — в конце. Сложность заключается в том, что список должен обновляться при каждом обращении к памяти. Поиск страницы, ее удаление, а затем вставка в начало списка — это операции, поглощающие очень много времени, даже если они выполняются аппа-ратно (если предположить, что необходимое оборудование можно сконструировать).
Однако существуют другие способы реализации алгоритма LRU с помощью специального оборудования. Для первого метода требуется оснащение компьютера 64-разрядным аппаратным счетчиком С, который автоматически возрастает после каждой команды. Кроме того, каждая запись в таблице страниц должна иметь поле, достаточно большое для хранения значения счетчика. После каждого обращения к памяти текущая величина счетчика С запоминается в записи таблицы, соответствующей той странице, к которой произошла ссылка. А если возникает страничное прерывание, операционная система проверяет все значения счетчиков в таблице страниц и ищет наименьшее. Эта страница является не использовавшейся дольше всего.
Теперь рассмотрим второй вариант аппаратной реализации алгоритма LRU. На машине с п страничными блоками оборудование LRU может поддерживать матрицу п х п бит, изначально равных нулю. Всякий раз, когда происходит обращение к страничному блоку k, аппаратура сначала присваивает всем битам строки k значение 1, затем приравнивает к нулю все биты столбца k. В любой момент времени строка, двоичное значение которой наименьшее, является не использовавшейся дольше всего. Работа этого алгоритма продемонстрирована на рис. 4.17, где рассматриваются четыре страничных блока и следующий порядок обращения к страницам:
0 1 2 3 2 1 0 3 2 3
После ссылки на страницу 0 мы получаем ситуацию, показанную на рис. 4.17, а;
после обращения к странице 1 — рис. 4.17, б и т. д.
П
рограммное моделирование алгоритма LRU
Хотя оба описанных выше алгоритма LRU в принципе осуществимы, очень мало (если вообще такие есть) машин оснащено подобным оборудованием, поэтому разработчики операционных систем для компьютеров, не имеющих такой аппаратуры, редко используют эти алгоритмы. Вместо этого требуется программно реализуемое решение. Одна из разновидностей схемы LRU называется алгоритмом NFU (Not Frequently Used — редко использовавшаяся страница). Для него необходим программный счетчик, связанный с каждой страницей в памяти, изначально равный нулю. Во время каждого прерывания по таймеру операционная система исследует все страницы в памяти. Бит R каждой страницы (он равен 0 или 1) прибавляется к счетчику. В сущности, счетчики пытаются отследить, как часто происходило обращение к каждой странице. При страничном прерывании для замещения выбирается страница с наименьшим значением счетчика.
Основная проблема, возникающая при работе с алгоритмом NFU, заключается в том, что он никогда ничего не забывает. Например, в многоходовом компиляторе страницы, которые часто использовались во время первого прохода, могут все еще иметь высокое значение счетчика при более поздних проходах. Фактически, если случается так, что первый проход занимает самое долгое время выполнения из всех, страницы, содержащие программный код для следующих проходов, могут всегда иметь более низкое значение счетчика, чем страницы первого прохода. Следовательно, операционная система удалит полезные страницы вместо тех, которые больше не нужны.
К счастью, небольшая доработка алгоритма NFU делает его способным моделировать алгоритм LRU достаточно хорошо. Изменение состоит из двух частей. Во-первых, каждый счетчик сдвигается вправо на один разряд перед прибавлением бита R. Во-вторых, бит R добавляется в крайний слева, а не в крайний справа бит счетчика.
На рис. 4.18 продемонстрировано, как работает видоизмененный алгоритм, известный под названием «старение» (aging). Предположим, что после первого тика часов биты R для страниц от 0 до 5 имеют значения 1,0, 1,0, 1, 1 соотвественно (у страницы 0 бит R равен 1, у страницы 1 R = 0, у страницы 2 R = 1 и т. д.). Другими словами, между тиком 0 и тиком 1 произошло обращение к страницам 0, 2, 4 и 5, их биты R приняли значение 1, остальные сохранили значение 0. После того как шесть соответствующих счетчиков сдвинулись на разряд и бит R занял крайнюю слева позицию, счетчики получили значения, показанные на рис. 4.18, а. Остальные четыре колонки рисунка изображают шесть счетчиков после следующих четырех тиков часов.
Когда происходит страничное прерывание, удаляется та страница, чей счетчик имеет наименьшую величину. Ясно, что счетчик страницы, к которой не было обращений, скажем, за четыре тика, будет начинаться с четырех нулей и, таким образом, иметь более низкое значение, чем счетчик страницы, на которую не ссылались в течение только трех тиков часов.
Эта схема отличается от алгоритма LRU в двух случаях. Рассмотрим страницы 3 и 5 на рис. 4.18, д. Ни к одной из них не было обращений за последние два тика, к обеим было обращение за предшествующий этому тик. Следуя алгоритму LRU, при удалении страницы из памяти мы должны выбрать одну из этих двух. Проблема в том, что мы не знаем, к какой из них позже произошло обращение в интервале времени между тиками 1 и 2. Записывая только один бит за промежуток времени, мы теряем возможность отличить более ранние от более поздних обращений в этом интервале времени. Все, что мы можем сделать — это выгрузить страницу 3, потому что к странице 5 также обращались двумя тиками раньше, а к странице 3 — нет.
Второе отличие между алгоритмами LRU и «старения» заключается в том, что в последнем счетчик имеет конечное число разрядов, например 8. Предположим, что каждая из двух страниц имеет значение счетчика, равное 0. В данной ситуации мы только случайным образом можем выбрать одну из них. На самом деле может оказаться, что к одной странице в последний раз обращались 9 тиков назад, а к другой — 1000. И мы не имеем возможности увидеть это. На практике, однако, обычно достаточно 8 битов при тике системных часов около 20 мс. Если к странице не обращались в течение 160 мс, очень вероятно, что она не важна.
Алгоритм «рабочий набор»
В простейшей схеме страничной подкачки в момент запуска процессов нужные им страницы отсутствуют в памяти. Как только центральный процессор пытается выбрать первую команду, он получает страничное прерывание, побуждающее операционную систему перенести в память страницу, содержащую первую инструкцию. Обычно следом быстро происходят страничные прерывания для глобальных переменных и стека. Через некоторое время в памяти скапливается большинство необходимых процессу страниц, и он приступает к работе с относительно небольшим количеством ошибок из-за отсутствия страниц. Этот метод называется замещением страниц по запросу (demand paging), потому что страницы загружаются в память по требованию, а не заранее.
Конечно, достаточно легко написать тестовую программу, систематически читающую все страницы в огромном адресном пространстве, вызывая так много страничных прерываний, что будет не хватать памяти для их обработки. К счастью, большинство процессов не работают таким образом. Они характеризуются локальностью обращений, означающей, что во время выполнения любой фразы процесс обращается только к сравнительно небольшой части своих страниц. Каждый проход многоходового компилятора, например, обращается только к части от общего количества страниц, и каждый раз к другой части. Множество страниц, которое процесс использует в данный момент, называется рабочим набором ([89, 92]). Если рабочий набор целиком находится в памяти, процесс будет работать, не вызывая большого количества ошибок, до тех пор пока он не перейдет к другой фазе выполнения (то есть к следующему проходу компилятора). Если доступная память слишком мала для того, чтобы содержать полный рабочий набор, процесс вызовет много страничных прерываний и будет работать медленнее, так как выполнение инструкции занимает несколько наносекунд, а чтение страницы с диска обычно требует 10 мс. При скорости одна или две команды за 10 мс для завершения программы понадобятся века. Говорят, что программа, вызывающая страничное прерывание каждые несколько команд, пробуксовывает (thrashing) [90].
В многозадачных системах процессы часто перемещаются на диск (то есть все их страницы удаляются из памяти), чтобы позволить другим процессам получить доступ к центральному процессору. Возникает вопрос, что делать, когда процесс снова загружается в память. С формальной точки зрения делать ничего не нужно. Процесс будет вызывать одно за другим страничные прерывания до тех пор, пока не загрузится в память весь его рабочий набор. Проблема в том, что наличие 20, 100 или даже 1000 страничных прерываний при каждой загрузке процесса сильно замедляет работу системы и, кроме того, тратит впустую значительное количество времени работы центрального процессора, так как обработка страничного прерывания операционной системой требует нескольких миллисекунд работы процессора.
Поэтому многие системы со страничной организацией пытаются отслеживать рабочий набор каждого процесса и обеспечивают его нахождение в памяти до запуска процесса. Такой подход носит название модели рабочего набора . Он разработан для того, чтобы значительно снизить процент страничных прерываний. Загрузка страниц перед тем, как разрешить процессу работать, также называется опережающей подкачкой страниц (prepaging). Заметьте, что рабочий набор изменяется с течением времени.
Давно известно, что большинство программ не обращаются к своему адресному пространству равномерно; чаще всего ссылки группируются на небольшом количестве страниц. Обращение к памяти может быть выборкой команды, данных или сохранением данных. В любой момент времени t существует множество страниц, использовавшихся за k последних обращений к памяти. Это множество w(k, t) и есть рабочий набор. Так как все недавние обращения к памяти для k > 1 обязательно должны были обращаться ко всем страницам, использовавшимся для k = 1 обращения к памяти, то есть к последней и, возможно, еще к некоторым страницам, w(k, t) является монотонно неубывающей функцией от k. Функция w(k, t) ограничена для больших k, потому что программа не может обращаться к большему количеству страниц, чем содержится в ее адресном пространстве, кроме того, редкие программы обращаются ко всем страницам адресного пространства. На рис. 4.19 изображена зависимость размера рабочего набора от k.
Т
от факт, что большинство программ случайным образом обращается к небольшому числу страниц, но это множество медленно изменяется во времени, объясняет быстрое возрастание функции в начале и затем медленное увеличение для больших k. Например, программа, которая выполняет цикл, затрагивающий две страницы и использующий данные на четырех страницах, может обращаться ко всем шести страницам через каждые 1000 инструкций, но самое последнее обращение к некоторым другим страницам могло произойти миллионом команд раньше, во время начальной загрузки фазы. Вследствие этого асимптотического характера содержимое рабочего набора не чувствительно к выбранной величине k. Существует широкий диапазон значений k, для которых рабочий набор постоянен. Поскольку рабочий набор медленно меняется со временем, можно сделать разумное предположение, что те страницы, которые будут нужны для возобновления работы программы, составляют основу рабочего набора во время последней остановки процесса. Опережающая подкачка страниц заключается в загрузке рабочего набора до того, как процессу разрешается возобновиться.
Рис. 4.19. Рабочий набор — это множество страниц, используемых k последними обращениями к памяти. Функция w(k, t) представляет собой размер рабочего набора в момент времени t
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
