Устройство для управления виртуальной памятью

Устройство для управления виртуальной памятью

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике, может быть использовано в вычислительных машинах с виртуальной памятью ,и позволяет осуществить оптимальное распределение страниц оперативной памяти между активными задачами. С этой целью в состав устройства для управления вирту-. апьной памятью по авт. ев. К 955076 введен блок управления страничным обменом, который по результатам анализа числа страничных сбоев и числа успешных обращений к оперативной памяти позволяет с помощью аппаратных средств перераспределить страницы оперативной памяти между активными задачами. 21 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„SU„„13271

А2 (51)4 G 06 F 12/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 955076 (21) 4029267/24-24 (22) 25.02.86 (46) 30,07.87. Бюл. У 28 (72) Э.В.Борисов, С.В.Горелов,П.В.Токарев и О.В.Чикало (53) 681.325 (088.8) (56) Авторское свидетельство СССР

11r 955076, кл. G .06 F 12/08, 1980. (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ВИРТУАЛЬНОЙ ПАМЯТЬЮ (57) Изобретение относится к вычисли.тельной технике, может быть использо-. вано в вычислительных машинах с виртуальной памятью,и позволяет осуществить оптимальное распределение страниц оперативной памяти между активными задачами. С этой целью в состав устройства для управления вирту-. альной памятью по авт. св.

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

1327!

Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах с виртуальной памятью, С>

Цель из обре тения — расширение функциональных возможностей путем обеспечения динамического оптимального перераспределения страниц ОП между активными задачами. 10

На фиг ° 1 приведена функциональная схема устройства для управления виртуальной памятью; на фиг. 2 — схе,ма блока входных регистров, на фнг, 3схема блока выходных регистров; на фиг. 4 - схема формирователей; на фиг, 5 — схема блоков сравнения; на фиг. 6 — схема компаратора, на фиг, 7схема блока местного управления; на фиг. 8 — схема блоков памяти страниц; 20 на фиг. 9 - схема элемента памяти; на фиг. 10 †-схема генератора расстановки; на фиг. Il - схема блока управления замещением; на фиг. 1? — схема узла приоритета; на фиг, 13 - схема 2б блока коррекции; на фиг. 14 — схема блока управления страничным обменом; на фиг. 15 — схема блока определения числа страничных сбоев; на фиг. !6 ,схема блоков расстановки; на Фиг. 17 30 схема первого блока сравнения; на фиг ° 18 — схема второго блока сравнения, на фиг. 19 — схема формирователя адреса обмена страниц; на фиг. 20— временная диаграмма тактовых импульЗБ сов; на фиг. 21 — пространство состояния активной задачи в оперативной памяти

Устройство для управления виртуальной памятью (фиг, 1) содержит блок I входных регистров, блок 2 выходных регистров, управляющий регистр 3, регистр 4 общего назначения, блоки 5 сравнения, блок 6 местного управления, блоки 7 памяти страниц, генератор 8 расстановки, блок 9 управления замещением, блок 10 коррекции, блок 11 управления страничнъгм обменом, вход 12 оператинной памяти„ вход 13 задания режима, вход 14 синхронизации, вход 15 задания кода операции устройства, входы 16-24 блока 6 местного управления, вход 25 управления прерыванием блока 6 местного управления, выходы 26 — 31 блока б местного управления, дополнительный выход 32 блока 6 местного управления, вход 33 устройства, информационный выход 34 блока i входных регистров, 3

2 выход 35 сигнала и ре рын ан ия, информационньгй выход 36 устройства, Блок 11 управления страничным обменом (фиг, 14) содержит блоки 37 определения числа страничных сбоев, первый 38 и второй 39 блоки расстановки, первый 40 и второй 41 блоки сравнения> первый — четвертый дешифраторы 42 — 45, первый 46 и второй 47 сумматоры, первую — четнертую группы 48 — 51 элементов памяти, перную— четвертую группы 52 — 55 блоков нычисления, блок 56 вычисления, группу 57 формирователей, элемент И-ИЛИ 58.

Блок 37 определения числа страничных сбоев (фиг. 15} содержит первый 59 и второй 60 элементы И, первый — третий счетчики 61 — 63, элемент ИЛИ 64.

Первый блок 40 сравнения (фиг. 17 ) содержит первый 65 и второй 66 регистры, блок 67 поразрядного сравнения, коммутатор 68, группу 69 триггеров, элемент 70 задержки, группу 71 элементов И, элемент И 72.

Первый 38 и второй 39 блоки расстановки имеют одинаковую конструкцию (фиг. 16) и содержат группу 73 регистров, группу 74 блоков поразрядного сравнения, группу 75 элементов И, группу 76 элементов ИЛИ, группу 77 регистров перезаписи, дешифратор 78, коммутатор 79, группу 80 регистров памяти.

Второй блок 41 сравнения (фиг. IS) содержит блок 81 памяти, группу 82 регистров памяти, группу блоков 83 сравнения, группу 84 И элементов, группу элементов 85 И, Формирователь 57 группы (фиг.19) соцержит первый 86 и второй 87 входные регистры, блок 88 поразрядного сравнения, первый 89 и второй 90 элементы И, выходные регистры 91 и 92, элемент ИЛИ 93.

Блок входных регистров (фиг. 2) содержит регистр 94 логического адреса, вычитатель 95, группу 96 элементов И, выходы 97-99 регистра 94 логического адреса> выходы 100-104 управляющего регистра 3.

Блок 7 памяти страниц (фиг. 8) содержит группы 105-1)5 элементов памяти> регистры 116 и 117, дешифратор 118, элементы И 119 — 134, элементы ИЛИ 135 — 138. з 13

