с ИНИЦИАЛИЗАЦИЯ ПЕРЕМЕННЫХ С

J = 1

TOTAL =. Q

DO 10 I - 1,PAGES

TABLE!I) - a

FREQ(f) = В

ENTERftJ * 0 10 CONTINUE

С ЦШ IW СТРСКЕ ОБРаНЕНИЙ

DO 100 I = 1,М

с ПОЛУЧЕНИЕ 1-ГО ОБРАЩЕНИЯ И УВЕЛИЧЕНИЕ ЕГО ЧАСТОТЫ С

к- = REF(I)

FREQ(K) - FREQ(K) + 1

С НАХОДИТСЯ ЛИ К-Я СТРАНИЦА В ПАМЯТИ С

IF(TABLE(K) .NE. О) GO ТО 2q GO ТО 30

НЕТ СТРАНИЧНОГО ОТКАЗА

20 FAULT! I) => О

GO ТО 10G

С. СТРАНИЧНЫЙОТКАЗ

30. FAULT! и = 1

TOTAL => TOTAL + 1

С ВСЕ ЛИ СТРАНИЧНЫЕ ОБЛАСТИ ЗАПОЛНЕНЫ

IF!J .GT. FRAMES) GO TO 40 GO TO 90

С НАЙТИ НАИМЕНЕЕ ЧАСТО ИСПОЛЬЗУЕМУЮ СТРАНИЦУ

С ДЛЯ УДАЛЕНИЯ

" 40 Н . 1

Ml =. FRAMEI1)

MIN = FREQ(MI)

DO 80 L =. 2, FRAMES Ll = FRAME(L)

IF(MIN-FREQILI) ) 80,70,50 50 MIN = FREQ!L1)

60 H = L

Ml «.L1

GO TO 80

70 IF(ENTER(M1) - ENTER(LI) ) 80,80,60

80 continue

с УДАЛЕНИЕ НАИМЕНЕЕ ЧАСТО ИСПОЛЬЗУЕМОЙ СТРАНИЦЫ

С И РАЗМЕЩЕНИЕ СТРАНИЦЫ. К В ПАМЯТИ

Л = FRAME (М) f«AK£(M) .= К ENTER(K) =. I TABLE(К) » М TABLE(JI) - О GO ТО 10Q

С РАЗМЕЩЕНИЕ СТРАНИЦЫ К Б ОБЛАСТИ Л

90 TABLE<K) - J

F«AHE<J) -.К E«TEfi<H) - 1 J - J ♦ 1

100 CONTtNUE С .

С ПЕЧАТЬ РЕЗУЛЬТАТОВ С

WRITE (6,900) FRAMES .PACES 900 Р0ННАТ(1НО.39НАЛГОРИТН УПРАВЛЕНИЯ СТРАНИЧНОЙ ПАМЯТЬЮ , . 1 9H.LfU Ш ,13,12« ОБЛАСТЕЙ И .I3.8H СТРАНИЦ)

WRITE (6,950)

950 F0RHATi1W.37HCTP0KA ОБРАЩЕНИЙ И ПОСЛЕДОБАТЕЯЬ+ЮСТЬ, 1 6Н ОТКАЗОВ)

WRITE (6,1J30flJ ШГ( 13. I.I.N) WaiT£ (,6,MflO) .IFAULTJD.I-I.N) 1000 FQRMAT(1H0,4Dl3) С

С ПЕРВЫЕ =FRAHES= ОТКАЗОВ - СВОБОДНЫЕ С

TOTAL = TOTAL = FRAMES RATE = FLOAT(TOTAL) / (N-FRAHES) WRITE (6.1010) TOTAL,RATE ICIO F0RMAT(1HC.21H ЧИСЛО ОТКАЗОВ РАВНО ,I.3,10H A ЧАСТОТА, 1 7Н РАВНА ,F6.3)

RETURN ЕШ

7 8 9 10 11 12 13 14 15 16 17 18 19 20

А = В + С GO ТО 400

400 I = I + 1

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

1. За каждым обращением к странице с текстом программы будет следовать обращение к странице с данными в 98% случаев; в 2% случаев за ними будут следовать обращения к произвольно выбранной новой странице с текстом программы.

2. Страница данных выбирается по принципу «самого последнего обращения». С этой целью для запоминания страниц с данными в порядке самого последнего обращения используется стек. Новые страницы данных выбираются из вершины стека и ниже с соответствующими вероятностями 0.50, 0.25, 0.125, 0.0625, 0.03125 и т. д.

3. Если выбрана некоторая страница данных, за ней в 98% случаев следует обращение к предыдущей странице текста программы. В 2% случаев за ней следует другая произвольно выбранная страница с текстом программы.

4. Строка обращений длины iV= 10 ООО считается достаточной для того, чтобы произошли обращения ко всем страницам.

Рис. 5.4.6 показывает, какой могла бы быть типичная строка обращений к страницам, основанная на этих предположениях. На рис. 5.4.7 представлены результаты испытания пяти алгоритмов управления страничной памятью. Эти результаты позволяют предположить, что алгоритм LRU следует предпочесть алгоритмам RANDOM, FIFO и LFU - факт, подтверждаемый практикой.

Программа

Рис. 5.4.5. Предполагается, что каждая программа имеет 6 страниц текста программы и 14 страниц данных.

Упражнения 5.4

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