Министерство Образования Российской Федерации

Новосибирский Государственный Технический Университет

КУРСОВАЯ РАБОТА

по дисциплине “Операционные системы”

Факультет: АВТ Преподаватель:

Группа: АМ-509

Студент:

Новосибирск, 2008

СОДЕРЖАНИЕ

Теоретические основы планирования и диспетчеризации. 3

Исходные данные. 8

Временная диаграмма при использовании FIFO.. 10

Временная диаграмма при использовании SJF. 11

Сравнительный анализ диаграмм.. 12

Структурные схемы дисциплин обслуживания. 12

Алгоритм функционирования диспетчера. 13

Заключение. 14

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

Теоретические основы планирования и диспетчеризации

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

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

Можно выделить следующие компоненты этой службы:

·  планировщик заданий,

·  планировщик задач (планировщик процессов).

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

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

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

В случае мультипрограммирования планировщик выбирает несколько заданий из множества всех представленных и вводит их в систему. Для каждого задания формируется таблица задания JCB (Job Control Block). Рис. 1.

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

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

Рис. 1. Таблица задания

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

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

Классификация дисциплин обслуживания приведена на рис. 2.

Рис. 2. Классификация дисциплин обслуживания

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

,

где t – время обращения задания;

tЗ – время завершения задания;

tП – время поступления задания.

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

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

,

где W – взвешенное время обращения;

T – действительное время выполнения задания (трудоемкость).

Для случая M заданий можно провести оценку по среднему взвешенному времени обращения

,

где – средневзвешенное время обращения;

– взвешенное время обращения i-го задания;

M – количество заданий.

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

Математическое обеспечение (МО) – это совокупность алгоритмов, алгоритмических языков, математических методов и программного обеспечения, предназначенных для увеличения эффективности решения задач.

Программное обеспечение (ПО) – совокупность регулярно используемых программ при эксплуатации вычислительных систем.

К ресурсам вычислительных систем относят:

1.  Аппаратные ресурсы

1.1.  ЦП

1.2.  Внешние устройства

1.3.  Периферийные устройства

2.  Программные ресурсы

2.1.  Библиотеки подпрограмм

2.2.  Сервисные программы

2.3.  Системные программы

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

1.  Пользователя

1.1.  Управление заданиями

1.2.  Задачами

1.3.  Данными

1.4.  Восстановлением

2.  Системы

2.1.  Управление ЦП

2.2.  Внешними устройствами

2.3.  Оперативной памятью

2.4.  Информацией

Рассмотрим управление заданиями. Задание – это максимальная единица работы для системы, задания являются независимыми и выполняются параллельно.

Особенности управления заданиями

1.В системе одновременно создается и выполняется множество параллельных работ – заданий.

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

3.В операционной системе создается множество управляющих таблиц, т. е. управление в системе основано на методе управляющих таблиц.

4.Процессы периодически требуют общие ресурсы (внешние устройства, CPU, системные таблицы, системные программы и др.).

5.Все процессы постоянно обращаются к управляющей программе Супервизору (SV) – головная программа, для управления ресурсами.

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

Шаг задания – это составная часть задания, выполняемая самостоятельно. Шаги выполняются строго последовательно и взаимодействуют.

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

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

·  распределение центрального процессора в динамике в соответствии с критериями;

·  эффективная отработка алгоритмов управления задачами.

·  сбалансированное использование ресурсов.

·  баланс между временем ответа и коэффициентом использования ресурсов.

Диспетчер – это программа, которая выбирает задачи (процессы) из «очереди на выполнение», переводит их в активное состояние и передает их на обработку центральному процессору.

Планирование процессов включает в себя решение следующих задач:

-  определение момента времени для смены выполняемого процесса;

-  выбор процесса на выполнение из очереди готовых процессов;

-  переключение контекстов "старого" и "нового" процессов.

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

В соответствии с алгоритмами, основанными на квантовании, смена активного процесса происходит, если:

·  процесс завершился и покинул систему,

·  произошла ошибка,

·  процесс перешел в состояние ОЖИДАНИЕ,

