Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [ 85 ] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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

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, так как следующее обращение к ней

обращение к странице

Содержимое страничных, областей

Новое содержимое, страничных областей

свободное замещение

свободное замещение

свободное замещение.

->

отказ: 3 позже всех

->.

->.

отказ: 1 позже всех

отказ: 2 позже всех

->

->

->

отказ: 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 (/)



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [ 85 ] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0017