Блок 5 сравнения (фиг. 5) содержит. компаратор I 39, регистр 40, элемен.ты И 141 и 142 °

Генератор 8 расстановки (фиг. 10) содержит группу 143 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, коммутатор 144 и дешифратор 145.

Блок 9 управления замещением (фиг. 11) содержит элементы ИЛИ !46, дешифратор 147, коммутаторы 148 и узел 149 приоритета.

Блок 10 коррекции (фиг. 13) содержит дешифратор 1 50, элементы И 151 — 154 и элементы ИЛИ 155.

Блок 2 выходных регистров (фиг. 3) содержит регистр 156 физического адреса, регистр 157 замещаемой страницы, регистр 158 флажков, коммутаторы 159.и 160, формирователи 161 и !62 и элемент ИЛИ 163.

Элемент памяти групп 105-1 15 бло. ка 7 памяти страниц (фиг. 9) содержит дешифратор 164 адреса, информационный регистр 165, группу 166 элементов И и коммутатор 167.

Компаратор 139 (фиг.6) содержит элемент ИЛИ-НЕ 168 и в каждом разряде элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 169, Узел 149 приоритета (фиг. 12) блока 9 управления замещением содержит элементы И 170 и элементы ИЛИ 171.

Формирователи 161 и 162 (фиг. 4) содержат элементы ИЛИ 172 (предполагается, что устройство содержит два блока памяти страниц).

Блок 6 местного управления (фиг.7) содержит второй — седьмой 173 - 178, тринадцатый — пятнадцатый 179 — 181, восьмой — двенадцатый 182 — 186 и первый 187 элементы И и шестой 188, пятый 189, первый — четвертый 190—

193 элементы ИПИ и триггеры 194 и!95.

Устройство для управления вир.туальной памятью работает следующим образом.

Режимы работы устройства определя. ются путем возбуждения устройством управления процессора соответствующего входа блока 6 местного управления.

Во время выполнения операции, связанной с обращением к ОП, устройство управления процессора возбуждает вход 17 блока 6, Если бит слова состояния программы, определяющий режим преобразования адресов, не установлен, то во время действия импульса СО открывается элемент И 181, сигнал с

271!3

4 выхода которого через элемент ИЛИ 189 производит запись в регистр 156 физического адреса, поступающего на вход регистра 156 через коммутатор 159 блока 2 выходных регистров.

Если процессор работает в режиме преобразования адреса, то устанавливается соответствующий бит слова состояния программы и указанная выше информация загружается в управляющий регистр 3, сюда же передается инфор" мация о количестве страниц, минимально необходимых для выполнения каждой активной задачи,а также информация о длине задачи в страницах, определяемой значением параметра REGION оператора EXEC. Во время выполнения операции, связанной с обращением к оперативной памяти, устройство управления возбуждает вход 17 блока 6 местного управления. Тогда во время действия импульса CO открывается эле" мент И 1 85, по сигналу с выхода 27.

25 которого логический адрес записывается в регистр 94 логического адреса блока l входных регистров. В блоке 1 адрес виртуальной страницы формируется так же, как в устройстве-прототи"

30 пе, Разряды адреса виртуальной с1раницы, кроме смещения, поступают на входы группы 143 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ генератора 8 расстановки, результат с выхода которой через ком-- мутатор 144 поступает на адресные входы групп 105-1!5 элементов памяти каждого из блоков 7 памяти стра" ниц, Информация; прочитанная с выб" раиной ячейки групп 105 - !07, 113 и 1!5 элементов памяти поступает в соответствующий блок 5 сравнения.

