Page replacement कसरी काम गर्छ, र thrashing केले गराउँछ?

Question

IT Interview Practice · Accepted Answer

जब physical RAM भरिन्छ तर process हरूलाई थप page चाहिन्छ, OS ले ठाउँ बनाउन एउटा resident page **evict** गर्नैपर्छ — यदि यो dirty छ भने यसलाई **swap** (disk) मा लेखेर। कुन page evict गर्ने भन्ने **page replacement** निर्णय हो, र यसलाई बिगार्दा performance नष्ट हुन्छ।

## Replacement नीतिहरू

सैद्धान्तिक इष्टतम भनेको भविष्यमा सबैभन्दा टाढा प्रयोग हुने page evict गर्नु हो (**Bélády को 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 ले O(1) लागतमा LRU-जस्तै परिणाम दिन्छ। Linux ले यसलाई **active/inactive LRU list** हरूसँग थप परिष्कृत गर्छ।

## Working set र thrashing

एउटा process को **working set** भनेको यसले एउटा समय अन्तरालभित्र सक्रिय रूपमा प्रयोग गर्ने page हरूको समूह हो। *संयुक्त 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 लगभग निष्क्रिय तर disk I/O saturated, र latency विस्फोट हुँदै।

## यसलाई सुधार्ने / जोगिने

- **RAM थप्नुहोस्** वा **load घटाउनुहोस्** (कम समवर्ती process) ताकि working set हरू अटाऊन्।
- Scheduler ले माग घटाउन सिंगो process हरूलाई **suspend र swap out** गर्न सक्छ (medium-term scheduling)।
- Linux को **OOM killer** अन्तिम उपाय हो — सधैंभरि thrash हुनुभन्दा एउटा process मार्ने।
- **Locality** सुधार्नुहोस् ताकि working set आफैं सानो होस्।

## यो किन महत्त्वपूर्ण छ

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

Replacement नीतिहरू

Working set र thrashing

यसलाई सुधार्ने / जोगिने

यो किन महत्त्वपूर्ण छ

सम्बन्धित प्रश्नहरू