Устройство для контроля распределения ресурсов Советский патент 1987 года по МПК G06F15/177 

1 1

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

Целью изобретения является повышение быстродействия.

На фиг, 1 представлена функцио- нальная схема предлагаемого устройст ва для контроля распределения ресурсов; на фиг. 2 - функциональная схема блока 1.1 регистров; на. фиг. 3 - функциональная схема блока 2.1 регистров j на фиг. 4.- функциональная схема блока синхронизацииj на фиг.5 функциональная схема распределителя импульсов; на фиг. 6 - функциональная схема управляющего мультиплексора 8, 1; на фиг. 7 - функциональная схема управляющего мультиплексора 9.1; на фиг. 8 - функциональная схема информационного льтиплексора; на фиг. 9 - временные диаграммы функционирования устройства.

Устройство для контроля распределения ресурсов (фиг. 1) содержит пер вый (1.1) - (1п+1)-ый (l.m) блоки регистров, второй (2.1) - 2.1П-ЫЙ (2.in) блоки регистров, блок 3 синхронизации, третий распределитель 4 импульсов, первый распределитель 5 импульсов, четвертый распределитель 6 импульсов, второй распределитель 7 импульсов, первый (8.1) - (т+1)-й (8.т) управляющие мультиплексоры, второй 9.1 - 2.т-й 9.т управляющие мультиплексоры, первый информационный мультиплексор 10, второй информационный мультиплексор 11, регистр 12 единиц ресурсов, первую схему 13 сравнения, .шифратор 14,вторую схему 15 сравнения, четвертый 16, второй 17, пятый 18, третий 19 триггеры управления, триггер 20 совпадения, триггер 21 тупика, первый триггер 22 управления, триггер 23 анализа, блоки элементов И 24.1 - 24.п, блоки элементов И 25.1 - 25,п, блоки элементов И 26.1 - 26.k; 27.1 - 27.k, где п - максимально возможное число единиц ресурса данного типа, а k - число запросов к ресурсу данного типа, коммутатор 28, блок 29 элементов И, восьмой 30, девятый 31, десятый 32, восемнадцатый 33, четырнадцатый 34, шестой 35, пятнадцатый 36, тринадцатый 37, первый 38, третий 39, второй 40, четвертый 41, пятый 42,

20

25

2970512

одиннадцатый 43, двадцатый 44, двенадцатый 45, девятнадцатый 46, шест- надцатый 47, седьмой 48, семнадцатый 49, двадцатый 50 элементы И,блок

5 51 элементов И, седьмой 52, восьмой 53, второй 54, первый 55, элемент ИЛИ-НЕ 56, пятый 57, шестой 58,-третий 59, четвертый 60 элементы ИЛИ, второй 61 элемент ИЛИ-НЕ,вход пуска

0 62 устройства, первую группу 63 и вторую 64 информационных входов устройства, третью группу 65 информационных входов устройства, выход 66 устройства. -5 На фиг. 4 приняты обозначения

первый 67,второй 68,третий 69 и четвертый 70 выходы блока 3 синхрониза- ции.Кроме того на чертежах приняты обозначения;выходы 71.1 - 71.ти 72.-1- 72.га мультиплексоров 8.1 - 8.njвыходы 73.1 - 73.m мультиплексоров 9.1 - 9.т, группа вькодов 74.1 - 74.п распределителя импульсов 4, группа выходов 75.1 - 75.m распределителя импульсов 5j выход 76 распределителя 5, группа выходов 77.1 - 77.k распределителя 6, выход 78 распределителя 6,группа выходов 79.1 - 79.m распределителя 6,группа вькодов 79.1 - 79.m распределителя импульсов 7, выход 80 распределителя импульсов 7, выходы 81,. 1 - 8l.m блока элементов И 29, информационные выходы 82.1 - 82.m регистров 1.1 - 1.т,ин35 формационные выходы регистров 83.1 - 83.m регистров 2.1 - 2.т, вход 84 останова блока 3 синхрониз ации.

Блок 1 регистров (фиг. 2) содержит регистры 85.1 - 85.п, элемент

40 ИЛИ 86, первую (87.1) - п-ю (87.п) группы информационных входов, первый 81.1 и второй 73.1 управляющие входы, группу 82.1 выходов, состоящую из первой (88.1) - п-ой (88.п) групп выходов соответственно первого (85.1) - п-го (85.п) регистров.

Блок 2.1 регистров (фиг. 3) содержит регистры 89.1 - 89.k, первую 90.1 k-ю 90.k группы информационных