Одновременно информация с выбранной ячейки групп 105 - 107 элементов памяти каждого из блоков 7 поступает на соответствующие входы блока 40 сравнения входных адресов блока 11 управления страничным обменом. В блоке 40 по информации из группы 105—

107 элементов памяти определяется ко-. личество страниц оперативной памяти, 50 относящихся к каждой активной задаче. Условия удаления страниц из оперативной памяти, сформированные элементами И 121 - 125 блока 7, и соответствующая информация из групп 108, 110 — 113 элементов памяти записывается в регистры .116 и 1!7 соответственно сигналом с выхода 30 блока 6 местного управления, поступающим че"

5 l 327 l рез открытый элемент И 179 но время действия импульса Cl. В блоке 5 производится сравнение адресов виртуальных страниц. поступающих с блоков входных регистров и блоков 7 памяти страниц.

Если сравнение произошло, выбранная строка групп 105-1!5 элементов памяти загружена и данная страница не используется н операциях ввода- !0 вывода, то это указывает Hà "".o что требуемая виртуальная страница находится в оперативной памяти и доступна. Эта ситуация запоминается в регистрах 140 каждого из блоков 5 по сигналам, поступающим с выхода 29 открытого элемента И 179 во время действия импульса Cl и характеризует успешное обращение к странице оперативной памяти. Эта информация с 20 выхода коммутатора 76 блока 5 поступает на перный вход соответствующего блока 37 определения числа страничных сбоев. Сигналы с выходов элементов И 141 поступают в блок 2 на эле- 25 мент ИЛИ 163, с помощью которого определяется, находится ли требуемая страница в оперативной памяти и раз.решено ли к ней обращение. Эта ситуация запоминается в триггере 194 во 30 время действия импульса Cl по сигналу, поступающему на вход синхронизации триггера 194 через открытый элемент И 179, Если сравнение произошло, выбранная строка групп 105-115 элементов памяти загружена, но данная страница используется в операциях ввода-вывода, то это указывает на то,, что требуемая виртуальная страница находится в оперативной памяти, но недоступна для обрашений со стороны процессора. Эта ситуация запоминается н триггере 195 (единичное состояние) во время действия импульса Cl по счг- g5 калу, поступающему на вход синхронизации триггера 195 через открытый элемент И 179. Это условие формируется элементами И блоков 5 и элементом И 190 блока 6.

Если с помощью элемента ИПИ 163 установлено, что доступ к виртуальной странице возможен (единичное состояние триггера 194, то ее сформированный физический адрес записывается н регистр 156 физического адреса по сигналу с выхода 28 блока 6 местно-. го управления, поступающему на уп-. равляющий вход регистра 156 физичес 13 б кого адреса через элемент ИЛИ 184 и открытый элемент И 180 во время действия импульса C l Физический адрес страни ъ поступает на вход регистра 156 через коммутатор 159. Физический прес формируется как ".анокупность номера блока 5 сравнения, где произошло опознание виртуальных адресон, кода, поступающего с выхода коммутатора 144 генератора 8 расстановки, и смещения, поступающего с выхода 99 регистра 94 логического адреса. Двоичный код номера блока 5 . сравнения Ьормируе,est формирователем 161. После этого производится коррекция страничнои таблицы, заключающаяся и установлении битов обращения и битов изменения, если обращение в оперативную память производилось для записи информации. Дпя этого во время действия импульса С2 открывается элемент И 178, сигнал с выхода 30 которого поступает на элемент И 132 каждого из блоков 7 памяти страниц.

Содержимое регистров 140 блоков 5 сравнения поступает на нторые входы элементов И 132 соответствующих блоков 7 памяти страниц. Так как опознание виртуального адреса возможно только в одном из блоков 5 сравнения, то открываются элементы И 119, 120, 132 и 134 соответствующего блока 7 памяти страниц. Элементы И 119 и 120 определяют установку информации на входы групп 108 и 109 элементов памяти соответствующего блока 7 памяти страниц, а открытый элемент И 132 разрешает прохождение сигнала записи на управляющие входы групп 100 и 109 элементов памяти, Запись в группу 109 элементов памяти производится только при установке триггером кода. операции, определяющего запись информации н оперативную память, В этом случае

oTKpbIT элемент И 134е

После формирования условий для определения свободной или возможно замещаемой страницы они анализируются блоком 9 управления замещением, Сформированный адрес нозможко замещаемой страницы и способ ее замещения помещаются н регистр 157 замещаемой страницы и в регистр 158 флажков соотнетстненно по сигналам с выхода 28 элемента И 182 но время действия имгульса С2.

Если триггеры 194 и 195 находятся в нуленсм состоянии, то зто определяет, что требуемой виртуальной страницы

) 327) I нет в операти«ной памяти, что соответствует страничному сбон>. Эта информапия через элемент И 186 поступает на «торой «ход соответст«ующего (> блока 37 определения числа страничных сбоев. Если хотя Сы в двух блоках 37 число успешных обращений К к оперативной памяти или число страничных сбоев D достигают своих критичес- ) ких значений К или D, которые выкр бираются с учетом специфических характеристик потока задач, решаемых в данной вычислительной системе, или могут быть получены в результате ими- )5 тационного моделирования вычислительного процесса, то информация об этом с первых выходов соответствующих блоков 37 через элемент И-ИЛИ 58 поступает на дополнительный вход 25 блока 6 и открывает элемент И 187, сигнал с выхода 26 блока 6 вызывает прерывание, определяющее, что необходимо провести перераспределение страниц оперативной памяти между активными задачами ° После обработки этих прерываний операционная система передает в блок ll управления страничным обменом. через блок входных регистров для каждой задачи, участвующей в страничном обмене, минимально, допустимое число страниц оперативной памяти, необходимое для решения каждой задачи, и длину задачи в страницах оперативной памяти.В блоке llопределяются пары задач, находящиеся одновре35 менно в оперативной памяти, например задаче, имеющей наибольшее избыточное. число страниц, ставится в соответствие задача,требующая наибольшего числа

