Kako deluje razvrščanje CPU (CPU scheduling) in kateri so pogosti algoritmi?

Question

IT Interview Practice · Accepted Answer

**Razvrščanje CPU (CPU scheduling)** je kernelova odločitev, *katera* pripravljena nit dobi CPU *naslednja* in za *kako dolgo*. Ker je pripravljenih niti običajno več kot jeder, jih **scheduler** multipleksira in skuša uravnotežiti nasprotujoče si cilje — **throughput**, **nizko latenco / odzivni čas** in **pravičnost** — hkrati pa se izogniti **starvation** (stradanju).

## Pogosti algoritmi

```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** ponazori osrednji gumb — **quantum**:

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

## Pravi schedulerji

Dolgoletna privzeta izbira v Linuxu je bila **CFS (Completely Fair Scheduler)**: namesto fiksnih rezin sledi **virtual runtime (vruntime)** vsake naloge in vedno požene nit, ki je doslej prejela najmanj CPU, uteženo z njeno vrednostjo **nice** — kar približa "vsak dobi pravičen delež". Rdeče-črno drevo (red-black tree) ključi po vruntime, zato je izbira naslednje naloge O(log n). (Novejši kerneli uporabljajo EEVDF, izboljšavo z istim ciljem pravičnosti in tesnejšimi mejami latence.)

**Preemptive proti cooperative:** sodobni OS-i so **preemptivni** — časovna prekinitev omogoči schedulerju, da prisilno vzame CPU nazaj, tako da ena nit ne more monopolizirati jedra.

## Zakaj je to pomembno

Razvrščanje neposredno oblikuje latenco in throughput, ki ju uporabniki čutijo. Spraševalci to načnejo, da vidijo, ali razumete kompromise — zakaj interaktivna obremenitev želi kratke quantume ali dvig prioritete, zakaj prioritetno razvrščanje potrebuje **aging**, da prepreči starvation, in kako MLFQ/CFS dosežejo dobro interaktivno vedenje, ne da bi vnaprej poznali dolžino opravil. To je tudi miselni model za nastavljanje `nice`, prioritet v realnem času in za diagnosticiranje izstradane ali zatikajoče se storitve.

Pogosti algoritmi

Pravi schedulerji

Zakaj je to pomembno

Povezana vprašanja