если необходимо, какую-нибудь из страниц, находящихся в памяти; это называется замещением страниц по требованию.

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

6. Как только затребованная страница помещена в память, выполнение первой программы возобновляется.

7. Когда возобновляется исполнение прерванной виртуальной программы, происходит обращение к той же странице; на этот раз страничного отказа не возникает.

В этом разделе мы обсуждаем в несколько идеализированном виде некоторые алгоритмические аспекты управления страничной памятью. Мы продемонстрируем несколько простых алгоритмов управления страничной памятью, интересных с теоретической или практической стороны, и испытаем их, чтобы выяснить, как они влияют на эффективность использования памяти в компьютере.

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

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

Мы обсудим следующие пять алгоритмов управления страничной памятью:

RANDOM (СЛУЧАЙНЫЙ). Этот алгоритм предполагает, что в любой момент времени обращения ко всем страницам равновероятны. Замещаемая страница выбирается случайно.

FIFO (первым пришел - первым ушел). Этот алгоритм всегда замещает страницу, которая дольше всех находилась в памяти. Его оправдание основано на принципе локальности программы, утверждающем, что число ссылок в программе между двумя последовательными замещениями страниц относительно велико. Иначе говоря, программы проявляют тенденцию к выполнению команд из данного множества страниц в течение некоторого времени, после чего переходят к другому множеству страниц. Следовательно, предполагается, что страница, дольше всех находящаяся в памяти, имеет наименьшую вероятность использования в будущем.

LRU (самое давнее обращение). Этот алгоритм замещает в памяти страницу, к которой самое продолжительное время не было обращений. При этом мы рассчитываем, что раз к этой странице не было обращений в недавнем прошлом, то их не будет и в ближайшем будущем.

LFU (самое редкое истльзование). Этот алгоритм следит за таблицей частоты обращений для всех страниц программы (как находящихся в памяти, так и вне ее) и замещает в памяти страницу, частота обращений к которой оказывается наименьшей. Оправданием этого алгоритма является то, что страницы программы проявляют тенденцию к делению на две категории: страницы, используемые часто (например, содержащие циклы DO), и страницы, используемые редко (например, содержащие операторы инициализации программы, операторы ввода/вывода или редко требующиеся данные).

BEST (НАИЛУЧШИЙ). Этот алгоритм представляет прежде всего теоретический интерес, так как он предполагает полное знание о всех предстоящих обращениях к страницам и всегда производит наилучший возможный выбор замещаемой страницы, т. е. замещает страницу, обращение к которой произойдет позже, чем к любой другой.

Как мы увидим, алгоритмы СЛУЧАЙНЫЙ и НАИЛУЧШИЙ весьма полезны, так как они являются эталонами, с которыми можно сравнивать трудоемкость любого другого алгоритма управления страничной памятью.

Ради простоты предположим, что входные данные для каждого из этих алгоритмов управления страничной памятью состоят из массива REF(l), . . ., REF(A/) целого типа, целого FRAMES, указывающего число доступных страничных областей и целого PAGES, указывающего число страниц в данной программе. Массив REF(l), . . ., REF(AA), называемый цепочкой обращений, представляет полную последовательность обращений к страницам, генерируемых при исполнении данной виртуальной программы, причем мы предполагаем, что эти страницы пронумерованы числами 1, 2, . . ., PAGES. Хотя на практике возможно, что цепочка обращений будет содержать много подпоследовательностей повторяющихся обращений к одним и тем же страницам, при изучении алгоритмов управления страничной памятью такие повторения номеров страниц мы будем считать несущественными. То есть мы будем предполагать, что REF(/)=/=REF(/+l) для /=1, . . ., Л-1.

Прежде чем рассматривать реализацию алгоритмов управления страничной памятью, рассмотрим пример, иллюстрирующий работу алгоритма BEST (наилучший). Предположим, что даны три страничные области памяти, в которых должна работать программа, состоящая из пяти страниц. Цепочка обращений при исполнении этой программы пусть будет: 12341253452 5.

На рис. 5.4.1 показана последовательность замещений страниц, выполняемых алгоритмом BEST. Хотя и можно сказать, что странич-

ные отказы происходят в строках 1, 2 и 3, мы их будем считать «свободными» замещениями. Заметьте, что при страничном отказе на строке 4 мы замещаем страницу 3, так как следующее обращение к ней

Рис. 5.4.1. Последовательность замещений страниц при использовании алгоритма BEST, т, е. замещается та страница в памяти, следующее обращение к которой

произойдет позже всех.

произойдет в момент времени 8, тогда как к страницам 1 и 2 произойдут обращения в моменты 5 и 6 соответственно. Заметьте также, что при равных возможностях (например, в строке 11) мы замещаем страницу с меньшим номером. Советуем читателю построить аналогичную таблицу замещения страниц еще хотя бы для одного алгоритма управления страницами, прежде чем продолжать чтение.

Мы оставляем реализацию алгоритмов RANDOM и BEST в качестве упражнений и сосредоточим внимание на реализации алгоритмов Firo, LRU и LFU.

Для реализации алгоритма FIFO организуем круговую очередь FRAME (1), FRAME (2), . . ., FRAME (М), где M=FRAMES - число страниц в оперативной памяти. Как только происходит обращение к новой странице, она помещается в первую попавшуюся свободную область до тех пор, пока все области не окажутся заполненными, после чего мы продолжаем загрузку новых страниц в области FRAME (1), FRAME (2) и т. д. Эта реализация показана на рис. 5.4.2.

Для реализации алгоритма LRU создадим таблицу страниц TABLE, в которой TABLE (/)=J, если в данный момент страница / находится в области памяти Для упорядочения множества страниц, находящихся в памяти в соответствии с наиболее давним обращением, используется список с двумя связями вперед и назад- BEFORE (/)