Устройство для моделирования про-чЕССОВ МАССОВОгО ОбСлужиВАНия Советский патент 1981 года по МПК G06N1/00 

Изобретение относится к вычислительной технике, в частности к устро ствам, моделирующим процессы массового обслуживания, и может быть использовано при исследовании вычислительной системы разделения времени. Известно устройство для моделирования систем массового обслуживания, содержащее генератор случайных сигналов, блок регистрации очереди и блок имитации очереди ul. Недостатком известного устройства является низкая точность моделирования процессов массового обслуживания Наиболее близким по технической сущности к предлагаемому является устройство для моделирования процессов массового обслуживания содержащее генератор входных импульсов, обслуживаюидий прибор, блок формирования времени обслуживания, коммутатор, блок управления, блок ими- тации очереди, блок коэффициентов счета, блок регистрации очереди L23. Недостаток известного устройства низкая точность моделирования процессов массового обслуживания. Цель изобретения - повышение точности моделирования процессов мас сового обслуживания. Поставленная цель достигается тем, что в устройство для моделирования процессов массового обслуживания, .содержащее коммутатор, первый выход которого подключен к первому входу блока управления, первьй выход которого соединен с первым входом блока имитации очереди, второй и третий входы которого подключены ко второму и третьему выходам коммутатора, первый и второй входы которого соединены с первым и вторым выходами блока имитации очереди, третий вход коммутатора подключен ко второму выходу блока управления, второй вход которого является входом устройства, генератор входных импульсов, блок регистрации очереди, блок .формирования времени обслуживания, блок коэффициектов счета, дополнительно введены арифметический блок, блок многоуровневой очереди и блок анализа очереди, причем выход генератора входных импульсов соединен с четвертым входом коммутатора и со входом блока формирования времени обслуживания, выход которого подключен к первом входу блока многоуровневой очереди, выход которого соединен с пятым входом коммутатора, четвертый выход которого подключен ко второму входу блока многоуровневой очереди, пятый и шестой выходы коммутатора подключены к первому и второму входам арифметического блока, первый, второй и третий выходы которого соединены с mecTbiM, седьмым и восьмым входами коммутатора, девятый вход которого подключен к выходу блока коэффициентов счета, седьмой, восьмой и девятый выходы коммутатора соединены с первым, вторым и третьим входами блока регистрации очереди, первый и . второй выходы которого подключены к первому и второму входам блока анализа очереди, выход которого подключен к десятому входу коммутатора,одиннадцатый вход которого соединен с третьим выходом блока управления, четвертый выход которого подключен к третьему входу- блока анализа очереди, десятый и одиннадцатый выходы коммутатора являются выходами устройства, кроме того, блок анализа очереди содержит первый элемент ИЛИ, выход которого соединен с первым входом элемента И,-выход которого подключен к первому входу второго элемента ИЛИ, выход которого подключен к первым входам элементов И первой группы, вторые входы всех,кроме первого, элементов И первой группы соединены с выходами элементов И второй группы, первые входы которых соединены со вторым входом элемента И, со .вторым входом первого элемента И первой группы и с первым входом блока анализа очереди, вторые входы элементов И второй группы подключены к входам первого элемента ИЛИ ко второму входу блока анализа очереди, третий вход которого соединен со вторым входом второго элемента ИЛИ, выход каждого элемента И второй группы подключен к соответствующим входам последующих элементов И второй группы , выходы

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

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

Устройство для моделирования процессов-массового обслуживания содержит бло1 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 блока управленияJ выводы 30-32 блока vпpявлeния, входы 33-35 блока имитации очереди, выходы 36 и 37 блока имитации очереди, генератор 38 входных импульсов с регулируемым законом распределения интервалов между моментами поступления соседних импульсов.

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

