УСТРОЙСТВО ПАКЕТНОЙ ОБРАБОТКИ ЗАПРОСОВ Российский патент 1995 года по МПК G06F9/46 

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

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

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

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

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

Это достигается тем, что устройство пакетной обработки запросов, содержащее первый n-разрядный регистр заявок, где n число абонентов устройства, группу из n регистров приоритета, группу из n схем сравнения, счетчик, две группы из n элементов И, группу из n триггеров, два элемента И, три элемента ИЛИ, триггер и генератор тактовых импульсов, дополнительно содержит второй n-разрядный регистр заявок, второй счетчик, схему сравнения, триггер режима, регистр, делитель частоты, блок элементов И, четвертый, пятый элемент ИЛИ, третий, четвертый элементы И, причем группы запросных входов и ответных входов устройства соединены соответственно с группами информационных входов и входов сброса первого регистра, нулевые входы триггеров группы соединены с группой ответных входов устройства, группа информационных входов i-го (i=1. n) регистра приоритета группы является группой входов приоритета устройства, единичный выход i-го триггера группы подключен к i-ому входу третьего элемента ИЛИ и является информационным выходом устройства, первый вход первого элемента ИЛИ является входом запуска устройства, информационные входы регистра являются входами времени обслуживания пакета заявок, входы установки в единичное и нулевое состояние триггера режима являются соответственно первым и вторым входами управления режимом работы устройства, группа ответных входов устройства соединена с группой входов сброса второго регистра заявок.

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

Устройство содержит первый регистр 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, 32 управления режимом работы устройства, информационные выходы 33, причем группа информационных входов i-го (i= 1.n) регистра 2 приоритета группы является группой входов 27 приоритета устройства, выход i-го регистра 2 приоритета группы подключен к первому входу i-й схемы 3 сравнения группы, а вторые входы всех схем сравнения группы соединены с выходом счетчика 4, счетный вход которого соединен с выходом элемента И 8, первый прямой вход которого подключен к единичному выходу триггера 13, нулевой вход которого соединен с инверсным входом элемента И 8 и выходом элемента И 9, входы установки в единичное состояние всех разрядов счетчика 4 и триггера 13 подключены к выходу элемента ИЛИ 11, выход i-й схемы 3 сравнения группы подключен к первому входу i-го элемента И 5 группы, второй вход которого соединен с нулевым выходом i-го триггера 7 группы, выход i-го элемента И 5 группы соединен с прямым входом i-го элемента И 6 группы и с i-ым входом элемента ИЛИ 10, выход которого подключен к первому входу элемента И 9, второй вход которого соединен с выходом элемента ИЛИ 12 и с инверсными входами элементов И 6 группы, выход i-го элемента И 6 группы соединен с i-ым входом первой группы входов элемента ИЛИ 11 и с единичным входом i-го триггера 7 группы, единичный выход которого подключен к i-ому входу элемента ИЛИ 12 и является информационным выходом 33 устройства, первый вход элемента ИЛИ 11 является входом 26 запуска устройства, группы запросных 28 и ответных 29 входов устройства соединены соответственно с группами информационных входов и входов сброса регистра 1 заявок, нулевые входы триггеров 7 группы соединены с группой ответных 29 входов устройства, выход i-го разряда регистра 1 заявок подключен к i-ому входу блока элементов И 21, вход которого соединен с выходом элемента ИЛИ 22 и входом установки в нулевое состояние счетчика 16, i-й выход блока элементов И 21 подключен к i-ому входу регистра 15 заявок и i-ому входу второй группы входов элемента ИЛИ 11, i-й выход регистра 15 заявок соединен с третьим входом i-го элемента И 5 группы и с i-ым входом элемента ИЛИ 23, инверсный выход которого подключен к первому входу элемента ИЛИ 22, второй вход которого соединен с выходом элемента И 24, первый вход которого подключен к единичному выходу триггера 18 и первому прямому входу элемента И 25, второй вход элемента И 24 соединен с выходом схемы 17 сравнения и инверсным входом элемента И 25, первая группа входов схемы 17 сравнения подключена к выходам регистра 19, а вторая группа входов к выходам счетчика 16, информационные входы регистра 19 являются входами 30 времени обслуживания пакета устройства, второй прямой вход элемента И 25 соединен с выходом делителя 20 частоты, вход которого соединен с выходом генератора 14 импульсов и вторым прямым входом элемента И 8, входы установки в единичное и нулевое состояние триггера 18 режима являются соответственно первым и вторым входами 31, 32 управления устройства, группа ответных входов 29 устройства соединена с группой входов сброса регистра 15 заявок, выход элемента И 25 соединен со счетным входом счетчика 16.

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

