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

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

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

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

Устройство для контроля распределения ресурсов содержит (фиг. 1 и 2) регистры 1.1 - 1.П (п - число типов ресурсов системы), трип ер 2 режима, генератор 3 импульсов, триггер 4 управления, коммутаторы 5.1-5.П первой группы 5, ко.ммутаторы 6.1 - б.п второй группы 6, элементы И 7.1-7.п группы 7, нервый 8 и второй 9 элеме1ггы И, 6;ioK 10 элементов И и элемент ИЛИ 11, составляюшие каждый коммутатор групп 5 и 6, информационные входы 12.1 --12.п, вход 13 запуска, выходы 14.1 -14.п признака тупиковой ситуации, выходы 15.1 - 15.п поразрядных конъюнкций, коммутатор первой грунпы 5.

Регистры 1.1-1.П предназначены для приема, хранения и выдачи информации о состоянии распределения ресурсов. Поскольку процесс, владеюп1,ий ресурсом R;., пе может повторно его запрашивать, k-й разряд каждого регист)а .k не используется. В остальные разряды fe-ro регистра .k информация записывается следующим образом. Если k-M ресурсом владеет какой-либо процесс (процессы), который, кроме этого, запрашивает другой ресурс, например R, (или несколько ресурсов одновременно), то в j-й разряд k-ro регистра l.k записывается единица, а в остальные - нули. Если k-м ресурсом владеет один или несколько процессов и этот нроцесс (процессы) дополнительно никакие другие ресурсы не запрашивают, то во все разряды k-ro регистра .k записываются нули.

Процессы, только запрашивающие какие-либо ресурсы, также не запоминаются в регистрах l.i.

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

Функционирование устройства рассмотрим на примере процесса контроля раснре- делеиия ресурсов в системе (фиг. 4).

В каждом состоянии все регистры 1.1 - 1.п находятся в нулевом состоянии (входы установки в «О не показаны).

По сигналу пуска с входа 13 триггер 2 режима устанавливается в единичное состояние, а триггер 4 управления после повторного запуска - в нулевое (фиг. 3). Высоким потенциалом с единичного выхода

5

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

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

В соответствии с графом распределения ресурсов (фиг. 4) в четвертые разря- 5 ДЫ первого регистра 1.1 и второго регистра 1.2, в первый разряд третьего регистра 1.3, третий разряд четвертого регистра 1.,4, второй, третий и восьмой разряды соответственно регистров 1.5-1.7 записываются единицы. Во все разряды регист- 0 ра 1.8 и в остальные разряды регистров 1.1 -1.7 записываются нули.

По заднему фронту первого импульса триггер 4 управления устанавливается в единичное состояние (фиг. 3). Элемент И9 закрывается низким потенциалом с пулевого выхода этого триггера, а высокий потенциал с единичного выхода подается на вход элемента ИВ. Поэтому второй и.мпульс с выхода генератора 3 импульсов открывает его. Сиг- на.л, сформированный на выходе элемента Q ИВ, поступает на входы блокировки всех ко.м мутаторов.

Во всех коммутаторах первой 5 и второй 6 групп коммутаторов срабатывают элементы ИЛИ. После этого на выходах всех коммутаторов обеих групп формируются высо- г кие потенциалы, и через открытые элементы И 7.1-7.П (для примера 7.1-7.8) сигналы поступают на вторые информационные входы всех коммутаторов первой 5 и второй 6 групп.

После этого на вторых инфсрмацион- 0 пых входах всех комму аторов обеих групп 5 и 6 присутствует высокий потенциал.

Срабатывают те эле.менты блока 10 элементов И всех ком.мутаторов первой группы, па соответствующих информационных вхо- , дах которых присутствуют высокие потенциалы с выходов соответствующих разрядов регистров 1.1--1.П.

В данном случае такими элементами являются третьи элементы И блоков 10 элементов И нервого 1.1 и второго 1.2 регист- Q ров, первый третий и седьмой, второй третий и седьмой э.лементы И блоков 10 элементов И соответственно регистров 1.3-1.7.

С возбужденных выходов этнх элементов высокие потенциалы поступают на соответствующие информационные входы соответ- 5 ствующнх коммутаторов второй группы 6. а также на входы элементов ИЛИ 1 I, высокие потенциа.чы с выходов которых поступают на входы соответствуюп1их элементов И 7.к.

Так, после срабатывания соответствующих элементов И блоков 10 элементов И возбужденными разрядами группы выходов первого 1.1 и второго 1.2 регистров являются разряды соответственно 15.1.4 и 15.2.4, с третьего 1.3 по седьмой 1.7 - соответственно разряды 15.3.1, 15.4.3 и 15.4.7, 15.5.2, 15.6.3, 15,7.8, единичные потенциалы которых поступают на соответствующие информационные входы соответствующих коммутаторов 6.1-6.8, исключая 6.5 и 6.6. На все информационные входы этих коммутаторов подаются нулевые потенциалы.

