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

триггер установки, i -и вход 1,2,..., п запуска ..блока управления соединен с i-м входом элемента ИЛИ блока управления, выход которого соединен с первым входом первого элемента И блока управления второй вход которого соединен с вторым входом блока, а выход - с входом установки в единицу триггера синхронизации, выход которого соединен с входом элемента задержки и с входом синхронизации кольцевого счетчика, i -и выход которого является 1-м входом третьей группы входов блока элементов И, первый выход элемента задержки соединен с первым входом второго элемента И, выход которого соединен с входом установки в ноль триггера, синхронизации, второй выход элемента задержки соединен с инверсным входом первого элемента И блока управления а третий выход соединен с первым вх дом третьего элемента И блока управления , второй выход которого соединен с третьим входом блока, выход соединен с вторым входом второго элемента И блока управления, а третий вход соединен с выходом триггера установки, первый вход которого соединен с первым входом блока, а второй вход соединен с четвертым входом блока.

2. Устройство по п. 1, о т л и ч ающе еся тем, что блок приоритета содержит группу из Ч регистров, пер вьш и второй блоки из И групп элементов И, первую группу элементов ИЛИ, узел поиска левой единшу, вторую группу элементов ИЛИ, причем выходы регистров группы поразрядно соединены с первыми входами первого блока (1 групп элементов И, вторые входы которых соединены соответственно с первой груп21671

пой входов блока, третьу входы соединены соответственно с второй группой входов блока, а выходы первого блока и групп элементов И соединены соответственно с первыми входами второго блока П групп элементов И и с входами соответствующих эле - ментов ИЛИ первой группы, выходы которых через узел поиска левой единицы соединены с вторыми входами второго блока fi групп элементов И, выходы которых соединены соответственно с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с входом коммутации блока, а выходы блока соединены соответственно с выходами элементов ИЛИ второй группы.

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

I. УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ ЗАЯВОК ПО ПРОЦЕССОРАМ, содержащее блок буферной памяти, блок управления, регистр готовности, регистр сдвига, блок элементов И, элемент ИЖ и элемент И, причем выход элемента ИЛИ соединен с первым входом элемента И, информационный вход блока буферной памяти соединен с информационным входом устройства, а первый выход соединен с информационным входом регистра сдвига, отличающееся тем, .что, с целью расширения области применения путем обеспечения работы в реапьном масштабе времени, в устройство введены блок приоритета, блок коммутации и блок магистральной связи, причем i -и вход (i 1,2,... , ц ), где и - количество процессоров) готовности устройства соединен с i -м входом запуска блока управления, с -м входом первой труппы входов блока элементов И и с j -м входом группы информационныхJ входов блока приоритета,i -и вход кода установки приоритета которого соединен с i -м входом установки устройства, i -и выход блока приоритета соединен с i-м входом второй группы входов блока элементов И, i-и вход третьей группы входов которого соединен с 4 -м управляющим выходом блока управления, первый вход которого соединен с выходом элемента И и с входом чтения блока буферной памяти, выход состояния которого соединен с вторым входом блока управления и с входом записи регистра сдвига, информационные выходыj которого соед1П1ены соответственно с входами элемента И, а вход сдвига регистра сдвига соединен с В1 1ходом элемента 11Ш1, входы которого соединены соответственно с выходами блока элементов И и с информационными входами регистра готовности, j -и инверсный выход которого соединен соответ(Л ственно с 1 -м входом четвертой группы входов блока элементов И и с i -м входом третьей группы входов блока приоритета, вход разрешения которого соединен с первым выходом блока коммутации, первый, второй и третий входь которого соединены с соответСТВУЮ1ДИМИ входами установки режимов работы устройства, второй выход с третьим входом блока управления, а четвертый вход - с четвертым входом блока управления, выходом состояния блока магистральной связи и с входом сброса регистра готовности , прямые выходы которого соединены с соответствующими входами группы входов блока магистральной связи, вход которого соединен с выходом номера задачи и исходных данных-блока буферной памяти, причем блок управления содержит первый элемент . И, триггер синхронизации, второй и третий элементы И, элемент з адержки, элемент ИЛИ, кольцевой счетчик и

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

Известно устройство для распреде ления заданий процессорам, содержащее блок управления, регистр готовности, элемент ИЛИ, первый регистр сдвига, группу элементов И, первую группу блоков элементов И, группу процессоров, группу регистров номеров задания, группу элементов ИЛИ, группу блоков элементов ИЛИ, группу схем сравнения, группу элементов запрета, второй регистр сдвига, вто рую группу блоков элементов И ij . Устройство не может функционировать в составе систем с магисл ральной структурой связи вследствие одновременного вьщеления для выполнения задания процессоров, освобождающихся от выполнения предыдущего задания. Оно не реализует какую-либо конкретную дисциплину распределения заявок по процессорам даже то да, когда каждая заявка требует для своей обработки только одного процессора. Кроме того, устройство вьщает отказ на выполнение задания, если число свободных процессоров меньше числа потребных процессоров из-за того, что в нем не предусмотрена организацияочереди заявок, и не осуществляет приоритетного назначения процессоров, вследствие чего не может быть использовано в МВС с неоднородной структурой. Наиболее близким к предлагаемому по технической сущности является устройство для распределения заявок по процессорам, содержащее блок буферной памяти, блок управления, регистр готовности, регистр сдвига, блок элементов И, элемент ИЛИ и эле мент И, причем выход элемента ШШ соединен с первым входом элемента И информационный вход блока буферной памяти соединен с информационным входом устройства, а первый выход с информационным входом регистра сдвига 2 . Известное устройство не может фу ционировать в составе систем с магистральной структурой связи по при чине радиального сопряжения с процессорами. Оно имеет ограниченную область применения из-за отсутствия дисциплин диспетчеризации при числе потребных процессоров для обработки каждой заявки не более одного. Такое нерегламентирОванное функционирование устройства делает его непри емлемым для МВС реального времени, когда необходимо производить восста новление исходной последовательности обработанных заявок. Кроме того, устройство не .обеспечивает приоритетного назначения процессорови поэтому не может быть применено в МВС с неоднородной структурой, когд 714 процессоры различаются по производи-тельности и функциональному назначению. Цель изобретения - расширение области применения путем обеспечения работы в реальном масштабе времени. Для достижения поставленной цели в устройство для распределения заявок по процессорам, содержащее блок буферной памяти, блок управления, регистр готовности, регистр сдви-. га, блок элементов И, элемент ИЛИ и элемент И,причем выход элемента ИЛИ соединен с первым входом элемента И, информационный вход блока буферной памяти соединен с информационным входом устройства, а первый выход И соединен с информационным входом регистра сдвига, введены блок приоритета, блок коммутации и блок магистральной связи, причем i -и вход (i 1,2,...,п, где П - количество процессоров) готовности устройства соединен с 1 -м входом запуска блока управления, с -м входом первой группы входов блока элементов И и с i -м входом группы информационных входов блока приоритета, i -и вход кода установки приоритета которого соединен с i -м входом установки устройства, i -и выход блока приоритета соединен ci -м входом второй группы входов блока элементов H,i -и вход третьей группы входов которого соединен с 1 -м управляющим выходом блока управления, первый вход которого соединен с выходом элемента И и с входом чтения блока буферной памяти, выход состояния которого соединен с вторым входом блока управления и с входом записи регистра сдвига, информационные выходы которого соединены соответ ственно с входами элемента И, а вход сдвига регистра сдвига соединен с выходом элемента ИЛИ,входы которого соединены соответственно с выходами блока элементов.И и с информационными входами регистра готовности, t -й-инверс ный выход которого соединен соответственно с 1 -м входом четвертой группы входов блока элементов И и CJ-M входом третьей группы входов блока приоритета, вход разрешения которого соединен с первым выходом блока коммутации, первый, второй и третий входы которого соединены с соответствующими входами установки режимов работы устройства, второй выходс третьим входом блока управлеш1я, а четвертьй вход - с четвертым входом блока управления, выходом состо ния блока магистральной связи, и с входом сброса регистра готовности, прямые выходы которого соединены с соответствующими входами группы входов блока магистральной связи, вход которого соединен с выходом номера задачи и исходных данных блока буферной памяти, причем блок управления содержит первый эле мент И триггер синхронизации, втор и третий элементы И, элемент задерж ки, элемент ИЛИ, кольцевой счетчик и триггер установки, i -и вход (i «1,2,...п) запуска блока управления соединен с i -м входом элемента ИЛИ блока управления, выход которого со динен с первым входом первого элеме та И блока управления, второй вход которого соединен с вторым входом блока, а выход - с входом установки в едиьшцу триггера синхронизации, выход которого соединен с входом эл мента задержки и с входом синхронизации кольцевого счетчика, v-и выход которого является i -м входом третьей группы входов блока элементов И, первый выход элемента задерж ки соединен с первым входом второго элемента И, выход которого соединен с входом установки в ноль три гера синхронизации, второй выход эл мента задержки соединен с инверсным входом первого элемента И блока упр ления, а третий выход соединен с первым входом третьего элемента И блока управления, второй выход кото рого соединен с третьим входом блока, выход соединен с вторым входом второго элемента И блока управления а третий вход соединен с выходом триггера установки, первый вход котор о го соединен с первым входом блока, а второй вход соединен с чет вертым входом блока. I. Блок приоритета содержит группу из п регистров, первьй и второй бло ки из п групп элементов И, первую группу элементов ИЛИ, узел поиска левой единицы, вторую группу элементов ИЛИ, причем выходы регистров группы поразрядно соединены с первыми входами первого блока групп элементов И, вторые входы которых соединены соответственно с первой группой входов блока, третьи входы соединены соответственна с второй группой входов блока, а выходы первого блока п групп элементов И соединены соответственно с первыми входами второго блока И групп элементов И и с входами соответствующих элементов ИЛИ первой группы, выходы которых через узел поиска левой единицы соединены с вторыми входами второго блока/в-.групп элементов И, выходы которых соединены соответственно с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с входом коммутации блока, а выходы блока соединены соответственно с выходами элементов ИЛИ второй группы. Блок коммутации содержит триггер , цикла, первый элемент ИЛИ, триггер приоритета, элемент И и второй элемент ИЛИ, причем первый и второй входы блока соединены соответственно с .единичным и нулевым входами триггера цикла и первым и вторым входами первого элемента ИЛИ, выход которого соединен с входом установки в ноль триггера приоритета, вход установки в единицу которого соединен с третьим входом блока, единичный выход соединен с первым выходом блока, а нулевой выход соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с единичным выходом триггера цикла, нулевой выход которого соединен с первым входом элемента И, второй вход которого соединен с четвертым входом блока, а выход соединен с третьим входом второго элемента ИЛИ, выход которого соединен с вторым выходом блока. На фиг. 1 представлена структурная схема предлагаемого устройстства; на фиг. 2 - блок приоритета; на фиг. 3 - блок коммутации. Устройство содержит блок 1 буферной памяти, блок 2 элементов И, блок 3 управления, блок 4 приоритета, блок 5 коммутации, блок 6 магистральной связи, элемент ИЛИ 7, регистр 8 готовности,регистр 9 сдвига, элемент И 10, входы 11 и 12 устройства, выходы 13 блока управления, выходы 14 блока приоритета, входы 15 устройства, входы 16 и 17 блока приоритета, входы 18, 19 и 20 устройства, выход 21 блока коммутации, выход 22 блока магистральной связи, выходы 23 блока элементов И, выходы 24 регистра готовности, выход 25 элемента ИЛИ, выходы 26 регистра сдвига, выход 27 блока буферной памяти, выход 28 эле мента И, выходы 29 и 30.блока буфер ной памяти, элементы И 31 . Блок 3 управления содержит первы элемент И 32, триггер 33 синхронизации, второй элемент И ЗА, элемент 35 задержки, элемент ИЛИ 36, третий элемент И 37, кольцевой счетчик 38, триггер 39 установки, выход 40 элемента ИЛИ, выход 41 элемента И 34, выходы 42 и 43 элемента 35 задержки, вход 44 триггера 33, вход 45 элемента И 34, выход 46 триггера 33, выход 47 элемен та 35 задержки, выход 48 триггера 3 Блок 4 приоритета (фиг.2) содерж fpynny из И регистров 49, первый бл из П групп элементов И 50 (l-n), пе вую группу элементов ИЛИ 51 (1-П), узел 52 поиска левой единицы, второ блок из ц групп элементов И 53 (1-П вторую группу элементов ИЛИ 54 (1-П выходы 55 регистров 49, выходы 56 блока элементов И 50, выходы 57 гру пы элементов ИЛИ 51, выходы 58 узла 52, выходы 59 блока групп элемен тов И 53. Блок 5 коммутации (фиг,3) содержит триггер 60 цикла, первый элемент ИЛИ 61, триггер 62 приоритета, элемент И 63, второй элеиент ИЛИ 64, выход 65 элемента ИЛИ 61, выход 66 триггера 62, выходы 67 и 6 триггера 60, выход 69 элемента И 63 Устройство работает следующим образом. , Режим Мягкий цикл. Отличительным свойством этого режима является реализация алгоритма поиска свободных процессоров по кольцу, т.е. путем последовательного сканирования и анализа признаков процессоров занят - свободен. Если процессор свободен, ТОон берется на учет и далее в поиске не участвует. Если процессор занят, то обследуется следуюпщй по счету процессор. Когда.дпя конкретной заявки набрано нужное число процессоров, .производится их загруз ка. Задание данного режима производи ся путем подачи сигнала на вход 20. На выходах,16 и 21 блока 5 коммутации устанавливаются высокие потенциалы. Наличие высокого потенциала на входе 16 определяет наличие высоких потенциалоь и на выходах 14 блока 4 приоритета. Это означает,. что в данном режиме блок 4 приоритета участия не принимает. Работа устройства по обслуживанию каяадой отдельной заявки состоит в выполнении ряда последовательных циклов. Перед началом обслуживания очередной заявки регистр 8 готовности и регистр 9 сдвига обнулены, блок 3 управления находится в исходном состоянии, на выходе 27 блока 1 буферной памяти присутствует низкий потенциал. Обслуживание очередной заявки начинается в тот момент времени, когда она 4иксируется на верхнем регистре блока 1 буферной дамяти. Факт фиксации знаменуется появлением высокого потенциала на выходе 27, реализующем запись из блока I буферной памяти на выходе 29 кода числа процессоров в регистр 9 сдвига и иидициирующим начало работ блока 3 управления. Реакцией на этот сигнал является срабатывание кольцевого счетчика 38 и запуск генератора, образованного триггерами 33 синхронизации, элементами И 32, 34 и 37 и элементов 35 задеож ки. Срабатывание счетчика 38 возможно только в том случае, если имеется хотя бы один свободный процессор (в этом случае имеет место высокий потенциал на выходе 40). Если ни одного свободного процессора нет, то блок 3 управления Находится в ожидании до появления сигнала на входах 12 готовности хотя бы от одного процессора. Срабатывание счетчика 38 вызывает появление на одном из его выходов 13 высокого потенциала, который воздействует на соответствующий элемент И 31 в блоке 2 элементов И. Этот элемент И 31 срабатывает если на соответствующих ему шинах I2 и 17 имеют место высокие потенциалы. Высокий потенциал на входе 17 означает, что соответствующий процессор может быть использован для обработки згшвкн. Срабатывание элемента И 31 и повление сигнала на соответствующем ыходе 23 означает, что соответствующий процессор учтен и будет исполь зован для обработки заявки. Учет производится путем записи 1 в COOT нет ствую1Ций разряд регистра 8 , готовности, сигнал с инверсного выхода которого становится низким и по входу 17 запирает .сработавший эле мент И 31. Сигнал с выхода 23 через элемент ИЛИ 7 воздействует на регист 9 сдвига и элемент И 10. При этом со держимое регистра 9 сдвига сдвигается и из регистра выталкивается 1 Если после сдвига регистр не принял нулевого состояния, то сигнал с выхода элемента ИЛИ 7 не проходит через элемент И 10 и начинается следую щий цикл работы устройства по поиску следующего процессора. Если элемент И 31 в блоке 2 элементов И не срабатывает (соответствующий процессор занят - низкий потенциал на входе 12 или соответствующий процессор уже учтен для обработки данной заявки - низкий потенциал на ши не 17) , то необходимо ожидать выработки очередного импульса внутренним генератором в блоке 3 управления. Этот импульс воздействует на счетчик 38, в результате чего появляется высокий потенциал на следующем по порядку входе 13. Это означает, что начинается сканирование следующего по счету процессора. Если процессор -.свободен и не учтен, то производит ся его ytteT в регистре 8 готовности и сдвиг в регистре 9 сдвига. Если процессор занят или учтен, то следует ожидать начала следующего цикла поиска начало цикла определяется выработкой следующего импульса генератором в блоке 3 управления) . Может оказаться, что числа свобод ных процессоров меньше числа потребных. В этом случае свободные процессоры будут учтены в регистре 8 готовности, а блок 3 управления будет продолжать сканирование по кругу. По мере освобождения занятых процессоров будут проявляться высокие потенциалы на соответствующих шинах 12 и при очередном анализе состояния эти процессоры будут учтены. Поиск необходимого числа процессоров продолжается до тех пор, пока в регистре 9 сдвига не останется ни одной 1 при этом все процессоры учтены в регистре 8 готовности. Срабатывание элемента И 10 означает, что поиск завершен. По сигналу с выхода 28 в блоке 3 управления срабатывает триггер 39 установки, в результате чего прекращается функционирование генератора. Этот же сигнал с выхода 28 является сигналом Чтение для блока 1 буферной памяти. В результате действия этого сигнала потенциал на выходе 27 становится низким, а из блока 1 буферной памяти в блок 6 магистральной связи выдается сообщение, содержа-щее номер задачи и исходные данные. После выдачи сообщения из буфера на его верхний регистр записывается следующая заявка, код числа процессора которой передается в регистр 9 сдвига, а на выходе 27 появляется вновь высокий потенциал, при помощи которого код числа процессоров фиксируется в регистре 9 сдвига. Высокий потенциал, поступающий в блок 3 управления, никакого действия не оказывает, так как работа этого блока блокируется триггером 39 установки (величина времени задержки элемента 35 больше времени срабатывания цепи: счетчик 38, элементы И 31, Ш1И 7, регистр 9 сдвига, элемент И 10, блок 1 буферной памяти) и может быть инициирована только его сбросом. Связь элемента ИЛИ 7 с элемергтов И 10 необходима для того, чтобы исключить двойственность состояния триггера 39, когда буфер оказывается пустым, а сигнал с выхода 22 поступает. Блок 6 магистральной связи, получив сообщение, организует его выдачу в процессоры, номера которых учтены в регистре 8 готовности. Загрузка процессоров может производиться как последовательно, так и параллельно во времени. Каждый процессор, получив задание на работу, снимает сигнал готовности с соответствующего входа 12. Блок 6 магистральной связи, учитывая время передачи сообщения в процессоры и реакцию процессоров, выдает сигнал сброса на выход 22 тогда, когда все процессоры уже сняли свои сигналы занятости. Сигнал сброса обнуляет регистр 8 готовности и, действуя на триггер 39 установки в блоке 3 управления, снимает блокировку, инициируя при этом начало первого цикла обслуживания новой заявки. Режим Мягкий цикл целесообразно применять, если в системе используют ся однородные равноприоритетные процессоры. Число необходимых процессоров m 1 разумно задавать для тех случаев, когда одна заявка подвергается различной обработке, следует задавать, когда ведется обычная предварительная обработка потока телеизмерений. При этом в силу высокой реактивности предпагаемого устр.ойства дисциплина обслуживания будет соответствовать дисциппине пер вый освободился - первый загрузился, т.е. той, которая наиболее при емпема для решения задачи восстановления исходной последовательности в системах реального масштаба времени. Режим Жесткий цикл. Данный режим обеспечивает назна ченне процессоров строго по порядку друг за другом. Если очередной просматриваемый процессор занят, то ус ройство ждет его освобождения. Режи рассчитан для назначения только по одному процессору для обработки каждой заявки (). Это вызвано тем, что при задании m 1 имеют место большие потери по производительности в системе. Основная целесообразность применения режима заключается в том, что при исключительно просто решается задача восстановления исходной последовательности обрабатываемых сообщений в системах реального масштаба време ни.. Задание режима производится путе тодачи сигнала И по входу 19 в блок коммутации, в результате чего на вх де 16 разрешения устанавливается вы сокий потенциал, а на выходе 21 .низкий. Как и в предыдущем режиме потенциал на входе 16 отключает бло 4 приоритета. Потенциал на выходе 2 является блокировкой для блока 3 управления. Исходное состояние регистра 8 готовности, регистра 9 сдвига, блока 1 буферной памяти такое же, как и для режима Мягкий цикл. Вход в работу, т.е. запись числа необходимых процессоров (в дан ном режиме всегда одного в регистр сдвига и инициация блока 3 управле|Ния также аналогичны режиму Мягкий цикл. Срабатывание счетчика 38 вызывает появление высокого потенци ла на одной из шин 13, который воздействует на соответствующий элемент И 31. Работа блока 3 управления приостанавливается, так как три1- гер 33 синхронизации не сбрасывается, поскольку элемент И 37 закрыт низким потенциалом. Элемент И 31 срабатывает, если на соответствующем входе 12 имеется высокий потенциал (на соответствующей шине I7 всегда высокий потенциал, так как работа ведется всегда с одним процессором. Если на входе 12 потенциал низкий, то все устройство ждет, когда появится высокий потенциал, т.е. ждет освобождения нужного процессора. При срабатывании элемента И 31 появляется сигнал на соответствукнцем выходе 23, производится учет процессора в регистре 8 готовности и через элемент ИЛИ 7 осуществляется сдвиг в регистре 9 сдвига.,Так как в регистре 9 сдвига была зафиксирована только одна 1, то после первого же воздействия на него регистр 9 сдвига обнуляется и далее устройство функционирует как в режиме Мягкий цикл. Воздействие на блок 1 буферной памяти сигналом с выхода 28 приводит к появлению низкого потенциала на выходе 27, к считыванию сообщения, выдаче его в блок 6 магистральной связи, продвижению информации в блоке 1 буферной памяти и к записи, нового кода числа процессоров в регистр 9 сдвига, а воздействие тем же сигналом на блок 3 управления приводит к срабатыванию триггера 39 установки. После загрузки процессор меняет потенциал на соответствующем входе 12. После этого из блока 6 магистральной связи выf aeтся сигнал на выход 22, который сбрасывает триггер 39 установки и, пройдя через элементы И 63 и ИЛИ 64 блока 5 коммутации, поступает на элемент И 37, что приводит к сбрасыванию триггера 33 синхронизации.,- в блоке 3 управления и началу обслуживания новой заявки. Режим Приоритет . Этот режим отличается от режима Мягкий цикл только тем, что срабатывание блока 2 элементов И зависит от приоритета процессоров. Со стороны блока 4 приоритета имеет место высокий потенциал на одном из входов 14 для самого высокоприоритетного свободного процессора.

Режим устанавливается путем подачи сигнала по шине 18 в блок 5 коммутации. При этом на входе 16 разрешения появляется ниэкий потенциал, а на выходе 21 - высокий.

Таким образом, введение в состав устройства для распределения заявок

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

(Риг.г

Фиг. 2

Фиг,