Round Robin и приоритеты

Как дать каждому процессу честный «кусочек» процессора и что делать, когда задачи разной важности.

Round Robin (RR) — вытесняющий алгоритм: каждому процессу даётся фиксированный квант времени, после чего он отправляется в конец очереди, а процессор переходит к следующему.

Round Robin: всем по кусочку

RR — это FCFS с одной добавкой: процесс работает не до конца, а максимум один квант (time slice). Не успел — добро пожаловать в конец очереди, дай поработать другим. Это как если бы кассир обслуживал каждого ровно минуту, а потом просил встать в хвост, если не закончили.

Главное достоинство — отзывчивость: ни один процесс не ждёт слишком долго первого запуска. Поэтому RR — основа планировщиков интерактивных систем.

from collections import deque

# (имя, время выполнения), все пришли в момент 0
procs = [("P1", 5), ("P2", 4), ("P3", 3)]
quantum = 2

remaining = {name: burst for name, burst in procs}
q = deque(name for name, _ in procs)
t = 0
completion = {}

while q:
    name = q.popleft()
    run = min(quantum, remaining[name])
    t += run
    remaining[name] -= run
    if remaining[name] == 0:
        completion[name] = t
    else:
        q.append(name)

total_wait = 0
for name, burst in procs:
    turn = completion[name]
    wait = turn - burst
    total_wait += wait
    print(f"{name}: оборот={turn}, ожидание={wait}")

print(f"Среднее ожидание (RR, квант={quantum}): {total_wait/len(procs):.2f}")

Вывод:

P1: оборот=12, ожидание=7
P2: оборот=10, ожидание=6
P3: оборот=11, ожидание=8
Среднее ожидание (RR, квант=2): 7.00

Как выбрать размер кванта

Это тонкий компромисс:

• Слишком большой квант — RR превращается в FCFS, отзывчивость падает.
• Слишком маленький квант — много переключений контекста, накладные расходы съедают процессор.

На практике квант выбирают так, чтобы он был заметно больше времени переключения контекста, но достаточно мал для хорошей отзывчивости — обычно десятки миллисекунд.

Приоритетное планирование

Не все процессы равны: системному демону или видеоплееру важнее получать процессор, чем фоновому индексатору. Приоритетный планировщик выбирает процесс с наивысшим приоритетом. SJF — частный случай: там «приоритет» это короткая длительность.

Проблема: голодание

Если всё время приходят высокоприоритетные задачи, низкоприоритетные могут не дождаться процессора — это голодание (starvation).

Решение: старение

Старение (aging) — постепенное повышение приоритета процессов, которые долго ждут. Чем дольше процесс простаивает, тем выше его приоритет, так что рано или поздно он получит процессор. Это гарантирует, что никто не будет голодать вечно.

# (имя, базовый приоритет, сколько единиц уже ждёт)
# меньше число = выше приоритет
procs = [("P1", 5, 0), ("P2", 1, 0), ("P3", 8, 12)]

def effective(prio, waited):
    # старение: за каждые 4 единицы ожидания приоритет растёт на 1 (число уменьшается)
    return prio - waited // 4

for name, prio, waited in procs:
    eff = effective(prio, waited)
    print(f"{name}: базовый={prio}, ждёт={waited}, эффективный={eff}")

winner = min(procs, key=lambda p: effective(p[1], p[2]))
print(f"Процессор получает: {winner[0]} (благодаря старению догнал по приоритету)")

Вывод:

P1: базовый=5, ждёт=0, эффективный=5
P2: базовый=1, ждёт=0, эффективный=1
P3: базовый=8, ждёт=12, эффективный=5
Процессор получает: P2 (благодаря старению догнал по приоритету)

Здесь P3 был очень низкоприоритетным (8), но после долгого ожидания его эффективный приоритет вырос до 5 — он догнал P1. Так старение спасает от голодания.

Итог

• Round Robin даёт каждому процессу квант времени, обеспечивая отзывчивость.
• Слишком большой квант ≈ FCFS; слишком маленький — много переключений.
• Приоритетное планирование выбирает самый важный процесс.
• Без защиты приоритеты ведут к голоданию низкоприоритетных задач.
• Старение (aging) повышает приоритет долго ждущих процессов и устраняет голодание.