Формулировка задачи: Пусть имеется n каналов, на которые поступает поток заявок с интенсивностью l; поток обслуживания одним каналом имеет интенсивность m. Найти финальные вероятности состояний в системе массового обслуживания, а также характеристики ее эффективности:
А – абсолютная пропускная способность, то есть среднее число заявок, обслуживаемых в единицу времени.
Q – относительная пропускная способность, то есть среднюю долю пришедших заявок, обслуживаемых системой.
Pотк – вероятность отказа, то есть того, что заявка покинет систему не обслуженной.
К – среднее число занятых каналов.
Задача: Состояние системы массового обслуживания s будем нумеровать по числу заявок, находящихся в системе:
So – в системе нет ни одной заявки
S1 – в системе находится одна заявка
Sk – в системе находится k заявок, остальные каналы свободны.
Sn- в системе находится n заявок, все каналы заняты.
Граф состояний многоканальной системы массового обслуживания с отказами выглядит следующим образом:
Блокнот
Интенсивности потоков l одинаковы, так как на системы массового обслуживания действует один и тот же поток заявок. Интенсивности потоков обслуживания m увеличиваются с каждым занятым каналом.
Зная все интенсивности, воспользуемся формулами финальных вероятностей для схемы гибели и размножения.
Члены размножения l/m будут представлять собой коэффициенты при Po в выражениях для P1, P2,… Pn.
P1=l/m*Po
Блокнот
Обозначим l/m =r - приведенная интенсивность потока заявок, то есть среднее число заявок, приходящее за среднее время обслуживание одной заявки, тогда:
Блокнот
Найдем вероятность отказа, то есть того, что все n каналов заняты:
Блокнот
Тогда относительная пропускная способность Q, то есть вероятность того, что заявка будет обслужена, равна:
Блокнот
Абсолютную пропускную способность получим, умножая интенсивность потока заявок l на Q.
Блокнот
Так как каждый занятый канал в единицу времени обслуживает в среднем m заявок, то среднее число занятых каналов равно:
Блокнот
1. Управление ресурсами однопроцессорных систем оперативной обработки данных;
1.1. Алгоритм SPT;
1.2. Алгоритм RR;
1.3. Алгоритм FB;
2. Методы управления ресурсами многопроцессорных систем;
2.1. Алгоритм Макнотона;
2.2. Алгоритм LPT.
SPT- Shortest Processing Task First.
Данный алгоритм используется, когда времена решения задач априори известны. Задача назначается на решения в порядке убывания времени решения, то есть t1<=t2<=…<=tL
При этом время ответа Ui для задачи Zi есть Ui= , где tj – время решения. Тогда среднее время ответа U=1/L . U есть минимальное среднее время обслуживания в алгоритме SPT.
RR – Round Robin.
l
CPU
Очередь заданий Q
s
Поток заданий 1-s
В реальных системах оперативной обработки априорная информация о временах решения задач отсутствует. В таком случае пользуются алгоритмом циклического обслуживания. Заявки на выполнение работ поступают с интенсивностью l в очередь Q, откуда они выбираются и исполняются процессором. Дл обслуживания отдельной заявки отводится постоянный квант времени q. Если работа была выполнена за время q, она покидает систему. В противном случае, она вновь поступает в конец очереди и ожидает предоставление ей очередного кванта процессорного времени.
Оценим среднее время ожидания и пребывания работ в системе с циклическим планированием. Пусть длительность кванта – случайная величина, распределенная по экспоненциальному закону. Примем также, что на вход системы поступает простейший поток с интенсивностью l работ в единицу времени и с вероятностями s или (1-s) работа не будет или, соответственно, будет завершена в текущем кванте. Отсюда следует, что вероятность того, что работа будет выполнена точно за k квантов (не завершена за первые k-1 квантов и завершена в k-ом варианте). Данная вероятность описывается геометрическим распределением (то есть равным количеству испытаний случайного эксперимента до наблюдения первого успеха). Pk=sk-1(1-s).
