Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

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

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

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

Москва - 2007

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

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

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

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

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

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

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

Защита состоится «25» мая 2007 года в 12.30 час на заседании диссертационного совета К 212.156.02 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный, Московской обл., Институтский пер. д.9., ауд. 903 КПМ.

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

Автореферат разослан « 6 » апреля 2007 г.

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

1. Общее описание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По теме диссертации опубликована 21 работа.

Результаты диссертационного исследования докладывались, обсуждались и получили одобрение специалистов на научных семинарах и конференциях (в том числе, международных): SoftTool (2002 г, Москва), Интерполитех (2003 г, Москва), «Ottawa Linux Symposium» (г. Оттава, Канада, 2000г.), «ASP World Asia 2000» (Сингапур, 2000 г.), «LinuxWorld» (г. Кельн, Германия, 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. Технология и алгоритм процесса перепланирования свободных ресурсов вычислительной системы, а также комплекс программ имитационного моделирования вычислительной системы в процессе перепланирования.

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

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

В главе 1 приведена формальная постановка задачи исследования.

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

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

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

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

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

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

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

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

F(t) = 1 - exp{- t/T_m()}

где T_m - среднее время между поступлениями двух задач одного типа.

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

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

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

Для решения задач требуется N типов ресурсов. Потребности задач в ресурсах определяются матрицами R=R_ij, i=1,N, j=1,M и = _ij, i=1,N, j=1,M.

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

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

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

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

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

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

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

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

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



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

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

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

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

Наконец, определяется комбинированный параметр

_m = _m + q( _m - _m),

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

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

m₀ = Arg { max _m }

Первая находящаяся в очереди задача типа m₀ поступает на решение в свободный канал процессора.

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

m₀ = Arg { max _m }

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

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

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

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

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

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

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

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

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

Управление ресурсами системы производится в несколько этапов.

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

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

U = U(u₁, u₂, u₃….u_N)

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

Так как

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

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

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

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

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

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

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

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

= R^*+ ₀,

где и ₀ - константы;

R^* = (R_r - u_rR)

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

r_r = u_rR

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

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

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

Y = Y(u₁, u₂, u₃,….u_N-1, T, q)

Величины всех компонентов вектора Y подлежат определению при оптимизации планировщика ресурсов.

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

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

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

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

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

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

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

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

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

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

= max {T₁ + min(t_S, T₂)},

где T₁ и T₂ - соответственно нижнее и верхнее критериальные значения времени до снятия задачи с решения; оба этих параметра - атрибуты, зависящие от класса решаемой задачи.

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

Если же оказывается, что t_S < T₂, то задача поступает в накопитель (подсистема №1) и задерживается в нем, по крайней мере, на время t_n, величина которого случайная, подчиненная усеченному нормальному закону распределения с математическим ожиданием образующего нормального закона m_n и СКО _n. Параметры этого нормального закона также специфичны для каждого класса задач. Если по истечению времени t_n задача получает (или уже имеет) необходимые для продолжения ее решения ресурсы, тот она перемещается из накопителя в соответствующую очередь. При этом обновляется величина t_S.

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

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

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

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

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

Анализ показывает, что при больших L величина _П L^-1/2. Поэтому при увеличении количества статических испытаний разброс снижается, но скорость этого снижения резко уменьшается с увеличением величины L. Таким образом, разработанная математическая модель позволяет алгоритмически установить зависимости финальных средних значений показателей качества системы от совокупности параметров планировщика ресурсов, определяемой вектором Y.

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

Анализ результатов моделирования.

В работе показано, что:

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

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

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

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

Рис. 1 Показатели качества

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

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



Рис. 2 Доли решенных задач

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

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

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



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

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

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

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

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

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

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

(U₀, П₁₀) = Arg{min П₁(U)}

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

U 0; U 1 (кроме компоненты T);

T T_max; П₂ П_2min; П₃ П_3min; П₄ П_4min;

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

Оценка скорости решения задач с использованием этого алгоритма, показывает, что при относительной точности E/П₁₀ = 0,02-0,03 требуемое общее количество обращений к процедуре вычислений показателей качества (в рассматриваемом случае - количество обращений к математической модели вычислительной системы) примерно на порядок превышает количество независимых переменных. Поэтому потребуются 110-120 обращений к математической модели.

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

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

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

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

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

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

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

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

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

вычислительный программа виртуальный управление

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

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

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

u_r = R_r(₀)/( ₀),

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

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

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

Автором получены следующие новые научные результаты.

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

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

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

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.

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

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

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

10. Tormasov Alexander, Lunev Dennis, Beloussov Sergei, Protassov Stanislav, Pudgorodsky Yuri. Virtual computing environment. // US Patent #7099948, 2001. / Опубликованный текст полученного патента.

11. 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. / Опубликованный текст полученного патента.

13. 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 Stanislav; 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 Stanislav; Pudgorodsky Yuri. Distributed network data storage system and method. // US Pat. App. #20020147815, 2002. / Опубликованная заявка на патент.

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

20. Tormasov Alexander; Lunev Dennis; Beloussov Serguei; Protassov Stanislav; Pudgorodsky Yuri. Fault tolerant storage system and method. / / Опубликованная заявка на патент

21. Tormasov Alexander; Khassine Mikhail; Beloussov Serguei; Protassov Stanislav. Fault tolerant storage system and method.

Размещено на Allbest.ru

...