Сценарии (кратко, с пояснениями)
- Приоритетная инверсия (взаимная блокировка по ресурсу): интерактивный процесс $I$ (высокий приоритет) ждёт мьютекса, который захватил фоновый процесс $B$ (низкий приоритет). Между ними может вставать поток средней приоритета $M$, который занимает CPU, не давая $B$ освободить мьютекс — результат: $I$ блокирован пока не завершит $M$. Это классическая инверсия приоритетов, фактически блокировка $I$ из‑за того, что держатель ресурса не получает CPU.
- Классический дедлок по циклу захвата ресурсов: два процесса $P_1$ и $P_2$ держат разные ресурсы и ждут чужих; если $P_1$ — интерактивный, а $P_2$ — фоновый, система может «заморозить» и отзывчивость пострадает, если фоновый не сможет быть запущен для освобождения ресурса.
- Голодание (starvation) фоновых задач: при непрерывном потоке интерактивных задач фоновые никогда не получают CPU. Формально: если приход интерактивных задач такой, что общий занятый интерактивный CPU доли $\to 1$, то время ожидания фоновой задачи $t_{wait}\to \infty$.
- Непримитивное голодание: длинные неконкурентные секции (non‑preemptible) у интерактивных задач — даже редкие, но долгие такие секции блокируют фоновые на большие интервалы.
Предлагаемые модификации планировщика (цель: сохранить отзывчивость интерактивных и ограничить ожидание фоновых)
1) Приоритетное «донорство» при блокировках (priority inheritance)
- Идея: если задача $A$ ждёт лок на $L$, и держатель $H$ имеет меньший приоритет, временно повысить приоритет $H$ до приоритета $A$ до освобождения.
- Псевдокод (упрощённо):
acquire_lock(L, requester):
if L.holder == NULL:
L.holder = requester
else:
if L.holder.priority < requester.priority:
donate_priority(L.holder, requester.priority)
block requester on L
release_lock(L):
L.holder = next_waiter
restore_priority(previous) // откат донорства
- Эффект: устраняет приоритетную инверсию без значительного ухудшения отзывчивости.
2) Старение приоритета (aging) с ограничением повышений
- Формула эффективного приоритета:
$$p_{eff}(t)=\min (p_{max},p_0+\alpha \cdot t_{wait})$$ где $p_0$ — базовый приоритет, $t_{wait}$ — время в очереди, $\alpha$ — скорость старения, $p_{max}$ — потолок.
- Практический приём: сделать $p_{max}$ чуть ниже порога для интерактивных пиков, чтобы не полностью лишить интерактивности, и комбинировать с гарантией CPU (см. пункт 3).
- Псевдокод:
update_priority(task):
task.p_eff = min(p_max, task.p0 + alpha * task.wait_seconds)
3) Гарантированное окно/доля CPU для фоновых (reservations / periodic window)
- Идея: в каждом периоде $P$ система гарантирует фоновым задачам не менее доли $f$ CPU ($0<f<1$).
- Гарантия даёт верхнюю границу на задержку: задача с потребностью CPU $C$ завершится не позднее $\frac{C}{f}$ секунд.
- Псевдокод (упрощённо):
window_start():
bg_used = 0
scheduler_select():
if bg_used < f * P and exists runnable_background:
pick background task (round‑robin)
else:
pick highest p_eff runnable task
on_context_switch(to_task, duration):
if to_task.is_background:
bg_used += duration
- Пример параметров: $P=$ $1$ s, $f=$ $0.1$ (10% CPU для фоновых) — фоновые получат связный гарантированный минимум при малом ущербе отзывчивости.
4) MLFQ с периодическим «подъёмом» (MLFQ + boost)
- Несколько уровней очередей: интерактивная верхняя, фоновая нижняя. Каждые $T_{boost}$ все задачи повышаются в приоритете (или очереди сбрасываются), чтобы предотвратить бесконечное голодание.
- Параметры: интервал буста $T_{boost}$ выбирается так, чтобы интерактивность не страдала ($T_{boost}$ порядка сотен мс–секунд).
- Псевдокод:
every T_boost:
for task in all_tasks:
promote(task) // или сбросить к начальному уровню
5) Ограничение времени выполнения интерактивной задачи (time quantum / soft throttling)
- Если интерактивная задача занимает CPU больше порога $T_{long}$, на время снизить её эффективный приоритет (или снять интерактивный флаг), чтобы другие могли выполниться.
- Параметр: $T_{long}$ = например $100$–$500$ ms.
6) Комбинированная стратегия (рекомендуемая)
- Приоритетное донорство для блокировок (убирает инверсии).
- Aging с формулой $p_{eff}=\min (p_{max},p_0+\alpha t_{wait})$.
- Гарантированная доля $f$ в периоде $P$ для фоновых (даёт жёсткие пределы ожидания: время выполнения $C\le C/f$).
- MLFQ boost как страховка от долгого голодания.
- Ограничение длительности квантов интерактива для подавления CPU‑хогов.
Пример числовых настроек (пример, все числа в KaTeX)
- диапазон приоритетов $p\in [0,100]$, интерактивные стартуют $p_0=90$, фоновые $p_0=20$;
- старение $\alpha =5$ единиц/с, потолок $p_{max}=80$;
- гарантированная доля фоновых $f=0.1$ в периоде $P=1$ s;
- boost интервал $T_{boost}=200$ ms;
- порог долга интеракта $T_{long}=200$ ms.
Короткая оценка гарантий
- Сочетание aging+reservation даёт «мягкие» и «жёсткие» гарантии: старение уменьшает ожидание эмпирически, а резерв $f$ даёт формальную границу на задержку фоновых задач: задача с CPU‑требованием $C$ завершится за не более $\frac{C}{f}$ реального времени при постоянной конкуренции.
Практические замечания
- Параметры нужно подбирать по нагрузке; слишком агрессивное повышение приоритета снижает отзывчивость.
- Priority inheritance должен быть применён на уровне синхронизаторов (mutex, IO locks).
- Для мульти‑юзерных систем стоит применять доли/квоты по пользователям, чтобы один пользователь‑интерактивщик не убивал всех фоновых задач других.
(Резюме: используйте priority inheritance для удаления инверсий, aging + потолок для плавного снятия голодания, плюс небольшую жёсткую гарантию CPU $f$ в окне $P$ и периодический boost/ограничения квантов для страховки — это сохраняет отзывчивость интерактивных задач и ограничивает ожидание фоновых.)