Системы с инверсионным обслуживанием и обобщенным вероятностным приоритетом и их применение к оценке показателей эффективности систем распределенных вычислений Мейханаджян Лусине Акобовна

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

Введение

Глава 1. Система обслуживания с инверсионным порядком обслуживания и обобщенным вероятностным приоритетом неограниченной емкости 19

1.1 Описание системы 19

1.2 Стационарные вероятности состояний 22

1.3 Стационарное распределение времени пребывания заявки в системе 40

1.4 Стационарные показатели качества 48

Глава 2. Система обслуживания с инверсионным порядком обслуживания и обобщенным вероятностным приоритетом конечной емкости 52

2.1 Описание системы 52

2.2 Стационарные вероятности состояний 55

2.3 Стационарное распределение времени пребывания заявки в системе 61

Глава 3. Оценка показателей эффективности систем распределенных вычислений с неточной информацией о временах обработки заданий 70

3.1 Общие сведения о системах распределенных вычислений с неточной информацией о временах обработки заданий

3.2 Постановка задачи получения оценок сверху для среднего времени пребывания в одном классе систем с неточной информацией о временах выполнения заданий 75

3.3 Метод получения оценок. Результаты численных экспериментов 77

Заключение 90

Библиография

• Стационарные вероятности состояний
• Стационарное распределение времени пребывания заявки в системе
• Стационарное распределение времени пребывания заявки в системе
• Постановка задачи получения оценок сверху для среднего времени пребывания в одном классе систем с неточной информацией о временах выполнения заданий

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

Актуальность темы.

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

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

Значительный вклад в разработку и анализ классических моделей ТМО связан с именами А.Я. Хинчина, Б.В. Гнеденко, А.А. Боровкова, Д. Кендалла, Д. Литтла, Д. Кокса, В. Смита, Л. Клейнрока,

¹D. G. Feitelson, Workload Modeling for Computer Systems Performance Evaluation. Cambridge University Press, 2015.

²K. Ren, Y. Kwon, M. Balazinska, and B. Howe. Hadoop’s adolescence: A comparative workload analysis from three research clusters. In Technical Report, CMU-PDL-12-106, 2012.

Б.А. Севастьянова, Л. Такача, Ф. Поллачека. Среди современных авторов по ТМО и приложениям в области теории телетрафика и анализа производительности инфокоммуникационных систем можно выделить Г.П. Башарина, П.П. Бочарова, В.М. Вишневского, А.Н. Дудина, В.А. Наумова, В.А. Ивницкого, И.Н. Коваленко, А.В. Печинкина, А.И. Зейфмана, К.Е. Самуйлова, С.Н. Степанова, В.Ю. Королёва, В.Г. Ушакова, И.И. Ци-товича и др.

В некоторых реальных системах распределённых вычислений, как, например, в Hadoop,³ точные времена выполнения заданий на процессорах практически никогда не известны априори. Таким образом, при использовании в этих системах дисциплин обслуживания, ориентированных на время выполнения заданий, необходимо оперировать оценками этого времени, точность которых зависит от конкретной ситуации. В качестве примера можно привести модель MapReduce. Обычно времена выполнения MapReduce заданий заранее неизвестны и для оценки времён используются различные приёмы. Известно, что если в системе дисциплина выбора заявок на обслуживание основывается на информации об остаточных временах выполнения заданий и эта информация неточна, то вместо того, чтобы повысить производительность системы, она может её снизить. Известен ряд работ, посвящённых анализу показателей эффективности функционирования систем с неточной априорной информацией о временах обслуживания заданий (inaccurate job size information) и, в частности, усовершенствованию известных дисциплин обслуживания таким образом, чтобы они были нечувствительны к ошибкам.

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

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

³Уайт, Том. Hadoop. Подробное руководство Hadoop. 2-е. СПб.: Питер, 2013.

