Размещено на http://www.allbest.ru/



Аннотация

Облачные вычисления представляют собой инновационную технологию, позволяющую удаленному пользователю получать доступ к ресурсам с помощью различных сервисов Интернета. С развитием концепта больших данных и роста популярности таких сервисов стало необходимо оптимально распределять ресурсы между ресурсами системы и поддерживать высокую производительность. Одним из новых подходов к данной технологии является распределение. В данной работе рассматриваются модели облачных вычислений, в которых поступающие запросы разделяются на несколько подзапросов, которые независимо и параллельно обслуживаются разными серверами. Для оценки качества функционирования моделей мы рассчитываем вероятность потери требования, вероятность немедленного обслуживания и время отклика c помощью методов теории массового обслуживания. Расчеты выполнены с использованием аналитических результатов и имитационной модели. В заключении приведен сравнительный анализ полученных результатов.



Abstract

Cloud computing is an innovative technology which enables remote users to indicate resources through the Internet services. The concept of big data evolves, and service popularity grows dramatically, so it has become critical to allocate resources better and to maintain high efficiency. One of the new approaches to this technology is a division of the requests into subtasks with parallel execution of servers. In this paper such models are considered, but also the systems with impatient clients are modeled. To estimate quality of model's performance we have calculated blocking probability, probability of immediate service and mean response time by using a queuing theory. The estimations have been obtained by numerical and simulation experiments and as a result, a comparative analysis of the calculations have been demonstrated.



Оглавление

Введение

1. Постановка задачи

2. Описание моделей с конечной очередью

2.1 Описание модели с разделением заявки на 4 подзадачи

2.2 Описание модели с разделением заявки на 4 подзадачи в виде СМО M|G|1

2.3 Описание модели с разделением заявки на 2 подзадачи

3. Описание моделей с конечной очередью и с ограниченным временем ожидания

3.1 Описание модели с разделением заявки на 4 подзадачи

3.2 Описание модели с разделением заявки на 2 подзадачи

4. Аналитические выражения для показателей качества обслуживания систем

4.1 Системы без ограничений на время ожидания

4.1.1 Вероятность потери заявки

4.1.2 Вероятность немедленного обслуживания

4.1.3 Среднее время отклика

4.2 Системы с ограниченным временем ожидания

4.2.1 Вероятность потери заявки

4.2.2 Вероятность немедленного обслуживания

4.2.3 Среднее время отклика

4.3 Аналитические выражения показателей для СМО M|G|1

4.4 Расчет показателей эффективности моделей из параграфов 2.1. и 2.2

5. Имитационное моделирование функционирования систем

5.1 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 4 сервера

5.2 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 2 сервера

5.3 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 4 сервера с нетерпеливыми заявками

5.4 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 2 сервера с нетерпеливыми заявками

6. Анализ результатов численного и имитационного моделирования

6.1 Анализ вероятности потери заявки, среднего числа заявок в системе и времени отклика

6.2 Анализ вероятности немедленного обслуживания

Заключение

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

Приложение



Введение

имитационный моделирование система заявка

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

Преимущества таких систем для компаний - заказчиков очевидно:

1) Сокращение расходов на использование ресурсов. Ресурсы приобретаются из облака по требованию и оплачиваются только по использованию;

2) Система облачных вычислений легко масштабируется. Можно с легкостью подключать новые устройства или увеличивать хранилища данных [1];

3) Все данные и приложения находятся в одном месте. Сокращается рабочее время на поиск информации.

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

В последнее время число поступающих запросов на сервера крупных ориентированных на облачные вычисления сервисов растет с огромной скоростью. Например, облачная система Facebook ежедневно получает и обрабатывает 700 Tбайт данных [1]. Для оптимального распределения данных и запросов в системе облачных вычислений стали использовать принцип параллелизма [2,3,4]. Сложные массивные пользовательские запросы стали распределяться на несколько серверов, каждый из которых работает параллельно и независимо.

Рассмотрим процесс поступления и обработки заявки облаком [2]:

1) Заявка поступает в систему и встает в очередь;

2) Сервер делит заявку на части и отправляет их на обслуживание к рабочим серверам;

3) Заявка после обслуживания всех подзадач покидает систему.

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

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

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



1. Постановка задачи

Введем модель облачных вычислений с параллельным обслуживанием заявок. У нас будет один главный сервер с накопителем конечной очереди заявок и 4 сервера, которые будут обслуживать части заявки. Алгоритм обслуживания «сложной заявки» - заявки из нескольких подзадач сервером выглядит следующим образом:

