Устройство для моделирования про-чессов массового обслуживания

 

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

Социапистическмх

Республик

О П И С А Н И Е (840918

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6l) Дополнительное к авт. свил-ву (22)Заявлено 12.09,79 (21) 2823967/18-24 (51)М. Кл.

G 06 F 15/20 с присоединением заявки J%

3Ъоударстеенкый комитет (23) Приоритет по делам иэабретеиий к открытий

Опубликовано 23.06. 81. Бюллетень Щ 23

Дата опубликования описания 30.06.81 (53) УДК68! .333 (088.8) (72) Автор изобретения

В.И.Янковский (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ

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

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

Известно устройство для моделирования систем массового обслуживания, содержащее генератор случайньж сигналов, блок регистрации очереди и блок имитации очереди Г11.

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

Наиболее близким по технической

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

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

Цель изобретения — повьппение точности моделирования процессов мас" сового обслуживания.

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

3 .84091 реди, блок .формирования времени обслуживания, блок коэффициеитов счета, дополнительно введены арифметический блок, блок многоуровневой очереди и блок анализа очереди, 5 причем выход генератора входных импульсов соединен с четвертым вхо1 дом коммутатора и со входом блока формирования времени обслуживания, выход которого подключен к первому 10 входу блока многоуровневой очереди, выход которого соединен с пятым входом коммутатора, четвертый вы ход которого подключен ко второму входу блока многоуровневой очереди, пятый и шестой выходы коммутатора подключены к первому и второму входам арифметического блока, первый, второй и третий выходы которого соединены с шестым, седьмым и восьмым входами коммутатора, девятый вход которого подключен к выходу блока коэффициентов счета, седьмой, восьмой и девятый выходы коммутатора соединены с первым, вторым и третьим входами блока регистрации очереди, первый и второй выходы которого подключены к первому и второму входам блока анализа очереди, выход которого подключен к десятому входу коммутатора,.одиннадцатый вход которого соединен с третьим выходом блока управления, четвертый выход которого подключен к третьему входу блока анализа очереди, десятый и одиннадцатый выходы коммутатора являются выходами устройства, кроме того, блок анализа очереди содержит первый элемент ИЛИ, выход которого соединен с первым входом элемента И, выход которого подключен 40 к первому входу второго элемента ИЛИ, выход которого подключен к первым входам элементов И первой группы, вторые входы всех, кроме первого, элементов И первой группы соединены 45 с выходами элементов И второй группы, первые входы которых соединены со вторым входом элемента И, со,вторым входом первого элемента И первой группы и с первым входом блока анализа очереди, вторые входы элементов И второй группы подключены к входам первого элемента ИЛИ ко второму входу блока анализа очереди, третий вход которого соединен со вторым входом второго элемента ИЛИ, выход каждого элемента И второй группы подключен к соответствующим входам последующих элементов И второй группы, выходы

8 4 элементов И первой группы соединены с выходом блока анализа очереди.

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

Устройство для моделирования процессов массового обслуживания содержит блок 1 формирования времени обслуживания заявок, блок 2 многоуровневой очереди, арифметический блок 3., коммутатор 4, блок 5 регистрации многоуровневой очереди, блок

6 анализа очереди, блок 7 коэффициентов счета, блок 8 управления, блок

9 имитации очереди, входы 10, 11, выходы 12, 13, входы 14 и 15 арифметического блока, выходы 16-18 арифметического блока, вход 19 блока многоуровневой очереди, входы 20 блока многоуровневой очереди, выходы

21 блока многоуровневой очереди, выходы 22 блока коэффициентов счета, входы 23 коммутатора, входы 24-26 блока регистрации многоуровневой очереди, выходы 27 и 28 блока регистрации многоуровневой очереди, вход 29 блока управления, вы оды 30-32 блока чпрявления, входы 33-35 блока имитации очереди, выходы 36 и 37 блока имитации очереди, генератор 38 входных импульсов с регулируемым законом распределения интервалов между моментами поступления соседних импульсов.

Блок 1 формирования времени обслуживания заявок представляет собой датчик случайных чисел, который по сигналам, поступающим на его вход от генератора импульсов 38, вырабатывает, коды случайных величин с регулируемым законом распределения. Появляющийся на выходе блока 1 код случайной величины представляет собой время обслуживания i oé заявки -Р время в течение которого устройство должно выделить свои ресурсы для обслуживания i-ой заявки в монопольном режиме, т.е. для обслуживания заявки от начала до концы без прерываний.

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

8409

5 квантов обслуживания, вьщеленной

i-ой заявки (недообслуженная заявка из и-1 уровня поступит в конец n-ro уровня очереди). Обслуживание заявок внутри каждого уровня очереди осу5 ществляется по принципу "раньше пришел — раньше обслужен". Блок 2 может быть выполнен, например, в виде совокупности .групп регистров сдвига, причем количество групп рав- 1р на.числу уровней очереди. Запись зна" чения времени обслуживания i-ой заяц,(Дал.

BKH l, в регистре сдвига и-ой группы соответствует занесению i-ой заявки в очередь и-ro уровня. Запись 15 заявок в уровне очереди осуществляется, начиная с младшего номера группы регистров сдвига. Разрядность регистров сдвига равна разрядности, î w

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

4 путем определения самого старшего номера не пустого регистра сдвига и выдачи кода, записанного в этом реги- ЗО стре сдвига в блок 3. Все остальные коды заявок этого уровня сдвигаются при этом в сторону старших номеров регистров сдвига.

Блок 7 коэффициентов счета предназначен для хранения и выдачи в блок

3 .кодов коэффициентов К>. Коэффициенты К„ определяют количество квантов обслуживания в блоке 3 и зависят от номера П уровня очереди. Чем боль- 4р ше номер уровня очереди, тем большее значение имеет коэффициент КП. Блок

7 представляет собой группу регистров, в которых записаны коды коэффициентов К, причем выходы 22 этих регист- 45 ров связаны с коммутатором 4. Коммутатор 4 по команде от блока 6 анализа очереди обеспечивает поступление кода К„, соответствующего уровню очереди, из которого обслуживается текущая заявка.

Арифметический блок 3 определяет время, в течение которого текущая заявка находится на обслуживании. Для 55 этого в блоке производится вычисление произведения величины Π— кванта обслуживания на коэффициент К вЂ” 8 =

=S-Кп. Сигнал об освобождении блока

18 6

t3 появляется на выходах 16 и 17 через время, пропорциональное величине

О =8 Кп. Кроме того,1 в блоке 3 определяется обслужат текущую заявку до конца или нет. С этой целью определяется знак разности двух величин Д п5сл— 1

О . Если л (О, то заявка обслужена до конца, в противном случае обсл

Ь„ — новое значение „- и поступает в многоуровневую очередь как недообслуженная заявка. Блок 3 содержит решающее устройство, в котором вычисляются Й =8-К, h,„ и определяется знак

Ь„, и линию задержки, которая задерживает появление сигналов на выходах

16-1 8 блока 3 на время, пропорциональное времени обслуживания текущей заявки за данный цикл обслуживания—

©; -К1.

Блок 5 регистрации многоуровневой очереди представляет собой набор реверсивных счетчиков; число которых равно количеству уровней очереди.

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

26 — вычитающими входами реверсивных счетчиков блока 5.

В состав блока 6 анализа очереди входят элементы И 39, имеющий прямой и инверсный входы, элементы ИЛИ 40, ИЗИ 41, И 42, группа элементов И 43, имеющих прямые и инверсные входы, группа элементов И 44. Первый вход элемента ИЛИ 41 соединен с выходом

32 блока 8 управления. Входы элемента ИЛИ 40 соединены с группой выходов

28 блока 5, а также с прямыми вхо" дами элементов И 43 ° Выход элемента ИЛИ 40 соединен с инверсным входом элемента И 39, прямой вход которого соединен с первым входом элемента И 42, инверсными входами элементов И 43 и выходом 27 блока 5. Выход элемента И 39 соединен со вторым входом элемента ИЛИ 41, выход которого соединен совторым входом элемента И 42 и первыми входами элементов И 44. Вторые входы элементов И 44 соединены с выходами элементов И 43. Кроме того, выход каждого элемента И 43 соединен с инверснъ ми входами последующих элементов И 43. Блок 6 анализа очереди обеспечивает выдачу сигнала на коммутатор 4 о поступлении пер-.

840918

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

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

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

Каждая заявка (импульс) проходит от генератора 38 на вход 10 устройства, поступая на вход блока 1. На выходе блока 1 появляется код величины времени обслуживания i îé заявки — t„, который запишется по входу 19 в первый уровень блока 2.

Кроме того, i-ая заявка (импульс) регистрируется в первом уровне блока 5, поступая через коммутатор 4 на вход 24 этого блока. Вход 24 блока 5 является счетным входом реверсивного счетчика первого уровня. На

его выходе 27 появляется сигнал, поступающий на вход блока 6. Кроме этого, если в устройстве имеются недообслуженные заявки, то сигналы с соответствующих выходов 28 блока 5 поступают на входы блока б.

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

23 коммутатора 4.

В соответствии с этим сигналом, коммутатор 4 переключает свои входы и выход таким образом, что обеспечивается обслуживание заявки из и-ого уровня: выход 21 блока 2 соединяется со входом 14 блока 3 так, что на него поступает заявка из и-oro уровня блока 2; вход n+l-ого уровня очереди во входах 20 блока

2 соединяется с выходом 18 блока 3; выход 22 блока 7 соединяется со входом 15 блока 3 таким образом, что на него поступает коэффициент К, соответствующий и-ому уровню очереди. Кроме этого, обеспечива" ется соединение выхода 16 блока 3 с n"ûì входом 26 блока 5,. а также выхода 17 блока 3 с и+1-ым входом

25 блока 5 и с:и-ым входом 26 блока 5.

8

Если блок 3 свободен и в первом уровне очереди блока 2 нет заявок, то вновь поступившая 1-ая заявка обслуживается блоком 3.

Если ь < 0, то i-ая заявка обслужена до конца, и на выходе 16 блока 3 появляется сигнал, который поступает на выход 12 устройства, образуя поток обслуженных заявок, кроме этого, сигнал с выхода 16 поступает на вход 26 блока 5. Тем самым производится уменьшение числа заявок и-ого уровня очереди блока

5, т.е. уменьшается значение реверсивного счетчика п-oro уровня на единицу.

Если же Ь 7 О, т. е. заявка обслуЭ жена не до конца, сигнал появляется на выходе 17. Поступая на входы

26 и 25 блока 5, этот сигнал производит уменьшение значения реверсивного счетчика и-ого уровня на единицу и увеличение значения реверсивного счетчика n+1 — уровня на единицу. Тем самым недообслуженная заявка регистрируется в более низком и+1-ом уровне блока 5. Кроме того, на вход 29 блока 8 поступает сигнал об освобождении блока 3, по которому в соответствующие моменты блок 8 формирует сигналы, появляющиеся на его выходах 30 и 32 и поступающие на входы коммутатора 4 и блока 6.

Значение величины й„ вЂ” новое значение времени обслуживания i-ой, окисл заявки -1.- — по сигналу с выхода

30 блока 8 переписывается в и+1-ый уровень блока 2, поступая с выхода

18 блока 3 на соответствующий вход

20 блока 2.

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

27 и 28 на входы блока 6 поступают сигналы от непустьгх уровней. В блоке б определяется наименьший номер не пустого уровня очереди, который по сигналу с выхода 32 блока 8 поступает на вход группы входов 23 коммутатора. Далее цикл обслуживания повторяется.

Если устройство моделирует одноканальную систему массового обслуживания с дисциплиной очереди "первым пришел — первым обслужен", управляющий сигнал поступает на вход 11

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

1 времени ожидания заявка поступает с

9 84091 устройства, а блок управления 8 формирует сигналы, поступающие с его выхода 31 на коммутатор 4. Коммутатор переключает свои входы и выходы таким образом, что с выходов 22 блока 7 на вход 15 блока 3 подается коэффициент К;, .Значение К шта ково, что всегда выполняется условие рос

-К„ „„8 (0„

10 т.е. заявка, поступившая на обслуживание в блок 3, обслуживается cgaэу до конца и очередь — одноуровневая. Сигнал об окончании обслуживания заявки появляется на выходе 16 блока окисл

3 через время, пропорциональноеТ „.

В остальном, принцип поступления и обслуживания заявок блоками устрой,ства не отличается от вышеописанного, 20

При моделировании очереди с ограниченным временем ожидания используется блок 9 имитации очереди, выг элненный, например, в виде набора счетчиков, каждый из которых имитирует одно место в очереди. При подаче соответствующих управляющих сигна-. лов на вход 11 устройства, блок 8 .управления устанавливает коммутатор в состояние, при котором входы 33, 34 и выход 36 блока соединяются соответ- . ственно со входом 10 устройства, выходом

i б блока 3 и выходом 12 устройства. Ко входу 35 блока 9 задается предельная величина показаний счетчиков. Заявки рас- З5 пределяются между счетчиками с помощью коммутатора 4. Момент поступления импульса (заявки) регистрируется началом отсчета времени.

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

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

8 10 выхода 37 блока 9 через коммутатор 4 на выход 13 устройства, а соответствующий регистр в блоке 2 и счетчик в блоке 9 переводятся.в нулевое состояние.

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

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

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

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

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

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

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

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

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

Ф 311280, кл. G 06 С 7/48, 1970.

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

Р 544971, кл. G Об F 15/20, 1974 (прототип).

840918

Составитель А.Колчин

Техред М,Коштура Корректор С.Шекмар

Редактор Н.Пушненкова

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

Заказ 4768 73 Тираж 745 .Подписное

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

113035, Москва, И-35, Раушская наб., д. 4/5