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

 

Изобретение относится к вычислительной технике и может найти применение в вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения - повышение оперативности контроля. Устройство для контроля распределения ресурсов содержит п регистров 1 запросов , п регистров 2 распределения ресурсов, регистр 3 свободных ресурсов, триггер k режима, одновибраторы 5, , триггеры 6 тупика, триггеры 7 управления, nxm блоков 8 сравнения, группу 9 элементов И, группы блоков элементов И 10 и 11, m параллельных комбинационных сумматоров 12, коммутатор 13, элемен-- ты И 15 и 19, элементы ИЛИ 16, 18, и 20, 1 ил. (Л

СООЗ COBETCHHX

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

РЕСПУБЛИК (g()g G 06 F 11/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ и втоРСКОмм сзидктбдьСтаЧ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ по изоБ ятяниям и откРытиям

Г1РИ ГКНТ СССР

1 (21) 4770175/24 (22) 09,11.89 (46) 23,05.92 Бюл. Г 19

- (71) Конструкторское бюро электроприборостроения (72) А,В,Бек, M.А,Чернышов., Г.Н,Тимонькин, С,Н,Ткаченко., B.Ñ,Харченко, В.В,Герасименко и С,В„Хотименко (53) 681 ° 3 (088.8) (56) Авторское свидетельство СССР

Г 1015385, кл, С 06 F 11/00;

G 06 Р 9/00, 1983.

Авторское свидетельство СССР Г 1297051, кл, с Об 7 11/00, 1987. (54) УСТРОГ.СТВО лЛЯ КОИТРРЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57} Изобретение относится к вычислиÄÄSUÄÄ 1l735851 А1

2 тельной технике и может найти применение в вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения - повыше" ние оперативности контроля. Устройство для контроля распределения ресурсов содержит и регистров 1 запросов, и регистров 2 распределе" ния ресурсов, регистр 3.свободных ресурсов, триггер 4 режима,. одновибраторы 5, 14 и 17, триггеры 6 тупика, триггеры 7 управления, п х m блоков

8 сравнения, группу 9 элементов И, группы блоков элементов И 10 и 11, m параллельных комбинационных сумматоров 12, коммутатор 13, элемен-" ты И 15 и 19, элементы ИЛИ 16, 18, и 20, 1 ил, 1735851

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

Рель изобретения — повышение оперативности контроля.

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

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

1.1тl.п и регистров 2.1

2.,п распределения ресурсов, регистр

3 свободных ресурсов, триггер 4 режима, первый одновибратор 5, и триггеров 6.1 - 6.п тупика, и триггеров

7. 1 - 7.п управления,,и x m блоков

8,1,! - 8,п,m сравнения, группу элементов И 9.1 - 9,п, первую

10,1.1 " 10.п,m и вторую 11.1

ll„m группы блоков элементов И, m параллельных комбинационных сумматоров 12.1 - 12.тп, коммутатор 13, второй 14 одновибратор, первый 15 элемент И, первый 16 элемент ИЛИ, трети% 17 одновибратор, второй 18 элемент ИЛИ, второй 19 элемент И, третий 20 элемент ИЛИ, вход 21 пуска устройства, группа входов 22 свободных ресурсов устройства, группа входов 23,i запросов устройства, группа входов 24.i распределений устройства, выход 25.i.j группы выходов ресурсов в тупике устройства, выход

26,i группы выходов процессов в тупике устройства, выход 27 занятости устройства. и регистров 1.1-1.п запросов служат для приема и хранения матрицы запросов процессов. и регистров 2.1

2.п распределения ресурсов необходимы для приема и хранения матрицы распределения ресурсов процессам.

Регистр 3 свободных ресурсов выполняет функции приема и хранения вектора свободных ресурсов и результата сложения строки матрицы рас1 пределения ресурсов процессам с вектором свободных ресурсов. Триггер 4 режима выполняет перевод устройства из режима ожидания в режим работы и обратнб. Одновибратор 5 и элемент ИЛИ 20 предназначены для формирования импульса, свидетельствующего о ненулевом результате суммирования. и триггеров 6,1-6.п тупика служат для индикации процессов, вовлеченных в тупиковую ситуацию. и триггеров 7.1-7.п управления необходимы для управления процессом суммирования, моделирующим освобождение ресурсов. и х т блоков сравнения

8 1 - 8 .1.1 B.n.m выполняют поэлементное сравнение строк матрицы запросов процессов с элементами векторов свободных ресурсов.

Группа элементов И 9,1 - 9.п фиксирует тот факт, что все элементы строки матрицы запросов процессов меньше или равны элементам вектора свободных ресурсов.

Первая группа блоков элементов И

10.!. 1 — 10,п.m предназначена для подключения информационных выходов регистров 2.2 — 2.п распределения

2О ресурсов к первым n"ì информационным входам параллельных сумматоров

I2.1 - 12 m, Вторая группа блоков элементов И

11„1 - ll,m выполняет функцию подключения выходов регистра 3 свободных ресурсов к (n+1) м входам па" раллельных сумматоров 1?.1 — 12.m.

m параллельных комбинационных сумматоров 12,1 - 12,m выполняют операцию сложения.

Коммутатор 13 предназначен для подключения к входу регистра 3 выходов сумматоров 12,1 - 12,m и третьей группы информационных входов 22. Одновибратор 14 и элемент

35 ИЛИ 16 служат для формирования сигнала, инициирующего занесения суммы с выходов сумматоров 12, 1 — 12 m

s регистр 3 свободных ресурсов.

Сдновибратор 17 предназначен для

40 управления элементом И 19 и триггерами 6,i и 7,i (i = l,п), Первый элемент И 15 формирует сигнал, по которому производится инициирование начала работы устройства, Первый эле4$ мент ИЛИ l6 предназначен для формирования сигнала, по которому производится занесение информации в регистр 3 свободных ресурсов.

Второ" элемент ИЛИ 18 управляет

N подключением выходов регистра 3 свободных ресурсов к (и+1)-м входам параллельных сумматоров 12,1-12.m через блоки 1 t,l-ll.m элементов И., Второй элемент И 19 служит для формирования сигнала установки в нулевое состояние триггера 4 режима в соответствии с сигналами с выходов элементов И 9.i (i = l,n).! б цессов) запросов заносится информация о запросах процесса, которому присвоен

