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

 

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

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

РЕСПУБЛИК (я)л 6 06 F 11/00

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛ6СТВУ (21) 4769191/24 (22) 09.11.89 (46) 30.12.91. Бюл. М 48 (72) А.В.Бек, М,А.Чернышов, Г.Н.Тимонькин. С.Н.Ткаченко, В.С.Харченко, В.В.Герасименко и С.В.Хотименко (53) 681.3(088.8) (56) Авторское свидетельство СССР

М 1015385, кл. G 06 F 11/00, G 06 F 9/00, 1983.

Авторское свидетельство СССР

М t 297051, кл. G 06 F 11/00, 1987. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

„„Я2„„1702372 А1 (57) Изобретение относится к вычислительной технике и может найти применение в высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения— повышение оперативности контроля, Устройство содержит и регистров 1.1-1,п запросов, и регистров распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, и триггеров 5.1-5.п тупика, и тригеров 6 1-6 и управления, (nxm) блоков сравнения 7.1-7.п.m, первую группу элементов И

8.1-8.п, первую группу элементов ИЛИ 9.19 и, вторую группу элементов И 10.1-10,п, третью группу элементов И 11.1-11,п, чет1702372

10 вертую и пятую группы элементов И, генератор тактовых импульсов, вторую группу элементов ИЛ И, группу коммутаторов 16.1—

16лп, m блоков элементов И, m сумматоров, коммутатор 19, первый и второй элементы

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

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

Устройство для контроля распределения ресурсов содержит п регистров 1,1 — 1,n запросов, и регистров 2.1-2.п распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, и триггеров 5.1 — 5.п тупика, и триггеров 6.1-6.п управления, i(nxm) блоков 7.1.1 — 7.п.гп сравнения первую группу элементов И 8.1 — 8.m, первую группу элементов ИЛИ 9.1 — 9.п, вторую группу эле. ментов И 10.1-10 и, третью группу элементов И 11.1 — 11.п, четвертую группу элементов И 12,1-12.(n-1), пятую группу элементов И 13.1-13.п, генератор 14 тактовых импульсов, вторую группу элементов ИЛИ

15.1-15.п, группу коммутаторов 16,1 — 16.m, m блоков элементов И 17.1-17лп, m сумматоров 18 1-18лп, коммутатор 19, второй элемент И 20, третий и первый элементы ИЛИ

21, 22, первый элемент И 23, второй и четвертый элементы ИЛИ 24, 25, вход 26 пуска устройства, вход 27.1(} = 1,n) группы входов запросов устройства, вход 28 свободных ресурсов устройства, вход 29.1i группы входов распределения ресурсов устройства, выход

3ОЛ j группы выходов ресурсов в тупике устройства, выход 313 группы выходов процессов в тупике устройства, одновибратор

32.

Регистры 1.1-1.п запросов служат для приема и хранения матрицы запросов от процессов на ресурсы системы, Регистры 2.1-2.п распределения ресурсов предназначены для приема и хране-. ния матрицы распределения ресурсов процессам.

45 ментами в устройстве являются (n-5) триггеров 6.6-6.п управления, п-1 триггеров 5.25,птупика,,триггера 4 режима,,(nxm-2) блоков сравнения 7.2.2-7.n m, (5n - 20) элементов И, (2n - 4) элементов ИЛИ, m коммутаторов, mсумматоров,,одновибратор 32. 2 ил.

Регистр 3 свободных ресурсов выполняет функции приема и хранения вектора свободных ресурсов и результата сложения строки матрицы распределения ресурсов процессам с вектором свободных ресурсов, Триггер 4 режима выполняет перевод устройства из режима ожидания в режим работы и обратно.

Триггеры 5.1 — 5.п тупика служат для индикации процессов, вовлеченных в тупиковую ситуацию.

