Устройство для контроля распределения ресурсов Советский патент 1991 года по МПК G06F11/00 

1

(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.

Авторское свидетельство СССР № 1297051, кл. G 06 F 11/00, 1987.

(54)УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

(57) Изобретение относится к вычислительной технике и может найти применение в высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения - повышение оперативности контроля. Устройство содержит п регистров 1.1-1 .п запросов, п регистров распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, п триггеров 5.1-5.П тупика, п триге- ров бЛ-б.п управления, (nxm) блоков сравнения 7.1-7.П.ГП, первую группу элементов И 8.1-8.п, первую группу элементов ИЛИ 9.1- 9.п, вторую группу элементов И 10.1-10.п, третью группу элементов И 11.1-11,п. чет

Ш-1

vj о

го

GJ vj Ю

вертую и пятую группы элементов И, генератор тактовых импульсов, вторую группу элементов ИЛИ, группу коммутаторов 16.1 - 16.т, т блоков элементов И, m сумматоров, коммутатор 19, первый и второй элементы И, первый, второй, третий и четвертый эле- енты ИЛИ, одновибратор 32, Новыми элеИзобретение относится к вычислительной технике и может найти применение в Современных высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов.

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

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

Устройство для контроля распределения ресурсов содержит п регистров 1.1-1.П запросов, п регистров 2.1-2.П распределения ресурсов, регистр 3 свободных ресурсов, триггер 4 режима, п триггеров 5.1-5.п тупика, п триггеров 6.1-б.п управления, |(пхт)блоков 7.1.1 -Т.п.т сравнения первую irpynny элементов И 8.1-8.т, первую группу элементов ИЛИ 9.1-Э.п, вторую группу элементов И 10.1-10.П, третью группу элемен- тов И 11.1-11.п, четвертую группу элементов И 12.1-12.(п-1), пятую группу элементов И 13.1-13.П, генератор 14 тактовых импульсов, вторую группу элементов ИЛИ 15.1-15.ti, группу коммутаторов 16.1-16.rn, m блоков элементов И 17.1-17.т, т сумматоров 18.1-18.rn, коммутатор 19, второй элемент И 20, третий и первый элементы ИЛИ 21, 22, первый элемент И 23, второй и четвертый элементы ИЛИ 24, 25, вход 26 пуска устройства, вход 27.I (I 1,п) группы входов запросов устройства, вход 28 свободных ресурсов устройства, вход 29.11 группы входов распределения ресурсов устройства, выход ЗОЛ j группы выходов ресурсов в тупике ус- тройства, выход 31.1 группы выходов процессов в тупике устройства, одновибратор 32.

Регистры 1.1-l.n запросов служат для приема и хранения матрицы запросов от процессов на ресурсы системы.

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

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

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

Триггер 4 режима выполняет перевод устройства из режима ожидания в режим работы и обратно.

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

Триггеры 6.1-б.п управления необходимы для организации операции сложения, моделирующей освобождение ресурсов.

(nxm) блоков 7.1.1-7.п.m сравнения (выполняют поэлементное сравнение строк матрицы запросов процессов с элементами вектора свободных ресурсов.

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

Первая группа элементов ИЛИ 9.1-Э.п осуществляет выбор обнуляющих сигналов для триггеров 6.1-б.п управления с двух входов.

Вторая группа элементов И 10.1-10.п выполняет формирование сигналов, необходимых для выполнения операции суммирования.

Третья группа элементов И 11.1-11.П формирует сигналы обнуления триггеров 6.1-б.п управления в том случае, если соответствующий процесс не владеет ни одной единицей ресурсов.

Четвертая группа элементов И 12.1- 12,(п-1) служит для разрешения или запрещения прохождения тактовых импульсов в зависимости от сигналов, выставленных на выходах элементов И 10.1-Ю.п.

Пятая группа элементов И 13.1-13.п предназначена для регулирования сигналов, необходимых для выполнения операций сложения.

Генератор 14 тактовых импульсов служит для формирования последовательности тактовых импульсов.

Вторая группа элементов ИЛИ 15.1- 15.п предназначена для фиксации отсутствияраспределенияресурсовсоответствующим процессом.

Группа коммутаторов 16.1-16.m выполняет функцию коммутации i-й группы выходов регистров 2.1-2.П распределения ресурсов к первым входам сумматоров 18.1-18.rn.

Блоки 17.1-17.rn элементов И предназначены для подключения выходов регистра 3 свободных ресурсов к вторым входам сумматоров 18.1-18.rn.

Сумматоры 18.1-18.m выполняют операцию сложения.

Коммутатор 19 коммутирует по входу регистра 3 свободных ресурсов выходы сумматоров 18.1-18.rn и третью группу информационных входов.

Элемент И 20 служит для формирования сигнала, по которому инициируется работа устройства.

Элемент ИЛИ 21 вырабатывает сигналы, по которым осуществляется занесение информации в регистр 3 свободных ресурсов.

Элемент ИЛИ 22 служит для формирования сигнала запуска генератора 14 тактовых импульсов.

Элемент ИЛИ 24 управляет подключением выходов регистра 3 свободных ресурсов к вторым входам сумматоров 18.1-18.rn через блоки 17.1-17.rn элементов И.

Элемент ИЛИ 25 формирует сигнал, по которому заносится информация в регистр 3 свободных ресурсов с выходов сумматоров 18.1-18.rn.

Одновибратор 32 формирует сигнал записи информации в триггеры 5,1-5.п; 6.1- б.п.

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

В исходном состоянии триггер 4 режима и триггеры 6.1-б.п управления находятся в нулевом состоянии.i

По сигналу пуска, поступающему на вход 26 пуска устройства, на выходе элемента И 20 формируется импульс, по переднему фронту которого заносится информация об имеющихся запросах на ресурсы системы в регистры 1.1-1.П запросов с первой группы информационных входов 27.1-27.П, о распределенных ресурсах - в регистры 2.1-2.П с третьей группы информационных входов 29.1-29.П, о свободных на текущий момент времени ресурсах - в регистр 3 свободных ресурсов с второй группы информационных

входов 28 через коммутатор 19 и устанавливаются в единичное состояние все триггеры 5.1-б.п тупика, а по заднему фронту устанавливается в единичное состояние триггер 5 4 режима. Длительность сигнала пуска такова, что позволяет закончиться переходным процессам в схеме по цепи: регистры 1.1-1.П запросов и регистр 3 свободных ресурсов, блоки 7.1-7.п.т сравнения, элемен0 тов И 8.1-8.П триггеры 6.1-6.п управления и элементы И 10.1-Ю.п.

Регистры 1.1-l.n запросов и регистры 2.1-2.П распределения ресурсов закреплены за процессами, то есть в регистр запро5 сов 1. i (I Т, п, где п - число одновременно функционирующих процессов) заносится информация о запросах 1-го процесса, а в регистр 2.1 распределения ресурсов - информация о ресурсах, распределенных это0 му процессу.

Выходы каждого регистра 1.1, 2.1 и 3 разделены на группы выходов (полей) по числу типов ресурсов, которыми располагает контролируемая система. В j-м поле

5 () каждого регистра запросов Л. I и распределения ресурсов 2.1 содержатся коды, отражающие число ресурсов j-ro типа запрашиваемых и распределенных 1-му процессу соответственно. В j-м поле регистра 3 сво0 бодных ресурсов содержится код, равный числу свободных ресурсов j-ro типа в системе на момент контроля.

Информация о запросах на ресурсы системы с выходов регистров 1.1-l.n запро5 сов поступает на первые входы блоков 7.1-7.п.m сравнения, на вторые входы которых с выходов регистра 3 свободных ресурсов поступает информация о числе свободных ресурсов в системе. Единичный

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

5 запрашивается ресурсов j-ro типа не больше, чем есть свободных ресурсов j-ro типа в системе.

Когда на выходах всех блоков сравнения i-й группы (,п) установятся единич0 ные сигналы, на выходе элемента И 8.I формируется единичный сигнал с выхода одновибратора 32, устанавливающий в нулевое состояние триггер 5.1 тупика и в единичное состояние - триггер 6.1.1

5 управления. Это значит, что i-й- и процесс в тупиковую ситуацию при текущем распределении не вовлечен. Все ресурсы, которыми он владеет, будут возвращены в систему. Единичный сигнал с выхода триггера 6.1 управления поступает на вторые входы 1-х

элементов И первой 10.1 и второй 11.1 групп элементов И.

В случае, если в регистре 2.1.1 распределения ресурсов содержится нулевая информация, 1-му процессу не распределен ни один из m типов ресурсов, на выходе элемента ИЛИ 15.1 второй группы элементов /1ЛИ формируется нулевой потенциал, кото- )ый поступает на первый вход элемента И 10.1 первой группы элементов И и запреща- :т прохождение через него единичного потенциала с выхода триггера 6.1 управления, а также поступает на первый инверсный вход элемента И 11.1 второй группы элементов И, на третий инверсный вход которого поступает нулевой потенциал с выхода элемента ИЛИ 9.1 первой группы элементов ИЛИ, в результате чего на выходе элемента И 11.1 формируется единичный потенциал, поступающий на второй вход элемента ИЛИ 9.1, на выходе которого формируется единичный потенциал, поступающий на третий инверсный вход элемента И 11.1, в результате этого на его выходе формируется нулевой потенциал.

Таким образом, на выходе элемента И 11.1 формируется единичный импульс, поступающий через элемент ИЛИ 9.1 на вход установки в О триггера 6.1 управления, и по заднему фронту обнуляет его.

В том случае, когда в регистре 2.1 распределения ресурсов записана ненулевая информация, то есть 1-му процессу распределен хотя бы один ресурс любого типа, на выходе элемента ИЛИ 15.1 второй группы элементов ИЛИ формируется единичный потенциал, который поступает на первый вход элемента и 10.1 первой группы элементов И, и на его выходе формируется единичный сигнал, поступающий на второй инверсный вход элемента И 12 третьей группы, на второй вход элемента И 13.1 четвертой группы, на i-й инверсный вход второго элемента И 23 и на 1-й вход элемента ИЛИ 22. На выходе последнего формируется единичный потенциал, поступающий на управляющий вход генератора 14 тактовых импульсов, который начинает вырабатывать последовательность тактовых импульсов, поступающих на первые входы элементов И 12.1 и 13.1 третьей и четвертой групп. Длительность тактового импульса такова, что позволяет осуществить формирование суммы на выходах сумматоров 18.1-18.т, занесение ее в регистр 3 свободных ресурсов, сравнение в блоках 7.1.1-7.п.m сравнения и формирование соответствующих сигналов на выходах элементов И 10.1-10.п. Пауза между тактовыми импульсами равна сумме длительности тактового импульса и времени распространения его по цепи элементов И 12.1-12.(п-1) и 13.п. В случае, если на выходе элемента И 10.1 выставлен единичный потенциал (1-й процесс в тупиковую ситуацию не вовлечен), который поступает на второй инверсный вход элемента И 12.1 и запрещает прохождение через него тактовых импульсов, потенциал с выхода элемента И 10.1 поступает на второй вход элемента

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

Тактовый импульс с выхода генератора 14 через цепь элементов И 12.1-12 (1-1) и 13.1 поступает на 1-е управляющие входы

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

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

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

Кроме того, единичный импульс с выхода элемента И 13,1 поступает через элемент ИЛИ 9.1 на вход триггера 6.1 управления и по заднему фронту обнуляет его. Информа5 ция с выходов сумматоров 18.1-18.rn поступает на входы четвертого элемента ИЛИ 25, на выходе которого формируется единичный потенциал, поступающий на второй вход элемента ИЛИ 21, на выходе которого

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

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

0 который поступает на второй инверсный вход элемента И 12.1 и разрешает прохождение через него тактовых импульсов, а также нулевой потенциал с выхода элемента И 10.1 поступает на второй вход элемента И

5 13.1, запрещая прохождение через него тактовых импульсов. Тактовый импульс с выхода генератора 14 через цепь элементов И 12.1-12.1 поступает на входы элементов И 12. (1+1) и 13 (1+1) и, если на выходе элемента И 10. (1+1) выставлен единичный потенциал,

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

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

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

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

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

Нулевой потенциал на сигнальном выходе 32 устройства свидетельствует о том, что анализ состояния системы завершен, единичный потенциал свидетельствует о том, что в данный момент устройство занято и осуществляет анализ состояния системы.

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

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

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

0 триггеров управления, п-1 триггеров тупика, nxm-2 блоков сравнения, 5п - 23 элементов И, (2п - элементов ИЛИ, m коммутаторов, m сумматоров, одновибратор, причем 1-й вход (,п), где п - число одновременно

5 функционирующих процессов) группы входов запросов устройства соединен с информационным входом 1-го регистра запроса, J-й выход 0 f.m, где m - число типов разделяемых процессами ресурсов системы) ко0 торого соединен с первым входом блока I.J сравнения, выход которого соединен с I.J- выходом группы выходов ресурсов в тупике устройства и с 0+1 hM входом 1-го элемента И первой группы, выход которого соединен

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

5 элементов И второй и третьей групп, выход 1-го элемента И второй группы соединен с инверсными входом 1-го элемента И четвертой группы, с первым входом 1-го элемента И пятой группы, с 1-м входом первого эле0 мента ИЛИ и с 1-м инверсным входом первого элемента И, выход 1-го элемента И третьей группы соединен с первым входом 1-го элемента ИЛИ первой группы, выход которого соединен с входом установки в О

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

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

выход которого соединен с информационным входом регистра свободных ресурсов, выход третьего элемента ИЛИ соединен с С-входом регистра свободных ресурсов и входом одновибратора, выход которого соединен с(т+2)-ми входами элементов И первой группы, J-й выход регистра свободных ресурсов соединен с вторыми входами l,j блока сравнения и с информационным входом |-го блока элементов И, выход которого

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

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