50 входов, управляющий вход 72.1,группу 83.1 выходов, состоящую из первой 91.1 - k-ой 91.k групп выходов соответственно первого 89.1 - k-ro 89.k регистров.

55 Блок 3 синхронизации (фиг. 4) содержит триггер 92 режима, генератор 93 последовательностей импульсов, элемент И 94, вход 62 пуска.

30

45

управляющий вход 84, первый 67,второй 68, третий 69 и четвертый 70 выходы.

Единичный выход триггера 92 режима соединен с управляющим входом генератора 93 последовательностей импульсов, а также с первым входом элемента И 94, выход которого соединен с нулевым входом триггера 92 режима.

Распределители 4-7 импульсов имеют идентичную функциональную схему (фиг. 6).Причем (п+1)-й выход распределителя 4 импульсов не используется. В скобках на фиг. 5 обозначены номера соответствующих входов и выходов соответственно распределителей 5-7 импульсов.

Распределитель 4 (5 - 7) импульсов содержит счетчик 95 с входом установки в ноль, дешифратор 96 с син- хровходом. Вход 97 - счетный вход распределителя импульсоз, вход 98 - останова распределителя.

Управляющий мультиплексор 8.1 (фиг. 6) содержит блок 99 элементов И, элемент И 100, элемент ИЛИ 101.

Управляющий мультиплексор 9.i (фиг. 7) содержит блок 102 элементов И, элемент И 103.

Первый (второй) информационный мультиплексор 10 (11) (фиг. 8) содержит первую 104 (105) - т-ую 106 (107) группы блоков элементов И,блок 108 элементов ИЛИ.

Регистр 12 (фиг. 1) единиц ресурсов предназначен для приема, хранения и вьщачи количества единиц ресурсов для каждого типа ресурса.Причем, регистр 12 условно разбит на m полей по числу типов ресурсов.В i-oe поле в момент запуска системы с группы 65 входов заносится код максимального количества единиц i-ro типа ресурса.

Схема 13 сравнения предназначена для сравнения кодов номеров процессоров запрашивающих ресурсы и владеющих ими. Шифратор 14 предназначен

гер 20 совпадения предназначен для фиксации наличия номера анализируемого процесса, владеющего ресурсом среди множества процессов, запраши5 вающих ресурсы, а также для формирования игнала разрешения выбора следующего кода номера процесса, владеющего каким-либо ресурсом.

Триггер 21 тупика предназначен

10 для фиксирования сигнала тупика.Триггер 22 управления предназначен для фиксирования сигнала, указывающего на факт удаления хотя бы одного процесса в результате анализа.Триггер

15 23 анализа предназначен для фиксации сигнала окончания анализа.

.Группы (24.1 - 24.п) - (25.1 - 25.п) блоков элементов И предназначен для одновременной передачи инфор20 мации о кодах номеров процессов,

владеющих ресурсами, с входа 63 устройства в регистры блоков 1.1 - 1.т регистров. Группы (26.1 - 26.k) - (27.1 - 27.k) блоков элементов И

25 I предназначены для одновременной пере- дачи информации о кодах номеров процессов, запрашивающих ресурсы,с входа 64 устройства в регистры блоков 2.1 - 2.т регистров.

30 Коммутатор 28 предназначен для формирования на выходной шине кода, выбранного одним из управляющих сигналов. Элементы 29.1 - 29.т предназначены для формирования сигнгшов ус35 тановки в ноль регистров блоков 1.1 - 1.т регистров.

Элемент И 30 предназначен для формирования сигнала-идентификатора нулевого состояния регистров 1.1 40 l.m. Элементы И 31 - 36,43 - 49 предназначены для синхронизации работы элементов устройства. Элемент И 37 предназначен для формирования сигнала установки в нулевое состояние

45 триггера 22 управления. Элемент И 38 (50) предназначен для формирования сигнала разрешения выбора следующё- го кода номера процесса, владеющего (запрашивающего) как 1м-либо ре-

для формирования текущего кода едини-50 сурсом системы. Элемент И 39 предназцы ресурса данного типа. Схема 15 сравнения предназначена для сравнения текущего кода единицы ресурса данного типа с кодом количества единиц ресурса данного типа. Триггеры 16-19 управления предназначены для управления работой распределителей 4-7 импульсов соответственно.Триггер 20 совпадения предназначен для фиксации наличия номера анализируемого процесса, владеющего ресурсом среди множества процессов, запрашивающих ресурсы, а также для формирования игнала разрешения выбора следующего кода номера процесса, владеющего каким-либо ресурсом.

Триггер 21 тупика предназначен

