Однородность виртуализационных событий, порожденных различными операционными системами
Автор: Маркеева Л.Б., Мелехова А.Л., Тормасов А.Г.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика. Информатика
Статья в выпуске: 3 (23) т.6, 2014 года.
Бесплатный доступ
В облачных инфрастуктурах распределение виртуальных машин между серверами происходит динамически в зависимости от объема и характера потребляемых ресурсов. Для эффективного распределения необходимы как данные о текущей нагрузке, так и возможности предсказывать нагрузку в будущем. Одним из перспективных подходов для данного класса задач является машинное обучение, где решение строится на базе виртуализационных событий, порождаемых низкоуровневыми алгоритмами операционных систем. Недостатком методов машинного обучения является трудоемкость подготовки обучающих выборок. В случае анализа виртуальных машин работа затрудняется большим числом комбинаций. Без явных доказательств нельзя полагать никакие операционные системы, работающими по одним и тем же алгоритмам. Даже конфигурация может существенно влиять на низкоуровневую составляющую поведения системы. Исследования, представленные в данной работе, посвящены сокращению числа проверяемых комбинаций через проверку однородности выборок, порожденных различными системами.
Виртуальная машина, распределение ресурсов, облачные технологии, однородность выборок, машинное обучение
Короткий адрес: https://sciup.org/142186019
IDR: 142186019
Текст научной статьи Однородность виртуализационных событий, порожденных различными операционными системами
Виртуализация ресурсов стала, одной из самых важных тем в ИТ-индустрии в связи с задачей оптимизации ресурсов. Большинство современных рабочих нагрузок имеют пикообразный характер использования ресурсов, когда в основную часть времени потребляется лишь небольшой процент ресурса, но в момент значительной активности этого же объема ресурса перестает хватать, начинаются простои. Для достижения желаемого уровня гибкости все чаще используется виртуализация. Распространенной практикой, повышающей процент утилизации, является назначение виртуальных ресурсов превосходящими реальные аппаратные ресурсы. Этот режим работы получил названия переподписки или переназначения [3]. Для реализации эффективного режима, переназначения необходима, политика. управления ресурсами виртуальных машин, основанная на. принципе «от каждого по способностям, каждому по потребностям», когда, назначение ресурса, пропорционально реальному потреблению, а. не заявленной величине.
Память и процессор (CPU) являются самыми распространенными переназначенными ресурсами, так как их уровень утилизации не очень высок при рабочих нагрузках. В случае избытка, этих ресурсов действия современных операционных систем (ОС) существенно различаются в зависимости от того, какой из ресурсов избыточен. Например, когда. ОС не требует процессорных мощностей, она. посылает сигнал останова, (hit-инструкция) процессору с целью сократить энергопотребление. Системы виртуализации «перехватывают» это событие и точно определяют момент, в который процессорную мощность можно передать другому потребителю. По неиспользуемой памяти Intel х8б архитектура, не поддерживает уведомлений. Если же ОС не использует страницу, то либо этот факт игнорируется, либо ОС, перемещая страницу в кэш, заполняет её заданными в настройках системы числовыми последовательностями (например, нулями). Таким образом, задача, определения реального объёма используемой памяти не может быть осуществлена аппаратными методами.
Обозначим рабочий набор как набор страниц памяти, работа с которыми будет осуществляться потребителем памяти (процессом/виртуальной машиной) в заданный интервал времени [15]. Определение размера рабочего набора не является новой задачей [16-20]. Можно провести аналогию с процессом в операционной системе: виртуальная машина не знает, что пространство ее физических адресов не полно, подобно тому как процесс не знает, что выделенное адресное пространство меньше физической памяти. Доступ к неприсутствующей гостевой физической странице перехватывается управляющим модулем виртуальной машины незаметно для гостевой операционной системы, подобно тому как страничный промах обрабатывается системой прозрачно для процесса. Как процесс зачастую не информирует ОС о необходимом ему объеме памяти, так и гостевая ОС не уведомляет виртуальную машину. Хотя тематика рабочего набора уже основательно проработана (например, фундаментальный труд Деннинга по теме датируется 1970м годом [4]), но виртуализация вносит дополнительное измерение. Если память процесса для ОС априори является черным ящиком, то для виртуальной машины возможно через паравиртуализацию получить информацию о гостевом менеджменте ресурсов или даже «улучшить» код виртуальной машины для лучшей координации с управляющим модулем. Данная работа основана на еще одной альтернативе, использующей статистику по виртуализационным событиям, как отражение процессов, происходящих в гостевой ОС. Эту же статистику можно применить для предсказания пиковых нагрузок. Но для её получения нужно собрать огромный объем обучающих выборок, который тем больше, чем шире круг поддерживаемых ОС и их конфигураций.
2. Паттерны виртуализационных событий
Рассмотрим, что представляют собой виртуализационные события. Главная задача виртуализации с точки зрения производительности - минимизировать накладные расходы, порождаемые технологией. Чем дольше виртуальный процессор будет работать в режиме непосредственного исполнения, чем меньше переключений в управляющий модуль, тем лучше. Однако некоторые инструкции и события виртуального процессора не могут быть исполнены без нарушения целостности хостовой системы, и поэтому их необходимо виртуализовать. Эти опасные события будем здесь и далее называть виртуализационными событиями [5].
Большая часть виртуализационных событий связана с операциями, исполняемыми ядром ОС. Более того, часть из операций однозначно коррелирует со случившимися событиями. Например, из количества различных значений CR3 регистра можно узнать количество процессов на системе. Действительно, каждый процесс в современной операционной системе имеет отдельное адресное пространство, а значит, свое страничное преобразование. В архитектуре Intel х86 корень дерева страничных преобразований хранится в регистре CR3 [6]. Соответственно изменение CR3 говорит о том, что новый процесс был поставлен на исполнение. Другим примером является регистр IA32_FSBASE_MSR, запись в котором свидетельствует о переключении между kernel и user уровнем в Microsoft Windows х64.
Разные операции, происходящие в гостевой ОС, имеют разную потребность в ресурсах. В описанном выше примере с CR3 переключение на новый процесс повлечет за собой обращение к его страницам. Вне зависимости от полезной нагрузки процесса система предоставит ему стек, подгрузит хотя бы одну страницу кода, загрузит дескриптор процессора. Таким образом, можно считать, что количество рабочих CR3 вносит долю в общий рабочий набор.
В работе, представленной на IEEE Cloud [2], приведена эмпирическая проверка гипотезы о корреляции между потреблением ресурсов и виртуализационными событиями. Но исследования были выполнены лишь для одной операционной системы - Microsoft Windows ХР х32 UP. Данная работа призвана оценить, адекватна ли полученная модель для других гостевых ОС.
3. Выбор математического аппарата для оценки однородности выборок
Значительная часть проверок критерия однородностей построена на знании закона распределения анализируемых выборок. Для рассматриваемой задачи такое априори может быть лишь догадкой и, как показано в работе Лео Бреймана [1], может негативно повлиять на результаты исследований. Поэтому в данной работе предполагается, что распределение неизвестно.
Для проверки гипотезы Но: принадлежности выборок одному распределению при неизвестном законе распределения этих выборок применяются непараметрические критерии однородности [10]. Большинство из этих критериев в качестве альтернативной гипотезы используют или гипотезу сдвига, или гипотезу масштаба. Данные гипотезы являются неестественными для рассматриваемой задачи, так как альтернативные гипотезы сдвига и масштаба изначально несут в себе предположение возможного несовпадения алгоритмов ОС. Например, критерий Вилкоксона, один из наиболее часто встречающихся критериев однородности, с гипотезой Но и альтернативной гипотезой сдвига Н1, не всегда позволяет обнаружить различие функций распределения [7].
Наиболее очевидной альтернативной гипотезой является Нц Ғ (ж) = С(ж), т.к. она предполагает совпадение алгоритмов ОС.
В качестве критерия однородности также можно использовать двухвыборочный критерий согласия. Существует класс двухвыборочных критериев согласия, свободных от распределения, в случае проверки простых гипотез [9], [11]:
• критерий Колмогорова-Смирнова,
• критерий Андерсона,
• критерий ш2 [8. 9].
4. Эксперимент4.1. Подготовка обучающих выборок
Гипотеза Но простая [11]. Следовательно, при помощи этих критериев можно проверить гипотезу Но без необходимости знать теоретическое распределение.
Из трех вышеперечисленных критериев наибольшую мощность имеет критерий Андерсона [11], который и был использован для экспериментов, описанных ниже.
В качестве экспериментальной виртуальной машины был выбран Parallels Desktop for Мас. Для сбора необходимых данных код Parallels Desktop был изменен. Конфигурация стенда не влияет на собираемую статистику до момента нехватки памяти. Набор виртуализованных устройств значительно уступает набору реальных, поэтому поведение гостевой ОС не зависит от конкретной модели жесткого диска или сетевой карты. Поколение процессора так же не оказывает существенного воздействия, поскольку большая часть процессорных фунций работает прозрачно для виртуализации, не вызывая виртуализационных событий. Влияние аппаратной виртуализации для нужд теста было преднамеренно ограничено. В данном случае был выбран МасРго 2,1 с 16GB RAM, 2 х Quard-Core Intel Xeon.
Обучающая выборка должна происходить в условиях, максимально приближенных к реальной нагрузке. В данном случае виртуальная машина исполняла одинаковый набор тестов вне зависимости от типа системы.
Тестовый набор состоял из следующих подмножеств.
-
• Множество включений и выключений, периодов неактивности и периодов сна, периодов максимальной загруженности процессора (busy loop).
е Синтетические тесты на переключение между процессами и потоковую многозадачность, на сетевую и дисковую активность, на заполнение большого объема оперативной памяти, вычислительные нагрузки.
• Некоторые нагрузки из «реальной жизни», как то: инсталляции приложений Microsoft Office, работа с документами, графический ЗВ-тест. Этот набор преднамеренно неполон для большей надежности контрольного эксперимента.
4.2. Реализация инструментов для проверки гипотезы однородности4.3. Проверка однородности для 64-битных ОС Windows (Windows 2k8, Windows 7)
Конечная цель описанного набора состояла в том, чтобы симулировать наиболее распространенные рабочие нагрузки. Его выполнение заняло 28 ч, данные о произошедших виртуализационных событиях и о наблюдаемом рабочем наборе собирались каждые 10 с и сохранялись в CSV-формате. В результате выполнения тестового набора была подготовлена выборка размером более 104 пар.
В качестве инструментов для проверки гипотезы однородности использовалась свободная программная среда R, предназначенная для статистических расчетов и работы с графикой, распространяющаяся по лицензии GNU [12].
Для расширения возможностей R использовался дополнительный пакет kSamples — набор ранговых критериев однородности, содержащий в том числе критерий Андерсона [13]. Так же использовался сторонний исходный код для расчета критерия Зигеля-Тьюки [14].
Вывод результатов расчета критериев осуществляется с точностью до б-го знака.
Оценки однородности были выполнены как на выборках, представляющих абсолютную величину используемой физической памяти, так и на выборках, демонстрирующих относительный прирост потребления памяти.
График потребления памяти

