Geum.ru

Задача анализа, т е. определение количественных

Вид материалаЗадача
Подобный материал:
1   2   3   4   5


- --- 1 Роб

tоб = 0 * Ротк + TAUоб * Роб = ---- Роб = -----

MU MU


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

-

занятых каналов К. Убедимся в справедливости соотношения,

связывающего эти две характеристики:

- -

К = LA * tоб


Рассмотрим еще один показатель эффективности СМО - среднее

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

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

-

пребывания в очереди (ожидания) tож и из среднего времени

-

пребывания в канале обслуживания tоб. Вследствие независимости

процессов обслуживания и ожидания справедливо соотношение


- - -

tс = tож + tоб


Очевидно, что среднее время пребывания в системе и среднее

число заявок в системе связано соотношением:


- -

Z = LA * tс


Рассмотрим предельный вариант СМО с ожиданием, когда число

мест в очереди бесконечно (n --> бесконечность) и на время

пребывания заявки в системе не наложено ограничений (NU = 0,

ALFAож = 0, ALFAоб = 0). Такие СМО называются чистыми СМО с

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

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

на обслуживание, либо ставится в очередь на обслуживание, причем

из-за отсутствия потерь все заявки из входящего потока рано или

поздно будут обслужены.

Граф переходов такой СМО имеет вид:


+----+ LA +----+ LA LA +----+ LA

| S0 +----->| S1 +-----> ... ----->| Si +-----> ...

| |<-----| |<----- ... <-----| |<-----

+----+ +----+ +----+

MU 2*MU i*MU (i+1)*MU


LA +----+ LA +----+ LA LA +----+ LA

----->| Sm +----->|Sm+1+-----> ... ----->|Sm+l+----->

<-----| |<-----| |<----- <-----| |<-----

+----+ +----+ +----+

m*MU m*MU m*MU m*MU m*MU


Индекс состояний определяет число заявок, связанных с

системой, число состояний в системе бесконечно велико. Граф

соответствует типичной схеме гибели и размножения.

Определим предельные вероятности состояний, устремив j к

бесконечности:

i

RO ----

Pi = ----- Po, i = 1, m

i!


m l

RO RO ----------------

Pm+j = ----- ----- Po, l = 1, бесконечность

m! m**l


+ i m +-1

| m RO RO беск-ть + RO +l|

Po = |1 + SUMMA ----- + ----- SUMMA |-----| |

| i = 1 i! m! l = 1 + m + |

+ +


Из анализа выражения для Р0 следует, что установившийся

режим в СМО сушествует (предельные вероятности отличны от нуля),


беск-ть l

если сходится сумма SUMMA (RO/m) . Необходимым условием

l = 1

сходимости этой суииы для RO > 0, m > 0 является неравенство

RO/m = LA/(m*MU) < 1, то есть когда интенсивность входящего

потока LA меньше максимальной интенсивности суммарного

потока обслуживаний m*MU. Невыполнение указанного неравенства

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

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

При условии LA < m*MU предельный переход l --> бесконечность

в выражении (УП-17) дает


+ i m +-1

| m RO RO RO/m |

Po = |1 + SUMMA ----- + ----- ----------| =

| i = 1 i! m! 1 - RO/m |

+ +


+ i m+1 +-1

| m RO RO |

= |1 + SUMMA ----- + ------------ |

| i = 1 i! m!(m - RO) |

+ +


В "чистой" СМО с ожиданием потери отсутствуют, поэтому

вероятность обслуживания равна единице Роб = 1, интенсивность

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

о

потока LA = LA.

-

Среднее время ожидания заявки tож можно получить предельным

переходом из Тож для системы с конечной длиной очереди n,

устремив n --> бесконечность. Получим:


m

- RO

tож = ---------------------- * P0

(m-1)! * MU*(m -RO)**2


Среднее время обслуживания будет иметь значение

- ---

tоб=1/MU=TAUоб, то есть будет совпадать со средней длительностью

обслуживания заявки.

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

пребывания заявки в "чистой" СМО с ожиданием


m

- RO ---

tc = ---------------------- * P0 + TAUоб

(m-1)!*MU*(m-RO)**2

-

Среднюю длину очереди l и среднее число заявок, связанных с

- -

каналами обслуживания К можно найти, умножив, соответственно, tож

-

