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

 

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

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

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

РЕСПУБЛИК (50 4 С 06 F 11 00

gal+/ъ ° ф,ФЪ: 7

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

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

МЬВвз . Я

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3879690/24-24 (22) 02,04,85 (46) 07.11.86. Бюл. У 41 (72) С.Н.Ткаченко, В.В.Герасименко, Г.Н.Тимонькин и B.Ñ.Õàð÷åíêo. (53) 681.3(088.8) (56) International jornal of Systems

Science, 1979, v. 10, Р 15, р. 477483, fig. 3.

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

Ф 1015385, кл. G 06 F 11/00, 1983. (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ВЬИИСЛИТЕЛЬНОЙ

СИСТЕМЕ (57) Изобретение относится к вычислительной технике, может быть использовано в системах контроля современных высокопроизводительных вычислительных систем. Цель изобретения—

„„SU„, 269138 A 1 увеличение быстродействия, а также повышение достоверности контроля.

Устройство содержит матрицу регистрирующих ячеек (каждая ячейка содержит триггер), мультиплексор тупика, триггер тупика, блок синхронизации, группу мультиплексоров, две .группы триггеров, элемент И, коммутатор. На информационные входы коммутатора задаются коды номеров процессов, ко- . торые удерживают в данный момент ресурс вычислительной системы. С коммутатора информация записывается в триггере ячеек матрицы. Процесс анализа состоит в выявлении состояния отC сутствия или наличия тупика. В случае тупика номера ресурсов, распреде- > ление которых приводит к тупику, определяются по состоянию триггеров ячеек матрицы. 5 ил.

1 12691

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

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

На Лиг. 1cL, +,á представлена схема устройства; на фиг. 2 — схема бло- 10 ка синхронизации, на фиг. 3 — временные диаграммы функционирования блока синхронизации.

Устройство содержит n m ((m := и, где и — число строк регистрирующей 15 матрицы, равное числу контролируемых ресурсов, тп — число столбцов) ячеек регистрирующей матрицы 1.i.j (i

1...,,n, j = 1,...,m), )i,i) ячейки регистрирующей матрицы (диа- 20 гональ), содержащие триггеры, образованные триггером 2.i-i и элементы

И З.i,i, блок 4 синхронизации, триггер 5 тупика, информационные входы 6 устройства (п шин задания кода номера i-го процесса вычислительной системы), мультиплексоры 7,,...,7„,..., . 7,группы п — канальный коммутатор 8 входной информации, образованный элементами И 8,...,Я„, каждый 1-й мульти- 30 плексор группы содержит элемент И 9 с инверсными входами, элемент И 1 О.j, элемент И 11.j, группу формирователей 12,j импульса, каждый из которых содержит элемент И 13.1, элемент ИЛИ

14.j, триггер 15.j группу формирователей 16.j импульса, образованных триггером 17.1 и элементом И 18.1, мультиплексор 19 тупика, образованный элементом И 20 с инверсивными входа- 40 ми, элементом И 21, кроме того., устройство содержит элемент И 22, элемент ИЛИ 23, выход 24 сбоя (тупика), выходы 25-29 блока синхронизации.

Блок синхронизации (фиг. 2) содержит генератор 30 тактовых импульсов, элементы И 31-35, выходы 36 и

37 генератора тактовых импульсов, одновибратор 38, триггеры 39 и 40.

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

Группы ф ар мир о в ателей 1 2 и 1 б 55 импульса предназначены для вьдачи те. кущей информации о ресурсах, которые в тупик не вовлечены, либо вовсе

38 2 отсутствуют в системе. Триггер 5 тупика предназначен для фиксации состояния тупика в вычислительной системе в анализируемый момент времени.

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

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

Мультиплексоры 7.j в частности элементы И 9, необходимы для обнаружения ресурсов, которые в анализируемый момент времени в тупик не вовлечены, элементы И 10, 11 и 13— для обеспечения синхронной работы а элементов устройства по всем ресурсам.

Элементы ИЛИ 14.j предназначены для обнаружения факта удаления транзитного замыкания какого-либо ресурса на данный„

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

Элемент И 22 используется для формирования сигнала отсутствия тупика, элемент И 2! — для формирования сигнала тупика, элемент ИЛИ 23 — дпя формирования сигнала окончания работы устройства.

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

Триггер 40 применяют для формирования сигнала запуска генератора 30, триггер 39 — для формирования сигналов управления выдачей информации на выходы блока.

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

Элементы И 31-34 нужны для формирования сигналов на выходах 26-29 блока

1269138

4 синхронизации соответственно, а элемент И 35 — для формирования сигнала установки в нулевое состояние триггера 40.

Работа блока синхронизации (фиг.2) заключается в следующем.

В исходном положении триггеры 39 и 40 находятся в нулевом состоянии (входы установки не показаны). По переднему фронту сигнала пуска, пос- 10 тупающего с входа пуска, обнуляется триггер 39 и запускается одновибратор

38, который формирует на своем выходе импульс положительной полярности, поступающий на первый выход 25. По 5 заднему фронту сигнала пуска триггер 40 устанавливается в единичное состояние и запускает генератор 30 импульсов. Единичный потенциал с выхода триггера 40 поступает также 20 на первый вход элемента И 35. Единичный потенциал с нулевого выхода триггера 39 подается на первые входы первого 31 и второго 32 элементов И. 25

Генератор 30 импульсов формирует на выходах 36 и 37 последовательности синхронизирующих импульсов (фиг.3) По первому синхроимпульсу с выхо- З0 да 36 генератора 30 открывается элемент И 31, на выходе 26 формируется импульс положительной полярности.

Первый импульс с выхода 37 генератора 30 открывает элемент И 32, на 35 выходе 27 также формируется импульс положительной полярности. По заднему фронту этого импульса триггер 39 устанавливается в единичное состояние, положительный потенциал с его еди- 40 ничного выхода поступает на первые входы элементов И 33 и 34. Вторые и последующие импульсы синхронизирующих последовательностей с выходов

36 и 37 генератора 30 через открытые 45 .,элементы И 33 и 34 поступают соответ ственно на выходы 28 и 29 блока 4 синхронизации. Кроме того, импульсы. с выхода элемента И 34 подаются на второй вход элемента И 35. По еди- 50 ничному сигналу от элемента ИЛИ 23 элемент И 35 открывается, и на его выходе формируется импульс положительной полярности. По заднему фронту этого импульса триггер 40 режима 55 устанавливается в нулевое состояние, и блок 4 приводится в исходное сос- .1 тояние.

Рассмотрим функционирование устройства.

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

По переднему фронту сигнала начала анализа, поступающего с входа пуска устройства, на первом выходе

25 блока 4 синхронизации формируется единичный импульс, который разрешает через коммутатор 8 прием кода номера процесса, который владеет ресурсом.

Если i ì ресурсом владеют некоторые процессы либо же его только запрашивают, то триггеры 2 ° i.1-2.i.n

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

2.j.1 k-й ячейки находится в единичном состоянии. Если m-й ресурс в момент t анализа системы отсутствует в системе, в случае потребляемых ресурсов, либо же полностью не задействован (на него нет запросов и никакой процесс им не владеет) — в случае повторно используемых ресурсов, то m-й триггер 2.m.m m-й ячейки

I m.m в начальный момент: анализа (до

/ появления импульса с третьего выхода 27 блока 4 синхронизации) находится в единичном состоянии. Информация с триггеров 2.1-2.п ячеек поступает на информационные входы мультиплексоров 7 группы (элементы

И 9. 1-9.п). Единичные сигналы формируются на выходах тех элементов

И 9.i на входы которых поступают все нулевые потенциалы с триггеров (2.i.1-2.i.п) соответствующей i-й ячейки 1.i.

По заднему фронту сигнала начала анализа на выходе 26 блока 4 синхронизации формируется единичный импульс, который поступает на управляющий вход мультиплексоров 7 (элементы И 11. 1-11.n) открывает те элементы И 11.i на первых входах которых присутствует единичный потенциал. Единичные сигналы с выходов открытых элементов И 11.i поступают на вход разрешения соответствующих формирователей 12.i импульса и устанавливают их в единичное состояние.

Единичные потенциалы с единичных выходов соответствующих триггеров

15.i поступают на первые входы соответствующих элементов И 13 ° i.

По единичному импульсу с выхода

29 блока 4 синхронизации, поступающему на входы синхронизации формирователей 16 и мультиплексоров 7, срабатывают те формирователи 16, которые имеют на своих входах единичные потенциалы. Единичные импульсы с выходов соответствующих элементов

И 10.1 поступают íà 1-е входы элемента И 22. Единичные импульсы с выхо50

S 12691

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

Единичным импульсом с выхода 15

27 блока 4 синхронизации, поступающим на вторые входы всех элементов

И 3.1 1. открываются те элементы

И З.i-i для которых триггеры 2.i находятся в единичном состоянии. По 20 заднему фронту импульса с выхода 27 блока 4 синхронизации эти триггеры устанавливаются в нулевое состояние.

Установка в нулевое состояние соответствующих диагональных триггеров 25 матрицы производится с целью индентификации состояния системы.

Если состояние не тупиковое— триггеры всех ячеек должны быть в нулевом состоянии. 30

После обнуления соответствующих триггеров 2.i.i нулевые потенциалы с единичных выходов триггеров соответствующих i-х ячеек поступают на информационные входы мультиплексоров 7 (входы соответствукнцих элементов И 9.i). Единичный импульс с выхода 28 блока 4 синхронизации поступает на входы синхронизации формирователей

12. 1, °, 12.п импульса и открывает те формирователи 12, у которых на входах разрешения присутствуют положительные потенциалы. На выходах этих формирователей формируются еди- 45 ничные импульсы, по которым соответствующие формирователи 16. 1,..., 16.п переходят в разрешенное состояние.

38 Ь дов соответствующих элементов И 18. i поступают на информационные входы мультиплексора 19 тупика (инверсные

i-e входы элемента И 20), на входы установки в нуль соответствующих триггеров 17.i устанавливая их по ,заднему фронту в нулевое состояние, а также на вторые входы всех соответствующих элементов И З.j .i (i j), открывают те элементы И З,j .i, для которых соответствующие i-e триггеры 2.j.i находятся в единичном состоянии, Единичные импульсы с соответствующих открытых элементов И

З.j,i поступают на входы соответствующих формирователей 12.j и устанавливают их в единичные состояния.

По заднему фронту этих импульсов соответствующие 1-е .триггеры 2,j ..i устанавливаются в нулевое состояние.

Так происходят удаление и фиксация удаления всех транзитивно замыкающихся ресурсов на данный -й, если в результате анализа установлено, что данный i — и в тупик не вовлечен, т.е. триггеры всех ячеек находятся в нулевом состоянии, Следовательно, циклической цепочки взаимного ожидания ресурсов нет.

По второму импульсу с выхода 28 блока 4 синхронизации открываются соответствующие j-e элементы И 13.j и происходит перепись информации с триггеров 15,j в соответствующие триггеры 17.j с установкой по заднему фронту импульса триггера 15.j в нулевое состояние (подготовка к приему очередной информации). По второму импульсу с выхода 29 блока 4 синхронизации открываются соответствующие j-e элементы И 18.j и единичные импульсы поступают на информационные входы мультиплексора 19 тупика (инверсные входы элемента И 20), на входы установки в нуль соответствующих триггеров 17.j, устанавливая по заднему фронту их в нулевое состояние, а также на вторые входы всех соответствующих элементов И

З.m.j (m + j, m = 1,n), и открывают те элементы И З.m j для которых соответствующие j-e триггеры 2.m.j ш-ячеек находятся в единичном состоянии. Кроме того, по этому же импульсу открываются те элементы И 10.1 (1 = 1,n), которые имеют на своих первых входах единичные потенциалы.

Единичные импульсы с выходов соот1269

7 ветстнующих элементов И 10.1 поступают на 1-е входы элемента И 22.

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

Если по очередному импульсу с выхода 29 блока 4 синхронизации на выходах всех элементов И 10.1-10.п формируются единичные сигналы (все 1О триггеры всех ячеек находятся в нулевом состоянии), то срабатывает элемент И 22, нулевой сигнал с инверсного выхода. которого запрещает срабатывание элемента И 11, а еди- 15 ничный сигнал с прямого выхода через элемент ИЛИ 23 поступает на вход элемента И 35 блока 4 синхронизации, инициируя тем самым окончание работы устройства. Сигнал тупика на вы- щ ход 24 устройства не выдается.

Если же по очередному импульсу с выхода 29 блока 4 синхронизации на выходах элементов И 18. 1 — 18.п фор25 мируются все нулевые сигналы, это свидетельствует о том, что во всех ячейках, в которых записана информация о распределении ресурсов системы удаление ресурсов не вовлеЭ

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

В результате открывается элемент

И 20, единичный сигнал с которого по- ступает на второй вход элемента И

21, на третий вход которого поступает импульс с выхода 29 блока 4 синхронизации, а на первый — единичный импульс с инверсного выхода элемента И 22. На выходе элемента И 21 формируется единичный импульс, который устанавливает триггер 5 тупика в единичное состояние, а также через элемент ИЛИ 23 поступает на вход элемента И 35 блока 4 синхронизации.

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

138 тупиковое множество ресурсов, могут быть определены непосредственно по состоянию ячеек 1, Для выполнения очередного цикла контроля распределения ресурсов в системе работа устройства повторяется аналогично описанному.

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

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

9 1269138 )О

