Патент ссср 826353

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советскик

Социвлистическик

Республик ()826353 (61) Дополнительное к авт. свид-ву— (22) Заявлено 04.07.79 (21) 2808086/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл

G 06 F 9/36

Гввударетееиимк квмитет (53) УДК 681.325 (088.8) лв делам извбретеиий и вткрмтий

Опубликовано 30.04.81. Бюллетень № 16

Дата опубликования описания 30.04.81 (А. Л. Ганькин, Н. Н. Захаревич и А. Н. Степанов

Московский ордена Трудового Красного фнам нц "-. инженерно-физический инсан@ (72) Авторы изобретения (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ДИНАМИЧЕСКОГО РАСПРЕДЕЛЕНИЯ

ПАМЯТИ

Изобретение относится к вычислительной технике и может быть использовано в мультипрограммных ЭВМ с одноуровневой организацией памяти.

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

Недостатком такого устройства является большой объем оборудования.

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

ИЛИ.

Это устройство предусматривает деление пространства оперативной памяти на блоки, которые в свою очередь делятся на области одинаковой в пределах блока длины. Базовые адреса начала блоков, размеры облас5 тей и признаки их занятости хранятся в видеинформационных слов в местной памяти устройства — по одному слову на блок. При подаче запроса на область определенной длины ее размер записывается в регистр за— проса. Затем производится последователь1о ный просмотр информационных слов в местной памяти в поисках наиболее подходящей по размерам области. При нахождении блока, содержащего такие области, производится дальнейший просмотр информационного слова путем его сдвига на регистре числа с целью нахождения свободной области в этом блоке. При освобождении памяти производится поиск информационного слова соответствующего блоку, содержащему ненужную более память. Затем производится коррекция информационного слова (2) .

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

) );.<) )Ъ1 ) )., ."ац)))) сд5

" ) "«<).я -,роп)е<)ч:,е устрой ) « це.:ь до) г:,.<.:«тем, что в х .") <)о)<< т<3<. ). я ди<)ам .-:««Bol<) паснреде;и)<ия «а "я" <, ), «ржаш< е )< ги«гр запроса, счетчик Ми;«< -:, «че ) <).) а.)р< «а, коммутатор, реги«3 р адр«са, . з«. i сравнения, блок управления, пс рвый и второй элементы И, элемент ИЛИ, триггер управления, причем выход счетчика адреса соединен с первым входом узла сравнения, выход коммутатора со«динен с входом регистра адреса, выход узла сравнения соединен с первым входом блока управления, введены сдвиговый регистр, счетчик длины участка, причем выход j)<. п<стрB) адреса соединен со вторым Входом 1зла < р;<вне«ия и с адресным г+ходом устроиства, выход счетчика адреса соединен с первым входом коммутатора, второй вход коммутатора соединен с адресным входом устройства, третий вход коммутатора соединен с первым выходом блока управления, выход сдвигового регистра соединен со вторым входом блока управления и со сбросовым входом сдвигового регистра, второй выход блока управления соединен с первым входом первого элемента И, третий выход блока управления соединен с первым входом второго элемента И, четвертый выход блока управления соединен со счетным входом счетчика длины участка, запросный вход устройства соединен со входом регистра запросов, пятый выход блока управления соединен с управляющим входом счетчика длины участка, выход регистра запросов соединен со входом счетчика длины участка, третий вход блока управления соедин ll с управляющим входом устройства, выход счетчика областей соедннен с четвертым входом блока управления и с выходом отсутствия пространства <памяти устройств<<, выход сч< Г)п<еа 1л«п)ь< у ц3«т< << соединен с няпгым входом блока упр;<вл«ния. с управляющим входом счетчика обласг«й, с первым входом элемента ИЛИ и с i«левым входом триггера управления, выход узла сравнения со«пи<ни с единичным входом триггера управления, выход три i«pB управления соединен со вт<)рым входом эл«мента ИЛИ, выход элемента ИЛИ соединен «< вторыми входами первого и второго элементов И, выход первого элемента И соединен с нулевым информационным входом сдвигового регистра, выход второго элемента И соединен с единичным информационным вхо дом сдвигового регистра, вход синхроимпуль сов устройства соединен со счетным входом счетчика областей> с ynpaBëÿþùèì входом сдвигового регистра, с входом счетчика и с шестым входом блока управления, седьмой вход блока управления соединен с входом логического нуля устройсхва.

Кроме того, блок управления содержит два элемента НЕ, девять элементов И, эле4 .lei т И--HE, пять элементов ИЛИ, четыре триггера, причем вход первого элемента HE соединен со вторым входом блока, выход первого элемента HE соединен с первым входом первого элемента И, выход первого элемента И соединен с первым входом первого элемента ИЛИ. выход п«рвого элемента ИЛИ соединен с единичным входом первого триггера и с первым входом второго элемента И, выход второго элемента И соединен с первым входом второго элемента ИЛИ, с первым входом третьего элемента И и с пятым выходом блока, выход третьего элемента И соединен с первым выходом блока, второй вход первого элемента И соединен с первым входом четвертого элемента И, с синхровходом первого триггера, с первым входом пятого элемента И, с первым входом шестого элемента И, с первым входом седьмого элемента И, с шестым входом блока, выход седьмого элемента И соединен со вторым выходом блока, выход шестого элемента И соединен с третьим выходом блока, единичный выход первого триггера соединен со вторым входом пятого элемента И, выход пятого элемента И соединен со вторым входом второго элемента ИЛИ и с четвертым выходом блока, нулевой выход первого триггера соединен со вторым входом второго элемента И, вход второго элемента НЕ соединен с четвертым входом блока, выход второго элемента HE соединен с первым управляющим входом втоЗО рого триггера, с первым управляющим входом третьего триггера и с управляющим входом первого триггера, единичный выход второго триггера соединен с третьим входом первого элемента И, со вторым входом

35 ч тв< ргого элемента И и со вторым входом г!)«) ье) о элемента И, нулевой выход второго трипера соединен с первым входом элемента И вЂ” НЕ и с первым входом восьмого элемента И, информационный вход второго григгс ра соединен с нулевым выходом треть4О еп) триггера, вход синхронизации второго триггера соединен с входом синхронизации третьего триггера, с входом синхронизации четвертого триггера и с пятым входом блока, второй управляющий вход второго, третьего триггеров и управляющий вход четвертого триггеров соединены с третьим входом блока, информационный вход третьего триггера соединен с выходом элемента И вЂ” НЕ, единичный выход третьего триггера соединен со вторым входом восьмого элемента И и со вторым входом элемента И вЂ” HE, информационный вход четвертого триггера соединен с седьмым входом блока, выход четвертого триггера соединен со вторым входом седьмого элемента И и с первым входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым входом шестого элемента И и с третьим входом седьмого элемента И, выход восьмого элемента И соединен со вторым входом третьего элемента ИЛИ и с .третьим вхо826353 дом шестого элемента И, выход третьего элемента ИЛИ соединен с первым входом девятого элемента И, выход девятого элемента И соединен со вторым входом первоlo элемента ИЛИ, второй вход девятого элсмепта И соединен с первым входом блока, первый вход четвертого элемента ИЛИ соединен с пятым входом блока, второй вход четвертого элемента ИЛИ соединен с выходом четвертого элемента И, выход четвертого элемента И, выход четвертого элемента

ИЛИ соединен с нулевым входом первого

1О триггера.

На фиг. 1 приведена блок-схема устройства; на фиг. 2 — структурная схема блока управления.

Устройство содержит сдвиговый регистр >s

1, счетчик 2 адреса, регистр 3 запроса, счетчик 4 длины участка, регистра 5 адреса, коммутатор 6,счетчик 7 областей, узел 8 сравнения, триггер 9 управления,.элементы

И 10 и ll, элемент ИЛИ 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.

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

Распределяемая между программами память делится на области фиксированной длины. Программе может быть выделен участок памяти равный одной или нескольким последовательным областям. Каждой об- 4п ласти поставлен в соответствие один разряд регистра I. Занятой области соответствует состояние разряда «1», а свободной — «О».

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

1, замкнутого в кольцо; синхронно со сдви- 4 гом регистра меняется содержимое счетчика 2, указывающее номер области, соответствующей разряду регистра 1. Режим работы устройства. («Выделение», «Освобождение») определяется кодом, подаваемым на вход 26. В режиме выделения памяти на вход 14 подается код запроса — уменьшенная на единицу длина требуемого участка в областях, который заносится в регистр

3 запроса. Код запроса заносится затем в счетчик 4 длины участка. Далее производится поиск свободного участка памяти, заключающийся в отыскивании в регистре 1 последовательности из нужного количества нулей. При появлении любого нуля после любой единицы в старшем разряде регистра 1 адрес этой области заносится в регистр

5 через коммутатор 6.

Появление последующих нулей в старшем разряде вызывает вычитание единицы из счетчика 4 до тех пор, пока не произойдет его обнуление. Если последовательность нулей имеет недостаточную длину; то при появлении следующей посл ;10Bd TEë ьности нулей происходит повторное занесение кода запроса из регистра 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 через элемент 11. Количество нулей определяется содержимым счетчика 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

ЗО

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

4О

55 гера 31 в нулевое состояние и блокировку подачи входных сигналов через элемент 34, а также выдачу сигнала по выходу 20. В этот момент блок переходит в режим записи единиц в регистр l. Далее на выход 22 вновь передается сигнал посредством элементов 36, 47 и 38. Этот сигнал инициируется входным сигналом по входу 25 от узла

8 сравнения. Разрешением подачи этого сигнала служит состояние 010 триггеров 3133 (или 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, отличающееся тем, что блок управления содержит два элемента НЕ, девять элементов И, элемент И—

HF„пять элементов ИЛИ, четыре триггера, причем вход первого элемента НЕ соединен со вторым входом блока, выход первого элемента НЕ соединен с первым входом первого элемента И, выход первого элемента И соединен с первым входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с единичным входом первого триггера и с первым входом второго элемента И, выход второго элемента И соединен с первым входом второго элемента ИЛИ, с первым входом третьего элемента И и с пятым выходом блока, выход третьего элемента И соединен с первым выходом блока, второй вход первого элемента И соединен с первым входом четвертого элемента И, с синхровходом первого триггера, с первым входом пятого элемента И, с первым входом шестого элемента И, с первым входом седьмого элемента И, с шестым входом блока, выход седьмого элемента И соединен со вторым выходом блока, выход шестого элемента И соединен с третьим выходом блока, единичный выход первого триггера соединен со вторым входом пятого элемента И, выход пятого элемента И соединен со вторым входом второго элемента ИЛИ и с четвертым выходом блока, нулевой выход первого триггера соединен со вторым. входом второго элемента И, вход второго элемента

826353

10 (Риг.!

НЕ соединен с четвертым входом блока, выход второго элемента HE соединен с первым управляющим входом второго триггера, с первым управляющим входом третьего триггера и с управляющим входом первого триггера, единичныи выход второго триггера соединен с третьим входом первого элемента И, со вторым входом четвертого элемента И и со вторым входом третьего элемента И, нулевой выход второго триггера соединен с первым входом элемента И—

1О

НЕ и с первым входом восьмого элемента И, информационный вход второго триггера соединен с нулевым выходом третьего триггера, вход синхронизации второго триггера соединен с входом синхронизации третьего триггера, с входом синхронизации четвертого триггера и с пятым входом блока, второй управляющий вход второго, третьего триггеров и управляющий вход четвертого триггеров соединены с третьим входом блока, информационный вход третьего триггера соединен с выходом элемента И вЂ” НЕ, еди20 ничный выход третьего триггера соединен со вторым входом восьмого элемента И с вторым входом элемента И вЂ” НЕ, информационныи вход четвертого триггера соединен с седьмым входом блока, выход четвертого триггера соединен со вторым входом седьмого элемента И и с первым входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым входом шестого элемента И и с третьим входом седьмого элемента И, выход восьмого элемента И соединен со вторым входом третьего элемента ИЛИ и с третьим входом шестого элемента И, выход третьего элемента

ИЛИ соединен с первым входом девятого элемента И, выход девятого элемента И соединен со вторым входом первого элемента ИЛИ, второй вход девятого элемента И соединен с первым входом блока, первый вход четвертого элемента ИЛ И соеди нен с пятым входом блока, второй вход четвертого элемента ИЛИ соединен с выходом четвертого элемента И, выход четвертого элемента ИЛИ соединен с нулевым входом первого триггера.

Источники информации, принятые во внимание при экспертизе

1. Патент США № 3643225, кл. 340 — 172.5 опублик. 1972.

2. Патент США ¹ 3596257,,кл. 340 в 172, опублик.1971 (прототип) .

826353

22

Составитель К. Кудряшев

Редактор С. Шевченко Техред А. Бойкас Корректор М. Демчик

Заказ 2501/71 Тираж 745 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж вЂ” 35, . Раушская наб., д. 4/5

Филиал ППП «Патент», r. Ужгород, ул. Проектная, 4