10. Модели теории массового обслуживания

10.1. Необходимость в теории СМО

Теория систем массового обслуживания (СМО) восходит к работам А.К.Эрланга по исследованию причин неэффективности телефонных сетей.

В автоматизированных информационных системах на некоторых участках сети могут возникать перегрузки, что приводит к образованию очередей. Чтобы удовлетворить заданному критерию разработки, при проектировании системы необходимо учитывать эти очереди и уметь отвечать на следующие вопросы: сколько времени придется ждать в очереди, чтобы передать сообщение по данной линии; сколько времени пользователь (например, операционист банка) будет ожидать обслуживания у своего терминала или компьютера ответа на свой запрос; какова вероятность того, что сервер и/или сеть будут заняты? Ответы на эти вопросы позволяют определить важные параметры, используемые при проектировании сети, такие как число компьютеров, которые можно подключить к одному серверу, или требования к оборудованию ЛВС.

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

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

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

10.2. Примеры СМО

Примерами СМО могут служить:

· телефонные станции,

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

· билетные кассы,

· справочные бюро,

· магазины,

· парикмахерские

и т. п.

· Как своеобразные системы массового обслуживания могут рассматриваться:

· информационно-вычислительные сети,

· операционные системы электронных вычислительных машин;

· системы сбора и обработки информации;

· автоматизированные производственные цехи,

· поточные линии;

· транспортные системы;

· системы противовоздушной обороны

и т. п.

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

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

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

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

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

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

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

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

10.3. Определения

10.3.1. Каналы

В любой системе обслуживания предполагается наличие объектов двух типов:

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

· потока заявок

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

В зависимости от числа каналов обслуживания системы массового обслуживания могут быть

· одноканальными

· многоканальными

10.3.2. Заявки

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

10.3.3. Дисциплины

Правило, или алгоритм взаимодействия заявок и каналов мы будем называть дисциплиной обслуживания, или дисциплиной. Отметим, что, вообще говоря, заявке может требоваться несколько обслуживаний в одном или нескольких каналах. Обычно термин система обслуживания (queueing system) употребляется при рассмотрении относительно простых моделей, в которых каждый вызов может иметь только одно обслуживание в некотором канале. Если же вызовы должны пройти обслуживания на ряде приборов в соответствии с заданными маршрутами, то принято говорить о сети обслуживания (queueing network). Другими словами, сеть - это просто сложная система. Для системы обслуживания с одним прибором наиболее известными являются варианты дисциплин:

· Первый пришел - первый обслуживается (first in first out, FIFO, или served first come first served, FCFS).

При этой дисциплине сначала (в произвольном порядке) обслуживаются вызовы, пришедшие в момент времени n=1, затем вызовы, пришедшие в момент n=2, и т.д.

· Приоритетная.

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

10.4. Характеристики СМО

10.4.1. Пропускная способность

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

10.4.2. Системные показатели

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

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

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

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

· среднее время ожидания в очереди;

· закон распределения времени ожидания;

· среднее количество заявок, находящихся в очереди;

· средний доход, приносимый СМО в единицу времени, и т. д.

10.5. Простейший поток

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

10.5.1. Практический пример

Предположим, что в произвольный момент времени клиент обращается в банк с просьбой выдать ему некоторую сумму денег. Это событие вызовет формирование сообщения, которое будет передано в информационную систему банка. Исключим из рассмотрения часы пик и возьмем период времени, в течение которого среднее число клиентов, обращающихся в банк, постоянная величина. Упомянутое событие может произойти в любой момент времени в течение рассматриваемого периода. Обстоятельства, вызывающие это событие, обусловлены личными соображениями клиента и потому возникают случайно. Другими словами, вероятность их появления в данную секунду равна вероятности их появления в любую другую секунду.

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

Рисунок 0-1 К механизму возникновения пуассоновского потока

Эта ситуация является типичной для многих систем, работающих в реальном масштабе времени. Например, система может получать в среднем 10 сообщений в 1 с. Хотя такая система загружена довольно сильно, вероятность того, что какое-либо конкретное; сообщение поступит в данную секунду, очень мала и равна вероятности его поступления в следующую секунду.

10.5.2. Свойства потоков

Рисунок 0-2 Потоки событий (а) и простейший поток (б)

10.5.2.1. Стационарность

Поток называется стационарным, если вероятность попадания того или иного числа событий на элементарный участок времени длиной τ (

Рисунок 0-2, а) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут рассматриваться как стационарные. Например, поток вызовов, поступающих на телефонную станцию, скажем, на интервале от 12 до 13 часов может считаться стационарным. Тот же поток в течение целых суток уже не будет стационарным (ночью интенсивность потока вызовов гораздо меньше, чем днем). Заметим, что так же обстоит дело и с большинством физических процессов, которые мы называем «стационарными» в действительности они стационарны только на ограниченном участке времени, а распространение этого участка до бесконечности лишь удобный прием, применяемый в целях упрощения.

