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

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

00344-

Емельянов Павел Владимирович

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

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

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

Москва - 2008

3 о СЕН 2008

003447370

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

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

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

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

профессор

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

кандидат технических наук КОНЬКОВ Александр Константинович

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

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

-¿О

Защита состоится «. /6 » Р^Т^АЯ 2008 года в /о часов на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская область, г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

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

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

Учёный секретарь диссертационного совета Д 212.15р?05, кандидат физико-математических наук / / Федько О. С.

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

Актуальность работы

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

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

Уже больше года компания Intel поставляет все свои настольные процессоры со встроенной технологией для аппаратной поддержки виртуализации под названием VT™, которая существенно повысила производительность существующих программных реализаций этой технологии. В то же самое время уже создан огромное количество различных программных комплексов, работающих с поддержкой этой технологии, например, VMWare, Parallels, KVM и т. д. Если раньше основными пользователями этой технологии были компании с большим парком техники, то сейчас

'В англоязычных источниках популярностью пользуется понятие «контейнера» для определения виртуального сервера

она доступна на каждом персональном компьютере.

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

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

Цель работы

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

• обеспечивать изоляцию виртуальных сред друг от друга;

• ограничивать виртуальные среды в потреблении физической памяти;

• обеспечивать требуемый уровень сервиса для виртуальных машин.

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

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

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

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

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

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

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

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

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

Часть реализованного программного комплекса была внедрена автором совместно со специалистами из компаний IBM и Google в основное ядро Unix-подобной операционной системы Linux2, которая является одной из наиболее популярных операционных систем и установлена как на домашних компьютерах, так и на крупных серверах по всему миру.

Кроме того, реализация всех описанных моделей была внедрена в продукты компании Parallels Virluozzo Containers3 и OpenVZ4, представляющие собой виртуализационные решения на базе ядра Linux. Их использование показало, что модели представляют не только теоретический интерес, но и успешно решают поставленные перед ними практические задачи, а именно - позволяют контролировать потребление памяти виртуальной машиной.

2 Исходные тексты доступны по адресу http7/git.kcrncl.org/?p=linux/kcmel/git/torvalds/linux-2 6 git

3Uttp;//www.parallcls.com/cn/virtuozzo/

*littp://openvz.org

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

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

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

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

Все модели, подходы и результаты, изложенные в работе опубликованы, в том числе в изданиях, рекомендованных ВАК РФ [1, 2, 3].

Результаты диссертации доложены на XLVII и XLIX научных конференциях Московского физико-технического института (Москва-Долгопрудный, 2004 - 2006) и на международных конференциях Linux-разра-ботчиков «Linux Symposium» (Оттава, Канада, 2007) и «LinuxConf Europe» (Кэмбридж, Великобритания, 2007). Доложенные материалы получили одобрение специалистов, включая ключевых разработчиков ядра Linux. Так же модель предоставления гарантий в сокращенной форме опубликована в документации к проекту OpenVZ5.

Реализации алгоритмов, внедренные в продукты Parallels Virtuozzo Containers и QpenVZ, установлены на тысячах серверов по всему миру и обеспечивают корректную работу и изоляцию почти полумиллиона виртуальных серверов.

Структура и объем работы

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

6littp://wiki. openvz.org/Contamers/Guaranteus_for_resources

на 101 странице и включает 20 иллюстраций.

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

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

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

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

• ограничение группы процессов в использовании физической памяти;

• гарантированное выделения памяти заранее заданного объема;

• учет возможного существования участков разделяемой памяти между группами процессов;

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

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

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

6Оригинальное название модели англоязычное - "Ьвапсошиеге"

по сравнению с остальными существующими разработками, соответствует поставленным требованиям. Показано, что несмотря на это, в модели присутствуют ряд недостатков.

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

В начале главы приведена необходимая терминология.

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

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

Пусть в системе с п. группами вектор г = (го,..., r„_j) показывает количество страниц, которое используется группами, а вектор I — (Iо,.. •, ln-i) ~ это набор ограничений, выставленный администратором системы. Тогда в соответствии с поставленным требованием система управления памятью при запросах на выделение Дг, единиц памяти для группы i должна отказывать в выделении тогда и только тогда, когда г, + Дг, > 1г (после этого необходимо пересчитать компоненты г).

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

• Сначала процесс запрашивает у ядра т. н. «регионы», в рамках которых ему будет разрешено выделять физическую память. Этот запрос

7См. например Love R. Linux Kernel Development. — Novell Press, 2005. — Ch. 14: The Process Address Space.

осуществляется процессом явно с помощью системного вызова ттар. На данном этапе ОС не выделяет процессу физической памяти.

