Устройство для управления виртуальной памятью Советский патент 1987 года по МПК G06F12/08 

1132

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

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

На фиг, I приведена функциональная схема устройства для управления виртуальной памятью; на фиг. 2 - схе- .ма блока входных регистров; на фит, 3 схема блока выходных регистров фиг, 4 - схема формирователей; на фиг. 5 - схема блоков сравнения; на фиг. 6 - схема компаратора; на фиг, 7 схема блока местного управления; на фиг. 8 - схема блоков памяти страниц; на фиг, 9 - схема элемента памяти; на фиг, 10 --схема генератора расстановки; на фиг, 1 1 - схема блока управления замещением; на фиг, 12 - схема узла приоритета; на фиг. 13 - схема блока коррекции; на фиг, 14 - схема блока управления страничным обменом; на фиг, 15 - схема блока определения числа страничных сбоев; на фиг. 16 - .схема блоков расстановки; на фиг. 17 - схема первого блока сравнения; на фиг, 18 - схема второго блока сравнения, на фиг. 19 - схема формирователя адреса обмена страниц; на фиг. 20 - временная диаграмма тактовых импуль

сов; на фиг. 21 - пространство состояния активной задачи в оперативной памяти.

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

Q

5 0 5 о

5

0

5

0

5

32

выход 35 сигнала прерывания, информа- щюнный выход 36 устройства.

Блок 11 управления страничным обменом (фиг, 1Д) содержит блоки 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 сравнения (фиг, 18) содержит блок 81 памяти, группу 82 регистров памяти, группу блоков 83 сравнения, группу 84 И элементов, группу элементов 85 И.

Формирователь 57 группы (фиг,19) содержит первый 86 и второй 87 входные регистры, блок 88 поразрядного :сравнения, первый 89 и второй 90 элементы И, выходные регистры 91 н 92, элемент ИЛИ 93,

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

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

313

Блок 5 сравнения (фиг. 5) содержит компаратар 139, регистр 1ДО, элементы И А1 и 142.

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

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

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

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

Элемент памяти групп 105-115 блока 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 и 195.

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

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

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

13

выхода которого через элемент ИЛИ 189 производит запись в регистр 156 физического адреса, поступающего на вход регистра I56 через коммутатор 159 блока 2 выходных регистров. Если процессор работает в режиме преобразования адреса, то устанавливается соответствующий бит слова состояния программы и указанная вьппе информация загружается в управляющий регистр 3, сюда же передается информация о количестве страниц, минимально необходимых для выполнения каждой активной задачи,а также информация о длине задачи в страницах, определяемой значением параметра REGION оператора EXEC, Во время выполнения операции, связанной с обращением к оперативной памяти, устройство управления возбуждает вход 17 блока 6 местного управления. Тогда во время действия импульса СО открывается элемент И 185, по сигналу с выхода 27. которого логический адрес записывается в регистр 94 логического адреса блока 1 входных регистров, В блоке 1 адрес виртуальной страницы формируется так же, как в устройстве-прототипе. Разряды адреса виртуальной страницы, кроме смещения, поступают на входы группы 143 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ генератора 8 расстановки, результат с выхода которой через ком-- мутатор 144 поступает на адресные входы групп 105-115 элементов памяти каждого из блоков 7 памяти страниц. Информацияi прочитанная с выбранной ячейки групп 105 - 107, 113 и 1I5 элементов памяти поступает в соответствующий блок 5 сравнения. Одновременно информация с выбранной ячейки групп 105 - 107 элементов памяти каждого из блоков 7 поступает на соответствующие входы блока 40 сравнения входных адресов блока 11 управления страничным обменом, В блоке 40 по информации из группы 105- 107 элементов памяти определяется количество страниц оперативной памяти,

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

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

Если сравнение произошло| выбранная строка групп 105-115 элементов памяти загружена и данная страница не используется в операциях ввода- вывода, то это указывает на то, что требуемая виртуальная страница находится в оперативной памяти и доступна. Эта ситуация запоминается в регистрах 140 каждого из блоков 5 по сигналам, поступающим с выхода 29 открытого элемента И 179 во время действия импульса С1, и характеризует успешное обращение к странице оперативной памяти. Эта информация с выхода коммутатора 76 блока 5 поступает на первый вход соответствующего блока 37 определения числа страничных сбоев. Сигналы с выходов элементов И 141 поступают в блок 2 на эле мент ИЛИ 163j с помощью которого определяется, находится ли требуемая страница в оперативной памяти и раз.решено ли к ней обращение. Эта ситуация запоминается в триггере 194 во время действия импульса С1 по сигналу, поступающему на вход синхронизации триггера 194 через открытый элемент И 79.

