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

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

Реферат

 

Изобретения относятся к области вычислительной техники и могут быть применены в системах обмена данными. Техническим результатом является своевременное обслуживание незкоприоритетных запросов. Устройство содержит N абонентских блоков, где N 2, счетчик, генератор тактовых импульсов, делитель, N-входовый элемент ИЛИ-НЕ, мультиплексор, инверторы, элемент И, селектор-мультиплексор, шифратор приоритетов, N-входовый элемент И-НЕ, дешифратор низкого уровня, К блоков выборки и фиксации, где К - разрядность кода оставшегося времени ожидания. Способ описывает работу данного устройства. 2 c. и 2 з. п. ф-лы, 13 ил.

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

Известны способы обслуживания запросов вычислительной системы, реализованные, например, в устройстве по а. с. СССР 1441398 "Многоканальное устройство динамического приоритета", МПК G 06 F 9/46, опубл. 30.11.88, БИ 44, где повышение приоритета запроса осуществляется линейно через определенные интервалы времени; по а. с. СССР 1562912 "Многоканальное устройство с динамическим изменением приоритета", МПК G 06 F 9/46, опубл. 07.05.90, БИ 17, где повышение приоритета запроса происходит после каждого обслуживания запроса по другим приоритетным направлениям. (Под терминами обслуживание, запрос, приоритет понимается следующее. Обслуживание - совокупность действий вычислительной системы, включающая выборку запроса из очереди, выделение ему ресурса, а также проведение завершающих операций. Запрос - посылка сигнала, инициирующего ответ. Входное сообщение, содержащее требование к системе на выделение ресурса. Приоритет - число, предписанное задаче, процессу или операции, определяющее очередность их выполнения или обслуживания. Чем меньше число, тем выше уровень приоритета).

Однако известные способы-аналоги не учитывают допустимое время нахождения запроса в очереди, следствием чего является высокая вероятность потери низкоприоритетных запросов в результате их несвоевременного обслуживания.

Известны устройства обслуживания запросов - см. , например, а. с. СССР 1441398 "Многоканальное устройство динамического приоритета", МПК G 06 F 9/46, опубл. 30.11.88, БИ 44; а. с. СССР 1562912 "Многоканальное устройство с динамическим изменением приоритета", МПК G 06 F 9/46, опубл. 07.05.90, БИ 17.

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

Наиболее близким по своей технической сущности к заявленному способу обслуживания запросов является способ, реализованный в устройстве для обслуживания запросов см. а. с. РФ 2140666 "Способ обслуживания запросов пользователей вычислительной системы и устройство его реализующее", МПК G 06 F 9/46, опубл. 27.10.99, БИ 30.

Способ-прототип заключается в том, что формируют коды максимального времени ожидания обслуживания запроса Т_ож.i, где i= 1,2, . . . , N - соответствующий номер приоритета i-го абонента, а N - общее число абонентов, и запоминают их. Затем формируют сигналы запросов и организуют из сигналов запросов очередь второго порядка в соответствии с номерами приоритетов абонентов. Запросы из очереди второго порядка, достигшие максимального времени ожидания, переносят в очередь первого порядка на позиции, соответствующие номерам их приоритетов. Последовательно обслуживают запросы из очереди первого порядка в соответствии с возрастанием номеров их приоритетов, а при отсутствии запросов в очереди первого порядка, обслуживают запросы из очереди второго порядка.

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

Однако способ-прототип имеет недостаток: невысокую вероятность своевременного обслуживания низкоприоритетных запросов. Это объясняется тем, что способ-прототип не учитывает временные интервалы запросов (ВИЗ) из очереди второго порядка при их приоритетном обслуживании. По этой причине запросы с малыми ВИЗ ожидают обслуживания столько же, сколько и запросы того же приоритета с большими ВИЗ. (Под ВИЗ понимается время, требуемое для обслуживания запроса).

Из известных наиболее близким аналогом (прототипом) по своей технической сущности заявленному устройству является устройство (первый вариант) см. а. с. РФ 2140666 "Способ обслуживания запросов пользователей вычислительной системы и устройство его реализующее", МПК G 06 F 9/46, опубл. 27.10.99, БИ 30.