10.5.2.2. Отсутствие последействия

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

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

Рассмотрим, например, поток грузовых поездов, идущих по железнодорожной ветке. Если по условиям безопасности они не могут следовать один за другим чаще, чем через интервал времени t₀, то между событиями в потоке имеется зависимость, и условие отсутствия последействия нарушается. Однако, если интервал t₀ мал по сравнению со средним интервалом между поездами, то такое нарушение несущественно.

10.5.2.3. Ординарность

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

Ординарность означает, что события в потоке приходят поодиночке, а не парами, тройками и т. д. Например, поток клиентов, направляющихся в банк, практически можно считать ординарным, чего нельзя сказать о потоке клиентов, направляющихся в ЗАГС для регистрации брака, и т. д.

Если в неординарном потоке события происходят только парами, только тройками и т. д., то можно его рассматривать как ординарный «поток пар», «поток троек» и т. д. Несколько сложнее обстоит дело, если число событий, образующих «пакет» (группу одновременно приходящих событий), случайно. Тогда приходится наряду с потоком пакетов рассматривать случайную величину X число событий в пакете, и математическая модель потока становится более сложной.

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

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

Если поток событий не имеет последействия, ординарен, но не стационарен, он называется нестационарным пуассоновским потоком. Интенсивность такого потока λ. (среднее число событий в единицу времени) зависит от времени.

10.5.3. Распределение Пуассона

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

Поясним, что это означает. Рассмотрим на оси t, где наблюдается поток событий, некоторый участок времени длины τ (см.

Рисунок 0-2, а), начинающийся в момент t₀ и заканчивающийся в момент t₀ + τ. Нетрудно доказать (доказательство дается во всех курсах теории вероятностей), что вероятность попадания на этот участок ровно т событий и выражается формулой:

(0-1)

где а среднее число событий, приходящееся на участок τ; е основание натуральных логарифмов (2,71828…),

Для стационарного (простейшего) пуассоновского потока величина а равна интенсивности потока, умноженной на длину интервала:

Вид распределения показан на

Рисунок 0-3

Рисунок 0-3 Распределение Пуассона

Рассмотрим на оси t простейший поток событий с интенсивностью λ. (Рисунок 0-2б). Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

F(t) = P(T<t), (0-2)

т. е. вероятность того, что величина Т будет иметь значение, меньшее, чем t. Отложим от начала интервала Т (точки t₀) отрезок t и найдем вероятность того, что интервал Т будет меньше t. Для этого нужно, чтобы на участок длины t, примыкающий к точке t₀, попало хотя бы одно событие потока. Вычислим вероятность этого F(t) через вероятность противоположного события (на участок t не попадет ни одного события потока):

F(t) = 1 - Р0

Вероятность Р₀ найдем по формуле (1), полагая m = 0:

откуда функция распределения величины Т будет:

(0-3)

Чтобы найти плотность распределения f(t) случайной величины Т, необходимо продифференцировать выражение (0‑1) по t:

(0-4)

Закон распределения с плотностью (0‑4) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.

Рисунок 0-4 Экспоненциальное распределение

Найдем числовые характеристики случайной величины Т - математическое ожидание (среднее значение) M[t]=mt, и дисперсию Dt. Имеем

(0-5)

(интегрируя по частям).

Дисперсия величины Т составляет:

(0-6)

Извлекая корень квадратный из дисперсии, найдем среднее квадратическое отклонение случайной величины Т.

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

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

Пример СМО- 1.

В качестве примера рассмотрим банковскую систему, работающую в реальном масштабе времени и обслуживающую большое число клиентов. В часы пик запросы от кассиров банка, работающих с клиентами, образуют пуассоновский поток и поступают в среднем по два в 1 с (λ = 2).Поток состоит из заявок, поступающих с интенсивностью 2 заявки в секунду.

Рассчитаем вероятность Р (m) появления m сообщений в 1 с. Так как λ = 2, то из предыдущей формулы имеем

Подставляя m=0, 1, 2, 3, получим следующие величины (с точностью до четырех десятичных знаков):

Рисунок 0-5 Пример простейшего потока

Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).

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

Пример СМО- 2.

Прибор (сервер), обрабатывающей три сообщения в 1с.

Пусть имеется оборудование, которое может обрабатывать три сообщения в 1 с (µ=3). Поступает в среднем два сообщения в 1с, причем в соответствии c распределением Пуассона. Какая часть этих сообщений будет обрабатываться сразу же после поступления?

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

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

Другими словами, 85,71% сообщений будут обслуживаться немедленно, а 14,29% с некоторой задержкой. Как видим, задержка в обработке одного сообщения на время, большее времени обработки 3 сообщений, будет встречаться редко. Время обработки 1сообщения составляет в среднем 1/3 с. Следовательно, задержка более 1с будет редким явлением, что вполне приемлемо для большинства систем.

