Моделирование одноканальной СМО методом особых состояний

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

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

Рассмотрим одноканальную СМО, аналогичную предыдущей одноканальной СМО, т.е. СМО на вход которой через случайные промежутки времени t с заданным законом распределения f(t) поступают однородные заявки.

Если заявка застает канал занятым, она может ожидать в течении случайного промежутка t_ож с заданным законом распределения f(t_ож). По истечении этого времени она получает отказ. Если канал был свободен или заявка могла дождаться освобождения канала, она обслуживается. Время обслуживания – случайная величина t_обс с заданным законом распределения f(t_обс). Но в результате моделирования необходимо кроме среднего времени ожидания заявок в очереди, среднего времени простоя канала и вероятности получения отказа, определить среднюю длину очереди К_ср.

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

Анализируя работу системы можно выделить три ситуации.

Первая ситуация заключается в том, что в момент поступления следующей заявки канал занят. Заявка становится в очередь.

Рассмотрим первую ситуацию с помощью графического изображения

Рисунок 3.12 - Схематическое представление первой ситуации

Формализовать такую ситуацию можно следующим образом:

;

.

Вторая ситуация заключается в том, в момент поступления очередной j-той заявки канал освободился от обслуживания некоторой m-й заявки, которая стояла на обслуживании и очереди нет. Момент начала совпадает с моментом поступления. Рассмотрим вторую ситуацию с помощью графического изображения

Рисунок 3.13 - Схематическое представление второй ситуации

Формализовать вторую ситуацию можно следующим образом:

t_j> =t_m^св

k=0

t_j^нач = t_j

Dt^пр= t_j^нач - t_m^св

Эта ситуация по структуре алгоритма будет совпадать с методом последовательной проводки.

Третья ситуация: К моменту поступления заявки канал освобождался. Тогда на обслуживание выбирается какая-то s-тая заявка из очереди. Момент начала обслуживания совпадает с моментом освобождения канала.

Рисунок 3.14 - Схематическое представление третьей ситуации

Формализовать третью ситуацию можно следующим образом:

t_j> =t_m^св

k> 0

t_s^нач = t_m^св

k=k-1

Dt^ож= t_s^нач - t_s

Третья ситуация, как бы не имеет логического конца, что будет все таки с последней поступившей заявкой? Решить ее судьбу можно только после того, как определятся судьбы заявок, стоящих в очереди. И здесь в свою очередь две ситуации, но они сводятся к двум уже известным. Т.е. есть два варианта - за рассматриваемое время все заявки из очереди успеют обслужиться и заявка при поступлении сразу идет на обслуживание (рис.3.15) и за это же время не все заявки из очереди успеют обслужиться и заявка при поступлении поступают в очередь (рис.3.16) Графически это выглядит следующим образом.

Рисунок 3.14 - Представление ситуации, когда заявки поступают на обслуживание

Рисунок 3.15 - Представление ситуации, когда заявки поступают в очередь

.

Кратко, данный алгоритм можно описать следующим образом.

Операторы 1 и 2 моделируют момент поступления очередной заявки в систему. После поступления заявки с помощью оператора 3 проверяем, свободен ли канал.

Положительной исход соответствует первой ситуации (канал занят), и операторы 4-6 моделируют постановку заявки в очередь. K – номер заявки в очереди. При этом в соответствующие массивы потребуется занести те параметры заявки, которые нужны для расчета тех искомых величин, которые необходимо определить по условию задачи. Например, если надо определить, сколько простояла заявка в ожидании освобождения канала, в массиве tp под номером k запомним момент поступления заявки в систему tp[k]=t_j. Аналогично другие необходимые параметры заявки.

При отрицательном исходе оператора 3, (соответствует ситуации когда канал освобождался в период между последними моментами поступления заявок) проверяем - есть ли очередь (оператор 9).

Если очереди нет (k=0) – ситуация вторая, заявка сразу, без ожидания поступает на обслуживание и наблюдается простой канала. Моделируем обслуживание (операторы 10 - 14).

Если очередь есть (k> 0) – ситуация третья – выбираем заявку из очереди. В этом случае заявка ожидала и оператор 17 посчитает сколько выбранная из очереди заявка ожидала. Для этого потребуются данные, занесенные в соответствующую ячейку в операторе 6. Далее моделируем обслуживание и удаляем ее из очереди (операторы 20 - 22).

Характерной особенностью этой ситуации является то, что после выполнения моделирования обслуживания нельзя вернуться к оператору 1 и моделировать приход очередной заявки, поскольку мы не определились с судьбой последней пришедшей заявки и t_j как бы висит в воздухе. А вот момент освобождения канала изменился и теперь надо сравнить уже имеющийся t_j с новым t_s^св Таким образом управление передается оператору 3.

^.

Варианты выбора заявки из очереди

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

Рассмотрим некоторые варианты выбора заявок из очереди

1. Выбор в порядке поступления.

Выбирается первая в очереди заявка s=1. Параметры ее удаляются из соответствующих массивов

2. Выбор заявки по минимальному времени отказа

В этом случае должны храниться моменты отказов для всех заявок, стоящих в очереди и среди них находится заявка с минимальным временем отказа.

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

3.Выбор заявки из очереди в случайном порядке.

Если все заявки равноправны, то вероятность выбора любой из них будет равна . Сам выбор – это моделирование полной группы событий.

Удаление параметров заявки из очереди может осуществляться как в предыдущем примере.

4.Выбор заявки по приоритету.

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

Например: заявки иимеют два приоритета

1 - приоритет выше

2 - приоритет ниже

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

Контрольные вопросы для самопроверки

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

2. В чем заключается первая ситуация (согласно порядка в данной лекции).

3. Как формализовать первую ситуацию.

4. В чем заключается вторая ситуация (согласно порядка в данной лекции).

5. Как формализовать вторую ситуацию.

6. В чем заключается третья ситуация (согласно порядка в данной лекции).

7. Как формализовать третью ситуацию.

8. Как выглядит фрагмент алгоритма для постановки заявки в очередь

9. Как выглядит фрагмент алгоритма для выбора заявки в порядке поступления.

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

11. Как выглядит фрагмент алгоритма для выбора заявки из очереди по минимальному времени отказа

12. Как выглядит фрагмент алгоритма для выбора заявки из очереди по приоритету