Модель обслуживания заявок

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

Область техники, к которой относится полезная модель

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

Уровень техники

Известно устройство для моделирования систем массового обслуживания, содержащее группу блоков формирования потоков заявок, группу блоков формирования потоков заявок и дисциплины обслуживания, группу блоков обслуживания заявок, группу блоков образования и обслуживания очереди, переключатель задания режимов, задатчик структур и параметров модели, блок-коммутатор структур моделей и блок индикации (см. Авторское свидетельство СССР 840915, кл. G06F 15/20, 1979 г.).

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

Известно устройство для моделирования процесса обслуживания заявок с различными приоритетами, содержащее два генератора импульсов со случайным интервалом следования, два триггера, три элемента И, элемент запрета и ограничительный диод (см. Авторское свидетельство СССР 962969, кл. G06F 15/20, G06F 9/46, 1981 г.).

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

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

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

Раскрытие полезной модели

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

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

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

Краткое описание чертежей

На фиг.1 представлена структурная схема модели обслуживания заявок, системы состоящая из входа заявок высокого приоритета 1, входа заявок низкого приоритета 2, блоков обслуживания заявок 3, первого и второго элементов ИЛИ 4, 5 соответственно.

На фиг.2 представлена структурная схема блока обслуживания заявок, содержащая блок обслуживания заявок 3, второй триггер 6, первый триггер 7, разделительный диод 8, элемент И 9, первый генератор импульсов 10, второй генератор импульсов 11, первый ключ 12 и второй ключ 13.

Осуществление полезной модели

Модель обслуживания заявок работает следующим образом.

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

Модель содержит вход 1 заявок высокого приоритета, вход 2 заявок низкого приоритета, блоки 3 обслуживания заявок (по заданному числу моделируемых каналов обслуживания заявок) и первой и второй элементы ИЛИ 4 и 5, число входов каждого из которых равно числу блоков 3 обслуживания заявок.

Каждый блок 3 обслуживания заявок содержит второй триггер 6, первый триггер 7, разделительный диод 8, элемент И 9, первый 10 и второй 11 генераторы импульсов со случайным интервалом следования, первый 12 и второй 13.

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

Потоки заявок на обслуживание на входах 1 и 2 устройства представляют случайные импульсные последовательности, интервалы между которыми распределены по определенным (разным или одним и тем же) законам.

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

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

Диод 8 служит для развязки между выходом элемента И 9 и входом триггера 6.

Блок 3 обслуживания заявок может работать в трех режимах: обслуживание заявок низкого приоритета; обслуживание заявок высокого приоритета; обслуживание заявок высшего приоритета, поступивших в период обслуживания заявок низкого приоритета.

Рассматриваемый k-й блок обслуживания заявок работает следующим образом.

В исходном состоянии во всех трех режимах триггеры 7 и 6 устанавливаются в положение, при котором на первых выходах, подключенных к ключам 12 и 13, имеется высокий потенциал. Ключи 12 и 13 k-го блока будут открыты, если в предшествующих (с первого по (k-1)-го) блоках триггеры 7 и 6 находятся в состояниях, при которых на их вторых выходах имеются высокие потенциалы.

Обслуживание заявок низкого приоритета рассмотрим на примере блока 3 первого канала (k=1).

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

Обслуживание заявок высокого приоритета также рассмотрим на примере блока 3 первого канала (k=1).

Импульс с первого входа блока через открытый ключ 12 запускает генератор 10 и переводит триггер 7 в состояние, при котором снимается высокий потенциал с ключей 12 и 13. Ключи 12 и 13 закрыты. Заявки, поступившие до окончания работы генератора 10 с первого и второго входов, к обслуживанию не принимаются. По окончании обслуживания и появления импульса на выходе генератора 10 блок приводится в исходное состояние, открываются ключи 12 и 13.

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

Заявка низкого приоритета с второго входа блока через открытый ключ 12 запускает генератор 11 и опрокидывает триггер 6. При этом закрывается ключ 13, а на первый вход элемента И 9 поступает разрешающий потенциал. Заявка высшего приоритета, поступившая с первого входа до окончания работы генератора 11, через открытый ключ 12 запускает генератор 10, устанавливает генератор 11 в исходное состояние (этим имитируется прекращение обслуживания заявки с низким приоритетом) и опрокидывает триггер 7. При этом закрываются ключ 12. В таком состоянии схема удерживается до окончания обслуживания заявки с высоким приоритетом.

