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

Союз СоветскихСоциапистическмхРеспублик ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(51)М. Кл. С 06 Г 15/20 с присоелинениею заявки РЙ Государственный комитет(23) Приоритет по делам иаабретеиий к открытий(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ МАССОВОГО ОБСЛУЖИВАНИЯ Изобретение относится к вычислительной технике, в частности к устройствам, моделирующим процессы массо. вого обслуживания, и может быть использовано при исследовании вычислительной системы разделения времени.Известно устройство для моделирования систем массового обслуживания, содержащее генератор случайных сигналов, блок регистрации очереди и блок имитации очереди Г 11.Недостатком известного устройства является низкая точность моделирования процессов массового обслуживания,Наиболее близким по технической15 сущности к предлагаемому являетсяустройство для моделирования процессов массового обслуживания содержащее генератор входных импульсов,обслуживающий прибор, блок формирования времени обслуживания, коммутатор, блок управления, блок имитации очереди, блок коэффициентов есчета, блок регистрации очереди Г 21 Недостаток известного устройства низкая точность моделирования процессов массового обслуживания.Цель изобретения - повьппение точности моделирования процессов мас" сового обслуживания.Поставленная цель достигается тем, что в устройство для моделирования процессов массового обслуживания, содержащее коммутатор, первый выход которого подключен к первому входу блока управления, первый выход которого соединен с первым входом блока имитации очереди, второй и третий входы которого подключены ко второму и третьему вьжодам коммутатора, первый и второй входы которого соединены с первым и вторым выходами блока имитации очереди, третий вход коммутатора подключен ко второму выходу блока управления, второй вход которого является входом устройства, генератор входных импульсов, блок регистрации оче15 3 .84091реди, блок .формирования времени обслуживания, блок коэффициеитов счета, дополнительно введены арифметический блок, блок многоуровневойочереди и блок анализа очереди,5причем выход генератора входныхимпульсов соединен с четвертым входом коммутатора и со входом блока формирования времени обслуживания, выход которого подключен к первому 1 Овходу блока многоуровневой очереди,выход которого соединен с пятымвходом коммутатора, четвертый вьгход которого подключен ко второмувходу блока многоуровневой очереди,пятый и шестой выходы коммутатораподключены к первому и второму входам арифметического блока, первый,второй и третий выходы которого соединены с шестым, седьмым и восьмым входами коммутатора, девятый вход которого подключен к выходу блока коэффициентов счета, седьмой, восьмой идевятый выходы коммутатора соединеныс первым, вторым и третьим входамиблока регистрации очереди, первый ивторой выходы которого подключены кпервому и второму входам блока анализа очереди, выход которого подключенк десятому входу коммутатора,.одиннадцатый вход которого соединен с третьим выходом блока управления, четвертый выход которого подключен ктретьему входу блока анализа очереди, десятый и одиннадцатый выходыкоммутатора являются выходами устройства, кроме того, блок анализа очереди содержит первый элемент ИЛИ, выходкоторого соединен с первым входомэлемента И, выход которого подключен 4 Ок первому входу второго элемента ИЛИ,выход которого подключен к первымвходам элементов И первой группы,вторые входы всех, кроме первого,элементов И первой группы соединены 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 код случайной величины представляет собой время обслуживания 1-ой заявки -Рвремя в течение которого устройство должно выделить свои ресурсы для обслуживания 1-ой заявки в монопольном режиме, т.е, для обслуживания заявки от начала до концы без прерываний.Блок 2 многоуровневой очереди предназначен для образования из вновь поступающих и недообслуженных заявок многоуровневой очереди, Вновь поступающие заявки направляются в конец первого уровня очереди, имеющего высший приоритет обслуживания. Недообслуженные заявки поступают в последующие уровни очереди, начиная со второго в зависимости от количества8409 5квантов обслуживания, вьщеленной1-ой заявки (недообслуженная заявкаиз иуровня поступит в конец и-гоуровня очереди). Обслуживание заявоквнутри каждого уровня очереди осу 5ществляется по принципу "раньшепришел - раньше обслужен". Блок 2может быть выполнен, например, в виде совокупности .групп регистровсдвига, причем количество групп равна.числу уровней очереди. Запись зна"чения времени обслуживания 1-ой заяц ОфКвки ь, в регистре сдвига и-ой группы соответствует занесению 1-ой заявки в очередь и-го уровня, Запись 15заявок в уровне очереди осуществляется, начиная с младшего номера группы регистров сдвига. Разрядностьф регистров сдвига равна разрядностикода величины о",При поступлейии кода очередной заявки в группу регистров сдвига п-ого,уровня очереди, ранее записанные кодызаявок сдвигаются в сторону старшихномеров регистров сдвига. Выбор очередкой заявки для обслуживания изи-го уровня производится коммутатором4 путем определения самого старшегономера не пустого регистра сдвига ивыдачи кода, записанного в этом реги- ЗОстре сдвига в блок 3. Все остальныекоды заявок этого уровня сдвигаютсяпри этом в сторону старших номероврегистров сдвига,Блок 7 коэффициентов счета предназначен для хранения и выдачи в блок3 .кодов коэффициентов К 11. Коэффициенты К определяют количество квантовобслуживания в блоке 3 и зависят отномера 11 уровня очереди. Чем боль Оше номер уровня очереди, тем большеезначение имеет коэффициент К 11. Блок7 представляет собой группу регистров,в которых записаны коды коэффициентов Кп, причем выходы 22 этих регистров связаны с коммутатором 4, Коммутатор 4 по команде от блока 6 анализа очереди обеспечивает поступлениекода К, соответствующего уровню оче-реди, из которого обслуживается текущая заявка. Арифметический блок 3 определяетвремя, в течение которого текущаязаявка находится на обслуживании, Для 55этого в блоке производится вычислениепроизведения величины 0 - квантаобслуживания на коэффициент К - 8 ==В Кп. Сигнал об освобождении блока 18 6 3 появляется на выходах 16 и 17 через время, пропорциональное величине О =О Кп, Кроме того,1 в блоке 3 определяется обслужат текущую заявку до конца или нет. С этой целью определяется знак разности двух величин ДоБСл -О , Если л ( О, то заявка обслужена до конца, в противном случаеобслЬ - новое значениеми поступает в многоуровневую очередь как недообслуженная заявка. Блок 3 содержит решающее устройство, в котором вычисляются Й =О К , Ь и определяется знак Ь, и линию задержки, которая задерживает появление сигналов на выходах 16-18 блока 3 на время, пропорциональное времени обслуживания текущей заявки за данный цикл обслуживания - " К 11Блок 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 50 55 Увой заявки в первый уровень очере- .ди, а также определяет наименьшийномер не пустого уровня очереди ипо сигналу оу блока 8 управлениявыдает на коммутатор 4 сигналы дляобслуживания заявки этого уровня,Устройство работает следующимобразом,Если устройство моделирует процесс обслуживания заявок фикси-рованными.квантами с образованиемиз недообслуженных и вновь поступивших заявок многоуровневой очереди.Каждая заявка (импульс) проходит от генератора 38 на вход 10устройства, поступая на вход блока 1. На выходе блока 1 появляется кодвеличины времени обслуживания 1-ойзаявки - Ь , который запишетсяпо входу 19 в первый уровень блока 2. Кроме того, 1-ая заявка (импульс) регистрируется в первом уровне блока 5, поступая через коммутатор 4 на вход 24 этого блока. Вход 24 блока 5 является счетным входом реверсивного счетчика первого уровня. На его выходе 27 появляется сигнал, поступающий на вход блока 6. Кроме этого, если в устройстве имеются недообслуженные заявки, то сигналы с соответствующих выходов 28 блока 5 поступают на входы блока б.В блоке 6 определяется наименьший номер не пустого и-го уровня очереди, который поступает на входы 23 коммутатора 4. В соответствии с этим сигналом,коммутатор 4 переключает свои входы и выход таким образом, что обеспечивается обслуживание заявки изи-ого уровня: выход 21 блока 2 соединяется со входом 14 блока 3 так,что на него поступает заявка изи-ого уровня блока 2; вход и+1-огоуровня очереди во входах 20 блокаЪ2 соединяется с выходом 18 блока 3;выход 22 блока 7 соединяется со входом 15 блока 3 таким образом, чтона него поступает коэффициент К 1,соответствующий и-ому уровню очереди. Кроме этого, обеспечива"ется соединение выхода 16 блока 3с и"ым входом 26 блока 5, а такжевыхода 17 блока 3 с и+1-ым входом25 блока 5 и с:и-ым входом 26 блока 5,5 10 15 20 25 30 35 40 8Если блок 3 свободен и в первом уровне очереди блока 2 нет заявок, то вновь поступившая 1-ая заявка обслуживается блоком 3.Если ь с О, то 1-ая заявка обслужена до конца, и на выходе 16 блока 3 появляется сигнал, который поступает на выход 12 устройства, образуя поток обслуженных заявок, кроме этого, сигнал с выхода 16 поступает на вход 26 блока 5. Тем самым производится уменьшение числа заявок и-ого уровня очереди блока 5, т,е. уменьшается значение реверсивного счетчика и-ого уровня на единицу.Если же ЬО, т, е. заявка обслуЭжена не до конца, сигнал появляется на выходе 17. Поступая на входы 26 и 25 блока 5, этот сигнал производит уменьшение значения реверсивного счетчика и-ого уровня на единицу и увеличение значения реверсивного счетчика и+1 - уровня на единицу. Тем самым недообслуженная заявка регистрируется в более низком и+1-ом уровне блока 5. Кроме того, на вход 29 блока 8 поступает сигнал об освобождении блока 3, по которому в соответствующие моменты блок 8 формирует сигналы, появляющиеся на его выходах 30 и 32 и поступающие на входы коммутатора 4 и блока 6.Значение величины ь - новое значение времени обслуживания 1-ой, обслзаявки -1. - по сигналу с выхода130 блока 8 переписывается в и+1-ый уровень блока 2, поступая с выхода 18 блока 3 на соответствующий вход 20 блока 2. После того, как в блоке 5, с учетом вновь поступивших заявок, устанавливаются новые значения реверсивных счетчиков уровней очереди, с выходов 27 и 28 на входы блока 6 поступают сигналы от непустых уровней. В блоке 6 определяется наименьший номер не пустого уровня очереди, который по сигналу с выхода 32 блока 8 поступает на вход группы входов 23 коммутатора. Далее цикл обслуживания повторяется,Если устройство моделирует одноканальную систему массового обслуживания с дисциплиной очереди "первым пришел - первым обслужен", управляющий сигнал поступает на вход 1120 При моделировании очереди с ограниченным временем ожидания используется блок 9 имитации очереди, выполненный, например, в виде наборасчетчиков, каждый из которых имитирует одно место в очереди. При подаче соответствующих управляющих сигна-.лов на вход 11 устройства, блок 8управления устанавливает коммутаторв состояние, при котором входы 33,34 и выход 36 блока соединяются соответ- .ственно со входом 10 устройства, выходом1 б блока 3 и выходом 12 устройства, Ковходу 35 блока 9 задается предельная величина показаний счетчиков. Заявки рас- З 5пределяются между счетчиками с помощьюкоммутатора 4. Момент поступленияимпульса (заявки) регистрируетсяначалом отсчета времени,Обслуживание заявок производится аналогично режиму работы устройства при моделировании системы мас.сового обслуживания с дисциплиной"первым пришел - первым обслужен". 45 Удаление заявок из очереди осуществляется сигналом, появляющимся на выходе 1 б блока 3. Выбор заявок из очереди проводится по наибольшему времени пребывания заявки в очереди. После выбора заявки из очереди, соответствующий счетчик устанавливается в нулевое состояние. Обслуживание заявки в блоке 3 заключается в том, что сигнал на выходе 16 появляется после поступления заявки в блок 3 через время, пропорциональноеСОР" . При повышении заданного времени ожидания заявка поступает с 50 55 9 84091 устройства, а блок управления 8 формирует сигналы, поступающие с его выхода 31 на коммутатор 4. Коммутатор переключает свои входы и выходы таким образом, что с выходов 22 блока 7 на вход 15 блока 3 подается коэффициент К;,д.Значение Кдщтаково, что всегда выполняется условиепосл-К,с 16 (О,10 т.е. заявка, поступившая на обслуживание в блок 3, обслуживается сразу до конца и очередь - одноуровневая. Сигнал об окончании обслуживания заявки появляется на выходе 16 блока .окисл 3 через время, пропорциональноеСВ остальном, принцип поступления и обслуживания заявок блоками устрой,ства не отличается от вьппеописанного. 8 10выхода 37 блока 9 через коммутатор 4 на выход 13 устройства, а соответствующий регистр в блоке 2 и счетчик в блоке 9 переводятся.в нулевое состояние.Импульсы, появляющиеся на выходе 13 устройства, образуют поток необслуженных заявок.Наличие новых элементов и связеймежду ними позволяет повысить точность моделирования процессов массового обслуживания.Формула изобретения1. Устройство для моделирования процессов массового обслуживания, содержащее коммутатор, первый выход которого подключен к первому входу блока управления, первый выход которого соединен с первым входом блока имитации очереди, второй и третий входы которого подключены ко второму и третьему выходам коммутатора, первый и второй входы которого соединены с первым и вторым выходами блока имитации очереди, третий вход коммутатора подключен ко второму выходу блока управления, второй вход которого является входом устройства, генератор входных импульсов, блок регистрации очереди, блок формирования времени обслуживания, блок коэффициентов счета, о т л и ч а ю щ е е с я тем, что, с целью повьппения точности моделирования, в устройство дополнительно введены арифметический блок, блок многоуровневой очереди и блок анализа очереди, причем выход генератора входных импульсов соединен с четвертым входом коммутатора и со входом блока формирования времени обслуживания, выход которого подключен к первому входу блока многоуровневой очереди, выход которого соединен с пятым входом коммутатора, четвертый выход которого подключен ко второму .входу блока многоуровневой очереди, пятьщ и шестой .выходы коммутатора подключены к первому и второму входам арифметического блока первый, второй и третий выходы которого соединены с шестым, седьмым и, восьмым входами коммутатора, девятый вход которого подключен к выходу блока коэффициентов счета, седьмой восьмой и девятый выходы коммутатора)84091 1 О5га соединены с первым, вторыми третьимвходами блока регистрацив 1.очереди,первый и второй выходы которого подключены к первому и второму входамблока анализа очереди, выход которого подключен к десятому входу коммутатора, одиннадцатый вход которого соединен с третьим выходом блокауправления, четвертый выход которо- .го подключен к третьему входу блокаанализа очереди, десятый и одиннадцатый выходыкоммутатора являютсявыходами устройства,2. Устройство по п. 1, о т л и"ч а ю щ е е с я тем, что блок анализа очереди содержит первый элемент ИЛИ, выход которого соединенс первым входом элемента И, выходкоторого подключен к первому входувторого элемента ИЛИ, выход которого подключен к первым входам элементов И первой группы, вторые входы всех, кроме первого, элементов Ипервой группы соединены с выходами 8 12элементов И второй группы, первые входы которых. соединены со вторым входом элемента И, со вторым входом первого элемента И первой группы и с первым входом блока анализа очереди, вторые входы элементов И второй группы подключены к входам первого элемента ИЛИ и ко второму входу блока анализа очереди, третий вход которого соединен со вто- рым входом второго элемента ИЛИ, выход каждого элемента И второй группы подключен к соответствующим входам последующих элементов И второй группы, выходы элементов И первой группы соединены с выходом блока анализа очереди.Источники информации;принятые во внимание при экспертизе1. Авторское свидетельство СССР У 311280, кл. С 06 С 7/48, 1970.2, Авторское свидетельство СССР У 544971, кл. 6 06 Г 15/20, 1974 (прототип)./5 илиал ППППатент , г. Ужгород, ул. Проектная 68 73 ВНИИПИ Госуд по делам и 113035, Моск