Каким должен быть алгоритм планирования?
Пусть есть последовательность процессов <p_0, p_1, ..., p_n>. Тогда перед алгоритмом планирования стоит задача найти такую перестановку процессов, чтобы критерий K был наилучшим
Поэтому нужно ввести параметры, которые характеризуют процесс и которые будут использоваться в вычислении критерия. Параметры можно разделить на 4 группы:
А для самого процесса можно выделить 2 значения:
CPU burst - время, в ходе которого процесс непрерывно использовал ресурсы процессора
I/O burst - время, которое процесс ожидает операции ввода/вывода
Реальные значения CPU burst и I/O burst мы не знаем, мы можем только оценить их
Алгоритмы планирования делиться на два типа:
Невытесняющие - даем процессу работать столько, сколько его CPU-burst
Вытесняющие - алгоритм, передающие управление другим процессам, не давая им закончить
Разберем некоторые из них:
Первым пришел - первым обслужен (First-Come First-Served, FCFS)
В этом подходе мы обрабатываем процессы в порядке их поступления
Пусть есть три процесса. Обозначим за 🔄 - процесс исполняется, 💤 - процесс ожидает, ✅ - процесс выполнился.
Тогда будет уделять процессорное время первому появившемуся процессу
| Процесс | CPU burst | |
|---|---|---|
| p_0 | 13 | 🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄✅ |
| p_1 | 4 | 💤💤💤💤💤💤💤💤💤💤💤💤💤🔄🔄🔄🔄✅ |
| p_2 | 1 | 💤💤💤💤💤💤💤💤💤💤💤💤💤💤💤💤💤🔄✅ |
Суммарное время выполнения - T = 18 тактов.
Среднее полное время выполнения tau_полн = (13 + 17 + 18) / 3 = 16.
Среднее время ожидания tau_ожид = (0 + 13 + 17) / 3 = 10
Теперь сделаем нашу очередь в другую сторону:
| Процесс | CPU burst | |
|---|---|---|
| p_2 | 1 | 🔄✅ |
| p_1 | 4 | 💤🔄🔄🔄🔄✅ |
| p_0 | 13 | 💤💤💤💤💤🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄🔄✅ |
Здесь среднее полное время выполнения tau_полн = (18 + 5 + 1) / 3 = 8, а ожидания - tau_ожид = (5 + 1 + 0) / 3 = 2
Как можно заметить, среднее время выполнения и время ожидания - сократилось. В этом и недостаток метода: эффективность зависит от перестановки процессов в очереди
Циклический (Round Robin, RR)
В этом алгоритме мы устанавливаем временной отрезок (так называемый квант времени), например, k = 4. Процессы образуют собой кольцевую очередь. Round Robin дает каждому процессу исполнится этот временной отрезок, а дальше исполнение переходит к следующему в очереди
| Процесс | CPU burst | |
|---|---|---|
| p_0 | 13 | 🔄🔄🔄🔄💤💤💤💤💤🔄🔄🔄🔄🔄🔄🔄🔄🔄✅ |
| p_1 | 4 | 💤💤💤💤🔄🔄🔄🔄✅ |
| p_2 | 1 | 💤💤💤💤💤💤💤💤🔄✅ |
Среднее полное время tau_полн = (18 + 8 + 9) / 3 = 11.7, ожидания - tau_ожид = (5 + 4 + 8) / 3 = 5.7
Если развернуть очередь, то среднее полное время и время ожидания не улучшиться по сравнению с тем, что было в FCFS, но при этом время в худшей перестановке процессов значительно улучшилась
Теперь пусть k = 1:
| Процесс | CPU burst | |
|---|---|---|
| p_0 | 13 | 🔄💤💤🔄💤🔄💤🔄💤🔄🔄🔄🔄🔄🔄🔄🔄✅ |
| p_1 | 4 | 💤🔄💤💤🔄💤🔄💤🔄✅ |
| p_2 | 1 | 💤💤🔄✅ |
Среднее полное время tau_полн = (18 + 9 + 3) / 3 = 10, ожидания - tau_ожид = (5 + 5 + 2) / 3 = 4. Таким образом, при уменьшении кванта времени время на исполнение и ожидание уменьшается. Однако алгоритм Round Robin требует некоторое время на переключение процессов, поэтому при k = 1 среднее время исполнения и ожидания достигает локального максимума
Заметим, что при k = ∞ алгоритм вырождается в FCFS
Тогда существует такое k', время с которым будет минимальным - при этом такое k' зависит от CPU burst процессов в очереди, поэтому такое k' предсказать нельзя
При этом при появлении нового процесса нельзя предсказать оптимальное место его вставки в кольцевую очередь
Несмотря на это, Round Robin используются в гипервизорах и виртуальных машинах
Кратчайший процесс первым (Shortest Job First, SJF)
Кратчайший процесс первым - выбираем к исполнению кратчайший процесс, предпологая, что мы знаем его CPU burst.
При кванте времени k = 2 получаем:
| Процесс | CPU burst | Время появления процесса | |
|---|---|---|---|
| p_0 | 6 | 0 | 💤💤💤💤💤💤💤🔄🔄🔄🔄🔄🔄✅ |
| p_1 | 2 | 2 | ◾️◾️🔄🔄✅ |
| p_2 | 7 | 6 | ◾️◾️◾️◾️◾️◾️💤💤💤💤💤💤💤🔄🔄🔄🔄🔄🔄🔄✅ |
| p_3 | 5 | 0 | 🔄🔄💤💤🔄🔄🔄✅ |
Shortest Job First - эффективный, но несправедливый алгоритм
Гарантированное планирование
Данный алгоритм был придуман в Массачусетском институте технологий
Пусть N - количество процессов, T_i - время сессии, tau_i - время исполнения. По справедливости каждому процессы мы должны дать tau_i = T_i / N.
Тогда коэффициент справедливости равен R_i = tau_i * N / T_i - чем ближе он к 1, тем более справедливая система. Если для процесса R_i < 1, то значит, что он обделен времени.
Определим квант времени k.
k тактов исполнитсяR_i все еще наименьшее среди остальных, то даем ему еще k тактов и так далее. Иначе ищем новый процессДанный алгоритм оказался неустойчивым ко взлому, например, можно создать программу, которая первые несколько часов будет в состоянии сна, а после пробуждения будет получать все процессорное время
Многоуровневые очереди (или приоритетное планирование)
| Номер очереди | Процессы |
|---|---|
| I | ⚙️⚙️ |
| II | ⚙️⚙️⚙️ |
| III | |
| IV | ⚙️ |
| … | |
| M | ⚙️⚙️ |
Мы ранжируемы процессы в очереди. Внутри очереди процессы крутятся, например, по алгоритму Round Robin
Сначала даем выполниться процессам из очереди I, если она пуста, то из II. Если пуста II, то исполнение переходит к процессам из III и так далее. Но если появляется процесс в очереди выше, то исполнение переходит к нему
В 1967 году в Массачусетстком институте технологий запустили суперкомпьютер IBM 7094. Через 6 лет сделали дамп памяти и обнаружили 2 процесса, которые кто-то запустил в 1967, и до них очередь так и не дошла
Такие процессы стали называться “голодающими”
Теперь нужно придумать механизм лифта, который будет поднимать и опускать нужные процессы
Многоуровневые очереди с обратной связью
Для каждой очереди введем квант времени
| Номер очереди | Квант времени | Процессы |
|---|---|---|
| I | 4 | ⚙️⚙️ |
| II | 8 | ⚙️⚙️⚙️ |
| III | 16 | |
| IV | 32 | ⚙️ |
| … | ||
| M | 2^(M + 1) | ⚙️⚙️ |
Теперь:
И это по сути SJF, но за O(1) и при неизвестных CPU burst процессов