Lehekülgede asendamine: FIFO, LRU ja optimaalne asenduspoliitika

Mälus on mõned kaadrid, millest igaüks mahutab ühe lehekülje. Programm küsib lehekülgi pöördumisjadas antud järjekorras. Kui lehekülg on juba mõnes kaadris, on tegu tabamusega. Muidu tekib leheküljeviga. Kui kõik kaadrid on täis, tuleb mõni lehekülg eemaldada: FIFO eemaldab kõige varem laaditud lehekülje, LRU selle, mida kasutati kõige ammu, ja OPT selle, mida läheb vaja kõige kaugemas tulevikus.

Näidisarvutus — Lehekülgede asendamine: FIFO, LRU ja optimaalne asenduspoliitika

Pöördumisi	12

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Lehekülgede asendamine: FIFO, LRU ja optimaalne asenduspoliitika

Mälu jagatakse võrdse suurusega kaadriteks ja programmi andmed sama suurteks lehekülgedeks, nii et iga lehekülg mahub igasse kaadrisse. Pöördumisjada näitab, millises järjekorras programm lehekülgi kasutab. Pöördumine lehekülje poole, mida mälus pole, põhjustab leheküljevea: lehekülg laaditakse mällu. Kui ühtegi vaba kaadrit pole, määrab asenduspoliitika, milline lehekülg eemaldada. Asenduspoliitikal esineb antud jada korral Bélády anomaalia, kui F + 1 kaadriga tekib rohkem leheküljevigu kui F kaadriga.

Mida iga sümbol tähendab

F: kaadrite arv
n: lehekülgede arv tsüklis (lahendusega ülesandes)
r: tsükli korduste arv

Eeldab: Lehekülgi laaditakse nõudmisel: lehekülg laaditakse alles siis, kui seda küsitakse. Alguses on mälu tühi, seega põhjustab esimene pöördumine iga lehekülje poole leheküljevea iga asenduspoliitika korral. Kui mitut lehekülge enam vaja ei lähe, eemaldab OPT siinses mudelis neist väikseima numbriga lehekülje. Iga pöördumine puudutab üht lehekülge; lugemist ja kirjutamist ei eristata ning lehekülje eemaldamisega ei kaasne lisakulu. LRU täpne rakendamine nõuab iga mälupöördumise aja teadmist. Selle salvestamine on liiga kulukas, mistõttu operatsioonisüsteemide tuumad kasutavad LRU ligikaudseid variante, kus iga lehekülje juures hoitakse kasutusbitti. Neist tuntuim on kellalgoritm.

Üks kaader lisaks, üks leheküljeviga rohkem 🖖

Vajuta FIFO, 3 kaadrit ja seejärel FIFO, 4 kaadrit. Jada on 1 2 3 4 1 2 5 1 2 3 4 5 ning suurema mäluga tekib rohkem leheküljevigu: 10 võrreldes 9-ga. Liigu mõlemas näites sammhaaval sammuni 7, kus küsitakse lehekülge 5. Kolme kaadri korral on leheküljed 1 ja 2 juba eemaldatud ja uuesti laaditud, seega on need kõige uuemad ning FIFO eemaldab lehekülje 4. Nelja kaadri korral on 1 ja 2 kogu aeg mälus püsinud. Lehekülg 1 on laaditud kõige varem ja FIFO eemaldab selle üks samm enne, kui programm seda küsib. Bélády, Nelson ja Shedler kirjeldasid seda nähtust 1969. aastal. Nähtus on haruldane: kontrollisime FIFO-ga kõiki kaheteistkümnest pöördumisest lühemaid jadasid kõigi võimalike lehekülgede arvudega ja üheski seda ei esine. Täpselt kaheteistkümne pöördumisega jadasid on 4 213 597, kui ainult lehekülgede nimetuste poolest erinevad jadad lugeda samaks. Neist kaheksas esineb see nähtus. Kõik need algavad jadaga 1 2 3 4 1 2 5 1 ning kõigis lisandub kolmelt kaadrilt neljale üle minnes üks leheküljeviga. Siinne jada on neist kaheksast ainus, kus on viis lehekülge.

LRU ja OPT puhul ei suurenda mälu lisamine kunagi leheküljevigade arvu 🖖