1) Запрос встает в очередь на обслуживание.

2) Сервер разделяет заявку по определенной дисциплине на подзадачи и отправляет на обслуживание.

3) Заявки заканчивают обслуживаться, объединяются и покидают систему.

Наглядный пример функционирования процесса обработки заявки показан на рис. 1.

Рис. 1 Процесс обслуживания заявки сервером

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

1) Заявка разделяется на 4 подзадачи, которые обслуживаются на 4 серверах одновременно и независимо. Она будет полностью считаться обслуженной за время , где - время, за которое обслужится ая подзадача.

2) Заявка разделяется на 2 подзадачи, которые обслуживаются на 2 серверах одновременно и независимо. Соответственно, время, за которое она обслужится, .

Введем основные характеристики системы:

1) Система имеет один общий конечный накопитель с числом мест k.

2) Входящий поток заявок является пуассоновским с интенсивностью поступления л заявок в минуту.

3) Среднее время обслуживания одной заявки - a минут. Длительность обслуживания одного требования является экспоненциально распределенной величиной.

4) Тогда в случае режима с разделением на 4 сервера интенсивность обслуживания 1 - ой подзадачи сервером = , а для случая с разделением на 2 подзадачи интенсивность .

Теперь введем модель облачных вычислений с нетерпеливыми заявками и накопителем конечной мощности. Нетерпеливые заявки -- это требования, которые должны покинуть систему по истечении определенного времени. Например, пользователи посылают запрос в облако, а вследствие перегруза сервера запрос обрабатывается очень долго. Тогда пользователь может отменить свой запрос и не ждать результата.

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

Опишем основные характеристики системы:

1) Система имеет один общий накопитель с мощностью k.

2) Входящий поток заявок является пуассоновским с интенсивностью поступления л заявок в минуту.

3) Среднее время обслуживания одной заявки - a минут. Длительности обслуживания требования экспоненциальные величины с параметрами и для 1- ого и 2 - ого режима соответственно.

4) Тогда в случае режима с разделением на 4 сервера интенсивность обслуживания 1 - ой подзадачи сервером = , а для случая с разделением на 2 подзадачи интенсивность .

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

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



2. Описание моделей с конечной очередью

Перейдем к детальному описанию СМО, в которой очередь на обслуживание имеет конечную длину k. Поток поступающих требований имеет интенсивность л. При поступлении на обслуживание заявка сразу же разделяется на подзадачи.

Интенсивность обслуживания одной подзадачи одним сервером для 1 - ого и 2 - ого сервера и . Заявка может покинуть систему, когда полностью обслужатся все подзадачи одной заявки [3].

2.1 Описание модели с разделением заявки на 4 подзадачи

Введем случайный процесс - число заявок в очереди в момент времени t, и - число занятых каналов в момент времени t, . Введем - случайный процесс с непрерывным временем и с дискретным множеством состояний .

Случайный процесс является марковским, тогда, когда для него выполнено соотношение [5]:

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

Обозначим вероятность перехода из состояния в состояние за время h [5]:

Выпишем вероятности перехода за время для нашей системы:

Вероятности перехода не зависят от t, поэтому марковский процесс является однородным по времени [5].

Тогда выражения для интенсивностей переходов будут выглядеть следующим образом:

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



Рис. 2 Граф переходов для процесса X(t)

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

Эргодическое распределение удовлетворяет следующей системе уравнений глобального баланса [5]:

Кроме того, для решения системы уравнений добавляется условие нормировки:

Найдем стационарное распределение системы для случая . Для этого выпишем матрицу интенсивностей переходов:

Тогда записав уравнения глобального баланса, получим значения для

:

Для аналитически решить систему довольно трудно, далее будет приведено ее решение с помощью численных вычислений.

2.2 Описание модели с разделением заявки на 4 подзадачи в виде СМО M|G|1

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

В нашем случае величина , где - независимые случайные величины, распределенные экспоненциально с параметром Тогда запишем выражение для :

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

