АЛГОРИТМЫ УПРАВЛЕНИЯ МНОГОУРОВНЕВОЙ ПАМЯТЬЮ
Будем рассматривать двухуровневую память со страничной организацией, состоящую из оперативной (верхний уровень) и внешней (нижний уровень) памятей. Если при выполнении программы обнаруживается, что страница с нужными данными (операндами, куском программы) отсутствует в памяти верхнего уровня, она передается туда из памяти нижнего уровня. Если при этом в памяти верхнего уровня нет для нее свободного места, то она замещает одну из страниц, находящихся в ОП. При этом если в замещаемую страницу во время ее пребывания в ОП производилась запись, то она должна быть передана в память нижнего уровня (заменит там свою устаревшую копию).
Эти операции передачи информации между уровнями памяти вызывают простои процессора и, следовательно, потери производительности вычислительной системы, поэтому следует стремиться уменьшить число таких операций в процессе выполнения программы. Очевидно, что число этих операций обмена информацией зависит от того, какая информация отсылается из памяти верхнего уровня, так как к этой информации возможно обращение в процессе дальнейшего выполнения программы.
Приведем формализованную модель процесса обмена информацией между верхним и нижним уровнями памяти. Пусть программа вместе с исходными данными состоит из k страниц, которым присвоены номера 1, 2, ..., k, тогда программу можно рассматривать как множество страниц:
Q = {1,2, …, k}.
Все страницы программы постоянно хранятся в памяти нижнего уровня, а, кроме того, r из них могут находиться в памяти верхнего уровня (оперативной памяти), при этом
1 < r < k.
Выполнение программы порождает последовательность обращений к страницам памяти. Рассматриваем эту последовательность как реализацию некоторого случайного процесса:
q0, q1, q2, …, qt,
где qt – случайная дискретная величина, принимающая в момент времени t значение одного из номеров страниц программы (qt Î Q).
Если St – совокупность страниц в памяти верхнего уровня в момент t, причем в любой момент в этой памяти присутствует r страниц программы, то изменение состояния памяти верхнего уровня после обращения qt
описывается следующими соотношениями:
В первом случае обращение производится к странице, которая находится в памяти верхнего уровня, и поэтому состояние этой памяти не меняется.
Во втором случае происходит обращение к странице, отсутствующей в памяти верхнего уровня. Эта ситуация называется страничным сбоем, так как программа не может дальше выполняться, пока нужная страница qt
не будет переписана из памяти нижнего уровня в память верхнего уровня, что сопряжено с потерями времени. Поскольку в памяти верхнего уровня нет свободного места, из нее приходится удалять некоторую страницу vt с тем, чтобы на ее место можно было поместить страницу qt. Если во время пребывания страницы vt в памяти верхнего уровня в нее производилась запись, эта страница при замещении должна переписываться в память нижнего уровня. Такая процедура называется процессом замещения страниц, а правило, по которому при возникновении страничного сбоя выбирается страница vt Î St для удаления из памяти верхнего уровня, – алгоритмом замещения.
Для данной программы, порождающей некоторый поток обращений к памяти, существует, по крайней мере, одна такая последовательность замещений страниц, которая дает минимальное для этой программы число страничных сбоев – минимально возможную последовательность замещений. При конструировании алгоритма замещений стремятся приблизить реализуемую этим алгоритмом последовательность замещений к минимальной.
Оптимизация процесса замещений страниц упрощается, если известно, в каком порядке в будущем будут происходить обращения к памяти или, по крайней мере, вероятности обращений в будущем к отдельным страницам программы. Ясно, например, что в первую очередь из памяти верхнего уровня следует удалить страницу, к которой обращений больше не будет (вероятность обращений в будущем равна 0).
Трудность состоит в том, что, как правило, при выполнении программы отсутствуют информация о потоке обращений или сколько-нибудь достоверные сведения о вероятности обращений к отдельным страницам в будущие моменты времени.
Алгоритмы замещения можно разделить на две группы:
Хотя алгоритмы первой группы на практике применить нельзя, они играют важную роль в теории алгоритмов замещения, позволяя производить оценки (в том числе экспериментальные), в какой степени характеристики эвристических алгоритмов приближаются к предельно возможным оптимальным.
Физически нереализуемые алгоритмы
Алгоритм Михновского-Шора. При каждом замещении страницы из памяти верхнего уровня отсылается в память нижнего уровня страница, очередное обращение к которой произойдет позже, чем к любой другой странице в памяти верхнего уровня.
Справедливо следующее предложение. Число замещений страниц в памяти верхнего уровня (число страничных сбоев) при выполнении замещений по алгоритму Михновского-Шора является минимальным для заданных потока обращений и исходного распределения памяти, что имеет теоретическое доказательство.
Таким образом, алгоритм Михновского-Шора реализует минимально возможную для данной программы последовательность замещений, поэтому этот алгоритм называют МИН-алгоритмом.
Если условиться, что известна вероятность обращений к отдельным страницам программы, то оптимальным в смысле минимума среднего числа страничных сбоев является ОПТ-алгоритм: при каждом замещении страницы из памяти верхнего уровня отсылается страница, вероятность обращения к которой не больше, чем к любой другой странице в этой памяти.
Физически реализуемые (эвристические) алгоритмы замещения
Был предложен ряд алгоритмов этого класса.
Алгоритм случайного замещения (СЗ-алгоритм). При возникновении страничного сбоя из памяти верхнего уровня с равной вероятностью отсылается любая из находящихся там страниц.
НДИ-алгоритм. Из памяти верхнего уровня отсылается страница, наиболее давно использовавшаяся.
Алгоритм "первый пришел – первый ушел" (ПППУ-алгоритм). Отсылается страница, дольше других находившаяся в памяти верхнего уровня.
Алгоритм "последний пришел – первый ушел". Отсылается страница, позже других поступившая в память верхнего уровня.
Следующие два алгоритма обладают определенными свойствами адаптации к потоку обращений к памяти.
Алгоритм "карабкающаяся страница" (КС-алгоритм). Страницы в памяти верхнего уровня образуют последовательность:
При очередном обращении qt к памяти эта последовательность изменяется по правилу:
При обращении к странице jm, присутствующей в памяти верхнего уровня, последняя меняется местами с соседней слева страницей, другими словами, "карабкается" к началу последовательности, подальше от ее конца, куда происходит замещение при страничном сбое. Этот процесс иллюстрирует схема на рис. 9.18.
Алгоритм "рабочий комплект" (РК-алгоритм). Страницы в памяти верхнего уровня, использовавшиеся в течение заданного интервала времени, образуют "рабочий комплект". Страницы из этой памяти, не вошедшие в "рабочий комплект", формируют две очереди кандидатов на замещение:
- очередь страниц, в которые не вносились изменения, пока они присутствовали в памяти верхнего уровня;
- очередь страниц, в которые вносились изменения.
Замещение при страничном сбое производится по правилу: первый пришел из рабочего комплекта – первый ушел из памяти верхнего уровня. При этом сначала подлежат замещению страницы из первой очереди. Описанный алгоритм использовался еще в компьютерах IBM-360/370.
Предположим, что последовательность обращений q1, q2, …, qt соответствует последовательности независимых случайных дискретных величин, таких что
Примем за состояние процесса замещения набор (а в некоторых случаях упорядоченную последовательность) страниц, находящихся в памяти верхнего уровня. Тогда для ряда алгоритмов замещения (СЗ, НДИ, ПППУ и некоторых других) процесс изменения состояния верхнего уровня описывается однородной конечной эргодической цепью Маркова, что указывает на существование стационарных вероятностей пребывания процесса в определенных состояниях и, как следствие этого, стационарных вероятностей страничных сбоев.
В качестве критерия эффективности Wr,k алгоритма замещения А примем стационарную вероятность страничных сбоев:
Можно для ряда алгоритмов замещения найти зависимость Wr,k
от p1, p2, …, pk и сравнить алгоритмы между собой, а также с физически нереализуемым ОПТ-алгоритмом. Определить Wr,k
для ряда алгоритмов можно, используя метод, основанный на однородных эргодических цепях Маркова.
Описанные выше эвристические алгоритмы замещения страниц и их различные комбинации лежат в основе алгоритмов замещения, используемых в современных ЭВМ. При этом конкретные технические реализации алгоритмов замещения страниц весьма сложные и сильно зависят от конкретной конфигурации аппаратных средств, типа операционной системы и даже ее модификации. Следует отметить только, что в большинстве случаев алгоритмы замещения страниц в современных ЭВМ содержат механизмы упреждающей выборки страниц. Идея использования упреждающей загрузки страниц из ВП в ОП, как и в случае обновления блоков в кэш-памяти
(см. п. 9.3.3), основана на предположении о том, что при очередном страничном сбое обращение с большой вероятностью произойдет к следующей по порядку странице, уже находящейся в ОП. Кроме того, как уже отмечалось в п. 9.4.1, перемещение модифицированных страниц из ОП в ВП осуществляется в большинстве случаев через кэшированную часть ОП (дисковый кэш), поскольку велика вероятность обращения к недавно удаленной странице. Такой механизм позволяет ускорить процесс подкачки страниц при повторном обращении.
Более подробно вопросы организации виртуальной памяти в настоящем разделе не рассматриваются, поскольку относятся к области системного программного обеспечения компьютера (ядра операционной системы).
