2.5. Strankovani na zadost

• Dosud vzdy mohla byt uloha zpracovana jen tehdy, az ji byla pridelena pamet pro cely adresovy prostor => caste nevyuzite volne oblasti. Reseni:

1. Obrovske pameti - ekonomicky vice mene nemozne
2. Simulace obrovske pameti - TO JE ONO! virtualni (zdanliva) pamet - dve hlavni techniky vedouci k vytvoreni virtualni pameti jsou strankovani na zadost a segmentace pameti.

Obr. 18 Princip vytvoreni virtualni pameti

• Upusteni od pozadavku umisteni celeho adresoveho prostoru ulohy do operacni pameti => soucet vsech adresovych prostoru muze prekrocit celkovou kapacitu operacni pameti.
• V pameti je jen prave pouzivana cast ulohy.
• Vetsina programu behem sveho konkretniho prubehu vyuziva jen malou cast sveho adresoveho prostoru, protoze:

1. Uzivatelske programy pro osetreni chyb se uziji jen kdyz k chybe dojde (vetsinou je to snad vyjimka)
2. Logicke vetve vylucuji soucasni prubeh alternativnich casti programu
3. Mnoha tabulkam (statickym pametovym strukturam) prideleno pevne mnozstvi adresoveho prostoru, ktere se ne vzdy vyuzije
4. Soubeh mnoha podprogramu se casove vylucuje "vstupni faze", "vypocetni faze" a "vystupni faze" apod.
• Mozne problemy:

1. Situace, kdy se program odvolava na oblast adresoveho prostoru, ktera neni zavedena v operacni pameti
2. Strategie rozhodovani, ktere stranky maji byt uchovany v operacni pameti
• Technicke reseni:

• Rozsirit tabulku stranek o stavovy bit, tj. false - stranka je v operacni pameti, true - stranka neni v operacni pameti. Pokud technicke prostredky pro transformaci adresy zjisti, ze stavovy bit pozadovane stranky je 1, vyvola se page interrupt - vypadek stranky <- NEJEDNA SE O CHYBU UZIVATELSKEHO PGMu (narozdil napr. od preruseni v dusledku poruseni ochrany pameti).
• OS osetri page interrupt zavedenim pozadovane stranky do op. pameti a aktualizaci stavoveho bitu teto stranky. Pote se znovu zahaji provadeni instrukce uziv. pgmu. Stranka byla do pameti zavedena na zadost.
• Pri naplanovani zpracovani ulohy je do op. pameti zavedena pouze prvni "startovaci" stranka. Ostatni jsou pak zavadeny na zadost => nepotrebne stranky se do pameti vubec nedostanou. Kopie celeho adresoveho prostoru ulohy se uchovava v zalozni pameti (magneticky disk) a odtud se ctou pozadovane stranky.
• Mozne komplikace:

• Co v okamziku, kdy neni pam. prostor pro zavedeni dalsi stranky? Resi se pomoci vymeny stranek (page swapping). Obetovana stranka (ta ktera byla urcena k vyrazeni z operacni pameti) se nejprve prekopiruje do zalozni pameti a pak se misto ni zavede stranka nova. Velke vyzkumy stran algoritmu nahrazovani. Muze se stat, ze vyhozena stranka je bezprostredne na to pozadovana a je nutno ji znovu zavest - NEZADOUCI!
• Ctyri funkce modulu pridelovani pameti jsou pri strankovani na zadost slozitejsi a flexibilnejsi:

1. Sledovani stavu pameti - tabulky:

1. tabulky stranek PMTs - jedna tabulka pro adresovy prostor kazde ulohy
2. tabulka bloku pameti MBT - jedna v systemu
3. tabulky souboru FMT (File Map Tables) - pro kazdy adresovy prostor ulohy
2. Rozhodovani o prideleni pameti - castecne provadi planovac uloha. Prideleni je vsak determinovano take vypadky stranek
3. Pridelovani pameti - je nutne najit "vhodny" blok pameti pro startovaci stranku a zmenit stavovy bit bloku.
4. Uvolnovani pameti - neni-li vhodny blok pameti k dispozici, musi byt nektery z obsazenych uvolnen. Je-li uloha dokoncena, vsechny bloky ktere obsadila se uvolni.

