Устройство для управления очередностьюобслуживания

 

Союз советских

Социалистических

Ресвублнк

QHHCAHHE

ИЗОБРЕТЕНИЯ

К АВТОИ:КОМУ СВИДН ИЛЬСТВУ

ii@805311 (61) Дополнительное и авт. свнд»ву— (22) Заявлено 091078 Д1) 2672498/18-24 с присоединением заявим H9 .— (23) Приоритет

Опублниовано 1802.81. бюллетень 89 6

Дата опубликования описания 18.02.81 (51)м. ê,з

G F 9/46

Государственный комитет

СССР но делам изобретений и открытий (И) >4К 681. З25 (088.8) (72) Авторы изобретения

Ю.В. Бочин и Г.A. Сатышев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ОЧЕРЕДНОСТЬЮ

ОБСЛУЖИВАНИЯ

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

"пришел последним — обслужен первым".

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

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

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

Каждая ячейка матрицы содержит три ком .утатора единиц и схему управления коммутаторами (2 ).

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

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

Ячейки матрицы, расположенные в первой строке, соединены со входами и выходами устройства, а ячейки, расПоложенные в последнем столбце. — с входами и выходами схемы управления.

Ячейка содержит три коммутатора единиц и схему управления коммутаторами, содержащую элементы И, ИЛИ, НЕ, входы которой соединены со своими входамИ коммутаторов единиц,, а выход — с входами управления коммутаторов (31.

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

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

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

Ъ. в виде матрицы с числом столбцов й, каждый узел которой содержит элементы И, ИЛИ,,НЕ, введены многопоро» говый элемент и группа элементов задержки, а число строк матрицы равно й-й, где И вЂ” число входов устройства, обслуживаемых без очереди, причем входы устройства соединены со входами многопорогового элемента, каждый вход устройства через соответствующий элемент задержки соединен с запросным входом первого узла соответствующего столбца матрицы, выход узла столбца матрицы соединен с запросным входом последующего узла столбца матрицы, выходы узлов последней строки матрицы являются выходами устройства, выход i-ro порога многопорогового элемента соединен с запрещающими входами узлов (i-И)-ой строки матрицы и с разрешающими входами узлов (i-И-1)-ой строки матрицы, а в каждом УЫле матрицы запросный вход узла соединен с первым входом первого элемента И узла и через первый элемент

HE узла — с первым входом второго элемента И узла, запрещающий вход узла через второй элемент НЕ узла, выходы первого и второго элементов И узла через элемент ИЛИ узла соединены со вторым входом первого элемента

И узла, второй вход второго элемента И узла и выход первого элемента И узла являются соответственно разрешающим входом и выходом узла.

На фиг. 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, выходы 49-42 многопорогового элемента, элементы

43-45 задержки, Устройство работает следующим образом, .Пусть число выходов, обслуживаемых без очереди, равно 2 (т.е. число исходящих каналов И = 2; а И = 5 (см. фиг. 2). Веса всех входов элемента 5 одинаковы и равны единице, а выходы

40-42 элемента 5 являются выходами порогов, соответствующих весам 3, 4 и 5, При отсутствии на входах 35-39 устройства требований, на выходах

40-42 элемента 5 сигналы отсутствуют.

Отсутствие сигналов на запрещающих входах 16 узлов 1-4., 19-29 разрешает прохождение через них требований.

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

31 сигнала, управляющего обслуживанием этого требования.

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

37, на. выходе 40 элемента 5 появится

"единица", которая поступает на запрещающие входы 16 узлов 1, 2, 19-21.

Поэтому требование, поступившее по

2О входу 37, пройдя элемент 44 задержки, не пройдет через узел 20. Величина задержки элемента 44 (а также элементов 6, 7, 43 и 45) должна быть не меньше, чем время срабатывания элемента 5.

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

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

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

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

60 (Н-И) ожидают очереди. При снятии обслуживаемых требований (по окончании их обслуживания) устройство должно осуществлять обслуживание ожидающих очереди требований в порядке, 65 обРатном очередности их поступления.

805311

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

Это происходит следующим образом.

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

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

При снчтии следующего обслужива- Зо емого требования, например, с входа

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

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

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

В самом деле, узлы матрицы известного устройства содержат 27 элемен» тов И, ИЛИ, НЕ, а узлы матрицы изобретения — пять аналогичных элементов.

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

Так при М = 8 количество элементов И, 65

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

Быстродействие известного устройства определяется выражением

t> (8(N-1). + 4), где t> — задержка одного логического элемента; и — число входящих каналов. Аналогичное выражение для изобретения имеет вид

+ ЗЗ Fgfe Н вЂ” число щих каналов; t — задержка, вносимая элементами задержки. Поскольку должно быть не меньше времени срабатывания порогового элемента, равного t (И+1) (максимальное знаЪ ченне), то общее выражение для быстродействия изобретения имеет вид

t>(2N - И + 1). Например, при N = 10 и и = 6 быстродействие известного устройства равно 76 t3, а изобретения — 15

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

НЕ узла — с первым входом второго элемента И узла, запрещающий вход узла через второй элемент HE узла, выходы первого и второго элементов И узла через элемент ИЛИ узла соединены со вторым входом первого элемента И узла, второй вход второго элемента И узла и выход первого элемен805311 та И узла.явля отся соответственно разрешакщим входом и выходом узла.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

М 496558, кл. G Об F 9/ОО, 1970.

2. Сборник "Известия ВУЗов". Се-. рия "Электромеханика", 1974, Р 3, с. 239, рис. б.

3. Там же, 1975, 9 11, с. 122 (прототип).

805311

Г

17 В /7

Заказ 10903/71

Тираж 756 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 - Москва Ж-35 Ра шская наб. . 4 5

I Г

У, д /

Филиал ППП "Патент", г. ужгород, ул, Проектная, 4

Составитель ф. Шагиахметов

Редактор С. Лыжов Техред N. Коштура Корректор М. Вигула