и tоб на интенсивность входящего потока LA:

m+1 (VII-34)

- - RO

l = tож * LA = ----------------------- * P0,

(m - 1)!(m - RO)**2


- - --- 1

K = tоб * LA = TAUоб * LA = ---- * LA = RO.

MU


СМО без потерь ("чистые" СМО с ожиданием) не имеют

аналогов среди реальных СМО, однако удобны тем, что позволяют

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

очереди заметно превышает среднюю длину очереди.


2.2.3. СМО с отказами.


Последней среди СМО разомкнутого типа рассмотрим

классическую СМО с отказами. Для этой СМО характерно полное

отсутствие очереди (n = 0), заявка, поступившая на вход СМО,

либо сразу попадает на обслуживание, если свободен хотя бы один

из каналов обслуживания, либо получает отказ и попадает в ту

часть выходящего потока, которая соответствует потерям. В каждый

момент времени с системой может быть связано не более m заявок,

где m - число каналов обслуживания.

Граф переходов m-канальной СМО с отказами приведен на рис.


+----+ LA +----+ LA +----+ LA +----+ LA +----+

| S0 +----->| S1 +>---->| Si +>---->|Sm-1+----->| Sm |

| |<-----| |<----<| |<----<| |<-----| |

+----+ +----+ +----+ +----+ +----+

MU 2MU iMU (i+1)MU (m-1)MU mMU


Предельные вероятности состояний системы, процессы в

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


i +

RO ---- |

Pi = ----- Po, i = 1, n |

i! |

+ i +-1 >

| m RO | |

P0 = |1 + SUMMA ----- | |

| i = 1 i! | |

+ + +


Отказ получает заявка, заставшая СМО в состоянии Sm,

следовательно

m + i +-1

RO | m RO |

Pотк = Pm = ----- |1 + SUMMA ----- |

m! | i = 1 i! |

+ +


Вероятность обслуживания Роб и интенсивность потока

о

обслуженных заявок LA равны, соответственно


Роб = 1 - Ротк = 1 - Pm,

о

LA = LA*Роб = LA*(1 - Pm)

-

Среднее число каналов К может быть найдено как отношение

о

интенсивности потока обслуженных заявок LA к

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

интенсивностью обслуживания MU.


о

- LA LA*Роб

К = ----- = ------- = RO * Роб = RO*(1 - Pm)

MU MU

-

Среднее число заявок, звязанных с системой, Z совпадает со

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

- -

Z = К = RO(1 - Pm).


Задача.


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

неограниченным числом запросов на решение задач. Интенсивность

потока задач LA = 1,2 сек**(-1), средняя трудоемкость задач

--- 5

TAU = 4 * 10 операций. Используется процессор со средним

- 5

быстродействием B = 2 * 10 оп/с. Объем буферной памяти позволяет

очередь неограниченной по длине. Потоки событий в системе можно

считать простейшими.

Необходимо сравнить два варианта организации

вычислительного процесса:

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

тельный алгоритм обработки,

2) все три процессора реализуют параллельный алгоритм

обработки, причем среднее время обработки за счет организации

параллелизма уменьшается в 2,667 раза.

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

эффективности _ _

Е = 2 усл. ед. l + 30 усл. ед./сек * tс.


Для анализа первого варианта используется модель

трехканальной СМО без потерь:

-

B -1 LA

m = 3 MU1 = ----- = 0,5 с , RO1 = -------- = 2,4.

--- MU1

TAU


Условие существования установившегося режима выполняется:


RO1/m = 2,4/3 = 0,8 < 1.


+ i 4 +-1

| 3 RO1 RO1 |

Р0 = |1 + SUMMA ----- + -------------| = 0,056.

| i = 1 i! 3!(3 - 2,4) |

+ +

4

- RO1

l = ---------------- Po = 2,58;

2!(3 - 2,4)**2


-

- l 1

tc = -------- + ---- = 4,15с.

LA MU


Е = 129,66 усл. ед.


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

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

потока обслуживания равна:

-1

MU2 = 2,667 * MU1 = 1,333 с


LA

RO2 = -------- = 0,9.

MU2


Условие выполнения установившегося режима RO2 < 1

выполняется.

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


+ 2 +-1 + 2 2 +-1

| RO2 | | 1 - RO2 + RO2 |

