როგორ მუშაობს page replacement და რა იწვევს thrashing-ს?

Question

IT Interview Practice · Accepted Answer

როცა ფიზიკური RAM ივსება, მაგრამ process-ებს მეტი page სჭირდებათ, OS-მ უნდა **განდევნოს (evict)** რეზიდენტი page ადგილის გასათავისუფლებლად — ჩაწეროს ის **swap-ში** (დისკზე), თუ ის dirty-ია. რომელი page განდევნოს, არის **page replacement-ის** გადაწყვეტილება, და მისი არასწორად გაკეთება წარმადობას ანადგურებს.

## Replacement-ის პოლიტიკები

თეორიული ოპტიმუმია იმ page-ის განდევნა, რომელიც ყველაზე შორ მომავალში იქნება გამოყენებული (**Bélády's OPT**) — შეუძლებელი, რადგან მომავალს ვერ ხედავთ. ამიტომ ვახდენთ **LRU-ს (least recently used)** მიახლოებას: განდევნეთ ყველაზე დიდი ხნის განუახლებელი page. ნამდვილ LRU-ს სჭირდება timestamp ყოველ წვდომაზე (ძალიან ძვირი), ამიტომ რეალური kernel-ები იყენებენ **clock (second-chance) ალგორითმს**:

```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 სიებით**.

## Working set და thrashing

process-ის **working set** არის page-ების ნაკრები, რომელსაც ის აქტიურად იყენებს დროის ფანჯარაში. Paging კარგად მუშაობს, *სანამ გაერთიანებული working set-ები 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 ინგრევა, რადგან თითქმის ყოველი წვდომა promahvს. სიმპტომები: CPU თითქმის უქმია, მაგრამ დისკის I/O გაჯერებულია, და latency აფეთქდება.

## გამოსწორება / აცილება

- **დაამატეთ RAM** ან **შეამცირეთ დატვირთვა** (ნაკლები ერთდროული process), რომ working set-ები დაეტიოს.
- scheduler-ს შეუძლია მთელი process-ების **შეჩერება და swap-out** მოთხოვნის შესამცირებლად (medium-term scheduling).
- Linux-ის **OOM killer** ბოლო საშუალებაა — process-ის მოკვლა სამუდამო thrash-ის ნაცვლად.
- გააუმჯობესეთ **locality**, რომ თავად working set უფრო პატარა იყოს.

## რატომ არის ეს მნიშვნელოვანი

ეს აკავშირებს მთელ მეხსიერების ისტორიას ერთად და საყვარელი senior კითხვაა, რადგან thrashing რეალური production-ის ხარვეზის რეჟიმია: service, რომელიც N მომხმარებელზე კარგადაა, კლდიდან ვარდება N+1-ზე, როცა მისი working set RAM-ს აჭარბებს. ხელწერის ამოცნობა (მძიმე paging, გაჯერებული დისკი, გაჩერებული CPU) და ბერკეტების ცოდნა (RAM, დატვირთვის ჩამოგდება, locality — და ის, რომ swap მეხსიერების დეფიციტს latency-ის კატასტროფად აქცევს) არის განსხვავება რამდენიმე წუთში დიაგნოსტიკასა და იდუმალად გაყინულ მანქანაზე ცქერას შორის.

Replacement-ის პოლიტიკები

Working set და thrashing

გამოსწორება / აცილება

რატომ არის ეს მნიშვნელოვანი

დაკავშირებული კითხვები