40 страниц оперативной памяти для успешного завершения. В блоке ll определяется количество страниц, которые будут участвовать в обмене, и формируются адреса обмена в группе бло45 ков 57, которые с выхода блока 11 поступают на вход дешифратора !50 блока 10 коррекции, в котором анализируются адреса задач, участвующих в обмене и условия обмена. В реэуль1

50 тате такого анализа по сигналу дешифратора 150 производится смена номера задачи в группе )06 элементов памяти блоков 7 путем передачи в группу 106 . блоков 7 памяти страниц "дающих" задач, номеров берущих" задач. При действии импульса С) открывается элемент И 173 блока 6, сигнал с выхода 30 которого и сигнал с выхода эле3 8 мел та И. )!! l 88 открывают элема нт И )? 6 того блока 7, который выбран дешифраторо» 45 т енератора 8. Сигнал с выхода открытого элемента И 126 поступает на управляющие входы группы 06 элементов памяти, разрешая запись нового номера активной задачи, участвующей в страничном обмене, с выхода дешифратора 150 блока 10 коррекции °

После завершения цикла страничных обменов между задачами, одновременно находящимися в оперативной памяти, устройство продолжает работать в режиме динамического преобразования адресов до тех пор, пока не будут снова достигнуты значения K ð или D „ð хотя бы для двух активных задач, При обращении к внешней памяти блок 10 коррекции анализирует условие, сформированное дешифратором 147, которое определяет, возможно ли осуществить замещение или ввод требуемой страницы. Если это возможно, то в соответствующей строке страничной таблицы устанавливается бит-указатель ожидания ввода-вывода. Для этого сигнал с выхода открытого элемента И 154 блока 10 коррекции поступает на элементы И 130 каждого из блоков 7 памяти страниц. В выбранном узлом 149 приоритета блоке 7 памяти страниц открывается элемент И 130 при наличии сигнала с выхода 30 элемента И 177 блока 6 местного управления, и во время действия импульса С2 осуществляется запись в группу 113 элементов памяти.

Информация на входе группы 113 элементов памяти каждого иэ блоков 7 памяти страниц устанавливается с выхода элемента ИЛИ 155 блока 10 коррекции.

Если при анализе условий блоком 10 коррекции установлено, что ввести требуемую страницу невозможно, то: бит-указатель ожидания ввода-вывода страничной таблицы не помечается.

Если.требуемойвиртуальной страницы нет в оперативной памяти, то во время действия импульса С2 открывается элемент И 183„ сигнал с выхода 26 которого.вызывает прерывание, определяющее, что требуемой виртуальной страницы нет в оперативной памяти, Если триггер 194 находится в нулевом состоянии, а триггер 195 - в единичном, то это означает, что требуе" мая виртуальная страница находится в оперативной памяти, но использует10

9 13271 3

20 ся системой ввода-вывода. Поэтому никакая строка страничной таблицы не помечается, так как сигнал с выхода триггера 195 закрывает элемент И 177, а в момент действия импульса С2 открывается элемент И 184, что вызывает прерывание, определяющее, что процессору разрешено обращаться к странице, которая используется системой ввода-вывода.

