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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН

„„SU„„1297061 (511 4 G 06 F 11/26

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

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

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

Н A8TOPCHOMV СВИДЕТЕП6СТВУ (21) 3962157/24-24 (22) 09.10.85 (46) 15.03.87. Вюл. У 1О (72) С.Н. Ткаченко, В.В. Герасименко, Г.Н. Тимонькин и В.С. Харченко (53) 681.3(088.8) (56) Авторское свидетельство СССР

Р 1015385, кл. G 06 F 11/00, 1983.

International Domal of Systems .

Science, 1979, ч. 10, 9 5, р. 477483, Fig 3. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к вычислительной технике и может найти применение в современных высокопроизводительных вычислительных системах для контроля корректности распределения ресурсов. Цель изобретения — повышение быстродействия контроля. Устройство содержит первый 1 и второй 2 регистры, триггер 3 режима, генератор 4 импульсов, первый триггер 5 управления, элемент задержки 6, второй триггер 7 управления, группы коммутаторов, каждая из которых содержит по и коммутаторов, где n — число контролируемых ресурсов, первый 9, второй )0 третий 11, четвертый 12 элементы И, элементы ИЛИ 13. Устройство позволяет уменьшить время для обнаружения тупика эа счет асинхронного определения тупиковых множеств (групп ресурсов). 1 табл., 3 ил. 1

1297061

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

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

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

5 .Устройство для контроля распределения ресурсов содержит (фиг. 1) группу регистров 1 и регистр 2, триггер 3 режима, генератор 4 тактовых импульсов, первый триггер 5 управления, элемент задержки 6, второй триггер 7 управления, первую 8„1-8.п группы коммутаторов, каждая из кото— рых содержит по и коммутаторов, где

n — количество контролируемых ресурсов, первый 9, второй 10, третий 11 и четвертый 12 элементы И, элемент

ИЛИ 13, группу 14 входов распределения ресурсов устройства, вход 15 пуска, выход 16, (первый 17.1.1-17.1.1. .п) — (первый 17.n.l-l7.n.n) выходов соответственно первой — n-ой групп выходов первого регистра

Первый регистр 1 предназначен для приема, хранения и выдачи информации 35 о состоянии распределения ресурсов вычислительной системы. Причем каждому i-ому ресурсу в регистре I соответствует i-я группа входов (выходов). Если i-ым ресурсом владеет k-ыи

" 40 процесс, который еще запрашивает и -ый ресурс, то при приемке информации в регистр 1 в -ый разряд i-ой группы запишется единица, в противном случае нуль.

2

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

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

Каждый 1-ый коммутатор 8.j.1 ,1-ой группы (if) ) предназначен для формирования сигнала обнаружения взаимодействия )-го русурса с i-ым.

Коммутатор З.i.i каждой i-ой группы коммутаторов предназначен для формирования сигнала, указывающего на факт вовлеченности i-го ресурса в тупик.

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

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

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

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

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

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

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

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

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

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

Второй импульс с выхода генератора 4 тактовых импульсов через открытый элемент И 10 поступает на второй вход элемента И 1 1 и открывает его. 0

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

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

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

61

В таблиц начения:

1 либо 0

4 е приняты следующие обозна соответствующий информационный вход соответствующего коммутатора подается либо 1 либо 0; на соответствующий управляющий вход соответствующего коммутатора подан разрешающий потенциал с, выхода второго триггера 7 управления; первое срабатывание соответствующих коммутаторов. Время задержки на срабатывание определяется временем задержки одного коммутатора (одного элемента

И и одного элемента

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

ИЛИ).

Комму- Группа, 8 татор, У 8.1 8.2 8.3 8.4

0 0 0

1 — 0

Я Я

0 0 0 0

0 0 0 0

2 0 0 0 0

0 0 0

Д» -Oi jg

0 0 0

1297061 6

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

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

По истечении кванта времени

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

На единичном выходе триггера 3

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

Продолжение таблицы

Группа, №

Коммутатор, № (8.З вЂ” 0 0,0 0 0

0 -0

0 0

0 0

При поступлении на i-ые управляющие входы всех коммутаторов каждой

i-ой группы 8.i коммутаторов положительного потенциала одновременно сра ботают (таблица): первый 8.2.1 и четвертый 8.2.4 коммутаторы второй группы 8,2 коммутаторов, второй коммутатор 8.3 ° 2 третьей группы 8.3 и третий коммутатор 8,4.3 четвертой группы 8.4 коммутаторов. Сигналы с их выходов поступают соответственно на первые и четвертые управляющие входы всех коммутаторов второй группы 8.2 коммутаторов, на вторые управляющие входы всех коммутаторов третьей группы 8.3 коммутаторов и на третьи управляющие входы всех коммутаторов четвертой группы 8.4 коммутаторов. По этим сигналам сработают 41 соответственно третий коммутатор

8.2.3 второй группы 8.2, первый

8.3.1 и четвертый 8.3.4 коммутаторы третьей группы 8.3 и второй коммутатор 8.4.2 четвертой группы 8.4.

Сигналы с выходов активных коммутаторов поступают соответственно на третьи управляющие входы всех коммутаторов второй группы 8.2 коммутаторов, первые и четвертые управляющие входы всех коммутаторов третьей группы 8.3 коммутаторов и вторые управляющие . входы всех коммутаторов четвертой группы 8.4 коммутаторов.

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

Ц Я -ф

4 -0 0 0 0

-О1 jg

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

Устройство для контроля распределения ресурсов, содержащее регистры, группу регистров, триггер режима, и групп коммутаторов (где n — количество контролируемых ресурсов) и элемент ИЛИ, причем группа информационных входов устройства соединена с информационными входами регистров группы, каждый j-й выход (j=l,n)

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

Оход 6 "®ск" дыход триггера Ю юж мА

Оыход генерапора ф

Нь!хад триггера 5

Выход элемента

012

Выход злемеиаа

877 быход триггера

010ц

00tl

0001

0100

Составитель И. Сафронова

Редактор Т. Парфенова Техред Jf.Ñåðäþêoâà Корректор H. Муска

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

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4. ления соединен с инверсными входами первого и второго элементов И, с первыми управляющими входами всех коммутаторов и групп, с тактовым входом и входом установки в 0 триггера 5 режима, выход которого соединен с входом пуска генератора тактовых импульсов, вход пуска устройства соединен с нулевым входом первого триггера управления и прямым входом первого элемент И, выход которого соединен с единичным входом триггера режима, выход генератора тактовых импульсов соединен с прямым входом второго элемента И, выход которого соединен с первыми входами третьего и четвертого элементов И., с единичным и тактовым входами первого триггера управления, единичный и нулевой выходы первого триггера управления соединены с вторыми входами соответственно третьего и четвертого элементов И, выход третьего элемента И .соединен с единичным входом второго триггера управления и через элемент задержки — с нулевым входом второго триггера управления, выход четвертого элемента И соединен с тактовыми входами регистров группы и входом начальной установки регистра, выход элемента ИЛИ является выходом признака тупиковой ситуации устройства.