CPU scheduling ఎలా పనిచేస్తుంది, సాధారణ అల్గోరిథమ్‌లు ఏమిటి?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** అనేది *ఏ* సిద్ధంగా ఉన్న thread CPUను *తర్వాత*, *ఎంతసేపు* పొందుతుందో అనే kernel నిర్ణయం. సాధారణంగా coreల కంటే ఎక్కువ నడవగల threadలు ఉంటాయి కాబట్టి, **scheduler** వాటిని multiplex చేస్తుంది, పోటీపడే లక్ష్యాలను — **throughput**, **low 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)
```

## నిజమైన schedulerలు

Linux యొక్క దీర్ఘకాల డిఫాల్ట్ **CFS (Completely Fair Scheduler)**: స్థిర slices బదులు అది ప్రతి task యొక్క **virtual runtime (vruntime)**ను ట్రాక్ చేస్తుంది, ఇప్పటివరకు అతి తక్కువ CPU పొందిన threadను ఎల్లప్పుడూ నడుపుతుంది, దాని **nice** విలువ ప్రకారం weighted చేయబడి — "అందరికీ న్యాయమైన వాటా" అనేదానికి దగ్గరగా. అది vruntime ద్వారా ఒక red-black treeను కీ చేస్తుంది, కాబట్టి తర్వాతి taskను ఎంచుకోవడం O(log n). (కొత్త kernelలు EEVDF వాడతాయి, అదే fairness లక్ష్యంతో పాటు మరింత గట్టి latency హద్దులతో కూడిన శుద్ధీకరణ.)

**Preemptive vs cooperative:** ఆధునిక OSలు **preemptive** — ఒక timer interrupt schedulerను బలవంతంగా CPUను తిరిగి తీసుకోనిస్తుంది, కాబట్టి ఒక thread ఒక coreను గుత్తాధిపత్యం చేయలేదు.

## ఇది ఎందుకు ముఖ్యం

Scheduling వినియోగదారులు అనుభవించే latency మరియు throughputను నేరుగా రూపొందిస్తుంది. మీరు ట్రేడ్-ఆఫ్‌లను అర్థం చేసుకున్నారో లేదో చూడటానికి ఇంటర్వ్యూయర్‌లు దీన్ని పరిశోధిస్తారు — ఒక interactive workload ఎందుకు చిన్న quanta లేదా priority boost కోరుతుంది, priority scheduling starvationను నివారించడానికి ఎందుకు **aging** అవసరం, MLFQ/CFS job పొడవులను ముందుగా తెలియకుండా మంచి interactive ప్రవర్తనను ఎలా పొందుతాయి. ఇది `nice`, real-time priorities ట్యూన్ చేయడం, మరియు ఆకలిగొన్న లేదా laggy సర్వీస్‌ను నిర్ధారించడం వెనుక ఉన్న మానసిక మోడల్ కూడా.

సాధారణ అల్గోరిథమ్‌లు

నిజమైన schedulerలు

ఇది ఎందుకు ముఖ్యం

సంబంధిత ప్రశ్నలు