⁴A. Verma, L. Cherkasova, and R. H. Campbell, Aria: automatic resource inference and allocation for MapReduce environments, in Proc. of ICAC, 2011.

⁵Matteo Dell’Amico, Damiano Carra, Pietro Michiardi: PSBS: Practical Size-Based Scheduling. IEEE Trans. Computers 65(7): 2199-2212 (2016)

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

Цели и задачи диссертационной работы.

Разработка аналитических методов нахождения оценок показателей эффективности функционирования систем распределённых вычислений с большим разбросом времён выполнения заданий и неточной априорной информацией о длительностях их выполнения на основе моделей СМО M|G|1|r, 0 < г < оо, с дисциплиной инверсионного порядка обслуживания с обобщённым вероятностным приоритетом (LCFS GPP).

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

1. Новая специальная дисциплина обслуживания LCFS GPP, которая является обобщением известных дисциплин: инверсионный порядок обслуживания с прерыванием и без, инверсионный порядок обслуживания с вероятностным приоритетом.

2. Метод анализа вероятностно-временных характеристик системы M|G|1|r, 0 < г < оо, с дисциплиной LCFS GPP, основанный на введении дополнительных переменных - остаточных времён обслуживания.

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

4. Метод оценки среднего времени отклика в системах распределённых вычислений с большим разбросом времён выполнения заданий и неточной априорной информацией о длительностях их выполнения, моделируемых с помощью систем M|G|1 с дисциплиной LCFS GPP.

Научная новизна. Все результаты диссертации являются новыми. По сравнению с известными, в диссертации получены перечисленные ниже результаты.

5. Для анализа показателей эффективности систем распределённых вычислений c большим разбросом времён выполнения заданий и неточной априорной информацией о длительностях их выполнения предложена модель СМО M|G|1|r, 0 < г < оо, в отличие от известных работ, с новой дисциплиной обслуживания LCFS GPP.

6. Для СМО M|G|1|r, 0 < г < оо, с дисциплиной LCFS GPP, являющейся обобщением ряда других известных дисциплин, разработан аналитический метод расчёта основных показателей эффективности - средняя

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

3. Для систем с большим разбросом времён выполнения заданий и неточной априорной информацией о временах их выполнения, применена модель СМО M|G|1 с дисциплиной LCFS GPP, позволяющая по сравнению с дисциплинами FCFS, sbLCFS, PS давать более точную оценку среднему времени отклика.

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

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

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

Обоснованность предположений об использовании СМО M|G|1 для разработки методов повышения эффективности функционирования некоторых систем распределённых вычислений следует из результатов последних исследований в данной области исследований.

Теоретическая и практическая ценность.

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

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

Результаты работы использованы в научно-исследовательских работах, проводимых в РУДН и в Институте проблем информатики ФИЦ ИУ РАН, в том числе в рамках грантов Российского фонда фундаментальных исследований 13-07-00223 “Разработка эффективных алгоритмических методов и программных средств моделирования и расчёта характеристик инфоте-лекоммуникацонных систем на основе систем массового обслуживания с некоторыми особенностями функционирования при обслуживании заявок”

и 15-07-03406 “Создание информационной технологии для поддержки оптимальных решений в системах обработки, хранения и передачи больших объёмов информации, функционирующих в условиях неопределённости”.

Результаты диссертации внедрены в учебный процесс в РУДН при подготовке выпускных работ бакалавров и магистров, обучающихся по направлению “Фундаментальная информатика и информационные технологии”.

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

всероссийской конференции с международным участием “Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем” (Москва, Россия, 2013);

первой научно-практической конференции молодых учёных “Задачи современной информатики” (Москва, Россия, 2014);

второй научно-практической конференции молодых учёных “Задачи современной информатики” (Москва, Россия, 2015);

30-й европейской конференции по математическому и имитационному моделированию (European Conference on Modelling and Simulation, Регенсбург, Германия, 2016);

на научных семинарах в РУДН и в Институте проблем информатики ФИЦ ИУ РАН.

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