Если сравнение произошло, выбран- ная строка групп 05-115 элементов памяти загружена, но данная страница используется в операциях ввода-вывода, то это указывает на тоэ что требуемая виртуальная страница нахо- дится в оперативной памяти, но недоступна для обрашений со стороны процессора. Эта ситуация запоминается в триггере 195 (единичное состояние) во время действия импульса С1 по сиг налу, поступающему на вход синхронизации триггера 195 через открытый элемент И 79. Это условие формируется элементами И блоков 5 и злемен - том и 190 блока 6.

Если с помощью элемента ИЛИ 63 установлено, что доступ к виртуально странице возможен ( единившее состояние триггера 194 , то ее сформированный физический адрес записывается в регистр 156 физического адреса по сигналу с выхода 28 блока 6 местного управления, поступающему на управляющий вход регистра 156 физичес3 -6

кого адреса через элемент НИИ 184 и открытый элемент И 180 во время действия импульса С1, Физический адрес поступает на вход регистра 155 через коммутатор 159. Физический адрес формируется как совокупность номера блока 5 сравнения, где произошло опознание виртуальных адресов, кода, поступающего с выхода ком1-1утатора 144 генератора 8 расстановки, и смещения, поступающего с выхода 99 регистра 94 логического адреса. Двоичный код номера блока 5 . сравнения формируется формирователем 161, После этого производится коррекция страничной таблицы, заключающаяся в установлении битов обращения и битов изменения, если обращение в оперативную память производилось для записи информации. Для этого во время де.йствия импульса С2 открывается элемент И 178, сигнал с выхода 30 которого поступает на элемент И 132 каждого из блоков 7 памяти страниц. Содержимое регистров 140 блоков 5 сравнения поступает на вторые входы элементов И i 32 соответствующих блоков 7 памяти страниц, Так как опознание виртуального адреса возможно только в одном из блоков 5 сравнения то открываются элементы И 119, 120, 132 и 134 соответствующего блока 7 памяти страниц. Элементы И 119 и 120 определяют установку информации на входы групп 108 и 109 элементов памяти соответствующего блока 7 памяти страниц, а открытый элемент И 132 разрешает прохождение сигнала записи на управляющие входы групп 100 и 109 элементов памяти. Запись в группу 109 элементов памяти производится только при установке триггером кода, операции определяющего запись информации Е оперативную память, В этом случае открыт элемент И 134,

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

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

713

нет в оперативной памяти, что соответствует страничному сбою. Эта информация через элемент И 186 поступает на второй вход соответствующего блока 37 определения числа странич- ных сбоев. Если хотя Сы в двух блоках 37 число успешных обращений К к оперативной памяти или число страничных сбоев D достигают своих критических значений К или , которые выбираются с учетом специфических характеристик потока задач, решаемых в данной вычислительной системе, или могут быть получены в результате имитационного моделирования вычислительного процесса, то информация об этом с первых выходов соответствующих блоков 37 через элемент Н-ИЛИ 58 поступает на дополнительньй вход 25 блока 6 и открывает элемент И 187, сигнал с выхода 26 блока 6 вызывает прерывание, определяющее, что необходимо провести перераспределение страниц оперативной памАти между активными задачами. После обработки этих прерываний операционная система передает в блок 11 управления страничным обменом-че;рез блок входных регистров для каждой задачи, участвующей в страничном обмене, минимально ; допустимое число страниц оперативной памяти, необходимое для решения каждой задачи, и длину задачи в страницах оперативной памяти.В блоке 1 определяются пары задач,находящиеся одновременно в оперативной памяти,например задаче, имеющей наибольшее избыточное- число страниц,ставится в соответствие задача,требующая наибольшего числа страниц оперативной памяти для успешного завершения. В блоке П определяется количество страниц, которые будут участвовать в обмене, и формируются адреса обмена в группе блоков 57, которые с выхода блока 11 поступают на вход дешифратора 150 блока 10 коррекции, в котором анализируются адреса задач, участвующих в обмене, и условия обмена. В резуль тате такого анализа по сигналу дешиф ратора 150 производится смена номера задачи в группе 106 элементов памяти блоков 7 путем передачи в группу 106 блоков 7 памяти страниц дающих задач, номеров берущих задач. При действии импульса С1 открьшается элемент И 173 6, сигнал с выхода 30 которого и сигнал с выхода эле

10

15

20

25

30

35

40

45

50

55

мен-|,-э ИЛИ 188 открывают :элем1;нт И 126 того блока 7, ко-т-орый выбран дешифратором 145 генератора 8. Сигнал с выхода открытогсч элемента И 126 поступает на управляющие входы группы 106 элементов памяти, разрешая запись нового номера активной задачи, участ- вуюпгей в страничном обмене, с выхода дешифратора 150 блока 10 коррекции. После завершения цикла страничных обменов между задачами, одновременно находящимися в оперативной памяти, устройство продолжает работать в режиме динамического преобразования адресов до тех пор, пока не будут снова достигнуты значения или D„р хотя бы для двух активных задач. При обращении к внешней памяти блок 10 коррекции анализирует условие, сформированное дешифратором 147, которое определяет, возможно ли осуществить замещение или ввод требуемой страницы. Если это возможно, то в соответствующей строке страничной таблицы устанавливается бит-указатель ожидания ввода-вывода. Для этого сигнал с выхода открытого элемента И 154 блока 10 коррекции поступает на элементы И 130 каждого из блоков 7 памяти страниц. В выбранном узлом 149 приоритета блоке 7 памяти страниц открывается элемент И 130 при наличии CHI- нала с выхода 30 элемента И 177 блока -6 местного управления, и во время действия импульса С2 осуществляется запись в группу 113 элементов памяти. Информация на входе группы I13 элементов памяти каждого из блоков 7 памяти страниц устанавливается с выхода элемента ИЛИ 155 блока 10 коррекции.

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

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

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

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

При вьшолиении операций ввода-вывода необходимо установить бит-указатель ожидания ввода- вывода в страничной таблице для реальных физических страниц опеоативной п;1мяти, к ко- Topbfri производится обращение при выполнении этих операций. После окончания операции ввода-вывода бит-указатель ожидания ввода-вывода сбрасывается.

Для выполнения таких действий процессором в младшие разряды регистра 4 общего назначе1 ия устанавливается адрес реальной физической страницы, в соответствующий старший разряд - код, определяющий установку или сброс бита-указателя ожидания ввода-вывода, а устройство управления процессора возбуждает вход 18 блока 6 местного- управления. Таким образом, младшая часть физического адреса страницы с выхода регистра 4 общего назначения через коммутатор 144 генератора 8 расстановки поступает на адресный вход групп 105-115 элементов памяти каждого из блоков 7 памяти страниц. Старшая часть физического адреса страницы дешифруется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один из блоков 7 памяти страниц, т.е. соответствующая часть страничной таблицы. Код установки или сброса бита-указателя ожидания ввода-вывода поступает на- вход группы 113 элементов памяти каждого из блоков 7 памяти страниц через элементы ИЛИ 155 и И 151. В момент действия импульса С1 открывается элемент И, сигнал с выхода 30 которого открывает элемент И 129 того блока 7 памяти страниц, который выбран дешифратором 145 генератора 8 расстановки. Сигнал с выхода открытого элемента И 129 через элемент ИЛИ 36 поступает на управляющий вход группы 113 элементов памяти, вызывая запись,информации, поступающей на вход эле0

0

11310

ментов 115 памяти, с гплходл элемента Ш1И 155 блока 10 коррекции.

При первоначалыкчй загрузке физической страницы р о терлтивргую память шш очистке onepaTj BHon памяти необходимо установить или сбросить бит- указатель запреше)1ня удаления страниц и бит-указатель действительности строки страничной таблицы. Для вьтол- нения таких действий процессор устанавливает в младших разрядах регистра 4 общего назначения адрес реальной физической страницы, в соответствуюg щих старших разрядах - биты, определяющие действительность строки страничной таблицы, и код, определяющий запрещение удаления страниц из оперативной .памяти, а устройство управления процессора возбуждает вход 19 блока 6 местного управления.

