Добавлен: 29.10.2018
Просмотров: 48076
Скачиваний: 190
246
Глава 3. Управление памятью
сивно используемую страницу. Главная привлекательность алгоритма NRU в том, что
его нетрудно понять, сравнительно просто реализовать и добиться от него производи-
тельности, которая, конечно, не оптимальна, но может быть вполне приемлема.
3.4.3. Алгоритм «первой пришла, первой и ушла»
Другим низкозатратным алгоритмом замещения страниц является алгоритм FIFO (First
In, First Out — «первым пришел, первым ушел»). Чтобы проиллюстрировать его работу,
рассмотрим супермаркет, у которого вполне достаточно полок для представления как раз
k различных товаров. И вот однажды какая-то компания представляет новый удобный
продукт — быстрорастворимый, полученный в результате сублимационной сушки нату-
ральный йогурт, который может быть восстановлен в микроволновой печи. Он сразу же
приобретает популярность, поэтому наш забитый под завязку супермаркет должен из-
бавиться от одного старого продукта, чтобы запастись новым.
Можно, конечно, найти самый залежалый товар (то есть что-нибудь, чем торгуют уже
лет сто двадцать) и избавиться от него на том основании, что им уже больше никто
не интересуется. В реальности супермаркет ведет связанный список всех продуктов,
имеющихся на текущий момент в продаже, в порядке их поступления. Новый продукт
попадает в конец списка, а продукт из самого начала списка удаляется.
Для алгоритма замещения страниц можно воспользоваться той же идеей. Операци-
онная система ведет список всех страниц, находящихся на данный момент в памяти,
причем совсем недавно поступившие находятся в хвосте, поступившие раньше всех —
в голове списка. При возникновении ошибки отсутствия страницы удаляется страница,
находящаяся в голове списка, а к его хвосту добавляется новая страница. Примени-
тельно к магазину принцип FIFO может привести к удалению воска для эпиляции
усов, но он также может привести и к удалению муки, соли или масла. Применительно
к компьютерам может возникнуть та же проблема: самая старая страница все еще может
пригодиться. Поэтому принцип FIFO в чистом виде используется довольно редко.
3.4.4. Алгоритм «второй шанс»
Простой модификацией алгоритма FIFO, исключающей проблему удаления часто
востребуемой страницы, может стать проверка бита R самой старой страницы. Если
его значение равно нулю, значит, страница не только старая, но и невостребованная,
поэтому она тут же удаляется. Если бит R имеет значение 1, он сбрасывается, а стра-
ница помещается в конец списка страниц и время ее загрузки обновляется, как будто
она только что поступила в память. Затем поиск продолжается.
Действие этого алгоритма, названного «второй шанс», показано на рис. 3.14. Страницы
с A по H содержатся в связанном списке отсортированными по времени их поступления
в память.
Предположим, что ошибка отсутствия страницы возникла на отметке времени 20.
Самой старой является страница A, время поступления которой соответствует началу
процесса и равно 0. Если бит R для страницы A сброшен, страница либо удаляется из
памяти с записью на диск (если она измененная), либо просто удаляется (если она не-
измененная). Но если бит R установлен, то A помещается в конец списка и ее «время
загрузки» переключается на текущее (20). Также при этом сбрасывается бит R. А поиск
подходящей страницы продолжается со страницы B.
3.4. Алгоритмы замещения страниц
247
Рис. 3.14. Действие алгоритма «второй шанс»: а — страницы, отсортированные в порядке FIFO;
б — список страниц при возникновении ошибки отсутствия страницы, показателе времени 20
и установленном в странице А бите R; числа над страницами — это время, когда они были за-
гружены
Алгоритм «второй шанс» занимается поиском ранее загруженной в память страницы,
к которой за только что прошедший интервал времени таймера не было обращений.
Если обращения были ко всем страницам, то алгоритм «второй шанс» превращается
в простой алгоритм FIFO. Представим, в частности, что у всех страниц на рис. 3.14, а
бит R установлен. Операционная система поочередно перемещает страницы в конец
списка, очищая бит R при каждом добавлении страницы к концу списка. В конце
концов она возвращается к странице A, у которой бит R теперь уже сброшен. И тогда
страница A выселяется. Таким образом, алгоритм всегда завершает свою работу.
3.4.5. Алгоритм «часы»
При всей своей логичности алгоритм «второй шанс» слишком неэффективен, по-
скольку он постоянно перемещает страницы в своем списке. Лучше содержать все
страничные блоки в циклическом списке в виде часов (рис. 3.15). Стрелка указывает
на самую старую страницу.
Рис. 3.15. Алгоритм «часы»
248
Глава 3. Управление памятью
При возникновении ошибки отсутствия страницы проверяется та страница, на которую
указывает стрелка. Если ее бит R имеет значение 0, страница выселяется, на ее место
в «циферблате» вставляется новая страница и стрелка передвигается вперед на одну
позицию. Если значение бита R равно 1, то он сбрасывается и стрелка перемещается
на следующую страницу. Этот процесс повторяется до тех пор, пока не будет найдена
страница с R = 0. Неудивительно, что этот алгоритм называется «часы».
3.4.6. Алгоритм замещения наименее
востребованной страницы
В основе неплохого приближения к оптимальному алгоритму лежит наблюдение, что
страницы, интенсивно используемые несколькими последними командами, будут,
скорее всего, снова востребованы следующими несколькими командами. И наобо-
рот, долгое время не востребованные страницы наверняка еще долго так и останутся
невостребованными. Эта мысль наталкивает на вполне реализуемый алгоритм: при
возникновении ошибки отсутствия страницы нужно избавиться от той страницы, ко-
торая длительное время не была востребована. Эта стратегия называется замещением
наименее востребованной страницы
(Least Recently Used (LRU)).
Теоретически реализовать алгоритм LRU вполне возможно, но его практическая реали-
зация дается нелегко. Для его полной реализации необходимо вести связанный список
всех страниц, находящихся в памяти. В начале этого списка должна быть только что
востребованная страница, а в конце — наименее востребованная. Сложность в том, что
этот список должен обновляться при каждом обращении к памяти. Для поиска страни-
цы в списке, ее удаления из него и последующего перемещения этой страницы вперед
потребуется довольно много времени, даже если это будет возложено на аппаратное
обеспечение (если предположить, что такое оборудование можно создать).
Существуют и другие способы реализации LRU с использованием специального обо-
рудования. Сначала рассмотрим самый простой из них. Для его реализации аппаратное
обеспечение необходимо оснастить 64-разрядным счетчиком C, значение которого
автоматически увеличивается после каждой команды. Кроме этого каждая запись
в таблице страниц должна иметь довольно большое поле, чтобы содержать значение
этого счетчика. После каждого обращения к памяти текущее значение счетчика C со-
храняется в записи таблицы страниц, относящейся к той странице, к которой было это
обращение. При возникновении ошибки отсутствия страницы операционная система
проверяет все значения счетчика в таблице страниц, чтобы найти наименьшее из них.
Та страница, к чьей записи относится это значение, и будет наименее востребованной.
3.4.7. Моделирование LRU в программном обеспечении
При всей принципиальной возможности реализации алгоритма LRU вряд ли най-
дется машина, обладающая нужным оборудованием. Скорее всего, нам понадобится
решение, которое может быть реализовано в программном обеспечении. Одно из воз-
можных решений называется алгоритмом нечастого востребования (Not Frequently
Used (NFU)). Для его реализации потребуется программный счетчик с начальным
нулевым значением, связанный с каждой страницей. При каждом прерывании от
таймера операционная система сканирует все находящиеся в памяти страницы. Для
каждой страницы к счетчику добавляется значение бита R, равное 0 или 1. Счетчики
позволяют приблизительно отследить частоту обращений к каждой странице. При
3.4. Алгоритмы замещения страниц
249
возникновении ошибки отсутствия страницы для замещения выбирается та страница,
чей счетчик имеет наименьшее значение.
Основная проблема при использовании алгоритма NFU заключается в том, что он
похож на слона: никогда ничего не забывает. К примеру, при многопроходной компи-
ляции те страницы, которые интенсивно использовались при первом проходе, могут
сохранять высокие значения счетчиков и при последующих проходах. Фактически
если на первый проход затрачивается больше времени, чем на все остальные проходы,
то страницы, содержащие код для последующих проходов, могут всегда иметь более
низкие показатели счетчиков, чем страницы, использовавшиеся при первом проходе.
Вследствие этого операционная система будет замещать нужные страницы вместо тех,
надобность в которых уже отпала.
К счастью, небольшая модификация алгоритма NFU позволяет довольно близко подойти
к имитации алгоритма LRU. Модификация состоит из двух частей. Во-первых, перед до-
бавлением к счетчикам значения бита R их значение сдвигается на один разряд вправо.
Во-вторых, значение бита R добавляется к самому левому, а не к самому правому биту.
На рис. 3.16 показано, как работает модифицированный алгоритм, известный как ал-
горитм
старения. Предположим, что после первого прерывания от таймера бит R для
страниц от 0-й до 5-й имеет значения соответственно 1, 0, 1, 0, 1 и 1 (для страницы 0 оно
равно 1, для страницы 1 — 0, для страницы 2 — 1 и т. д.). Иными словами, между пре-
рываниями от таймера, соответствующими тактам 0 и 1, было обращение к страницам
0, 2, 4 и 5, в результате которого их биты R были установлены в 1, а у остальных страниц
их значение осталось равным 0. После того как были смещены значения шести соот-
ветствующих счетчиков и слева вставлено значение бита R, они приобрели значения,
показанные на рис. 3.16, а. В четырех оставшихся столбцах показаны состояния шести
счетчиков после следующих четырех прерываний от таймера.
Рис. 3.16. Алгоритм старения является программной моделью алгоритма LRU. Здесь показаны
шесть страниц в моменты пяти таймерных прерываний, обозначенных буквами от а до д
250
Глава 3. Управление памятью
При возникновении ошибки отсутствия страницы удаляется та страница, чей счетчик
имеет наименьшее значение. Очевидно, что в счетчике страницы, к которой не было
обращений за, скажем, четыре прерывания от таймера, будет четыре ведущих нуля,
и поэтому значение ее счетчика будет меньшим, чем счетчика страницы, к которой не
было обращений в течение трех прерываний от таймера.
Этот алгоритм отличается от алгоритма LRU двумя особенностями. Рассмотрим стра-
ницы 3 и 5 на рис. 3.16, д. Ни к одной из них за два прерывания от таймера не было
ни одного обращения, но к обеим было обращение за прерывание от таймера, предше-
ствующее этим двум. В соответствии с алгоритмом LRU, если страница должна быть
удалена, то мы должны выбрать одну из этих двух страниц. Проблема в том, что мы
не знаем, к какой из них обращались в последнюю очередь между тактом 1 и тактом 2.
При записи только одного бита за интервал между двумя прерываниями от таймера мы
утратили возможность отличить более раннее обращение от более позднего. Все, что мы
можем сделать, — удалить страницу 3, поскольку к странице 5 также было обращение
двумя тактами ранее, а к странице 3 такого обращения не было.
Второе различие между алгоритмом LRU и алгоритмом старения заключается в том,
что в алгоритме старения счетчик имеет ограниченное количество бит (в данном при-
мере — 8 бит), которое сужает просматриваемый им горизонт прошлого. Предположим,
что у каждой из двух страниц значение счетчика равно нулю. Все, что мы можем сде-
лать, — это выбрать одну из них произвольным образом. В действительности вполне
может оказаться, что к одной из этих страниц последнее обращение было 9 тактов
назад, а ко второй — 1000 тактов назад. И это обстоятельство установить невозможно.
Но на практике 8 бит вполне достаточно, если между прерываниями от таймера про-
ходит примерно 20 мс. Если к странице не было обращений в течение 160 мс, то она,
наверное, уже не так важна.
3.4.8. Алгоритм «рабочий набор»
При использовании замещения страниц в простейшей форме процессы начинают свою
работу, не имея в памяти вообще никаких страниц. Как только центральный процессор
попытается извлечь первую команду, он получает ошибку отсутствия страницы, застав-
ляющую операционную систему ввести в память страницу, содержащую первую команду.
Обычно вскоре за этим следуют ошибки отсутствия страниц с глобальными переменны-
ми и стеком. Через некоторое время процесс располагает большинством необходимых
ему страниц и приступает к работе, сталкиваясь с ошибками отсутствия страниц отно-
сительно редко. Эта стратегия называется замещением страниц по требованию (demand
paging), поскольку страницы загружаются только по мере надобности, а не заранее.
Разумеется, нетрудно написать тестовую программу, систематически читающую все стра-
ницы в огромном адресном пространстве, вызывая при этом такое количество ошибок
отсутствия страниц, что для их обработки не хватит памяти. К счастью, большинство
процессов так не работают. Они применяют локальность обращений, означающую, что
в течение любой фазы выполнения процесс обращается только к относительно неболь-
шой части своих страниц. К примеру, при каждом проходе многопроходного компилятора
обращение идет только к части имеющихся страниц, причем всякий раз к иной.
Набор страниц, который процесс использует в данный момент, известен как рабочий
набор
(Denning, 1968а; Denning, 1980). Если в памяти находится весь рабочий набор,
процесс будет работать, не вызывая многочисленных ошибок отсутствия страниц, пока