Содержание к диссертации
Введение
ГЛАВА 1. Операционная система как управляемая система массового обслуживания. постановка задачи исследования .18
1.1. Структурно-функциональная схема управляемой системы массового обслуживания. Постановка задачи исследования 18
1.2. Управление ресурсами 30
ВЫВОДЫ ПО ГЛАВЕ 1 34
ГЛАВА 2. Имитационная модель многопоточной системы массового обслуживания, управляемой планировщиком ресурсов 37
2.1. Основные принципы построения и схема модели 37
2.2. Система исходных данных математической модели 50
2.3. Результаты моделирования и их анализ 56
ВЫВОДЫ ПО ГЛАВЕ 2 80
ГЛАВА 3. Метод определения рационального распределения ресурсов операционной системы 83
3.1. Математическая формулировка оптимизационной задачи для определения рациональных значений параметров планировщика ресурсов 83
3.2. Методика приближенного определения рациональных значений параметров планировщика ресурсов 93
Выводы по главе 3 102
Заключение 105
Список использованных источников
- Управление ресурсами
- Система исходных данных математической модели
- Математическая формулировка оптимизационной задачи для определения рациональных значений параметров планировщика ресурсов
- Методика приближенного определения рациональных значений параметров планировщика ресурсов
Введение к работе
Актуальность темы
Операционная система (ОС) определяет облик вычислительной системы в целом. Она обеспечивает эффективность использования компьютера путем рационального управления его ресурсами. От алгоритмов управления ресурсами во многом зависит эффективность работы всей системы.
Некоторые алгоритмы управления связаны с риском перевода какого-либо процесса в состояние ожидания на неопределенное время. Избыточное число запросов на некоторые виды ресурсов может привести к ухудшению качества системы в целом, что и наблюдается в реальных условиях. Неопределенные факторы, выраженные даже в слабых колебаниях уровня внешней нагрузки и работе внутренних процессов ОС, иногда приводят к такой ситуации, когда компьютер практически переходит в неработоспособное состояние. Понимание происходящих в операционной системе процессов потребления ресурсов осложняется недостаточной проработкой моделей функционирования ОС и сложными «инженерными» подходами, применяемыми при разработке планировщиков ресурсов.
Вышеизложенное позволяет сделать вывод о том, что разработка моделей и методов рационального распределения ресурсов сегодня является достаточно актуальной.
Цель работы, объект и предмет исследования
Цель диссертационной работы – разработка технологии выбора рациональных параметров планировщика ресурсов операционной системы на основе использования результатов имитационного моделирования.
Задачи исследования:
Анализ существующих подходов к распределению ресурсов операционной системы, выявление их достоинств и недостатков.
Разработка имитационной модели и метода управления распределением ресурсов вычислительной системы, удовлетворяющего заданным ограничениям.
Разработка комплекса программ для реализации имитационной модели.
Обоснование рациональных параметров планировщика ресурсов операционной системы.
Объект исследования – процессы управления ресурсами в операционных системах компьютеров.
Предмет исследования – методы рационального распределения ресурсов операционной системы.
Методы исследования
В ходе научных исследований по разработке имитационной модели операционной системы и метода управления распределением ресурсов использовались аналитические методы теории систем массового обслуживания, методы исследования операций, методы теории операционных систем и системного программирования.
Научная новизна
Научная новизна работы заключается в том, что автором предложена имитационная модель операционной системы и технология рационального распределения ресурсов операционной системы. В отличие от ранее существовавших моделей распределения ресурсов, разработанная в ходе диссертационного исследования имитационная модель и технология позволяют существенно повысить утилизацию ресурсов вычислительной системы путем выбора рациональных значений параметров планировщика ресурсов.
Практическая значимость
В ходе выполнения научных исследований автором была проведена серия численных экспериментов, результаты которых позволили оценить преимущества разработанного метода.
Разработанная имитационная модель и комплекс программ могут быть использованы при создании новых программных продуктов (прежде всего, операционных систем и систем виртуализации), предназначенных для обеспечения решения задач управления распределением ресурсов с целью достижения наибольшей утилизации ресурсов вычислительной системы. Кроме того, разработанная модель и технология могут быть использованы в качестве самостоятельных решений задач управления распределением ресурсов. Результаты работы могут быть использованы в учебном процессе при подготовке специалистов в области теории операционных систем.
Апробация и реализация результатов работы
По теме диссертации опубликована 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 на программно-аппаратный комплекс телематических служб.
Структура и объем работы.
Управление ресурсами
Повышение качества функционирования рассматриваемой системы массового обслуживания достигается перераспределением ресурсов между -различными источниками. Для этого в систему встроена специальная процедура (при программной реализации она может рассматриваться как задача дополнительного типа М+1), которая, периодически включаясь, осуществляется перераспределение имеющихся в источниках свободных ресурсов для достижения их рационального распределения. При этом те источники, в которых перед включением процедуры уже нет свободного ресурса, получают его из других источников. Это дает возможность снабдить полным набором требуемых ресурсов находящиеся в накопителе задачи и интенсифицировать процесс их решения. Это опциональный шаг в решении задачи, который обычными планировщиками ресурсов операционных систем явным образом не используется, но, по-видимому, является необходимым для улучшения качества функционирования системы.
Управление ресурсами производится в несколько этапов.
Этап 1 (осуществляется только один раз перед началом функционирования системы): поскольку в системе предусматривается схема перераспределения ресурсов, то логично применить этот полезный инструмент для рационального распределения ресурсов в начальный момент времени.
Предположим, что известен профиль U = U(U,,U2,U3,....UN) рационального распределения общего располагаемого ресурса между различными источниками. Так как N Iur=l, г=1 то количество независимых параметров ur равно N-1.
По своему физическому смыслу величины иг - это параметры долгосрочного управления ресурсами вычислительной системы. Их конкретные значения должны устанавливаться в результате решения оптимизационной задачи по выбору рациональных параметров планировщика ресурсов.
Предположим, что такая задача сформулирована и решена. Тогда естественно так запрограммировать планировщик ресурсов, чтобы перед началом функционирования системы он произвел перераспределение общих располагаемых ресурсов между различными источниками в соответствии с рациональным профилем U. Это представляется вполне естественным, т.к. если существует инструмент перераспределения ресурсов, то логично его использовать не только в процессе функционирования системы, но и до начала ее работы.
Этап 2 (может повторяться): вводится дополнительный параметр AT -минимальное время между последовательными включениями процедуры перераспределения ресурсов.
В процессе функционирования системы отслеживается наступление события «дефицит ресурсов». Если это событие произошло в промежутке времени от t-AT до t (t - текущее время), то генерируется специальный сигнал, переводящий процедуру перераспределения ресурсов в актуализированное состояние.
При разблокированной процедуре с наступлением очередного момента времени на перераспределение ресурсов сначала проверяется наличие свободного потока процессора. Если в момент времени t такой поток имеется, то производится запуск процедуры перераспределения ресурсов. В противоположном случае запуск откладывается до ближайшего момента времени, когда в системе появится свободный поток.
Система исходных данных математической модели
Рассмотренная математическая модель функционирует при определенной совокупности исходных данных, выполняющих в процессе вычислений роль констант модели.
Для удобства пользователя исходные данные структурированы в виде отдельных кластеров, доступ к которым для просмотра и (или) редактирования в компьютерной программе осуществляется через удобный интерфейс. Таким образом, математическая модель позволяет по единой расчетной схеме получать результаты, относящиеся к различным условиям ее функционирования.
В представленной ниже системе исходных данным приведены также конкретные значения параметров, полученные из оценки реальной системы (см. выше обоснование выбора их значений). Это сделано по следующим причинам: для обозначения совокупности значений исходных данных, для которых в следующем подразделе представлены результаты моделирования; для представления масштабов величин и оценки степени их соответствия реальным значениям параметров; для оценки чувствительности результатов моделирования при изменении различных параметров или групп параметров. Основные системообразующие параметры представлены в таблице 2.4. Таблица 2.4
Величина Ттах времени наблюдения примерно соответствует общей продолжительности рабочего дня: 9 часов - с 900 до 18 . При этом единица измерения времени примерно соответствует одной секунде.
Значения параметров 0 и %0, определяющих время задержки выполнения задач при действии процедуры перераспределения ресурсов, введены на основе опыта эксплуатации реальных систем.
Количество статистических испытаний L выбрано минимальным для того, чтобы, с одной стороны, почувствовать разброс значений при различных реализациях, а, с другой стороны, на этапе экспериментальных расчетов время моделирования не делать чрезмерно большим.
Профиль интенсивности потока задач принимался по данным (рис. 2.2). Временная зависимость индекса интенсивности имеет кусочно-линейный характер.
Следующая группа данных - параметры типов задач (таблица 2.5). Для каждого типа задач приводятся 2 параметра - вероятность (частота) появления обычной задачи внутри данного типа и среднее время поступления в систему задачи данного типа.
Вероятность принадлежности различных типов задач к 1-му классу (обычные задачи) определялись из условия, что распределение обычных задач (1-й класс) по типам соответствует нормальному закону распределения с математически ожиданием, равным 8 и с.к.о. = 1,5, распределение счетных задач (2-й класс) по типам соответствует нормальному закону распределения -с математически ожиданием, равным 5 и с.к.о. = 1. При этом общая вероятность появления задачи 1-го класса (т.е. вероятность, усредненная по всем типам задач) равна 0,9.
Для решения задач каждого типа необходимы N типов ресурсов, которые локализованы в N источниках. Данные по ресурсным требованиям задач разных типов представлены в таблице 2.6. Единица измерения ресурсов выбрана в относительном виде - она составляет 1% от суммарного ресурса системы. Такой способ определения единицы измерения ресурсов достаточно удобен и универсален; например, он может быть полезен при построении математических моделей перспективных вычислительных систем, в которых ресурсные возможности существенно возрастут, также как и ресурсные требования различных, все более усложняющихся, задач.
В таблице 2.6 приведены данные о средних значениях (математических ожиданиях) rrm требуемых ресурсов. По существу таблица 2.6 эквивалентна матрице R.
Математическая формулировка оптимизационной задачи для определения рациональных значений параметров планировщика ресурсов
В предыдущей главе была рассмотрена имитационная математическая модель вычислительной системы, управляемой планировщиком ресурсов. Эта модель позволяет установить алгоритмическую зависимость системы показателей качества вычислительной системы от параметров управления, которые образуют вектор U.
Компонентами U являются N-1 независимых параметров долгосрочного управления, определяющих рациональные начальные доли общего ресурса в разных источниках, один параметр среднесрочного управления AT (минимальный промежуток времени между последовательными операциями по перераспределению ресурсов) и один параметр обратной связи q, предназначенный для динамической корректировки значимостей решаемых задач.
Общее количество независимых параметров управления равно N+1. Так как для принятых исходных данных количество видов ресурсов N равно 10, то совокупность параметров управления представлена в основном параметрами долгосрочного управления.
При проектировании или настройке вычислительной системы естественно выбрать значения параметров управления таким образом, чтобы обеспечить максимальную степень приспособленности системы к выполнению возложенных на нее функций.
В результате математического моделирования решается первая часть задачи обоснования оптимальных (рациональных) значений параметров управления. В соответствии с терминологией системного анализа (анализа систем) [7-9], этот этап обычно называется задачей анализа (термин «задача» здесь применен в другом смысле, чем в предыдущих главах).
Следующий этап - формулировка и решение задачи синтеза, в данном случае - синтеза рационального планировщика ресурсов вычислительной системы при наличии нескольких показателей качества и системных ограничений, устанавливающих границы области изменения параметров управления.
Определение рациональных значений оптимизируемых параметров в подобных задачах производится численными методами поиска экстремальных значений оптимизируемых (целевых) функций и соответствующего этим экстремальным значениям набора независимых оптимизируемых параметров. Для того чтобы сделать алгоритм решения задачи синтеза однозначным, необходимо в качестве целевой функции оперировать не несколькими, а только одним показателем качества.
В настоящее время существуют два подхода к формированию целевой функции.
Первый из них представлен методами многокритериальной оптимизации, в которых формируется обобщенный (агрегатный) показатель качества системы, учитывающий все значимые показатели качества рассматриваемой системы. Например, очень часто в качестве агрегатного показателя используются аддитивная, мультипликативная или полилинейная формы [41] свертки частных показателей с определенными «весами». Иногда применяются и более сложные функции свертки.
Основным недостатком схемы многокритериальной оптимизации является не всегда достаточная обоснованность вида функции свертки, что снижает достоверность полученных таким способом результатов.
Другой возможный подход к обоснованию рациональных значений оптимизируемых параметров (в рассматриваемом случае - это параметры управления ресурсами) - формулировка задачи в виде задачи математического программирования, когда в качестве целевой функции применяется один -(главный) из показателей качества, а на значения остальных показателей налагаются некоторые определенные ограничения. Они, вместе с естественными ограничениями на значения оптимизируемых параметров, образуют полную систему системных ограничений задачи синтеза.
Следует отметить, что рассмотренные два подхода не являются альтернативными, а связаны между собой. Например, если считать все «веса» частных показателей, кроме главного, равными нулю, то второй подход трансформируется в первый. Кроме этого, следует заметить, что при формулировке задачи синтеза в виде задачи математического программирования с расширенной системой ограничений требуется применение системы критериальных значений, определяющих области изменения частных показателей качества (за исключением главного показателя), что не всегда можно сделать однозначно.
Вместе с тем, при решении многопараметрических оптимизационных задач методические (но не вычислительные) трудности, связанные с реализацией 2-го подхода, как правило, оказываются меньшими. Это связано с возможностью более детальной декомпозиции проблемы, когда многие критериальные значения устанавливаются различными группами специалистов, а также контролем результатов расчетов при решении оптимизационной задачи - отслеживании траектории движения к экстремуму в допустимой области изменения оптимизируемых параметров.
В связи с этим, в дальнейшем будут рассмотрены математические формулировки задачи синтеза оптимального (рационального) планировщика ресурсов в виде задач математического программирования с главным показателем качества. При этом, исходя из его природы задача может быть сформулирована, как задача минимизации или максимизации значений показателя.
Методика приближенного определения рациональных значений параметров планировщика ресурсов
Предлагаемая методика приближенного определения рациональных значений параметров управления вычислительной системы основана на использовании закономерностей ее функционирования, выявленных при математическом моделировании ее динамики (глава 2). Основной принцип определения рациональных значений параметров управления - одинаковая (в среднем) степень доступности ресурсов из различных источников.
Наиболее существенными закономерностями для решения рассматриваемого вопроса, установленными при математическом моделировании системы, являются следующие: продолжительности обслуживания задач значительно превышает «чистое» время их решения; дополнительное время пребывания задач в вычислительной системе происходит по причине их задержки в накопителе и в очереди; средняя суммарная величина задержки задач в очереди и дополнительной задержки в накопителе из-за недостатка ресурсов пропорциональная общей продолжительности обслуживания задач; коэффициент пропорциональности определяется показателем качества Пі и он стабилен в широком диапазоне времени функционирования вычислительной системы; количество задач, находящихся в очередях, существенно меньше количества задач, находящихся в накопителе; средние требования к ресурсам для задач разных классов существенно отличаются; для счетных задач они могут быть значительно выше, чем для обычных; величина требований имеет тенденцию к увеличению по мере завершения процесса решения задач обоих классов; в соответствие с принятыми исходными данными время перераспределения ресурсов между источниками значительно меньше среднего времени решения для обоих классов задач.
При отсутствии дополнительных задержек задач в накопителе (из-за недостатка ресурсов) и в очереди средние общие продолжительности обслуживания задач в вычислительной системе М[Ток] составят: M[Tok] = M[Tsk]x(l + Му/ММ), (3.1) где M[Tsk] - средние общие продолжительности решения задач («чистое» время решения); M[tnk] - средние минимальные продолжительности задержки задач в накопителе; M[tsk] - средние величины времени до снятия задачи со счета; к - здесь параметр для обозначения класса задач: к=1 для обычных задач, к=2 - для счетных задач. Выражение (3.1) соответствует идеальному случаю отсутствия дополнительной задержки задач в накопителе и в очереди. С учетом дополнительного времени задержки оно при тех обозначениях может быть переписано в следующем виде: М[Ток] = M[Tsk]x(l + M[tnk]/M[tsk])/(1 - П,), (3.2)
Принцип одинаковой (в среднем) степени доступности ресурсов из различных источников означает, что доли общего ресурса в источниках должны быть пропорциональны средним общим потребностям в ресурсах. Причем -естественно требовать выполнение этого принципа в первую очередь - в самые напряженные моменты функционирования вычислительной системы в течение рабочего дня.
Обозначим т - текущее время. Тогда, если вычислительная система в основном справляется с потоком поступающих в нее задач (а именно такие системы исследуются в настоящей работе), в ней к моменту т находится количество задач m-го типа (в среднем), определяемое выражением т т pmx J dt/Tm(t) + (1 - pm)xj" dt/Tm(t), т-М[То1] т-М[То2] где рт - вероятность принадлежности задач к первому классу (обычные задачи); Тт - среднее время между поступлениями в вычислительную систему задач m-го типа; значения этой величины определяется по данным таблицы 2.5 и временного профиля загрузки вычислительной системы (рис. 2.2).
Тогда динамика ресурсных требований ртг(т) от m-й задачи к r-му ресурсу может быть определена следующим образом: pmrCO = rmrxk,(amr/rmr)x{ pmx Jk2i[ni(t-M[Tol], 5,)xdt/Tm(t) + T-M[Tol] + (1 -Pm)x) k22[n2(t -M[To2], 52)xdt/Tm(t)} (3.3) T-M[Tol]
В этом выражении первый коэффициент к ст /rmr) учитывает поправку на отклонение математического ожидания усеченного нормального закона от математического ожидания rmr образующего нормального закона.