• Затем процесс запрашивает у ядра физическую память в рамках выделенных ранее регионов. Этот запрос производится неявно - процесс просто обращается по некоторому виртуальному адресу в рамках созданного региона (например, записывая туда данные). При таком обращении генерируется аппаратное исключение типа «страничный отказ», которое перехватывается ядром операционной системы: Результатом выполнения этого запроса ядром является выделенный процессу физический участок памяти.

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

Нетрудно видеть, что г может измениться только в результате выполнения запроса второго типа, поэтому рассматриваемый алгоритм «счетоводов» перехватывает все запросы этого типа и подсчитывает количество физических страниц, выделенных группе процессов по этим запросам. При этом алгоритм использует точные, но весьма громоздкие счетчики для корректной работы с участками разделяемой памяти. Как показали измерения, эта процедура заметно снизила производительность выполняющихся процессов - память по второму запросу стала выделяться до 20% медленнее, что является серьезным недостатком алгоритма. Для преодоления указанного недостатка, предложено обходить дополнительные вычисления когда это возможно.

Предложенная модель улучшения алгоритма выглядит следующим образом. Рассмотрим группу процессов с некоторым множеством из тI регионов отдельных процессов с длинами М3, 3 = 0, ггц — 1. Обозначим также за количество физических страниц, выделенных внутри региона

Очевидно, что

Rj<M:,Vj. (1)

IIa этом соотношении построено предлагаемое изменение алгоритма - для каждого региона j введен новый булевый признак 53, который показывает, нужно ли выполнять точные (и медленные) вычисления во время обработки запросов второго типа. Также для региона j построена оценочная величина

EJ = 6jRJ + (1-63)MJ, (2)

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

R3<E3< Mj. (3)

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

В главе вычислено математическое ожидание времени, которое уйдет у ядра для обработки одного запроса второго типа (г) в ситуации, когда в системе присутствуют ms регионов, для которых 5г = 1 и выяснено, при каких условиях это время достигает своего минимума.

Искомая величина задается выражением

£t = &jtJ. (4)

j

где p-j - вероятность того, что запрос придет в регион j, а т3 - время выполнения запроса и этом регионе.

Требуется решить задачу поиска набора регионов (ji,. ■. ,jm.)> Для которых <5j, = 1, таких, что

Ет —> min. (5)

Легко показать, что для т3 справедливо

г3 = 53Т + (1 - 63)1, (6)

где Т - время медленных вычислений, а Ь - время быстрых, для которых справедливо Т а для вероятности р3 имеет место

р3~(М3-Я3)А3, (7)

где А — ] - активность использования региона. Под активностью региона в главе понимается величина, характеризующая частоту обращений про-' цессов к страницам в регионе. Точное значение этой величины не известно для произвольного приложения, и в главе приведен ряд подходов к ее вычислениям. Например, рассмотрены регионы с одинаковой активностью [А] = 1, V?) и предложена оценка активности регионов по относительному уровню их использования (А3 = Д^М"1).

Опуская константу в выражении (7), обозначим а3 = (М3 —В,3)А3. Таким образом для Ет имеет место

Ег= £ а3Т + £ а31. (8)

].&,=1

Отсюда индуктивно несложно доказать, что решением задачи (5) является такой набор регионов, для которого вектор (а^,..., аят„) состоит из наименьших значений а3. Таким образом, на каждом шаге, когда требуется найти очередной регион для которого нужно установить 5, = 1 нужно выбрать регион с минимальных из существующих а5.

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

В главе доказана теорема

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

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

Результатом предложенной модернизации алгоритма явилась почти полная компенсация потери производительности на стандартных конфигурациях, применяемых пользователями этой подсистемы в рамках проекта Ореп\^, что продемонстрировано результатами тестирования8 некоторых типовых нагрузок на стандартные приложения (\УЕВ-сервер, система резервного копирования данных, архиватор, система контроля версий и генератор фракталов) (см. рис. 1).

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

Определение. Гарантией называется объем ресурсов, которое будет предоставлено группе по запросу независимо от того, сколько ресурсов уже предоставлено другим группам.

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

8 В экспериментах в качестве такой оценки было использовано значение

Основное ядро ' . :: Счетоводы

Улучшение

Рис. 1: Производительность ядер на стандартных конфигурациях.

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

Модель построена на примере гарантированного выделения памяти. Рассмотрена система с Я единицами (страницами, байтами, килобайтами) памяти, на которой требуется разделить ее между п группами. Количество памяти, которое требуется гарантированно предоставлять группам задается вектором д = (до,... ,дп-\).

При этом, естественно, требуется, чтобы набор д^ был корректен, то

есть

5><Д.' ' 0)

г

Для достижения этого результата предложено вычислить вектор I =

(¿о, • • ■ ,1п-1)1 задающий ограничения потребления ресурсов в группах, таким образом, чтобы при любом уровне потребления любых п — 1 групп в системе оставалось необходимое для оставшейся группы количество ресурса (т.е. д¡). При этом ожидается, чтобы полученные ограничения не будут противоречить требуемым гарантиям, т.е.