При выполнении операций ввода-вывода необходимо ус.тановить бит-указатель ожидания ввода"вывода в страничной таблице для реальных физичесКНх t It HHU oIIeDBTHBHoH .tMtt, t Которым производится обращение при вь:— полнении этих операций, IIîñëå окончания операции ввода-вывода бит-указатель ожидания ввода-вывода сбрасывается.

Для выполнения таких действий процессором в младшие разряды регистра 4 общего назначения устанавливается адрес реальной физической страницы, в соответствующий старший разряд — код, определяющий установку или сброс бита-указателя ожидания ввода-вывода, а устройство управления процессора возбуждает вход 18 блока 6 местного управления. Таким образом, младшая часть физического адреса страницы с выхода регистра 4 общего назначения через коммутатор 144 генератора 8 расстановки поступает на адресный вход групп !05-115 элементов памяти каждого из блоков 7 памяти страниц, Старшая часть физического адреса страницы дешифруется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один из блоков 7 памяти страниц, т,е ° соответствующая часть страничной таблицы. Код установки или сброса бита-указателя ожидания ввода-вывода поступает на- вход группы 113 элементов памяти каждого из блоков 7 памяти страниц через элементы ИЛИ 155 151 В момент действия импульса Сl открывает я элемент И, сигнал с выхода 30 которого открывает элемент И 129 того блока 7 памяти страниц, который выбран дешиф ратором 145 генератора 8 расстановки, Сигнал с выхода открытого элемента И il29 через элемент KIP, 136 поступает на управляющий вход группы 113 элементов памяти, вызывая запись инФормации, поступающей на вход элементов I 5 птмяти, с як хола зле tt..ttт» ИЛИ 55 блока 10 коррекции.

При первоначальной загрузке физической cтраницы в оttE!Itативную память или очистке оперативной памяти необходимо установить или сбросить битуказатель запрещения удаления страниц и бит-указатель действительности строки страничной таблицы. Дчя выполнения таких действий процессор устанавливает в младших разрядах регистра 4 обще"o назначения адрес реальной физической страницы, в соответствующих старших разрядах — биты, определяющие действительность строки страничной таблицы, и код, определяющий запрещение удаления страниц из оперативной памяти, а устройство управления процессора возбуждает ьход 19 блока 6 местного управления.

Таким образом, младшая часть Физи ческого адреса страницы с выхода регистра 4 общего назначения через ком25 мутатор 144 генератора 8 расстановки поступает на адресные входы групп 105115 элементов памяти каждого из блоков 7 памяти страниц. Старшая часть физического адреса дешифрируется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один из блоков 7 .памяти страниц, т.е. соответствующую часть страничной таблицы.

Коды установки битов-указателей за-. прещения удаления и действительности

35 строки страничной таблицы поступают на входы групп 114 и 115 элементов памяти каждого из блоков 7 памяти страниц через элементы И 152 и 153

40 блока 10 коррекции, В момент действия импульса Cl открывается элемент И 175 и через элемент ИЛИ 188 сигнал с выхода 28 элемента KIH 188 открывает элемент И 128 того блока 7 памяти страниц, который выбран дешифратором 145 генератора 8 расстановки.

Сигнал с выхода открытого элемента. И 128, поступающий на управляющие входы групп !14 и 115 элементов памяти, вызывает запись информации, по56 ступающей на входы -рупп 11 и 115

/ элементов памяти с выхода элементов И 152 и 153 блока 10 коррекции соответственно.

При первоначальной загрузке виртуальной страницы в оперативную память информация о6 этой странице записывается в соответствующую строку страничной таблицы. При этом устll 132711 ройстно управления процессора возбуждает вход 20 блока 6. Так как страница вводится в оперативную память только в том случае, если к ней было обращение, то физический адрес спера5 тивной памяти, куда будет загружаться виртуальная страница, находится в регистре 157 замещаемой страницы.

Процессор помещает адрес физической страницы из соответствующих разрядов регистра 157 замещаемой страницы в младшие разряды регистра 4 общего назначения, в соответствующих старших разрядах которого размещаются информация о запрещении удаления страницы иэ оперативной памяти и бит действительности строки страничной таблицы. Адрес виртуальной страницы размещается в регистре 94 логического адреса блока 1 входных регистров, куда записывается по сигналам с выхода 27 блока 6 местного управления через открытый элемент И 185.

Таким образом, младшая часть фи- 25 эического адреса с выходов регистра 4 общего назначения через коммутатор 144 генератора 8 расстановки поступает на адресный вход групп 105—

115 элементов памяти каждого из блоков 7 памяти страниц. Старшая часть физического адреса дешифрируется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один из блоков 7 памяти страниц, т.е. соот35 ветствующую часть страничной таблицы.

