18
На правах рукописи
Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ДВУХУРОВНЕВОГО УПРАВЛЕНИЯ РЕСУРСАМИ В ОПЕРАЦИОННЫХ СИСТЕМАХ С ЗАКРЫТЫМИ ИСХОДНЫМИ КОДАМИ
Луковников Иван Васильевич
Москва - 2006
Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета)
Научный руководитель: кандидат физико-математических наук Тормасов Александр Геннадиевич
Официальные оппоненты: доктор технических наук профессор Семенихин Сергей Владимирович кандидат физико-математических наук Обернихин Виталий Александрович
Ведущая организация: Институт Автоматизации Проектирования РАН
Защита состоится «___» __________ 2006 года в ___ часов на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (Государственном университете) по адресу: 141700, г.Долгопрудный, Московской обл., Институтский пер. д.6., ауд. 903 КПМ.
С диссертацией можно ознакомиться в библиотеке МФТИ
Автореферат разослан «____» ______________ 2006 г.
Ученый секретарь диссертационного совета К 212.156.02 Федько О.С.
1. Общая характеристика работы
Актуальность темы
В диссертационной работе рассматривается математическая задача планирования и распределения ресурсов между вычислительными задачами в современных операционных системах (ОС) с закрытыми исходными кодами. Задача была поставлена с учетом следующих требований: распределение ресурсов операционной системы согласно соглашению об уровне сервиса (SLA), корректная работа на системе с закрытым исходным кодом (что не позволяет частично или полностью заменить системный механизм планирования и избежать эффектов, вызванных работой данного механизма). Для таких систем решение должно содержать набор ограничений, которые нужно наложить на систему, чтобы обеспечить необходимую точность управления. Задачи такого класса актуальны для современных средств виртуализации операционных систем.
Особенно остро задача распределения ресурсов встала в последние годы, ставшие периодом бурного развития средств виртуализации вычислительных задач и операционных систем. Существующие программные комплексы позволяют создавать на одном физическом сервере несколько десятков, а, в ряде случае, и несколько тысяч виртуальных выделенных серверов (VDS). Наметился также существенный рост интереса гигантов IT индустрии к системам виртуализации: компания Intel активно развивает технологию аппаратной поддержки виртуализации VT, компания AMD продвигает аналогичную технологию Pacifica, ведущие производители программного обеспечения, такие как RedHat, SuSe, Microsoft, уже включили или планируют включить в ближайшие версии своих программных продуктов поддержку виртуализации операционных систе. Подобного рода тенденции позволяют ожидать появления систем виртуализации на каждом современном компьютере в самом ближайшем будущем. К сожалению, существующие системы распределения и планирования ресурсов далеки от совершенства. Если для ОС, основанных на решениях с открытым исходным кодом, эта задача успешно решается в таких проектах как, например, OpenVZ или Xen, то для ОС с закрытым исходным кодом, таких как MS Windows, ситуация практически плачевная - из-за невозможности заменить механизмы планирования ресурсов, используемые, например Windows 2003 Server, разработчики программных комплексов, таких как Aurema, вынуждены искать различные методы управления «поверх» таких механизмов. Более того, недостаточный этих механизмов учет в существующих моделях приводит к значительному ухудшению качества обслуживания и, зачастую, стабильности системы.
Цель работы, задачи исследования
Целью данной диссертационной работы является разработка математической модели двухуровневого управления ресурсами в современных операционных системах с закрытым исходным кодом. Под двухуровневым управлением в рамках данной работы понимается управление, удовлетворяющее критериям:
1) осуществляет управление, используя механизмы, предоставляемые, явно или неявно, системой управления нижележащего уровня (основным управлением ресурсами, предусмотренным создателями данной операционной системы, или микроуправлением)
2) интервалы воздействия этого управления, как правило, превышают интервалы, характерные для системы управления нижележащего уровня.
Задачи исследования:
· разработка математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами
· объяснение, в рамках данной модели, механизмов существующих методов контроля ресурсов в современных операционных системах
· исследование ограничений, которые нужно задать в системе, чтобы обеспечить требуемое качество управления
Объект исследования - механизмы управления ресурсами в современных операционных системах, используемые для предоставления требуемого качества обслуживания.
Предмет исследования - модель двухуровневого управления в современных операционных системах с закрытыми исходными кодами.
В ходе выполнения научных исследований автором был проведен ряд экспериментов, подтверждающих эффективность предложенной модели.
Методы исследования
В ходе научных исследований по разработке математической модели двухуровневого управления ресурсами в современных операционных системах с закрытыми исходными кодами широко использовались аналитические методы теории массового обслуживания, теории цифровой фильтрации, методы имитационного моделирования, теория операционных систем и системного программирования, методы, используемые в современных системах виртуализации.
Для проведения экспериментов предложенная модель была реализована как составная часть программного комплекса Virtuozzo (Windows версия). Так же был проведен ряд экспериментов с использованием реальных программных комплексов от сторонних производителей.
Научная новизна
Научная новизна работы заключается в том, что автором предложена математическая модель двухуровневого управления виртуализованными ресурсами вычислительных систем и комплексов при предоставлении различных видов сервиса в современных операционных системах с закрытыми исходными кодами, основанных на формировании виртуальной среды пользователя.
В отличие от ранее существовавших моделей виртуализации, разработанная в ходе диссертационного исследования математическая модель более полно учитывают особенности, налагаемые собственными механизмами управления ОС, что позволяет существенно повысить утилизацию ресурсов системы, повысить ее надежность и обеспечить необходимое качество обслуживания.
Разработанная математическая модель двухуровневого управления виртуализированными ресурсами современных операционных систем с закрытыми исходными кодами является новым вкладом в развитие теории операционных систем, системного программирования и технологий виртуализации операционных систем.
Практическая значимость
На основе предложенной математической модели была разработана значительная часть системы управления ресурсами в коммерческом программном комплексе Virtuozzo (Windows версия), являющемся мировым лидером в сфере виртуализации операционных систем. На сегодняшний день это решение обеспечивает бесперебойную работу нескольких сот тысяч виртуальных выделенных серверов в десятках стран мира, используемых для предоставления услуг хостинга, консолидации сервисов в крупных государственных и коммерческих корпорациях, обучения в образовательных учреждениях.
Разработанная математическая модель так же может быть использована при создании новых программных комплексов, предназначенных для решения задач виртуализации с целью достижения максимального уровня утилизации ресурсов, надежности систем и обеспечения высокого качества обслуживания.
Так же разработанная модель может быть использована в качестве основы для самостоятельных решений различных задач, возникающих в ходе предоставления различных видов сервиса в современных операционных системах.
Апробация и реализация результатов работы
По материалам данного диссертационного исследования были опубликованы работы [1-10]. В опубликованных работах автору принадлежит материал, связанный с математическими моделями управления виртуализованными ресурсами и их обоснованием (40%-60% объема).
Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях:
· XLVII и XLVIII научной конференциях МФТИ «Современные проблемы фундаментальных и прикладных наук» (Долгопрудный, 2004, 2005)
· X-ой Всероссийской научно практической конференции «Научное творчество молодежи» (Кемерово, 2006)
· Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО (Томск, 2006) и др.
Так же результаты были доложены и получили одобрение на научных семинарах, проводимых кафедрой информатики МФТИ в 2001-2006гг.
Результаты работы реализованы как часть программного комплекса Virtuozzo. В настоящее время этот программный комплекс занимает лидирующее положение в мире в сфере предоставления услуг виртуализации операционных систем.
Положения, выносимые на защиту
На защиту выносятся следующие основные положения:
1. Математическая модель двухуровневого управления ресурсами операционных систем с закрытыми исходными кодами
2. Математическая модель и метод группового управления ресурсами центрального процессора в условиях функционирования виртуальных выделенных серверов с целью ограничения потребления времени центрального процессора сверху
2. Структура и объем диссертации
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и трех приложений. Работа изложена на 110 страницах, содержит 26 рисунков и список использованных источников из 112 наименований в алфавитном порядке.
Содержание работы
Во введении обосновывается актуальность темы, дается исторический обзор исследований, посвященных решаемым в диссертации задачам, формулируются цели исследования и основные результаты, которые выносятся на защиту, обосновывается научная и практическая значимость выполненного исследования.
В главе 1 дан краткий обзор наиболее существенных в настоящее время алгоритмов и групп алгоритмов управления ресурсами в современных операционных системах на примере управления ресурсами центрального процессора. Для каждой группы приведены примеры соответствующих алгоритмов управления ресурсами, рассмотрены их достоинства и недостатки. Далее приведена сводная таблица парадигм планирования, рассмотрена важность алгоритмов планирования для обеспечения надлежащего качества обслуживания. Приведена двухуровневая иерархия алгоритмов планирования в современных операционных системах с закрытыми исходными кодами. Рассмотрены примеры комбинированных планировщиков. Описываются проблемы, связанные с созданием планировщиков каждого уровня, обусловленные как техническими, так и прочими трудностями. Отдельно обсуждаются преимущества реализации алгоритмов планирования на каждом уровне иерархии. Рассмотрены требования, предъявляемые к таким реализациям, приведены примеры реализаций.
Начало главы 2 посвящено проблеме постановки задачи в виде составления общей модели двухуровневого управления и исследования ограничений, которые надо наложить на систему, чтобы обеспечить надлежащую точность управления. Так же вводится понятие двухуровневого управления, и приводятся примеры существующих программных комплексов, реализующих концепцию двухуровневого управления. Далее в главе обсуждаются особенности построения моделей двухуровневого управления и ограничения, связанные с использованием математических моделей, требующих существенных вычислительных ресурсов для их обсчета.
Вторая часть главы 2 посвящена построению математической модели двухуровневого управления.
Вводится понятие функции потребления как зависимости потребления процессом одного или нескольких ресурсов от времени. Далее рассматривается случай, когда в операционной системе существует N вычислительных задач.
Каждой задаче соответствует желаемая функция потребления
,
где
i - порядковый номер задачи в системе
t* - собственное время задачи. Собственное время задачи совпадает с физическим временем в системе, если нет конкурентных задач.
Объясняется, что в случае, если желаемая функция потребления описывает потребление более одного ресурса, ее можно представить в виде вектора потребления
,
где
- потребление j-ого ресурса i-ой задачей в момент времени t*.
Область значений желаемой функции потребления вводится как
Что соответствует:
1 - задача потребляет дополнительную единицу ресурса в данный момент времени
0 - задача не потребляет дополнительную единицу ресурса в данный момент времени
-1 - задача освобождает занятую единицу ресурса в данный момент времени.
Например:
· если задача потребляет квант времени центрального процессора, то соответствующий компонент вектора потребления равен 1
· если задача не потребляет ресурсы центрального процессора (ожидает завершение операции ввода-вывода или ожидания на объекте синхронизации), то соответствующий компонент вектора равен 0
· если задача запросила выделение виртуальной памяти, то мы считаем, что в данный момент времени ей может быть выделена 1 единица памяти операционной системы (соответствие единицы потребления памяти единицам потребления, используемым в операционной системе, может зависеть от алгоритмов управления памятью в данной ОС) и соответствующий компонент вектора потребления, отвечающий за виртуальную память, равен 1