Планирование и диспетчеризация процессов в операционных системах

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Оглавление

  • Цели работы
  • Раздел 1. Планирование верхнего уровня управления заданиями
    • 1.1 Общие сведения о планировании заданий
    • 1. 2 Задание и исходные данные
    • 1. 3 Выполнение работы
      • 1.3. 1 Алгоритм FIFO
      • 1.3.2 Алгоритм SJF
    • 1. 4 Графики
    • Выводы
  • Раздел 2. Диспетчеризация
    • 2.1 Общие сведения о диспетчеризации
    • 2.2 Задание
    • 2.3 Исходные условия
    • 2.4 Диспетчеризация задач для бесприоритетной ДО FB
    • 2.5 Диспетчеризация задач для ДО с динамическим приоритетом (зависимость от времени обслуживания)
    • 2.6 Алгоритм функционирования диспетчера
    • 2.7 Описание программы
    • 2.8 Результаты моделирования. Временные диаграммы
  • Список литературы
  • Приложение 1. Программная реализация диспетчера
  • Цели работы
  • 1. Изучение основных понятий планирования и диспетчеризации заданий.
  • 2. Изучение и исследование различных дисциплин обслуживания.

Задачи работы:

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

2. Провести сравнительный анализ двух ДО.

3. Разработать структуру функционирования диспетчера работ в вычислительной системе.

Инструментарий:

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

Раздел 1. Планирование верхнего уровня управления заданиями

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

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

Современные ОС имеют целое множество функций:

Основные функции:

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

· Загрузка программ в оперативную память и их выполнение.

· Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода).

· Управление оперативной памятью (распределение между процессами, организация виртуальной памяти).

· Управление доступом к данным на энергонезависимых носителях (таких как жёсткий диск, оптические диски и др.), организованным в той или иной файловой системе.

· Обеспечение пользовательского интерфейса.

· Сохранение информации об ошибках системы.

Дополнительные функции:

· Параллельное или псевдопараллельное выполнение задач (многозадачность).

· Эффективное распределение ресурсов вычислительной системы между процессами.

· Разграничение доступа различных процессов к ресурсам.

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

· Взаимодействие между процессами: обмен данными, взаимная синхронизация.

· Защита самой системы, а также пользовательских данных и программ от действий пользователей (злонамеренных или по незнанию) или приложений.

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

Центральная часть ОС — ядро, управляющее выполнением процессов, ресурсами вычислительной системы и предоставляющая процессам координированный доступ к этим ресурсам. Любая операционная система позволяет обрабатывать поступающую информацию в мультипрограммном режиме, т. е. в систему может поступить несколько заданий и если она обладает достаточными ресурсами памяти, то эти задания могут быть выполнены либо все одновременно, либо в какой-то последовательности. Примитивные многозадачные среды обеспечивают чистое «разделение ресурсов», когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени. Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. В последних ресурсы распределяет служба управления, которая содержит 2 составляющие: планировщик заданий и планировщик задач. Планировщик заданий выбирает, какие задания и в какой последовательности должны поступать на обработку. Он должен обеспечивать определённую дисциплину выбора заданий на обработку. Для принятия такого решения могут учитываться такие характеристики заданий, как приоритет, необходимые ресурсы и т. п. Планировщик заданий не только выделяет необходимые ресурсы для поступающего на обработку задания, но и освобождает ресурсы после выполнения задания. Также планировщик задач занимается распределением ресурсов процессора между процессами. Он должен решить, какому из созданных процессов предоставить процессор, в какой момент и на сколько, во временном отношении.

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

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

Бес приоритетные ДО:

1. FIFO — «первым пришел — первым выбран на обслуживание».

Время обслуживания заявки равно ее трудоемкости.

2. LIFO — «последним пришел — первым выбран на обслуживание».

Время обработки самой последней задачи аналогично FIFO.

3. RAND — случайный выбор заявки из очереди.

4. RR — «круговорот». Отличается от FIFO лишь временем обслуживания: каждая заявка получает определенный квант времени (одинаковый для всех).

Приоритетные ДО:

1. PRT — выбор заявок на обслуживание по приоритету. Более приоритетной заявке соответствует меньшее число.

2. SJF — выбор заявки на обслуживание с минимальной трудоемкостью.

3. Дисциплины обслуживания со сложными динамическими приоритетами.

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

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

t = tЗ — tП, где

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

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

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

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

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

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

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

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

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

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

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

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

1.2 Задание и исходные данные

Задание.

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

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

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

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