для фиксирования сигнала тупика.Триггер 22 управления предназначен для фиксирования сигнала, указывающего на факт удаления хотя бы одного процесса в результате анализа.Триггер

23 анализа предназначен для фиксации сигнала окончания анализа.

.Группы (24.1 - 24.п) - (25.1 - 25.п) блоков элементов И предназначен для одновременной передачи информации о кодах номеров процессов,

владеющих ресурсами, с входа 63 устройства в регистры блоков 1.1 - 1.т регистров. Группы (26.1 - 26.k) - (27.1 - 27.k) блоков элементов И

предназначены для одновременной пере- дачи информации о кодах номеров процессов, запрашивающих ресурсы,с входа 64 устройства в регистры блоков 2.1 - 2.т регистров.

Коммутатор 28 предназначен для формирования на выходной шине кода, выбранного одним из управляющих сигналов. Элементы 29.1 - 29.т предназначены для формирования сигнгшов установки в ноль регистров блоков 1.1 - 1.т регистров.

Элемент И 30 предназначен для формирования сигнала-идентификатора нулевого состояния регистров 1.1 l.m. Элементы И 31 - 36,43 - 49 предназначены для синхронизации работы элементов устройства. Элемент И 37 предназначен для формирования сигнала установки в нулевое состояние

триггера 22 управления. Элемент И 38 (50) предназначен для формирования сигнала разрешения выбора следующё- го кода номера процесса, владеющего (запрашивающего) как 1м-либо ре-

начен для формирования сигнала тупика. Элемент И 40 предназначен для формирования сигнала-признака ого, что при анализе были удаления прб- цессов. Элемент И 41 предназначен для формирования сигнала разрешения нового цикла анализа. Элемент И 42 предназначен для формирования сигна

5

ла установки в единичное состояние триггера 23 анализа. Блок 51 элементов И предназначен для одновременной передачи кода с выхода мультиплексора 11 на вторую группу входов схемы 13 сравнения.

Элементы ИЛИ 52 - 55 предназначены для формирования сигналов разрешения первой и последующих выборок кодов номеров процессов,владеющих ресурсами, а также для управления работой распределителей 6 и 7 импульсов „

Элементы ИЛИ-НЕ 56 и 61 предназначены для формирования сигналов, управляющих работой элементов И 38 и 50 соответственно. Элементы ИЛИ 57 - 60 предназначены для формирования сигналов разрешения выбора кодо номеров процессов, запрашивающих ресурсы.

Вход 62 пуска предназначен для приема сигнала пуска устройства.Первая группа 63 информационных входов предназначены для приема кодов номеров процессов, владеющих единицами ресурсов. Вторая группа 64 информационных входов предназначена дпя према кодов номеров процессов, запрашивающих единицы ресурсов. Третья группа 65 информационных входов преназначена для приема информации о максимальном количестве единиц ресурсов i-ro типа (i 1jm).

Выход 66 устройства предназначен для вьщачи сигнала-признака тупико- вой ситуации в вычислительной системе.

Рассмотрим функциональное назначение элементов блока 1.1 регистров (фиг. 2).

Регистр 85.j предназначен для приема, хранения и выдачи информации о коде процесса, владеющего j-о единицей i-ro ресурса. Элемент ИЛИ 86 предназначен для формирования сигнала установки в нуль регистров 86.1 - 86.п. Группа 87.j информационных входов предназначена для приема в регистр 85.j-ro кода номера пр цёсса, владеющего единицами ресурса i-ro типа.

Рассмотрим функциональное значение элементов блока 2 регистров (фиг. 3).

Регистр 89.j предназначен для приема, хранения и вьщачи информаци о коде номера процесса, запрашиваю

5

0

щего

0

j-ю единицу 1-го типа ресурса. Группа 90.j информационных входов предназначена для приема в регистр 89.j кода номера процесса,запрашивающего j-ю единицу i-ro ресурса. Вход 72.i предназначен для установки в нуль всех регистров блока 2.i регистров. Группа 83.i выходов предназначена для выдачи информации о кодах номеров процессов, запрашивающих единицы ресурса i-ro типа.

Рассмотрим функциональное назначение элементов блока 3 синхронизации (фиг. 4).

Триггер 92 режима предназначен для формирования сигнала запуска генератора 93, Генератор 93 предназначен для формирования трех последовательностей импульсов на выходах 67 70 (фиг. 9) блока 3. Элемент И 94 предназначен для формирования сигнала установки в ноль триггера 92 режима. Вход 62 пуска предназначен 5 для приема сигнала пуска устройства. Вход 84 предназначен для приема сигнала окончания анализа. Выход 67 предназначен для вьздачи сигнала управления работой управляющих мультиплексоров 8.1 - 8.т, 9.1 - 9.т, а также для управления приемом информации в регистры всех блоков.

