Вычислительная система в мультипрограммном режиме. Планирование и диспетчеризация задач
Основные и дополнительные функции современных операционных систем. Особенности реализации приоритетных дисциплин обслуживания. Оценки эффективности планирования. Планирование верхнего уровня управления заданиями. Сравнительный анализ дисциплин FIFO и SJF.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 23.09.2013 |
| Размер файла | 353,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Оглавление
- Введение
- 1. Теоретические основы планирования и диспетчеризации
- 1.1 Дисциплины обслуживания
- 1.3 Оценки эффективности планирования
- 2. Планирование верхнего уровня управления заданиями
- 2.1 Исходные данные
- 2.2 Сравнительный анализ дисциплин FIFO и SJF
- 2.3 Выводы
- 3. Диспетчеризация
- 3.1 Задание
- 3.2 Бесприоритетная ДО - смешанный алгоритм
- 3.3 Приоритетная ДО - относительный приоритет
- Заключение
- Список литературы
- Приложение
Введение
Цель работы:
В данной курсовой работе целью является исследование дисциплин обслуживания в мультипрограммной среде и их сравнение.
Вследствие этого ставятся следующие задачи:
изучение теоретических данных об основах планирования и диспетчеризации;
построение временных диаграмм для исследования работы алгоритмов дисциплин FIFO и SJF;
выявление сходств и различий между работой алгоритмов;
разработка структуры функционирования диспетчера работ в вычислительной системе.
В силу этого, работа содержит 3 раздела, посвящённых теории основ планирования и диспетчеризации, сравнению дисциплин FIFO и SJF и а также представлению структуры функционирования диспетчера работ в вычислительной системе.
1. Теоретические основы планирования и диспетчеризации
В наше время компьютеры представляют собой крайне сложные машины, и для стабильной работы им просто необходимы системы управления, а именно - операционные системы. В свою очередь, операционные системы (ОС) представляют собой целый комплекс управляющих и обрабатывающих программ, которые, с одной стороны, выступают как интерфейс между устройствами вычислительной системы и прикладными программами, а с другой стороны - предназначены для управления устройствами, управления вычислительными процессами, эффективного распределения вычислительных ресурсов между вычислительными процессами и организации надёжных вычислений.
Современные ОС имеют целое множество функций:
Основные функции:
· Выполнение по запросу программ (ввод и вывод данных, запуск и остановка других программ, выделение и освобождение дополнительной памяти и др.).
· Загрузка программ в оперативную память и их выполнение.
· Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода).
· Управление оперативной памятью (распределение между процессами, организация виртуальной памяти).
· Управление доступом к данным на энергонезависимых носителях (таких как жёсткий диск, оптические диски и др.), организованным в той или иной файловой системе.
· Обеспечение пользовательского интерфейса.
· Сохранение информации об ошибках системы.
Дополнительные функции:
· Параллельное или псевдопараллельное выполнение задач (многозадачность).
· Эффективное распределение ресурсов вычислительной системы между процессами.
· Разграничение доступа различных процессов к ресурсам.
· Организация надёжных вычислений (невозможности одного вычислительного процесса намеренно или по ошибке повлиять на вычисления в другом процессе), основана на разграничении доступа к ресурсам.
· Взаимодействие между процессами: обмен данными, взаимная синхронизация.
· Защита самой системы, а также пользовательских данных и программ от действий пользователей (злонамеренных или по незнанию) или приложений.
· Многопользовательский режим работы и разграничение прав доступа (см. аутентификация, авторизация).
Центральная часть ОС - ядро, управляющее выполнением процессов, ресурсами вычислительной системы и предоставляющая процессам координированный доступ к этим ресурсам. Любая операционная система позволяет обрабатывать поступающую информацию в мультипрограммном режиме, т.е. в систему может поступить несколько заданий и если она обладает достаточными ресурсами памяти, то эти задания могут быть выполнены либо все одновременно, либо в какой-то последовательности. Примитивные многозадачные среды обеспечивают чистое "разделение ресурсов", когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени. Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. В последних ресурсы распределяет служба управления, которая содержит 2 составляющие: планировщик заданий и планировщик задач. Планировщик заданий выбирает, какие задания и в какой последовательности должны поступать на обработку. Он должен обеспечивать определённую дисциплину выбора заданий на обработку. Для принятия такого решения могут учитываться такие характеристики заданий, как приоритет, необходимые ресурсы и т.п. Планировщик заданий не только выделяет необходимые ресурсы для поступающего на обработку задания, но и освобождает ресурсы после выполнения задания. Также планировщик задач занимается распределением ресурсов процессора между процессами. Он должен решить, какому из созданных процессов предоставить процессор, в какой момент и на сколько, во временном отношении.
1.1 Дисциплины обслуживания
Известно большое количество правил в соответствии с которыми формируется список готовых к выполнению задач. Различают два больших класса дисциплин обслуживания - бесприоритетные и приоритетные. При бесприоритетном обслуживании выбор задачи производится в некотором заранее установленном порядке без учета их относительной важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения.
Более развёрнутая классификация имеет следующий вид:
Бесприоритетные ДО:
1. FIFO - "первым пришел - первым выбран на обслуживание".
Время обслуживания заявки равно ее трудоемкости.
2. LIFO - "последним пришел - первым выбран на обслуживание".
Время обработки самой последней задачи аналогично FIFO.
3. RAND - случайный выбор заявки из очереди.
планирование диспетчеризация дисциплина обслуживание
4. RR - "круговорот". Отличается от FIFO лишь временем обслуживания: каждая заявка получает определенный квант времени (одинаковый для всех).
Приоритетные ДО:
1. PRT - выбор заявок на обслуживание по приоритету. Более приоритетной заявке соответствует меньшее число.
2. SJF - выбор заявки на обслуживание с минимальной трудоемкостью.
3. Дисциплины обслуживания со сложными динамическими приоритетами.
1.2 Оценки эффективности планирования
Существует несколько оценок эффективности планирования. Одной из них является время обращения задания - время, прошедшее с момента поступления задания в систему до момента завершения его выполнения.
t = tЗ - tП, где
t - время обращения задания, tЗ - время завершения задания, tП - время поступления задания.
Но эта оценка не является универсальной. Например, если сравнивать время обращения одночасового и одноминутного задания (при условии, что задания начнут выполняться сразу же, как только поступят в систему), то время обращения одночасового задания будет значительно больше, чем время обращения одноминутного. Но это совсем не значит, что одночасовое задание было обслужено плохо, т.к. время обращения задания не может быть меньше времени выполнения.
Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения
W = (tЗ - tП) / T, где
W - взвешенное время обращения,
T - действительное время выполнения задания.
Для случая M заданий можно провести оценку по среднему взвешенному времени обращения
WСР - средневзвешенное время обращения,
Wi - взвешенное время обращения i - го задания,
M - количество заданий.
2. Планирование верхнего уровня управления заданиями
2.1 Исходные данные
Вычислительная система располагает оперативной памятью (ОП) V и внешним объемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время ti, для простоты каждое задание состоит из одной задачи и требует объем ОП - vi, объем внешней памяти hi, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*hi, после чего начинается счет.
Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время
Тi = q*hi + ti.
Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:
1) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO);
2) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание с наименьшим ti (правило SJF).
Необходимо построить временную диаграмму мультипрограммной работы при использовании каждого из двух алгоритмов. На диаграмме выделить события (моменты поступления заданий, моменты назначения на выполнение, моменты начала счета, моменты завершения) и периоды между событиями. Для каждого периода указать процессорное время на задание, доступную память, доступную дисковую память, степень мультипрограммирования. Провести сравнение двух случаев по средневзвешенному времени обращения:
,
где - время завершения задания, - время поступления задания в систему.
Таблица 1. Последовательность заданий и их параметры
|
N задания |
Xi |
Ki |
vi |
hi |
i |
tпоступления |
|
|
0 |
417 |
- |
- |
- |
- |
- |
|
|
1 |
894 |
7 |
9 |
1 |
30 |
7 |
|
|
2 |
675 |
6 |
7 |
4 |
20 |
13 |
|
|
3 |
142 |
0 |
6 |
2 |
70 |
13 |
|
|
4 |
411 |
8 |
4 |
6 |
40 |
21 |
|
|
5 |
294 |
2 |
2 |
3 |
40 |
23 |
|
|
6 |
475 |
7 |
9 |
1 |
30 |
30 |
|
|
7 |
742 |
6 |
7 |
4 |
20 |
36 |
|
|
8 |
611 |
7 |
9 |
1 |
30 |
43 |
|
|
9 |
694 |
9 |
1 |
3 |
50 |
52 |
|
|
10 |
275 |
9 |
1 |
3 |
50 |
61 |
Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki.
2.2 Сравнительный анализ дисциплин FIFO и SJF
Воспользовавшись программным пакетом MultiVis. exe, составим трассировочные таблицы для обеих дисциплин обслуживания и сравним их работу в равных условиях (одинаковые ресурсы).
Дисциплина FIFO
Таблица 2. Трассировка планирования по алгоритму FIFO
|
время |
событие |
V |
H |
K |
|
|
7 |
Поступило задание 0: начинается ввод задания. Процессор простаивает. |
7 |
11 |
0 |
|
|
11 |
Завершён ввод задания 0. Задания на процессоре: 0. |
7 |
11 |
1 |
|
|
13 |
Поступило задание 1: начинается ввод задания. Поступило задание 2: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
21 |
Поступило задание 3: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
23 |
Поступило задание 4: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
30 |
Поступило задание 5: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
32 |
Завершён ввод задания 1. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
36 |
Поступило задание 6: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
43 |
Поступило задание 7: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
50 |
Завершено задание 0 и его ресурсы освобождены. Из очереди выбирается задание 2: начинается ввод задания. Задания на процессоре: 0 1. |
3 |
6 |
2 |
|
|
52 |
Поступило задание 8: начинается ввод задания. Задания на процессоре: 1. |
2 |
3 |
1 |
|
|
60 |
Завершён ввод задания 2. Задания на процессоре: 1 2. |
2 |
3 |
2 |
|
|
61 |
Поступило задание 9: начинается ввод задания. Задания на процессоре: 1 2. |
1 |
0 |
2 |
|
|
64 |
Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 1 2. |
8 |
4 |
2 |
|
|
66 |
Завершён ввод задания 8. Задания на процессоре: 2 8. |
8 |
4 |
2 |
|
|
75 |
Завершён ввод задания 9. Задания на процессоре: 2 8 9 |
8 |
4 |
3 |
|
|
213 |
Завершено задание 8 и его ресурсы освобождены. Из очереди выбирается задание 3: начинается ввод задания. Задания на процессоре: 2 8 9. |
5 |
1 |
3 |
|
|
222 |
Завершено задание 9 и его ресурсы освобождены. Из очереди выбирается задание 4: начинается ввод задания. Задания на процессоре: 2 9. |
4 |
1 |
2 |
|
|
235 |
Завершено задание 2 и его ресурсы освобождены. Из очереди выбирается задание 5: начинается ввод задания. Задания на процессоре: 2. |
1 |
2 |
1 |
|
|
237 |
Завершён ввод задания 4. Задания на процессоре: 4. |
1 |
2 |
1 |
|
|
240 |
Завершён ввод задания 5. Задания на процессоре: 4 5. |
1 |
2 |
2 |
|
|
243 |
Завершён ввод задания 3. Задания на процессоре: 3 4 5. |
1 |
2 |
3 |
|
|
330 |
Завершено задание 5 и его ресурсы освобождены. Задания на процессоре: 3 4 5. |
10 |
3 |
3 |
|
|
344 |
Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 6: начинается ввод задания. Задания на процессоре: 3 4. |
5 |
2 |
2 |
|
|
349 |
Завершено задание 3 и его ресурсы освобождены. Из очереди выбирается задание 7: начинается ввод задания. Задания на процессоре: 3. |
0 |
7 |
1 |
|
|
354 |
Завершён ввод задания 7. Задания на процессоре: 7. |
0 |
7 |
1 |
|
|
364 |
Завершён ввод задания 6. Задания на процессоре: 6 7. |
0 |
7 |
2 |
|
|
404 |
Завершено задание 6 и его ресурсы освобождены. Задания на процессоре: 6 7. |
7 |
11 |
2 |
|
|
405 |
Завершено задание 7 и его ресурсы освобождены. Задания на процессоре: 7. |
16 |
12 |
1 |
Сведём полученные данные в таблицу 3 и рассчитаем средневзвешенное время обращения для каждого задания.
Средневзвешенное время обращения рассчитывается:
, ,
- время поступления задания;
- время завершения задания.
Ниже приведены расчёты взвешенного времени обращения для каждой задачи и средневзвешенного времени обращения для дисциплины FIFO в целом:
Максимальный коэффициент мультипрограммирования равен 3. Такой коэффициент был получен на участках 75 - 213 (Задания 2,8,9) и 243-330 (Задания 3,4,5); Средневзвешенное время обращения ;
Таблица 3. Сводная таблица для алгоритма FIFO
|
Задание |
t поступления i |
t назначения на выполнение i |
t начала счета i |
t завершения i |
Wi |
|
|
1 |
7 |
7 |
11 |
50 |
1.257143 |
|
|
2 |
13 |
13 |
32 |
64 |
1.300000 |
|
|
3 |
13 |
51 |
60 |
235 |
2.787500 |
|
|
4 |
21 |
214 |
243 |
349 |
4.700000 |
|
|
5 |
23 |
223 |
237 |
344 |
5.854545 |
|
|
6 |
30 |
236 |
240 |
330 |
8.600000 |
|
|
7 |
36 |
345 |
364 |
404 |
9.225000 |
|
|
8 |
43 |
350 |
354 |
405 |
10.371429 |
|
|
9 |
52 |
52 |
66 |
213 |
2.492308 |
|
|
10 |
61 |
61 |
75 |
222 |
2.492308 |
Приведём график работы дисциплины обслуживания FIFO:
Рис.1. График исполнения задач на процессоре для ДО FIFO
Дисциплина SJF
Таблица 4. Трассировка планирования по алгоритму SJF
|
время |
событие |
V |
H |
K |
|
|
7 |
Поступило задание 0: начинается ввод задания. Процессор простаивает. |
7 |
11 |
0 |
|
|
11 |
Завершён ввод задания 0. Задания на процессоре: 0. |
7 |
11 |
1 |
|
|
13 |
Поступило задание 1: начинается ввод задания. Поступило задание 2: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
21 |
Поступило задание 3: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
23 |
Поступило задание 4: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
30 |
Поступило задание 5: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0. |
0 |
7 |
1 |
|
|
32 |
Завершён ввод задания 1. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
36 |
Поступило задание 6: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
43 |
Поступило задание 7: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 0 1. |
0 |
7 |
2 |
|
|
50 |
Завершено задание 0 и его ресурсы освобождены. Из очереди выбирается задание 6: начинается ввод задания. Задания на процессоре: 0 1. |
2 |
4 |
2 |
|
|
52 |
Поступило задание 8: начинается ввод задания. Задания на процессоре: 1. |
1 |
1 |
1 |
|
|
61 |
Поступило задание 9: нехватка ресурсов - задание помещено в очередь. Задания на процессоре: 1. |
1 |
1 |
1 |
|
|
62 |
Завершено задание 1 и его ресурсы освобождены. Задания на процессоре: 1. |
8 |
5 |
1 |
|
|
66 |
Завершён ввод задания 8. Задания на процессоре: 8. |
8 |
5 |
1 |
|
|
70 |
Завершён ввод задания 6. Задания на процессоре: 6 8. |
8 |
5 |
2 |
|
|
110 |
Завершено задание 6 и его ресурсы освобождены. Из очереди выбирается задание 5: начинается ввод задания. Задания на процессоре: 6 8. |
6 |
8 |
2 |
|
|
115 |
Завершён ввод задания 5. Задания на процессоре: 5 8. |
6 |
8 |
2 |
|
|
160 |
Завершено задание 8 и его ресурсы освобождены. Задания на процессоре: 5 8. |
7 |
11 |
2 |
|
|
168 |
Завершено задание 5 и его ресурсы освобождены. Из очереди выбирается задание 7: начинается ввод задания. Задания на процессоре: 5. |
7 |
11 |
1 |
|
|
169 |
Из очереди выбирается задание 3: начинается ввод задания. Процессор простаивает. |
3 |
5 |
0 |
|
|
170 |
Из очереди выбирается задание 4: начинается ввод задания. Процессор простаивает. |
1 |
2 |
0 |
|
|
173 |
Завершён ввод задания 7. Задания на процессоре: 7. |
1 |
2 |
1 |
|
|
185 |
Завершён ввод задания 4. Задания на процессоре: 4 7. |
1 |
2 |
2 |
|
|
199 |
Завершён ввод задания 3. Задания на процессоре: 3 4 7. |
1 |
2 |
3 |
|
|
234 |
Завершено задание 7 и его ресурсы освобождены. Из очереди выбирается задание 9: начинается ввод задания. Задания на процессоре: 3 4 7. |
9 |
0 |
3 |
|
|
249 |
Завершён ввод задания 9. Задания на процессоре: 3 4 9. |
9 |
0 |
3 |
|
|
292 |
Завершено задание 4 и его ресурсы освобождены. Из очереди выбирается задание 2: начинается ввод задания. Задания на процессоре: 3 4 9. |
5 |
1 |
3 |
|
|
302 |
Завершён ввод задания 2. Задания на процессоре: 2 3 9. |
5 |
1 |
3 |
|
|
309 |
Завершено задание 3 и его ресурсы освобождены. Задания на процессоре: 2 3 9. |
9 |
7 |
3 |
|
|
368 |
Завершено задание 9 и его ресурсы освобождены. Задания на процессоре: 2 9. |
10 |
10 |
2 |
|
|
407 |
Завершено задание 2 и его ресурсы освобождены. Задания на процессоре: 2. |
16 |
12 |
1 |
Средневзвешенное время обращения рассчитывается:
, ,
- время поступления задания;
- время завершения задания;
Данные расчёты аналогичны расчётам для дисциплины FIFO, поэтому я не вижу смысла их здесь приводить.
Максимальный коэффициент мультипрограммирования K равен 3. Такой коэффициент был получен на участке 199-234 (3, 4,7).
Таблица 5. Сводная таблица для алгоритма SJF
|
Задание |
t поступления i |
t назначения на выполнение i |
t начала счета i |
t завершения i |
Wi |
|
|
1 |
7 |
7 |
11 |
50 |
1.257143 |
|
|
2 |
13 |
13 |
32 |
62 |
1.250000 |
|
|
3 |
13 |
293 |
302 |
407 |
4.937500 |
|
|
4 |
21 |
170 |
199 |
309 |
4.128571 |
|
|
5 |
23 |
171 |
185 |
292 |
4.909091 |
|
|
6 |
30 |
111 |
115 |
168 |
3.971429 |
|
|
7 |
36 |
51 |
70 |
110 |
1.875000 |
|
|
8 |
43 |
169 |
173 |
234 |
5.485714 |
|
|
9 |
52 |
52 |
66 |
160 |
1.676923 |
|
|
10 |
61 |
235 |
249 |
368 |
4.738462 |
Приведём график работы дисциплины обслуживания SJF:
Рис. 2. График исполнения задач на процессоре для ДО SJF
2.3 Выводы
Результаты данной работы показали разницу между дисциплинами обслуживания FIFO и SJF. Сравнивая две трассировки, можно увидеть, что в начале они не отличаются друг от друга. Существенные отличия начинают появляться с момента завершения некоторого задания. Тогда встает необходимость о запуске на выполнения задания, находящегося в очереди. Именно здесь дисциплина обслуживания проявляет свою сущность, что очень наглядно отражается на графиках зависимости распределения ресурсов и коэффициента мультипрограммирования от времени.
Средневзвешенное время обращения зависит от выбора дисциплины обслуживания. Поэтому при проектировании систем очень важное значение имеет выбор дисциплины в зависимости от характера решаемых задач.
3. Диспетчеризация
3.1 Задание
Разработать структуру функционирования диспетчера работ в вычислительной системе, заданной в разделе 1, на интервале Т1, который соответствует максимальному коэффициенту мультипрограммирования. Квант времени, выделяемый каждой работе, выбирается исходя из конкретной ситуации: число работ, параллельно занимающих процессор, интервал Т1, дисциплины обслуживания.
Диспетчер использует метод разделения времени в сочетании с приоритетами. ДО - следующие:
бесприоритетные ДО (БП) - смешанный алгоритм;
приоритетные ДО (П) - относительный приоритет;
Интервал наибольшей протяженности, соответствующий максимальному коэффициенту мультипрограммирования Кmax=3, 75 - 213 (Задания 2,8,9). Задания, развивающиеся на процессоре на этом интервале, перечислены в таблице:
Таблица 6. Задания на процессоре
|
N задания |
v |
h |
приоритет |
||
|
2 |
2 |
3 |
40 |
2 |
|
|
8 |
4 |
6 |
90 |
1 |
|
|
9 |
1 |
3 |
10 |
3 |
Приоритеты заданиям присвоены по принципу увеличения приоритета задачи с увеличением ее трудоемкости. Значение 1 означает наивысший приоритет.
3.2 Бесприоритетная ДО - смешанный алгоритм
На рисунке представлена схема смешанного алгоритма обслуживания
Рис.3. Схема смешанного алгоритма обслуживания
Суть данного алгоритма заключается в том, что каждая заявка проходит в i-ой очереди несколько кругов и только потом переходит в очередь i+1. Этот алгоритм является производным алгоритма с обратной связью и смешанного алгоритма.
Блок-схема алгоритма работы диспетчера представлена на рисунке.
n_replay - параметр диспетчера, задающий количество квантов работы задачи перед ее переходом в следующую очередь.
rep - счетчик, связанный с каждой задачей, индицирующий количество квантов ее исполнения в текущей очереди.
i - номер текущей очереди.
t - текущее значение времени
?t - квант времени, предоставляемый задаче
Рис.4. Блок-схема смешанного алгоритма обслуживания
Рис.5. Результат работы программы диспетчера с относительным приоритетом
3.3 Приоритетная ДО - относительный приоритет
Выполнение приоритетной заявки не прерываются при поступлении более приоритетной. На рисунке 11 представлена схема алгоритма обслуживания (относительный приоритет).
Рис.6. Схема алгоритма обслуживания с относительным приоритетом
Если поступило несколько заявок одного приоритета, то в очереди они обслуживаются по принципу FIFO.
Чем меньше значение приоритета, тем раньше выполняется задача.
Блок-схема алгоритма работы диспетчера представлена на рисунке.
i - номер текущей очереди.
t - текущее значение времени
?t - квант времени, предоставляемый задаче
Рис.7. Блок-схема алгоритма обслуживания с относительным приоритетом
Рис.8. Результат работы программы диспетчера с относительным приоритетом
Заключение
В результате проделанной работы были пополнены знания об общей организации ОС, её внутренней структуре, разновидностях, алгоритмах работы основных составляющих ОС.
Были построены временные диаграммы мультипрограммной работы каждого, из указанных в задании алгоритмов. И проведено сравнение двух случаев по средневзвешенному времени обращения. Оказалось, что для данного набора задач предпочтительнее использовать дисциплину SJF, т.к. в нём преобладают задачи с относительно небольшой трудоёмкостью.
Из работы программы-диспетчера, реализующей дисциплины обслуживания по смешанному алгоритму и с относительным приоритетом видно, что что при использовании дисциплины обслуживания со смешанным алгоритмом каждому заданию по очереди выделяется квант процессорного времени, а при использовании дисциплины обслуживания с относительным приоритетом сначала выполняется задача с самым высоким приоритетом. При этом, если приоритет двух задач совпадает, то им по очереди выделяется по кванту процессорного времени, пока одна из них или они обе не завершатся.
Список литературы
1. Л.А. Коршикова. Операционные системы как системы управления вычислительными ресурсами: Учеб. пособие. - Новосибирск: Изд-во НГТУ, 2001. - 63 с.
2. 1. Коршикова Л.А. "Основы операционных систем": учеб. Пособие / - Новосибирск: изд-во НГТУ, 2008. - 356 с.
3. Многозадачная операционная система. Моделирование функций. Методические указания к лабораторной работе по дисциплине СПО.681 М735 №1538, НГТУ, 1997 г.
Приложение
Листинг программы, используемой в пункте 3:
struct Task // Структура, определяющая задачу
{
int pr; // приоритет
int num; // номер
Task *next; // следующая задача
Task (int num, int pr=-1): pr (pr), num (num), next (NULL) {}
};
class Queue // класс очереди
{
Task *first, *last;
public:
int cnt;
Queue (): first (NULL), last (NULL), cnt (0) {}
Enqueue (int num, int pr=-1) // включение
{
if (! first) first = last = new Task (num, pr);
else
{last->next = new Task (num, pr); last = last->next; }
cnt++;
}
Enqueue (Task *t) // включение
{
if (! first) first = last = t;
else
{last->next = t; last = last->next; }
cnt++;
}
Task* Dequeue () // исключение
{
if (first)
{
Task *t = first;
first = first->next;
cnt--;
return t;
}
}
int Empty () // пусто?
{
return! cnt;
}
};
class Dispather // базовый класс диспетчера
{
protected:
double kvant; // квант CPU, выделяемый задаче
int n_tasks; // количество задач
int sv_kvant; // квант SV
Queue Q [10]; // массив очередей
public:
Dispather (double kvant, int sv_kvant);
virtual Add (int n, int prt) = 0; // длбавить задачу
virtual Do (double t, double T) = 0; // выполнять
};
Dispather:: Dispather (double kvant, int sv_kvant)
: kvant (kvant), n_tasks (0), sv_kvant (sv_kvant)
{
}
class DispatherNoPrt: public Dispather // класс диспетчера со смешанным алгоритмом
{
int n_replay; // количество повторений
public:
DispatherNoPrt (double kvant, int sv_kvant, int n_replay)
: Dispather (kvant, sv_kvant), n_replay (n_replay) {}
Add (int n, int prt=-1);
Do (double t, double T);
};
DispatherNoPrt:: Add (int n, int prt)
{
Q [0]. Enqueue (n); n_tasks++;
}
DispatherNoPrt:: Do (double t, double T)
{
int cur_q = 0;
Task* cur_t;
double tmAbs = t;
for (double tm=t; tm<=T;)
{
for (int rep=0; rep<n_replay; rep++)
{
for (int i=0; i<n_tasks && tm<=T; i++)
{
cur_t = Q [cur_q]. Dequeue ();
cout<<"SV "<<' '<<" Time = "<<tmAbs<<endl;
tmAbs += sv_kvant;
cout<<"Task #"<<cur_t->num<<' '<<"Time = "<<tmAbs<<endl;
if (rep == n_replay-1) Q [cur_q+1]. Enqueue (cur_t);
else Q [cur_q]. Enqueue (cur_t);
tm+=kvant;
tmAbs += kvant;
}
}
cur_q++;
}
}
class DispatherPrt: public Dispather // класс диспетчера с относительным приоритетом
{
public:
DispatherPrt (double kvant, int sv_kvant)
: Dispather (kvant, sv_kvant) {}
Add (int n, int pr);
Do (double t, double T);
};
DispatherPrt:: Add (int n, int pr)
{
Q [pr]. Enqueue (n, pr);
n_tasks++;
}
DispatherPrt:: Do (double t, double T)
{
int cur_q = 0;
Task* cur_t;
double tm=t;
double tmAbs = t;
for (int j=0; j<10; j++)
{
if (! Q [cur_q]. Empty ())
{
for (double tml=0;
tm<=T && tml<= (double) (T-t) / (double) n_tasks* (double) Q [cur_q]. cnt; tml+=kvant)
{
cur_t = Q [cur_q]. Dequeue ();
cout<<"SV "<<' '<<" Time = "<<tmAbs<<endl;
tmAbs += sv_kvant;
cout<<"Task #"<<cur_t->num<<' '<<"Time = "<<tmAbs<<endl;
Q [cur_q]. Enqueue (cur_t);
tm+=kvant;
tmAbs+=kvant;
}
}
cur_q++;
}
}
#include <iostream. h>
#include <conio. h>
#include "disp. h"
void main ()
{
cout<<"1 - FIFO"<<endl;
cout<<"2 - SJF"<<endl;
int c;
cin>>c;
double kv, sv;
cout<<"Enter CPU kvant: ";
cin>>kv;
cout<<"Enter SV kvant: ";
cin>>sv;
Dispather *d;
if (c == 1)
d = new DispatherNoPrt (kv, sv,
2);
if (c == 2)
d = new DispatherPrt (kv, sv);
d->Add (2,2);
d->Add (3,3);
d->Add (4,1);
d->Add (5,4);
d->Add (8,2);
d->Do (0, 42);
cin>>c;
delete d;
}
Размещено на Allbest.ru
Подобные документы
Сведения о планировании заданий. Характеристика алгоритмов FIFO и SJF. Диспетчеризация задач для бесприоритетной ДО FB и с динамическим приоритетом (зависимость от времени обслуживания). Алгоритм функционирования диспетчера и результаты моделирования.
курсовая работа [702,3 K], добавлен 23.09.2013Планирование и диспетчеризация процессора. Гистограмма периодов активности процессора. Примеры экспоненциального усреднения. Диспетчеризация по приоритетам и стратегия Round Robin – "круговая система". Примеры многоуровневой аналитической очереди.
презентация [1,8 M], добавлен 24.01.2014История развития операционных систем семейства Windows и основные понятия системного администрирования. Определение востребованности операционных систем Windows, сравнительная характеристика их функции и возможностей, особенности применения на практике.
курсовая работа [38,5 K], добавлен 08.05.2011Мониторинг эффективности операционных систем. Обеспечение программам возможности осуществлять обмен данными с внешними устройствами. Методы управления памятью в операционных системах. Основные различия между статическим и динамическим связыванием.
практическая работа [3,0 M], добавлен 17.05.2022Основные понятия операционных систем. Синхронизация и критические области. Сигналы и взаимодействие между процессами. Управление памятью. Драйверы устройств. Особенности современных операционных систем. Центральный процессор, микросхемы часов и таймеров.
учебное пособие [1,2 M], добавлен 24.01.2014Основные функции и процессы подсистемы управления процессами. Диспетчеризация процессов (потоков). Алгоритмы планирования выполнения потоков. Назначение и разновидности приоритетов в операционных системах. Функции подсистемы управления основной памятью.
презентация [117,7 K], добавлен 20.12.2013Назначение серверных операционных систем. Сравнительный анализ серверных операционных систем Windows и Linux и сравнение их по важным показателям таким как: пользовательский графический интерфейс, безопасность, стабильность работы, возможность и цена.
курсовая работа [50,1 K], добавлен 03.07.2012Основные понятия об операционных системах. Виды современных операционных систем. История развития операционных систем семейства Windows. Характеристики операционных систем семейства Windows. Новые функциональные возможности операционной системы Windows 7.
курсовая работа [60,1 K], добавлен 18.02.2012Понятие операционных систем, их классификация и разновидности, отличительные признаки и основные свойства. Содержание операционных систем, порядок взаимодействия и назначение их компонентов. Организация дискового пространства. Описание современных ОС.
контрольная работа [42,4 K], добавлен 07.11.2009Изучение современных принципов, подходов и методов моделирования сложно формализуемых объектов. Решение задач структурной и параметрической идентификации. Характеристики вычислительных систем как сложных систем массового обслуживания. Теория потоков.
курс лекций [2,3 M], добавлен 18.02.2012