Рис. 1
На рис. 1 представлена динамика изменения количества загруженных в рабочий набор страниц памяти (ось ординат) с течением времени (ось абсцис), с шагом 30 с, для операционных систем Win8k2 х64 и Windows 7 х64.
Как видно из графика, алгоритмы ОС по управлению памятью у Win8k2 х64 и Windows 7 х64 визуально различаются.
Результаты расчетов критериев однородности выборок по потреблению памяти
В табл. 1.1 представлены результаты расчетов тестов.
Т а б л и ц а 1.1
Однородность
Название критерия |
р Value |
Однородность |
Wilcoxon |
0 |
Нет |
Siegel-Tukey |
0 |
Нет |
Anderson-Darling |
0 |
Нет |
График роста потребления памяти в выборках

Рис. 2
На рис. 2 представлена динамика относительного роста рабочего набора (ось ординат) с течением времени (ось абсцис) для Win2k8 х64, Windows 7 х64, шаг измерений 30 с. То есть график показывает, сколько страниц было загружено по сравнению с предыдущим измерением.
Результаты расчетов критериев однородности выборок роста потребления физической памяти
В табл. 1.2 представлены результаты расчетов тестов.
Т а б л и ц а 1.2
Однородность
Название критерия |
р Value |
Однородность |
Wilcoxon |
0 |
Нет |
Siegel-Tukey |
0 |
Нет |
Anderson-Darling |
0 |
Нет |
-
4.4. Проверка однородности для 32-битных ОС Windows (Windows 7, Windows ХР)
График потребления памяти

