автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическая модель планирования групп процессов с гарантированным качеством обслуживания

На правах рукописи

Коротаев Кирилл Сергеевич

У

Математическая модель планирования групп процессов с гарантированным качеством обслуживания

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва-2006

Работа выполнена на кафедре информатики Московского физико-технического института (государственного университета).

Научный руководитель: кандидат физико-математических наук

доцент

ТОРМАСОВ Геннадий Александрович

Официальные оппоненты: доктор технических наук

профессор

СЕМЕНИХИН Сергей Владимирович

кандидат физико-математических наук ОБЕРНИХИН Виталий Александрович

Ведущая организация: Институт Автоматизации

Проектирования РАН

Защита состоится « » уЬ -I 2006 года в часов

на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская область, г. Долгопрудный, Институтский пер., д. 9.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан « » 2006 года.

Учёный секретарь диссертационного совета К 212Л56.02, кандидат физико-математических наук /~7 Федько О. С.

.ZOOS ft

Общая характеристика

Актуальность темы

В диссертационной работе рассматривается математическая задача планирования и распределения вычислительных ресурсов операционной системы (процессорного времени) между группами процессов (пользователями) с учетом следующих требований: пропорциональное распределение ресурсов во времени и гарантированное качество обслуживания; возможность ограничения группы заданной долей ресурса; корректная работа на многопроцессорных системах. Эта задача актуальна для современных систем разделения пользователей и их изоляции.

Особенно остро задача разделения ресурсов встала в связи с бурным развитием систем виртуализации и изоляции программного обеспечения и операционных систем (ОС). Виртуализация позволяет запускать на одном физическом сервере несколько виртуальных машин (ВМ) или виртуальных серверов (ВС), и, таким образом, позволяет, например, программное обеспечение с нескольких машин выполнять на одном, физическом компьютере более экономно используя имеющиеся мощности. По отчетам аналитических агенств IDC и Gartner рынок систем виртуализации растет огромными темпами, и ожидается, что за 2006 год рост составит более 100%. Начиная с 2007 года компания Intel планирует оснащать все свои настольные процессоры технологией VT для аппаратной поддержки виртуализации. Аппаратная виртуализация повысит производительность систем виртуализации, и ожидается, что в скором времени каждый настольный компьютер уже изначально будет поставляться с какой-либо системой вир-туализции, позволяющей запускать приложения в своих собственных виртуальных средах. При этом при виртуализации остро встают вопросы распределения ресурсов, их планирования и гарантирования. Процессорное время, как ресурс, рассматриваемый в данной работе - не исключение.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