В момент деиствия импульса Cl открывается элемент И 173 блока 6, сигнал с выхода 30. которого и сигнал с выхода элемента ИПИ 188 открывают эле- 40 менты И 126 — 128, 331 и 133 того блока 7 памяти страниц, который выб-. ран дешифратором 145 генератора 8 расстановки. Сигналы с выходов откры" тых элементов И !26 — 128, 131 и 133 поступают на управляющие входы групп

105 — 112, 114 и 115 элементов памяти, вызывая запись информации, поступаюшей на входы групп 105 — 112, 114 и 1 15 элементов. На входах групп 105 - 107 элементов памяти устанавливается номер виртуальной страницы с выхода блока 1 входных регистров. На входах групп 108 и 109 элементов памяти устанавливается логический нуль, так как элементы груп5S пы 119 и 120 закрыты. На входах группы 110 элементов памяти дешифратором 118 устанавливается значение ло(3) (4) 3 12 гической единицы, а на входах групп ill и !12 элементов памяти— значение логического нуля (загружаемая страница включается в множество наиболее часто используемых страниц), Информация на входах групп 114 и 115 элементов памяти определяется содержимым соответствующих старших разрядов регистра 4 общего назначения. Эта информация через элементы И 152 и !53 блока 30 коррекции поступает на входы групп 114 и 115 элементов памяти.

Математическое обоснование опти" мального страничного обмена в ОП меж" ду активными задачами таково.

Пространство состояния задачи (фиг. 2!), находящейся в оперативной памяти, может быть охарактеризовано следующими параметрами:

L; — число страниц, необходимое для решения i-й задачи, длина задачи в страницах (определяется параметром

REGION в операторе EXEC);

D- — число текущих сбоев, N число различных страниц i-й задачи, к которым произошло обращение за время накопления D сбоев;

Х; — число страниц ОП, выделенных для i-й задачи на момент D сбоев

L. — минимально требуемое число

1 страниц для решения i-й задачи;

К - число успешных обращений к страницам i-й задачи. .Алгоритм оптимального управления страничным обменом в ОП между актив" ными задачами.

При достижении в процессе решения

i-й задачи В,к сбоев или К„успешных обращений к ОП (Вк и К„ являются постоянными коэффицйентамй для всех активных задач) вычисляются для этой задачи коэффициенты: л л л Na; я Эт

Х i Ь ° (l )

1 1 а также

1 где Ы вЂ” общее число активных задач.

Затем общее количество активных задач в ОП разбивается на два подмножества: подмножество задач с избытком страниц ОП вЂ” "дающее" I и под1 множество задач с недостатком стра- . ниц ОП вЂ” "берущее" I6 путем проверки условий:

I6 ) i/"; ) Ae 3

I Ф m i i/3 4 „3.!3 !32

"Дающее подмножество по !. упоряI дочивается путем расстановки элеменл л тов 1 от Л до Л; месх „ р

Для элементов берущего подмножества I определяются коэффициенты и и элементы I упорядочиваются

1 щсп р от ". до 3 . Далее производят Мел Влн лерераспределение страниц ОП между активными задачами, учитывая тот факт, что задача с min и ; может отдать максимальное число страниц„ а задача с max J!è; может принять максимальное число страниц ОП:

K in(L,.-х,,х.-L I,isI<, х . (5)

При этом обмен между i-й и j-й задачами производится таким образом, чтобы.полностью удовлетворить i-ю задачу, если ь - х < х - ь

) 1 (6) либо полностью освободить j-ю задачу от избыточных страниц ОП, если ь ° -х "х -ь

1 J J (7)

Вместе с тем при . 3 удовлетвоl J рить задачи из множества T - эа счет задач из множества Т не представляется возможным. Это условие также может служить основанием для выбора величин К „и D „

Блок 11 управления страничным обменом (фиг, 2-) работает следующим образом.

При первоначальной загрузке виртуальной страницы оперативной памяти информация об этой странице записывается в соответствующую строку страничной таблицы в группы 105 — !!5 элементов памяти блока 7. Одновременно из групп 105 — 107 элементов информация: номер виртуальной машины и номер виртуальной памяти (группа элементов 105); номер задачи (группа элементов 106); номер сегмента и номер страницы (группа элементов 107)— поступает в блок 40 сравнения входных адресов страниц. В блоке 40 сравниваются адреса, записанные в группах 105 — 107 элементов, и определяется, сколько страниц оперативной памяти - Х относится к каждой задаче, поступившей на выполнение. Эта информация из блока 40 поступает в первыйи-й блоки памяти, причем в перwA блок каждой группы поступает информация о первой задаче, во второй о втовой и т.д. Количество блоков па7! !3