Рис. 3
На рис. 3 представлена динамика изменения количества загруженных в рабочий набор страниц памяти (ось ординат) с течением времени (ось абсцис), с шагом 30 с, для операционных систем Win? х32 и WinXP х32.
Результаты расчетов критериев однородности выборок по потреблению памяти
В табл. 1.3 представлены результаты расчетов тестов.
Т а б л и ц а 1.3
Однородность
Название критерия |
р Value |
Однородность |
Wilcoxon |
2 · 10-9 |
Нет |
Siegel-Tukey |
0 |
Нет |
Anderson-Darling |
0 |
Нет |
График роста потребления памяти в выборках
На рис. 4 представлена динамика относительного роста рабочего набора (ось ординат) с течением времени (ось абсцис) для Win2k8 х64, Windows 7 х64, шаг измерений 30 с. То есть график показывает, на сколько больше страниц было загружено по сравнению с предыдущим измерением.
Результаты расчетов критериев однородности выборок роста потребления физической памяти
В табл. 1.4 представлены результаты расчетов тестов.
Т а б л и ц а 1.4
Однородность
Название критерия |
pValue |
Однородность |
Wilcoxon |
4 . 2 · 10 -5 |
Нет |
Siegel-Tukey |
0 . 228 |
Нет |
Anderson-Darling |
1 · 10 -9 |
Нет |

