Лекция: Алгоритмы замещения страниц

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

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

Оптимальный алгоритм (OPT).

Одним из последствий открытия аномалии Билэди стал поиск оптимального алгоритма, который при заданной строке обращений имел бы минимальную частоту page faults среди всех других алгоритмов. Такой алгоритм был найден. Он прост: замещай страницу, которая не будет использоваться в течение самого длительного периода времени. Каждая страница должна быть помечена числом инструкций, которые будут выполнены, прежде чем на эту страницу будет сделана первая ссылка. Выталкиваться должна страница, для которой это число наибольшее. Этот алгоритм легко описать, но реализовать невозможно. ОС не знает, к какой странице будет следующее обращение. (Ранее такие проблемы возникали при планировании процессов – алгоритм SJF). Зато мы можем сделать вывод, что для того, чтобы алгоритм замещения был максимально близок к идеальному алгоритму, система должна как можно точнее предсказывать обращения процессов к памяти. Данный алгоритм применяется для оценки качества реализуемых алгоритмов.

Рис. 51

Рис. 52

Алгоритм NRU – не использовавшаяся в последнее время страница

Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц.

При обращении бит R выставляется в 1, через некоторое время ОС не переведет его в 0.

M переводится в 0 только после записи на диск.

Благодаря этим битам можно получить 4 класса страниц:

1. Не было обращений и изменений (R=0, M=0).

2. Не было обращений, было изменение (R=0, M=1).

3. Было обращение, не было изменений (R=1, M=0).

4. Были обращения и изменения (R=1, M=1).

Рис. 53

Рис. 54

Рис. 55

Алгоритм «вторая попытка»

Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.

В таком алгоритме часто используемая страница никогда не покинет память. Но в этом алгоритме приходится часто перемещать страницы по списку.

Рис. 56

Когда требуется загрузить блок в заполненный до предела кэш, какой-либо другой блок должен быть удален из кэша (и записан на диск, если он был модифи­цирован в кэше). Эта ситуация очень похожа на страничную организацию памяти, и к ней применимы все обычные алгоритмы замены, такие как mFIFO (First In First Out — первым прибыл — первым обслужен), «вторая по­пытка» и LRU (Least Recently Used — с наиболее давним использованием). Одно приятное отличие кэширования от страничной организации памяти состоит в том, что обращения к кэшу производятся относительно нечасто, что позволяет хранить все блоки в точном LRU-порядке со связными списками.

К сожалению, здесь есть одна проблема. Теперь, когда мы можем реализовать точное выполнение алгоритма LRU, оказывается, что алгоритм LRU является не­желательным. Вызвано это тем, что буквальное применение алгоритма LRU сни­жает надежность файловой системы и угрожает ее непротиворечивости (обсуж­давшейся в предыдущем разделе). Если в кэш считывается и модифицируется критический блок, например блок i-узла, но не записывается тут же на диск, то компьютерный сбой может привести к тому, что файловая система окажется в про­тиворечивом состоянии. Если блок i-узла поместить в конец цепочки LRU, то мо­жет пройти довольно много времени, прежде чем этот блок попадет в ее начало и будет записан на диск.

Рис. 57

Поскольку большинство современных процессоров не предоставляет соответствующей аппаратной поддержки для реализации алгоритма LRU, хотелось бы иметь алгоритм, достаточно близкий к LRU, но не требующий специальной поддержки. Программная реализация алгоритма, близкого к LRU, – алгоритм NFU (Not Frequently Used). Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти, и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает. Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главный недостаток алгоритма NFU состоит в том, что он ничего не забывает. Например, страница, к которой очень часто обращались в течение некоторого времени, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содержит большую величину. Например, в многопроходных компиляторах страницы, которые активно использовались во время первого прохода, могут надолго сохранить большие значения счетчика, мешая загрузке полезных в дальнейшем страниц.

Рис. 58

К счастью, возможна небольшая модификация алгоритма, которая позволяет ему «забывать». Достаточно, чтобы при каждом прерывании по времени содержимое счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения. Другим, уже более устойчивым недостатком алгоритма является длительность процесса сканирования таблиц страниц.

Алгоритм «рабочий набор»

Замещение страниц по запросу – страницы загружаются по требованию, а не заранее, т. е. процесс прерывается и ждет загрузки страницы.

Буксование – каждую следующую страницу приходится процессу загружать в память.

Рис. 59

Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости.

Рабочий набор – множество страниц (k), которое процесс использовал до момента времени (t), т. е. можно записать функцию w(k,t). На рис.60 показана зависимость рабочего набора w(k,t) от количества запрошенных страниц. Рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса.

Рис. 60

Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор.

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

В принципе, можно использовать множество страниц, к которым обращался процесс за последние t секунд.

Текущее виртуальное время (Tv) – время работы процессора, которое реально использовал процесс.

Время последнего использования (Told)– текущее время при R=1, т. е. все страницы проверяются на R=1, и если «да», то текущее время записывается в это поле. Теперь можно вычислить возраст страницы (не обновления) Tv-Told,и сравнить с t, если возраст больше t, то страница не входит в рабочий набор, и страницу можно выгружать.

Получается три варианта:

· если R=1, то текущее время запоминается в поле время последнего использования;

· если R=0 и возраст > t, то страница удаляется;

· если R=0 и возраст =< t, то эта страница входит в рабочий набор.

Рис. 61

Кэш

Рис. 62

