CPU scheduling کیسے کام کرتی ہے، اور عام الگورتھمز کون سے ہیں؟

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** kernel کا یہ فیصلہ ہے کہ *کون سا* تیار thread CPU کو *اگلا* پائے گا، اور *کتنی دیر* کے لیے۔ چونکہ عام طور پر cores کے مقابلے میں چلنے کے قابل threads زیادہ ہوتے ہیں، **scheduler** انہیں multiplex کرتا ہے، اور آپس میں متصادم مقاصد — **throughput**، **کم latency / response time**، اور **انصاف** — میں توازن رکھنے کی کوشش کرتا ہے، جبکہ **starvation** سے بچتا ہے۔

## عام الگورتھمز

```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** بنیادی گھنڈی کو ظاہر کرتا ہے — **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

Linux کا دیرینہ default **CFS (Completely Fair Scheduler)** رہا ہے: مقررہ ٹکڑوں کے بجائے یہ ہر task کے **virtual runtime (vruntime)** کا حساب رکھتا ہے اور ہمیشہ وہ thread چلاتا ہے جسے اب تک سب سے کم CPU ملا ہو، اس کی **nice** ویلیو کے وزن کے مطابق — "ہر کسی کو منصفانہ حصہ ملتا ہے" کا تخمینہ لگاتے ہوئے۔ یہ ایک red-black tree کو vruntime کے مطابق key کرتا ہے، اس لیے اگلا task منتخب کرنا O(log n) ہے۔ (نئے kernels EEVDF استعمال کرتے ہیں، جو اسی انصاف کے مقصد کے ساتھ ایک بہتری ہے مگر ساتھ میں سخت تر latency حدود رکھتی ہے۔)

**Preemptive بمقابلہ cooperative:** جدید OSes **preemptive** ہوتے ہیں — ایک timer interrupt scheduler کو زبردستی CPU واپس لینے دیتا ہے، اس لیے ایک thread کسی core پر اجارہ داری نہیں کر سکتا۔

## یہ کیوں اہم ہے

Scheduling براہِ راست وہ latency اور throughput گھڑتا ہے جو صارفین محسوس کرتے ہیں۔ انٹرویو لینے والے اسے کھنگالتے ہیں تاکہ دیکھ سکیں کہ آپ trade-offs سمجھتے ہیں یا نہیں — کوئی interactive workload مختصر quanta یا priority boost کیوں چاہتی ہے، priority scheduling کو starvation روکنے کے لیے **aging** کیوں درکار ہے، اور MLFQ/CFS بغیر job کی لمبائی پہلے سے جانے اچھا interactive رویہ کیسے حاصل کرتے ہیں۔ یہ `nice`، real-time priorities کو ٹیون کرنے، اور کسی بھوکی رہ گئی یا لٹکتی سروس کی تشخیص کے پیچھے کا ذہنی ماڈل بھی ہے۔

عام الگورتھمز

حقیقی schedulers

یہ کیوں اہم ہے

متعلقہ سوالات