Queuedt2.m

Общая схема моделирования СМО.

Рассмотрим возможности использования Q-схем для формального описания процесса функционирования некоторой системы S. Характерная ситуация в работе таких систем – появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т.е. стохастический характер процесса их функционирования. В общем случае моменты поступления заявок в систему из внешней среды образуют входящий поток, а моменты окончания обслуживания образуют выходящий поток обслуженных заявок.

Формализуя какую-либо реальную систему с помощью Q-схемы, необходимо построить структуру такой схемы. В качестве элементов структуры Q-схем будем рассматривать элементы трех типов: И – источники, Н – накопители, К – каналы обслуживания заявок.

Известно, что существует два основных принципа построения моделирующих алгоритмов: «принцип » и «принцип ». При построении моделирующего алгоритма Q-схемы по «принципу », т.е. алгоритма с детерминированным шагом, необходимо для построения адекватной модели определить минимальный интервал времени между соседними событиями (во входящих потоках и потоках обслуживания) и принять, что шаг моделирования равен этому «минимальному интервалу». В моделирующих алгоритмах, построенных по «принципу », т.е. в алгоритмах со случайным шагом, элементы Q-схемы просматриваются при моделировании только в моменты особых состояний (в моменты появления заявок из И или изменения состояний К).

В данной главе будут рассматриваться возможности реализации алгоритма по «принципу » с помощью программных средств системы MATLAB и при помощи средства визуального моделирования STATEFLOW. Выбор принципа построения моделирующего алгоритма обусловлен тем, что в STATEFLOW заложен механизм системного времени –по некоторым тактам, задаваемым в параметрах запуска системы. Остановимся более подробно на детерминированном моделирующем алгоритме.

Рассмотрим простую систему, структура которой представлена на рисунке 5.24.

Рис. 5.24 Структура системы

Эта система представляет собой однофазную систему массового обслуживания с двумя каналами (К1 и К2) и накопителем с конечной емкостью (Н). Заявки, поступающие в систему, имеют бесконечное время ожидания. N1 – поток потерянных заявок, N2 – поток обслуженных заявок.

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

Схема детерминированного моделирующего алгоритма Q-схемы представлена на рисунке 5.25.

Рис. 5.25 Блок-схема детерминированного моделирующего алгоритма

Блок 6 служит для отсчетов системного времени, т.е. для вычислений , где -постоянный шаг, -текущий момент времени, -следующий момент времени.

Работа вспомогательных блоков – ввода, исходных данных 1, установки начальных условий 2, обработки 7 и вывода результатов моделирования 8 – не представляет для нас особого интереса, т.к. данные блоки аналогичны во всех алгоритмах.

Остановимся более подробно на рассмотрении функционирования блоков 4, 5, работа которых отражает специфику детерминированного подхода.

Для удобства детализации алгоритма введем следующие обозначения:

t – текущий момент системного времени;

ti – время прихода очередной заявки;

R=2 – число каналов;

K(j) – каналы системы, j=1,2;

z(j) – состояние канала K(j), ;

tvk(j) – время окончания обслуживания очередной заявки каналом K(j);

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

D(ti) – процедура генерации заявок источником определяет момент поступления очередной

заявки в систему;

Рис. 5.26 Блок-схема алгоритма моделирующего окончание обслуживания заявки

l(j) – число заявок, обработанных K(j);

k – количество заявок в накопителе

M – емкость накопителя.

Окончание обслуживания заявки в некотором канале K(j) в момент времени t может вызвать процесс распространения изменений состояний элементов («особых состояний») системы в направлении, противоположном движению заявок в системе, поэтому при моделировании все элементы системы должны просматриваться начиная с обслуживающего канала последней фазы по направлению к накопителю 1-ой фазы. Данный принцип не обязательно использовать в случае однофазных СМО, но он важен при моделировании работы более сложных систем – систем обслуживания с двумя и более фазами.

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

Рисунок 5.18

