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

Союз СоветскихСоциалистическихРесвублнк ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОИ:КОМУ СВИДОЗЛЬСТВУ(22) Заявлено 091078 (31) 2672498/18-24с присоединением заявки йо . -(51)М, Кл,з С 06 Г 9/46 Государственный комитет СССР но делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ОЧЕРЕДНОСТЬЮ ОБСЛУЖИВАНИЯ Изобретение относится к вычислительной технике, в частности к устройствам для управления очередностью обслуживания, и может быть использовано в системах, где необходима реализация обслуживания запросов в инверсном порядке, т.е. по правилу "пришел последним - обслужен первым".Известно устройство для управления очередностью обслуживания, содержащее счетчики записи и считывания, а в каждом канале регистр и схему сравнения (11 .Недостаток устройства - ограниченные функциональные возможности, обу словленные реализацией обслуживания запросов в порядке поступления.Известно устройство для управления очередностью обслуживания, выполненное в виде матрицы, составленной вэ 20 однотипных ячеек, и схемы управления. Каждая ячейка матрицы содержит три кою 1 утатора единиц и схему управления коммутаторами )2).устройство предназначено для реа" 25 лизации обычной (прямой) очереди и не может быть использовано для реализации инверсной очереди беэ прерывания (т.е. такой дисциплины обслуживания, при которой реализуется прин цип - "последним пришел - первым поставлен в очередь").Наиболее близким к изобретению потехнической сущности и достигаемомурезультату является устройство дляуправления очередностью обслуживания,выполненное в виде матрицы из однотипных ячеек и схемы управления.Ячейки матрицы, расположенные в первой строке, соединены со входами ивыходами устройства, а ячейки, расПоложенные в последнем столбце, - свходами и выходами схемы управления.Ячейка содержит три коммутатора единиц и схему управления коммутаторами, содержащую элементы И, ИЛИ, НЕ,входы которой соединены со своимивходамИ коммутаторов единиц а выход - с входами управления коммутаторов 31,Недостаток устройства - необходимость для его построения большогочисла логических элементов, а такжеего малое быстродействие.Цель изобретения - сокращение оборудования и повышение быстродействия.Поставленная цель достигается тем,что в устройство для управления очередностью обслуживания, выполненноеъ,в виде матрицы с числом столбцов й,каждый узел которой содержит элементы И, ИЛИНЕ, введены многопороговый элемент и группа элементов задержки, а число строк матрицы равной-и, где И - число входов устройства,обслуживаемых без очереди, причемвходы устройства соединены со входамимногопорогового элемента, каждый входустройства через соответствующий элемент задержки соединен с запроснымвходом первого узла соответствующегостолбца матрицы, выход узла столбцаматрицы соединен с запросным входомпоследующего узла столбца матрицы,выходы узлов последней строки матрицы являются выходами устройства, выход -го порога многопорогового элемента соединен с запрещающими входами узлов (-И)-ой строки матрицы ис разрешающими входами узлов(-г 1-)-ой строки матрицы, а в каждом УЫле матрицы запросный вход узласоединен с первым входом первого элемента И узла и через первый элементНЕ узла - с первым входом второгоэлемента И узла, запрещающий входузла через второй элемент НЕ узла,выходы первого и второго элементов Иузла через элемент ИЛИ узла соединены со вторым входом первого элементаИ узла, вторбй вход второго элемента И узла и выход первого элемента И .узла являются соответственно разрешающим входом и выходом узла.На фиг. 1 представлена обобщеннаяструктурная схема устройства; нафиг. 2 - один из конкретных вариантов выполнения устройства.Устройство для управления очередностью обслуживания содержит (фиг,1)матрицу с узлами 1-4, многопороговыйэлемент 5, элементы 6 и 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 сигнала, управляющего обслуживанием этого требования.1При поступлении на устройство слез дующего требования, например по входу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 О то через него требование по-прежнемуне проходит, поскольку оно поступилопосле прихода запрещающего, но доприхода разрешающего сигнала). Поэтому требование, поступившее по входу 4 38, пройдет через узел 21, но непройдет через узел 25, поскольку наего вход 16 поступает запрещающийсигнал с выхода 41 элемента 5.Последнее требование, поступившеепо входу 39, вызывает появление "единицы" на выходе 42 элемента 5. В ре.- зультате узлы 2 и 26 оказываются открыты для прохождения через них требований, а узел 4 закрыт. Требованиепройдет через узлы 2 и 26, но непройдет. через узел 4. Таким образом,на входы устройства поступило пятьтребований, из которых два требования (И), поступивших. первыми, отоб"раны для обслуживания, а остальные 6 О (Н-Я) ожидают очереди. При снятииобслуживаемых требований (по окончании их обслуживания) устройство должно осуществлять обслуживание ожидающих очереди требований в порядке, Я обратном очередности их поступления.805311 20 формула изобретения Это происходит следующим образом.При снятии обслуживаемого требования,например, с выхода 35 снимаются 1 единицы" с выходов 18 узлов 1, 22, 3 ис выхода 42 элемента 5. Снятие запрещающего сигнала с входов 16 узловпоследней строки разрешает прохождение через них требований. В результате требование, находящееся на выходе 18 узла 26, вцзывает появлениесигнала на вцходе 34 устройства, Этот осигнал управляет обслуживанием требования, поступающего по входу 39,т.е, последнего требования из очереди (самого "свежего" ). При снятии обслуживаемого требования, например, с входа Зб снимаются "единицыф с выходов 18 узлов 19, 23, 27 и с выхода 41 элемента 5; Снятие сигнала с входов 16 узлов второй строки разрешает прохождение требований через эти узлы, Поэтому требование, находящееся на выходе 18 узла 21, проходит через узел 25, затем через узел 29 (с его входа 16 "единица" снята еще раньше) н вызывает появление на выходе 33 сигнала, управляющего обслуживанием требования, поступившего по входу 38. При снчтии следующего обслужива- Зоемого требования, например, с входа39 снимается "единица": с выхода 40элемента 5, что разрешает прохождениетребования, поступившего по входу 37через узлы 20, 24 и 28. В результатена выходе 32 устройства появляетсясигнал, управляющий обслуживаниемтребования, поступившего первым (т.е.самого "старого"). Таким образом, при снятии .Обслу О живаемых требований устройство выбирает нз очереди оставшихся требований самые последние для Обслуживания, т.е. реализует инверсную очередь без прерывания, при этом требования мо гут поступать в любом порядке, та 3 аке в любом порядке могут выбывать обслу" живаемые требования.Таким образом, изобретение имеет меньше оборудования. ЯВ самом деле, узлы матрицы известного устройства содержат 27 элемен тов И, ИЛИ, НЕ, а узлы матрицы изобретения - пять аналогичных элементов. Для обслуживания 10-ти каналов известное устройство должно содержать 2490 элементов И, ИЛИ, НЕ и 20 элементов задержки. Предложенное же устройство для обслуживания 10-ти каналов с помощью изобретения требует 560 элементов И, ИЛИ, НЕ и 10 элементов за держки при числе И исходящих каналов равным 1 (наихудший для изобретения случай). При увеличении И указанное соотношение еще более улучшается, Так при М = 8 количество элементов И, 65 ИЛИ, НЕ в изобретении равно 210. Визвестном устройстве количество элементов от М не зависит. Для управления можно применить и любое устройство, реализующее все свои пороги ив котором веса входов одинаковы иравны единице,Быстродействие известного устройства определяется выражением 3 18(й). + 41, где с. - задержка одного логического элемента; й - число входящих каналов. Аналогичное выражение для изобретения имеет вид с(и"и) + фзз, где и - число исходящих каналов; е - задержка, вносимая элементами задержки. Посколькудолжно быть не меньше времени срабатывания порогового элемента, равного(И+1) (максимальное знаЪченне), то общее выражение для быстродействия изобретения имеет вид с(2 Й - И + 1). Например, при й = 10 и И = 6 быстродействие известного устройства равно 76 с 3, а изобретения - 153 Устройство для управления очередностью обслуживания, выполненное в виде матрицы с числом столбцов й, каждый узел которой содержит элементы И, ИЛИ, НЕ, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования и повышения быстродействия, оно содержит многопороговый элемент и группу элементов задержки, а число строк матрицы равно М-И, где И - число выходов устройства,обслуживаемых без очереди, причем входы устройства соединены со входами многопорогового элемента, каждый вход устройства через соответствующий элемент задержки соединен с запросным входом первого узла соответствующего столбца матрицы, выход узла столбца матрицы соединен с запросным входом последующего узла стОлбца матрицы, выходы узлов последней строки матрицы являются выходами устройства, выход 1-го порога многопорогового элемента соединен с запрещающими входами узлов (1-И)-ой строки матрицы и с разрешающими входами узлов (1-И)-ой строки матрицы, а в каждом узле матрицы запросный вход узла соединен с первым входом первого элемента И узла и через первый элемент НЕ узла - с первым входом второго элемента И узла, запрещающий вход узла через второй элемент НЕ узла, выходы. первого и второго элементов И узла через элемент ИЛИ узла соединены со вторым входом первого элемента И узла, второй вход второго элемента И узла и выход первого элемента И узла,являотся соответственноразрещакщим входом и выходом узла.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9 496558, кл. 6 Об Г 9/ОО, 1970. 2, Сборник "Известия ВУЗов". Се-.рия "Электромеханика", 1974, Р 3,с. 239, рис. б. 3. там же, 1975, 9 11, с. 122805311 Составитель Ф. Шагиахметоведактор С. Лыжова Техред М. Коштура Корректо Заказ 10903/ илиал ППП "Патент", г, Ужгород, ул, Проектная Тираж 756 ВНИИПИ Государст по делам изобр 13035, Москва, ЖенноготенийРаущ Подписноеомитета ССоткрытийая наб., д