Введем - момент окончания обслуживания ого требования, а - число требований, оставшихся в системе после ухода этого требования. Последовательность { образует цепь Маркова.

Для этой системы не вводится понятие вероятности потери заявки, поэтому в дальнейшем мы будем исследовать среднее число заявок в системе и среднее время отклика.

2.3 Описание модели с разделением заявки на 2 подзадачи

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

Вероятности перехода за время h:

Тогда выражения для интенсивностей перехода примут вид:



Рис. 3 Граф переходов для системы

Для этого процесса также выполнено свойство неприводимости матрицы, и все состояния являются возвратными. Следовательно, выполнено условие существования и единственности стационарного и предельного распределения.

Запишем систему уравнений глобального баланса для этой системы:

Рассмотрим случай для Тогда матрица интенсивностей переходов будет иметь вид:



Выпишем выражения для стационарного распределения :



3. Описание моделей с конечной очередью и с ограниченным временем ожидания

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

Интенсивность обслуживания одной подзадачи одним сервером для 1 - ого и 2 - ого сервера и . Заявка может покинуть систему, когда полностью обслужатся все подзадачи одной заявки.

Функционирование такой системы можно увидеть на рис. 4.

Рис. 4 Модель СМО с накопителем конечного объема и ограниченным временем ожидания



3.1 Описание модели с разделением заявки на 4 подзадачи

Как и в предыдущей главе введем двумерный случайный процесс с непрерывным временем с дискретным множеством состояний .

В данном случае процесс также является марковским, так как время нахождения заявок в очереди распределено экспоненциально, свойство отсутствия последействия выполнено. А также сохраняется свойство однородности.

Выпишем интенсивности перехода для этого случая и получим граф переходов на рис.5.:

Рис. 5 Граф переходов для процесса

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

Теперь выпишем систему уравнений глобального баланса:

3.2 Описание модели с разделением заявки на 2 подзадачи

Рассмотрим процесс с разделением заявки на 2 сервера. Процесс обладает теми же свойствами, что и процесс с разделением на 4 сервера. Для него граф интенсивностей переходов будет выглядеть следующим образом рис. 6.:

Рис. 6 Граф переходов для системы с разделением заявки на 2 сервера и ограниченным временем ожидания

Выпишем систему глобального баланса:



4. Аналитические выражения для показателей качества обслуживания систем

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

4.1 Системы без ограничений на время ожидания

4.1.1 Вероятность потери заявки

Рассмотрим систему с ограниченной очередью k и без нетерпеливых требований. Имеем в виду, что новая заявка не поступает на обслуживание, пока не обслужится полностью предыдущая. Поэтому заявка может покинуть систему только в случае, когда очередь равна k [5]. Тогда аналитическое выражение вероятности потери заявки примет вид:

(1)

где - предельное распределение в состоянии , которое мы можем получить, решив системы глобального баланса для каждой модели, а , если это система с разделением заявки на 4 сервера и , если с разделением на 2.

4.1.2 Вероятность немедленного обслуживания

Заявка может сразу же обслужиться в случае, когда в очереди нет требований и все каналы свободны [2]. В нашем случае эта вероятность равна



4.1.3 Среднее время отклика

Из закона Литтла следует, что в долгосрочной перспективе среднее число заявок в системе в стационарном режиме равно произведению среднего времени W (время отклика), которое заявка проводит в системе, на пропускную способность системы .Тогда время отклика системы[2]:

где - абсолютная пропускная способность системы, которую можно найти из формулы Среднее число заявок -- это сумма среднего числа заявок в очереди , и среднего числа заявок на обслуживании [2]:

(3)

Математические ожидания для и в случае разделения заявки на 4 сервера можно найти следующим образом:

В случае разделения на 2 заявки выражения примут вид:



4.2 Системы с ограниченным временем ожидания

4.2.1 Вероятность потери заявки

Теперь рассмотрим систему с ограниченной очередью k и c ограниченным временем ожидания. В данном случае считаем, что заявка поступает в систему, а по истечении установленного времени уходит или же просто не попадает на обслуживание. Тогда аналитическое выражение для вероятности потери требования примет вид [5]:

где - предельное распределение в состоянии , а средняя длина очереди, которую можно найти по формуле (4) или (6) в зависимости от режима обслуживания. Напомним, что , если это система с разделением заявки на 4 сервера и , если с разделением на 2.

4.2.2 Вероятность немедленного обслуживания

Как и в прошлой модели эта вероятность равна



4.2.3 Среднее время отклика

В данном случае также воспользуемся законом Литтла для расчета среднего времени отклика:

где а среднее число заявок в системе находим как сумму (3) и . При этом в случае с разделением на 4 сервера одной заявки используем формулы (4) и (5) для нахождения и соответственно, а для второго случая (6) и (7)

4.3 Аналитические выражения показателей для СМО M|G|1

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

Опять воспользуемся законом Литтла для нахождения времени отклика, но в данном случае формула будет без учета потери заявок:

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

где и - условие существования эргодического распределения.

Запишем выражение для второго момента распределения длительности интервала обслуживания:

4.4 Расчет показателей эффективности моделей из параграфов 2.1. и 2.2

Рассчитаем время отклика в системе с , для СМО M|G|1. Тогда

Среднее число заявок:

Время отклика получаем .

Для аналогичных параметров рассчитаем характеристики среднего времени отклика и среднего числа заявок для СМО из параграфа 2.1., но предположим, что длина очереди ограничена достаточно большим числом , а вероятность потери .

Тогда среднее число заявок , а

Получаем, что при показатели эффективности для данных систем будут совпадать с погрешностью 0,57%. В дальнейшем мы будем исследовать поведение СМО при различных начальных параметрах и с ограничением на очередь.

5. Имитационное моделирование функционирования систем

Для расчета показателей качества СМО часто использует алгоритмы стохастического моделирования.

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

5.1 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 4 сервера

Эргодическая теорема [6]. Пусть матрица интенсивностей перехода марковского процесса неприводима, и - начальное распределение вероятностей. Тогда выполнено

Получаем выражение для расчета средней доли времени, которое система проводит в состоянии

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

- Т достаточно удаленный момент времени.

Теперь запишем теорему, которая связывает распределение процесса в случайные моменты времени и распределение моментов прихода очередного требования в систему:

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

, (12)

то выполняется [7, стр.168]

Поэтому теперь мы можем воспользоваться фактом того, что математические ожидания равны (форм. (12) и (13)), поэтому мы можем рассматривать систему только в моменты прихода очередного требования.

Предположим, что - это индикатор потери n - ого требования в стационарном режиме, а .

Тогда из условия стационарности и предыдущей теоремы [7]:

где - сумма на конечном интервале, а - число требований пришедших на интервале.

Аналогично будем считать вероятность немедленного обслуживания. Тогда

где - сумма на конечном интервале.

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

Теперь можем записать выражение для подсчета оценки средней длины очереди:

где - число требований в очереди в момент прихода - ого требования, а - достаточно большое число моментов изменения числа заявок в системе.

Аналогичным образом будем считать число заявок на обслуживании. В данном случае, когда у нас хотя бы 1 канал все еще обслуживает подзадачу заявки, то будем считать, что в системе 1 заявка. Тогда множество таких состояний Выражение для математического ожидания числа заявок на обслуживании:

Запишем оценку для :

где - число требований на обслуживании в момент прихода - ого требования.

Алгоритм имитационного моделирования

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

На вход подаем длину очереди , интенсивность входящего потока л и среднее время обслуживания заявки . Необходимо посчитать: d - число потерянных требований, count - число заявок в системе, immediate - число заявок, обслуженных сразу же после поступления.



Рисунок. 7 Алгоритм моделирования СМО с разделением заявки на 4 подзадачи

Программный код алгоритма реализован на языке программирования Python, который можно посмотреть в приложении.

5.2 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 2 сервера

Теперь рассмотрим ситуацию, когда заявка разделяется на обслуживание на 2 сервера, то есть на обслуживании может оказаться уже 2 заявки в 1 момент времени.

В данном случае воспользуемся выводами (12) и (13), а также формулой (14), только теперь будем рассматривать попадания процесса в множество состояний - множество состояний, когда очередь занята. Оценку для вероятности немедленного обслуживания находим по формуле (15).

Длину очереди находим аналогично по формуле (16) и также рассматриваем дискретные моменты времени приходов требований.

Для оценки математического ожидания числа заявок в системе следует учесть, что у нас есть две ситуации:

1) Если два канала заняты, то на обслуживании находится одна заявка.