Блок 2 многоуровневой очереди предназначен для образования из вновь поступающих и недообслуженных заявок многоуровневой очереди. Вновь поступающие заявки направляются в конец первого уровня очереди, имеющего высщий-приоритет обслуживания. Недообслуженные заявки поступают в последующие уровни очереди, начиная со второго в зависимости от количества 58 квантов обслуживания, выделенной i-ой заявки (недообслуженная заявка из п-1 уровня поступит в конец п-го уровня очереди). Обслуживание заявок внутр и каждого уровня очереди осуществляется по принципу раньше пришел - раньше обслужен. Блок 2 может быть выполнен, например, в виде совокупности .групп регистров сдвига, причем количество групп равНО; числу уровней очереди. Запись зна чения времени обслуживания i-ой заяBKHt в регистре сдвига п-ой группы соответствует занесению 1-рй заяв ки в очередь п-го уровня. Запись заявок в уровне очереди осуществляется, начиная с младшего номера груп пы регистров сдвига. Разрядность регистров сдвига равна разрядности кода величины С При поступлении кода очередной за явки в группу регистров сдвига п-ого уровня очереди, ранее записанные код заявок сдвигаются в сторону старших номеров регистров сдвига. Выбор очередной заявки для обслуживания из п-го уровня производится коммутаторо 4 путем определения самого старшего номера не пустого регистра сдвига и выдачи кода, записанного в этом реги стре сдвига в блок 3. Все остальные коды заявок этого уровня сдвигаются при этом в сторону старших номеров регистров сдвига. Блок 7 коэффициентов счета предназначен для хранения и вьщачи в бло 3 .кодов коэффициентов К,,. Коэффициен ты Kj определяют количество квантов обслуживания в блоке 3 и зависят от номера п уровня очереди. Чем больше номер уровня очереди, тем большее значение имеет коэффициент К. Блок 7 представляет собой группу регистро в которых записаны коды коэффициентов К, причем выходы 22 этих регист ров связаны с коммутатором 4. Коммутатор 4 по команде от блока 6 анализа очереди обеспечивает поступление кода Kj, соответствующего уровню оче реди, из которого обслуживается текущая заявка. Арифметический блок 3 определяет время, в течение которого текущая заявка находится на обслуживании. Дл этого в блоке производится вычислени произведения величины 0 - кванта обслуживания на коэффициент 9-Kf. Сигнал об освобождении блока 3 появляется на выходах 16 и 17 через время, пропорциональное величине 0 0Kj. Кроме того,, в блоке 3 определяется . обслужат текущую заявку до конца или нет, С этой целью определяется знак разности двух величин Л st - в , Если д. 4 О, то заявка обслужена до конца, в противном случае - новое значение t и поступает в многоуровневую очередь как недообслуженная аявка. Блок 3 содержит решающее устройство, в котором вычисляются 0 9-К, и определяется знак и линию задержки, которая задерживает появление сигналов на выходах 16-18 блока 3 на время, пропорциональное времени обслуживания текущей заявки за данньй цикл обслуживания «i-Kn. Блок 5 регистрации многоуровневой очереди представляет собой набор реверсивных счетчиков , число которых равно количеству уровней -очереди. Заявки каждого уоовня регистрируются своим счётчиком. По входу 24 регистрируются вновь поступающие заявки . Входы 25 являются счетными входами ревепсивньк счетчиков, а входы 26 - вычитающими входами реверсивных счетчиков блока 5. В состав блока 6 анализа очереди входят элементы И 39, имеющий прямой и инверсный входы, элементы Ш1И 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 о поступлении пер-. вой заявки в первый уровень очереди, а также определяет наименьший номер не пустого уровня очереди и по сигналу ох блока 8 управления выдает на коммутатор 4 сигналы для обслуживания заявки этого уровня. Устройство работает следующим образом. Если устройство моделирует процесс обслуживания заявок фиксированными квантами с образованием из недообслуженных и вновь поступивших заявок многоуровневой очереди. . Каждая заявка (импульс) проходит от генератора 38 на вход 10 устройства, поступая на вход блока 1 . На выходе блока 1 появляется ко величины времени обслуживания i -ой заявки - t. , которью запишется по входу 19 в первый уровень блока Кроме того, i-ая заявка (импуль регистрируется в первом уровне бло ка 5, поступая через коммутатор 4 на вход 24 этого блока. Вход 24 бл ка 5 является счетным входом ревер сивного счетчика первого уровня.. Н его выходе 27 появляется сигнал, п ступающий на вход блока 6. Кроме этого, если в устройстве имеются н дообслуженные заявки, то сигналы с соответствующих выходов 28 блока 5 поступают на входы блока 6. В блоке 6 определяется наименьший номер не пустого п-го уровня очереди, который поступает на вход 23 коммутатора 4. в соответствии с этим сигналом. коммутатор 4 переключает свои входы и выход таким образом, что обес печивается обслуживание заявки из п-ого уровня: вь1ход 21 блока 2 сое диняется со входом 14 блока 3 так, что на него поступает заявка из п-ого уровня блока 2; вход п+1-ого уровня очереди во входах 20 блока 2 соединяется с выходом 18 блока 3 выход 22 блока 7 соединяется со вхо дом 15 блока 3 таким образом, что на него поступает коэффициент К,, соответствуюпщй п-ому уровню очереди. Кроме этого, обеспечивается соединение выхода 16 блока 3 с п-ым входом 26 блока 5,. а также выхода 17 блока 3 с п+1-ым входом 25 блока 5 и сп-ым входом 26 блока 5. 8 Если блок 3 свободен и в первом ровне очереди блока 2 нет заявок, то вновь поступившая i-ая заявка обслуживается блоком 3. Если A.jjO, то i-ая заявка обслуена до конца, и на выходе 16 блока 3 появляется сигнал, который поступает на выход 12 устройства, образуя поток обслуженных заявок, кроме этого, сигнал с выхода 16 поступает на вход 26 блока 5. Тем самым производится уменьшение числа . заявок п-ого уровня очереди блока 5, .т.е. уменьшается значение реверсивного счетчика п-ого уровня на единицу. Если жед-70, т.е. заявка обслужена не до конца, сигнал появляется на выходе 17. Поступая на входы 26и 25 блока 5, этот сигнал производит уменьшение значения реверсивного счетчика п-ого уровня на единицу и увеличение значения реверсивного счетчика п+1 - уровня на единицу. Тем самым недообслуженная заявка регистрируется в более низком п+1-ом уровне блока 5. Кроме того, на вход 29 блока 8 поступает сигнал об освобождении блока 3, по которому в соответствующие моменты блок 8 формирует сигналы, появляющиеся на его выходах 30 и 32 и поступающие на входы коммутатора 4 и блока 6. Значение величины Д - новое, значение времени обслуживания i-ой заявки -t - по сигналу с выхода 30. блока 8 переписывается в n+1-ый уровень блока 2, поступая с выхода 18 блока 3 на соответствующий вход 20 блока 2. После того, как в блоке 5, с учетом вновь поступивших заявок, устанавливаются новые значения реверсивных счетчиков уровней очереди, с выходов 27и 28 на входы блока 6 поступают сигналы от непустых уровней. В блоке 6 определяется наименьший номер не пустого уровня очереди, который по сигналу с выхода 32 блока 8 поступает на вход группы входов 23 коммутатора. Далее цикл обслуживания повторяется. Если устройство моделирует одноканальную систему массового обслуживания с дисциплиной очереди первым пришел - Цервым обслужен, управляющий сигнал поступает на вход 11 9 устройства, а блок управления 8 фор мирует сигналы, поступающие с его выхода 31 на коммутатор 4. Коммутатор переключает свои входы и выходы таким образом, что с выходов 22 блока 7 на вход 15 блока 3 подается коэффициент K ow-Значение К т«хта ково, что всегда выполняется услови а / п - J т.е. заявка, поступившая на обслу живание в блок 3, обслуживается сра зу до конца и очередь - одноуровневая . Сигнал об окончании обслуживан заявки появляется на выходе 16 блок 3 через время, пропорционапьноеС В остальном, принцип поступления и обслуживания заявок блоками устрой.ства не отличается от вьшеописанноПри моделировании очереди с огра ниченным временем ожидания используется блок 9 имитации очереди, выполненный, например, в виде набора счетчиков, каждый из которых имитирует одно место в очереди. При пода че соответствующих управляющих сигн лов на вход 11 устройства, блок 8 управления устанавливает коммутатор в состояние, при котором входы 33, 34 и выход иб блока соединяются соотве ственно со входом 10 устройства, выход i 6 блока 3 и выходом 1 2 устройства. Ко входу 35 блока 9 задается предельная в личина показаний счетчиков. Заявки ра пределяюТся между счетчиками с помощь коммутатора 4. Момент поступления импульса (заявки) регистрируется началом отсчета времени. Обслуживание заявок производится аналогично режиму работы устройства при моделировании системы мас.сового обслуживания: с дисциплиной первым пришел - первым обслужен. Удаление заявок из очереди осуществляется сигналом, появляющимся йа выходе 16 блока 3. Выбор заявок из очереди проводится по наибольшему времени пребывания заявки в очереди. После выбора заявки из очереди, соответствующий счетчик устанав ливается в нулевое состояние Обслу живание заявки в бдоке 3 заключается в том, что сигнал на вькоде 16 появляется после поступления заявки в блок 3 через время, пропорциональ Hoet-P . При повышении заданного времени ожидания заявка поступает с . выхода 37 блока 9 через коммутатор 4 на выход 13 устройства, а соответствующий регистр в блоке 2 и счетчик в блоке 9 переводятся.в нулевое состояние. Импульсы, появляющиеся на выходе 13-устройства, образуют поток необслуженных заявок. Наличие новых элементов и связей между ними позволяет повысить точ- . ность моделирования процессов массового обслуживания. Формула изобретения 1. Устройство для моделирования процессов массового обслуживания, содержащее коммутатор, первый выход которого подключен к первому входу блока управления, первый выход которого соединен с первым входом блока имитации очереди, второй и третий входы которого подключены ко второму и третьему выходам коммутатора, первый и второй входы которого соединены с первым и вторым выходами блока имитации очереди, третий вход коммутатора подключен ко второму выходу блока управления, второй вход которого является входом устройства, генератор входных импульсов, блок регистрации очереди, блок формирования времени обслуживания, блок коэффициентов счета, отлича.ющееся тем, что, с целью повышения точности моделирования, в устройство дополнительно введены арифметический блок, блок многоуровневой очереди и блок анализа очереди, причем выход генератора входных импульсов соединен с четвертым входом коммутатора и со входом блока формирования времени обслуживания, выход которого -подключен к первому входу блока многоуровневой очереди, выход которого соединен с пятым входом коммутатора, четвертый выход которого подключен ко второму .входу блока многоуровневой очереди, пяты и шестой .вьткоды коммутатора подключены к первому и второму входам арифметического блока| первый, второй и третий выходы которого соединень с шестым, седьмым и, восьмым входами коммутатора, девятый вход которого подключен к выходу блока коэффициентов счета, седьмой восьмой и девятый выходы коммутатора

11

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

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

8. 12 .

элементов И второй группы, первые входы которых соединены.со вторым входом элемента И, со вторым входом первого элемента И первой группы и с первым входом блока анализа очереди, вторые входы элементов И второй группы подключены к входам первого элемента ИЛИ и ко второму ВХОДУ блока анализа очереди, третий вход KOTOpo.ro соединен со вторым входом второго элемента ИЖ, выход каждого элемента И второй труппы подключен к соответствующим входам последую1цих элементов И второй группы, выходы элементов И первой группы соединены с выходом блока анлиза очереди.

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

1.Авторское свидетельство СССР № 311280, кл. G 06 G 7/48, 1970.

2.Авторское свидетельство СССР № 544971, кл. G 06 F 15/20, 1974 (прототип).

5 55 53

Фиг. /