ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 04.12.2023
Просмотров: 51
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Сводная таблица
| Задание | t поступления i | t завершения i | Ti | Wi |
| 1 | 6 | 46 | 40 | 1 |
| 2 | 11 | 41 | 30 | 1 |
| 3 | 12 | 122 | 110 | 1 |
| 4 | 12 | 126 | 80 | 1,425 |
| 5 | 15 | 56 | 15 | 2,7333333 |
| 6 | 24 | 89 | 65 | 1 |
| 7 | 28 | 126 | 70 | 1,4 |
| 8 | 33 | 152 | 30 | 3,9666667 |
| 9 | 40 | 161 | 35 | 3,4571429 |
| 10 | 40 | 232 | 80 | 2,4 |
Средневзвешенное время обращения W = 1,9382143.
Временная диаграмма FIFO приведена в приложении 1.
1.3.2. Алгоритм SJF
Трассировка
| | | 16 | 12 |
| время | событие | V | H |
| 6 | поступило задание 1. (7, 4)- начало загрузки (1). Процессор простаивает. | 9 | 8 |
| 11 | поступило задание 2. (5, 0)- загрузка не требуется. | 4 | 8 |
| 12 | поступило задание 3. (3, 4)- начало загрузки (3). Задания на процессоре: 2 | 1 | 4 |
| 12 | поступило задание 4. (6, 2)- нехватка ресурсов, ожидание. | 1 | 4 |
| 15 | поступило задание 5. (4, 1)- нехватка ресурсов, ожидание. | 1 | 4 |
| 24 | поступило задание 6. (1, 3)- начало загрузки (6). | 0 | 1 |
| 26 | завершена загрузка (1). Задания на процессоре: 1, 2 | 0 | 1 |
| 28 | поступило задание 7. (3, 2)- нехватка ресурсов, ожидание. | 0 | 1 |
| 32 | завершена загрузка (3). Задания на процессоре: 1, 2, 3 | 0 | 1 |
| 33 | поступило задание 8. (5, 0)- нехватка ресурсов, ожидание | 0 | 1 |
| 39 | завершена загрузка(6). Задания на процессоре: 1, 2, 3, 6 | 0 | 1 |
| 40 | поступило задание 9. (9, 1)- нехватка ресурсов, ожидание. поступило задание 10. (6, 2)- нехватка ресурсов, ожидание. | 0 | 1 |
| 41 | завершение задания 2. (5, 0)+ освобождение ресурсов. Задания на процессоре: 1, 3, 6 | 5 | 1 |
| 41 | начало загрузки (5). (4, 1)- | 1 | 0 |
| 46 | завершение задания 1. (7, 4)+ освобождение ресурсов. Завершена загрузка (5). Задания на процессоре: 3, 5, 6 | 8 | 4 |
| 46 | начало работы (8). (5, 0)-. Загрузки не требует. Задания на процессоре: 3, 5, 6, 8 | 3 | 4 |
| 46 | начало загрузки (7). (3, 2)- | 0 | 2 |
| 56 | завершение задания 5. (4, 1)+. Задания на процессоре: 3, 6, 8 | 4 | 3 |
| 56 | завершена загрузка 7. задания на процессоре: 3, 6, 7, 8 | 4 | 3 |
| 76 | завершение задания 8. (5, 0)+. Задания на ЦП: 3, 6, 7 | 9 | 3 |
| 76 | начало загрузки (9). (9, 1)- | 0 | 2 |
| 81 | завершена загрузка (9). Задания на ЦП: 3, 6, 7, 9 | 0 | 2 |
| 89 | завершение задания 6. (1, 3)+. Задания на ЦП: 3, 7, 9 | 1 | 5 |
| 106 | завершение задания 7. (3, 2)+. Задания на ЦП: 3, 9 | 4 | 7 |
| 111 | завершение задания 9 (9, 1)+. Задания на ЦП: 3 | 13 | 8 |
| 111 | начало загрузки (4). (6, 2)- | 7 | 6 |
| 111 | начало загрузки (10). (6, 2)- | 1 | 4 |
| 121 | завершена загрузка (4, 10). Задания на ЦП: 3, 4, 10 | 1 | 4 |
| 122 | завершение задания 3. (3, 4)+. Задания на ЦП: 4, 10. | 4 | 8 |
| 192 | завершение задания 4. (6, 2)+, 10. (6, 2)+ | 16 | 12 |
Сводная таблица
| Задание | t поступления i | t завершения i | Ti | Wi |
| 1 | 6 | 46 | 40 | 1 |
| 2 | 11 | 41 | 30 | 1 |
| 3 | 12 | 122 | 110 | 1 |
| 4 | 12 | 192 | 80 | 2,25 |
| 5 | 15 | 56 | 15 | 2,7333333 |
| 6 | 24 | 89 | 65 | 1 |
| 7 | 28 | 106 | 70 | 1,1142857 |
| 8 | 33 | 76 | 30 | 1,4333333 |
| 9 | 40 | 111 | 35 | 2,0285714 |
| 10 | 40 | 193 | 80 | 1,9125 |
Средневзвешенное время обращения W = 1,5472024.
Временная диаграмма SJF приведена в приложении 2.
1.3.3. Выводы
Планирование по принципу SJF «сначала короткие задания» обеспечивает уменьшение среднего времени обращения (1.9 FIFO, 1.5 SJF) и нахождения задач в системе (232 FIFO, 192 SJF), но отдает явное предпочтение коротким заданиям, которые преобладают в заданной последовательности задач, задерживая при этом длинные.
Применение принципа FIFO несколько увеличивает среднюю длительность времени ожидания и общее время нахождения в системе.
Максимальные коэффициенты мультипрограммирования совпадают для обеих дисциплин (Кmax=4).
В данной последовательности задач предпочтительней использовать ДО SJF, т.к. в системе преобладают короткие задачи.
Раздел 2. Диспетчеризация.
2.1. Общие сведения о диспетчеризации
Средний уровень планирования - диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирование повторяется, процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки.
Таким образом, цели диспетчирования задач следующие:
- распределение центрального процессора в динамике в соответствии
с критериями;
- эффективная отработка алгоритмов управления задачами.
- сбалансированное использование ресурсов.
- баланс между временем ответа и коэффициентом использования ресурсов.
Итак: диспетчер - это программа, которая выбирает задачи (процессы) из "очереди на выполнение", переводит их в активное состояние и передает их на обработку центральному процессору.
2.2. Задание и исходные данные
Задание
Разработать структуру функционирования диспетчера работ в вычислительной системе, заданной в разделе 1. Квант времени, выделяемый каждой работе, выбирается исходя из конкретной ситуации: число работ, параллельно занимающих процессор, интервалы времени с коэффициентом многозадачности дисциплины обслуживания.
Диспетчер использует метод разделения времени в сочетании с приоритетами. ДО - следующие:
- бесприоритетные ДО (БП) - смешанный алгоритм;
- приоритетные ДО (П) – относительный приоритет;
2.3. Выполнение работы
2.3.1. Диспетчер задач для бесприоритетной ДО – смешанный алгоритм.
Смешанный алгоритм обслуживания- это совмещение (RR+FB). На рисунке ниже представлена схема алгоритма обслуживания с учетом ДО (RR и FB)
Рис. Схема алгоритма обслуживания с учетом ДО (RR и FB)
Каждая заявка проходит в i-ой очереди несколько кругов и только потом переходит в очередь i+1.
Трассировка смешанного алгоритма.
| № | Время | Квант | Событие |
| 1 | 11-26 | 2.5 | Задача 2 поступает со входа, выполняется, поступает во 2 очередь. |
| 2 | 26-32 | 1.5 | Задача 1 поступает со входа, выполняется, поступает в 2 очередь. Задача 2 поступает со 2 очереди, выполняется, поступает в 3 очередь. |
| 3 | 32-39 | 1.15 | Задача 3 поступает со входа, выполняется, поступает во 2 очередь. Задача 1 поступает со 2 очереди, выполняется, поступает в 3 очередь. Задача 2 поступает с 3 очереди, выполняется, поступает в 3 очередь. |
| 4 | 39-41 | 0.25 | Задача 6 поступает со входа, выполняется, поступает во 2 очередь. Задача 3 поступает со 2 очереди, выполняется, поступает в 3 очередь. Задача 1 поступает с 3 очереди, выполняется, поступает в 3 очередь. Задача 2 поступает с 3 очереди, выполняется, завершается. |
| 5 | 41-46 | 0.85 | Задача 6 поступает со 2 очереди, выполняется, поступает в 3 очередь. Задача 3 поступает с 3 очереди, выполняется, поступает в 3 очередь. Задача 1 поступает с 3 очереди, выполняется, завершается. |
| 6 | 46-56 | 1.65 | Задача 5 поступает со входа, выполняется, завершается. Задача 6 поступает с 3 очереди, выполняется, поступает в 3 очередь. Задача 3 поступает с 3 очереди, выполняется, поступает в 3 очередь. |
| 7 | 56-66 | 1.65 | Задача 4 поступает со входа, выполняется, поступает во 2 очередь. Задача 6 поступает с 3 очереди, выполняется, поступает в 3 очередь. Задача 3 поступает с 3 очереди, выполняется, поступает в 3 очередь. |
| 8 | 66-89 | 2.85 | Задача 7 поступает со входа, выполняется, поступает во 2 очередь. Задача 4 поступает со 2 очереди, выполняется, поступает в 3 очередь. Задача 6 поступает с 3 очереди, выполняется, завершается. Задача 3 поступает с 3 очереди, выполняется, поступает в 3 очередь. |
| 9 | 89-122 | 5.5 | Задача 7 поступает со 2 очереди, выполняется, поступает в 3 очередь. Задача 4 поступает с 3 очереди, выполняется, поступает в 3 очередь. Задача 3 поступает с 3 очереди, выполняется, завершается. |
| 10 | 122-126 | 0.65 | Задача 8 поступает со входа, выполняется, поступает во 2 очередь. Задача 7 поступает с 3 очереди, выполняется, завершается. Задача 4 поступает с 3 очереди, выполняется, завершается. |
| 11 | 126-131 | 2.5 | Задача 8 поступает со 2 очереди, выполняется, поступает в 3 очередь. |
| 12 | 131-152 | 5.25 | Задача 9 поступает со входа, выполняется, поступает во 2 очередь. Задача 8 поступает с 3 очереди, выполняется, завершается. |
| 13 | 152-161 | 4.5 | Задача 9 поступает с 3 очереди, выполняется, завершается. |
| 14 | 162-232 | 35 | Задача 10 поступает со входа, выполняется, завершается. |
Диаграмма смешанного алгоритма обслуживания представлена в приложении 3.
2.3.2. Приоритетная ДО – относительный приоритет
В соответствие с данной дисциплиной обслуживания, при поступлении более приоритетной задачи в вычислительную систему, прерывания не происходит, заявка выполняется до конца, а после включается более приоритетная. Если имеются несколько заявок с одинаковым приоритетом, то они помещаются в очередь по принципу FIFO и затем возвращаются из очереди.
Приоритет фиксированный. Схема обслуживания включает N уровней очередей (соответствующих N уровням приоритетов)
На рисунке ниже представлена схема алгоритма ДО (относительный приоритет)
Трассировка относительного приоритета.
| № | Время | Квант | Событие |
| 1 | 11-15 | 4 | Поступает задача 2. |
| 2 | 15-24 | 9 | Выполняется задача 2. |
| 3 | 24-26 | 2 | Выполняется задача 2. |
| 4 | 26-32 | 3 | Выполняется задача 2. Поступает задача 1, ее приоритет меньше, задача 2 не прерывается. |
| 5 | 32-39 | 2.35 | Выполняются задачи 2, 1. Поступает задача 3, ее приоритет больше, задача 2 не прерывается. |
| 6 | 39-41 | 0.5 | Поступает задача 6, ее приоритет больше, задача 2 не прерывается. Выполняются задачи 2, 3, 1. Завершается задача 2. |
| 7 | 41-46 | 1.65 | Выполняются задачи 3, 6, 1. Завершается задача 1. |
| 8 | 46-50 | 1.35 | Поступает задача 5, ее приоритет меньше, задача 3 не прерывается. Выполняются задачи 3, 6. |
| 9 | 50-56 | 2 | Выполняются задачи 3, 6, 5. Завершается задача 5. |
| 10 | 56-66 | 3.35 | Поступает задача 4, ее приоритет меньше, задача 3 не прерывается. Выполняются задачи 3, 6. |
| 11 | 66-89 | 5.75 | Поступает задача 7, ее приоритет меньше, задача 3 не прерывается. Выполняются задачи 3, 4, 6. Завершается задача 6. |
| 12 | 89-122 | 11 | Выполняются задачи 3, 4, 7. Завершается задача 3. |
| 13 | 122-126 | 1.35 | Поступает задача 8, ее приоритет меньше, задача 4 не прерывается. Выполняются задачи 4, 7. Завершается задача 4 и 7. |
| 14 | 126-131 | 5 | Выполняется задача 8. |
| 15 | 131-152 | 10.5 | Поступает задача 9, ее приоритет такой же, задача 8 не прерывается. Завершается задача 8. |
| 16 | 152-161 | 9 | Завершается задача 9. |
| 17 | 162-182 | 20 | Поступает задача 10. |
| 18 | 182-202 | 20 | Выполняется задача 10. |
| 19 | 202-232 | 30 | Завершается задача 10. |