">
Информатика Программирование
Информация о работе

Тема: Моделирование работы планировщика с обратной связью

Описание: Операционная система и процессы. Модель функционирования параллельных программ. Алгоритм планирования процессов. Анализ предметной области и построение модели. Формализация задачи. Понятие процессов как основных динамических объектов.
Предмет: Информатика.
Дисциплина: Программирование.
Тип: Курсовая работа
Дата: 16.08.2012 г.
Язык: Русский
Скачиваний: 11
Поднять уникальность

Похожие работы:

Министерство образования РФ

ФГБОУ ВПО «Удмуртский Государственный Университет»

Математический Факультет

Курсовая работа на тему:

«Моделирование работы планировщика с обратной связью»

Ижевск, 2012

Содержание

Введение3

1.Аналитическая часть5

1.1Постановка задачи5

1.2. Операционная система и процессы5

1.3.Модель функционирования параллельных программ8

1.3.1.Понятие ресурса8

1.3.2.Организация программ как системы процессов9

1.4.Алгоритм планирования процессов 10

2.Построение объектной модели13

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

2.2. Формализация задачи15

3.Формирование объектной модели16

3.1.Идентификация классов и объектов16

3.2.Идентификация семантики классов17

3.3.Идентификация отношений между классами18

Заключение19

Список литературы20

Приложение21

Результат работы программы25

Введение

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

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

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

2.Эффективность – постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.

3.Сокращение полного времени выполнения (turnaround time) – обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.

4.Сокращение времени ожидания (waiting time) – сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.

5.Сокращение времени отклика (response time) – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

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

1.Были предсказуемыми. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.

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

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

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

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

1.Аналитическая часть

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

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

1.2.Операционная система и процессы

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

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

Программа – совокупность команд, связанных между собой, служащих для управления поведения вычислительной системы (ВС). Термин «программа» предназначен для описания статических, неактивных объектов. Программа же в процессе исполнения является динамическим, активным объектом. Для описания таких активных объектов внутри компьютерной системы вместо термина «программа» будем использовать термин – «процесс». Процесс – программа в стадии выполнения. Или, процесс – работа, выполняемая ЦП ВС в стадии выполнения программы, над какими-либо данными.

Состояния процесса:

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



Рис. 1.

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

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



Рис. 2.

ИСПОЛНЕНИЕ - активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

ОЖИДАНИЕ - пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

ГОТОВНОСТЬ - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

В состоянии ИСПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ИСПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно "вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

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

1.3.Модель функционирования параллельных программ.

1.3.1. Понятие ресурса

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

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

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

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

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

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

1.3.2. Организация программ как системы процессов

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



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

1.4.Алгоритм планирования процессов

«Многоуровневые очереди с обратной связью»

Алгоритмы назначения приоритетов процессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы.

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

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

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

Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке очередь, тем выше ее приоритет, и соответственно приоритет процессов, находящихся в ней. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один не заблокированный процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один незаблокированный процесс в очередях 0 и 1 и т.д. И наконец, процесс в очереди N может получить процессор в свое распоряжение только тогда, когда очереди 0, 1, 2 … N пусты. В итоге, после полной итерации алгоритма, то есть прохода всех очередей, мы получим систему в которой очереди ожидания пусты и все процессы оказываются в заблокированном состоянии. Планирование процессов внутри очередей осуществляется с использованием алгоритма RR.

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

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 1 условная единица. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 2 условные единицы. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается – остается в очереди 1. В очереди 2 величина кванта времени составляет 3 условные единицы и т.д. Если процесс дошел до очереди N, то для него квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать. Таким образом, через некоторое время все процессы, требующие малого времени работы процессора, окажутся размещенными в высокоприоритетных очередях, а все процессы, требующие большого счета и с низкими запросами к времени отклика, – в низкоприоритетных.



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

1. Количество очередей для процессов, находящихся в состоянии готовность.

2. Алгоритм планирования, действующий между очередями.

3. Алгоритмы планирования, действующие внутри очередей.

4. Правила помещения родившегося процесса в одну из очередей.

5. Правила перевода процессов из одной очереди в другую.

6. Число, указывающее увеличение длины кванта времени при переходе от одной очереди к другой.

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

2.Построение объектной модели

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

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

1.Процесс.

2.Операционная система.