После появления импульса на выходе генератора 10, имитирующего окончание обслуживания заявки высшего приоритета, опрокидывается триггер 7, открывая ключи 12, 13. Одновременно этот же импульс проходит через элемент И 9, на втором входе которого имеется разрешающий потенциал от триггера 6 на запуск генератора 11. Тем самым имитируется повторное обслуживание заявки с низким приоритетом, прерванное поступлением высокоприоритетной заявки. До окончания обслуживания триггер 6 удерживает ключ 13 в закрытом, а элемент И 9 - в открытом состоянии.

После появления импульса на выходе генератора 11 блок возвращается в исходное состояние.

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

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

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

Обслуживание устройством заявок низкого приоритета.

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

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

Как только закончится обслуживание заявки низкого приоритета хотя бы в одном блоке, импульс с второго выхода этого блока через элемент ИЛИ 5 пройдет на второй выход устройства. Одновременно на четвертом выходе блока 3, в котором обслуживание заявки низкого приоритета закончилось, появляется сигнал логического «нуля». После принятия к обслуживанию пришедшей заявки низкого приоритета четвертый выход рассматриваемого блока откроется. Появится сигнал логической «единицы». Таким образом, любая вновь поступившая заявка низкого приоритета с входа 2 параллельно поступит на все блоки 3 устройства, но будет принята на обслуживание первым из свободных блоков в порядке нумерации.

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

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

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

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

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

Заявка высокого приоритета с входа 1 устройства поступит на первый вход первого блока 3 и примется этим блоком к обслуживанию. Одновременно откроются третий и четвертый выходы первого блока 3 (присутствуют сигналы логической «единицы»).

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

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

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

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

Модель обслуживания заявок, содержащая два элемента ИЛИ и N блоков обслуживания заявок, каждый из которых состоит из двух генераторов импульсов со случайным интервалом следования, двух триггеров, разделительного диода, двух ключей и элемента И, при этом первые входы первого и второго ключей являются соответственно входами заявок высокого и низкого приоритетов модели, выход первого ключа подключен к первому входу первого триггера и входу запуска первого генератора импульсов со случайным интервалом следования, выход второго ключа соединен с первым входом второго триггера и через разделительный диод к входу запуска второго генератора импульсов со случайным интервалом следования, выход которого соединен с вторым входом второго триггера, выход первого генератора импульсов со случайным интервалом следования подключен к второму входу первого триггера и входу элемента И, первый выход первого триггера подключен к управляющим входам первого и второго ключей, второй выход первого триггера соединен с управляющими входами ключей 12 последующих блоков 3, первый выход второго триггера подключен к второму входу второго ключа, а второй выход второго триггера подключен к второму входу элемента И и к управляющим входам ключей 13 последующих блоков 3, информационные входы первого ключа второго блока обслуживания заявок и последующих подключены к вторым выходам триггеров 7 предшествующих блоков 3, информационные входы второго ключа второго блока обслуживания заявок и последующих подключены к вторым выходам триггеров 6 предшествующих блоков 3, выходы первых генераторов импульсов со случайным интервалом следования всех блоков обслуживания заявок соединены соответственно с входами первого элемента ИЛИ, выход которого является выходом обслуженных заявок высокого приоритета устройства, а выходы вторых генераторов импульсов со случайным интервалом следования всех блоков обслуживания заявок соединены соответственно с входами второго элемента ИЛИ, выход которого является выходом обслуженных заявок низкого приоритета устройства, отличающаяся тем, что, с целью повышения скорости выбора свободного блока обслуживания заявок, в состав блоков обслуживания заявок дополнительно введены первый и второй ключи, с помощью которых для соответствующих уровней приоритета заявок опрашиваются состояния данного k-го и предшествующих (с первого по (k-1)-й) блоков обслуживания заявок, и в случае занятости всех предшествующих блоков и свободного состояния данного (k-го) блока, заявка поступает в данный канал на обслуживание; блоки обслуживания заявок подключены параллельно, вследствие чего заявки на обслуживание подаются одновременно на все блоки обслуживания заявок.