_ОЭ 20|(Гакг^ ¿У?

Помимо систем виртуализации, вопрос разделения, планирования и гарантирования ресурсов возникает и в самих современных многопользовательских ОС. В ОС, таких как Windows и Linux, которые позволяют сотням пользователей одновременно работать и выполнять свои приложения, до сих пор нет адекватных средств для управления ресурсами: памятью, процессором, диском и др. В лучшем случае эта задача решается на уровне нитей или процессов, что никак не позволяет контролировать конечных пользователей. Помимо этого проблема заключается в тонком различии между всеми этими ресурсами, что не позволяет эффективно решить задачу единым подходом для всех видов ресурсов сразу.

Математическим моделям планирования ресурсов посвящено большое количество работ за рубежом. В последнее десятилетие тема активно развивается и в нашей стране.

Цель работы

Целью работы является создание для ОС общего назначения (Windows, Linux) единой математической модели планирования процессорного времени со следующими специальными свойствами:

• обеспечение минимально гарантированной доли процессорного времени группе процессов,

• обеспечение ограничения на максимально потребляемое группой процессов время.

Исследуется возможность распределения процессорного времени на базе существующих моделей с использованием виртуального времени и вектора ошибок.

Для анализа качества обслуживания планировщиков предложены методы оценки математических моделей на вносимую задержку в обслуживании и удовлетворение критерия пропорциональности распределения.

Научная новизна

1. Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов в соответствии с оценками, данными в работе.

2. В дополнение к предыдущей модели, обеспечивающей гарантированную долю процессорного времени, предложена математическая модель и алгоритм, обеспечивающий в рамках этой модели жесткие пределы на потребляемые группой процессов ресурсы. Вместе эти модели позволяют задавать верхний и нижний пределы потребляемых ресурсов.

3. Для внедрения в стандартный планировщик операционной системы указанных моделей планирования разработана и обоснована модель "виртуальных процессоров".

4. На основании предложенных математических моделей разработан соответствующий комплекс программ. Проведены численные эксперименты с его использованием. Проведено сравнение различных планировщиков задач; продемонстрированы особенности многопроцессорных систем с точки зрения планирования процессорных ресурсов.

Научная и практическая ценность работы

На примере разработанного комплекса программ продемонстрирована принципиальная пригодность предложенной модели пропорционального планирования групп процессов и модели жестких ресурсных ограничений, включая требуемую корректную поддержку многопроцессорных систем.

Созданный комплекс программ для ЭВМ может служить основой для разработки моделей изоляции пользователей и программ, обеспечиваю-

щих количественные и качественные гарантии в обслуживании. Реализация данных моделей внедрена как составная часть в продукты УкШогго1 и ОрепУЕ2, и ее использование показывает, что модели представляют не только научный интерес и задают новые направления в теории планирования процессорных ресурсов, но и успешно решают поставленные перед ними задачи на практике, а именно позволяют управлять и контролировать потребление процессорных ресурсов ВС. Вместе данные программные продукты установлены на более чем 8,000 серверов по всему миру и обеспечивают корректную работу и изоляцию более чем 400,000 виртуальных серверов.

Разработанные в ходе исследования методы планирования могут быть также адаптированы для управления потоком сетевых данных и дисковым вводом-выводом в случае нескольких устройств — сетевых каналов или дисков (аналог многопроцессорности).

Методы исследования

Для построения основных моделей работы используются теория алгоритмов, методы теории операционных систем и системного программирования, математические методы анализа. Широко используется аппарат математического анализа и математических моделей вычислительных систем.

Для проведения численных исследований предложенные модели реализованы как составная часть комплекса программ, и проведены эксперименты с использованием модельных и реальных приложений.

Аппробация результатов работы

Материалы, отражающие содержание диссертационной работы, опубликованы в работах [1-12]. В опубликованных работах автору принад-

1 Ьир://Лу\у\у. virtuozzo.com

2Нир://орегто.ог£

лежит более 60% материала, связанного с изложением математических моделей управления ресурсами, соответствующими алгоритмами и комплексами программ. Результаты диссертации обсуждены и одобрены спе-4 * циалистами на следующих научных конференциях:

• XLVII и XLVIII научной конференциях МФТИ «Современные проблемы фундаментальных и прикладных наук» (Долгопрудный, 2004, 2005),

• международной конференции «Cluster 2005» (Boston, USA, 2005),

• X всероссийской научно-практической конференции «Научное творчество молодежи» (Кемерово, 2006),

• всероссийской научно-практической конференции посвященной 60-летию ТОИПКРО (Томск, 2006), .

• III международной конференции разработчиков свободных программ на Протве (Обнинск, 2006).

Также основные результаты были доложены и получили одобрение специалистов на следующих научных семинарах:

• Linux Kernel Summit (Ottawa, Canada, 2006),

• LinuxTag (Wiesbaden, Germany, 2006),

• кафедры информатики Московского физико-технического института (государственного университета) (2003-2006гг).

Структура и объём диссертации

Диссертация состоит из введения, четырех глав, заключения и списка использованных источников, включающего 107 наименований. Диссертация изложена на 111 страницах, включает 2 таблицы и 19 рисунков.

Содержание работы

Во введении обосновывается актуальность темы исследования, научная и практическая ценность работы, её научная новизна, кратко излагается содержание и структура диссертации.

В первой главе даётся развёрнутый анализ того, какие требования предъявляются к современным планировщикам процессов. Основные из которых: возможность планирования групп процессов (пользователей, а не одиночных процессов), пропорциональное распределение процессорного времени между группами, обеспечение жестких пределов на потребляемые ресурсы, корректная работа на многопроцессорных (SMP) системах. А в качестве важных параметров качества обслуживания вводится понятие «задержки в обслуживании» (latency) и сложности алгоритма. Приводятся математические оценки задержки и пропорциональности, полученные для идеального планировщика.

Далее в главе дается обзор исследований по теме диссертации и современного состояния проблемы в соответствие с сформулированными требованиями.

Во второй главе рассматривается математическая модель пропорционального планирования процессорных ресурсов. Автором предложена модель называющаяся PSFQ и являющаяся естественным обобщением SFQ модели, разработанной P. Goyal и H. Vin3, на случай SMP планирования групп процессов. Модель вводит два основных отличия от оригинальной модели, первоначально разработанной для планирования сетевых данных: каждый процессор подобен своему каналу передачи данных с фиксированной пропускной способностью и для SMP систем существуют такие веса групп, что условие пропорциональности может нарушаться (недопустимые веса, not feasible).

3Goyat P., Vin H. Ai., Cheng H. Start-Time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks // Proceedings of ACM SIGCOMM'96. - 1996. - Pp. 157-168.

Обозначим за # группу процессов, а за гу£ - ее вес (приоритет), где г € {1,тг}, п - общее число групп. Пусть также ^(^,£2) есть работа, совершенная группой ди или количество процессорного времени, выделенного группе за интервал времени [¿1,^2]- Тогда для идеально пропорционального планировщика процессов каждая группа на некотором интервале времени должна была бы получать свою долю Вг от общего процессорного времени В, равную:

Т.е. выполнялось бы равенство:

= о для vu (1)

Wi Wj

и в простейшем случае Wï(ii,i2) = —

Данное условие, однако, не выполнимо для реальных систем, т.к. не учитывает тот факт, что процессы в системе рождаются и умирают, просыпаются и засыпают, а процессорное время в ОС дискретно - существует минимальный квант времени q, в течение которого процесс не может быть вытеснен. Поэтому пропорциональным планировщиком называется тот, который делает это выражение как можно ближе к нулю.

SFQ модель, как и многие другие модели пропорционального планирования, основывается на модели виртуального времени4, которое вводится как функция v(t), меняющаяся со скоростью равной скорости изменения функции Wk(t)/wk обслуживаемого потока данных, т.е.

±vn\ â 1М.

dt dt Wk

Можно показать, что такая функция v(t) является кусочно-гладкой с производной:

dv(t)

4Zhang L. Virtual clock: A new traffic control algorithm for packet switching // ACM Transactions on Computer Systems. - May 1991. — no. 9(2). — Pp. 101-124.

которая меняется каждый раз при изменении множества активных сессий B(t). Функция v(t) может рассматриваться как некоторое нормализованное количество сервиса, выдаваемое системой обслуживаемым сессиям. Данная функция затем используется для сравнения выданного количества сервиса к-той сессии. Обслуживается в первую очередь та сессия, которая больше всего недополучила сервиса по сравнению с v(t). Вычисление v(t) прямым способом не эффективно, т.к. требует постоянного пересчета суммы весов в выражении (2).

SFQ модель, в качестве базовой, в работе была выбрана не случайно. Во-первых, SFQ модель позволяет вычислять v(t) за время сравнимое с 0(1). Во-вторых, применительно к сетевым потокам данных, SFQ модель предлагает качество обслуживания близкое к теоретическому:

Теорема 1 (О наилучшей пропорциональности планирования5). Рассмотрим класс S планировщиков пакетов данных таких, что для любого интервала времени (¿ъ^г) " любой пары активных потоков данных к и j выполняется условие:

Wk{hM) Wj(tut2)

<Д(М, (3)

и>к ги^

где Б{к,з) не зависит от временного интервала (<1,£г)- Тогда для любого планировщика класса в будет выполняться неравенство:

1 / г шах г тах ч

^^ ^ + ^ )' (4) I \ 11)] )

где Щ** - максимальная длина пакета потока к.

Стандартный БРО алгоритм выбирает на исполнение единичные процессы. Группа процессов отличается в этом плане от единичного процесса тем, что может исполняться сразу на нескольких процессорах. При этом

5Golestani S. J. A self-clocked fair queueing scheme for broadband applications. // Proceedings of IEEE INFOCOM'94. - Jun 1994. - Pp. 636-646.

стандартный SFQ алгоритм никак этого не учитывает. Покажем, как можно его расширить, чтобы он мог использоваться не только для планирования процессов, но и групп процессов.

Для этого каждой группе процессов припишем два новых параметра:

• runnablei — максимальное количество процессоров, которое данная группа может занять. В простейшем случае, это количество готовых к исполнению процессов в группе;

• runningi - количество выделенных группе gi процессоров в данный момент времени.

Существенным здесь является новое ограничение на планирование: runningi < mm(N,runnablei), где N - количество процессоров в системе.

Вес группы wg называется допустимым (feasible) в том, и только в том случае, если:

wg типпаЬ1ед

- ~~, (5)

где R - множество готовых с исполнению групп. Иными словами, вес является допустимым, если группа в состоянии потреблять назначенную ей долю процессорного времени.

В работе показывается, что в случае недопустимых весов нарушается ограниченность роста виртуального времени групп относительно друг друга, что приводит к нарушениям пропорциональности планирования. Получена оценка максимального роста виртуального времени ASmaх, в соответствие с которой модифицируется исходная модель.

Полная PSFQ модель планирования групп процессов, полученная в работе и учитывающая особенности многопроцессорных систем, выглядит следующим образом:

1. В момент времени i, когда группе требуется выдать квант времени q,

ее метка старта вычисляется как

Sg = min^max(u(i),Fff),u(i) + ASmoiji (6)

где

N

ASmax = Q--:—7-Г • (7)

mmk{wk)

При этом значение гиппгпдд увеличивается на 1.

2. По истечение кванта времени или когда группа освобождает процессор добровольно, метка окончания вычисляется как

+ ,8)

