Курсовая работа по дисциплине: «Операционные системы» (стр. 1 )

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Курсовая работа

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

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

ВС в мультипрограммном режиме. Диспетчеризация задач

Факультет: АВТ

Группа: АМ-610

Студент:

Преподаватель:

Вариант: 003, 3

Новосибирск 2009

Содержание:

Раздел 1. 2

1.1 Задание. 2

1.2 Теоретические основы. 4

1.3 Исходные данные. 6

1.4 ДО FIFO. 7

1.5 ДО SJF. 10

1.6 Сравнительный анализ двух диаграмм. 13

Раздел 2. 14

2.1 Задание. 14

2.2 Исходные данные. 14

2.3 Диспетчеризация задач для бесприоритетной ДО LIFO. 15

2.4 Диспетчер задач для приоритетной ДО – адаптивное обслуживание.. 17

2.5 Программная реализация диспетчера с ДО FIFO. 20

2.6 Листинг работы программы диспетчера с ДО FIFO. 23

2.7 Программная реализация диспетчера с ДО «адаптивное обслуживание.. 27

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

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

Раздел 1

1.1  Задание.

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

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

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

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

,

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

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

1.2  Теоретические основы.

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

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

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

Задание представляет собой описание комплекса работ, которые пользователь хочет выполнить на ЭВМ. Этот комплекс может быть представлен в виде последовательности некоторых частных работ, описываемых с помощью шагов задания. Из шагов задания формируются задачи. Для выполнения задач система создает процессы. Объектами работы планировщика заданий являются задания, а планировщик задач управляет процессами. Планировщик заданий выбирает, какие задания и в какой последовательности должны поступать на обработку (своего рода «макропланировщик»). Планировщик задач выступает в роли «микропланировщика», распределяющего процессор между процессами. В случае мультипрограммирования планировщик заданий выбирает несколько заданий из множества всех представленных и вводит их в систему. Для каждого задания формируется таблица задания JCB (Job Control Block). Для программного выполнения этих заданий планировщик заданий создает процессы и выделяет им необходимые ресурсы (память, внешние устройства). Планировщик процессов должен решить, какому из созданных процессов предоставить процессор, в какой момент и на какое время. Планировщик заданий обеспечивает определенную дисциплину выбора заданий на обработку. Для принятия такого решения могут учитываться такие характеристики заданий, как приоритет, необходимые ресурсы и т. п. Планировщик заданий не только выделяет необходимые ресурсы для поступающего на обработку задания, но и освобождает ресурсы после выполнения задания.

Дисциплины обслуживания

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

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

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

В настоящей работе рассматриваются 2 дисциплины обслуживания:

1 - линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.

2 - дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.

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

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

t = tЗ – tП, где

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

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

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

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

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

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

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

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

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

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

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

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

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

Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 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 = 003

= + Кi - интервал поступления заданий;

M=10 - число заданий.

Таблица 1. Исходные данные

Номер задачи	Xi	Ki	Используемая ОП, vi	Используемая внешняя память, hi	Трудо емкость tCPU	Время поступления,	Время загрузки, q*hi (tв)	Ti
0	438	2	2	3	40	2	15	55
1	483	9	1	3	50	11	15	65
2	798	4	3	2	60	15	10	70
3	3	0	6	2	70	15	10	80
4	438	2	2	3	40	17	15	55
5	483	9	1	3	50	26	15	65
6	798	4	3	2	60	30	10	70
7	3	0	6	2	70	30	10	80
8	438	2	2	3	40	32	15	55
9	483	9	1	3	50	41	15	65

Значение используемых параметров вычислительной системы:

V=16 - Оперативная память

H=12 - Внешняя память

q=5 - Коэффициент для вычисления времени ввода данных задания с внешней памяти (q×hi), после которого будет произведён счет

1.4 ДО FIFO.

Таблица 2. Журнал событий мультипрограммной работы ЭВМ (ДО FIFO).

Время	События	Доступно	Требуется	Km
V	H	vi	hi
0	Заданий нет. Простой системы.	16	12	0	0	0
2	Поступило задание 0: начинается ввод задания. Процессор простаивает	14	9	2	3	0
11	Поступило задание 1: начинается ввод задания. Процессор простаивает.	13	6	1	3	0
15	Поступило задание 2: начинается ввод задания. Поступило задание 3: начинается ввод задания. Процессор простаивает.	4	2	3 + 6	2 + 2	0
16	Завершён ввод задания 0. Задания на процессоре: 0 .	4	2	0	0	1
17	Поступило задание 4: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0	4	2	0	0	1
24	Завершён ввод задания 2. Завершён ввод задания 3. Задания на процессоре:	4	2	0	0	3
25	Завершён ввод задания 1. Задания на процессоре:	4	2	0	0	4
26	Поступило задание 5: нехватка ресурсов - задание помещено в очередь. Задания на процессоре:	4	2	0	0	4
30	Поступило задание 6: начинается ввод задания. Поступило задание 7: нехватка ресурсов - задание помещено в очередь. Задания на процессоре:	1	0	3	2	4
32	Поступило задание 8: нехватка ресурсов - задание помещено в очередь. Задания на процессоре:	1	0	0	0	4
39	Завершён ввод задания 6. Задания на процессоре:	1	0	0	0	5
41	Поступило задание 9: нехватка ресурсов - задание помещено в очередь. Задания на процессоре:	1	0	0	0	5
181	Завершено задание 0 и его ресурсы освобождены. Из очереди выбирается задание 4: начинается ввод задания. Задания на процессоре:	1	0	2	3	5
196	Завершён ввод задания 4. Задания на процессоре:	1	0	0	0	5
269	Завершено задание 1 и его ресурсы освобождены. Из очереди выбирается задание 5: начинается ввод задания. Задания на процессоре:	1	0	1	3	5
284	Завершён ввод задания 5. Задания на процессоре:	1	0	0	0	5
317	Завершено задание 2 и его ресурсы освобождены. Задания на процессоре:	4	2	0	0	5
333	Завершено задание 6 и его ресурсы освобождены. Из очереди выбирается задание 7: начинается ввод задания. Задания на процессоре:	1	2	6	2	4
343	Завершён ввод задания 7. Задания на процессоре:	1	2	0	0	4
355	Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 8: начинается ввод задания. Задания на процессоре:	5	1	2	3	4
370	Завершён ввод задания 8. Задания на процессоре:	5	1	0	0	4
372	Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 9: начинается ввод задания. Задания на процессоре:	6	1	1	3	4
387	Завершён ввод задания 9. Задания на процессоре:	6	1	0	0	4
481	Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: V=7, H=4, K=4.	7	4	0	0	4
516	Завершено задание 8 и его ресурсы освобождены. Задания на процессоре:	9	7	0	0	3
547	Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 7 9 .	10	10	0	0	2
555	Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 7 .	16	12	0	0	1