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

 

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

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

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

РЕСПУБЛИК (19) (11) А1 (5D 4 G 06 F 11/00

/ Д

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ (21) 3965505/24-24 (22) 16.10.85 (46) 15.03.87. Бюл. Р 10 (72) Б.М.Конорев, А.В.Бек, М,А.Чернышев, Г.Н.Тимонькин, С.Н.Ткаченко, В.С.Харченко и В.В.Герасименко (53) 681.3(088.8) .(56) International Jornal Systems

science, 1979 ч.10, Р 5, р. 477-483, Fig 3.

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

У 1015385, кл. G 06 F 11/00, 1983. (54) .УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к вычислительной технике и может быть использовано в современных параллельных вычислительных системах для обнаружения тупиковых ситуаций. Цель изобретения — повышение быстродействия. Сущность изобретения состоит в том, что новая совокупность конструктивных признаков позволяет повысить оперативность контроля путем сокращения числа необходимых для обнаружения тупика рабочих циклов, а также реализации возможности контроля систем с ресурсами, емкость которых более единицы. При этом конструкция устройства позволяет регистрировать и хранить для каждого ресурч са множество кодов номеров процессов (по числу единиц ресурса каждого ти". па), владеющих ресурсом, а также множество кодов номеров процессов, запрашивающих ресурс. 9 ил.

1 12

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

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

На фиг. 1 представлена функцио- нальная схема предлагаемого устройства для контроля распределения ресурсов; на фиг. 2 — функциональная схема блока 1.i регистров; на фиг. 3 функциональная схема блока 2.i регистров; на фиг. 4, — функциональная схема блока синхронизации; на фиг. 5— функциональная схема распределителя импульсов; на фиг. б — функциональная схема управляющего иультинлексо" ра 8.i; на фиг. 7 — функциональная схема управляющего мультиплексора

9.i на фиг. 8 — функциональная схема информационного мультиплексора; на фиг. 9 — временные диаграимы функционирования устройства.

Устройство для контроля распределения ресурсов (фиг. 1) содержит первый (1.1) — (m+1)-ый (1.m) блоки регистров, второй (2.1) — 2.m-ый (2.m) блоки регистров, блок 3 синхронизации, третий распределитель 4 импульсов, первый распределитель 5 импульсов, четвертый распределитель 6 импульсов, второй распределитель 7 импульсов, первый (8.1) — (m+1)-й (8.m) управляющие мультиплексоры„ второй 9.1 — 2.m-й 9.m управляющие мультиплексоры, первый информационный мультиплексор 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, rpe n — максимально возможное число единиц ресурса данного типа, а k— число запросов к ресурсу данного типа, коммутатор 28, блок 29 элементов

И, восьмой 30, девятый 31, десятый

32, восемнадцатый 33, четырнадцатый

34, шестой 35, пятнадцатый 36, тринадцатый 37, первый 38, третий 39, второй 40, четвертый 41, пятый 42, 97051 2 одиннадцатый 43, двадцатый 44, двенадцатый 45„ девятнадцатый 46, шест надцатый 47, седьмой 48, семнадцатый 49, двадцатый 50 элементы И,блок

51 элементов И, седьмой 52, восьиой

53, второй 54, первый 55, элемент

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

10 62 устройства, первую группу 63 и вторую 64 информационных входов устройства, третью группу 65 информационных входов устройства, выход 66 устройства.

На фиг, 4 приняты обозначения: первый 67,второй 68,третий 69 и четвертый 70 выходы блока 3 синхрониза- ции.Кроме того на чертежах приняты обозначения . выходы 71. 1 — 71.m и 72 ..172.m мультиплексоров 8.1 — 8.п,выходы 73.1 — 73.m мультиплексоров

9.1 — 9.m, группа выходов 74.1

74.п распределителя импульсов 4, 25 группа выходов 75.1 — 75.тп распределителя импульсов 5, выход 76 распределителя 5, группа выходов 77.1

77.k распределителя 6, выход 78 распределителя б,группа выходов 79.1 79.m распределителя б,группа выходов

79,1 — 79.m распределителя импульсов

7, выход 80 распределителя импульсов

7, выходы 81„1 — 81.m блока элементов И 29, информационные выходы

82.1 — 82.m регистров 1.1 — 1.m èí35 формационные выходы регистров 83.1

83.m регистров 2. 1 — 2.m вход 84 останова блока 3 синхронизации;

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

40 ИЛИ 86, первую (87. 1) - n-ю (87.n) группы информационных входов, первый

81,i и второй 73.i управляющие входы, группу 82.i выходов, состоящую из первой (88. 1) - n-ой (88.n) групп

45 выходов соответственно первого (85.1) — n-ro (85.n) регистров.

Блок 2.i регистров (фиг. 3) содержит регистры 89.1 — 89.k первую

90.1 k-ю 90.k группы информационных

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

89.k регистров.

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

f5

-50

3 12 управляющий вход 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 ° i (фиг ° 6) содержит блок 99 элементов

И, элемент И 100, элемент ИЛИ 101.

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

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

108 элементов ИЛИ.

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

i-oe поле в момент запуска системы с группы 65 входов заносится код максимального количества единиц i-го типа ресурса.

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

16 — 19 управления предназначены для управления работой распределителей

4 — 7 импульсов соответственно.Триг97051 4

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

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

23 анализа предназначен для фиксации сигнала окончания анализа. . Группы (24.1 — 24.n) — (25.1

25.n) блоков элементов И предназначен для одновременной передачи информации о кодах номеров процессов, владеющих ресурсами, с входа 63 устройства в регистры блоков 1.1 — 1.m регистров, Группы (26. 1 — 26.k) (27.1 — 27,k) блоков элементов И

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

2.1 — 2.m регистров.

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

1.1 — 1.тп регистров.

Элемент И 30 предназначен для формирования сигнала-идентификатора нулевого состояния регистров 1. 1

1.m. Элементы И 31 — 36,43 — 49 предназначены для синхронизации работы элементов устройства, Элемент И 37 предназначен для формирования сигнала установки в нулевое состояние триггера 22 управления ° Элемент И 38 (50) предназначен для формирования сигнала разрешения выбора следующе.го кода номера процесса, владеющего (запрашивающего) как m-либо ресурсом системы. Элемент И 39 предназначен для формирования сигнала тупика. Элемент И 40 предназначен для формирования сигнала-признака того, что при анализе были удаления прЬцессов. Элемент И 41 предназначен для формирования сигнала разрешения нового цикла анализа. Элемент И 42 предназначен для формирования сигна1297051 ла установки в единичное состояние триггера 23 анализа. Блок 51 элементов И предназначен для одновременной передачи кода с выхода мультиплексора 11 на вторую группу входов схемы 13 сравнения.

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

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

57 — 60 предназначены для формирования сигналов разрешения выбора кодов номеров процессов, запрашивающих ресурсы.

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

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

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

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

86 предназначен для формирования сигнала установки в нуль регистров

86.1 — 86.п. Группа 87.j информационных входов предназначена для приема в регистр 85.j-ro кода номера процесса, владеющего единицами ресурса

i-ro типа.

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

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

f0

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

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

Триггер 92 режима предназначен для формирования сигнала запуска генератора 93. Генератор 93 предназначен для формирования трех последовательностей импульсов на выходах

67 — 70 (фиг. 9) блока 3. Элемент

И 94 предназначен для формирования сигнала установки в ноль триггера 92 режима. Вход 62 пуска предназначен для приема сигнала пуска устройства.

Вход 84 предназначен для приема сигнала окончания анализа. Выход 67 предназначен для выдачи сигнала управления работой управляющих мультиплексоров 8.1 - 8.m, 9.1 — 9.m a также для управления приемом информации в регистры всех блоков.

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

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

Счетный вход 97 предназначен для приема импульсов на одноименный вход счетчика 97. Вход 98 установки предназначен для приема сигнала установки в ноль счетчика 95. Группа выходов 74.1 — 74.п (75.1 — 75.m; 76;

77.1 — 77.k; 78; 79.1 — 79.m, 80) предназначена для выдачи распределенных во времени импульсов.

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

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

Элемент ИЛИ 101 предназначен для формирования сигнала управления работой блока 2.i регистров. Группа

82.i информационных входов предназначена для приема кодов номеров процессов, владеющих единицами ресурса i-го типа с целью дальнейшего анализа. Вход 68 предназначен для 10 приема сигнала разрешения работы мультиплексора. Выходы 71.i и 72.i предназначены для выдачи сигналов управления.

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

Элемент 102.j предназначен для формирования признака отсутствия запроса на j-ю единицу i-ro ресурса. 20

; Элемент 103 предназначен для формирования сигнала установки в нуль регистров соответствующег блока 1.д регистров. Группа 83.i информационных входов предназначена для приема кодов номеров процессов, запрашивающих i-й ресурс. Вход 68 предназначен для приема сигнала разрешения работы мультиплексора. Выход 73.i предназначен для управления раба- 30 той соответствующего блока 1.i регистров.

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

Блоки 104 (1OS) — 106 (107) элементов И соответственно первой ш-ой групп предназначены для выбора кодов номеров процессов, владеющих (запрашивающих) соответствующими единицами ресурсов различных типов.

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

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

В тупиковую ситуацию могут быть вовлечены только те процессы, которые владеют какими-либо ресурсами и дополнительно их запрашивают.В свою очередь, в тупик могут быть вовлечены только те ресурсы, которыми процессы владеют (все единицы ресурса заняты) и на них есть запросы от других процессов (хотя бы один запрос). Ресурсы, на которые нет занросов, либо свободна хотя бы одна единица ресурса из дальнейшего анализа удаляются, так как в анализируемый момент времени t они в тупик вовлечены не будут. Удаление (обнуление соответствующего блока 1.i 2.i регистров) производится по сигналам с выходов управляющих мультиплексоров 8.i и 9.i (i = 1,ш).

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

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

Тогда, если в результате анализа владельца единицы ресурса определенного типа по просителям всех типов ресурсов не обнаружено искомого кода, то данный процесс из дальнейшего анализа необходимо удалять. Следовательно, ресурс, единицей которого владел .анализируемый процесс, в тупик также вовлечен не будет. Поэтому производится обнуление соответствующего блока 1.i регистров и с помощью управляющего мультиплексора 8.i блока

2.i регистров. Кроме того, триггером 22 фиксируется факт удаления" процесса в цикле анализа.

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

9 129

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

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

Синхронизации разрешает прием информации через блоки 24 — 27 элементов И о состоянии распределения ресурсов системы и запросов на них в регистры соответствующих блоков 1.i и 2.i регистров (i 1,ш, где m— число типов ресурсов в системе).

Этим же сигналом управляющие мультиплексоры И.i и 9.i (i 1,m) закрыты. Взаимная установка в нулевое состояние регистров соответствующих блоков 1.i и 2.i регистров (i

1,г) запрещена °

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

Нулевым сигналом с выхода 67 блокируется прием информации в регистры блоков 1.1 и 2. регистров и откры1 ваются мультиплексоры 8. и 9„i, Если хотя бы один регистр блока

1.i регистров содержит нулевой код (соответствующая единица ресурса

i-го типа свободна), то на выходе

72.i управляющего мультиплексора

8.i формируется единичный сигнал, который является сигналом установки в нуль всех регистров блока 2.i регистров. Кроме того, единичный сиг7051 10 нал ц армируется на выходе 73.j муль» типлексора 9.j для которого все регистры соответствующего блока

2.j регистров имеют нулевые коды„

Зтот сигнал является сигналом установки в нуль регистров блока 1.j регистров.

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

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

Одновременно сигнал пуска с входа

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

16 и первый 17 триггеры управления при этом устанавливаются в единичное состояние. Сигналы с единичных

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

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

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

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

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

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

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

15

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

Если же, выбранный код процесса не нулевой, то на инверсном выходе элемента И 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 формируется положитель297051 12 ный сигнал, который инициирует выбор очередного запроса ресурса того же типа.

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

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

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

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

Если сравниваемые коды не равны, то далее распределитель 6 импульсов обеспечивает выбор кодов номеров sa30 просов в пределах одного типа ресурса. По каждому очередному импульсу с выхода 70 блока 3 синхронизации (фиг. 4) на выходах распределителя

6 последовательно вырабатывается пос35 ледовательность сигналов, которые управляют работой мультиплексора 11.

Этот мультиплексор осуществляет выбор содержимого очередного регистра блока 2.1 регистров.

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

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

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

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

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

97051

13 12 по заднему фронту импульса с выхода

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

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

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

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

Если во время последовательного сравнения кода номера процесса,вла- . деющего единицей ресурса определенного типа, с кодами номеров процессов, хранящихся в регистрах блоков

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

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

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

1,i регистров, устанавливая тем самым все регистры в нулевое состояние.

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

Через соответствующий управляющий мультиплексор 8.i происходит коррекция содержимого соответствующего блока 2.i регистров.

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

Сигнал с выхода схемы 15 сравнения инициирует переход к анализу очередного типа ресурса с предварительной установкой в исходное состояние распределителей 4 — 7 импульсов.

Аналогично описанному анализ продолжается до тех пор, пока не исчерпаются все m типов ресурсов (блоки

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

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

1297051

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

3 синхронизации и через элемент И

94 по импульсу с выхода 68 устанавливает триггер 92 режима в нулевое состояние. На этом функционирование устройства прекращается и производится идентификация состояния системы.

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

21 остается в нулевом состоянии. С выхода 66 устройства сигнал тупика не выдается.

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

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

Устройство для контроля распределения ресурсов, содержащее первый и второй блоки регистров, первый и второй распределители импульсов,первый и второй управляющие мультиплексоры, первый и второй информацион— ные мультиплексоры, первую схему сравнения, первый и второй триггеры управления, триггер совпадения,триг—

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

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

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

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

35 ИЛИ и с нулевыми входами триггеров тупика и анализа, выход которого соединен с первым входом третьего элемента И, выход второго элемента И соединен с е иничным входом первого триггера управления и первой группой входов третьего блока элементов И, первые m выходов первого распределителя импульсов (где m —число типов ресурсов в системе) сое 15 динен с второй группой входов третьего блока элементов И, с соответствующими управляющими входами первого информационного мультиплексора, (тп+1)-ый выход первого распределите50 ля импульсов соединен с первыми входами четвертого и пятого элементов И, выход которого соединен с единичным входом триггера анализа,прямой выход первого элемента И соединен с вторым входом первого элемента ИЛИ, выход шестого элемента И соединен с синхровходом первого распределителя импульсов и нулевым вхо1? 129 дом второго триггера управления, единичный выход которого соединен с первым входом шестого элемента И,выход седьмого элемента И, соединен с синхровходом второго распределителя импульсов, тп-выходов которого соединены с соответствующим управляющим входом второго информационного мультиплексора, (m+1)-й выход второго распределителя импульсов соединен с вторым входом второго элемента И, выход первого элемента ИЛИ-НЕ соединен с (1+1)-м инверсным входом первого элемента И (где 1 — разрядность кода, указывающего на номер процесса функционирующего в системе), прямой и инверсный выходы первого триггера управления соединены с вторыми входами соответственно четвертого и пя того элементов И, выход третьего элемента И соединен с единичным входом триггера тупика, прямой выход которого является выходом признака тупика устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, в устройство введены (2ш-2) блоков регистров, блок синхронизации, третий и четвертый распределители импульсов,(2m-2) управляющих мультиплексоров, регистр единиц ресурсов, шифратор, вторая схема сравнения, третий, четвертый и пятый триггеры управления, (2m-1) блоков элементов И, коммутатор, четырнадцать элементов И, семь элементов ИЛИ и второй элемент ИЛИ-НЕ, причем группы выходов блоков регистров с третьего по (m+1)-ый соединены с второй группой входов первого информационного мультиплексора и с информационными входами соответствующих управляющих мультиплексоров с третьего по (m+1)-ый группы выходов блоков регистров с (m+2)-ro по 2m-ый соединены с второй группой информационных входов второго информационного мультиплексора и с группами информационных входов соответственно с (m+2)-ro по 2m-ый управляющих мультиплексоров, выходы которых соединены с первыми входами начальной установки с третьего по (m+1)-ый блоков регистров, первые выходы управляющих мультиплексоров с третьего по (ш+1)-ый соединены с входами начальной установки с (ш+2)го по 2m-ый блоков регистров, вторые выходы управляющих мультиплексоров

7051 18 с первого по (m+1) — ûé соединены с соответствующими входами восьмого элемента И, инверсный выход которого соединен с вторым входом третьего элемента И, вход пуска устройства соединен с входом запуска блока синхронизации, с первым входом второго элемента ИЛИ, с нулевыми входами триггеров тупика и анализа, первый 10 выход блока синхронизации соединен с управляющими входами всех управляющих мультиплексоров, с вторыми входами первого и второго блоков элементов И, второй выход блока синхронизации соединен с первыми входами девятого, десятого, одиннадцатого и тринадцатого элементов И„ третий выход блока синхронизации соединен с первыми входами четырнад20 цатого, пятнадцатого, шестнадцатого и семнадцатого элементов И, четвертый выход блока синхронизации соединен с вторым входом шестого и девятнадцатого элементов И, выход седьмого элемента И соединен с входом установки в "О" третьего триггера управления, прямой выход которого соединен с вторым входом седьмого элемента И, группа выходов третьего

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

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

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

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

1297051 20

50 динен с вторыми входами третьего и четвертого элементов ИЛИ, с первыми входами пятого и шестого элементов

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

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

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

40 совпадения соединен с вторым входоМ восьмого элемента ИЛИ, выход второго элемента И соединен с третьим входом восьмого элемента ИЛИ,выход четвертого элемента И соединен с вторым входом седьмого элемента ИЛИ и вторым входом пятнадцатого элемента И, выход которого соединен с входом останова первого распределителя импульсов, инверсный выход первого элемента И соединен с вторым входом пятого элемента ИЛИ и третьим входом четвертого элемента ИЛИ, четвертый выход блока синхронизации соединен с вторым входом двадцать первого элемента И,выход которого соединен с нулевым входом пятого триггера управления, выход первого элемента ИЛИ соединен с вторым входом десятого элемента И, выход которого соединен с единичным входом второго триггера управления, выход четырнадцатого элемента И соединен с входом начальной установки третьего распределителя импульсов, выходы девятнадцатого, щестнадцатого и семнадцатого элементов И соединены соответственно с тактовым входом четвертого распределителя импульсов, с входом начальной установки четвертог о распределителя импульсов и входом начальной установки второго распределителя импульсов, группа выходов первого распределителя импульсов соединена с управляющими входами коммутатора, единичный выход тригге" ра анализа соединен с входом останова блока синхронизации, выходы блоков элементов И . третьего по 2ш-ый соединены с информационными входами соответствующих блоков регистров, входы кодов номеров процессов, владеющих ресурсами устройства, соединены с первой группой входов блоков элементов И, начиная с третьего по (m+2)-é,íõîäû кодов номеров процессов затрачивающих ресурсы устройства .соединены с первой группой входов блоков элементов И,начиная.c(m+3)-го по

2m-й,первый выход блока синхронизации соединен с вторыми входами блоков элементов И, начиная с 3 — го по 2m-й.

1297051

1297051 бтра

МЦ йо блан

ИтР7

Г) д

Яп Йпнщ-р—

za>!as ) i

gm

Йома

2Ф п (Ы n/

И.i

1. s (l, f- -I m) 70

N бд б7

1297051

1297051

Составитель И.Сигалов

Редактор Т.Парфенова Техред М.Коданич . Корректор. Г.Решетник .

Заказ 782/52 Тираж 673 Подписное

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

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

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