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

3-

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

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

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

Устройство содержит п групп по п триггеров 1 в каждой, где п - число типов ресурсов в системе, первый триггер 2, счетчик 3, второй триггер 4, п элементов ИЛИ-НЕ 5, я групп по п элементов И 6 в каждой, первый 7, второй 8 и третий 9 элементы И, элемент ИЛИ 10, четвертый 11 и пятый 12 элементы И, входы 13 состояния распределения ресурсов устройства, вход 14 запуска, вход 15 синхронизации, вход 16 числа процессов устройства и выход 17 признака наличия тупиковой ситуа11р и устройства,

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

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

Устройство для контроля распределения ресурсов позволяет проанализи- ровать состояние системы на наличие тупиковой ситуации.-Состояние системы однозначно определяется орграфом, наличие цикла в котором свидетельствет о наличии тупика. Орграф можно представить в виде квадратной матрицы связностей.

Устройство реализует алгоритм сокращения дуг, входящих в вершины, из которых не выходит ни одна дуга. Физически новая матрица связностей строится следующим образом (в одном рабочем такте); определяются нулевые строки, и в столбцах с номерами, со

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

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

0 Элементы ИПИ-НЕ 5 предназначены для формирования сигнала о наличии в i-й строке хотя бы одного единичного элемента.

Счетчик 3 предназначен для приема

5 кода числа (1-1), где 1 - количество ресурсов распределенных процессов, функционирующих в системе, а также для подсчета числа тактовых импульсов. Триггер 4 предназначен для фик0 сации сигнала о наличии тупиковой ситуации Элемент ИЛИ 10 предназначен дпя формирования сигнала окончания процедуры контроля. Элемент И 12 предназначен для формирования сигнала о наличии тупиковой ситуации.

Рассмотрим работу устройства на примере анализа состояния вычислительной системы, представленного графом (фиг, 2)

0 Сигнал пуска, поступающий на вход 14 запуска устройства, разрешает по- :ступление синхроимпульса с входа 15 устройства. По передне 1у фронту этого .синхроимпульса происходит, запись ин5 формации о текущем распределении ре- сурсов системы в триггеры 1 и произ- во дится запись в счетчик 3 двоичного кода числа (1-1) в соответствии с графом (фиг. 2). По заднему фронту

5

5 0

ся триггеры 2 и 4 в единичное состояние. В соответствии с графом и его матричным представлением триггеры 1.2.1, 1.2.3, 1.2.4, 1.4.2 устанавливаются в единичное состояние. Эти единичные сигналы подаются на входы элементов ИПИ-НЕ.5.2, 5.3, 5.4, на выходах которых формируются сигналы логического О, а на выходах остальных элементов ИЛИ-НЕ сигналы логической 1. Они подаются на входы всех элементов И. 6, кроме элементов И 6.1.2-6.4.2, 6.1.3-6.4.3, 6.1.4- 6.3о4. По второму синхроимпульсу, 5 который поступает на вторые входы

всех элементов И 6, на выходе элемента И 6.2.1 формируется импульс, который подается на R-вХод триггера 1.2.1 и обнуляет его. Второй синхро-

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

После четвертого импульса на выходе счетчика 3 формируется-двоич- ньй код числа 0. При поступлении пятого импульса на выходе элемента И 11 формируется импульс, который подается на вход элемента ИТИ 10, на выходе которого формируется импульс, сигнализиругадий об окончании анализа, который обнуляет триггер 2, Еди- ничньй сигнал с инверсного выхода триггера 2 подается на вход элемента И 12, на второй вход которого подается единичный сигнал с триггера 4 На выходе элемента И 12 формируется сигнал логической 1, свидетельству о наличии тупиковой ситуации, В случае отсутствия тупиковой ситуации в результате анализа матрица преобразуется в нулевую и на выходе элемента И 9 формируется импульс, обнулякщий триггер 4, а на выходе элмента ИДИ 10 формируется импульс, свидетельствующий об око.нчании анализа и обнуляю1ций триггер 2, Нулевой сигнал с выхода триггера 4 подается на вход элемента И 12, а на выходе 17 устройства будет нулевой сигнал, свидетельствующий об отсутствии тупиковой ситуации.

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

Устройство для контроля распределения ресурсов в вычислительной си- стеме,содержащее п групп по п триггеров в каждой и п групп по п элементов И в каждой, причем i-и вход j-й

группы (где i 1

п;

j 1,...

состояния распределения ресурсов устройства подключен к информационному входу i-ro триггера i-й группы, выход которого подключен к первому входу i-ro элемента И j-й группы, отличающееся тем, что, с целью ;увеличения быстродействия устройства..

15 5099006

оно, содержит п элементов ШИ-НЕ, первый и второй триггеры, счетчик, пять элементов И и элемент ИЛИ, пртгем , вход запуска устройства подключен к первому входу первого элемента И, выход которого подключен к входу синхронизации счетчика, к информационному входу первого триггера, к инфор10 мационному входу второго триггера и к входам синхронизации всех триггеров групп, вход синхронизации устройства подключен к второму входу первого элемента И и к nepBONry входу второго элемента П, выход которого подключен к входу вычитания единицы счетчика, к вторым входам всех элементов И грзшп и первым входам третьего и четвертого элементов И, выход треть20 его элемента И подключен к пepвo гy входу элемента ИПИ и к входу установки в О второго триггера, прямой выход которого подключен к первому входу пятого элемента И, выход кото25 рого подключен к выходу признака наличия тупиковой ситуации устройства, вход числа процессов которого подключен к информационному входу счетчика, выход которого подключен к второ-

30 му входу четвертого элемента И, выход которого подключен к второму входу пятого элемента И и к второ1и:у входу элемента ИПН, выход которого подключен к входу установки в О первоэс го триггера, прямой выход которого подключен к второму входу второго элемента И, инверсный выход первого триггера подключен к третьему входу, первого элемента И и к третьему вхо40 ДУ пятого элемента И, выход i-ro ле. мента И j-й группы подключен к входу

-установки в VO i-ro триггера j-й

группы, прямые выходы триггеров j-й

группы подключены соответственно к

45 входам j-ro элемента 1ШИ-НЕ, выход которого, подключен к третьим входам элементов И групп с первой по ()-H), к третьим входам j-x элементов И групп с (j + 1)-й по п-к и к (j+1)-My входу третьего элемента И.

50

10000 1010 0001 0100

Изобретение относится к области вычислительной техники и может быть использовано для контроля корректности распределения ресурсов. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит N групп по N триггеров 1 в каждой, где N - число типов ресурсов в системе, первый триггер 2, счетчик 3, второй триггер 4, N элементов ИЛИ-НЕ 5, N групп по N элементов И 6 в каждой, первый 7, второй 8 и третий 9 элементы И, элемент ИЛИ 10, четвертый 11 и пятый 12 элементы И, входы 13 состояния распределения ресурсов устройства, вход 14 запуска устройства, вход 15 синхронизации устройства, вход 16 числа процессов устройства, выход 17 признака наличия тупиковой ситуации устройства. 2 ил.

ие.2