Система обслуживания с делением и слиянием требований,в которой требование занимает все свободныеобслуживающие приборы

Полный текст

1. Введение Реальные системы, в которых имеет место параллельная обработка [1] (многопроцессорные системы, GRID-системы, распределённые базы данных), получают все большее распространение. В таких системах поступающие для обработки задачи делятся на более простые для выполнения подзадачи, которые распределяются по системе, занимая выделенные для них ресурсы. После завершения своего выполнения подзадачи освобождают выделенные им ресурсы, однако исходная задача будет считаться выполненной только после выполнения всех её подзадач. Для анализа производительности указанных выше систем используются модели теории массового обслуживания, такие как [2]: с центральным делением без синхронизирующей очереди (centralized splitting model without synchronization queue, split-merge model), с центральным делением и синхронизирующей очередью (centralized splitting model with synchronization queue), с распределённым делением и синхронизирующей очередью (distributed splitting model with synchronization queue), которые обычно относят к классу систем массового обслуживания с делением и слиянием требований (fork-join queueing systems) [3 - 8], а также такие родственные модели как, например, модель независимых приборов (independent server model) [9, 10], модель командного обслуживания (team service model) [11]. Общим во всех перечисленных моделях является деление поступающих требований на части - фрагменты, которые обслуживаются параллельно на приборах системы, и последующее объединение обслуженных фрагментов в исходные требования. Требование считается обслуженным и покидает систему только после окончания обслуживания всех его фрагментов. Распределение фрагментов поступающих требований по приборам системы с делением и слиянием требований, как и число фрагментов, получаемых при делении одного требования, задаётся некоторой детерминированной или вероятностной [12, 13] стратегией. Так, в работах [3, 4, 6 - 8] требования каждый раз делятся на одинаковое число фрагментов, по одному фрагменту для каждого обслуживающего прибора системы. С другой стороны, в [12] рассматривалась модель, в которой каждое требование может быть поделено на случайное число фрагментов, которые поступают на обслуживающие приборы в соответствии с некоторым распределением вероятностей. Обзор всех основных теоретических и прикладных результатов связанных с моделями данного класса можно найти в [14, 15]. В статье рассматривается многоприборная система массового обслуживания с очередью бесконечной вместимости и пуассоновским входящим потоком. Основным отличием от известных работ является то, что деление требования в момент начала обслуживания на фрагменты происходит так, что они занимают все свободные обслуживающие приборы, то есть число фрагментов, получаемых при делении одного требования, зависит от состояния системы обслуживания, а длительность обслуживания фрагмента зависит от его величины. Фрагменты обслуживаются независимо друг от друга. Фрагмент, обслуживание которого завершено, освобождает обслуживающий его прибор. Требование будет считаться обслуженным только после того, как будет завершено обслуживание всех его фрагментов, сразу после чего фрагменты требования объединяются, а полученное исходное требование покидает систему обслуживания. Также отметим, что во многих работах [4, 7, 12, 13] рассматривается случай идентичных обслуживающих приборов, в представленной же системе обслуживания приборы имеют различные интенсивности обслуживания. Статья организована следующим образом. В разделе 2 подробно описывается изучаемая система массового обслуживания. Стационарное распределение состояний системы обслуживания, а также выражения для основных стационарных характеристик приводятся в разделах 3 и 4 соответственно. Раздел 5 содержит численные результаты анализа системы обслуживания. 2. Описание системы обслуживания Рассматривается система обслуживания, состоящая из обслуживающих приборов и очереди бесконечной вместимости с дисциплиной обслуживания FCFS. В систему обслуживания поступает пуассоновский поток требований с интенсивностью Λ. Обозначим через класс требования и положим, что для всех требований, поступающих из источника, = 1. Требование, поступающее на обслуживание, делится на фрагменты так, что они занимают все свободные в данный момент времени обслуживающие приборы: если имеется 1 6 6 свободных приборов, то поступающее требование разделяется на идентичных фрагментов с классом = . Каждый из фрагментов мгновенно занимает свободный прибор и начинает обслуживаться. То есть деление требования на > 1 фрагментов происходит в том случае, когда в момент поступления этого требования очередь системы была пуста, при этом имелось более одного свободного прибора. В других случаях требование не делится, однако для удобства будем называть и такое требование фрагментом. Длительность обслуживания любого фрагмента с классом на приборе есть экспоненциально распределённая случайная величина с параметром , здесь - интенсивность обслуживания фрагмента (требования) класса = 1. Фрагмент, обслуживание которого завершено, освобождает обслуживающий его прибор. Требование будет считаться обслуженным только после того, как будет завершено обслуживание всех его фрагментов. Сразу после этого фрагменты требования мгновенно объединяются в исходное требование, которое покидает систему обслуживания. 3. Стационарное распределение системы обслуживания Состояние системы обслуживания определим как вектор где 0 - число требований в очереди, где Очевидно, что мерный процесс есть цепь Маркова с непрерывным временем, определённая на пространстве состояний , Обозначим через интенсивность перехода цепи из состояния в состояние Справедливо число свободных приборов при нахождении системы обслуживания в состоянии ; 4. если Упорядочим состояния цепи Маркова в лексикографическом порядке. Под макросостоянием с номером , будем понимать множество состояний , определяемое как Мощности множеств равны соответственно. Заметим, что из (1) и (2) следует возможность перехода из макросостояния только в макросостояния интенсивности этих переходов не зависят от . Цепь Маркова является квазипроцессом размножения и гибели [16], а инфинитезимальный оператор цепи имеет блочнодиагональный вид: Матрицы имеют размерность соответственно. Матрицы суть квадратные матрицы порядка . Выражения (2) полностью определяют элементы матриц 0 и 10 . Отметим, что 2 = Λ I , где I - единичная матрица; 1 - диагональная матрица, 1 = -diag где diag ( ) задаёт диагональную матрицу с вектором на главной диагонали, 1 - единичный вектор-столбец. Матрицы 00 , 01 определяются выражениями (3) , (4) , (5) . Для вычисления стационарного распределения воспользуемся аппаратом матрично аналитических решений [17], а именно матрично геометрическим методом. Здесь есть вектор-строка, каждая компонента которого задаёт вероятность нахождения системы обслуживания в некотором состоянии из макросостояния в соответствии с введённым лексикографическим порядком. Будем использовать следующие обозначения: - стационарная вероятность нахождения системы в состоянии - стационарная вероятность нахождения системы в макросостоянии Для системы обслуживания стационарный режим будет существовать тогда и только тогда, когда выполнено условие где - коэффициент использования системы обслуживания. Известно [16, 17], что при выполнении условия (6) стационарное распределение имеет вид где есть решение уравнения векторы 0 и 1 находятся как решение уравнения с условием нормировки Вычисление стационарных характеристик Используя стационарное распределение , определим математическое ожидание ¯ числа требований в очереди системы обслуживания и математическое ожидание длительности пребывания требований в очереди, Одной из основных характеристик, представляющих интерес в системах данного класса, является длительность времени пребывания требования [4, 6, 7] в системе обслуживания, которая определяется как длительность интервала времени от поступления требования в систему до возвращения требования в источник. Под длительностью обслуживания требования в системе обслуживания будем понимать максимум из длительностей интервалов времени, затраченных на обслуживание приборами всех фрагментов этого требования. Обозначим через математическое ожидание длительности обслуживания требований в системе обслуживания, тогда математическое ожидание длительности времени пребывания требований в системе обслуживания = + . Рассмотрим два случая для поступающего из источника требования. 1. Требование застаёт все приборы системы обслуживания занятыми и встаёт в очередь. Тогда длительность обслуживания требования есть случайная величина с экспоненциальным распределением. 2. Требование застаёт в системе обслуживания > 0 свободных обслуживающих приборов. В этом случае длительность обслуживания требования есть максимум из независимых случайных величин с экспоненциальными распределениями. Пусть система обслуживания находится в состоянии тогда вероятность завершения обслуживания фрагмента на приборе определяется как м.о. длительности обслуживания для требования, занявшего освободившийся прибор, определяется выражением Будем рассматривать систему обслуживания при условии, что в очереди есть требования, тогда множество определяет множество состояний обслуживающих приборов. При данном предположении вероятность является вероятностью перехода из состояния в состояние обусловленного завершением обслуживания некоторого фрагмента на приборе . Случайный процесс, вложенный по моментам ухода фрагментов, является цепью Маркова с дискретным временем и множеством состояний * . Пусть состояния в * упорядочены в лексикографическом порядке, а задаёт матрицу переходов для цепи Маркова Предположим, что требование поступает в систему, когда в очереди находится > 0 требований. Рассмотрим эволюцию цепи Маркова, описывающей переходы между состояниями приборов. В этом случае задаёт вероятность нахождения приборов в состоянии при условии нахождения в очереди требований. Вектор будет являться вектором начального распределения для рассматриваемого процесса. Через завершений обслуживания поступившее в систему обслуживания требование будет первым в очереди на обслуживание, следовательно, математическое ожидание длительности обслуживания требования, заставшего требований в очереди, определяется как где есть вектор-столбец, составленный из элементов множества в соответствии с введённым лексикографическим порядком на множестве Рассмотрим теперь случай, когда поступающее в систему обслуживания требование не застаёт в очереди требований. Если все обслуживание приборы заняты, то математическое ожидание длительности обслуживания определяется аналогично предыдущему случаю. Пусть требование застаёт некоторые обслуживающие приборы свободными; обозначим через ( ) множество номеров свободных приборов для состояния Положим для некоторого тогда требование разделится на 0 фрагментов, длительность обслуживания этого требования будет максимумом из независимых экспоненциально распределённых случайных величин. Таким образом, для требований, которые застают очередь системы пустой, математическое ожидание 0 длительности обслуживания требования определяется как здесь E обозначает оператор математического ожидания, exp() - случайная величина с экспоненциальным распределением с параметром . Обсуждение нахождения распределения максимума случайных величин можно найти, например, в [16, 18]. Тогда для математического ожидания длительности обслуживания требований справедливо Матрица есть решение уравнения (8) , которое может быть переписано в привычном для уравнения Сильвестра [19, 20] виде (9) Из (7) после преобразований получаем Математическое ожидание числа требований в системе . 5. Пример На основании полученных выражений рассмотрим изменение математического ожидания длительности пребывания требований в системе обслуживания в зависимости от числа обслуживающих приборов и интенсивности входящего потока. Предполагается, что коэффициент использования меняется в следующих границах: Графики зависимости представлены на рис. 1. Отметим, что полученные с использованием выражений численные результаты были подтверждены также результатами имитационного моделирования. Рис. 1. Зависимость математического ожидания длительности пребывания требований в системе обслуживания Отметим, что когда коэффициент использования приближается к единице, рассматриваемая система ведёт себя аналогично системе с обслуживающими приборами без деления требований, тогда в случае, когда все обслуживающие приборы имеют одинаковую интенсивность обслуживания , математическое ожидание длительности времени пребывания требований в системе может быть приближённо найдено как Сравнение результатов для случая, когда = 4, = 1, приведено в табл. 1. Таблица 1 Математическое ожидание длительности пребывания требований в системе для двух различных моделей с делением требований 0,5714 0,6821 0,8324 1,1540 1,5604 2,8001 5,2955 без деления требований 1,0002 1,0132 1,0870 1,3572 1,7455 2,9694 5,4571 Видно, что во всех случаях система без деления требований на фрагменты имеет большее математическое ожидание длительности пребывания требований в системе, то есть может быть использована для нахождения верхней границы для . 6. Заключение В статье рассмотрена многоприборная система массового обслуживания с очередью бесконечной вместимости, в которой требование делится на фрагменты так, что они занимают все свободные обслуживающие приборы. С использованием матрично-геометрического метода получено стационарное распределение вероятностей состояний системы, а также точные выражения для основных стационарных характеристик системы (математическое ожидание длительности пребывания требований в системе обслуживания, математическое ожидание длительности пребывания требований в очереди и т.д.). В качестве направления дальнейших исследований могут быть рассмотрены различные дисциплины разделения требований, например, с ограничением на максимальное число фрагментов, порождаемых одним требованием.

Об авторах

О А Осипов

Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского

Автор, ответственный за переписку.
Email: oleg.alex.osipov@gmail.com

Осипов Олег Александрович - ассистент кафедры системного анализа и автоматического управления СГУ

ул. Астраханская, д. 83, г. Саратов, Россия, 410012

Список литературы