10.6. Основы теории

10.6.1. Коэффициент использования оборудования

Систему можно рассматривать как оборудование с определенным коэффициентом использования, или коэффициентом загрузки. В Ошибка! Источник ссылки не найден. Система может обрабатывать максимум µ=3 сообщения в 1с, но фактически обрабатывает в среднем только 2. Таким образом, коэффициент использования системы будет

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

Пример СМО- 3

· Если кассир банка занят в течение 80% своего рабочего времени, а остальное время он тратит на ожидание клиентов, то его можно рассматривать как устройство с коэффициентом использования 0,8.

· Если канал связи используется для передачи 8-битовых символов со скоростью 2400 бит/с, т. е. передается максимум 2400/8 символов в 1 с, и мы строим систему, в которой суммарный объем данных составляет 12000 символов, посылаемых от различных устройств через канал связи в минуту наибольшей нагрузки (включая синхронизацию, символы конца сообщений, управляющие и т. д.), то коэффициент использования оборудования канала связи в течение этой минуты равен

· Если механизм доступа к файлу в час наибольшей нагрузки осуществляет 9000 обращений к файлу, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования механизма доступа в час наибольшей нагрузки составляет

Понятие коэффициента использования оборудования будет использоваться довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

Используя предыдущую формулу, можно составить таблицы значений функции Пуассона, по которым можно определить вероятность поступления m или более сообщений в данный отрезок времени. Например, если в среднем поступает 3,1 сообщения в секунду [т. е. λ = 3,1], то вероятность поступления 5 и более сообщений в данную секунду равна 0,2018 (для m = 5 в таблице). Или в аналитическом виде

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

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

ρ ≤ 0,9

Эти значения можно получить с помощью таблиц Пуассона.

Пусть снова средняя скорость поступления сообщений λ = 3,1 сообщения/с. Из таблиц следует, что вероятность поступления 6 или более сообщений в 1 с равна 0,0943. Следовательно, это число можно взять в качестве критерия нагрузки для проведения начальных расчетов.

10.6.2. Задачи проектирования

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

Чем больше коэффициент использования оборудования, тем длиннее возникающие очереди. Как будет показано ниже, можно спроектировать удовлетворительно работающую систему с коэффициентом использований ρ =0,7 но коэффициент, превышающий ρ > 0,9, может привести к ухудшению качества обслуживания. Другими словами, если канал пересылки массива данных имеет загрузку 20%, вряд ли на нем возникнет очередь. Если же загрузка; составляет 0,9, то, как правило, будут образовываться очереди, иногда очень большие.

При проектировании системы обычно делается оценка коэффициента использования для различных видов оборудования; соответствующие примеры будут приведены в последующих главах. Знание этих коэффициентов позволяет рассчитать очереди к соответствующему оборудованию.

· Какова длина очереди?

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

На вопросы подобного типа можно ответить с помощью теории очередей.

10.6.3. Системы массового обслуживания, их классы и основные характеристики

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

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

СМО классифицируются на системы с:

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

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

Обслуживание (дисциплина очереди) в системе с ожиданием может быть

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

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

· стековым (первой из очереди выбирается последняя заявка).

· Приоритетным

o со статическим приоритетом

o с динамическим приоритетом

(в последнем случае приоритет может, например, увеличиваться с длительностью ожидания заявки).

Системы с очередью делятся на системы

· с неограниченным ожиданием и

· с ограниченным ожиданием.

В системах с неограниченным ожиданием каждая заявка, поступившая в момент, когда нет свободных каналов, становится в очередь и «терпеливо» ждет освобождения канала, который примет ее к обслуживанию. Любая заявка, поступившая в СМО, рано или поздно будет обслужена.

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

· длины очереди (числа заявок, одновременно находящихся в очереди система с ограниченной длиной очереди),

· времени пребывания заявки в очереди (после какого-то срока пребывания в очереди заявка покидает очередь и уходит система с ограниченным временем ожидания),

· общего времени пребывания заявки в СМО

и т. д.

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

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

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

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

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

и т. д.

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

· среднее число заявок в очереди;

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

· среднее время ожидания заявки в очереди;

· среднее время пребывания заявки в системе (в очереди и под обслуживанием);

а также и другие характеристики ожидания.

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

Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов п, интенсивность потока заявок λ, производительность каждого канала (среднее число заявок μ, обслуживаемое каналом в единицу времени), условия образования очереди (ограничения, если они есть).

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.

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

10.6.4. Формулы расчета характеристик СМО для случая обслуживания с одним прибором

Приводимые далее формулы описывают очереди с одиночным прибором обслуживания (элементы очереди ожидают обслуживания на входе одного устройства).