Функциональное назначение элементов распределителя 4 (5 - 7) импульсов следующее.

Счетчик 95 предназначен для формирования кода .выбора очередного процесса. Дешифратор 96 предназначен для формирования сигнала выбора кода очередного процесса для анализа.

Счетный вход 97 предназначен для приема импульсов на одноименный вход счетчика 97. Вход 98 установки предназначен для приема сигнала установки в ноль счетчика 95. Группа выходов 74.1 - 74.п (75.1 - 75.т; 76; 77.1 - 77.k; 78; 79.1 - 79,m, 80) предназначена для вьщачи распределенных во времени импульсов.

Рассмотрим функциональное назначение элементов управляющего мульти- плексора 8.i (фиг. 6),

Элемент 99.i предназначен-для формирования сигнала разрешения в 5 случае нулевого входного кода.Элемент 100 предназначен для формирования сигнала управления, если все сигналы разрешения положительные,

0

5

0

5

.е. все регистры блока 1.1 регистов находятся в нулевом состоянии. лемент ИЛИ 101 предназначен для ормирования сигнала управления работой блока 2.1 регистров. Группа 82.1 информационных входов предназачена для приема кодов номеров проессов, владеющих единицами ресурса 1-го типа с целью дальнейшего анализа. Вход 68 предназначен для риема сигнала разрешения работы ультиплексора. Выходы 71.1 и 72.1 предназначены для выдачи сигналов правления.

Элементы управляющего мультиплексора 9.1 имеют следующие функциональные значения (фиг. 7).

Элемент 102.J предназначен для формирования признака отсутствия запроса на j-ю единицу 1-го ресурса. Элемент 103 предназначен для формирования сигнала установки в нуль регистров соответствующего блока 1.1 регистров. Группа 83.1 информационных входов предназначена для приема кодов номеров процессов, запрашивающих 1-й ресурс.Вход 68 предназначен для приема сигнала разрешения работы мультиплексора.Выход 73.1 предназначен для управления работой соответствующего блока 1.1 регистров.

Рассмотрим функциональное назначение элементов мультиплексора 10 (11) (фиг. 8).

Блоки 104 (105) - 106 (107) элементов И соответственно первой тп-ой групп предназначены для выбора кодов номеров процессов,владеющих (запрашивающих) соответствующими единицами ресурсов различных типов. Элементы ИЛИ 108.1 - 108.1 предназначены для формирования кодов номеров процессов, владеющих (запрашивающих) ресурсами (ресурсы).Группа 82 (83) информационных входов предназначена для приема кодов номеров процессов, владеющих (запрашивающих) ресурсами (ресурсы). Группы 74 (77) и 75 (79) входов предназначены для приема сигналов управления работой мультиплексора. Группа 109 выходов предназначена для вьщачи на вторую группу входов схемы 13 сравнения кода йоме- ра процесса, владеющего (запрашивающего) соответствующей единицей какого-либо типа ресурса.

Работа устройства происходит в соответствии со следующим алгоритмом.

В тупиковую ситуацию могут быть

вовлечены только те процессы,которые владеют какими-либо ресурсами и дополнительно их запрашивают.В свою очередь, в тупик могут быть вовлечены только те ресурсы, которыми процессы владеют (все единицы ресурса заняты) и на них есть запросы от других процессов (хотя бы один запрос) . Ресурсы, на которые нет запросов, либо свободна хотя бы одна единица ресурса из дальнейшего анализа удаляются, так как в анализируемый момент времени t они в тупик вовлечены не будут. Удаление (обнуление соответствующего блока 1.1, 2.1 регистров) производится по сигналам с выходов управляющих мультиплексо- ров 8.1 и 9.1 (1 ТТи).

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

Процедуру полного просмотра и сравнения кодов номеров процессов, владеющих ресурсами, с кодами номеров процессов, запрашивающих их по всем типам ресурсов, назовем циклом

анализа.

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

то данный процесс из дальнейшего анализа необходимо удалять. Следовательно, ресурс, единицей которого владел анализируемый процесс, в тупик также вовлечен не будет. Поэтому производится обнуление соответствующего блока 1.1 регистров и с помощью управляющего мультиплексора 8.1 блока 2.1 регистров. Кроме того, триггером 22 фиксируется факт удаления

процесса в цикле анализа.

Если текущий цикл анализа завершен и в нем были удаления процессов, то процедура анализа продолжается.

