Общий случай разомкнутой СМО

Рассматривая общий случай разомкнутой СМО, заявки следует считать нетерпеливыми, то есть имеющими право пробыть в СМО не более tДОПеди- ниц времени. Если время пребывания заявки в системе tСпревышает tДОП, за- явка покидает систему и считается для нее потерянной. Нетерпеливость заявок

хорошо отражает свойство старения информации в вычислительных системах реального времени. Будем считать tДОПслучайной величиной, распределенной

экспоненциально с математическим ожиданием М(tДОП) =

TДОП .

Удобной для дальнейшего рассмотрения абстракцией является представ-

ление о простейшем потоке уходов из СМО с интенсивностью n = 1/ t ДОП. Ухо-

ды заявки возможны либо из очереди, если tОЖ >

tДОП, либо из канала обслу-

живания, если tОЖ Ј

TДОП

Ј tС .Методически удобно рассматривать два потока

уходов с интенсивностями, соответственно, nОЖ+ nОБ= n= 1/

TДОП .

3.10.

Граф состояний, соответствующий описанной СМО, приведен на рисунке

Рис. 3.10. Граф состояний разомкнутой многоканальной СМО с очередью и нетерпеливыми заявками

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

Система линейных алгебраических уравнений для предельных вероятно-

стей состояний системы имеет вид:

м- lP0 + (m + n ОБ)P1 = 0,

1 Ј i Ј m - 1,

п-[l+ m(m + n ОБ)]Pm + lPm-1 + [m(m + n ОБ) + n ОЖ]Pm+1 = 0,

н

п-{l+ [m(m + n ОБ) + in ОЖ]}Pm+i + lPm+i-1 + [m(m + n ОБ)(i + 1)n ОЖ]Pm+i+1 = 0;

п-[m(m+ n ОБ) + nn ОЖ]Pm+n + lPm+n-1 = 0.

По

1 Ј i Ј n - 1

Условие нормировки вероятностей:

(3.44)

M n

еPi + еPm +i = 1.

i =0

i =1

Решая данную систему уравнений, можно найти искомые вероятности.

Основные показатели эффективности СМО могут быть найдены по уже известным формулам:

Среднее число занятых каналов:

m n

K = еip i + mеp m + i.

Средняя длина очереди:

i = 0

n

i =1

l = е iPm + i.

i =1

Среднее число заявок в СМО

Z = K + l.

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

Вероятность отказа PОТКможет быть определена как вероятность нахож-

дения системы в состоянии Pm+n, то есть

PОТК

= Pm+n.

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

ОЖ

+ P ОБ ,

ОБ

где PУ

- вероятность ухода заявки во время ожидания; PУ

- вероятность

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

Вероятность ухода заявки во время обслуживания можно определить как отношение суммарной интенсивности ухода во время обслуживания, равной произведению среднего числа занятых каналов Kна интенсивность уходов из одного канала обслуживания nОБ, к интенсивности входящего потока l, то есть

Kn

У l

Аналогично можно выразить вероятность ухода во время ожидания через среднюю длину очереди lинтенсивность ухода одной заявки из очереди nОЖи

интенсивность входящего потока l

ln

У l

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

+ P ОБ .

Вероятность обслуживания PОБ, то есть вероятность появления в потоке обслуженных заявок произвольной заявки из входящего потока, может быть

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

PОБ = 1 - PП .

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

СМО, как интенсивность потока обслуженных заявок lО:

lО = l PОБ = l(1 - PП )

Пример. 3.4

Проектируется трехпроцессорная ВС оперативной обработки информа-

ции. Интенсивность потока задач l= 1,2 с-1, средняя трудоемкость задач t=

4 105 операций. Используются процессоры со средним быстродействием

В= 2 105 оп/с. Объем буферной памяти не позволяет иметь очередь. Потоки событий в системе можно считать простейшими.

Необходимо сравнить два варианта организации вычислительного про-

цесса:

- каждый из процессоров по отдельности реализует последовательный алго-

ритм обработки;

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

2,667 раза.

Для сравнения вариантов использовать комплексный показатель эффек-

тивности: Е = 25 усл. ед lО - 10 усл. ед

Решение:

TОБ

- 10 усл. ед lП.

1. Для анализа первого варианта используем модель трехканальной СМО

без очереди:

