Устройство для распределения ресурсов внешней памяти вычислительного комплекса Советский патент 1986 года по МПК G06F13/00 

I

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

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

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

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

Блок выбора минимального числа содержит (фиг. 2) блок 17 регистров, блок 18 поразрядных узлов анализа, /1ервую 19, вторую 20 и третью 21 группы блоков элементов И, первый 22 и второй 23 блоки элементов ИЛИ, блок 24 триггер ов, блок 25 элементов И-НЕ, третий блок 26 элементов ИЛИ, блок

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

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

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

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

10

ts

20

12429692

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

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

По входу 28 в регистр 10 поступа- 2J ет код требуемого размера дыры. Блок 11 регистров обеспечивает хранение информации грубой таблицы, в i-й (i 1, m) регистр 11 по входу 30 заносится код размера максимальной дыры 1-й точной, таблицы. Блок 2 регистров 1-го блока 1 анализа свободных участков внешней памяти предназначен для хранения i-й точной таблицы,, по j-му (J 1, т) входу 31 в j-й регистр 2 i-ro блока 1 заносится код размера j-й дыры точной таблицы. Блок 3 регистррв i-ro блока 1 слуясит для хранения кодов начальных адресов соответствующих дыр i-й точной таблицы и номеров внешних устройств, на которых они расположены, в j-й регистр 3 блока 1 по j-му входу 32 заносится соответствующей . код начального адреса и номера внешнего уСТ1 ОЙСТВс.

При поступлении запроса на память i-M элементом 12 сравнения проводится сравнение содержимого регистра 10 и i-ro регистра 11. Если код i-ro регистра 11 превышает или равен содер- . жимому регистра 10, то на выходе i-ro элемента 12 сравнения появляется импульс, который по i-му входу 36 устанавливает в единичное состояние 1-й триггер 24 блока 13 выбора минимального числа,

Содерясимое i-ro регистра 11 заносится в i-й регистр 17. Из числа регистров 11 выбирают те, содержимое

30

35

40

45

50

55

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

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

Если в первом разряде сравниваемых35 ройство вьщает начальный адрес наибочисел содержатс51 только нули или только единицы, то на выходе .соответствующего элемента И-НЕ 25 присутствует единичный сигнал, ко- торьш открывает элемент И 27. Следо- ват ельно, в этом случае сразу проводится анализ второго или последующих разрядов. После того, как все разряды сравниваемых чисел проанализиро

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

На выходе i-ro формирователя 14 импульсов появится импульс если i-й триггер 24 в единичном состоянии. Если несколько триггеров 24 в единичном состоянии, то из их числа выбирается триггер 24, соответствующий

0

5

0

5

регистру 11 с наименьшим номером i. Проводится это с помощью элементов ИЛИ-НЕ 15 и И 16, В результате описанного этапа работы устройства проведен выбор наиболее подходящей точногЧ таблицы, которой соответствует блок 1. С помощью i-ro блока 4 элементов сравнения, проводят выбор дыр i-й точной таблицы, удовлетворяющих запросу на память, j-й элемент 4 сравнения вьфабатыйает импульс, если код j-ro регистра 2 превьшает или ра- .вен содержимому регистра 10, Блоком 5 выбдра минимального числа проводят выбор дьфы i-и точной таблицы, наи- . более подходящей требуемому запросу на память. Проводится это при поступлении импульса запуска с выхода i-ro элемента И 16 на вход запуска блока 5;, В результате на j-м выходе блока 5 появляется сигнал, разрешающий прохождение кода начального адреса j-й дыры i-й точной таблицы и номера внешнего устройства, на котором она расположена, из j-ro регистра 3 через j-й блок элементов И 6, i-й блок элементов ИЛИ 7, блок 8 элементов ИЛИ на выход 33 устройства. Одновременно с этим на выходе 34 устройства появляется импульс готовности, который свидетельствует об окончании работы устройства и обнуляет триггеры 24 блоков 5 и 13 выбора минимального числа.

Таким образом, предлагаемое уст

50

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

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

Устройство для распределения ресурсов внешней памяти вычислительного комплекса, содержащее блок регистров, блок элементов сравнения, блок элементов ИЛИ и регистр, причем выход блока регистров подключен к первому входу блока элементов сравнения, отличающееся тем, что, с целью сокращения времени поиска свободного участка внешней памяти, в него введены группа блоков анализа свободных участков внешней памяти, блок выбора минимального числа, эле- 55 мент задержки, группа формирователей импульсов, группа элементов ШШ-НЕ, группа элементов И, причем каждый блок анализа свободных участков внешней памяти содержит первый и второй блоки регистров, блок элементов сравнения, блок выбора минимального числа, блок элементов И, блок элемен тов ИЛИ выход задания размера требуемой памяти устройства подключен к входу регистра, вЬкод которого соединен с вторыИ входом блока элементо сравнения и с первыми информационны- ми входами всех блоков анализа свободных участков внешней памяти группы, j-й (J 1, т) вход размера свободных участков внешней памяти группы входов устройства и j-й вход на- чального адреса и номера блока памяти группы входов устройства подключены соответственно к второму и третьему информационным входам 1-го блока анализа свободных участков внешней памяти группы, вход запуска устройства подключен к входу запуска блока выбора минимального числа и к входу элемента задержки, выход которого подключен к входу сброса блока выбора минимального числа, выходу готовности устройства и к входам запуска всех блоков анализа свободных участков внешней памяти группы, выход блока элементов сравнения под- ключен к группе установочных входов блока выбора минимального числа, группа информационных входов которого подключена к выходу блока регистров к входу которого подключена группа входов размера максимального свободного участка внешней памяти устройства, i-й (i 1, m) выход блока выбора минимального числа под- ключен к входу i-ro формирователя им пульсов группы, выход которого подключен к i-M входам с i-ro по (m - - 1)-й элементов ИЛИ-НЕ группы, выход i-ro (i 2, m) формирователя импульсов группы соединен с первым входом i-ro (i 2, m) элемента И группы, выход i-ro (i 1, m - i) элемента ИЛИ-НЕ группы подключен к второму входу i-ro (i 2, m) элемента И, выход которого соединен с входом сброса i-ro блока анализа свободных участков внешней памяти груп- пы выход первого формирователя импульсов группы подключен к входу сброса первого блока анализа свободных участков внешней памяти группы, выход i-To блока анализа свободных участков внешней памяти группы подключен к i-му входу блока элементов ИЛИ, ВЬКОД которого подключен к информационному выходу устройства,при- чем в-каждом блоке анализа свободных участков внешней памяти группы первый, второй, третий информационные входы, вход запуска и вход сброса подключены соответственно к первому входу блока элементов сравнения, к входам первого и второго блоков регистров и к входам запуска и сброса блока выбора минимального числа, выход .блока элементов ИЛИ подключен к выходу блока анализа свободных участков внешней памяти группы, выход первого блока регистров подключен к второму входу блока элементов сравнения и к группе информационных входов блока выбора минимального числа, група установочных входов и выход которого подключены соответственно к выходу блока элементов сравнения и к первому входу блока элементов И, второй вход и выход которого подключены соответственно к выходу второго блока регистров и к входам блока элементов ИЛИ.. .

28

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

Ofn26p

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

фиг. 2

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

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

3707/49

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

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

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

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