Анализ моделей массового обслуживания для оценки времени отклика в системе облачных вычислений Горбунова Анастасия Владимировна

Содержание к диссертации

Введение

Глава 1. Построение моделей массового обслуживания для систем облачных вычислений 12

1.1 Показатели эффективности системы облачных вычислений 12

1.2 Обзор систем параллельного обслуживания заявок 15

1.3 Постановка задачи исследования 39

Глава 2. Анализ системы характеристик системы массового обслуживания с параллельной обработкой запросов 41

2.1 Особенности модели системы облачных вычислений с расщеплением запросов 41

2.2 Время отклика в системе облачных вычислений 46

2.3 Время синхронизации в системе облачных вычислений 52

2.4 Результаты расчётов вероятностно-временных характеристик 55

Глава 3. Анализ времени отклика системы облачных вычислений с гистерезисным управлением подключением виртуальных машин 59

3.1 Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы 59

3.2 Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы с ограничением на одновременное число активаций 70

3.3 Вероятностно-временные характеристики времени отклика. Численные результаты применения рекуррентного алгоритма 81

Заключение 84

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

Список рисунков

• Обзор систем параллельного обслуживания заявок
• Постановка задачи исследования
• Время отклика в системе облачных вычислений
• Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы с ограничением на одновременное число активаций

Введение к работе

Актуальность темы исследования. Облачные вычисления (cloud computing) представляют собой технологию, позволяющую удалённому пользователю в режиме реального времени по требованию получать доступ к вычислительным ресурсам: программным приложениям, серверам, устройствам хранения данных, сервисам и др., через Интернет в рамках согласованного качества обслуживания для выбранной ценовой категории. В задачи поставщика таких услуг входит не только обеспечение требуемого уровня оказываемых услуг, но и, как следствие, избежание перегрузки ресурсов при обработке пользовательских требований и снижение энергозатрат.

Существенное значение в системах облачных вычислений имеет технология виртуализации. Благодаря виртуализации ресурсов физического сервера многие облачные провайдеры могут предложить своим пользователям высокопроизводительные сервисы для решения кластерных задач и высокопроизводительных приложений. Подобные задачи характеризуются высоким уровнем параллелизма. В качестве примера можно назвать производственные и бизнес-приложения в таких отраслях как фармацевтика, нефтяная и газовая промышленность, здравоохранение, финансы и обрабатывающая промышленность; научно-исследовательские организации используют возможность применения облачных кластеров при проведении крупномасштабных исследований в различных областях. Таким образом, применение технологии виртуализации для организации параллельных вычислений в рамках одного высокопроизводительного приложения при решении сложной комплексной задачи имеет не меньшую ценность, чем одновременное использование одного сервера несколькими приложениями. Более того, при такой настройке ресурсов, как параллельная обработка данных, очевидно, появляется возможность снижения энергозатрат за счёт уменьшения времени обработки пользовательских запросов, что, вообще говоря, тоже можно отнести к одному из методов повышения энергетической эффективности и энергосбережения.

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

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

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

Степень разработанности темы. Для анализа показателей качества обслуживания в системах облачных вычислений в случае обработки сложного комплексного запроса, содержащего в себе несколько задач и требующего высокой готовности и производительности системы, естественно допустить возможность использования модели массового обслуживания с параллельной обработкой данных (fork-join queueing system). К одному из первых упоминаний этой модели можно отнести систему с двумя параллельно функционирующими блоками D/M/1, моделирующими ситуацию одновременного прибытия в аэропорт пассажиров и их вещей, последующего разделения

этих двух условных блоков и их соединения через некоторое время в зоне выдачи багажа. Точное выражение для среднего времени отклика было получено только для двух параллельно функционирующих систем М/М/1, в остальных же случаях были получены различными методами аппроксимации среднего времени отклика. Сложность в исследовании этой системы объясняется существующей зависимостью между очередями подзапросов из-за общих моментов поступления. Несмотря на широкий спектр задач, которые решаются с помощью систем массового обслуживания с параллельной обработкой запросов, и их популярность среди зарубежных авторов, в нашей стране данная система исследовалась значительно меньше. Среди отечественных учёных, внёсших существенный вклад в анализ подобных систем, можно назвать СП. Моисееву благодаря проведённым ею исследованиям системы параллельного обслуживания сдвоенных заявок с неограниченным числом приборов, в результате чего были получены точные выражения для двумерного распределения вероятностей числа подзапросов в системе (приборов в каждой подсистеме), характеристики числа занятых приборов в соответствующих подсистемах и коэффициент корреляции между ними.