Устройство обслуживания запросов абонентов вычислительной системы, содержащее N абонентских блоков, где N2, счетчик, элемент И, генератор тактовых импульсов, делитель, N-входовый элемент ИЛИ-НЕ, мультиплексор, первый инвертор. При этом счетный вход счетчика соединен с выходом элемента И, а второй вход элемента И подключен к выходу генератора тактовых импульсов и входу делителя. Выход делителя соединен с тактовыми входами N абонентских блоков. Запросные входы и K-разрядные входы, где К2 - разрядность кода максимального времени ожидания обслуживания запросов, "Код максимального времени ожидания" N абонентских блоков являются соответствующими запросными входами и K-разрядными входами "Код максимального времени ожидания" устройства, N входов N-входового элемента ИЛИ-НЕ подключены к выходам "Превышение" соответствующих N абонентских блоков, а выход N-входового элемента ИЛИ-НЕ подключен к входам "Запрет" N абонентских блоков. N информационных входов мультиплексора соединены с первыми сигнальными выходами соответствующих N абонентских блоков. J, где J = ]log₂N[, выходов "Код абонента" счетчика подключены к соответствующим J адресным входам мультиплексора и одновременно являются соответственно J выходами "Код абонента" устройства. Выход мультиплексора подключен к входу первого инвертора и одновременно является разрешающим выходом устройства. Выход первого инвертора соединен с первым входом элемента И, а вход сброса счетчика является опросным входом устройства. Входы "Обнуление" N абонентских блоков являются соответствующими входами "Обнуление" устройства.

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

Такая схема позволяет по сравнению с устройствами-аналогами повысить вероятность своевременного обслуживания запросов низкого приоритета.

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

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

В заявленном способе поставленная цель достигается тем, что в известном способе обслуживания запросов вычислительной системы, заключающемся в том, что формируют коды максимального времени ожидания обслуживания запроса Т_ож.i, где i= l, 2, . . . , N - соответствующий номер приоритета i-го абонента, а N - общее число абонентов, запоминают их, формируют сигналы запросов, организуют из сигналов запросов очередь второго порядка в соответствии с номерами приоритетов абонентов, из очереди второго порядка переносят в очередь первого порядка запросы, достигшие максимального времени ожидания на позиции, соответствующие номерам их приоритетов, последовательно обслуживают запросы из очереди первого порядка в соответствии с возрастанием номеров их приоритетов, а при отсутствии запросов в очереди первого порядка, обслуживают запросы из очереди второго порядка, одновременно с формированием кодов максимального времени ожидания обслуживания запросов дополнительно формируют М, где М2, кодов максимальных, отличающихся по длительности временных интервалов T_об, достаточных для обслуживания соответствующих запросов. При обслуживании запросов из очереди второго порядка предварительно сравнивают временной интервал T_ож.min, оставшийся до истечения времени ожидания обслуживания запроса с минимальным номером приоритета, с максимальными временными интервалами T_об остальных запросов из очереди второго порядка. При наличии запросов, T_об которых меньше T_ож.min, обслуживают из их числа запрос, имеющий наименьший номер приоритета, а при их отсутствии обслуживают запрос из очереди второго порядка с минимальным номером приоритета, причем сравнивают T_ож.min и T_об и обслуживают запросы из очереди второго порядка до тех пор, пока отсутствуют запросы в очереди первого порядка.

Новая совокупность существенных признаков позволяет достичь указанного технического результата за счет формирования М, где М2, кодов максимальных, отличающихся по длительности временных интервалов T_об, достаточных для обслуживания соответствующих запросов, причем при обслуживании запросов из очереди второго порядка предварительно сравнивают временной интервал T_ож.min, оставшийся до истечения времени ожидания обслуживания запроса с минимальным номером приоритета, с максимальными временными интервалами T_об остальных запросов из очереди второго порядка и при наличии запросов, T_об которых меньше T_ож.min, обслуживают из их числа запрос, имеющий наименьший номер приоритета, а при их отсутствии обслуживают запрос из очереди второго порядка с минимальным номером приоритета, причем сравнивают T_ож.min и T_об и обслуживают запросы из очереди второго порядка до тех пор, пока отсутствуют запросы в очереди первого порядка.

Поставленная цель в заявленном устройстве обслуживания разноприоритетных запросов абонентов вычислительной системы достигается тем, что в известном устройстве обслуживания запросов абонентов вычислительной системы, содержащем N абонентских блоков, где N2, счетчик, счетный вход счетчика соединен с выходом элемента И, второй вход элемента И подключен к выходу генератора тактовых импульсов и входу делителя, выход делителя соединен с тактовыми входами N абонентских блоков, запросные входы и К-разрядные входы "Код максимального времени ожидания" N абонентских блоков являются соответствующими запросными входами и K-разрядными входами "Код максимального времени ожидания" устройства, N-входового элемента ИЛИ-НЕ, N входов которого подключены к выходам "Превышение" соответствующих N абонентских блоков, а выход N-входового элемента ИЛИ-НЕ подключен к входам "Запрет" N абонентских блоков, мультиплексора, N информационных входов которого соединены с первыми сигнальными выходами соответствующих N абонентских блоков, а его J, где J = ]log₂N[, адресных входа подключены к соответствующим J выходам "Код абонента" счетчика, выход мультиплексора подключен к входу первого инвертора, выход первого инвертора соединен с первым входом элемента И, а вход сброса счетчика является опросным входом устройства, причем входы "Обнуление" N абонентских блоков являются соответствующими входами "Обнуление" устройства, дополнительно введены селектор-мультиплексор, второй инвертор, N-входовый элемент И-НЕ, шифратор приоритетов, дешифратор низкого уровня, К блоков выборки и фиксации. J информационных входов первой группы селектора-мультиплексора подключены к соответствующим J выходам "Код абонента" счетчика, J выходов селектора-мультиплексора являются соответственно J выходами "Код подлежащего обслуживанию абонента" устройства. Вход второго инвертора подключен к входу первого инвертора, а выход второго инвертора подключен к разрешающему входу селектора-мультиплексора и одновременно является разрешающим выходом устройства, n-й, где n= 1,2, . . . , N, инверсный вход шифратора приоритетов подключен к второму сигнальному выходу (N+l)-n-гo абонентского блока. J инверсных выходов шифратора приоритетов подключены к соответствующим J входам второй группы входов селектора-мультиплексора. N входов N-входового элемента И-НЕ подключены к соответствующим N инверсным входам шифратора приоритетов, а выход N-входового элемента И-НЕ подключен к управляющему входу селектора-мультиплексора. J входов дешифратора низкого уровня подключены к соответствующим J выходам "Код абонента" счетчика, а N инверсных выходов дешифратора низкого уровня подключены к входам "Разрешение сравнения" соответствующих N абонентских блоков. J входов "Код абонента" каждого из К блоков выборки и фиксации подключены к соответствующим выходам "Код абонента" счетчика. m-й, где m= 1,2, . . . , К, разряд выхода "Код оставшегося времени ожидания" n-го абонентского блока подключен к n-му разряду N-разрядного входа "Разряд кода оставшегося времени ожидания" m-го блока выборки и фиксации. Управляющий вход каждого из К блоков выборки и фиксации подключен к выходу первого инвертора. Выходы "Разряд выбранного кода оставшегося времени ожидания" К блоков выборки и фиксации подключены к соответствующим разрядам K-разрядных входов "Выбранный код оставшегося времени ожидания" каждого из N абонентских блоков. При этом каждый абонентский блок снабжен дополнительно K-разрядным входом "Код максимального времени обслуживания", которые одновременно являются K-разрядными входами "Код максимального времени обслуживания" устройства.

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

Блок выборки и фиксации состоит из мультиплексора и D-триггера. N информационных входов мультиплексора являются соответственно N-разрядным входом "Разряды кода оставшегося времени ожидания" блока выборки и фиксации, a J адресных входов мультиплексора являются соответственно J входами "Код абонента" блока выборки и фиксации. Информационный вход D-триггера подключен к выходу мультиплексора, управляющий вход D-триггера является управляющим входом блока выборки и фиксации. Выход D-триггера является выходом "Разряд выбранного кода оставшегося времени ожидания" блока выборки и фиксации.

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

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

Заявленные объекты изобретения поясняются чертежами, где показано на фиг. 1 - структура вычислительной системы; на фиг. 2 - размещение запросов в очереди второго порядка; на фиг. 3 - порядок переноса запросов из очереди второго порядка в очередь первого порядка; на фиг. 4 - фиг. 7 - временные диаграммы работы устройства обслуживания разноприоритетных запросов абонентов вычислительной системы; на фиг. 8 - среднее время нахождения в вычислительной системе и вероятность своевременного обслуживания запросов с различными приоритетами и различными ВИЗ; на фиг. 9 - среднее время нахождения в очереди запросов с различными приоритетами и различными ВИЗ; на фиг. 10 - среднее время нахождения в вычислительной системе запросов всех приоритетов с различными ВИЗ; на фиг. 11 - устройство обслуживания разноприоритетных запросов абонентов вычислительной системы; на фиг. 12 - абонентский блок; на фиг. 13 - блок выборки и фиксации.

Реализация заявленного способа заключается в следующем. Для каждого запроса (группы запросов) формируются коды ВИЗ T_об.i и коды максимального времени ожидания обслуживания Т_ож.i. Формирование вышеуказанных кодов осуществляется из следующих соображений. Время пребывания запроса i-го абонента в вычислительной системе известно и установлено нормативными документами. Оно определяется величиной Т_доп.i. Величина ВИЗ i-го абонента T_об.i характеризует временные затраты вычислительной системы на его обслуживание (выделение ресурса). Величина T_об.i для каждого запроса определяется экспериментальным путем в начальный период функционирования системы или на основании статистических данных функционирования аналогичных систем. Причем, в общем случае, возможно объединение запросов i-го абонента, имеющих близкие по величине ВИЗ в М, где М2, групп и назначение для каждой группы запросов величины T_об.ji, где j - порядковый номер группы запросов, достаточной для обслуживания (выделения ресурса) запроса с максимальным ВИЗ из данной группы. Величина максимального времени ожидания обслуживания запроса Т_ож.i, определяет максимальное время пребывания запроса в очереди, по истечении которого запросу должен быть выделен ресурс вычислительной системы и может быть определена следующим соотношением: T_ож.i= T_доп.i-T_об.ji-T_зап.i; (1) где T_ож.i - максимальное время ожидания обслуживания запроса i-го приоритета (абонента), где i= l, 2, . . . , N; Т_доп.i - допустимое время пребывания запроса i-го абонента в вычислительной системе, по истечении которого запрос теряет актуальность или данный абонент несет определенные убытки; T_об.ji- ВИЗ i-го абонента, где j= 1,2, . . . , M - номер группы запросов; T_зап.i - некоторый запас времени определяемый издержками обслуживания.

Сформированные для каждого абонента вычислительной системы коды максимального времени ожидания обслуживания и коды ВИЗ запоминаются (заносятся в память). После чего система готова к работе и принимает сигналы запросов, вырабатываемые абонентами вычислительной системы (см. фиг. 1). Они поступают на устройство обслуживания запросов, где осуществляется постановка их в очередь второго порядка согласно начальным приоритетам (первый абонент имеет высший приоритет, а N-й абонент - низший) (см. фиг. 2). Непосредственно после этого начинается подсчет времени нахождения запросов в данной очереди.

После поступления от вычислительной системы сигнала об освобождении ресурса, устройство обслуживания запросов определяет в очереди второго порядка запрос с минимальным номером z приоритета, сравнивает промежуток времени T_ож.z, оставшийся до истечения максимального времени ожидания обслуживания данного запроса, с временными интервалами T_об.ji (i= z+1, z+2, . . . , N) остальных запросов, находящихся в данный момент времени в очереди второго порядка. При обнаружении запроса, ВИЗ которого не превышает времени, оставшегося до истечения времени ожидания обслуживания запроса с наименьшим номером приоритета, то есть удовлетворяющего неравенству T_об.ji< T_ож.z, (2) где T_об.ji- ВИЗ i-го абонента, где i= z+1, z+2, . . . , N; j= 1,2, . . . , М - номер группы запросов; T_ож.z- временной интервал, оставшийся до истечения максимального времени ожидания обслуживания запроса в очереди второго порядка, устройство обслуживания выдает вычислительной системе код АБ, в котором находится обнаруженный запрос, после чего система выделяет затребованный ресурс. При обнаружении нескольких запросов, удовлетворяющих неравенству (2), вычислительный ресурс будет выделен запросу с наименьшим номером приоритета.

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

Например, в начальный момент времени t₁ (см. фиг. 4а) в системе находятся 4 запроса и поступил сигнал вычислительной системы об освобождении ресурса. Наивысшим приоритетом обладает запрос 1 (с минимальным номером приоритета). Кроме того, в устройстве находятся запрос 3, чью потребность в вычислительном ресурсе можно удовлетворить за отрезок времени, оставшийся запросу 1 до истечения максимального времени ожидания (T_об.j3< T_ож.1) и при этом запрос 1 не будет считаться опоздавшим. Ресурс будет выделен запросу 3. После освобождения ресурса запросом 3, в момент времени t_2a (см. фиг. 5а), ресурс будет выделен запросу 1, так как он имеет минимальный номер приоритета и в устройстве нет запросов, удовлетворяющих условию (2). После освобождения ресурса запросом 1 в момент времени t_3а (см. фиг. 6а) ресурс будет выделен запросу 4, так как к этому моменту времени максимальное время ожидания обслуживания запроса 4 в очереди второго порядка превысило величину Т_ож.4, и запрос перенесен в очередь первого порядка. После освобождения ресурса запросом 4, в момент времени t_4a (см. фиг. 7а) ресурс будет выделен запросу 2.

Последовательность обслуживания запросов при применении способа-прототипа будет следующей. В начальный момент времени t₁ ресурс будет выделен запросу 1 (см. фиг. 4б). В момент времени t_2б ресурс будет выделен запросу 2 (см. фиг. 5б). Далее в моменты времени t_3б и t_4б ресурс будет выделен запросам 4 и 3 соответственно, поскольку у каждого из них к соответствующим моментам времени истечет время ожидания. В результате запросам 4 и 3 ресурс будет выделен с существенным опозданием.

Заявленный способ обслуживания разноприоритетных запросов обеспечивает высокую вероятность обслуживания низкоприоритетных запросов за счет учета максимального времени ожидания обслуживания запросов в очереди второго порядка, а также уменьшение времени нахождения в очереди запросов с малыми ВИЗ (по сравнению с способом-прототипом) за счет использования резерва времени, оставшегося до истечения максимального времени ожидания обслуживания первоочередных запросов.

Правомерность теоретических предпосылок проверялась с помощью имитационной модели вычислительной системы, при экспоненциальном законе распределения поступления запросов на обслуживание. Результаты проверки приведены в табличном виде на фиг. 8-10, где Пр. - номер приоритета запросов (для упрощения рассмотрено три приоритета); ВИЗ - временной интервал запроса; Т_cр. - среднее время нахождения запроса в вычислительной системе (среднее время обслуживания); - среднеквадратическое отклонение; Р(ТТ_доп.) - вероятность своевременного обслуживания запросов вычислительной системой; Т_{cр. в о череди} - среднее время ожидания запросом выделения ресурса вычислительной системой.

Из приведенных данных следует, что заявленный способ позволяет увеличить вероятность своевременного обслуживания низкоприоритетных запросов до 3% за счет уменьшения времени нахождения в очереди запросов с малыми ВИЗ в 1.1-1.3 раза по сравнению со способом-прототипом, что указывает на возможность достижения данного технического результата.

Устройство (фиг. 11) состоит из генератора тактовых импульсов 2, делителя 3, N-входового элемента ИЛИ-НЕ 4, счетчика 5, элемента И 6, первого инвертора 7, мультиплексора 8, дешифратора низкого уровня 11, шифратора приоритетов 12, N-входового элемента И-НЕ 13, второго инвертора 14, селектора-мультиплексора 15, N абонентских блоков (АБ) l₁-l_N (схема АБ изображена на фиг. 12), К блоков выборки и фиксации (БВФ) 9₁-9_k (схема БВФ изображена на фиг. 13).

Элементы соединены между собой следующим образом (см. фиг. 11). Выход генератора тактовых импульсов 2 подключен к входу делителя 3 и второму входу элемента И 6. Выход делителя 3 подключен к тактовым входам 20 АБ. Первые сигнальные выходы 25₁-25_N АБ подключены соответственно к информационным входам A₁-A_N мультиплексора 8, выход Y которого подключен к входу первого инвертора 7 и к входу второго инвертора 14. Выход первого инвертора 7 подключен к первому входу элемента И 6 и к управляющим входам 29 каждого из К БВФ. Выход элемента И 6 подключен к счетному входу С счетчика 5. Вход сброса R счетчика 5 является опросным входом устройства 31. J информационных выходов Q₁-Q_J счетчика 5 подключены к соответствующим J входам "Код абонента" 27 БВФ, к соответствующим J управляющим входам V мультиплексора 8, к J входам а₁-а_j первой группы информационных входов селектора-мультиплексора 15, и к J информационным входам X₁-X_J дешифратора низкого уровня 11. Выход второго инвертора 14 подключен к разрешающему входу Е селектора-мультиплексора 15 и является разрешающим выходом 32 устройства. Запросные входы 16 АБ являются соответствующими запросными входами устройства. K-разрядные входы 17 "Код максимального времени ожидания" АБ являются соответствующими K-разрядными входами 17 "Код максимального времени ожидания" устройства. Входы "Обнуление" 18 АБ являются соответствующими входами "Обнуление" устройства. K-разрядные входы 19 "Код максимального времени обслуживания" АБ являются соответствующими К-разрядными входами 19 "Код максимального времени обслуживания" устройства. Инверсные входы 28 шифратора приоритетов 12 соединены с вторыми сигнальными выходами 28 АБ 1₁-1_N, при этом подключение осуществлено следующим образом: 1-й инверсный вход шифратора приоритетов 12 подключен к второму сигнальному выходу N-го АБ, 2-й инверсный вход шифратора приоритетов 12 подключен к второму сигнальному выходу N-1-гo АБ, n-й инверсный вход шифратора приоритетов 12 подключен к второму сигнальному выходу (N+1)-n-гo АБ, а N-й инверсный вход шифратора приоритетов 12 подключен к второму сигнальному выходу 1-го АБ. Кроме того, N инверсных входов 28 шифратора приоритетов 12 соединены с соответствующими N входами N-входового элемента И-НЕ 13. Инверсные выходы шифратора приоритетов 12 подключены к соответствующим J входам второй группы информационных входов B₁-B_J селектора-мультиплексора 15. Выход элемента И-НЕ 13 подключен к селективному входу V селектора-мультиплексора 15.

Выходы Y₁-Y_j селектора-мультиплексора 15 являются соответствующими J выходами 33 "Код подлежащего обслуживанию абонента" устройства. Выходы "Превышение" 24₁-24_N АБ 1₁-1_N подключены к соответствующим входам N-входового элемента И-НЕ 4. Выход N-входового элемента И-НЕ 4 подключен к входам 21 "Запрет" АБ 1₁-1_N. Инверсные выходы дешифратора низкого уровня 11 подключены соответственно к входам 22₁-22_N "Разрешение сравнения" АБ. K-разрядные выходы 23₁-23_N "Код оставшегося времени ожидания" каждого из N АБ подключены к N-разрядным входам 30₁-30_N "Разряды кода оставшегося времени ожидания" К БВФ, при этом подключение осуществлено следующим образом: 1-е разряды K-разрядных выходов 23₁-23_N "Код оставшегося времени ожидания" каждого из N АБ подключены к соответствующим разрядам N-разрядного входа 30₁ "Разряды кода оставшегося времени ожидания" 1-го БВФ, 2-е разряды K-разрядных выходов 23₁-23_N "Код оставшегося времени ожидания" каждого N АБ подключены к соответствующим разрядам N-разрядного входа 30₂ "Разряды кода оставшегося времени ожидания" 2-го БВФ, m-е разряды К-разрядных выходов 23₁-23_N "Код оставшегося времени ожидания" каждого из N AБ подключены к соответствующим разрядам N-разрядного входа 30_m "Разряды кода оставшегося времени ожидания" m-го БВФ, К-е разряды K-разрядных выходов 23₁-23_N "Код оставшегося времени ожидания" каждого из N АБ подключены к соответствующим разрядам N-разрядного входа 30_K "Разряды кода оставшегося времени ожидания" K-го БВФ. Выходы 10₁-10_K "Разряд выбранного кода оставшегося времени ожидания" К блоков выборки и фиксации подключены к соответствующим разрядам K-разрядных входов 26 "Выбранный код оставшегося времени ожидания" каждого из N АБ.

Генератор тактовых импульсов 2 предназначен для выработки синхронизирующей последовательности импульсов и может быть построен по любой известной схеме. См. , например, В. Л. Шило. Популярные микросхемы ТТЛ. - М. : АРГУС, 1993, с. 18.

Делитель 3 предназначен для увеличения периода следования поступающей на его вход последовательности импульсов. Конкретная величина необходимого деления зависит от выбранной тактовой частоты генератора тактовых импульсов устройства, а также от заданного диапазона выдержек времени _ож.i. Схемы реализации такого делителя известны. В частности, делитель может быть построен на счетчике. См. , например, П. П. Мальцев, Н. С. Долидзе и др. Цифровые интегральные микросхемы. Справочник. - М. : Радио и связь, 1994, с. 62-74. При этом входом делителя будет счетный вход счетчика, а выходом делителя - один из выходов счетчика.

Счетчик 5 предназначен для счета поступающих на его счетный вход импульсов и вывода их числа в двоичном коде. См. , например, П. П. Мальцев, Н. С. Долидзе и др. , Цифровые интегральные микросхемы. Справочник. - М. : Радио и связь, 1994, с. 62-74.

Мультиплексор 8 предназначен для поочередной коммутации сигнальных выходов 14 абонентских блоков на вход инвертора 7 и вход инвертора 14. См. , например, B. C. Тутников, В. В. Лопатин и др. Электронные устройства информационно-измерительной техники. Учебное пособие. -Л. : ЛПИ им. Калинина, 1980, с. 70-72.

Дешифратор низкого уровня 11 предназначен для преобразования поступающего на его вход двоичного кода в сигнал низкого уровня на одном из его выходов. Схемы реализации дешифратора низкого уровня известны. См. , например, П. П. Мальцев, Н. С. Долидзе и др. Цифровые интегральные микросхемы. Справочник. - М. : Радио и связь, 1994, с. 42-43.

Шифратор приоритетов 12 предназначен для преобразования сигнала низкого уровня на одном из его входов в двоичный код на его выходе, причем преобразование осуществляется с учетом приоритетов сигналов, соответствующих номерам входов. Схема реализации шифратора приоритетов известна. См. , например, П. П. Мальцев, Н. С. Долидзе и др. Цифровые интегральные микросхемы. Справочник. - М. : Радио и связь, 1994, с. 40.

Селектор-мультиплексор 15 предназначен для коммутации одной из двух J-разрядных групп входов на выход. Схемы реализации такого селектора-мультиплексора известны. См. , например, П. П. Мальцев, Н. С. Долидзе и др. Цифровые интегральные микросхемы. Справочник. - М. : Радио и связь, 1994, с. 36.

Абонентские блоки 1₁-1_N предназначены для контроля поступления сигналов запросов, подсчета оставшегося времени ожидания, сравнения оставшегося времени ожидания выбранного запроса с ВИЗ остальных запросов, выработки управляющих сигналов на внеочередное обслуживание запросов по результатам сравнения, а также управляющих сигналов на повышение приоритета по истечении установленного времени ожидания для каждого запроса.

Абонентский блок может быть реализован в различных вариантах. В частности, его схема, показанная на фиг. 12, содержит элемент И 1.1, элемент ИЛИ 1.2, инвертор 1.3, счетчик 1.4, трехвходовый элемент И 1.5, компаратор 1.6, трехвходовый элемент И-НЕ 1.7.

Первый вход элемента И 1.1 (см. фиг. 12) соединен с инверсным входом разрешения счета счетчика 1.4, с вторым входом трехвходового элемента И 1.5 и является запросным входом 16 АБ. K информационных входов ₁-D_K счетчик