Устройство для моделирования процесса обслуживания заявок с различными приоритетами Советский патент 1991 года по МПК G06F15/20 

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

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

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

Устройство содержит вход 1 заявок с низким приоритетом, вход 2 заявок с высоким приоритетом, третий триггер 3, первый элемент И 4, первый элемент ИЛИ 5, первый триггер 6, второй элемент И 7, первый блок 8 определения временных интервалов, выполненный в виде счетчика импульсов, первый генератор 9 импульсов

со случайным интервалом следования, генератор 10 счетных импульсов, второй триггер 11, третий элемент И 12, второй блок 13 определения временных интервалов, второй генератор 14 импульсов со случайным интервалом следования, третий 15, четвертый 16, первый 17 пятый 18, шестой 19 и второй 20 счетчики импульсов, выходы обслуженных заявок низкого 21 и высокого 22 приоритетов, пятый триггер 23, четвертый триггер 24, четвертый 25, пятый 26, шестой 27, седьмой 28, девятый 29, восьмой 30 и десятый 31 элементы И, второй элемент ИЛИ 32, первый 33 и второй 34 элементы задержки, шестой 35 и седьмой 36 триггеры, первый дифференцирующий элемент 37, одиннадцатый 38, двенадцатый 39 и тринадцатый 40 элементы И, тре- |тий элемент ИЛИ 41, дешифратор 42, мультиплексор 43, восьмой 44 и девя 1ел

тый 45 триггеры, второй дифференцирующий элемент 46, вход 47 задания граничного времени устройства, являющийся адресным входом мультиплексора 43, и седьмой счетчик 48 импульсов. Потоки заявок на обслуживание на входах 1 и 2 представляют случайные импульсные последовательности, интервалы между которыми распределены по определенным (разным или одним и тем же) законам. Генераторы 9 и 14 имитируют один обслуживающий прибор, закон распределения случайных импульсов на их выходах один и тот же. Временной интервал от момента запуска генераторов до появления импульсов на их выходах случаен и распределен по принятому закону обслуживания заявок. Блоки 8 и 13 представляют двоичные счетчики импульсов, емкость которых можно изменять в зависимости от величины интервала времени -, требуемого на ориентацию прибора к обслуживанию данного потока заявок, и могут быть выполнены в виде элементов задержки с изменяемой величиной задержки

Вербальная модель работы -устройства сводится к следующему„

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

