Si funksionon CPU scheduling, dhe cilët janë algoritmet e zakonshme?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** është vendimi i kernel-it se *cili* thread i gatshëm e merr CPU-në *më pas*, dhe për *sa kohë*. Meqë zakonisht ka më shumë thread-e të gatshëm për ekzekutim sesa core-e, **scheduler**-i i multiplekson ata, duke synuar të balancojë qëllime konkurruese — **throughput**, **latency e ulët / kohë përgjigjeje**, dhe **drejtësi (fairness)** — ndërkohë që shmang **starvation**.

## Algoritmet e zakonshme

```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** ilustron rregullatorin qendror — **quantum**-in:

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

## Scheduler-a realë

Default-i i hershëm i Linux-it ishte **CFS (Completely Fair Scheduler)**: në vend të copëzave fikse kohore, ai gjurmon **virtual runtime (vruntime)** e çdo task-u dhe ekzekuton gjithmonë thread-in që ka marrë më pak CPU deri tani, të peshuar sipas vlerës së tij **nice** — duke përafruar "secili merr një pjesë të drejtë". Ai përdor një red-black tree me çelës vruntime, kështu që zgjedhja e task-ut tjetër është O(log n). (Kernel-et më të reja përdorin EEVDF, një përmirësim me të njëjtin qëllim drejtësie plus kufij më të ngushtë latency-je.)

**Preemptive vs cooperative:** OS-et moderne janë **preemptive** — një timer interrupt lejon scheduler-in ta marrë me forcë CPU-në mbrapsht, kështu që një thread nuk mund të monopolizojë një core.

## Pse ka rëndësi

Scheduling formëson drejtpërdrejt latency-në dhe throughput-in që ndiejnë përdoruesit. Intervistuesit e sondazhojnë për të parë nëse i kupton kompromiset — pse një workload interaktiv dëshiron quanta të shkurtër ose një rritje prioriteti, pse priority scheduling ka nevojë për **aging** për të parandaluar starvation, dhe si MLFQ/CFS arrijnë sjellje të mirë interaktive pa e ditur paraprakisht gjatësinë e job-eve. Është gjithashtu modeli mendor pas rregullimit të `nice`, prioriteteve real-time, dhe diagnostikimit të një shërbimi të uritur (starved) ose me vonesa (laggy).

Algoritmet e zakonshme

Scheduler-a realë

Pse ka rëndësi

Pyetje të ngjashme