Триггеры 6,1 — б.п управления необходимы для организации операции сложения, моделирующей освобождение ресурсов. (nxm) блоков 7.1.1-7.n.m сравнения (выполняют поэлементное сравнение строк матрицы запросов процессов с элементами вектора свободных ресурсов.

Первая группа элементов И 8.1-8.п фиксирует тот факт, что все элементы строки матрицы запросов процессов меньше или равны элементам вектора свободных ресурсов.

Первая группа элементов ИЛИ 9.1 — 9,п осуществляет выбор обнуляющих сигналов для триггеров 6.1-6.п управления с двух входов, Вторая группа элементов И 10,1-10.п выполняет формирование сигналов, необходимых для выполнения операции суммирования, Третья группа элементов И 11.1-11.п формирует сигналы обнуления триггеров

6.1-6,п управления в том случае, если соответствующий процесс не владеет ни одной единицей ресурсов.

Четвертая группа элементов И 12.1—

12.(п-1) служит для разрешения или запрещения прохождения тактовых импульсов в зависимости от сигналов, выставленных на выходах элементов И 10.1 — 10.п, Пятая группа элементов И 13.1-13.п предназначена для регулирования сигналов, необходимых для выполнения операции сложения.

1702372

Генератор 14 тактовых импульсов слу-, входов 28 через коммутатор 19 и устанавлижит для формирования последовательности ваются в единичное состояние все триггеры тактовых импульсов. 5.1 — 5.п тупика, а по заднему фронту устаВторая группа элементов ИЛИ 15.1 — навливается вединичноесостояниетриггер

15 и предназначена для фиксации отсутст- 5 4 режима. Длительность сигнала пуска тавия распределения ресурсов кова, что позволяет закончиться переходсоответствующим процессом. ным процессам в схеме по цепи: регистры

Группа коммутаторов 16.1 — 16.m. выпал- 1.1 — 1.п запросов и регистр 3 свободных реняет функцию коммутации !-й группы выхо- сурсов, блоки 7.1 — 7.п,m сравнения, элемендов регистров 2.1-2.п распределения 10 тов И8.1 — 8.п триггеры 6.1 — 6.п управления и ресурсов к первым входам сумматоров элементы И 10.1 — 10.п, 18.1-18.m. Регистры 1.1 — 1 и запросов и регистры

Блоки 17.1 — 17.m элементов И предназ- 2.1— - 2.п распределения ресурсов закрепленачены для подключения выходов регистра ны за процессами, то есть в регистр зап оЗсвободныхресурсовквторым входам сум- 15 сов 1. i(I =1, й, где и — число одновременно маторов 18 1-18ю. функционирующих процессов) заносится

Сумматоры 18.1 — 18.m выполняют one- информация о запросах i-го процесса оцесса, а в регистр 2 распределения ресурсов — инКоммутатор 19 коммутирует по входу формация о ресурсах, распределенных эторегистра 3 свободных ресурсов выходы сум- 20 му процессу. маторов 18 1 — 18.m и третью группу инфор- Выходы каждого регистра 1.I, 2.! и 3 мационных входов. разделены на группы выходов (полей) по

Элемент И 20 служит для формирования числу типов ресурсов, которыми располагасигнала, по которому инициируется работа ет контролируемая система. В !-м поле устройства. 25 О=1,m) каждого регистра запросов 1. i и расЭлемент ИЛИ 21 вырабатывает сигна- пределения ресурсов 2.! содержатся коды, лы, по которым осуществляется занесение отражающиечисло ресурсов !-го типа запрасов, информации в регистр 3 свободных ресур- шиваемых и распределенных !-му проце процессу соответственно. В J-м поле регистра 3 своЭлемент ИЛИ 22 служит для формиро- 30 бодных ресурсов содержится код, равный вания сигнала запуска генератора 14 такто- числу свободных ресурсов J-го типа в систевых импульсов. ме на момент контроля.

Элемент ИЛИ 24 управляет подключе- Информация о запросах на ресурсы синием выходов регистра 3 свободных ресур- стемы с выходов регистров 1.1 — 1,п запросов к вторым входам сумматоров 18,1-18.m 35 сов поступает на первые входы блоков через блоки 17.1 — 17.m элементов И, 7.1 — 7.п.m сравнения, на вторые входы котоЭлемент ИЛИ 25 формирует сигнал, по рых с выходов регистра 3 свободных ресуркоторому заносится информация в регистр сов поступает информация о числе

