Устройство для распределения заданий

 

УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ, содержащее первый элемент ИЛИ, первую группу блоков элементов И, первую группу элементов ИЛИ, регистр готовности процессоров и блок управления , блок управления содержит регистр сдвига и первый элемент ИЛИ, выходы регистра готовности процессоров соединены с первой группой информационных входов блока управления, вторая группа информационных входов которого соединена с первой группой кодовых входов устройства, выходы регистра сдвига блока управления соединены с входами элемента ИЛИ и с первыми входами блоков элементов И первой группы , вторые входы которых соединены с выходами регистра готовности процессоров, выходы блоков элементов И первой группы соединены с входами одноименных элементов ИЛИ первой группы и с первой группой информационных выходов устройства, выходы элементов ИЛИ первой группы соединены с входами сброса регистра готовности процессоров, отличающееся тем, что, с целью повышения быстродействия, устройство содержит два элемента ИЛИ, элемент НЕ, элемент ЗАПРЕТ, вторую и третью группы элементов ИЛИ, группу элементов И, вторую группу блоков элементов И, матрицу блоков элементов И (по К блоков в каждой строке), две матрицы регистров (по К регистров в каждой строке); матрицу схем сравнения (по К схем сравнения в каждой строке, где К - количество заданий в системе ), две группы регистров и группу схем сравнения, причем первые группы входов всех схем сравнения группы подсоединены к выходам одноименных регистров второй группы, входы которых связаны с второй группой кодовых входов устройства, вторые группы входов схем сравнения группы соединены с выходами одноименных регистров второй группы, входы которых соединены с выходами одноименных блоков элемента И первой группы, выходы каждого регистра второй группы соединены с группой входов одноименных элементов И второй группы , выходы схем сравнения группы соединены с входами первого элемента ИЛИ, выход которого подсоединен к запрещающему входу элемента ЗАПРЕТ и к первым входам элементов И группы, первые группы входов каждой схемы сравнения каждого i столбца матрицы схем сравнения подсоединены к выходам одноименных регистров (Л одноименного столбца первой матрицы, к входам регистров первой матрицы подключена группа информационных входов устройства , выходы схем сравнения каждой строки матрицы схем сравнения соединены с входами одноименного элемента ИЛИ третьей группы, выходы которого соединены с входами второго элемента ИЛИ и вторыми входами соответствующих элементов И группы, выходы элементов И группы подсоесо динены к управляющим входам соответствующих блоков элементов И второй груп00 пы, к выходам второй группы информацион4; ных выходов устройства и к первым входам соответствующих элементов ИЛИ второй группы, выходы блоков элементов И второй группы соединены с третьей группой информационных выходов устройства, второй вход каждого элемента ИЛИ второй группы подсоединен к соответствующему входу группы сигнальных входов устройства , выход каждого элемента ИЛИ второй группы подсоединен к единичному входу одноименного разряда регистра готовности процессоров, к входу сброса одноименного регистра второй группы и к входам сброса регистров одноименной строки второй мат

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

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

РЕСПУБЛИК

1si)4 G 06 F 9/46, 9/00

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3718534/24-24 (22) 27.03.84 (46) 15.09.85. Бюл. № 34 (72) А. Х. Ганитулин и В. Г, Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР № 468240, кл. G 06 F 9/00, 1972.

Авторское свидетельство СССР № 629538, кл. G 06 F 9/00, 1978. (54) (57) УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ, содержащее первый элемент ИЛИ, первую группу блоков элементов И, первую группу элементов ИЛИ, регистр готовности процессоров и блок управления, блок управления содержит регистр сдвига и первый элемент ИЛИ, выходы регистра готовности процессоров соединены с первой группой информационных входов блока управления, вторая группа информационных входов которого соединена с первой группой кодовых входов устройства, выходы регистра сдвига блока управления соединены с входами элемента ИЛИ и с первыми входами блоков элементов И первой группы, вторые входы которых соединены с выходами регистра готовности процессоров, выходы блоков элементов И первой группы соединены с входами одноименных элементов ИЛИ первой группы и с первой группой информационных выходов устройства, выходы элементов ИЛИ первой группы соединены с входами сброса регистра готовности процессоров, отличающееся тем, что, с целью повышения быстродействия, устройство содержит два элемента ИЛИ, элемент НЕ, элемент ЗАПРЕТ, вторую и третью группы элементов ИЛИ, группу элементов И, вторую группу блоков элементов И, матрицу блоков элементов И (по К блоков в каждой строке), две матрицы регистров (по К регистров в каждой строке); матрицу схем сравнения (по К схем сравнения в каждой строке, где К вЂ” количество заданий в системе), две группы регистров и группу схем сравнения, причем первые группы входов

