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

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

ИМИТАЦИОННАЯ МОДЕЛЬ И МЕТОД РАЦИОНАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ОПЕРАЦИОННОЙ СИСТЕМЫ

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

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

Москва - 2007

003071889

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

Научный руководитель:

Официальные оппоненты:

кандидат физико-математических наук Тормасов Александр Геннадьевич

доктор технических наук, профессор Семенихин Сергей Владимирович

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

Защита состоится «

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

_2007 года в час

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

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

Автореферат разослан «

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

6 ъ

2007 г

Федько О С

ОБЩЕЕ ОПИСАНИЕ РАБОТЫ Актуальность темы

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

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

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

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

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

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

• Разработка комплекса программ для реализации имитационной модели

• Обоснование рациональных параметров планировщика ресурсов операционной системы

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

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

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

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

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

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

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

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

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

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных семинарах и конференциях (в том числе, международных) SoftTool (2002 г, Москва), Интерполитех (2003 г, Москва), «Ottawa Linux Symposium» (г Оттава,

Канада, 2000г ), «ASP World Asm 2000» (Сингапур, 2000 г ), «LmuxWorld» (г Кельн, Германия, 2006 г), «HostingCon 2005» (Чикаго, США, 2005 г), Перспективы систем информатики (Шестая международная конференция памяти академика А П Ершова, Новосибирск, 28-29 июня 2006 г ), ISPCON (г Балтимор, США) и др

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

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

Получено свидетельство о регис фации в Российском Агентстве по патентам и товарным знакам № 2001611530 от 13 11 2001 г на программный продукт HSPcomplete, основанный на технологии Virtuozzo

Получен сертификат соответствия Министерства по связи и информатизации № RU 00007 01ЭС00, № ОС/1 -СПД - 463 на программно-аппаратный комплекс телематических служб

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Но в данном случае это не просто система массового обслуживания с фиксированным, неизменным во времени, набором параметров, а управляемая система Управление осуществляется планировщиком ресурсов

Поступающие в систему задачи по уровню значимости подразделяются на М типов Характерное значение параметра М составляет 16 Значимость каждого типа задачи может определяться номером ш ее типа или величиной, пропорциональной ш Коэффициент пропорциональности удобно выбрать из условия, чтобы сумма значимостей задач всех типов была нормирована на 1

м

т=1

^т = 2хт/{Мх(М+1)}, при М=16 §т= т/136

| Помимо того, что каждая задача относится к некоторому типу, она также принадлежит одному из 2-х классов

В первый класс входят обычные задачи

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

Таким образом, каждая задача характеризуется парой целых чисел (тип, класс)

Принимается, что потоки задач всех типов на входе системы -случайные и квазистационарные, законы распределения количеств поступающих на вход задач - показательные То есть, функция распределения Р(1:) величины промежутка времени I между поступлениями

двух задач одного типа определяется как

Р(г)=1-ехр{-1/Тт(т)} где Тт - среднее время между поступлениями двух задач одного типа

В общем случае величины Тт(т) различны для разных типов задач и зависят от системного времени т (текущее время суток)

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

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

Для решения задач требуется N типов ресурсов Потребности задач в ресурсах определяются матрицами 11=11,,, 1=1 )=1 ,М и а= ои51=1,N.

Элементы II определяют среднюю потребность (математическое ожидание) ш —й задачи в п-м ресурсе

Для учета возможных разбросов величин ресурсов используется матрица а, элементы которой определяют среднеквадратичные отклонения (с к о) величин требуемых ресурсов от их средних значений гтп Структура этой матрицы аналогична К Таким образом, требуемые величины ресурсов для каждой задачи рассматриваются как случайные величины В частном случае, когда потребность некоторой т-й задачи в п-ресурсе определена однозначно, т е не случайна, следует считать стпп, = 0 В дальнейшем считается, что случайные величины соответствуют усеченным нормальным законам распределения с математическим ожиданием гпт и апт образующего нормального закона Усечение производится со стороны отрицательных значений, что естественно из физических соображений величины требуемых ресурсов не могу г быть меньше нуля

Поступившая в систему задача запрашивает N типов ресурсов, необходимых для ее решения Эти ресурсы локализованы в N источниках

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

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

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

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

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

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

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

м

а™ = фтХ^ш /(ЕфтХ^т) т=1

где

{О, если т-я задача не присутствует в очереди

1, если т-я задача находится в очереди Сумма всех значимостей ат задач, присутствующих в очередях, нормирована на 1

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

м

Рт — фт

где 7,т - общее количество решенных задач на текущий момент времени I

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

Наконец, определяется комбинированный параметр Tm=am + qx(am-ßm),

где 0 < q < 1 - коэффициент обратной связи, деформирующий совокупность ат значимостей задач на входе с учетом уже решенных задач

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

ш0 = Arg { max ym} Первая находящаяся в очереди задача типа ш0 поступает на решение в свободный канал процессора

На начальной фазе функционирования системы может оказаться, что все Zm равны О В этом случае решение о поступающей в счетно-решающее устройство задаче принимается только с учетом параметров а^, те. из условия

ш0 = Arg { max а™ }

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

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

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

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

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

общая доля решенных задач за время функционирования системы в течение рабочего дня

м м П2 = Е2т4/]С