i-й порядковый номер, а в регистр распределения ресурсов 2.i заносится I информация о ресурсах, распределенных этому процессу, Выходы каждого регистра 1. 1, 2.i и 3 разделены на m групп выходов (полей) по числу типов ресурсов, которыми располагает контролируемая система. В j"ì поле (j = 1,m) каждого регистра 1. i запро" сов и 2,i распределения ресурсов содержатся коды, отражающие число ресурсов i-ro типа, запрашиваемых и распределенных i"ìó процессу соответственно, В 1-м поле регистра 3 свободных ресурсов содержится код, равный числу свободных ресурсов

j-ro типа в системе, Информация о запросах на ресурсы системь! с выходов регистров 1.1

1,п запросов поступает на первые входы блоков 8.1.1 - В.n.m сравнения, на вторые входы которых с выходов регистра 3 свободных ресурсов поступа" ет информация о числе свободных ресурсов в системе соответствующего типа.

Единичный сигнал блок Р,i.j (i

= 1,n, j = m) вырабатывает в том случае, когда код, поступающий на первый вход меньше или равен коду, поступающему на второй вход. Физически это значит, что i-м процессом запрашивается ресурсов j-го типа не больше, чем есть свободных ресурсов

j-го типа в системе. Когда на выходах всех блоков сравнения i-й группы (i = 1,,n) установятся единичные сигналы, на выходе элемента И 9. i формируется единичный уровень, устанавливающий по сигналу с выхода одновибратора 17 в нулевое состояние триггер б.i тупика и в единичное состояние триггер 7,i управления.

Кроме того, сигналы с выходов элементов И 9. i поступают íà i-e инверсные входы второго элемента И