Структура и объём диссертации. Диссертация состоит из введения, трёх глав, заключения, трёх приложений и списка литературы. Текст диссертации изложен на 125 страницах, включая 3 приложения. Список литературы содержит 74 наименования.

Стационарные вероятности состояний

Введем обозначение u(s; х) для ПЛС длительности ПЗ, открываемого заявкой длины х. Пользуясь свойствами ПЛС, выпишем выражения для нахождения u{s;x). Рассмотрим события, которые могут наступить после поступления заявки, открывающей ПЗ. Таким образом ПЛС длительности ПЗ u(s; х) равно — e sa;, если до момента х завершения обслуживания заявки на приборе не поступила новая заявка (с вероятностью е Хх); — e st, если в момент времени 0 t х поступила заявка и обе заявки (вновь поступившая заявка и заявка, находящаяся на приборе) покинули систему (плотность вероятности данного события равна Xe xt J do(y,x — і) b{y) dy); о — e stu(s;v), если в момент 0 t х поступила заявка длины у, одна из двух заявок (вновь поступившая заявка или заявка, находящаяся на приборе) покинула систему, а вторая открыла новый ПЗ системы с новой длиной v (с плотностью вероятностей Xe xt j do(v\y,x — t) b(y) dy); о — e stu(s;v)u(s;w), если в момент 0 t х поступила заявка длины у, обе заявки (вновь поступившая заявка и заявка, находящаяся на приборе) остаются в системе и новая длина одной из двух заявок равна -и, а второй — w (плотность вероятности данного события равна Xe xt f[d(v,w\y,x — і) + d (v ,w\y ,х — t)]b(y)dy). о Теперь по формуле полной вероятности получаем следующее уравнение для нахождения ПЛС u(s; х) 00 Г u{s; х) = ai(s,x) + u(s; v) d2(s,x,v) dv + 00 r r + u(s;v)dv u{s;w) a s ,x ,v ,w) dw, (1.22) где Г ai(s,x) = e (s+x)x + Ae"(s+A)t do(y,x - t) b(y) dy; Г d2(s,x,v) = Xe (S+ )ldt do(v\y,x— t)b(y) dy; Г az(s,x,v,w) = Xe ( +s)tdt [d(v,w\y,x — t) + d (v,w\y,x — t)} b(y) dy. о о Отметим, что в простейших частных случаях, решение полученного интегрального уравнения (1.22) можно получить в явном виде. Для численного решения (1.22) в общем случае можно воспользоваться известными численными методами (см., например, [18,28,69]).

Перейдем к нахождению времени пребывания заявки на приборе. Из-за особенностей дисциплины LCFS GPP вновь поступающие заявки с некоторой вероятностью могут выбивать заявку с прибора (на первое место в очереди или из системы). Поэтому время пребывания заявки на приборе посчитаем двумя способами: с учетом прерываний обслуживания и без. Время пребывания заявки на приборе без учета времени прерываний обслуживания

Введем обозначение cp(s; х) для ПЛС времени пребывания заявки длины ж, поступившей на прибор без учета времени прерываний ее обслуживания. Как и в случае ПЛС ПЗ выпишем выражения для нахождения cp(s; ж), пользуясь свойствами ПЛС. То есть рассмотрим события, которые могут произойти с заявкой, поступившей на прибор. Время пребывания заявки на приборе (в терминах ПЛС) равно — e sa;, если до момента х завершения обслуживания заявки на приборе не поступила новая заявка (с вероятностью е Хх); — e st, если в момент времени 0 t х поступила новая заявка и обе заявки (новая заявка и заявка на приборе) покинули систему (с плотностью вероятностей Xe xt j do(y,x — t) b{y) dy); о — e st, если в момент 0 t х поступила заявка длины у выбила ранее обслуживавшуюся заявку из системы, а сама заняла прибор (с плот 00 ностью вероятностей Xe xt j do(v\y,x — t) b(y) dy); о — e stcp(s; w), если в момент 0 t х поступила заявка длины у, изменила длину заявки, обслуживающейся на приборе, на to и покинула систему (с плотностью вероятностей Xe xt j dQ(w\y,x — t) b(y) dy); о — e stcp(s; w), если в момент 0 t х поступила заявка длины у, обе заявки остались в системе и изменили длины, причем вновь поступившая заявка получила новую длину -и, заявка, находящаяся на приборе, - длину w (с плотностью вероятностей Xe xt f[d(v,w\y,x — t) + d (v,w\y,x — t)} b(y) dy).

