Содержание к диссертации
Введение
ГЛАВА I Обзор существующих математических алгоритмов управления 11
1.1. Планировщик задач, основанный на их приоритетах (PD scheduler) 11
1,1.1 Rate-Monolithic алгоритм 11
1.1.2. EDF (Earliest Deadline First) алгоритм 13
1.2. Планировщик задач, основанный на долях процессорного времени (SD) 15
l.ZL Fair CPU scheduler 16
1.3. Планировщики, основанные на времени (TD) 20
1.4. Другие планировщики 21
1.5. Роль планировщиков. Комбинированные планировщики 27
ВЫВОДЫ ПО ГЛАВЕ 1 36
ГЛАВА 2. Постановка задачи. математическая модель двухуровневого управления 38
2.1. Постановка задачи 38
2.2. Математическая модель двухуровневого управлении 41
2.3. Классификация ресурсов 53
2.3.1. Возобновляемые ресурсы 54
2.3.2. Невозобновляемые и частично возобновляемые ресурсы 61
Выводы по главе 2 64
ГЛАВА 3. Модель и метод двухуровневого управления ресурсами CPU 68
3.1. Построение модели 68
3.2. Алгоритм планирования в Windows 2003 Server . 74
3.3. Экспериментальное подтверждение математической модели 79
Выводы по главе 3 87
Заключение 88
Список использованных источников
- Планировщик задач, основанный на долях процессорного времени (SD)
- Роль планировщиков. Комбинированные планировщики
- Математическая модель двухуровневого управлении
- Алгоритм планирования в Windows 2003 Server
Введение к работе
Актуальность темы
Современные вычислительные мощности позволяют даже на домашнем компьютере производить за считанные минуты расчеты, на которые всего пять-шесть лет назад потребовалось бы несколько часов. Объем оперативной памяти, экономически доступной конечному пользователю, превосходит размеры дисков, стоявших в персональных компьютерах шесть лет назад. В десятки раз выросли и производительность, и объем современных жестких дисков.
И тем не менее в ряде областей, таких как предоставление провайдерских услуг, корпоративном обслуживании клиентов, предоставлять конечному пользователю физически выделенный сервер нецелесообразное 102]:
высокая стоимость аппаратуры серверов
высокие затраты на аренду помещений для размещения серверов
электричество и охлаждение
обслуживание
большое время на развертывание и восстановление нового сервера Размещение нескольких виртуальных серверов на одном физическом
усугубляет проблемы безопасности и обеспечения надлежащего качества обслуживания, важным элементом которого является разграничение ресурсов между виртуальными серверами, таких как различные виды памяти, пропускная способность сети, пропускная способность жесткого диска, время центрального процессора...
Для обеспечения надлежащего качества обслуживания возникает необходимость ограничения потребление ресурсов группами процессов.
В способах разграничения потребления ресурсов наиболее простым является выставление офаничения на всю группу процессов на так называемом микро-уровне - когда управление выполняется на интервалах, сравнимых по величине с минимальными интервалами изменения регулируемого параметра. Как правило, это делается на уровне ядра операционной системы. Таким образом, достигается эффект, при котором все процессы в группе не могут потребить в сумме больше, чем разрешено.
Такой способ является достаточно эффективным, но в ряде случаев не может быть реализован в силу разных причин. Например, для реализации подобного решения может потребоваться вмешательство в ядро операционной системы, что опять-таки в ряде случаев офаниченно как соображениями безопасности, так и некоторыми другими.[109]
Примером реализации подобного рода управления ресурсами может послужить технология Virtuozzo.[108].
Альтернативным решением является наложение офаничений на фуппу процессов на так называемом макро-уровне - когда управление выполняется на интервалах, как правило, превосходящих минимальные интервалы изменения управляемого параметра и осуществляется средствами высокого уровня, опираясь на механизмы, предоставляемые нижним уровнем. Примером такого управления может послужить технология Aurema[107], корректирующая поведение стандартного планировщика Windows 2003 Server с помощью изменения базового приоритета процессов в системе. Однако в этом случае пики потребления ресурсов между такого рода макро-воздействиями могут существенно снизить точность управления[104].
Будем называть двухуровневым управлением управление, удовлетворяющее ниже перечисленным критериям:
1) осуществляет управление, используя механизмы, предоставляемые,
явно или неявно, системой управления нижележащего уровня
(основным управлением ресурсами операционных систем или
микроуправлением) 2) интервалы воздействия этого управления, как правило, превышают
интервалы, характерные для системы управления нижележащего
уровня.
Алгоритмы и методы двухуровневого управления - это новая область в теории управления ресурсами операционных систем. Существующие математические модели не учитывают особенности алгоритмов управления нижнего уровня, что приводит к существенному ухудшению точности управления.
Цель работы, объект и предмет исследования
Цель диссертационной работы - разработка математических моделей и методов двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами.
Задачи исследования:
разработка математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами
объяснение, в рамках данной модели, механизмов существующих методов контроля ресурсов в современных операционных системах
исследование ограничений, которые нужно задать в системе, чтобы обеспечить требуемое качество управления
Объект исследования - механизмы управления ресурсами в современных операционных системах, используемые для предоставления надлежащего качества обслуживания.
Предмет исследования - модель двухуровневого управления ресурсами в современных операционных системах.
Методы исследования
В ходе научных исследований по разработке математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами использовались аналитические методы теории массового обслуживания, теории цифровой фильтрации, методы имитационного моделирования, методы теории операционных систем и системного программирования» методы, используемые в современных системах виртуализации.
Научная новизна
Научная новизна работы заключается в том, что автором предложена математическая модель двухуровневого управления виртуализованными ресурсами вычислительных систем и комплексов при предоставлении различных видов сервиса в современных операционных системах с закрытыми исходными кодами, основанных на формировании виртуальной среды пользователя.
В отличие от ранее существовавших моделей виртуализации, разработанная в ходе диссертационного исследования математическая модель более полно учитывает особенности» налагаемые собственными механизмами управления ОС» что позволяет существенно повысить утилизацию ресурсов системы, повысить ее надежность и обеспечить необходимое качество обслуживания.
Разработанная математическая модель двухуровневого управления виртуализированными ресурсами современных операционных систем с закрытыми исходными кодами является новым вкладом в развитие теории операционных систем, системного программирования и технологий виртуализации операционных систем»
Практическая значимость
Разработанные математические модели могут быть использованы при создании новых программных комплексов, предназначенных для решения задач виртуализации с целью достижения максимального уровня утилизации ресурсов, надежности систем и обеспечения высокого качества
обслуживания.
Также разработанные математические модели и методы могут быть использованы в качестве самостоятельных решений различных задач, возникающих в ходе предоставления различных видов сервиса в современных операционных системах.
Так, математическая модель двухуровневого управления позволяют решить ряд технических проблем, связанных с обеспечением заданного
распределения ресурсов, которое имеет огромное практическое значение для обеспечения бесперебойной работы консолидированных сервисов, используемых как крупными коммерческими и государственными корпорациями, так и образовательными учреждениями.
На сегодняшний день разработанные математические модели двухуровневого управления виртуализованных ресурсов на основе виртуальных сред использованы при создании коммерческого программного продукта Virtuozzo[108], являющегося одним из наиболее популярных решений для создания виртуальных выделенных серверов- На сегодняшний день это решение обеспечивает бесперебойную работу нескольких сот тысяч виртуальных выделенных серверов в десятках стран мира, используемых для предоставления провайдерских услуг, консолидации сервисов в крупных государственных и коммерческих корпорациях, обучения в образовательных учреждениях.
Апробация и реализация результатов работы
По выполненным диссертационным исследованиям опубликовано 11 работ. В опубликованных работах автору принадлежит более 40% материала, связанного с изложением основ математической модели виртуализации ресурсов с использованием виртуальных сред.
Результаты диссертационного исследования докладывались» обсуждались и получили одобрение специалистов на нескольких конференциях: МФТИ 2004-2005 г, Москва [96,98,110], Х-ой Всероссийской научно практической конференции, 2006 г, Анджеро-Судженск [102,100], Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО, 2006 г. Томск [99,103,104] и др.
Также результаты докладывались и получили одобрение специалистов на научных семинарах» проводимых кафедрой информатики МФТИ.
Результаты работы реализованы при создании программного комплекса Virtuozzo[108]. В настоящее время этот программный комплекс занимает лидирующее положение в сфере предоставления услуг виртуализации операционных систем.
Положения, выносимые на защиту
На защиту выносятся следующие основные положения:
1. Математическая модель двухуровневого управления
ресурсами операционных систем с закрытыми исходными
кодами
2. Математическая модель и метод группового управления
ресурсами центрального процессора в условиях
функционирования виртуальных выделенных серверов с
целью ограничения потребления времени центрального
процессора сверху
Планировщик задач, основанный на долях процессорного времени (SD)
В PD алгоритмах планировщик выбирает между более и менее важными задачами и всегда обрабатывает более приоритетные задачи первыми. Это не всегда приемлемо, например, в видеоконференциях в режиме реального времени. Для подобного рода приложений более значительным является пропорциональное выделение ресурсов центрального процессора (процессоров),
SD планировщик основан на GPS (general processor sharing) алгоритме[15,30,61,77], получившем широкое применение не только для процессоров, но и для управления сетевыми пакетами[5,17,20,23],
GPS обрабатывает пакеты, как если бы они находились в различных логических очередях, просматривая каждую непустую очередь и обрабатывая бесконечно малую долю данных в каждой очереди,
В случае с планировщиком задач операционных систем каждой очереди выставляется определенный вес (или определенная доля) и ресурсы выделяются прямо или обратно пропорционально весу очереди. Наиболее известные алгоритмы из этой серии: Weighted Fair Queuing (WFQ)[4,84], Fair CPU Scheduler [5,14,15].,,
К недостаткам SD планировщиков относится невозможность гарантировать непрерывность выполнения задач в режиме реального времени в перегруженных системах. Таким образом, использование GPS алгоритма в системах управления жизнедеятельностью, например, недопустимо.
Другим недостатком, проистекающим из концепции SD, является отсутствие системы приоритетов, что может привести к задержкам на перегруженной системе. Рассмотрим Fair CPU Scheduler подробнее В данном алгоритме планирования время для групп процессов выделяется согласно заранее известным весам.
Основанная идея состоит в следующем (см. рис Л): пусть у нас имеются группы процессов пусть каждая группа процессов имеет хотя бы один процесс Тогда доля процессорного времени, получаемого каждой группой, будет та (1-3) Здесь Wi - вес каждой группы.
Аналогичным образом считается доля времени каждого процесса в группе, относительно времени выделенного всей группе. Рассмотрим пример использования Fair CPU scheduler для планирования. Пусть у нас имеются 2 группы процессов. Группа 1 включает в себя процесс Р1 с весом 1. Группа 2 включает в себя процессы Р2 и РЗ с весами 5 и 6. Тогда Группа 1 получит долю времени CPU равную 1 = 1 1+(5+6) 12 Группа 2 получит долю 5+6 11 1+(5+6) 12 Поскольку Р1 - единственный процесс в группе 1, он получит время CPU равное, согласно (1,3) J_ 12 Процессы Р2 и РЗ поделят свое время согласно (1,3) равное 5 11_ 5 5+6 12 12 и 6 ,,11,6 5+6 12 12 соответственно для Р2 и РЗ. Как уже и упоминалось, FairSchcd алгоритм является разновидностью SFQ алгоритмов [5].
Существует расширенная модель SFQ - PSFQ[99]. Суть модели состоит в следующем - вводятся два основных отличия от оригинальной SFQ модели: каждый процессор подобен своему каналу передачи данных с фиксированной пропускной способностью, и для SMP систем можно подобрать такие веса групп, что нарушается условие пропорциональности выделения ресурсов.
Полная формулировка модели выглядит следующим образом. Каждой группе процессов приписываются два новых параметра: runnabki - максимальное количество процессоров, которое может занять данная группа g, runningi- количество выделенных в данный момент времени процессоров (для группы gj)
Тогда показывается» что: і) В данный момент времени f, когда группе требуется выдать квант времени q4 ее метка старта вычисляется как 5g=min(max(v(0,fg),va)+Mmax, (1.4) Здесь JL W= :-A- (1-5) При этом running увеличивается на единицу, 2) По истечении кванта времени или когда группа освобождает процессор добровольно, метка окончания вычисляется как F„=S„+—U-, (1.6) 4 і w где [tjjj] - последний промежуток исполнения группы и, соответственно, совершенная на этом промежутке работа Щіі4і)-При этом runningg уменьшается на единицу.
Роль планировщиков. Комбинированные планировщики
Планировщик отвечает за выделение системных ресурсов задаче согласно критериям качества обслуживания (QoS)[49,96]. Тем не менее, критерии QoS, как правило, определяются на верхнем уровне и не могут быть напрямую использованы для передачи низкоуровневому планировщику- Для успешной передачи низкоуровневому планировщику, QoS критерии должны быть преобразованы в низкоуровневые атрибуты для передачи планировщику[104].
Например, планировщик разработан для управления задачами на заданном интервале времени, и выбирает задачу с наиболее высоким приоритетом. Тем не менее, планировщик должен знать начало и конец интересуемого временного интервала, и приоритеты задач.
Например, в RM планировщике пользовательское приложение определяет только период и время выполнения для каждой задачи, далее некий сервис промежуточного уровня (между низкоуровневым планировщиком и приложением пользователя) преобразует эти данные во время начала, окончания и приоритет задачи.
В большинстве современных ядер операционных систем сервис промежуточного уровня объединен с низкоуровневым планировщиком в единое целое [28,69].
Тем не менее, существует ряд преимуществ в разделении этих уровней.
Во-первых, написать планировщик низкого уровня гораздо сложнее, чем транслятор QoS параметров, т.к. низкоуровневый планировщик тесно связан со структурами и функциональностью ядра[69]. Если данные уровни разделены, то написание транслятора новых QoS параметров становится гораздо менее трудоемкой задачей, т.к. низкоуровневый планировщик не будет нуждаться в изменениях. Более того, если транслятор выделен из планировщика, это позволяет приложениям делать преобразования самостоятельно, что в ряде случаев может быть полезно.
Приложение даже может производить планирование задач, используя различного рода динамические критерии.
Более того, создание таких приложений позволяет управлять планированием задач в системах, где изменение низкоуровневых планировщиков не возможно по тем или иным причинам, например, в ситуации отсутствия доступа к исходным текстам.
Конечно, управление приложениями, работающими в режиме реального времени не целесообразно, т.к. например, происходит переключение между задачами. Более того, управляющее воздействие транслятора становится более дискретным - по указанной же причине.
Практически очевидно, что если планировщик низшего уровня относится к PD, то у транслятора должен быть приоритет реального времени. При этом наличие задач приоритетами, близкими к приоритету реального времени, не желательно. В противном случае они могут оказать существенное влияние на точность работы транслятора (но не самого низкоуровневого планировщика). Исключение может быть сделано для системных приложений или для приложений, управление которыми не входит в компетенцию транслятора.
Учитывая, что транслятор имеет приоритет реального времени, он не должен пытаться поглотить всё процессорное время, т.к., очевидно, в этом случае теряется его смысл.
Существуют коммерческие приложения, например Aurema [107], работающие указанным выше способом. Данное приложение динамически меняет приоритеты процессам, что позволяет задачам получать гарантированную долю процессорного времени.
В основе математической модели, используемой Aurema [107], лежит [87] фильтра Калмана [94] с активной обратной связью.
Математическая модель двухуровневого управлении
Перейдем к математической модели двухуровневого управления. Введем дополнительное определение. Функция потребления - зависимость потребления процессом одного или нескольких ресурсов от времени. Пусть в операционной системе существуют N процессов. Каждому процессу соответствует желаемая функция потребления (/ ). (2.1) Здесь (-порядковый номер процесса в системе, t - собственное время процесса. Собственное время процесса совпадает с физическим временем в системе, если нет конкурентных задач. В случае, если желаемая функция потребления описывает потребление более одного ресурса, ее можно представить в виде вектора потребления Ri t ) = (Rl( ),Rf(t\.,RJУ)). (2.2) Здесь R?(t ) -потребление 7-ого ресурса i-ым процессом в момент времени t.
Пусть желаемая функция потребления соответствует нескольким ресурсам операционной системы - вектору потребления (CPU, оперативная память, виртуальная память, пропускная способность физического диска или сетевого устройства и так далее).
Мы будем считать, что желаемая функция потребления каждого ресурса принимает 3 значения - процесс потребляет дополнительную единицу ресурса в данный момент времени О - процесс не потребляет дополнительную единицу ресурса в данный момент времени -1 - процесс освобождает занятую единицу ресурса в данный момент времени, Таким образом R/( )c[QA-l}. (2.3)
Например: если процесс потребляет квант времени CPU, то соответствующий компонент вектора потребления равен 1 если процесс не потребляет CPU (ожидает завершение операции ввода-вывода или ожидания на объекте синхронизации), то соответствующий компонент вектора равен О если процесс запросил выделение виртуальной памяти, то мы считаем, что в данный момент времени ему может быть выделена 1 единица памяти операционной системы (соответствие единицы потребления памяти единицам потребления, используемым в операционной системе, может зависеть от алгоритмов управления памятью в данной ОС) и соответствующий компонент вектора потребления, отвечающий за виртуальную память, равен 1 если процесс не запрашивает выделение виртуальной памяти, то мы считаем, что соответствующий компонент вектора потребления, отвечающий за виртуальную память, равен О если процесс освобождает виртуальную память, то мы считаем, что в данный момент времени он может освободить не более 1 единицы виртуальной памяти и соответствующий компонент вектора потребления, отвечающий за виртуальную память, равен -1 легко попять, что для потребления CPU соответствующий компонент вектора потребления не может быть равен -1
Обсудим свойства вектора потребления: его компоненты могут иметь ненулевую ковариацию (например, операция ошибки страницы (page fault) при работе со спроецированным файлом, может привести не только к увеличению потребления физической памяти процессом, но и к потреблению пропускной способности жесткого диска {а если файл находится на сетевом устройстве, то и пропускной способности сети)) компоненты вектора, как уже и упоминалось выше, удовлетворяют условию (2.3) матрица ковариации векторов потребления разных процессов может быть ненулевой (увеличение потребления физической памяти одним процессом может привести к уменьшению потребления физической памяти другим процессом - за счет переноса длительно неиспользуемых страниц памяти в файл подкачки) учет параметров в векторе потребления может зависеть от модели учета ресурсов (например, обращение к жесткому диску, вызванное за счет ошибки страницы (page fault) [29], может быть «записано» как на счет процесса, ее вызвавшего, так и на счет той части системы, которая отвечает за управление памятью. Альтернативным примером может послужить выполнение в системах семейства Microsoft Windows асинхронных вызовов (АРС или DPC [69]), потребление времени CPU которыми записывается «на счет» процессов system и idle соответственно)
Алгоритм планирования в Windows 2003 Server
Рассмотрим данный метод применительно к обеспечению ограничения на потребление времени центрального процессора сверху в однопроцессорной системе под управлением Windows 2003, Windows 2003 использует PD алгоритм планирования задач, т.е. нить с высочайшим приоритетом будет выполняться всегда, при этом учитываются ограничения «привязки» к процессору, которые мы рассмотрим ниже.
Если нить выбрана для выполнения, то она будет выполняться в течение времени, называемом квантом (quantum) [69]. Квант - отрезок времени, в течение которого задача будет выполняться, перед тем как Windows 2003 прервет задачу для поиска другой, с приоритетом равным или более высоким, чем текущий, или для изменения приоритета текущей задачи. Выполнение задачи может быть прервано и продолжено позже, если есть задача с более высоким приоритетом. Так же нить может потребить лишь часть кванта и затем добровольно перейти в режим ожидания,.
Код планировщика задач в Windows 2003 реализован на уровне ядра. Отсутствует единый модуль или программа, код «размазан» по ядру, где соответствующие события и происходят- Процедуры, выполняющие планирование, принято называть диспетчером ядра (kernel dispatcher) [69]. Переключение возникает по одному из следующих событий: 1) Нить становится готовой к выполнению, например, нить была только что создана или вышла из режима ожидания. 2) Нить покидает состояние выполнения по завершению выделенного ей кванта и умирает или переходит в ждущий режим, 3) Приоритет нити меняется из-за системного вызова или решения самой операционной системы. 4) Меняется привязка нити к процессору. Это очень важные свойства и в дальнейшем мы будем активно их использовать. Смена текущей нити называет переключением контекста (context switch).
Другим важным фактом является то, что Windows 2003 планирует нити гранулярно. Планирование осуществляется только на основе нити без относительно какому процессу она принадлежит. Если процесс А имеет 10 нитей и процесс В имеет 2 нити, при этом все нити равного приоритета, каждая нить получит 1/12 процессорного времени - система не выделяет 50% процессу А и 50% процессу В.
Следующим важным фактом, которым мы будем пользоваться, является то, что Windows 2003 имеет 32 уровня приоритетов - от 0 до 31: 16 уровней реального времени (16-31) 15 различных уровней (1-15) один системный уровень (0)
Приоритеты выставляются как с помощью Win32 API, так и непосредственно вызывая функции ядра Windows.
Win32 API выстраивает нити по классам приоритетов, выставленных при создании (Realime, High, Above Normal, Normal, Below Normal, Idle) и за тем по относительному приоритету нити внутри процесса (Time-critical, Highest, Above-normal, Normal, Below-normal, Lowest, Idle),
Таким образом, в Win32 API каждая нить имеет приоритет, состоящий из приоритета класса и относительного приоритета нити. Соотношение между приоритетами Win32 API и приоритетами ядра показано на рисунке ниже [69].
По умолчанию базовый приоритет процесса находится в середине каждого уровня (24,13,10, 8,6,4), Тем не менее, некоторые системные процессы имеют базовый приоритет выше нормального (8) В то время как процесс имеет только базовый приоритет, каждая нить имеет 2 уровня приоритетов - текущий и динамический. При этом Windows 2003 не выставляет динамических приоритетов нитям с приоритетами в диапазоне реального времени (от 16 до 31, см Рисунок 15,)
Как мы уже упоминали, переключение между процессами может произойти по истечении кванта времени. Отметим, что это очень важная величина и ее значение меняется в зависимости от типа операционной системы (так квант по умолчанию в Windows ХР равен 6, в то время как квант в Windows 2003 равен 36), Более высокое значение кванта выбирается для минимизации количества переключения контекста. За счет этого задача, получившая квант времени, имеет очень высокие шансы выполнить свою работу до истечения кванта времени.
Каждый тик системных часов вычитается фиксированное значение (3) из кванта нити, если вычитать нечего, квант заканчивается и происходит переключение на другую нить. Частота тиков системных часов зависит от аппаратной платформы и составляет 10 миллисекунд на IA32, Управление величиной кванта осуществляется через переменную реестра HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\ Win32PrioritySeparation