Далее срабатывают соответствующие элементы И коммутаторов 6.1, 6.4, 6.7, 6.8. Сигналы с возбужденных элементов И селектируются элементами ИЛИ 11 в каждом коммутаторе и с выходов коммутаторов поступают на вторые входы элементов И 7.1 - 7.8. На этом процесс анализа заканчивается.

Длительность сигнала на выходе элемента И8 должна быть немногим больше длительности переходного процесса в устройстве.

Как только на выходе элемента И8 поя- явится нулевой потенциал на выходах коммутаторов 5.8, 6.5 и 6. 6 также формируются низкие потенциалы, которые запирают элементы И 7.8, 7.5 и 7.6 соответственно. Значит и на выходах 14.8, 14.5, и 14.6 присутствуют нулевые потенциалы.

Появление нулевых сигналов на выходах 14.5 и 14.8 вызывает в свою очередь появление нулевых сигналов на выходах коммутаторов 6.2 и 5.7 соответственно. Элементы И7.2 и 7.7 закрываются, формируя на своих выходах нулевые потенциалы, которые поступают на выходы 14.2 и 14.7 соответственно. Остальные разряды группы выходных шин остаются в возбужденном сое- стоянии. Следовательно, ресурсы, номера которых соответствуют номерам возбужденных разрядов группы выходов устройства, находятся в тупике. Для рассматриваемого примера это ресурсы R1, R3 и R4.

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

По заднему фронту импульса с выхода элемента И8 триггер 2 режима устанавливается в нулевое состояние и низким по0

0

5

0

5

0

5

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

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

Устройство для контроля распределения ресурсов в вычислительной системе, содержащее п регистров, где п - число типов ресурсов системы, первую группу из п коммутаторов, информационный вход /С-го регистра К ,...,п, является /(-м информационным входом устройства, выход К-го регистра подключен к первому информационному входу /С-го коммутатора первой группы, отличающееся тем, что, с целью повышения надежности за счет выявления ресурсов, которые непосредственно вовлечены в тупик, в него введены вторая группа из п коммутаторов, триггер режима, триггер управления, генератор импульсов, два элемента И и группа из п. элементов И, первый и второй входы К.-ГО элемента И группы подключены к выходам К-У- коммутаторов первой и второй группы соответственно, выход /(-го элемента И группы является К.-м выходом признака тупиковой ситуации устройства и соединен с входами соответствующих разрядов вторых информационных входов р-х коммутаторов (р К, р 1, п) первой и второй групп, разряды выхода поразрядных конъюнкций /С-го коммутатора первой группы подключены к соответствующим разрядам первого информационного входа р-х коммутаторов второй группы, вход установки триггера управления является входом пуска устройства и соединен с входом сброса триггера режима, прямой и инверсный выходы которого подключены к первым входам первого и второго элементов И, выход первого элемента И соединен с входами синхронизации и разрешения установки в «О триггера управления и входами блокировки всех коммутаторов первой и второй групп, выход второго элемента И соединен с входами синхронизации всех регистров, выход триггера управления подключен к входу запуска генератора импульсов, выход которого соединен с вторыми входами первого и второго элементов И и с входами синхронизации разрешения установки в «1 триггера режима.

KOMMyina.-nop

6.1

12.f

L

Вг

.e ж

5.2я 5.2(n-/j

/5 7л

6.2

7Z.2

h

52

1/577

jz J Ui

L Г

1.2

п-1

/572

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных вычислительных системах для оперативного контроля корректности распределения ресурсов. Устройство позволяет повысить надежность за счет выявления ресурсов, которые непосредственно вовлечены в тупик. Устройство содержит п регистров (п - число типов ресурсов системы), триггер режима, генератор импульсов, триггер управления, коммутаторы первой и. второй групп, группу элементов И, два элемента И. Из множества ресурсов, определяемых как тупиковые, одна часть находится в действительном тупике, в то время как другая часть находится в кажущемся тупике, т.е. от владеющих ими процессов имеются запросы на действительное тупиковое подмножество ресурсов. В устройстве производится выделение только последнего подмножества, что позволяет исключать только действительный тупиковый процесс. 3 ил. (О оо 1чЭ СГ1 ОО оо

13

S.in-l) 1

--yj

./

H

fi/i

75/7.2

Щп-J)

IZ/i

t

I(n-l)

V

IFJTI /I

In

Л-)

JMH. nIS. г.. I

ni

.2

.M}

.n

Фиг. 2

Сигнал пуска

Bb/)iod mpuzepQ.2

db/xoff , генератор1&

Выход mpusepat

Bbiinod элемента U9

элемента ив

i

т

i

t

t

t

Фиг.З

Фиэ.