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

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

КОБЕЦ Алексей Леонидович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ НАЛОЖЕННОГО УПРАВЛЕНИЯ РЕСУРСАМИ ВИДА "ПОТОКИ ВВОДА-ВЫВОДА" В ОПЕРАЦИОННЫХ СИСТЕМАХ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

003 1В1Т14

Москва - 2007

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

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

Тормасов Александр Геннадиевич

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

профессор

Семенихин Сергей Владимирович

кандидат технических наук старший научный сотрудник Шилов Валерий Владимирович

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

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

Защита состоится «9_» диссертационного совета К 212 156 02 при Московском физико-техническом институте (Государственном университете) по адресу 141700, г Долгопрудный, Московской обл , Институтский пер д 9 , ауд 903 КПМ

•30

_ноября_2007 года в|2- часов на заседании

С диссертацией можно ознакомиться в библиотеке МФТИ

Автореферат разослан « Ь » октября 2007 г

Ученый секретарь диссертационного совета К 212 156 02

Федько О С

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

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

Производительность современных операционных систем существенно зависит от производительности операций ввода-вывода, но производительность дискового оборудования растет меньшими темпами Например, производительность RISC-процессора увеличивается приблизительно на 50% в год, а скорость доступа к диску лишь на 10% [данные с сайта http //www sisoftware netl На уровне программного обеспечения основными факторами, обостряющими данную проблему, являются

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

• Развитие средств мультимедиа, которое порождает необходимость хранения больших объемов данных на диске и более надежного и быстрого доступа к этим данным,

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

Намечается тенденция роста интереса к системам виртуализации в IT индустрии Например, основные игроки на рынке производителей процессоров, Intel и AMD, внедряют технологии аппаратной виртуализации, Virtualization Technology и Pacifica, соответственно, производители операционных систем, такие как, Microsoft, Apple и Linux, включают в свое программное обеспечение поддержку виртуализации Существует ряд компаний или открытых проектов, которые разрабатывают исключительно средства виртуализации операционных систем (VMware, Xen, SWsoft) Существуют также средства дисковой виртуализации, например, Loopback Device в семействе операционных систем Unix или Virtual Disk в Microsoft Windows или VMware Workstation

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

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

• Пропускная способность распределяется согласно соглашению об уровне сервиса (Service Level Agreement),

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

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

Отметим, что задачи такого уровня актуальны для средств встроенной виртуализации ОС

Цель работы, задачи исследования

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

• Управление осуществляется на основе стандартных механизмов управления ресурсами ОС

• Интервалы, на которых осуществляется такое управление, превышают интервалы, на которых работают механизмы управления самой ОС

Задачи исследования:

• Разработка математической модели группового наложенного управления ресурсами вида потоки ввода-вывода в современных ОС

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

• Исследование и объяснение, в рамках данной модели, существующих механизмов контроля ресурсов дискового ввода-вывода в современных ОС

Объект исследования - алгоритмы планирования подсистемы ввода-вывода в ОС

Предмет исследования - механизмы управления ресурсами ввода-вывода в современных ОС

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

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

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

Предложенная модель была реализована как часть программного комплекса Уи1ио2жо Был проведен ряд экспериментов с использованием данного комплекса

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

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

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

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

Практическая значимость

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

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

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

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

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

По выполненным диссертационным исследованиям опубликовано 10 работ, в том числе три [1,4,5] - в ведущих научных журналах, рекомендованных ВАК РФ В опубликованных работах автору принадлежит более 40% материала, связанного с изложением основ математической модели наложенного управления ресурсами (включая группы потоков ввода-вывода) с использованием виртуальных сред

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных конференциях и семинарах XI Всероссийской научно-практической конференции «Научное творчество молодежи», посвященной 50-летию СО РАН 2007 г Анжеро-Судженск, Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО, 2006 г Томск, Московской международной конференции по вычислительной молекулярной биологии(МССМВ'07), 2007 г, семинары кафедры информатики МФТИ (2001-2007гг), семинар в ВЦ РАН под руководством члена-корреспондента РАН Флерова Ю А (2006г)

Также результаты докладывались и получили одобрение специалистов на научных семинарах, проводимых кафедрой информатики МФТИ

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

Положения, выносимые на защиту

На защиту выносятся следующие основные положения

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

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

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

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

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

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

В главе 1 содержится обзор существующих алгоритмов реализации управлением дискового ввода-вывода Алгоритмы разбиты на две группы

• Аппаратные, которые реализованы в самих устройствах дисков, о которых операционной системе зачастую не известно,

• Системные, которые являются частью операционной системы или построены «над» ней

В качестве аппаратных алгоритмов рассмотрены FCFS, SSTF, Elevator, EDF, LSF, P-SCAN, FD-EDF, SCAN-EDF, SSDEO, SSDEV и др Из системных алгоритмов рассмотрены Rate-Monotonie, WFQ, FairSched, P-SFQ, пропорциональное планирование на базе вектора ошибки, WRR, Lottery Scheduling и др Для всех рассмотренных алгоритмов показаны преимущества и недостатки Рассмотрено сравнение алгоритмов планирования на основе приоритетов и пропорциональности, приведена таблица Далее рассмотрено комбинированное планирование, как отдельный класс планировщиков Приведены преимущества использования комбинированных планировщиков, а также способы их реализации Отдельно рассмотрен фильтр Калмана, как инструмент для достижения заданной точности через определенный круг итераций, показана его математическая реализация, приведены примеры продуктов, в которых он используется

Глава 2 посвящается постановке задачи путем составления модели наложенного управления и исследования ограничений, которые требуется наложить, для обеспечения требуемым качеством обслуживания(С)о8) Вводиться понятие наложенного управления Рассматриваются особенности построения модели, ее ограничения и способы реализации В дальнейшем речь идёт в основном о ресурсах дискового ввода-вывода

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

потребления, как функции собственного^*), системного^) и идеального(7**) времени соответственно

