Page replacement कैसे काम करता है, और thrashing किससे होती है?

Question

IT Interview Practice · Accepted Answer

जब physical RAM भर जाती है पर processes को और pages चाहिए, तो OS को जगह बनाने के लिए एक resident page को **evict** करना पड़ता है — अगर वह dirty है तो उसे **swap** (disk) पर लिखते हुए। किस page को evict करें यह **page replacement** निर्णय है, और इसे गलत करना performance को बर्बाद कर देता है।

## Replacement policies

सैद्धांतिक इष्टतम यह है कि उस page को evict करें जो भविष्य में सबसे दूर इस्तेमाल होगा (**Bélády's OPT**) — असंभव, क्योंकि आप भविष्य नहीं देख सकते। तो हम **LRU (least recently used)** का अनुमान लगाते हैं: उस page को evict करें जो सबसे लंबे समय से इस्तेमाल नहीं हुआ। सच्चे LRU को हर access पर एक timestamp चाहिए (बहुत महँगा), इसलिए असली kernels **clock (second-chance) algorithm** इस्तेमाल करते हैं:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

Clock, LRU-जैसे परिणाम O(1) cost पर देता है। Linux इसे **active/inactive LRU lists** से और परिष्कृत करता है।

## Working set और thrashing

एक process का **working set** उन pages का समुच्चय है जिन्हें वह एक time window के भीतर सक्रिय रूप से इस्तेमाल करता है। Paging ठीक काम करती है *जब तक संयुक्त working sets RAM में समा जाएँ*। जब वे नहीं समाते:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

Thrashing एक चट्टान है, ढलान नहीं: सीमा से थोड़ा ऊपर जाएँ और throughput ढह जाता है क्योंकि लगभग हर access miss होता है। लक्षण: CPU लगभग निष्क्रिय पर disk I/O संतृप्त, और latency विस्फोटित।

## इसे ठीक करना / टालना

- **RAM जोड़ें** या **load घटाएँ** (कम concurrent processes) ताकि working sets समा जाएँ।
- Scheduler पूरे processes को **suspend और swap out** करके माँग सिकोड़ सकता है (medium-term scheduling)।
- Linux का **OOM killer** अंतिम उपाय है — हमेशा के लिए thrash करने के बजाय एक process को मार दें।
- **Locality** सुधारें ताकि working set खुद छोटा हो जाए।

## यह क्यों महत्वपूर्ण है

यह पूरी memory कहानी को एक साथ बाँधता है और एक पसंदीदा senior सवाल है क्योंकि thrashing एक असली production failure mode है: एक service जो N users पर ठीक है, N+1 पर चट्टान से गिर जाती है जब उसका working set RAM से आगे निकल जाता है। हस्ताक्षर पहचानना (भारी paging, संतृप्त disk, ठहरा हुआ CPU) और levers जानना (RAM, load shedding, locality — और यह कि swap एक memory की कमी को एक latency आपदा में बदल देता है) मिनटों में इसका निदान करने और एक रहस्यमय रूप से जमे हुए box को घूरते रहने के बीच का अंतर है।

Replacement policies

Working set और thrashing

इसे ठीक करना / टालना

यह क्यों महत्वपूर्ण है

संबंधित प्रश्न