CPU scheduling कसरी काम गर्छ, र सामान्य algorithm हरू के के हुन्?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** भनेको *कुन* तयार thread ले *अर्को* पटक CPU पाउँछ, र *कति बेर* पाउँछ भन्ने kernel को निर्णय हो। सामान्यतया core भन्दा बढी चल्न सक्ने thread हुने हुनाले, **scheduler** ले तिनलाई multiplex गर्छ, प्रतिस्पर्धी लक्ष्यहरू — **throughput**, **कम latency / response time**, र **निष्पक्षता (fairness)** — लाई सन्तुलन गर्ने प्रयास गर्दै, र **starvation** बाट जोगिँदै।

## सामान्य algorithm हरू

```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)
```

## वास्तविक scheduler हरू

Linux को लामो समयदेखिको default **CFS (Completely Fair Scheduler)** थियो: निश्चित slice हरूको सट्टा यसले प्रत्येक task को **virtual runtime (vruntime)** ट्र्याक गर्छ र अहिलेसम्म सबैभन्दा कम CPU पाएको thread सधैं चलाउँछ, यसको **nice** मान अनुसार weighted गरेर — "सबैले निष्पक्ष हिस्सा पाउँछन्" भन्ने कुरालाई नजिक्याउँदै। यसले vruntime अनुसार एउटा red-black tree key गर्छ, त्यसैले अर्को task छान्नु O(log n) हो। (नयाँ kernel हरूले EEVDF प्रयोग गर्छन्, जुन उही fairness लक्ष्य सहित थप कडा latency सीमा भएको परिष्कार हो।)

**Preemptive बनाम cooperative:** आधुनिक OS हरू **preemptive** हुन्छन् — एउटा timer interrupt ले scheduler लाई बलपूर्वक CPU फिर्ता लिन दिन्छ, त्यसैले एउटा thread ले एउटा core मा एकाधिकार जमाउन सक्दैन।

## यो किन महत्त्वपूर्ण छ

Scheduling ले प्रयोगकर्ताले महसुस गर्ने latency र throughput लाई सीधै आकार दिन्छ। Interviewer हरूले यसलाई तपाईं trade-off बुझ्नुहुन्छ कि भनेर जाँच्छन् — किन interactive workload ले छोटो quanta वा priority boost चाहन्छ, किन priority scheduling लाई starvation रोक्न **aging** चाहिन्छ, र MLFQ/CFS ले job को लम्बाइ पहिल्यै नजानिकनै कसरी राम्रो interactive व्यवहार पाउँछन्। यो `nice` tune गर्ने, real-time priority, र starve भएको वा laggy service निदान गर्ने पछाडिको मानसिक model पनि हो।

सामान्य algorithm हरू

वास्तविक scheduler हरू

यो किन महत्त्वपूर्ण छ

सम्बन्धित प्रश्नहरू