Устройство для приоритетного обслуживания заявок Советский патент 1992 года по МПК G06F9/50 

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

Цель изобретения - повышение быстродействия и достоверности функционирования yctponcTBa.

Поставленная цель достигается тем, что в устройство для приоритетного обслуживания заявок, содержащее п-разрядный регистр заявок, группу из п регистров приоритета (где п-число обслуживаемых a6oHeHtoB), группу из п схем сравнения, группу из п триггеров, группу из п элементов ИЛИ, группу из блоков элементов И. блок элементов ИЛИ, первый и второй блоки элементов И, группу элементов И, регистр текущего приоритета, регистр приоритета заявки, схему сравнения, счетчик, генератор тактовых импульсов, триггер управления, первый, второй и третий элементы ИЛИ , первый и второй элементы И, причем группа информационных входов регистра заявок является группой запросных входов устройства, информационные входы регистров приоритета группы являются группой кодовых входов устройства, выходы 1-го регистра приоритета группы соединены с первыми входами i-й схемы сравнения группы и элементов И i-fo блока группы, выходы которого подключены к соответствующим входам блока элементов ИЛИ, вторые входы схем сравнения группы соединены с выходами счетчика, счетный вход которого пбдклю1 ен к выходу первого элемента И, вход установки в единичное состояние разрядов счетчика соединен с выходом второго элемента ИЛИ, третий вход первого элемента И подключен к выходу второго элемента И, второй вход которого соединен с выходом третьего элемента ИЛИ, входы которого подключены к прямым выходам триггеров группы, первый вход второго элемента И подключен к инверсному выходу триггера управления, прямой выход которого соединен с первыми входами элементов И первого блока, второй вход первого элемента И подключен к выходу первого элемента ИЛИ, первый вход первого элемента И соединен с выходом генератора тактовых импульсов, выходы блока элементов ИЛИ подключены к вторым входам элементов И первого и второго блоков, выходы второго блока элементов И соединены с входом регистра текущего приоритета, выходы первого блока элементов И соединены с входом регистра приоритета заявки, выход которого соединен с первым входом схемы сравнения, второй вход которой соединен с выходом регистра текущего приоритета, выход схемы сравнения подключен к первым входам элементов ИЛИ группы, вторые входы которых соединены с ответными входами устройства, выход 1-го 0 элемента ИЛИ группы подключен к входу установки в О 1-го триггера группы, вход установки в 1 которого соединен с выходом 1-го элемента И группы, прямые выходы триггеров группы являются выходами устройства, входы триггера управления соединены соответственно с входами сигналов установки а О и 1, введены группа из п / элементов И-НЕ, группа из п элементов НЕ, элемент НЕ, причем входы 1-го элементл И0 НЕ группы соединены с 1-м выходом регистра заявок, с выходом 1-й схемы сравнения группы, с инверсным выходом i-ro триггера группы, и с выходами всех остальных элементов И-НЕ группы, выход 1-го элемента 5 И-НЕ группы подключен к входу i-ro элемента НЕ группы, выход которого подключен к первому входу i-ro элемента И группы, к соответствующему входу второго элемента ИЛИ и к вторым входам элементов И i-ro 0 блока группы, входы первого элемента ИЛИ соединены с выходами регистра заявок, второй вход i-ro элемента И rpynnti соединен с первыми входами элементов И второго блока и выходом элемента НЕ,вход которого 5 подключен к выходу третьего элемента ИЛИ..

Сущность изобретения заключается в следующем.

Повышение быстродействия достигает0 ся путем исключения возможности прерывания начавшегося процесса выбора наиболее приоритетного запроса. Повышение достоверности обеспечивается путем исключения возможности взведения в 1 5 нескольких триггеров группы одновременно..

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

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

заявки, регистр 23 .текущего приоритета, схему 24 сравнения, запросные 25, кодовые 26 и ответные 27 входы устройства, вход 28 установки в 1 и вход 29 установки в О триггера управления, выходы 30 устройства.

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

