826353

ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоцивлистическикРеспубликлв делам извбретеиий и вткрытийОпубликовано 30.04.81. Бюллетень16Дата опубликования описания 30.04.81 А. Л. Ганькин, Н. Н. Захаревич и А. Н. СтепановМосковский ордена Трудового Краного фнамнц ".инженерно-физический интим(54) УСТРОЙСТВО ДЛЯ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ ПАМЯТИИзобретение относится к вычислительной технике и может быть использовано в мультипрограммных ЭВМ с одноуровневой организацией памяти.Известно устройство, позволяющее аппаратно распределять оперативную память между выполняемыми программами в мультипрограммном режиме и содержащее ассоциативную память для хранения номеров страниц, регистры, счетчики и логические схемы для адресации списков свободных и занятых областей памяти 1.Недостатком такого устройства является большой объем оборудования. Наиболее близким к предлагаемому по технической сущности и достигаемому результату является устройство для выделения малых участков памяти, содержащее регистр запроса, счетчик адреса, регистр адреса, схему управления, схему сравнения, счетчик областей, регистр адреса последнего информационного слова, местную память с произвольной выборкой, регистр числа, сумматор адреса, регистр кода операции, триггеры вентили, коммутаторы и схемы ИЛИ. 2Это устройство предусматривает делениепространства оперативной памяти на блоки, которые в свою очередь делятся на области одинаковой в пределах блока длины. Базовые адреса начала блоков, размеры областей и признаки их занятости хранятся в виде- информационных слов в местной памяти устройства - по одному слову на блок. При подаче запроса на область определенной длины ее размер записывается в регистр за - проса. Затем производится последователь О ный просмотр информационных слов в местной памяти в поисках наиболее подходящей по размерам области. При нахождении блока, содержащего такие области, производится дальнейший просмотр информационного слова путем его сдвига на регистре числа 1 с целью нахождения свободной области вэтом блоке. При освобождении памяти производится поиск информационного слова соответствующего блоку, содержащему ненужную более память. Затем производится коррекция информационного слова 2. Недостатком этого устройства является большой объем оборудования, вызванный необходимостью формирования и просмотра) с 1 5О15 5055 гсцця - прсцнцустрой,".с г ц;: цель дотаГс. теч, что в х рссстс.динам,чсксэсо пасцределсцц цая", э;.ржцце ргцсгр запроса, счетчик сэбл;сс- счсск адэс са, коммутатор, регистр адрс са, х з,сравнения, блок управления, цэвый и второй элементы И, элмеп ИЛИ, триггер управления, причем выход счетчика адреса соединен с первым входом узла сравнения, выход коммутатора ссэдццец с входом регистра адреса, выход узла сравнения соединен с первым входом блока управления, введены сдвиговый регистр, счетчик длины участка, причем выход эс псстра адрса соединен со вторым входом хзгс сргцсцц и с адресным гходом устроиства, выход счетчика адреса соединен с црвым входом коммутатора, второй вход коммутатора соединен с адресным входом устройства, третий вход коммутатора соединен с первым выходом блока управления, выход сдвигового регистра соединен со вторым входом блока управления и со сбросовым входом сдвигового регистра, второй выход блока управления соединен с первым входом первого элемента И, третий выход блока управления соединен с первым входом второго элемента И, четвертый выход блока управления соединен со счетным входом счетчика длины участка, запросный вход устройства соединен со входом регистра запросов, пятый выход блока управления соединен с управляющим входом счетчика длины участка, выход регистра запросов соединен со входом счетчика длины участка, третий вход блока управл- ния соединен с управляющим входом устройства, выход счетчика областей соединц с четвертым входом блока управления и с выходом отсутствия пространства памяти устройствс, выход ссцса длинь учакЗ соединен с цяпгым входом бгцэка уцр;св,ция. с управляющим входом счетчика обласгй, с первым входом элемента ИЛИ и с цл- вым входом трисеэа управления, выхсэд узла сравнцц содипи с дцццчным входом триггера управлцця, выход триггсра управ ления соединен со втсээым входом элемента ИЛИ, выход элемента ИЛИ соединен со вторыми входами первого и второго эгментов И, выход первого э;емецта И соединен с нулевым информационным входом сдвигового регистра, выход второго элемента И соединен с единичным информационным вхо дом сдвигового регистра, вход синхроимпуль сов устройства соединен со счетным входом счетчика областей с управляющим входом сдвцгового регистра, с входом счетчика и с шестым входом блока управления, седьмой вход блока управления соединен с входом логического нуля устройссва,Кроме того, блок управления содержит два элемента НЕ, девять элементов И, эле 4.,ент ИНЕ, пять элементов ИЛИ, чегьсре триггера, причем вход первого элемента НЕ соединен со вторым входом блока, выход первого элемента НЕ соединен с первым входом первого элемента И, выход первого элемента И соединен с первым входом первого элемента ИЛИ, выход црвого элемента ИЛИ соединен с единичным входом первого триггера ц с первым входом второго элемента И, выход второго элемента И соединен с первым входом второго элемента ИЛИ, с первым входом третьего элемента И и с пятым выходом блока, выход третьего элемента И соединен с первым выходом блока, второй вход первого элемента И соединен с первым входом четвертого элемента И, с синхровходом первого триггера, с первым входом пятого элемента И, с первым входом шестого элемента И, с первым входом седьмого элемента И, с шестым входом блока, выход седьмого элемента И соединен со вторым выходом блока, выход шестого элемента И соединен с третьим выходом блока, единичный выход первого триггера соединен со вторым входом пятого элемента И, выход пятого элемента И соединен со вторым входом второго элемента ИЛИ и с четвертым выходом блока, нулевой выход первого триггера соединен со вторым входом второго элемента И, вход второго элемента НЕ соединен с четвертым входом блока, выход второго элемента НЕ соединен с первым управляющим входом вто- ЗО рого триггера, с первым управляющим входом третьего триггера и с управляющим входом первого триггера, единичный выход второго триггера соединен с третьим входом первого элемента И, со вторым входом 35с тгц ргсэго элемента И и со вторым входом гьсо элемента И, нулевой выход второго трипера соединен с первым входом элемента И - НЕ ц с первым входом восьмого элемента И, информационный вход второго грцггс ра содццец с нулевым выходом треть О пэ триггера, вход синхронизации второготриггера соединен с входом синхронизации третьего триггера, с входом синхронизации четвертого триггера и с пятым входом блока, второй управляющий вход второго, третьго триггеров и управляющий вход четвертого триггеров соединены с третьим входом блока, информационный вход третьего триггера соединец с выходом элемента И - НЕ,единичный выход третьего триггера соединен со вторым входом восьмого элемента И ц со вторым входом элемента И - НЕ, информацисшцый вход четвертого триггера соединен с седьмым входом блока, выход четвертого триггера соединен со вторым входом седьмого элемента И и с первым входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым входом шестого элемента И и с третьим входом седьмого элемента И, выход восьмого элемента И соединен со вторым входом третьего элемента ИЛИ и с .третьим вхосчетчик 4 длины участка. Далее производится поиск свободного участка памяти, заключающийся в отыскивании в регистре 1 последовательности из нужного количества нулей. При появлении любого нуля после 55 дом шестого элемента И, выход третьего элемента ИЛИ соединен с первым входом девятого элемента И, выход девятого элемента И соединен со вторым входом первого элемента ИЛИ, второй вход девятого элемента И соединен с первым входом блока, первый вход четвертого элемента ИЛИ соединен с пятым входом блока, второй вход четвертого элемента ИЛИ соединен с выходом четвертого элемента И, выход четвертого элемента И, выход четвертого элемента ИЛИ соединен с нулевым входом первого1 О триггера,На фиг. 1 приведена блок-схема устройства; на фиг. 2 - структурная схема блока управления.Устройство содержит сдвиговый регистр 15 1, счетчик 2 адреса, регистр 3 запроса, счетчик 4 длины участка, регистра 5 адреса, коммутатор 6,счетчик 7 областей, узел 8 сравнения, триггер 9 управления,.элементы И 10 и 11, элемент ИЛИ 12, блок 13 управления,запросный вход 14 устройства, адресный выход 15 устройства, выход 16 отсутствия пространства памяти устройства, адресный вход 17 устройства, третий выход 18 блока управления, второй выход 19 блока управления, первый выход 20 блока управления, четвертый выход 21 блока управления, пятый выход 22 блока управления, пятый вход 23 блока управления, второй вход 24 блока управления, первый вход 25 блока управления, управляющий вход 26 устройства, четвертый вход 27 блока управ- ЗО ления, вход 28 синхронизации импульсов устройства, вход 29 логического нуля устройства, триггеры 30 - 33, элементы И 34 - 42, элемент И - НЕ 43, элементы НЕ 44 и 45, элементы ИЛИ 46 - 49.Устройство работает следующим образом.Распределяемая между программами память делится на области фиксированной длины. Программе может быть выделен участок памяти равный одной или нескольким последовательным областям. Каждой об д ласти поставлен в соответствие один разряд регистра 1. Занятой области соответствует состояние разряда 1, а свободной - О. В процессе работы устройства происходит непрерывный сдвиг содержимого регистра 1, замкнутого в кольцо; синхронно со сдви гом регистра меняется содержимое счетчика 2, указывающее номер области, соответствующей разряду регистра 1. Режим работы устройства, (Выделение, Освобождение) определяется кодом, подаваемым на вход 26. В режиме выделения памяти на вход 14 подается код запроса - уменьшенная на единицу длина требуемого участка в областях, который заносится в регистр 3 запроса. Код запроса заносится затем в любой единицы в старшем разряде регистра 1 адрес этой области заносится в регистр 5 через коммутатор 6.Появление последующих нулей в старшем разряде вызывает вычитание единицы из счетчика 4 до тех пор, пока не произойдет его обнуление. Если последовательность нулей имеет недостаточную длину; то при появлении следуюшей последовательности нулей происходит повторное занесение кода запроса из регистра 3 в счетчик 4 и адреса в регистр 5. Если требуемой последовательности нулей не обнаружено в регистре 1, на что указывает переполнение счетчика 7, на выход 16 выдается сигнал отсутствия свободной памяти. После нахождения требуемой последовательности нулей производится установка соответствующих разрядов регистра 1 в единицу, для чего код запроса заносится в счетчик 4 и содержимое регистра 5 сравнивается с текущим адресом в счетчике 2 с помощью узла 8. При равенстве этих кодов триггер 9 устанавливается в единицу, разрешая запись в младший разряд регистра 1 единицы через элемент И 10 и элемент ИЛИ 12 с одновременным вычитанием единицы из содержимого счетчика 4. Об окончании процесса записи сигнализирует обнуление счетчика 4. Адрес начала выделенного участка снимается с выхода 15.При освобождении памяти код запроса передается с входа 14 на регистр 3, а адрес начала освобождаемого участка - на вход 17 и далее через коммутатор 6 на регистр адреса 5. Далее производится поиск участка с указанным адресом путем сравнения содержимого регистра 3 с текущим адресом в счетчике 2. Если результат сравнения - истина, то производится установка триггера 9 в единицу и запись нулей в регистр 1 через элемент 1. Количество нулей определяется содержимым счетчика 4, из которого при этом вычитаются единицы.Работает блок 13 следующим образом. Код, определяющий режим работы, подается по входу 26, в результате чего триггеры 31 - 33 устанавливаются в состояние 110 - режим выделения памяти или 001 - режим освобождения памяти.В режиме выделения памяти высокий потенциал на прямом выходе триггера 31 разрешает прохождение сигналов с выхода старшего разряда регистра 1 взода 24 через элементы 44, 34, 46 и 47 на единичный и нулевой входы триггера 30, При этом появление единицы на входе 24 вызывает переброс триггера 30 в состояние нуля, а появление первого нуля после предыдушей единицы вызывает переброс этого триггера в единицу. Первый импульс, соответствующий первому нулю, передается на выход 22 посредством элементов 44, 34, 47 и 38. Последующие импульсы передаются на выход 21 через элемент 37.Появление сигнала по входу 23, обнуление счетчика 4 вызывает переброс триг826353 20 25 ЗО Формула изобретения 40 50 55 гера 31 в нулевое состояние и блокировку подачи входных сигналов через элемент 34, а также выдачу .сигнала по выходу 20. В этот момент блок переходит в режим записи единиц в регистр 1. Далее на выход 22 вновь передается сигнал посредством элементов 36, 47 и 38. Этот сигнал инициируется входным сигналом по входу 25 от узла 8 сравнения. Разрешением подачи этого сигнала служит состояние 010 триггеров 31- 33 (или 001 для режима освобождения памяти). Затем вновь вырабатывается после довательность импульсов по выходу 21 до получения входного сигнала по входу 23. Эти импульсы передаются также на выход 19 посредством элемента 41, управляемого состоя нием три ггеров 31 - 33. Си гнал по5 входу 23 от счетчика 4 вызывает сброс триггера 32 в нуль, прекращение подачи импульсов по выходу 19 и возврат схемы в исходное состояние (все триггеры в нулевом состоянии). В режиме освобождения памяти триггеры 32 - 33 устанавливаются в состояние 001. Далее сигналом по входу 25 инициируется выдача импульса записи нулей в регистр 1 по выходу 19 через элемент 42. Сигнал по входу 23 также вызывает сброс схемы в исходное состояние.Сигнал по входу 27 через элемент 45 вызывает принудительную устанГвку всех триггеров в нуль и возврат схемы в исходное состояние. 1. Устройство для динамического распределения памяти, содержащее регистр запроса, счетчик областей, счет ик адреса,коммутатор, регистр адреса, узел сравнения, блок управления, первый и второй элементы И, элемент ИЛИ, триггер управления, причем выход счетчика адреса соединен с первым входом узла сравнения, выход коммутатора соединен с входом регистра адреса, выход узла сравнения соединен с первым входом блока управления, отличающееся тем, что, с целью упрощения устройства, оно содержит сдвиговый регистр,счетчик длины участка, причем выход регистра адреса соединен со вторым входом узла сравнения и с адресным выходом устройства, выход счетчика адреса соединен с первым входом коммутатора, второй вход коммутатора соединен с адресным входом устройства, третий вход коммутатора соединен с первым выходом блока управления, выход сдвигового регистра соединен со вторым входом блока управления и со сбросовым входом сдвигового регистра, второй выход блока управления соединен с первым входом первого элемента И, третий выход блока управления соединен с первым входом второго элемента И, четвертый выход блока управления соединен со счетным входом счетчика длины участка, запросный вход устройства соединен с входом регистра запросов, пятый выход блока управления соединен с управляющим входом счетчика длины участка, выход регистра запросов соединен с входом счетчика длины участка, третий вход блока управления соединен с управляющим входом устройства, выход счетчика областей соединен с четвертым входом блока управления и с выходом отсутствия пространства памяти устройства, выход счетчика длины участка соединен с пятым входом блока управления, с управляющим входом счетчика областей, с первым входом элемента ИЛИ и с нулевым входом триггера управления, выход узла сравнения соединен с единичным входом триггера управления выход триггера управления соединен со вторым входом элемента ИЛИ, выход элемента ИЛИ соединен со вторыми входами первого и второго элементов И, выход первого элемента И соединен с нулевым информационным входом сдвигового регистра, выход второго элемента И соединен с единичным информационным входом сдвигового регистра, вход синхроимпульсов устройства соединен со счетным входом счетчика областей, с управляющим входом сдвигового регистра, с входом счетчика адреса и с шестым входом блока управления, седьмой вход блока управления соединен с входом логического нуля устройства. 2, Устройство по п. 1, отличающееся тем, что блок управления содержит два элемента НЕ, девять элементов И, элемент И - НЕ, пять элементов ИЛИ, четыре триггера, причем вход первого элемента НЕ соединен со вторым входом блока, выход первого элемента НЕ соединен с первым входом первого элемента И, выход первого элемента И соединен с первым входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с единичным входом первого триггера и с первым входом второго элемента И, выход второго элемента И соединен с первым входом второго элемента ИЛИ, с первым входом третьего элемента И и с пятым выходом блока, выход третьего элемента И соединен с первым выходом блока, второй вход первого элемента И соединен с первым входом четвертого элемента И, с синхровходом первого триггера, с первым входом пятого элемента И, с первым входом шестого элемента И, с первым входом седьмого элемента И, с шестым входом блока, выход седьмого элемента И соединен со вторым выходом блока, выход шестого элемента И соединен с третьим выходом блока, единичный выход первого триггера соединен со вторым входом пятого элемента И, выход пятого элемента И соединен со вторым входом второго элемента ИЛИ и с четвертым выходом блока, нулевой выход первого триггера соединен со вторым. входом второго элемента И, вход второго элемента(Риг. НЕ соединен с четвертым входом блока, выход второго элемента НЕ соединен с первым управляющим входом второго триггера, с первым управляющим входом третьего триггера и с управляющим входом первого триггера, единичныи выход второго 5 триггера соединен с третьим входом первого элемента И, со вторым входом четвертого элемента И и со вторым входом третьего элемента И, нулевой выход второго триггера соединен с первым входом элемента И -1 О НЕ и с первым входом восьмого элемента И, информационный вход второго триггера соединен с нулевым выходом третьего триггера, вход синхронизации второго триггера соединен с входом синхронизации третьего триггера, с входом синхронизации четвертого 1 Б триггера и с пятым входом блока, второй управляющий вход второго, третьего триггеров и управляющий вход четвертого триггеров соединены с третьим входом блока, информационный вход третьего триггера соединен с выходом элемента И - НЕ, еди 20 ничный выход третьего триггера соединен со вторым входом восьмого элемента И с вторым входом элемента И - НЕ, информационныи вход четвертого триггера соединен с седьмым входом блока, выход четвертого триггера соединен со вторым входом седьмого элемента И и с первым входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым входом шестого элемента И и с третьим входом седьмого элемента И, выход восьмого элемента И соединен со вторым входом третьего элемента ИЛИ и с третьим входом шестого элемента И, выход третьего элемента ИЛИ соединен с первым входом девятого элемента И, выход девятого элемента И соединен со вторым входом первого элемента ИЛИ, второй вход девятого элемента И соединен с первым входом блока, первый вход четвертого элемента ИЛИ соединен с пятым входом блока, второй вход четвертого элемента ИЛИ соединен с выходом четвертого элемента И, выход четвертого элемента ИЛИ соединен с нулевым входом первого триггера.Источники информации,принятые во внимание при экспертизе 1. Патент США3643225, кл. 340 - 172.5 опублик. 1972.2. Патент США М 3596257, кл. 340 в 172, опублик.1971 (прототип) .Составитель нко Техред А. Бо Тираж 745 ИИПИ Государственного по делам изобретений 5, Москва, Ж - 35, Ра ППП Патент, г. УжгКорректор МПодписноекомитета СССРи открытийшская наб., д. 4/5род, ул. Проектная, 4