,

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

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

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

Таблица 1. Последовательность заданий и их параметры

n

X

K

v

h

T

t поступления

0

390

5

5

0

30

5

1

147

1

3

4

90

6

2

446

3

4

1

10

9

3

539

7

9

1

30

16

4

190

7

9

1

30

23

5

747

6

7

4

20

29

6

646

2

2

3

40

31

7

939

4

3

2

60

35

8

990

1

3

4

90

36

9

347

9

1

3

50

45

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

1.3 Выполнение работы

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

1.3.1 Алгоритм FIFO

Таблица 2. Трассировка планирования по алгоритму FIFO

Время

Событие

V, H, K

Время: 5

Поступило задание 0: ввод задания не нужен.

Задания на процессоре: 0.

V=11, H=12, K=1.

Время: 6

Поступило задание 1: начинается ввод задания.

Задания на процессоре: 0.

V=8, H=8, K=1.

Время: 9

Поступило задание 2: начинается ввод задания.

Задания на процессоре: 0.

V=4, H=7, K=1.

Время: 13

Завершён ввод задания 2. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 16

Поступило задание 3: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 23

Поступило задание 4: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 25

Завершён ввод задания 1. Задания на процессоре: 0 1 2.

V=4, H=7, K=3.

Время: 29

Поступило задание 5: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=4, H=7, K=3.

Время: 31

Поступило задание 6: начинается ввод задания.

Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 35

Поступило задание 7: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 36

Поступило задание 8: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 39

Завершено задание 2 и его ресурсы освобождены.

Задания на процессоре: 0 1 2.

V=6, H=5, K=3.

Время: 45

Завершён ввод задания 6. Поступило задание 9:

начинается ввод задания. Задания на процессоре: 0 1 6.

V=5, H=2, K=3.

Время: 59

Завершён ввод задания 9. Задания на процессоре: 0 1 6 9.

V=5, H=2, K=4.

Время: 75

Завершено задание 0 и его ресурсы освобождены.

Из очереди выбирается задание 3: начинается ввод задания.

Задания на процессоре: 0 1 6 9.

V=1, H=1, K=4.

Время: 80

Завершён ввод задания 3. Задания на процессоре: 1 3 6 9.

V=1, H=1, K=4.

Время: 200

Завершено задание 3 и его ресурсы освобождены.

Из очереди выбирается задание 4: начинается ввод задания.

Задания на процессоре: 1 3 6 9.

V=1, H=1, K=4.

Время: 201

Завершено задание 6 и его ресурсы освобождены.

Задания на процессоре: 1 6 9.

V=3, H=4, K=3.

Время: 205

Завершён ввод задания 4. Задания на процессоре: 1 4 9.

V=3, H=4, K=3.

Время: 246

Завершено задание 9 и его ресурсы освобождены.

Задания на процессоре: 1 4 9.

V=4, H=7, K=3.

Время: 280

Завершено задание 4 и его ресурсы освобождены.

Из очереди выбирается задание 5: начинается ввод задания.

Задания на процессоре: 1 4.

V=6, H=4, K=2.

Время: 281

Из очереди выбирается задание 7: начинается ввод задания.

Задания на процессоре: 1.

V=3, H=2, K=1.

Время: 291

Завершено задание 1 и его ресурсы освобождены.

Завершён ввод задания 7.

Из очереди выбирается задание 8: начинается ввод задания.

Задания на процессоре: 1 7.

V=3, H=2, K=2.

Время: 300

Завершён ввод задания 5. Задания на процессоре: 5 7.

V=3, H=2, K=2.

Время: 311

Завершён ввод задания 8. Задания на процессоре: 5 7 8.

V=3, H=2, K=3.

Время: 355

Завершено задание 5 и его ресурсы освобождены.

Задания на процессоре: 5 7 8.

V=10, H=6, K=3.

Время: 420

Завершено задание 7 и его ресурсы освобождены.

Задания на процессоре: 7 8.

V=13, H=8, K=2.

Время: 464

Завершено задание 8 и его ресурсы освобождены.

Задания на процессоре: 8.

V=16, H=12, K=1.

Таблица 3. Сводная таблица для алгоритма FIFO

Задание

t поступления

t назначения на выполнение

t начала счета

t завершения

W

0

5

5

5

75

2. 366 667

1

6

6

25

291

2. 600 000

2

9

9

13

39

2. 66 667

3

16

76

80

200

5. 285 714

4

23

201

205

280

7. 371 429

5

29