В исходном состоянии регистр 1 заявок, регистры 3 приоритета группы, триггеры 14 группы обнулены, а разряды счетчика 4 переведены в Г (цепи установки не показаны).

В режиме без прерывания обслуживания текущей заяки сигналом по входу 29 триггер 18 управления устанавливается в О.

По группам входов 26 устройства в регистры 3 приоритета заносятся коды, определяющие приоритеты соответствующих абонентов. Наибольшему приоритету соответствует наибольший код. Запросы на обслуживание поступают по запросным входам 25 устройства в соответствующие разряды регистра 1 заявок. С поступлением хотя бы одного запроса сигнал единичного уровня с одного из выходов регистра 1 заявок через первый элемент ИЛИ 8 поступает на второй вход первого элемента И 6. По третьему (инверсному) входу элемент И 6 подготовлен к работе, так как с выхода второго элемента И 7 на него поступает сигнал нулевого уровня. На выходе второго элемента И 7 сигнал нулевого уровня потому, что все триггеры 14 группы в нулевом состоянии и соответственно сигнал нулевого уровня на втором входе второго элемента И 7. G приходом сигнала единичного уровня на второй вход первого элемента И 6 разрешается поступление импульсов с выхода генератора, 5 тактовых импульсов на счетный Bxoii счетчика 4. В результате на выходе счетЧика 4 формируется убывающая последовательность двоичных кодов, начиная от максимально возможного. Код с выхода t-ro регистра 3 приоритета поступает на первые входы 1-й схемы 2 сравнения и на первые входы элементов И 1-го блока 16. На второй вход t-й схемы 2 сравнения поступает код с выхода счетчика 4. При совпадении кодов на выходе соответствующих схем 2 сравнения формируются сигналы единичного уровня (возможность наличия равных приоритетов у заявок различных абонентов не исключается).

Сигнал единичного уровня с выхода 1-й схемы 2 сравнения поступает на соответствующий вход 1-го элемента И-НЕ 11, один из входов которого подключен к 1-му выходу

регистра 1 заявок, а на всех остальных сигналы единичного уровня с выходов дру гих элементов И-НЕ 11 и с инверсного выхода 1-го триггера 14. Таким образом, если есть запрос i-ro абонента на обслуживание (Т в 1-м разряде регистра 1 заявок), то с приходом сигнала единичного уровня с выхода 1-й схемы 2 сравнения на выходе ITO элемента И-НЕ появляется сигнал нулевого уровня.

Указанные условия совпадения сигналов на входе могут оказаться выполненными для нескольких элементов И-НЕ 11 группы. Однако из-за естественного разброса параметров элементов сигнал нулевого уровня на выходе одного из них опережает другие, а поступая на соответствующие входы остальных, блокирует возможность появления сигналов нулевого уровня на выходе любого другого из элементов. Сигнал нулевого уровня с выхода 1-го элемента И-НЕ 11 поступает на вход 1-го элемента НЕ 12, с выхода которого сигнал единичного уровня поступает на вторые входы элементов И 1-го блока 16, на соответствующий вход второго элемента ИЛИ 9 и на первый вход i-ro элементаИ 13, на втором входе которого сигнал единичного уровня с выхода элемента НЕ 21. Сигнал единичного уровня на выходе элемента НЕ 2Г обусловлен нулевым состоянием всех триггеров 14,

По сигналу единичного уровня на втоpbJx входах элементов И 1-го блока 16 код приоритета i-ro абонента через блок 17 элементов ИЛИ поступает на вторые входы элементов И второго 20 блока, на первых входах которого сигналы единичного уровня с выхода элемента НЕ 21. Код с выходов элементов И второго блока 20 заносится в регистр 23 текущего приоритета. Сигнал единичного уровня с выхода второго элемента ИЛИ 9 поступает на счетчик 4 и переводит его разряды в состояние 1 (в исходное состояние).

