Устройство для распределения заданий процессорам Советский патент 1986 года по МПК G06F9/50 

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

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

На чертеже приведена структурная схема устройства.

Устройство содержит триггер 1 запуска, вход 2 запуска устройства, генератор 3 импульсов, элемент И 4, элемент И 5, элемент И 6, элемент 7 задержки, элемент 8 задержки, триггер 9 режима, управляющие входы 10 и 11 режима устройства, триггер 12 управления сдвигом, схема 13 сравнения, триггер 14 записи, элементИ15, элемент И 16, элемент НЕ 17, приоритетные шифраторы 18 и 15, элемент И 20, элемент И 21, триггер 22 вьща- чи, элемент ИЛИ 23, элементы ИЛИ 24 и 25, группу элементов И 26, элемент 27 задержки, элемент И 28, элемент Н 29, коммутатор 30, первый управляющий вход 31 коммутатора 30, второй управляющий вход 32 коммутатора 30, первый информационный вход 33 коммутатора 30, второй информационный вход 34коммутатора 30, первую груп- пу выходов 35 коммутатора 30, вторую группу выходов 36 коммутатора 30, группу регистров 37 хранения, блок 38 элементов И, блок 39 элементов И, регистр 40 сдвига, вход 41- управления сдвигом регистра 40 сдвига, вход 42 сброса регистра 40 сдвига, группу информационных входов 43 регистра 40 сдвига, группу входов 44 сброса регистра 40 сдвига, элемент 45 задержки, элемент 46 задержки , группу элементов И 47, регистр 48 распределения, группу информационных выходов 49 устройства, регистр 50 готовности, группу элементов И 51, группу информационных входов 52 устройства, буферный регистр 53, выход 54 кода ко- личества процессоров буферного ре- гистра 53, выход 55 кода номера за- дачи буферного регистра 53, группу элементов ИЛИ 56, элемент И 57, одно- иибратор 58, элемент ИЛИ 59, группу элементов И 60, регистр 61 готовности, группу одновибраторов 62.

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

5

0

5

0

Исходное состояние устройства характеризуется тем, что триггеры 1, 14, 12 и 22, регистры 40, 61, 53, 50 и 37 установлены в состояние О (не показано). После этого по входам 52 в регистр 50 готовности принимаются . в соответствующие разряды, закрепленные за каждым процессором, сигналы готовности процессоров. По входу 33 поступают заявки, содержащие код номера задачи и код числа потребных для ее решения процессоров, в сопро- вожден:ии сигнала запуска по входу-2.

Работа устройства состоит из двух этапов. На первом этапе из поступающих заявок по входу 33 на коммутатор 30 формируется очередь в группе регистров 37 хранения, число которых определяется числом источников заявок. Одновременно на этом этапе осуществляется отслеживание состояния процессоров. Если процессор свободен, то соответствующий ему разряд в регистре 50 устанавливается в 1, а так как регистр 40 сдвига находится в нулевом состоянии, то на выходе элемента ИЛИ 23 формируется нулевой сигнал, которым через элементы НЕ 17 и ИЛИ 59 открыты элементы И 60. При этом единичные сигналы готовности, зафиксированные в регистре 50, передаются в соответствующие разряды регистра 61 готовности.

Формирование очереди заявок осуществляется следующим образом. Так как регистр 40 сдвига находится в состоянии О, то единичным выходным сигналом элемента НЕ 17 открыты по первым входам элементы И 28 и 29 и первый элемент И 26 группы, а по второму входу - последний элемент И 26. Так как триггер 14 находится в состоянии О, то по третьему входу

открыт элемент И 29, а элемент И 28 закрыт нулевым сигналом с единичного выхода триггера 14. Посредством элементов И 28 и 29 формируется сигнал записи, по которому обеспечивается

передача коммутатором 30 на выходы 35 и 36 и далее на входы первого регистра 37 хранения либо содержимого буферного регистра 53 с входа 34, либо заявки с входа 33 соответственно. По первому импульсу генератора, поступающему через открытые элементы И 4 и И 26 и элемент 27 задержки на вторые входы элементов И 26f и

31

29, обеспечивается запись первой заявки в первый регистр 37.

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

В очередном такте после заполнения последнего регистра 37 (первой поступившей заявкой) начинается второй этап работы устройства.