Wg

где [i 1, <2] ~ последний промежуток исполнения группы и, соответственно, совершенная на этом промежутке времени работа W(ii,i2)-При этом значение runningg уменьшается на 1.

3. Виртуальное время в системе v(t) вычисляется в зависимости от того, есть ли выполняющиеся задания на процессоре:

Г min(Sg) если есть исполняющаяся группа ^ max{Fg) если процессоры простаивают (idle)

4. Изначально ■и(О) = 0 и Sg = Fg = О

5. Каждый раз, когда в группе просыпается или засыпает процесс, значение параметра runnablei увеличивается или уменьшается на 1 соответственно.

6. Каждый раз, когда нужно принять решение о планировании, выбирается группа с минимальной меткой старта Sg, удовлетворяющая условию:

runningg < min(runnableg, N) (10)

В работе доказан ряд теорем относительно свойств полученной модели. В частности:

Теорема 2 (Оценка пропорциональности для допустимых весов). Для любого временного интервала [ti,t2], на котором две группы fug готовы к исполнению в течение всего интервала, в случае допустимых весов групп выполняется неравенство, устанавливающее следующую максимальную разницу в получаемых группами ресурсах:

Данная теорема аналогична теореме 1 и показывает связь между длинной пакета в сетевых алгоритмах и величиной кванта планировщика процессорного времени.

Теорема 3 (Максимальная задержка в обслуживании). Для PSFQ модели планирования максимальная задержка (latency) в обслуживании группы g не превосходит:

где Я - множество готовых к исполнению групп, а иОд = и>д в случае допустимых весов и

в случае недопустимых весов.

Теорема 4. В РБРСЭ модели для исполняющейся за любой интервал времени [¿1^2] группы / с недопустимым весом го/ выполняется следующее неравенство:

(И)

(12)

Wf(t i,t2)>

runnable,

-(¿2 — h) — latency

(13)

N

Теорема 5 (Сложность РБРО модели). Математическая сложность РЭИС} модели не превосходит 0(1пп) при операциях планирования, просыпания и засыпания группы и 0(п) при создании/удалении группы.

В третьей главе предлагается и анализируется разработанная автором модель жесткого ограничения потребляемого группой процессов процессорного времени. Модель пропорционального планирования, рассматриваемая в предыдущей главе, обеспечивает гарантии на минимально выделяемое группе процессов процессорное время, а именно:

ям

где 0 < 6 < ¿о для некоторого произвольного фиксированного 5о. Так происходит из-за того, что в реальности зачастую не все группы готовы исполняться:

Жд{Ь,1>2) > (¿2 -Ь)-5> =^-(¿2 -¿1) -

Егб

где множество Л - множество готовых к исполнению групп.

Поэтому, для предоставления помимо гарантий еще и верхней границы потребляемого группой д процессорного времени, требуется так же модель ограничения ресурсов, такая что:

№д(Ъ,Ь)<Гд(Ь-Ь), (14)

где гд е [0,1] - максимальная доля всех имеющихся процессорных ресурсов.