„„SU„„1179340 А всех схем сравнения группы подсоединены к выходам одноименных регистров второй группы, входы которых связаны с второй группой кодовых входов устройства, вторые группы входов схем сравнения группы соединены с выходами одноименных регистров второй группы, входы которых соединены с выходами одноименных блоков элемента И первой группы, выходы каждого регистра второй группы соединены с группой входов одноименных элементов И второй группы, выходы схем сравнения группы соединены с входами первого элемента ИЛИ, выход которого подсоединен к запрещающему входу элемента ЗАПРЕТ и к первым входам элементов И группы, первые группы входов каждой схемы сравнения каждого столбца матрицы схем сравнения подсое- Я динены к выходам одноименных регистров одноименного столбца первой матрицы, к входам регистров первой матрицы подключена группа ннформадноннмх входов устройства, выходы схем сравнения каждой строки матрицы схем сравнения соединены с входами одноименного элемента ИЛИ третьей группы, выходы которого соединены с входами второго элемента ИЛИ и вторыми входами соответствующих элементов И группы, выходы элементов H группы подсое- 3 динены к управляющим входам соответ- (© ствующих блоков элементов И второй груп- фф пы, к выходам второй группы информацион- р ных выходов устройства и к первым входам соответствующих элементов ИЛИ вто- C рой группы, выходы блоков элементов И второй группы соединены с третьей группой информационных выходов устройства, второй вход каждого элемента ИЛИ второй группы подсоединен к соответствующему входу группы сигнальных входов устройства, выход каждого элемента ИЛИ второй группы подсоединен к единичному входу одноименного разряда регистра готовности процессоров, к входу сброса одноименного регистра второй группы и к входам сброса регистров одноименной строки второй мат1 179340

10 рицы регистров, выход первого элемента

ИЛИ соединен с входом элемента НЕ и информационным входом элемента ЗАПРЕТ, выход элемента НЕ подсоединен к третьим входам блоков элементов И первой группы и к первым входам блоков элементов И матрицы, выход каждого разряда регистра готовности соединен с вторыми входами каждого блока элементов И одноименной строки матрицы, выход каждого разряда регистра сдвига блока управления соединен с третьими входами блоков элементов И одноименной строки матрицы, группы входов каждого блока элементов И каждого столбца матрицы блоков элементов И подсоединены к выходам регистров одноименного столбца первой матрицы, выход каждого блока элементов И каждого столбца матрицы блоков элементов И подсоединен к четвертой группе информационных выходов устройства и к группам входов каждого регистра одноименного столбца второй матрицы регистров, группа выходов каждого регистра первой группы соединена с группой входов одноименного блока элементов И первой группы, блок управления содержит регистр, приоритетный шифратор, группу элементов И, группу элементов ИЛИ, сумматор, второй, третий элементы ИЛИ, три элемента НЕ, три элемента И, элемент задержки, триггер, дешифратор, генератор импульсов, одновибратор, причем первая группа информационных входов блока управления соединена с группой входов регистра, вторая группа информационных входов блока управления соединена с входом приоритетного шифратора, группа выходов которого соединена с первой группой входов сумматора, вторая группа входов которого соединена с группой инверсных выходов регистра, прямые выходы которого соединены с входами дешифратора и с входами второго элемента ИЛИ блока управления, выход которого соединен с первыми вхоИзобретение относится к вычислительной технике и может найти применение в многопроцессорных системах для организации совместного использования системных ресурсов при выполнении заданий.

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

На фиг. 1 показана структурная схема предлагаемого устройства; на фиг. 2 — структурная схема блока управления.

Устройство (фиг. 1) содержит блок управления 1, регистр 2 готовности процессодами первого и второго элементов И, выход сигнала отказ устройства соединен с выходом первого элемента И блока управления, второй вход первого элемента И соединен с выходом первого элемента ИЛИ блока управления, второй вход первого элемента ИЛИ блока управления соединен с выходом знакового разряда сумматора, выход первого элемента НЕ блока управления через элемент задержки соединен с вторым входом второго элемента И блока управления, выход знакового разряда сумматора через второй элемент HE соединен с третьим входом второго элемента И, выход которого соединен с единичным входом триггера, выход которого соединен с входом одновибратора и с первым входом третьего элемента И, второй вход и выход которого соединены соответственно с выходом генератора импульсов и с входом управления регистра сдвига, выходы которого соединены с входами третьего элемента ИЛИ, выход которого через третий элемент НЕ соединен с входом сброса триггера, выход одновибратора соединен с первыми входами элементов И группы блока управления, выходы которых соединены с входами регистра сдвига, первый выход дешифратора соединен с вторым входом первого элемента

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

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

l5

20 ды 23 блока 1, группу сигнальных входов

24 устройства, группу информационных выходов 25 устройства, группу информационных выходов 26 устройства, группу информационных выходов 27 устройства, группу информационных входов 28 устройства, группу информационных выходов 29 устройства, группу кодовых входов 30 устройства, группу кодовых входов 31 устройства.

Блок 1 управления (фиг. 2) содержит приоритетный шифратор 32, группу элементов ИЛИ 33, генератор 34 импульсов, сумматор 35, элемент ИЛИ 36, элемент

И 37, элемент ИЛИ 38, элемент НЕ 39, дешифратор 40, группу элементов И 41, регистр сдвига 42, элемент НЕ 43, элемент задержки 44, элемент И 45, триггер 46, одновибратор 47, элемент И 48, элемент

НЕ 49, элемент ИЛИ 50, регистр 51.

Устройство работает следующим образом.

Исходное состояние устройства характеризуется тем, что в начале работы всей вычислительной системы в состояние «О» устанавливаются регистры 11, регистры 12 матрицы, регистры 14 матрицы, регистры 17 группы, регистр 2, триггер 46, регистр сдвига 42, регистр 51.

Пусть на вход устройства поступают задания, состояшие из последовательности шагов, имеющих те же номера, что и все задание. Каждый шаг задания может выдавать запросы на дополнительные ресурсы.

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

На первом этапе работы устройства по группе входов 31 в регистр 51 блока управления 1 поступает код числа необходимых для выполнения задания процессоров. По группе входов 24 через вторую группу элементов ИЛИ 3 в регистр 2 готовности процессоров поступают сигналы о готовности процессоров. В блоке управления

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

Преобразование позиционного кода в двоичный производится посредством шифратора 32.

В сумматоре 35 производится сравнение кодов числа требуемых и свободных процессоров. На первые входы сумматора 35 число

Зо

55 требуемых процессоров для выполнения задания поступает в обратном коде, а на вторые входы — число свободных процессоров — в прямом.

Сложение чисел в сумматоре 35 производится в обратных кодах. Если число требуемых процессоров больше или равно числу свободных, то значение знакового разряда сумматора 35 равно нулю, в противном случае, если число требуемых процессоров меньше числа свободных, значение знакового разряда сумматора равно единице.

Если число свободных процессоров меньше количества потребных, то единичным сигналам с выхода знакового разряда сумматора 35 через элемент ИЛИ 38 и с выхода элемента ИЛИ 36 формируется сигнал

«Отказ» элементом И 37, поступающий на выход 20, уведомляющий о невозможности выполнения задания из-за отсутствия свободных процессоров.

Одновременно с поступлением кода по входу 31 в устройство выдаются код номера задания по группе входов 30 в регистры 17 и далее на первые входы схем сравнения 16, а по группе входов 28 в регистры 14 — коды номеров ресурсов, необходимых для выполнения задания, и далее — на первые входы схем сравнения 13.

На регистрах 11 хранятся коды номеров задания, назначенных на соответствующие процессоры при предшествующих циклах работы устройства. На регистрах 12 каждой строки .матрицы регистров хранятся номера ресурсов, закрепленных за одноименным процессором, таким образом, в регистре 12 каждой строки матрицы регистров хранится номер занятого ресурса. Схемы сравнения

13 сравнивают коды занятых и потребных для выполнения поступившего задания ресурсов и, если имеется равенство кодов хотя бы в одной схеме сравнения, вырабатывается сигнал, который через элементы

ИЛИ 9 и 7 подается на информационный вход элемента запрета 6.

Схемы сравнения 16 сравнивают номера заданий, реализуемых вычислительной системой, с номером поступившего задания.

Если совпадение не выявлено ни одной схемой сравнения 16, сигнал на запрещающий вход элемента запрета 6 не выдается, единичный сигнал с выхода элемента запрета 6 поступает на вход 22 блока управления 1.

При этом на входе элемента ИЛИ 38 и на выходе 20 устройства появляется сигнал «Отказ», уведомляющий о невозможности выполнения задания из-за отсутствия свободного ресурса вычислительной системы.

Если в системе имеется хотя бы один процессор, выполняющий задание, номер которого равен номеру поступившего, на выходе одной из схем сравнения 16 появится .сигнал. При этом с выхода элемента ИЛИ 19

1 179340 подается сигнал, запрещающий прохождение сигнала на вход 22 блока управления 1.

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

Если некоторый ресурс, необходимый для выполнения задания, занят, то одна из схем сравнения 13 матрицы выдает сигнал, который через один из элементов ИЛИ 9 поступает на вход элемента И 10. Так как элементы И 10 открыты по управляющему входу единичным сигналом с выхода элемента ИЛИ 19, то единичный сигнал появляется на выходе одного из элементов

И 10, а затем — на соответствующем выходе группы выходов 26. Этот сигнал используется в вычислительной системе для прерывания работы процессора. Одновременно сигнал с выхода элемента И 10 поступает и на вход блоков элементов И 15, разрешая выдачу номера задания по выходам 27 регистра 1 1 в систему организации возврата к прерванным вычислениям.

Через некоторое время, обусловленное задержкой в прохождении сигнала через элемент ИЛИ 3, появляется сигнал на соответствующем единичном входе регистра 2, на входе сброса соответствующего регистра 11 и на входах сброса регистров 12 соответствующей строки матрицы регистров, обеспечивая освобождение занятых ресурсов.

Описанный процесс освобождения ресурсов выполняется параллельно для всех процессоров, захвативших необходимый ресурс.

По его окончании появляется разрешающий сигнал на входе элемента НЕ 8 и на выходе элемента НЕ 43, который через определенное время, обусловленное задержкой в элементе задержки 44, устанавливает триггер 46 в единичное состояние. Это означает, что данное задание обеспечено всеми необходимыми ресурсами и его можно допустить для выполнения в вычислительную систему. В этом случае выполняется третий этап устранения тупиковых ситуаций, Особенности его выполнения состоят в следующем.

При установки триггера 46 в единичное состояние перепад напряжения на единичном выходе триггера дифференцируется одновибратором 47. Импульсом с выхода одновибратора 47 разрешается передача ко5

50 да с выхода дешифратора 40 через группу элементов ИЛИ 33 и группу элементов

И 41 в регистр сдвига 42. При этом производится преобразование двоичного кода числа потребных процессоров, содержащегося в регистре 51, в позиционный следующим образом.

Пусть число потребных процессоров равно 3, при этом двоичный код в регистре 51 равен 01 1.

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

Этот код передается в регистр сдвига 42 по импульсу одновибратора 47 через элементы И 41. После записи кода в регистр сдвига 42 на выходах блоков элементов

И 18, находящихся в определенных строках матрицы, появляются сигналы кодов номера ресурса, а на выходах соответствующих блоков элементов И 4 — код номера задания. Номер блоков элементов И 4 и строки матрицы блоков элементов И 18 определяется совпадением единичных разрядов в регистре 2 и регистре сдвига 42. С выхода выбранного блока элементов И 4 код номера задания выдается по соответствующим выходам группы выходов 25 на процессоры и регистр 11, а через элементы ИЛИ 5 устанавливает в «О» соответствующие разряды регистра 2. С выходов выбранной строки матрицы блоков элементов И 18 коды номеров ресурсов выдаются через соответствующие выходы группы выходов 29 в процессоры и в соответствующую строку матрицы регистров 2 для закрепления за данным заданием. Если при этом в регистре 42 сдвига остались единичные разряды, о чем свидетельствует сигнал на выходе элемента ИЛИ 50, то триггер 46 остается в единичном состоянии.

В этом случае импульсы сдвига, вырабатываемые генератором 34 импульсов, поступают через элемент И 48 на вход сдвига влево регистра 42. Время задержки генератора выбирается так, чтобы его импульсы воздействовали на состояние регистра сдвига 42 после приема в него кода по импульсу с элемента 47 по окончании установки триггера 46 в единичное состояние. После определенного количества сдвигов кода в регистре 42 все его разряды обнуляются. При этом сигнал с выхода элемента ИЛИ 50 снимается, а на выходе элемента НЕ 49 появляется сигнал, устанавливающий триггер 46 в нулевое состояние. Это означает, что заданию выделено необходимое количество процессоров и других ресурсов вычислительной системы.

1 179340

1.! 79340

Редактор С. Тимохина

Заказ 5677/51

Составитель М. Кудряшев

Техред И. Верес Корректор М. Самборская

Тираж 710 Подписное

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

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4