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

11297061

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

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

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

Устройство для контроля распределения ресурсов содержит (фиг. 1) группу регистров 1 и регистр 2, триггер 3 режима, генератор 4 тактовых

10

t5

Элемент задержки 6 предназначен для формирования импульсов, задержанных на время ч , установки в нуль второго триггера 7 управления. Время задержки Т определяется суммарным временем задержки на срабатывание п кdм fyтaтopoв.

Второй триггер 7 управления предназначен для формирования сигнала, управляющего работой коммутаторов всех групп коммутаторов, а также первого 9 и второго 10 элементов И.

Каждый i-ый коммутатор S.j.i j-ой группы (itj) предназначен для формирования сигнала обнаружения взаимодействия j-ro русурса с i-ым. Коммутатор 8.1.1 каждой 1-ой группы коммутаторов предназначен для формирования сигнала, указьшающего на

импульсов, первый триггер 5, управле- 20 факт вовлеченности 1-го ресурса в НИН, элемент задержки 6, второй триг- тупик, гер 7 управления, первую 8,. 1-8.п группы коммутаторов, каждая из которых содержит по п коммутаторов, где п - количество контролируемых ресурсов, первый 9, второй 10, третий 11 и четвертый 12 элементы И, элемент ИЛИ 13, группу 14 входов распределения ресурсов устройства, вход 15 пуска, выход 16, .(первый 17.1.1-17.1.1.

25

30

.п) - (первый 17.п.1-17.п.п) выходов соответственно первой - п-ой групп выходов первого регистра I.

Первый регистр 1 предназначен для приема, хранения и вьздачи информации 35 о состоянии распределения ресурсов вычислительной системы. Причем каждому 1-ому ресурсу в регистре I соответствует 1-я группа входов (выхоПервый элемент И 9 предназначен для управления работой триггера 3 режима. Второй элемент И 10 предназначен для формирования сигнала, управляющего работой триггера 5 управления. Третий элемент И 11 предназначен для формирования сигнала управления работой элемента задержки 6 и второго триггера 7 управления. Четвертый элемент И I2 предназначен для формирования сигнала разрешения приема информации в регистр 1 о распределении ресурсов.

Элемент ИЛИ 13 предназначен для формирования сигнала-признака тупиковой ситуации. Группа 14 информационных входов предназначена для приема информации о распределении ресурсов

дов). Если 1-ым ресурсом владеет k-ый вычислительной системе. Вход 15 процесс, который еще запрашивает и пуска предназначен для приема сигна- j-ый ресурс, то при приемке информа- ла, инициирующего начало работы уст- ции в регистр 1 в о-ый разряд 1-ой ройства. Выход 16 устройства предназ

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

Второй регистр 2 предназначен для фиксации номеров ресурсов, вовлеченных в тупик. Триггер 3 режима предназначен для приема сигнала пуска устройства и формирования сигнала запуска генератора 4 импульсов. Генератор 4 импульсов предназначен для формирования последовательности импульсов, (фиг. 2). Триггер 5 управления предназначен для формирования сигналов управления работой устройства.

0

5

Элемент задержки 6 предназначен для формирования импульсов, задержанных на время ч , установки в нуль второго триггера 7 управления. Время задержки Т определяется суммарным временем задержки на срабатывание п кdм fyтaтopoв.

Второй триггер 7 управления предназначен для формирования сигнала, управляющего работой коммутаторов всех групп коммутаторов, а также первого 9 и второго 10 элементов И.

Каждый i-ый коммутатор S.j.i j-ой группы (itj) предназначен для формирования сигнала обнаружения взаимодействия j-ro русурса с i-ым. Коммутатор 8.1.1 каждой 1-ой группы коммутаторов предназначен для формирования сигнала, указьшающего на

0 факт вовлеченности 1-го ресурса в тупик,

0 факт вовлеченности 1-го ресурса в тупик,

5

0

35

Первый элемент И 9 предназначен для управления работой триггера 3 режима. Второй элемент И 10 предназначен для формирования сигнала, управляющего работой триггера 5 управления. Третий элемент И 11 предназначен для формирования сигнала управления работой элемента задержки 6 и второго триггера 7 управления. Четвертый элемент И I2 предназначен для формирования сигнала разрешения приема информации в регистр 1 о распределении ресурсов.

Элемент ИЛИ 13 предназначен для формирования сигнала-признака тупиковой ситуации. Группа 14 информационных входов предназначена для приема информации о распределении ресурсов

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

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

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

В исходном состоянии все элементы памяти находятся в нулевом состоя- НИИ (входы установки не показаны).

По сигналу пуска, поступающему на вход 15 пуска устройства, открьшает- ся элемент И 9 и положительным потенциалом с его выхода триг.гер 3 ре

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

Первый импульс с выхода генератора 4 импульсов через открытый элемент И 10 поступает на единичный вход триггера 5 управления, а также входы элементов И И и И 12. Элемент И 12 открьшается, и на его выходе формируется сигнал положительной полярности, который устанавливает регистр 2 в нулевое состояние. По заднему фронту импульса с выхода генератора 4 тактовых импульсов через элемент И 10 триггер 5 управления устанавливается в единичное состояние, а по заднему фронту импульса с выхода элемента И 12 информация о состоянии распределения ресурсов в вычислительной системе с группы 14 информационных входов записывается в регистр 1.

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

Второй импульс с выхода генератора 4 тактовых импульсов через открытый элемент И 10 поступает на второй вход элемента И П и открывает его. Единичный потенциал с выхода этого элемента устанавливает триггер 7 управления в единичное состояние, а также поступает на вход элемента задержки 6.

