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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 801327 4 С 06 Р 12/08 ОМИТЕТ СССРИЙ И ОТКРЫТИИ ГОСУД АРСТ 8 ЕННЫПО ДЕЛАМ ИЗОБРЕ АНИЕ ИЗОБРЕТЕНИЯКОМУ СВИДЕТЕЛЬСТВУ О КА суни ежду акв сосвирту-. 9 28В.Горелов,П.В ия стра- ультабоев и ративк вычислииспольэо-.ах с виракти(56) Авторское свидетельство СССРУ 955076, кл. С .06 Р 12/08, 1980.(54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ВИРТУАЛЬНОЙ ПАМЯТЬЮ(57) Изобретение относитсятельной технике, может бытьвано в вычислительных машин туальной памятью,и позволяетществить оптимальное распределстраниц оперативной памяти итивными задачами. С этой цельтав устройства для управленияальной памятью по авт. св.У 955076 введен блок управленничным обменом, который но ретам анализа числа страничныхчисла успешных обращений к опной памяти позволяет с помощьюратных средств перераспределиницы.оперативной памяти междуными задачами. 21 ип.13271формирователя группы 57, и именно между такими задачами производится страничный обмен таким образом, чтолибо дающая задача полностью освобождается от избыточных страниц либо берущая" задача полностью удовлетноряется недостающими страницами. Блок 11 управления страничным обменом начинает функционировать, если хотя бы для двух задач достигнуты значения Э или Кщ которые формируются по информации, поступающей на входы блоков 37 определения числа страничных сбоев с выхода компаратора 139 блока 5 и выхода триггера 194 блока 6. Сигналы о достижении К р илн О с вторых выходов блока 37 посту пают на входы элемента И-ИЛИ 58 с выхода которого поступает сигнал на дополнительный вход 25 блока б, по которому формируется прерывание, поступающее на выход 26 блока 6 и обрабатывающееся н операционной системе, За время обработки этого прерына В ния по сигналам от операционной системы блок 11 производится перераспределение страниц оперативной памяти между активными задачами.Блок 37 определения числа странич- ЗО ных сбоев (фиг. 15) включает элемент И 59, элемент И 60 с первым инверсным входом, на входы которых поступают сигналы с выходов компаратора 139 блока 5 и триггера 194 блока 6.Если страница,к которой происхо 35 дит обращение, находится в оперативной памяти, то оба сигнала присутствуют на входе элемента И 59, что свидетельствует об успешном обращении к оперативной памяти, Импульс с вьгхода элемента И 59 поступает на нход счетчика 61 успешных обращений Ко не другой вход которого предварительно подается код числа К , который пер 45 воначально устанавливается н счетчике 61, Если с выхода триггера 194 сигнал не поступил, зто свидетельствует об отсутствии требуемой страницы в оперативной памяти и наступает страничный сбой - обращение к ннеш 50 ней памяти. В этом случае сигнал не поступает на первый инверснъм вход элемента И 60, а на второй вход поступает сигнал с ныхода компаратсра 139 блока 5. Импульс с выхода эле- В 5 мента И 60, свидетельствующий о страничном сбое, поступает на вход счетчика 62, в котором предварительно ус 13 18тановлен код числа 0и одновременно на вход сче чика 63, в котором подсчитывается текущее число страничных сбоев В При переполнении (до-стижении 13 или К ) одного из счетКрчиков 61 или 62 им.пульс переполнения с выхода элемента ИЛИ 64 поступает на дополнительный вход 25 блока 6 н одновременно по этому импульсу происхо-, дит считывание величины О, счетчика 63 на вторую группу входон дешифратора 43, а также обнуление счетчиков 61 и 62.Блок 40 сравнения входных адресов (фиг. 17) работает следующим образом,В регистр 65 памяти поступает инФормация от первой страницы с элементов памяти групп 105 - 107 блока 7 и запоминается н нем, Информация от последующих страниц поступает через элемент 71 И, инверсный вход которого подключен к нулевому выходу первого триггера группы 69, Все другие адреса страниц поступают через соответствующие элементы И группы 71 н блок 67 поразрядного сравнения, в котором происходит сравнение содержимого элементов памяти групп 105 - 107 каждой последующей страницы с информацией, хранящейся в регистре 65, Выход блока 67 поразрядного сравнения подключен на вход регистра 66 памяти числа страниц, относящихся к 1-й задаче, в данном случае к той номер которой в этот момент хранится в регистре 65 После сраннения последней страницы с кодом н регистре 65 по сигналу, поступившему на перный вход последнего элемента И группы 71 через линию 70 задержки производится считывание числа страниц оперативной памяти, относящихся к данной задаче которое ггоступает на вход коммутатора 68, а последний пересылает число страниц первой задачи, полученное з результате сравнения первого страничного адреса со всеми адресами, на вход первого блока памяти группы 48, Результат каждого сравнения з случае совпадения адресов дает импульс на выходе блока 67, который суммируется в блоке 66, а также служит для установки соответствующего триггера, группы 69 изнулевое и таким образом запирает соответствующий элемент И группы 71, что позволяет исключить подвергшийся сравнению адрес страницы из обще19 13271 го числа страниц, поступающих. для сравнения с другими адресами на вход блока 40 сравнения. Процедура выполняется до тех пор, пока не будет проведено сравнение всех адресовБлоки 38 и 39 расстановки (фиг,16) работают следующим образом.Вычисленные значения Л, в блоках 1групп 52 или 53 поступают но входные регистры группы 73 со своими номерами задач, В перной части каждого регистра хранится значение Л а но второй - номер соответствующей задачи, Значение Л записанное в первом 15 входном регистре группы 73, поступает на первый вход первого блока поразрядного сравнения группы 74, на второй вход которого поступает Л с выхода второго регистра группы 71; если первое значение больше второго, то импульс появляется на первом выходе блока сравнения группы 74, в противном случае - на втором, Первый выход первого блокасравнения груп пы 74 подключен к первому входу первого элемента И группы 75, а второй - на вход второго элемента И группы 75, на второй и третий входы первого элемента И группы 75 подключены второй и третий выходы первого регистра . группы 73, с которых поступают, хранящиеся в нем значения Л, и номера задачи, Аналогичная информация поступает на входы второго элемента И35 группы 75 с выходов второго регистра группы 73, После сравнения большая величина Л, со своим номером через соответствующий элемент И группы 75 и элемент ИЛИ группы 76 поступает в первый регистр группы 77, содержимое которого таким же образом сравнивается со значением Л хранящимся, в третьем входном регистре группы Ъ. Такое сравнение производится до тех пор, пока не будет найдет максимальный элемент 3 , который с выхода последнего регистра группы 77 через соответствующие элементы групп 75 и 76 поступает на вход коммутатора 79,50 который пересылает первый Л в первый выходной регистр памяти группы 80, Номер найденного максимального элемента поступает н дешифратор 78 адреса, сигнал с выхода которого обнуляет соответствующий входной регистр55 группы 73, в который первоначально поступил Л. Далее процедура поиска Лпрнторяется для оставшихся 13 20элементов Л, до тех пор, пока нсеони не будут записаны по убыванию нвыходных регистрах группы 80,Блок 41 сравнения с л",р (фиг,18)работает следующим образом.В первый входной регистр 81 поступает значение Л, с выхода блока 56 вычисления, но входные регистры группы 82 поступают значения отЯ" до Л" . соответственно с выховак ъ лдов блока 38 расстановки, с выходалрегистра 811 поступает на первыйвход всех блоков поразрядного сравнения группы 83, на вторые входы которых поступают значения от Лдос выходов регистров группы 82,первые выходы блоков поразрядногосравнения группы 83 подключены навходы соответствующих элементов Игруппы 84, на вторые входы которыхподключены вторые выходы соответствующих регистров группы 82, с которых поступают номера задач, соответствующие Л . Второй выход блока срав 1нения группы 83 подключен на входсоответствующего элемента И группы 85, на второй вход которого такжеподается номер задачи, которой соответствует Л",Л сравниваетсяв блолке сравнения группы 83 с Л -р, Все номера задач, для которых Я" 1 Л, , по 1ступают с выходов соответствующихэлементов группы 85 на первую группувходов дешифратора 43, а все номеразадач, для которых Л" ( Л,", черезсоответствующие элементы Й группы 84поступают на первую группу входов дешифратора 44. Таким образом, в блоке 41 сравнения происходит разбиениевсего множества активных задач намножества "дающих" 1 и "берущих"1 задач.Формирователи адреса обмена страниц группы 57 (фиг. 19) работают следующим образом,В первый входной регистр 86 поступают число страниц К, отдаваемое-й задачей и вычисленное в соответствующем блоке группы 54 по формулеоК Х - 1., З е 1, и. номер задачиберущей страницы. Во второй входнойрегистр 87 поступает число страницК, принимаемое 1-й задачей и вычисленное в соответствующем блоке вычис-ления группы 55 по формуле К6 фХ;, 1 61, и номер отдающей задачи,С выходов регистров 86 и 87 значенияК и К поступают на первый и второй21 13271входы блока 88 поразрядного сравнения, Если К т К , та на первом выходе блока 88 появляется сигнал, еслиК 7 К, то сигнал появляется на втаГ,рам выходе блока 88 сравнения, первый "выход которого подключен на вход элемента И 89, на другие входы которого,подаются номер задачи, отдающей страницы, Нномер задачи, берущей страницы, Н и значение К , Второй выход блока 88 сравнения подключен напервый вход элемента И 90, на другиевходы которого подаются с выходов регистров 86 и 87 И Н з и К ю Выходы элементов И 89 и 90 подключенысоответственно на входы регистров 91и 92 памяти, выходы которых подключены на соответствующие входы элемента ИЛИ 93, выход которого подключенк одному из входов первой группывходов дешифратара 150 блока 1 О.Если К больше К, то обмен осуществляется таким образом, чтобы задача,берущая страницы, была полностью 25удовлетворена. В этом случае на первом выходе блока. 88 сравнения появляется импульс, па которому в регистр 91через элемент И 89 записывается адрес обмена в виде Изд К . Еслиявляется на втором выходе блока 88 сравнения, и в регистр 92 через элемент И 90 записывается адрес страничного обмена в виде 11 ХК, реали 35зующий вариант, когда задача, отдающая страницы, полностью от них освобождается,Блок 1 входных регистров (Фиг, 2)предназначен для формирования полного виртуального адреса, работает также, как и аналогичный блок в устройстве-прототипе, в него дополнительно введены выходы 103 и 104 управляющего регистра 3 для передачи из опе 45рационной системы значений Ь, (длина1-й задачи в страницах оперативнойпамяти), и т., (минимальное числостраниц для выполнения т.-й задачи),Блоки 7 памяти страниц (Фиг. 8)предназначены для хранения страничной50таблицы и обеспечивают воэможность еемодификации, каждый из блоков , содержит часть этой таблицы, Все блокипамяти содержат полнуо страничнуютаблицу, число строк которой равно55числу страниц, которое можно располо-.жить в оперативной памяти. Строкастраничной таблицы описывает единст 13венную страницу оперативной памяти,Блоки 7 работают так же, как и соответствующие блоки в устройстве-прототипе, В строку страничной таблицыдополнительно введена группа 1 Об элементов памяти, в которых хранятся номера задач, определяющие принадлежность.данной страницы оперативнойпамяти к конкретной активной задаче.Злемент 106 (фиг, 9) содержит дешифратор 1 бч, информационный регистр 165, группу 166 элементов памяти, коммутатор 167 и работает также, как и группы элементов памятистроки страничной таблицы в устройстве-пратотипе, В блок 7 введен дополнительный вход, являющийся информационным входом элемента памяти группы Обр подключенный к Одному из выходов первой группы выходов.дешифратора 150 блока 1 О коррекций, для перезаписи номеров активных задач. Кроме того, введены дополнительные вы"ходы с элементов памяти групп 105 -107, подкжоченные на третий вход блока 11 управления страничным обменом,которые служат для передачи адресавиртуальной машины и виртуальной памяти с элемента 105, адреса номераактивной задачи, к которой относитсястраница оперативной памяти, с элементов группы 106, адреса номера сегмента и номера страницы элементовгруппы 107, вся перечисленная информация поступает на вход блока 40сравнения входных адресов,Блок 5 сравнения (фиг. 5) предназначен для сравнения виртуальных адресов страниц, поступающих с выходовблока 1 входных регистров, с номерами виртуальных страниц, хранящихся всоответствующих блоках 7 памяти страниц, и работает так же, как и соответствующий блок в устройстве-прототипе,в немдагалнительна выход кампа 1ратара 39 подключен на первый входблока 11,:Блок 10 коррекции (Фиг, 13) предназначен дпя занесения информации вэлементы памяти группы 106, 113 - 115каждого блока. 7 и работает так же,как и соответствующий блок в устройстве-прототипе, в нега дополнительновведен дешифратор 150 адреса, перваягруппа входов каторога подключена квторому выходу блока 11, а на вторуюгруппу вт;сдав поступает информация обусловиях удаления страниц и частоте23 1327их использования из регистра 116, Выходы дешифратора 150 подключены к соответствующим входам элементов группы 106 номеров задач,Блок 6 местного управления (фиг.7)предназначен для выработки угравляю-.щих сигналов и работает так же, каки соответствующий блок в устройствепрототипе, в него дополнительно введены элемент И 187, первый прямойвход которого является дополнительнымвходом 25 блока 6, второй вход которого является входом 17 блока 6, третий вход которого является входом 22блока 6, а также элемент И 186 к первому входу которого подключен выходтриггера 195, а к второму - выходтриггера 194, выход элемента И 186является дополнительным выходом 32блока 6.Генератор 8 расстановки (Фиг.10),блок 9 управления замещением(Фиг,4) выполнены так же, как и соответствующие блоки в устройстве-прототипе, и выполняют те же функции,Таким образом, при вводе страницыв оперативную память устройство дляуправления виртуальной памятью реализует следующий алгоритм: при установленном бите ожидания ввода-выводаустанавливается адрес требуемойстраницы, вводится требуемая виртуальная страница, а затем сбрасывает 35ся бит ожидания ввода-вывода,При замещении страницы оперативной памяти предлагаемое устройствореализует следующий алгоритм: при ус 40тановленном бите ожидания ввода-вывода удаляется виртуальная страница иэтребуемой Физической страницы оперативной памяти, устанавливается адресвводимой виртуальной страницы а эаФ45тем сбрасывается бит ввода-вывода,Через определенные промежутки времени под управлением операционной системы выполняется корректировка битов частоты использования страниц. Во время одного цикла выполнения процедуры одновременно корректируются биты частоты использования страниц в соответствующих строках каждой части страничной таблицы в каждом блоке 7 памяти страниц.При достижении критического числа сбоев или успешных обращений к оперативной памяти блок 11 управления 324 страничным обменом через блок 6 местного управления формирует прерывание, которое обрабатывается в операционной системе, при этом в блоке 11 формируются адреса задач, участвуюших в обмене страниц. Сформированные адреса обмена с выходов соответствующих формирователей адреса группы 57 поступают на первую группу входов дешифратора 150 блока 10, на другую группувходов которого поступает информация об условиях удаления страниц и частоте их использования из регистра 116,С выхода дешифратора 150 сигналы поступают на входы элементов памяти группы 106 блока 7, меняют в них номера задач, к которым принадлежат соответствующие страницы, одновременнообнуляются счетчик 61 страничных сбоев и счетчик 62 успешных обращенийк оперативной памяти. После окончания одного цикла оптимального перераспределения страниц оперативнойпамяти между активными задачами устройство продолжает работать в режимединамической трансляции и преобразования адреса до тех пор, пока сноване будут достигнуты критические значения числа страничных сбоев или успешных обращений к оперативной памяти.Таким образом, предлагаемое устройство для управления виртуальнойпамятью реализует процесс преобразования адресов с помощью аппаратныхсредств, а также постоянный учет чис.ла успешных обращений и числа страничных сбоев при обращении к страницам оперативной памяти, принадлежа-,щим каждой активной задаче, и поэтой информации оптимально перераспределяет страницы оперативной памяти между активными задачами, что поз.воляет в целом сократить число страничных обменов с внешней памятью изначительно повысить производительность вычислительной системы,Формула изобретения Устройство для управления виртуальной памятью по авт. св, У 955076, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет оптимального перераспределения страниц оперативной памяти между активными задачами, в него введен блок управления страничным обменом, причем информационный выход.25 1.32/1 блока входных ретистров подключен к входу задания числа страниц для решения активной задачи блока управления страничным обменом, информационныйвыход которого подключен к входу ана-лиза адресов страничного обмена блока коррекции, выходы признаков равенства блоков сравнения подключены к входу анализа сбоев блока управления страничным обменом, пятый управ 13 26ляюпгий выход блока местного управления подключен к входу опроса наличия сбоев блока управления страничным обменом, выход признака наличиясбоев которого подключен к входу управления прерыванием блока местногоуправления, вторые информационные выходы блоков памяти страниц подключены к входу виртуальных номеров блокауправления страничным обменом,)3271Изобретение относится к вычислительной технике и может быть использовано в вычислительных машинах свиртуальной памятью,Цель изобретения - расширениефункциональных возможностей путемобеспечения динамического оптимального перераспределения страниц ОП между активными задачами. 1 ОНа фиг1 приведена Функциональная схема устройства для управлениявиртуальной памятью; на Фиг. 2 - схе,ма блока входных регистров; на фнг, 3 схема блока выходных регистров; нафиг. 4 - схема формирователеи; нафиг, 5 - схема блоков сравнения; нафиг. 6 - схема компаратора; нафиг, 7 схема блока местного управления; нафиг. 8 - схема блоков памяти страниц; 20на фиг. 9 - схема элемента памяти; нафиг. 10 - схема генератора расстановки; на Фиг. 11 - схема блока управления замещением; на фиг. 12 - схемаузла приоритета; на фиг, 13 - схема 2 бблока коррекции; на фиг. 14 - схемаблока управления страничным обменом;на фиг. 15 - схема блока определениячисла страничных сбоев; на фиг. 6,схема блоков расстановки; на фиг. 17 - ЗОсхема первого блока сравнения; наФиг18 - схема второго блока сравнения, на фиг. 19 - схема формирователя адреса обмена страниц; на фиг, 20 -временная диаграмма тактовых импульЗБсов; на фиг, 21 - пространство состояния активной задачи в оперативнойпамяти.Устройство для управления вирту"альной памятью (Фиг, 1) содержитблок 1 входных регистров, блок 2 выходных регистров, управляющий регистр 3, регистр 4 общего назначения,блоки 5 сравнения, блок 6 местногоуправления, блоки 7 памяти страниц,генератор 8 расстановки, блок 9 управления замещением, блок 10 коррекции, блок 1) управления страничнъгмобменом, вход 12 оператинной памятивход 13 задания режима, вход 14 синхронизации, вход 15 задания кода операции устройства, входы 16-24 блока 6местного управления, вход 25 управления прерыванием блока 6 местного управления, выходы 26 - 31 блока 6местного управления, дополнительныйвыход 32 блока 6 местного управления,вход 33 устройства, информационныйвыход 34 блока 1 входных регистров,32выход 35 сигнала прерывания, информационньгй выход Зб устройства,Блок 11 управления страничным обменом (фиг, 14) содержит блоки 37 определения числа страничных сбоев,первый 38 и второй 39 блоки расстановки, первый 40 и второй 4) блокисравнения первый - четвертый дешифраторы 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 задержки, группу 7)элементов И, элемент И 72,Первый 38 и второй 39 блоки расстановки имеют одинаковую конструкцию (Фиг. 16) и содержат группу 73регистров, группу 74 блоков поразрядного сравнения, группу 75 элементов И, группу 76 элементов ИЛИ, группу 77 регистров перезаписи, дешифратор 78, коммутатор 79, группу 80 регистров памяти.Второй блок 41 сравнения (Фиг, 8 )содержит блок 81 памяти, группу 82регистров памяти, группу блоков 83сравнения, группу 84 И элементов,группу элементов 85 И,Формирователь 57 группы (фиг,)9)соцержит первый 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 - )38, 1327113оставитель А. ехред И.Попов актор Л,Веселовска рект илипенко каэ 3391/ч 6 Тирах 672Государственного комит елам изобретений и отк сква. Ж, Раушская н одписноеР ета С рытий 113035,Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, з 13Блок 5 сравнения (фиг. 5) содержит.компаратор 139, регистр 40, элемен.ты И 141 и 142Генератор 8 расстановки (фиг10)содержит группу 143 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, коммутатор 144 и дешифратор 145.Блок 9 управления замещением(фиг. 11) содержит элементы ИЛИ 46,дешифратор 147, коммутаторы 148 иузел 149 приоритета,Блок 10 коррекции (фиг. 13) содержит дешифратор 150, элементы И 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 элементы И и шестой 88,пятый 189, первый - четвертый 190 -193 элементы ИПИ и триггеры 94 и 195.Устройство для управления вир.туальной памятью работает следующимобразом.Режимы работы устройства определяются путем возбуждения устройствомуправления процессора соответствующего входа блока 6 местного управления.Во время выполнения операции, связанной с обращением к ОП, устройствоуправления процессора возбуждаетвход 17 блока 6, Если бит слова состояния программы, определяющий режимпреобразования адресов, не установлен, то во время действия импульса СОоткрывается элемент И 181, сигнал с 271 34выхода которого через элемент ИЛИ 189производит запись в регистр 156 физического адреса, поступающего навход регистра 156 через коммутатор 159 блока 2 выходных регистров.Если процессор работает в режимепреобразования адреса, то устанавливается соответствующий бит слова состояния программы и указанная выше информация загружается в управляющийрегистр 3, сюда же передается инфор"мация о количестве страниц, минимально необходимых для выполнения каждойактивной задачи,а также информацияо длине задачи в страницах, определяемой значением параметра КЕС 1 ОИоператора ЕХЕС. Во время выполненияоперации, связанной с обращением коперативной памяти, устройство управления возбуждает вход 17 блока 6местного управления. Тогда во времядействия импульса СО открывается эле"мент И 1 85, по сигналу с выхода 27.25 которого логический адрес записывается в регистр 94 логического адресаблока 1 входных регистров. В блокеадрес виртуальной страницы формируется так же, как в устройстве"прототи"пе, Разряды адреса виртуальной страницы, кроме смещения, поступают навходы группы 143 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ генератора 8 расстановки, результат с выхода которой через ком-.мутатор 144 поступает на адресныевходы групп 105-15 элементов памя"ти каждого из блоков 7 памяти стра"ниц, Информация; прочитанная с выб"раиной ячейки групп 105 - 07, 113и 15 элементов памяти поступает всоответствующий блок 5 сравнения.Одновременно информация с выбраннойячейки групп 105 - 107 элементов памяти каждого из блоков 7 поступаетна соответствующие входы блока 40сравнения входных адресов блока 11управления страничным обменом, Вблоке 40 по информации из группы 105 -107 элементов памяти определяется ко-,личество страниц оперативной памяти, 50относящихся к каждой активной задаче. Условия удаления страниц из оперативной памяти, сформированные элементами И 121 - 125 блока 7, и соответствующая информация из групп 108,1 О - 113 элементов памяти записывается в регистры .116 и 17 соответственно сигналом с выхода 30 блока 6местного управления, поступающим че"5 1327рез открытый элемент И 179 во времядействия импульса С 1. В блоке 5 производится сравнение адресов виртуальных страниц. поступающих с блоковвходных регистров и блоков 7 памятистраниц,Если сравнение произошло, выбранная строка групп 105-15 элементовпамяти загружена и данная страницане используется в операциях вводавывода, то это указывает на то, чтотребуемая виртуальная страница находится в оперативной памяти и доступна. Эта ситуация запоминается в регистрах 140 каждого из блоков 5 посигналам, поступающим с выхода 29открытого элемента И 179 во времядействия импульса С 1, и характеризует успешное обращение к странице оперативной памяти, Эта информация с 20выхода коммутатора 76 блока 5 поступает на первый вход соответствующегоблока 37 определения числа страничных сбоев. Сигналы с выходов элементов И 141 поступают в блок 2 на элемент ИЛИ 163, с помощью которого определяется, находится ли требуемаястраница в оперативной памяти и раз.решено ли к ней обращение. Эта ситуация запоминается в триггере 194 во 30время действия импульса С 1 по сигналу, поступающему на вход синхронизации триггера 194 через открытый элемент И 179,Если сравнение произошло, выбранная строка групп 105-115 элементовпамяти загружена, но данная страница используется в операциях ввода-вы-вода, то это указывает на то чтотребуемая виртуальная страница находится в оперативной памяти, но недоступна для обрашений со стороны процессора. Эта ситуация запоминаетсяв триггере 195 ( единичное состояниево время действия импульса С 1 по счгкалу, поступающему на вход синхронизации триггера 195 через открытыйэлемент И 179. Это условие формируется элементами И блоков 5 и элемен- том И 190 блока 6.Если с помощью элемента ИПИ 63установлено, что доступ к зиртуальнойстранице возможен ( единичное состояние триггера 194, то ее сформированный физический адрес записывается врегистр 156 физического адреса посигналу с выхода 28 блока 6 местного управления, поступающему на управляющий вход регистра 156 физичес 13 бкого адреса через элемент ИЛИ 184 и открытый элемент И 180 во время действия импульса С 1. Физический адрес страниць 1 поступает на вход регистра 56 через коммутатор 159. Физический адрес формируется как совокупность номера блока 5 сравнения, где произошло опознание виртуальных адресов, кода, поступающего с выхода коммутатора 144 генератора 8 расстановки, и смещения, поступающего с выхода 99 регистра 94 логического адреса, Двоичный код номера блока 5 . сравнения формируется формирователем 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 элементов памяти производится только прн установке триггером кода, операции, определяющего запись информации в оперативную память, В этом случае открыт элемент И 34После формирования условий для определения свободной или возможно замещаемой страницы они анализируются блоком 9 управления замещением, Сформированный адрес возможко замещаемой страницы и способ ее замещения помещаются в регистр 157 замещаемой страницы и в регистр 158 флажков соотве,ственно пс сигналамс выхода 28 элемента И 82 во время действия имгульса С 2.Если триггеры 194 и 195 находятся в нулевсм состоянии, то зто определяет, что требуемой виртуальной страницы132711цет в оперативцой памяти, что соответствует страничному сбон. Эта информация через элемент И 186 поступает ца второй вход соответствующего блока 37 определения числа страничных сбоев. Если хотя бы в двух блоках 37 число успешных обращений К к оперативной памяти или число страничных сбоев П достигают своих критичес О ких значений К или П, которые выкрбираются с учетом специфических характеристик потока задач, решаемых в данной вычислительной системе, или могут быть получены в результате ими тационного моделирования вычислительного процесса, то информация об этом с первых выходов соответствующих блоков 37 через элемент И-ИЛИ 58 поступает на дополнительный вход 25 блока 6 и открывает элемент И 87, сигнал с выхода 26 блока 6 вызывает прерывание, определяющее, что необходимо провести перераспределение страниц оперативной памяти между активными задачами. После обработки этих прерываний операционная система передает в блок 11 управления страничным обменом через блок 1 входных регистров для каждой задачи, участвующей в страничном обмене, минимально; допустимое число страниц оперативной памяти, необходимое для решения каждой задачи, и длину задачи в страницах оперативной памяти.В блоке 11 определяются пары задач, находящиеся одновре 35 менно в оперативной памяти, например задаче, имеющей наибольшееизбыточное число страниц, ставится в соответствие задача,требующая наибольшего числа40 страниц оперативной памяти для успешного завершения. В блоке 11 определяется количество страниц, которые будут участвовать в обмене, и формируются адреса обмена в группе бло 45 ков 57, которые с выхода блока 11 поступают на вход дешифратора 150 блока 10 коррекции, в котором анализируются адреса задач, участвующих в обмене и условия обмена. В реэуль 150 тате такого анализа по сигналу дешифратора 150 производится смена номера задачи в группе 106 элементов памяти блоков 7 путем передачи в группу 106 . блоков 7 памяти страниц "дающих" задач, номеров берущих" задач, При действии импульса С 1 открывается элемент И 173 бло 1 а 6, сигнал с выхода 30 которого и сигнал с выхода эле 3 8мента 1 ГИ 188 открывают элемент И 16 того блока 7, который выбран дешцфратором 145 генератора 8, Сигнал с выхода открытого элемента И 126 поступает ца управляющие входы группы 106 элементов памяти, разрешая запись нового номера активной задачи, участвующей в страничном обмене, с выхода дешифратора 150 блока 1 О коррекцииПосле завершения цикла страничных обменов между задачами, одновременно находящимися в оперативной памяти, устройство продолжает работать в режиме динамического преобразования адресов до тех пор, пока не будут снова достигнуты значения К,р или 0 р хотя бы для двух активных задач, При обращении к внешней памяти блок 10 коррекции анализирует условие, сформированное дешифратором 147, которое определяет, возможно ли осуществить замещение или ввод требуемой страницы. Если это возможно, то в соответствующей строке страничной таблицы устанавливается бит-указатель ожидания ввода-вывода. Для этого сигнал с выхода открытого элемента И 54 блока 10 коррекции поступает на элементы И 130 каждого из блоков 7 памяти страниц, В выбранном узлом 149 приоритета блоке 7 памяти страниц открывается элемент И 130 при наличии сигнала с выхода 30 элемента И 177 блока 6 местного управления, и во время действия импульса С 2 осуществляется запись в группу 113 элементов памяти. Информация на входе группы 113 элементов памяти каждого иэ блоков 7 памяти страниц устанавливается с выхода элемента ИЛИ 155 блока 10 коррекции.Если при анализе условий блоком 10 коррекции установлено, что ввести требуемую страницу невозможно, то . бит-указатель ожидания ввода-вывода страничной таблицы не помечается.Если требуемойвиртуальной страницы нет в оперативной памяти, то во время действия импульса С 2 открывается элемент И 183 сигнал с выхода 26 которого.вызывает прерывание, определяющее, что требуемой виртуальной страницы нет в оперативной памяти,Если триггер 94 находится внулевом состоянии, а триггер 95 - в единичном, то это означает, что требуе" мая виртуальная страница находится в оперативной памяти, но использует10 9 132713 0 15 20 ся системой ввода-вывода, Поэтомуникакая строка страничной таблицы непомечается, так как сигнал с выходатриггера 195 закрывает элемент И 177,а в момент действия импульса С 2 открывается элемент И 184, что вызывает прерывание, определяющее, что процессору разрешено обращаться к странице, которая используется системойввода-вывода. При выполнении операций ввода-вывода необходимо ус.тановить бит-указатель ожидания ввода"вывода в страничной таблице для реальных физических страниц оперативной памяти, к которым производится обращение при вь: - полнении этих операций, После окончания операции ввода-вывода бит-указатель ожидания ввода-вывода сбрасывается. Для выполнения таких действий процессором в младшие разряды регистра 4 общего назначения устанавливается адрес реальной физической страницы, в соответствующий старший разряд - код, определяющий установку или сброс бита-указателя ожидания ввода-вывода, а устройство управления процессора возбуждает вход 18 блока 6 местного управления. Таким образом, младшая часть физического адреса страницы с выхода регистра 4 общего назначения через коммутатор 144 генератора 8 расстановки поступает на адресный вход групп 05-115 элементов памяти каждого из блоков 7 памяти страниц, Старшая часть физического адреса страницы дешифруется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один из блоков 7 памяти страниц, т,есоответствующая час.ть страничной таблицы. Код установки или сброса бита-указателя ожидания ввода-вывода поступает на вход группы 113 элементов памяти каждого из блоков 7 памяти страниц через элементы ИЛИ 155 и И 151, В момент действия импульса С 1 открывается элемент И, сигнал с выхода 30 которого открывает элемент И 129 того блока 7 памяти страниц, который выбран дешиф- ратором 145 генератора 8 расстановки, Сигнал с выхода открытого элемента И 129 через элемент ИЛИ 136 поступает на управляющий вход группы 113 элементов памяти, вызывая запись информации, поступающей на вход элементов5 гмя ти, с якхола элемент ИЛ 155 блока 1 О коррекции,При первоначальной загрузке физической страницы в пе 1)ативцую память или очистке оперативной памяти необходимо установить или сбросить битуказатель запрещения удаления страниц и бит-указатель действительности строки страничной таблицы, Для выполнения таких действий процессор устанавливает в младших разрядах регистра 4 общего назначения адрес реальной Физической страницы, в соответствующих старших разрядах - биты, определяющие действительность строки страничной таблицы, и код, определяющий запрещение удаления страниц из оперативной памяти, а устройство управления процессора возбуждает ьход 19 блока 6 местного управления.Таким образом, младшая часть Физического адреса страницы с выхода регистра 4 общего назначения через ком мутатор 144 генератора 8 расстановкипоступает на адресные входы групп 105115 элементов памяти каждого из блоков 7 памяти страниц, Старшая частьфизического адреса дешифрируется дешифратором 145 генератора 8 расстановки, что позволяет выбрать один иэблоков ,памяти страниц, т,е. соответствующую часть страничной таблицы.1(оды установки битов-указателей за-.прещения удаления и действительности 35строки страничной таблицы поступаютна входы групп 114 и 115 элементовпамяти каждого из блоков 7 памятистраниц через элементы И 152 и 153блока 10 коррекции, В момент действия импульса С открывается элемент И 175 и через элемент ИЛИ 188сигнал с выхода 28 элемента ИЛИ 188открывает элемент И 128 того блока 7памяти страниц, который выбран дешифратором 145 генератора 8 расстановки.Сигнал с выхода открытого элемента И 128, поступающий на управляющиевходы групп 14 и 115 элементов памяти, вызывает запись информации, поступающей на входы групп 11 и 115/элементов памяти с выхода элементов И 152 и 153 блока 10 коррекциисоответственно. При первоначальной загрузке виртуальной страницы в оперативную память информация об этой странице записывается в соответствующую строку страничной таблицы. При этом уст 13 1327 3и нДающее подмножество по Л. упорядочивается путем расстановки элеменл лтов 1 от Л до Л,14 аХ94Для элементов берущего" подмножества 1 определяются коэффициентыи элементы 1 упорядочиваются 1 К 11от Л" до Л . Далее производят141 алЕлилерераспределение страниц ОП между активными задачами, учитывая тот факт, что задача с шп Л; может отдать максимальное число страниц а задача с шах И; может принять максимальное число страниц ОП: Кщв 1 пС.-Х. рХ,-Ьр 16 Х,де 1 . 15) При этом обмен между 1-й и -й задачами производится таким образом, чтобы.полностью удовлетворить 1-ю задачу, если 20С 6) ЗОХ - 1,11либо полностью освободить "ю задачуот избыточных страниц ОП, если1.- Х.Х. - 1,ф.,1Вместе с тем при ,л удовлетвоалрить задачи из множества 1- эа счетзадач из множества 1 не представляется возможным. Это условие такжеможет служить основанием для выборавеличин К и ВБлок 11 управления страничным обменом (фиг, 2) работает следующимобразом,При первоначальной загрузке вирЭбтуальной страницы оперативной памятиинформация об этой странице записывается в соответствующую строку страничной таблицы в группы 105 в 5элементов памяти блока 7. Одновременно из групп 105 - 107 элементовинформация: номер виртуальной машиныи номер виртуальной памяти группаэлементов 105); номер задачи (группа4 бэлементов 106); номер сегмента и номер страницы (группа элементов 107) -поступает в блок 40 сравнения входных адресов страниц. В блоке 40 сравниваются адреса, записанные в групбОпах 105 - 107 элементов, и определяется, сколько страниц оперативной памяти - ХХ относится к каждой задаче,поступившей на выполнение. Эта информация из блока 40 поступает в первыйи-й блоки памяти, причем в перббвый блок каждой группы поступает информация о первой задаче, во второйо втовой и т,д, Количество блоков памяти соответствует числу страниц оперативной памяти, На другой вход блоков памяти группы 48 через дешифратор 42 поступает из группы 109 элементов блока 7 число обращений к страницам данной задачи - НЛ, первый выход каждого блока памяти группы 48 подключен на вход сумматора 46, в котором производится подсчет общего количества задач, одновременно находящихся в оперативной памяти, по числу блоков памяти группы 48, в которые поступила информация, Вторые и третьи выходы укаэанных блоков 48 памяти подключены на входы блоков вычисления Л,. группы 52, выходы которых подключены на входы блока 38 расстановки и на входы сумматора 47, в коХ" л тором производится вычислениеЬх 1 В блоке 38 расстановки производится определение максимального коэффициента Л 4 и последующих Л" до Л", при этом на первый вход блока 38 расстановки .поступает Л , а на поЬ 4 Хследний - Л,х,; , С выходов сумматоров 46 и 47 информация поступает на входы блока 56, в котором производится вычисление среднего значенияср по формуле нЛ Хл 1 1Выход блока 56 подключен на первый вход блока 41 сравнения с Л , наСр К остальные входы которого поступают значения коэффициентов. от Л" до4 л 4 Хс выходов блока 38 расстанов 411 Слкипри этом Л, поступает на второй вход блока 41, Л ., - на третин и т.д., на последний вход бло.ка 41 поступает 71"с последнего выхода блока 38, В блоке 4 сравнения с 1, множество Л" разделяется на два подмножества: подмножество задач с избытком страниц оперативной 1л лпамяти (1 , Я. -. Л" ), подмножество заСр лдач, испытывающих недостаток страниц, оперативной памяти (1,Ь ( Я " ). Номера задач иэ множества 1 поступают на первую группу входов дешифратора 44, на вторую группу входов которого поступают иэ блока 1 входных реогистров значения Ь, для всех активных задач, на третью группу входов: дешифратора 44 поступают значения Х из блоков 48 памяти группы, при этом на выход дешифратора 44 проходят значения Х и Ь , соответствующие Л", 61, таким образом что на первую пару15 13711входов дешифратора 44 поступают Х,и Ь , соответствующие А из мко 1 сижества 1 , на последнюю пару выхоо Лдов - Хи Ь , соответствующие;,)Первая пара выходов дешифратора 44подключена на входы первого блока 50памяти группы, в который записываются значения Х и Ь., соответствующиезадаче с ,3" , из 1, а последняя 18группа выходов дешифратора 44 - кпоследнему блоку памяти группы 50,в которой записываются значения Х,Ь, соответствующие 1" . из 1. Выщходы блоков 50 памяти группы подключены на входы блоков 54 вычислениягруппы, в которых для каждой задачииз множества Т производится вычисление выражении Х -Ь , 11 , и этотрезультат с номером задачи, к которой он относится, передается с выхода соответствующего блока памяти .группы 54 на первый вход соответствующего формирователя адреса страничного обмена группы 57. Номера задач р 5из множества Еб поступают на первуюгруппу входов дешифратора 43, на вторую группу входов .которого из блока 1 поступают значения Ь., на третью группу - сигналы с выходов блоков 37 определения текущего числасбоев страниц оперативной памяти.Дешифратор 43 пропускает значенияЙ , Ь; для каждой задачи из множества Т на входы соответстнующих блоб 35ков памяти группы 49, выходы которыхподключены на входы соответствующихблоков группы 53, в которых производится вычисление Ь . по формулед;- для каждой задачи из множества Тб. Значения 1". с выходов соответ 1ствующих блоков группы 53 поступаютна входы блока 39 расстановки, который функционирует так же, как . 45блок 38 расстановки. На первом выходе блока 39 расстановки формируетсяномер задачи, для которой 1" , напоследнем - номер задачи у которойУкаэанные номера поступают на 50 первую группу входов дешифратора 45, на вторую группу входов которого по ступают значения Ь. иэ блока 1, на третью - значения Х. иэ блокон памяти группы 48. На первую пару выходов дешифратора 45 поступают значения Х ,Ь, соответствующие задаче из множества 1 , для которой 3" , на побфследнюю пару дешифратор 45 пропуска 3 16ет значения Х, Ь задачи из множесткф нва 1, для которой 3 ,. . Первая пара выходов дешифратора 45 подключена на вход первого блока памяти группы 51, в который поступают значения Х Ь, для задачи Х, е 1 , у которойи т.д последняя пара выходов подключена на входы последнего блока памяти группы 51, в который записываются значения Х, Ь, для задачи 1 , у которой М",. , Выходы блоков памяти группы 51 подключены на входы соответствующих блоков вычисления группы 55, в которых производятся вычисления величин К = Ь;-Х; для каждой задачи из множества 1 результаты вычислений с выходов блоков группы 55 поступают на вторые входы формирователей адресов группы 57 страничного обмена, выходы которых подключены к первой группе входов дешифратора 150 блока 10 коррекции. При этом на входе каждого формирователя адреса группы 57 формируется адрес страничного обмена, включающий н себя номер задачи, отдающей страницы К, номер задачи, берущей страницы М б, и число страниц, участвующих в обмене, Кб или К. Сформиронанные адреса поступают на первую группу входов дешифратора 150 блока 10, на вторую группу входов которого из блока 116 поступают адреса страниц, наи- менее используемых и принадлежащих задачам, между которыми производится страничный обмен, Страничный обмен между активными задачами фактически заключается в замене в группе элементов 106 памяти блока 7 номера задачи, отдающей страницы, на номер задачи, берущей страницы, при этом количество страниц,в которых будет проведена смена номеров задач, определяется в соответствующем формирователе 57 адреса группы иэ выраженияК=пппЬ. -ХХ.-Ь.11,ИТ,Зе Т.Задача иэ множества 1, у которойиберет максимальное число страниц, задача из множества 1, у которой 1 отдает максимальное число страниц, .Для таких пар задач величины, их характеризующие - Х , Ь.о1(1 ЕТ), Х, Ь 1 (1 ЕТ), поступают через соотнетствуюшие блоки вычисления группы 54, в которых определяются значения К = Х; - Ь, на входы одногс1 ф