2) Если занято больше 2, то на обслуживании находится две заявки.

С учетом выражения (7) оценку для среднего числа заявок также находим по формулам (17) и (19), как и для случая с разделением на 4 заявки.

Алгоритм имитационного моделирования

Также рассматриваем 100 реализаций алгоритма для .

На вход подаем длину очереди , интенсивность входящего потока л и среднее время обслуживания заявки . Необходимо посчитать: d - число потерянных требований, count - число заявок в системе, immediate - число заявок, обслуженных сразу же после поступления.

Алгоритм моделирования изображен на рис. 8.



Рисунок. 8 Алгоритм моделирования СМО с разделением заявки на 2 подзадачи



5.3 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 4 сервера с нетерпеливыми заявками

Оценка параметров осуществляется так же, как и для системы с 4 серверами без нетерпеливых заявок, за исключением оценки вероятности потери заявки. В данном случае заявка может покинуть систему из очереди, если время ожидания закончилось. Соответственно, мы рассматриваем две ситуации потери требования. Формула для расчета вероятности потери введена ранее (8).

На вход подаем длину очереди , интенсивность входящего потока л, среднее время обслуживания заявки и среднее время ожидания заявки в очереди . Необходимо посчитать: d - число потерянных требований, count - число заявок в системе, immediate - число заявок, обслуженных сразу же после поступления.

