Page replacement ఎలా పనిచేస్తుంది, thrashingకు కారణం ఏమిటి?

Question

IT Interview Practice · Accepted Answer

భౌతిక RAM నిండిపోయినా processలకు మరిన్ని pages అవసరమైనప్పుడు, OS స్థలం చేయడానికి ఒక resident pageను **evict** చేయాలి — అది dirty అయితే దాన్ని **swap** (disk)కు వ్రాయాలి. ఏ pageను evict చేయాలో అనేది **page replacement** నిర్ణయం, దాన్ని తప్పుగా చేయడం పెర్ఫార్మెన్స్‌ను నాశనం చేస్తుంది.

## Replacement policies

సైద్ధాంతిక optimum భవిష్యత్తులో అత్యంత దూరంగా వాడబడే pageను evict చేయడం (**Bélády's OPT**) — అసాధ్యం, ఎందుకంటే భవిష్యత్తును చూడలేరు. కాబట్టి మనం **LRU (least recently used)**ను ఉజ్జాయింపుగా వాడతాం: ఎక్కువ కాలం వాడని pageను evict చేయండి. నిజమైన LRUకు ప్రతి access మీద ఒక timestamp అవసరం (చాలా ఖరీదైనది), కాబట్టి నిజమైన kernelలు **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) ఖర్చుతో ఇస్తుంది. Linux దీన్ని **active/inactive LRU lists**తో మరింత శుద్ధి చేస్తుంది.

## Working set మరియు thrashing

ఒక ప్రాసెస్ యొక్క **working set** అనేది ఒక సమయ విండోలో అది చురుకుగా వాడే pagesల సమూహం. *కలిపిన working setలు RAMలో సరిపోతున్నంత వరకు* paging బాగా పనిచేస్తుంది. అవి సరిపోనప్పుడు:

```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 దాదాపు idle కానీ disk I/O saturated, latency పేలడం.

## దాన్ని సరిచేయడం / నివారించడం

- working setలు సరిపోయేలా **RAM జోడించండి** లేదా **లోడ్ తగ్గించండి** (తక్కువ ఏకకాల processలు).
- Scheduler డిమాండ్‌ను కుదించడానికి మొత్తం processలను **సస్పెండ్ చేసి swap out** చేయగలదు (medium-term scheduling).
- Linux యొక్క **OOM killer** చివరి ఉపాయం — శాశ్వతంగా thrash చేయడం కంటే ఒక ప్రాసెస్‌ను చంపడం.
- working set స్వయంగా చిన్నదిగా ఉండేలా **locality**ను మెరుగుపరచండి.

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

ఇది మొత్తం memory కథను ముడివేస్తుంది, thrashing ఒక నిజమైన production వైఫల్య మోడ్ కాబట్టి ఇది ఒక ఇష్టమైన senior ప్రశ్న: N vinియోగదారుల వద్ద బాగానే ఉన్న సర్వీస్ దాని working set RAMను మించినప్పుడు N+1 వద్ద కొండ చరియ నుండి పడిపోతుంది. సంతకాన్ని (భారీ paging, saturated disk, ఆగిపోయిన CPU) గుర్తించడం, మీటలను (RAM, load shedding, locality — మరియు swap ఒక memory కొరతను latency విపత్తుగా మారుస్తుంది) తెలుసుకోవడం అనేది దాన్ని కొద్ది నిమిషాల్లో నిర్ధారించడానికి, రహస్యంగా ఘనీభవించిన బాక్స్‌ను తదేకంగా చూడటానికి మధ్య తేడా.

Replacement policies

Working set మరియు thrashing

దాన్ని సరిచేయడం / నివారించడం

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

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