Одним из методов исследования систем с динамическим управлением подключением виртуальных машин является анализ с помощью моделей массового обслуживания с динамической активацией дополнительных приборов. Стоит отметить, что, как правило, выделяют два типа гистерезисного управления: гистерезисное управление входящим потоком (текущей нагрузкой) и гистерезисное управление обслуживанием, и для анализа этих моделей используются методы теории вероятностей, теории массового обслуживания и теории телетрафика. Среди авторов, внёсших серьёзный вклад в исследования можно назвать: М.А. Красносельского и А.В. Покровского, К.Е. Самуй-лова, А.В. Печинкина, Ю.В. Гайдамака, С.Я. Шоргина, В.М. Вишневского, СП. Моисееву, В.А. Нетеса, R.D. Nelson и A.N. Tantawi, F. Baccelli, S. Balsamo и I. Mura, L. Flatto and S. Hahn, С. Kim и А.К. Agrawala, A. Thomasian, J. Menon, I. Tsimashenka и W.J. Knottenbelt, E. Varki, S. Varma и A.M. Makowski и др.

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

обслуживанием и разработка методов для анализа вероятностно-временных характеристик показателей качества обслуживания в этих системах. Для достижения цели исследований в диссертации решаются следующие актуальные задачи:

1. Построение и исследование системы облачных вычислений в виде системы массового обслуживания с параллельной обработкой заявок.

2. Анализ вероятностно-временных характеристик системы массового обслуживания с параллельной обработкой заявок, таких как среднее время отклика и дисперсия времени синхронизации.

3. Разработка рекуррентного алгоритма расчета оценки времени отклика для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин.

4. Разработка рекуррентного алгоритма расчета оценки времени отклика для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин с ограничением на одновременное число активаций.

Научная новизна.

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

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

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

а также моменты высших порядков указанных случайных величин. Ранее можно было оценить только математическое ожидание непосредственным решением системы уравнений равновесия (СУР). 4. Для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин и ограничением на одновременное число активаций разработан рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика и времени ожидания начала обслуживания, с помощью которого оцениваются не только математическое ожидание, но и дисперсия, а также моменты высших порядков указанных случайных величин. Ранее можно было оценить только математическое ожидание непосредственным решением СУР. Теоретическая и практическая значимость работы. Теоретическая ценность полученных в диссертации результатов заключается в создании математического аппарата для исследования систем облачных вычислений в контексте решения кластерных задач и высокопроизводительных приложений, а также в контексте повышения энергетической эффективности и энергетического сбережения посредством динамической активации виртуальных машин. Полученные модели системы облачных вычислений в совокупности с разработанными алгоритмами могут использоваться для решения задач подбора оптимальных параметров функционирования систем, способствующих снижению энергозатрат и избежанию ухудшения качества обслуживания пользователей. Полученный математический аппарат может быть расширен с помощью других комбинаций типов входящего трафика и времён обслуживания.

Полученные оценки для дисперсии времени отклика и времени синхронизации, а также рекуррентный алгоритм расчета, позволяющий оценить моменты высших порядков для времени отклика и времени ожидания начала обслуживания, могут использоваться уже на этапе проектирования облачных центров при планировании необходимых ресурсов, которые потребуются для обеспечения соответствующего уровня обслуживания пользователей с учетом целей и задач, поставленных заказчиками перед проектными организациями. Результаты работы использованы в рамках исследований по грантам РФФИ № 15-07-03051 «Формализация моделей и развитие методов анализа

вероятностных характеристик инфокоммуникационных межмашинных беспроводных сетей пятого поколения» и № 15-07-03608 «Разработка методов решения задач управления доступом в широкополосных беспроводных инфокоммуникационных сетях на основе нелинейного анализа и математической теории телетрафика», а также в учебном процессе при подготовке выпускных работ бакалавров и магистров, обучающихся по направлению «Фундаментальная информатика и информационные технологии».

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