т=1 ш=1

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

«взвешанная» (с учетом значимое ги каждого типа задачи) доля решенных задач за время функционирования системы в течение рабочего дня

м м

Пз = ¿Лш^т^/Е ¿,mXZmo, т=1 т=1

Степень загрузки процессора - отношение суммарного времени решения задач во всех каналах к величине кхТтах (к - количество каналов процессора)

При проектировании рациональной системы следует стремиться к мйнимизации 1-го показателя качества и максимизации 2-го, 3-го и 4-го показателей

Управление ресурсами системы производится в несколько этапов Этап 1 (осуществляется только один раз перед началом функционирования системы) поскольку в системе предусматривается схема перераспределения ресурсов, то логично применить этот полезный инструмент для рационального распределения ресурсов в начальный момент времени

Предположим, что известен профиль

и = и(иь и2, и3 ин)

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

N

Еиг= 1,

г= 1

то количество независимых параметров иг равно N-1

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

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

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

В процессе функционирования системы отслеживается наступление события «дефицит ресурсов» Если это событие произошло в промежутке времени от 1-АТ до 1 (I - текущее время), то генерируется специальный сигнал, переводящий процедуру перераспределения ресурсов в актуализированное состояние

Этап 3 (может повторяться многократно в процессе функционирования системы) определяются количество свободных ресурсов во всех источниках

N

Кх - X Кг, Г — 1

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

При функционировании процедуры перераспределения ресурсов между источниками решение всех задач, находящихся в данный момент в счетно-решающем устройстве, приостанавливается Продолжительность % перераспределения ресурсов (время задержки выполнения задач в счетно-решающем устройстве) зависит от суммарной величины Я* перетока ресурсов между источниками Приближено х определяется по линейному соотношению

X = 9x11*+ хо,

где 0 и хо - константы,

К.* =£(1^-^x1^)

и

Новые (т е после действия процедуры перераспределения) значения ресурсов в источниках будут составлять

гг = игхГ1т

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

Из изложенного следует, что АТ представляет собой параметр среднесрочного управления ресурсами системы

Таким образом, существуют 3 типа параметров управления долгосрочные, среднесрочные и краткосрочные Общее количество независимых параметров управления составляет N+1 Они образуют множество (вектор) параметров планировщика ресурсов У = У(иь и2, и3, иы.ь АТ, ц) Величины всех компонентов вектора У подлежат определению при оптимизации планировщика ресурсов

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

Принцип функционирования математической модели состоит в следующем

Задается малый шаг по времени Д1, и через интервалы Дг с момента времени 1=0 до момента 1=Тшах рассматривается состояние системы в целом, основных подсистем, история перемещения задач по подсистемам и изменения их атрибутов Величина А1 должна быть, по крайней мере, в 3-5 раз меньше среднего значения минимального промежутка времени между наступлением событий, значимых для функционирования системы

Через малые интервалы времени М сначала уточняется ситуация на аде в систему, затем проверяется состояние каналов процессора, далее -определяются те задачи в накопителе, которые могут быть перемещены в :реди (при этом уточняется остатки ресурсов во всех источниках) Затем определяется приоритеты задач в очереди и номер задач, поступающий в свободный канал процессора

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

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

Завершение решения задачи происходит, когда ее суммарное время пребывания в процессоре становится не меньше заданного Ts Величина Ts -случайная, распределенная в соответствии с усеченным нормальным законом распределения с параметрами mTs и СКО aTS Она определяется классом задачи для счегных задач Ts значительно больше, чем для обычных

Предполагаемое время ts до снятия задачи с решения - также величина случайная, подчиненная усеченному нормальному закону распределения с математическим ожиданием образующего нормального закона ms и СКО as Параметры этого нормального закона специфичны для каждого класса задач

Но в действительности на каждом этапе задача решается в течение времени v, которое определяется следующим образом