281

300

355

8. 175 000

6

31

31

45

201

3. 109 091

7

35

282

291

420

5. 514 286

8

36

292

311

464

3. 900 000

9

45

45

59

246

3. 107 692

Средневзвешенное время обращения W = 4. 349 655

Максимальный коэффициент мультипрограммирования = 4

1.3.2 Алгоритм SJF

Таблица 4. Трассировка планирования по алгоритму SJF

Время

Событие

V, H, K

Время: 5

Поступило задание 0: ввод задания не нужен.

Задания на процессоре: 0.

V=11, H=12, K=1.

Время: 6

Поступило задание 1: начинается ввод задания.

Задания на процессоре: 0.

V=8, H=8, K=1.

Время: 9

Поступило задание 2: начинается ввод задания.

Задания на процессоре: 0.

V=4, H=7, K=1.

Время: 13

Завершён ввод задания 2. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 16

Поступило задание 3: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 23

Поступило задание 4: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 2.

V=4, H=7, K=2.

Время: 25

Завершён ввод задания 1. Задания на процессоре: 0 1 2.

V=4, H=7, K=3.

Время: 29

Поступило задание 5: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=4, H=7, K=3.

Время: 31

Поступило задание 6: начинается ввод задания.

Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 35

Поступило задание 7: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 36

Поступило задание 8: нехватка ресурсов — задание

помещено в очередь. Задания на процессоре: 0 1 2.

V=2, H=4, K=3.

Время: 39

Завершено задание 2 и его ресурсы освобождены.

Задания на процессоре: 0 1 2.

V=6, H=5, K=3.

Время: 45

Завершён ввод задания 6. Поступило задание 9:

начинается ввод задания. Задания на процессоре: 0 1 6.

V=5, H=2, K=3.

Время: 59

Завершён ввод задания 9. Задания на процессоре: 0 1 6 9.

V=5, H=2, K=4.

Время: 75

Завершено задание 0 и его ресурсы освобождены.

Задания на процессоре: 0 1 6 9.

V=10, H=2, K=4.

Время: 170

Завершено задание 6 и его ресурсы освобождены.

Из очереди выбирается задание 5: начинается ввод задания.

Задания на процессоре: 1 6 9.

V=5, H=1, K=3.

Время: 190

Завершён ввод задания 5. Задания на процессоре: 1 5 9.

V=5, H=1, K=3.

Время: 207

Завершено задание 9 и его ресурсы освобождены.

Задания на процессоре: 1 5 9.

V=6, H=4, K=3.

Время: 237

Завершено задание 5 и его ресурсы освобождены.

Из очереди выбирается задание 3: начинается ввод задания.

Задания на процессоре: 1 5.

V=4, H=7, K=2.

Время: 242

Завершён ввод задания 3. Задания на процессоре: 1 3.

V=4, H=7, K=2.

Время: 258

Завершено задание 1 и его ресурсы освобождены.

Задания на процессоре: 1 3.

V=7, H=11, K=2.

Время: 281

Завершено задание 3 и его ресурсы освобождены.

Из очереди выбирается задание 4: начинается ввод задания.

Задания на процессоре: 3.

V=7, H=11, K=1.

Время: 282

Из очереди выбирается задание 7: начинается ввод задания.

Процессор простаивает.

V=4, H=9, K=0.

Время: 283

Из очереди выбирается задание 8: начинается ввод задания.

Процессор простаивает.

V=1, H=5, K=0.

Время: 286

Завершён ввод задания 4. Задания на процессоре: 4.

V=1, H=5, K=1.

Время: 292

Завершён ввод задания 7. Задания на процессоре: 4 7.

V=1, H=5, K=2.

Время: 303

Завершён ввод задания 8. Задания на процессоре: 4 7 8.

V=1, H=5, K=3.

Время: 359

Завершено задание 4 и его ресурсы освобождены.

Задания на процессоре: 4 7 8.

V=10, H=6, K=3.

Время: 432

Завершено задание 7 и его ресурсы освобождены.

Задания на процессоре: 7 8.

V=13, H=8, K=2.

Время: 468

Завершено задание 8 и его ресурсы освобождены.

Задания на процессоре: 8.

V=16, H=12, K=1.

Таблица 5. Сводная таблица для алгоритма SJF

Задание

t поступления

t назначения на выполнение

t начала счета

t завершения

W

0

5

5

5

75

2. 366 667

1

6

6

25

258

2. 300 000

2

9

9

13

39

2. 66 667

3

16