2.5.1. Technicke prostredky

• U strankovani na zadost je treba oproti obycejnemu strankovani rozsirit technicke vybaveni o tri dulezite funkce:

1. Stavovy bit v tabulce stranek - indikace zda stranka je ci neni v operacni pameti
2. Rozsireni mechanismu preruseni o "vypadek stranky" (tj. byl ucinen pokus o pristup ke strance, ktera neni v operacni pameti), aby mohl OS tuto situaci osetrit
3. zaznam o pouzivani stranky (tj. pocet pristupu do stranky, pocet cteni, resp. zapisu do stranky apod.) pro strategii rozhodovani, kterou stranku v pripade potreby odstranit z operacni pameti
• Mozne reseni u pr. systemu IBM/370
• Polozky v PMT se lisi pouze tim, ze jeden z nevyuzitych bitu se pouzije jako stavovy bit.

Obr. 19 Stavovy bit stranky v cisle bloku

• Kazdy blok pameti popisuji navic dalsi dva bity:

1. bit indikace pameti (reference bit) - pri cteni lib. mista z bloku se nastavuje na 1
2. bit indikace zmeny (change bit) - pri zapisu do lib. mista v bloku se nastavuje na 1
• Oba bity muze nastavit jadro v privilegovanem rezimu.

2.5.2. Algoritmy programoveho vybaveni

• Modul pridelovani pameti musi spolupracovat s spravou souboru (pristup k zalozni pameti). Kazda stranka ma jednoznacne prirazenou adresu v zalozni pameti - adresu souboru (file address). Tato adresa pak logicky nalezi ke kazde tabulce stranek, napr:

Obr. 20 Kompletni adresa bloku

• V minulem obrazku se predpoklada, ze adresa souboru ma delku 16 bitu

Obr. 21 Vztah tabulky souboru a tabulky stranek

Osetreni vypadku stranky

• Pamet je pridelovana a odebirana i behem provadeni ulohy pomoci mechanismu preruseni
• Pri strankovani na zadost velmi uzce spolupracuje programove a technicke vybaveni (se systemem souboru pracuje programove vybaveni, viz. Obr. 22)
• Prvni cast vyvojoveho diagramu se provadi nejcasteji - implementovana jako soucast technickeho vybaveni pro transformaci adres
• Druha cast je prerusovaci modul v OS
• Pritomnost stranky v pameti se zjistuje podle indikacniho bitu v odpovidajici polozce tabulky stranek 0 - stranka je v pameti; 1 - stranka neni v pameti (vzdy je nutno proverit vsechny adresy v instrukci obsazene a adresu na niz je instrukce ulozena - spousteni instrukci pomoci instrukce EX tj. proved instrukci na uvedene adrese (neprime adresovani instrukce) apod.)
• U systemu s neprimym adresovanim na nekolika urovnich muze nastat v podstate neomezeny pocet vypadku stranek behem vykonani jedne instrukce
• Je-li v pameti volny blok, zjisti se z k tomu urcene specialni adresy v pameti cislo pozadovane stranky - odpovidajici adresa stranky se zjisti z tabulky souboru - stranka se zavede do pameti - aktualizuji se tabulka stranek a tabulka bloku pameti a znovu se zahaji prerusena instrukce
• Neni-li zadny volny blok k dispozici je nutno nekterou stranku z pameti odstranit. Po vyberu takove stranky se musi osetrit jeji bit zmeny. Ma-li hodnotu 0 je kopie stranky v zalozni pameti identicka s tou v op. pameti a stranku neni treba znovu zapisovat do zal. pameti pred jejim odstranenim z op. pameti. Jinak se stranka zapise do zal. pameti a blok se uvolni.
• Pri osetreni vypadku stranky mohou nastat az 2 I/O operace. Behem nich je mozne pridelit procesor jine uloze, ale vyzaduje to rozsirit stavy bloku o dalsi polozku prenos (in transit), protoze:

• Do pameti je zavadena stranka ulohy 1, a proto je procesor pridelen uloze 2. Pritom v uloze 2 nastane vypadek stranky a tato uloha potrebuje volny blok pameti. Pokud by blok ulohy 1 byl oznacen jako prideleny, pak by se prerusovaci modul mohl pokusit o jeho uvolneni, ale zapis stranky ulohy 1 nebyl dosud dokoncen. Pokud by blok ulohy 1 byl oznacen jako volny, pak by sice mohl byt pridelen uloze 2, ale potom by obe ulohy chteli mit svou stranku v temze bloku. Pokud je blok oznacen jako prenos, je v danem okamziku nepridelitelny a po dokonceni I/O stranky muze byt jeho stav zmenen na prideleny nebo volny.

Obr. 22 Interakce mezi programovym a softwarovym vybavenim

• V systemech se znacnou frekvenci I/O stranek se vyuziva rychla cache pamet a chytre pridelovani periferii.

Algoritmy nahrazovani stranek v operacni pameti

• Reseni problemu "vyber stranku k odstraneni z pameti":

1. Nahradi se vzdy stranka v bloku 3. (tj. prvni blok za OS) - velmi jednoduche a velmi neefektivni - mohl by vest az k zahlceni systemu
2. FIFO (First In - First Out) - prvni tam, prvni ven
3. LRU (Least Recently Used) - nejdele nepouzita

Problem je analogicky problemu prodejny s plnymi regaly, ktera musi zavest novy vyrobek. Je nutne urcit algoritmus, podle ktereho se vybere zbozi k odstraneni do skladu. Je mozne zvolit to, ktere je v prodejne nejdele (FIFO) - mnohdy uspesna strategie, ktera vede k odstraneni zbozi s proslou zarucni dobou. U zbozi s dlouhodobou trvanlivosti (caj, cukr apod.) vsak vede k problemum.

Lepe je nahradit zbozi, na kterem je v prodejne nejvic prachu - to, ktere nebylo dlouho pozadovano (LRU). Pokud je algoritmus zvolen vhodne, do skladu se pro odlozene zbozi musi jen zridka.

Ven z kramu.

Simulace algoritmu nahrazovani stranek

• Ohodnotme nahrazovaci algoritmus retezcem volani pameti a spocitejme pocet vypadku stranky. Retezec nazveme referencni retezec (reference string). Sled adres necht je generovan umele (napr. generatorem nahodnych cisel) nebo primym zaznamem kazdeho volani pameti skutecneho programu. To dava priblizne 1 milion adres za sekundu.

1. K vytvoreni referencniho retezce uzijme cisla stranek na kterych se jedn. instrukce nachazi.
2. Pokud je volana stranka p, potom zadne bezprostredne nasledujici volani stranky p nevyvola vypadek stranky, a proto se tato volani v retezci neprojevi.
• Pri sledovani procesu je mozne ziskat napr. nasledujici sled adres:

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

• Pokud ma blok pameti velikost 100 bytu, je vysledny referencni retezec:
1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1
• Pro urceni poctu vypadku stranky je nutno znat pocet pristupnych bloku. S klesajicim poctem volnych bloku roste pocet vypadku stranky. V hornim pripade, mame-li tri nebo vice volnych bloku, dojde pouze ke trem vypadkum stranky nutnym k zavedeni jedn. stranek 1, 4 a 6. Je-li volny toliko jeden blok, vyvola vymenu kazde volani stranky a vypadku bude 11.