3 свободных ресурсов с выходов суммато- свободных ресурсов в системе. Единичный ров 8.1-18.гп. 40 сигнал блока 7.!.! сравнения (!=1, и; j =1,т)

Одновибратор 32 формирует сигнал за- вырабатывается в том случае, когда код, пописи информации в триггеры 5,1-5.п; 6.1 — ступающий на первый вход, меньше или раУ вен коду, поступающему на второй вход. стройство работает следующим абра- Физически это значит, что i-м процессом зом. 45 запрашивается ресурсов j-го типа не больВ исходном состоянии триггер 4 режи- ше, чем есть свободных ресурсов J-ro типа в ма и триггеры 6.1 — 6.п управления находятся системе. в нулевом состоянии. Когда на выходах всех блоков сравнео сигналу пуска, поступающему на ния i-й группы (!=1,n) установятся единичвход 6пускаустройства,навыходеэлемен- 50 ные сигналы, на выходе элемента И 8,i та 20формируетсяимпульс,попереднему формируется единичный сигнал с выхода фронту которого заносится информация об одновибратора 32, устанавливающий в нуимеющихся запросах на ресурсы системы в левое состояние триггер 5 тупика и в едирегистры1.1 — 1,пзапросовс первой группы ничное состояние — триггер 6.1,l информационных входов 27,1-27.п, о рас- 55 управления. Это значит, что i-й- и процесс в пределенных ресурсах — в регистры 2.1 — 2.п тупиковую ситуацию при текущем распре291-29.п о в с третьей группы информационных входов делении не вовлечен. Вс е ресурсы, которы.п, о свободных на текущий момент ми он владеет, будут возвращены в систему. е времени ресурсах — в регистр 3 свободных Единичный сигнал с выхода триггера 6.! р сурсов с второй группы информационных равления поступает на вторые входы I-x уп1702372 элементов И первой 10.l и второй 11.l групп элементов И.

В случае, если в регистре 2.1. l распределения ресурсов содержится нулевая информация, !-му процессу не распределен ни один из m типов ресурсов, на выходе элемента ИЛИ 15.I второй группы элементов !

ИЛИ формируется нулевой потенциал, кото рый поступает на первый вход элемента И 10 первой группы элементов И и запреща ет прохождение через него единичного потенциала с выхода триггера 6.i управления, а также поступает на первый инверсный вход элемента И 11.l второй группы элементов И, на третий инверсный вход которого поступает нулевой потенциал с выхода элемента ИЛИ 9.! первой группы элементов

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

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

11,l формируется единичный импульс, поступающий через элемент ИЛИ 9.! на вход установки в "О" триггера 6,! управления, и по заднему фронту обнуляет его, В том случае, когда в регистре 2.i распределения ресурсов записана ненулевая информация, то есть i-му процессу распределен хотя бы один ресурс любого типа, на выходе элемента ИЛИ 15,l второй группы элементов ИЛИ формируется единичный потенциал, который поступает на первый вход элемента и 10,! первой группы элементов И, и на его выходе формируется единичный сигнал, поступающий на второй инверсный вход элемента И 12 третьей группы, на второй вход элемента И 13,! четвертой группы, íà l é инверсный вход второго элемента И 23 и íà i-й вход элемента ИЛИ

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

12.1 и 13.1 третьей и четвертой групп. Длительность тактового импульса такова, что позволяет осуществить формирование суммы на выходах сумматоров 18.1 — 18.гп, занесение ее в регистр 3 свободных ресурсов, сравнение в блоках 7,1.1-7.n.m сравнения и формирование соответствующих сигналов на выходах элементов И 10.1-10,п. Пауза между тактовыми импульсами равна сумме длительности тактового импульса и времени распространения его по цепи элементов

И 12,1 — 12,(n-1) и 13.п. В случае, если на выходе элемента И 10.i выставлен единичный потенциал (i-й процесс в тупиковую ситуа5 цию не вовлечен), который поступает на второй инверсный вход элемента И 12,i и запрещает прохождение через него тактовых импульсов, потенциал с выхода элемента И 10.! поступает на второй вход элемента

10 И 13.l, разрешая прохождение через него тактовых импульсов.