Сигнал единичного уровня с выхода 1-го элемента И 13 поступает на вход 1-го триггера 14 и переводит его в состояние 1. С переходом 1-го триггера 14 в состояние 1 на выходе третьего элемента ИЛИ 10 формируется сигнал единичного уровня, а на выходе элемента НЕ 21 сигнал нулевого уровня. Сигнал единичного уровня с выхода третьего элемента ИЛИ 10 поступает на второй вход второго элемента И 7, на первом входе которого сигнал единичного уровня с инверсного выхода триггера 18 управления.

Сигнал единичного уровня с выхода второго элемента И 7 поступает на третий (ин ерсный) вход первого элемента И 6 и

-блокирует поступление тактовых импульсов на счетный вход счетчика 4. Сигнал нулевого уровня с выхода элемента НЕ 21 поступает на вторые входы элементов И13 группы, где , блокирует возможность взведения любого другого, кроме уже взведенного 1-го триггера 14 группы, и на первые входы элементов И второго блока 20, где блокирует возможность передачи новой информации в регистр 23 (в регистре 23 фиксируется код текущего приоритета). Сигнал единичного уровня с прямого выхода 1-го триггера 14 поступает по выходу 30 устройства в проlieccop, уведомляет последний о необходимости приступить к обслуживанию заявки 1-гЬ абонента.

Во все время обслуживания заявки 1-го абонента другие процедуры (по выбору очередной по приоритету заявки) блокированы. По завершению обслуживания на 1-й ответный вход 27 устройства поступает сигнал единичного уровня, который гасит i-й запрос в регистре 1 заявок и через 1-й элемент ИЛИ 15переводит-и триггер 14 в состояние О. С переходом 1-го триггера 14 в состояние О на выходе третьего элемента ИЛИ 10 сигнал нулевого уровня, а на выходе НЕ 21 сигнал единичного уровня. Сигнал нулевого уровня с выхода третьего элемента ИЛИ 10 поступает на второй вход второго элемента И 7 и обеспечивает снятие блокировки по 1ретьему (инверсному) входу первого элемента И 6. Сигнал единичного уровня с выхода элемента НЕ 21 поступает на вторые входы элементов И 13 и на первые входы элементов И второго 20 блока, где разрешает прохождение сигналов взведения в 1 триггеров 14 и прихождение кода текущего приоритета соответственно.

Если а регистре 1 заявок есть запрос хотя бы одного абонента, то сигнал единичного уровня поступает на второй вход первого элемента И 6, тактовые импульсы поступают на счетный вход счетчика 4. Укаэанный процесс повторяется.

Работа в режиме с прерыванием обслуживания текущей заявки начинается при установке по входу 28 триггера 18 управления в состояние 1.

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

После выбора текущей заявки в регистре 23 зафиксирован ее приоритет, 1-й триггер 14 всостоянии 1,счетчик4 висходном состоянии. Однако в связи с тем, что на инверсном выходе триггера 18 управления сигнал нулевого уровня на выходе второго элемента И 7 сигнал нулевого уровня, блокировки первого элемента И 6 по третьему

(инверсному) входу не происходит. Поэтому сразу же после выбора заявки Г-го абонента на обслуживание начинается вновь процесс поиска наиболее приоритетной заявки тактовые импульсы с выхода генератора 5 через первый элемент И 6 поступают на счетный вход-счетчика 4. Вновь на выходах схем 2 сравнения при совпадении кодов фopмиpyюtcя сигналы единичного уровня.

Однако сигнал единичного уровня с выхода 1-й схемы 2 сравнения на дальнейшую обра ботку не поступает, так как он блокирован наличием на одном из входов 1-го элемента И-НЕ 11 сигнала нулевого уровня с инверсного выхода 1-го триггера 14.

