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

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

Факультет автоматики и вычислительной техники

 

 

 

 

 

 

Курсовой  проект

По  дисциплине

«Операционные системы»

 

 

 

 

Выполнил  студент факультета ЗО ИДО

Юцис А.В.

Группа  ЗФ 927

Проверил                       Коршикова Л.А.

 

 

 

 

 

 

 

 

 

 

 

Новосибирск-2012 г 

 

1. Цель работы.

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

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

2. Общие сведения о планировании заданий

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

2. Цели планирования

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

1)            быть справедливой. Дисциплина считается  справедливой, если ко всем процессам  она относится одинаково и  ни один процесс не будет  отложен на бесконечное время;

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

3)            обеспечивать минимальное время  ответа (для интерактивных систем);

4)            быть предсказуемой, т.е. одно  и то же задание должно выполняться  в разных сеансах приблизительно  за одно и то же время;

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

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

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

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

9)            учитывать приоритеты;

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

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

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

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

2.3.  Критерии планирования

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

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

3.       Рабочие  характеристики процесса:

• приоритетность;
• наличие прерывания по отсутствии страниц;
• время ЦП, уже выделенному процессу;
• ожидаемое время завершения.

 Механизм планирования  должен как можно раньше определять  характер заданий. Механизм планирования  должен отдавать предпочтение  коротким заданиям, лимитируемым  вводом/выводом.

2.4. Дисциплины планирования

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

2.       Более  простой является дисциплина  планирования по принципу FIFO (First In - First Out). Это планирование обеспечивает хорошую справедливость, однако многие цели планирования оказываются не выполненными. Например, время ответа в режиме разделения времени гарантируется слабо.

3.       Циклическое  планирование, когда задания обслуживаются  по кругу (Round Robin, RR). Грубо говоря, это FIFO с ограниченным временем кванта ЦП. Если процесс не завершается по истечении кванта, он возвращается в конец очереди готовых процессов. При работе в режиме разделения времени обеспечивается хорошее время ответа для всех интерактивных пользователей.

4.       Дисциплина SJF (Shortest Job First) - кратчайшее задание - первым. Эта дисциплина обеспечивает уменьшение минимального времени ожидания, по сравнению с FIFO, но дисперсия времен ожидания оказывается несколько выше. Проблема возникает при оценке времени выполнения того или процесса. Регулярный счет однотипных заданий позволяет применять данную дисциплину.

5.       Планирование  по принципу SRT (Shortest Remaining Time) - по наименьшему отстающему времени. Данный механизм учитывает, сколько время осталось процессу до завершения.

6.      По относительно  наибольшему времени реакции  HRN (Highest Response Ratio Next). Эта дисциплина обеспечивает выполнение задания с приоритетом, учитывающим не только время обслуживания процесса, но и время, затраченное на ожидание. Динамический приоритет рассчитывается по формуле:

 Приоритет = (Время_ожидания + Время_обслуживания) / Время_обслуживания

5. . Оценки эффективности планирования

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

t = t_З – t_П, где

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

t_З – время завершения задания,

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

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

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

W = (t_З – t_П) / T, где

W – взвешенное время  обращения,

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

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

W_СР – средневзвешенное время обращения,

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

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

 

3. Часть 1

3.1 Задание и исходные  данные к курсовой работе.

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

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

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

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

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

K_i = [X_i / 7] mod 10;

X₀ = 429;

№ задания	Xi	Ki	V	H	T	ti
0	350	0	6	2	70	0
1	867	4	3	2	60	4
2	486	9	1	3	50	15
3	819	7	9	1	30	22
4	150	1	3	4	90	23
5	467	7	9	1	30	30
6	686	8	4	6	40	38
7	219	1	3	4	90	39
8	950	6	7	4	20	45
9	67	9	1	3	50	54