m = 3 m1 = В / t = 0,5 с-1 .

Система уравнений для установившегося режима будет иметь вид:

м-1,2P0 + 0,5P1 = 0,

п

п1,2P0 - (1,2 + 0,5)P1 + 2 Ч 0,5P2

н

п1,2P1 - (1,2 + 2 Ч 0,5)P2 + 3 Ч P3

= 0,

= 0,

P0 + P1 + P2 + P3

= 1.

Решение данной системы:

P0 = 0,12; P1 = 0,28; P2 = 0,33; P3 = 0,27.

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

PОТК = P3 = 0,27.

Интенсивность потока потерянных заявок lП

lП = lPОТК = 0,322 с-1 .

Вероятность обслуживания PОБи интенсивность потока обслуженных заявок lОравны, соответственно

PОБ = 1 – PОТК = 0,73,

lО = lPОБ = 0,878 с-1 .

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

1

T ОБ

= PОБ= 1,46 с.

Показатель эффективности:

Е = 25 *0,878 - 10*1,46- 10 *0,322 = 4,1 усл.ед.

2. Анализ варианта с параллельной обработкой проведем на модели од-

ноканальной СМО, для которой интенсивность потока обслуживания равна:

m2 = 2,667m1 = 1,333 c-1 .

Система уравнений для установившегося режима будет иметь вид:

м- 1,2P0 + 1,333P1 = 0,

н

оP0 + P1 = 1.

Решение данной системы:

P0 = 0,53; P1 = 0,47.

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

PОТК = P1 = 0,47.

Интенсивность потока потерянных заявок lП

lП = lPОТК = 0,57 с-1

Вероятность обслуживания PОБи интенсивность потока обслуженных заявок lОравны, соответственно

PОБ = P0 = 0,53,

lО = lPОБ = 0,63 с-1 .

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

1

tОБ =

M2

Показатель эффективности:

PОБ= 0,39 с.

Вывод

Е = 25 *0,63 - 10*0,39- 10 *0,57 = 6,2 усл.ед.

При заданных коэффициентах показателя эффективности вариант парал-

лельной обработки более предпочтителен.

Замкнутые СМО

Важный и интересный класс СМО составляют СМО замкнутого типа. Как говорилось ранее, для замкнутых СМО характерно конечное число источ- ников заявок, причем параметры суммарного входящего потока СМО зависят от состояния самой СМО.

Примером замкнутой СМО может служить вычислительная система опе- ративной обработки с диалоговым режимом работы. Упрощенно представим ее функционирование на некотором интервале времени следующим образом.

Рис. 3.11. Схема замкнутой СМО

Система оперативной обработки содержит Мтерминалов, за каждым из которых работает пользователь (П), формирующий запросы на обслуживание заявки. Обслуживание запросов выполняется совокупностью из mоднотипных ЭВМ (m Ј M), рассматриваемых без детализации их внутренней структуры, как каналы обслуживания с длительностью обслуживания, распределенной по экс-

поненциальному закону с математическим ожиданием

tОБ. Операционная сис-

тема реализует бесприоритетные дисциплины ожидания и обслуживания в по- рядке поступления запросов. Причем все ресурсы некоторой ЭВМ (каналы об- служивания) полностью монополизируются назначенной на обслуживание за- явкой до конца ее обслуживания. Заявка, заставшая все каналы обслуживания занятыми, занимает место в очереди, число мест в которой n = M - m, заявки считаются терпеливыми. Формирование нового запроса пользователь начинает лишь после получения ответа на предыдущий запрос. Причем длительность промежутка времени, необходимого пользователю для формирования очеред- ного запроса, будем считать распределенной экспоненциально с математиче-

ским ожиданием Т, что позволяет рассматривать пользователя как источник простейшего потока с интенсивностью l =1/ Т.

Построим граф состояний такой СМО.

ожидающих ответа на сделанные запросы, то есть с числом заявок, находящих-

ся на обслуживании и в очереди:

- S0- в системе нет ни одной заявки, каналы обслуживания простаивают. Все пользователи независимо друг от друга заняты подготовкой запросов, сле- довательно, интенсивность суммарного потока заявок, переводящего СМО в состояние S1, равна Мl;