238

242

281

7. 600 000

4

23

282

286

359

9. 628 571

5

29

171

190

237

5. 225 000

6

31

31

45

170

2. 545 455

7

35

283

292

432

5. 685 714

8

36

284

303

468

3. 936 364

9

45

45

59

207

2. 507 692

Средневзвешенное время обращения W= 4. 386 213

Максимальный коэффициент мультипрограммирования равен 4

1.4 Графики

Графики выполнения заданий на процессоре:

Рис. 2. График исполнения задач на процессоре для ДО FIFO

Рис. 3. График исполнения задач на процессоре для ДО SJF

Выводы

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

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

Раздел 2. Диспетчеризация

2.1 Общие сведения о диспетчеризации

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

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

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

с критериями;

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

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

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

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

2.2 Задание

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

Диспетчер использует метод разделения времени в сочетании с приоритетами. ДО — следующие:

— бес приоритетные ДО (БП) — FB- обратная связь;

— приоритетные ДО (П) — обслуживание с динамическим приоритетом (зависимость от времени обслуживания — tобсл).

Матрица работ из раздела 1 (правило FIFO):

Таблица № 4 Исходные данные

N

T

tp

Pr

0

30

5

3

1

20

30

8

2

40

27

11

3

40

29

5

4

70

107

7

5

50

113

5

6

70

174

9

7

50

183

10

8

90

327

19

9

30

379

13

2.3 Исходные условия

Вариант выбирается согласно последним двум цифрам зачетной книжки (09).

Соответственно варианту выбираются дисциплины обслуживания, то есть:

бес приоритетная: FB - Feed Back (обратная связь) — многоуровневый циклический алгоритм

приоритетная: ДО динамическим приоритетом (зависимость от времени обслуживания — tобсл. . );

планирование алгоритм диспетчеризация моделирование

2.4 Диспетчеризация задач для бесприоритетной ДО FB

На рисунке 4 представлена схема циклической ДО (FB)

Рис. 4. Схема циклической ДО (FB)

n=1 — это первая очередь, в нее поступает входной поток заявок. Из нее заявка поступает на ресурс и/или полностью обслуживается или снова поступает в очередь, но с номером на 1 больше. Поток заявок поступает в самую приоритетную очередь n=1. Заявка получает квант и переходит в очередь n+1. Заявка в i-ой очереди обслуживается, если пусты все остальные очереди. В очереди N заявки обслуживаются до завершения (в очереди N принцип FIFO + RR).

/

Рис. 5. Алгоритм Д О FB.

2.5 Диспетчеризация задач для ДО с динамическим приоритетом (зависимость от времени обслуживания)

Приоритет изменяется в период выполнения задания (tобсл.). На рисунке представлена временная диаграмма изменения приоритета от времени.

Рис. 6. Временная диаграмма изменения приоритета от времени.

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

Pi(t) = ai*tожид. + bi*tвыполн. , где Pi(t) — приоритет i- ой работы.

Смена выполняющегося задания происходит в следующих случаях:

1. процесс завершен или произошла ошибка;

2. процесс перешел в состояние ожидания;

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

4. в очереди появился процесс с большим приоритетом

Достоинства системы с динамическим приоритетом:

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

· дисциплина основана на реальных динамических характеристиках заявок.

· Учитывает приоритетность задач

· Уменьшает возможность недобросовестного использования механизмов приоритетов

Недостатки:

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

· Сложная организация, так как необходим пересчет приоритетов

/

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

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

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

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

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

2.7 Описание программы

Программа Disp позволяет произвести моделирование c помощью одного из двух алгоритмов: FB или обслуживание с динамическим приоритетом (зависимость от времени обслуживания tобсл).

Запуск программы осуществляется по команде Disp. exe Внешний вид программы представлен на рисунке 9.

В меню программы можно задать параметры моделирования.

SV — время работы супервизора;

PROC — продолжительность кванта времени в течении которого обрабатывается задание;

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

Так же предусмотрена кнопка Clear — очистить, для того чтобы можно было несколько раз выводить временные диаграммы разных алгоритмов.

Рис. 9. Внешний вид программы

2.8 Результаты моделирования. Временные диаграммы

Рис. 10. Временная диаграмма результатов моделирования алгоритма FB

Рис. 11. Временная диаграмма результатов моделирования алгоритма с динамическим приоритетом

Заключение

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