Данный алгоритм представляет собой модификацию алгоритма, описанного в пункте 5.1.



Рисунок. 9 Алгоритм моделирования СМО с разделением заявки на 4 подзадачи и нетерпеливыми требованиями

5.4 Алгоритм для оценки показателей эффективности обслуживания в случае разделения заявки на 2 сервера с нетерпеливыми заявками

Оценка параметров осуществляется так же, как и для системы с 2 серверами без нетерпеливых заявок, за исключением оценки вероятности потери заявки. В данном случае заявка может покинуть систему из очереди, если время ожидания закончилось. Соответственно, мы рассматриваем две ситуации потери требования.

На вход подаем длину очереди , интенсивность входящего потока л, среднее время обслуживания заявки и среднее время ожидания заявки в очереди . Необходимо посчитать: d - число потерянных требований, count - число заявок в системе, immediate - число заявок, обслуженных сразу же после поступления.

Данный алгоритм представляет собой модификацию алгоритма, описанного в пункте 5.2.

Рисунок. 10 Алгоритм моделирования СМО с разделением заявки на 2 подзадачи и нетерпеливыми требованиями



6. Анализ результатов численного и имитационного моделирования

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

6.1 Анализ вероятности потери заявки, среднего числа заявок в системе и времени отклика

Система с разделением заявки на 4 подзапроса и конечной очередью из параграфа 2.1.

Рассмотрим систему со следующими начальными условиями: пусть интенсивность входного потока л = 125 заявок в минуту, среднее время обслуживания одной заявки a = 0.07 минуты, длина очереди равна k = 50, 100, 150 и 200. Теперь обозначим - вероятность потери заявки, вычисленная согласно теоретическим результатам, а - вероятность потери заявки, рассчитанная имитационной моделью, а и - математическое ожидания числа заявок в системе соответственно.

Тогда результаты для вероятностей потери заявки и среднего числа заявок в системе:

Таблица 1

Вероятность потери заявки и среднее число заявок в системе для 2 - ух методов моделирования

Длина очереди	50	100	150	200
	0.780573	0.780573	0.780571	0.780571
	0.780538	0.780439	0.780456	0.780436
	50.765642	100.765642	150.765642	200.765642
	50.767791	100.729249	150.664723	200.765642

Для оценки точности вычислений рассчитаем абсолютную и относительную погрешности:

Аналогично считаем для среднего числа заявок в системе. Абсолютная и относительная погрешность результатов вероятности потери заявки представлены на рис. 11 - 12.

Получить относительную погрешность вероятности потери требования имитационной модели можно из условия

, (21)

где нормальная случайная величина c параметрами - выборочная дисперсия величины при [7, стр.284].

Тогда с помощью генератора нормально распределённой величины для реализаций алгоритма рассчитаем величину относительной погрешности среднего в процентах:

Аналогично рассчитаем величину максимальной погрешности числа заявок для , c увеличением k погрешность увеличивается. Следовательно погрешность имитационной модели удовлетворяет погрешности теоретической на основе рис. 13 - 14.

Рассчитаем время отклика и по формуле (2):



Таблица 2

Среднее время отклика для модели из параграфа 2.1. для 2 - ух методов моделирования

Время отклика	50	100	150	200
	1.847451	3.673747	5.496664	7.319581
	1.850831	3.660388	5.459092	7.260566

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

Рисунок 12 Относительная погрешность результатов расчета вероятности потери заявки для системы с разделением заявки на 4 подзапроса

Теперь оценим среднее число заявок в системе для тех же параметров и сравним методы.