В зависимости от состояния -триг- гера 9 режима устройство может работать в одном из двух режимов: обслуживание заявок в порядке поступления или обслуживание заявок по круговому циклическому алгоритму. Первому режиму соответствует единичное состоя- , ние триггера 9, устанавливаемого сигналом по входу 11 устройства, а вто-- рому - нулевое, которое устанавливается сигналом по входу 10 устройства.

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

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

46096 .4

распределение с вободных процессоров данной задаче.

Работа устройства в режиме обслуживания в порядке поступления состо- 5 ит в следующем. Триггер 9 режима установлен в состояние 1 сигналом- по входу 11, поступающим в устройство после установки его в исходное состояние.

)0 После заполнения последнего регистра 37 хранения группы по очеред- ному тактовому сигналу с выхода последнего элемента И 26 код числа требуемых процессоров из этого р егистра 5 через открытые элементы блока 38

элемента И единичным сигналом с выхода элемента НЕ 17 по входам 43 пере- дае,тся в регистр 40 сдвига. Через некоторое время, определяемое эле- 20-ментом 27 задержки, в последний регистр 37 группы передается заявка из предпоследнего регистра. Наличие элемента 27 задержки в цепи управления записью в последний регистр 37 группы 25 позволяет обеспечить завершение записи в регистры 40 и 53 до того, как изменится состояние очереди, т.е. до осуществления сдвига заявок в очереди. Исходя из этого выбираются па- эр.раметры элемента 27 задержки. Элемент 46 задержки обеспечивает совмещение моментов появления информации на выходах буферного регистра через элементы И 38 и 39 и тактового сигнала с выхода последнего элемента И 26 группы.

Таким образом, к моменту начала выполнения функции распределения процессоров устройство характеризуется следующим состоянием.

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

После записи кода числа требуемых процессоров в регистр 40 на вькоде элемента ИЛИ 23 уста навливается еди- ничньш потенциал, открьшающий по вторым входам элементы И 15, 16, 5 и 6, 55 по первому - элемент И 20, Нулевым сигналом с выхода элемента НЕ 17 одновременно с этим закрываются элементы И 29, элементы И 26 группы и

40

45

блоки 38 и 39 элементов И, а также снимается единичный сигнал на первом входе элемента ИЛИ 59. Но так как тГ иггер 9 режима установлен в состоя ние 1, то на выходе элемента ШШ 59 поддерживается единичный уровень сигнала. При этом в регистре 61 отслеживается состояние процессоров, что необходимо для распределения процессоров задаче, когда число свободных процессоров меньше потребных. Особенностью функции отслеживания состояния процессоров является то, что перевод процессора из состояния Свободен в состояние Занят может произойти в результате выполнения функции вьзделения процессоров задаче, а освобождение процессора, т.е. перевод его из состояния Занят в состояние Свободен, может произойти в любое время работы устройства. После передачи информации в регистр 40 сдвига единичным сигналом с выхода элемента ИЛИ 23 открывается элемент И 20 и через некоторое время определяемое элементом 45 задержки, устанавливается в состояние 1 через элемент ИЛИ 25 триггер 22 выдачи. Вр,емя задержки элементом 45 оп- ределяется длительностью переходных процессов в элементах И 38, в рег ист ре 40 сдвига и элементе 17. Поэтому параметры элемента 45 задержки выбираются так, чтобы импульс на втором входе элемента И 20 действовал по завершении переходных процессов в элементах И 38, в регистре 40 и элементе 29.

Нулевым сигналом с выхода элемен- та НЕ 17 закрывается последний элемент И 26 и элемент И 29, чем блокируется прием заявки с входа 33. Сигналом с единичного выхода триггера 22 открываются элементы И 51.

Если до момента очередного тактового сигнала генератора 3 импульсов происходит совпадение единичных сигналов в соответствующих элементах И 47, то соответствующие разряды ре- гистра 48 распределения устанавливаются в состояние 1. Перепадами потенциалов запускаются соответствующие, одновибраторы 62 группы, выходные сигналы которых устанавливают в состояние О соответствующие разряды регистров 50 и 40. Одновременно через открытые элементы И 51 устанав

