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

Полный текст

1. Введение Название исследуемой системы с параллельной обработкой запросов или с расщеплением запросов не имеет утвердившегося в русском языке терминологического аналога, в англоязычной же литературе используется термин «fork-join queueing system» [1-3]. Интерес к указанной системе объясняется тем, что она является естественной моделью для многих других реальных систем. В качестве примеров можно привести сферу обслуживания, медицинские приложения, производственные системы, системы облачных вычислений и др. [4]. Если же говорить об информационных технологиях, то прежде всего стоит упомянуть распределённые вычисления, технология которых оказала значительное влияние и на концепцию облачных вычислений, а также параллельные вычисления, например обработку пакетов данных, телефонных вызовов и др. Однако, несмотря на широкий спектр задач, которые решаются с помощью систем массового обслуживания с параллельной обработкой запросов, и их популярность среди зарубежных авторов, в нашей стране данная система исследовалась значительно меньше [4-9]. Статья организована следующим образом: в разделе 2 описываются особенности построения системы с расщеплением запросов и родственных ей систем, в разделе 3 подробно описан метод точного анализа среднего времени отклика для случая расщепления на два подзапроса, в разделе 4 представлены два метода аппроксимации среднего времени отклика, в заключении кратко подведены итоги и анонсировано содержание второй части работы. 2. Системы параллельного обслуживания заявок Общая идея функционирования системы fork-join (рис. 1) заключается в следующем: на вход поступает поток заявок (запросов) в момент поступления в точке «расщепления» (англ. fork point) заявка разделяется на родственных заявок (подзапросов): каждая из которых отправляется в очередь на обслуживание к приборам или серверам с номерами 1, 2, . . . , соответственно. Предполагается, что запросы имеют одну и ту же структуру и каждый сервер предназначен для выполнения конкретных задач: подзапрос может обслуживаться только на -м сервере, Обработанные подзапросы попадают в буфер синхронизации, где дожидаются родственных им подзапросов. В момент поступления последнего родственного подзапроса одного из запросов происходит их синхронизация, т.е. объединение, после чего обработанный запрос покидает систему. Здесь и далее будем считать,что синхронизация происходит мгновенно. Рис. 1. Система массового обслуживания типа fork-join Стоит отметить, что описанную модель рассматривают и как сеть массового обслуживания (СеМО): после расщепления подзапросы одновременно поступают на вход ветвей, которые представляют собой одноканальные системы массового обслуживания (СМО) с очередями. Однако данный подход предполагает дальнейший переход к рассмотрению независимых СМО, что является упрощающим допущением в силу существующей зависимости между очередями подзапросов вследствие общих моментов поступления. Тем не менее таких сложностей не возникает для случая, когда каждая подсистема состоит из бесконечного числа приборов [6, 7]. Анализ SPM (splitting and matching queueing system) системы массового обслуживания в [10] является одной из самых ранних работ на эту тему. В ней рассматриваются авиапассажиры и их багаж, которые прибывают вместе на самолёте в аэропорт, но разделены до тех пор, пока пассажиры не получат свои вещи в зоне выдачи багажа. В этой статье анализируется система с двумя ветвями ||1, т.е. с детерминированным входящим потоком и экспоненциальным временем обслуживания на каждом из серверов. SM (split-merge queueing system) система является одним из вариантов fork-join системы массового обслуживания (рис. 2). Её отличие заключается в том, что на свободные серверы не поступит ни один подзапрос следующего запроса до того момента, пока не обслужатся все подзапросы текущего запроса [11], т.е. происходит блокировка каждого освободившегося сервера до окончания обработки всех задач запроса. Рис. 2. Система массового обслуживания типа split-merge FF (fission-fusion queueing system) система - это ещё одна разновидность forkjoin системы (рис. 3). Если допустить, что все подзапросы являются идентичными и неразличимыми: , то запрос может покинуть систему после обработки любых подзапросов, иначе говоря, подзапросы могут принадлежать разным запросам [11]. Рис. 3. Система массового обслуживания типа fission-fusion Модель независимых серверов (independent server model, ISM) представляет собой многоканальную систему массового обслуживания. Для обслуживания поступившего запроса требуется случайное число серверов, не превышающее их общее количество, причём обслуживание очередного запроса не может начаться до тех пор, пока число свободных серверов не станет по крайней мере равно числу серверов, требуемых для обслуживания. В частности, в работе [12] рассматриваемая система состоит из однородных серверов, времена обслуживания являются независимыми и имеют экспоненциальное распределение. Входящий поток является пуассоновским, а число серверов, требуемых для обработки запроса, определяется некоторой вероятностью. Запросы обслуживаются в порядке поступления (First Come First Served, FCFS) и могут покинуть систему только после освобождения всех затребованных серверов. Поскольку времена обслуживания на отдельных серверах являются независимыми, то сервер, закончивший обслуживание запроса, становится доступным для других задач. Таким образом, время обслуживания запроса является максимумом случайного числа экспоненциально распределённых случайных величин. Для модели были получены такие характеристики, как распределение времени обслуживания, распределение числа занятых серверов, а также достаточные условия для существования стационарного распределения. В случае модели группового обслуживания (team service model, TSM), так же как и в случае ISM системы, для обработки задач требуется наличие нескольких свободных серверов одновременно, но при этом серверы начинают обслуживание этих задач и освобождаются одновременно [13, 14]. Также существует такой вариант fork-join системы, когда поступающие на вход в систему несколько потоков запросов делятся на подзапросы и отправляются на обслуживание на серверы в соответствии с заданной матрицей вероятностей, т.е. запросы поступают как независимых потоков, затем делятся на части, которые распределяются по серверам в соответствии с некоторой стратегией (политикой), которая и определяется матрицей [15, 16]. Первые результаты исследования fork-join системы массового обслуживания были получены для случая расщепления заявки на два подзапроса 1 , 2 с пуассоновским входящим потоком и экспоненциальным временем обслуживания на обоих серверах [17]. Однако несмотря на марковость предположений анализ fork-join систем массового обслуживания даже для случая = 2 затруднителен по следующим причинам: процессы поступления подзапросов на серверы коррелируют; модель описывается двумерной цепью Маркова с бесконечным числом состояний для каждой размерности. В силу указанных выше факторов точного решения для распределения числа подзапросов в fork-join системе не было найдено. Но при этом для случая пуассоновского входящего потока и экспоненциальных времён обслуживания можно получить явные выражения для маргинальных вероятностей [4]. Приближенное же решение для распределения числа подзапросов в случае очередей неограниченных размеров может быть получено для достаточно большой ёмкости накопителя - такой, что вероятность потери запросов в связи с этой большой ёмкостью будет пренебрежимо мала, и в данном случае будут применимы итерационные численные методы решения систем линейных уравнений большой размерности [18]. Большинство авторов в своих работах исследуют один из основных показателей качества функционирования подобных систем массового обслуживания - время отклика где - случайная величина времени пребывания подзапроса в системе до его попадания в буфер синхронизации, Стоит сразу отметить, что точное выражение для среднего времени отклика было получено только для fork-join системы с двумя ветвями в [1] с помощью результатов работы [17]. Для случая > 2 с помощью различных методов были получены аппроксимации среднего времени отклика. 3. Анализ системы с двумя ветвями M|M|1 Модель цепи Маркова с непрерывным временем для fork-join системы с двумя ветвями ||1 и накопителем неограниченной ёмкости рассматривается в [17]. Этот анализ был расширен для ветвей в [19]. Для изучения стационарного и нестационарного режимов основной краевой задачи (дифференциальное уравнение вместе с набором дополнительных ограничений) в работе [19] использовались методы исследования функций комплексной переменной, представленные, например, в [20]. В ходе последующего обсуждения более подробно остановимся на анализе статьи [17], поскольку она ведёт к точному решению задачи для fork-join системы с двумя ветвями | |1. Итак, рассмотрим fork-join систему, попадая в которую запрос расщепляется на = 2 подзапроса, входящий поток является пуассоновским с интенсивностью = 1, а интенсивности обслуживания на двух серверах удовлетворяют условию: 1 < 1 6 2 , гарантируя, что со временем система не переполнится, т.е. число подзапросов не устремится к бесконечности. Поведение системы описывается непрерывным марковским процессом - число подзапросов -го типа, соответственно Указанные состояния интерпретируются следующим образом: если 0} в некоторый момент времени , то в системе находится заявок 1-го типа, т.е. 1 , и заявок 2-го типа, т.е. - стационарная вероятность указанного состояния. Далее записывается система уравнений равновесия в терминах двойной производящей функции [17, 21, 22]: Анализ производящей функции позволяет получить выражения для , которые для симметричного случаяравны между собой: Также с помощью преобразований производящей функции в граничных точках: в [17] были получены асимптотические выражения для стационарных вероятностей состояний соответственно. Это ещё раз свидетельствует о том, что данная задача требует более совершенных математических методов решения. Используя результаты анализа в [17], среднее время отклика для fork-join системы с двумя симметричными ветвями выводится в Приложении B в [1]. Интенсивность пуассоновского входящего потока имеет значение , интенсивности обслуживания на двух серверах раны , т.е. 1 = 2 = , причём < , так, что нагрузка на каждый из серверов = / меньше единицы: Вывод [ 2,max ] основан на наблюдении, что эта величина есть сумма времени пребывания в системе ||1, т.е. 1,max , и времени, проведённого подзапросом в системе после обслуживания на сервере в ожидании второго, и до ухода из неё (время синхронизации) : [ 2,max ] = [ 1,max ] + []. Согласно формуле Литтла, = 2[], где - это среднее число подзапросов, которые обслужились на приборе и ждут свою пару [22-24]. Через обозначим вероятность того, что число подзапросов во второй очереди превышает число подзапросов в первой очереди на . Благодаря симметрии = - , > 1 и, таким образом, Из уравнений, представленных в [1], можно получить: Тогда = +1 + ,0 , где ,0 - это вероятность того, что в первой очереди находится подзапросов, а во второй - ноль. Далее с учётом формулы (1) можем записать: Затем подставляем в формулу для времени синхронизации выражение для из (2) и меняем порядок суммирования: Потом вычисляем значения первой и второй производной при = 1 от выражения для производящей функции (, 0), полученном в (3) и от выражения, которое записывается исходя из определения этой функции: Теперь можем подставить полученные формулы в (4): следовательно, среднее время отклика определяется следующим выражением: 4. Аппроксимация времени отклика 4.1. Эмпирическая формула аппроксимации Один из способов аппроксимации времени отклика для fork-join системы с ветвями ||1 и одинаковыми интенсивностями обслуживания на серверах был предложен в [1]. Идея предложенного метода аппроксимации появилась из наблюдения за поведением времени отклика при проведении численных экспериментов. Верхнюю границу для среднего времени отклика можно получить, сделав допущение о независимости случайных величин времён пребывания подзапросов в системе, или, что тоже самое, рассмотреть СеМО, состоящую из независимых параллельно функционирующих систем | |1. Данное предположение подтверждается приведённым в [1] доказательством того факта, что случайные величины времён пребывания подзапросов в системе являются положительно ассоциированными. По определению [25] две случайные величины и являются положительно ассоциированными, если [ ()()] > [ ()][()], т.е. ковариация любых пар неубывающих функций и является неотрицательной, а одно из свойств положительно ассоциированных случайных величин 1 , 2 , . . . заключается в том, что [25] Нижняя граница для среднего времени отклика получается, если «пренебречь» очередями (т.е. для значений близких к нулю): в этом случае время отклика будет являться максимумом независимых одинаково распределённых случайных величин (н.о.р.с.в.) со средним 1/. Таким образом, имеем: то частичная сумма гармонического ряда. Верхняя и нижняя границы растут с одной и той же скоростью , иными словами, для больших значений границы имеют порядок (ln ). Поэтому, зная значение [ 2,max ] , можем записать: [ ,max ] ≈ () [ 2,max ] , где () - это коэффициент масштабирования, растущий со скоростью (ln ). Следовательно, аппроксимация времени отклика может быть представлена в следующем виде: = ()+() . Поскольку по определению 2 () = 1, то, подставив это значение в предыдущее выражение, получим, что () = (1 - ())/ 2 , таким образом, Посредством имитационного моделирования в [1] определяется значение () ≈ 4/11. Окончательно имеем Полученное приближение, исходя из численного анализа, проведённого авторами, имеет погрешность аппроксимации, не превышающую 5% для значений 2 6 6 32. В статье [26] исследуется аналогичная fork-join система с ветвями ||1. Полученная аппроксимация является средним арифметическим верхней и нижней оценок. В качестве верхней оценки используется видоизменённое выражение для верхней оценки из вышеупомянутой работы [1]. Нижняя оценка получается при анализе эквивалентной величины времени отклика, но для системы с непараллельной организацией очереди [27]. Итак, Далее вычисляется среднее арифметическое полученных оценок, в результате чего имеем: 4.2. Интерполяция с помощью предельных значений загрузки системы В [28] предложен другой метод аппроксимации времени отклика - комбинация методов интерполяции высокой и слабой входных нагрузок (heavy and light traffic interpolation approximations). Указанные техники в отличие от описанного выше метода не используют результаты имитационного моделирования, однако их применение может быть расширено и до анализа fork-join систем не только с экспоненциальным временем обслуживания или c пуассоновским входящим потоком. Для рассматриваемой задачи найти решение в аналитическом виде очень затруднительно, однако возможно получить асимптотические формулы для искомых характеристик. Интерполяция слабой загрузкой системы является результатом её работы в режиме слабой нагрузки, т.е. когда интенсивность входящего потока очень мала. В этом случае целесообразно обратиться к разложению в ряд Тэйлора характеристик производительности системы (в частности, функции распределения времени отклика - как функции от - в окрестности нуля), с помощью которого можно определить неизвестные величины в представлении исследуемой функции в виде полинома от порядка . Рассматриваются только полиномы нулевой и первой степени. Если же говорить об интерполяции с помощью высокой загрузки, то для fork-join системы речь идёт об анализе такого режима, в котором значение очень близко к значению . Ключевым параметром при интерполяции с помощью метода высокой нагрузки является параметр , два крайних значения которого интерпретируются как два предельных случая: если = 0, то это означает, что входящий поток является детерминированным, если = 1, то время обслуживания - детерминированное, а ветви fork-join системы являются независимыми ||1 и ||1 СМО, соответственно. Таким образом, благодаря исследованию поведения функции времени отклика в граничных значениях загрузки системы удаётся, в отличие от метода, описанного в [1], не прибегая к численным экспериментам для определения констант в интерполяционной формуле, определить их точные выражения в замкнутой форме. Для случая fork-join системы с ветвями | |1 аппроксимация времени отклика имеет вид: В случае распределения Эрланга второго порядка для входящего потока с функцией распределения и для времени обслуживания с функцией распределения Также в работе [28] для того, чтобы получить оценку среднего времени отклика в случаях с другими распределениями для входящего потока и времени обслуживания, метод интерполяции высокой нагрузки был модифицирован, и анализировались три значения ключевой константы = 0, 1/2, 1, что привело к квадратичной интерполяции, благодаря которой, в сочетании с методом низкой нагрузки, были получены формулы аппроксимации среднего времени отклика для следующих немарковских случаев: - распределение Эрланга второго порядка для входящего потока с функцией распределения и экспоненциальное время обслуживания с функцией распределения - пуассоновский входящий поток с функцией распределения 0 и распределение Эрланга второго порядка времени обслуживания с функцией распределения 0 а также для гиперэкспоненциального входящего потока и экспоненциального времени обслуживания, пуассоновского входящего потока и гиперэкспоненциального времени обслуживания, формулы для которых в силу их громоздкости приводить не будем. 5. Заключение В статье рассмотрены особенности построения систем массового обслуживания с расщеплением запросов. Представлен метод точного анализа среднего времени отклика ( = 2), а также его аппроксимации. Во второй части работы будут рассмотрены другие подходы к приближенному анализу времени отклика: матричногеометрический метод, анализ с помощью порядковых статистик для различных типов распределения времени пребывания подзапросов в системе.

Об авторах

А В Горбунова

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

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

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

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

И С Зарядов

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

Email: zaryadov_is@rudn.university

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

ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

К Е Самуйлов

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

Email: samuylov_ke@rudn.university

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

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

Э С Сопин

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

Email: sopin_es@rudn.university

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

ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

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