Эта статья была подготовлена в 1999 году для публикации в Соросовском образовательном журнале (СОЖ), которая по техническим причинам не была осуществлена.

Стохастические системы и сети обслуживания

С.Г. Фосс

"Очереди являются бедствием нашей эпохи" (кто-то это сказал)

Действительно, кто из нас не сталкивался с очередями? Нам часто приходится тратить время на ожидание: в магазине мы стоим в очереди, в автобусе или автомашине ждем зеленого сигнала светофора или (что хуже) попадаем в дорожные пробки; долго пытаемся дозвониться по телефону или войти в сеть ИНТЕРНЕТ... Каждый легко вспомнит массу примеров потери времени на ожидание - еженедельной, ежедневной, даже ежечасной. Можно произвести приближенный подсчет, сколько в среднем за неделю вы простаиваете во всех очередях, с которыми сталкиваетесь. Затем умножить это время на число недель в году - и ужаснуться!     Из-за чего возникают очереди? Во всех случаях схема, по сути, одна и та же: есть некоторое количество "клиентов", каждый из которых желает "обслужиться" в одном и том же месте, и сделать это одновременно они не могут - их интересы вступают в "конфликт". Для того, чтобы этот конфликт разрешать, формируется некоторое правило (алгоритм, дисциплина), упорядочивающее обслуживания клиентов. В одних случаях (например, в случае со светофором) правила задаются заранее, "третьим лицом"; в других они формируются стихийно.     Математическая теория систем обслуживания - область прикладной математики, использующая методы теории вероятностей и математической статистики. Часто ее называют также теорией массового обслуживания, а в англоязычной литературе - теорией очередей (queueing theory). Стимулом к развитию теории систем обслуживания явилось стремление научиться предсказывать случайно изменяющиеся потребности по результатам наблюдений и на основе этого организовывать обслуживание с приемлемым временем ожидания.

     1.  Введение

         Первые математические работы по системам обслуживания появились в начале двадцатого века. Они были тесно связаны с практическими задачами, касавшимися вопросов обслуживания телефонных линий, определения оптимального количества касс и продавцов в торговых предприятиях, выработки правил расчета запасов в магазинах, достаточных для их бесперебойной работы, и других. Среди этих работ особо важное место занимают исследования датского ученого А.К. Эрланга (1878-1929). Благодаря развитию теории вероятностей, к середине двадцатого столетия теория систем обслуживания получила хороший математический фундамент. Среди фамилий ученых, внесших наибольший вклад в теорию очередей, следует назвать такие, как Ф. Поллачек, А.Я. Хинчин, Б.В. Гнеденко, Ж.Ф.С. Кингман, Р.М. Лойнес, С.М. Росс, В.Л. Смит, Г. Коэн, А.А. Боровков, У. Прабху, П. Франкен, В.А. Малышев.

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

• среди математических статей за 1980-1995 годы - 13 процентов ;
• среди диссертаций за 1980-1995 годы - 24 процента ;
• среди работ, опубликованных в научных и инженерных журналах и сборниках в областях физики, электроники, вычислительных методов и информационных технологий - 60 процентов (данные по индексу INSPEC, разработанному американским и немецким обществами электронной инженерии).

         В практике возникают новые и новые задачи, связанные с очередями и требующие математического решения, что способствует появлению новых и развитию известных направлений исследований. Например, с каждым годом компьютерные системы работают все быстрее и быстрее, но их очереди становятся все длиннее и длиннее. Поэтому стали актуальными проблемы, связанные со "взаимодействием" очередей в течение длительных промежутков времени. А это привело к интенсивному развитию направления, получившего название "теория больших уклонений" (``large deviation theory'').

         Статьи по математической теории систем обслуживания публикуются в десятках различных журналов. С 1986 года издается специализированный математический журнал ``Queueing Systems'' ("Системы очередей").

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

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

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

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

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

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

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

     2.  Сведения из теории вероятностей

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

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

         Если событие при некотором испытании может как произойти, так и не произойти, то мы назовем это событие случайным. Случайному событию приписывается некоторое число между 0 и 1, называющееся его вероятностью и обозначающееся через . Например, если подбрасывается симметричная монета, то событие   является случайным, и ему естественно приписать вероятность

