Cum funcționează scheduling-ul CPU și care sunt algoritmii comuni?

Question

IT Interview Practice · Accepted Answer

**Scheduling-ul CPU** este decizia kernel-ului privind *care* thread pregătit primește CPU-ul *în continuare* și pentru *cât timp*. Deoarece de obicei sunt mai multe thread-uri rulabile decât core-uri, **scheduler-ul** le multiplexează, urmărind să echilibreze obiective concurente — **throughput**, **latență / timp de răspuns scăzut** și **corectitudine (fairness)** — evitând totodată **starvation**-ul.

## Algoritmi comuni

```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** ilustrează butonul de bază — **quantum**-ul:

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

## Scheduler-e reale

Implicitul de multă vreme al Linux a fost **CFS (Completely Fair Scheduler)**: în loc de felii fixe, urmărește **virtual runtime (vruntime)**-ul fiecărei sarcini și rulează mereu thread-ul care a primit cel mai puțin CPU până acum, ponderat după valoarea sa **nice** — aproximând „fiecare primește o parte echitabilă". Indexează un red-black tree după vruntime, așa că alegerea sarcinii următoare este O(log n). (Kernel-urile mai noi folosesc EEVDF, o rafinare cu același obiectiv de fairness plus limite de latență mai strânse.)

**Preemptive vs cooperative:** OS-urile moderne sunt **preemptive** — o întrerupere de timer permite scheduler-ului să ia forțat CPU-ul înapoi, așa că un thread nu poate monopoliza un core.

## De ce contează

Scheduling-ul modelează direct latența și throughput-ul pe care le simt utilizatorii. Intervievatorii îl sondează pentru a vedea dacă înțelegi compromisurile — de ce un workload interactiv vrea quantum-uri scurte sau un boost de prioritate, de ce priority scheduling are nevoie de **aging** pentru a preveni starvation-ul și cum MLFQ/CFS obțin un comportament interactiv bun fără să cunoască dinainte durata sarcinilor. Este și modelul mental din spatele reglării `nice`, priorităților real-time și al diagnosticării unui serviciu înfometat sau cu lag.

Algoritmi comuni

Scheduler-e reale

De ce contează

Întrebări conexe