R,(t*), R?(t), ЯГ(") (1)

Собственное время - это время, которое идет только, если задача потребляет ресурс, если ресурс не потребляется, то время «замораживается» Системное время - время, в котором задача получала ресурс Идеальное время - это время, исполняясь в котором достигается требуемое качество обслуживания, т е наложенное планирование работает так, как требуется

Любая функция потребления, по определению, может принимать только 3 значения, это 1 - когда ресурс потребляется, 0 - когда задача простаивает, -1 - когда ресурс освобождается, т е справедливо

Далее, для случаев потребления нескольких(К) ресурсов, по аналогии с функциями потребления, вводятся векторы желаемого, фактического и идеального потребления Вектор желаемого потребления

Рассматриваются основные свойства вектора потребления

• Координаты вектора потребления могут иметь ненулевую ковариацию (зависеть друг от друга) Например, копирование файла через сеть приводит не только к использованию дисковой пропускной способности, но и сетевой

• Координаты так же удовлетворяют (2)

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

• Поскольку все ресурсы операционной системы связаны, иногда сложно определить - какой параметр изменился, например, при возникновении ошибки страницы (Page Fault) [сс], можно считать, что либо процессорное время используется, либо пропускная способность жесткого диска В таких ситуациях решение принимается согласно принятой модели планирования

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

Далее утверждается, что справедливо неравенство

Я, (/*) 6 {0,1,-1}

(2)

Л?«*))

(3)

обусловленное следующими факторами

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

b) Эффект CPU boosts, приоритет процесса при завершении операции ввода-вывода будет поднят стандартным планировщиком Windows 2003 Server

c) Swapping - операции работы с файлом подкачки памяти

d) Влияние аппаратного уровня Например, многие современные портативные компьютеры могут менять тактовую частоту процессора, что в свою очередь меняет и «скорость» работы задачи Данный эффект наблюдается при работе виртуальных серверов VMware на сервере с динамическим изменением частоты [сс], например, время внутри виртуального сервера бежит то быстрее то медленнее

e) Starvation Эффект, при котором, процесс получает ресурс после очень долгого его ожидания

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

Это преобразование «растягивает» временную ось собственного времени процесса, Г* (такое «растяжение» происходит, поскольку, например, в системе существуют другие задачи и рассматриваемой задаче ресурс может быть не предоставлен в «желаемый» им момент времени)

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

Далее приводиться иллюстрация модели на примере потребления дисковой пропускной способности На Рис 1 показана функция желаемого потребления

(5)

t =St(f )

(6)

Желаемое потребление задачи

I I I

2 3 4 5 6 7 3 9

Собственное время задачи

Рис 1. Желаемого потребление

Далее приводится пример функции фактического потребления

Фактическое потребление задачи

I I

I

3 4 5 6 7 8 9

Системное время

Рис 2. Фактическое потребление

Идеальное потребление задачи

1

123456789 10 II Идеальное время 12

Рис 3. Идеальное потребление

Из иллюстраций видно, что в собственном времени задача потребляла пропускную способность диска в момент времени 1, а фактически она потребляла в момент времени 2.

Критерием качества считается интегральное отклонение функции идеального потребления от функции фактического потребления Математически критерий качества можно сформулировать следующим образом при каких предположениях о поведении R/t) выполняется условие

Т2

J ||R;(t)~R*4t*4t))||dt<а(Т2~Тх) (7)

т\

Т1 - начало временного отрезка наложенного управления

Т2 - конец временного отрезка наложенного управления

а - допустимая погрешность с соответствующей размерностью,

Под t *(t) подразумевается зависимость идеального времени от фактического времени

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

R2=\R\ (8)

Перейдем к собственному времени задачи и перепишем неравенство (7) в виде

■г?

Tl (9)

JTp

2Rj**(Sl(i* (Ft(t*))}dt* <a(T2~Tx)

Будем классифицировать ресурсы, как предложено в работе Луковникова И В «Математическая модель двухуровневого управления ресурсами в операционных системах с закрытыми кодами»

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

может освобождать память с намного позднее запрещения ее потребления задаче

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

• Частично возобновляемые - э-то ресурсы, для которых можно запретить потребление задачей данного ресурса и через некоторое время освободить ресурсы для использования другими процессами Например, физическая память задачи Обычно за освобождение и выделение таких ресурсов отвечает некая подсистема (в случае памяти - подсистема управления памятью ОС) Можно запретить процессу потреблять память, и, при необходимости, подсистема управления памятью ОС освободит физическую память для других процессов за счет выпихивания памяти данного процесса в файл подкачки

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

Далее делается допущение Пусть ОК1(Р1(1*)) - функция, описывающая неконтролируемые эффекты операционной системы Тогда функция желаемого потребления будет выглядеть

=(ю)

Д^-РД/*)) - это некоторая «реальная» функция потребления, без учетов неконтролируемых эффектов операционной системы В случае идеального наложенного планирования, когда гарантия совпадает с лимитом справедливо выражение

7 (< = Ъ(Тг-Тх) = ЬАТ (11)

УЛЬ

Где

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

Далее допускается, что без учета эффекта ОС задача потребляет возобновляемый ресурс точно так, как заявлено в требованиях по качеству обслуживания, т е справедливо равенство

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

Далее кратко рассматриваются невозобновляемые и частично возобновляемые ресурсы Анализируется вид неравенства (9) применительно к таким ресурсам

Переходим к описанию модели наложенного группового управления

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

• Все задачи в группе на рассматриваемом интервале времени потребляют один и тот же возобновляемый ресурс

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

Будем считать, что в любой момент времени ресурс может потреблять только одна из задач группы Группа задач характеризуется функцией желаемого потребления GR, которая равна 1, если хотя бы одна из задач группы потребляет ресурс, равна 0, если никакая из задач группы ресурс не потребляет Таким образом, для возобновляемых ресурсов

(12)

Учитывая равенства (10), (11), (12), после преобразований получаем

(13)

dt* +ЬАТ-аАТ

GR(tgr)a{ 0,1}

(14)

Где - это собственное время группы задач

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

Стоит отметить, что под задачей, обычно подразумевается поток, поэтому можно говорить группа потоков

Рассмотрим группу, состоящую из 2-х потоков, один из которых потребляет ресурс в моменты системного времени(кванты) 2, 7 и 11, а второй только в 9 Преобразование системного времени в групповое время, а затем в собственное время первого потока представлено на Рис 4

Интенсивность "обменов

Собственное время потока

Рис 4. Преобразование времени

Значение функции потребления ОН совпадает со значением функции потребления 1-го потока в группе, когда г-й поток потребляет ресурс, те =1 Очевидно, т к речь идет об одном ресурсе, СИ = Я1, в тот момент времени, когда г-й поток потребляет ресурс Таким образом, если мы имеем N потоков в группе, которые потребляют один ресурс, то поскольку в каждый момент времени ресурс потребляется одним потоком

= П5)

1=1

~ функция преобразования времени группы в собственное время потока, tgr — собственное время группы потока

(* = Р(^Г) (16)

Функция преобразования собственного времени группы в реальное (системное) время выглядит следующим образом

( = (17)

Данные функции «растягивают» временную ось собственного времени группы до собственного времени задачи (см Рис 4)

В связи с эффектами внешней среды, введем, функцию фактического потребления СД (I), которая зависит от реального времени, для которой справедливо неравенство

ОК*({)фОК({) (18)

Пусть СЖ**(1ег*) - это функция идеального потребления, те та же самая функция, что и функция желаемого потребления, но в идеальном времени группы ё' Идеальное время группы Рг - это время при котором идеально выполняется наложенное нами ограничение (например, гарантия доли дисковой пропускной способности для группы в целом) Отметим, что ограничения наложены на отдельно взятую задачу из группы могут и не выполняться Функция преобразования собственного времени группы в в идеальное время

(19)

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

Особенности построения векторов фактического, желаемого и идеального потребления ничем не отличаются от модели на основе задачи

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

J IIGR*(t)-GR*V*(0)IIdt< A(T2~Tx) (20)

Tl

Где

Tl - начало временного отрезка наложенного управления

Т2 - конец временного отрезка наложенного управления

А — допустимая погрешность с соответствующей размерностью,

Под fr>(t) подразумевается зависимость идеального времени от фактического времени Используем ту же меру векторов потребления для групп потоков Перейдем от векторов потребления к отдельно взятым аргументам Учитывая свойство нашей меры, имеем

Т2

j (2i) п

Поскольку, функция потребления удовлетворяет свойству (15), то, как следствие, для функций потребления группы справедливо свойство (8) Учитывая это свойство, и, переходя к собственному времени группы, имеем

Т2

J {\GR *0F *(!&")) | +1 GR (lgD I -

Tl (12)

2GR *'*(Ssr (tgr))GR *(Fgr (tgr ))} - dtgr < A(T2 - 7,)

Теперь, представим функцию фактического потребления как сумму реальной функции потребления и влияния вносимого эффектом ОС

GR *(FZr(tsr)) = GR (FSr{ts''))+DG(FZr(tSr)) (13)

Учитывая, что каждая задача в группе удовлетворяет выражению (11), мы можем утверждать, что группа удовлетворяет

7 (GR dtgr = ВАТ (14)

Tl

Где

В - доля возобновляемого ресурса выделенная группе, которая является постоянной на данном временном интервале

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

T]GR(FZ4t^))dF^ridtgr >

П * (15)

Т2 . dF^it }

I DG(F g (t )) У >dtgr +ВАТ-ААТ

74 dt

Таким образом, накладывая ограничения на функцию преобразования времени F^ifgr), путем изменения скорости потребления (уменьшая значение производных в формуле (1 33), замедляя собственное время группы ограничивая доступ к диску для всех потоков группы) и анализируя поведение системы в режиме реального времени, мы можем достигать приемлемую точность выделения пропускной способности диска

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

В главе 3 рассмотрен способ практического применения модели, для распределения пропускной способностью диска в случае возникновения конкуренции между несколькими группами потоков нескольких виртуальных серверов на примере системы Virtuozzo Linux (ядро 2 6 9-023stab033 7-smp, 4Гб RAM, 170Гб SCSI диск, 2 CPU) Производиться ряд экспериментов показывающих эффективность данной модели

Запускается один виртуальный сервер, внутри него порождается дисковая активность чтения 64Кб блоков из Зх файлов, суммарного размера 3Гб Находиться относительный максимум полосы пропускания в зависимости от количества потоков читающих диск Величина 64Кб выбрана не случайно, поскольку это стандартная единица обмена между дисковым кешом и диском Перед каждым замером производиться перезагрузка системы, для очищения дискового кеша Данная зависимость показана сплошной линией на Рис 6

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

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

запросов, в конце концов, происходит одним из алгоритмов аппаратного планирования, подробно рассмотренных в первой главе Падение полосы пропускания с возрастанием количества потоков объясняется эффектом рэндомизации запросов, те при чтении или записи большим количеством потоков, головка диска вынуждена совершать гораздо больше «прыжков» Так же большое влияние на пропускную способность влияет фрагментация диска, чем хаотичнее разбросаны данные, тем дольше их поиск Использование процессора не превышало 10% в обоих случаях, что говорит об отсутсвии CPU голодания Большая величина значения при малом количестве потоков записи обусловлена работой дискового кеша

Далее рассматривается группы потоков с просыпающими и засыпающими потоками В основе эксперимента лежала следующая программа Создается N процессов, внутри каждого процесса создается несколько потоков, которые по очереди читают 640Кб(10 итераций по 64Кб) и засыпают Таким образом, мы имеем N потоков в единицу времени, которые чередуются через определенные периоды Объединим эти потоки в группу Данный эксперимент показывает работу группового времени, поскольку время группы в целом идет, а время отдельного потока - нет Схематически, функцию потребления такой группы можно представить, как показано на Рис 5 Здесь группа потребляет в течение квантов времени от 0 до 15, первый поток в кванты от 0 до 1 и от 10 до 11, второй от 1 до 2 и от 11 до 12, остальные потоки для простоты иллюстрации опущены

см см

is м

о о О о

и S ё й

п с: ......Т -----Т-........-!---------Г..........'! • -"1-----------?--- с. с.

0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 Собственное время группы потоков

Рис 5 Пример функции потребления группы

Далее рассматривается зависимость пропускной способности чтения или записи в зависимости от N на таких группах Результат, получается предсказуемым, поскольку мы снова приходим к некоторой постоянной пропускной способности обусловленной аппаратным планировщиком

Зависимость изображена пунктирной линией, см. Рис. 6-7, для чтения и записи соответственно.

Зависимость полосы прот екания от количества потоков

Количество потоков

Рис 6. Полоса пропускания от количества потоков чтения в группе

Зависимость полосы пропускания от ,, количества потоков записи

Количество потоков

Рис 7. Полоса пропускания от количества потоков записи в группе

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

Далее рассматривается способ распределения пропускной способности диска между двумя виртуальными серверами с требуемым соотношением(33% и 66%) доли пропускной способности между ними.

Запускается два виртуальных сервера, в каждом запускается группа из 10 потоков, читающая и пишущая на диск В каждой группе 5 потоков пишут, а 5 потоков читают, происходит чередование потоков как в предыдущем примере Как следствие, при паритетном запуске этих двух групп му получаем пропускную способность суммы в 16 Мб/сек, стандартный планировщик системы должен выдать им равное количество пропускной способности диска Пусть, теперь мы хотим достигнуть соотношения 11 к 5 для отношения потребления этими группами пропускных способностей Для этих целей мы будем тормозить вторую группу таким образом, чтобы её потребление было 5 Мб/сек Сделаем оценку задержки, которую нужно осуществлять при чтении или записи потокам второй группы Если времена относятся обратно пропорционально полосе потребления группы, то новое собственное время должно быть в 8/5 раз медленнее первоначального Теперь, поскольку группа поедает 8Мб в секунду, а за одно обращение мы пишем или считываем 64Кб, таким образом, группа 128 раз должна сделать обращение к диску, т е наша задержка при обращении должна быть

i^b^« 0,0047 (16)

128

секунд

На практике, для достижения требуемого соотношения потребовалась большая задержка, поскольку при добавлении задержек уменьшается и количество обращений, т е общая пропускная полоса уменьшается Практическая величина задержки 0,0053 сек

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

Fgr(tgr) = 1,6784 *t (17)

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

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

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

1 Разработана математическая модель группового наложенного управления ресурсами вида потоки ввода-вывода в ОС

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

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

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

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

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

2 Луковииков И, Коротаев К, Кобец А, Проблемы управления распределяемыми ресурсами ОС// Приоритетные направления модернизации общего образования Материалы Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО -Т 1 -Томск ТОИПКРО, 2006 - С 180—181

3 Тормасов А Г, Кобец А Л, Луковииков В В, Модель управления группами потоков ввода/вывода с заданной точностью// Моделирование процессов обработки информации Сб науч тр / М Моек физ -тех инст, 2007 - С 272—275

4 Кобец А Д Луковииков В В, Пименов В М, Соколов Е В , Оценка точности группового наложенного управления ресурсами операционной системы для дискового ввода/вывода //"Вестник НГУ Серия Информационные технологии" 2007, Т 5, вып 1, С 28-31

5 Пименов В М, Соколов ЕВ, КобецА Л, Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных// "Вестник НГУ Серия Информационные технологии" 2007, Т 5, вып 1, С 32-39

6 Kobets А, Votyakov К, Lukovnikov V, Optimization of resources distribution for high performance computation// Moscow Conference on Computational Molecular Biology (MCCMB'07), http //mccmb genebee msu su/2007/. - 2c

7 Кудрин МЮ, Гилимьянов P Ф, Кобец А Л, Луковииков В В, Сравнение цепочечной модели с существующими распределенными объектными моделями// Научное творчество молодежи Часть IV Материалы XI Всероссийской научно-практической конференции - Кемерово Кемеровский гос универ-т, - С 7-8

8 Петров В А , Луковииков В В, Кобец А Л, Влияние пропускной способности соединений на длительность поиска в регулярных распределенных системах// Научное творчество молодежи Часть IV Материалы XI Всероссийской научно-практической конференции - Кемерово Кемеровский гос универ-т,-С 10-11

9 Тормасов А Г, Кобец А Л, Луковников В В, Модель оценки точности группового наложенного управления ресурсами операционной системы на примере дискового ввода/вывода// Научное творчество молодежи Часть IV Материалы XI Всероссийской научно-практической конференции -Кемерово Кемеровский гос универ-т,-С 13-14

10 Votyakov К, Kobets А , Semi-macroscopic model for computation of electrostatic effects m membrane proton pump - bactnorhodopsin// Moscow Conference on Computational Molecular Biology (MCCMB'07),

http //mccmb genebee msu su/2007/. - 2c

Кобец Алексей Леонидович

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ НАЛОЖЕННОГО УПРАВЛЕНИЯ РЕСУРСАМИ ВИДА "ПОТОКИ ВВОДА-ВЫВОДА" В ОПЕРАЦИОННЫХ СИСТЕМАХ

Автореферат

Подписано в печать 01 10 2007 Формат 60x90/16 Уел печ л 1 0 Тираж 80 экз Заказ No 470 Московский физико-технический институт (государственный университет)

Печать на аппарате Rex-Rotary Copy Printer 1280 НИЧ МФТИ

141700, г Долгопрудный Московской обл, Институтский пер, 9, тел (095) 4088430, факс (095) 5766582

ОГЛАВЛЕНИЕ.

ВВЕДЕНИЕ.

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

Цель работы, объект и предмет исследования.

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

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

Практическая значимость.

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

Положения, выносимые на защиту.

ГЛАВА 1 ОБЗОР СУЩЕСТВУЮЩИХ МОДЕЛЕЙ УПРАВЛЕНИЯ РЕСУРСАМИ

1.1 First Come First Served (FCFS/FIFO/LIFO) алгоритм.

1.2 Shortest Seek Time First (SSTF) алгоритм.

1.3 Elevator (SCAN, C-SCAN, LOOK, C-LOOK) алгоритм.

1.3.1 SCAN алгоритм.

1.3.2 Cyclical SCAN (C-SCAN) алгоритм.

1.3.3 LOOK алгоритм.

1.3.4 Cyclical LOOK (C-LOOK) алгоритм.

1.4 Earliest Deadline First (EDF) алгоритм.

1.5 Least Slack Time First (LSF) алгоритм.

1.6 Priority SCAN (P-SCAN) алгоритм.

1.7 Feasible deadline SCAN (FD-SCAN) алгоритм.

1.8 Feasible deadline EDF (FD-EDF) алгоритм.

1.9 SCAN-EDF алгоритм.

1.10 Shortest Seek and Earliest Deadline by Ordering (Value) (SSEDO и SSEDV) алгоритмы.

1.10.1 SSEDO алгоритм.

1.10.2 SSEDV алгоритм.

1.11 Rate-Monotonic (RM) алгоритм.

1.12 Пропорциональное планирование.

1.12.1 Weighted Fair Queuing (WFQ) алгоритм.

1.12.2 Fair CPU Scheduler алгоритм.

1.12.3 Расширенный SFQ (P-SFQ) алгоритм.

1.13 Пропорциональное планирование на основе вектора ошибки.

1.14 Другие планировщики.

1.15 Комбинированное планирование.

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ НАЛОЖЕННОГО УПРАВЛЕНИЯ.

2.1 Постановка задачи.

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

2.3 Разновидности распределяемых ресурсов.

2.3.1 Возобновляемые ресурсы.

2.3.2 Другие ресурсы.

2.4 Потребление возобновляемых ресурсов группой задач.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3 МОДЕЛЬ И МЕТОДЫ ГРУППОВОГО НАЛОЖЕННОГО УПРАВЛЕНИЯ РЕСУРСАМИ ВИДА "ПОТОКИ ВВОДА-ВЫВОДА".

3.1 Построение модели.

3.2 Практическое подтверждение математической модели.

3.3 Классификация потребителей.

ВЫВОДЫ ПО ГЛАВЕ 3.

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

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

• Высокая стоимость серверов

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

• Большое время на «развёртывание» нового сервера

• Затраты на электричество и охлаждение серверов

• Затраты на обслуживание

• Аренда помещений для серверов

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

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

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

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

Примерами такого способа управления ресурсами могут служить технология Virtuozzo[72], Microsoft Virtual PC. [76]

Другим способом управления является выставление ограничения на группу потоков на интервалах гораздо больше времени минимального измерения регулируемого ресурса и осуществляется механизмами, которые предоставляются операционной системой. Такой способ является более простым в реализации, в тоже время при пиковых потреблениях ресурса точность управления может существенно снизиться. Примерами реализации такого способа является технологии xLswitch[75], Aurema[78],

Хеп[77], которые работают на основе средств, предоставляемых стандартным планировщиком операционной системы, изменяя приоритеты процессов в системе.

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

• Управление осуществляется на основе стандартных механизмов управления ресурсами операционной системы.

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

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

Управление ресурсами дискового ввода-вывода предоставляет дополнительный интерес, например, производительность RISC процессора растёт приблизительно на 50% в год, а время доступа к диску всего лишь на 10% [85]. Диск становиться узким местом всей системы реального времени, поэтому управление ресурсами диска предоставляет большой интерес, т.к. улучшение в управлении ресурсами ввода-вывода значительно повысит производительность системы в целом.

Цель работы, объект и предмет исследования

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

Задачи исследования:

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

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

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

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

Предмет исследования - модель группового наложенного управления ресурсами типа потоки ввода-вывода в современных операционных системах.

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

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

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

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

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

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

Практическая значимость

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

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

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

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

По выполненным диссертационным исследованиям опубликовано 10 работ, в том числе три [2,5,6]- в ведущих научных журналах, рекомендованных ВАК РФ. В опубликованных работах автору принадлежит более 40% материала, связанного с изложением основ математической модели наложенного управления ресурсами (включая группы потоков ввода-вывода) с использованием виртуальных сред.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на нескольких конференциях: XI Всероссийской научно-практической конференции «Научное творчество молодёжи», посвященной 50-летию СО РАН 2007 г. Анжеро-Судженск [81,82,84], Московской конференции по вычислительной молекулярной биологии 2007 г. [80,83], Всероссийской научно-практической конференции, посвященной 60-летию ТОИПКРО, 2006 г. Томск [71].

Также результаты докладывались и получили одобрение специалистов на научных семинарах, проводимых кафедрой информатики МФТИ.

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

Положения, выносимые на защиту

На защиту выносятся следующие основные положения:

1) Математическая модель наложенного управления ресурсами типа потоки ввода-вывода в операционных системах.

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

Выводы по главе 3.

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

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

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

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

Затем автор рассматривает разного рода потребителей. Классифицирует их следующим образом:

• Отложенная запись через кеш

• Кешированное чтение

• Принудительное чтение или запись

• Внешнее ограничение на ввод-вывод

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

Заключение

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

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

Автором решены следующие задачи:

1. Разработана математическая модель группового наложенного управления ресурсами вида потоки ввода-вывода в ОС.

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

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

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

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

Дальнейшие направления исследования автора:

1. Совершенствование математической модели группового наложенного управления, расширение модели для учета работы дискового кеш, файла подкачки памяти ОС.

2. Работа над взаимодействием данной модели с алгоритмами управления памятью, процессорного времени и сетевой пропускной способности.

1. Браммер К., Зиффлинг Г. Фильтр Калмана-Бьюси. М.: Наука, 1982.

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

3. Тормасов А.Г., Кобец А.Л., Луковников В.В, Модель управления группами потоков ввода/вывода с заданной точностью// Моделирование процессов обработки информации: Сб. науч. тр. / М.: Моск. физ.-тех. инст., 2007. С. 272—275.

4. Кобец А.Л, Луковников В.В., Пименов В.М., Соколов Е.В., Оценка точности группового наложенного управления ресурсами операционной системы для дискового ввода/вывода //"Вестник НГУ. Серия: Информационные технологии". 2007, Т. 5, вып. 1, С. 28-31

5. Пименов В.М., Соколов Е.В., Кобец А.Л., Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных// "Вестник НГУ. Серия: Информационные технологии". 2007, Т. 5, вып. 1, С. 32-39

6. Bennett,J. and Zhang.H. WFQ: Worst-case fair weighted fair queueing. In IEEE Infocom, Mar. 1996.

7. J. Bennett , H. Zhang, Hierarchical packet fair queueing algorithms, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.675-689, Oct. 1997

8. Black, D. "Scheduling and Resource Management Techniques for Multiprocessors". PhD Thesis, CMU-CS-90-152, Carnegie Mellon University, July 1990. Электронный ресурс: http://citeseer.ist.psu.edu/article/black90scheduling.html.

9. O.Bruno,J. Brustoloni,J. Gabber, E. 6zden,B. and Silberschatz A. . Disk scheduling with quality of service guarantees. IEEE ICMCS, June 1999.

10. Chen, S et el. Performance evaluation of two new disk scheduling algorithms for real-time systems.Journal of Real-Time Systems, 3(3):307-336, Sept. 1991.

11. Cormen, T. Leiserson, C., Rivest, R, and Stein C. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262-03293-7. Section 6.5: Priority queues, pp. 138-142.

12. H.Deianov B. Fair CPU Scheduler for Linux: Электронный ресурс: http://fairsched.sourceforge.net/doc/fairsched.txt.

13. Demers,A. Keshav, S. Shenker, S /'Analysis and simulation of a fair queueing algorithm",Proceedings ofSIGCOMM '89, 1989,pp. 1-12.

14. Golubchik, L. Lui, Gail, H Evaluation of tradeoffs in resource management techniques for multimedia storage servers.IEEE ICMCS, June 1999.

15. J. Guo, J. yao. An Efficient Packet Scheduling Algorithm in Network Processors. Department of Computer Science and Engineering. University of California, Riverside. Электронный ресурс: http://www.cs.ucr.edu/~bhuyan/papers/infocom05.pdf.

16. Goyal P., Guo X., Vin H. M. A hierarchical CPU scheduler for multimedia operating systems. Distributed multimedia computing laboratory. Department of Computer Sciences, University of Texas at Austin. 2001

17. Hahne, E. "Round Robin Scheduling for Fair Flow Control in Data Communication Networks", Report LIDS-TH-1631, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts. December, 1986.

18. John L. Hennessy, David A. Patterson, Computer Architecture, A Quantitative Approach (ISBN 1-55860-724-2)

19. Jensen,E Locke,K.D and Tokuda.H A time driven scheduling model for real-time operating systems. In Proceedings IEEE Real-Time Sytems Symposium, pages 112-122, 1985.

20. R. Abbott and H. Garcia-Molina. Scheduling I/O requests with deadlines: a performance evaluation. Proceedings of the Real-time Systems Symposium, pages 113-124, 12, 1990.

21. Howard, J. Kazar, M. Menees, S. Nichols, D. Satyanarayanan, M. Sidebotham,R. and West,M. . Scale and performance in a distributed file system. ACM Transactions on Computer Systems, 6( 1 ):51 -81, Feb. 1988.

22. Kargahi, M, Movaghar, A, "A Method for Performance Analysis of Earliest-Deadline-First Scheduling Policy," dsn, p. 826, 2004 International Conference on Dependable Systems and Networks (DSN'04), 2004.

23. M. Katevenis, S. Sidiropoulos, C. Courcoubetis: "Weighted Round-Robin Cell Multiplexing in a General-Purpose ATM Switch Chip", IEEE Journal on Selected Areas in Communications, vol. 9, no. 8, October 1991, pp. 1265-1279.

24. Knuth, D. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.4: Dynamic Storage Allocation, pp.435-456.

25. Lehoczky, J. Sha, L. and Ding, Y. The Rate monotonic scheduling algorithm: exact characterization and average case behavior, IEEE RealTime Systems Symposium, pp. 166-171, December 1989.

26. L. Lenzini , E. Mingozzi , Giovanni Stea, A Unifying Service Discipline for Providing Rate-Based Guaranteed and Fair Queuing Services Based on the Timed Token Protocol, IEEE Transactions on Computers, v.51 n.9, p. 1011-1025, September 2002

27. L. Lenzini, E. Mingozzi, "Packet timed token service discipline: A scheduling algorithm based on the dual-class paradigm for providing QoS in integrated services networks," Comput. Netw., vol. 39, pp. 363-384, July 2002.

28. L. Lenzini, E. Mingozzi, and G. Stea, "Full exploitation of the Deficit Round-Robin capabilities by efficient implementation and parameter tuning," Univ. of Pisa, Italy, Tech. Rep., Oct. 2003.

29. Leung, J. Y.,Whitehead J. Y. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2(4):237--250, December 1982.

30. L. Lenzini, E Mingozzi, G. Stea Tradeoffs between low complexity, low latency, and fairness with deficit round-robin schedulers. IEEE/ACM Transactions on Networking (TON.) Volume 12 , Issue 4 (August 2004), pp 681 693. SSN:1063-6692

31. L. Lenzini, E. Mingozzi, and G. Stea, "Aliquem: A novel DRR implementation to achieve better latency and fairness at 0(1) complexity," in Proc. 10th Int. Workshop on Quality of Service (IWQoS), Miami Beach, FL, May 2002, pp. 77-86.

32. Liu C.L., Layland. J. "Scheduling algorithms for multiprogramming in hard real-time environment" Journal of the ACM, 20(1):46-61, 1973

33. Liu, С and Layland, J . Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment. Journal of the ACM, 20(1):46-61, Jan. 1973.

34. C. Lumb, J. Schindler, G. Ganger, D. Nagle, and E. Riedel. Towards higher disk head utilization: Extracting free bandwidth from busy disk drives. 4th USENIX OSDI, Oct. 2000.

35. C. Ruemmler and J. Wilkes. An introduction to disk drive modeling.IEEE Computer, 27(3): 17-28, 1994.

36. А. К. Parekh and R. G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1(3):344—357, June 1993.

37. D. Saha , S. Mukherjee , Satish K. Tripathi, Carry-over round robin: a simple cell scheduling mechanism for ATM networks, IEEE/ACM Transactions on Networking (TON), v.6 n.6, p.779-796, Dec. 1998

38. Seltzer,M. Chen,P. and Ousterhout, J. . Disk scheduling revisited. USENIX Winter Technical Conference, Jan. 1990.

39. Sha, L. Rajkumar R. Lehoczky, J. P. Priority inheritance protocols: an approach to real-time synchronization, IEEE Transactions on Computers, vol. 39 no. 9, September 1990, pp. 1175-1185.

40. M. Shreedhar , George Varghese, Efficient fair queueing using deficit round-robin, IEEE/ACM Transactions on Networking (TON), v.4 n.3, p.375-385, June 1996

41. E. Shriver, C. Small, and K. Smith. Why does file system prefetching work? USENIX Annual Technical Conference, June 1999.

42. Solomon D.A, Russinovich M.E. Inside Microsoft® Windows® 2000, Third Edition, Microsoft Press, 2000

43. Stankovic,J.A. Spuri, M. Di Natale,M. and Buttazzo, G.C. Implications of Classical Scheduling Results for Real-Time Systems. IEEE Computer, pp. 16--25, 1995.

44. Stewart, D, Barr, M. "Rate Monotonic Scheduling" Embedded Systems Programming, March 2002, pp. 79-80. Электронный ресурс: http://www.netrino.com/Publications/Glossary/RMA.html.

45. Stoica I., Zhang H., Eugene Ng. T.S. A hierarchical fair service curve algorithm for link-sharing, real-time and priority services. School of Computer Science. Carnegie Mellon University. 1997

46. F. Toutain, "Decoupled generalized processor sharing: A fair queuing principle for adaptive multimedia applications," in Proc. IEEE INFOCOM , San Francisco, CA, Mar.-Apr. 1998, pp. 291-298.

47. S. Tsao , Y. Lin, Pre-order deficit round robin: a new scheduling algorithm for packet-switched networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.35 n.2-3, p.287-305, Feb. 2001

48. P. Van Emde Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Math. Syst. Theory, vol. 10, pp. 99-127, 1977.

49. C. Waldspurger and W. Weihl. Lottery scheduling: Flexible proportional-share resource management. In 1st USENIX OSDI, Nov. 1994.

50. C. Waldspurger and W. Weihl. Stride scheduling: Deterministic proportional resource management. Technical report, MIT/LCS/TM-528, June 1995.

51. Wang S., Wang Y.-Ch., Lin K.-J. A priority-based weighted fair queuing scheduler for real-time network, Electrical and Computer Engineering, University of California, Irvine. 2002

52. Wang Y.-Ch., Lin K.-J. Implementing a general real-time scheduling framework on the RED-Linux real-time kernel. Department of Electrical and Computer Engineering, University of California, Irvine. 1999

53. Williams, P. Jun 2000 Unitied States Patent 6,758,889

54. B. Worthington, G. Ganger, and Y. Patt. Scheduling algorithms for modern disk drives.In ACM Sigmetrics, 1994.

55. J. Yao, J. Guo, and Z. Xu, "Scheduling real-time multimedia tasks in network processors," IEEE GLOBECOM, Dallas,, November 2004.

56. K. Yau, J. Lui, and F. Liang. Defending against distributed denial-of-service attacks with max-min fair server-centric router throttles. In Proceedings of IEEE International Workshop on Quality of Service (IWQoS), Miami Beach, FL, May 2002.

57. H. Zhang. Providing end-to-end performance guarantees using non-work-conserving disciplines. Computer Communications, 18(10), Oct. 1995.

58. Zhang, H Resource Management For Service-Oriented Internet. School of Computer Science, Carnegie Mellon University. Электронный ресурс: http://www.cra.org/Policy/NGI/papers/zhang.

59. H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. IEEE, vol. 83, pp. 1374-1396, Oct. 1995.

60. Леви. JI. Применение фильтров Калмана в навигационной аппаратуре, Электронный ресурс: http://www.navgeocom.ru/gps/kalman/index.htm.

61. Проект Virtuozzo Электронный ресурс: http://virtuozzo.com.

62. Проект Altiris Электронный ресурс: http://altiris.com.

63. Проект OpenVZ Электронный ресурс: http://openvz.org.

64. Проект xLswitch Электронный ресурс: http://swsoft.com.

65. Проект Microsoft Virtual PC Электронный ресурс: http://www.microsoft.com/windows/products/winfamily/virtualpc/default. mspx.

66. Проект Хеп Электронный ресурс: http://xensource.com.

67. Проект Aurema Электронный ресурс: http://aurema.com.

68. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. -М.: Мир, 1984.

69. Kobets A., Votyakov К., Lukovnikov V., Optimization of resources distribution for high performance computation// Moscow Conference on Computational Molecular Biology (MCCMB'07), Электронный ресурс: http://mccmb.genebee.msu.su/2007/.

70. Votyakov К., Kobets A., Semi-macroscopic model for computation of electrostatic effects in membrane proton pump bactriorhodopsin// Moscow Conference on Computational Molecular Biology (MCCMB'07), Электронный ресурс: http://mccmb.genebee.msu.su/2007/.

71. Проект измерения производительности программного обеспечения и аппаратных устройств, Sisoftware Электронный источник http://sisoftware.net.

72. Проект VMWare, Электронный ресурс: http://vmware.com.

73. Serlin О. Scheduling of Time Critical Processes //Proceedings of the AFIPS Spring Joint Computer Conference. — Vol. 40. -1972.

74. Yifeng Zhu, Evaluation of Scheduling Algorithms for Real-Time Disk I/O, University of Nebraska Lincoln, NE, 66588-0155

75. A. N. Reddy and J. Wyllie. Disk scheduling in multimedia I/O system. Proceedings of ACM Multimedia'93, Anaheim, CA, pages 225-234, 8, 1993.