v = max {Ti + min(ts, Т2)}, где Т[ и Т2 - соответственно нижнее и верхнее критериальные значения времени до снятия задачи с решения, оба этих параметра - атрибуты, зависящие от класса решаемой задачи

При этом если оказывается, что ts > Т2, то задача возвращается в конец соответствующей очереди (в подсистему № 2 «очередь») с сохранением всех захваченных ею ресурсов

Если же оказывается, что ts < Т2, то задача поступает в накопитель (подсистема №1) и задерживается в нем, по крайней мере, на время tn, величина которого случайная, подчиненная усеченному нормальному закону распределения с математическим ожиданием образующего нормального закона mn и СКО а„ Параметры этого нормального закона также специфичны для каждого класса задач Если по истечению времени t„ задача получает (или уже имеет) необходимые для продолжения ее решения ресурсы, тот она перемещается из накопителя в соответствующую очередь При этом обновляется величина ts

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

ви, ви,

величину 8, при этом 50% задач снижает свои требования к ресурсу, соответствующая величина которого немедленно возвращается в соответствующий источник, а вторые 50% задач, наоборот, ужесточают свои ресурсные требования Считается, что величина 8 зависит от класса задач, а д изменяемого ресурса устанавливается равновероятным образом из всех дов ресурсов

Определение основных характеристик системы осуществляется методом статистических испытаний (методом Монте-Карло) Для этого проводилось достаточно большое количество Ь испытаний процесса функционирования вычислительной системы в течение времени наблюдения Ттах Значение Ь выбирается из условия обеспечения статистической устойчивости усредненных величин показателей качества системы Для этого параллельно со средними значениями этих показателей определяются величины их среднеквадратичных отклонений от средних значений

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

Мерой разброса величин некоторого параметра П в различных статистических испытаниях от его среднего значения является днеквадратичное отклонение стп, определяемое по соотношению

мс по

ср

<тп = {(I Ц2)/Ь - [(Е П,)/Ц 2} 1/2х {Ь/(Ь -1)} т,

3=1

где J = 1, Ь - номер статистического испытания пр

Анализ показывает, что при больших Ь величина ап г Ь'"2 Поэтому

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

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

запросов рассматривалось обработка типового HTTP запроса Типовая задача представляет собой поток веб сервера, который обслуживает 150 запросов и умирает, причем веб сервер поддерживает 10 постоянно работающих потоков обслуживания Отсюда получается, что каждый поток живет примерно 500 секунд (150/3 * 10) Также оценивается, что каждая обработка запроса в ОС вызывает примерно 50 прерываний (и эта цифра не зависит практически от числа каналов процессора), и среднее время между этими прерываниями мы считаем одинаковым Задачи второго класса («счетные») обычно представляют собой обслуживающие процессы ОС, например, процессы резервного копирования данных, и время их жизни примерно на порядок больше времени жизни обычных задач Анализ результатов моделирования В работе показано, что

• при t > 20-25 тыс ед наблюдается снижение доли решенных задач всех типов (т е возрастает количество задач, находящихся в CPU),

• доля решенных задач нижних (1-6) типов оказывается заметно меньшей, чем для более высоких (7-16) типов

При t > 20-25 тыс ед в системе проявляется некоторый негативный фактор, способствующий ухудшению ее финальных характеристик Причем, в большей мере этот фактор действует на счетные задачи

Результаты моделирования динамики показателей качества системы графически представлены на (рис 2, 3)

-0,1----

время тыс отн ед

Рис 2 Показатели качества Обращает на себя внимание стационарность значений первого показателя качества (рис 1, темная линия), который определяет среднюю долю дополнительных задержек задачи в накопителе из-за недостатка одного или нескольких ресурсов, а также — в очереди

На рис 2 изображены графики динамики показателей качества 2-го и 3-г0 типов - усредненных значений долей решенных задач (темная линия) и «взвешенной» доли решенных задач (светлая линия) В последнем случае в качестве весовых факторов использовались значимости задач разного типа

время отн ед

Для

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

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

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

-ресурс9 -ресурсЮ

время, тыс ота ед

Рис 4 Величина ресурса в источнике

-ресурс2| -ресурсЗ

время, тыс ота ед.

Рис 5 Величина ресурса в источнике Детальный анализ показывает, что каждая задача, изменяя свои ресурсные требования, в среднем их ужесточает на несколько большую величину, чем снижает Иначе говоря, в процессе обслуживания в системе задача повышает свои ресурсные требования А так как количество таких изменений по каждому виду ресурса может составлять несколько сотен (для принятых исходных данных - около 500), то общим результатом многократного изменения ресурсных требований будет их существенное повышение Особенно это относится к счетным задачам (класс 2), у которых принятая величина 8 в 3 раза больше, чем у обычных задач

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

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

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

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

Формулировка задачи синтеза оптимального (рационального)

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

(Uo.II,о) =Агё{тшП,(и)}

при ограничениях

17 > 0, и < 1 (кроме компоненты ДТ),

N-1

Еиг,<1,

г- 1

ДТ < Ттах, П2 > П2гаш, П3 > Пзшш, П4 > П4тш,

Решение этой задачи математического программирования -мйнимизация показателя качества П1 - проводится численными методами

Оценка скорости решения задач с использованием этого алгоритма, показывает, что при относительной точности Е/Пю = 0,02-0,03 требуемое общее количество обращений к процедуре вычислений показателей качества

(в

рассматриваемом случае - количество обращений к математической

модели вычислительной системы) примерно на порядок превышает количество независимых переменных Поэтому потребуются 110-120 обращений к математической модели

Характерные значения средней величины показателя качества П( составляют 0,125, финальные значения СКО определения этой величины 0,04 Для обеспечения относительной точности определения величины целевой функции около 1% потребуется количество Ь 2 1000 статистических испытаний

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

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

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

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

• количество задач, находящихся в очередях, существенно меньше количества задач, находящихся в накопителе,

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

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

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

т

РтгСО = Г)1хгтгхк1(сгтг /гтг)х{ ртх \ к2,[п,0:-М[То1], 5,)хсИ/Тт(1) +

т - М[То1]

-с

+ Л2*0 - РтЯ ки[П2(1-М[Т«й], 82)хск/Тт(1) },

т - М[То1]

Общие требования Яг(т) к средней величине г-ого ресурса определяются следующим образом

м

Гч(т) = Е ртг(т),

т=1

а общие требования 9?(т) к средней величине всех видов ресурсов - по соотношению

N N M

г —1 r»lm=l

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

ur = Rt(to)/5Î(T О),

где то - момент времени, соответствующий максимальным ресурсным требованиям

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

Осуществлено исследование закономерностей процесса функционирования вычислительной системы при помощи имитационной модели и проведено теоретическое обоснование эффекта увеличения ресурсных требований задач в выбранной модели перераспределения ресурсов

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Белоусов С М Математическая модель многопоточной системы массового обслуживания, управляемой планировщиком ресурсов // Вестник Новосибирского Государственного Университета Серия Информационные технологии, - 2006 г, Том 4, Вып 1, С 14-26

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

3 Белоусов С М Об одной постановке задачи распределения ресурсов вычислительной системы // Объединенный научный журнал - 2005 г, №14(142), С 53-57

4 Белоусов С М, Тормасов А Г Задачи по распределению ресурсов операционной системы с учетом возможности взаимного перераспределения пулов // Перспективы систем информатики Шестая международная конференция памяти академика А П Ершова Сборник трудов конференции Новосибирск, 28-29 июня 2006 г с 35-38

5 Белоусов С М К вопросу об основных характеристиках и классификации операционных систем // Объединенный научный журнал - 2005 г, № 14 (142), С 58-64

6 Белоусов С М, Протасов С С, Тормасов А Г Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети // Объединенный научный журнал - 2004 г , № 24 (116), С 74-78

Белоусов С М, Протасов С С, Тормасов А Г Архитектура и особенности функционирования современных операционных систем // Объединенный научный журнал - 2004 г, 24 (116), С 78-83 Белоусов С М, Протасов С С, Тормасов А Г Об одном методе балансировки нагрузки между серверами ассиметричной фермы // Электронный журнал "Исследовано в России", 4257, 10-31, 2004 http //zhurnal gpi ru/articles/2004/4257 pdf

Белоусов С M, Протасов С С, Тормасов А Г Прошлое, настоящее и будущее развитие архитектуры и принципов создания операционных систем //Объединенный научный журнал - 2004 г, №24 (116), С 83-86 lp Tormasov Alexander, Lunev Dennis, Beloussov Sergei, Protassov Stanislav, Pudgorodsky Yuri Virtual computing environment // US Patent #7099948, 2001 / Опубликованный текст полученного патента Й Tormasov Alexander, Lunev Dennis, Beloussov Serguei, Protassov Stanislav, Pudgorodsky Yuri Hosting service providing platform system and method // US Patent #7076633, 2001 / Опубликованный текст полученного патента 12 Tormasov Alexander G, Beloussov Serguei M, Tsypliaev Maxim V, Lyadvinsky Maxim V System and method for using file system snapshots for online data backup // US Patent #7047380, 2004 / Опубликованный текст полученного патента 1{5 Tormasov Alexander, Khassine Mikhail, Beloussov Serguei, Protassov Stanislav Fault tolerant storage system and method using a network of servers // US Patent #6961868, 2001 / Опубликованный текст полученного патента

14 Tormasov Alexander G, Beloussov Serguei M, Tsypliaev, Maxim V, Lyadvinsky Maxim V System and method for rapid restoration of server from back up // US Pat App #20060143501, 2006 / Опубликованная заявка на патент

15 Tormasov Alexander, Beloussov Serguei, Protassov Stanislav, Pudgorodsky Yuri Common template file system tree // US Pat App #20060089950, 2006 / Опубликованная заявка на патент

16 Tormasov Alexander, Protassov Stamslav, Beloussov Serguei Method of implementation of data storage quota //US Pat App #20050066134,2005 / Опубликованная заявка на патент

17 Tormasov Alexander G, Beloussov Serguei M, Tsypliaev Maxim V, Lyadvinsky Maxim V System and method for using file system snapshots for online data backup // US Pat App #20050027956, 2005 / Опубликованная заявка на патент

18 Tormasov Alexander, Beloussov Sergei, Protassov Stamslav, Pudgorodsky Yuri Distributed network data storage system and method // US Pat App #20020147815,2002 / Опубликованная заявка на патент

19 Tormasov Alexander, Lunev Dennis, Beloussov Serguei, Protassov Stamslav, Pudgorodsky Yuri Hosting service providing platform system and method // US Pat App #20020143906,2002 / Опубликованная заявка на патент

20 Tormasov Alexander, Lunev Dennis, Beloussov Serguei, Protassov Stamslav, Pudgorodsky Yuri Fault tolerant storage system and method / / Опубликованная заявка на патент / US Pat App #20020124072,2002

21 Tormasov Alexander, Khassine Mikhail, Beloussov Serguei, Protassov Stamslav Fault tolerant storage system and method // US Pat App #20020116659, 2002 / Опубликованная заявка на патент

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

Белоусов Сергей Михайлович

ИМИТАЦИОННАЯ МОДЕЛЬ И МЕТОД РАЦИОНАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ОПЕРАЦИОННОЙ СИСТЕМЫ

Автореферат

Подписано в печать 05 04 07 Формат 60x90/16 Уел печ л I 0 Тираж 80 экз Заказ No 376 Московский физико-технический институт; (государственный университет)

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

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

ПРИНЯТЫЕ СОКРАЩЕНИЯ.

ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ.

ВВЕДЕНИЕ.

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

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

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

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

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

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

Краткое описание диссертации.13

Анализ предметной области.14

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

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

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

2. В зависимости от используемого главного показателя качества данная оптимизационная задача может быть сформулирована как задача его минимизации или максимизации. Учитывая сложность рельефа целевой функции целесообразно использовать численные методы многопараметрической оптимизации первого порядка. Для рассматриваемого случая такие методы позволят получить решение с приемлемой точностью за 110-120 обращений к процедуре вычисления целевой функции.

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

При этом оказывается проще получить решение задачи максимизации - потребуется в 25-35 раз меньшее количество статистических испытаний.

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

5. Результаты расчетов средних ресурсных потребностей вычислительной системы при различных характеристиках потока поступающих на ее вход задач, показали, что динамика ресурсных требований подобна профилю интенсивности поступления задач, но смещена по времени примерно на 1,6 часа сторону больших значений времени. Кроме этого, ресурсные требования существенно зависят от доли изменяемого ресурса задач 2-го класса (счетные задачи) при их перемещении из счетно-решающего устройства в накопитель, то есть для существующих систем наличие даже небольшого количества задач с большим временем исполнения на фоне стандартной нагрузки дает существенное изменение поведения системы (что наблюдается на практике, когда возникновение процесса резервного копирования, казалось бы не требующего больших ресурсов от системы, приводит к существенному повышению общего уровня нагрузки системы).

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

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

-105

Заключение

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

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

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

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

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

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

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

-1077. В качестве системы показателей качества управляемой вычислительной системы используются 4 показателя:

• уровень «накладных расходов»: средняя относительная величина суммарных дополнительных задержек задач в накопителе и в очереди;

• общая доля решенных задач за время функционирования системы в течение рабочего дня;

• «взвешенная» с учетом значимости каждого типа задачи доля решенных задач за время функционирования системы в течение рабочего дня;

• степень загрузки процессора - отношение суммарного времени решения задач во всех потоках к величине kxTmax.

8. Параметры планировщика ресурсов вычислительной системой подразделяются на 3 типа: долгосрочного, среднесрочного и краткосрочного управления. При этом общее количество параметров управления составляет N+1, где N - количество видов используемых ресурсов. Новой является предложенная технология взаимного перераспределения ресурсов - в процессе функционирования вычислительной системы периодически (при наличии сигнала о недостатке хотя бы одного из ресурсов) производится перераспределение свободных ресурсов между разными источниками для обеспечения пропорций, установленными параметрами долгосрочного управления.

9. Разработан и реализован алгоритм функционирования вычислительной системы, в котором учет неопределенных, в т.ч. - неблагоприятных, факторов моделируется розыгрышем совокупности случайных чисел, подчиненных показательному, усеченному нормальному и равномерному законам распределения. Параметры системы обновляются через малые интервалы («шаги») по времени; характерная величина шага в (3-5) раз меньше среднего промежутка времени между значимыми событиями; в рассматриваемом случае она составляет около 0,003 ед. времени при общем количестве шагов около 10 млн. за одну историю системы.

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

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

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

-10913. В зависимости от используемого главного показателя качества данная оптимизационная задача может быть сформулирована как задача его минимизации или максимизации. Учитывая сложность рельефа целевой функции целесообразно использовать численные методы многопараметрической оптимизации первого порядка. Для рассматриваемого случая такие методы позволят получить решение с приемлемой точностью за 110-120 обращений к процедуре вычисления целевой функции.

14. Оценки возможного времени решения задачи математического программирования показали, что на современной вычислительной базе получение решения оптимизационной задачи невозможно по причине не методического, а технического свойства - недостаточным быстродействием современных вычислительных средств. В будущем, при повышении их производительности на 3 порядка, возможно получение решения за приемлемое время. При этом оказывается проще получить решение задачи максимизации - потребуется в 25-35 раз меньшее количество статистических испытаний.

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

16. Результаты расчетов средних ресурсных потребностей вычислительной системы при различных характеристиках потока поступающих на ее вход задач, показали, что динамика ресурсных требований подобна профилю интенсивности поступления задач, но смещена по времени примерно на 1,6 часа сторону больших значений времени. Кроме этого, ресурсные требования существенно зависят от доли изменяемого ресурса задач 2-го класса (счетные задачи) при их перемещении из счетно-решающего устройства в накопитель.

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

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

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

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

1. Авен О.И., Турин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

2. Александров В. М. Приближенное решение задачи линейного быстродействия // Автоматика и телемеханика. 1998. ~ 12. С. 3-13.

3. Александров В. М. Численный метод решения задачи линейного быстродействия // Журнал вычислительной математики и математической физики. 1998. Т. 38. ~ 6. С. 918-931.

4. Баничук Н. В., Петров В. М., Черноусько Ф. JL Численное решение вариационных и краевых задач методом локальных вариаций // Журнал вычислительной математики и математической физики. 1966. Т. 6. ~ 6. С. 947-961.

5. Белман Р. Динамическое программирование. М.: Издательство иностранная литература, 1960.

6. Белоусов С.М. Математическая модель многопоточной системы массового обслуживания, управляемой планировщиком ресурсов // Вестник Новосибирского Государственного Университета. Серия: Информационные технологии, 2006 г., Том 4, Вып. 1, С. 14 - 26.

7. Белоусов С. М. «Об одной постановке задачи распределения ресурсов вычислительной системы» // Объединенный научный журнал 2005 г., № 14 (142), С. 53-57.

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

9. Белоусов С. М. «К вопросу об основных характеристиках и классификации операционных систем»// Объединенный научный журнал 2005 г., № 14 (142), С. 58-64.

10. Белоусов С. М., Протасов С. С., Тормасов А. Г. Использование виртуальных сред для предоставления услуг по размещению ресурсов в глобальной сети // Объединенный научный журнал 2004 г., № 24 (116), С. 74-78.

11. Белоусов С. М., Протасов С. С., Тормасов А. Г. Архитектура и особенности функционирования современных операционных систем // Объединенный научный журнал 2004 г., 24 (116), С. 78-83

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

13. Белоусов С. М., Протасов С. С. Использование виртуальных сред для повышения уровня утилизации ресурсов вычислительной системы (принята к публикации)

14. Белоусов С. М., Протасов С. С., Тормасов А.Г. Об одном методе балансировки нагрузки между серверами ассиметричной фермы // Электронный журнал "Исследовано в России", 4257, 10-31, 2004. http://zhurnal.gpi.ru/articles/2004/4257.pdf

15. БерзинЕ.А. Оптимальное распределение ресурсов и элементы синтеза систем. Под ред. Золотова Е.В. — М.: Советское радио, 1974.

16. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления. М.: Мир, 1972.

17. Васильев О. В., Тятюшкин А. И. К численному решению задач линейного быстродействия // Дифференциальные и интегральные уравнения. Иркутск: Издательство Иркутского университета. 1973. Вып. 2. С. 57-69.

18. ВентцельЕ.С. Теория вероятностей. Изд.2-е — М.: Гос. издательство физико-математической литературы, 1962.

19. Вентцель Е.С., Овчаров JI.A. Теория вероятности и ее инженерные приложения. — М.: Наука, 1988.

20. Габасов Р., Кириллова Ф. М. Качественная теория оптимальных процессов. М.: Наука, 1971.

21. Гантмахер Р. Теория матриц. М.: Наука, 1966.

22. Гихман И.И., Скороход А.В., Ядренко М.Н. Теория вероятностей и математическая статистика. — Киев: Вища школа, 1979.

23. Гнеденко Б.В. и др. Приоритетные системы обслуживания. -М.: Изд-во МГУ, 1973.

24. Гнеденко Б.В. Курс теории вероятностей. Изд. 2-е — М.: Гос. издательство технико-теоретической литературы, 1954.

25. Головкин Б.А. Параллельные вычислительные системы. М.Наука, 1980.

26. Давыдов Э. Г. Исследование операций: Учебное пособие для студентов вузов. М.: Высш. шк., 1990. - 383 е.: ил.

27. Демьянов В. Ф., Рубинов А. М. Приближенные методы решения экстремальных задач. JL: Издательство Ленинградского государственного университета, 1968.

28. Джейсуол Н. Очереди с приоритетами. М.: Мир, 1973.

29. Евдокимов В.П., Маловицкий В.И., Семинишин Ю.А. и др. Моделирование систем сбора и обработки данных М.: Наука, 1983. - 128 с.

30. Иванов-Мусатов О.С. Теория вероятностей и математическая статистика. — М.: Наука, 1979.

31. Каган Б.М. Электронные машины и системы: Учебное пособие. 2-е изд., перераб. И доп. М.: Энергоатомиздат, 1985.

32. Карманов В. Г. Математическое программирование. М.: Наука, 1975.

33. Карманов В.Г. Математическое программирование. Изд. 2-е. — М: Наука, Главная редакция физико-математической литературы, 1980.

34. Киселев Ю. Н. Оптимальное управление. М.: Издательство Московского государственного университета, 1988.

35. Круглый 3.JL Алгоритмы расчета моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. -1980.-№ 4 С. 73-79.

36. Моисеев Н.Н. "Математические задачи системного анализа". —М.: Наука, гл. ред. физ-мат. литературы, 1981.

37. Моисеев Н.Н., Столяров Ю.П., Столярова Е.М. Методы оптимизации — М., Наука, Главная редакция физико-математической литературы, 1978.

38. Мультипроцессорные системы и параллельные вычисления: Пер. с англ. / Под ред. Ф.Г. Энслоу. М.: Мир, 1976.

39. Олифер В., Олифер Н. Сетевые операционные системы. СПб., 2000. -512с.

40. Основы теории вычислительных систем: Учебное пособие / Под ред. С.А. Майорова. М.: Высшая школа, 1978.

41. Перегудов Ф.И., Тарасенко Ф.П. "Введение в системный анализ". —М.: Высшая школа, 1989.

42. Полак Э. Численные методы оптимизации. Единый подход. М.: Мир, 1974.

43. Поляк В. Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

44. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. Радио, 1972.

45. Праневичус Г.И. Модели и методы исследования вычислительных систем. Вильнюс: Мокслас, 1982.

46. Рини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. Перев. с англ. В.В.Подиновского, М.Г.Гафта, В.С.Бабинцева под ред. И.Ф.Шахнова. — М: Радио и связь, 1981

47. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

48. Смирнов В.И. Курс высшей математики. Том 1, изд. 23. — М: Наука, 1974.

49. Табак А., Куо Б. Оптимальное управление и математическое программирование. Пер. с англ. Мееровича Л.А. — М: Наука, главная ред. физико-математической литературы, 1975.

50. Теория прогнозирования и принятия решений. / Под ред. Саркисяна С.А. — М.: Высшая школа, 1977

51. Теория систем и методы системного анализа в управлении и связи /Под ред. Лазарева В.Г. и др. — М.: Радио и связь, 1983.

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

53. Феррари Д. Оценка производительности вычислительных систем: Пер. с англ. М.: Мир, 1981.

54. Шрайбер Т.Дж. Моделирование на GPSS. Перевод с английского. М.: Машиностроение, 1980.

55. Pat. # 7099948. Virtual computing environment. Tormasov Alexander, Lunev Dennis, Beloussov Sergei, Protassov Stanislav, Pudgorodsky Yuri

56. Pat. # 7076633. Hosting service providing platform system and method. Tormasov Alexander, Lunev Dennis, Beloussov Serguei, Protassov Stanislav, Pudgorodsky Yuri

57. Pat. # 7047380. System and method for using file system snapshots for online data backup. Tormasov Alexander G., Beloussov Serguei M., Tsypliaev Maxim V., Lyadvinsky Maxim V.

58. Pat. # 6961868. Fault tolerant storage system and method using a network of servers. Tormasov Alexander, Khassine Mikhail, Beloussov Serguei, Protassov Stanislav

59. Pub. App. # 20060143501 System and method for rapid restoration of server from back up. Tormasov Alexander G.; Beloussov Serguei M.; Tsypliaev; Maxim V.; Lyadvinsky Maxim V.

60. Pub. App. # 20060089950 Common template file system tree. Tormasov Alexander; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

61. Pub. App. # 20050066134 Method of implementation of data storage quota. Tormasov Alexander; Protassov Stanislav; Beloussov Serguei

62. Pub. App. # 20050027956 System and method for using file system snapshots for online data backup. Tormasov Alexander G.; Beloussov Serguei M.; Tsypliaev Maxim V.; Lyadvinsky Maxim V.

63. Pub. App. # 20020147815 Distributed network data storage system and method. Tormasov Alexander; Beloussov Sergei; Protassov Stanislav; Pudgorodsky Yuri

64. Pub. App. # 20020143906 Hosting service providing platform system and method. Tormasov Alexander; Lunev Dennis; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

65. Pub. App. # 20020124072 Virtual computing environment 10 20020116659 Fault tolerant storage system and method. Tormasov Alexander ; Lunev Dennis; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri

66. Pub. App. # 20020116659 Fault tolerant storage system and method. Tormasov Alexander; Khassine Mikhail; Beloussov Serguei; Protassov Stanislav

67. Ali, H. and El-Rewini, H. On the intractability of task allocation in distributed systems. Parallel Processing Letters, 1994.

68. Allon, et al. July 23, 1996 United States Patent 5,539,883

69. B. Narahari, A. Youssef and H. Choi. Matching and Scheduling in a Generalized Optimal Selection Theory. Proceedings of the IEEE Heterogeneous Processing Workshop, pages 3-8,1994

70. Barak A. and La'adan O., The MOSIX Multicomputer Operating System for High Performance Cluster Computing, Journal of Future Generation Computer Systems, Vol. 13, No. 4-5, pp. 361-372, March 1998

71. Barak A., Guday S. and Wheeler R., The MOSIX Distributed Operating System, Load Balancing for UNIX. Lecture Notes in Computer Science, Vol. 672, Springer-Verlag, 1993

72. Bokhari, S. A shortest tree algorithm for optimal assignments across space and time in distributed processor system. IEEE Transaction on Software Engineering, SE-7 (6), 1981.

73. Brendel January 30, 2001 United States Patent 6,182,139

74. Brendel, et al. June 30,1998 United States Patent 5,774,660

75. C. Z. Xu and F. С. M. Lau. Analysis of the Generalized Dimension Exchange Method for Dynamic Load Balancing. Journal of Parallel Distributed Computing, vol. 16(4), pages 385-393,1992.

76. Chen, S. et al. A Selection Theory and Methodology for Heterogeneous Su-percomputing, Proc. Workshop on Heterogeneous Processing, IEEE CS Press, Los Alamitos, CA, Order No. 3532-02, 1993.

77. Coffman, E. G. Computer and Job-Shop Scheduling Theory, John Wiley, 1976.

78. Distributed Operating Systems by Andrew S. Tanenbaum, 1994 Prentice Hall; ISBN: 0132199084

79. El-Rewini, H. and AH, H. On considering communication in scheduling task graphs on parallel processors. Journal of Parallel Algorithms and Applications, 3,177-191,1994.

80. El-Rewini, H. and AH, H. Static scheduling of containing conditional branching in parallel programs. Journal of Parallel and Distributed Computing, 4154,1995.

81. El-Rewini, H. and Lewis, T. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing, 138-153, 1990.

82. El-Rewini, H., Lewis, T. and AH, H. Task Scheduling in Parallel and Distributed Systems, Prentice-Hall, 1994.

83. Freund, R. and Siegel, H. Heterogeneous processing. IEEE Computer, 26, 1317,1993.

84. Fujii, M., Kasami, T. and Ninomiya, K. Optimal sequencing of two equivalent processors. SIAM Journal of Applied Mathematics, 17 (4), 1969.

85. Gabow, H. An almost linear algorithm for two-processor scheduling. Journal of ACM, 29 (3), 766-780, 1982.

86. Gerasoulis and Yang, T. A comparison of clustering heuristics for scheduling DAGs on multiprocessors. Journal of Parallel and Distributed Computing, 16 (4), 276-291, 1992.

87. H.S. Stone. Critical Load Factors in Two-Processor Distributed Systems. IEEE Transactions on Software Engineering, vol. SE-4(3), pages 254-258, May 1978.

88. L. M. Ni and P. K. McKinley. A Survey of Wormhole Routing Techniques in Direct Networks. IEEE Computer, vol. 26(2), pages 62-76, February 1993.

89. Lee, D. and Kim, M. Optimal task assignment in linear array networks. IEEE Transactions on Computers, 41 (7), 877-880, 1992.

90. Lewis, T. and El-Rewini, H. Parallax: A tool for parallel program scheduling. IEEE Parallel and Distributed Technology: Systems and Applications, 1 (2), 62-72,1993.

91. Lo, V. Heuristic algorithms for task assignment in distributed systems. IEEE Transactions on Computers, 37 (11), 1384-1397,1988.

92. M. H. Mickle and J. M. Paul. Load Balancing Using Heterogeneous Processors for Continuum Problems on a Mesh. Journal of Parallel and Distributed Computing, vol. 39, pages 66-73, 1996.

93. В. E. Карпов ,K. А. Коньков. Основы операционных систем. Курс лекций. Учебное пособие. М.: Интернет-университет информационных технологий, 2004. - 632 с.

94. Operating Systems: a design-oriented approach/Charles Crowley. Irwin. 1997. ISBN 0-256-15151-2

95. Papadimitriou, H. and Yannakakis, M. Scheduling interval-ordered tasks. SIAM Journal of Computing, 8,405-409,1979.

96. S. J. Kim and J. С Browne. A General Approach to Mapping of Parallel Computation upon Multiprocessor Architectures. Proceedings of the International Conference on Parallel Processing, vol. 3, pages 1-8,1988.

97. S. Ranka, Y. Won and S. Sahni. Programming a Hypercube Multicomputer. IEEE Software, pages 69-77, September, 1988.

98. Sarkar, V. Automatic partitioning of a program dependence graph into parallel tasks. IBM Journal Res. Develop., 35 (5/6), 1991.

99. Sethi, R. Scheduling graphs on two processors. SIAM Journal of Computing, 5 (1), 73-82, 1976.

100. Shen and W. Tsai. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems Using a Minimax Criterion. IEEE Transactions on Computers, vol. C-34(3), pages 197-203, March 1985.

101. Stone, H. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transaction on Software Engineering, 85-93,1977.

102. T. Yang and A. Gerasoulis. A Fast Static Scheduling Algorithm for DAG's on an Unbounded Number of Processors. Proceedings of IEEE Supercomput-ing'91, pages 633-642. Albuquerque, NM, November 199

103. Ullman, J. NP-complete scheduling problems. Journal of Computer and System Sciences, 10, 384-393, 1975.-117108. V. Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors.