Устройство для распределения ресурсов внешней памяти вычислительного комплекса

 

Изобретение относится к вычислительной технике и может быть использовано & устройствах для распределения ресурсов в вычислительных комплексах. Целью изобретения является сокращение времени поиска свободной внешней памяти. Устройство содержит группу блоков анализа свободных участков внешней памяти, блок регистров , блок элементов сравнения, блок выбора минимального числа, группу элементов И, блок элементов ИЛИ, элемент задержки, регистр, группу формирователей импульсов, группу элементов ИЛИ-НЕ. Устройство аппаратно реализует алгоритм поиска наиболее подходящего по размерам для вычислительных ресурсов участка внешней памяти вычислительного комплекса. 2 ил. Q (О 1чЭ ф ts5

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

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

РЕСПУБЛИН (gg 4 G 06 F 13/00

; I: !

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

Н A BTGPCH0MY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3801744/24-24 (22) 16. 10. 84 (46) 07. 07.86. Бап. № 25 (72) В.В.Мазаник (53) 681.3(088.8) (56) Авторское свидетельство СССР № 881722, кл. G Oo F 3/04, 1981

Авторское свидетельство СССР № 1051527, кл. G 06 F 3/04, 1983. (54) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ВНЕШНЕЙ ПАМЯТИ ВЫЧИСЛИТЕЛЬНОГС

КОМПЛЕКСА (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах для распре„„Я0„„1242969 А I деления ресурсов в вычислительных комплексах. Целью изобретения является сокращение времени поиска свободной внешней памяти. Устройство содержит группу блоков анализа свободных участков внешней памяти, блок регистров, блок элементов сравнения, блок выбора минимального числа, группу элементов И, блок элементов ИЛИ, элемент задержки, регистр, группу формирователей импульсов, группу элементов

ИЛИ-НЕ. Устройство аппаратно реализует алгоритм поиска наиболее подходящего по размерам для вычислительных ресурсов участка внешней памяти вычислительного комплекса. 2 ил, 1242969

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

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

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

Устройство содержит (фиг. 1) группу блоков 1 анализа свободных участков внешней памяти, первый 2 и второй 3 блоки регистров, блок 4 элемен» тов сравнения, блок 5 выбора минимального числа, блок 6 элементов И, блок 7 элементов ИЛИ, блок 8 элементов ИЛИ, элемент 9 задержки, регистр

1О, блок 11 регистров, блок 12 элементов сравнения, блок 13 выбора минимального числа, группу 14 формирователей импульсов, группу 15 элеменгов ИЛИ-НЕ, группу 16 элементов И.

Блок выбора минимального числа

25 содержит (фиг. 2) блок 17 регистров, блок 18 поразрядных узлов анализа, „первую 19, вторую 20 и третью ?1 группы блоков элементов И, первый 22 и второй 23 блоки элементов ИЛИ, блок

24 триггеров, блок 25 элементов И-HE третий блок 26 элементов ИЛИ, блок

27 элементов И.

Кроме того, устройство имеет вход

28 задания размера требуемой памяти устройства (фиг. 1), вход 29 запуска устройства, группу входов 30 размера максимального свободного участка памяти устройства, группу входов 31 размера свободных участков памяти устройства, группу входов 32 начального адреса и номера блока памяти . устройства, информационный выход 33 устройства, выход 34 готовности устройства, группу 35 информационных входов блока выбора минимального числа (фиг. 2), группу 36 установочных входов блока выбора минимального числа, вход 37 запуска блока выбора минимального числа, вход 38 сброса блока выбора минимального числа, выход 39 блока выбора минимального числа.

Устройство обеспЕчивает аппаратную реализацию процедуры "Дай кусок" для .выделения необходимых участков свободной внешней памяти в вычислительном комплексе. Сущность процедуры заключается в следующем.

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

В исходном состоянии триггеры 24 блоков 5 и 13 выбора минимального числа находятся. в нулевом состоянии.

По входу 28 в регистр 10 поступает код требуемого размера дыры. Блок

11 регистров обеспечивает хранение информации грубой таблицы, и i-й (i — 1, ш) регистр 11 по i-му входу 30 заносится код размера максимальной дыры 1.-й точной таблицы. Блок 2 регистров -го блока 1 анализа свободных участков внешней памяти предназначен для хранения i-й точной таблицы,.по j-му (j = 1, m) входу 31 в

j-й регистр 2 i-го блока 1 заносится код размера 1-й дыры i-й точной таблицы. Блок 3 регистров i-го блока

1 служит для хранения кодов начальных адресов соответствующих дыр i-u точной таблицы и номеров внешних устройств, на которых они расположены, в j A регистр 3 блока 1 по j ìó входу 32 заносится соответствующий . код начального адреса и номера внешнего устройства.

При поступлении запроса на память

1-м элементом 12 сравнения проводится сравнение содержимого регистра 10 и

i-го регистра 11. Если код i-горегистра 11 превышает или равен содер- . жимому регистра 10, то на выходе

i-ro элемента 12 сравнения появляется импульс, который по i-му входу 36 устанавливает в единичное состояние i-й триггер 24 блока 13 выбора минимального числа.

Содержимое i-го регистра 11 заносится в i-й регистр 17. Из числа регистров 11 выбирают те, содержимое з 1242 которых удовлетворяет требуемому запросу на память (превышает или равно ему). Блоком 13 выбора минимального числа определяется номер i-го регистра 11, в котором хранится код разме5 ра наиболее подходящей дыры из грубой таблицы. Производится это следующим образом.

Импульс по входу 29 устройства и по входу 37 запускает блок 13 выбо10 ра минимального числа. Блоком 13 проводится поразрядный анализ сравниваемых чисел (записанных в регистрах

17). Если в первом разряде чисел имеется и "0" и "1" то через элементы

У

И 19 и 20 блока 18 узлов анализа на элементы ИЛИ 22 и 26 поступают единичные сигналы. На выходе соответствующего элемента И-НЕ 25 формируется нулевой сигнал, которым закры20 вается соответствующий элемент И 27.

Через элементы И 19 и 21, относящиеся к тем регистрам 17, в первом разряде которых "0", единичный сигнал поступает на входы установки в нулевое состояние соответствующих тригге. ров 24. Элементы И 19 и 20 соответствующих узлов 18 анализа закрываются и единичный сигнал будет только на выходе элемента ИЛИ 26. На выходе элемента И-НЕ 25 формируется единич30 ныи сигнал, по которому открывается элемент И 27. Далее проводится анализ следующего разряда оставшихся сравниваемых чисел.

Если в первом разряде сравниваемыхЗ5 чисел содержатся только нули или только единицы, то на выходе соответствующего элемента И-HE

25 присутствует единичный сигнал, который открывает элемент И 27. Следо- 40 вательно, в этом случае сразу проводится анализ второго или последующих разрядов. После того, как все разряды сравниваемых чисел проанализированы, на выходе элемента И 27 фор- 45 мируется единичный уровень. При этом на выходе 39 хранится унитарный код номера регистра 11, содержащего минимальное число, удовлетворяющее запросу. Таких чисел может быть несколь- 50 ко, тогда несколько триггеров 24 будут в единичном состоянии.

На выходе i-го формирователя 14 импульсов появится импульс если i-й триггер 24 в единичном состоянии.

Если несколько триггеров 24 в единичном состоянии, то из их числа выбирается триггер 24, соответствующий

969 4 регистру 11 с наименьшим номером

Проводится это с помощью элементов

ИЛИ-НЕ 15 и И 16. В результате описанного этапа работы устройства проведен выбор наиболее подходящей точной таблицы, которой соответствует блок 1.

С помощью i-го блока 4 элементов сравнения, проводят выбор дыр i-й точной таблицы, удовлетворяющих запросу на память, j-й элемент 4 сравнения вырабатывает импульс, если код j-го регистра 2 превышает или равен содержимому регистра 10. Блоком

5 выбора минимального числа проводят выбор дыры i-й точной таблицы, наиболее подходящей требуемому запросу на память. Проводится это при поступлении импульса запуска с выхода i-го элемента И 16 на вход запуска блока

5;. В результате íà j-м выходе блока

5 появляется сигнал, разрешающий прохождение кода начального адреса

j-й дыры i é точной таблицы и номера внешнего устройства, на котором она расположена, из j-го регистра 3 через j-й блок элементов И 6, i-й блок элементов ИЛИ 7, блок 8 элементов ИЛИ на выход 33 устройства. Одновременно с этим на выходе 34 устройства появляется импульс готовности, который свидетельствует об окончании работы устройства и обнуляет триггеры 24 блоков 5 и 13 выбора минимального числа.

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

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

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

25 ней памяти содержит первый и второй блоки регистров, блок элементов сравнения, блок выбора минимального числа, блок элементов И, блок элементов ИЛИ, выход задания размера требуемой памяти устройства подключен к входу регистра, вЫход которого соединен с вторым входом блока элементов сравнения и с первыми информационными входами всех блоков анализа свободных участков внешней памяти группы, j-й (j = 1, ш) вход размера свободных участков внешней памяти группы входов устройства и j-й вход начального адреса и номера блока памяФ ти группы входов устройства подключены соответственно к второму и третьему информационным входам i-ro блока анализа свободных участков внешней памяти группы, вход запуска устройства подключен к входу запуска блока выбора минимального числа и к входу элемента задержки, выход которого подключен к входу сброса блока выбора минимального. числа, выходу готовности устройства и к входам запуска всех блоков анализа свободных участков внешней памяти группы, выход блока элементов сравнения подключен к группе установочных входов блока выбора минимального числа, группа информационных входов которого подключена к выходу блока регистров, к входу которого подключена

35 группа входов размера максимального свободного участка внешней памяти устройства, i-й (i = 1, m) выход блока выбора минимального числа подключен к входу i-ro формирователя им40 пульсов группы, выход которого подключен к i-м входам с i-ro по (m—

1)-й элементов ИЛИ-НЕ группы, выход i-го (i = 2, m) формирователя импульсов группы соединен с первым входом i-го (i = 2, m) элемента И группы, выход i-го (i = 1, m — I) элемента ИЛИ-НE группы подключен к второму входу i ãî (i = 2, m) элемента И, выход которого соединен с входом сброса i-ro блока анализа свободных участков внешней памяти группы, выход первого формирователя импульсов группы подключен к входу сброса первого блока анализа свободных участков внешней памяти группы, выход i-го блока анализа .свободных участков внешней памяти группы подключен к i-му входу блока элементов

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

1242969

Составитель С.Бурухин

Техред И.Ходанич Корректор А.Зимокосов

Редактор Н.Гунько

Заказ 3707/49

Тираж 671 Подписное

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

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

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