ливаются в состояние О соответствущие разряды регистра 50, а на выходах 49 в соответствующие группы из регистра 53 по выходам 55 передается номер задачи. Таким образом в сооветствующих группах выходов 49 соответствующему процессору выдаются сигнал его выбора и номер задачи для решения, а в регистре 50 готовности соответствующий разряд отражает состояние процессора Занят.

При этом возможны два случая: после установки в состояние О разрядов регистра 40 сдвига общее его. содержимое стало нулевым, в одном либо в нескольких разрядах регистра сдвига сохранились значения 1.

В первом случае на выходе элемента НЕ 17 формируется единичный сигнал:, по которому устанавливается в состояние О триггер 22 выдачи, очередная заявка принимается в первый тррдггер 37 хранения, осуществляется перемещение заявок в регистрах 37, и очередная заявка из последнего регистра 37 хранения рассмотренным способом передается в регистр 40 сдвига.

Во втором случае на выходе элемента ИЛИ 24 удерживается единичный потенциал, которым открыты элементы И 15 и 16 по вторым входам. Так как триггер управления сдвигом находится в состоянии О, то элемент И 16 закрыт, поэтому импульсы с выхода элемента И 4 проходят через элементы И 15 и ШШ 24 на вход 41 управления сдвигом регистра. 40 сдвига. По этому импульсу происходит сдвиг содержимого регистра 40 в сторону старших разрядов . Если нет совпадения единичных сигналов на элементах И 47, то оче- редными тактовыми сигналами производится дальнейший сдвиг информации в регистре 40. При этом сдвиг выполняется до тех пор, пока содержимое регистра сдвига не станет равным нулю. Такое положение может возникнуть либо по завершении одного цикла, если число свободных лроцессоров достаточно для решения задачи, либо, за несколько циклов, в течение которых в регистре 61 готовности происходит отслеживание состояния процессоров.

Режим обслуживания заявок в порядке поступления будет продолжаться.

пока триггер режима не будет установлен в состояние .

Для перевода устройства в режим обслуживания по круговому циклическому алгоритму оно приводится к исходному состоянию, а затем по сигналу с входа 10 триггер 9 режима устанавливается в состояние О.

В этом режиме формирование очереди и отслеживание состояния процес соров до момента передачи первой заявки в регистр 40 сдвига и буферный регистр 53 производится аналогично рассмотренному. Отличие этого режима состоит в том , что до очередного так тового сигнала генератора 3 импульсов в устройстве производится анализ возможности распределения свободных процессоров принятой заявке. При этом, так как на выходе элемента НЕ 17 формируется нулевой сигнал и триггер 9 режима находится в состоянии О, то нулевым сигналом с выхода элемента ИЛИ 59 закрываются элементы И 60, чем фиксируется число свободны процессоров в регистре 61 на момент сравнения. Для сравнения количества потребных процессоров с числом свобоных используется схема 13 сравнения, на первые входы которой подается двоичный код числа потребных процессоров, а на вторые - двоичный код числа свободных процессоров. Если код числа на первом входе больше или равен коду числа на втором, то значени выходного сигнала схемы сравнения равно нулю. Если наоборот, то значение выходного сигнала равно 1.

.Так как число потребных и свободных процессоров представляется пози- ционнь м кодом, то для сравнения их в схеме сравнения необходимо преобразовать позиционные коды в двоичные.

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

Двоичный прямой код с выходов приоритетного шифратора 19 подается на

вторые входы схемы 13 сравнения.

Пусть число потребных процессоров больше свободных. При этом выходной сигнал схемы сравнения равен единице. Этим сигналом закрывается по инверсному входу элемент И 6 и открывается элемент И 5 по третьему входу. Через некоторое время, определяемое элементом 8 задержки, через элемент И 5 устанавливается в состояние 1 триг гер 14 записи и в состояние О - регистр 40 сдвига по входу 42. Величина времени задержки элементом 8 определяется временем переходных процессов . в шифраторе 18 и схеме .

13 сравнения.

Единичным сигналом с выхода элемента НЕ 17 открываются элементы И 26 и 28. Так как триггер 14 установлен в состояние 1, то сигнал

записи формируется элементом И 28. По этому сигналу, поступающему на первый управляющий вход 31 коммута- тора , копия заявки из буферного регистра 53 с выходов 54 и 55 по

входам 34 коммутатора записывается в первый регистр 37 хранения группы с выходов 35 и 36 коммутатора 30. Через некоторое время, определяемое элементом 7 задержки, триггер 14