Ii,i 1 ячейки, соединены с нулевыми с выходом мультиплексора тупика и входами триггеров своих ячеек, а так- единичным входом триггера тупика, же с входами разрешения х-га фор- второй выход блока синхронизации мирователя импульса первой группы соединен с входами синхронизации н первым выходом i-ro мультиплексора 5 формирователя импульса первой групгруппы, выходы формирователя импуль- пы, третий выход блока синхронизаса первой группы соединены со свои- ции соединен с первыми управляющими ми входами блокировки и входами раз- входами мультиплексоров группы, с решения одноименных формирователей входами синхронизации формирователя импульса второй группы, выходы кото- 10 импульса второй группы и входом синрых соединены со своими входами бло- хронизации мультиплексора тупика, кировки и информационными входами четвертый выход блока синхронизации мультиплексора тупика, а также с соединен с входами синхронизации управляющими входами элементов И . триггеров (i.,i)-x ячеек регистрируюячеек одноименных столбцов регистри- 15 щей матрицы, пятый выход блока синрующей матрицы, вторые выходы мульти- :хронизации соединен с вторыми управ-, плексоров группы соединены с входа- ляющими входами мультиплексоров груйми элемента И, прямой выход которо- пы, а инверсный выход элемента И го соединен с первым входом элемента соединен с управляющим входом мульИЛИ, второй вход которого соединен 20 типлексора тупика.

° ° °

° ° °

° °

° В °

° ° .2.2

O ° °

° ° Э

° ° °

° ° °

° ° фт-1),2

° ЮФ

° ° °

° а °

1269138

Уий.fd

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

ВНИИПИ Заказ 6037/51

1269138

Тираж 671

Подписное