Kaip veikia CPU planavimas ir kokie yra dažni algoritmai?

Question

IT Interview Practice · Accepted Answer

**CPU planavimas (scheduling)** yra kernel sprendimas, *kuri* paruošta gija gaus CPU *kita* ir *kuriam laikui*. Kadangi paprastai vykdytinų gijų yra daugiau nei branduolių, **scheduler** jas multipleksuoja, siekdamas subalansuoti konkuruojančius tikslus — **throughput**, **mažą latency / atsako laiką** ir **teisingumą** — kartu vengdamas **starvation** (badavimo).

## Dažni algoritmai

```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** iliustruoja pagrindinę reguliavimo rankenėlę — **quantum**:

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

## Tikri scheduleriai

Ilgametis Linux numatytasis buvo **CFS (Completely Fair Scheduler)**: vietoj fiksuotų laiko atkarpų jis seka kiekvienos užduoties **virtual runtime (vruntime)** ir visada vykdo tą giją, kuri iki šiol gavo mažiausiai CPU, sverdamas pagal jos **nice** reikšmę — apytiksliai „kiekvienas gauna teisingą dalį“. Jis rakina raudonai juodą medį (red-black tree) pagal vruntime, todėl kitos užduoties pasirinkimas yra O(log n). (Naujesni kernel naudoja EEVDF — patobulinimą su tuo pačiu teisingumo tikslu ir griežtesnėmis latency ribomis.)

**Preemptive vs cooperative:** modernios OS yra **preemptive** — timer interrupt leidžia scheduler priverstinai atsiimti CPU, todėl viena gija negali monopolizuoti branduolio.

## Kodėl tai svarbu

Planavimas tiesiogiai formuoja latency ir throughput, kurį jaučia naudotojai. Interviuotojai gilinasi į tai, kad pamatytų, ar suprantate kompromisus — kodėl interaktyvi darbo krūvis nori trumpo quantum ar priority padidinimo, kodėl priority scheduling reikia **aging** starvation išvengti ir kaip MLFQ/CFS pasiekia gerą interaktyvų elgesį iš anksto nežinodami užduočių ilgio. Tai taip pat mąstymo modelis, slypintis už `nice` derinimo, real-time prioritetų ir badaujančio ar strigančio serviso diagnozavimo.

Dažni algoritmai

Tikri scheduleriai

Kodėl tai svarbu

Susiję klausimai