page replacement کیسے کام کرتی ہے، اور thrashing کیا چیز پیدا کرتی ہے؟

Question

IT Interview Practice · Accepted Answer

جب فزیکل RAM بھر جاتی ہے لیکن processes کو مزید pages درکار ہوتے ہیں، تو OS کو جگہ بنانے کے لیے کسی resident page کو **نکالنا (evict)** پڑتا ہے — اگر وہ dirty ہو تو اسے **swap** (disk) پر لکھتے ہوئے۔ کون سا page نکالنا ہے یہ **page replacement** کا فیصلہ ہے، اور اسے غلط کرنا پرفارمنس کو تباہ کر دیتا ہے۔

## Replacement پالیسیاں

نظری بہترین یہ ہے کہ اس page کو نکالا جائے جو مستقبل میں سب سے دور استعمال ہوگا (**Bélády کا OPT**) — ناممکن، کیونکہ آپ مستقبل نہیں دیکھ سکتے۔ اس لیے ہم **LRU (least recently used)** کا تخمینہ لگاتے ہیں: وہ page نکالیں جو سب سے زیادہ دیر سے غیر استعمال شدہ ہو۔ حقیقی LRU کو ہر رسائی پر ایک 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) لاگت پر دیتا ہے۔ 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 منہدم ہو جاتا ہے کیونکہ تقریباً ہر رسائی miss ہوتی ہے۔ علامات: CPU تقریباً بے کار مگر disk I/O سیر شدہ (saturated)، اور latency پھٹتی ہوئی۔

## اسے ٹھیک کرنا / اس سے بچنا

- **RAM شامل کریں** یا **بوجھ کم کریں** (کم بیک وقت processes) تاکہ working sets سما جائیں۔
- scheduler پوری processes کو **معطل اور swap-out** کر سکتا ہے تاکہ طلب سکڑ جائے (medium-term scheduling)۔
- Linux کا **OOM killer** آخری چارہ ہے — ہمیشہ کے لیے thrash کرنے سے بہتر ہے کسی process کو مار دینا۔
- **locality** بہتر کریں تاکہ working set خود چھوٹا ہو جائے۔

## یہ کیوں اہم ہے

یہ پوری میموری کی کہانی کو ایک ساتھ باندھ دیتا ہے اور ایک پسندیدہ senior سوال ہے کیونکہ thrashing ایک حقیقی production failure mode ہے: ایک service جو N صارفین پر ٹھیک ہے N+1 پر کھائی میں گر جاتی ہے جب اس کا working set RAM سے تجاوز کر جاتا ہے۔ دستخط پہچاننا (بھاری paging، سیر شدہ disk، رکی ہوئی CPU) اور گھنڈیوں کو جاننا (RAM، load shedding، locality — اور یہ کہ swap میموری کی کمی کو ایک latency تباہی میں بدل دیتا ہے) اسے چند منٹوں میں تشخیص کرنے اور ایک پُراسرار طور پر منجمد باکس کو تکتے رہنے کے درمیان فرق ہے۔

Replacement پالیسیاں

Working set اور thrashing

اسے ٹھیک کرنا / اس سے بچنا

یہ کیوں اہم ہے

متعلقہ سوالات