На дальнейшую обработку (условия изложены) поступает сигнал единичного уровня с выхода j-й схемы 2 сравнения - на выходе jiro элемента И-НЕ 11 сигнал нулевого уровня. На выходе j-ro элемента НЕ 12 сигнал единичного уровня. Этот сигнал поступает на первый вход j-ro элемента И 13, на вторые входы элементов И j-ro блока 16 и на соответствующий вход второго элемента ИЛИ 9. Сигнал единичного уровня на первом входе -го элемента И 13 блокирован сигналом нулевого уровня на втором входе (следствие состояния 1 1-го триггера 14). По сигналу единичного уровня нз вторых входах элементов И j-ro блока 16 код приоритета j-ro абонента с выхода элементов И -го блока 16 через блок 17 элементов ИЛИ поступает на вторые входы первого 19 и второго 20 блоков элементое И. Возможность передачи кода через второй блок 20 элементов И блокирована сигналом нулевого уровня (следствие состояние 1 irro триггера 14) на его первых входах. Так как триггер 1 управления всостоянии 1, то по

сигналу единичного уровня с его прямого выхода, поступаиэщему на первые входы элементов И первого блока 19, код приоритета заявки j-ro абонента с выходов первого блока 19 элементов И поступает в

22 приоритета заявки. Сигнал единичного уровня с выхода второго элемента ИЛИ 9 поступает на вход счетчика 4 и переводит его в исходное состояние. Коды текущего приоритета с выхода регистра 23 и приоритета вновь выбранной заявки с выхода регистра 22 поступают на входы (:хемы 24 сравнения. Если код текущего приоритета больше или равен коду приоритета вновь выбранной заявки, то с приходом очередного тактового импульса на счетный вход счетчика 4 повторяется процесс поиска наиболее приоритетной заявки, а выполнение заявки 1-го абонента продолжается.

Если же код приоритета вновь выбранной заявки оказывается больше кода текущего приоритета, то на выходе схемы 24 сравнения формируется сигнал единичного уровня. Этот сигнал поступает на первые входы элементов ИЛИ 15 и далее на входы установки в О триггеров 14, С приходом данного сигнала 1-й триггер 14 переходит в состояние О. При обнулении 1-го триггера 14 на выходе третьего элемента ИЛИ 10 сигнал нулевого уровня, а на выходе элемента НЕ 21 сигнал единичного уровня. Сигнал единичного уровня с выхода элемента НЕ 21 поступает на вторые входы элементов И 13 группы и первые входы элементов И второго 20 блока. С приходом сигнала единичного уровня на первые входы второго блока 20 элементов И код приоритета вновь выбранной заявки с выходов блока 17 элементов ИЛИ передается в регистр 23 текущего приоритета. На выходе схемы 24 сравнения пропадает сигнал единичного уровня - снимается сигнал обнуления триггеров 14.

С приходом сигнала единичного уровня на вторые входы элементов И 13 сигнал единичного уровня с выхода J-ro элемента И 13 поступает на вход j-ro триггера 14 и переводит его в состояние 1. Таким образом, если в ходе обработки заявки 1-го абонента поступает более приоритетная заявка j-ro абонента, то обслуживание первой прекращается (i-й триггер 14 обнуляется) и она переводится в разряд отложенных (-й разряд регистра 1 заявок не обнулен), а вторая принимается на обслуживание ()-й триггер 14 переводится в состояние 1) и переводится в разряд текущей (ее приоритет зафиксирован в триггере 23).

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

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

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

К

обслуживание потребуется у тактов. Предположим, что запросы каждого из абонентов поступают с некоторой частотой ft. В этом случае за время, необходимое для выКбора заявки, могут поступить т У. f 1

просов. В базовом устройстве поступление каждого из запросов (через элемент ИЛИ 6) вызывает прерывание процесса выбора заявки (перевод счетчика 4 в исходное состояние). После этого процесс выбора возобновляется, но может быть опять прерван запросом. Таким образом, в базовом устройстве среднее время выбора заявки соК К

ставляет 2 тактов.