Коды приоритетов абонентов по входам 27 устройства заносятся в соответствующие регистры 2 приоритета, причем самому высокому приоритету соответствует наибольший из кодов. Код заданного для обслуживания пакета заявок временного интервала по входу 30 устройства заносится в регистр 19. Триггер 18 по входам 31 или 32 устанавливается в единичное или нулевое состояние в зависимости от выбранного режима работы устройства. Перед началом работы устройства все триггеры 7 и счетчик 16 находятся в нулевом состоянии. В результате элементы И 5 первой группы открыты по второму входу, элементы И 6 второй группы по инверсному входу, а элемент И 9 закрыт по первому входу нулевым сигналом с выхода элемента ИЛИ 12. На выходе схемы 17 сравнения присутствует нулевой сигнал, открывающий по инверсному входу элемент И 25.

При выборе режима работы устройства без задания ограничения на время обслуживания пакета, что соответствует начальной установке триггера 18 в нулевое состояние по входу 32, на единичном выходе триггера 18 присутствует нулевой сигнал, закрывающий по первым входам элементы И 24, 25. При выборе режима работы устройства с заданием ограничения на время обслуживания пакета заявок (начальная установка триггера 18 в единичное состояние по входу 31 устройства), элементы И 24, 25 оказываются открытыми по первым входам единичными сигналами с единичного выхода триггера 18.

В исходном состоянии при отсутствии запросов в регистре 15 заявок на инверсном выходе элемента ИЛИ 23 присутствует единичный сигнал, который через элемент ИЛИ 22 поступает на управляющий вход блока элементов И 21, открывая их. Тем самым разрешается перепись содержимого регистра 1 в регистр 15. Единичный сигнал с выхода элемента ИЛИ 22 поступает также на вход установки в нулевое состояние всех разрядов счетчика 16.

Запросы на обслуживание поступают через запросные входы 28 устройства в соответствующие разряды регистра 1 заявок, число разрядов которого равно числу абонентов n. При поступлении первой заявки на обслуживание в регистр 1 (одновременном поступлении нескольких заявок) соответствующие разряды регистра 1 устанавливаются в единичное состояние. На входе блока элементов И 21 присутствует единичный сигнал, разрешающий перепись информации из регистра 1 в регистр 15, следовательно соответствующие разряды регистра 15 также установятся в единичное состояние. На инверсном выходе элемента ИЛИ 23 появится нулевой сигнал, закрывающий по первому входу элемент ИЛИ 22. В результате по входу закрывается блок элементов И 21, что запрещает перепись информации из регистра 1 в регистр 15. Нулевой сигнал с выхода элемента ИЛИ 22 поступает также на вход установки в нулевое состояние счетчика 16, разрешая выполнение операции суммирования в режиме с заданием ограничения на время обслуживания пакета заявок.

