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 O(1) ખર્ચે LRU-જેવા પરિણામો આપે છે. Linux તેને **active/inactive LRU lists** વડે વધુ સુધારે છે.

## Working set અને thrashing

process નો **working set** એ pages નો સમૂહ છે જે તે એક સમય-બારીમાં સક્રિય રીતે વાપરે છે. 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 લગભગ idle પણ disk I/O saturated, અને 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 છે: N users પર બરાબર ચાલતી service N+1 પર ખડક પરથી પડે છે કારણ કે તેનો working set RAM ને ઓળંગે છે. હસ્તાક્ષર ઓળખવો (ભારે paging, saturated disk, અટકેલ CPU) અને levers જાણવા (RAM, load shedding, locality — અને કે swap memory ની અછતને latency આપત્તિમાં ફેરવે છે) એ થોડી મિનિટોમાં નિદાન કરવા અને રહસ્યમય રીતે થીજી ગયેલા box ને તાકી રહેવા વચ્ચેનો તફાવત છે.

Replacement policies

Working set અને thrashing

તેને ઠીક કરવું / ટાળવું

આ શા માટે મહત્વનું છે

સંબંધિત પ્રશ્નો