Yaya CPU scheduling ke aiki, kuma waɗanne ne algorithms na kowa?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** shi ne shawarar kernel game da *wanne* thread mai shiri zai samu CPU *na gaba*, kuma na *tsawon lokaci nawa*. Tunda yawanci akwai threads masu gudana fiye da cores, **scheduler** yana raba su (multiplex), yana nufin daidaita manufofi masu gogayya — **throughput**, **ƙarancin latency / lokacin amsawa**, da **adalci** — yayin da yake guje wa **starvation**.

## Algorithms na kowa

```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** yana nuna babbar maɓalli — **quantum**:

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

## Schedulers na gaske

Tsohon default na Linux na daɗewa shi ne **CFS (Completely Fair Scheduler)**: maimakon yankuna kai-tsaye yana bin diddigin **virtual runtime (vruntime)** na kowane task kuma kullum yana gudanar da thread da ya samu CPU mafi ƙaranci har yanzu, an auna shi da darajarsa ta **nice** — yana kusanto "kowa ya samu rabo na adalci." Yana yin key ga red-black tree ta vruntime, don haka zaɓen task na gaba yana O(log n). (Sabbin kernels suna amfani da EEVDF, wani gyara mai manufa iri ɗaya ta adalci tare da ƙarin iyakoki matse na latency.)

**Preemptive vs cooperative:** OSes na zamani suna **preemptive** — timer interrupt yana ba scheduler damar ƙwace CPU baya da ƙarfi, don haka thread ɗaya ba zai iya mallakar core shi kaɗai ba.

## Me ya sa yake da muhimmanci

Scheduling yana tsara latency da throughput da masu amfani ke ji kai tsaye. Masu hira suna binciken sa don ganin ko ka fahimci trade-offs — dalilin da ya sa workload mai hulɗa (interactive) ke son quanta gajere ko ɗagawar priority, dalilin da ya sa priority scheduling ke bukatar **aging** don hana starvation, da yadda MLFQ/CFS ke samun kyakkyawan halin hulɗa ba tare da sanin tsawon aiki tun farko ba. Har ila yau shi ne samfurin tunani a bayan daidaita `nice`, priorities na real-time, da gano sabis da aka bar wa yunwa ko mai jinkiri.

Algorithms na kowa

Schedulers na gaske

Me ya sa yake da muhimmanci

Tambayoyi masu alaƙa