Уравнение (1.23) есть уравнение Фредгольма 2-го рода. Отметим, что и свободный член &1(S,IE), и ядро b2{s,x,w) интегрального уравнения (1.23) - неотрицательные функции. Как правило, для решения уравнений Фредгольма 2-го рода прибегают к известным численным методам решения интегральных уравнений (см., например, [18,28,69]). В рамках диссертационной работы, будем пользоваться итерационным методом. Возьмем нулевое приближение в качестве начальной итерации. В этом случае имеем возрастающие итерации. При практической реализации этого метода возникают затруднения, поскольку выражение для ядра уравнения (1.23) является весьма сложным и поэтому в каждом конкретном случае необходимо разрабатывать специальный метод решения.

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

Современные платформы распределенной обработки данных и, в частности, MapReduce-вычислений (Hadoop, Spark, Dryad), являются сложными технологиями, состоящими из большого числа программных библиотек, утилит, модулей и т. д. В связи с этим построение математических моделей таких объектов, допускающих аналитический анализ, без введения упрощающих предположений не представляется возможным. Однако введение слишком сильных предположений неизбежно связано с потерей адекватности модели.

В качестве математической модели системы распределенных вычислений Hadoop, к которой применяются полученные в диссертации результаты, была выбрана модель из [10,26]. В [10] система распределенных вычислений Hadoop моделируется в виде системы массового обслуживания1 типа Gloo2 и используется авторами для обоснования эффективности предложенной ими новой дисциплины обслуживания - HFSP3, которая обладает рядом преимуществ перед другими, использующимися в настоящее время дисциплинами. При построении математической модели авторами исполь 1Подобный выбор, отчасти мотивирован тем, что математические методы теории массового обслуживания являются удобными аппаратом для анализа влияния различных особенностей функционирования стохастических моделей инфотелекомцникационных систем на показатели их эффективности [21,22,36,43,46-48,73].

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

Согласно [26] данная дисциплина реализована для Hadoop version 1. зовались следующие предположения4: 1. каждое задание описывается двумя числами: время поступления задания в систему, прогнозное время выполнения задания . В прогнозных временах выполнения заданий наблюдается очень большой разброс; 2. число задач в каждом задании таково, что задание может занять все процессоры одновременно; 3. задачи в одном задании не зависят друг от друга; 4. при прерывании выполнения задания, выполнение составляющих его задач останавливается мгновенно; 5. число процессоров таково, что для любого числа имеющихся в системе заданий может быть выделено одинаковое число процессоров5, процессоры работают с одинаковой и известной скоростью; 6. прерывание задания и расположение данных не влияет на общее время выполнения задания; 7. если прогнозное время выполнения задания равно , то фактическое время выполнения задания равно , причем и связаны соотношением = , где – случайная величина, имеющая ло-гнормальное распределение с параметрами 0 и . Сделаем несколько комментариев о введенных предположениях. Каждое MapReduce задание состоит из фиксированного числа map и reduce задач, причем reduce задачи в общем случае зависят от map задач. Однако, предположение (1), как показано в [10], допустимо в ряде практических случаев. 4Данные предположения приводятся согласно [10]. 5Данное предположение необходимо для обеспечения возможности реализации дисциплины PS. Например, воспользовавшись данными FB09-0 с Facebook от 2009 года6, содержащими информацию о 5894 MapReduce заданиях, можно по методике из [10] получить пары (,), 1 5894. Предположение (7) означает, что времена обслуживания известны не точно, а с ошибкой7. Это предположение соответствует ситуациям, с которыми приходится сталкиваться на практике. Что касается выбора логнормального распределения и мультипликативной модели для связи прогнозного и фактического времени выполнения, то это предположение основывается на результатах работы [26] (см. раздел IV-C). Известны и другие модели для связи прогнозного и фактического времени выполнения, как, например, в [34], однако в численных экспериментах в рамках диссертационной работы они не рассматривались. Как показано в [11, Раздел 3], если дисциплина обслуживания использует прогнозную информацию о временах обслуживания и эта информация неточна (то есть фактическое время выполнения может оказаться как больше, так и меньше прогнозного), то производительность системы может оказаться очень низкой. В качестве примера, как уже было указано во Введении можно привести дисциплины SRPT и FSP, которые при точной прогнозной информации о временах обслуживания поступающих заданий превосходят (по критерию минимума среднего времени пребывания в системе) “справедливую” дисциплину PS. При неточной прогнозной информации дисциплины SRPT и FSP могут сильно проигрывать дисциплине PS. Одной из задач, которая следует из известных работ по данной тематике, является задача разработки дисциплины, которая может “справиться” с неточными временами обслуживания (то есть была лучше дисциплины PS) и при этом