.

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

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

         Например, при бросании игрального кубика могут выпасть числа 1,2,3,4,5,6. Введем шесть событий

, .

 , , .

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

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

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

Для любого числа можно определить вероятность того, что примет значение, не меньшее чем :

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

Среднее квадратическое отклонение (или - неформально - средний разброс) случайной величины есть квадратный корень из дисперсии: .

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

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

     и   

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

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

.

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

        Например, если подбросить кубик несколько раз и обозначить через значение, выпадающее при -ом подбрасывании, то эти случайные величины будут одинаково распределены.

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

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

        Например, если мы подбросим два одинаковых кубика по разу, то всего различных исходов 36 (каждому варианту выпадения первого кубика может соответствовать 6 вариантов выпадения второго), и все они "равновозможны", т.е. вероятность того, что на первом выпадет число , а на втором - (где - любые целые числа от 1 до 6), равна , что совпадает с произведением . Значит, соответствующие случайные величины независимы.

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

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

Теорема 2.1.   Закон больших чисел, ЗБЧ3.

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

         Например, если будем бросать кубик достаточно много раз и складывать выпадающие значения, то при делении полученной суммы на количество испытаний получим число, очень близкое к 3,5.

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

Теорема 2.2.   Центральная предельная теорема, ЦПТ.

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

        Часто центральную предельную теорему называют также "принципом инвариантности"⁴. Действительно, каково бы ни было "индивидуальное" распределение случайных величин , с ростом исчезает влияние этой "индивидуальности" на "поведение" случайной величины - оно достаточно точно задается функцией Лапласа.

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

     3.  Системы и сети очередей

        В этом параграфе мы обсудим несколько примеров систем и сетей очередей.

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

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

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

        Естественно считать, что система работает "стабильно", если с ростом времени распределения случайных величин остаются ограниченными - в некотором смысле, но в каком? Можно, к примеру, назвать систему стабильной, если найдется некоторое число , при котором неравенство

  (3.2)

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

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

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

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

Теорема 3.1.

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

        Поясним, как доказывается эта теорема.

Начнем со случая .

Если все вырождены (и совпадают с ), то при всех . Поэтому система стабильна.

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

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

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

        В случае утверждение Теоремы 3.1 доказывается значительно сложнее, и мы его приводить не будем. Опишем лишь один полезный прием, используемый при доказательстве и называемый часто "правилом насыщения" (saturation rule). Предположим, что к некоторому моменту времени в системе скопилось очень много вызовов (система "насыщена" вызовами). Тогда, начиная с момента , в течение длительного времени сервер обслуживает только имеющиеся вызовы - независимо от того, что еще в систему поступает. Допустим, что так сервер работает в течение времени . За это время обслуживается приблизительно вызовов (то есть сервер обслуживает приблизительно вызовов за единицу времени, эту дробь естественно назвать интенсивностью, или скоростью обслуживания), а поступает вызовов. По закону больших чисел,

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

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

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

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

• Дисциплина первый пришел - первый обслуживается (first come first served, FCFS). При этой дисциплине сначала (в произвольном порядке) обслуживаются вызовы, пришедшие в момент времени , затем вызовы, пришедшие в момент , и т.д.

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

        Справедлива следующая

Теорема 3.2.

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

         Доказательства Теорем 3.1 и 3.2 используют одни и те же рассуждения.

         Пример 2. Открытая сеть Джексона с двумя серверами и одним типов вызовов.

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

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

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

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

         В случае, когда вызов сразу поступил в очередь к первому серверу, вероятность того, что он снова вернется на этот сервер хотя бы раз (другими словами, посетит этот сервер хотя бы два раза), равна вероятности того, что он переходит с первого сервера на второй и затем - со второго на первый. Так как эти события независимы, то . Аналогично, вероятность того, что вызов вернется на первый сервер хотя бы раз, если он начал обслуживание с этого сервера, равна . Поэтому среднее число посещений равняется

.

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

.

         И так как первый случай осуществляется с вероятностью , а второй - с вероятностью , то