Р0 = |1 + RO2 + ---------| = | ----------------| = 1 - RO2 = 0,1

| 1 - RO2 | | 1 - RO2 |

+ + + +


2 -

- RO2 - l 1

l = --------- = 8,1; tc = -------- + ----- = 7,5 c

1 - RO2 LA MU2


E = 241,2 усл. ед.

По сравнению с вариантом последовательной обработки

увеличивается реактивность системы.


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


Важный и интересный класс СМО составляют СМО замкнутого

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

конечное число источников заявок, причем параметры суммарного

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

отметить, что разомкнутых в строгом смысле этого слова СМО в

действительности не существует, однако для значительного числа

СМО зависимостью интенсивности входящего потока от состояния СМО

можно пренебречь и считать их разомкнутыми. Примером замкнутой

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

диалоговым режимом работы. Упрощенно представим ее

функционирование на некотором интервале времени следующим

образом. Система оперативной обработки содержит М терминалов, за

каждым из которых работает пользователь (П), формирующий запросы

на обслуживание заявки (рис. УП-6). Обслуживание запросов

выполняется совокупностью из m однотипных ЭВМ (m <= M),

рассматриваемых без детализации их внутренней структуры как

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

---

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

Операционная система реализует бесприоритетные дисциплины

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

все ресурсы некоторой ЭВМ (каналы обслуживания) полностью

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

обслуживания. Заявка, заставшая все каналы обслуживания

занятыми, занимает место в очереди, число мест в которой

n = M - m, заявки считаются терпеливыми. Формирование нового

запроса пользователь начинает лишь после получения ответа на

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

необходимого пользователю для формирования очередного запроса,

будем считать распределенной экспоненциально с математическим

_

ожиданием Т, что позволяет рассматривать пользователя как

_

источник простейшего потока с интенсивностью LA = 1/Т.


П1

+-+-+ +----+ +------+

+-> | | | | T1 |\ | |

| +-+-+ +----+ \ /| ЭВМ1 |\

| П2 \ / | | \

| +-+-+ +----+ \ / +------+ \

+-->| | | | T2 |\ \ / \

| +-+-+ +----+ \ \ Q / \

| \ \ +-+-----+-+-+ / . \

| +--+--| | ... | | +--| . ++

| ПМ / +-+-----+-+-+ \ . / |

| +-+-+ +----+ / \ / |

+-->| | | | TM |/ \ / |

| +-+-+ +----+ \ +------+ / |

| \ | | / |

| \| ЭВМm |/ |

| | | |

| +------+ |

+--------------------------------------------------------------+


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

системы будем связывать с числом пользователей, ожидающих ответа

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

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


(M-1)*LA [M-(m-1)]*LA [M-(m+l)]*LA LA

+----+ М*LA+----+ +----+(M-m)*LA +----+ +----+

| S0 +---->| S1 +->------->| Sm +-------->|Sm+l+->------->|Sm+n|

| |<----| |<-------<-| |<--------| |<-------<-| |

+----+ +----+ +----+ +----+ +----+

MU 2*MU m*MU m*MU m*MU m*MU m*MU


S0 - в системе нет ни одной заявки, каналы обслуживания

простаивают, все пользователи независимо друг от друга заняты

подготовкой запросов, следовательно, интенсивность суммарного

потока заявок, переводящего СМО в состояние S1, равна М*LA;

S1 - в системе одна заявка, обслуживанием которой занят

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

ответа на свой запрос и не формирует новых запросов,

следовательно, интенсивность потока переходов в соседнее справа

состояние равна (М - 1)*LA; интенсивность потока переходов в

соседнее слева состояние связана с интенсивностью суммарного

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

на интенсивность потока обслуживаний одного канала, то есть 1*MU;


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Sm - в системе m заявок, все ЭВМ заняты обслуживанием

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

интенсивность суммарного потока заявок равна (M - m)*LA,

суммарного потока обслуживания - m*MU.

Sm+l - в системе m + l заявок, все ЭВМ заняты и одна заявка

стоит в очереди на обслуживание, интенсивность суммарного потока

заявок равна [M - (m + l)]*LA, где l - длина очереди, суммарный

поток обслуживаний имеет интенсивность попрежнему m*MU;


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Sm+n - в системе m + n заявок, то есть все пользователи

сформировали и ввели в систему запросы на обслуживание, m ЭВМ