В частности, в среднем прогнозное время выполнения оказывается больше фактического. обеспечивала тот же уровень справедливости, что и PS. Эта задача была частично решена в [11,26]. Разработав имитационную модель системы -Gloo, авторы на численных примерах показывают, что, в указанных выше предположениях, предложенная ими дисциплина8 является более эффективной (с точки зрения среднего времени пребывания заявки в системе и среднего значения для отношения времени пребывания заявки в системе к ее времени обслуживания9), чем дисциплины FCFS, PS, SRPT.

Другая задача связана с получением оценок для среднего времени пребывания (или, по-другому, среднего времени отклика). В аналитических и имитационных моделях систем с неточной прогнозной информацией о временах обслуживания заданий, расчетные значения среднего времени пребывания10 заведомо неточны. Поскольку фактические времена выполнения заданий отличаются от прогнозных, то отличаются и средние времена. В связи с этим возникает вопрос о том, можно ли каким-то образом использовать неточную прогнозную информацию для получения более точных оценок для среднего времени пребывания? Оказывается, что этого можно добиться в случае, когда известно, что распределения прогнозных времен выполнения заданий имеют тяжелый хвост11. Допуская некоторую вольность речи, можно сказать, что на практике это соответствует тому, что времена выполнения заданий могут принимать значения от нескольких секунд до нескольких часов. Эмпирические свидетельства того, что в системах распределенных вычислений типа Hadoop, распределения времен выполнения заданий обладают этим свойством можно найти, например, воспользовав

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

Жирным выделены значения средних времен пребывания в системе №1. Прочерк означает, что при таких комбинациях входных параметров, стационарного распределения (и, значит, стационарного среднего) при данной дисциплине не существует.

Прокомментируем некоторые результаты из табл. 1. При = 0.5 среднее время пребывания в системе №1 при дисциплине PS равно 2, а при дисциплине FIFO равно 2.12. Дисциплина LCFSGPP без порога дает оценку снизу для этого значения, равную 1.95. Введение в дисциплину порога, начиная с которого длины заявок переразыгрываются заново, позволяет получить верхнюю оценку (например, 2.03 при значении порога в 5.2). Изменяя значения порога, можно получать и другие оценки, как снизу, так и сверху.