Тактовый импульс с выхода генератора

14 через цепь элементов И 12.1 — 12 (l-1) и

13,i поступает на — е управляющие входы

15 коммутаторов 16.1-16,m, разрешая тем самым прохождение информации с выходов регистра 2,l распределения ресурсов на первые входы сумматоров 18,1 — 18,m (m— число типов ресурсов в системе), а также

20 поступает на !-й вход элемента ИЛИ 24, на выходе которого формируется единичный сигнал, поступающий на управляющие входы группы блоков элементов И 17.1 — 17.m u разрешающий прохождение информации с

25 выходов регистра 3 свободных ресурсов на вторые входы сумматоров 18.1-18.m, на выходах которых формируется сумма свободных и распределенных i-му процессу ресурсов, то есть моделируется освобожде30 ние ресурсов i-м процессом.

Кроме того, единичный импульс с выхо. да элемента И 13,! поступает через элемент

ИЛИ 9.! на вход триггера 6.! управления и по заднему фронту обнуляет его. Информа35 ция с выходов сумматоров 18.1 — 18лп поступает на входы четвертого элемента ИЛИ 25, на выходе которого формируется единичный потенциал, поступающий на второй вход элемента ИЛИ 21, на выходе которого

40 формируется единичный потенциал, по которому происходит занесение в регистр 3 свободных ресурсов информации, сформированной на выходах сумматоров 18.1-18.m и поступающей на информационные входы

45 регистра 3 свободных ресурсов через коммутатор 19, В случае, если на выходе элемента И 10 выставлен нулевой потенциал (i-й процесс на данном этапе анализа не может получить запрашиваемые ресурсы), 50 который поступает на второй инверсный вход элемента И 12.! и разрешает прохождение через него тактовых импульсов, а также нулевой потенциал с выхода элемента И

10.! поступает на второй вход элемента И

55 13.i, запрещая прохождение через него тактовых импульсов, Тактовый импульс с выхода генератора 14 через цепь элементов И

12.1-12.! поступает на входы элементов И

12. {!+1) и 13 {!+1) и, если на выходе элемента

И 10, (i+1) выставлен единичный потенциал, 1702372

10

25

45 том, что в данный момент устройство занято 50

55 происходит цикл обработки информации, аналогичный описанному выше для i-го процесса, а если на выходе элемента И 10. (!+1) выставлен нулевой потенциал, тактовый импульс поступает через элемент И 12. (!+1) на входы элементов И 12.(!+2) и 13. (+2) и т.д.

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

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

Когда произойдет обнуление всех триггеров 6,1 — 6.п управления в результате циклов обработки информации, описанных выше, на выходах элементов И 10.1 — 10.п сформируются нулевые потенциалы, которые поступают на инверсные входы элемента И 23, и на его выходе формируется единичный сигнал, обнуляющий триггер 4 режима. На этом анализ состояния системы устройством завершается.

На второй группе информационных выходов 31.1-31 и выставляются индикаторы процесов, вовлеченных в тупик: номер разряда, на котором выставлен единичный потенциал, соответствует процессу, вовлеченному в тупиковую ситацию, На первой группе информационных выходов 30.Ц выставляется информация, по каким типам ресурсов процесс вовлечен в тупик: номер разряда в j-й группе О=1,m), на котором выставлен нулевой потенциал, соответствует номеру типа ресурсов, по которому i-й (!=in) процесс вовлечен в тупик, Нулевой потенциал на сигнальном выходе 32 устройства свидетельствует о том, что анализ состояния системы завершен, единичный потенциал свидетельствует о и осуществляет анализ состояния системы.

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

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

40 элементов ИЛИ, коммутатор, причем S-входы с первого по пятый триггеров управления соединены с выходами соответственно с первого по пятый элементов И, выход первого триггера тупика является первым выходом группы выходов процессов в тупике устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения оперативности контроля, в устройство дополнительно введены и-5 триггеров управления, п-1 триггеров тупика, пхв-2 блоков сравнения, 5n — 23 элементов