.

         Для того, чтобы понять, при каких условиях сеть работает стабильно, воспользуемся снова правилом насыщения. Но теперь нам удобнее рассуждать в терминах не числа вызовов, а количества "работы".

         Каждый вызов посетит в среднем первый сервер раз. Значит, он в среднем "приносит" на этот сервер количество работы, равное . За единицу времени в систему поступает в среднем вызовов. Значит, все они вместе приносят на первый сервер количество работы . Обозначим это число через . Если первый сервер "насыщен", то он постоянно занят (работает с интенсивностью единица). Поэтому для стабильности нужно, чтобы выполнялось условие Аналогично, требуется и второе условие:

         Поэтому неудивительно, что имеет место следующая теорема.

Теорема 3.3.

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

         Теорема 3.2 обобщается естественным образом на случай любого числа вызовов, а Теорема 3.3 - любого числа серверов.

         До конца 80-х годов у большинства ученых, работающих в области теории систем обслуживания, была надежда на то, что "правило насыщения" является универсальным, т.е. с его помощью всегда можно найти верные условия стабильности систем обслуживания. Однако в 1990 году Р.П. Кумар привел относительно простой пример детерминированной (неслучайной) системы, в которой условия стабильности существенно отличаются от получаемых с помощью этого правила. Затем А.Л.Столяр и А.Н.Рыбко (1992) построили пример системы со случайными характеристиками, имеющей те же свойства. Эти и другие примеры привели к развитию так называемой "теории жидкостной аппроксимации", позволяющей анализировать условия стабильности случайных систем обслуживания с помощью вспомогательных динамических "жидкостных" моделей, удовлетворяющих ряду интегро-дифференциальных уравнений.

    4.  Системы множественного доступа

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

         Рассмотрим, к примеру, одноканальную систему с несколькими типами вызовов. Допустим, что любой вызов (любого типа) требует обслуживания в течение единичного времени (скажем, время обслуживания равно 1 секунде). Предположим, что сервер находится на космической станции, все вызовы первого типа скапливаются в очереди где-то в Австралии, второго - в России, третьего - в Бразилии, и т.д. Наземная связь работает намного хуже, чем связь космическая. Упорядочить вызовы в каждой очереди можно, а упорядочивать поступление на сервер вызовов из разных очередей очень сложно, на этом может теряться большое количество времени и средств. Поэтому на практике стали применять такой алгоритм:

• заранее каждой очереди указывается некоторое число (-ой очереди - число , где ) ;

• в каждую единицу времени, первый вызов из первой очереди посылает сигнал на сервер с вероятностью , первый вызов из второй очереди - с вероятностью , и т.д., причем делают они это независимо один от другого (если некоторая очередь пуста, то из нее сигнала не посылается);

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

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

         Такого рода системы (и сети) получили название "системы множественного доступа" (``multi-access broadcast channel''). Часто в литературе термин "вызов" заменяют на "сообщение", а "обслуживание вызова" - на "передачу сообщения".

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

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

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

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

Теорема 4.1.

Симметричная система множественного доступа с двумя очередями стабильна, если выполняется одно из двух: и ; .

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

         Ясно, почему сформулированные в Теореме 4.1 условия являются только достаточными для стабильности. Предположим, что система насыщена, и нам удалось посчитать, какую часть времени в течение обе очереди непусты (скажем, эта доля равна ). Тогда "средняя" интенсивность обслуживания за время равняется

 ,

 .

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

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

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

        Самый простой вариант - когда вероятности от не зависят и равны одному и тому же числу . Но в этом случае справедлива

Теорема 4.2.

При любом выборе числа система без очередей нестабильна!

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

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

Теорема 4.3.

Если , то существует алгоритм, при котором система стабильна. Если , то таких алгоритмов нет.

