Обзор систем параллельной обработки заявок. Часть II

Полный текст

1. Введение Наряду с такими методами аппроксимации среднего времени отклика системы с расщеплением запросов, как эмпирический подход и интерполяция с помощью предельных значений загрузки системы [1], отдельного внимания заслуживают матрично-геометрический метод и анализ с помощью порядковых статистик, которому посвящена большая часть статьи, поскольку известные результаты теории порядковых статистик позволяют расширить ряд изучаемых распределений для входящего потока и времени обслуживания, а также оценить не менее важные характеристики для рассматриваемой системы: математическое ожидание и дисперсию времени синхронизации. Под временем синхронизации здесь фактически подразумевается её задержка, т.е. время между окончанием обслуживания первого и последнего подзапросов одного запроса [2]. Статья организована следующим образом: в разделе 2 описываются особенности и результаты применения матрично-геометрического метода к анализу системы с расщеплением запросов, в разделе 3 представлен подход к анализу среднего времени отклика, основанный на теории порядковых статистик, в заключении кратко подведены итоги работы. 2. Анализ с помощью матрично-геометрического метода Идея использования матрично-геометрического подхода при анализе fork-join систем в большинстве работ сводится к рассмотрению моделей, аппроксимирующих исходную, непосредственный анализ которых позволяет сделать вывод, что изучаемый процесс, описывающий поведение системы, является квазипроцессом «размножения и гибели» со всеми вытекающими из этого следствиями [3 - 5]. То же касается и fork-join системы с конечными очередями к серверам в условиях пуассоновского входящего потока и экспоненциальных времён обслуживания. Так, в [6, 7] был предложен алгоритм, позволяющий свести матрицу вероятностей переходов для марковского процесса, описывающего поведение системы, к блочно-диагональному виду, что даёт возможность компактно записать систему уравнений равновесия (СУР) и решить её одним из известных численных методов и, как следствие, вычислить среднее время отклика. Матрично-геометрический подход для оценки времени отклика fork-join системы используется в серии статей [8 - 10]. В первой работе [8] были предложены две модели, аппроксимирующие исходную fork-join систему с ветвями || 1 и различными интенсивностями обслуживания на разных серверах (приборах): 1) поступающий запрос принимается в систему тогда и только тогда, когда число подзапросов -го типа, находящихся в системе, меньше некоторого фиксированного положительного целого числа , в противном случае он теряется; 2) отказ в обслуживании на -м сервере происходит тогда и только тогда, когда нарушается условие: для некоторого и для фиксированных положительных целых чисел причём сервер блокируется до тех пор, пока подзапрос не закончит обслуживаться на сервере . Здесь вектор отражает состояние системы, - число подзапросов -го типа в системе, В результате анализа обеих систем с помощью матрично-геометрического метода удаётся определить стационарное распределение числа подзапросов в системах ( ⃗ ). Далее полученное распределение используется при алгоритмическом решении задачи нахождения функции распределения времени оклика: > 0. Таким образом, задача сводится к поиску условного распределения времени отклика при условии, что система находится в состоянии ⃗ . Для первой модифицированной модели искомое условное распределение может быть выражено с помощью распределения Эрланга, а во втором случае условное распределение получается при анализе процесса поглощения для подзапросов. Кроме того, авторы доказали, что решения, полученные при анализе этих двух систем, являются верхней и нижней границами для функции распределения времени отклика соответственно. В следующей статье авторов [9] изучается fork-join система с пуассоновским входящим потоком, но при этом время обслуживания на однородных серверах имеет распределение Кокса. Отметим, что для стационарных вероятностей состояний в СМО | | 1 известно точное решение [11]. Как и в предыдущей работе рассматриваются две аналогичные, аппроксимирующие исходную систему модели: 1) модель, в которой все очереди кроме очереди к первому серверу имеют конечную ёмкость; 2) модель, в которой вводится ограничение на то, что разница между каждой парой длин очередей к серверам не должна превышать заданный порог. Матрично-геометрический анализ указанных систем, предложенный в [12], благодаря тому, что матрицы вероятностей перехода сводятся к блочно-треугольному виду, позволяет получить стационарные вероятности, которые используются для вывода распределения времени отклика, а, соответственно, и моментов этого распределения. Полученные выражения являются верхними и нижними границами для моментов времени отклика. Следующая работа [10] продолжает начатые исследования. Авторы предлагают алгоритмический метод для вычисления верхних и нижних оценок производительности системы, который, по их мнению, может быть расширен для анализа систем с отличными от пуассоновского входящим потоком и отличным от экспоненциального временем обслуживания на разнородных серверах. Отметим, что матрично-геометрический метод (МГМ) использовался и при анализе систем, родственных fork-join. Так, МГМ был применён для анализа модели независимых серверов (ISM), в [13] с помощью МГМ анализируется split-merge система [I] с двумя ветвями с наложением ограничения на ёмкость накопителя одной из очередей. Были получены выражения для математического ожидания, дисперсии и функции распределения времени отклика. Также был разработан метод аппроксимации для систем с более чем с двумя ветвями. В работах [14, 15] также исследуется fork-join система, но уже с распределением фазового типа для входящего потока и с потерями. В статье [16] рассматривается ещё одна вариация классической fork-join системы, для анализа которой используется МГМ: обслуживание каждого подзапроса происходит в несколько этапов, включая фазу ожидания и фазу объединения родственных подзапросов; существует динамическая политика планирования нагрузки системы для поддержания эффективного использования сервера. 3. Анализ с помощью порядковых статистик Поскольку время отклика fork-join системы классически определяется как максимум, а в некоторых случаях и как минимум из случайных величин времён пребывания подзапросов в системе [17], то естественно, что одним из альтернативных способов оценки среднего времени отклика является использование теории порядковых статистик [18 - 20]. По определению [18 - 20], если - конечная выборка, определённая на некотором вероятностном пространстве , и далее, если перенумеровать последовательность в порядке неубывания таким образом, что, то такая последовательность будет называться вариационным рядом, а его члены - порядковыми статистиками. Случайная величина же () : называется -й порядковой статистикой исходной выборки. Из определения ясно, что . (1) Таким образом, время отклика в терминах теории порядковых статистик, где - положительные случайные величины времён пребывания подзапросов в системе до попадания в буфер синхронизации. Следовательно, математическое ожидание времени отклика можно вычислить, зная распределения экстремальных значений , причём функция распределения второй случайной величины фактически является совместной функцией распределения случайных величин . Обозначим через - функцию распределения, а через ( ) - плотность распределения случайной величины . Если сделать допущение о том, что - независимые, что в нашем случае, как уже говорилось выше, является упрощающим предположением, то: а -й момент случайной величины времени отклика можно определить, вычислив интеграл: Далее, если предположить, что серверы являются однородными, т.е. случайные величины не только независимы, но и одинаково распределены, а, следовательно, их функции и плотности распределения равны между собой: , то Также заметим, что математическое ожидание максимума н.о.р.с.в. можно представить в виде [21]: Для того чтобы проанализировать время отклика, необходимо вычислить указанные интегралы. В зависимости от типа распределения для оценки интегралов могут быть применены численные методы, однако для таких распределений, как экспоненциальное, гиперэкспоненциальное и распределение Эрланга 2-го порядка, распределение Кокса, результат может быть получен в символьном виде [21 - 23]. Вычислительные затраты увеличиваются с ростом ветвей ( ) и увеличением порядка для распределений Эрланга или Кокса. Для уменьшения вычислительных затрат при вычислении максимума может быть использован характеристический максимум [24]. 3.1. Экспоненциальное распределение Допустим, что времена пребывания подзапросов в подсистемах являются независимыми экспоненциально распределёнными случайными величинами с плотностями распределения Для того, чтобы определить моменты высшего порядка максимума независимых экспоненциальных случайных величин, эффективнее с вычислительной точки зрения может быть дифференцирование соответствующее число раз преобразования Лапласа- Стилтьеса (ПЛС) совместной функции распределения максимума по и в последующем приравнивание к нулю. В частности, для случая = 2 функция распределения, плотность распределения и ПЛС [25, 26] равны: Тогда математическое ожидаемое максимума равно [21, 23, 25, 26]: Общее выражение для ПЛС максимума экспоненциально распределённых случайных величин может быть записано в следующем виде [27] где обозначает сложение по модулю . Кроме того, ПЛС максимума независимых экспоненциально распределённых случайных величин с параметрами и плотностью распределения можно представить с помощью рекуррентной формулы [28]: где « / » означает исключение Тогда момент -го порядка максимума независимых экспоненциально распределённых случайных величин равен: Рассмотрим ещё одну важную характеристику производительности системы облачных вычислений - время синхронизации. Время синхронизации определяется как время между поступлением первого и последнего подзапросов одного запроса в буфер синхронизации, иными словами, это разность между максимумом и минимумом из времён пребывания подзапросов в системе: В теории порядковых статистик данная величина называется размахом [18 - 20]. Одни из первых результатов анализа этого показателя были приведены в работе [2], а именно численное решение оптимизационной задачи по минимизации среднего времени синхронизации. В статье [25] были представлены оценки математического ожидания в случае неоднородных приборов, а в случае однородных приборов получена оценка и для дисперсии времени синхронизации: Вычислить дисперсию исследуемой величины, для определения которой недостаточно знать значения дисперсий случайных величин ,max и ,min , можно и в неэкспоненциальном случае, действуя аналогичным образом, а именно пользуясь известными в теории порядковых статистик формулой для функции распределения размаха положительных н.о.р.с.в.: либо непосредственно формулой для вычисления дисперсии размаха выборки объёма н.о.р.с.в. с функцией распределения[18]: 3.2. Распределение Эрланга Формула для аппроксимации среднего времени отклика fork-join системы с распределением Эрланга -го порядка ( ), которое представляет собой сумму независимых случайных величин, распределённых по одному и тому же экспоненциальному закону с параметром для времени пребывания в -й ветви системы, с функцией и плотностью распределения: 3.3. Распределение экстремальных значений Ещё один метод вычисления максимума н.о.р.с.в. - это его аппроксимация распределением экстремальных значений [30]. Распределение экстремальных значений представляет собой предельное распределение наибольшего () (наименьшего (1) ) из значений н.о.р. непрерывных с.в. при бесконечном увеличении их числа → ∞ , т.е., говоря иными словами, это предельное распределение наибольшего (наименьшего) выборочного значения при бесконечном увеличении объёма выборки из непрерывного распределения [30], хотя, конечно, нельзя сказать, что распределение экстремального значения - это распределение () при → ∞ , поскольку фактически оно будет вырожденным, поэтому, чтобы получить невырожденное предельное распределение, рассматривают линейное преобразование () с коэффициентами, зависящими от объёма выборки, что в действительности аналогично нормировке, но по большому счету не исчерпывается только последовательностями линейных преобразований [30]. Существует три типа семейств экстремальных распределений [30]: 1) тип I - распределение типа Гумбеля, которое ещё иногда называют дважды экспоненциальным 2) тип II - распределение типа Фреше: 3) тип III - распределение типа Вейбулла где 0 - параметры. Распределения типа II и III приводятся к распределению типа I с помощью преобразований , соответственно, поэтому в основном акцент делается на распределении типа Гумбеля, плотность распределения которого имеет вид: а математическое ожидание и дисперсия равны: где , 577721 - это постоянная Эйлера-Маскерони. При получается стандартная форма распределения типа I - распределение Гумбеля: В [30] упоминается об установленной связи между свойствами генерального распределения ( ) и типом предельного распределения. Полученные условия, которым, вообще говоря, удовлетворяют далеко не все распределения (например, распределения с «тяжёлыми хвостами»), являются необходимыми и достаточными для сходимости к одному из трёх типов семейств экстремальных значений и касаются поведения ( ) при больших (малых) значениях , если речь идёт о наибольших (наименьших) значениях случайных величин. Причём при одном и том же исходном распределении наибольшее и наименьшее значения могут иметь предельные распределения, относящиеся к разным типам. К распределениям, которые удовлетворяют условию сходимости к типу I можно отнести нормальное, экспоненциальное и логистическое, к типу II - распределение Коши, а к типу III - распределения, сосредоточенные на ограниченной сверху части числовой оси [30]. Так, в [20] было показано, что распределение максимального значения () в выборке из случайных величин с экспоненциальным распределением с параметром = 1 приближается к распределению Гумбеля в его стандартной форме с ростом объёма выборки, т.е. где - это случайная величина с распределением Гумбеля с функцией распределения из (8), математическим ожиданием и дисперсией Отметим, что для случая, когда каждая порядковая статистика имеет стандартное распределение экстремальных значений типа I из (8), математическое ожидание максимума вычисляется по формуле [30]: . 3.4. Произвольное распределение Рассмотрим обобщение вывода в [28] для аппроксимации моментов максимума случайных величин с произвольным распределением [4]. Рассмотрим случайную величину , - неотрицательные и независимые с функциями распределения - это ПЛС этих функций распределения, Тогда математическое ожидание можно выразить следующим образом: Пусть- первые два момента случайной величины - случайной величины 2 . Тогда, если 1 - экспоненциальная, то Далее окончательно получаем следующую аппроксимацию: которая фактически является точным результатом для случая, когда обе случайные величины 1 и 2 имеют экспоненциальное распределение. Таким образом, в общем случае, когда речь идёт о случайных величинах, необходимо аппроксимировать ПЛС функции распределения максимума ( - 1) случайных величин. Поэтому допустим, что уравнение (4) применимо не только к экспоненциальным случайным величинам. Обозначим среднее значение максимума случайных величин с математическими ожиданиями и вторыми моментами. Тогда можно выразить рекуррентно Результаты моделирования для оценки точности приближения приведены в [28], а также в [31] с использованием уравнения из (2). Рассматриваются следующие распределения: распределение Эрланга 2-го, 3-го и 4-го порядков и распределение Парето с функцией распределения вида Условие > 2 необходимо для того, чтобы первые два момента были конечными, так что . Погрешность аппроксимации выражений (9) и (2) мала и для 2 , но быстро увеличивается начиная с . Интересно, что оба уравнения дают точные результаты для распределения Парето, а последнее уравнение даёт более точные результаты в обоих случаях. 3.5. Аппроксимация на основе границ моментов порядковых статистик Если математическое ожидание и дисперсию генерального распределения обозначить и 2 соответственно, то справедливо [18, 19]: Поэтому в [18, 19] для максимума н.о.р.с.в. () была предложена аппроксимация следующего вида: Заметим, для экспоненциального распределения справедливо, что а для равномерного распределения выполняется: [27]. Если же математическое ожидание равно нулю, а стандартное квадратическое отклонение равно единице, то, очевидно, Знак равенства в выражении (11) имеет место для н.о.р.с.в. с функцией и плотностью распределения Для аппроксимации ожидаемого значения максимума н.о.р.с.в. с нормальным распределением в работе [32] используется в формуле (10), т.е.: Более точная аппроксимация дана в [30]: Стоит отметить, что в уравнении (12) существует некоторый сдвиг (смещение), который корректируется путём вычитания 0 , из выражения в скобках в (12) [33]. Таким образом, имеем: На основе формулы (10) в [34] для случайной величины времени отклика было представлено приближение где max обозначают математическое ожидание и среднее квадратическое отклонение времени отклика СМО || 1 с коэффициентом загрузки системы . Напомним, что если времена обслуживания подзапросов распределены по произвольному закону [4], то математическое ожидание максимума н.о.р.с.в. с функцией распределения ( ). Легко показать, что для экспоненциального распределения , а для распределения экстремальных значений [30]. Сравнительный анализ полученного приближения и результатов имитационного моделирования при заданном распределении времени отклика может быть использован для получения выражения [34]: Так, например, для fork-join системы с двумя ветвями || 1 из выражения (6) следует, что Заключение В статье рассмотрены подходы к приближенному анализу времени отклика: матрично-геометрический метод, анализ с помощью порядковых статистик для различных типов распределения времени пребывания подзапросов в системе. Также приводятся результаты для математического ожидания и дисперсии времени синхронизации. Стоит отметить, что существуют исследования, посвящённые анализу работы сетей массового обслуживания, в качестве узла или узлов которой выступает система с расщеплением, но обзор подобных работ выходит за рамки поставленной перед авторами задачи.

Об авторах

А В Горбунова

Российский университет дружбы народов

Автор, ответственный за переписку.
Email: gorbunova_av@rudn.university

Горбунова Анастасия Владимировна - кандидат физико математических наук, ассистент кафедры прикладной информатики и теории вероятностей РУДН

ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

И С Зарядов

Российский университет дружбы народов; Институт проблем информатики Федеральный исследовательский центр «Информатика и управление» РАН

Email: zaryadov_is@rudn.university

Зарядов Иван Сергеевич - кандидат физико математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН, старший научный сотрудник ИПИ ФИЦ ИУ РАН

ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198; ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

К Е Самуйлов

Российский университет дружбы народов

Email: samuylov_ke@rudn.university

Самуйлов Константин Евгеньевич - профессор, доктор технических наук, заведующий кафедрой прикладной информатики и теории вероятностей РУДН

ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

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