Page replacement nasıl çalışır ve thrashing'e ne yol açar?

Question

IT Interview Practice · Accepted Answer

Fiziksel RAM dolar ama process'ler daha fazla page'e ihtiyaç duyarsa, OS yer açmak için yerleşik bir page'i **tahliye etmelidir (evict)** — kirliyse (dirty) onu **swap**'a (disk) yazarak. Hangi page'in tahliye edileceği **page replacement** kararıdır ve yanlış yapmak performansı mahveder.

## Değiştirme politikaları

Teorik optimum, gelecekte en uzak zamanda kullanılacak page'i tahliye etmektir (**Bélády'nin OPT'si**) — imkânsız, çünkü geleceği göremezsiniz. Bu yüzden **LRU (least recently used — en son kullanılandan en eskisi)** ile yaklaşırız: en uzun süredir kullanılmayan page'i tahliye et. Gerçek LRU her erişimde bir zaman damgası gerektirir (çok maliyetli), bu yüzden gerçek kernel'ler **clock (second-chance) algoritmasını** kullanır:

```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) maliyetle LRU benzeri sonuçlar verir. Linux bunu **active/inactive LRU listeleri** ile daha da iyileştirir.

## Working set ve thrashing

Bir process'in **working set**'i, bir zaman penceresi içinde aktif olarak kullandığı page'ler kümesidir. Paging, *birleşik working set'ler RAM'e sığdığı sürece* sorunsuz çalışır. Sığmadıklarında:

```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 bir uçurumdur, bir yokuş değil: sınırı biraz aşın, neredeyse her erişim miss ettiği için throughput çöker. Belirtiler: CPU neredeyse boşta ama disk I/O doygun ve latency patlıyor.

## Onu düzeltmek / önlemek

- **RAM ekleyin** ya da **yükü azaltın** (daha az eşzamanlı process), böylece working set'ler sığar.
- Scheduler, talebi küçültmek için tüm process'leri **askıya alıp swap-out** edebilir (orta vadeli scheduling).
- Linux'un **OOM killer**'ı son çaredir — sonsuza dek thrash yapmaktansa bir process'i öldürmek.
- Working set'in kendisi daha küçük olsun diye **locality**'yi iyileştirin.

## Neden önemli

Bu, tüm bellek hikâyesini birbirine bağlar ve favori bir senior sorusudur; çünkü thrashing gerçek bir production hata modudur: N kullanıcıda gayet iyi olan bir servis, working set'i RAM'i aştığında N+1'de uçurumdan düşer. İmzayı (yoğun paging, doygun disk, durmuş CPU) tanımak ve kaldıraçları bilmek (RAM, yük atma, locality — ve swap'ın bir bellek kıtlığını bir latency felaketine dönüştürdüğü); bunu dakikalar içinde teşhis etmek ile gizemli biçimde donmuş bir makineye bakakalmak arasındaki farktır.

Değiştirme politikaları

Working set ve thrashing

Onu düzeltmek / önlemek

Neden önemli

İlgili sorular