- S1- в системе одна заявка, обслуживанием которой занят один канал об- служивания. Пославший запрос пользователь ждет ответа и не формирует но- вых запросов, следовательно, интенсивность потока переходов в соседнее спра- ва состояние равна (М - 1)l.Интенсивность потока переходов в соседнее слева состояние связана с интенсивностью суммарного потока обслуживаний, равной произведению числа занятых каналов на интенсивность потока обслуживаний одного канала, то есть m;

- Sm- в системе mзаявок, все ЭВМ заняты обслуживанием запросов пользо- вателей. Очереди на обслуживание еще нет, интенсивность суммарного потока заявок равна (M - m)l, суммарного потока обслуживания - mm;

- Sm+l- в системе m + lзаявок, все ЭВМ заняты и одна заявка стоит в очереди на обслуживание. Интенсивность суммарного потока заявок равна

[M-(m + l)]l, где l- длина очереди, суммарный поток обслуживаний имеет ин-

тенсивность по-прежнему mm;

- Sm+n- в системе m + nзаявок, то есть все пользователи сформировали и ввели в систему запросы на обслуживание, mЭВМ обслуживают mзаявок, n=M - mзаявок находятся в очереди на обслуживание. Интенсивность суммар- ного потока заявок равна нулю, так как все пользователи ждут ответа на свои запросы, интенсивность суммарного потока обслуживания равна mm;

Для исследования переходного режима в рассматриваемой СМО необхо-

димо составить и решить систему дифференциальных уравнений Колмогорова.

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

м-MlP0 + mP1 = 0

п[M - (i - 1)]lP

-[(M - i)l + im]P

+ (i + 1)mP

= 0;

1 Јi Јm - 1;

П i -1

i i +1

н[M - (m - 1)]lPm -1 -[(M - m)l + mm]Pm + mmPm +1

= 0;

п{M -[m + (i - 1)]}lP

- {mm+ [M - (m + i)]l}P

+ mmP

= 0;

1 Јi Јn - 1

п m + i -1

оп-mmPm + n + lPm +n -1 = 0

m + i

m + i +1

(3.45)

Условие нормировки вероятностей имеет вид

M n

еPi + еPm +i = 1.

i =0

i =1

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

Вероятность обслуживания для замкнутой СМО равна единице, так как любая заявка будет в конце концов обслужена: PОБ = 1.

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

m n

K = еip i + mеp m + i.

i = 0

i =1

Интенсивность потока обслуживания заявок lОдля замкнутой СМО име- ет смысл средней суммарной производительности каналов обслуживания, рав- ной произведению среднего числа занятых каналов обслуживания Kна произ- водительность одного канала обслуживания m:

lО= K m.

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

Поскольку пользователь, сформировав и введя в систему запрос на об- служивание, до получения ответа на свой запрос не формирует новых запросов, суммарный поток заявок на обслуживание будет определяться (М - Z )l. По-

скольку система находится в установившемся режиме, интенсивность суммар-

ного потока заявок на входе системы должна уравновешиваться интенсивно- стью потока обслуженных заявок, то есть в среднем должно выполняться соот- ношение (М - Z )l = K m.

Отсюда несложно найти среднее число заявок в системе:

Z = Ml- Km.

l

Зная Zи K, находим среднюю длину очереди:

l = Z - K.

Важной характеристикой замкнутой СМО является среднее время пре-

бывания заявки в системе

tC, характеризующее и среднее время, в течение ко-

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

Поскольку для замкнутой системы из-за отсутствия потерь среднее время

обслуживания

TОБ

совпадает со средней длительностью обслуживания

tОБ,

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

Рассмотрим возможные гипотезы относительно времени ожидания

tОЖв

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

Заявка, застающая СМО в одном из состояний S0, ..., Sm-1, не будет ждать (tОЖ = 0), так как застает хотя бы один свободный канал обслуживания. Нуле- вое время ожидания мы должны приписать и состоянию Sm+n, так как в этом состоянии внутри замкнутой системы не может появиться новых заявок.

С состоянием Smследует связать ненулевое время ожидания, в среднем равное 1/(mm), так как застав СМО в состоянии Sm, заявка должна будет стать в очередь и дождаться ближайшего события в суммарном потоке обслуживаний, то есть ближайшего момента окончания обслуживаний в каком-либо из mне- зависимо функционирующих занятых каналов обслуживания.