Таким образом, младщая часть физи- ческого адреса страницы с выхода регистра 4 общего назначения через ком5 мутатор 144 генератора 8 расстановки поступает на адресные входы групп 105- 115 элементов памяти каждого из блоков 7 памяти страниц. Старшая часть физического адреса дешифрируется деQ щифратором 145 генератора 8 расстановки, что позволяет выбрать один иэ блоков 7 .памяти страниц, т.е. соответствующую часть страничной таблицы. Коды установки битов-указателей запрещения удаления и действительности строки страничной таблицы поступают на входы групп 114 и- элементов памяти каждого из блоков 7 памяти страниц через элементы И 152 и 153 блока 10 коррекции. В момент действия импульса С1 открывается элемент И 175 и через элемент Ш1И 188 сигнал с выхода 28 элемента ИЛИ 188 открывает элемент И 28 того блока 7 памяти страниц, который выбран дешифратором 145 генератора 8 расстановки. Сигнал с выхода открытого элемента И 128, поступающий на управляющие входы групп 114 и 115 злементов памяти, вызывает запись информации, поступающей ка входы групп 114 и 15 элементов памяти с выхода элементов И 152 и 153 блока Ю коррекции соответствекно.

5 При первоначальной загрузке виртуальной страни1яы в оперативную память информация об э.той странице записывается в соответств тощую строку страничной таблицы. При этом уст5

0

5

0

1113

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

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

блоков 7 памяти страниц, т.е. соот

