Научная библиотека

1.6 Полумарковские однолинейные системы и методы их анализа

Как отмечалось в предыдущем разделе, процесс - число запросов в системе М\М\1 в момент t - является процессом гибели и размножения, то есть, частным случаем цепи Маркова с непрерывным временем. Аналогичный процесс для систем обслуживания типа M\G\1 с распределением времени обслуживания, отличным от показательного, и типа GI\M\1 с входящим потоком, отличным от простейшего, уже не является марковским.

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

Тем не менее, исследование процесса может быть сведено к исследованию марковских процессов. Первый способ «маркови-зации» - так называемый метод вложенных цепей Маркова - будет проиллюстрирован на примере системы M\G\1 в подпункте 6.1 и на примере системы GI\M\1 - в подпункте 6.2. Одна из разновидностей другого способа «марковизации» - метода введения дополнительной переменной - будет проиллюстрирована в подпункте 6.3. В подпункте 6.4 будет кратко описан и проиллюстрирован на примерах еще один мощный метод исследования СМО - метод введения дополнительного события.

1.6.1 Метод вложенных цепей Маркова в приложении для системы M\G\1

Рассмотрим однолинейную СМО с ожиданием, на вход которой поступает простейший поток интенсивности , а время обслуживания запроса имеет произвольное распределение с функцией распределения преобразованием Лапласа - Стилтьеса и конечными начальными моментами

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

Вместе с тем, очевидно, что если мы знаем состояние процесса в момент окончания обслуживания к запроса, то мы можем предсказать значение процесса в момент окончания обслуживания (k + 1)-го запроса, который произойдет через случайное время, и, имеющее распределение B(t). За это время может поступить случайное (распределенное по закону Пуассона с параметром ) число запросов и один запрос уйдет из системы.

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

Пусть - момент окончания обслуживания в системе M\G\1 k-го запроса. Процесс является однородной цепью Маркова с дискретным временем.

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

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

Итак, переходная вероятность определяется формулой:

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

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

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

где коэффициент загрузки равен

Уравнения равновесия (1.16) с учетом вида (1.37) матрицы вероятностей одношаговых переходов можно переписать здесь в виде:

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

Учитывая явный вид (1.35) вероятностей можно получить явное выражение для производящей функции

Умножая уравнения системы (1.39) на соответствующие степени 2 и суммируя их, получаем:

Меняя порядок суммирования, переписываем это соотношение в виде:

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

Учитывая (1.40), можно переписать формулу (1.41) в следующем виде:

Формула (1.42) определяет искомую производящую функцию стационарного распределения вероятностей вложенной цепи Маркова с точностью до значения неизвестной пока вероятности того, что рассматриваемая СМО пуста в произвольный момент окончания обслуживания запроса. Для нахождения этой вероятности вспомним, что система уравнений равновесия содержит еще уравнение (1.17) (условие нормировки). Из условия нормировки следует, что Поэтому для нахождения вероятности мы должны подставить в (1.42) z = 1. Однако, простая подстановка не дает результата поскольку и числитель, и знаменатель (1.42) обращаются в нуль.

Для раскрытия неопределенности можно использовать правило Лопиталя. Однако, при вычислении величины L среднего числа запросов в системе в моменты окончания обслуживания запросов потребуется вычислить величину П (1), для чего придется применять правило Лопиталя дважды, при вычислении дисперсии числа запросов в системе придется применять правило Лопиталя трижды и т.д. Во избежание многократного применения правила Лопиталя можно рекомендовать заранее разложить числитель и знаменатель дроби в правой части (1-42) в ряд Тэйлора по степеням (z — 1) (если мы заинтересованы в вычислении начального момента распределения числа запросов, то разложение нужно провести с точностью до ), сократить числитель и знаменатель на (z — 1) и только потом выполнять операции взятия производных и подстановки значения z = 1. Отметим, что если требуется вычислить моменты высокого порядка, при этом можно использовать возможности символьных вычислений, например, с помощью пакета «Mathematica».

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

(1.43)

Подставляя выражение (1.43) в формулу (1.42), получаем:

Формула (1.45) называется формулой Поллячека - Хинчина для производящей функции распределения числа запросов в системе M\G\1.

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

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

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

Из теории процессов марковского восстановления (см., например, [171]) следует, что это распределение существует при тех же условиях, что и вложенное распределение (то есть, при выполнении условия (1.38)), и вычисляется через вложенное распределение следующим образом:

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

Введем в рассмотрение производящую функцию

Умножая соотношения (1.46), (1.47) на соответствующие степени z и суммируя, получаем:

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

Делая замену переменной интегрирования учитывая равенство и связь между преобразованиями Лапласа и Лапласа-Стилтьеса, отсюда имеем:

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

В результате мы убедились в справедливости соотношения:

Таким образом, для рассматриваемой системы M\G\1 распределения вероятностей числа запросов в системе в моменты окончания обслуживания запросов и произвольные моменты времени совпадают. А.Я. Хинчин [118] назвал это утверждение основным законом стационарной очереди.

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

и

Условием существования пределов (1-49) является выполнение неравенства (1.38). Поскольку время пребывания запроса в системе равно сумме его времени ожидания и времени обслуживания, а время обслуживания запросов в классических моделях СМО предполагается независимым от состояния системы (и от времени, в течение которого запрос ожидал в очереди), то из свойства 2 преобразования Лапласа - Стилтьеса следует, что:

Популярным методом получения выражения для преобразований Лапласа - Стилтьеса является вывод интегро-дифференциального уравнения Такача для распределения виртуального времени ожидания (то есть, времени, в течение которого ждал бы начала обслуживания запрос, если бы он поступил в систему в данный момент времени), см., например, [67].

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

Умножая соотношения (1.51) на соответствующие степени z и суммируя, получаем:

Подставляя в это соотношение явный вид (1.45) производящей функции используя (1.50) и делая замену переменной: получаем следующую формулу:

Формула (1.52) называется формулой Поллячека - Хинчина для преобразования Лапласа - Стилтьеса распределения времени ожидания в системе M\G\1.

Используя формулу (1.18), из (1.52) получаем следующее выражение для величины среднего времени W ожидания запроса в системе:

Среднее время V пребывания запроса в системе находится как:

Сравнивая формулы (1.44) и (1.53), снова получаем формулу Литтла:

Если имеется настоятельная необходимость нахождения вида функции распределения времени ожидания W(x), а не ее преобразования Лапласа - Стилтьеса, обращение этого проебразования, заданного формулой (1.52), проводится разложением правой части (1.52) на простые дроби (если это возможно) или численными методами (см., например, [176], [261]). Полезной может оказаться также так называемая формула Бенеша:

где есть свертка порядка функции распределения

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