г, > (ю)

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

Л = Д- £ 1Г (П)

В главе показано, что система неравенств (11) в рамках рассматриваемой задачи эквивалентна системе линейных уравнений, которая в матричной форме выглядит следующим образом

/ 1 \

А-1 - Я

~9.

(12)

\1/

где

-Е,

(13)

и находя обратную матрицу

_ А - (п - 2)Е ~ п -1 '

(14)

можно получить, что искомые величины 1г задаются соотношением

и = 9г + А, (15)

где

Д №

тг - 1

Решение этой задачи позволило доказать следующую теорему.

Теорема 2. Введенные ранее условия корректности гарантий (9) и корректности вычисляемых ограничений (10) являются эквивалентными.

Таким образом, для группы определены три зоны уровней потребления ресурсов (см. рис. 2) - зона «жестких» гарантий, в которой группе память будет гарантированно9 предоставлена; зона «мягких» гарантий, в которой группе не гарантируется в выделении памяти, но и не отказывается при наличии свободных страниц; и запрещенная зона.

Уровень

д у^ I потребления >-^-1-^-'-1-»>- ресурсов

Область Область _

запрещенная

«жестких» «мягких»

область

гарантий гарантий

Рис. 2: Зоны уровней потребления ресурсов.

Особое внимание уделено проблеме присутствия ядра операционной системы. А именно - поскольку ядро тоже потребляет физическую память, то эту память тоже нужно учитывать в приведенных выше расчетах. Кроме того, отмечено, что создание большого количества объектов ядра может быть инициировано процессом, что дает возможность одному процессу потребить всю ядерную память, что, в свою очередь, может являться вариантом атаки тина «отказ в обслуживании».

Предложено определить вектор I как сумму ограничений двух типов - ограничение в использовании памяти ядра (¿д.) и ограничение в использовании памяти процесса (1и):

Г= £ + С ' (17)

'Кроме случаев »ыхода системы из строя

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

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

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

Технология выгрузки страниц на диск является логическим следствием модели виртуальной памяти - когда в системе заканчивается оперативная память, а процесс требует еще, можно часть страниц из оперативной памяти скопировать на другой, более емкий, носитель10, а освободившееся место использовать для других нужд. Для более эффективной работы подобного алгоритма страницы памяти хранятся в списке, отсортированном по времени «недавнего использования» (LRU11).

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

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

11 От англ. least recently used

в котором хранятся только страницы, используемые этой группой.

Таким образом, каждой странице памяти р ставится в соответствие две числовые характеристики: аде(р, t) - «возраст» страницы, равный времени, прошедшему с момента, когда ядро зарегистрировало факт обращения к странице до текущего момента времени t любым процессом; и ageg(p,t) - «возраст» страницы в группе, вычисляемый аналогично, но лишь для обращений процессов из группы д.

В главе доказана важная теорема.

Теорема 3. В любой момент времени t для любых двух страниц рх и р2 и группы, g свойство age(p\,t) < age(p2,t) равносильно свойству a9eg(Pht) ^ a,geg(p2,t) в том и только том случае, когда к странице обращаются только процессы из той же группы.

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

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

Описанный в главе алгоритм был реализован автором в виде комплекса программ - расширения к ядру ОС Linux. Был проведен ряд экспериментов с модифицированным ядром и в главе также приведены результаты этих экспериментов.

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

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

1. Разработана математическая модель предоставления гарантий выделения группам процессов физической памяти. Показана применимость модели к другим типам ресурсов на примере задачи распределения процессорного времени.

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

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

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

1. Емельянов П. В., Коротаев К. С. Математическая модель обеспечения гарантий выделения ресурсов операционной системы // Информационные технологии. — М. 2008 — № 3 — С. 83-85.

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

- С. 58-63.

3. Емельянов П. В. Оптимизация модели контроля потребления памяти группой процессов // Вестник Новосибирского Гос. Унив-та. Серия: Информационные Технологии — 2008 — Т. 6, вып. 1 - С. 37-46.

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

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

- С. 77-80.

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

7. Емельянов П. В., Коротаев К. С., Лунев Д. В. Расширение функциональности существующей модели контроля памяти в ядре Linux //

Сопрем. проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная мат-ка: Труды XLVII научной конф-ции.

— М. — Долгопрудный: Моск. физ.-техн. ин-т, 2004. — С. 37.

8. Емельянов П. В., Лунев Д. В. Математическая модель предоставления гарантий выделения ресурсов на базе жестких ограничений // Соврем, проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная мат-ка: Труды 49-й научной конф-ции. — М. — Долгопрудный: Моск. физ.-техн. ин-т, 2006. — С. 37-38.

9. Pavel Emehanov, Denis Lunev, Kmll Korotaev Resource Management: Beancounters // Proceedings of the Linux Symposium — Ottawa: 2005.