Таким образом, в регистре 15 будут зафиксированы одна или несколько одновременно поступивших запросов от абонентов, образующих первый пакет заявок. При переписи не нулевого содержимого регистра 1 в регистр 15 на соответствующих входах второй группы входов элемента ИЛИ 11 появятся единичные сигналы, длительность которых достаточна для установки в единичное состояние триггера 13 и всех разрядов счетчика 4. Тем самым инициируется начало цикла работы устройства. Сигнал с единичного выхода триггера 13 открывает по первому прямому входу элемент И 8, разрешая поступление импульсов с выхода генератора 14 на счетный вход счетчика 4. Элемент И 8 открыт по инверсному входу нулевым сигналом с выхода элемента И 9. На выходе счетчика 4 формируется убывающая последовательность двоичных кодов чисел, начиная от максимально возможного. При совпадении кодов на выходе счетчика 4 с кодом в каком-либо регистре 2 приоритета на выходе соответствующей схемы 3 сравнения появится единичный сигнал, который через элемент И 5, открытый по первому входу сигналом с соответствующего разряда регистра 15 заявок, зафиксировавшего запрос от абонента, поступает на входы элемента ИЛИ 10 и соответствующего элемента И 6 второй группы. С выхода элемента ИЛИ 10 единичный сигнал поступает на второй вход элемента И 9, закрытого по первому входу нулевым сигналом с выхода элемента ИЛИ 12. Элементы И 6 открыты по инверсному входу, поэтому сигнал с выхода элемента И 5 проходит через элемент И 6, устанавливает в единичное состояние соответствующий триггер 7, а также через элемент ИЛИ 11 поступает на входы установки в "1" триггера 13 и счетчика 14. Единичный сигнал с единичного выхода триггера 7 поступает на выход 33 устройства, инициируя обслуживание соответствующего абонента. Этот же сигнал через элемент ИЛИ 12 закрывает по инверсным выходам все элементы И 6 второй группы. Тем самым исключается установка в единичное состояние других триггеров 7 до окончания обслуживания данного абонента. Нулевой сигнал с нулевого выхода триггера 7, соответствующего абоненту, поставленному на обслуживание, закрывает по второму входу соответствующий элемент И 5 первой группы. Тем самым исключается опрос данного абонента во всех последующих циклах работы устройства до окончания его обслуживания.

Сигнал с выхода элемента ИЛИ 11 инициирует еще один дополнительный цикл работы устройства, в котором определяется следующая по приоритету заявка из очереди на обслуживание. На выходах счетчика 4 вновь формируется убывающая последовательность кодов чисел, начиная от максимально возможного. При совпадении кодов на выходах счетчика 4 с кодом в каком-либо регистре 2 приоритета на выходе соответствующей схемы 3 сравнения формируется единичный сигнал. При наличии запроса в соответствующем разряде регистра 15 заявок, а также при условии, что соответствующий триггер 7 находится в нулевом состоянии, т.е. если обслуживаемый пакет заявок содержит более одной заявки, единичный сигнал с выхода схемы 3 сравнения через соответствующий элемент И 5 первой группы поступает на прямой вход элемента И 6 второй группы. Так как все элементы И 6 второй группы закрыты по инверсным входам, то сигнал на вход установки в "1" триггера 7 не поступает. С выхода элемента И 5 единичный сигнал через элемент ИЛИ 10 поступает также на второй вход элемента И 9. В этом цикле работы устройства элемент И 9 открыт по первому входу единичным сигналом с выхода элемента ИЛИ 12. Поэтому на выходе элемента И 9 появляется единичный сигнал, который устанавливает в нулевое состояние триггер 13 и закрывает элемент И 8 по инверсному входу. В результате прекращается поступление сигналов с выхода генератора 14 на счетный вход счетчика 4 устройства. Таким образом, на выходе элемента И 5 первой группы, соответствующего наиболее приоритетной заявке из необслуженных заявок данного пакета, постоянно присутствует единичный сигнал. Если пакет заявок состоит из одной заявки, зафиксированной в регистре 15, то в дополнительном цикле работы устройства на выходе счетчика 4 будет формироваться циклическая последовательность двоичных кодов чисел до появления единичного сигнала на выходе элемента ИЛИ 11.

По окончании обслуживания очередного абонента сигнал ответа по входу 29 устройства устанавливает в нулевое состояние соответствующие разряды регистров 1, 15 и триггер 7. Нулевым сигналом с выхода элемента ИЛИ 12 открываются по инверсным входам все элементы И 6 второй группы. Если в обслуживаемом пакете заявок выделена очередная наиболее приоритетная заявка, то сигнал с выхода соответствующего элемента И 5 через элемент И 6 устанавливает в единичное состояние соответствующий триггер 7. Тем самым заявка старшего приоритета из очереди, зафиксированной в регистре 15, ставится на обслуживание. Одновременно единичный сигнал с выхода элемента И 6 через элемент ИЛИ 11 поступает на вход установки в единичное состояние счетчика 4 и триггера 13, т. е. инициируется очередной цикл работы устройства, позволяющий выделить из очереди, зафиксированной в регистре 15, следующую по приоритету заявку за обслуживаемой.

