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

11 Изобретение относится к вычислительной технике и может быть использовано в системах контроля современных высокопроизводительных вычислительных систем. Цель изобретения - увеличение быстродействия и повьшшние достовернос ти контроля. На фиг. ICL, ,Ь представлена схе ма устройства, на фиг. 2 - схема бло ка синхронизацииJ на фиг. 3 - временные диаграммы функционирования блока синхронизации. Устройство содержит n-m((m 11, где п - число строк регистрирующей матрицы, равное числу контролируемых ресурсов; m - число столбцов) ячеек регистрирующей матрицы 1.1.j (i 1,...,n, j 1,...,m), i,i ячейки регистрирующей матрицы (диагональ), содержаище триггеры, образованные триггером 2.i.i и элементы И S.i.i, блок 4 синхронизации, триггер 5 тупика, информационные входы 6 устройства (п шин задания кода номера i-ro процесса вычислительной системы) , мультиплексоры 7 ,..., 7j ,. .. , 7,, группы п - канальный коммутатор 8 входной информации,образованньй элеме тами И 8 ,. .. ,8п , каждый j-й мультиплексор группы содержит элемент И 9j с инверсными входами, элемент И 10.j элемент И 11. j , группу формирователей 12.J импульса, каждьм из которых содержит элемент И 13.J, элемент ИЛИ j, триггер 15.J, группу формиро-вателей 16.J импульса, образованных триггером 17.J и элементом И 18.J, мультиплексор 19 тупика, образованны элементом И 20 с инверсивными входами, элементом И 21, кроме того, устройство содержит элемент И 22, элемент ИЛИ 23, выход 24 сбоя (тупика), выходы 25-29 блока синхронизации. Блок синхронизации (фиг„ 2) содержит генератор 30 тактовых импульсов, элементы И 31-35, выходы 36 и 37 генератора тактовых импульсов, одновибратор 38, триггеры 39 и 40. Триггеры всех ячеек предназначены для приема, хранения и выдачи информации о состоянии распределения ресурсов вычислительной системы на момент анализа. Группы формирователей 12 и 16 импульса предназначены для выдачи те кущей информации о ресурсах, которые в тупик не вовлечены,либо вовсе 82 отсутствуют в системе. Триггер 5 тупика предназначен для фиксации состояния тупика в вычислительной системе в анализируемый момент времени. Информационные входы 6 предусмотрены для приема информации о состоянии распределения ресурсов, на них задается код процесса, который захватил ресурс. Элементы И, входящие в ячейки, нужны для выдачи информации о состоянии распределения ресурсов, а также для управления триггером .г ячеек в соответствии с управляющими сигналами. Коммутатор 8 используется для одновременной передачи информации о состоянии распределения ресурсов с входа устройства в триггеры ячеек матрицы. Мультиплексоры 7.J, в частности элементы И 9, необходимы для обнаружения ресурсов, которые в анализируемый момент времени в тупик не вовлечены, элементы И 10, 11 и 13- для обеспечения синхронной работы элементов устройства по всем ресурсам. Элементы ИЛИ 14.j предназначены для обнаружения факта удаления транзитного замыкания какого-либо ресурса на данный,. Мультиплексор 19 предназначен для формирования сигнала, указывающего на отсутствие изменений в триггерах всех ячеек матрицы. Элемент И 22 используется для формирования сигнала отсутствия тупика, элемент И 21 - для формирования сигнала тупика, элемент ИЛИ 23 - для формирования сигнала окончания работы устройства. Выход 24 устройства предназначен для выдачи сигнала - признака тупиковой ситуации в вычислительной системе. Триггер 40 применяют для формирования сигнала запуска генератора 30, триггер 39 - для формирования сигналов управления вьщачей информации на выходы блока. Одновибратор 38 предназначен для формирования сигнала приема информации в триггеры ячеек о состоянии распределения ресурсов р генератор 30 .- ; для формирования двух последовательностей импульсов на выходах 36 и 37. Элементы И 31-34 нужны для формирования сигналов на выходах 26-29 блока 3 4 синхронизации соответственно, а элемент И 35 - для формирования сиг нала установки в нулевое состояние триггера 40. Работа блока синхронизации (фиг. заключается в следующем. В исходном положении триггеры 39 и 40 находятся в нулевом состоянии (входы установки не показаны). По переднему фронту сигнала пуска, пос тупающего с входа пуска, обнуляется триггер 39 и запускается одновибрат 38, который формирует на своем выхо де импульс положительной полярности поступающий на первый выход 25. По заднему фронту сигнала пуска триггер 40 устанавливается в единичное состояние и запускает генератор 30 импульсов. Единичный потенциал с выхода триггера 40 поступает также на первый вход элемента И 35. Единичный потенциал с нулевого выхода триггера 39 подается на первые входы первого 31 и второго 32 элементов И. Генератор 30 импульсов формирует на выходах 36 и 37 последовательнос ти синхронизирующих импульсов (фиг. По первому синхроимпульсу с выхода 36 генератора 30 открывается элемент И 31, на выходе 26 формируется импульс положительной полярности. Первый импульс с выхода 37 генератора 30 открывает элемент И 32, на выходе 27 также формируется импульс положительной полярности. По заднему фронту этого импульса триггер 39 устанавливается в единичное состояние положительный потенциал с его единичного выхода поступает на первые входы элементов И 33 и 34. Вторые и последующие импульсы синхронизирую щих последовательностей с выходов 36 и 37 генератора 30 через открытые :Элементы И 33 и 34 поступают соответ ственно на выходы 28 и 29 блока 4 синхронизации. Кроме того, импульсы с выхода элемента И 34 подаются на второй вход элемента И 35. По единичному сигналу от элемента ИЛИ 23 элемент И 35 открывается, и на его выходе формируется импульс положительной полярности. По заднему фронту этого импульса триггер 40 режима устанавливается в нулевое состояние, и блок 4 приводится в исходное соетояние. 84 Рассмотрим функционирование устройства . В исходном положении все элементы памяти находятся в нулевом состоянии (входы установки не показаны). По переднему фронту сигнала начала анализа, поступающего с входа пуска устройства, на первом выходе 25 блока 4 синхронизации формируется единичный импульс, который разрешает через коммутатор 8 прием кода номера процесса, который владеет ресурсом. Если i-M ресурсом владеют некоторые процессы либо же его только запрашивают, то триггеры 2.i.1-2.L,n i-й строки находятся в нулевом состоянии. Если к-м ресурсом владеет i-й процесс, который запрашивает еще и 1-й ресурс, то 1-й триггер 2.J.1 k-й ячейки находится в единичном состоянии. Если т-й ресурс в момент t анализа системы отсутствует в системе, в случае потребляемых ресурсов, либо же полностью не задействован (на него нет запросов и никакой процесс им не владеет) - в случае повторно используемых ресурсов, то т-й триггер 2.m.m m-и ячейки l.m.m в начальный момент, анализа (до появления импульса с третьего выхода 27 блока 4 синхронизации) находится в единичном состоянии. Информация с триггеров 2.1-2.П ячеек поступает на информационные входы мультиплексоров 7 группы (элементы И 9.1-9.п). Единичные сигналы формируются на выходах тех элементов И 9.1, на входы которых поступают все нулевые потенциалы с триггеров (2.1.1-2.1.п) соответствующей 1-й ячейки 1.1. По заднему фронту сигнала начала анализа на выходе 26 блока 4 синхронизации формируется единичный импульс, который поступает на управляющий вход мультиплексоров 7 (элементы И 11.1-11.П), открывает те элементы И 11.1, на первых входах которых присутствует единичньй потенциал. Единичные сигналы с выходов открытых элементов И 11.1 поступают на вход разрешения соответствующих формирователей 12.1 импульса и устанавливают их в единичное состояние. Единичные потенциалы с единичных выходов соответствующих триггеров 15.1 поступают на первые входы соответствующих элементов И 13.1.

51

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

Единичным импульсом с выхода 27 блока 4 синхронизации, поступающим на вторые входы всех элементов И 3.i.i, открываются те элементы И 3.i.i, для которых триггеры 2.1 находятся в единичном состоянии. По заднему фронту импульса с выхода 27 блока 4 синхронизации эти триггеры устанавливаются в нулевое состояние. Установка в нулевое состояние соответствующих диагональных триггеров матрицы производится с целью индентификации состояния системы.

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

После обнуления соответствующих триггеров 2.1.1 нулевые потенциалы с единичных выходов триггеров соответствующих 1-х ячеек поступают на информационные входы мультиплексоров 7 (входы соответствуннцих элементов И 9.1).

:. Единичный импульс с выхода 28 блока 4 синхронизации поступает на входы синхронизации формирователей 12.1,...,12.п импульса и открывает те формирователи 12, у которых на входах разрешения присутствуют полоз&1тельные потенциалы. На выходах этих формирователей формируются единичные импульсы, по которым соответствующие формирователи 16.1,.. ., 16.п переходят в разрешенное состояние.

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

дов соответствующих элементов И 18.1 поступают на информационные входы мультиплексора 19 тупика (инверсные 1-е входы элемента И 20), на входы установки в нуль соответствующих триггеров 17.1 устанавливая их по ,заднему фронту в нулевое состояние, а также на вторые входы всех соответствующих элементов H3.j.i () открывают те элементы И 3.j.i, для которых соответствующие 1-е триггеры 2.j.i находятся в единичном состоянии. Единичные импульсы с соответствующих открытых элементов И 3.j.i поступают на входы соответствующих формирователей I2.j и устанавливают их в единичные состояния. По заднему фронту этих импульсов соответствующие 1-е .триггеры 2.j.i устанавливаются в нулевое состояние Так происходят удаление и фиксация удаления всех транзитивно замыкающихся ресурсов на данный 1-й, если в результате анализа установлено, что данньш 1-й в тупик не вовлечен, т.е. триггеры всех ячеек находятся в нулевом состоянии. Следовательно, циклической цепочки взаимного ожидания ресурсов нет.

По второму импульсу с выхода 28 блока 4 синхронизации открываются соответствующие j-e элементы И 13.j и происходит перепись информации -с триггеров 15.J в соответствующие триггеры 17.J с установкой по заднему фронту импульса триггера 15.J в нулевое состояние (подготовка к приему очередной информации). По второму импульсу с выхода 29 блока 4 синхронизации открываются соответствующие j-e элементы И 18.j, и единичные импульсы поступают на информационные входы мультиплексора 19 тупика (инверсные входы элемента И 20) на входы установки в нуль соответствующих триггеров 17.J, устанавливая по заднему фронту их в нулевое состояние, а также на вторые входы всех соответствующих элементов И 3.m.j (та 3 j , m 1 ,n), и открывают те элементы И 3.m,j, для которых соответствующие j-e триггеры 2.m.j m-ячеек находятся в единичном состоянии. Кроме того, по этому же импульсу отк ьшаются те элементы И 10.1 (1 1,п), которые имеют на своих первых входах единичные потенциалы. Единичные импульсы с выходов соот7ветствую1цих элементов И 10.1 поступают на 1-е входы элемента И 22, Процесс анализа продолжается до обнаружения одного из двух возможных состояний: отсутствие либо наличие тупика. Если по очередному импульсу с вы хода 29 блока 4 синхронизации на выходах всех элементов И 10.1-10.п формируются единичные сигналы (все триггеры всех ячеек находятся в нулевом состоянии), то срабатывает элемент И 22, нулевой сигнал с инверсного выхода которого запрещает срабатывание элемента И 2l, а единичный сигнал с прямого выхода чере элемент ИЛИ 23 поступает на вход элемента И 35 блока 4 синхронизации инициируя тем самым окончание работы устройства. Сигнал тупика на выход 24 устройства не вьщается. I Если же по очередному импульсу с выхода 29 блока 4 синхронизации на выходах элементов И 18.1-18.п формируются все нулевые сигналы, это свидетельствует о том, что во всех ячейках, в которых записана информация о распределении ресурсов системы, удаление ресурсов, не вовлеченных в тупик, не произошло. И еели на выходах элементов И 10.1-10.п формируются как единичные, так и ну левые сигналы, либо же только нулевые, это свидетельствует о том, что в ячейках есть какая-то информация, т.е. транзитивно-замкнувшиеся друг на друга ресурсы, которые в результате анализа не бьши удалены. В результате открывается элемент И 20, единичный сигнал с которого п ступает на второй вход элемента И 21, на третий вход которого поступает импульс с выхода 29 блока 4 си хронизации, а на первый - единичный импульс с инверсного выхода элемен та И 22. На выходе элемента И 21 формируется единичный импульс, кото рый устанавливает триггер 5 тупика в единичное состояние, а также чере элемент ИЛИ 23 поступает на вход элемента И 35 блока 4 синхронизации Работа устройства на этом прекращается. На выходе 24 устройства присутствует сигнал тупика в вычислительной системе. Номера ресурсов, : распределение которых приводит к ту пиковой ситуации, а также ресурсов, которые транзитивно .замкнулись на 88 тупиковое множество ресурсов, могут быть определены непосредственно по состоянию ячеек 1. Для выполнения очередного цикла контроля распределения ресурсов в системе работа устройства повторяется аналогично описанному. Формула изобретения Устройство для контроля распределения ресурсов в вычислительной системе, содержащее регистрирующую матрицу, п-канальный коммутатор входной информации (п - число ресурсов вычислительной системы), мультип ексор тупика, триггер тупика, блок синхронизации и элемент ИЛИ, причем информационные входы каждого канала (канального коммутатора входной информации) соединены с соответствующими шинами задания кода номера i-ro процесса вычислительной системы (i 1,...,п), первый выход блока синхронизации соединен с управляющими входами всех каналов и канального коммутатора входной информации, J выход элемента ИЛИ соединен с входом, сброса блока синхр1онизации, отличающееся тем, что, с целью увеличения быстродействия, а также повышения достоверности контроля, оно содержит п мультиплексоров группы, первую и вторую группы формирователей импульсов, элемент И, а регистрирующая матрица содержит m (m n) ячеек, причем каждая ячейка регистрирующей матрицы, за исключением i,i ячеек,содержит триггер и элемент И, а каждая 1,1 ячейка, регистрирующей матрицы содержит триггер, причем вход пуска устройства соединен с входом пуска блока синхронизации и входом сброса триггера тупика, выход которого является выходом сбоя устройства, выходы i-го канала п-канальной входной информации соединены с единичными входами триггеров ячеек i-й строки регистрирующей матрицы, выходы триггеров всех ячеек i-й строки регистрирующей матрицы соединены с информационными входами i-x мультиплексоров группы, выходы триггеров ячеек регистрирующей матрицы, исключая i,i ячейки, соединены с информационными входами элементов И своих ячеек, выходы элементов И ячеек i-й строки регистрирующей матрицы, исключая 91 i,i ячейки, соединены с нулевыми входами триггеров своих ячеек, а так же с входами разрешения i-ro формирователя импульса первой группы и первым выходом i-ro мультиплексора группы, выходы формирователя импульса первой группы соединены со своими входами блокировки и входами разрешения одноименных формирователей импульса второй группы, выходы которых соединены со своими входами блокировки и информационными входами мультиплексора тупика, а также с управляющими входами элементов И . ячеек одноименных столбцов регистри рующей матрицы, вторые выходы мульти плексоров группы соединены с входами элемента И, прямой выход которого соединен с первым входом элемент ИЛИ, второй вход которого соединен 3810 с выходом мультиплексора тупика и единичным входом триггера тупика, второй выход блока синхронизации соединен с входами синхронизации формирователя импульса первой группы, третий выход блока синхронизации соединен с первыми управляющими входами мультиплексоров группы, с входами синхронизации формирователя импульса второй группы и входом синхронизации мультиплексора тупика, четвертый выход блока синхронизации соединен с входами синхронизации триггеров (i.,i)-x ячеек регистрирующей матрицы, пятый выход блока син:хронизации соединен с вторыми управ7 Ляющими входами мультиплексоров rpyfiпы, а инверсный выход элемента И соединен с управляющим входом мультиплексора тупика.

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

4LL 16.1

CpU2.Z