- Pp. 285-292.

10. Pavel Emehanov, Denis Lunev, Kmll Korotaev Resource Management: Beancounters // Proceedings of the LinuxConf Europe — Cambridge: 2007. - 7 Pp.

11. Balbir Smgh, Pavel Emehanov Memory Controller: рабочая программа [Электронный ресурс]: хранилище содержит исходные тексты ядра ОС Linux. — Электрон, дан. (1 файл). — 2007. — Режим доступа: http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=mm/memcontrol.c

В работах с соавторами соискателю принадлежат следующие результаты. [1] - разработка математической модели предоставления гарантий выделения физической памяти; [2,4]- проведение численных экспериментов над реализованным комплексом программ и изложение результатов; [5] - разработка комплекса программ по управлению распределением памяти ядра; [6] - анализ проблем, возникающих в задачах пропорциональною планирования; [И] - реализация алгоритмов подсчета и ограничения использошшнм физической памяти и выгрузки страниц па диск.

Емельянов Павел Владимирович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ

УПРАВЛЕНИЯ ПОТРЕБЛЕНИЕМ ПАМЯТИ В МНОГОПОЛЬЗОВАТЕЛЬСКИХ СРЕДАХ И СИСТЕМАХ ВИРТУАЛИЗАЦИИ

Подписано в печать 09.09.2008 г. Формат 60x84 1/w. Печать офсетная

Уел печ. л 1,0 Уч.-изд. л 1,0 Тираж 80 экз. Заказ № ^ - £>'1Х>

Государственное образовательное учреждение высшего профессионального образования Московский физико-технический институт (государственный университет) Отдел автоматизироцаиных систем «ФИЗТЕХ-ПОЛИГРАФ»

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

Введение

1 Обзор существующих моделей управления памятью

1.1 Терминология

1.1.1 Термины теории операционных систем.

1.1.2 Термины теории управления памятью.

1.1.3 Термины теории многопроцессорных систем.

1.2 Эволюция моделей управления памятью.

1.2.1 Системы без поддержки многозадачности.

1.2.2 Однопользовательские системы с поддержкой многозадачности

1.2.3 Многопользовательские операционные системы.

1.2.4 Системы виртуализации

1.3 Менеджер памяти в современной операционной системе.

1.4 Портрет идеального менеджера.

1.4.1 Первое требование: Ограничение в использовании

1.4.2 Второе требование: Гарантии выделения.

1.4.3 Третье требование: Разделение между группами.

1.4.4 Четвертое требование: Многократное использование

1.5 Существующие менеджеры.

1.5.1 Стандартный менеджер памяти в Linux.

1.5.2 Менеджер памяти в VMware.

1.5.3 Управление памятью в Хеп.

1.5.4 Управление памятью в Solaris Zones и FreeBSD Jails

1.5.5 Проект контроля за ресурсами CKRM.

1.5.6 Проект «счетоводы» по контролю памяти.

1.6 Виртуальная выгрузка страниц на диск

3.2 Определение гарантии и способы ее обеспечения.61

3.3 Математическая модель.64

3.4 Анализ результата.66

3.4.1 Корректность полученных гарантий .66

3.4.2 Вычисление гарантий из выставленных ограничений . 68

3.4.3 Случай нарушения пределов.68

3.5 Учет присутствия ядра ОС.69

3.5.1 Память ядра.70

3.6 Применимость модели к ресурсам другого типа.72

3.7 Заключение.73

4 Модель «группового» вытеснения страниц на внешний носитель 75

4.1 Введение .75

4.2 Существующая модель «сканера».75

4.3 Расширенная модель «сканера».76

4.4 Кэширование выгружаемых страниц.79

4.5 Результаты экспериментов.80

4.6 Поведение при нехватке памяти.83

4.7 Заключение.83

Заключение 85

Списки 86

Примечания 90

Введение

Ядро любой операционной системы предоставляет пользователям компьютера различные ресурсы [1, 2]. При этом наряду с задачей выделения ресурсов часто возникает задача их распределения — различные пользователи должны быть ограничены в потреблении того или иного ресурса. Делается это для различных целей, например для защиты системы от умышленного (или случайного) потребления всех свободных ресурсов одним пользователем, для приорити-зации пользователей системы в зависимости от их «важности», для создания у отдельных пользователей иллюзии работы на отдельной машине и для многих других вещей.

Современные операционные системы предоставляют пользователю и программам довольно большой набор ресурсов, например открытые файлы и сетевые соединения, объекты ядра операционной системы и сегменты памяти программ, буфера сетевого стека для отправки и получения данных и многие другие, однако в первом приближении ресурсов всего два — это процессорное время и оперативная память. [3]