Рисунок 0-6 Модель системы массового обслуживания с очередью

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

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

Назначение излагаемой теории очередей состоит в приближенном определении среднего размера очереди, а также среднего времени, затрачиваемого сообщениями на ожидание в очередях. Желательно также оценить, насколько часто очередь превышает определенную длину. Эти сведения позволят нам вычислить, например, необходимый объем буферной памяти для хранения очередей сообщений и соответствующих программ, необходимое количество линий связи, необходимые размеры буферов для концентраторов и т. д. Появится возможность оценивать времена ответа.

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

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

Пусть

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

t_q среднее время ожидания заявки в очереди,

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

ρ коэффициент использования прибора

c_s коэффициент вариации времени обслуживания

Тогда для времени ожидания заявки в очереди справедлива формула Хинчина-Полачека

Число заявок, ожидающих обслуживания (среднюю длина очереди), можно найти, умножив на величину λ:

что, учитывая, что

дает

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

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

10.6.5. Анализ использования формулы Хинчина-Полачека

Рассмотрим два особых случая:

1). Время обслуживания постоянно, т. е.

Поэтому

2). Время обслуживания имеет экспоненциальное распределение, т. е.

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

С другой стороны, разброс времени обслуживания не так велик, как в случае произвольного или экспоненциального его распределения, т.е., σ_s редко достигает значений t_s. Этот случай иногда считают "наихудшим и потому пользуются формулами, относящимися к экспоненциальному распределению времен обслуживания. Такой расчет может дать несколько завышенные размеры очередей и времен ожидания в них, но эта ошибка, по крайней мере, не опасна.

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

Рассмотрим следующий пример. Имеется шесть типов сообщений с временами обслуживания 15, 20, 25, 30, 35 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

10.6.6. Пример расчета

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

Время ответа системы и его стандартное отклонение рассчитаны с учетом времени ввода данных с АРМа, печатания и оформления документа.

Действия кассира были прохронометрированы. Время обслуживания ts равно общему времени, затрачиваемому кассиром на клиента. Коэффициент использования кассира ρ пропорционален времени его занятости. Если λ число клиентов в часы пик, то ρ для кассира равно

Предположим, что в часы пик приходит 30 клиентов в час. В среднем кассир тратит 1,5 мин на клиента. Тогда

ρ =(1,5 * 30) / 60 = 0,75

т. е. кассир используется на 75%.

Число людей в очереди можно быстро оценить с помощью графиков. Из них следует, что если ρ = 0,75, то среднее число nq людей в очереди у кассы лежит между 1,88 и 3,0 в зависимости от стандартного отклонения для t_s.

Предположим, что измерение стандартного отклонения для t_s дало величину 0,5 мин. Тогда

σ_s = 0,33 t_s

Из графика на первом рисунке находим, что nq = 2,0, т. е. в среднем у кассы буду ожидать два клиента.

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

t_∑ = t_q + t_s = 2,5 мин + 1,5 мин=4мин

где t_s вычисляется с помощью формулы Хинчина-Полачека.

10.6.7. Фактор усиления

Анализируя кривые, изображенные на рисунках, мы видим, что, когда оборудование, обслуживающее очередь, используется более чем на 80%, кривые начинают расти с угрожающей быстротой. Этот факт очень важен при проектировании систем передачи данных. Если мы проектируем систему, в которой оборудование используется более чем на 80%, то незначительное увеличение трафика может привести к резкому спаду производительности системы или даже заставить ее работать в аварийном режиме.

Увеличение входного трафика на небольшое число х%. приводит к увеличению размеров очереди приблизительно на

Если коэффициент использования оборудования равен 50%, то это увеличение равно 4ts% для экспоненциального закона распределения времени обслуживания. Но если коэффициент использования оборудования равен 90%, то увеличение размера очереди равно 100ts%, что в 25 раз больше. Незначительное увеличение нагрузки при 90%-ном использовании оборудования приводит к 25-кратному увеличению размеров очереди по сравнению со случаем 50%-ного использования оборудования.

Аналогично время пребывания в очереди увеличивается на

При экспоненциально распределенном времени обслуживания эта величина имеет значение 4 t_s² для коэффициента использования оборудования, равного 50%, и 100 t_s² для коэффициента 90%, т. е. снова в 25 раз хуже.

Кроме того, для малых коэффициентов использования оборудования влияние изменений σs на размер очереди незначительно. Однако для больших коэффициентов изменение σ_s сильно сказывается на размере очереди. Поэтому при проектировании систем с высоким коэффициентом использования оборудования желательно получить точные сведения о параметре σ_s. Неточность предположения относительно экспоненциальности распределения t_s наиболее ощутима при больших значениях ρ. Более того, если вдруг время обслуживания возрастет, что возможно в каналах связи при передаче длинных сообщений, то в случае большого ρ образуется значительная очередь.