Устройство для управления очередностьюОбСлужиВАНия Советский патент 1981 года по МПК G06F9/50 

(54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ОЧЕРЕДНОСТЬЮ ОБСЛУЖИВАНИЯ

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

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

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

ИЗФестно устройство для управления очередностью обслуживания, выполненное в виде матрицы, составленной из однотипных ячеек, и схемы уп1 авления. Каждая ячейка матрицы -содержит три KONa;yTaTOpa единиц и схему уйравления коммутаторами 1.2 ,

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

Наиболее близким к изобретению по технической сущности и достигаемому результату является устройство для управления очередностью обслуживания, выполненное в виде матрицы из однотипных ячеек и схемы управления. Ячейки матрицы, расположенные в пер0вой строке, соединены со входами и выходами устройства, а ячейки, расиоложенные в последнем столбце.- с входами и выходами схемы управления. Ячейка содержит три коммутатора еди5ниц и схему управления коммутаторами , содержащую элементы И, ИЛИ, НЕ, входы которой соединены со своими входами коммутаторов единиц,, а выход - с входами управления коммутаторов .

0

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

5

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

Поставленная цель достигается тем, что в устройство для управления очередностью обслуживания, выполненное

в виде матрицы с числом столбцов N, каждый узел которой содержит элементы И, ИЛИ,.НЕ, введены миогопороговый элемент и группа элементов задержки, а число строк матрицы равно N-M, где М - число входов устройства обслуживaeNttdx без очереди, причем входы устройства соединены со входами многопорогового элемента, каждый вхо устройства через соответствукйдий элемент задержки соединен с запросным входом первого узла соответствующего столбца матрищл, выход узла столбца матрицы соединен с запросным входом последующего узла столбца матрицы, выходы узлов послед ней строки матрицы являются выходами устройства, выход i-го порога многопороговогб элемента соединен с запрещакедими входами узлов )-ой строки матрицы и с разрешающими вхОда ми узлов (-м-1)-ой строки матрицы, а в каждом уйле матрицы запросный вход узла соединен с первым входом первого элемента и узла и через, первый элемент НЕ узла - с первым входОм второго элемента И узла, запрещающий вход узла через второй элемент НЕ уэла, выходы первого и второго элементов И узла через элемент ИЛИ узла -соединены со вторым входом первого элемента И узла,, второй вход второго элемента И узла и выход первого элемента И узла являются соответственно разрешающим входом и выходом узла.

На фиг. 1 представлена обобщенная структурная схема устройства; на фиг. 2 - один из конкр етных вариантов выполнения устройства.

Устройство для управления очередностью обслужкв-аяия содержит (фиг. 1) матрицу с узлами 1-4, многопороговый элемент 5, элементы б и 7 задержки, входы 8, .выходы 9, а каждый узел матрицы содержит элементы НЕ 10 и 11, элементы И 12 и 13, элементы ИЛИ 14, запросный вход 15, запрещающий вход 16, разрешающий вход 17, выход 18.

Конкретный вариант устройства содержит (фиг. 2) узлы 19-29, выходы 30-34, входы 35-39, выходы многопорогового элемента, элементы 43-45 задержки.

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

Пусть число выходов, обслуживаемы без очереди, равно 2 (т.е. число исходящих каналов а N 5 (см. фиг. 2). Веса всех входов элемента одинаковы и равны единице, а выходы 40-42 элемента 5 являются выходами порогов, соответствукяцих весам 3, 4 и 5...

При отсутствии на входах 35-39 устройства требований, на выходах 40-42 элемента 5 сигналы отсутствуют Отсутствие сигналов на запрещающих входах 16 узлов. 1-4., 19-29 разрешает прохождение через них требований.

Поэтому при поступлении на один из входов устройства, например 35, требовйния, оно проходит узлы 1, 22 и 3, вызывая шэявление на выходе 30 устройства сигнала, управляющего обслуживанием этого требования. Состояние элемента 5 при этом не изменится, поскольку наименьший его порог 3, а веса всех его входов одинаковы и равны i. При поступлении на устрой ;тво следующего тpeбoвaJiия, например по входу 36, оно проходит узлы 19, 23 и 27, вызывая появление на выходе 31 сигнала, управляющего обслуживанием этого требования.

При поступлении на устройство следукяцего требования, например по входу

37,на выходе 40 элемента 5 появится единица, которая поступает на запрещающие входы 16 узлов 1, 2, 19-21. Поэтому требование, поступившее по входу 37, пройдя элемент 44 задержки, не пройдет через узел 20. Величина задержки элемента 44 (а также элементов 6, 7, 43 и 45) должна быть не меньше, чем время срабатывания элемента 5.

Поступление сигнала на запрещающие входы 16 узлов 1 и 19 не препятствует прохождению требования через эти узлы, поскольку эти требования поступили до прихода запрещающего сигнала.

Следующее требование, поступившее, например, по входу 38, вызывает появление на выходе 41 элемента 5 единицы, которая поступает на резрешающие входы 17 узлов 1, 2, 19-21. Это разрешает прохождение требований через узЛы 2, 21, несмотря на наличи запрещающего сигнала на входах 16 этих узлов. (Что касается узла )0, то через него требование по-прежнему не проходит, поскольку оно поступило после прихода запрещающего, но до Прихода разрешающего сигнала). Поэтому требование, поступившее по входу