Рост процессорных мощностей и объемов памяти за последнее десятилетие существенно опередил рост потребностей программного обеспечения - программы уже далеко не всегда использует эти мощности на 100% [4, 5]. Такая ситуация привела к появлению и развитию различных технологий «виртуализации» вычислительных систем. Виртуализация позволяет запускать на одном физическом сервере несколько виртуальных машин (ВМ) или виртуальных серверов (ВС)1, и, таким образом, позволяет, например, программное обеспечение с нескольких машин выполнять на одном физическом компьютере более экономно используя имеющиеся мощности. [6, 7, 8] англоязычных источниках прижилось понятие «контейнера» для описания виртуального сервера.

По отчетам аналитических агентств рынок систем виртуализации только за 2007г. вырос почти в 1.5 раза [10], а к 2009 году прогнозируют более 100% [9] рост. Технология виртуализации также признана одной из самой многообещающих технологий 2005 года [11].

Уже больше года компания Intel поставляет все свои настольные процессоры со встроенной технологией для аппаратной поддержки виртуализации под названием VT™, которая существенно повысила производительность существующих программных реализаций этой технологии. [12, 13] В то же самое время уже создан огромное количество различных программных комплексов, работающих с поддержкой этой технологии, например, VMWaire [14], Parallels [15], KVM [16] и т. д. [17, 18]. Если раньше основными пользователями этой технологии были компании с большим парком техники, то сейчас она доступна на каждом персональном компьютере. Уже сейчас современные свободные дистрибутивы Linux такие как Fedora, Ubuntu и др. оснащаются, например, системой виртуализации Хеп [35] или KVM. [19, 20, 21, 22, 23]

Задача справедливого управления ресурсами и родственная ей задача обеспечения гарантированных параметров качества обслуживания на уровне операционной системы стали весьма актуальны для современных вычислительных систем коллективного пользования (веб-хостингов, центров хранения и обработки данных и др.) именно всвязи с бурным развитием этих технологий. Известные на сегодня стратегии решения этих задач обладают различными недостатками и часто вообще неудовлетворительны, поэтому в этой области ведутся интенсивные исследования. [24]

Также следует заметить, что вопрос разделения и гарантированного выделения ресурсов возникает не только в системах виртуализации, но и в самих многопользовательских операционных системах (ОС). Например ни в Windows, ни в Linux, которые позволяют огромному количеству пользователей одновременно работать и выполнять свои приложения, до сих пор нет удовлетворительных средств для управления ресурсами: памятью, процессором, диском и др. Для отдельных ресурсов существуют средства контроля за отдельными процессами или нитями, для некоторых - на уровне отдельных пользователей, но в общем случае нет никаких средств контролировать произвольную группу процессов, которой, в конечном счете, является виртуальная машина. Тонкие различия между различными ресурсами операционной системы и их использованием не позволяет эффективно решить эти задачи с помощью единого подхода, хотя попытки и предпренимались [25, 26].

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

На сегодняшний день накоплено огромное количество работ и данных в этой области, но до сих пор отсутствует единая теоретическая модель, способная связать все необходимые модели и учесть их особенности совместной работы в единой системе. Математическое моделирование в этой ситуации видится мощным инструментом для развития такой единой теоретической модели. Математическому моделированию процессов работы с памятью посвящено большое количество работ за рубежом [27, 28, 29, 30, 31]. В последнее время тема активно развивается и в нашей стране [33, 32, 34].

Цель работы

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

• обеспечивать изоляцию виртуальных сред друг от друга;

• ограничивать виртуальные среды в потреблении физической памяти;

• обеспечивать требуемый уровень сервиса для виртуальных машин.

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

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

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

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

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

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

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

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

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

Часть реализованного программного комплекса была внедрена автором совместно со специалистами из компаний IBM и Google в основное ядро Unix-подобной операционной системы Linux2, которая является одной из наиболее популярных операционных систем и установлена как на домашних компьютерах, так и на крупных серверах по всему миру.

Кроме того, реализация всех описанных моделей была внедрена в продукты компании Parallels Virtuozzo Containers3 и OpenVZ4, представляющие собой виртуализационные решения на базе ядра Linux. Их использование показало, что модели представляют не только теоретический интерес, но и успешно решают поставленные перед ними практические задачи, а именно - позволяют контролировать потребление физической памяти виртуальной машиной или «контейнером».

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

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

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

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

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

Заключение

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

• обеспечивает изоляцию виртуальных сред друг от друга;

• ограничивает виртуальные среды в потреблении физической памяти;

• обеспечивает требуемый уровень сервиса для виртуальных машин.

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

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

1. Разработана математическая модель предоставления гарантий выделения группам процессов физической памяти. Показана применимость модели к другим типам ресурсов на примере задачи распределения процессорного времени.

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

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

1. Э. Таненбаум, А. Вудхалл Операционные системы. Разработка и реализация. // изд. Питер — СПб.: 2006 - 1.BN 5-469-00148-2