После пуска, ввода исходных данных и установки начальных условий (блоки 1 и 2 на рис. 5.24) проверяется условие окончания моделирования системы
(блок 3). Затем переходят к имитации обслуживания заявок каналом K(j), j=1,2. Если закончилось обслуживание, то фиксируется выход из системы очередной обслуженной заявки и проводится освобождение канала.

Затем имитируется взаимодействие в процессе обслуживания заявок в накопителе и каналах. Проверяется необходимость и возможность обслуживания каналами K(j), j=1,2 заявок из накопителя Н. Если в Н имеются заявки и один из K(j) свободен, то имитируется обслуживание заявки, фиксируется занятость конкретного канала и освобождение одного места в Н (рис. 5.27).

Далее имитируется взаимодействие источника (И) и накопителя Н с учетом занятости каналов этой фазы. Если в текущий момент времени t поступила заявка из И, то она, при наличии свободного канала, может быть обслужена K(j), либо, при наличии мест в накопителе, поставлена в очередь, либо, при занятости каналов и отсутствии свободных мест в накопителе, утеряна. После этого определяется время поступления в Q-схему очередной заявки из источника и управление передается блоку 6, который определяет момент очередного шага.

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

Данный алгоритм легко реализуется при помощи языка программирования MATLAB.

% Однофазная система массового обслуживания по принципу dt

function queuedt2

tm=100; % время окончания функционирования системы

k=0; % количество заявок в очереди

M=2; % емкость очереди

otk=0; % количество потерянных заявок

tpn=0; % время поступления заявки в накопитель

vpn=[]; % массив времен поступления заявок в накопитель первой фазы

tpk=[0,0]; % время начала обработки заявки в каналах первой фазы

tvk=[0,0]; % время начала обработки заявки в каналах первой фазы

vvk=[,]; % массив времен поступления заявок в каналы первой фазы

ti=0; % время поступления заявки в систему;

vti=[0]; % массив времен поступления заявок;

dt=0.1; % постоянный шаг

t0=dt; % начальный момент времени

N=5; % параметр источника

m=[10,7]; % параметры каналов первой фазы

z=[0,0]; % параметры, характеризующие состояние каналов

num=0; % количество сгенерированных заявок

R=2; % количество каналов

l=[0,0]; % количество заявок, обработанных каналами

srO=0;

km=0; % количество заявок, сразу поступивших на обслуживание в канал

for t=t0:dt:tm

ql=0;

for j=1:R

if tvk(j)<=t && z(j)==1 % если канал первой фазы освободился

z(j)=0;

l(j)=l(j)+1;

if k>0 % если в накопителе есть заявки

p=exprnd(m(j));

tpk(j)=t; % заявка из накопителя идет на обслуживание в канал

tvk(j)=tpk(j)+p;

z(j)=1; % канал становится занят

k=k-1; % число заявок в очереди уменьшается на единицу

end

end

end

if ti<t % источник сгенерировал заявку

q=exprnd(N);

ti=ti+q;

vti=[vti,ti];

num=num+1;

for j=1:R

if ql==0 % если заявка еще не ушла на обслуживание

if z(j)==0 % и если канал первой фазы свободен и

p=exprnd(m(j)); % заявка идет на обслуживание в канал

tpk(j)=t;

tvk(j)=tpk(j)+p;

z(j)=1;

km=km+1;

ql=1;

end

end

end

if ql==0 % если заявка еще не обслуживается

if k<M % если в очереди есть место

tpn=ti; % заявка становится в очередь

k=k+1;

vpn=[vpn,tpn];

else

if k==M % если мест в очереди нет

otk=otk+1; % заявка считается потерянной

end

end

end

srO=srO+k;

end

sol1=[t,ti,tvk(1),z(1),tvk(2),z(2),k,otk,num];

end

not_end=0;

for j=1:R

if z(j)==1

not_end=not_end+1;

end

end

n=size(find(vti<tm),2); % количество поступивших заявок

finish=0;

for j=1:R

finish=finish+l(j); % количество обслуженных заявок

end

sr=srO/n; % средняя длина очереди

p=otk/(finish+otk); % вероятность потери заявки