Были построены временные диаграммы мультипрограммной работы каждого, из указанных в задании алгоритмов. И проведено сравнение двух случаев по средневзвешенному времени обращения. По результатам построения временных диаграмм ДО SJF (средневзвешенное время 4. 04единиц) оказалась немного более эффективной, чем ДО FIFO (4. 70единиц).

Была составлена учебная программа-симулятор наглядно демонстрирующая работу диспетчера с помощью временных диаграмм. Программа-симулятор диспетчера позволяет рассмотреть работу таких ДО как LIFO и обслуживание с динамическим приоритетом (от tобсл). Подробная трассировка алгоритмов в текстовом формате, подкреплена наглядными временными диаграммами.

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

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

1. Л. А. Коршикова. Операционные системы как системы управления вычислительными ресурсами: Учеб. пособие. — Новосибирск.: НГТУ, 2007. — 52с.: ил.

2. Э. Таненбаум. Современные операционные системы. 2-е изд. — СПб.: Питер, 2007. — 1038 с.: ил.

Приложение 1. Программная реализация диспетчера

void CKR_OSDlg: :FB ()

{

//собственно сам алгоритм

int countT=0; //счетчик в списке aMCPU

int cTr=0;

int tT=0;

int tPT=0;

int c=0;

int nIndex=0;

char s1[10];

char s2[10]=": «;

CString st;

//oDop. SV=atoi (m_SV);

//oDop. PROC=atoi (m_PROC);

CFile OutFile2(«trace1. txt», CFile: modeCreate | CFile: :modeWrite);

char s[80];

int len=0;

bool x=true;

while (true)

{

oDop. SortTaskTime (oDop. cTask);

c=1;

tT=oDop. T-cTr;//от чего

oDop. T+=oDop. SV;//до чего

if (oDop. T==115)

{

countT++;

countT--;

}

st. Format («%d: Супервизор старт «, tT+cTr); //oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

for (int n=1; n<oDop. cTask;n++) // проверяем на конец моделирования

if (oDop. aTask[n]. b) c++;

if (c==oDop. cTask)

{

st. Format («%d: Супервизор финиш «, oDop. T);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

st. Format («Конец моделирования»);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

cc++;

return;

}

countT=1;

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T)

{

oDop. tTask[i]=oDop. aTask[i];

if (oDop. aTask[i]. Time>=tT+cTr & & !oDop. aTask[i]. b)

{

oDop. aTask[i]. Queue=1; //очередь

oDop. tTask[i]. Queue=1;

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

}

countT++;

};

st. Format («%d: Супервизор финиш «, oDop. T);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

oDop. SortQueue (countT-1);//? сортитуем список по приоритетам

while (true) // выбираем из списка ту, которая получит свой квант

{

if (countT==1) break;

if (!oDop. tTask[countT-1]. b)

{

if (oDop. tTask[countT-1]. Trud<=oDop. PROC) //если осталось у задачи трудоемкость меньше,//чем 5 квантов

{

cTr=oDop. tTask[countT-1]. Trud; //то продвигаем время на труд этой задачи

nIndex=oDop. Index (countT-1);

oDop. aTask[nIndex]. Trud=0;

oDop. aTask[nIndex]. b=true;

for (int j=1,in=0; j<countT-1;j++)

{

in=oDop. Index (j);

if (!oDop. aTask[in]. b)

{

//oDop. aTask[in]. Function (cTr);

}

}

st. Format («%d: %d задача начала выполнение «, oDop. T, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T+cTr)

{

if (oDop. aTask[i]. Time>=oDop.T & & !oDop. aTask[i]. b)

{

oDop. aTask[i]. Queue=1; //очередь

//oDop. tTask[i]. Queue=1;

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

}

}

st. Format («%d: у задачи %d закончился квант времени «, oDop. T+cTr, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

st. Format («задача %d выполнена «, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

GetStrPrior (oDop. cTask);

break;

}

else

{

cTr=oDop. PROC;//иначеипродвигаем время на 5 квантов

nIndex=oDop. Index (countT-1);

oDop. aTask[nIndex]. Trud-=oDop. PROC;// обнуляем трудоемкость

oDop. aTask[nIndex]. Prior--;

oDop. aTask[nIndex]. Queue++; //очередь

for (int j=1,in=0; j<countT-1;j++)

{

in=oDop. Index (j);

if (!oDop. aTask[in]. b)

{

//oDop. aTask[in]. Function (cTr);

}

}

st. Format («%d: %d задача начала выполнение «, oDop. T, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T+cTr)

{

if (oDop. aTask[i]. Time>=oDop.T & & !oDop. aTask[i]. b)

{

oDop. aTask[i]. Queue=1; //очередь

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

}

}

st. Format («%d: у задачи %d закончился квант времени «, oDop. T+cTr, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceF. InsertString (-1,st);

GetStrPrior (oDop. cTask);

break;

}

}

else countT--; //следущая в списке

}

oDop. T+=cTr; //продвигаем модельное время

}

}

void CKR_OSDlg: :Dinam ()

{

//собственно сам алгоритм с динамическим приоритетом

int countT=0; //счетчик в списке aMCPU

int cTr=0;

int tT=0;

int tPT=0;

int c=0;

int nIndex=0;

char s1[10];

char s2[10]=": «;

CString st;

//oDop. SV=atoi (m_SV);

//oDop. PROC=atoi (m_PROC);

CFile OutFile2(«trace1. txt», CFile: modeCreate | CFile: :modeWrite);

char s[80];

int len=0;

bool x=true;

while (true)

{

oDop. SortTaskTime (oDop. cTask);

c=1;

tT=oDop. T-cTr;//от чего

oDop. T+=oDop. SV;//до чего

if (oDop. T==145)

{

countT++;

countT--;

}

st. Format («%d: Супервизор старт «, tT+cTr); //oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

for (int n=1; n<oDop. cTask;n++) // проверяем на конец моделирования

if (oDop. aTask[n]. b) c++;

if (c==oDop. cTask)

{

st. Format («%d: Супервизор финиш «, oDop. T);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

st. Format («Конец моделирования»);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

cc++;

return;

}

countT=1;

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T)

{

oDop. tTask[i]=oDop. aTask[i];

if (oDop. aTask[i]. Time>=tT+cTr & & !oDop. aTask[i]. b)

{

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

}

countT++;

};

st. Format («%d: Супервизор финиш «, oDop. T);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

oDop. SortPrior (countT-1);//? сортитуем список по приоритетам

while (true) // выбираем из списка ту, которая получит свой квант

{

if (countT==1) break;

if (!oDop. tTask[countT-1]. b)

{

if (oDop. tTask[countT-1]. Trud<=oDop. PROC) //если осталось у задачи трудоемкость меньше,//чем 5 квантов

{

cTr=oDop. tTask[countT-1]. Trud; //то продвигаем время на труд этой задачи

nIndex=oDop. Index (countT-1);

oDop. aTask[nIndex]. Trud=0;

oDop. aTask[nIndex]. b=true;

for (int j=1,in=0; j<countT-1;j++)

{

in=oDop. Index (j);

if (!oDop. aTask[in]. b)

{

//oDop. aTask[in]. Function (cTr);

}

}

st. Format («%d: %d задача начала выполнение «, oDop. T, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T+cTr)

{

if (oDop. aTask[i]. Time>=oDop.T & & !oDop. aTask[i]. b)

{

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

}

}

st. Format («%d: у задачи %d закончился квант времени «, oDop. T+cTr, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

st. Format («задача %d выполнена «, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

GetStrPrior (oDop. cTask);

break;

}

else

{

cTr=oDop. PROC;//иначеипродвигаем время на 5 квантов

nIndex=oDop. Index (countT-1);

oDop. aTask[nIndex]. Trud-=oDop. PROC;// обнуляем трудоемкость

oDop. aTask[nIndex]. Prior--;

for (int j=1,in=0; j<countT-1;j++)

{

in=oDop. Index (j);

if (!oDop. aTask[in]. b)

{

//oDop. aTask[in]. Function (cTr);

}

}

st. Format («%d: %d задача начала выполнение «, oDop. T, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

for (int i=1; i<oDop. cTask;i++)//формируем список только что поступивших задач

if (oDop. aTask[i]. Time<oDop. T+cTr)

{

if (oDop. aTask[i]. Time>=oDop.T & & !oDop. aTask[i]. b)

{

st. Format («%d: %d задача поступила «, oDop. aTask[i]. Time, oDop. aTask[i]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

}

}

st. Format («%d: у задачи %d закончился квант времени «, oDop. T+cTr, oDop. aTask[nIndex]. Name);

OutFile2. Write (st, st. GetLength ());

OutFile2. Write («n», 1);

m_TraceD. InsertString (-1,st);

GetStrPrior (oDop. cTask);

break;

}

}

else countT--; //следущая в списке

}

oDop. T+=cTr; //продвигаем модельное время

}

}

ПоказатьСвернуть
Заполнить форму текущей работой