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

) (И) А 1 Г 06 Р 11 О ИСАНИЕ ИЗОБРЕТЕНИЯ СВИДЕТЕЛЬСТВУ АВТОРСН35(57) Изобретениетельной техникезовано для контр КОНТРОЛЯ РАСПРЫЧИСЛИТЕЛЬНОЙ тносится к вычисли- может быть исполья корректностии ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР(56) Авторское с1015385, кл. САвторское свид1252791, кл. С распределения ресурсов. Цель изобретения - повышение быстродействия,устрой=тва. Поставленная цель достигается тем, что устройство содержити групп по и триггеров 1 в каждой,где и - число типов ресурсов в системе, первый триггер 2, счетчик 3, второй триггер 4, и элементов ИЛИ-НЕ 5,и групп по и элементов И 6 в каждой,первый 7, второй 8, третий 9 элементы И, элемент ИЛИ 10, четвертый 11и пятый 12 элементы И, входы 13 состояния распределения ресурсов устройства, вход 14 запуска устройства,вход 15 синхронизации устройства,вход 16 числа процессов устройства,выход 17 признака наличия тупиковойситуации устройства. 2 ил.00 ответствукцими номерам нулевых строк,элементы, содержащие единицы, обнуляются. Этот процесс в устройстве реализуется параллельно.Триггеры 1 предназначены для приема информации о состоянии распреде"ления ресурсов системы, а также дляфиксации результатов текущего анализа.Элементы ИЛИ-НЕ 5 предназначеныдля Аормирования сигнала о наличиив -й строке хотя бы одного единичного элемента.Счетчик 3 предназначен для приемакода числа (1-1), где 1 - количестворесурсов распределенных процессов,функционирующих в системе, а такжедля подсчета числа тактовых импульсов. Триггер 4 предназначен для фиксации сигнала о наличии тупиковойситуации. Элемент ИЛИ 10 предназначен для Аормирования сигнала окончания процедуры контроля. Элемент И 12предназначен для Аормирования сигнала о наличии тупиковой ситуации.Рассмотрим работу устройства напримере анализа состояния вычислительной системы, представленного графом(фиг. 2),Сигнал пуска, поступающий на вход14 запуска устройства, разрешает поступление синхроимпульса с входа 15устройства. По переднему фронту этогосинхроимпульса происходит запись инАормации о текущем распределении ре,сурсов системы в триггеры 1 и производится запись в счетчик 3 двоичногокода числа (1-1) в соответствии сграАом (Аиг. 2). По заднему Аронтуэтого синхроимпульса устанавливаются триггеры 2 и 4 в единичное состояние. В соответствии с граАом и егоматричным представлением триггеры1.2.1, 12.3, 1.2.4, 1.4.2 устанавливаются в единичное состояниеЭтиединичные сигналы подаются на входыэлементов ИЛИ-НЕ.5.2, 5.3, 5,4, навыходах которых Аормируются сигналылогического "0", а на выходах остальных элементов ИЛИ-НЕ сигналы логичес.кой "1". Они подаются на входы всехэлементов И. 6, кроме элементовИ 6.1.2-6.4.2, 6.1.3-6.4.3, 6.1.46.3.4. По второму синхроимпульсу,который поступает на вторые входывсех элементов И 6, на выходе элемента И 62,1 Аормируется импульс, который подается на Е-вход триггера1,2.1 и обнуляет его. Второй синхро 315099Изобретение относится к вычислительной технике и может быть использовано для контроля корректности распределения ресурсов.Цель изобретения - увеличение быстродействия.На фиг. 1 представлена схема устройства для контроля распределенияресурсов в вычислительной системе; 10на фиг. 2 - пример граАа связностираспределенных ресурсов л соответствующая ему матрица связностей,Устройство содержит и групп по итриггеров 1 в каждой, где и - число 15типов ресурсов в системе, первыйтриггер 2, счетчик 3, второй триггер 4, и элементов ИЛИ"НЕ 5, и групппо и элементов И 6 в каждой, первый7, второй 8 и третий 9 элементы И, 20элемент ИЛИ 10, четвертый 11 и пятый12 элементы И, входы 13 состоянияраспределения ресурсов устройства,вход 14 запуска, вход 15 синхронизации, вход 16 числа процессов устройства и выход 17 признака наличия тупиковой ситуации устройства.В многопроцессорных вычислительньгх системах между параллельными вычислительными процессами возникают 30состязания за владение ресурсами иможет возникнуть тупиковая ситуация,когда один процесс владеет каким-торесурсом и пытается захватить другойресурс, который занят другим процессом и который, в свою очередь, запрашивает ресурс, занятый предыдущимпроцессом. В этой ситуации оба процесса взаимно блокируются друг надруге, ресурсы не используются и процессы останавливаются, что приводитк снижению эААективности Аункционирования вычислительной системы.Устройство для контроля распределения ресурсов позволяет проанализировать состояние системы на наличиетупиковой ситуации, Состояние системы однозначно определяется орграфом,наличие цикла в котором свидетельствует о наличии тупика, Орграф можнопредставить в виде квадратной матрицы связностей.Устройство реализует алгоритм сокращения дуг, входящих в вершины, изкоторых не выходит ни одна дуга. Физически новая матрица связностейстроится следующим образом (в одномрабочем такте); определяются нулевыестроки, и в столбцах с номерами, со5 15импульс также подается на счетныйвход счетчика 3, из содержимого которого вычитается единица. Аналогично работает устройство и на следукщих тактах.После четвертого импульса на выходе счетчика 3 Формируется двоичный код числа О. При поступлении пятого импульса на выходе элементаИ 11 Формируется импульс, который подается на вход элемента ИЛИ 10, навыходе которого Формируется импульс,сигнализирующий об окончании анализа, который обнуляет триггер 2, Единичный сигнал с инверсного выходатриггера 2 подается на вход элемента И 12, на .второй вход которого подается единичный сигнал с триггера 4.На выходе элемента И 12 Формируетсясигнал логической "1", свидетельствующий о наличии тупиковой ситуади.В случае отсутствия тупиковой ситуации в результате анализа матрицапреобразуется в нулевую и на выходеэлемента И 9 Формируется импульс,обнуляющий триггер 4, а на выходе элемента ИЛИ 10 Формируется импульс,свидетельствующий об окончании анализа и обнуляющий триггер 2. Нулевойсигнал с выхода триггера 4 подаетсяна вход элемента И 12, а на выходе17 устройства будет нулевой сигнал,свидетельствующий об отсутствии тупиковой ситуации,формула изо бретения Устройство для контроля распределения ресурсов в вычислительной системе,содержащее и групп поп триггеров в каждой и и групп по и элементов И в каждой, причем х-й вход 3-йгруппы (где 1. = 1 и; 3 =- 1,р)состояния распределения ресурсов устройства подключен к инФормационному входу х-го триггера -й группы, выход которого подключен к первому входу -го элемента И 3-й группы, о т л ич а ю щ е е с я тем, что, с целью .,увеличения быстродействия устройства.,09900 6оно, содержит и элементов ИЛИ-НЕ, первый и второй триггеры, счетчик, пятьэлементов И и элемент ИЛИ, причемвход запуска устройства подключен кпервому входу первого элемента И, выход которого подключен к входу синхронизации счетчика, к инФормационному входу первого триггера, к инфор мационному входу второго триггера ик входам синхронизации всех триггеров групп, вход синхронизации устройства подключен к второму входу первого элемента И и к первому входу вто рого элемента И, выход которого подключен к входу вычитания единицы счетчика, к вторым входам всех элементов И групп и первым входам третьегои четвертого элементов И, выход треть его элемента И подключен к первомувходу элемента ИЛИ и к входу установки в иОи второго триггера, прямойвыход которого подключен к первомувходу пятого элемента И, выход кото рого подключен к выходу признака наличия тупиковой ситуации устройства,.вход числа процессов которого подключен к инФормационному входу счетчика, выход которого подключен к второ му входу четвертого элемента И, выход которого подключен к второму входу пятого элемента И и к второму входу элемента ИЛИ, выход которого подключен к входу установки в "0" перво го триггера, прямой выход которогоподключен к второму входу второгоэлемента И, инверсный выход первоготриггера подключен к третьему входу,первого элемента И и к третьему вхо ду пятого элемента И, выход -го лемента И 1-й группы подключен к входуустановки в ",0" -го триггера З-йгруппы, прямые выходы триггеров 1-йгруппы подключены соответственно к 45 входам 3-го элемента ИЛИ-НЕ, выходкоторого. подключен к третьим входам1-х элементов И групп с первой по(3-1)-ю, к третьим входам 3-х элементов И групп с Ц+1)-й по и-ю и к 50 (3+1)-му входу третьего элемента И.150990000 7 ОРО О ЮОР ОР УО Составитель В. СмирновТехред М.Дидык Корректор В. Кабапий Редактор О. Головач Заказ 5814/47 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101