19, на выходе которого может быть сформирован единичный сигнал, обнуляющий триггер 4 режима.

Если какой-либо из триггеров б,i тупика в результате анализа установился в нулевое состояние, то по" тейциалом низкого уровня со своего прямого выхода он запирает соответствующий элемент 9, i, что свидетельствует о беступиковости данного про» цесса.

5 173585

Третий элемент ИЛИ 20 предназна" чен для формирования сигнала, свидетельствующего о начале суммирования информации в сумматорах 12.j (j

1,m).

Вход 21 является входом пуска устройства. Первая группа информационных входов 22 предназначена для приема информации о свободных ресурсах в системе, Вторая группа информационных входов 23,1-23.п предназначена для приема информации. о текущих запросах процессов на ресурсы системы, Третья группа информационных входов 24.1"24.п служит для приема информации о текущем распределении ресурсов одновременно выполняющимся процессам, Первая группа информационных вы- 2О ходов 25.1,1 - 25.n.m предназначена для выдачи информации о ресурсах, по которым процессы вовлечены в тупик, Вторая группа информационных выходов 26,1-26.п служит для индикации процессов, вовлеченных в тупиковую ситуацию. С сигнального выхода

27 снимается информация о состоянии устройства.

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

В исходном состоянии триггер 4 режима и триггеры 7.1-7,п управления находятся в нулевом состоянии, По сигналу .пуска, поступающему на вход 21 пуска устройства, на выходе 35 первого элемента И 15 формируется импульс, по переднему фронту которого заносится информация об имеющихся запросах на ресурсы системы в регистры 1. — 1,п запросов с второй группы информационных входов 23.1

23.п, о распределенных ресурсахв регистры 2,! — 2.п с третьей груп. пы информационных входов 24,1-24,п, о свободных на текущий момент време- 45 ни ресурсах, системы - в регистр 3 свободных ресурсов с первой группы информационных входов 22 через коммутатор 13, и устанавливаются в единичное состояние все триггеры 6,1.б,п тупика, а по заднему фронту устанавливается в единичное состояние триггер 4 режима.