При поступлении по входу 29 устройства сигнала об окончании обслуживания заявки, являющейся последней в обслуживаемом пакете заявок, устанавливаются в нулевое состояние соответствующие разряды регистров 1, 15 и триггер 7. При этом все разряды регистра 15 оказываются в нулевом состоянии, поэтому на инверсном выходе элемента ИЛИ 23 установится единичный сигнал, поступающий через элемент ИЛИ 22 на вход блока элементов И 21 и на вход установки в нулевое состояние всех разрядов счетчика 16. Тем самым разрешается перепись содержимого регистра 1 в регистр 15. Заявки, поступающие в регистр 1 во время обслуживания заявок, зафиксированных в регистре 15, образуют очередной пакет заявок. Счетчик 16 обнуляется. Во время переписи пакета заявок в регистр 15 единичные сигналы с выходов блока элементов И 21 через элемент ИЛИ 11 устанавливают в единичное состояние все разряды счетчика 4 и триггер 13. Тем самым инициируется очередной цикл работы устройства по выявлению наиболее приоритетной заявки в очередном пакете заявок. После переписи очередного пакета заявок в регистр 15 на инверсном выходе элемента ИЛИ 23 появится нулевой сигнал, поступающий через элемент ИЛИ 22 на вход блока элементов И 21 запрещающий перепись информации из регистра 1 в регистр 15. Пакет заявок, зафиксированных в регистре 15, начинает обслуживаться в соответствии с заданными в регистрах 2 приоритетами. Очередной пакет заявок формируется в регистре 1 во время обслуживания заявок текущего пакета.

Циклы работы устройства запускаются каждый раз при поступлении сигнала окончания обслуживания очередной заявки по входу 29 при наличии единичного сигнала (выявленной заявки) на прямом входе соответствующего элемента И 6. Кроме того, цикл работы устройства запускается при наличии единичного сигнала на управляющем входе блока элементов И 21 при переписи не нулевого содержимого регистра 1 в регистр 15. В каждом цикле работы устройства могут быть изменены приоритетные коды абонентов. В этом случае цикл работы устройства по выявлению старшей по приоритету заявки из очереди пакета должен быть инициирован сигналом по входу 26 запуска устройства.

При установке триггера 18 в единичное состояние, что соответствует режиму работы устройства с заданием ограничения на время обслуживания пакета заявок, элементы И 24, 25 оказываются открытыми по первым входам. Импульсы с выхода генератора 14 через делитель 20 частоты и элемент И 25 поступают на счетный вход счетчика 16. При отсутствии заявок в регистре 15 единичный сигнал с инверсного выхода элемента ИЛИ 23 через элемент ИЛИ 22 поступает на вход установки в ноль счетчика 16, блокируя выполнение операции суммирования в счетчике 16. При переписи очередного пакета заявок в регистр 15 на выходе элемента ИЛИ 22 установится нулевой сигнал, разрешающий выполнение операции суммирования в счетчике 16. В результате на выходе счетчика 16 формируется возрастающая последовательность двоичных кодов чисел, пропорциональных времени обслуживания пакета заявок. При совпадении двоичного кода, занесенного в регистр 19 по входу 30 устройства, и кода, формируемого на выходе счетчика 16, т. е. по истечении заданного для обслуживания пакетов заявок временного интервала на выходе схемы 17 сравнения формируется единичный сигнал, поступающий на инверсный вход элемента И 25 и на второй вход элемента И 24. Элемент И 25 закрывается по инверсному входу. В результате прекращается поступление импульсов на счетный вход счетчика 16. На выходе элемента И 24 появится единичный сигнал, который через элемент ИЛИ 22 поступит на вход установки в ноль счетчика 16 и вход блока элементов ИЛИ 21, разрешая перепись содержимого регистра 1 в регистр 15. При переписи заявок в регистр 15 единичные сигналы с выходов блока элементов И 21 через элемент ИЛИ 11 устанавливают в единичное состояние все разряды счетчика 4 и триггер 13. Инициируется цикл работы устройства по выявлению наиболее приоритетной заявки в очередном пакете заявок. В пакете могут присутствовать заявки, не обслуженные за выделенное для обслуживания предыдущего пакета заявок время, и новые заявки, поступившие в регистр 1 во время обслуживания предыдущего пакета заявок. Длительность сигнала на управляющем входе блока элементов И 21 достаточна для записи пакета заявок в регистр 15 и инициирования нового цикла работы устройства.

