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

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

Q(t) – объем незавершенной работы системы. Необходимо оценить время, которое требуется для завершения этого объема работы.

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

Рассмотрим одноканальную разомкнутую СМО с неограниченной очередью. На вход системы поступают заявки H типов, считаем, что заявки каждого из H типов образуют простейший поток. Известны интенсивности: . Суммарный поток тоже будет простейшим: .

Принципиально: потоки обслуживания H типов имеют произвольное распределение.

Кодификатор: M|G|1|∞|∞

--------------------------------------------------------

Рассмотрим СМО с бесприоритетной дисциплиной ожидания и дисциплиной обслуживания с абсолютным приоритетом (с прерыванием обслуживания).

В канале k обрабатывается заявка З_j. В СМО поступает заявка З_i.

1. если поступившая заявка имеет менее высокий приоритет, то в канале продолжает обрабатываться З_j, а заявка З_i встает в соответствующую очередь O_i на последнее место.

2. если поступившая заявка имеет более высокий приоритет, то она поступает в канал на обработку, не дожидаясь завершения обработки З_j, а З_j поступает в соответствующую очередь О_j на ПЕРВОЕ место.

Если канал свободен, а очереди с приоритетом 1..k пусты, то заявка сразу же поступает на обслуживание, поэтому .

– среднее время ожидания начала обслуживания.

– среднее время ожидания в прерванном состоянии.

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

За время обслуживания заявки k-того приоритета в систему может прийти еще заявок приоритета .

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

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

– Время обслуживания заявок всех приоритетов, более высоких, чем k, которые могут прервать обслуживание нашей заявки:

Но за время могут поступить еще несколько заявок более высокого приоритета, чем k. Их количество будет равно:

Среднее время обслуживания всех заявок будет таким:

Это может продолжаться до бесконечности, поэтому перейдем к пределу:

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