38,пройдет через узел 21, но не пройдет через, узел 25, поскольку на его вход 16 поступает запрещающий . сигнал с выхода 41 элемента 5,

Последнее требование, поступившее по входу 39, вызывает появление едини №3 на выходе 42 элемента 5. В ре.зультате узлы 2 и 26 оказываются открыты для прохождения через «их требований, а узел 4 эакрыт. Требование пройдат через уэлы 2 и 26, но не пройдет через узел 4. Таким образом, на входы устройства поступило пять требований, из которых два требования (Н-2}, поступивших первыми, отобраны для обслуживания, а остальные (Н-м) ожидают очереди. При снятии обслуживаемых требований (по окончании их обслуживания) устройство должно осуществля ь обслуживание ожидающих очереди требований в порядке, обратном очередности их поступления.

Это происходит следующим образом. При снятии обслуживаемого требования, например, с выхода 35 снимаются единицы с выходов 18 узлов 1, 22, 3 и с выхода 42 элемента 5. Снятие запрещающего сигнала с входов 16 узлов последней строки разрешает прохождение через них требований. В результате требование, находящееся на выходе 18 узла 26, вызывает появление сигнала на выходе 34 устройства. Этот сигнал управляет обслуживанием требования, поступающего по входу 39, т.е. последнего требования из очереди (самого сзвежего).

При снятии обслуживаемого требования, например, с входа 36 снимаются единицы с выходов 18 узлов 19, 23, 27 и с выхода 41 элемента 5; Снятие сигнала с входов 16 узлов второй строки разрешает прохождение требований через эти узлы. Поэтому требование, находящееся на выходе 18 узла 21, проходит через узел 25, затем через узел 29 (с его 16 единица снята еще раньше) и вызывает появление на выходе 33 сигнала,-управляющего обслуживанием требования, поступившего по входу 38.

При снятии следующего обслуживаемого требования, например, с входа 39 снимается единица : с выхода 40 элемента 5, что разрешает прохождение требования, поступившего по входу 37 через узлы 20, 24 и 28. В результате на выходе 32 устройства появляется сигнал, управляющий обслуживанием требованяя, поступившего первым (т.е. самого старого).

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

Таким образом, изобретение имеет меньше оборудования.

В самом деле, узлы матрицы известного устройства содержат 27 элементов И, ИЛИ, НЕ, а узлы матрицы изобретев ьия - пять аналогичных элементов. Для обслуживания 10-ти каналов извест ное устройство должно содержать 2490 элементов И, ИЛИ, НЕ и 20 элементов задержки. Предложенное же устройство для обслуживания 10-ти каналов с пойощью изобретения требует 560 элементов И, ИЛИ, НЕ и 10 элементов задержки при числе М исходящих каналов равным 1 (наихудший для изобретения случай). При увеличении М указанное соотношение еще более улучшается. Так при М 8 количество элементов И,

ИЛИ, НЕ В изобретении равно 210. Б известном устройстве количество элементов от М не зависит. Для управления можно применить и любое устройство, реализующее все свои пороги и в котором веса входов одинаковы и равны единице,

Вьютродействие известного устройства определяется выражением tj te(N-l). + 4, где t - задержка одного логического элемента; N - число входящих каналов. Аналогичное выражение для изобретения имеет вид t(N-M) + эа ® исходящих каналов; tg - задержка, вносимая &лементами задержки. Поскольку зъ быть не меньше времени срабатывания порогового элемента, равного t(N-H) (максимальное значение) , то общее выражение для быстродействия изобретения имеет вид t(2N - М + 1). Например, при N tO и М 6 быстродействие известного устройства равно 76 tj, а изобретения - 15 t.

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

Устройство для управления очередностью обслуживания, выполненное в виде матрицы с числом столбцов N, каждый узел которой содержит элементы И, ИЛИ, НЕ, отличающеес я тем, что, с целью сокращения оборудования,и повышения быстродействия, оно содержит многопороговый элемент и группу элементов задержки, а число строк матрицы равно N-M, где М - число выходов устройства,обслуживаемых без очереди, причем входы устройства соединены со входами многопорогового элемента, каждый вход устройства через соответствующи элемент задержки соединен с запросны входом первого узла соответствующего столбца матри :, выход узла столбца матрицы соединен с запросным входом последующего узла столбца матрицы, выходы узлов последней строки матрицы являются выходгили устройства, выход i-ro порога многопорогового элемента соединен с запрещающими входами узлов (i-М)-ой строки матрицы и с разрешакяцими входами узлов (1-М-1)-ой строки матрицы, а в каждом узле матрицы запросный вход узла соединен с первьм входом первого элемента И узла и через первый элемент НЕ узла - с первым входом второго элемента И узла, запрещающий вход узла через второй элемент НЕ узла, выходы первого и второго элементов И узла через элемент ИЛИ узла соединены со вторым входом первого элемента И узла, второй вход второго элемента И узла и выход первого элемен80531та И узла.являются соответственно разрешающим еходом и выходом узла. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР №496558, кл. G 06 F 9/00, 1970, 18 2.Сборник Известия ВУЗов. Серия Электромеханика, 1974, № 3, с. 239, рис. 6. 3.Там же, 1975, № 11, с. 122 (прототип).

35

а/н

18

17

/.Xf

16 f15

i2J

18

f7 W

42

37

,15

20

17

f8

8

18

fd

17 78

1

В

16

16

Ф1.г