При = 0.4 видно, что среднее время пребывания в системе №1 при дисциплине PS равно 1.66, а в системе №2 – 2.07. Дисциплина LCFS GPP без порога дает хорошую оценку сверху, равную 1.68. Обратная ситуация с дисциплиной FIFO. Среднее время пребывания в системе №1 при FIFO равно 1.74, а в системе №2 – 2.48. Здесь дисциплина LCFSGPP без порога дает оценку снизу, а не сверху (так как 1.68 1.74), которая является бесполезной. Дисциплина LCFS GPP с порогом равным, например, 7 позволяет получить оценку сверху, равную 1.96.

Особо отметим следующее наблюдение. Как показывают численные эксперименты, при дисциплине LCFS GPP с порогом и небольших значениях среднее время пребывания оказывается меньше, чем при дисциплине LCFSGPP без порога23. Однако при дальнейшем увеличении , среднее время начинает монотонно возрастать.

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

Ниже сформулированы основные результаты диссертации. – Рассмотрена новая специальная дисциплина обслуживания – инверсионный порядок обслуживания с обобщенным вероятностным приоритетом (LCFS GPP), которая является обобщением известных дисциплин: инверсионный порядок обслуживания с прерыванием и без, инверсионный порядок обслуживания с вероятностным приоритетом. – Предложен метод анализа вероятностно-временных характеристик системы MG1r, 0 , с дисциплиной LCFS GPP, основанный на введении дополнительных переменных – остаточных времен обслуживания. – Получены соотношения в виде интегродифференциальных уравнений для анализа и расчета основных показателей эффективности рассмотренных систем – стационарной вероятности потери и недо-обслуживания заявки, стационарного распределения времени ожидания и пребывания в системе.

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

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

Для того, чтобы сравнивать средние времена V1 и г 2 пребывания заявок в системе №1 и системе №2 соответственно, а также иметь возможность проверять неравенства V1 v г 2, необходимо сделать предположение о виде ФР времени обслуживания заявок в системе №1, то есть о распределении G(x). Предположим, что G(x) есть ФР Вейбулла с параметрами формы

Напомним, что здесь под словосочетанием “ФР В(х) имеет тяжелый хвост” подразумевается выполнение для ФР В(х) условия lim oo eEZ[1 — B(z)] = оо для любого є 0. к и масштаба а, то есть д(х) = G (x) = — ( — ) e v"J , х 0. а а

Отметим, что данное предположение о временах выполнения заданий в системах распределенных вычислений подтверждается эмпирическими данными (см., например, [11]). Во всех приводимых далее численных примерах значение а = Г(1 + 1/к) 1. Таким образом, при любом к среднее время обслуживания равно единице. “Тяжесть” хвоста распределения изменялась путем изменения значения параметра к.

Поскольку ФР G(x) известна, то можно вычислить и ФР В(х). Действуя стандартным образом, получаем

Поскольку интеграл входящий в выражение для 2() не превосходит единицы по условию нормировки, то можем записать

Предел Hindoo I\(z) найти сложнее и здесь этим заниматься не будем, поскольку для наших целей этого не требуется. В итоге показано, что при О & 1, є 0 и fc = 1,е 1 ФР B(z) имеет тяжелый хвост Покажем, что и при к = 1иО є 1 также имеет место (3.1). Учитывая, что

Для того, что найти такое значение -и , что V1 v V2 изменим теперь дисциплину обслуживания в системе №2. Вне зависимости от того, какая была ранее использована дисциплина, будем действовать следующим образом. Во-первых будем обслуживать заявки в порядке обратному к поступлению. Далее, каждый раз при поступлении очередной заявки (но после того, как стало известно ее время обслуживания) будем независимо от предыдущей истории функционирования системы заново разыгрывать время обслуживания поступающей заявки и заявки на приборе в соответствии с ФР В(х). Далее поступившую заявку поставим на первое место в очере 18Данное соотношение, согласно [12, Глава 5], позволяет установить количественные составляющие принципа Парето. Если х удовлетворяет (3.2), то это означает, что на (х ) х 100% приходится [1 — (х )] х 100% времени обслуживания и, наоборот, [1 — (х )] х 100% заявок занимают лишь (х ) х 100% обслуживания. ди, а заявку на приборе продолжим обслуживать с новым (остаточным) временем обслуживания.