Положения, выносимые на защиту.

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

9. Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика и времени ожидания начала обслуживания для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин.

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

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

ванность при сопоставлении с известными результатами, полученными для частных случаев.

Результаты диссертационного исследования докладывались на следующих научных конференциях: Вторая молодежная научная конференция «Задачи современной информатики» (Москва, 2015 г.); 9-ая Международная отраслевая научно-техническая конференция «Технологии информационного общества» (Москва, 2015 г.); X Юбилейная Международная практическая конференция «Современные информационные технологии и ИТ-образование» (Москва, 2015 г.); XV Международная конференция имени А.Ф. Терпугова «Информационные технологии и математическое моделирование (ИТТМ-2016)» (Томск, 2016 г.); Девятнадцатая международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь (DCCN-2016)» (Москва, 2016 г.); I Международная научная конференция «Конвергентные когнитивно-информационные технологии» (Москва, 2016 г.).

Публикации. Основные результаты по теме диссертационного исследования изложены в 8 печатных изданиях -], из которых 2 — изданы в журналах, рекомендованных ВАК РФ ;], и получены лично соискателем. В работах, опубликованных в соавторстве, личный вклад соискателя заключается в получении результатов, касающихся разработки моделей и их анализа; при его непосредственном участии разработаны программные средства.

Соответствие паспорту специальности. Диссертационное исследование выполнено в соответствии с паспортом специальности 05.13.17 «Теоретические основы информатики» и включает оригинальные результаты в области исследования информационных процессов и требований их пользователей к показателям эффективности, в области разработки моделей информационных процессов, разработки общих принципов организации телекоммуникационных систем и оценки их эффективности. Таким образом, диссертационное исследование соответствует следующим разделам паспорта специальности 05.13.17 «Теоретические основы информатики»: п. 2 (Исследование информационных структур, разработка и анализ моделей информационных процессов и структур), п. 16 (Общие принципы организации телекоммуникационных систем и оценки их эффективности).

Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и двух приложений. Полный объём диссертации составляет 97 страниц с 13 рисунками. Список литературы содержит 104 наименования.

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

Матрично-геометрический подход для оценки времени отклика fork-join системы используется в серии статей [22-24]. В первой работе [22] были предложены две модели, аппроксимирующие исходную fork-join систему с К ветвями М/М/1 и различными интенсивностми обслуживания на разных серверах:

1. поступающий запрос принимается в систему тогда и только тогда, когда число подзапросов к-го типа, находящихся в системе, меньше некоторого фиксированного положительного целого числа Uk: rik Uk, к = 2,К, в противном случае он теряется;

2. отказ в обслуживании на J -ом сервере происходит тогда и только тогда, когда нарушается условие: щ — rij ф Uij для некоторого і и для фиксированных положительных целых чисел Uij, Vi,j,i Ф j, причём сервер j блокируется до тех пор, пока подзапрос не закончит обслуживаться на сервере г; где вектор ft = (піУ..,Пку,пк) отражает состояние системы, rik — число под-запров STk в системе, к = 1,К.

В результате анализа обеих систем с помощью матрично-геометрического метода удаётся определить стационарное распределение числа подзапросов в системах 7г(п). Далее полученное распределение используется при алгоритмическом решении задачи нахождения функции распределения времени оклика: FwKmax{x) = y /7r{n)FWH (ж), х 0. J Каппах ft Таким образом, задача сводится к поиску условного распределения времени отклика FWn (х) при условии, что система находится в состоянии ft. Для К,тах первой модифицированной модели искомое условное распределение может быть выражено с помощью распределения Эрланга, а во втором случае условное распределение получается при анализе процесса поглощения для подзапросов. Кроме того, авторы доказали, что решения, полученные при анализе этих двух систем, являются верхней и нижней границами для функции распределения времени отклика, соответственно.