Vajuta LRU, 4 kaadrit: sama jada korral tekib 8 leheküljeviga, kolme kaadriga aga 10. F kaadriga hoiab LRU mälus F viimati kasutatud lehekülge; F + 1 kaadriga mahutab ta needsamad ja veel ühe. Seega on väiksema mälu leheküljed igal sammul olemas ka suuremas mälus ning pöördumine, mis annab tabamuse kolme kaadriga, annab tabamuse ka nelja kaadriga. FIFO hoiab mälus viimati laaditud lehekülgi. Kaadrite arvust sõltub aga kogu laadimiste ajalugu: pärast sammu 7 on kolme kaadriga mälus 1, 2 ja 5, nelja kaadriga aga 2, 3, 4 ja 5. OPT puhul sisaldab suurem mälu igal sammul kõiki väiksema mälu lehekülgi, nagu LRU puhulgi. Selle omadusega asendusalgoritme nimetatakse pinualgoritmideks. Tulemuste all olevas tabelis on kirjas leheküljevigade arv iga kaadrite arvu korral. Pinualgoritmide puhul ei kasva see kaadrite lisamisel kunagi. FIFO puhul võib kasvada ning vastav lahter on esile tõstetud.

Mälust ühe lehekülje võrra suurem tsükkel põhjustab LRU-ga igal pöördumisel vea 🖖

Vajuta Tsükkel, LRU: viit lehekülge loetakse järjest kolm korda, kasutada on neli kaadrit. Kõik 15 pöördumist põhjustavad leheküljevea, sest kõige ammu kasutatud lehekülg on alati just see, mida tsüklis järgmisena küsitakse. FIFO käitub täpselt samamoodi. Vajuta Tsükkel, OPT ja vigade arv langeb 7-ni. OPT eemaldab lehekülje, mida läheb vaja kõige kaugemas tulevikus. Sammudel 5 ja 9 on selleks vahetult enne loetud lehekülg. OPT saab selle kindlaks teha vaid seetõttu, et vaatab enne valikut kogu jada lõpuni läbi. Ükski operatsioonisüsteem seda teha ei saa. OPT annab võrdlusaluse: vähima leheküljevigade arvu, millega ükski asenduspoliitika selle jada läbida saaks. Lisa tsüklile viies kaader ja kõigi kolme puhul tekib 5 viga, iga lehekülje kohta üks.

Ülesanne täielikult lahendatud

Millal põhjustab LRU iga pöördumisega leheküljevea? 5 sammu
Vajuta Tsükkel, OPT ja leia, millistel sammudel tekivad selle 7 leheküljeviga. Vaatle seejärel programmi, mis liidab 100 lehekülge täitva massiivi elemendid kokku 1 000 korda, kasutades 99 kaadrit. Mitu leheküljeviga tekib LRU-ga, mitu OPT-ga ja mitu siis, kui lisada 100. kaader?

Ava see ülesanne tööriistas
1. Siinses näites põhjustavad esimesed viis pöördumist leheküljevea: neli esimest täidavad tühjad kaadrid ja viies sunnib lehekülje eemaldama. Seejärel tekivad vead sammudel 9 ja 13, nelja pöördumise järel: 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. Kui n leheküljega tsükli jaoks on n − 1 kaadrit, on täpselt üks tsükli lehekülg mälust väljas. Leheküljevea hetkel läheb kõige kaugemas tulevikus vaja vahetult enne loetud lehekülge, milleni jõutakse uuesti n − 1 pöördumise pärast. Viimasel läbimisel ei lähe mõnda lehekülge enam vaja ja OPT võib eemaldada hoopis ühe neist. Vahetult enne loetud lehekülje eemaldamisel jäävad järgmise n − 2 pöördumise leheküljed mällu, nii et järgmine viga tekib n − 1 pöördumise pärast.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU 99 kaadriga: kui lehekülg p põhjustab vea, on kõik ülejäänud leheküljed kaadrites olemas. Kõige ammu kasutati lehekülge p + 1, mida tsükkel küsib järgmisena. Kõik 100 × 1 000 = 100 000 pöördumist põhjustavad leheküljevea, nagu siinses näites kõik 15 pöördumist. FIFO eemaldab samad leheküljed.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT puhul täidavad esimesed 99 pöördumist kaadrid. Alates 100. pöördumisest tekib viga iga 99 pöördumise järel, pöördumistel 100, 199, 298, … . Neid vigu on 1 + ⌊(100 000 − 100) / 99⌋ = 1 + 1 009 = 1 010. Kokku tekib 99 + 1 010 = 1 109 viga. Üldvalem on n + ⌊n(r − 1)/(n − 1)⌋, siin n = 100 ja r = 1 000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. 100. kaadri lisamisel mahub kogu massiiv mällu: kõigi kolme asenduspoliitika korral tekib 100 leheküljeviga, iga lehekülje kohta üks. Pärast esimest läbimist vigu enam ei teki.
  
  $F = 100 : 100 faults$
Vastus

LRU-ga 100 000, OPT-ga 1 109 ja ühe lisakaadriga 100 leheküljeviga. LRU jaoks on halvim tsükkel, mis ületab mälu mahtu ühe lehekülje võrra. Puuduva kaadri lisamine vähendab siin vigade arvu tuhat korda.

$LRU 100000, OPT 1109, 100 with one frame more$

Õpitee

Mida andmestruktuur võimaldab odavalt teha

Allikad (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.