Hogyan működik a CPU-ütemezés, és mik a gyakori algoritmusok?

Question

IT Interview Practice · Accepted Answer

A **CPU scheduling** a kernel döntése arról, hogy *melyik* futásra kész thread kapja meg *következőként* a CPU-t, és *mennyi időre*. Mivel általában több futtatható thread van, mint core, a **scheduler** multiplexeli őket, egymással versengő célok — **throughput**, **alacsony latency / válaszidő** és **méltányosság** — kiegyensúlyozására törekedve, miközben elkerüli a **starvationt** (kiéheztetést).

## Gyakori algoritmusok

```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
```

A **round-robin** szemlélteti a fő szabályozót — a **quantumot**:

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

## Valódi schedulerek

A Linux régóta használt alapértelmezettje a **CFS (Completely Fair Scheduler)** volt: rögzített időszeletek helyett minden task **virtual runtime-ját (vruntime)** követi, és mindig azt a threadet futtatja, amely eddig a legkevesebb CPU-t kapta, a **nice** értékével súlyozva — közelítve a "mindenki méltányos részt kap" elvet. Egy red-black fát kulcsol a vruntime szerint, így a következő task kiválasztása O(log n). (Az újabb kernelek az EEVDF-et használják, egy finomítást ugyanazzal a méltányossági céllal, plusz szorosabb latency-korlátokkal.)

**Preemptive vs cooperative:** a modern OS-ek **preemptive**-ek — egy timer interrupt lehetővé teszi, hogy a scheduler erőszakkal visszavegye a CPU-t, így egy thread nem tudja kisajátítani egy core-t.

## Miért fontos

A scheduling közvetlenül alakítja a felhasználók által érzékelt latency-t és throughputot. Az interjúztatók azért firtatják, hogy lássák, érted-e a kompromisszumokat — miért akar egy interaktív terhelés rövid quantumokat vagy priority boostot, miért kell a priority schedulinghoz **aging** a starvation megelőzésére, és hogyan érnek el az MLFQ/CFS jó interaktív viselkedést a jobok hosszának előzetes ismerete nélkül. Ez a gondolati modell a `nice` hangolása, a real-time prioritások és egy kiéheztetett vagy akadozó szolgáltatás diagnosztizálása mögött is.

Gyakori algoritmusok

Valódi schedulerek

Miért fontos

Kapcsolódó kérdések