CPU scheduling hufanyaje kazi, na algoriti zinazozoeleka ni zipi?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** ni uamuzi wa kernel wa *thread ipi* iliyotayari itapata CPU *inayofuata*, na kwa *muda gani*. Kwa kuwa kwa kawaida kuna thread zinazoweza kukimbia nyingi kuliko cores, **scheduler** huzichanganya (multiplex), ikilenga kusawazisha malengo yanayoshindana — **throughput**, **latency ya chini / muda wa mwitikio**, na **usawa** — huku ikiepuka **starvation**.

## Algoriti zinazozoeleka

```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** huonyesha kifundo kikuu — **quantum**:

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

## Scheduler halisi

Chaguo-msingi la muda mrefu la Linux lilikuwa **CFS (Completely Fair Scheduler)**: badala ya vipande vilivyowekwa, hufuatilia **virtual runtime (vruntime)** ya kila task na daima hukimbia thread iliyopokea CPU kidogo zaidi hadi sasa, ikipimwa uzito kwa thamani yake ya **nice** — ikikaribia "kila mmoja hupata sehemu ya haki." Huweka funguo kwenye red-black tree kwa vruntime, hivyo kuchagua task inayofuata ni O(log n). (Kernels mpya zaidi hutumia EEVDF, uboreshaji wenye lengo lile lile la usawa pamoja na mipaka mikali zaidi ya latency.)

**Preemptive dhidi ya cooperative:** OS za kisasa ni **preemptive** — timer interrupt huruhusu scheduler kunyakua CPU kwa nguvu, hivyo thread moja haiwezi kuhodhi core.

## Kwa nini ni muhimu

Scheduling huchagiza moja kwa moja latency na throughput ambavyo watumiaji huvihisi. Wahoji huchunguza hili kuona kama unaelewa trade-offs — kwa nini kazi ya kimwingiliano (interactive) hutaka quanta fupi au boost ya kipaumbele, kwa nini priority scheduling inahitaji **aging** kuzuia starvation, na jinsi MLFQ/CFS zinavyopata tabia nzuri ya kimwingiliano bila kujua urefu wa kazi mapema. Pia ni mfumo wa kifikra nyuma ya kurekebisha `nice`, vipaumbele vya real-time, na kutambua service iliyofishwa njaa au yenye kuchelewa.

Algoriti zinazozoeleka

Scheduler halisi

Kwa nini ni muhimu

Maswali yanayohusiana