В предлагаемом устройстве воздейстл вне запросов на состояние счетчика исКлю чено. Счетчик изменяет свое состояние по результатам выбора очередной заявки. Таким образом среднее время выбора очередной заявки в предлагаемом устройстве

5 составляет тактов.

Очевидно, что производительность

К

предлагаемого устройства в ту X i

0 выше производительности базового.

В современных вычислительных комплексах (Эльбрус И-ему подобные) К 16, п 128 (п - количество абонентов). Предположим, что частота следования запросов на

5 три порядка ниже частоты следования тактовых импульсов. Несложный подсчет показывает, что даже при таких условиях производительность предлагаемого устройства на 2,4% выше производительности базового. С возрастанием величин К, п, fi (ожидать этого имеются основания) выигрыш в производительности возрастает соответственно. При п 129 и fi 000 (где F 5 частота генератора тактовых импульсов) выигрыш составляет уже 3,3%.

В современных вычислительных комплексах п К. Из этого следует, что несколько заявок будут иметь, равные приоритеты.

0 Значит на выходах нескольких схем 2 сравнения одновременно появляются сигналы единичного уровня. В базовом устройстве реализованная схема блокировки появления нескольких выходных сигналов в общем случае оказывается недейственной. Действительно, еслипред пол ожить, что разброс по времени срабатывания элементов составляг f ет менее ту (в противном случае элементы

0 должны быть отбракованы самым невзыскательным контролем), то в базовом устройстве сигнал единичного уровня на входе одного из триггеров 12 может опередить появление сигналов на входе других тригге5fт

ров на время меньше г (менее -п - задержка на элементе И 5; менее ту - задержка на

элементе И 11). Естественная задержка воздействия сигнала блокировки составляет не

менее 2,5 г( - задержка на триггере 12 с

учетом опрежающего срабатывания, т- задержка на элементе ИЛИ 13, т- задержка на элементе И 11).

Таким образом, даже при самых выигрышных для базового устройства предположениях - разброс параметров в одну (выигрышную) сторону у всех элементов, блокировка осуществима только при последовательном поступлении запросов в регистр 1, причем с интервалом, равным не менее, чем время выбора заявки плюс 2,5г В асинхронной системе достоверность работы базового устройства невысока. Как правило, на нескольких выходах 30 одновременно будут формироваться сигналы единичного уровня. Это потребует от процессора дополнительных процедур по конкретизации сделанного выбора.

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

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