В следующей статье авторов [23] изучается fork-join система с пуассонов-ским входящим потоком, но при этом время обслуживания на однородных сер 28 верах имеет распределение Кокса. Отметим, что для стационарных вероятностей состояний в СМО //1 известно точное решение [94]. Как и в предыдущей работе рассматриваются две аналогичные, аппроксимирующие исходную систему модели: 1. модель, в которой все очереди кроме очереди к первому серверу имеют конечную ёмкость; 2. модель, в которой вводится ограничение на то, что разница между каждой парой длин очередей к серверам не должна превышать заданный порог.

Матрично-геометрический анализ указанных систем, предложенный в [95] благодаря тому, что матрицы вероятностей перехода сводятся к блочно-треугольному виду, позволяет получить стационарные вероятности, которые, используются для вывода распределения времени отклика, а, соответственно, и моментов этого распределения. Полученные выражения являются верхними и нижними границами для моментов времени отклика.

Следующая работа [24] продолжает начатые исследования. Авторы предлагают алгоритмический метод для вычисления верхних и нижних оценок производительности системы, основанный опять же на построении двух ограничивающих исходную систему моделей, стационарное распределение для которых находится с помощью матрично-геометрического метода. Указанный подход, по мнению авторов, может быть расширен для анализа систем с отличными от пуассоновского входящим потоком и отличным от экспоненциального временем обслуживания на разнородных серверах. Представлены доказательства того, что оценки являются верхними и нижними, также приведены оценки погрешности предложенных аппроксимаций.

Отметим, что матрично-геометрический метод (МГМ) использовался и при анализе систем родственных fork-join. Так, МГМ был применён для анализа модели независимых серверов (ISM), в [96] с помощью МГМ анализируется split-merge система с двумя ветвями с наложением ограничения на ёмкость накопителя одной из очередей. Были получены выражения для математического ожидания, дисперсии и функции распределения времени отклика. Также был разработан метод аппроксимации для систем с более чем с двумя ветвями. В работах [97; 98] также исследуется fork-join система, но уже с распределением фазового типа для входящего потока и с потерями. В статье [99] рассматрива 29 ется ещё одна вариация классической fork-join системы, для анализа которой используется МГМ: обслуживание каждого подзапроса происходит в несколько этапов, включая фазу ожидания и фазу объединения родственных подзапросов; существует динамическая политика планирования нагрузки системы для поддержания эффективного использования сервера.

Анализ с помощью порядковых статистик. Поскольку время отклика fork-join системы классически определяется как максимум, а в некоторых случаях и как минимум из К случайных величин времён пребывания подзапросов в системе [84], то естественно, что одним из альтернативных способов оценки среднего времени отклика является использование теории порядковых статистик [33-35]. По определению [33-35], если і,...,# — конечная выборка, определённая на некотором вероятностном пространстве (Г2, F, Р), и для си Є Q : ХІ = i(uj),i = 1,...,К, и далее, если перенумеровать последовательность {xA\f=l в порядке неубывания таким образом, что х х ) %(к-1) х{К), то такая последовательность будет называться вариационным рядом, а его члены — порядковыми статистиками. Случайная величина же (&) : (ш) = х ) называется к—ой порядковой статистикой исходной выборки. Из определения ясно, что (i) = min(i,...,#), (#) = max(i,...,#). (1.15) Таким образом, время отклика Wx:m&x = (К) или W min = (i) в терминах теории порядковых статистик, где &, к = 1,К — положительные случайные величины времён пребывания подзапросов в системе до попадания в буфер синхронизации. Следовательно, математическое ожидание времени отклика можно вычислить, зная распределения экстремальных значений щ и (#), причем функция распределения второй случайной величины фактически является совместной функцией распределения случайных величин і,...,#: F&KAx) = Р(тах(і,...,х) х) = Р(і ху..к х)- F {1Ax) = P(min(i,...,#) х) = 1 — P(i х,...к х) Обозначим через Fk{x) — функцию распределения, а через fk{%) — плотность распределения случайной величины &, к = 1,К. Если сделать допущение о том, что і,...,х — независимые, что в нашем случае, как уже говорилось выше,

Постановка задачи исследования

Рассмотрим еще одну важную характеристику производительности системы облачных вычислений — время синхронизации. Время синхронизации определяется как время между поступлением первой и последней частей подзапросов одного запроса в буфер синхронизации, иными словами это разность между максимумом и минимумом из времен пребывания подзапросов в системе: [И7 ] = /[W max] — [И- тт]. (2.48)