И, (2n — 4 ;элементов ИЛИ, m коммутаторов, m сумматоров, одновибратор, причем !-й вход (l--1,п), где n — число одновременно функционирующих процессов) группы входов запросов устройства соединен с информационным входом I-ro регистра запроса, !

-й выход (j =1,m, где m — число типов разделяемых процессами ресурсов системы) которого соединен с первым входом блока Ц сравнения, выход которого соединен с Цвыходом группы выходов ресурсов в тупике устройства и с (j+1)-M входом !-го элемента

И первой группы, выход которого соединен с входом установки в нуль !-ro триггера тупика, а выходы с шестого по и-й элементов

И первой группы .соединены с S-входами соответственно с шестого по и-й триггеров управления, прямой выход I-ro триггера тупика соединен i-м выходом группы выходов процессов в тупике устройства и с первым входом i-ro элемента И первой группы, прямой выход !-го триггера управления соединен с первыми прямыми входами !-х элементов И второй и третьей групп, выход

l-го элемента И второй группы соединен с инверсными входом i-го элемента И четвертой группы, с первым входом l-го элемента

И пятой группы, с i-M входом первого элемента ИЛИ и с i-м инверсным входом первого элемента И, выход I-го элемента И третьей группы соединен с первым входом

i-го элемента ИЛИ первой группы, выход которого соединен с входом установки в "0

"I-го триггера управления и с первым инверсным входом !-го элемента И третьей группы, выход i ãî элемента И четвертой группы соединен с прямым входом (i+1)-го элемента

И четвертой группы и с вторым входом (i+1)ro элемента И пятой группы, выход i-го элемента И пятой группы соединен с вторым входом I-ro элемента ИЛИ первой группы, с !-м входом второго элемента ИЛИ и с

i-ми разрешающими входами каждого коммутатора с первого по m-й, I-й вход группы входов распределения ресурсов устройства соединен с информационным входом I-ro регистра распределения ресурсов, J-й выход которого соединен с i-м входом !-ro элемента ИЛИ второй группы элементов ИЛИ и с

1702З72

i-м информационным входом J-го коммутатора, выход которого соединен с первым входом j-го сумматора, выход l-го элемента

ИЛИ второй группы соединен с вторым входом I-ro элемента И второй группы и с вторым инверсным входом f-го элемента И третьей группы, выход первого элемента

ИЛИ соединен с управляющим входом гене ратора тактовых импульсов, выход которого соединен с прямым входом первого элемента И четвертой группы и с вторым, входом первого элемента И пятой группы,, вход пуска устройства соединен с первым входом второго элемента И, выход которого, соединен с первым входом третьего элемента ИЛИ, с выходом установки в единичное состояние триггера режима, с входами уста, новки в единичное состояние всех тригге, ров тупика и с С-входами всех регистров

; :запросов и регистров распределения ресур сов, инверсный выход триггера режима со ; единен с вторым входом второго элемента И, прямой выход триггера режима соединен, с выходом занятости устройства, с первым инверсным и вторым управляющим входами (в+1)-го коммутатора и с прямым входом первого элемента И, вход свободных ресурсов устройства соединен с первым информационным входом (я+1)-го коммутатора, 5 выход которого соединен с информационным входом регистра свободных ресурсов, выход третьего элемента ИЛИ соединен с

С-входом регистра свободных ресурсов и входом одновибратора, выход которого сое1О динен с (m+2)-ми входами элементов И первой группы, )-й выход регистра свободных ресурсов соединен с вторыми входами Ц блока сравнения и с информационным входом J-го блока элементов И, выход которого

15 соединен с вторым блоком J-го сумматора, выходы сумматоров соединены с вторым информационным входом (я+1 -го коммутатора, с входами четвертого элемента ИЛИ, выход которого соединен с вторым входом

20 третьего элемента ИЛИ и с (1+1}м инверсным входом первого элементу И, выход которого соединен с входом установки в нулевое состояние триггера режима, выход второго элемента ИЛИ соединен с разреша25 ющими входами всех блоков элементов И.

1702372

Составитель Д.Ванюхин

Редактор А.Маковская Техред М.Моргентал Корректор M.Êó÷åðÿâàÿ, Заказ 4544 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101