Рисунок 13 Абсолютная погрешность среднего числа заявок в системе с разделением заявки на 4 подзапроса

Рисунок 14 Относительная погрешность среднего числа заявок в системе с разделением заявки на 4 подзапроса

Относительные погрешности вычислений двух методов составляют менее 1% и удовлетворяют рассчитанным теоретически. С увеличением мест в очереди время отклика увеличивается равномерно. Из результатов можно сделать вывод, что оба метода с определенной точностью сходятся, и для дальнейшего исследования и оптимизации модели можно использовать алгоритм имитационного моделирования, введенный в параграфе 5.1.

Система с разделением заявки на 2 подзапроса и конечной очередью из параграфа 2.3.

Пусть начальные условия для моделирования будут такие же, как и для предыдущей модели: л = 125 заявок в минуту, a = 0.07 минуты, k = 50, 100, 150 и 200.

Аналогично обозначим: - вероятность потери заявки, рассчитанная теоретическими формулами, а - вероятность потери заявки, рассчитанная имитационной моделью, а и - математическое ожидания числа заявок в системе. Результаты моделирования представлены в табл.3.

Таблица 3

Вероятность потери заявки и среднее число заявок в системе из параграфа 2.3. для 2 - ух методов

Длина очереди	50	100	150	200
	0.608163	0.608163	0.608163	0.608163
	0.608010	0.608157	0.607896	0.608196
	51.464007	101.464007	151.464007	201.464007
	51.587592	101.526602	151.425529	201.275877

Оценим погрешность с помощью теоретических формул. Для вероятности потери , а для , причем для больших она растет.

Результаты для среднего времени отклика и :



Таблица 4

Среднее время отклика для модели из параграфа 2.3. для 2 - ух методов моделирования

Длина очереди	50	100	150	200
	1.050723	2.071557	3.092390	4.113223
	1.051775	2.070698	3.084628	4.086073

Рисунок 15 Абсолютная погрешность результатов расчета вероятности потери заявки для системы с разделением заявки на 2 подзапроса

Рисунок 16 Относительная погрешность результатов расчета вероятности потери заявки для системы с разделением заявки на 2 подзапроса

Рассчитаем абсолютную и относительную погрешности вычислений имитационной модели для вероятности потери требования и среднего числа заявок в системе с помощью формул (20) (рис.15 - 18):

Рисунок 17 Абсолютная погрешность среднего числа заявок в системе с разделением заявки на 2 подзапроса

Рисунок 18 Относительная погрешность среднего числа заявок в системе с разделением заявки на 2 подзапроса

Сравнительный анализ результатов для 2-ух систем

Рассмотрим поведение систем при одинаковых параметрах: , , меняется от 0,015 до 0, 07. На графиках рис.19 - 20 изображены результаты вероятности потери и среднего времени отклика для двух систем:



Рисунок 19 Вероятность потери требования для двух систем из параграфа 2.1. и 2.3., а = [0.015, 0.07]

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

Рисунок 20 Среднее время отклика систем из параграфа 2.1. и 2.3., а = [0.015, 0.07]

Для среднее время отклика для системы с разделением на 4 сервер превышает на более чем 90 % значение времени отклика 2 - ой системы. С увеличением разница между значениями становится меньше, при этом время отклика 2 - ой системы меньше на 70 % времени отклика для 1 -ой системы при .

Теперь проведем сравнение при изменении от 0,07 до 0,7 рис. 21 - 22. Для больших сравнивать системы не имеет смысла, так как стремится к 1.

Рисунок 21 Вероятность потери требования для систем из параграфа 2.1. и 2.3., а = [0.07, 0.7]

При увеличении разница между и уменьшается с 22% при становится равной 2% при. Следовательно, при всех допустимых система с разделением на 2 подзапроса меньше теряет заявки, чем система с разделением на 4 подзапроса.



Рисунок 22 Среднее время отклика систем из параграфа 2.1. и 2.3., а = [0.07, 0.7]

Для всех время отклика для системы с разделением на 2 подзапроса меньше на 71, 8% времени отклика второй системы. Поэтому можно сделать вывод, что время отклика для всех допустимых меньше для системы с разделением на 2 подзапроса.

Система с разделением заявки на 4 подзапроса c нетерпеливыми требованиями из параграфа 3.1.