Заявка, заставшая СМО в состоянии Sm+1, занимает в очереди второе ме- сто и должна будет дождаться второго из ближайших событий в суммарном потоке обслуживаний, время ожидания для нее удваивается.

Заявка, застающая СМО в состоянии Sm+i, (i = 1,n-1), должна ждать в среднем (i+1)/(mm), единиц времени. Среднее время ожидания найдем как ма- тематическое ожидание времени ожидания, связанного с произвольным со- стоянием СМО:

t ОЖ

n -1 (i + 1)

= е

p m + i. (3.46)

i = 0 mm

Среднее время пребывания заявки в системе темы, равно

tC, или время реакции сис-

Пример.3.5

t C =

+ t ОБ

= е(l + 1)

L =0 mm

p m + l

+ 1. (3.47)

m

В лаборатории 5 однотипных ЭВМ, которые обслуживаются двумя ин- женерами. ЭВМ требует обслуживания в среднем каждые 2 часа. Инженер тра- тит на обслуживание в среднем 12 минут. ЭВМ имеет пропускную способность

3 зад/ч. Сравнить по пропускной способности лаборатории два варианта орга-

низации обслуживания ЭВМ:

1) каждый инженер обслуживает ЭВМ самостоятельно;

2) инженеры обслуживают ЭВМ совместно, однако их взаимопомощь увеличивает производительность в 1,9 раз.

Решение.

В этой задаче источником заявок на обслуживание являются ЭВМ, роль каналов обслуживания играют инженеры.

Первый вариант организации обслуживания сводится к замкнутой СМО с параметрами:

M = 5; m = 2; n = (M – m) = 3.

Интенсивность входящего потока l= 0,5 час-1, интенсивность потока об-

служивания m1= 5 ч-1.

Система уравнений для установившегося режима будет иметь вид:

м- 2,5P0 + 5P1 = 0,

П2,5P

- 7P

+ 10P

= 0,

П 0 1 2

п2P1 - 11,5P2 + 10P3

н

п1,5P2 - 11P3 + 10P4

= 0,

= 0,

пP3 - 10,5P4 + 10P5

п

= 0,

оP0 + P1 + P2 + P3 + P4 + P5

Решение данной системы:

= 1.

P0 = 0,618; P1 = 0,309; P2 = 0,062; P3 = 0,01; P4 = 0,001; P5 = 0.

Среднее число занятых инженеров:

K = P1 + 2P2 + 2(P3 + P4 + P5) = 0,45.

Среднее число обслуживаемых ЭВМ:

Z = (5Ч0,5-0,45Ч5)/0,5 = 0,5

Средняя длина очереди:

l = 0,5 - 0,45 = 0,05.

Среднее число ЭВМ, занятых производительной работой, равно

M - Z = 4,5.

Пропускная способность системы равна 3Ч4,5 = 13,5 зад/ч.

Второй вариант с взаимной помощью сводится к замкнутой СМО с пара-

метрами:

M = 5; m = 1; n = 4; l = 0,5 ч-1,m2 = 1,9m1 = 9,5 ч-1,

Система уравнений для установившегося режима будет иметь вид:

м- 2,5P0 + 9,5P1 = 0,

П2,5P

- 11,5P

+ 9,5P

= 0,

П 0 1 2

п2P1 - 11P2 + 9,5P3

н

= 0,

п1,5P2 - 10,5P3 + 9,5P4

= 0,

пP3 - 10P4 + 9,5P5

п

= 0,

оP0 + P1 + P2 + P3 + P4 + P5

Решение данной системы:

= 1.

P0 = 0,751; P1 = 0,199; P2 = 0,042; P3 = 0,007; P4 = 0,001; P5 = 0.

Среднее число занятых инженеров:

K = P1 + P2 + P3 + P4 + P5 = 0,249.

Среднее число обслуживаемых ЭВМ:

Z = (5Ч0,5-0,249Ч9,5)/0,5 = 0,269.

Средняя длина очереди:

l = 0,269 - 0,249 = 0,02.

Среднее число ЭВМ, занятых производительной работой, равно

M - Z = 4,73.

Пропускная способность системы равна 3Ч4,73 = 14,2 зад/ч.

Вывод

Организация работы по второму варианту повышает пропускную спо-

собность лаборатории.