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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 46 51)5 6 НИЕ ИЗОБРЕТЕНИ СВИДЕТЕЛЬСТВУ вторСк тельных систем, Цель изобретения - увеличение быстродействия устройства, Цель достигается введением в устройство групп элементов И-НЕ, НЕ, триггеров, элементов задержки, схем сравнения, мультиплексора, элемента ИЛИ - НЕ, Устройство позволяет при поиске процессора для решения задачи определенного типа исключить необходимость начинать обход всегда с первого и обходить все (включая и занятые) процессоры, а также обеспечивает возможность по ходу работы(беэ дополнительных процедур) выявлять номер процессора, решающего наименее приоритетную задачу определенного типа. 1 ил.(54) УСТРОЙСТВО Д ЗАДАНИЙ ПРОЦЕС (57) Изобретение от ной технике и может построении многоп ЛЯ РАСПРЕОРАМоситсяыть исоцессо ЕНИЯ к вычислительпользовано при рных вычислишифратор, группы элементов И, блоки элементов И, группы элементов ИЛИ, элементы ИЛИ, схемы сравнения, генератор импульсов, элементы И, триггер, элементы задержки, блок элементов задержки, сигнальный выход устройства.Однако данное устройство обладает недостаточным быстродействием.Недостаточное быстродействие обусловлено тем, что независимо от прочих обстоятельств (например, готовности процессоров) и ри очередном расп редел ении всегда осуществляется обиход процессоров, начиная с первого.Цель изобретения - увеличение быстродействия устройства за счет обхода только готовых к работе процессоров и исключения необходимости составления списка упорядоченных приоритетов,Поставленная цель достигается тем, что в устройство для распределения заданий процессорам, содержащее регистр готовноОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР(56) Авторское свидетельство СССРМ 913377, кл, 6 06 Е 9/00, 1980.Авторское свидетельство СССРМ 1453406, кл. 6 06 Г 9/46, 1989,Изобретение относится к вычислительной технике и может быть использовано припостроении многопроцессорных вычислительных систем.Известно устройство для распределения заданий процессорам.Однако известное устройство не обеспечивает приоритетную обработку входящих заданий,Наиболее близим к изобретению потехнической сущности является устройстводля распределения заданий процессорам,содержащее группу входов приоритета задания, группу сигнальных входов, группувходов номера задания, запросный вход,регистр готовности процессоров, регистрприоритета задания, регистр адреса записиприоритета задания, блок памяти приоритетов заданий, блок памяти упорядоченных приоритетов заданий, блок памятиномеров заданий, узел сортировки информации, два блока управления, дешифратор,1711162 А 1сти процессоров, регистр приоритета заданий, регистр номера задания, дешифратор,блок памяти номеров процсссоров, блок памяти приоритетов заданий, блок памятисписков заданий процессоров, схему сравнения, группу блоков элементов И, группуэлементов задержки, генератор импульсов,два элемента ИЛИ, элемент задержки, элемент И, причем группа информационныхвходов регистра готовности процессоров 10соединена с группой сигнальных входов устройства, группа входов номера задания устройства соединена с информационнымивходами регистра номера задания, выходыкоторого соединены с информационными 15входами дешифратора и блоков элементовИ группы, группа входов приоритета задания устройства соединена с информационными входами регистра приоритетазаданий, выходы которого соединены с второй группой входов схемы сравнения, первая группа входов которой соединена синформационным выходом блока памятиприоритетов заданий, выход генератора импульсов соединен с вторым входом элемента И, введены группа элементов И - НЕ,группа элементов НЕ, группа триггеров,груп а схем сравнения, мультиплексор,первый и второй блоки элементов И, элемент ИЛИ-НЕ, второй элемент И, элемент 30НЕ, причем входы 1-го элемента И-НЕ соединены соответственно с 1-м выходом регистра готовности процессоров, с выходомэлемента И и с входом управления схемысравнения, с выходом 1-го элемента задер-. 35жки, с выходами всех предшествующихэлементов И-НЕ группы, вход 1-го элемента НЕ группы соединен с выходом 1-го элемента И-НЕ, выход 1-го эл мента НЕгруппы соединен с входом установки в "1" 401-го триггера, с+м адресным входом блокапамяти списков заданий процессорам, с соответствующим входом первой группы ин-формационных входов мультиплексора, синформационным входом соответствующего элемента И первого блока, с соответствующим входом элемента ИЛИ - НЕ, выходкоторого соединен с входами установки в"0" триггеров группы и с вторым входомвторого элемента И, первый вход которого 50соединен с выходом элемента НЕ, вход которого соединен с выходом первого элемента ИЛИ и с первыми управляющимивходами мультиплексора и элементов Ипервоо и второго блоков, инверсный выход 551-о триггера соединен с входом 1-го элемента задержки группы, входы первого элемента ИЛИ соединены с выходами схемсравнения группы, первые и вторые группыинформационных входов которых соединены с определенными информационными выходами блока памяти списков заданий и процессора и с информационными выходами регистра номера задания соответственно, третий вход второго элемента И соединен с первым выходом схемы сравнения, второй выход которой соединен с вторыми управляющими входами элементов И первого и второго блоков, информационные входы второго блока элементов И соединены с выходом регистра приоритета заданий, выходы первого и второго блоков элементов И соединены с входами записи блока памяти номеров процессоров и блока памяти приоритетов заданий соответственно, первый выход дешифратора соединен с первым входом элемента И, другие выходы дешифратора соединены с соответствующими адресными входами блока памяти номеров процессоров и блока памяти приоритетов заданий, выход второго элемента И соединен с вторым управляющим, входом мультиплексора, вторая группа информационных входов которого соединена с информационными выходами блока памяти номеров процессоров, выходы мультиплексора являются сигнальными выходами устройства и соединены соответственно с управляющими входами блоков элементов И группы и с входами второго элемента ИЛИ, выход которого соединен с входом элемента задержки, выход которого соединен с входами установки в "0" регистра приоритета заданий и регистра номера заданий, входы установки в "0" разрядов регистра готовности процессоров соединены с соответствующими входами группы ответных входов устройства, выходы блоков элементов И группы являются информационными выходами устройства,На чертеже представлена функциональная схема предлагаемого устройства для распределения заданий процессорам,Устройство содержит группу 1 сигнальных входов устройства, группу 2 входов приоритета заданий устройства, группу 3 входов номера задания устройства, регистр 4 готовности процессоров, регистр 5 приоритета заданий, регистр 6 номера задания, дешифратор 7, генератор 8 импульсов, элемент И 9, блок 10 памяти номеров процессоров, блок 11 памяти приоритетов заданий, схему 12 сравнения, группу элементов И - НЕ 13, группу элементов НЕ 14, группу трииггеров 15, блок 16 памяти списков заданий процессорам, группу схем 17 сравнения, первый элемент ИЛИ 18, мультиплексор 19, группу 20 сигнальных выходов устройства, группу блоков 21 элементов И, группы 22 информационных выходов510 15 20 25 3035 40 45 50 55 устройства. первый 23 и второй 24 блоки элементов И, второй элемент ИЛИ 25, элемент ИЛИ-НЕ 26, элемент НЕ 27. второй элемент И 28, группу элементов 29 задержки, элемент 30 задержки, группу 31 ответных входов устройства,Сущность изобретения заключается в следующем.Введение групп элементов И - НЕ, НЕ и группы триггеров позволяет избежать при очередном распределении перебора всех (включая и занятые) процессоров, начиная с первого, В предлагаемом устройстве анализируются возможности только отовых (свободных от решения задач) процессоров. Изменение порядка хранения информации о приоритетах, номерах заданий и номерах процессоров в блоках памяти и введение группы схем сравнения ускоряет процесс снятия задания с малым приоритетом с обслуживания с последующей передачей освобожденного процессора для реализации более приоритетного задания,Устройство работает следующим образом,В исходном состоянии регистры 4 - 6 и триггеры 15 обнулены; в блок 16 памяти списков заданий процессорам в каждую из строк занесен список номеров заданий, выполняемых соответствующим процессором, во все разряды всех строк блока 11 памяти приоритетов заданий занесены "1" (цепи установки в исходное состояние не показаны),По входам 1 по мере выполнения ранее принятых на обработку заданий от процессоров поступают сигналы готовности и записываются в соответствующие разряды регистра 4,От пользователей по входам 3 поступает информация о номере задания,Данная информация состоит как бы из двух групп разрядов; первая группа указывает номер пользователя (абонента), вторая - номер задачи, характеризующий ее тип (один пользователь обладает правом на решение задач нескольких типов). По входам 2 одновременно с номером задания пользователь выставляет приоритет задания (задачи одного типа у разных пользователей при различных условиях обстановки могут иметь различные приоритеты). Значение приоритета принимается в регистр 5, а номер задания - в регистр 6,Как только в регистре 6 окажется информация, отличная от нулевой, на первом выходе дешифратора 7 сформируется сигнал единичного уровня, который поступает на первый вход элемента И 9. Тактовые импульсы с выхода генератора 8 через элемент И 9 начинают поступать на управляющий вход схемы 12 сравнения и на соответствующие входы элементов И - НЕ 13 группы.Сигналы нулевого уровня могли бы появиться на выходе любого из элементов ИНЕ 13, которым соответствуют единичные значения разрядов регистра 4, с приходом очередного тактового импульса. Однако сигнал нулевого уровня появится на выходе только одного элемента И - НЕ 13, которому соответствует младший из разрядов регистра 4, находящийся в единичном состоянии, Допустим, это 1-й разряд. Сигнал нулевого уровня с выхода 1-го элемента И - НЕ 13, поступая на входы всех последующихэлементов И - НЕ 13 группы, блокирует возможность появления на их выходах сигналов нулевого уровня. Сигнал нулевого уровня с выхода 1-го элемента И - НЕ 13 поступает на вход 1-го элемента НЕ 14, Сигналединичного уровня с выхода 1-го элемента 14 НЕ поступает на соответствующий адресный вход блока 16 памяти списков заданий и на вход установки в "1" 1-го триггера 15. С переходом 1-го триггера 15в "1" сигнал нулевого уровня с его инверсного выхода поступает на вход 1-го элемента 29 задержки группы и через него на один из входов 1-го элемента И-НЕ 13, где блокирует возможность повторного появления сигнала нулевого уровня на его выходе.Задержка элементов 29 выбирается достаточной для выполнения устройством своих функций, но меньшей, нежели период следования тактовых импульсов генератора 8.С приходом сигнала единичного уровня на адресный вход блока 16 производится считывание строки информации, содержащей список типов задач, выполняемых 1-м процессором. Размер строки определяетсямаксимальным количеством типов задач, решаемых одним ггроцессором. (Например, процессор способен решать задачи 15 типов, Строка должна содержать 15 групп по четыре разряда - 60 разрядов).Если какой-то из процессоров решает меньший круг задач, то соответствующие группы разрядов строки должны содержать нулевую информацию. Информация считанной строки по группам разрядов передаетсяна первые входы соответствующих схем 17 сравнения группы. На вторые входы всех . схем 17 сравнения группы поступает информация о типе задачи с выхода регистра 6номера задания.Сигналы с выходов элементов НЕ 14группы поступают на первую группу информационных входов мультиплексора 19 и наинформационные входы первого 23 блока элементов И. Данные сигналы образуютунитарный распределенный код, который является номером процессора, опрашиваемого в данном такте. Код приоритета с выхода регистра 5 приоритета заданий поступает на информационные входы второго блока 24 элементов И и на вторую группу информационных входов схемы 12 сравнения. Информация о номере задачи с выхода регистра б поступает на вход дешифратора 7,Сигналы с выхода дешифратора 7 поступают на адресные входы блока 10 памяти номеров процессоров и блока 11 памяти приоритетов заданий, Происходит обращение к ячейкам памяти, соответствующим номеру задачи. Из блока 11 памяти приоритетов заданий считывается информация о. приоритете задачи данного типа, решаемой ранее, и передается на первую группу информационных входов схемы 12 сравнения, Если приоритет вновь поступившей задачи меньше приоритета задачи, решаемой ранее, то сигнал единичного уровня формируется на первом выходе схемы 12 сравнения.Если -й процессор не приспособлен к решению задачи, укаэанного пользователем типа, то с приходом очеоедного тактового импульса с генератора 8 аналогичным образом проверяются возможности следующего иэ готовых к работе процессоров.Если же 1-й процессор приспособлен к решению задачи указанного пользователем типа (в его списке заданий присутствует соответствующий номер задачи), го на выходе одной из схем 17 сравнения группы формируется сигнал единичного уровня, который через первый элемент ИЛИ 18 поступает на первый управляющий вход мультиплексора 19 и на первые управляющие входыпервоо 23 и второго 24 блоков элементов И, С приходом сигнала единичного уровня на первый управляющий вход мультиплексора 19 на его выход передается информация с первой группы информационныхвходов, На одном из выходов группы 20 сигнальных выходов устройства появляется сигнал единичного уровня.Сигнал единичного уровня на соответствующем выходе группы 20 означает, что одноименный процессор избран для выполнения задания очередного пользователя. Этот же сигнал поступает на управляющий вход одноименного блока 21элементов И руппы и на соответствующий вход второго элемента ИЛИ 25, С поступлением сигнала единичного уровня на управляющий вход соответствующего блока 21 элементов И группы через него на выходы 22 группы информационных выходов ус 5 10 15 20 25 30 тройства передается информация с выхода регистра б номера задания (номер пользователя (абонента) и номер (тип) задачи), Таким образом, готовый к работе процессор получает сигнал (по выходу 20) на начало работы и уведомление (по выходам 22) о том, что он занимается для решения задачи соответствующего типа в интересах определенного пользователя (абонента), Приступив к выполнению задачи процессор посылает сигнал на ответный вход группы 31 устройства, с помощью которого обнуляется соответствующий разряд регистра 4 готовности процессора (процессор занят), Если окажется, что вновь поступившая задача обладает меньшим приоритетом, нежели задача такого же типа, но принятая на обслуживание ранее, то происходит следующее. На первых управляющих входах первого 23 и второго 24 блоков элементов И сигнал единичного уровня с выхода первого элемента ИЛИ 18(есть процессор для решения задачи), на вторых управляющих входах первого 23 и второго 24 блоков элементов И сигнал единичного уровня с первого выхода схемы 12 сравнения (вновь поступившая задача имеет меньший приоритет). Информация о номере процессора, выбранного для решения задачи, с входа первого 23 блока элементов И передается для записи в блок 10 памяти номеров процессоров по адресу, соответствующему номеру(типу) задачи. Информация о приоритете задачи, принимаемой для реализации, с входа второго 24 блока элементов И передается для записи в блок 11 памяти приоритетов заданий.Блоки 10 и 11 памяти имеют число ячеек,соответствующее количеству типов (номеров) задач, которые могут поступить на обработку, По ходу работы в ячейках памяти, соответствующих определенному типу задачи. содержится следующая информация; в блоке 10 - номер процессора, который выполняет задачу данного типа, имеющего наименьший приоритет из всех поступивших; в блоке 11 - значение приоритета этой задачи,Сигнал единичного уровня с выхода второго элемента ИЛИ 25 поступает через элемент 30 задержки на входы установки в "0" регистров 5 и б. Обнуление регистров должно быть задержано на время. достаточное для устойчивой записи информации в бло ки 10 и 11 памяти и выдачи на информационные 22 выходы устройства, но должно осуществиться до формирования очередного импульса на выходе генератора 8. После обнуления регистра б номера заданий на первом выходе дешифратора 7 сигналнулевого уровня, который поступает на первый вход элемента И 9 и запрещает прохождение очередного тактового импульса с выхода генератора 8.Очередной цикл функционирования устройства начинается с поступления информации очередного задания: приоритета задания в регистр 5 и номера задания в регистр б. На нулевое состояние регистра б предопределяет появление сигнала единичнога уровня на первом выходе дешифратора 7 - снятие блокировки прохождения импульсов генератора 8 через элемент И 9.Может сложиться следующая ситуация, Ни один из готовых процессоров не приспособлен для решения задачи, указанной в очередном задании (ее способны решить другие, но они заняты), То, что все готовые процессоры опрошены, подтверждается сигналом единичного уровня на выходе элемента ИЛИ - НЕ 26. Опрос 1-го процессора сопровождается установлением 1-га триггера 15 в состояние "1", что блокирует возможность появления сигнала единичного уровня на выходе -го элемента НЕ 14. То, что ни один из процессоров не решает задач данного типа, подтверждается сигналом нулевого уровня на выходе первого элемента ИЛИ 18 - сигналом единичного уровня на выходе элемента НЕ 27, Сигнал единичного уровня с выхода элемента НЕ 27 поступает на первый вход второго элемента И 28, Сигнал единичного уровня с выхода элемента ИЛИ-НЕ 26 поступает на входы обнуления триггеров 15 группы и на второй вход второго элемента И 28. Обнуление триггеров 15 группы приводит к снятию (через время задержки элемента 29) блокировки повторного опроса процессоров, готовых к рабате. Па адресу, соответствующему типу задачи очередного задания (с выходов дешифратора 7), в блоке 10 памяти номеров процессоров считывается информация о номере процессора и передается на вторую группу информационных выходов мультиплексора, а в блоке 11 памяти приоритетов заданий считывается информация о приоритете и передается на втааую группу информационных входов схемы 12 сравнения.Таким образом, к моменту окончания безуспешного поиска свободного процессора известен процессор, заведомо приспособленный к решению задач соответствующего типа, решающий задачу, обладающую наименьшим приоритетом среди всех ранее поступавших задач данного типа, и приоритет решаемой задачи,Возможзны два варианта, Если приоритет вновь поступившего задания меньше20 35 40 45 50 55 510 25 30 или равен приоритету решаемой задачи, то для вновь поступившего задания процессор не назначается, Задание будет выполнено при освобождении одного из процессоров, приспособленных к решению задач заданного типа, Если приоритет вновь поступившего задания превышает приоритет решаемой задачи, то на втором выходе схемы 12 сравнения формируется сигнал единичного уровня. Этот сигнал поступает на третий вход второго элемента И 28, Сигнал единичного уровня с выхода второго элемента И 28 поступает на второй управляющий вход мультиплексора 19, По этому сигналу на сигнальные выходы устройства 20 передается информация с второй группы информационных входов мультиплексора 19. Сигнал единичного уровня будет на выходе, соответствующем процессору. который решает задачу заданного типа, имеющую наименьший приоритет среди всех ранее поступивших, Этот сигнал поступает также на управляющий вход соответствующего блока 21 элементов И группы и на соответствующий вход второго элемента ИЛИ 25. На соответствующую группу информационных выходов 22 устройства выдается (с выхода регистра 6) информация о задании. для исполнения которого назначен процессор Регистры 5 и б обнуляются,Таким образом, процессор, выполняющий задачу типа, совпадающего с типом задачи вновь поступившего задания, на имеющую меньший приоритет, получает новое задание (па выходам 22) и сигнал (по выходу 20), предписывающий приступить к исполнению вновь поступившего задания.Прерывание ранее решаемой задачи и возврат к ее исполнению выполняются средствами, предусмотренными для про цессоров данного типа. Технические преимущества предлагаемого устройства относительно известного могут быть определены следующим образом,Предположим, что любой из процессоров с вероятностью 0,5 может оказаться занятым, а если свободен, то с вероятностью 0,5 способен решать задачу заданного типа. Тогда при обращении к первому из опрашиваемых процессоров в известном устройстве с вероятностью 0,25 обнаруживают искомый процессор, а в предлагаемом устройстве - вероятность 0,5 (так как опрашиваются только готовые процессоры). Задают некоторую вероятность обнаружения процессора, способность решить задачу заданного типа, например, 0,9. В ба 17111 б 2ния быстродействия устройства, в него введены группа элементов И - НЕ, группа элементов НЕ, группа триггеров, группа элементов задержки, группа схем сравнения, мультиплексор, элемент ИЛИ - НЕ, 5 причем первый вход -го элемента И-НЕ группы соединен с -м ( = 1,п, и - число процессоров) выходом регистра готовности процессоров, вторые входы всех элементов И - НЕ группы соединены с 10 выходом первого элемента И и с входом управления схемы сравнения, третий вход -го элемента И - НЕ группы соединен с выходом -го элемента задержки группы, вход -го элемента НЕ группы соединен с выхо дом 1-го элемента И-НЕ группы и с соответствующими входами всех последующих элементов И-НЕ группы, выход -го элемента НЕ группы соединен с входом установки в "1" -го триггера группы, с -м адресным 20 входом блока памяти списков заданий процессоров, с соответствующим входом первой группы информационных входов мультиплексора, с соответствующим в.;одом группы входов первого блока элемен тов И и с соответствующим входом элемента ИЛИ - НЕ, выход которого соединен с входами установки в "0" триггеров группы и с втооым входом второго элемента И, выход первого элемента ИЛИ соеди нен с первым управляющим входом мультиплексора и с вторыми входами первого и второго блоков элементов И, инверсный выход -го триггера группы соединен с входом -го элемента задержки группы, вхо ды первого элемента ИЛИ соединены с выходами соответствующих схем сравнения группы, первые и вторые группы входов которых соединены с группой выходов блока памяти списков заданий процессоров и с группой выходов регистра номера задания соответственно, третий вход второго элемента И соединен с выходом "Больше" схемы сравнения. выходы первого и второго блоков элементов И соединены с входами записи блока памяти номеров процессоров и блока памяти приоритетов заданий соответственно, первый выход дешифратора соединен с вторым вадом первого элемента И, другие выходы дешифратора соединены с соответству,ощими адресными входами блока памяти номеров про,ессоров и блока памяти приоритетов заданий, выход второго элемента И соединен с вторым управляющим входом мультиплексора, вторая группа информационных входов которого соединена с информационными выходами блока памяти номеров процессоров, выходы мультиплексора являются сигнальными выходами устройства и соединены с вторыми входами соответствующих блоков элементов И группы и с входами второго элемента ИЛИ, выход элемента задержки соединен с входами установки в "0" регистра приоритета заданий и регистра номера заданий, входы установки в "О" разрядов регистра. готовности процессоров соединены с соответствующими входами группы ответных входов устройства.оставитель А. Невскиехред М,Моргентал дактор А, Козориз орректор И, Муск оизводственно-издательский комбинат "Патент", г. ужгород, ул,Гагарина, 101 аказ 340 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж-З 5, Раушская наб 4/5