Здесь - основание натуральных логарифмов и .

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

        Отметим, что . Как следует из Tеоремы 4.3, даже при оптимальном алгоритме сервер вынужден простаивать приблизительно 63 процента времени. Различными авторами рассматривались алгоритмы из более широкого класса (в частности, допускалась возможность вызову каждый раз при определении вероятности подачи сигнала учитывать, сколько раз он пытался подать сигнал до этого), что позволило поднять границу области стабильности с до .

     5.  Системы поллинга

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

         Рассмотрим систему поллинга с двумя очередями (системы с большим числом очередей рассматриваются аналогично). Вспомним описание системы с двумя типами вызовов (см. Пример 1 параграфа 3) и предположим, что вызовы каждого типа образуют свою очередь. Пусть сервер обходит очереди по некоторому циклическому правилу (например, правило {1,2,1,1,2} означает, что в течение каждого цикла сервер сначала посещает первую очередь, затем вторую, затем дважды первую и, наконец, вторую. На этом очередной цикл заканчивается и начинается следующий). Предположим, что за один цикл сервер посещает первую очередь раз, а вторую - раз. За каждый цикл сервер тратит на переходы из одной очереди в другую время (будем считать его неслучайным). Зададим два целых положительных числа и и определим следующее правило обслуживания: при каждом очередном посещении первой очереди, если сервер застает там вызовов, то он обслуживает из них (т.е. если , то обслуживается вызовов, иначе - вызовов). После этого сервер покидает эту очередь и переключается на следующую очередь из его маршрута. Аналогично, при приходе во вторую очередь он каждый раз обслуживает все находившиеся там вызовы, но не больше, чем .

        Предположим, что распределения случайных величин невырождены. Справедлива

Теорема 5.1.

Условие    (5.1) является необходимым и достаточным для стабильности системы поллинга с двумя очередями.

        В частности, если , то мы получаем первую часть утверждения Теоремы 3.2.

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

        За один цикл обслуживается вызовов первого типа (если такое число вызовов в системе есть). Поэтому для обслуживания всех вызовов первого типа потребуется приблизительно циклов (точнее, если эта дробь не является целым числом, то нужно взять ближайшее целое, большее ее). Аналогично, для обслуживания всех вызовов второго типа нужно приблизительно циклов. Следовательно, для обслуживания всех вызовов, пришедших во вспомогательную систему, требуется циклов. За эти циклов сервер потратит единиц времени на обслуживание вызовов первого типа и - второго. Так как в каждом цикле он тратит единиц времени на переключение, то циклов будут длиться время Решим приблизительно неравенство

  (5.2)

    Литература

1. Саати Т.Л. Элементы теории массового обслуживания. М.; Советское радио, 1971.

2. Боровков А.А. Вероятностные процессы в теории массового обслуживания. М.; Наука, 1972.

3. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания, 2-е изд. М.; Наука, 1987.

4. Цыбаков Б.С., Михайлов В.А. Случайный множественный доступ пакетов. Алгоритм дробления. // Проблемы передачи информации, 1980, Т. 16, вып. 4, с. 65-79.

5. Рыбко А.Н., Столяр А.Л. Об эргодичности случайных процессов, описывающих функционирование открытых сетей массового обслуживания.// Проблемы передачи информации, 1992, Т. 28, вып. 2, с. 3-26.

6. Malyshev V.A. Networks and dynamical systems.// Advances in Applied Probability, 1993, Vol. 25, p. 140-175.

7. Baccelli F., Foss S. On the saturation rule for the stability of queues. // Journal of Applied Probability, 1995, Vol. 32, p. 494-507.

Footnotes:

² Мы приведем один пример такой случайной величины (который потребуется в следующем параграфе) и посчитаем ее математическое ожидание. Рассмотрим последовательность независимых бросаний монеты, в каждом из которых герб выпадает с вероятностью , а решетка - с вероятностью . Будем считать, что . Пусть - случайная величина, означающая номер испытания, при котором герб выпадает в первый раз. Найдем вероятность при всех . Ясно, что . Далее, событие означает, что одновременно при первом бросании выпадает решетка и при втором - герб. И так как испытания независимы, то . Совершенно аналогично, при каждом событие означает, что при каждом из первых бросаний выпадает решетка, а при -ом бросании - герб. И из независимости испытаний следует, что . Значит, случайная величина принимает значение с вероятностью , значение с вероятностью и так далее. Из школьного курса вы знаете, что сумма геометрической прогрессии равна . Поэтому Так как случайная величина принимает лишь неотрицательные целые значения, то естественно определить ее среднее равенством , где сумма берется по всем натуральным . И так как то . Если, в частности, (монета симметрична), то равенство означает, что нам "в среднем" потребуется два бросания до выпадения герба. Если , то потребуется "в среднем" три бросания, и т.д.

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

⁴ На житейский язык термин "принцип инвариантности" можно перевести как "с чего бы мы ни начали, всегда придем к одному и тому же". Один из известнейших "принципов инвариантности" звучит так: "все дороги ведут в Рим".

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