ветствующую часть страничной таблицы В момент действия импульса С1 открывается элемент И 173 блока 6, сигнал с выхода 30 которого и сигнал с выхода элемента ИЛИ 188 открывают эле- менты И 126 - 128, 131 и 133 того блока 7 памяти страниц, который выбран дешифратором 145 генератора 8 расстановки. Сигналы с выходов открытых элементов И 126 - 128, 131 и 133 поступают на управлякяше входы групп 105 - 112, 114 и 115 элементов памяти, вызывая запись информации, по- ступаюшей на входы групп 105 П 2, П4 и 115 элементов. На входах групп 105 - 107 элементов памяти устанавливается номер виртуйльной страницы с выхода блока 1 входных регистров. На входах групп 108 и 109 элементов памяти устанавливается логический нуль, так как элементы группы 119 и 120 закрыты. На входах группы 110 элементов памяти дешифратором 11 8 устанавливается значение ло

g

5 о

5

Q g

3 2

гической едини1Ц51, а на входах групп 111 и 112 элементов памяти - значение логического нуля (загружаемая страница включается в множество наиболее часто используемых страниц. Информация на входах групп 114 и 11 5 элементов памяти определяется содержимым соответствующих старших разрядов регистра 4 общего назначения. Эта информация через элементы И 152 и I53 блока 10 коррекции поступает на входы групп 114 и 115 элементов памяти.

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

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

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

D - число текущих сбоев;

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

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

.L. - минимально требуемое число страниц для решения i-й задачи;

Кд - число успешных обращений к страницам i-й задачи.

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

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

(1)

л Njrs

А . ----- X,

,п DT д. . -f-,

Li

а также

«А

(2)

1Л1

рГ- й /

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

15- (3)

ij. {i/r. л,pV

(4)

1313

Дающее подмножество по А. упорядочивается путем расстановки элементов I,. от Д. до А;

о . м«х ( „

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

от J до /1 Г . Далее производят

тсс I min;

лерераспределение страниц ОП между

активными задачами, учитывая тот факт, что задача с min А j может отдать максимальное число страниц, а задача с шах Л; может принять макси- мальное число страниц ОП:

K-min L.-X. ,X.-Ljj ,i€ly,jelj. (5)

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

L. -X, Xj -L°.

(6)

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

L. - X. 7/ X. - L°..(7)

Вместе с тем при A j удовлетворить задачи из множества 1 за счет задач из множества 1„ не представляется возможным. Это условие также может служить основанием для выбора величин К р и D р .

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

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

Q

20

35

25

зо

Qg j-n3U

мяти соответствует числу страниц оперативной памяти. На другой вход блоков памяти группы 48 через дешифратор 42 поступает из группы 109 элементов блока 7 число обращений к страницам данной задачи - N, Первый выход каждого блов:а памяти группы 48 подключен на вход сумматора 46, в котором производится подсчет обшего количества задач, од-новременно находящихся в оперативной памяти, по числу блоков памяти группы 48, в которые поступила информация. Вторые и третьи выходы указанных блоков 48 памяти подключены на входы блоков вычисления у1 j группы 52, выходы которых подключены на входы блока 38 расстановки и на входы сумматора 47, в котором производится вычисление Z А - .

1-1

В блоке 38 рас становки производится определение максимального коэффициента и последующих Л ДО ( „;„ при этом на первый вход блока 38 расстановки .поступает А

|Т1С(Х

, а на последний - А ; , с выходов сумматоров 46 и 47 информация поступает на входы блока 56, в котором производится вычисление среднего значения Д по формуле N

л :. л:.

55

Д :

f N Выход блока 56 подключен на первый вход блока 41 сравнения с ip., на остальные входы которого поступают значения коэффициентов от Д до

то

Д . С ВЫХОДОВ блока 38 расстановки,, при этом , поступает на второй вход блока 41, на третий и т.д., на последний вход бло- ка 41 поступает 1,, с последнего

Г| 11

выхода блока 38. В блоке 41 сравнения с множество i разделяется на два подмножества: подмножество задач с избытком страниц оперативной памяти (1а 1 f подмножество задач, испытывающих недостаток страниц, оперативной памяти (I, сД ). Номера задач из множества la. поступают на первую группу входов дешифратора 44, на вторую группу входов которого поступают из блока 1 входных регистров значения L J для всех активных задач, на третью группу входов дешифратора 44 поступают значения Х из блоков 48 памяти группы, при этом на выход дешифратора 44 проходят значения X, и L, соответствующие , таким образом,, что на первую пару

1513

входов дешифратора поступают X, и L , соответствующие /1 из мно1 Ч « 1

жества I , на последнюю пару выходов - Х и L°, соответствуюшие ,, Первая пара выходов дешифратора 44 подключена на входы первого блока 50 памяти группы, в который записываются значения X. и L, соответствующие задаче с ,„д, из 1, а последняя группа выходов дешифратора 44 - к последнему блоку памяти группы 50, в которой записываются значения Х, L°, соответствующие А . из 1„, ВылШ1 О3

ходы блоков 50 памяти группы подклю- чены на входы блоков 54 вычисления группы, в которых для каждой задачи из множества 1 производится вычисление выражении X -Lj, j I а, и этот результат с номером задачи, к кото- рой он относится, передается с выхода соответствующего блока памяти : группы 54 на первый вход соответствующего формирователя адреса страничного обмена группы 57. Номера задач из множества Ij поступают на первую группу входов дешифратора 43, на вторую группу входов .которого из блока 1 поступают значения L., на третью группу - сигналы с выходов бло- ков 37 определения текущего числа сбоев страниц оперативной памяти. Дешифратор 43 пропускает значения d. , Lj для каждой задачи из множества Ig на входы соответствующих блоков памяти группы 49, выходы которых подключены на входы соответствующих блоков группы 53, в которых производится вычисление по формуле Д

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

ва If. Значения А, с выходов соответ0ч

ствующих блоков группы 53 поступают на входы блока 39 расстановки, который функционирует так же, как . блок 38 расстановки. На первом выходе блока 39 расстановки формируется номер задачи, для которой , последнем - номер задачи, у которой min Указанные номера поступают на первую группу входов дешифратора 43, на вторую группу входов которого поступают значения L. из блока 1, на третью - значения X. из блоков памяти группы 48. На первую пару выходов дешифратора 45 поступают значения X.,L,, соответствующие задаче из множества Ig, для которой °

следнюю пару дешифратор 45 пропуска3

16

ет значения X , L задачи из множества Т, для которой Д J . Первая пара выходов дешифратора 45 подключена на вход первого блока памяти группы 51, в который поступают значения X., L. для задачи X е 1, у которой no(f т.д., последняя пара выходов подключена на входы последнего блока памяти группы 51, в которьй записываются значения Х, L, для задачи I-, у которой . Выходы блоков памяти группы 51 подключены на входы соответствующих блоков вычисления группы 55, в которых производятся вычисления величин К для каждой задачи из множества Ig, результаты вычислений с выходов блоков группы 55 поступают на вторые входы формирователей адресов группы 57 страничного обмена, выходы которых подключены к первой группе входов дешифратора 150 блока 10 коррекции. При этом на входе каждого формирователя адреса группы 57 формируетс адрес страничного обмена, включающий в себя номер задачи, отдающей страницы Njj, номер задачи, берущей страницы N-j, и число страниц, участвующих в обмене. Kg или Ко. Сформированные адреса поступают на первую группу входов дешифратора 150 блока 10, на вторую группу входов которого из блока 116 поступают адреса страниц, наименее используемых и принадлежащих задачам, между которыми производится страничный обмен. Страничный обмен между активными задачами фактически заключается в замене в группе элементов 106 памяти блока 7 номера задачи, отдающей страницы, на номер задачи, берущей страницы, при этом количество страниц в которых будет проведена смена номеров задач, определяется в соответствующем формирователе 57 адреса группы из выра жения

.-Х-,X.-Lj ,iel5,jel.

Задача из множества Ig, у которой mof берет максимальное число страниц, задача из множества In, у которой . , отдает максимальное число страниц. .Для таких пар задач величины, их характеризующие - Х, L. (icij), X,, L (jelj), поступают через соответствукшие блоки вычисления группы 54,в которых определяются значения К X -, - L J , на входы одного

i7

формирователя г руппы 57, и именно между такими задачами производится страничный обмен таким образом, что ибо дающая задача полностью освобождается от избыточных страниц, либо берущая задача полностью удоветворяется недостающими страницами Блок 11 управления страничным обменом начинает функционировать, если хотя чд бы для двух задач достигнуты значения или К , которые форкируготся о информации, поступающей на входы блоков 37 определения числа страничных сбоев с выхода компаратора 139 5 блока 5 и выхода триггера i 94 блока 6. Сигналы о достижении К р или p с вторых вьгходов блока 37 постуают на входы элемента И-ИЛИ 58, с ыхода которого поступает сигнал на 2о ополнительный вход 25 блока 6, по оторому формируется прерывание, поступающее на выход 26 блока 6 и обабатывающееся в операционной систее. За время обработки этого прерыва- 25 ния по сигналам от операционной системы блок 11 .производится перераспрееление страниц оперативной памяти между активными задачами. Блок 37 определения числа странич- Q ньгх сбоев (фиГе 15) включает элемент И 59, элемент И 60 с первьм инверсным входом, на входы которых поступают сигналы с выходов компаратора 139 блока 5 и триггера 194 блока 6.Если страница,к которой происходит обращение,находится в оперативной памяти, то оба сигнала присутствуют на входе элемента И 59, что свидетельствует об успешном обращении к оперативной памяти. Импульс с выхода элемента И 59 поступает на вход счетчика 61 успешных обращений К, нй другой вход которого предварительно подается код числа К| , который первоначально устанавливается в счетчике 61, Если с выхода триггера 194 сигнал не поступил, это свидетельствует об отсутствии требуемой страницы в оперативной памяти и наступает страничный сбой - обращение к внешней памяти, В этом случае сигнал не поступает на первый инверсный вход элемента И 60, а на второй вход поступает сигнал с выхода компаратора 39 блока 5, Импульс с выхода эле ментй И 60, свидетельствующий о страничном сбое, поступает на вход счет- чика 62, в котором предварительно ус35

40

50

.„ 55

чд 52о25Q35

40

50

1318

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

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

В регистр 65 памяти поступает информация от первой страницы с элементов памяти групп 105 - 107 блока 7 и запоминается в нем. Информация от последующих страниц поступает через элемент 71 И, инверсный вход которого подключен к нулево1чу выходу первого триггера группы 69, Все другие адреса страниц поступают через соответствующие элементы И группы 71 в блок 67 поразрядного сравнения, в котором происходит сравнение содержимого элементов памяти групп 105-107 ка;кдой последующей страницы с инфор- ччацией, хранящейся- в регистре 65. Выход блока 67 поразрядного сравнения подключен на вход регистра 66 памяти числа страниц относящихся к i-й задаче, в данном случае к той, номер которой в этот момент хранится в регистре 65. После сравнения последней страницы с кодом в регистре 65 по сигналу, поступившему на первый вход последнего элемента И группы 71 через линию 70 задержки производится считывание числа страниц оперативной памяти, ; относящихся к данной задаче., которое поступает на вход коммутатора 68 а последний пересылает число страниц первой задачиJ полученное в результате сравнения первого страничного адреса со всеми адресами, на вход первого блока памяти группы 48, Результат каждого сравнения s случае совпадения адресов дает ннпульс на выходе блока 67 который суг мируется в блоке

а также служит для

чд 5 2о 25 Q55

установки состзетствующего триггера группы 69 из единичного состояния в нулевое и таким образом запирает соответствующий элемент И группы 71, что позволяет исключить подвергшийся сравнению адрес страницы из обще19,327113 20

го числа страниц, поступающих- дляэлементов Д. до тех пор, пока все

сравнения с другими адресами на входони не будут записаны по убыванию в

блока 40 сравнения. Процедура выпол-выходных регистрах группы 80. няется до тех пор, пока не будет про- . , Блок 41 сравнения с А (фиг. 1 8)

ведено сравнение всех адресов. работает следующим образом.

Блоки 38 и 39 расстановки (фиг.16) В первый входной регистр 81 поработают следующим образом.ступает значение с выхода блоВычисленные значения А в блокахка 56 вычисления, во входные регист- групп 52 или 53 поступают во вход- юР группы 82 поступают значения от ные регистры группы 73 со своими но-Л „ до Л,. соответственно с выхо- мерами задач. В первой части каждогодов блока 38 расстановки, с выхода регистра хранится значение Д, , а ворегистра 81 Л .р поступает на первый второй - номер соответствующей зада-вход всех блоков поразрядного срав- чи. Значение Д., записанное в первом igнения группы 83, на вторые входы ко- входном регистре группы 73, поступа-торых поступают значения от Д д до ет на первый вход первого блока по- /(т1л выходов регистров группы 82, разрядного сравнения группы 74, напервые выходы блоков поразрядного второй вход которого поступает А j ссравнения группы 83 подключены на выхода второго регистра группы 73; соответствующих элементов И если первое значение больше второго,группы 84, на вторые входы которых то импульс появляется на первом вы-подключены вторые выходы соответст- ходе блока сравиения группы 74, ввутощих регистров группы 82, с кото- противном случае - на втором. Первыйрых поступают номера задачj соответ- выход первого блока сравнения груп- 25ствующие д . Второй выход блока срав- пы 74 подключен к первому входу пер-нения группы 83 подключен на вход вого элемента И группы 75, а второй-соответствующего элемента И груп- на вход второго -элемента И группы 75,пы 85, на второй вход которого также на второй и третий входы первого зле-подается номер задачи, которой соот- мента И группы 75 подключены второй Qветствует/1 ; сравнивается в бло- и третий выходы первого регистра .ке сравнения группы 83 с Аср« ВСе но- группы 73, с которых поступают, хра-мера задач, для которых /l. ° нящиеся в нем значения Д и номераступают с выходов соответствующих задачи. Аналогичная информация посту-злёментов группы 85 на первую группу пает на входы второго элемента И -входов дещифратора 43, а все номера группы 75 с выходов второго регистразадач, для которых Дс/ через группы 73. После сравнения большаясоответствующие злементы И группы 84 величина А. со своим номером черезпоступают на первую группу входов де- соответствующий элемент И группы 75шифратора 44. Таким образом, в бло- и элемент ИЛИ группы 76 поступает вке 41 сравнения происходит разбиение первый регистр группы 77, содержимоевсего множества активных задач на которого таким же образом сравнивает-множества дающих I и берупщх ся со значением Д. , хранящимся, в тре-1 задач.

тьем входном регистре группы 7i. Та- Формирюватели адреса обмена стракое сравнение производится до тех ниц группы 57 (фиг. 19) работают слепор, пока не будет найдет максималь-дующим образом.

ный элемент f , который с выхода В первый входной регистр 86 поступоследнего регистра группы 77 черезпают число страниц K«, отдаваемое

соответствующие элементы групп 75i-й задачей и вычисленное в соответи 76 поступает на вход коммутатора 79,ствующем блоке группы 54 по формуле

который пересылает первый А j,, в пер-К Xj- LJ , j е Ij, и номер задачи

вый выходной регистр памяти группы 80.берущей страницы. Во второй входной

Номер найденного максимального эле-регистр 87 поступает число страниц

мента поступает в дещифратор 78 ад-Kg, принимаемое j-й задачей и вычисреса, сигнал с выхода которого обну-ленное в соответствующем блоке вычисляет соответствующий входной регистрлёния группы 55 по формуле Kg L. группы 73, в который первоначально sJElg, и номер отдающей задачи.

поступил , Далее процедура по-С выходов регистров 86 и 87 значения

иска , првторяется для оставшихсяKg и К поступают на первый и второй

21132711

ходы блока 88 поразрядного сравнеия. Если K,j Kg, то на первом выхое блока 88 появляется сигнал, если g К,, то сигнал появляется на втоом выходе блока 88 сравнения, первый выход которого подключен на вход элеента И 89, на другие входы которого

одаются номер задачи, отдающей страницы, Nj номер задачи, берущей стра- ницы, N,r и значение К, Второй выход блока 88 сравнения подключен на первый вход элемента И 90, на другие

входы которого подаются с выходов регистров 86 и 87 Nj, N 36 и Kg, Выхо- g ды элементов И 89 и 90 подключены соответственно на входы регистров 91 и 92 памяти, выходы которых подключены на соответствующие входы элемента ИЛИ 93, выход которого подключен о к одному из входов первой группы входов деЫифратора 150 блока 10, ., Если Ка больше Kg, то обмен осуществляется таким образом, чтобы задача, берущая страницы, бьша полностью 25 удовлетворена. В этом случае на первом выходе блока 88 сравнения появляется импульс, по которому в регистр 9i через элемент И 89 записывается адрее обмена в виде ,К, Если зо Kf KQ, ТО ВЫСОКИЙ потенциал появляется на втором выходе блока 88 сравнения, и в регистр 92 через элемент И 90 записывается адрес страничного обмена в виде N. NjjK-, реали-. зующий вариант, когда задача, отдающая страницы, полностью от них освобождается ,

Блок 1 входных регистров (фиг. 2) предназначен для формирования полно- го виртуального адреса, работает так же, как и аналогичный блок в устройстве-прототипе, в него дополнитель- но введены выходы 103 и 04 управляющего регистра 3 для г аредачи из операционной систе 1ы значений L. (длина i-й задачи в страницах оперативной памяти), и L, (минима,пьное число страниц для выполнения i-й задачи).

Блоки 7 памяти страниц (фиг. 8) предназначены для хранения страничной таблицы и обеспечивают возможность ее модификации, каждый из блоков 7 содержит часть этой таблицы, Все блоки памяти со держат полную страничную таблицу, число строк которой равно числу страниц, которое можно расположить в оперативной памяти. Строка страничной таблицы описывает единст35

40

45

50

55

5

о

5

0

5

0

5

322

венную страницу оперативной памяти. Блоки 7 работают так же, как и соответствующие блоки в устройстве-прототипе. В строку страничной таблицы дополнительно введена группа 106 элементов памяти, в которых хранятся номера задачS определяющие прина шеж ность.данной страницы оперативной памяти к конкретной активной задаче.

Элемент 106 (фиг, 9) содержит де- шис1)рйтор 164, информационный регистр 165, группу 166 элементов памяти, коммутатор 167 и работает так же, как и группы элементов памяти строки страничной таблицы в устройстве-прототипе, В блок 7 введен дополнительный вход, являющийся информационным входом элемента памяти группы 106, подключенный к одному из выходов первой группы выходов.дешифра- тор)а S 50 блока 10 коррекции, для перезаписи номеров активных задач. Кроме того, введены дополнительные выходы, с элементов памяти групп 105- 107, подключенные на третий вход блока П управления страничным обменом, которые служат для передачи адреса виртуальной машины и виртуальной па- . мяти с элемента 105, адреса номера активной задачиJ к которой относится страница оперативной памяти, с элементов группы 106, адреса номера сегмента и номера страницы элементов группы 107, вся перечисленная информация поступает на вход блока 40 сравнения входных адресов.

Блок 5 сравнения (фиг, 5) предназначен для сравнения виртуальных адресов страниц, постзшающих с вьгходов блока 1 входных регистров, с номерами виртуальных страниц, хранящихся в соответствующих блоках 7 памяти страниц, и работает так же, как и соот- Бстствующий блок в устройстве-прототипе, в нем дополнительно вьгход компа- - ратора 139 подключён на первый вход блока 11,

Блок 10 коррекции (фиг, 13) предназначен для занесения информации в элементы памяти группы 106, 113-115 каждого блока 7 и работает так же как и соответствующий блок в устройстве-прототипе j в него дополнительно введен дешифратор 150 адреса, первая группа входов которого подключена к второму выходу блока 11, а на вторую группу вводов поступает информация об условиях удаления страниц и частоте

их использования из регистра 116, Выходы дешифратора 150 подключены к соответствующим входам элементов группы 106 номеров задач.

Блок 6 местного управления (фиг, 7 предназначен для выработки управляющих сигналов и работает так же, как и соответствующий блок в устройстве- прототипе, в него дополнительно вве- дены элемент И 187, первый прямой вход которого является дополнительны входом 25 блока 6, второй вход которого является входом 17 блока 6, третий вход которого является входом 22 блока 6, а также элемент И 186 к первому входу которого подключен выход триггера 195, а к второму - выход триггера 194, выход элемента И 186 является дополнительным выходом 32 блока 6.

Генератор 8 расстановки (фиг,10), блок 9 управления замещением (фиг.11), блок 2 выходных регистров (фиг.З), формирователи 161 и 162 (фиг.4) выполнены так же, как и соответствующие блоки в устройстве-прототипе , и выполняют те же функции,

Таким образом, при вводе страницы в оперативную память устройство для управления виртуальной памятью реализует следующий алгоритм: при установленном бите ожидания ввода-вывода устанавливается адрес требуемой страницы, вводится требуемая виртуальная страница, а затем сбрасывается бит ожидания ввода-вывода,

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

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

При достижении критического числа сбоев или успешных обращений к оперативной памяти блок 1I управления

-SQ g o

25

gQ

.,,

о gg

35

45

324

страничным обменом через блок 6 местного управления формирует прерывание, которое обрабатывается в операционной системе, при этом в блоке 11 формируются адреса задач, участвующих в обмене страниц. Сформированные адреса вбмена с выходов соответствующих формирователей адреса группы 57 поступают на первую группу входов дещифра- тора 150 блока 10, на другую группу входов которого поступает информация об условиях удаления страниц и частоте их использования из регистра 116. С выхода дешифратора 150 сигналы поступают на входы элементов памяти группы 106 блока 7, меняют в них номера задач, к которым принадлежат соответствующие страницы, одновременно обнуляются счетчик 61 страничных сбоев и счетчик 62 успещных обращений к оперативной памяти. После окончания одного цикла оптимального перераспределения страниц оперативной памяти между активными задачами устройство продолжает работать в режиме динамической трансляции и преобразования адреса до тех пор, пока снова не будут достигнуты критические значения числа страничных сбоев или успешных обращений к оперативной памяти.

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

Формула изобретения

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

.25132

блока входных регистров подключен к входу задания числа страниц ;у1я решения активной задачи блока управления страничньй обменом, информационный выход которого подключен к входу ана- лиза адресов страничного обмена блока коррекции, выходы признаков равенства блоков сравнения подключены к входу анализа сбоев блока управле- ния страничным обменом, пятый управ326

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

tr

фиг. 2 От т

К2

ОтЗЗ OmIZ

Om13

От 28 оИ f

-.р

AJ5

От 12

0m27

ОтЮЗ ОтЮ7 о о

Y иУ . От2В

1о

/

Г60

f57

От lit

tpU6,3

и

2ji

|К| ., X, ч,

f f ЛЛЛ r ySyww Л 1 1 л1л1г

I Г Ш 1 r 172 I Iyy I

ФVУФ

0tfe. 4

«

ЗтШ Опт

OmtS

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

2S

фи.9

От т

фиб.П

Фие.п

ОтШ

151

8гзг

о

Г53

fpus. f3

ut.

ОС

/7/77 Ш

От т

53

БО

Фиб,15

От Wit

SJ

sit

(25

S3

От W5-W7 о

Фиг.17

/,ПП--п

, 1

(/«. /I

j

HSSS

S3

Kfff

фие. 19

ф(/г. 20

0ui.ir

Редактор Л.Веселовская

Составитель А.Мишин Техред И.Попович

Заказ 3391/46

Тираж 672Подписиое

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий I13035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Корректор Л.Пилипенко