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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)ю G 06 F 15/20. ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЪСТВУ (21) 4909522/24 (22) 11.02.91 (46) 28.02.93, Бюл, ¹ 8 (72) О.Ю.Гаценко, В,А.Смагин, А.В.Запорожец, А, Н.Е кимцов и Г.Ф.Филимонихин (56) Авторское свидетельство СССР

N. 1305701, кп, G 06 F 15/20, 1985.

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

N 1716535, кл. G 06 F 15/20, 1990, (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано при

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

Цель изобретения — повышение точности моделирования очереди.

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

Устройство содержит генератор 1 случайного потока импульсов. счетчик 2 поступивших заявок, счетчик 3 потерянных заявок, первый 4, третий 5 и второй 6 элементы ЗАПРЕТ, первый 7, четвертый 8, пятый 9, второй 10, третий 11 элементы И, триггер 12, первый 13, второй 14 элементы

ИЛИ, генератор 15 счетных импульсов, генератор 16 импульсов случайной длительности, формирователь 17 импульса, реверсивный счетчик 18 обслуживания, группу элементов 19 случайной временной

„„Д0„„1798802 А1 статистическом моделировании систем мас- . сового обслуживания с учетом случайной емкости накопителя очереди. Цель изобретения — повышение точности моделирования, Для достижения поставленной цели в устройство введен блок формирования случайной емкости накопителя очереди, включающий генератор потока импульсов. случайной длительности, генератор счетных импульсов, счетный триггер, формирователь импульса, восемь элементов И, семь элементов Запрет. одиннадцать элементов

ИЛИ, три реверсивных счетчика, элемент

° ИЛИ-НЕ и элемент НЕ. 2 ил. задержки и блок 20 формирования случайной емкости накопителя очереди.

Блок 20 содержит генератор 21 потока импульсов случайной длительности, первый

22, восьмой 23, третий 24, четвертый 25, пятый 26, второй 27, шестой 28, седьмой 29 элементы И, второй 30, седьмой 31, третий

32, четвертый 33, первый 34, пятый 35, шестой 36 элементы ЗАПРЕТ, первый 37, седьмой 38, второй 39, третий 40, восьмой 41, десятый 43, одиннадцатый 43, четвертый 44, девятый 45, пятый 46, шестой 47 элементы

ИЛИ, элемент ИЛИ-НЕ 48, второй 49, третий

50, первый 51 реверсивные счетчики, формирователь 52 импульсов, счетный триггер

53, элемент НЕ 54, генератор 55 счетных импульсов. Первый вход "2" блока является входом постановки заявки в очереди, второй вход "3" блока является входом снятия заявки из очереди, третий вход "5" блока является входом сброса первого 49 и второго 50 реверсивных счетчиков блока, первый

1798802 выход "1" блока является выходом признака отсутствия свободных мест под хранение заявок, второй "4" выход блока является выходом признака наличия ненулевой очереди

Устройство моделирует процесс функционирования СМО, в которой происходит формирование случайной емкости накопителя очереди.

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

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

В исходном состоянии все каналы свободны от обслуживания, триггер 12 находится в состоянии, когда на управля,ощем входе элемента 6 ЗАПРЕТ сигнал отсутствует и он открыт, все счетчики в нулевом состоянии, генератор 15 счетных импульсов вырабатывает последовательность импульсов с периодом Т,, тенератор 55 счетных импульсов вырабатывает последовательность импульсов с периодом Т,ь, счетный триггер 53 находится в нулевом состоянии, в соответствии с которым элементы И 24-29 закрыты, а элементы ЗАПРЕТ 30, 32-36 открыты, Элементы И 11, 22 закрыты. С приходом первого импульса случайной длительности от генератора 20 происходит формирование емкости накопителя очереди. В начале процесса формирования случайной емкости накопителя передний фронт импульса от генератора 21 запускает формирователь, импульса 52, активный единичный уровень сигнала которого сбрасывает реверсивный счетчик 51, и через открытый элемент 34 ЗАПРЕТ, элемент

ИЛИ 43 сбрасывает реверсивный счетчик

50. Задний фронт сформированного формирователем 52 импульса устанавливает счетный триггер 53 в единичное состояние, На время сброса реверсивного счетчика 50 прохождение импульсов с генератора счетных импульсов 55 через элемент И 22 блокируется нулевым сигналом с элемента НЕ

54. После сброса реверсивного счетчика 50 нулевым сигналом от формирователя 52 импульса через элемент HE 54 открывается элемент И 22 и счетные импульсы от генератора 55, в соответствии с длительностью импульса от генератора 20 проходят через

20 открытый элемент 31 ЗАПРЕТ, элемент ИЛИ

37 и поступают на суммирующий вход реверсивного счетчика 51, имитируя образование емкости накопителя очереди. После занесения на реверсивный счетчик 51 отличного от нуля кода нулевой сигнал с выхода элемента ИЛИ-НЕ 48 открывает элемент

4 ЗАПРЕТ. Импульс от генератора 1 поступает на элемент 4 ЗАПРЕТ и элемент 6 ЗАПРЕТ, элемент ИЛИ 13, а также на вход триггера 12, переключает его, закрывая тем самым элемент 6 ЗАПРЕТ и открывает элемент И 10, Импульс с выхода элемента ИЛИ

13 запускает генератор 16 импульса случайной длительности, который, в свою очередь, открывает элемент И 11. Импульсы от генератора 15 счетных импульсов проходят через открытый элемент И 11 на суммирующий вход реверсивного счетчика

18, имитируя запись ранга заявки. По окончании работы генератора 16 элемент И 11 закрывается. а на выходе формирователя 17 появляется импульс, запускающий элемент

19 случайной временной задержки. До окончания обслуживания следующие заявки генератора 1 поступают на вход 2 блока формирования случайной емкости накопителя очереди. С входа 2 блока заявка поступает на вычитающий вход реверсивного

30 счетчика 51, имитируя уменьшение свободных мест под хранение заявок на единицу, и через открытый элемент И 26 через элемент ИЛИ 40 поступает на суммирующий вход реверсивного счетчика 50, имитируя

35 образование очереди, При этом через открытый элемент И 28 через элемент ИЛИ 47 .единичный сигнал поступает на выход "4" блока.

Через случайное время, равное продол40 жительности обслуживания заявка s каждом из каналов, на выходах элементов 19 случайной временной задержки появляются импульсы, которые через элемент ИЛИ 14 поступают на вычитающий вход реверсив45 ного счетчика 18. При обслуживании заявки

M каналами, что соответствует рангу заявки, импульс с выхода обнуления реверсивного счетчика 18 через элемент И 9 поступает на вход "3" блока формирования. С входа "3"

50 блока сигнал поступает через элемент ИЛИ

37 на суммирующий вход реверсивного счетчика 51, имитируя появление одного свободного места в накопителе под хранение заявки, и через элемент И 25, через

55 элемент ИЛИ 41 на вычитающий вход реверсивного счетчика 50, уменьшая очередь на единицу. Кроме того, импульс обнуления реверсивного счетчика 18 через элемент И 8, элемент ИЛИ 13 повторно запускает генератор 16, имитируя приход заявки из очереди, 1798802

10

25

40

55 и устанавливает перед этим в исходное состояние элементы 19 случайной временной задержки. Их установка в исходное состояние необходима для того, чтобы сигналы, появившиеся на выходе остальных элементов 19 случайной временной задержки, не оказывали влияния на работу реверсивного счетчика 18 и не искажали работу устройства. Такая работа устройства имеет место в том случае, если в очереди находится хотя бы одна заявка, при этом на выходе "4" блока есть сигнал, Если же в очереди нет заявок, то сигнал с выхода реверсивного счетчика 18 через элемент 5 запрета переключает триггер 12, открывая элемент 6 запрета и закрывая эле.мент И 10. При заполнении всей емкости накопителя очереди на выходе элемента

ИЛИ-НЕ 48 появляется сигнал, который закрывает элемент 4 запрета и открывает элемент И 7. При этом новые заявки поступают на вход счетчика 3 потерянных заявок.

Среднее время длительности потенциального сигнала с выхода генератора 16 случайной длительности импульса Т< должно быть намного больше периода длительности импульса, формируемого генератором

15 счетных импульсов с целью более точного подсчета рангов реверсивным 18 счетчиком, Более того, необходимо выполнение условия Tc «Tr «и Тс. где и — число исполнителей в устройстве.

Рассмотрим теперь, как работает устройство в очередном цикле формирования случайной емкости накопителя очереди.

Пусть в соответствии с описанным, содержимое резерсивного счетчика 50 представляет собой ненулевую очередь, счетный триггер на::.одится в единичном состоянии, С приходом очередного импульса случайной длительности от генератора 20 формирователем 52 вырабатывается импульс, сбрасывающий реверсивные счетчики 51 и

49. Задний фронт этого импульса изменяет состояние счетного триггера 53. Нулевой сигнал с выхода триггера 53 открывает элемент 30 запрета и закрывает элемент И 24.

Счетные импульсы от генератора 55 в соответствии с длительностью импульса от генератора 20 потока импульсов случайной длительности поступают на вычитающий вход реверсивного счетчика 50 и на суммирующий вход реверсивного счетчика 49.

Имеют место два случая.

1. Пусть число N поступающих от генератора 55 счетных импульсов превышает или равно числу R, находящемуся в реверсивном счетчике 50 (вновь образуемая емкость накопителя больше или равна числу заявок в очереди). Тогда в момент, когда на вычитающий вход реверсивного счетчика 50 поступит R сче1ных импульсов, его содержимое будет равно нулю. Нулевой сигнал через открытый элемент 36 запрета, элемент ИЛИ

46 закрывает элемент И 23 и открывает элемент 31 запрета. Вследствие этого на суммирующий вход реверсивного счетчика 51 поступает N— - Rимпульсов,,имитируя появление нового случайного числа мест для хранения заявок в накопителе очереди. На реверсивном счетчике 49 образуется очередь из R заявок, 2. Пусть число N поступающих от генератора 55 счетных импульсов меньше числа

R, находящегося в реверсивном счетчике 50 (вновь образуемая емкость накопителя очереди меньше числа заявок в очереди). Тогда в процессе формирования новой емкости накопителя очереди содержимое реверсивного счетчика 50 не сбрасывается и становится равным (R-N) — числу потерянных заявок. Нуль в реверсивном счетчике 51 имитируя отсутствие свободных мест для хранения заявок в накопителе очереди. На реверсивном счетчике 49 образуется новая очередь из Й заявок.

По окончании формирования емкости накопителя очереди заявки, направляемые в очередь, будут поступать через открытый элемент 32 запрета, элемент ИЛИ 38 на суммирующий вход реверсивного счетчика 49, а снятие заявки из очереди будет происходить поступлением сигнала через элемент

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

Среднее время длительности потенциального сигнала с выхода генератора 20 потока импульсов случайной длительности Тгв должно быть намного больше периода длительности импульса, формируемого генератором счетных импульсов 55. Длительность импульса, вырабатываемого формирователем 52, должна быть достаточной для устойчивого сброса реверсивного счетчика 50 либо 49 и определяется используемой элементной базой.

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

Устройство для моделирования систем массового обслуживания, содержащее генератор случайного потока импульсов, счетчик поступивших заявок. счетчик потерянных заявок, пять элементов И, группу элементов случайной временной задержки, первый и второй элементы ИЛИ, три элемента 3АПРЕТ, триггер, реверсивный счетчик обслуживания, генератор импульсов, случайной длительности, генератор счетных импульсов и формирователь импульса, причем выход генератора .случайного потока

1798802

10

30

55 импульсов соединен со счетным входом счетчика поступивших заявок, с информационным входом первого элемента ЗАПРЕТ и первым входом первого элемента И, выход которого подключен к счетному входу счетчика потерянных заявок, выход первого элемента ЗАПРЕТ соединен с первым входом второго элемента И и с информационным входом второго элемента ЗАПРЕТ, выход которого подключен к первому входу первого элемента ИЛИ и нулевому входу триггера, инверсный выход которого соединен с вторым входом второго элемента И и управляющим входом второго элемента ЗАПРЕТ, выход первого элемента ИЛИ подключен к входу запуска генератора импульсов случайной длительности, выход которого соединен с первым входом третьего элемента

И и входом формирователя импульса, выход которого подключен к входам запуска элементов случайной временной задержки группы, выход генератора счетных импульсов соединен с вторым входом третьего элемента И, выход которого подключен к суммирующему входу реверсивного счетчика обслуживания. выход обнуления которого соединен с установочными входами элементов случайной временной задержки группы, с первыми входами четвертого и пятого элементов И и информационным входом третьего элемента ЗАПРЕТ, выход которого подключен к единичному входу триггера, выходы элементов случайной временной задержки группы соединены с соответствующими входами второго элемента

ИЛИ, выход которого подключен к вычитающему входу реверсивного счетчика обслуживания, выход четвертого элемента И соединен с вторым входом первого элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью повышения точности моделирования, в него введен блок формирования случайной емкости накопителя очереди, содержащий генератор потока импульсов случайной длительности, генератор счетных импульсов, счетный триггер, формирователь импульса, восемь элементов И, семь элементов ЗАПРЕТ, одиннадцать элементов ИЛИ, первый, второй, третий реверсивные счетчики, элемент ИЛИ-НЕ и элемент

НЕ, причем в блоке формирования случайной емкости накопителя очереди выход генератора потока импульсов случайной длительности соединен с первым входом первого элемента И и входом формирователя импульса, выход которого соединен с первым входом второго элемента И, входом элемента НЕ, информационным входом первого элемента ЗАПРЕТ. с входом сброса первого реверсивного счетчика и входом счетного триггера, прямой выход которого соединен с первыми входами третьего, четвертого, пятого, седьмого элементов И, с вторым входом второго элемента И, и с управляющими входами первого, второго, третьего, четвертого, пятого и шестого элементов ЗАПРЕТ, выход элемента НЕ соединен с вторым входом первого элемента И, выход которого соединен с первым входом восьмого элемента И и с информационным входом седьмого элемента ЗАПРЕТ, выход которого соединен с первым входом первого элемента ИЛИ, выход которого соединен с суммирующим входом первого реверсивного счетчика, выходы разрядов которого соединены соответственно с входами элемента ИЛИ-НЕ, выход которого соединен с вторым входом первого элемента И устройства и с управляющим входом первого элемента ЗАПРЕТ устройства, в блоке формирования случайной емкости накопителя очереди выход восьмого элемента И соединен с информационным входом второго элемента ЗАПРЕТ и вторым входом третьего элемента И, выход которого соединен с первыми входами второго и третьего элементов ИЛИ, выход второго элемента ИЛИ подключен к вычитающему входу второго реверсивного счетчика, выходы разрядов которого соединены соответственно с входами четвертого элемента ИЛИ, выход которого соединен с информационным входом пятого элемента ЗАПРЕТ и вторым входом седьмого элемента И, выход которого соединен с первым входом пятого элемента

ИЛИ, выход которого соединен с вторым входом восьмого элемента И и с управляющим входом седьмого элемента ЗАПРЕТ, выход пятого элемента ЗАПРЕТ соединен с первым входом шестого элемента ИЛИ, выход второго элемента ЗАПРЕТ соединен с первыми входами седьмого и восьмого элементов ИЛИ, выход которого соединен с вычитающим входом третьего реверсивного счетчика, выходы разрядов которого соединены соответственно с входами девятого элемента ИЛИ, выход которого соединен с информационным входом шестого элемента

ЗАПРЕТ и вторым входом шестого элемента И; выход которого соединен с вторым входом шестого элемента ИЛИ, выход которого соединен с вторыми входами четвертого и пятого элементов И устройства и с управляющим входом третьего элемента

ЗАПРЕТ устройства, в блоке формирования случайной емкости накопителя очереди, выход шестого элемента ЗАПРЕТ соединен с вторым входом пятого элемента ИЛИ, выход второго элемента И и выход первого элемента ЗАПРЕТ соединены с первыми входа1798802 ми десятого элемента ИЛИ и одиннадцатого элемента ИЛИ соответственно, выходы десятого и одиннадцатого элементов ИЛИ соединены с входами сброса второго и третьего реверсивных счетчиков соответственно, выход второго элемента И устройства подключен к вычитающему входу первого реверсивного счетчика блока формирования случайной емкости накопителя очереди, второму входу пятого элемента И и информационному входу третьего элемента ЗАПРЕТ блока формирования случайной емкости накопителя очереди, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с суммирующим входом второго реверсивного счетчика, выход пятого элемента И блока формирования случайной емкости накопителя очереди соединен с вторым входом третьего элемента ИЛИ. выход которого соединен с суммирующим входом третьего реверсивного счетчика, выход пятого элемента И устройства соединен с вторым

5 входом первого элемента ИЛИ, с вторым входом четвертого элемента И, и информационным входом четвертого элемента ЗАПРЕТ блока формирования случайной емкости накопителя очереди, выход которо10 ro соединен с вторым входом второго элемента ИЛИ, выход четвертого элемента И соединен с вторым входом восьмого элемента ИЛИ, выход генератора счетных импульсов соединен с третьим входом первого

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

1798802

Составитель И.Дубинина

Техред М.Моргентал Корректор ЛЯивринц

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 774 Тираж Подписное

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

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