Описанное правило обслуживания заявок есть частный случай дисциплины LCFS GPP, при котором (,\,) = ()(), а остальные функции, определяющие дисциплину тождественно равны нулю.

Далее показано, что значение среднего времени пребывания в системе №2 при применении такого нового правила обслуживания заявок может удовлетворять ннеравенств зависит от трех параметров: параметра формы , (далее - величины ошибки) и загреравенствам \ 2. Выполнение узки19 системы .

На рисунках 3.3, 3.4, 3.5 и 3.6 представлено поведение значений f5 , и s при различных значениях и , в зависимости от загрузки .

Из рисунка 3.3, например, видно, что если () имеет экспоненциальное распределение (то есть = 1), то неравенства \ 2 выполняются для всех возможных20 значений загрузки. Из рисунка 3.3 также следует интересное наблюдение. Если зафиксировать интенсивность входящего потока, например = 0.9, то при больших значениях величины ошибки уже невозможно рассчитать значение среднего времени пребывания в системе №2, поскольку значение загрузки будет больше 121. При этом в системе №1 стационарный режим существует и дисциплина LCFS GPP позволяет получить хорошую оценку сверху для fs. Для значений 1 наблюдается похожая динамика (см. рисунок 3.4).

Если хвост распределения () в системе №1 становится тяжелее, ситуация меняется. Из рисунка 3.5 следует, что для = 0.9 при наличиисреднее время пребывания в системе №1 при дисциплине PS, 2 – среднее время пребывания в системе №2 при дисциплине PS, – среднее время пребывания в системе в системе №2 при дисциплине LCFS GPP. Распределение () предполагается экспоненциальным ( = 1). Неравенства 1 2 выполнены при любых значениях загрузки. ошибок неравенства 1 2 выполняются не всегда, то есть описанный частный случай дисциплины LCFS GPP не всегда позволяет получать оценку сверху для среднего времени пребывания в системе №1.

Однако для небольших значений , то есть когда распределение () имеет достаточно тяжелый хвост, описанный частный случай дисциплины LCFS GPP никогда не позволяет получать значения удовлетворяющие 1 2 (см. рисунок 3.6). Грубо говоря, постоянное переразыгрывание времени обслуживания поступающей заявки и заявки на приборе приводит Рисунок 3.4 — fs - среднее время пребывания в системе №1 при дисциплине PS, s - среднее время пребывания в системе №2 при дисциплине PS, - среднее время пребывания в системе в системе №2 при дисциплине LCFS GPP. Распределение () “легче” экспоненциального ( = 1.5). Неравенства \ 2 выполнены только при больших значениях величины ошибки к слишком оптимистичным оценкам для среднего времени пребывания.

При других дисциплинах обслуживания (FCFS/LCFS и spLCFS), получаются качественно такие же выводы (см., например, рисунок 3.7 для дисциплины spLCFS).

Воспользовавшись результатами в таблице 1 можно сделать следующий общий вывод: для нахождение значений , удовлетворяющих \ 2 с помощью описанного частного случая дисциплины LCFS Рисунок 3.5 — 1 - среднее время пребывания в системе №1 при дисциплине PS, 2 s - среднее время пребывания в системе №2 при дисциплине PS, - среднее время пребывания в системе в системе №2 при дисциплине LCFS GPP. Распределение () имеет тяжелый хвост ( = 0.9). На 30% заявок приходится 70% времени обслуживания. Неравенства 1 2 выполняются при значениях загрузки, которые зависят от величины ошибки .

GPP необходимо (но не достаточно), чтобы распределение () было таким, чтобы ( ) 0.3222. О том, что этого условия не достаточно свидетельствуют данные численных экспериментом, согласно которым выполнение неравенств 1 2 зависит и от значения нагрузки (см. рисунок 3.8).