·  исчерпан квант процессорного времени, отведенный данному процессу.

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени. Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По-разному может быть организована очередь готовых процессов: циклически, по правилу "первый пришел – первый обслужился" (FIFO) или по правилу "последний пришел – первый обслужился" (LIFO). Другая группа алгоритмов использует понятие "приоритет" процесса. Приоритет – это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии. Приоритет может выражаться целыми или дробными, положительным или отрицательным значением. Чем выше привилегии процесса, тем меньше времени он будет проводить в очередях. Приоритет может назначаться директивно администратором системы в зависимости от важности работы или внесенной платы, либо вычисляться самой ОС по определенным правилам, он может оставаться фиксированным на протяжении всей жизни процесса либо изменяться во времени в соответствии с некоторым законом. В последнем случае приоритеты называются динамическими. Существует две разновидности приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и алгоритмы, использующие абсолютные приоритеты. В обоих случаях выбор процесса на выполнение из очереди готовых осуществляется одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается проблема определения момента смены активного процесса. В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности.

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

Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

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

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

Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу. Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить "дружественное" отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением "недружественности" приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения. Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в "неудобные" для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу. Примером эффективного использования невытесняющей многозадачности является файл-сервер NetWare, в котором, в значительной степени благодаря этому, достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование невытесняющей многозадачности в операционной среде Windows 3.х.

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

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

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

Диспетчер – это программа, которая выбирает процессы из очереди-на-выполнение, переводит их в активное состояние и передает им контроль над центральным процессором (CPU).

Основная функция планировщика-диспетчера – возможность управлять действиями большого числа процессов.

Исходные данные

Вычислительная система располагает оперативной памятью (ОП) V и внешним объёмом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время ti, для простоты каждое задание состоит из одной задачи и требует объём ОП - vi, объём внешней памяти hi, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*hi, после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Тi = q*hi + ti. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

1)  среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO);

2)  среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание с наименьшим ti(правило SJF).

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

,

где - время завершения задания,

- время поступления задания в систему.

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

Xi = [7 * Xi-1 + 417] mod 1000;

Ki = [Xi / 7] mod 10, i=1¸M, Xo = N,

где [c] - целая часть числа с,

y mod z - остаток от деления y на z,

Xo = N - шифр (последние три цифры из зачетной книжки; если четное число, то +1, чтобы получилось нечетное).

Значение используемых параметров : V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki.

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

Диспетчер использует метод разделения времени в сочетании с приоритетами. Бесприоритетная ДО (БП) – LIFO; приоритетная ДО (П) – относительный приоритет.

Последние 3 цифры номера зачётной книжки: 901. Т. е. X0=901, построим остальные требуемые параметры по формулам приведённым выше.

Таблица 1

Исходные данные задач

Временная диаграмма при использовании FIFO

Временная диаграмма при использовании SJF

Таблица 3

Характеристики дисциплины SJF

В начале выполнения задач диаграммы отличаются мало, так как задачам достаточно ресурсов, и они начинают загружаться и выполняться сразу же после исполнения. Но в момент времени 82 в случае FIFO запускается задача 9, а в SJF задача 10. это приводит к некоторым перестановкам. В обоих случаях последней выходит из система задача 6 в момент времени 393 для FIFO и в 408 для SJF.

Однако среднее взвешенное время нахождения задач в системе у SJF меньше, чем у FIFO – 4,8 и 5 соответственно. Это показывает, что для данного набора задач дисциплина SJF эффективнее, но незначительно.

Структурные схемы дисциплин обслуживания

Следует отметить, что дисциплина обслуживания (ДО) – это правило работы с очередью (формирование очереди), обслуживание очереди.

Беcприоритетные ДО (БДО) – выбирают заявки без учета их важности, например, по признаку последовательности поступления. Линейные ДО характеризуются одинаковым средним временем ожидания не зависимо от длительности заявки (т. е. трудоемкости). Линейная ДО LIFO реализует принцип стека (последний вошёл, первый вышел).

Рис. 5. Схема обслуживания заявок по дисциплине LIFO.

Приоритетные ДО – выбирают работы по их важности. В ДО с фиксированным приоритетом приоритет не изменяется с течением времени. В ДО с относительным приоритетом (ОП) выполнение приоритетной заявки не прерываются при поступлении более приоритетной. На рисунке представлена схема алгоритма ДО(относительный приоритет ОП).

Рис. 6. Схема обслуживания заявок при относительном приоритете (ОП).

Если поступило несколько заявок одного приоритета, то в очереди они обслуживаются по принципу FIFO.

Алгоритм функционирования диспетчера

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

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

Рис. 7. Блок-схема алгоритма диспетчера.

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

Заключение

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

На наборе из десяти задач сравнивались две различные дисциплины обслуживания при планировании: FIFO и SJF. Основным критерием сравнения являлось среднее взвешенное время нахождения задачи в системе. По результатам построения временных диаграмм ДО SJF (средневзвешенное время 4.8 единиц) оказалась немного более эффективной, чем ДО FIFO (5 единиц).

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

Программа-симулятор диспетчера позволяет рассмотреть работу таких ДО как LIFO и ОП, как в автоматическом, так и пошаговом режиме.