Obr. 23 Graf zavislosti poctu vypadku stranky na poctu bufferu

• Pro demonstraci algoritmu vymeny stranek uzijme referencni retezec:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 pro pamet se 3 volnymi bloky.

• Pro vymenu vybira stranku, ktera je nejdele v pameti. Neni nutno zaznamenavat cas zavedeni kazde stranky. Staci vytvorit FIFO frontu stranek zavedenych v pameti a nahradit vzdy tu na vrcholu fronty. Kazda zavedena stranka se zaradi na konec fronty. Pro nas referencni retezec a pamet se 3 volnymi bloky, by sled vymen v pameti byl nasledujici:

Obr. 24 FIFO algoritmus vymeny stranek

• FIFO algoritmus vymeny je jednoduchy na pochopeni i programovani, nepracuje vsak vzdy dobre - nova stranka muze nahradit inicializacni cast pgmu, ktera uz nebude nikdy pouzita, nebo naopak stranka s velmi casto uzivanymi promennymi, ktera se bude muset brzy zavadet znovu.
• Problem, ke kteremu vede FIFO algoritmus ilustruje nasledujici referencni retezec:

Obr. 25 Krivka vypadku stranek s FIFO anomalii

• Na Obr. 25 je krivka zavislosti poctu vymen stranek a volnych bloku pameti. Je na ni videt, ze pocet vymen pro 4 volne bloky je vetsi (10) nez pocet vymen pro 3 volne bloky (9). Tento neocekavany efekt se nazyva FIFO anomalie, prip. Beladysova anomalie (Belady 1969).
• Beladysova anomalie vedla ke snaze vytvorit optimalni algoritmus vymeny stranek. Takove algoritmy byly teoreticky vytvoreny pod jmeny MIN (Belady 1969) nebo OPT (Mattson 1970). Jejich princip je nahradit stranku, ktera nebude v budoucnu dlouho pouzivana (viz. Obr. 26). Tyto algoritmy jsou vsak velmi tezko implementovatelne, protoze vyzaduji dopredu referencni retezec vymen. Jejich pouziti je v teoreticke rovine pro srovnani optimalnosti toho ktereho algoritmu. V analogii s drive uvadenym prikladem by se problem premistovani zbozi ze skladu do prodejny resil pomoci dlouhodobe presne znalosti vyvoje poptavky.

Obr. 26 Optimalni algoritmus vymeny stranek

Optimalni algoritmus neni implementovatelny, ale je mozno implementovat jeho aproximaci. Touto aproximaci je

LRU algoritmus

• Vychazi z toho, ze stranka, na kterou se dlouho nevyskytl zadny odkaz nebude pravdepodobne potreba ani nadale a naopak - zakladni myslenka teorie lokality
• Tato strategie je nejefektivnejsi ze vsech, ktere pracuji s uplynulym casem na rozdil od OPT a MIN
• Strategie LRU patri do tzv. zasobnikovych algoritmu tj. algoritmy u nichz nikdy nemuze vest zvyseni poctu bloku pameti k zvyseni vypadku stranky
• LRU strategie asociuje kazdou stranku s casem, kdy byla naposledy pouzita a pokud musi byt stranka z pameti vyrazena, LRU vybere tu, ktera nebyla pouzita nejdele
• Aplikaci LRU strategie na nas referencni retezec ukazuje Obr. 27. Behem LRU dochazi k 12 vypadkum stranek; prvnich 5 vypadku je stejnych jako u algoritmu OPT. V okamziku, kdy chybi stranka 4, LRU zjisti, ze nejdele nepouzita je v pameti stranka 2 a tudiz bude nahrazena strankou 4 atd.

Obr. 27 LRU algoritmus vymeny stranek

• Pocet vypadku stranky: 9(OPT) < 12(LRU) < 15(FIFO)
• LRU algoritmus je casto implementovan a funguje celkem dobre. Nejvetsi problem je, jak ho implementovat, protoze tento algoritmus vyzaduje velkou hardwarovou podporu. Problem je v tom, jak udrzet poradi uziti jednotlivych stranek. 2 implementace jsou proveditelne:

1. Citace: Kazdy blok pameti se asociuje s polem cas_uziti a do CPU se prida logicky casovac, ktery je inkrementovan pri kazdem pouziti pameti. Pokazde, kdyz je operace s ramcem dokoncena, zkopiruje se obsah logickeho casovace do pole cas_uziti dane stranky. Takto mame uchovany "cas" posledniho pouziti kazde stranky a nahrazovat se bude vzdy stranka s nejmensi hodnotou v registru cas_uziti. Tato technologie vyzaduje zapis do pameti (do registru cas_uziti) pri kazdem pristupu do pameti, casy musi byt aktualizovany pri kazde zmene obsahu bloku a musi byt osetreno preteceni casovace.
2. Zasobnik: Druhou cestou je vytvoreni zasobniku cisel bloku. Vzdy, kdyz je na nektery blok odkazovano, je jeho cislo smazano z predesleho vyskytu v zasobniku a ulozeno na vrchol. V tomto pripade je na vrcholu zasobniku nejcasteji pouzivana stranka a na konci ta nejmene. Implementace zasobniku musi umoznovat odebirat polozky z jeho tela. Vybrani polozky z tela zasobniku a jeji ulozeni na vrchol zpusobi pri nejhorsim zmenu 6ti ukazatelu. Tento pristup je primereny pro implementaci
.
• Nevyhodou LRU algoritmu je nutnost aktualizace zaznamu o uziti stranky po kazdem odkazu na stranku (u FIFO jen v pripade, ze byla stranka zavadena do pameti) => zpomaleni a zdrazeni vypocetniho systemu. Proto se tato implementace v podstate nepouziva a vyuziva se aproximace LRU algoritmu.
• Aproximace LRU algoritmu nevyuziva frontu zadosti o jednotlive stranky, ale svou cinnost stavi na referencnich bitech - bitech indikace pameti jedn. stranek (viz. kap. 3.5.1). Podle nich algoritmus nevi presny sled uziti jednotlivych stranek, vi ale, ktere stranky v minulosti pouzity byly (jejich ref. bit ma hodnotu 1) a ktere ne. Fungovani teto aproximace algoritmu znazornuje nasledujici diagram:

Obr. 28 Aproximace LRU algoritmu

• Aproximace vyuziva ukazatele presunu, ktery se cyklicky pohybuje po jednotlivych strankach. V okamziku vypadku stranky je projizdi jednu po druhe dokud nenarazi na tu, ktera ma referencni bit 0. Ta se pouzije pro vymenu. U tech, ktere maji ref. bit roven jedne je tento vynulovan, aby se zjistilo, zda do dalsiho pruchodu ukazatele byl nebo nebyl blok pouzit.

2.5.3. Vyhody

1. Vsechny vyhody az dosud uvadene, zejmena eliminace fragmentace bez zhustovani.
2. Rozsahla virtualni pamet - adresovy prostor ulohy neni omezen fyzickym rozsahem pameti.
3. Efektivnejsi vyuziti operacni pameti - malo, prip. vubec nevyuzite casti adresoveho prostoru se nezavadeji do operacni pameti (casto 25% i vice).
4. Neomezene multiprogramovani - neni omezeno fyzickym rozsahem operacni pameti

2.5.4. Nevyhody

1. Nakladne technicke prostredky, vnitrni fragmentace, rezie procesoru, pametovy prostor pro tabulky - narocnejsi nez u bezneho strankovani.
2. Nutno vytvorit prostredky pro prevenci zahlceni systemu (pripad, kdy cas procesoru pro osetreni vypadku stranek neumerne stoupne na ukor uzivatelskych uloh.

Zpet Obsah Vpred