2. Stanley A. Kurzban, Thomas S. Heines, Anthony P. Sayers Operating systems principles (2nd ed.) // Van Nostrand Reinhold Data Processing Series — New York: 1984 — ISBN 0-442-25734-1

3. Arthur E. Oldehoeft, Mamoru Maekawa, Rodney R. Oldehoeft Operating Systems: Advanced Concepts // The Benjamin-Cummings Publishing Company, INC — 1987 ISBN 0-8053-7121-4

4. Luis Silva, Javier Alonso, Paulo Silva, Jordi Torres, Artur Andrzejak Using Virtualization to Improve Software Rejuvenation // IEEE-NCA — Cambridge, MA, USA 2007

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

6. Александр Самойленко Виртуализация: новый подход к построению IT-инфраструктуры Электронный ресурс] / журнал iXBT, [2007]. — Режим доступа: http://www.ixbt.com/cm/virtualization.shtml, свободный. — За-гл. с экрана. — Яз. русск.

7. 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.

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

9. IDC: Virtualization market booming Электронный ресурс] / журнал Network World, [2006]. — Режим доступа: http: / / www.networkworld.com/news/2006/102506-idc-virtualization.html, свободный. — Загл. с экрана. — Яз. англ.

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

11. Александр Самойленко Технологии аппаратной виртуализации Электронный ресурс] / журнал iXBT, [2007]. — Режим доступа: http://www.ixbt.com/cm/virtualization-h.shtml, свободный. — Загл. с экрана. — Яз. русск.

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

13. Parallels, optimized computing Электронный ресурс] / Parallels, Virtualization and Automatization Software, [2008]. — Режим доступа: http://parallels.com, свободный. — Загл. с экрана. — Яз. англ.

14. Kernel Based Virtual Machine Электронный ресурс] / OpenSource project, [2008]. — Режим доступа: http://kvm.qumranet.com/kvmwiki, свободный.

15. Загл. с экрана. — Яз. англ.

16. Bochs IA-32 Emulator Project Электронный ресурс] / OpenSource project, [2008]. — Режим доступа: http://bochs.sourceforge.net, свободный. — Загл. с экрана. — Яз. англ.

17. QEMU open source processor emulator Электронный ресурс] / OpenSource project, [2008]. — Режим доступа: http://bellard.org/qemu/, свободный. — Загл. с экрана. — Яз. англ.

18. Д. Н. Колисниченко Fedora 8. Руководство пользователя // Диалектика М.: 2008. - ISBN 978-5-8459-1360-9

19. Денис Колисниченко Ubuntu Linux. Краткое руководство пользователя // БХВ-Петербург СПб.: 2007 - ISBN 978-5-9775-0104-0

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

21. Ubuntu Электронный ресурс] / Canonical LTD, [2008]. Режим доступа: http://www.ubuntu.com, свободный. — Загл. с экрана. — Яз. англ.

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

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

24. Banga G., Druschel P., Mogul J. Resource containers: A new facility for resource management in server systems // Proceedings of the USENIX

25. Symposium on Operating System Design and Implementation (OSDI). — 1999. — Pp. 45-48.

26. Timothee Bossart, Alix Munier Kordon, Francis Sourd Memory management optimization problems for integrated circuit simulators // Elsevier Science Publishers В. V. — Amsterdam, 2007.

27. Patrick R. Amestoy Memory Management Issues in Sparse Multifrontal Methods On Multiprocessors // International Journal of High Performance Computing Applications, 1993 — Vol. 7, Ж 1, Pp. 64-82.

28. S. Rixner, W. J. Dally, U. J. Kapasi, P. R. Mattson, and J. D. Owens Memory access scheduling // ISCA, 2000, pp. 128-138.

29. Gokul B. Kandiraju Towards self-optimizing memory management //A Thesis in Computer Science and Engineering — The Pennsylvania State University, 2004.

30. Carlos Macian, Sarang Dharmapurikar, John Lockwood Beyond Performance: Secure and Fair Memory Management for Multiple Systems on a Chip // Proceedings of IEEE International Conference on Field-Programmable Technology (FPT), 2003.

31. Соколов А. В. Анализ эффективности алгоритмов динамического распределения нестраничной памяти // Труды II Международной конференции «Развитие и применение открытых систем». — Петрозаводск 1995. — Сс. 76-77.

32. Белоусов С. М. Об одном подходе к эффективному распределению ресурсов вычислительной системы. // Процессы и методы обработки информации. Сборник научных трудов. — М.:МФТИ, 2005 — Сс. 58-67.

33. Луковников И., Коротаев К., Кобец А. Проблемы управления распределяемыми ресурсами ОС // Информационные технологии. — М. 2006. — №10 Сс. 71-78.

34. The Xen virtual machine monitor Электронный ресурс] / Open Source project, [2007]. — Режим доступа:http://www.cl.cam.ac.uk/research/srg/netos/xen/, свободный. — За-гл. с экрана. — Яз. англ.

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