Для того, чтобы вычислить среднее время синхронизации достаточно определить математическое ожидание каждой из компонент разности, что и было сделано выше: E [max( i,..., х) — min(i,..., #)] = E [max( i,..., #)] — E [min( i,... ,#)]. Таким образом, учитывая формулы (2.33) и (2.35), а также то, что & Exp(/j,k — А), к = 1,К, можем записать: Е \WK\ / г — / г + / т+ 2-— /І/ — Л 2-— /І/ + /ІТО — 2Л 2-— /І/ + /ІТО + /І/; — ЗА 1 +2 + ...+ - 1 ++ - (2.49) Теперь проанализируем время синхронизации для случая однородных приборов [79;80]. Как уже было сказано ранее, поскольку для определения + . . . + ( — 1) математического ожидания разности двух случайных величин \к,max и К,min их зависимость, которая, очевидно, существует, не играет никакой роли, то достаточно вычислить только первые моменты экстремальных значений: л К-1 л л „Гттг 1 V 1 I Е\WK\ = Е[WK max — Е[WK min 7 Т / = ГТ-"К-1- (2.50) [и, — А) 2-— і (и, — л) Но для того, чтобы получить выражение для дисперсии исследуемой величины, недостаточно знать значения дисперсий случайных величин \к,max и \к,min. В этом случае можно действовать двумя способами. Один из них — воспользоваться функцией распределения ранга для положительных н.о.р.с.в.: к к FwK(x) F (х) = N / fi(y) I I [Fj{y + х) — Fj(y)]dy, (2.51) =1 0 i=1j= А второй — напрямую воспользоваться формулой для вычисления дисперсии размаха выборки объема К н.о.р.с.в. с функцией распределения F(x) [33]: -DfW7 ] D[ K) (1)] = f ( к к к\ 2 (2.52) = 2 1 — F (у) — [1 — F{x)\ + [F{y) — F(x)\ \dxdy — {E\WK\)

Сформулируем утверждение. Утверждение 2.3.1. Оценка дисперсии времени синхронизации системы облачных вычислений с расщеплением запросов для случая однородных приборов имеет вид: 1 —V 1 О[Wк\ т Т2 / 2- (2.53) [и, — А г 2-— г УГ І=1 Доказательство. Для доказательства воспользуемся формулой (2.52). В нашем случае F(x) = 1 - е х)х,х 0, F(y) = 1 - е - \у 0. Поскольку время пребывания в подсистеме М\/М /1 будет иметь экспоненциальное распределение с параметром (/І — Л), то подынтегральное выражение из формулы (2.52) примет вид: (1 — F (у) — [1 — F{x)\ + [F{y] — F(x)\ ) = = 1 - (1 - e -x)yf - (1 - 1 + e- -x)xf + (1 - e -x)y - 1 + e- -x)x) = 1 \ І \ґ -\\і„ — (и—\)іу „ — (и—\)Кх І —— J. — / I — J. ) с — с т -/-— і i=0 if —- і i=0 1 1 \ л I \ ґ i\«„-(u—A)iw „ — (u—X)Kx , — J_ — J. — / ( — J. ) о — о "Г -/-— І i=l \ л / \/ -i\K—i—(i —X)(K—i)y—(i —X)ix _i_ / -і\К—(/л—Х)Ку i=l \ л f 1 VP- - ) -I- \ л Г 11\А - р-(м_ )( _ )?/р_(м_ ) :с_і_ -/-— і -/-— і i=l i=l I / -i \K —(p—X)Ky Подставляем полученное выражение в интеграл и делаем соответствующие вычисления: К К—I \ л І ( 1 Y/D (M— )W _I_ \ л ( 1 N\- — /з — (M— )(- — )Ул — (м—А)гж, i=l i=l к . _ Тґ І / -і \К —(/л—Х)Ку АгрАп, гр \ л Г 1 \ /і (м )% і о =1 V—, / К \ р — (/л—Х)іх У І \ л f 1 "\ — л —(м— )( — )У __ o"Z/ 1 /з-(м— )Ку Аг,, і (/І — Х)і (/і — л)і /_ і і=\ \ л ( 1 \ -пію (іл ) -У \ л ( 1 \К— ьр (м— )(к І)У і /_ і /- і і=\ і=\ І ((м — /\)02 і {.і1 ) 1 Е К к-іе к -хки (—1) —h (—1) ye ydy = _ —(м— ) Е іС 1 х- (—1) + / і {{її — Л)і) - і і (/І — \)2{K — i)i ((/i — A)if)2 00 ft К — А і WTS n / LT\ 1 i; " LT р — уН—л)Ку = — у I ) (—1) + / ( ) (—i) ((/i — A)i)2 і ((/І — A)i)2 2-— і {{її — A)i) 2-— і _ ґ TC\ р {іл )Ку + (—1) \ л II f 1 "\(Ж— ) ((/І — Х)К)2 і (/І — A)2(if — і)і І i=l — г ь -і -К" /К\ / і л і—1 if—1 /К\ / -і лТ7 / 7 / 7Г (/i — \у Z— I 1 K—1 (К\Ґ -i \K—i ( л \K\ + 4 1 о i(K-i) K2 Далее подставим вычисленный интеграл в (2.52) и определим оценку дисперсии времени синхронизации: ) () rj ( 1V—і -DiWV] Ж(К) (i)l = 7T / — о / — Ь (/i — A) —- г2 —- г : 2 1 -1 о K—l (K\ t -і \K—i ff -i K — l -, E ) ( — 1J ( — 1) 1 —V 777 \ 1 77o / ._ i(K — i) Kl 2 —- i Полученную формулу можно упростить, в результате будем иметь следующее выражение [79; 80]: 1 —v 1 D[Wк\ ТЛ / о- (2.54) (д — А)2 -/— г1 п 2.4 Результаты расчётов вероятностно-временных характеристик

Для оценки аппроксимации математического ожидания и дисперсии времени отклика, а также дисперсии времени, проведенного в буфере синхронизации, с помощью программных средств GPSS (General Purpose Simulation System) была построена имитационная модель. Поскольку интерес представляют характеристики системы в стационарном режиме ее работы, имитационное моделирование проводилось до того момента, пока не произошла стабилизация параметров модели, а именно после прохождения через систему около пятисот тысяч запросов.

Для иллюстрации качества различных аппроксимаций, полученных для математического ожидания времени отклика, на рисунке 2.3 представлены графики зависимости среднего времени отклика от количества подзапросов для следующих формул: Формула (2.59) является верхней границей для максимума независимых экспоненциально распределенных случайных величин с параметром ( — ).

Расчеты были выполнены для интенсивности входящего потока = 2 -1 и интенсивности обслуживания = 2.2 -1. Поскольку для = 2 получено точное выражение для среднего времени отклика [18], рассматривались значения 2. Как видно из графиков, формулы (2.55),(2.56),(2.57),(2.58) представлены в порядке убывания точности их приближения, а верхняя грань для среднего значения максимума порядковых является верхней гранью и для среднего времени отклика.

Время отклика в системе облачных вычислений

Слабой стороной исходной модели является чрезвычайно большая мощность пространства состояний, которая имеет квадратичную зависимость от количества серверов. Поэтому теперь рассмотрим упрощённую модель с уменьшенным пространством состояний благодаря наложению ограничения на максимальное количество одновременно возможных активаций, и проведём анализ её характеристик с помощью известных свойств преобразования Лапласа-Стилтьеса, алгоритм получения которого и будет предложен далее. Также заметим, что результаты численного эксперимента в [74] позволяют сделать вывод о том, что аппроксимация исходной модели упрощённой является допустимой ввиду положительного с точки зрения инженерных расчетов результата, поскольку максимальная погрешность приближения составляет не более 10%.

Итак, рассматривается система облачных вычислений с гистерезисным подключением и отключением дополнительных виртуальных машин в виде многолинейной системы массового обслуживания с приборами, часть которых может быть не активна, и конечной ёмкостью системы В систему поступает пуассоновский поток заявок с параметром Л. Считаем, что приборы являются однородными, время обслуживания распределено по экспоненциальному закону с параметром /І [74; 82].

Активным в пустой системе, т.е. готовым при поступлении заявки мгновенно начать ее обслуживание, является один прибор. При поступлении заявок в систему активация приборов происходит не мгновенно, при этом количество активных приборов определяется числом заявок в очереди, в которой установлены парные пороги, заданные значениями векторов Н = (Ні,Н2,...,Нк-і), Н\ ІІ2 ... Нк-1 и L = (Li,L2,...,-Ljf_i), L\ L12 ... LK-I где Lj__i НІ, і = 1,K — 2 и Li НІ, і = 1,K — 1. Заявки обслуживаются в порядке поступления, т.е. очередь имеет дисциплину FCFS. При поступлении на прибор заявка сохраняет место в очереди. Правила работы системы следующие:

1. Если в системе уже находится Щ заявок, то при поступлении новой заявки активируется (подключается) один (і + 1)-й дополнительный прибор, но не мгновенно, а через случайное время, имеющее экспоненциальное распределение с параметром а;

2. Если в системе есть Li заявок и при этом одна заявка обслужилась, то (і + 1)-й прибор мгновенно отключается, либо, если он не был активен, останавливается процедура его активации.

Функционирование системы описывается марковским процессом X(t) с множеством состояний: О —— {k,i,n) О п Hi, k = l,i = 1; Lk-i ті Hk, к = 2,i = к — 1,к Lk-i ТІ Hk, к = 3,К — 1, і = к — 2,к Lk-i ТІ R, к = К, і = к — 2,к (3.33) где — необходимое количество приборов для обслуживания заявок, находящихся в системе; — количество активированных приборов; — количество заявок в очереди.

На рисунке 3.3 представлена диаграмма интенсивностей переходов упрощённой модели в случае выбора описанного выше расположения порогов, число приборов = 4. Сформулируем утверждение [82]. (4,4,L4-1) fl л л л л л 1,1,0 1,1,1 1,1,2 ...21,1,л -1 2ц fl я /J 4Х -4u4/LT Рисунок 3.3 — Диаграмма интенсивностей переходов для упрощённой модели Утверждение 3.2.1. Преобразование Лапласа-Стилтьеса () времени ожидания начала обслуживания и ПЛС () времени пребывания заявки в системе равны: ()= ,,,,, (3.34) fl W(s) V(s) (3.35) /і + s где ,, – стационарные вероятности соответствующих состояний (,,) , а ,,() – ПЛС времени ожидания -й в очереди заявки, если система находится в состоянии (,,), определяются следующими рекуррентными (,,) выражениями (3.36)-(3.47):

Доказательство. Доказательство утверждения аналогично доказательству, приведенному в разделе 3.1. Рекуррентные соотношения (3.36)-(3.47) позволяют определить ПЛС для всех состояний (,,) , с помощью которых вычисляются ПЛС () времени ожидания начала обслуживания и ПЛС () времени пребывания заявки в системе с ограничением на одновременное количество активаций: где тік,і,п — стационарные вероятности для соответствующих состояний (&,г,п), алгоритм вычисления которых приведен в [74]. Теперь на основе базовых рекуррентных соотношений запишем формулы для конкретных состояний, на основе которых впоследствии и построим сам алгоритм:

Задача обращения ПЛС для времени ожидания начала обслуживания и времени отклика системы облачных вычислений с ограничением на одновременное число активаций даже несмотря на уменьшенную размерность пространства состояний в случае большого объема накопителя и, соответственно, значений парных порогов активации и отключения дополнительных приборов, представляет собой значительную вычислительную сложность. Однако благодаря свой 82 ствам ПЛС, в частности, тому, что -й момент случайной величины равен: E[ ]n = (—1)n/3 n (0), (3.77) где ()(0) — это значение -й производной ПЛС случайной величины в нуле, возможно вычислить моменты высших порядков и составить полноценное представление о поведении исследуемых случайных величин.

Итак, рассмотрим применение разработанного метода расчета временных характеристик модели системы облачных вычислений в терминах преобразования Лапласа-Стилтьеса для следующего набора данных: число приборов = 4, максимальная длина очереди = 75, векторы нижних и верхних порогов = (10,20,30), = (25,35,45), интенсивность обслуживания заявок = 1.

На рисунке 3.4 изображены графики зависимости среднего времени отклика от интенсивности входящего потока для различных значений параметра экспоненциального времени активации дополнительных приборов, на которых в целом наблюдается рост математического ожидания, что вполне естественно для увеличения значений интенсивности входящего потока. При = 0.1 колебания среднего времени отклика менее значительны, и с ростом кривая сглаживается, поскольку большую часть времени заявки проводят в ожидании начала обслуживания. Для двух других значений на графиках более четко выражены локальные минимумы, что объясняется выигрышем во времени при небольших значениях загрузки системы за счет быстрого и своевременного подключения дополнительных приборов.

Рекуррентный алгоритм вычисления преобразования Лапласа-Стилтьеса времени отклика системы с ограничением на одновременное число активаций

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

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

1. Построение и исследование системы облачных вычислений в виде системы массового обслуживания с параллельной обработкой заявок.

2. Анализ вероятностно-временных характеристик системы массового обслуживания с параллельной обработкой заявок, таких как среднее время отклика и дисперсия времени синхронизации.

3. Разработка рекуррентного алгоритма расчета оценки времени отклика для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин.

4. Разработка рекуррентного алгоритма расчета оценки времени отклика для модели системы облачных вычислений с гистерезисным управлением подключением виртуальных машин с ограничением на одновременное число активаций. Глава 2. Анализ системы характеристик системы массового обслуживания с параллельной обработкой запросов

Рассмотрим облачный центр, состоящий из нескольких физических машин, которые резервируются пользователями в порядке поступления запросов и могут использоваться совместно для их обработки посредством метода виртуализации (рис. 2.1). В систему поступают сложные запросы пользователей, содержащие несколько задач (подзапросов), для обработки каждой из которых требуется одна виртуальная машина. Запрос считается выполненным, т.е. пользователь получает отклик системы, после обработки всех его подзапросов (синхронизация происходит мгновенно). Функциональная схема облачной системы, используемой для решения описанных выше задач, представлена на рисунке 2.2.

Для моделирования облачного центра будем использовать fork-join систему массового обслуживания с К ветвями типа М\/М к/1, к = 1,К.

Времена пребывания подзапросов в системе с расщеплением являются зависимыми случайными величинами в силу общих моментов поступления. По 42 скольку точное выражение для времени отклика в fork-join системе в случае К 2 неизвестно, и возможность его получения остается под вопросом [18; 20], то в качестве её аппроксимации будем использовать К независимых параллельно функционирующих систем массового обслуживания М\/М к/1, к = 1,К.

Использование такого приближения представляется возможным не только исходя из естественных интуитивных соображений, но и благодаря тому, что выражения для маргинальных вероятностей числа подзапросов k-го типа, к = 1,К, в исходной fork-join системе совпадают с выражениями для стационарных вероятностей в системе М/М/1 [78], что и будет показано далее.

Однако важно заметить, что сложности из-за зависимости между временами поступления подзапросов в систему не мешают точному анализу системы в случае с бесконечным числом приборов в каждой из подсистем. В данных условиях становится возможным получить точное решения не только для времени отклика, но и для стационарного распределения числа подзапросов в системе [37-42].

Как уже было упомянуто ранее, точного решения для распределения числа подзапросов STk k = 1,К в fork-join системе не было найдено. Но при этом для случая пуассоновского входящего потока и экспоненциальных времён обслуживания можно получить явные выражения для маргинальных вероятностей [78].

Рассмотрим систему массового обслуживания с К независимыми параллельно работающими приборами (виртуальными машинами или серверами), каждый из которых имеет накопитель неограниченной емкости. В эту систему поступает пуассоновский поток запросов с интенсивностью Л. При этом в момент поступления в систему запроса, он делится на К подзапросов от 1-го до К-го типа и посылает подзапросы в каждую из К очередей. Запрос считается обслуженным в момент окончания обслуживания последнего из составляющих его подзапросов. Времена обслуживания заявок-подзапросов являются независимыми случайными величинами, распределенными по экспоненциальному закону с параметром / для подзапроса k-го типа, к = 1,К.