Динамическое управление питанием в задаче динамического управления ресурсами вариации планировщика и эксперименты (1187399), страница 4
Текст из файла (страница 4)
Также представляетинтерес вывод предельных зависимостей данных критериев.Введём H, среднее число активных ФМ за n временных шагов:nH=ai1∑ a , гдеn i =1 i— число активных ВМ на соответствующем временном шагеi=1,2, … , n .«Качество» консолидации ВМ обратно пропорционально H:меньшие значения H соответствуют лучшей консолидации. Введём такжеH add- среднее число ФМ, включённых дополнительно за эти n шагов дляобеспечения расположений мигрирующих ВМ:H25addn1= ∑ ( ai −a 1) .n i=1Физический смысл H add - скорость деконсолидации ВМ по целевомудиапазону ФМ в связи с миграциями.Для исследования влияния решений, принимаемых алгоритмамиобнаружения перегруженности, поставим мысленный эксперимент:Пусть в любой шаг времени алгоритм может инициировать миграцию сцелью избежания перегруженности ФМ.
Возможны 2 последствия этогорешения:1. Для расположения выбранной ВМ невозможно найти подходящую ФМ,и, в результате, новая ФМ должна быть активирована с целью расположитьВМ.2. ВМ может быть расположена на активной в данный момент ФМ.Уточним, что в данном эксперименте, в отличие от реальных ситуаций,ни одна ФМ не может быть выключена, т.е.
Если ФМ уже была активна впериодi=1,2, … , n , она остаётся активной до n включительно.Пусть p — вероятность последствия 1. Тогда вероятность последствия2— (1-p). Пусть T- случайная величина, описывающая время между 2последовательными миграциями ВМ, инициированными алгоритмом.Ожидаемое число миграций на n временных шагахn, гдеE[T ]E [T ]—ожидаемое время между миграциями. На основании вышесказанного,введёмX ∼B( E n[ T ] , p)- биноминально распределённую случайную переменную,описывающую число дополнительно включённых ФМ за n временныхшагов. Соответственно X , ожидаемое число дополнительно включённыхФМE [ X ]=np. Пусть А — случайная величина, описывающая время,E [T ]которое дополнительная ФМ была активна между шагом 1 и n. Тогда26ожидаемое время[ [ ]]nETE [ A ] = ∑ ( n − (i −1 ) E [ T ] ) p.i=1(3)Просуммируем (*):E [ A ]=[ [ ] ] ( ([ [ ] ] ) [ ] ) (nETpnnpnn+n −−1 E T ⩽1+22ETE[T ]nЗапишем H как:Оценим)(4)n11addH= ∑ ai= ∑ a1 + Hn i =1n i=1ожидаемоезначениеH add .E [ H add ]Очевидно,пропорциональна произведению E[X]E[A]:E[HВвидуadd]∝ 1 E [ X ] E [ A ]⩽ 1nцели2np npnnpn1+=1+n E [T ] 2E [T ] 2 E [T ]E[T ](улучшения)консолидации()ВМ,минимизировать H, следовательно, нужно минимизировать(5)необходимоE [ H add ] .
Из(5) видно, что этого можно добиться только максимизацией E[T].3.4.3. Оптимальный офлайн-алгоритм.Зависимости, доказанные в 3.4.2, позволяют теоретически получитьоптимальныйофлайн-алгоритмопределенияперегруженности,оперирующий «индивидуально» временами между миграциями ВМ. Дляначала, ограничим время в пределах от конца одной миграции до концадругой.Задача может быть сформулирована как оптимизационная:t a ( t m , ut ) → maxto( t m ,u t )⩽M ,t a ( t m , ut )где t a — время инициирования миграции, ut — уровень загруженностиФМ,27to- время, которое ФМ была перегружена, t a— времяактивности ФМ, М — ограничение по OTF-метрике, отвечающая за цельQoS.В выводе офлайн-алгоритма состояние системы известно в любоймоментвремени,следовательно,сконцентрируемсянапоискеоптимизирующего t_m:Алгоритм 1:input: history, Moutput: t_mwhile moment in history:if OTF(m) <= M:return t_m(m)else:drop(m)m=m->prev;Листинг 1.
Оптимальный офлайн-алгоритм определения t m .Алгоритмпроходитпоисторииизмеренийвобратнойпоследовательности, рассчитывая OTF-метрику, сверяя с М , и возвращаяискомое время, в случае успеха.Теорема 1. Алгоритм 1 является оптимальным офлайн-алгоритмом длязадачи определения перегруженности ФМ.Доказательство. Пустьtm- интервал времени внутри [ t 0 , t n ],полученный из алгоритма 1.
Тогда на полуинтервале ( t m , t n ] нагрузка несоответствовала ограничению по OTF M . Ввиду того, что t m — праваяграница [ t 0 , t m ], t m- максимально возможное время, удовлетворяющееограничению задачи, одновременно с этим максимизирующеетребовалось доказать.3.4.4. Марковский алгоритм. Стационарные нагрузки.28t a , что иРезультатыпредыдущихглавдаютвозможностьпостроенияоптимального онлайн-алгоритма определения перегруженности ФМ:сначала на базе имеющегося математического аппарата строится офлайналгоритм,адалее,применяясоревновательнуютеориюонлайн-алгоритмов, происходит построение и анализ онлайн-алгоритма.В качестве математического аппарата будем использовать цепиМаркова, как эффективный механизм работы со случайными процессами.Аппарат марковских цепей исчерпывающе описан в научной литературе[23-27] и широко используется в задачах оптимизации ресурсовыделения иэнергопотребления[1].Для построения Марковского офлайн-алгоритма, работающего саприори известными нагрузками, введём следующие детали в модель ФМ:1)нагрузки стационарны и соответствуют марковости процесса.2)загруженность ФМ, измеренная в дискретные моменты времени,соответствует цепи Маркова с дискретным временем.3)диапазон загруженности CPU ФМ разбивается на N состояний, которыеможно описать полуинтервалами: к примеру, состояние 1 отвечаетвсевозможным уровням загруженности в пределах [0%,10%), состояние 2— [10%,20%) и т.д.На основании введённой модели, зная нагрузки на ФМ, можно,применяя метод максимального правдоподобия, определить матрицупереходных вероятностей:pij =cij, где∑ c ikk=Sc ij - число переходов между состояниямиiи j .Пространство состояний S, формируемое данными полуинтервалами,расширяетсяпространствосостояниемназовёмфинализирующее:29«миграцияS plus.ВМ»-СостояниеA.Результирующее«миграцияВМ»-pN +1, N +1=1 и соответствует инициированию процессамиграции.
Результирующая, расширенная матрица переходов имеет вид:(pnorm… m111… … …0… 1pnorm=p ij ( 1 −m j ) - нормированные,ij), где— вероятность перехода изmjсоответствующего состояния в А. Таким образом, политика управленияпредставляется в виде вероятностей переходов в состояние «миграцияВМ».Оптимизационная задача в такой форме имеет вид:∑ Li →maxi∈ ST m+ LNT m + ∑ Li≤M ,i∈ SгдеLN— ожидаемое время до перехода в состояние А. T mмиграции,M— ограничение по метрике. Решение данной задачи —вектор ( m1, … , m N ) : ВМ мигрирует с вероятностью mi , где iсостояние.- времяПолитикадетерминистична,∀ i ∈1. . N ∃ k ∈ 1..
N :mk =1 →m i=0 .препросчитать ( m1, … , mN ) для- текущееОфлайн-алгоритмразличныхтиповеслипозволяетнагрузок,азатемпользоваться результатами просчёта.3.4.5. Марковский алгоритм. Нестационарные нагрузки.Оптимальный офлайн-алгоритм 3.4.5, очевидно, не подходит дляиспользования в условиях нестационарных нагрузок, которые возникают вреальной IaaS-системе. Однако данный метод позволяет вывести на егооснованииалгоритм,эффективнообрабатывающийнестационарныенагрузки средствами мультиразмерного скользящего окна [28].Соревновательность метода показана экспериментально в работе [20].303.4.6.
Марковский алгоритм. Заключение.Приведённые в 3.4.3-3.4.6 рассуждения предлагают базис дляпостроения эффективного оптимального онлайн-алгоритма определенияперегруженности ФМ с явным заданием ограничения по какой-либо SLAVметрике. Данный алгоритм демонстрирует[28] хорошие результатыадаптации к нестационарным нагрузкам и снижает суммарные затраты намиграции по построению.Реализация и интеграция такого алгоритма в общей задаче DRS-DPM— вопрос дальнейших исследований и работ автора.3.5. Определение недогруженности ФМ.Существуютдостаточносложныестратегиидляподзадачиопределения недогруженности ФМ, однако на практике предлагаетсяиспользовать простое решение, ввиду того, что точное предсказаниенедогруженности менее важно, по сравнению с подзадачей 3.4.
Процессобнаружения недогруженности осуществляется следующим образом.1)ФМ, уровни загруженности которых существенно ниже остальных покакому-либо критерию(среднее, медиана и др.), предлагают глобальномупланировщику все свои ВМ для поиска нового расположения. 2)если такоерасположение найдено, осуществляются миграции, а ФМ переводятся вэнергосберегающие состояния или отключаются. В противном случае ФМостаётся активной.1*)можно также предлагать ВМ для миграции по достижения некоторойстатической нижней границы загруженности, однако это может заметноувеличить число миграций.Применение 1 или 1* является компромисс-движимым: в приоритете кжесткому снижению энергопотребления возможно использование 1*,31однако предлагается использовать 1 с целью поддержания высокого уровняQoS.Диаграммапланировщикомобработкииситуациивзаимодействиянедогруженностисглобальнымлокальнымпланировщикомприведена на рис.
5.Рис. 5. Диаграмма обработки ситуации недогруженности ФМ.3.6. Выбор ВМ.В случае перегруженности ФМ, следующим шагом является выборлокальным планировщиком ВМ для разгрузки ФМ путём живых миграций.В исследовательских работах предлагается 3 варианта решения данной32подзадачи.3.6.1. Выбор ВМ. Случайный выбор.Данная политика подразумевает выбор ВМ на основании равномерноdраспределённой дискретной случайной случайной величины X =U ( 0,|V j|), значения которой индексируют набор ВМ V j, расположенных на ФМ j.3.6.2. Выбор ВМ. Минимальное время миграции.Политика подразумевает миграцию ВМ v, требующую меньшеговремени миграции относительно других ВМ.Живая миграция ВМ — многоэтапный процесс, оценка времениисполнения которого — достаточно сложная задача, описанная в рядеисследований[29-30].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