Сигнал с единичного выхода второг триггера 7 управления запирает элементы И 9 и 10 и поступает на i-ые управляющие входы всех коммутаторов каждой i-ой группы 8.1 коммутаторов (,4). Для примера (фиг. 3), где п - максимально возможное число типов ресурсов в вычислительной системе.

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

5

to

15

20

25

45

начения: 1 либо О

30

35

-на соответствующий информационный вход соответствующего коммутатора подается либо 1 либо 0;

на соответствующий управляющий вход соответствующего коммутатора подан разрешающий потенциал с выхода второго триггера 7 управления;

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

второе срабатывание соответствующих коммутаторов; суммарное время задержки определяется уже временем срабатывания двух кo мyтaтo- ров (два элемента И и . два элемента ИЛИ); третье срабатьтание соответствующих коммутаторов; суммарное время задержки равно времени срабатывания трех коммутаторов (три элемента И и три элемента ИЛИ).

45

40

0 О

о

0

о о

®

О

О

О

0

При поступлении на i-ые управляющие входы всех коммутаторов каждой i-ой группы 8.1 коммутаторов положительного потенциала одновременно ера ботают (таблица): первый 8.2.1 и четвертый 8.2.4 коьв утаторы второй группы 8.2 коммутаторов, второй коммутатор 8.3.2 третьей группы 8.3 и третий коммутатор 8.4.3 четвертой группы 8.А коммутатарбЬ. Сигналы с их выходов поступают соответственно на первые и четвертые управляющие входы всех коммутаторов второй группы 8.2 коммутаторов, на вторые jmpaB ляющие входы всех коммутаторов третьей группы 8.3 коммутаторов и на третьи управляющие входы всех коммутаторов четвертой группы 8.4 коммутаторов. По этим сигналам сработают соответственно третий коммутатор 8.2.3 второй группы 8.2, первый 8.3.1 и четвертый 8.3.4 коммутаторы третьей группы 8.3 и второй коммутатор 8.4.2 четвертой группы 8.4. Сигналы с выходов активных коммутаторов поступают соответственно на третьи управляющие входы всех коммутаторов второй группы 8.2 коммутаторов, первые и четвертые управляющие входы всех коммутаторов третьей группы 8.3 коммутаторов и вторые управляющие . входы всех коммутаторов четвертой группы 8.4 ко№1утаторов.

При этом сработают соответственно второй коммутатор 8.2.2 второй группы 8.2, третий 8.3.3 коммутатор третьей группы 8.3 и в четвертой группе 8.4 - четвертый коммутатор

5

0

0

5 ,

40

45

50

55

8.4.4. Сигналы с выходов этих коммутаторов поступают соответственно на второй, третий и четвертьш единичные входы второго регистра 2.

При этом элементом ИЛИ 13 формируется сигнал наличия тупика. Признак наличия тупиковой ситуации выдается на выход 16 устройства.

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

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

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

Устройство для контроля распределения ресурсов, содержащее регистры, группу регистров, триггер режима, п групп коммутаторов {где п - количество контролируемых ресурсов) и элемент ИЛИ, причем группа информационных входов устройства соединена с информационными входами регистров группы, каждый j-й выход (,п) 1-й группы выходов (,n). регистров группы соединен с j-ми информационными входами i-x коммутаторов с первой по п-ю групп, выход каждого i-ro коммутатора i-ой группы соединен с i-M информационным входом регистра, информационные выходы которого соединены с соответствующими входами элемента ИЛИ, о т л и ч а ю- щ е е с я тем, что, с целью повышения быстродействия, в устройство введены генератор тактовых импульсов, первый триггер управления, элемент задержки, второй триггер управления и четыре элемента И, причем выход каждого коммутатора i-й группы () соединен с J-ми управляющими входами

всех коммутаторов i-й группы, единичный выход второго триггера управления соединен с инверсными входами первого и второго элементов И, с первыми управляющими входами всех коммутаторов п групп, с тактовьм входом и входом установки в О триггера режима, выход которого соединен с входом пуска генератора тактовых импульсов , вход пуска устройства соединен с нулевым входом первого триггера управления и прямым входом первого элемент И, выход которого соединен с единичным входом триггера режима, выход генератора тактовых импульсов соединен с прямым входом второго элемента И, выход которого соединен с первыми входами третьего и четверВход 15 П1/СК

Bb/Aoff триггера J

режимА Вылод генератора

Вы}(од триггера 5

Вы}(од элемента И12

Выход улемента ИП

Вы}(од триггера 1

70618 того элементов R, с единичным и тактовым входами первого триггера управления, единичный и нулевой выходы первого триггера управления соедине- 5 ны с вторыми входами соответственно третьего и четвертого элементов И, выход третьего элемента И соединен с единичным входом второго триггера управления и через элемент задерж- 0 ки - с нулевым входом второго триггера управления, выход четвертого элемента И соединен с тактовыми входами регистров группы и входом начальной установки регистра, выход 5 элемента ИЛИ является выходом признака тупиковой ситуации устройства.

Фкг.2

/owo

rOQII 0001 0100/

Составитель И. Сафронова Редактор Т. Парфенова Техред 1Г.Сердюкова Корректор И. Муска

«.„

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д. 4/5

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

Фуг.З

Изобретение относится к вычислительной технике и может найти применение в современных высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения - повышение быстродействия контроля. Устройство содержит первый 1 и второй 2 регистры, триггер 3 режима, генератор 4 импульсов, первый триггер 5 управления, элемент задержки 6, второй триггер 7 управления, группы коммутаторов, каждая из которых содержит по п коммутаторов, где п - число контролируемых ресурсов, первый 9, второй 10, третий П, четвертый 12 элементы И, элементы ШШ 13. Устрой- ство позволяет уменьшить время для обнаружения тупика за счет асинхронного определения тупиковых множеств (групп ресурсов). 1 табл., 3 ил. с S (Л tsD СО о О5