Рис. 4
5. Вывод
В работе проверена гипотеза об однородности выборок, описывающих потребление физической памяти, в различных версиях ОС Microsoft Windows. Было выдвинуто предположение о том, что близкие по версии ОС одинаковой битности используют схожие алгоритмы работы с памятью (Windows 7 хб4, Windows 2k8 х64). Также было показано, что не произошло принципиальных изменений по отношению к модели работы с памятью и при изменении мажоритарного номера версии (Windows ХР х32, Windows 7 х32). В ходе проведенных экспериментов выяснилось, что выборки неоднородны, и сделан вывод о том, что модели потребления памяти нужно строить отдельно для каждого типа ОС.
Исследование выполнено в рамках договора между Министерством образования и науки РФ и ООО «Параллелс» № 02.G25.31.0054.
Список литературы Однородность виртуализационных событий, порожденных различными операционными системами
- Breiman Leo Statistical Modeling: The Two Cultures//Statistical Science. -2001. -V. 16, N 3. -P. 199-231
- Melekhova Anna Machine Learning in Virtualization: Estimate a Virtual Machine’s Working Set Size//Proceedings of the 2013 IEEE Sixth International Conference on Cloud Computing (CLOUD ’13). IEEE Computer Society. Washington, DC, USA. -2013. -P. 863-870
- VMware white papers. Understanding Memory Resource Management in VMware ESXTM Server. Denning Peter J. Virtual Memory//ACM Comput. Surv. 2, 3 (September 1970). -P. 153-189
- Robin J.S., Irvine C.E. Analysis of the Intel Pentium’s ability to support a secure virtual machine monitor, 2000
- Intel 64 and IA-32 Architectures Software Developer Manual. -http://www.intel.com/content/www/us/en/processors/architectures-software-developermanuals.html
- Орлов А.И. Прикладная статистика: учебник/А.И. Орлов. -М.: Экзамен, 2004. -656 с
- Кобзарь А.И. Прикладная математическая статистика: для инженеров и научных работников/А.И. Кобзарь. -М.: Физматлит, 2006. -816 с
- Лемешко Б.Ю. Мощность критериев согласия при близких альтернативах [Текст]/Б.Ю. Лемешко, С.Б. Лемешко, С.Н. Постовалов//Измерительная техника. -2007. -№ 2. -С. 22-27
- Критерий однородности [Электронный ресурс]. -Режим доступа: http://www.machinelearning.ru (дата обращения: 24.11.2013)
- Проверка статистических гипотез [Электронный ресурс]. -Режим доступа: http://ru.wikipedia.org (дата обращения: 24.11.2013)
- The R Project for Statistical Computing [Электронный ресурс]. -Режим доступа: http://www.r-project.org (дата обращения: 09.12.2013)
- kSamples: K-Sample Rank Tests and their Combinations [Электронный ресурс]. -Режим доступа: http://cran.r-project.org/web/packages/kSamples/index.html (дата обращения: 09.12.2013)
- Sigel-Tukey: a Non-parametric test for equality in variability (R code) [Электронный ресурс]. -Режим доступа: http://www.r-statistics.com/2010/02/siegel-tukey-a-nonparametric-test-for-equality-in-variability-r-code/(дата обращения: 09.12.2013)
- Tanenbaum Andrew Modern Operating Systems Third Edition. -2009. -P. 209-210
- Denning P.J. The working set model for program behavior//Commun. ACM. -1968. -V. 11, N 5
- Denning P.J. Working Sets Past and Present//IEEE Trans. Softw. Eng. -1980. -V 6, N 1 (January 1980). -P. 64-84
- Weiming Zhao, Xinxin Jin, Zhenlin Wang, Xiaolin Wang, Yingwei Luo, and Xiaoming Li Low cost working set size tracking//Proceedings of the 2011 USENIX conference on USENIX annual technical conference (USENIXATC’11). USENIX Association. Berkeley. CA, USA. -2011. -V. 17, N 17
- Working set [Электронный ресурс]. -Режим доступа: http://msdn.microsoft.com/enus/library/windows/desktop/cc441804(v=vs.85).aspx (дата обращения: 09.12.2013)
- Slutz D.R. and Traiger I.L. A note on the calculation of average working set size//Commun. ACM. -1974. -N 10. -P. 563-565