J4 мяти соответствует числу страниц oIIeративной памяти. На другой вход блоков памяти группы 48 через дешифратор 42 поступает из группы )09 эле5 ментов блока 7 число обращений к страницам данной задачи — N>, первый

1 выход каждого блока памяти группы 48 подключен на вход сумматора 46, в котором производится подсчет общего количества задач, одновременно находящихся в оперативной памяти, по числу блоков памяти группы 48, в которые поступила информация, Вторые и третьи выходы укаэанных блоков 48 памяти подключены на входы блоков вычисления 1,. группы 52, выходы которых подключены на входы блока 38 расстановки и на входы сумматора 47, в кол тором производится вычисление !

В блоке 38 расстановки производится определение максимального коэффициента 4 и последующих и ° до ll при этом на первый вход блока 38 раси становки .поступает Л „, а на последний — и;„, С выходов сумматоров 46 и 47 информация поступает на входы блока 56, в котором производится.вычисление среднего значения по формуле

Л и

Выход блока 56 подключен на первый вход блока 41 сравнения с 1, на остальные входы которого поступают

35 значения коэффициентов. от М до л плах с выходов блока 38 расстановФл с и ки„при этом й„, х поступает на второй вход блока 41, h „„, — на третин и т.д,, на последний вход бло.ка 41 поступает 3" «„с последнего выхода блока 38, В блоке 4! сравнения с h множество п разделяется на два подмножества: подмножество задач с избытком страниц оперативной

