page replacement ਕਿਵੇਂ ਕੰਮ ਕਰਦੀ ਹੈ, ਅਤੇ thrashing ਕਿਸ ਕਾਰਨ ਹੁੰਦੀ ਹੈ?

Question

IT Interview Practice · Accepted Answer

ਜਦੋਂ ਭੌਤਿਕ RAM ਭਰ ਜਾਂਦੀ ਹੈ ਪਰ processes ਨੂੰ ਹੋਰ pages ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਤਾਂ OS ਨੂੰ ਥਾਂ ਬਣਾਉਣ ਲਈ ਇੱਕ ਰਿਹਾਇਸ਼ੀ page ਨੂੰ **ਬੇਦਖ਼ਲ (evict)** ਕਰਨਾ ਪੈਂਦਾ ਹੈ — ਜੇ ਇਹ dirty ਹੈ ਤਾਂ ਇਸਨੂੰ **swap** (disk) 'ਤੇ ਲਿਖਦੇ ਹੋਏ। ਕਿਹੜਾ page ਬੇਦਖ਼ਲ ਕਰਨਾ ਹੈ, ਇਹ **page replacement** ਫ਼ੈਸਲਾ ਹੈ, ਅਤੇ ਇਸਨੂੰ ਗ਼ਲਤ ਕਰਨਾ performance ਨੂੰ ਤਬਾਹ ਕਰ ਦਿੰਦਾ ਹੈ।

## Replacement policies

ਸਿਧਾਂਤਕ ਆਦਰਸ਼ ਉਸ page ਨੂੰ ਬੇਦਖ਼ਲ ਕਰਨਾ ਹੈ ਜੋ ਭਵਿੱਖ ਵਿੱਚ ਸਭ ਤੋਂ ਦੂਰ ਵਰਤਿਆ ਜਾਵੇਗਾ (**Bélády's OPT**) — ਅਸੰਭਵ, ਕਿਉਂਕਿ ਤੁਸੀਂ ਭਵਿੱਖ ਨਹੀਂ ਦੇਖ ਸਕਦੇ। ਇਸ ਲਈ ਅਸੀਂ **LRU (least recently used)** ਦਾ ਅਨੁਮਾਨ ਲਾਉਂਦੇ ਹਾਂ: ਸਭ ਤੋਂ ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਨਾ ਵਰਤੇ page ਨੂੰ ਬੇਦਖ਼ਲ ਕਰੋ। ਸੱਚੀ 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 ਲਗਭਗ ਵਿਹਲਾ ਪਰ disk I/O ਸੰਤ੍ਰਿਪਤ, ਅਤੇ 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 ਤਬਾਹੀ ਵਿੱਚ ਬਦਲ ਦਿੰਦੀ ਹੈ) ਜਾਣਨਾ, ਇਸਨੂੰ ਕੁਝ ਮਿੰਟਾਂ ਵਿੱਚ ਨਿਦਾਨ ਕਰਨ ਅਤੇ ਇੱਕ ਰਹੱਸਮਈ ਢੰਗ ਨਾਲ ਜੰਮੇ ਹੋਏ box ਨੂੰ ਦੇਖਦੇ ਰਹਿਣ ਵਿਚਕਾਰ ਫ਼ਰਕ ਹੈ।

Replacement policies

Working set ਅਤੇ thrashing

ਇਸਨੂੰ ਠੀਕ / ਟਾਲਣਾ

ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

ਸੰਬੰਧਿਤ ਸਵਾਲ