При установке триггера 18 в нулевое состояние по второму управляющему входу 32 устройства элементы И 24, 25 оказываются закрытыми по первым входам. В результате блокируется поступление импульсов на счетный вход счетчика 16 и закрывается по второму входу элемент ИЛИ 22. Тем самым снимается ограничение на время обслуживания текущего пакета заявок.

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

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

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

УСТРОЙСТВО ПАКЕТНОЙ ОБРАБОТКИ ЗАПРОСОВ, содержащее первый n-разрядный регистр заявок (где n число абонентов устройства), группу из n регистров приоритета, группу из n схем сравнения, счетчик, две группы из n элементов И, группу из n триггеров, два элемента И, три элемента ИЛИ, триггер и генератор тактовых импульсов, причем группа информационных входов регистров приоритета группы является группой кода приоритета устройства, выход i-го (i 1 n) регистра приоритета группы подключен к первому входу i-й схемы сравнения группы, вторые входы всех схем сравнения группы соединены с выходом счетчика, счетный вход которого соединен с выходом первого элемента И, первый прямой вход которого подключен к единичному выходу триггера, нулевой вход которого соединен с инверсным входом первого элемента И и выходом второго элемента И, входы установки в единичное состояние всех разрядов счетчика и триггера подключены к выходу первого элемента ИЛИ, выход i-й схемы сравнения группы подключен к первому входу i-го элемента И первой группы, второй вход которого соединен с нулевым выходом i-го триггера группы, выход i-го элемента И первой группы соединен с прямым входом i-го элемента И второй группы и с i-м входом второго элемента ИЛИ, выход которого подключен к второму входу второго элемента И, второй вход которого соединен с выходом третьего элемента ИЛИ и с инверсными входами элементов И второй группы, выход i-го элемента И второй группы соединен с i-м входом первой группы входов первого элемента ИЛИ и с единичным входом i-го триггера группы, единичный выход которого подключен к i-му входу третьего элемента ИЛИ и является информационным выходом устройства, первый вход первого элемента ИЛИ является входом запуска устройства, группа запросных и ответных входов устройства соединена соответственно с группами информационных входов и входов сброса первого регистра, нулевые входы триггеров группы соединены с группой ответных входов устройства, отличающееся тем, что оно содержит второй n разрядный регистр заявок, второй счетчик, схему сравнения, триггер режима, регистр, делитель частоты, блок элементов И, четвертый, пятый элементы ИЛИ, третий, четвертый элементы И, причем выходы первого регистра заявок подключены к соответствующим входам группы входов блока элементов И, вход которого соединен с выходом четвертого элемента ИЛИ и входом установки в нулевое состояние второго счетчика, i-й выход блока элементов И подключен к i-му входу второго регистра заявок и к i-му входу второй группы входов первого элемента ИЛИ, i-й выход второго регистра заявок соединен с третьим входом i-го элемента И первой группы и с i-м входом пятого элемента ИЛИ, инверсный выход которого подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, первый вход которого подключен к единичному выходу триггера режима и первому прямому входу четвертого элемента И, второй вход третьего элемента И соединен с выходом схемы сравнения и инверсным входом четвертого элемента И, первая группа входов схемы сравнения подключена к выходам регистра, а вторая группа входов к выходам второго счетчика, информационные входы регистра являются входами времени обслуживания пакета устройства, второй прямой вход четвертого элемента И соединен с выходом делителя частоты, вход которого соединен с выходом генератора тактовых импульсов и вторым прямым входом первого элемента И, входы установки в единичное и нулевое состояния триггера режима являются соответственно первым и вторым входами управления режимом работы устройства, группа ответных входов устройства соединена с группой входов сброса второго регистра заявок, выход четвертого элемента И соединен со счетным входом второго счетчика.