записи устанавливается в состояние О. Параметры эл-емента 7 задержки выбираются, исходя из длительности, переходных процессов при передаче информации из регистра 53 через коммутатор 30 и в первый регистр 37 хранения группы. Тактовыми сигналами с выходов элементов И 26 происходит перемещение заявок в регистрах 37 аналогично рассмотренному.

Во втором случае, когда число потребных процессоров больше или равно числу.свободных, сигнал с выхоДа Меньше схемы 13 сравнения равен нулю. При этом элемент И 5 закрывается по третьему-входу, а элемент И 6 открывается по инверсному входу. Так как триггер 9 установлен в состояние О, на выходе элемента ИЛИ 23 удерживается единичный сигнал, то импульсами с выхода элемента 8 задержки устанавливается триггер 12 управления сдвигом в состояние 1. Этим самым импульсы сдвига подают

J

ся на вход 41 у11ра ления сдвигом регистра 40 сдвига чере: элементы И 1 и ИЛИ 24. Одновременно единичным сигналом с выхода элемента И 6 устанавливается в состояние 1 чере) элемент ИЛ1-1 25 триггер 22 выдачи,,, В дальнейшем работа устройства аналогична рассмотренной;

По завершении обслуживания всех заявок, находящихся в очереди в регистрах 37 хранения группы, а также заявки в регистре 40 сдвига, перепадом потенциалов в группе элементов ИЛИ 56 и элементе НЕ 17 через элемент И 57 запускается одновибра- тор 62. Сигналом с выхода одновиб- ратора 62 триггер 1 запуска устанавливается в состояние О . I

В дальнейшем, работа устройства

начинается по приходу заявок на вход 33 коммутатора в сопровождении сигнала запуска по входу 2.

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

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

6096

10

клждогсз рех истра хранения группы, кроме последнего, соединена с группой информацр1онных входов последующего регистра хранения гругл1ы, пер5 вый вход каждого элемента И третьей группы, кроме первого, соединен с выходов последующего элемента И этой группы, выход первого элемента ИЛИ соединен с первыми входами первого

О и второго элементов И, выходы элементов И четвертой группы соединены с группой информационных входов регистра распределения, группа выходов регистра сдвига соединена с первыми

5 входами элементов И четвертой группы к с входами первого элемента ИЛИ, группа выходов регистра готовности соединена с вторыми входами элементов И четвертой группы, выходы одно0 вибратора группы соединены с группами входов сброса регистра готовности и регистра сдвига, вторые входы элементов И третьей группы, кроме первого и последнего, соединены с пер5 выми входами первого- и последнего

элементов И третьей группы и с первыми вхо,дами первого и второго блоков элементов И, выход второго элемента И соединен с первым входом второго

0 элемента ИЛИ, первые входы третьего и четвертого элементов И соединены с вторым входом первого элемента И третьей группы и через первый элемент задержки, - с выходом последнего

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

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

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

1 12 4б09Г-.JA

рыми «ходами .э;гомеи гов И HTOpofi труп- устр(,1Йства соединен с и пь, пррвьп и HTOpcn i ВХОД, режима входами триггера режима.

Изобретение относится к вычислительной технике и может быть использовано в. многопроцессорных вычислительных системах. Цель изобретения - повышение быстродействия устройства при обслуживании заявок по круговому циклическому алгоритму. Новым в устройстве является использование шести элементов И, четГ Трех триггеров, генератора импульсов,двух элементов задержки, группы элементов запрета, шифратора, элемента НЕ, приоритетного шифратора, схемы срав-- нения и их связей в устройстве. 1 ил. N3 NU Gfi О СО О5

I Г r oh

tTTZir

i ::: 4 i:--|n I i -TJ

.. ;.J

l-|-i

1|е;-ч - - Ц 7 гМД-

Ц ; ----..., T,,7T ;

Г

r--Q

- (г т

: : ai-r-i I jT -:1-T i bl--l.J

4 - -i ::- i,

;EEt -----I--Редактор Н.Тупица

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

Техред Н.Бонкало Корректор Л.Пилипенко

Заказ 4002/42Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Рау 11ская: наб. , д, 4/5

Производственно-поли рафическое предприятие, г.Ужгород, ул.Проектная, 4