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

 

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

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

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

РЕСПУБЛИК с% 4 G 06 F 11 00 й-" " ",. Д" 4 ) P

ti . .: Mic, L .:.:;,Е

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

i;A

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

1 (21) 4400181/24-24 (22) 29.03.88 (46) 23.09.89. Бюл. № 35 (72) С.Н. Ткаченко, В.В. Герасименко, Г.Н. Тимонькин, В.С. Харченко и С.В. Хотименко (53) 681.325(088.8) (56) Авторское свидетельство СССР № 1015385, кл. С 06 F 11/00, 1982.

Авторское свидетельство СССР № 1252791, кл. G 06 F 15/20, 1985.

I (54) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ВЫЧИСЛИТЕЛЬНОЙ

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

ÄÄSUÄÄ 1509 О А1

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

3 15099

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

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

На фиг. 1 представлена схема устройства для контроля распределения ресурсов в вычислительной системе; 10 на фиг. 2 — пример графа связности распределенных ресурсов л соответствующая ему матрица связностей, Устройство содержит и групп по и триггеров 1 в каждой, где n — число 15 типов ресурсов в системе, первый триггер 2, счетчик 3, второй триггер 4, и элементов ИЛИ-НЕ 5, и групп по и элементов И 6 в каждой, первый

7, второй 8 и третий 9 элементы И, 20 элемент ИЛИ 10, четвертый 11 и пятый

12 элементы И, входы 13 состояния распределения ресурсов устройства, вход 14 запуска, вход 15 синхронизации, вход 16 числа процессов устройства и выход 17 признака наличия тупиковой ситуации устройства.

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

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

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

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

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

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

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

Сигнал пуска, поступающий на вход

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

1граАом (фиг. 2). По заднему Аронту этого синхроимпульса устанавливаются триггеры 2 и 4 в единичное состояние. В соответствии с графом и его матричным представлением триггеры

1.2.1, 1 ° 2.3, 1.2.4, 1.4.2 устанавливаются в единичное состояние ° Эти единичные сигналы подаются на входы элементов ИЛИ-HE.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, на выходе элемента И 6 ° 2.1 формируется импульс, который подается íà R-вход триггера 1,2.1 и обнуляет его. Второй синхро5 15 импульс также подается на счетный вход счетчика 3, из содержимого которого вычитается единица. Аналогично работает устройство и на следующих тактах.

После четвертого импульса на выходе счетчика 3 формируется двоичный код числа О. При поступлении пятого импульса на выходе элемента

И 11 формируется импульс, который подается на вход элемента ИЛИ 10, на выходе которого формируется импульс, сигнализирующий об окончании анализа, который обнуляет триггер 2, Единичный сигнал с инверсного выхода триггера 2 подается на вход элемента И 12 на .второй вход которого подается единичный сигнал с триггера 4.

На выходе элемента И 12 формируется сигнал логической 1, свидетельствующий о наличии тупиковой ситуа щи.

В случае отсутствия тупиковой ситуации в результате анализа матрица преобразуется в нулевую и на выходе элемента И 9 формируется импульс, обнуляющий триггер 4, а на выходе элемента ИЛИ 10 формируется импульс, свидетельствующий об окончании анализа и обнуляющий триггер 2. Нулевой сигнал с выхода триггера 4 подается на вход элемента И 12, а на выходе

17 устройства будет нулевой сигнал, свидетельствующий об отсутствии тупиковой ситуации. формула изо бретения

Устройство для контроля распределения ресурсов в вычислительной системе,содержащее и групп поп триггеров в каждой и п групп по и элементов И в каждой, причем i-й вход j-й группы (где i = 1,..., и; j =- 1,. ° ep) состояния распределения ресурсов устройства подключен к информационному входу i-го триггера i-й группы, выход .которого подключен к первому входу

i-го элемента И j-й группы, о т л ич а ю щ е е с я тем, что, с целью ,увеличения быстродействия устройства, 09900 6 оно, содержит и элементов ИЛИ-НЕ, первый и второй триггеры, счетчик, пять элементов И и элемент ИЛИ, причем вход запуска устройства подключен к первому входу первого элемента И, выход которого подключен к входу синхронизации счетчика, к информационному входу первого триггера, к инфор1р мационному входу второго триггера и к входам синхронизации всех триггеров групп, вход синхронизации устройства подключен к второму входу первого элемента И и к первому входу Вто»

15 рого элемента И, выход которого подключен к входу вычитания единицы счетчика, к вторым входам всех элементов И групп и первым входам третьего и четвертого элементов И, выход треть20 его элемента И подключен к первому входу элемента ИЛИ и к входу установки в "Ои второго триггера, прямой выход которого подключен к первому входу пятого элемента И, выход кото25 рого подключен к выходу признака наличия тупиковой ситуации устройства, .вход числа процессов которого подключен к информационному входу счетчика, выход которого подключен к второ30 му входу четвертого элемента И. выход которого подключен к второму входу пятого элемента И и к второму входу элемента ИЛИ, выход которого подключен к входу установки в "0 перво35 го триггера, прямой выход которого подключен к второму входу второго элемента И, инверсный выход первого триггера подключен к третьему входу, первого элемента И и к третьему вхоqp ду пятого элемента И, выход i-ro лемента И j-й группы подключен к входу установки в ",0" i-го триггера j-й группы, прямые выходы триггеров 1-й группы подключены соответственно к

45 входам j-ro элемента ИЛИ-НЕ, выход которого. подключен к третьим входам

j x элементов И групп с первой по (j-1)-ю, к третьим входам j-х элементов И групп с (j+1)-й по и-ю и к

5р (j+1)-му входу третьего элемента И.

1509900 обои

1 010

0 001

0f У0

Составитель В. Смирнов

Техред М.Дидык Корректор В. Ка барий

Редактор О. Головач

Заказ 5814/47 Тираж 668 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101