Рассмотрим систему со следующими начальными условиями: пусть интенсивность входного потока л = 125 заявок в минуту, среднее время обслуживания одной заявки a = 0.07 минуты, среднее время нахождения заявки в очереди b = 0.4 минуты, длина очереди равна k = 50, 100, 150 и 200. Теперь обозначим - вероятность потери заявки, рассчитанная теоретическими формулами, а - вероятность потери заявки, рассчитанная имитационной моделью, а и - математическое ожидания числа заявок в системе.

Результаты моделирования представлены в табл.5.



Таблица 5

Вероятность потери заявки и среднее число заявок в системе из параграфа 3.1. для 2 - ух методов

Длина очереди	50	100	150	200
	0.780571	0.780571	0.780571	0.780571
	0.780596	0.780462	0.780521	0.780652
	39.140542	40.028571	40.028571	40.028571
	38.565363	40.902071	41.080391	41.059336

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

Рисунок 24 Относительная погрешность результатов расчета вероятности потери заявки для системы с разделением заявки на 4 подзапроса с нетерпеливыми требованиями

Оценим абсолютную и относительную погрешность результатов по формуле (20) (рис. 23 - 26) и с помощью формулы (21):

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

Рисунок 26 Относительная погрешность результатов расчета среднего числа заявок для системы с разделением заявки на 4 подзапроса с нетерпеливыми требованиями

Тогда по формуле (21) получаем, что оценка погрешности вероятности потери заявки составляет .

Относительная погрешность среднего числа заявок составляет менее 2,5%, а оценка с помощью формулы (21) равна .

Результаты расчетов среднего времени отклика для начальных параметров и представлены в табл.6:

Таблица 6

Среднее время отклика для модели из параграфа 3.1. для 2 - ух методов моделирования

Длина очереди	50	100	150	200
	1.43064477	1.459375	1.459375	1.459375
	1.41129103	1.489318	1.489318	1.4952228

Относительная погрешность имитационной модели при вычислении среднего времени отклика составляет менее 2,5%.

Система с разделением заявки на 2 подзапроса c нетерпеливыми требованиями из параграфа 3.2.

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

Результаты моделирования представлены в табл.7.:

Таблица 7

Вероятность потери заявки и среднее число заявок в системе из параграфа 3.2. для 2 - ух методов

Длина очереди	50	100	150	200
	0.60817	0.60817	0.60817	0.60817
	0.60777	0.60700	0.60795	0.60792
	32.350428	32.408163	32.408163	32.408163
	33.034258	33.261958	33.261468	33.283710



Рисунок 27 Абсолютная погрешность результатов расчета среднего числа заявок для системы с разделением заявки на 2 подзапроса с нетерпеливыми требованиями

Рисунок 28 Относительная погрешность результатов расчета среднего числа заявок для системы с разделением заявки на 4 подзапроса с нетерпеливыми требованиями

Рассчитаем абсолютную и относительную погрешности вычислений имитационной модели для вероятности потери требования и среднего числа заявок в системе (рис. 27 - 30):

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

Рисунок 30 Относительная погрешность результатов расчета вероятности потери требования для системы с разделением заявки на 2 подзапроса с нетерпеливыми требованиями

Относительная погрешность имитационной модели при расчете вероятности потери заявки составляет менее 0,054% с помощью формулы (20), а для формулы (21) получаем Делаем вывод, что погрешность моделирования выше, чем погрешность теоретическая на 6%. Для среднего числа заявок оценка погрешности составляет , что удовлетворяет полученным результатам рис.28.

Среднее время отклика:

Таблица 8

Среднее время отклика для модели из параграфа 3.2. для 2 - ух методов моделирования

Длина очереди	50	100	150	200
	0.35125911	0.35125911	0.35125911	0.35125911
	0.35502845	0.34995811	0.35457639	0.35486881

Сравнительный анализ результатов для 2-ух систем с нетерпеливыми требованиями

Рассмотрим поведение систем при одинаковых параметрах: , , меняется от 0,015 до 0, 07, . На графиках рис. 31 - 32 изображены результаты вероятности потери и среднего времени отклика для двух систем:

Рисунок 31 Вероятность потери требования для двух систем из параграфа 3.1. и 3.2., а = [0.015, 0.07]

Для вероятность потери для системы с разделением на 2 подзадачи на 90 % меньше вероятности потери 1 системы. С увеличением разница между и уменьшается, где и - вероятности потери для 1 и 2 системы соответственно. При на 22% меньше, чем вероятность .