Устройство для приоритетного обслуживания заявок, содержащее п-разрядный регистр заявок, группу из п регистров приоритета (где п-число обслуживаемых або, Нентов), группу из п схем сравнения, группу из п триггеров, группу из п элементов ИЛИ, группу из п блоков элементов И, блок элементов ИЛИ, два блока элементов И, группу элементов И, регистр текущего приоритета, регистр приоритета заявки, схему сравнения, счетмик, генератор тактовых импульсов, триггер управления, три элемента ИЛИ, два элемента И, причем группа информационных входов регистра заявок является группой запросных входов устройства, информационные входы регистров приоритета группы являются группой кодовых входов устройства, выходы 1-го (,...,п) регистра приоритета группы соединены с первыми входами 1-й.схемы сравнения группы и 1-го блока элементов И группы, выходы которого подключены к соответствующим входам блока элементов ИЛИ, вторые входы схем сравнения группы соединены с выходами счетчика, счетный вход которого подключен к выходу первого элемента И, вход установки в единичное состоян11е разрядов счетчика соединен с выходом первого элемента ИЛИ, инверсный вход первого элемента И подключен к выходу второго элемента И, первый вход которого соединен с выходом второго элемента ИЛИ, входы которого подключены к прямым выходам триггеров группы, второй вход второго элемента И подключен к инверсному выходу триггера управления, прямой выход которого соединен с первыми входами первого блока элементов И, первый, прямой вход первогр элемента И соединен с выходом генератора тактовых импульсов, выходы блока элементов ИЛИ подключены к вторым входам первого и лервым входам второго блоков элементов И, выходы перврго и второго блоков элементов И соединены с информационными входами регистра приоритета заявки и регистра текущего приоритета соответственно, выходы которых соединены с входами схемы сравнения, выход схемы сравнения подключен к первым входам элементов ИЛИ группы, вторые входы которых соединены с соответствующими ответными входами устройства, выход 1-го элемента ИЛИ группы подключен к входу установки в О 1-го триггера группы, вход установки в 1 которого соединен с выходом i-ro элемента И группы, прямые выхо.п;. триггеров группы являются выходами устройства, входы триггера управления соединены соответственно с входами сигналов установки в О и 1 устройства, ответные входы устройства соединены Q соответствующими входами сброса регистра заявок, отличающеес я тем, что, с целью повышения быстродействия и достоверности функционирования, в него введены группа из п элементов И-НЕ, группа из п элементов НЕ и элемент НЕ, причем входы i-ro элемента И-НЕ группы соединены с 1-м выходом .регистра заявок, с выходом 1-й схемы сравнения группы, с инверсным выходом i-ro триггера группы и с выходами всех остальных элементов ИНЕ группы соответственно, выход 1-го элемента И-НЕ группы подключен к входу i-ro элемента НЕ группы, выход которого подключён к первому входу 1-го элемента И группы, к соответствующему входу пепвого. элемента ,ИЛИ и к вторым входам 1-го блока элементов И группы, второй вход 1-го элемента И группы соединен с вторыми входами второго блока элементов И и выходом элемента НЕ, вход которого подключен к выходу второго элемента ИЛИ, входы третьего элемента ИЛИ соединены с выходами регистру заявок, выход третьего элемента ИЛИ - с вторым прямым входом первого элемента И.

Изобретение относится к вычислительной технике, в частности к устройствам для приоритетного обслуживания запросов. Цель изобретения - повышение быстродействия и достоверности функционирования устройства. Поставленная цель достигается тем, что в Устройство введены группа элементов И-НЕ. группа элементов НЕ и элемент НЕ. В устройстве исключается прерывание процесса выбора заявки с приходом любого из запросов, также исключается возможность формирования одновременно нескольких сигналов о выборе заявки.1 ил.tntИзобретение относится к вычислительной технике, в частности к устройствам для приоритетного обслуживания запросов.Известно устройство для приоритетного обслуживания заявок, содержащее регистр заявок, группу регистров приоритета, группу схем сравнения, две группы'элемен- тов И. группу триггеров, три элемента ИЛИ, два элемента И, счетчик, триггер управления и генератор тактовых импульсов.Известное устройство имеет недостаточное быстродействие.Наиболее близким по технической сущности к предлагаемому является устройство для приоритетного обслуживания заявок, содержащее регистр заявок, группу регистров приоритета, группу схем сравнения, две группы элементов И, группу триггеров, группу блоков элементов И, две группы элементов ИЛИ, блок элементов ИЛИ. регистр текущего приоритета, регистр приоритета заявки, схему сравнения, четыре элементаИЛИ, два элемента И, счетчик, два триггера управления и генератор тактовых импульсов.Однако данное устройство обладает недостаточными производительностью и достоверностью функционирования. Н«здо- статочная производительность обусловлена тем, что любой запрос способен перевести счетчик в исходное состояние. Поскольку запросы асинхронны, процесс выбора (с помощью счетчика), наиболее приоритетного, возобновляется неоднократно. Недостаточная достоверность функционирования устройства заключается в неоднозначности выбора абонента (чьи задачи должны быть выполнены процессором) при одновременном поступлении нескольких запросов ,с равными приоритетами. Предусмотренное блокирование при одновременном поступлении запросов не срабатывает. Цепи прохождения сигналов от схем сравнения группы до триггеров группы совершенно^ о >&о ыСл>&>&