36. Роберт Лав Разработка ядра Linux = Linux Kernel Development. — 2-е изд. // «Вильяме» — M.: 2006. — ISBN 0-672-32720-1

37. Daniel P. Bovet, Marco Cesati Understanding the Linux Kernel // O'Reilly, 2002. ISBN: 0-596-00213-0

38. Андрей Робачевский, Сергей Немнюгин, Ольга Стесик Операционная система UNIX // БХВ-Петербург СПб.: 2007. — ISBN 5-94157-538-6

39. Вахалия Ю. UNIX изнутри // Питер СПб.: 2003. — ISBN 5-94723-013-5

40. Inside Macintosh: Memory // Apple Computers, Inc. — 3 JUL 1996.

41. Inside MAC OS X. System Overview // Apple Computer, Inc., 2001. — Chapter 2: System Technologies.

42. DJ Delorie Handling CPU Exceptions Электронный ресурс] / 1999 — Режим доступа: http://www.delorie.eom/djgpp/doc/dpmi/ch4.5.html, свободный — Загл. с экрана. — Яз. англ.

43. Maurice Herlihy, Nir Shavit The Art of Multiprocessor Programming // Morgan Kaufmann Publishers — Burlington: 2008. — ISBN: 978-0-12-3705914

44. René Moreau The Computer Comes of Age: The People, the Hardware, and the Software 11 MIT Press, 1984. — ISBN 0-262-13194-3

45. Herman Lukoff From Dits to Bits. : A Personal History of the Electronic Computer // Robotics Press, 1979. — ISBN 89661-002-0

46. Simon Lavington Early British Computers // Digital Press (US) and Manchester University Press (UK), 1980 — ISBN 0-932376-08-8 Ch 15. Programming an early computer — Pp. 87-98

47. Michael Singer PDP-11. Assembler Language Programming and Machine Organization 1980 - John Wiley & Sons, NY

48. B.H.Пильщиков ЯЗЫК МАКРОАССЕМБЛЕРА IBM PC (Справочное пособие) — 1992 МГУ, ВМК — Разд. 1.4 - Сегментирование

49. Евгений Панкратов Операционная система MS-DOS 6.22. Справочное пособие — Познавательная книга Плюс — М.: 2002. — ISBN 5-8321-01323

50. Rodnay, Zaks, Rodnay The CP/M Handbook With MP/M. — SYBEX Inc.: 1980.

51. В. H. Пильщиков Assembler. Программирование на языке ассемблера IBM PC Диалог-МИФИ - M.: 2005. - ISBN 5-86404051-7

52. Юрий Магда Ассемблер для процессоров Intel Pentium — Питер — СПб.: 2006. ISBN 5-469-00662-Х

53. Multics (Multiplexed Information and Computing Service) Электронный ресурс] / OpenSource project, 2007 — Режим доступа: http://www.multicians.org/, свободный — Загл. с экрана. — Яз. англ.

54. CDC KRONOS Электронный ресурс] — Режим доступа: http://en.wikipedia.org/wiki/CDCKRONOS, свободный — Загл. с экрана. — Яз. англ.

55. Алексей Федорчук Доступный UNIX. Linux, FreeBSD, DragonFlyBSD, NetBSD, OpenBSD БХВ-Петербург - СПб.: 2006. - ISBN 5-94157-876-8

56. Gordon E. Moore Cramming more components onto integrated circuits — Electronics Magazine, 1965 — №8, Vol. 38.5

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

58. Richard McDougall, Jim Mauro Solaris Internals: Solaris 10 and OpenSolaris Kernel Architecture (2nd Edition) — Sun Microsystems, 2000. — Chapter 6.

59. FreeBSD Handbook Электронный ресурс] / The FreeBSD Documentation Project, [2008]. — Режим доступа: http://www.freebsd.org/doc/enUS.IS08859-1/books/handbook/index.html, свободный. — Загл. с экрана. — Яз. англ. — Chapter 15: Jails.

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

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

62. IA-32 Intel Architecture. Software Developer's Manual // Intel, 2002. — Vol. 1, Chapter 2: Introduction to the IA-32 Intel Architecture.

63. Intel Itanium Architecture. Software Developer's Manual // Intel, 2002. — Vol. 1, Chapter 3: Execution Environment.

64. Brett Olsson, Anthony Marsala A developer's guide to the POWER architecture // IBM, 2004. — Book III. Operating environment architecture.

65. UltraSPARC Architecture 2005 // Sun Microsystems, 2008. — Chapter 3.3.1: Memory Access.

66. Andrew Sloss, Dominic Symes, Chris Wright ARM System Developer's Guide: Designing and Optimizing System Software // Morgan Kaufmann, 2004. — Chapter 14: Memory Management Units.

67. Mel Gorman Understanding the Linux Virtual Memory Manager // Prentice Hall, 2004.

