Kako funkcionira CPU scheduling i koji su uobičajeni algoritmi?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** je odluka kernela o tome *koji* spreman thread dobiva CPU *sljedeći* i na *koliko dugo*. Budući da obično ima više pokretljivih threadova nego jezgri, **scheduler** ih multipleksira, nastojeći uravnotežiti suprotstavljene ciljeve — **throughput**, **nisku latenciju / vrijeme odziva** i **pravednost** — uz izbjegavanje **starvationa**.

## Uobičajeni 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** ilustrira ključni regulator — **quantum**:

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

## Stvarni scheduleri

Dugogodišnji zadani izbor Linuxa bio je **CFS (Completely Fair Scheduler)**: umjesto fiksnih odsječaka prati **virtualno vrijeme izvođenja (vruntime)** svakog zadatka i uvijek pokreće thread koji je dosad primio najmanje CPU-a, ponderirano njegovom **nice** vrijednošću — aproksimirajući "svatko dobiva pravedan udio". Indeksira crveno-crno stablo (red-black tree) po vruntimeu, pa je odabir sljedećeg zadatka O(log n). (Noviji kerneli koriste EEVDF, profinjenje s istim ciljem pravednosti uz čvršće granice latencije.)

**Preemptivno vs kooperativno:** moderni OS-ovi su **preemptivni** — timer prekid (interrupt) omogućuje scheduleru da prisilno oduzme CPU, pa jedan thread ne može monopolizirati jezgru.

## Zašto je to važno

Scheduling izravno oblikuje latenciju i throughput koje korisnici osjećaju. Ispitivači to istražuju kako bi vidjeli razumijete li kompromise — zašto interaktivno opterećenje želi kratke quantume ili povišenje prioriteta, zašto priority scheduling treba **aging** kako bi spriječio starvation i kako MLFQ/CFS postižu dobro interaktivno ponašanje bez unaprijed poznatih duljina poslova. To je i mentalni model iza podešavanja `nice`, real-time prioriteta i dijagnosticiranja izgladnjelog ili trzavog servisa.

Uobičajeni algoritmi

Stvarni scheduleri

Zašto je to važno

Povezana pitanja