Содержание к диссертации
Введение
ГЛАВА 1. Обзор математических моделей планирования процессов 8
ГЛАВА 2. Модель PSFQ пропорционального распределения процессорного времени 45
ГЛАВА 3. Математическая модель жесткого ограничения выделя емых процессорных ресурсов 73
ГЛАВА 4. Модель виртуального процессора 86
Заключение 94
Список иллюстраций 96
Список таблиц 97
Список использованных источников
- Обзор математических моделей планирования процессов
- Модель PSFQ пропорционального распределения процессорного времени
- Математическая модель жесткого ограничения выделя емых процессорных ресурсов
- Модель виртуального процессора
Введение к работе
В диссертационной работе рассматривается задача планирования и распределения вычислительных ресурсов операционной системы (процессорного времени) между группами процессов (пользователями) с учетом следующих требований: пропорциональное распределение ресурсов во времени и гарантированное качество обслуживания; возможность ограничения группы заданной долей ресурса; корректная работа на многопроцессорных системах. Эта задача актуальна для современных систем разделения пользователей и их изоляции.
За последнее десятилетие компьютерные мощности существенно выросли, и современное программное обеспечение уже далеко не всегда использует эти мощности на 100% [1]. Поэтому в последнее время эта задача стала особенно актуальна в связи с развитием систем виртуализации и изоляции компьютерных ресурсов. Виртуализация позволяет запускать на одном физическом сервере несколько виртуальных машин (ВМ) или виртуальных серверов (ВС), и, таким образом, позволяет, например, программное обеспечение с нескольких машин выполнять на одном физическом компьютере (консолидация [2, 3]), более экономно используя имеющиеся мощности . По отчетам аналитических агентств IDC [4] и Gartner [5] рынок систем виртуализации растет огромными темпами и уже к 2009г. будет составлять около 15 миллиардов долларов. Согласно Info World технология виртуализации также признана одной из самой многообещающих технологий 2005 года [6].
Начиная с 2007 года, компания Intel планирует оснащать все свои настольные процессоры технологией VT™ [7] для аппаратной поддержки виртуализации. Аппаратная виртуализация должна повысить производительность таких систем [8], и поэтому, ожидается, что в скором времени каждый настольный компьютер уже изначально будет поставляться с какой-либой системой виртуализции, позволяющей запускать приложения в своих собственных виртуальных средах. Уже сейчас современные свободные дистрибутивы Linux, такие как Fedora [9] и SUSE Linux [10], начинают оснащаться, например, системой виртуализации Хеп [И, 12]. При этом при виртуализации остро встают вопросы распределения ресурсов, их пропорционального планирования и обеспечения. Процессорное время, как ресурс, рассматриваемый в данной работе - не исключение.
Помимо систем виртуализации, вопрос разделения, планирования и гарантирования ресурсов возникает и в самих современных многопользовательских операционных системах (ОС). В современных ОС, таких как Windows и Linux, которые позволяют сотням пользователей одновременно работать и выполнять свои приложения, до сих пор нет адекватных средств для управления ресурсами: памятью, процессором, диском и др. В лучшем случае, эта задача решается на уровне нитей или процессов, что никак не позволяет контролировать конечных пользователей. Дополнительно проблема заключается в различии между всеми этими ресурсами [13-15], что не позволяет эффективно решить задачу единым подходом для всех видов ресурсов одновременно, хотя некоторые попытки в этом направление предпринимались [16-18].
Математическим моделям планирования ресурсов посвящено большое количество работ за рубежом [19-25]. В последнее десятилетие тема активно развивается и в нашей стране [26-28].
Научная и практическая ценность работы.
На примере разработанного комплекса программ продемонстрирована принципиальная пригодность предложенной модели пропорционального планирования групп процессов и модели жестких ресурсных ограничений, включая требуемую корректную поддержку многопроцессорных систем.
Созданный комплекс программ для ЭВМ может служить основой для разработки моделей изоляции пользователей и программ, обеспечивающих количественные и качественные гарантии в обслуживании. Реализация данных моделей внедрена, как составная часть, в продукт OpenVZ [29,30], и ее использование показывает, что они представляют не только научный интерес и задают новые направления в теории планирования процессорных ресурсов, но и успешно решают поставленные перед ними задачи на практике, а именно, позволяют управлять и контролировать потребление процессорных ресурсов различными пользователями или ВС. Вместе данные программные продукты установлены на более чем 8,000 серверов по всему миру и обеспечивают корректную работу и изоляцию более чем 400,000 виртуальных серверов [31].
Разработанные в ходе исследования методы планирования могут быть также адаптированы для управления потоком сетевых данных и дисковым вводом-выводом в случае нескольких устройств — сетевых каналов или дисков (аналог многопроцессорности).
Методы исследования. Для построения основных моделей работы используются теория алгоритмов, методы теории операционных систем и системного программирования, математические методы анализа. Широко используется аппарат математического анализа и ма тематических моделей вычислительных систем.
Для проведения численных исследований предложенные модели реализованы, как составная часть комплекса программ, и проведены эксперименты с использованием модельных и реальных приложений.
Научная новизна.
1. Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов в соответствии с оценками, данными в работе.
2. В дополнение к предыдущей модели, обеспечивающей гарантированную долю процессорного времени, предложена математическая модель и алгоритм, обеспечивающий в рамках этой модели жесткие пределы на потребляемые группой процессов ресурсы. Вместе эти модели позволяют задавать верхний и нижний пределы потребляемых ресурсов.
3. Для внедрения в стандартный планировщик операционной системы указанных моделей планирования разработана и обоснована модель "виртуальных процессоров".
4. На основании предложенных математических моделей разработан соответствующий комплекс программ. Проведены численные эксперименты с его использованием. Проведено сравнение различных планировщиков задач; продемонстрированы особенности многопроцессорных систем с точки зрения планирования процессорных ресурсов.
Содержание и структура диссертации.
Данная диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы. Для удобства чтения работа снабжена оглавлением с указанием страниц в начале работы и списками таблиц и иллюстраций в конце.
Первая глава посвящена обзорному описанию известных моделей планирования процессов. Описывается современное состояние проблемы и перечисляются характерные черты различных моделей. Важным здесь является описание и анализ требуемых свойств, предъявляемых к современным системам и тому, насколько существующие работы отвечают этим требованиям.
Во второй главе вводится определение пропорционального планирования, рассматривается математическая модель пропорционального планировщика групп процессов, позволяющая управлять распределением процессорного времени между группами процессов. В модели делается упор на обязательную корректную работу на многопроцессорных системах и учет особенностей планирования групп процессов. Дается анализ свойств модели и доказательство ее пропорциональности в соответствие с определением. Приводится описание алгоритма на базе модели, анализ сложности данного алгоритма. В конце приводятся результаты численных экспериментов для различных конфигураций и сравнение этих данных с другими моделями планирования.
Третья глава описывает математическую модель жестких пределов на потребляемые ресурсы. Вводится "кредитная" модель потребления ресурсов, указываются ее свойства и оценки задержек, возникающих в системе. Приводится доказательство корректности модели для многопроцессорных систем. В конце приводятся результаты численных экспериментов для различных конфигураций одновременно с пропорциональным планированием и сравнение этих данных с другими моделями планирования.
В заключении указаны основные результаты и выводы диссертации.
Обзор математических моделей планирования процессов
Планировщик — это подсистема ОС, распределяющая ресурс между несколькими потребителями, нуждающимися в нем. В зависимости от алгоритма планирования возможны различные поведения системы в тех или иных случаях.
В реальности ОС управляет приложениями, реагируя на различные события в системе. Таких событий, как правило, всего 5:
1. Пробуждение (wakeup) процесса. При этом процесс переходит из состояния сна в состояние готовности к выполнению. Реально исполняться процесс начинает позднее, когда планировщик выбирает его к исполнению. Важным здесь является свойство вы-тесняемости, более детально описанное ниже в Требовании б к рассматриваемым планировщикам процессов.
2. Засыпание (sleep) процесса. Процесс обратно переходит из состояния готовности к выполнению в состоянии сна. Как правило, процессы засыпают до какого-нибудь внешнего события, например, нажатия кнопки на клавиатуре или получения данных из сети, которое выведет их из сна.
3. Рождение процесса (create). Рождение процесса эквивалентно событию пробуждения нового процесса. Есть, однако и особенность, проявляющаяся в том, что планировщик должен пересчитать доли ресурсов, выделяемые теперь уже п + 1 процессу.
4. Умирание процесса (exit). Аналогично засыпанию процесса с учетом предыдущего замечания.
5. Таймер (timer interrupt). Таймер позволяет ОС контролировать нагрузку на систему и вытеснять приложения, которые исполняются непрерывно слишком долго.
При этом, сами процессы могут быть в одном из следующих состояний: сна (sleeping), готовности к исполнению (active) и исполнения (running) (Рис. 1.1). Последнее состояние реализуется когда процесс получает процессорное время, т.е. планировщик процессов выбирает его на исполнение.
Важно помнить о всех 5 событиях, т.к. многие авторы склонны рассматривать идеализированные планировщики процессов, в которых, например, процессы исполняются непрерывно, никогда не засыпая и не просыпаясь. Такие допущения ведут к непрактичным моделям [27,46-48] и неверным расчетам сложности модели [47].
Необходимо помнить так же, что современные ОС являются вытесняемыми, т.е. ОС может переключать исполнение на другой процесс по таймеру. Следовательно, существует минимальный квант времени, в течение которого процесс не может быть прерван, и это должно быть отражено в оценках модели [49]. Требования, предъявляемые к пропорциональному планировщику
В начале работы были уже частично сформулированы требования, предъявляемые к желаемому планировщику групп процессов. Ниже приводятся все формальные требования, которые, с точки зрения автора, определяют, как должна вести себя современная ОС, способная работать при различных типах нагрузки - от системы реального времени до пользовательской ОС, и соответствующая целям работы. Далее в обзоре существующих моделей указывается соответствие рассматриваемых моделей этим требованиям. Требование 1. Возможность планирования групп процессов.
Самой распространенной стратегией распределения процессорного времени является распределение на основании "веса" или приоритета процесса, т.е. ОС старается выделять больше процессорного времени процессу с большим приоритетом. При этом, например, один низкоприоритетный, с точки зрения администратора, пользователь, запустивший множество процессов, может потреблять больше процессорного времени, чем высокоприоритетный с небольшим количеством процессов1. Последнее замечание на интуитивном уровне показывает, что пользователь, запустивший больше программ, получает больше ресурса, что может использоваться злоумышленником для атаки или для ухудшения качества обслуживания других пользователей.
Модель PSFQ пропорционального распределения процессорного времени
Как правило, пользовательские ОС сами определяют стратегию, на основании которой распределяется процессорное время. Самой распространенной стратегией является распределение процессорного времени на основании "веса" или приоритета процесса, т.е. ОС старается выделять больше процессорного времени процессу с большим приоритетом. При этом, как правило, невозможно сказать наверняка, насколько больше процессорного времени получит один процесс по сравнению с другими. И, что еще хуже, один низкоприоритетный пользователь, запустивший много процессов, может потреблять больше процессорного времени, чем высокоприоритетный с небольшим количеством процессов. Таким образом, задача планирования групп процессов, т.е. планирования, учитывающего приоритеты групп процессов, стандартными планировщиками не решается.
Особенно остро проблема планирования групп процессов стоит в системах виртуализации [11,32,40,89], которые позволяют запускать Виртуальные Сервера (ВС) или Машины (ВМ), т.к. они предоставляют возможность иметь на одном физическом сервере множество виртуальных со своим набором пользователей и процессов. В этом случае возникают не только группы процессов одного пользователя, но и группы процессов отдельного ВС. На рис. 2.1 показана возникающая при этом иерархия сервер-ВС-пользователи-процессы. Эта иерархия естественным образом подводит к идее создания иерархического планировщика процессов операционной системы (ОС) [90,91].
Данная глава посвящена рассмотрению части такого планировщика, а именно, планировщика групп, который позволил бы распределять процессорное время пропорциональным образом (Требования 1, 2). При этом такой планировщик может быть использован как для распределения процессорного времени между ВС, так и между поль зователями. Внутри же самого ВС может быть использован стандартный планировщик ОС, так что при этом будет полностью сохранена семантика существующих систем, с точки зрения пользователей и уже существующих приложений.
Для пропорционального планирования групп процессов (ВС или пользователей) автором разработан специальный SFQ подобный алгоритм (PSFQ), основанный на стандартном [72] и удовлетворяющий сформулированным требованиям. Основное отличие PSFQ модели от стандартной SFQ модели планирования состоит в возможности планировать группы процессов, а не единичный процесс и корректная работа на многопроцессорных системах.
Постановка задачи
Цель данной главы - получение планировщика, позволяющего распределять процессорное время между группами процессов и решающего следующие выше обозначенные проблемы:
1. Требование 1. Возможность планировать группы процессов, а не только единичный процесс. Необходимое требование для планирования процессов пользователей или ВС;
2. Требование 2. Пропорциональное распределение процессорного времени, гарантии в обслуживании. Необходимо для изоляции и обеспечения заданного уровня обслуживания (Service Level Agreement - SLA);
3. Требование 5. Корректная работа на многопроцессорных системах. Как ни странно, далеко не все алгоритмы разрабатывались с мыслью о многопроцессорных системах. Оно и понятно, ведь в системах реального времени для обеспечения гарантий в обслуживании и надежности применяются довольно простые однопроцессорные RISC процессоры с предсказуемыми характеристиками. Однако сейчас, когда почти все современные выпускаемые процессоры поддерживают технологии HyperThreading и Dual Core, поддержка многопроцессорных систем становиться просто необходимой, по крайней мере на серверных и настольных платформах;
4. Приемлемая производительность. Суммарная общая производительность системы должна быть близка к производительности с использованием только стандартного планировщика ОС. Иными словами, алгоритмы планирования должны быть эффективными, масштабируемыми и пропорциональность не должна обеспечиваться за счет существенного уменьшения производительности системы в целом.
Математическая модель жесткого ограничения выделя емых процессорных ресурсов
Стандартные современные планировщики процессов являются консервативными, т.е. выделяют процессорное время всегда, когда есть хоть один процесс способный исполняться. Это означает, что не зависимо от своего приоритета, процесс получит все процессорное время, если в системе больше нет других претендентов. Свойство консервативности, вообще говоря, само по себе полезно и приводит к более полному использованию имеющихся процессорных ресурсов, что увеличивает общую производительность системы. С другой стороны, консервативность приводит к тому, что в случае не загруженности системы, процессы никак не ограничены, что может быть нежелательно в ряде случаев, например, когда процессорное время продается. Еще одним примером возможного использования ограничений является бурно развивающаяся сегодня технология виртуальных серверов [3,12,29,41], в которой с помощью ограничений процессорного времени виртуальные серверы можно было бы делать аналогичными по производительности стандартным машинам.
Таким образом, для полного контроля над выделяемыми ресурсами требуется иметь возможность задавать пределы потребляемого процессорного времени [98], и, соответственно, требуется модификация существующих стандартных и групповых планировщиков.
Данная глава посвящена разработке и анализу такой математической модели ограничений выделяемого процессорного времени, которая позволила бы расширить существующие планировщики.
Цель работы
Целью работы является получение математической модели планировщика групп процессов с жесткими ограничениями сверху на потребляемое каждой группой процессорное время.
Требования, предъявляемые к модели: 1. использование интуитивно понятных параметров для указания ограничений процессорного времени. Примером может являться процент от общей мощности процессоров системы или мощность BMhz; 2. высокая точность ограничений; 3. корректность работы при любых типах нагрузки; 4. корректная работа на многопроцессорных системах. Существующие работы
Существует несколько работ, в которых предпринимаются попытки решить поставленную задачу. Так, в работе [40] данная задача решается следующим образом. Каждой группе процессов gi ставится в соответствие некоторая величина U. Далее задаются правила, в соответствие с которыми эта величина может изменяться: 1. U уменьшается на 1 каждый раз, когда группа д\ активна в момент вызова системного таймера. Таким образом, в среднем величина U уменьшается со скоростью, равной частоте таймера, которую обозначим за Hz. Отметим, что это не эквивалентно уменьшению t{ на 1 каждый раз, когда группа тратит этот промежуток времени, то есть непрерывно исполняется на всем его протяжении; 2. Раз в секунду U увеличивается на некоторую величину tsec; 3. Значение U ограничено снизу и сверху величинами tm{n и tmax ; 4. Группа получает процессорное время при условии U 0.
Можно показать [41], что если и(0) = 0 и если группы непрерывно выполняются, то есть процессы не засыпают и не просыпаются, эта модель действительно ограничивает потребление процессорного времени группы величиной tsec/Hz. Однако, данная модель обладает существенным недостатком. П.1 вышеописанного алгоритма подразумевает стохастическую модель учета потребляемого группой процессорного времени. Очевидно, точность такого учета очень сильно зависит от частоты таймера, и, вообще говоря, существуют виды процессорных нагрузок, при которых данные измерения будут не правильными. А, следовательно, и ограничения, накладываемые данной моделью, могут иметь большую погрешность.
Математическая модель жестких ограничений процессорного времени
Параметры системы и их обозначения принятые в модели: q - квант времени, в течение которого процесс не может быть вытеснен. В современных ОС, как правило, q равно 1 или 10 мс и определяется разрешением системного таймера; t - текущее время. Для обеспечения приемлемого качества пла нирования точность источника времени должна быть существен но больше q, т.е. tn+i — tn С q. В качестве такого источника вре мени удобно использовать процессорные циклы (cpu cycles); N - количество процессоров в системе. Специфичные обозначения, принятые в модели: гд - максимальное выделяемое группе процессорное время в долях от всех процессоров в системе, т.е. гд Є [0,1]. гд — 0 означает, что группа не должна получать процессор совсем, гд = 1 - группа никак не ограничена в потребляемом процессорном времени; сд - "кредит" процессорного времени, позволенного выделить данной группе. В случае сд q группа не должна получать процессорное время, до тех пор, пока ей не выделят следующую часть кредита и сд снова не станет больше q.
Модель виртуального процессора
Концепция виртуальных процессоров [97] состоит в отделении очередей готовых к исполнению процессов от информации о физическом процессоре и информации, связывающей эти две сущности. После этого номер очереди уже не является номером физического процессора, который ее исполняет, и очередь может исполняться на любом физическом процессоре (рис. 4.4). Применительно к системам виртуализации аппаратных платформ идея виртуального процессора не нова [101], однако, в таких системах под виртуальным процессором понимается полное состояние центрального процессора, не имеющее отношение к планированию ресурсов.
При этом возникают ограничения на планирование, а именно, то, что выбираться на исполнение должны только виртуальные процессоры, у которых очередь готовых к исполнению процессов не пуста, и что виртуальный процессор не должен выполняться на нескольких физических, равно, как и один физический процессор не должен обрабатывать более одного виртуального. Выше сказанное можно выразить следующим образом: Введем понятие состояния виртуального процессора: vcpu_statej Є {idle, active, running}, где: idle - означает, что очередь готовых к исполнению процессов виртуального процессора пуста. active - в очереди есть процессы на исполнение running - виртуальный процессор уже работает (т.е. один из его процессов запущен на одном из физических процессоров) Операция планирования.
Обозначим за рсрщ — vcpuj операцию планирования, т.е. событие, при котором на физический процессор с номером і назначается виртуальный процессор с номером j. При этом факт работы vcpuj на физическом процессоре рсрщ будем обозначать функцией-индикатором \{vcPuj Є рсрщ). Модель виртуального процессора подразумевает следующие ограничения по планированию [102]: " ЛІ x(vcPuj Є рсрщ) S 1 Для VA;, т.е. на одном физическом процессоре не может исполняться более одного виртуального. - Наоборот, Y kX(vcPUj Є рсрщ) 1 для Vj, т.е. один виртуальный процессор не может исполняться более, чем на одном физическом. - Как следствие, J i,jX{vcPUj Є рсрщ) NcpUS, где ІУфШ - общее число физических процессоров в системе.
Обратим внимание на следующее:
Утверждение 1. Пользовательские процессы не в состоянии различить физический и виртуальный процессор. Это следует из того
факта, что рассматриваемые ОС являются вытесняемыми и, соответственно, приложение не имеет возможности определить, на каком процессоре исполнится следующая инструкция.
Утверждение 2. Введение виртуальных процессоров не требует изменения ядра, за исключением планировщика, несмотря на то, что код ядра используют номера физического процессора, например, для организации массивов индексированных этим номером. Дело в том, что номер физического процессора в ядре остается корректным, и потому существующий код продолжит работать корректно.
Утверждение 3. Пользовательские процессы, жестко привязанные к конкретным процессорам, не могут отличить ситуацию, когда данная привязка будет осуществляться к виртуальному, а не физическому процессору. Данное утверждение следует из утверждения 1.
Из этих утверждений следует, что внедрение виртуальных процессоров является прозрачным для всей операционной системы и пользовательских приложений, за исключением планировщика ОС.
Свойства МПП с виртуализацией процессоров
Виртуализация процессоров позволяет сохранить важные свойства одноуровневых SMP планировщиков и получить новые, указанные в таблице 4.1.
Как видно из сравнения, авторский МПП сочетает в себе полезные свойства стандартных SMP планировщиков и уже существующих МПП. Заключение
Автором была разработана и успешно реализована система 3-х уровневого МПП из пропорционального планировщика групп, планировщика виртуальных процессоров и оригинального SMP планировщика процессов Linux 2.6 [107]. Получен планировщик, объединяющий в себе положительные свойства существующих SMP и групповых планировщиков, указанные выше, включая изоляцию. Полученный МПП, использующий все три модели, предложенные в работе, удовлетворяет требованиям 1-5,7-9, сформулированным в главе 1.
Можно выделить следующие основные результаты проделанной работы и вытекающие из них выводы:
1. Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов и включает математические оценки точности и задержки в обслуживании, что позволяет использовать эту модель в системах с гарантированным качеством обслуживания.
2. Предложена математическая модель ограничения потребляемого группой процессов процессорного времени. На основании данной модели получены оценки качества обслуживания.
3. Разработана и реализована модель "виртуальных процессоров", позволяющая объединить планировщик групп процессов со стандартным планировщиком операционной системы. Что позволяет получить пропорциональный планировщик процессов со свойствами стандартного планировщика, например, интерактивностью.
4. Предложенные модели реализованы в виде комплекса программ, обеспечивающего количественные и качественные гарантии в обслуживании. Проведены численные исследования свойств предложенных моделей на многопроцессорных системах.
