Сети массового обслуживания

Под системой очередей (СМО) понимается динамическая система, предназначенная для эффективного обслуживания потока запросов (запросов на обслуживание) при ограничениях на системные ресурсы.
Модели СМО удобны для описания отдельных подсистем современных вычислительных систем, таких как подсистема процессора - основная память, канал ввода-вывода и т. д. Вычислительная система в целом представляет собой совокупность взаимосвязанных подсистем, взаимодействие которых носит вероятностный характер. Приложение для решения определенной проблемы, поступающее в компьютерную систему, проходит последовательность этапов подсчета, доступа к внешним запоминающим устройствам и устройствам ввода-вывода.
После выполнения определенной последовательности таких этапов, количество и продолжительность которых зависит от сложности программы, заявка считается обслуженной и покидает компьютерную систему. Таким образом, вычислительную систему в целом можно представить набором СМО, каждая из которых отражает процесс функционирования отдельного устройства или группы устройств одного типа, входящих в состав системы.
Набор взаимосвязанных СМО называется сетью массового обслуживания (стохастической сетью).
1 Сети массового обслуживания. Общие сведенияТеория массового обслуживания - одно из разделов теории вероятностей. Эта теория занимается вероятностными задачами и математическими моделями (до этого мы рассматривали детерминированные математические модели). Напомним, что:
Детерминированная математическая модель отражает поведение объекта (системы, процесса) с точки зрения полной определенности в настоящем и будущем.
Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса) и, следовательно, оценивает будущее с точки зрения вероятности определенных событий.
Те. здесь, как, например, в теории игр, задачи рассматриваются в условиях неопределенности.
Давайте сначала рассмотрим некоторые концепции, которые характеризуют «стохастическую неопределенность», когда неопределенные факторы, включенные в задачу, являются случайными величинами (или случайными функциями), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность еще называют «благоприятной», «доброкачественной».
Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские, билетные кассы, информационные бюро, станочные и другие технологические системы, системы управления гибкими производственными системами и т. д.
Каждая СМО состоит из определенного количества сервисных единиц, которые называются сервисными каналами (это машины, транспортные тележки, роботы, линии связи, кассиры, продавцы и т. д.). Любой СМО предназначен для обслуживания потока запросов (требований), поступающих в произвольное время.
Обслуживание запроса продолжается некоторое, вообще говоря, случайное время, после чего канал освобождается и готов к приему следующего запроса. Случайный характер потока заявок и времени обслуживания приводит к тому, что в некоторые периоды времени на входе СМО накапливается излишне большое количество запросов (они либо попадают в очередь, либо оставляют СМО не обслуженными). В другие периоды СМО будет работать с недогрузкой или даже простаивать.
Процесс работы СМО - это случайный процесс с дискретными состояниями и непрерывным временем. Состояние СМО резко меняется в моменты появления некоторых событий (приход нового запроса, окончание обслуживания, момент, когда запрос, уставший ждать, покидает очередь).
Предметом теории массового обслуживания является построение математических моделей, связывающих заданные условия работы системы массового обслуживания (количество каналов, их производительность, правила работы, характер потока запросов) с интересующими нас характеристиками. - показатели эффективности системы массового обслуживания. Эти показатели описывают способность СМО справляться с потоком заявок. Это могут быть: среднее количество запросов, обслуживаемых СМО за единицу времени; среднее количество занятых каналов; среднее количество заявок в очереди; среднее время ожидания услуги и т. д.
Математический анализ работы СМО значительно облегчается, если процесс этой работы марковский, т.е. потоки событий, переводящие систему из состояния в состояние, являются наиболее простыми. В противном случае математическое описание процесса сильно усложняется и редко удается привести его к конкретным аналитическим зависимостям.
Первый дивизион (по наличию очередей):
1.СМО с отказами;
2.СМО с очередью.
В СМО с отказами заявка, полученная в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В системе очередей с очередью запрос, поступающий в то время, когда все каналы заняты, не уходит, а ставится в очередь и ожидает возможности обслуживания.
СМО с очередями делятся на разные типы в зависимости от того, как организована очередь - ограниченная или нет. Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
Так, например, рассматриваются следующие СМО:
1. СМО с нетерпеливыми обращениями (длина очереди и время обслуживания ограничены);
2. CMO с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т. д.
Кроме того, СМО делятся на открытые СМО и закрытые СМО.
В открытой СМО характеристики потока заявок не зависят от состояния самой СМО (сколько каналов заняты). В закрытой СМО они зависят. Например, если один рабочий обслуживает группу машин, которые время от времени требуют настройки, то интенсивность потока «требований» от машин зависит от того, сколько из них уже исправно работают и ждут настройки.
2 История развития История теории массового обслуживания насчитывает почти 100 лет. «Время ожидания и количество звонков» Йоханнсена (статья, опубликованная в 1907 г. и переизданная в «Post Office Electrical Engineers Journal», Лондон, октябрь 1910 г.), кажется, является первой статьей по этому вопросу. Но метод, использованный в этой статье, не был математически точным, и поэтому с точки зрения точной трактовки исторически важной является работа А.К. Эрланга «Теория вероятностей и телефонных разговоров» (Nyt tidsskrift for Matematik, B, 20 (1909), стр. 33). В этой статье он закладывает основу для места пуассоновского (и, следовательно, экспоненциального) распределения в теории массового обслуживания. Его статьи, написанные в следующие 20 лет, содержат некоторые из наиболее важных концепций и методов; два таких примера - понятие статистического равновесия и метод записи уравнений баланса состояния (позже названных уравнениями Чепмена-Колмогорова). Особо следует упомянуть его статью «О рациональном определении числа цепей», в которой впервые была рассмотрена проблема оптимизации в теории массового обслуживания.
Следует отметить, что в работе Эрланга, а также в работе, проделанной другими в двадцатые и тридцатые годы, мотивацией была практическая проблема скопления. В течение следующих двух десятилетий несколько теоретиков заинтересовались этими проблемами и разработали общие модели, которые можно было использовать в более сложных ситуациях. Некоторые из авторов, внесших важный вклад, - это Кроммелин, Феллер, Йенсен, Хинчин, Колмогоров, Палм и Поллачек. Подробный отчет об исследованиях, проведенных этими авторами, можно найти в книгах Сиски (1960) и Саати (1961). Исследования Колмогорова и Феллера чисто разрывных процессов заложили основу теории марковских процессов в том виде, в котором она развивалась в последующие годы.
Отмечая неадекватность теории равновесия во многих ситуациях с очередями, Поллачек (1934) начал исследования поведения системы в течение конечного промежутка времени. С тех пор и на протяжении всей своей карьеры он проделал значительную работу в области аналитического изучения поведения систем массового обслуживания. Тенденция к аналитическому изучению основных случайных процессов в системе продолжалась, и теория массового обслуживания оказалась плодородной почвой для исследователей, которые хотели провести фундаментальные исследования случайных процессов с использованием математических моделей.
Несмотря на то, что Эрланг не объяснил свои результаты в этих терминах, он использовал эту основную концепцию в своих результатах. По сей день подавляющее большинство результатов теории массового обслуживания, используемых на практике, получены в предположении статистического равновесия. Тем не менее, для полного понимания основных процессов необходим анализ, зависящий от времени. Но вовлеченные процессы непросты, и для такого анализа необходимы сложные математические процедуры. Таким образом, развитие теории массового обслуживания можно проследить по двум параллельным дорожкам:
(i) использование существующих математических методов или разработка новых для анализа лежащих в основе процессов;
(ii) включение различных характеристик системы, чтобы модель точно отражала явления реального мира.
Теория массового обслуживания как идентифицируемая совокупность литературы была по существу определена в фундаментальных исследованиях 1950-х и 1960-х годов. Полную библиографию исследований в этот период см. В Syski (1960), Saaty (1961, 1966) и Bhat (1969). Здесь мы упомянем лишь несколько статей и книг, которые, по мнению автора, оказали глубокое влияние на направление исследований в области теории массового обслуживания.
Очередь M / M / 1 (прибытие Пуассона, экспоненциальное обслуживание, одиночный сервер) - одна из самых ранних систем, подлежащих анализу. При статистическом равновесии баланс уравнений состояния прост, а предельное распределение размера очереди получается рекурсивными аргументами. Но для решения, зависящего от времени, необходимы более сложные математические методы. Первое такое решение было дано Бейли (1954) с использованием производящих функций для дифференциальных уравнений, управляющих основным процессом, в то время как Ледерман и Рейтер (1956) использовали спектральную теорию в своем решении. Преобразования Лапласа использовались позже для той же проблемы, и с тех пор их использование вместе с производящими функциями было одной из стандартных и популярных процедур при анализе систем массового обслуживания.
Вероятностный подход к анализу был инициирован Кендаллом (1951, 1953), когда он продемонстрировал, что вложенные цепи Маркова могут быть идентифицированы в процессе определения длины очереди в системах M / G / 1 и GI / M / Линдли (1952) вывел интегральные уравнения для распределений времени ожидания, определенных во вложенных марковских точках в общей очереди GI / G / 1. Эти исследования привели к использованию теории восстановления в анализе систем массового обслуживания в 1960-х годах. Идентификация вложенных цепей Маркова также облегчила использование комбинаторных методов, поскольку длина очереди в точках Маркова рассматривалась как случайное блуждание.
Математическое моделирование - это процесс аппроксимации. Вероятностная модель немного приближает это к реальности; тем не менее, он не может полностью представить феномен реального мира из-за сопряженных с ним неопределенностей. Следовательно, это вопрос удобства, где можно провести грань между простотой модели и близостью представления. В 1960-х годах несколько авторов начали исследования роли приближений в анализе систем массового обслуживания. Из-за необходимости использования результатов в приложениях в литературе появились различные типы приближений.
Чтобы упомянуть несколько, одним из подходов к аппроксимации является анализ в условиях интенсивного трафика (когда интенсивность трафика, отношение скоростей ввода к выходу, приближается к 1), и исследования по этой теме были инициированы Кингманом с целью получения более простого выражения для окончательного результата. Предположение о интенсивном движении также привело к диффузионному приближению, а также к результатам слабой сходимости таких исследователей, как Иглхарт.
Проведенный Гавером (1968) анализ виртуального времени ожидания очереди M / G / 1 является одной из первых попыток использования диффузионного приближения для системы массового обслуживания. Флюидное приближение, предложенное Ньюэлл (1968, 1971), рассматривает процессы прихода и отхода в системе как текучую среду, втекающую и выходящую из коллектора, и их свойства выводятся с использованием прикладных математических методов.
К концу 1960-х годов большинство базовых систем массового обслуживания, которые можно было рассматривать как разумные модели явлений реального мира, были проанализированы, и в выходящих статьях рассматривались лишь незначительные вариации этих систем, не внося особого вклада в методологию. Были даже заявления о том, что теория массового обслуживания находится на последних этапах своего существования. Но такие прогнозы были сделаны, не зная, что достижения компьютерных технологий будут значить для теории массового обслуживания. Достижения, вдохновленные или поддерживаемые компьютерными технологиями, проявляются в двух измерениях: методологическом и прикладном. Ниже приведены некоторые из важных тем, исследованных в ходе таких достижений. Поскольку с точки зрения прикладной вероятности методология и приложения способствуют развитию предмета симбиотическим образом, они перечислены ниже без классификации.
Процессы трафика в компьютерах и компьютерных сетях потребовали разработки математических методов для их сопоставления. Первая статья о сетях массового обслуживания написана Дж. Джексоном (1957). Математические основы анализа сетей массового обслуживания принадлежат Уиттлу (1967, 1968) и Кингману (1969), которые рассматривали их в терминологии популяционных процессов. Проблемы сложных сетей массового обслуживания широко исследуются с начала 1970-х годов. В нескольких обзорных статьях и книгах резюмируется основной вклад, сделанный в этой области.
Начиная с введения вероятностных распределений фазового типа, Марсель Нейтс (Marcel Neuts, 1975) разработал метод анализа, который расширяет и модифицирует более ранний метод преобразования на многомерные и делает его пригодным для решения с помощью компьютеров. См. Neuts (1978, 1981), Sengupta (1989) и Ramaswami (1990, 2001). Использование распределений фазового типа в представлении элементов системы и метода матричной аналитики в их анализе значительно расширило сферу применения систем массового обслуживания, для которых можно получить полезные результаты.
Традиционный метод анализа системы массового обслуживания зависит от обращения производящих функций и / или преобразований Лапласа для получения полезных результатов. Сложность инверсии преобразования подтолкнула к дальнейшим исследованиям в этой области, начиная с Abate и Dubner (1968), Dubner и Abate (1968) и Abate et al. (1968) по этой теме опубликовано много работ.
Необходимость анализа процессов трафика в быстрорастущей компьютерной и коммуникационной индустрии является основной причиной возрождения теории очередей после 1960-х годов. Исследования сетей массового обслуживания и такие книги, как Coffman an Deming (1973) и Kleinrock (1975, 1976), заложили основу для энергичного развития этой темы.
Для отслеживания этого роста мы можем процитировать следующие статьи из журнала Queuing Systems: Coffman and Hoffri (1986), описывающие важные компьютерные устройства и модели массового обслуживания, используемые при анализе их производительности; Яшков (1987) об аналитических моделях разделения времени, дополняющий МакКинни (1969) по той же теме; три специальных выпуска журнала под редакцией Митры и Митрани (1991), Доши и Яо (1995) и Константополуса (1998). Исследования приложений с очередями можно также найти в различных компьютерных журналах. По этой теме появилось и продолжает появляться несколько книг.
Некоторые из специальных моделей очередей 1950-х и 1960-х годов нашли более широкое применение в контексте компьютерных и коммуникационных систем. Ниже мы упомянем три такие модели, которые привлекли значительное внимание.
Модели опроса. Эти модели представляют системы, в которых один или несколько серверов циклически обслуживают несколько очередей. На основе вариаций в структуре системы и дисциплине очереди возникает большое количество моделей.
Модели для отпуска. Системы массового обслуживания с перерывами в обслуживании не редкость. Отказы машин, прерывание обслуживания из-за операций обслуживания, циклические очереди серверов и потоки запланированных заданий - вот лишь некоторые из примеров. Ключевой особенностью результатов является возможность разложить их на результаты, соответствующие системам без отпусков, и результаты в зависимости от распределений, связанных с последовательностью отпусков.
Очереди на повторное рассмотрение. В системах с ограниченной пропускной способностью клиенты, которым отказано во входе в систему, пытаются войти снова, что является довольно распространенным явлением. Поскольку они уже пытались получить услугу один раз, они принадлежат к другой группе клиентов, чем первоначальная. Проблемы, связанные с этим явлением, широко исследовались в литературе.
Заключение Возможность использования теории принятия решений в системах массового обслуживания определяется следующими факторами:
1. Количество заявок в системе (которая рассматривается как СМО) должно быть достаточно большим (в большом количестве).
2. Все заявки, поступающие на вход СМО, должны быть одного типа.
3. Для расчетов по формулам необходимо знать законы, определяющие поступление заявок и интенсивность их обработки. Причем поток заявок должен быть пуассоновским.
4. Структура СМО, т.е. набор входящих запросов и последовательность обработки заявки, должна быть жестко зафиксирована.
5. Необходимо исключить предметы из системы или описать их как требования с постоянной интенсивностью обработки.
К указанным выше ограничениям можно добавить еще одно ограничение, которое сильно влияет на размерность и сложность математической модели.
6. Количество используемых приоритетов должно быть минимальным. Приоритеты заявок должны быть постоянными, т.е. они не могут меняться в процессе обработки в СМО.
Список использованной литературы1. Кениг, Д. Методы теории массового обслуживания /Д.Кениг, Д.Штойян.: Пер. с нем. /Под. ред. Г.П.Климова. М., 1981.
2. Ивченко, Г.И. Теория массового обслуживания/ Г.И.Ивченко, В.А.Каштанов, И.Н.Коваленко. М., 1982.
3. Гнеденко, Б.В. Введение в теорию массового обслуживания / Б.В.Гнеденко, И.Н.Коваленко. М., 1987.
4. Саати, Т.Л. Элементы теории массового обслуживания и ее приложения / Т.Л Саати/ : Пер. с англ. /Под. ред. И.Н. Коваленко, изд-ие 2. М., 1971.