CPU scheduling ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ, ਅਤੇ ਆਮ ਐਲਗੋਰਿਦਮ ਕਿਹੜੇ ਹਨ?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** kernel ਦਾ ਇਹ ਫ਼ੈਸਲਾ ਹੈ ਕਿ *ਕਿਹੜੇ* ਤਿਆਰ (ready) thread ਨੂੰ *ਅਗਲੀ ਵਾਰ* CPU ਮਿਲੇ, ਅਤੇ *ਕਿੰਨੀ ਦੇਰ* ਲਈ। ਕਿਉਂਕਿ ਆਮ ਤੌਰ 'ਤੇ cores ਨਾਲੋਂ ਵੱਧ runnable threads ਹੁੰਦੇ ਹਨ, **scheduler** ਉਹਨਾਂ ਨੂੰ multiplex ਕਰਦਾ ਹੈ, ਟਕਰਾਉਂਦੇ ਟੀਚਿਆਂ — **throughput**, **ਘੱਟ latency / response time**, ਅਤੇ **ਨਿਰਪੱਖਤਾ (fairness)** — ਨੂੰ ਸੰਤੁਲਿਤ ਕਰਨ ਦਾ ਟੀਚਾ ਰੱਖਦਾ ਹੈ, ਜਦਕਿ **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 ਦਾ ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਡਿਫ਼ਾਲਟ **CFS (Completely Fair Scheduler)** ਸੀ: ਸਥਿਰ slices ਦੀ ਥਾਂ ਇਹ ਹਰ task ਦੇ **virtual runtime (vruntime)** ਨੂੰ ਟਰੈਕ ਕਰਦਾ ਹੈ ਅਤੇ ਹਮੇਸ਼ਾ ਉਹ thread ਚਲਾਉਂਦਾ ਹੈ ਜਿਸਨੂੰ ਹੁਣ ਤੱਕ ਸਭ ਤੋਂ ਘੱਟ CPU ਮਿਲੀ ਹੈ, ਇਸਦੇ **nice** value ਅਨੁਸਾਰ ਭਾਰ-ਯੁਕਤ — "ਹਰ ਕਿਸੇ ਨੂੰ ਨਿਰਪੱਖ ਹਿੱਸਾ ਮਿਲਦਾ ਹੈ" ਦੇ ਨੇੜੇ। ਇਹ vruntime ਦੁਆਰਾ ਇੱਕ red-black tree ਨੂੰ key ਕਰਦਾ ਹੈ, ਇਸ ਲਈ ਅਗਲਾ task ਚੁਣਨਾ O(log n) ਹੈ। (ਨਵੇਂ kernels EEVDF ਵਰਤਦੇ ਹਨ, ਉਸੇ fairness ਟੀਚੇ ਨਾਲ ਇੱਕ ਸੁਧਾਰ ਜੋ ਸਖ਼ਤ 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 lengths ਪਹਿਲਾਂ ਜਾਣੇ ਵਧੀਆ interactive ਵਿਵਹਾਰ ਕਿਵੇਂ ਹਾਸਲ ਕਰਦੇ ਹਨ। ਇਹ `nice`, real-time priorities ਟਿਊਨ ਕਰਨ ਅਤੇ ਇੱਕ starved ਜਾਂ laggy service ਦੀ ਨਿਦਾਨ (diagnose) ਕਰਨ ਪਿੱਛੇ ਦਾ ਮਾਨਸਿਕ ਮਾਡਲ ਵੀ ਹੈ।

ਆਮ ਐਲਗੋਰਿਦਮ

ਅਸਲੀ schedulers

ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

ਸੰਬੰਧਿਤ ਸਵਾਲ