Jak działa planowanie CPU i jakie są popularne algorytmy?

Question

IT Interview Practice · Accepted Answer

**Planowanie CPU (CPU scheduling)** to decyzja kernela o tym, *który* gotowy wątek dostanie CPU *jako następny* i na *jak długo*. Ponieważ zwykle jest więcej wątków zdolnych do działania niż rdzeni, **scheduler** multipleksuje je, dążąc do zrównoważenia konkurujących celów — **przepustowości (throughput)**, **niskiego opóźnienia / czasu odpowiedzi** i **sprawiedliwości** — jednocześnie unikając **głodzenia (starvation)**.

## Popularne algorytmy

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin** ilustruje kluczowe pokrętło — **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Prawdziwe schedulery

Długoletnim domyślnym schedulerem Linuxa był **CFS (Completely Fair Scheduler)**: zamiast stałych wycinków śledzi **virtual runtime (vruntime)** każdego zadania i zawsze uruchamia wątek, który dotąd otrzymał najmniej CPU, ważony jego wartością **nice** — przybliżając zasadę „każdy dostaje sprawiedliwy udział". Kluczuje czerwono-czarne drzewo (red-black tree) według vruntime, więc wybór następnego zadania jest O(log n). (Nowsze kernele używają EEVDF, udoskonalenia z tym samym celem sprawiedliwości plus ściślejszymi ograniczeniami opóźnień.)

**Preemptive a cooperative:** nowoczesne systemy operacyjne są **preemptive** — przerwanie zegara pozwala schedulerowi siłą odebrać CPU, więc jeden wątek nie może zmonopolizować rdzenia.

## Dlaczego to ważne

Planowanie bezpośrednio kształtuje opóźnienie i przepustowość, które odczuwają użytkownicy. Rozmówcy drążą ten temat, by sprawdzić, czy rozumiesz kompromisy — dlaczego obciążenie interaktywne chce krótkich quantów lub podbicia priorytetu, dlaczego planowanie priorytetowe potrzebuje **aging**, by zapobiec głodzeniu, i jak MLFQ/CFS uzyskują dobre zachowanie interaktywne bez znajomości długości zadań z góry. To także model myślowy stojący za strojeniem `nice`, priorytetami czasu rzeczywistego i diagnozowaniem zagłodzonej lub tnącej się usługi.

Popularne algorytmy

Prawdziwe schedulery

Dlaczego to ważne

Powiązane pytania