Сигналом с выхода элемента И 41 инициируется очередной цикл анализа.В противном случае работа устройства прекращается и анализируется состояние блоков 1.1 регистров (i 1,m), в которых записываются коды номеров процессов, владеюпще соответствующими типами ресурсов.Если они нуле- вые,то тупика в системе нет,иначе - тупик. Причем, оставшиеся коды номеров процессов ho соответствующим ресурсам и составляют тупиковое множество процессов и ресурсов.

Предлагаемое устройство функционирует следующим образом.

В исходном состоянии все триггеры находятся в нулевом состоянии (входы начальной установки не показаны) . Единичный потенциал с первого вькода 67 блока 3 (нулевого выхода триггера 92 блока 3 (фиг. 4). Синхронизации разрешает прием информации через блоки 24 - 27 элементов И о состоянии распределения ресурсов системы и запросов на них в регистры соответствующих блоков 1,i и 2.1 регистров (1 1 ,т, где m - число типов ресурсов в системе). Этим же сигналом управляющие мультиплексоры 8.1 и 9.1 (i 1,ш) закрыты. Взаимная установка в нулевое состояние регистров соответствующих блоков 1.1 и 2.1 регистров (1 1,т) запрещена.

По сигналу пуска (начала анализа) поступающему на вход 62 устройства (фиг. 1), триггер 92 блока 3 (фиг. 4 устанавливается в единичное состояние. Включается генератор 93 потенциалом с единичного выхода этого триггера и начинается формирование последовательностей импульсов на выходах генератора 93 блока 3 синхронизации в соответствии с временными диаграммами, приведенными на (фиг. 9) Нулевым сигналом с выхода 67 блокируется прием информации в регистры блоков 1.1 и 2.1 регистров и открываются мультиплексоры 8.1 и 9.1.

Если хотя бы один регистр блока 1.1 регистров содержит нулевой код (соответствующая единица ресурса 1-го типа свободна), то на выходе 72.1 управляющего мультиплексора 8.1 формируется единичный сигнал, который является сигналом установки в нуль всех регистров блока 2.1 регистров. Кроме того, единичный сигнал дюрмируется на выходе 73.j му/гь типлексора 9.j, для которого все регистры соответствующего блока регистров имеют нулевые коды,, Этот сигнал является сигналом установки в нуль регистров блока l.j регистров.

Сущность этих операций состоит в исключении из дальнейшего рассмотреНИН процессов, которые заведомо могут быть заверщены и, вследствие этого,к тупику не ; приведут.Далее производится переход к выявлению процессов, которые являются только владельцами некоторых единиц ресурсов, а сами дополнительно никакие другие единицы ресурсов не запрашивают.Если некоторый процесс является только владельцем какой-либо единицы ресурса определённого типа, то его номер не должен быть записан ни в одном из блоков 2,1 - 2.т . регистров.На проверке этого факта основывается выявление процессов, которые только

владеют ресурсами.

Одновременно сигнал пуска с входа 62 устройства через элементы ИЛИ 54 и 55 поступает соответственно на входы элементов И 31 и 32 и импульсом с выхода 68 блока 3 синхронизации эти элементы открываются.Третий 16 и первый 17 триггеры управления при этом устанавливаются в единичное состояние. Сигналы с единичных

выходов триггеров 16 и 17 поступают на входы элементов И 33 и 35 соответственно.

Импульс с выхода 65 блока 3 синхронизации открывает элементы И 33

и 35 и поступает на счетные входы распределит€ лей 4 и 5 импульсов (фиг. 5) соответственно.

Сигналы с первых выходов соответственно 74.1 и 75.1 распределителей

ft н 5 через первую группу 104 блоков элементов И, а также блок 108 элементов ИЛИ мультиплексора 10 (фиг г 8) разрешают подключение выходов первого регистра 85.1 блока 1.1 регистров

(фиг. 2) к первой группе входов схемы 13 сравнения (фиг. 1).Если код процесса в первом 85.1 регистре (фиг. 2) оказывается нулевым,то элемент И 38 (фиг. 1) на прямом выходе

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

11

процесс анализа по всем единицам ресурса первого типа.

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

Импульсом с выхода элемента И 33 триггер 20 совпадения устанавливается в нулевое состояние. Сигнал с первого выхода 75.1 распределителя 5 импульсов подается на вход элемента .И 37. Код с выходов 74.1 - 74.п распределителя 4 импульсов (фиг. 1 и 5) поступает на шифратор 14, с вькодов которого в модифицированном виде подается на первую группу входов второй схемы 15 сравнения.

По заднему фронту импульса с выходов элементов И 33 и 35 триггеры соответственно 16 и 17 устанавливаются в нулевое состояние, блокируя тем самым счетные входы распределителей 4 и 5 импульсов соответственно.

Итак, если выбранный код владельца единицы ресурса первого типа оказался отличным от нуля, то сигнал с инверсного выхода элемента И 38 через элементы ИЛИ 57 и 60 поступает на входы элементов И 43 и 45 соответственно. Импульс с выхода 68 блока 3. синхронизации (фиг. 4) открывает элементы И 43 и 45 и поступает на единичные входы триггеров 18 и 19 управления, устанавливая их в единичное состояние.

Положительные потенциалы с единичных выходов этих триггеров пос - тупают на входы элементов И 46 и 48 соответственно. Импульс с выхода 70 блока 3 синхронизации, открьшая элементы И 46 и 48, поступает на счетные входы распределителей 6 и 7 импульсов соответственно.

Сигналы с первых выходов 77.1 и 79.1 распределителей 6 и 7 через первую группу 105 блоков элементов И,а также блок 108 элементов И мультиплексора 11 (фиг. 8) осуществляют коммутацию вькодов первого регистра 89.1 блока 2.1 регистров на выходы мультиплексора.

Если код процесса в этом регистре нулевой, то на прямом выходе элемента И 50 формируется положитель9705112

ный сигнал, который инициирует выбор очередного запроса ресурса того же типа.

На инверсном выходе элемента И

5 50 (фиг. 1) вырабатывается низкий потенциал, который запрещает передачу кода номера процесса на вторую группу входов схемы 13 сравнения. Если же код выбранного процесса

10 не нулевой, то на инверсном выходе элемента И 50 формируется сигнал разрешения, по которому код номера процесса, запрашивающего единицу ресурса первого типа, подается на

15 вторую группу входов 13 сравнения.

По заднему фронту импульса с выхода элемента И 4В триггер 19 управления устанавливается в нулевое сое- 20 тояние. Выходные коды с распределителей 4 и 6 импульсов во время выборки кодов номеров процессов для анализа подаются соответственно на эле-, менты ИЛИ-НЕ 56 и 61, которые управ25 ляют работой элементов И 38 и 50 соответственно .

Если сравниваемые коды не равны то далее распределитель 6 импульсов обеспечивает выбор кЪдов номеров за30 просов в пределах одного типа ресурса. По каждому очередному импульсу с выхода 70 блока 3 синхронизации (фиг. 4) на выходах распределителя 6 посл едовательно вырабатывается пос35 ледорательность сигналов, которые управляют работой мультиплексора 11. Этот мультиплексор осу1цествляет выбор содержимого очередного регистра блока 2.1 регистров.

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

45 процесса в регистре - н.улевой); просмотрены все коды Номеров процессов, запрашивающие данный ресурс;,а (на (k+l)-OM выходе распределителя 6 импульсов формируется положительный

50 сигнал); равны кодов номеров процес - сов.

При выполнении первого условия нулевым сигналом с инверсного выхода элемента И 50 блок элементов И 51

55 закрывается , а на прямом выходе

элемента И 50 формируется положитель ный потенциал, который поступает на входы элементов ИЛИ 57 - 60,Поэтому

по заднему фронту импульса с выхода 70 блока 3 синхронизации (фиг. 4) триггер 18 устанавливается в нулет- вое состояние.

Импульсом с выхода 69 блока 3 синхронизации распределитель 6 импульсов устанавливается в исходное состояние. По импульсу с выхода 68 блока 3 синхронизации триггеры 18 и 19 устанавливаются в единичные состояния, открывая тем самым счетные входы распределителей 6 и 7 импульсов. Таким образом производится переход к анализу запросов очередного типа ресурса.

В случае выполнения второго условия на (k+O-oM 78 выходе распределителя 6 импульсов формируется сигнал, инициирующий переход к анализу запросов очередного ресурса.При этом сигнал через элементы ИЛИ 60 и И 50 по импульсу с выхода 68 блока 3 синхронизации устанавливает триггер 19 в единичное состояние, а через элементы ИЛИ 59 и И 47 импульсом с выхода 69 блока 3 синхронизации устанавливает распределитель 6 импульсов в исходное состояние.

Очередной импульс с выхода 70 блока 3 синхронизации поступает на счетные входы распределителей 6 и 7 импульсов.

Таким образом, процесс анализа продолжается аналогично описанному.

Если во время последовательного сравнения кода номера процесса,вла- деющего единицей ресурса определенного типа, с кодами номеров процессов, хранящихся в регистрах блоков 2.1 - 2.т регистров, происходит хотя бы одно совпадение (исследуемый процесс не только владеет ресурсами но и запрашивает их), то срабатывает триггер 20 совпадения и устанавливается в единичное состояние.

По этому сигналу производится выбор содержимого очередного регистра в пределах исследуемого ресурса, т.е. очередного регистра блока 1.1 регистров (i 1, т). Кроме того, осуществляется установка в исходное состояние распределителей 6 и 7 импульсов. Если же их в результате анализа всех запросов для выбранного владельца совпадений не произошло (исследуемый процесс дополнительно не затрачивает ресурсы), т.е. триггер 20 находится в нулевом состоянии

и присутствует сигнал с последнего выхода 80 распределителя 7 импульсов, то срабатывает элемент И 40. При этом триггер 22 устанавливается в единичное состояние. Одновременно сигналом с выхода элемента И 40 открывается соответствующий элемент блока 29 элементов И, и сформированный сигнал поступает на первый управляющий вход соответствующего блока 1.1 регистров, устанавливая тем самым все регистры в нулевое состояние.

Описанные действия позволяют учесть тот факт, что если свободна

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

Через соответствующий управляющий

мультиплексор 8.1 происходит коррекция содержимого соответствующего блока 2.1 регистров.

Если все коды номеров процессов, владеющие единицами ресурса данного

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

Сигнал с выхода схемы 15 сравнения инициирует переход к анализу очередного типа ресурса с предварительной установкой в исходное состояние распределителей 4-7 импульсов. Аналогично описанному анализ продолжается до тех пор, пока не исчерпаются все tn типов ресурсов (блоки

1.1, 1 1,т), Сигнал с выхода 76 распределителя 5 импульсов поступает на элементы И 41 и 42.

Если в данном цикле анализа были удаления процессов, то сигналом с

единичного выхода триггера 22 открывается элемент И 41, сигнал с выхода которого по тактовому импульсу с выхода 69 блока 3 через соответствующие элементы И 34, 36, 47 и 49

устанавливает и распределители 4-7 импульсов в исходное состояние и инициирует начало следующего цикла анализа.

Если в очередном цикле анализа не было удалений процессов, которые могут завершиться, то срабатывает элемент И 42, сигнал с выхода которого устанавливает триггер 23 в единичное состояние. Сигнал окончания анализа с единичного выхода триггера 23 поступает на управляющий вход 84 блока 3 синхронизации и через элемент И 94 по импульсу с выхода 68 устанавливает триггер 92 режима в нулевое состояние. На этом функционирование устройства прекращается и производится идентификация состояния системы.

Сигнал с выхода триггера 23 открывает элемент И 39. Если в результате анализа все процессы в системе могут быть завершены, то все регистры блоков 1.1 - 1.т регистров установятся в нулевое состояние. Следовательно, на выходе элемента И 30 формируется низкий потенциал и элемент И 39 остается закрытым. Триггер 21 остается в нулевом состоянии. С выхода 66 устройства сигнал тупика не выдается.

В противном случае триггер 21 устанавливается в единичное состояние и с выхода 66 устройства вьщается сигнал обнаружения тупиковой ситуации в вычислительной системе.

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

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

5

0

5

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

(т+О-ый выход первого распределите- 50 ля импульсов соединен с первьп«1И входами четвертого и пятого элементов И, выход которого соединен с единичным входом триггера анализа,прямой выход первого элемента И соеди- 55 нен с вторым входом первого элемента ИЛИ, выход шестого элемента И соединен с синхровходом первого распределителя импульсов и нулевым вхо0

17

дом второго триггера управления.единичный выход которого соединен с первым входом шестого элемента Ир выход седьмого элемента И, соединен с синхровходом второго распределителя импульсов, га-выходов которого соединены с соответствующим управляющим входом второго информационного мультиплексора, (iD+1)-ft выход второго распределителя импульсов соединен с вторым входом второго элемента И, выход первого элемента ИЛИ-НЕ соединен с (t-H)-M инверсным входом первого элемента И (где t - разрядность кода, указывающего на номер процесса функционирующего в системе), прямой и инверсный вькоды первого триггера управления соединены с вторыми входами соответственно четвертого и пятого элементов И, выход третьего элемента И соединен с единичным входом триггера тупика, прямой выход которого является выходом признака тупика устройства, отличающееся тем, что, с целью повышения быстродействия, в устройство введены (2т-2) блоков регистров, блок синхронизации, третий и четвертый распределители импульсов,(2т-2) управляющих мультиплексоров, регистр единиц ресурсов, шифратор, вторая схема сравнения, третий,четвертый и пятый триггеры управления, (2in-1) блоков элементов И, коммутатор, четырнадцать элементов И, семь элементов ИЛИ и второй элемент ИЛИ-НЕ, причем группы выходов блоков регистров с третьего по (т+1)-ый соединены с второй группой входов первого информационного мультиплексора и с информационными входами соответствующих управляющих мультиплексоров с третьего по (п1+1)-ый группы выходов блоков регистров с (m+2)-ro по 2тп-ый соединены с второй группой информационных входов второго информационного мультиплексора и с группами информационных входов соответственно с (т+2)-го по 2га-ый управляющих мультиплексоров,выходы которых соединены с первыми входами начальной установки с третьего по (т+О-ый блоков регистров,первые выходы управляющих мультиплексоров с третьего по (т+1)-ый соединены с входами начальной установки с ()- го по 2т-ый блоков регистров,вторые выходы управляющих мультиплексоров

9705118

с первого по (т+1)-ый соединены с соответствующими входами восьмого элемента И, инверсный выход которого соединен с вторым входом третьего

5 элемента И, вход пуска устройства соединен с входом запуска блока синхронизации, с первым входом второго элемента ИЛИ, с нулевыми входами триггеров тупика и анализа, первый

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

1-5 синхронизации соединен с первыми

входами девятого, десятого, одиннадцатого и тринадцатого элементов И, третий выход блока синхронизации соединен с первыми входами четырнад20 цатого, пятнадцатого, шестнадцатого и семнадцатого элементов И, четвертый выход блока синхронизации соединен с вторым входом шестого и девятнадцатого элементов И, выход

25 седьмого элемента И соединен с входом установки в О третьего триггера управления, прямой выход которого соединен с вторым входом седьмого элемента И, группа выходов третьего

30 распределителя импульсов соединена с тактовыми входами первого информационного мультиплексора, с входами первого элемента ИЛИ-НЕ и входами шифратора, выход которого соединен

35 с первым входом второй схемы сравнения, первый выход первого распределителя импульсо.в соединен с вторым входом тринадцатого элемента И,выход которого соединен с нулевым входом

40 первого триггера управления, группа тактовых выходов четвертого распределителя импульсов соединена с второй группой тактовых входов второго информационного мультиплексора и дами второго элемента ИЛИ-НЕ,выход которого соединен с инверсным входом двадцатого элемента И, выход четвертого распределителя импульсов соединен с первыми входами третьего и

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

191

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

20

5

0

5

совпадения соединен с вторым входом восьмого элемента ИЛИ, выход второго элемента И соединен с третьим входом восьмого элемента ИЛИ,выход четвертого элемента И соединен с вторым входом седьмого элемента ИЛИ и вторым входом пятнадцатого элемента И, выход которого соединен с входом останова первого распределителя импульсов, инверсный выход первого элемента И соединен с вторым входом пятого элемента ИЛИ и третьим входом четвертого элемента ИЛИ, четвертый выход блока синхронизации соединен с вторым входом -двадцать первого элемента И,вь1ход которого соединен с нулевым входом пятого триггера управления, выход первого элемента ИЛИ соединен с вторым входом десятого элемента И, выход которого соединен с единичным входом второго триггера управления, выход четырнадцатого элемента И соединен с входом начальной установки третьего распределителя импульсов, выходы девятнадцатого, щестнадцатого и семнадцатого элементов И соединены соответственно с тактовым входом четвертого распределителя импульсов, с входом начальной установки четвер- то1о распределителя импульсов и входом начальной установки второго распределителя импульсов, группа выходов первого распределителя импульсов соединена с управляющими входами коммутатора, единичный выход триггера анализа соединен с входом останова блока синхронизации,выходы блоков элементов И г третьего по Zm-bu соединены с информационными входами соответствующих блоков регистров, входы кодов номеров процессов,владеющих ресурсами устройства, соединены с первой группой входов блоков элементов И, начиная с третьего по (т+2)-й,входы кодов номеров процессов затрачивающих ресурсы устройства соединены с первой группой входов блоков элементов И,начиная с(т+3)-го по 0 2т-й,первый выход блока синхронизации соединен с вторыми входами блоков элементов И, начиная с 3-го по 2т-й.

0

5

0

5

N- .TrXV-f.jiX

I От i

a.V

i

(76,79,86)

От элепента ,m,49 фиг.5

ФигМ

I 7/z

iz.t

игЛ

Iff/Wl

1

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

9ZfnlK.m)

75тП9п1( о

гп

n

n

гт

n

л

Фиг.9