pkm=km/finish; % вероятность немедленного обслуживания заявки

disp(' n K1 K2 k otk not_end')

sol=[n,l(1),l(2),k,otk,not_end];

disp(' ')

disp(sol)

sprintf('Вероятность потери заявок= %g',p)

sprintf('Средняя длина очереди= %g',sr)

sprintf('Вероятность немедленного обслуживания заявки= %g', pkm)

Результат работы данной программы:

n K1 K2 k otk not_end

18 10 5 0 2 1

Вероятность потери заявок= 0.117647

Средняя длина очереди= 0.5

Вероятность немедленного обслуживания заявки= 0.8

Рассмотрим реализацию данной системы при использовании средства визуального моделирования MATLAB – STATEFLOW. Краткая характеристика этого расширения была дана в главе 4, поэтому сейчас остановимся более подробно на тех возможностях STATEFLOW, которые нам понадобятся для реализации этого примера.

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

Требуется построить SF-диаграмму, реализующую работу данной системы.

Разработаем модель по принципу нисходящего проектирования. Наша модель будет состоять из четырех блоков (рис. 5.28), функционирующих параллельно, каждый из которых впоследствии будет представлен своей SF-диаграммой.

Рис. 5.28 Структура модели

Блок 1 должен в определенные моменты времени генерировать поступление новой заявки в систему. Моменты появления заявок в системе носят стохастический, т.е. случайный, характер. Когда в системе появляется новая заявка она должна либо поступить на обработку в канал (блоки 3 и 4), если хотя бы один из каналов свободен, либо, если оба канала заняты, проследовать на обработку в блок 2, который, в свою очередь, либо поставит заявку в очередь, либо, при отсутствии мест в очереди, «потеряет» ее.

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

Блок Canal может находиться в двух состояниях: «канал свободен» и «канал занят». Между этими состояниями возможны переходы, которые характеризуются следующими событиями: приходом заявки на обработку, т.е. канал из состояния «свободен» переходит в состояние «занят», и окончанием обработки заявки каналом, т.е. канал из состояния «занят» переходит в состояние «свободен». Структура данного блока изображена на рисунке 5.29. Примем, что по умолчанию в начальный момент времени блок Canal находится в состоянии «свободен».

После определения общей структуры блока требуется описать «характеристики» состояний (данные, идентифицирующие нахождение в данном состоянии; действия, происходящие во время нахождения в состоянии, во время выхода из состояния и прочее) и события, определяющие переходы. Очевидно, что данные события будут зависеть от функционирования параллельно работающих блока 1 – блока поступления заявок в систему и блока 2 – блока, регулирующего работу очереди.

Общая структура блока 1 представлена на рисунке 5.30

Рис. 5.30 Структура генератора заявок

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

SF-диаграмма для системы представлена на рисунке 5.32, а SIMULINK-схема системы, после запуска процесса функционирования системы – на рисунке 5.31

Рис. 5.31 Simulink-схема системы после окончания процесса функционирования системы

Рис. 5.32 SF-диаграмма системы

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

Рис. 5.33 Структура Q-схемы

Кроме связей, отражающих движение заявок в Q-схеме (сплошные линии), можно говорить о различных управляющих связях. Примером таких связей являются различные блокировки обслуживающих каналов (по входу и по выходу): блокировки изображены в виде треугольников, а управляющие связи – пунктирными линиями. Блокировка канала по входу означает, что этот канал отключается от входящего потока заявок, а блокировка канала по выходу указывает, что заявка уже обслуженная блокированным каналом, остается в этом канале до момента снятия блокировки. В этом случае, если перед накопителем не используется блокировка канала, то при переполнении будут иметь место потери заявок.

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

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

Схема детерминированного моделирующего алгоритма Q-схемы представлена на рисунке 5.34

Рис. 5.34 Схема моделирующего алгоритма

Не будем повторно останавливаться на блок-схемах алгоритма, они строятся по аналогии с предыдущим случаем. Данный алгоритм легко реализуется на языке MATLAB.

Дата добавления: 2014-12-27