45 памяти (1, 1. -. Л,, подмножество зал и ср дач, испытывающих недостаток страниц, оперативной памяти (Х,h с Л " ). Номера задач иэ множества I поступают на первую группу входов дешифратора 44, на вторую группу входов которого поступают иэ блока 1 входных -рео гистров значения L, для всех активных задач, на третью группу входов:

56 дешифратора 44 поступают значения Х

1 из блоков 48 памяти группы, при этом на выход дешифратора 44 проходят знас и чения Х! и Ь;, соответствующие 61>, таким образом„ что на первую пару

15 13?711 входов дешифра тора 44 по ступают Х, ( и L, соответствующие А из мноt tACll 1 жества I,,на последнюю пару выхоо л дов — X „ и Ь, соответствующие ;„ ° .)

Первая пара выходов дешифратора 44 подключена на входы первого блока 50 памяти группы, в который записываются значения Х,. и L ., соответствующие задаче с .1", из I, а последняя 1g группа выходов дешифратора 44 — к последнему блоку памяти группы 50, в которой записываются значения Х„, L„, соответствующие A . из I>. Выmi tt ходы блоков 50 памяти группы подключены на входы блоков 54 вычисления группы, в которых для каждой задачи иэ множества Т производится вычисление выражении Х -Ь, j E Е, и этот

> результат с номером задачи, к которой он относится, передается с выхода соответствующего блока памяти . . группы 54 на первый вход соответствующего формирователя адреса страничного обмена группы 57. Номера задач р из множества Еб поступают на первую группу входов дешифратора 43, на втоpyto группу входов которого из блока l поступают значения Ь., на третью группу — сигналы с выходов бло- З0 ков 37 определения текущего числа сбоев страниц оперативной памяти.

Дешифратор 43 пропускает значения

d., Ь,. для каждой задачи из множества I на входы соответстнующих блоб 35 ков памяти группы 49, выходы которых подключены на входы соответствующих блоков группы 53, в которых производится вычисление Л по формуле

d — для каждой задачи из множест- 4о

L; ва I . Значения 1. с выходов соответ1 ствующих блоков группы 53 поступают на входы блока 39 расстановки, который функционирует так же> как . 45 блок 38 расстановки. На первом выходе блока 39 расстановки формируется номер задачи, для которой " „, на последнем — номер задачи1 у которой

Укаэанные номера поступают на 50 первую группу входов дешифратора 45, на вторую группу входов которого по ступают значения L. иэ блока I, на третью — значения Х. иэ блокон памя1 ти группы 48. На первую пару выходов дешифратора 45 поступают значения

Х,Ь, соответствующие задаче из множества I,,для которой 3" „„, на лоб следнюю пару дешифратор 45 пропуска3 16 ет значения X, L задачи из множеств ва Т, для которой 3",. Первая пара выходов дешифратора 45 подключена на вход первого блока памяти группы 51, в который поступают значения

Х;, L для задачи Х, е Е, у которой и т.д., последняя пара выходов подключена на входы последнего блока памяти группы 51, в который записываются значения Х„, L для эадачи I, у которой М",.„, Выходы блоков памяти группы 51 подключены на входы соответствующих блоков вычисления группы 55, в которых производятся вычисления величин К = L;-X; для каждой задачи из множества I результаты вычислений с выходов блоков группы 55 поступают на вторые входы формирователей адресов группы 57 страничного обмена, выходы которых подключены к первой группе входов дешифратора 150 блока 10 коррекции. При этом на входе каждого формирователя адреса группы 57 формируется адрес страничного обмена, включающий н себя номер задачи, отдающей страницы К, номер задачи, берущей страницы N3, и число страниц, участвующих в обмене, К или К . Сформиронанные адреса поступают на первую группу входов дешифратора 150 блока 10, на вторую группу входов которого из блока 116 поступают адреса страниц, наи менее используемых и принадлежащих задачам, между которыми производится страничный обмен, Страничный обмен между активными задачами фактически заключается в замене в группе элементов 106 памяти блока 7 номера задачи, отдающей страницы, на номер задачи, берущей страницы, при этом количество страниц в которых

l будет проведена смена номеров задач, определяется в соответствующем формирователе 57 адреса группы иэ выражения

К=ппп(Е.. -Х.,Х.-L-j,ie I<, jå Е

Задача иэ множества Ig у которой и берет максимальное число страниц, задача из множества I, у которой 1 .„, отдает максимальное число страниц..Для таких пар задач величиы13 их характеризующие — Х,1 Е" о 1

Е 6) 1 K L (jeI t1) поступают че рез соотнетствуюшие блоки вычисления группы 54, в которых определяются sначения К = Х; - L, на входы одногс

% .1 1 °

13271 формирователя группы 57, и именно между такими задачами производится страничный обмен таким образом, что

11 II либо дающая задача полностью осво5 бождается от избыточных страниц„ли-бо берущая" задача полностью удовлетворяется недостающими страницами.

Блок 11 управления страничным обменом начинает функционировать, если хотя бы для двух задач достигну гы значения Э или Кщр, которые формируются по информации, поступающей на входы блоков 37 определения числа страничных сбоев с выхода компаратора 139 блока 5 и выхода триггера 194 блока 6. Сигналы о достижении К „р илн

D " вторых выходов блока 37 посту-пают на входы элемента И-ИЛИ 58, с выхода которого поступает сигнал на дополнительный вход 25 блока б, по которому формируется прерывание, поступающее на выход 26 блока 6 и обрабатывающееся в операционной системе, За время обработки этого прерыва- 25 ния по сигналам от операционной системы блок 11 производится перераспределение страниц оперативной памяти между активными задачами.

Блок 37 определения числа странич- ЗО ных сбоев (фиг. 15) включает элемент И 59, элемент И 60 с первым инверсным входом, на входы которых поступают сигналы с выходов компаратора !39 блока 5 и триггера 194 блока 6.Если страница,к которой происхо35 дит обращение, находится в оперативной памяти, то оба сигнала присутствуют на входе элемента И 59, что свидетельствует об успешном обращении к оперативной памяти, Импульс с выхода элемента И 59 поступает на вход счетчика 61 успешных обращений Ко„ не другой вход которого предварительно подается код числа К„, который пер45 воначально устанавливается в счетчике 61. Если с выхода триггера 194 сигнал не поступил, зто свидетельствует об отсутствии требуемой страницы в оперативной памяти и наступае " страничный сбой — обращение к внеш50 ней памяти. В этом случае сигнал не поступает на первый инверснъй вход элемента И 60, а на второй вход поступает сигнал с выхода компаратсра 139 блока 5. Импульс с выхода эле- 55 мента И 60, свидетельствующий о страничном сбое, поступает на вход сче."чика 62, в котором предварительно ус-.

13 18 тановлен код числа D „и одновременно на вход сче чика 63, в котором подсчитывается текущее число страничных сбоев Т3, При переполнении (доститенги D или К,1 одного из счетКр чиков 61 или 62 имлульс переполнения с выхода элемента ИЛИ 64 поступает на дополнительный вход 25 блока 6 н одновременно по этому импульсу происхо-, дит считывание величины D, счетчика 63 на вторую группу зходоз дешифратора 43, а также обнуление счетчиков 61 и 62.

Блок 40 сравнения входных адресов (фиг. 17} работает следующим образом °

В регистр 65 памяти поступает инФормация от первой страницы с элементов памяти групп 105 — 107 блока 7 и запоминается в нем, Информация от последующих страниц поступает через элемент 71 И, инверсный вход которого подключен к нулевому выходу первого триггера группы 69. Все другие адреса страниц поступают через соответствующие элементы И группы 71 в блок 67 поразрядного сравнения, в котором происходит сравнение сод