Алгоритмы планирования

1. FCFS (First Came First Served)

Приведем пример на вычислениях. Допустим у нас есть три процесса и их CPU-burst: $p_0=13,\ p_1=4, \ p_2=1$ . Обслуживать будем их в порядке 0 → 1 → 2. Теперь можно произвести вычисления:

$$ T_{полн}=18 \ \ \ T_{исполн}=\frac{13 + 17 + 18}{3}=16 \ \ \ T_{ожид}=\frac{0 + 13 + 17}{3}=10 $$

Теперь вычислим значения, если процессы будем обслуживать в порядке 2 → 1 → 0:

$$ T_{полн}=18 \ \ \ T_{исполн}=\frac{1 + 5 + 18}{3}=8 \ \ \ T_{ожид}=\frac{0+1+5}{3}=2 $$

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

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

2. RR (Round Robin)

Приведем пример на вычислениях из предыдущего пункта, но при кванте исполнения $q=4$

$$ T_{полн}=18 \ \ \ T_{исполн}=\frac{18 + 8 + 9}{3} \approx 11.667 \ \ \ T_{ожид}=\frac{5+4+8}{3} \approx 5.667 $$

Как итог, мы получили значения лучше, чем в первом примере первого алгоритма

А теперь уменьшим квант исполнения до $q=1$ и проведём новые вычисления:

$$ T_{полн}=18 \ \ \ T_{исполн}=\frac{18 + 9 + 3}{3} = 10 \ \ \ T_{ожид}=\frac{5+5+2}{3} = 4 $$

3. SJF (Shortest Job First)

4. Гарантированное планирование