В модели каждый из процессов, в течение своей жизни переходит по трем состояниям – готовность, выполнение и блокировка и имеет следующие характеристики – время жизни и состояние. Для взаимодействия процессов в рамках операционной системы необходимо реализовать: очередь процессов готовых к выполнению, которая представляет из себя структуру организованную по принципу FIFO; список заблокированных процессов – организация данных в такой структуре должна носить характер «кучи», любой процесс в любой момент времени может быть извлечен. Также в модели необходимо реализовать состояние – выполнение, которое мы назовем процессором, т.е. если процесс находится в стадии выполнения в данный момент времени, он расположен на процессоре. Вся информация о процессах хранится в таблице процессов.

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

Каждый из процессов характеризуется понятием «вероятность блокировки», то есть за один элементарный квант времени у процесса есть вероятность после состояния «выполнение» перейти в состояние «блокировка». Покажем, что такой метод гарантирует правильное поведение системы в соответствии с изучаемым алгоритмом. Действительно, пусть процесс находится в очереди 0.Он, имея высокую вероятность блокировки будет переходить в состояние блокировки за 1 квант времени, то есть верным образом будет продемонстрирован, тот факт, что длина непрерывного пребывания на процессоре будет меньше, чем длина кванта времени в соответствующей очереди. Кроме того, вероятность данной характеристики позволяет нам наиболее реально выразить понятие «интерактивность», поскольку реально мы не можем говорить о том что время непрерывного пребывания процесса на процессоре постоянно. Более того это позволяет нам в успешно решить поставленную задачу. Теперь пусть процесс не заблокировался в очереди 0, он переходит в очередь 1 с длиной кванта времени 2. В этом случае разыграем попытку блокировки дважды. Если процесс не заблокировался, то он переходит в очередь 2 и т.д. Предположим «вероятность блокировки» равна p. Вероятность блокировки в очередь 0 равна p, в очереди 1 – (1-p)p, в очереди 2 – (1-p)2p и т.д. В силу того, что ?(1-p)k-1p = 1 ,гарантируется, что найдется очередь в которой процесс заблокируется, мы можем отождествить понятие «вероятность блокировки» нашей модели и понятие интерактивность процесса реальной операционной системы.

2.2.Формализация задачи

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

1. Будем считать, что квант времени принимает целочисленное значение. То есть длина элементарного кванта времени, время жизни процесса, увеличение кванта времени при переходе от одной очереди к другой – это целое положительное число.

2. Созданные процессы помещаются в очередь 0.

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

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

3. Формирование объектной модели.

3.1. Идентификация объектов и классов.

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

Итак, объектно-ориентированная модель включает следующие классы:

Очередь(QueueProc)

Процесс (Process).

Планировщик(Scheduler).

Его смысл будет раскрыт при дальнейшем проектировании модели.

3.2. Идентификация семантики классов.

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

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

Приведем полное описание методов и полей каждого класса: Название класса Название поля/метода Описание  1.QueueProc int n; Количество элементов   int quant; квант   Add(Process p) Добавляем процесс в очередь   Process Get_Process() Достает элемент из очереди   int Get_n() Возвращает количество элементов в очереди   int Get_Quant() Возвращает количество времени которое дает очередь  2.Process int identifier; Номер процесса   string Info() Вывод информации о процессе   String action; Действие   String condition; Состояние   int CPU_burst; Сколько времени требуется процессу до блокировки  3. Scheduler QueueProc queue0; Очередь с нулевым приоритетом   QueueProc queue1; Очередь с первым приоритетом   QueueProc queue2; Очередь со вторым приоритетом   QueueProc queue3; Очередь с третьим приоритетом   Process CreateProcess(int) Создание процесса   Sort(Process, int) Сортировка процессам по очередям   void Start() Запуск планировщика   void RunProcess(QueueProc) Запуск процесса  

3.3. Идентификация отношений между классами.

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

Реализуем данную модель на объектно-ориентированном языке C#, среда разработки Microsoft Visual Studio 2008. Как любой объектно-ориентированный язык, он позволяет удачно реализовать все элементы модели, их взаимосвязи и взаимодействия.

Заключение

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

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

Список литературы

1. Гордеев А. В. Операционные системы: учебник для вузов. — 2-е изд. — СПб.: Питер, 2007.

2. Таненбаум Э. С. Современные операционные системы. — 2-е изд. — СПб.: Питер, 2005.

3. Г.Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на C++. — М.: Бином, 1998.

4. Интернет – ресурсы:

http://esyr.org/wiki/

http://www.intuit.ru/department/os/osintro/3/osintro_3.html

http://www.software.unn.ru/ccam/files/HTML_Version/part5.html

Приложение

Исходный код

Результат работы программы