•Для этого в модели вводится понятие кредита процессорного времени сд, который позволено выделить данной группе, и, соответственно, модель называется "кредитной". Т.к. минимальный квант времени ОС q, то в случае сд < д группа не должна получать процессорное время до тех пор, пока ей не выделят следующий кредит в момент времени йд, и кредит сд снова не станет больше q. Первоначальный кредит сд = • N. Это позволяет группе сразу перейти в состояние исполнения при пробуждении и

избежать ненужной начальной задержки в обслуживании, что важно для интерактивных приложений.

В работе также предлагается оценка времени dg - момента времени t, до которого группа д не должна получать процессорное время в случае, если ее кредит исчерпан. Это существенно, т.к. позволяет снизить вычислительные затраты на модельные расчеты. А условие (7) PSFQ модели гарантирует корректную работу этих двух моделей вместе, ведь ограничение группы может приводить к недопустимым весам с точки зрения пропорционального планирования.

При переходе из состояния выполнения в момент времени ¿2 в любое другое состояние, нужно увеличить кредит сд в соответствие с прошедшим временем (с момента предыдущего перехода t%), плюс нужно вернуть неиспользованную часть кванта времени At = q — (t2 — h) (которая сразу же целиком засчитывается при выдаче процессорного времени):

cg(t2) = min (cs(ii) + rgN(t2 - ii) + [д - (i2 - ii)], qN) (15)

В случае, если группа исчерпала свой кредит и не может больше исполняться, то она переводится в новое состояние delayed, в котором она никогда не получает процессорное время. Выйти из этого состояния группа сможет в момент времени dg, когда у нее накопиться достаточно кредита, чтобы исполняться на всех процессорах одновременно:

j . , д ■ runnableg - Cg(t2) , д.

d° = t2 +-VV--(16)

В работе доказан ряд теорем относительно свойств полученной модели. В частности:

Теорема 6. Для любой группы д и интервала [¿i, ¿2] кредитная модель ограничивает потребляемое группой количество ресурса Wg(ti,t2) величиной:

Wgfa^ZrgNfo-tJ + qN

Причем это наименьшая возможная оценка сверху.

Не смотря на то, что данная оценка отличается от исходного условия (14), показано, что дополнительное слагаемое +qN вызвано дискретностью модели и чрезвычайно важно для планирования интерактивных приложений.

Дополнительно показано, что предложенная модель имеет наименьшую теоретически возможную задержку в обслуживании:

Теорема 7. Вносимая кредитной моделью задержка в обслуживании (latency) группы g не превосходит:

Причем это минимальная из возможных оценок сверху.

Теорема 8. Математическая сложность кредитной модели не превосходит, О (Inn), где п - количество групп в состоянии delayed.

В четвертой главе рассматривается модель виртуального процессора. Данная модель позволяет без особых усилий объединить две предложенные выше модели (или любой другой пропорциональный планировщик) со стандартным планировщиком ОС, что позволяет получить комбинированный планировщик, имеющий положительные свойства всех участвующих моделей. Так, использование стандартного планировщика ОС вместе с пропорциональным позволяет:

• сохранить семантику ОС, которая предоставляет возможность менять приоритеты отдельных процессов внутри групп,

' ' • получить планировщик, учитывающий интерактивность процессов,

• получить планировщик, учитывающий аппаратные особенности и разнородность аппаратных средств современных многопроцессорных систем (HyperThreading, multicore, NUMA).

(17)

Идея состоит в разделении информации об очередях процессов ОС на две части — процессорно-зависимую и процессорно-независимую. Процессорно-зависимая информация содержит в себе данные о состоянии физического процессора, а процессорно-независимая о виртуальном (очереди процессов). Благодаря такому разделению становится возможным исполнять виртуальные процессоры (т.е. процессы различных виртуальных процессоров) на различных физических процессорах. Последнее позволяет устранить зависимость решений планировщиков разных уровней, т.к. после того, как выше предложенный пропорциональный планировщик выбрал группу на исполнение, всегда можно выбрать виртуальный процессор, в котором стандартный планировщик ОС уже точно сможет выбрать процесс.

Сформулированы возникающие в модели ограничения на планирование, а именно то, что выбираться на исполнение должны только виртуальные процессоры, у которых очередь готовых к исполнению процессов не пуста, и что виртуальный процессор не должен выполняться на нескольких физических, равно как и один физический процессор не должен обрабаты-

X о

о. ^

1 .10

1 20 1 00 1 0 80 060

ШШШШШШт

^ ^ ^ ^

Накладываемоо ограниченно, 100% < один процессор

-о-Группа! оос 1

Грулпэ 2, оес 2,

10 20 30 40 50 60 70 ВО Ограничение, %

О ОропУг ОХел ОУгсгеег

(а) Пример с двумя группами (по одному процессу) с весами 1 и 2 на двухпроцессорной машине. Вторая группа последовательно ограничивается долей от 0 до 2 процессоров, постепенно вытесняя при этом менее приоритетную группу.

(б) Сравнение точности предложенной модели ограничения группы процессов с двумя другими моделями, реализованными в проектах Хеп и УЭегуег. Группа последовательно ограничивается долей от 0 до 2 процессоров.

Рис. 1. Совместная работа 3-х предложенных моделей,

вать более одного виртуального.

На рис. 1 приведены некоторые результаты численных экспериментов на SMP системе, демонстрирующие: а) корректную работу внедренных в стандартный планировщик ОС Linux алгоритмов на базе разработанных математических моделей; б) высокую точность предложенной модели ограничения потребляемого группой процессов процессорного времени по сравнению с двумя другими доступными реализациями.

В заключении указаны основные результаты и выводы диссертации.

Основные результаты и выводы диссертации

1. Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов и включает математические оценки точности пропорциональности и задержки в обслуживании.

2. Предложена математическая модель ограничения потребляемого группой процессов процессорного времени. На основании данной модели получены оценки качества обслуживания.