Для разница уменьшается, но вероятности потери и становятся больше 0,8 в связи с уменьшением интенсивности обслуживания. Поэтому рассматривать большие не имеет смысла. Соответственно, в случае добавления ограничения на время ожидания система с разделением на 2 подзадачи значительно меньше теряет заявки, чем система с разделением на 4 подзадачи.

Рисунок 32 Среднее время отклика для двух систем из параграфа 3.1. и 3.2., а = [0.015, 0.07]

При разница между временем отклика двух систем растет от 70% - 86%, при этом время отклика для 1 - ой системы больше. C увеличением время отклика увеличивается, а разница между двумя системами уменьшается. При время отклика 2 - ой системы на 54% меньше времени отклика 1 - ой системы.

Из результатов анализа следует, что система с разделением на 4 подзапроса менее эффективна, чем система с разделением заявки на 2 подзапроса.

6.2 Анализ вероятности немедленного обслуживания

Системы с разделением запроса на 4 и 2 подзапроса без нетерпеливых требований.

Алгоритм имитационного моделирования был реализован на интервале , а число реализаций алгоритма 100.

Рассмотрим систему со следующими начальными условиями: пусть интенсивность входного потока л = 20 заявок в минуту, среднее время обслуживания одной заявки a = 0.05, длина очереди равна k = 5, 35, 65 и 95. Теперь обозначим - вероятность немедленного обслуживания, рассчитанная численным методом, а - вероятность, рассчитанная численным методом.

Тогда результаты оценки вероятности немедленного обслуживания для системы с разделением на 4 подзапроса будут:

Таблица 9

Вероятность немедленного обслуживания для модели из параграфа 2.1. для 2 - ух методов моделирования,

Длина очереди	5	35	65	95
	0.48060294	0.47916666	0.47916666	0.47916666
	0.48065548	0.47910877	0.47918084	0.47919565

Рассчитаем аналогичную вероятность с теми же параметрами для системы с разделением на 2 подзапроса.



Таблица 10

Вероятность немедленного обслуживания для модели из параграфа 2.3. для 2 - ух методов моделирования,

Длина очереди	5	35	65	95
	0.46576210	0.46575342	0.46575342	0.46575342
	0.47395403	0.47450216	0.47494586	0.47524266

Рисунок 35 Вероятность немедленного обслуживания, системы из параграфов 2.1. и 2.3

Теперь будем изменять параметр среднего времени обслуживания заявки и посмотрим, как будет меняться величина немедленного обслуживания, , :

Из графика нельзя выделить систему, для которой показатель немедленного обслуживания был бы всегда больше. Поэтому обе системы могут быть эффективны при определенных начальных параметрах СМО.

Системы с разделением запроса на 4 и 2 подзапроса с нетерпеливыми требованиями.

Рассмотрим СМО с аналогичными параметрами для входящего потока требований, времени обслуживания и длины очереди, но введем дополнительно среднее время нахождения заявки в очереди минуты.

Результаты для системы с разделением заявки на 4 подзапроса:

Таблица 12

Вероятность немедленного обслуживания для модели из параграфа 3.1. для 2 - ух методов моделирования,

Длина очереди	5	35	65	95
	0.49573936	0.49526022	0.49526022	0.49526022
	0.48306018	0.48270928	0.48253372	0.48203573

Относительная погрешность вычислений для алгоритма имитационного моделирования составила менее 2,5%.

Для СМО с разделением заявки на 2 подзадачи для тех же параметров получим:

Таблица 13

Вероятность немедленного обслуживания для модели из параграфа 3.2. для 2 - ух методов моделирования,

Длина очереди	5	35	65	95
	0.46641781	0.46641284	0.46641284	0.46641284
	0.47548253	0.47546115	0.47531757	0.47563731

Относительная погрешность вычислений для алгоритма имитационного моделирования составила менее 2%.

Рисунок 36 Вероятность немедленного обслуживания, системы из параграфов 3.1. и 3.2

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



Заключение

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

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



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

1. S. Vakilinia, X. Zhang and D. Qiu, "Analysis and Optimization of Big-Data Stream Processing," 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, 2016, pp.1-6

2. Wei Hua Bai, Jian - Qing Xi, Jia - Xian Zhu, Shao - Wei Huang., Performance Analysis of Heterogeneous Data Centers in Cloud Computing Using a Complex Queuing Model, Mathematical Problems in Engineering, vol. June 2015, Article ID 980945

...