close

Вход

Забыли?

вход по аккаунту

?

sheduler

код для вставкиСкачать
 Министерство образования РФ
Ульяновский государственный технический университет
Факультет информационных систем и технологий
Кафедра "Вычислительная техника"
Дисциплина "Моделирование"
Курсовая работа
по теме
Моделирование процессов принятия решения:
моделирование принятия решения диспетчером задач операционной системы
Пояснительная записка
Выполнил: Подъячев М. А.,
гр. ЭВМд32 Проверил: Куцоконь Н.С.
Ульяновск 2003
Постановка задачи
Задача
Диспетчер задач ОС, получив управление, принимает решение о том, какую задачу из находящихся в данный момент в состоянии готовности передать на выполнение.
Цель принятия решения
Выбор следующей выполняемой задачи, оптимальный по ряду критериев.
Альтернативы
Множество задач, находящихся на момент принятия решения в состоянии готовности к выполнению.
Ограничения
* Диспетчер не может влиять на время выполнения задачи после передачи ей управления (невытесняющая многозадачность).
* Промежуток времени, по истечении которого задача возвращает управление ОС, неизвестен, но ограничен сверху предельным значением Tmax.
* Отсутствует какая-либо иная априорная информация об алгоритме работы конкретной программы или о продолжительности ее выполнения.
Тип задачи
Многокритериальная динамическая задача принятия решения в условиях неопределенности.
Описание
Управление выполнением задач в операционных системах может строиться по принципам вытесняющей или невытесняющей многозадачности. Первая реализована в большинстве современных операционных систем и даже получила название "истинной". Как правило, в этих системах процессор выделяется задаче на определяемый диспетчером задач ОС малый отрезок времени - "квант", по истечении которого эта задача принудительно приостанавливается, и на тех же условиях начинает выполняться какая-либо другая. Алгоритм выбора очередной выполняемой задачи обычно строится на арифметике динамических приоритетов, которая дает возможность быстро и достаточно разумно принять решение. Системы с вытесняющей многозадачностью отличаются устойчивым, предсказуемым поведением и достаточно малым временем реакции, что позволяет строить по этому принципу ОС как общего назначения, так и реального времени.
Вторая схема, невытесняющая многозадачность, была реализована, например, в Microsoft Windows 3.1 и в сетевых ОС Novell NetWare. Принцип работы этих систем - задача по собственной инициативе достаточно часто передает управление ОС, чтобы та могла обеспечить псевдопараллельное выполнение нескольких программ. Недостаток невытесняющей многозадачности в "чистом" виде - непредсказуемость времени монопольной работы программы и невозможность ограничить его для выполнения каких-либо срочных операций. Как правило, такая система использует простейшую "карусельную" схему диспетчеризации, возможно, с несколькими очередями для разноприоритетных задач. Между тем, именно для невытесняющей многозадачности особенно полезен был бы "разумный и предусмотрительный" алгоритм планирования выполнения задач: это самое большее, что система может сделать для уменьшения времени реакции, повышения эффективности и надежности, снижения риска недопустимых задержек.
В данной работе выбор задачи диспетчером рассматривается как задача принятия решения в условиях неопределенности. Диспетчер не ограничивается аппаратными и временными рамками в сборе информации и поиске оптимального варианта.
Описание модели
Для исследования алгоритма принятия решения и оценки качества управления применяется имитационная модель среды и объекта работы диспетчера - ОС и нескольких запущенных задач. Принцип работы модели можно сформулировать так: задача, будучи запущена, работает непрерывно в течение некоторого промежутка времени, определяемого ее алгоритмом, а затем приостанавливается и возвращает управление диспетчеру, вызывая одну из его функций; диспетчер выбирает и запускает одну из задач, готовых к выполнению.
В рамках модели, время работы задачи между последовательными вызовами диспетчера - случайная величина, закон распределения которой зависит от текущего состояния задачи - ее "счетчика команд". "Счетчик команд" определяет операцию, выполняемую на данном шаге алгоритма задачи, время выполнения этой операции, следующее состояние и вызываемую функцию диспетчера. Такая модель задачи может быть и стохастической сетевой, когда следующее состояние выбирает генератор случайных чисел, и детерминированной автоматной.
Для определения закона распределения размера кванта в реальных задачах был проведен эксперимент. Измерялась длительность типичной "элементарной операции" - прочитать из файла и обработать элемент данных. Полученное эмпирическое распределение аппроксимируется нормальным со стандартным отклонением, равным примерно 1/3 математического ожидания. Такое распределение было взято за основу при генерации и оценке случайного размера кванта в модели.
Для моделирования времени ожидания действий пользователя в интерактивных программах, например, в текстовом редакторе, используется экспоненциальное распределение (это также нашло экспериментальное подтверждение).
Задача передает управление диспетчеру, вызывая одну из его функций:
* Switch - передать управление другой задаче. Задача приостанавливается только для того, чтобы дать другим возможность работать.
* Spawn( newTask ) - запустить новую задачу newTask.
* Die - завершить выполнение данной задачи.
* Block( blockTime ) - блокировать задачу на время blockTime, а затем вновь перевести ее в состояние готовности и с возможно меньшей задержкой передать на выполнение.
Эта функция, в отличие от остальных, не имеет аналогов в реальных ОС, но может использоваться для имитации любых асинхронных операций, таких, как ожидание сообщения от операционной системы (вызов GetMessage в ОС Windows), операции ввода-вывода на внешнее устройство (например, чтение с жесткого диска), реакция на действия пользователя (ожидание нажатия клавиши) и т.п. Можно имитировать операции, выполняемые регулярно, через равные промежутки времени, такие, как обработка сообщения таймера или опрос регистра состояния устройства. Во всех этих ситуациях, с точки зрения диспетчера, задача блокируется на неопределенный промежуток времени до наступления некоторого внешнего события. Реально это время не известно ни диспетчеру, ни самой задаче. В данной модели его определяет задача, например, с помощью генератора случайных чисел. Диспетчер же при планировании "делает вид", что момент, когда наступит событие, не известен ему заранее.
Для имитации реального состава мультипрограммной смеси выбраны несколько видов типичных процессов:
* Оболочка
Файловый менеджер, командная строка или другая подобная среда управления файлами и программами. Ожидает ввода с клавиатуры команд со средней длиной LEN символов, затем запускает одну из нижеперечисленных задач или процесс копирования файлов. Кроме того, регулярно обновляет на экране текуще время.
par
do
switch (gets())
spawn(editor)
spawn(mplayer)
copy()
while (not exit)
and
while (true)
updateClock();
delay()
and
open()
do
read()
write()
while (not eof)
end
* Текстовый редактор.
Состоит из двух потоков: один, поток проверки правописания или подсветки синтаксиса, выполняет в фоновом режиме работу вычислительного характера; другой ждет ввода с клавиатуры, поступающего в виде простейшего определенной интенсивности.
open();
par
while (true)
highlight();
and
do
readkey();
write();
while (not eof)
end
* Медиаплейер.
Этот тип приложения, наверное, в наибольшей степени использует и демонстрирует преимущества многозадачности: она позволяет серьезным людям делать вид, что они, на самом деле, заняты серьезными делами, пока слушают музыку. Windows Media Player запускает около полутора десятков параллельно работающих потоков для чтения, декодирования и воспроизведения музыки или видео. Эти три характерных функции представлены в модели: поток чтения данных регулярно обращается к медленному устройству ввода (например, проигрывателю компакт-дисков) для операций чтения с короткой обработкой; два потока параллельно выполняют длительную вычислительную работу; наконец, четвертый сравнительно часто выполняет быстрый вывод данных на звуковую карту.
open();
par
do
read();
process();
while (not eof);
and
while (true)
compute();
and
while (true)
process();
write();
end
Первой запускается оболочка, которая затем порождет другие задачи.
В каждом случае имеет значение, прежде всего, не алгоритм (и, соответственно, характер потока запросов к системе) работы программы в целом, а "микроструктура" набора задач, порождаемых ею. Диспетчер задач - это, по определению, краткосрочный планировщик.
Если инициализировать генераторы случайных чисел одним и тем ж числом, можно на одном и том же сценарии работы задач исследовать влияние различных параметров алгоритма принятия решения на качество управления.
Качество можно оценивать по времени выполнения всего сценария и отдельных задач, по доле времени ожидания и накладных расходов, по среднему времени реакции системы на внешние события.
Принципы принятия решения Принимая решение о выборе той или иной задачи из множества задач, находящихся в состоянии готовности, диспетчер стремится обеспечить:
* минимальное время реакции на внешние, асинхронные события: путем рационального выбора задач, минимизировать ожидаемые задержки в обработке таких событий. Задержки возникают из-за того, что обработка происходит синхронно, то есть начинается не в момент возникновения события, а только когда выполнявшаяся в это время задача вернет управление диспетчеру.
* справедливое распределение процессорного времени: доля времени владения процессором для всех задач должна быть одинаковой.
* минимальную долю накладных расходов и простоев, возникающих при переключении с задачи на задачу и при пассивном ожидании внешнего события, когда диспетчер никого не ставит на выполнение, а ждет, пока некоторая задача не перейдет в состояние готовности.
Диспетчер выбирает задачу с учетом:
* текущей ситуации - распределения процесора между задачами за последнее время, времени ожидания готовых к выполнению задач и т.п. Для каждой задачи можно дать детерминированную численую оценку ее как кандидата на выполнение.
* результатов моделирования дальнейшего развития ситуации - оценки последствий выбора данной задачи. Такая оценка может быть дана на основе априорной информации - статистики, накапливаемой в процессе выполнения задачи. Реальные программы обладают свойством локальности, на котором базируются алгоритмы конвейеризации и предсказания переходов, кэширования и распределения памяти: если программа выполяет какую-либо операцию, вероятно, что она в ближайшее время повторит ее. Поэтому можно достаточно обоснованно прогнозировать поведение программы - время выполнения, время ожидания события, вызываемую функцию - на ближайшее время по одному или нескольким предыдущим квантам. "Проиграв" на имитационной модели несколько случайных вариантов, можно выбрать для выполнения задачу с учетом вероятного развития событий.
Важность прогноза вытекает из следующих соображений.
* возможность оценки риска: на какое время очередная задача, если ее сейчас запустить, может задержать реакцию на внешние события, которые наступят в ближайшее время?
* "оперативное планирование": можно улучшить качество управления на протяжении нескольких шагов, принимая неоптимальные на данном шаге решения. Простейшая систуация, требующая "оперативного планирования", показана на рисунке: с точки зрения времени реакции, выгоднее подождать готовности задачи В и затем выполнять ее, чем немедленно запустить задачу А.
Для поиска оптимального решения в подобных случаях существуют строгие и точные методы математического программирования. В данной работе использован простейший способ перебора вариантов и статистических испытаний. Не претендуя на оптимальность - как по качеству решения, так и по вычислительным затратам, - он позволяет смоделировать ситуацию как принятие решения в условиях неопределенности, каковым оно и является. Горизонт прогноза ограничивается числом DEPTH. Кроме того, вес оценки каждого последующего этапа обратно пропорционален неопределенности на текущем этапе, которая оценивается по среднему квадратическому отклонению времени выполнения задачи, выбираемой на текущем этапе.
Алгоритм принятия решения сначала оценивает по очереди все готовые к выполнению задачи, а затем вариант ожидания события, который можно рассматривать как особую системную "задачу ожидания" wait. В каждом случае
1) вычисляется "текущая" оценка данной альтернативы,
2) применяется процедура вычисления ожидаемой оценки времени реакции (т.к. именно для улучшения реактивности и вводится прогнозирование) на следующем шаге прогноза:
* повторяются SAMPLES раз для формирования матрицы выигрышей следующие действия:
* моделируется запуск выбранной задачи - генерируется случайным образом время ее работы и вызов, на котором она остановится, а также множество внешних событий, произошедших к моменту остановки, на основании статистики, собранной за N последних запусков задачи. Предполагается, что генерируемые величины подчиняются нормальному закону распределения.
* вычисляется оценка суммарной задержки к моменту остановки выбранной задачи,
* процедура применяется рекурсивно в полученной ситуации, в качестве результата возвращая значение оценки времени реакции на следующем шаге,
* взвешенная сумма двух последних оценок характеризует оптимальность выбора данной задачи.
* по матрице выигрышей по критериям Лапласа или Гурвица определяется значение, принимаемое за "ожидаемую" оценку данной альтернативы;
3) обе оценки, полученные на этапах 1 и 2, суммируются с соответствующими весовыми коэффициентами.
Затем выбирается та задача, для которой сумма на шаге 3 имеет наибольшее значение.
Критерии оценки альтернатив
1) Время ожидания с момента разблокирования: показатель, непосредственно характеризующий время реакции системы. Критерий применяется только к задачам, вновь готовым к выполнению после вызова Block, для остановленных по Switch он равен нулю. Вычисляется как отношение времени ожидания к времени блокирования:
2) Оценка последствий: определяемый путем моделирования развития событий критерий оптимальности решения на следующих шагах, отнесенный к неопределенности ситуации, которая оценивается средним квадратическим отклонением времени выполнения оцениваемой задачи.
3) Справедливое разделение процессорного времени: для равноприоритетных задач доля времени владения процессором должна быть одинаковой. Критерий вычисляется как отношение суммы HISTORY последних времен ожидания в состоянии готовности к общему времени работы и ожидания за тот же период.
4) Время с момента запуска: для улучшения реактивности системы недавно запущенная задача имеет преимущество перед "старожилами". Время выполнения новой задачи априорно ограничивается значением Tmax, иначе из "осторожности" дипетчер мог бы никогда ее не запустить. Тем не менее, Tmax достаточно велико, чтобы диспетчер не запускал новую, "не изученную" задачу в условиях жестких временных ограничений. В этих условиях, новая задача оказывается в крайне "невыгодном" положении по отношению к "старым" по предыдущему критерию и может долго ждать своей очереди. Критерий вычисляется как где launches - число запусков задачи на выполнение с момента ее порождения (вызовом Spawn). 5) Ожидание и накладные расходы на переключение: для той задачи, которая только что выполнялась, накладные расходы на переключение на диспетчер и обратно примем равными единице. Для любой другой задачи расходы на переключение фиксированны и равны времени переключения задач switchTime. Для wait-задачи к ним добавляются расходы на ожидание, равные времени ожидания waitTime. Задача "ожидание" планируется на выполнение, наряду с другими, и выбирается, если немедленная реакция на следующее событие предпочтительнее с точки зрения достигаемого при этом максимума интегрального критерия оптимальности решения. При оценке wait-задачи как кандидата на выполнение диспетчер задает время ее работы как ожидаемое время наступления самого раннего из ожидаемых событий. Будучи запущена, wait-задача работает точно до возникновения первого события. Таким образом, диспетчер может получть нулевое время реакции на данное событие.
Интегральный критерий
вычисляется после нормализации локальных как сумма полученных значений, умноженных на значения весов критериев, заданные весовым вектором. Критерии выше были перечислены в порядке убывания приоритета.
Способ нормализации должен обеспечить два свойства нормализованных локальных критериев:
* приведение их к безразмерной величине в фиксированном и одинаковом для всех диапазоне, чтобы составляющие весового вектора имели смысл именно приоритетов, а не масштабных коэффициентов, компенсирующих разницу в практически получаемых интервалах изменения критериев,
* сравнимость двух интегральных критериев оптимальности, рассчитанных в разных ситуациях. Именно, требовалось сравнивать значения оценки последствий для двух различных альтернатив. Сравнимость и нужный диапазон для каждого из остальных локальных критериев можно получить путем нормализации делением на максимальное значение этого критерия среди всех альтернатив. Однако этот способ неприменим для рекурсивного вычисления оценки последствий, так как дал бы приблизительно равные значения оценок для каждой альтернативы. Действительно, при нормализации по максимальному из самих нормализуемых значений наибольшее значение критерия будет равно единице, независимо от того, насколько велико абсолютное, ненормализованное значение.
Поэтому в процессе вычисления этого критерия процедура расчета не производила нормализации, она применялась только на этапе формирования интегрального критерия.
Результаты моделирования
Оценка влияния критериев
Критерий справедливого распределения процессорного времени при отсустствии влияния других критериев порождает дисциплину обслуживания "очередь" (FIFO). Размер "предыстории" HISTORY, учитываемой при расчете значения критерия, влияет на порядок выполнения следующим образом: диспетчер ставит одну и ту же задачу на выполнение HISTORY+1 раз подряд. Это связано с тем, что к моменту выбора задачи "предыстория" содержит одно - последнее - большое время ожидания (с момента окончания предыдущей "серии") и HISTORY маленьких (в течение предыдущей "серии"). В течение следующих HISTORY запусков это большое число последовательно сдвигается к началу "предыстории", оказывая, в силу аддитивности критерия, такое же влияние на его величину. Как только на HISTORY+2-м шаге оно выходит за пределы "контекста" критерия, значение суммы резко уменьшается, и управление получает следующая задача.
Такое поведение нежелательно: учет "предыстории" введен исключительно для компенсации неравномерности или циклических колебаний времени работы и простоя, критерий должен оставаться достаточно гибким и чувствительным к текущим изменениям. Для этого можно увеличить вес последних по времени поступления данных в "предыстории" - учитывать "срок давности". Тот же подход может применяться и при вычислении по данным "предыстории" числовых характеристик закона статистического распределения времени выполнения и блокировки задачи (для прогнозирования времени реакции, как описывалось выше).
В то же время, повторный выбор последней задачи на выполнение - явление желательное, так как минимизируются накладные расходы на переключение задач, повышается эффективность использования коротких квантов, которые также обеспечивают высокую реактивность системы. Поэтому в модель введен критерий величины накладных расходов. Он способствует как повторному выбору задач, так и выбору задач с большей продолжительностью и, соответственно, меньшей частотой переключений и меньшей долей расходов на них.
Критерий времени с момента запуска действительно позволяет при соответствующем выборе весового коэффициента запускать новую задачу сразу после возникновения.
Критерий ожидаемых последствий достаточно эффективно работает, по крайней мере, на ближайшую перспективу (дальше ситуацию трудно проследить даже при ручной обработке протокола выполнения сценария). Средние значения коэффициента оптимизма критерия Гурвица и критерий Лапласа дают наилучшие результаты, меньшие значения отдают предпочтение ожиданию и задерживают выполнение фоновых задач. Однако это справедливо только для тех случаев, когда верно предположение о нормальности распределения времен работы и ожидания. Иначе (как, например, при оценке экспоненциально распределенных времен) качество может ухудшаться.
В целом, выбранные критерии позволяют принимать "разумные и предусмотрительные" решения.
Направления улучшения модели
В рассмотренной модели все критерии принятия решения ориентированы на работу с временными параметрами задач как независимых процессов, конкурирующих только за процессорное время. Более "предусмотрительный" диспетчер в модели, включающей взаимосвязи процессов по другим видам ресурсов, таким, как устройства ввода-вывода, память, разделяемые данные и т.д., мог бы учитывать владение такими разделяемыми ресурсами, наличие блокировок одних задач другими.
Кроме того, можно рассмотреть возможность более точного моделирования алгоритма задачи путем обнаружения хотя бы коротких и простых циклов ее работы. Это значительно увеличит точность прогноза.
Не вводилось понятие гарантий обслуживания как, например, минимальной вероятности того, что время реакции не выйдет за заданные пределы. Такое ограничение может более явно и определенно, чем коэффициент отимизма, влиять на реактивность системы.
Документ
Категория
Рефераты
Просмотров
39
Размер файла
130 Кб
Теги
sheduler
1/--страниц
Пожаловаться на содержимое документа