обслуживают m заявок, n = M - m заявок находятся в очереди на

обслуживание, интенсивность суммарного потока заявок равна нулю,

так как все пользователи ждут ответа на свои запросы,

интенсивность суммарного потока обслуживания равна m*MU.

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

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

Колмогорова. Займемся исследованием установившегося режима,

несомненно существующего в рассматриваемой системе, так как граф

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

Предельные вероятности состояний описываются выражениями


i

M!RO ----

Pi = ------------ Po, i = 1, m;

(M - i)!i!


m+l

M!RO ----

Pm+l = -------------------- Po, l = 1, n;

[M - (m+l)]!m!m**l


+ i m+l +-1

| m M!RO n M!RO |

Po = |1 + SUMMA ------------ + SUMMA --------------------|

| i = 1 (M - i)!i! l = 1 [M - (m+l)]!m!m**l |

+ +


Вероятность обслуживания для замкнутой СМО равна единице,

так как любая заявка будет в конце концов обслужена: Роб = 1.

о

Интенсивность потока обслуживания заявок LA для замкнутой

СМО имеет смысл средней суммарной производительности каналов

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

-

обслуживания К на производительность одного канала обслуживания

о _

MU: LA = К * MU.

_

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

найдено как математическое ожидание числа занятых каналов:


_ m n m m

K = 0 * Po + SUMMAi*Pi + m*SUMMAPm+j = SUMMAi*Pi + m(1 - SUMMAPi)

i = 1 l = 1 i = 1 i = 0


_

Зная среднее число занятых каналов К и, соответственно,

о

интенсивность потока обслуживания заявок замкнутой СМО LA =

_ _

К*MU, можно найти среднее число Z заявок связанных с системой, из

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

введя в систему запрос на обслуживание, до получения ответа на

свой запрос не формирует новых запросов, суммарный поток заявок

_

на обслуживание будет определяться (М - Z)*LA. Поскольку

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

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

уравновешиваться интенсивностью потока обслуженных заявок, то

_ _

есть в среднем должно выполняться соотношение (М-Z)LA = К*MU.

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


_ _

_ M*LA - К*MU K

Z = --------------- = M - ----

LA RO


_ _

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


_ _

_ _ _ К _ К(RO + 1)

l = Z - К = M - ---- - K = M - -----------

RO RO


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

_

пребывания заявки в системе tс, характеризующее и среднее время,

в течение которого пользователь ждет ответа на свой запрос, то

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

_

системы из-за отсутствия потерь среднее время обслуживания tоб

___

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

_

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

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

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

времени. Заявка, застающая СМО в одном из состояний S0, ...,

Sm-1, не будет ждать (tож = 0), так как застает хотя бы один

свободный канал обслуживания. Нулевое время ожидания мы должны

приписать и состоянию Sm+n, так как в этом состоянии внутри

замкнутой системы не может появиться новых заявок. С состоянием

Sm следует связать ненулевое время ожидания, в среднем равное

1/(mMU), так как застав СМО в состоянии Sm, заявка должна будет

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

потоке обслуживаний, то есть ближайшего момента окончания

обслуживаний в каком-либо из m независимо функционирующих

занятых каналов обслуживания. Заявка, заставшая СМО в состоянии

Sm+1, занимает в очереди второе место и должна будет дождаться

второго из ближайших событий в суммарном потоке обслуживаний,

время ожидания для нее удваивается. Заявка, застающая СМО в

_____

состоянии Sm+l, l= 1,n-1, должна ждать в среднем (l+1)/(mMU)

единиц времени. Среднее время ожидания найдем как математическое

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

СМО:

_ m - 1 1 n - 1 (l+1)

tож = 0*Ро + 0*SUMMAPi + -----Рm + SUMMA -----*Pm+l + 0*Pm+n =

i = 1 mMU l = 1 mMU


n - 1 (l+1)

= SUMMA -----*Pm+l

l = 0 mMU

_

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

реакции системы, равно


_ _ _ n - 1 (l+1) ___ n - 1 (l+1) 1

tс = tож + tоб = SUMMA -----*Pm+l + TAUоб = SUMMA -----*Pm+l + --

l = 0 mMU l = 0 mMU MU


Пример.


В лаборатории 5 однотипных ЭВМ, которые обслуживаются двумя