Если заявка с более высоким приоритетом поступила в период обслуживания заявки с низким приоритетом, то на основе реального времени tOB(,, проведенного заявкой в системе, находится оценка tocr , которое является наиболее вероятным временем, которое осталось провести заявке в системе до завершения ее обслуживания,,

Если оценка tQOT

Locr то обслуживание заявки с низким приоритетом прекращается и начинается ориентация прибора к обслуживанию высокоприоритетной заявки, после ее завершения идет обслуживание высокоприоритетной

0

5

0

5

0

5

0

5

заявки, что приводит к потере низкойприоритетной заявки. Если оценка t.r

ост -ост то заяв- ка высокого приоритета становится в

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

ост

обслуживанию„ Граничное время t задается исходя из требований достижения максимальной пропускной способности СМО и может изменяться в процессе моделирования о

Если высокоприоритетная заявка поступила во время ориентации обслуживающего прибора к обслуживанию низкоприоритетной заявки, то в любом случае эта ориентация прерывается и начинается ориентация обслуживающего прибора к обслуживанию высокоприоритетной заявки, при этом низкоприоритетная заявка теряетсяt

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

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

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

После включения устройства триггеры 3, 6, 11, 23, 24, 35, 36, 44 и 45 устанавливаются в исходное состояние (нулевое). На единичном выходе триггера 3, подключенном к второму входу элемента И 4, имеется разрешающее напряжение; на нулевом выходе триггера 6, подключенном к первому входу элемента И 7, разрешающее напряжение отсутствует; на нулевом выходе триггера 11, подключенном к первому входу элемента И 12, отсутствует разрешающее напряжение; на входы элементов И 7 и 12 поступают счетные импульсы от генератора 10 На управляющих входах элементов И 7, 12 и 38, на входах блоков 8 и 13, соединенных с выходами элементов И 7 и 12, на запускающих входах генераторов 9 и 14 напряжение отсутствует„ На управляющих входах элементов И 29, 26 и 25 имеется разрешающее напряжение от триггеров 23, 35 и 24,а на управляющих входах элементов И 27, 30 и 31 разрешающее напряжение отсутствуете В дальнейшем во всех режимах работы функционирование устройства поддерживается автоматически.

Обслуживание заявок низкого приоритета происходит следующим образом

Заявки, пришедшие во время обслуж вания с входа 1, поступают на элемент И 4, перебрасывают триггер 6, запускают блок 8, и через элемент И 7 на него поступают счетные импуль сы. Достигнув числа, соответствующег времени ориентации, с выхода блока 8 импульс поступает на вход счетчика 16 и на запускающий вход генератора 9„ Если обслуживание предыдущей заявки еще не закончилось, то пришедшая заявка к обслуживанию не принимается и теряется. Если обслуживание предыдущей заявки закончилось, то 25 пришедшая заявка обслуживается после ориентирования прибора к обслуживанию. Импульс с выхода блока 8 перебрасывает после ориентирования триггер 6 в исходное состояние Таким

35 I

Импульс с входа 1 через элемент И 4 поступает на единичный вход триг- -JQ образом, устройство приходит в ис- гера 6 и переводит его в состояние, ходное состояние, готово к работе в при котором открывается элемент И 7, любом режиме.

и через него счетные импульсы от гене- Обслуживание заявок высокого при- ратора 10 начинают поступать на блок оритета происходит следующим обра- 8. Емкость счетчика блока 8 устанавли- зом, вается заранее в зависимости от величины интервала времени, требуемого на ориентацию прибора к обслуживанию заявок низкого приоритета, и после заполнения этого счетчика на выходе блока 8 появляется импульс, который имитирует окончание ориентации прибора к обслуживанию заявки низкого приоритета, запускает через открытый элемент И 25 генератор 9 и, одновременно поступая на счетчик 16, через элемент ИЛИ 5 переводит триггер б в положение, при котором элемент И 7 закрыт, и счетные импульсы от генератора 10 не поступают на блок 8.

40

Импульс с входа 2 поступает через открытый элемент И 40 и элемент ИЛИ 41 на нулевой вход триггера 3 и устанавливает его в состояние, при котором закрывается элемент И 4 (сни мается с его второго входа разрешающее напряжение), и заявки низкого приоритета не проходят с входа 1 на триггер 6, Одновременно этот же им-

45 пульс с входа 2 поступает на единичный вход триггера 11 и переводит его в состояние, при котором открывается элемент И 12, и через него счетные им пульсы от генератора 10 проходят на

50 вход блока 13. Емкость счетчика блока 13 устанавливается заранее в зависимости от величины интервала времени, требуемого на ориентирование прибора для обслуживания заявок высокоИмпульс с выхода элемента И 25 поступает на единичный вход триггера 24, переводя его в состояние, при котором элемент И 25 закрывается, не пропуская очередных заявок Запуск генератора 9 имитирует начало обслуживания заявки низкого приоритета. Через случайный интервал времени на выходе генератора 9 появляет

6

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

Заявки, пришедшие во время обслуживания с входа 1, поступают на элемент И 4, перебрасывают триггер 6, запускают блок 8, и через элемент И 7 на него поступают счетные импульсы. Достигнув числа, соответствующего времени ориентации, с выхода блока 8 импульс поступает на вход счетчика 16 и на запускающий вход генератора 9„ Если обслуживание предыдущей заявки еще не закончилось, то пришедшая заявка к обслуживанию не принимается и теряется. Если обслуживание предыдущей заявки закончилось, то 5 пришедшая заявка обслуживается после ориентирования прибора к обслуживанию. Импульс с выхода блока 8 перебрасывает после ориентирования триггер 6 в исходное состояние Таким

5

0

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

I

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

Импульс с входа 2 поступает через открытый элемент И 40 и элемент ИЛИ 41 на нулевой вход триггера 3 и устанавливает его в состояние, при котором закрывается элемент И 4 (снимается с его второго входа разрешающее напряжение), и заявки низкого приоритета не проходят с входа 1 на триггер 6, Одновременно этот же им-

пульс с входа 2 поступает на единич ный вход триггера 11 и переводит его в состояние, при котором открывается элемент И 12, и через него счетные импульсы от генератора 10 проходят на

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

вок высокого приоритета, который поступает на прямой вход элемента И 28 и одновременно на счетчик 19 и нулевой вход триггера 11, устанавливая его в состояние, при котором элемент И 12 закрыт, и счетные импульсы от генератора 10 не поступают на блок 13„ Импульс с выхода блока 13 проходит элемент И 28, так как на его управляющем инверсном входе имеется разрешающее напряжение с выхода регистра 36, и поступает через элементы ИЛИ 32, И 30, И 26 на вход запуска генератора 14, имитируя начало обслуживания заявки высокого приоритета, и на единичный вход триггера 23, переводя его в состояние, при котором элемент И 26 закрывается, а элемент И 27 открывается по управляющим входам.

Через случайный интервал времени, соответствующий времени обслужива- |ния, на выходе генератора 14 появляется импульс, имитирующий окончание обслуживания заявки, проходящей на выход 22 устройства, на вход счетчика 20, на единичный вход триггера 3, устанавливая его в исходное состояние, на нулевой вход триггера 35, подтверждая его состояние, на нулево вход триггера 23, переводя его в состояние, при котором элемент И 26 открывается, а элемент И 27 закрывается. Устройство вновь готово к обслуживанию заявок различных приоритетов. Заявки, пришедшие с входа 2 во время ориентации прибора к обслужванию, теряются.

Обслуживание заявки высокого приоритета при наличии в очереди заявки этого же приоритета происходит следующим образом

Постановка заявки в очередь о Пуст во время нахождения предыдущей заявки на обслуживание поступает с выхода блока 13 следующая заявка. При этом импульс с выхода генератора 10 проходит через открытый элемент И 27 а не через элемент И 28, так как у элемента И 28 отсутствует разпешаю- щее напряжение от триггера 36, перебрасывает триггер 35 в единичное состояние, закрывая тем самым вход элемента И 30 и открывая вход элемента И 29. Одновременно этот же импульс с выхода элемента И 27 проходит через элемент 33 задержки, открытый элемент И 29 на вход установки в

0

4758

1 триггера 36, имитируя тем самым постановку пришедшей заявки в очередь.

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

Через случайный интервал времени, соответствующий времени обслуживания заявки, на выходе генератора 14 появляется импульс, имитирующий окончание обслуживания предыдущей заявки. Этот импульс поступает на нулевой вход триггера 23, перебрас сывая его в состояние, при котором открывается элемент И 26 и закрывается элемент И 27, на нулевой вход триггера 35, переводя его в состояние, при котором элемент И 30 откры0 вается, а элемент И 29 закрывается, через элемент И 31 на нулевой вход триггера 36, переводя его в единичное состояние, Импульс, получаемый от дифференцирования отрицательного пе5 репада на выходе триггера 36 дифференцирующим элементом 37, поступает на первый вход элемента ИЛИ 32, на открытые элементы И 30, И 26, единичный вход триггера 23, закрывая эле0 мент И 26 и открывая элемент И 27, на вход запуска генератора 14, имитируя тем самым извлечение заявки из очереди и передачу ее на обслуживание,, Через время задержки элемен, та 34 после переброса триггера 36 открывается элемент И 28„ Если во время обслуживания заявки придет очередная заявка, то она будет поставлена в очередь Если обслуживание

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

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

По окончании ориентации и начала обслуживания заявки низкого приоритета триггер 24 устанавливается импульсом с выхода элемента И 25 в состояние, при котором элемент И 38 открывается по первому входу, на второй вход которого поступают счетные импульсы от генератора 10, Эти импульсы проходят на счетный вход счетчика 48, который подсчитывает время обслуживания t0&CA заявки низкого приоритета, Преобразованный дешифратором 42 из двоичного в унитарный

0

код времени t оесд поступает на входы мультиплексора 43, на адресны вход которого с входа 47 устройства подается код времени , тем самы t ст-и выход дешифратора 42 соединяется с выходом установки в 1 триггера 44. Перевод триггера 44 в единичное состояние происходит

ПРИ ДОСТИЖеНИИ ЧИСЛа ИМПУЛЬСОВ В

счетчике 48, соответствующего времени tocr , и до завершения обслуживания заявки низкого приоритета триггер 44 остается в единичном состоянии. В соответствии с положением триггера 44 поступающая с входа 2 заявка высокого приоритета либо

проходит через элемент И 40 на втоЛ .

ост-ост

рой вход элемента ИЛИ 41 (t триггер 44 в нулевом состоянии), ибо проходит через элемент И 39 на единичный вход триггера 45 (t/,T

X.

i tOOT, триггер 44 в единичном состоянии) ,

л

При toc.T tOCT заявка высокого приоритета проходит с входа 2 через элементы И 40, ИЛИ 41 на вход установки в О триггера 3, переводя его в состояние, снимающее разрешающее напряжение с элемента И 4, закрывая тем самым вход 1 для поступления заявок низкого приоритета. Одновременно эта заявка проходит на установочные входы блока 8, срывая ориентирование прибора к обслуживанию заявки низкого приоритета, если оно проводилось, и генератора 9, срывая обслуживание заявок низкого приоритета если оно проводилось, а также через элемент ИЛИ 5 на нулевой вход тригге ра 6. Если в этот момент проходит ориентация прибора к обслуживанию заявки низкого приоритета или обслуживание заявки этого же приоритета, то они прерываются и теряются, а заявка высокого приоритета поступает на единичный вход триггера 11, переводя в состояние, когда с его выхода подается разрешающее напряжение на элемент И 12, и от генератора 10 по- ступают счетные импульсы на вход блока 13, переводя устройство в режим ориентации к обслуживанию заявки высокого приоритета, по окончании которого - в режим обслуживания, а далее устройство переходит в исходное состояние и готово к работе (аналогично обслуживанию заявки высокого приоритета) .

JQ

j

20

тс

30 3540 45 о ,-,- При tocT t- tocr заявка высокого приоритета с входа 2 через элемент И 39 устанавливает в единичное состояние триггер 45, осуществляя постановку в очередь заявки высокого приоритета до завершения обслуживания заявки низкого приоритета. По окончании ее обслуживания импульс с выхода генератора 9 сбрасывает в нулевое состояние счетчик 48 и триггеры 44 и 45; дифференцирующий элемент 46 по заднему фронту импульса переключения триггера 45 с 1 в О формирует импульс, имитирующий извлечение из очереди заявки высокого приоритета, который через элемент ИЛИ 41 поступает на единичный вход триггера 11. Далее устройство работает по схеме, описанной в режиме обслуживания заявки высокого приоритета,

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

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

Формула изобретения Устройство для моделирования процесса обслуживания заявок с различными приоритетами по авт. св. № 1236496, отличающееся тем, что, с целью расширения области применения устройства за счет имитации процесса адаптивного изменения дисциплины обслуживания заявок, в него введены одиннадцатый, двенадцатый и тринадцатый элементы И, третий элемент ИЛИ, восьмой и девятый триггеры, седьмой счетчик импульсов, второй дифференцирующий элемент, дешифратор и мультиплексор, причем нулевой выход четвертого триггера соединен с первым входом одиннадцатого элемента И,- второй вход которого подключен к выходу генератора счетных импульсов, выход

1116

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

75

12

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

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