Регистры 1,1-.1.п запросов и.регистры 2.1-2.п распределения ресур- 55 сов закреплены за процессами, т,е. врегистр 1.,i (i = Т,п, где п - чис" ло одновременно функционирующих про7 1

Единичные потенциалы с выходов тех триггеров 7,1-7„n управления, номера которых соответствуют номеРам процессов, незаблокированных в данном .цикле обработки информации, .поступают на входы третьего элемента ИЛИ 18 и на управляющие входы соответствующих блоков элементов И первой группы блоков элементов И

10.1, t -.10,n,m, разрешая тем самым прохождение информации с выходов соответствующих регистров 2.1

2.и распределенных ресурсов на соответствующие входы параллельных сумматоров 12.1-12.m, Единичный сигнал с выхода третьего элемента ИЛИ

18 поступает на управляющие входы блоков элементов И 11„1 - t1.m второй группы блоков элементов И и разрешает прохождение информации с выходов регистра 3 свободных ресурсов на (и+1)-е входы параллельных сумма" торов 12.1 - 12.m (моделируется освобождение ресурсов незаблокированными процессами), Сформированная на выходах параллельных сумматоров 12,112,тп сумма поступает на входы третьего элемента ИЛИ 20, на выходе которого формируется единичнь|й потенциал, поступающий на управляющий вход одновибратора 5, который по переднему фронту формирует импульс управления одновибратором 14.

По заднему фронту этого импульса одновибратор 14 формирует импульс, обнуляющий триггеры 7.i (= Т,n) управления, через элемент

ИЛИ 16 -поступает на синхровход регистра 3 свободных ресурсов и одновибратора 17.

По переднему фронту импульса с выхода одновибратора 14 происходит . занесение в соответствующие поля регистра- 3 через коммутатоР 13 модифицированной суммы свободных и освобождаемых ресурсов. На вторые входы блоков 8„1.1-8,n.m поступает модифицированная информация с выходов регистра 3 свободных ресурсов и производится цикл обработки информации, аналогичный описанному выше, т.е.

ПО заднему Фронту импульса с выхода одновибратора 14 одновибратором

17 формируется импульс управления, поступающий на вход элемента И 19 и синхровходы триггеров 6.i тупика и 7.i (= 1,n) управления.

Ест на выходах элементов И 9.i (i = 1,й1 не будут сформированы

735851

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

На второй группе информационных выходов 26,1-26.и выставляется информация о процессах, вовлеченных в тупик: номер разряда, на котором выставлен единичный потенциал, соответствует номеру процесса, вовлеченного в тупиковую ситуацию, На первой группе информационных выходов

25,1.1 — 25,и.m выставляется информация, по- каким типам ресурсов процесс вовлечен в тупик: номер разряда в i-й группе (i = 1,n), на котором выставлен нулевой потенциал, соответствует номеру типа ресурсов, по которому 1.-й процесс вовлечен в тупик. Нулевой потенциал на сигнальном выходе 27 устройства свидетельствует о том, что анализ состояния системы устройства завершен, единичный потенциал свидетельствует, что в данный момент устройство занято и производит анализ состояния системы, Формула изобретения устройство для контроля распределения ресурсов, содержащее и ре35 гистров запросов и и регистров распределения ресурсов, регистр свободных ресурсов, два блока сравнения, пять триггеров управления, триггеры тупика и режима, коммутатор, m(n+1)

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

5Q группы выходов процессов в тупике устройства, о т л и ч а ю щ е е с я тем, что, с целью "повышения оперативности контроля, оно содержит (и-5) триггеров управления, (и-1)

55 триггеров тупика, (и-22) элементов

И, (n х ш-2) блоков сравнения, m сумматоров, три одновибратора, причем вход пуска устройства соединен с первым входом первого элемента И, .1

Составитель P,Ванюхин

Редактор О,Хрипта Техред М.дидык Корректор A.06Ðó÷ýÐ

Заказ 1817 Тираж Подписное

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

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

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

11 II

Я 17 выход которого соединен с входом ус-" тановки в единичное состояние триггера режима, с С-входами регистров запросов и регистров распределения ресурсов, с первым входом первого элемента ИЛИ и с входами установки в единичное состояние триггеров тупика, группы входов свободных ресурсов, запросов и распределений. устройства соединены соответственно с первой группой информационных входов коммутатора, с информационными входами регистров запросов, с информационными входами регистров распределения ресурсов, j-я группа выходов (j — 1,т), i-го регистра запросов (i

= 1,п) соединена,с первой группой входов (i-j) -го блока сравнения, выход которого соединен с i j-м выходом группы выходов ресурсов в тупике устройства и с (j+1) -м входом

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

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

35851 10 входами 1 j го блока элементов И первой группы, выходы которого соединены с 1 и группой входов j ão сумматора, выходы всех сумматоров соединены с входами третьего элемента ИЛИ и с соответствующими входами вгорой группы информационных входов коммутатора, выходы которого соединены с информационными входами регистра свободных ресурсов, 1-я группа выходов регистра свободных ресурсов соединена с вторыми входами i,j-x блоков сравнения и с информационны l5 ми -входами j-го блока элементов И второй группы, выходы которого соединены с .(n+1)-й группой входов j-го сумматора, инверсный выход триггера режима соединен с вторым входом первого элемента И, прямой выход триггера режима соединен с инверсным и прямым управляющими входами коммутатора и с выходом занятости устройства, выход второго элемент; ИЛИ соединен с управляющими входами всех блоков элементов И второй группы, выход третьего элемента ИЛИ соединен с управляющим входом первого одновибратора, выход которого соеди" нен с входом второго одновибратора, .

З выход которого соединен с входами установки в нулевое состояние всех триггеров управления и с вторым входом первого элемента ИЛИ, выход которого соединен с С-входом регистра свободных ресурсов и входом третье5 го одновибратора, выход третьего одновибратора соединен с прямым входом второго элемента И и с С»входами всех триггеров управления и

40 тупика °