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

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

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

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

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

Выполнил:

Студент гр.О 010200 - 33

Каракулов И.С.

Проверил:

к. ф.-м. н.

Тонков Л.Е.

Ижевск, 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.

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

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

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

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

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