Диссертация (1155093), страница 4

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

Текст из файла (страница 4)

объединение, после чего обработанный запрос покидает систему.Здесь и далее будем считать,что синхронизация происходит мгновенно....ST13 ST14ST13...ST1 ST1...ST25 ST24 ST23ST22...ST2......Диспетчер задач(fork point)...STK5STK4211......(join point)1STK3 STK2 STKБуфер синхронизацииРисунок 1.1 — Система массового обслуживания типа fork-joinСтоит отметить, что чаще всего описанную модель рассматривают каксеть массового обслуживания (СеМО): после расщепления подзапросы одновременно поступают на вход ветвей, которые представляют собой одноканальныесистемы массового обслуживания (СМО) с очередями.

Однако данный подходпредполагает дальнейший переход к рассмотрению независимых СМО, что является упрощающим допущением в силу существующей зависимости междуочередями подзапросов вследствие общих моментов поступления. Тем не менеетаких сложностей не возникает для случая, когда каждая подсистема состоитиз бесконечного числа приборов [37–42].Анализ SPM (splitting and matching queueing system) системы массовогообслуживания в [17] является одной из самых ранних работ на эту тему. В нейрассматриваются авиапассажиры и их багаж, которые прибывают вместе на самолёте в аэропорт, но разделены до тех пор, пока пассажиры не получат своивещи в зоне выдачи багажа. В этой статье анализируется система с двумя ветвями //1, т.е.

с детерминированным входящим потоком и экспоненциальнымвременем обслуживания на каждом из серверов.SM (split-merge queueing system) система является одним из вариантовfork-join системы массового обслуживания (рис.1.2). Её отличие заключаетсяв том, что на свободные серверы не поступит ни один подзапрос следующегозапроса до того момента, пока не обслужатся все подзапросы текущего запроса17[86], т.е. происходит блокировка каждого освободившегося сервера до окончанияобработки всех задач запроса.ST1ST2...T4 T3 T2...Диспетчер задач(split)...(merge)STKБуфер синхронизацииРисунок 1.2 — Система массового обслуживания типа split-mergeFF (fission-fusion queueing system) система — это ещё одна разновидностьfork-join системы (рис.1.3).

Если допустить, что все подзапросы 1 , 2 ,...,являются идентичными и неразличимыми: = , = 1,, то запрос может покинуть систему после обработки любых подзапросов, иначе говоря,подзапросы могут принадлежать разным запросам [86]....ST STSTST...ST STSTST.........Диспетчер задач(Fission point)...ST ST STFusionpointSTБуфер синхронизацииРисунок 1.3 — Система массового обслуживания типа fission-fusionМодель независимых серверов (independent server model, ISM) представляет собой многоканальную систему массового обслуживания. Для обслуживанияпоступившего запроса требуется случайное число серверов, не превышающееих общее количество, причем обслуживание очередного запроса не может начаться до тех пор, пока число свободных серверов не станет по крайней мереравно числу серверов, требуемых для обслуживания.

В частности, в работе [87]18рассматриваемая система состоит из однородных серверов, времена обслуживания являются независимыми и имеют экспоненциальное распределение. Входящий поток является пуассоновским, а число серверов, требуемых для обработкизапроса определяется некоторой вероятностью. Запросы обслуживаются в порядке поступления (First Come First Served, FCFS) и могут покинуть системутолько после освобождения всех затребованных серверов.

Поскольку временаобслуживания на отдельных серверах являются независимыми, то сервер, закончивший обслуживание запроса, становится доступным для других задач.Таким образом, время обслуживания запроса является максимумом случайного числа экспоненциально распределенных случайных величин. Для моделибыли получены такие характеристики, как распределение времени обслуживания, распределение числа занятых серверов, а также достаточные условия длясуществования стационарного распределения.В случае модели группового обслуживания (team service model, TSM) также как и в случае ISM системы, для обработки задач требуется наличие нескольких свободных серверов одновременно, но при этом серверы начинают обслуживание этих задач и освобождаются одновременно [32; 88].Также существует такой вариант fork-join системы, когда поступающиена вход в систему несколько потоков запросов делятся на подзапросы и отправляются на обслуживание на серверы в соответствии с заданной матрицейвероятностей, т.е.