Память вычислительной машины представляет собой иерархию запоминающих устройств (ЗУ), отличающихся средним временем доступа к данным, объемом и стоимостью хранения одного бита. Фундаментом этой пирамиды за­поминающих устройств служит внешняя память, как правило, представляемая жестким диском. Она имеет большой объем (десятки и сотни гигабайт), но ско­рость доступа к данным является невысокой. Время доступа к диску измеряется миллисекундами.

На следующем уровне располагается более быстродействующая (время доступа равно примерно 10-20 наносекундам) и менее объемная (от десятков мегабайт до нескольких гигабайт) оперативная память, реализуемая на относительно мед­ленной динамической памяти DRAM.

Для хранения данных, к которым необходимо обеспечить быстрый доступ, ис­пользуются компактные быстродействующие запоминающие устройства на ос­нове статической памяти SRAM, объем которых составляет от нескольких де­сятков до нескольких сотен килобайт, а время доступа к данным обычно не превышает 8.

Все перечисленные характеристики ЗУ быстро изменяются по мере совершенствования вычислительной аппаратуры. В данном случае важны не абсолютные значения времени доступа или объема памяти, а их соотношение для разных типов запоминающих уст­ройств.

И, наконец, верхушку в этой пирамиде составляют внутренние регистры процес­сора, которые также могут быть использованы для промежуточного хранения данных. Общий объем регистров составляет несколько десятков байт, а время доступа определяется быстродействием процессора и равно в настоящее время примерно 2-3.

Таким образом, можно констатировать печальную закономерность — чем больше объем устройства, тем менее быстродействующим оно является. Более того, стои­мость хранения данных в расчете на один бит также увеличивается с ростом бы­стродействия устройств. Однако пользователю хотелось бы иметь и недорогую, и быструю память. Кэш-память представляет некоторое компромиссное решение этой проблемы.

Рис. 63

Рассмотрим одну из возможных схем кэширования. Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя:

· значение элемента данных;

· адрес, который этот элемент данных имеет в основной памяти;

· дополнительную информацию, которая используется для реализации алго­ритма замещения данных в кэше и обычно включает признак модификации и признак действительности данных.

При каждом обращении к основной памяти по физическому адресу просматри­вается содержимое кэш-памяти с целью определения, не находятся ли там нуж­ные данные. Кэш-память не является адресуемой, поэтому поиск нужных дан­ных осуществляется по содержимому — по взятому из запроса значению поля адреса в оперативной памяти. Далее возможен один из двух вариантов развития событий:

— если данные обнаруживаются в кэш-памяти, то есть произошло кэш-попада­ние (cache-hit), они считываются из нее, и результат передается источнику за­проса;

— если нужные данные отсутствуют в кэш-памяти, то есть произошел кэш-про­мах (cache-miss), они считываются из основной памяти, передаются источни­ку запроса и одновременно с этим копируются в кэш-память.

Интуитивно понятно, что эффективность кэширования зависит от вероятности попадания в кэш. Покажем это путем нахождения зависимости среднего време­ни доступа к основной памяти от вероятности кэш-попаданий. Пусть имеется ос­новное запоминающее устройство со средним временем доступа к данным tl и кэш-память, имеющая время доступа t2, очевидно, что t2<tl. Пусть t – среднее время доступа к данным в системе с кэш-памятью, ар – вероятность кэш-попа­дания.

Среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш и изменяется от среднего времени доступа в ос­новное запоминающее устройство tl при р=0 до среднего времени доступа непо­средственно в кэш-память t2 при р=1. Отсюда видно, что использование кэш-па­мяти имеет смысл только при высокой вероятности кэш-попадания.

Вероятность обнаружения данных в кэше зависит от разных факторов, таких, на­пример, как объем кэша, объем кэшируемой памяти, алгоритм замещения дан­ных в кэше, особенности выполняемой программы, время ее работы, уровень мультипрограммирования и других особенностей вычислительного процесса. Тем не менее в большинстве реализаций кэш-памяти процент кэш-попаданий оказывается весьма высоким — свыше 90%. Такое высокое значение вероятно­сти нахождения данных в кэш-памяти объясняется наличием у данных объек­тивных свойств: пространственной и временной локальности.

Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью про­изойдет в ближайшее время.

Пространственная локальность. Если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам.

Именно основываясь на свойстве временной локальности, данные, только что считанные из основной памяти, размещают в запоминающем устройстве быстро­го доступа, предполагая, что скоро они опять понадобятся. В начале работы сис­темы, когда кэш-память еще пуста, почти каждый запрос к основной памяти вы­полняется «по полной программе»: просмотр кэша, констатация промаха, чтение данных из основной памяти, передача результата источнику запроса и копирова­ние данных в кэш. Затем, по мере заполнения кэша, в полном соответствии со свойством временной локальности возрастает вероятность обращения к данным, которые уже были использованы на предыдущем этапе работы системы, то есть к данным, которые содержатся в кэше и могут быть считаны значительно быст­рее, чем из основной памяти.

Рис. 64

Свойство пространственной локальности также используется для увеличения вероятности кэш-попадания: как правило, в кэш-память считывается не один ин­формационный элемент, к которому произошло обращение, а целый блок дан­ных, расположенных в основной памяти в непосредственной близости с данным элементом. Поскольку при выполнении программы очень высока вероятность, что команды выбираются из памяти последовательно одна за другой из соседних ячеек, то имеет смысл загружать в кэш-память целый фрагмент программы. Аналогично, если программа ведет обработку некоторого массива данных, то ее работу можно ускорить, загрузив в кэш-часть или даже весь массив данных. При этом учитывается высокая вероятность того, что значительное число обращений к па­мяти будет выполняться к адресам массива данных.