3. Разработана и реализована модель "виртуальных процессоров", позволяющая объединить планировщик групп процессов со стандартным планировщиком ОС.

4. Предложенные модели реализованы в виде комплекса программ, обеспечивающего количественные и качественные гарантии в обслуживании. Проведены численные исследования свойств предложенных моделей на многопроцессорных системах.

Список публикаций по теме диссертации

1. Коротаев К., Емельянов П. Многоуровневый планировщик процессорного времени для групп процессов, обеспечивающий гарантии в обслуживании // Информационные технологии. — М. 2006. — № 6. — С. 58-63.

2. Коротаев К., Савочкин А. Концепция виртуальных процессоров для планировщика задач, реализующего изоляцию групп процессов // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2005. - С. 81-87.

3. Емельянов П., Коротаев К., Луковников И. Основные проблемы реализации алгоритмов пропорционального планирования // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2006.- С. 86-91.

4. Основные проблемы обеспечения точности управления при наложенном управлении ресурсами в современных операционных системах / А. Тормасов, П. Емельянов, К. Коротаев и др. // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2006. — С. 237-242.

5. Коротаев К., Емельянов П. Модифицированный БРС^ алгоритм (МЭР(3) для честного распределения процессорного времени на многопроцессорных системах // Проблемы вычислительной математики, математического моделирования и информатики: Сб.н.тр. — М.: МЗ Пресс, 2006. - С. 214-233.

6. Коротаев К., Емельянов П. Пути адаптации современных групповых планировщиков задач для работы в многопроцессорных системах // Современные проблемы фундаментальных и прикладных наук. Часть

VII. Управление и прикладная математика: Труды XLVIII научной конференции. — М. — Долгопрудный: Моск. физ.-техн. ин-т, 2005.— С. 237.

7. Коротаев К., Савочкин А. Модель группового планировщика процессов с использованием виртуальных процессоров // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции. — М. — Долгопрудный: Моск. физ.-техн. ин-т, 2005. — С. 39.

8. Коротаев К., Емельянов П. Изучение и оптимизация производительности групповых планировщиков процессов на примере честного планировщика ядра ОС Linux // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции. — М. — Долгопрудный: Моск. физ.-техн. ин-т, 2005. — С. 40.

9. Korotaev К. Hierarchical CPU Schedulers for Multiprocessor Systems, Fair CPU scheduling and Processes Isolation 11 Proceedings of Cluster'05. — Boston: 2005. - Pp. 53-54.

10. Коротаев К., Луковников В., Луковников И. О существующих планировщиках задач, пропорциональности распределяемого ими процессорного времени и способах улучшения качества обслуживания // Научное творчество молодежи. Часть I. Материалы X Всероссийской научно-практической конференции. — Кемерово: Кемеровский гос. универ-т, 2005. — С. 74.

11. "Честный" планировщик задач на основе аппроксимации идеального времени (ITAFS): новый подкласс пропорционально-долевых алгоритмов планирования задач для процессоров / А. Костюшко, К. Коротаев, В. Луковников, И. Луковников // Научное творчество молодежи. Часть

I. Материалы X Всероссийской научно-практической конференции. — Кемерово: Кемеровский гос. универ-т, 2005. — С. 75.

12. Коротаев К. С., Луковников В. В., Луковников И. В. Многоуровневый планировщик процессов для изоляции процессов и групп пользователей. Проблемы балансировки нагрузки и пути их преодоления // Приоритетные направления модернизации общего образования. Материалы Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО.- Т. 1,- Томск: ТОИПКРО, 2006.- С. 174175.

Коротаев Кирилл Сергеевич

Математическая модель планирования групп процессов с гарантированным качеством обслуживания

Автореферат

Подписано в печать 12.09.2006 Усл. печ. л. 1.5. Тираж 80 экз. Заказ № 471

Московский физико-технический институт (государственный университет) Печать на аппаратуре Rex-Rotary Copy Printer 1280. НИЧ МФТИ

141709, г. Долгопрудный Московской обл., Институтский пер. 9.

Д0О6А

[И 8 9 84

Введение

ГЛАВА 1. Обзор математических моделей планирования процессов

ГЛАВА 2. Модель PSFQ пропорционального распределения процессорного времени

ГЛАВА 3. Математическая модель жесткого ограничения выделяемых процессорных ресурсов

ГЛАВА 4. Модель виртуального процессора

В диссертационной работе рассматривается задача планирования и распределения вычислительных ресурсов операционной системы (процессорного времени) между группами процессов (пользователями) с учетом следующих требований: пропорциональное распределение ресурсов во времени и гарантированное качество обслуживания; возможность ограничения группы заданной долей ресурса; корректная работа на многопроцессорных системах. Эта задача актуальна для современных систем разделения пользователей и их изоляции.

За последнее десятилетие компьютерные мощности существенно выросли, и современное программное обеспечение уже далеко не всегда использует эти мощности на 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. На основании предложенных математических моделей разработан соответствующий комплекс программ. Проведены численные эксперименты с его использованием. Проведено сравнение различных планировщиков задач; продемонстрированы особенности многопроцессорных систем с точки зрения планирования процессорных ресурсов.

Содержание и структура диссертации.

Данная диссертационная работа состоит из введения, четырех глав, заключения и списка использованной литературы. Для удобства чтения работа снабжена оглавлением с указанием страниц в начале работы и списками таблиц и иллюстраций в конце.

ЗАКЛЮЧЕНИЕ

Можно выделить следующие основные результаты проделанной работы и вытекающие из них выводы:

1. Предложена математическая модель пропорционального планирования групп процессов, позволяющая управлять распределением процессорного времени. Данная модель гарантирует выделение указанной доли времени группе процессов и включает математические оценки точности и задержки в обслуживании, что позволяет использовать эту модель в системах с гарантированным качеством обслуживания.

2. Предложена математическая модель ограничения потребляемого группой процессов процессорного времени. На основании данной модели получены оценки качества обслуживания.

3. Разработана и реализована модель "виртуальных процессоров", позволяющая объединить планировщик групп процессов со стандартным планировщиком операционной системы. Что позволяет получить пропорциональный планировщик процессов со свойствами стандартного планировщика, например, интерактивностью.

4. Предложенные модели реализованы в виде комплекса программ, обеспечивающего количественные и качественные гарантии в обслуживании. Проведены численные исследования свойств предложенных моделей на многопроцессорных системах.

Полученный многоуровневый планировщик процессов, использующий все три модели, предложенные в работе, удовлетворяет требованиям 1-5 и 7-9, сформулированным в главе 1.

1. Andrzejak A., Martin A., Jerry R. Bounding the Resource Savings of Utility Computing Models: Technical Report HPL-2002-339: HP Labs, 2002.

2. Price D., Tucker A. Solaris zones: Operating system support for consolidating commercial workloads // Proceedings of the USENIX 18th Large Installation System Administration Conference (LISA'04). 2004.

3. Tucker A., Comay D. Solaris zones: Operating system support for server consolidation // Proceedings of the USENIX Third Virtual Machine Research & Technology Symposium (VM'04). 2004.

4. Increasing the Load: Virtualization Moves Beyond Proof of Concept in the Volume Server Market, According to IDC: IDC Press Release: 18 Oct 2005.

5. Bittman T. Predicts 2004: Server Virtualization Evolves Rapidly: SPA-21-5502: Gartner Research, 2003.6. 2006 technology of the year awards. — Режим доступа: http://www.infoworld.com/reports/0lSRtoy06.html, свободный. — Загл. с экрана. — Яз. англ.

6. Intel. vanderpool technology. — Режим доступа: http://www.intel.com/technology/computing/vptech/, свободный. — Загл. с экрана. — Яз. англ.

7. Diagnosing Performance Overheads in the Xen Virtual Machine Environment / A. Menon, J. R. Santos, Y. Turner et al. // First ACM/USENIX Conference on Virtual Execution Environments (VEE'05). 2005. - Pp. 13-23.

8. Fedora Core Project Электронный ресурс. / RedHat company, [2006].— Режим доступа: http://www.redhat.com/fedora/, свободный. — Загл. с экрана. — Яз. англ.

9. SUSE Linux Электронный ресурс. / Novell company, [2006].— Режим доступа: http://www.novell.com/linux/, свободный. — Загл. с экрана. — Яз. англ.

10. И. XenSource: Delivering the power of Хеп Электронный ресурс. / Cambridge University, [2006].— Режим доступа: http://www.xensource.com/, свободный. — Загл. с экрана. — Яз. англ.

11. Хеп and the art of virtualization / В. Dragovic, К. Fraser, S. Hand et al. // Proceedings of the ACM Symposium on Operating Systems Principles. 2003. - Pp. 164-177.

12. Емельянов П., Савочкин А. Расширение функциональности существующей модели контроля памяти в ядре linux // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2005.- С. 77-80.

13. CKRM linux open source project, class based kernel resource management Электронный ресурс. / IBM, [2006].— Режим доступа: http://ckrm.sourceforge.net/, свободный. — Загл. с экрана. — Яз. англ.N

14. Improving Linux resource control using CKRM / S. Nagar, R. van Riel, H. Franke et al. // Proceedings of the Ottawa Linux Symposium. Vol. 2. - 2004. - Pp. 511-524.

15. Banga G., Druschel P., Mogul J. Resource containers: A new facility for resource management in server systems // Proceedings of the USENIX Symposium on Operating System Design and Implementation (OSDI). 1999. - Pp. 45-48.

16. Kay J., Lauder P. A Fair Share Scheduler // Communications of the ACM. 1988. - no. 31(1). - Pp. 44-55.

17. Chan W. C., Nieh J. Group Ratio Round-Robin: An 0(1) Proportional Share Scheduler // Proceedings of the 2005 USENIX Annual Technical Conference. 2005. - Pp. 337-352.

18. Nieh J., Vaill C., Zhong H. Virtual-Time Round-Robin: An 0(1) Proportional Share Scheduler // In Proceedings of the 2001 USENIX Annual Technical Conference. 2001. - Pp. 245-259.

19. Bavier A. The Tyche CPU Scheduler: Phd thesis / Princeton University. — Nov. 2004.

20. Klamann R. Opportunity scheduling: An unfair CPU scheduler for UNICOS // Proceedings of Cray User Group (CUG).- 1997.-Pp. 57-64.

21. Jones M. В., Rosu D., Rosu M.-C. CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities // Symposium on Operating Systems Principles.— 1997.-Pp. 198-211.

22. A proportionate fair scheduling rule with good worst-case performance / M. Adler, P. Berenbrink, T. Friedetzky et al. //

23. Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures. — 2003. — Pp. 101-108.

24. Протасов С., Белоусов С., Тормасов А. Прошлое, настоящее и будущее: развитие архитектуры и принципов создания операционных систем // "Объединенный научный журнал". — 2004.— № 24(116).- С. 83-86.

25. OpenVZ Server Virtualization Open Source Project Электронный ресурс. / [2006]. — Режим доступа: http://openvz.org/, свободный. — Загл. с экрана. — Яз. англ.

26. VMware virtualization software Электронный ресурс. / EMC Company, [2006].— Режим доступа: http://vmware.com, платный. — Загл. с экрана. — Яз. англ.

27. Microsoft Virtual PC virtualization Электронный ресурс. / Microsoft corporation, [2006].— Режим доступа: http://www.microsoft.com/windows/virtualpc, платный. — Загл. с экрана. — Яз. англ.

28. Multiprocessor Specification Электронный ресурс. / Intel, [2006].— Режим доступа: http://www.intel.com/design/archives/processors/pro/docs/242016.htm, свободный. — Загл. с экрана. — Яз. англ.

29. Lawton К. The Cross Platform IA-32 Emulator Электронный ресурс. / Open Source project, [2006].— Режим доступа: http://bochs.sourceforge.net/, свободный. — Загл. с экрана. — Яз. англ.

30. Bellard F. Qemu: open source processor emulator Электронный ресурс. / Open Source project, [2006].— Режим доступа: http://www.qemu.com/, свободный. — Загл. с экрана. — Яз. англ.

31. McEwan W. Virtual machine technology and their application in the delivery of ICT.

32. Waldspurger C. Memory resource management in VMware ESX Server // Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI '02). 2002.

33. Virtuozzo: server virtualization, consolidation and management Электронный ресурс. / SWsoft Inc., [2006].— Режим доступа: http://virtuozzo.com/, свободный. — Загл. с экрана. — Яз. англ.

34. Linux-Vserver project Электронный ресурс. / Herbert Poetzl, [2006].— Режим доступа: http://linux-vserver.org/, свободный. — Загл. с экрана. — Яз. англ.

35. Virtualization of linux based computers: the linux-VServer project // Proceedings of 19th International Symposium on High Performance Computing Systems and Applications. — May 2005. — Pp. 340-346.

36. Solaris containers Электронный ресурс. / Sun microsystems, [2006].— Режим доступа: http://www.opensolaris.org/os/community/zones/, свободный. — Загл. с экрана. — Яз. англ.

37. HP-UX lli virtual partitions Электронный ресурс. / Hewlett Packard, [2006].— Режим доступа: http://h20338.www2.hp.com/hpuxlli/cache/323722-0-0-0-121.html, свободный. — Загл. с экрана. — Яз. англ.

38. Diagnosing Performance Overheads in the Xen Virtual Machine Environment: Technical Report HPL-2005-80 / A. Menon, J. R. Santos, Y. Turner et al.: HP Labs, 2005.

39. Cherkasova L., Gardner R. Measuring CPU Overhead for I/O Processing in the Xen Virtual Machine Monitor: Technical Report HPL-2005-62: HP Labs, 2005.

40. Petrou D., Milford J. W., Gibson G. A. Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers // Proceedings of the USENIX 1999 Annual Technical Conference. 1999. - Pp. 1-14.

41. Golestani S. J. A Self-Clocked Fair Queueing Scheme for Broadband Applications. // Proceedings of IEEE INFOCOM'94. -Jun 1994.-Pp. 636-646.

42. Емельянов П., Коротаев К., Луковников И. Основные проблемы реализации алгоритмов пропорционального планирования // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2006. С. 86-91.

43. Etsion Y., Tsafrir D., Feitelson D. G. Desktop scheduling: how can we know what the user wants? // Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video. — 2004. — Pp. 110-115.

44. Liu С., Layland J. Scheduling algorithms for multiprogramming in a hard real-time environment // Journal of the ACM. — Jan 1973. no. 1(20). - Pp. 46-61.

45. Serlin O. Scheduling of Time Critical Processes // Proceedings of the 1972 AFIPS Spring Joint Computer Conference. Vol. 40. -1972.

46. Lehoczky J., Sha L., Ding Y. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior // Proceedings of the 10th IEEE Real-Time Systems Symposium (RTSS '89). Dec 1989. - Pp. 166-171.

47. Zhang Y., Sivasubramaniam A. Scheduling best-effort and realtime pipelined applications on time-shared clusters // Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures. 2001. - Pp. 209-219.

48. Multimedia Applications Require Adaptive CPU Scheduling / V. Baiceanu, C. Cowan, D. McNamee et al. // Proceedings of the Workshop on Resource Allocation Problems in Multimedia Systems. Dec 1996.

49. Biyabani S., Ramamritham K., Stankovic J. The Integration of Deadline and Criticalness in Hard Real-Time Scheduling // Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS '88). Dec 1988. - Pp. 152-160.

50. The design and implementation of an operating system to support distributed multimedia applications / I. Leslie, D. McAuley, R. Black et al. // IEEE Journal on Selected Areas in Communications. Sept. 1996. - no. 14(7). - Pp. 1280-1297.

51. Chandra A., Adler M., Shenoy P. Deadline fair scheduling: Bridging the theory and practice of proportionate-fair schedulingin multiprocessor servers // In Proceedings of the 7th IEEE RealTime Technology and Applications Symposium. — 2001.— Pp. 314.

52. Link-sharing and Resource Management Models for Packet Networks // IEEE/ACM Transactions on Networking. — Aug 1995. Vol. 3, no. 4. - Pp. 365-386.

53. A Simulation Study of Fair Queueing and Policy Enforcement // ACM Computer Communication Review. — Oct 1990. — Vol. 20, no. 5. Pp. 23-29.

54. Bennett J. C. R., Zhang H. Hierarchical packet fair queueing algorithms // IEEE/ACM Transactions on Networking. — 1997. — Vol. 5, no. 5. Pp. 675-689.

55. Goyal P., Vin H. M., Cheng H. Start-Time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks // Proceedings of ACM SIGCOMM'96.- 1996. — Pp. 157-168.

56. Analysis and Simulation of a Fair Queueing Algorithm // Proceedings of the ACM SIGCOMM '89. 1989. - Pp. 1-12.

57. Greenberg A., Madras N. How Fair is Fair Queuing // The Journal of ACM. July 1992. - Vol. 39(3). - Pp. 568-598.

58. Adaptive reservations in a linux environment / L. Abeni, T. Cucinotta, G. Lipari et al. // Proceedings of the 10th IEEE RealTime and Embedded Technology and Applications Symposium (RTAS'04).- 2004.- P. 238.

59. Waldspurger C. A., Weihl W. E. Lottery scheduling: Flexible proportional-share resource management // Proceedings of the First USENIX Symposium on Operating System Design and Implementation (OSDI). Nov. 1994. - Pp. 1-11.

60. Waldspurger С. A., Weihl W. E. Stride Scheduling: Deterministic Proportional-Share Resource Management: Tech. Rep. MIT/LCS/TM-528: 1995.

61. Duda K. J., Cheriton D. R. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general-purpose scheduler // Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP). Dec 1999. - Pp. 261-276.

62. Goyal P., Guo X., Vin H. A Hierarchical CPU Scheduler for Multimedia Operating Systems // Proceedings of the Second USENIX Symposium on Operating System Design and Implementation (OSDI).- 1996.-Pp. 107-122.

63. Nieh J., Lam M. The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications // Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP). Oct 1997. - Pp. 184-197.

64. Waldspurger C. Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management: PhD thesis / Massachusetts Institute of Technology. — Sept. 1995.

65. Stoica I., Abdel-Wahab H., Jey K. On the duality between resource reservation and proportional share resource allocation // Proceedings of Multimedia Computing and Networking 1997 (MMCN97). Feb. 1997. - Pp. 207-214.

66. A proportional share resource allocation algorithm for real-time time-shared systems / I. Stoica, H. Abdel-Wahab, K. Jey et al. // Proceedings of the 17th IEEE Real-Time Systems Symposium (RTSS '96). Dec. 1996. - Pp. 288-299.

67. Zhang L. Virtual clock: A new traffic control algorithm for packet switching // ACM Transactions on Computer Systems.— May 1991. no. 9(2). - Pp. 101-124.

68. Gunther N. J. Solaris System Resource Manager: All I Ever Wanted Was My Unfair Advantage (And Why You Can't Have It!) // Proceedings of CMG'99 Conference. 2000. - Pp. 194-205.

69. Newhouse Т., Pasquale J. ALPS: An Application-Level Proportional-Share Scheduler // Proceeedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC). 2006. - Pp. 45-57.

70. Tanenbaum A. Modern Operating Systems, 2nd edition. — Prentice Hall, 2001.

71. Aas J. Understanding the linux 2.6.8.1 CPU scheduler.- 2005. http://josh.trancesoftware.com/linux/linuxcpuscheduler.pdf.

72. Love R. Linux Kernel Development. — Novell Press, 2005. — Chapter 04: Process Scheduling.

73. A Linux Implementation of a Differentiated Services Router / T. Braun, H. J. Einsiedler, M. Scheidegger et al. // Networks and Services for the Information Society: 5th IFIP TC6 International Symposium, INTERWORKING 2000, 2000. - Pp. 302-315.

74. Kolyshkin K., Korotaev K. OpenVZ Project OS Server Virtualization // Proceedings of the LinuxTag conference. — 2006. http://www.linuxtag.org/2006/de/besucher/material.html.

75. Korotaev K. Hierarchical CPU Schedulers for Multiprocessor Systems, Fair CPU scheduling and Processes Isolation // Proceedings of Cluster'05. Boston: 2005. - Pp. 53-54.

76. Ford В., Susarla S. CPU Inheritance Scheduling // Usenix Association Second Symposium on Operating Systems Design and Implementation (OSDI). 1996. - Pp. 91-105.

77. Duda K. J., Cheriton D. R. Borrowed virtual-time (BVT) scheduling. — 2000. http://www.dsg.standford.edu/pub/bvt.html.

78. Application performance in the QLinux multimedia operating system / V. Sundaram, A. Chandra, P. Goyal et al. // Proceedings of 8th ACM Conference on Multimedia. 2000. - Pp. 127-136.

79. Коротаев К., Савочкин А. Концепция виртуальных процессоров для планировщика задач, реализующего изоляцию групп процессов // Процессы и методы обработки информации: Сб.ст. — М.: Моск. физ.-техн. ин-т, 2005. С. 81-87.

80. Enforcing Performance Isolation Across Virtual Machines in Xen: Technical Report HPL-2006-77 / D. Gupta, L. Cherkasova, R. Gardner, A. Vahdat: HP Labs, 2006.

81. Regehr J. Using Hierarchical Scheduling to Support Soft Real-Time Applications on General-Purpose Operating Systems: PhD thesis / University of Virginia. — 2001.

82. Devine S. W., Bugnion E., Rosenblum M. US patent #6,397,242: Virtualization system including a virtual machine monitor for a computer with a segmented architecture. — May 28, 2002.

83. Bulpin J. R., Pratt I. A. Hyper-Threading Aware Process Scheduling Heuristics // Proceedings on the 2005 USENIX Annual Technical Conference. 2005. - Pp. 103-106.

84. Siddha S. Chip Multi Processing aware Linux Kernel Scheduler // Proceedings on the 2005 Linux Symposium. 2005. - Pp. 337-347.

85. Nakajima J., Pallipadi V. Enhancements for Hyper-Threading technology in the operating system. Seeking the optimal scheduling //In Proceedings of the 2nd Workshop on Industrial Experiences with Systems Software. — 2002. — Pp. 25-38.

86. Squillante M. S., Lazowska E. D. Using Processor-Cache Affinity Information in Shared-Memory Multiprocessor Scheduling // IEEE Transactions on Parallel and Distributed Systems. — Feb 1993. — Vol. 4, no. 2.- Pp. 131-144.

87. Коротаев К., Емельянов П. Многоуровневый планировщик процессорного времени для групп процессов, обеспечивающий гарантии в обслуживании // Информационные технологии. — М.2006.-№ 6.-С. 58-63.