запросы поступают как независимых потоков, затем делятся на части, которые распределяются по серверам в соответствии с некоторойстратегией (политикой), которая и определяется матрицей [89; 90].Первые результаты исследования fork-join системы массового обслуживания были получены для случая расщепления заявки на два подзапроса 1 ,2с пуассоновским входящим потоком и экспоненциальным временем обслуживания на обоих серверах [19]. Однако несмотря на марковость предположенийанализ fork-join систем массового обслуживания даже для случая = 2 затруднителен по следующим причинам: процессы поступления подзапросов насерверы коррелируют; модель цепи Маркова имеет размерность , причём каждая из компонент имеет бесконечное число состояний.В силу указанных выше факторов точного решения для распределениячисла подзапросов , = 1, в fork-join системе не было найдено.

Но приэтом для случая пуассоновского входящего потока и экспоненциальных времен19обслуживания можно получить явные выражения для маргинальных вероятностей [78].Приближённое же решение для распределения числа подзапросов в случае очередей неограниченных размеров может быть получено для достаточнобольшой ёмкости накопителя — такой, что вероятность потери запросов в связис этой большой ёмкостью будет пренебрежимо мала, и в данном случае будутприменимы итерационные численные методы решения систем линейных уравнений большой размерности [91].Большинство авторов в своих работах исследуют один из основных показателей качества функционирования подобных систем массового обслуживания— время отклика , max = max(1 ,..., ), где — случайная величина временипребывания подзапроса в системе до его попадания в буфер синхронизации, = 1,.

Стоит сразу отметить, что точное выражение для среднего времениотклика было получено только для fork-join системы с двумя ветвями //1( = 2) в [18] с помощью результатов работы [19]. Для случая > 2 с помощью различных методов были получены аппроксимации среднего времениотклика.Анализ системы с двумя ветвями M/M/1.Модель цепи Маркова с непрерывным временем для fork-join системы с двумя ветвями //1 и накопителем неограниченной ёмкости рассматриваетсяв [19]. Этот анализ был расширен для ветвей //2 в [68]. Для изучения стационарного и нестационарного режимов основной краевой задачи (дифференциальное уравнение вместе с набором дополнительных ограничений) в работе [68]использовались методы исследования функций комплексной переменной, представленные, например, в [92].

В ходе последующего обсуждения более подробноостановимся на анализе статьи [19], поскольку она ведёт к точному решениюзадачи для fork-join системы с двумя ветвями //1.Итак, рассмотрим fork-join систему, попадая в которую запрос расщепляется на = 2 подзапроса, входящий поток является пуассоновским с интенсивностью = 1, а интенсивности обслуживания на двух серверах удовлетворяютусловию: 1 < 1 ≤ 2 , гарантируя, что со временем система не переполнится, т.е.

число подзапросов не устремится к бесконечности. Поведение системы20описывается непрерывным марковским процессом () = {1 (),2 (), ≥ 0},где () — число подзапросов -го типа, соответственно, = 1,2. Указанныесостояния интерпретируются следующим образом: если () = {(,), , ≥ 0}в некоторый момент времени , то в системе находится заявок 1-го типа, т.е.1 и заявок 2-го типа, т.е. 2 , а , — стационарная вероятность указанного состояния. Далее записывается система уравнений равновесия в терминах∑︀ ∑︀двойной производящей функции (,) = , [19; 50; 52]:(,) (,) = (,), ||,|| ≤ 1,(,) = 1 + 1 2 − 1 − 2 − 2 2 , (,) = 2 ( − 1) (,0) + 1 ( − 1) (0,).Анализ производящей функции позволяет получить выражения для (,0) и (0,), которые для симметричного случая 1 = 2 = равны между собой: (,0) = (0,) =( − 1)3/2.( − )1/2(1.1)Также с помощью преобразований производящей функции в граничных точках: (,0) и (0,), в [19] были получены асимптотические выражения длястационарных вероятностей состояний ,0 и 0, при → ∞, → ∞, соответственно.

Это ещё раз свидетельствует о том, что данная задача требует болеесовершенных математических методов решения.Используя результаты анализа в [19], среднее время отклика для fork-joinсистемы с двумя симметричными ветвями выводится в Приложении B в [18].Интенсивность пуассоновского входящего потока имеет значение , интенсивности обслуживания на двух серверах раны , т.е. 1 = 2 = , причём < ,так, что нагрузка на каждый из серверов = / меньше единицы:[︁ ]︁12 − [2, max ] = 2 − [1, max ] =[1, max ],88(1.2)где 2 = 1.5, [1, max ] = ( − )−1 − среднее время отклика для СМО //1[51–53].Вывод [2, max ] основан на наблюдении, что эта величина есть суммавремени пребывания в системе //1, т.е.

Характеристики

Список файлов диссертации