68. Setrlimit set resource limits and usage Электронный ресурс] / Unix manual pages. — Режим доступа: http://linux.about.com/library/cmd/blcmdl2setrlimit.htm, свободный — Загл. с экрана. — Яз. англ.

69. Carl A. Waldspurger Memory Resource Management in VMware ESX Server // Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI£02) — Boston, USA, 2002.

70. Xen Memory Management Электронный ресурс] / Open Source project, [2006]. — Режим доступа: http://wiki.xensource.com/xenwiki/XenMemoryManagement, свободный — Загл. с экрана. — Яз. англ.

71. Andrey V. Savochkin User Beancounter Patch Электронный ресурс] / [2000] — Режим доступа: http://www.asplinux.ru/en/install/ubpatch.shtml, свободный — Загл. с экрана. — Яз. русск.

72. Jonathan Corbet Resource beancounters Электронный ресурс] / Linux Weekly News, [2006]. — Режим доступа: http://lwn.net/Articles/197433/, свободный. — Загл. с экрана. — Яз. англ.

73. Jonathan Corbet Notes from a container Электронный ресурс] / Linux Weekly News, [2007]. — Режим доступа: http://lwn.net/Articles/256389/, свободный. — Загл. с экрана. — Яз. англ.

74. User Beancounters — a set of limits and guarantees controlled per container Электронный ресурс] / OpenVZ documentation, [2008]. — Режим доступа: http://wiki.openvz.org/Userbeancounters, свободный. — Загл. с экрана. — Яз. англ.

75. Емельянов П. В., Коротаев К. С. Математическая модель обеспечения гарантий выделения ресурсов операционной системы // Информационные технологии. — М. 2008 — № 3 — С. 83-85.

76. Емельянов П. В. Оптимизация модели контроля потребления памяти группой процессов // Вестник Новосибирского Государственного Университета. Серия: Информационные Технологии — 2008 — Т. 6, вып. 1 -С. 37-46.

77. Pavel Emelianov, Denis Lunev, Kirill Korotaev Resource Management: Beancounters // Proceedings of the Linux Symposium — Ottawa: 2005. — Pp. 285-292.

78. Pavel Emelianov, Denis Lunev, Kirill Korotaev Resource Management: Beancounters // Proceedings of the LinuxConf Europe — Cambridge: 2007. -7 Pp.

79. Kevin R. Wadleigh, Isom L. Crawford Software Optimization for High Performance Compiting: Creating Faster Applications. — Prentice Hall PTR, 2000. — Chapter 7.4: Subroutine of Function Call Overhead.

80. Christos H. Papadimitrion, Kenneth Steiglitz Combinatorial Optimization, Algorithms & Complexity // Dover Publishers, Inc. — Dover, 1998. — ISBN 0-486-40258-4

81. 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. 131144.

82. Peter J. Denning The working set model for program behavior // Communications of the ACM, 1968. — №5/1968, Volume 11, pp. 323-333.

83. Denning, P. J. Working Sets Past and Present // IEEE Transactions on Software Engineering, 1980. — №1/1980, Volume SE-6, pp. 64-84.

84. File locking Электронный ресурс] // Wikipedia the Free Encyclopedia, [2008]. — Режим доступа: http://en.wikipedia.org/wiki/Filelocking, свободный — Загл. с экрана. — Яз. англ.

85. UnixBench Электронный ресурс] / Suite for POSIX system benchmarking, [2007]. — Режим доступа: http://sourceforge.net/projects/unixbench/, свободный. — Загл. с экрана. — Яз. англ.

86. Dan Westom The Complete Book of Macintosh Assembly Language Programming // Scott, Foresman and Company — London, 1986 — ISBN: 0-673-18379-3

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

88. A NUMA API for Linux // Novell, 2005. — Technical Linux Whitepaper.

89. В.П. Гергель, P.P. Стропгип Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие // Издательство Нижегородского госуниверситета — НН.: 2003. — Сс. 30-31.

90. Marshall Brain Win32 System Services. The Heart of Windows 95 and Windows NT. Second edition // Prentice Hall PTR. — New Jersey, 1996.

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

92. Дональд Э. Кнут Искусство программирования. Том 1. Фундаментальные алгоритмы // Вильяме. — М.: 2005. — Сс. 435-455.

93. Christoph Lameter SLUB: The unqueued slab allocator V6 Электронный ресурс] / Linux Weekly News, [2007]. — Режим доступа: http://lwn.net/Articles/229096/ — Загл. с экрана. — Яз. англ.

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

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

96. Линус Торвальдс, Дэвид Даймонд Just for Fun. Рассказ нечаянного революционера // Эксмо-Пресс — М.: 2002.

97. Maurice J. Bach The Design of the UNIX Operating System // Prentice-Hall, 1986 — Chapter 3: Operating memory buffer (cache).