Si funksionon zëvendësimi i page-ve, dhe çfarë e shkakton thrashing?

Question

IT Interview Practice · Accepted Answer

Kur RAM-i fizik mbushet por proceset kanë nevojë për më shumë pages, OS-i duhet të **dëbojë (evict)** një page rezidente për të bërë vend — duke e shkruar në **swap** (disk) nëse është e ndotur (dirty). Cilën page të dëbohet është vendimi i **page replacement**, dhe ta gabosh e shkatërron performancën.

## Politikat e zëvendësimit

Optimumi teorik është të dëbosh page-in që do të përdoret më larg në të ardhmen (**OPT i Bélády-t**) — i pamundur, meqë nuk mund ta shohësh të ardhmen. Prandaj përafrojmë **LRU (least recently used — më pak i përdoruri së fundmi)**: dëbo page-in e papërdorur për kohën më të gjatë. LRU i vërtetë kërkon një timestamp në çdo qasje (tepër i kushtueshëm), prandaj kernel-et realë përdorin **algoritmin 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 jep rezultate të ngjashme me LRU me kosto O(1). Linux e përmirëson më tej me **lista LRU active/inactive**.

## Working set dhe thrashing

**Working set**-i i një process-i është grupi i pages që ai përdor në mënyrë aktive brenda një dritareje kohore. Paging funksionon mirë *për sa kohë që working set-et e kombinuara futen në RAM*. Kur nuk futen:

```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 është një greminë, jo një pjerrësi: kalo pak mbi kufirin dhe throughput-i shembet sepse pothuajse çdo qasje bën miss. Simptomat: CPU pothuajse në pushim (idle) por I/O e diskut e ngopur, dhe latency që shpërthen.

## Rregullimi / shmangia e tij

- **Shto RAM** ose **ul ngarkesën** (më pak procese njëkohëse) që working set-et të futen.
- Scheduler-i mund të **pezullojë dhe të bëjë swap-out** procese të tëra për të ngushtuar kërkesën (medium-term scheduling).
- **OOM killer**-i i Linux-it është zgjidhja e fundit — vrit një process në vend që të bësh thrash përgjithmonë.
- Përmirëso **locality**-në që vetë working set-i të jetë më i vogël.

## Pse ka rëndësi

Kjo e lidh të gjithë historinë e memories së bashku dhe është një pyetje e preferuar senior sepse thrashing është një mënyrë reale dështimi në production: një shërbim që është në rregull në N përdorues bie nga gremina në N+1 kur working set-i i tij tejkalon RAM-in. Të njohësh nënshkrimin (paging i rëndë, disk i ngopur, CPU e ngecur) dhe të dish levat (RAM, load shedding, locality — dhe se swap-i e kthen një mungesë memorieje në një katastrofë latency-je) është ndryshimi midis diagnostikimit të tij në minuta dhe të ngulurit e sysh te një kuti e ngrirë në mënyrë misterioze.

Politikat e zëvendësimit

Working set dhe thrashing

Rregullimi / shmangia e tij

Pse ka rëndësi

Pyetje të ngjashme