Prednasky_os_zlin

“index files”
V užívateľskom programe / v knižnici
bežnejší prístup Adresáre Logický pohľad na organizáciu súborov
urýchľuje prístup k súborom
ľahšie sa implementujú režimy prístupu
Staršie systémy
jeden adresár, viac súborov
dvoj-úrovňový adresár, užívatelia na druhej úrovni
“systémove” súbory patria užívateľovi “systém”
Moderné požiadavky
viacúrovňové adresáre Stromová štruktúra adresárov Adresár
je strom s neobmedzenou výškou
Každý vrchol je buďEach node is one of
súbor alebo
adresár
Každý súbor –adresár
cje identifikovateľný cestou (path)
od koreňa (absolutná)
od určitého adresára (relatívna) Operácie nad adresármi Sú to operácie
Tvorba (Create directory)
Vymazanieˇ(Delete directory)
niektoré OS požadujú aby adresár bol prázdny
Hľadanie súboru
Listovanie súborov v adresári
Premenovanie a presunutie súboru
Premenovanie a presunutie podadresárov Ochrana súborov Pri hierarchickej štruktúre
ochrana môže byť špecifikovaná
pre každý vrchol po ceste
Pre súbory
read, write, execute
Pre adresáre
viditeľný, prístupný pre prehľadávanie, modifikovateľný Nestromová štruktúra adresárov Generalizácia stromov
Orientovaný acyklický graf
(neobmedzený) Orientovaný graf
Obyčajne schéma
Dovoľujú súborom a adresárom vystupovať vo viacerých adresároch
Vďaka tomu
je viacej ciest k nim
sú problémy Dva prístupy Mať len jednu kópiu
každý nadradený adresár obsahuje ukazovatele
v Unix-e nazývané linky
hard linky a soft linky
ukazovatele musia byť transparentné
v Unix-e všetky hard-linky sú rovnaké
Udržiavať explicitné kopia
OS musí aktualizovať všetky kópia, aby odzrkadľovali aktuálny stav Zdieľanie súborov Problémy
Zmazanie zdieľaného súboru
Detailne hľadanie nie je efektívne
Riešenia
Ponechať linky „visuté“ (napr. Unix soft linky)
linky sa kontrolujú, keď sa k nim pristupuje
chýbajúce súbory – chyba
Udržiava počet referencií na link a
zmaže ho len ak počet je 0 Slučky v adresároch Pribudnutie slučky kvôli linku
Môže sa stať sa nekontroluje tvorba každého adresára
aby sa zaistilo, že link nevytvára slučku
náročne na implementáciu - výpočtovo
Problémy so slučkami
Detailne prehľadavanie môže byť nekonečne
Počet odkazov nefunguje vždy! Kopírovanie so slučkami Riešenie
Obmedziť podadresárové linky na systémového adninistrátora.
Použiť značkovanie a / alebo Garbage Collection
Značkovanie
označiť vrcholy, ktoré sú už prejdené
aj v prípade acyklických adresároch pomáha
Garbage Collection
Periodicky
označovať všetky adresáre a súbory, prístupne od koreňa
zvyšok vymazať
Synchronizácia procesov
Nezávislé a kooperujúce (spolupracujúce) procesy.
Paralelné vs. pseudo-paralené procesy
Porovnať výsledky pri poradí vykonania 1,2,3,4 a 1, 3, 2, 4. Časová závislosť Súčasný prístup k prostriedkom systému môže viesť k nekonzistencii dát, neprípustné Obecné pojmy synchronizácie Kritická sekcia
sekciu kódu, v ktorej môže používať zdieľané prostriedky systému alebo modifikovať zdieľanú informáciu (spoločné premenné, tabuľky, zdieľané súbory a iné)
Vzájomné vylučovanie
- protokol, ktorý procesy používajú pri požiadavke vstupu do kritickej sekcie. Obecné pojmy synchronizácie 2 Atomická operácia
operácia, ktorá nemôže byť prerušená, musí sa vykonať len celá.
napr. operácie čítania a zápisu sú atomické a vzájomné vylúčené.
byte read; byte write;
word read; word write
Kritéria správnosti 1. Vzájomné vylúčenie: ak proces Pi vykonáva svoju kritickú sekciu, žiadny iný proces nesmie vstúpiť do svojej kritickej sekcie.
2. Postup: aspoň jeden z procesov musí dostať povolenie na vstup do kritickej sekcie, ak v nej nie je žiadny iný proces. Výber procesu, ktorý dostane prístup nesmie trvať nekonečne dlho.
3. Konečné čakanie: žiadny proces nesmie nekonečne dlho čakať, ak požiadal o vstup do KS Princípy pri synchronizácií Dva základné princípy
Synchronizácia aktívnym čakaním - odsun kritickej sekcie sa uskutoční vložením pomocných (obyčajne prázdnych) inštrukcií do kódu procesu.
Synchronizácia pasívnym čakaním - odsun kritickej sekcie sa uskutoční dočasným pozastavením procesu, kým sa kritická sekcia neuvoľní. Vzájomné vylúčenie - vyhovuje
Postup - nevyhovuje, musia sa striedať
Konečné čakanie - vyhovuje Prostriedky pre synchronizáciu aktívnym čakaním Spoločné premenné - SW prostriedky, pre dva procesy
Algoritmus č.1 Vzájomné vylúčenie - vyhovuje
Postup - nevyhovuje, môže nastať deadlock – uviaznutie
Konečné čakanie - nevyhovuje var flag: array [0..1] of boolean; Spoločné premenné 2Algoritmus č.2

Vzájomné vylúčenie - vyhovuje
Postup - nevyhovuje
Konečné čakanie - vyhovuje Petersonove riešenie synchronizácie dvoch procesov spoločnými premennými Synchronizácia n procesov spoločnými premennými - algoritmus pekára Spoločné dátové štruktúry sú: 
var choosing: array [0..n-1] of boolean;
{ inicializované na false }
number: array [0..n-1] of integer;
{ inicializované na 0 }
Pre jednoduchosť definujeme nasledovné pravidlá:
· (a,b) < (c,d), ak a4096
s 1 výpadky >250000 Otázky Koľko rámcov prideliť každému procesu?
Pevný počet
Variabilný počet (z globálneho fondu)
Ako ich priradiť?
Keď proces potrebuje viac rámcov
zoberieme rámec danému procesu
alebo zoberieme od iného procesu? HW obmedzenia Minimálny počet rámcov pre proces
je určený hardware-om
Keď sa reštartuje inštrukcia, ktorá spôsobila výpadok
potrebuje toľko rámcov, koľko odkazov na pamäť môže obsahovať jedna inštrukcia
Môže to byť viac ako jedna stránka
CISC inštrukcia môže presahovať hranice stránky
dáta môžu presahovať hranice stránky
nepriame adresovanie môže presahovať hranice stránky Algoritmy priraďovania rámcov Staticky
priradia sa raz a stav zostava zachovany po celý čas vykonania procesu
Jednotne priraďovanie
Ak máme m rámcov, n procesom priradíme
m / n každému procesu
Jednoduché, ale môže viesť k plytvaniu voľných rámcov, pretože procesy obyčajne nemajú rovnaké virtuálne priestory. Proporcionálne prideľovanie Nech S je suma „potrieb“ rámcov všetkých, kde si je virtuálna pamäť pridelená procesu Pi
Procesu Pi pridelíme (si / S) . m rámcov
Problém
Neberú sa do úvahy priority procesov
ale môže sa objisť nerovnomerným prideľovaným
Neberie sa do úvahy správanie procesov Rozsah nahradzovania Lokálne nahradzovanie
Niekoľko rámcov sú rozdelené stránkam z pevného počtu rámcov pridelené procesu
Počet sa nemení v čase
Globálne nahradzovanie
Niekoľko rámcov sa vyberie z premenlivého počtu rámcov, ktoré sú zdieľané celým systémom
V tomto prípade výpadky stránok jedného procesu sú závislé na správaní a požiadaviek ostatných procesov Zahltenie Definícia
Nech pre dané časové okno T je čas výpočtu procesov a P je čas strávený pri výpadkov stránok
charakteristika zahltenia je časové okno, v ktorom T < P
Kompromis
S nárastom úrovne multiprogramovania narastie (potenciálne) aj efektívnosť využitia CPU
So zmenšovaním úrovne multiprogramovania bude aj menej výpadkov stránok Idea Využiť fakt, že programy preukazujú lokalitu v zmysle prístupov k pamäti
Počas každého „časového okna“
Sledujeme správanie aktívnych procesov
Zisťujeme koľko stránok potrebuje každý proces
Prispôsobujeme úroveň multiprogramovania Pracovné sady(Working Sets) Definícia:
Pracovná sada procesu je množina stránok, ktoré proces využíva v časovom okne W .
Výber parametra W
Pre časové okno w stanoviť veľkosť okna a veľkosť pracovnej sady každého procesu |wi |
Neaktivovať viacej procesov, ak súčet pracovných sad| wi | spolu s pracovnou sadou |wi| nového procesu Pj prekročí počet rámcov Implementácia Udržiava sa pracovná sada každého procesu
častá zmena jej rozmeru vedie k veľkej réžii
Typicky sa robí aproximácia, kde
Aktualizácia sa robí len niekoľko krát (v nejakom časovom intervale sa prezrú referenčné bity a aktualizuje sa stav pracovnej sady)
Bežná je technika podobná LRU
rámec je možne vypustiť z pracovnej sady ak sa nan neodkazovalo v intervale WS Ďalšie úvahy - prepaging „Čisté stránkovanie“ – veľa výpadkov, kým sa nájde počiatočná lokalita
Prepaging (predstránkovanie) - modifikácia stránkovania na žiadosť, kde
Nie všetky požadované stránky sú zavedené do pamäte
Počiatočná pracovná sad sa zavedie naraz ( ako jeden blok)
Prednosť, keď „cena“ obsluhy výpadkov stránok je je vyššia ako tá za predstránkovanie (v tom bloku sú aj nepotrebné stránky!!) Výber veľkosti stránky Veľká stránka
Menšia tabuška stránok – menej stránok
Menšia I/O cena, lebo čas hľadania na disku je menší ako prenos dát
menej výpadkov stránok
Malá stránka
menšia vnútorná fragmentácia
menšia réžia I/O, pretože sa prenášajú len dáta, ktoré sú potrebné in Trendy Väčšie stránky
ceny HW idú dole, rýchlosti rastú
pomer cena-výkon u diskov nejde až tak rýchlo
Takže výpadky stránok sú stále dominantným faktorom, zatiaľ čo fragmentácia nie je..
Konečný výber veľkosti závisí od parametrov konkrétnej implementácie systému Dávkovanie stránok Požadované stránky sa nedajú predvídať
ale stránky, ktoré sa zapisjú na disk – áno
dajú sa zhromaždiť spolu viacere zápisy stránok
napr. na rovnaký cylinder
a prispôsobiť adresy
Tento spôsob je použitý v niektorých implementáciach Unix-u Segmentácia na žiadosť Stránkovanie na žiadosť vyžaduje silnú HW podporu – preto lacnejšie systémy ho nevyužívajú
Ale je žiadúce kvôli
zdieľaniu fyzickej pamäte
a aby procesy za mohli vykonávať aj keď iba časť z nich je v pamäti
Riešením je segmentácia na žiadosť Príklad OS/2 HW Intel 80286 nepodporuje stránkovanie
Každý segment špeciálny má “access bit” (nastavuje sa pri prístupe k segmentu)
Prerušenia časovača sa využívajú na aktualizáciu týchto bitov
Front, ktorý obsahuje položku pre každý segment v pamäti
segmenty, ktorých bit je nastavený sa presunú na začiatok frontu – most recently used
všetky bity sa znulujú
Pri požiadavke na segment sa prehľadá front
Striasanie – periodicky, aby sa odstránila vonkajšia fragmentácia Nahradzovacie algoritmy V zaťaženom systéme všetky rámce sú využité
Nahradenie znamená
vybrať stránku-obeť
zapísať ju na disk (ak bola modifikovaná)
načítať novú stránku z disku
Snaha je
odstrániť stránku, ktorá čo najmenej ovplyvní výkon systému ( nespôsobí v blizkej dobe výpadok) Reťazec odkazov  Postupnosť čísel stánok, na ktorých sa proces odkazuje
Napr.
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Hardware-ové bity Poskytuje info o použití stránky
Obyčajne sú k dispozícií
Bit odkazu na stránku (page-referenced bit)
Bit modifikácie ( page-modified (dirty bit))
Reťazec odkazov sa dá odvodiť tak, že
Bity sa resetujú pre každou inštrukciou
Možnosti využitia bitov
Preferovať stránku, ktorá nebola modifikovaná
Nemusí sa zapisať na disk
Ale treba rozlišovať medzi nemodifikovanými stránkami FIFO Priraďuje každej stránke čas jej príchodu do pamäte.
Obeť - stránka, ktorá je najdlhšie v pamäti.
Nie je potrebné presne zapisovať čas, stačí vytvoriť FIFO front v pamäti.
Nahradí sa stránka, ktorá je na začiatku frontu a číslo novej stránky sa pridá na koniec frontu
Prednosti
jednoduchosť, nevyžaduje HW podporu
Nedostatky
Môže vchodiť stránku, ktorá je často používaná a tá ihneď spôsobí výpadok (napr. knižničná procedúra)
- Belady-ho anomália FIFO-a Optimálny algoritmus Nahradzuje stránku, ktorá nebude potrebná najdlhšiu dobu.
Má najmenší počet výpadkov stránok zo všetkých algoritmov.
Nepreukazuje Belady-ho anomáliu.
Ťažko sa realizuje - vyžaduje znalosť budúcich odkazov na stránky.
Užitočný pre porovnávanie pri vývoji nových algoritmov.   Jasnovidstvo nie je implementovateľné!
Ale môžeme porovnať opt. algoritmus s existujúcimi algoritmami
Deterministické algoritmy, ktoré aproximujú opt. algoritmus
Napr. tak, že na základe terajšieho správania predikujeme budúce.
Fenomén nazvaný lokalita, viackrát využívaný Algoritmus LRU - najdlhšie nepoužívaná použivame blízku minulosť ako aproximáciu pre blízku budúcnosť
ku každej stránke je priradený čas jej posledného použitia
Pracuje dobre pri simulácií
Problém
ako implementovať nahradzovanie podľa LRU
počítadlami
zásobníkom LRU implementovaný počítadlami Ku každej položke tabuľky stránok pripojí pole, ktoré obsahuje čas posledného použitia
k CPU sa pridávajú logické hodiny - počítadlo
Hodnota počítadla sa zvyšuje pri každom odkaze na pamäť
Pri nahradzovaní
vyhodí sa stránka s najmenšou hodnotou počítadla
Problémy
HW podpora
prehľadávanie tabuľky stránok pre nájdenie najdlhšie nepoužívanej stránky search time
Teoreticky Zásobník Uchováva čísel stránok v zásobníku.
Pri odkaze na stránku
sa jej číslo presunie na vrch zásobníka
na spodku je najdlhšie nepoužívaná stránka
Implementácia
obojsmerne zreťazený zoznamu s ukazovateľmi na hlavu a koniec ako mikrocoded
Pipelined stack search (CDC Star 100) LRU Approximácie Používajú sa
aproximácie času pre LRU
bity odkazov na stránky
Periodicky, OS (alebo hardware)
resetuje všetky referenčné bity
pre náhrade – vyberie stránka, na ktorú sa neodkazovalo
Algoritmus s dodatočnými bitmi
8 bitov pre zápis odkazov v pravidelných intervaloch
shift doľava v v pravidelných intervaloch
výber podľa dvojkového čísla Additional-reference-bits As above, but
For each page p
OS maintains an n-bit last-reference-time lrt[p]
Periodically, OS (or hardware)
shifts right lrt[p]
adds in current reference bit to m.s. position
resets reference bit
Page selected is that with lowest lrt Algoritmus druhej šance - cyklický Algoritmus druhej šance
udržiava zoznam rámcov ako cirkulárny front
udržiava pointer na tento zoznam
Využíva. referenčný bit, ktorý je pridaný ku každému rámcu
Nastavuje sa vždy, keď sa so stránkou pracuje.
Keď stránka je vybraná na odsunutie podľa FIFO, skúma sa jej referenčný bit.
Ak je nastavený na 0, stránka sa odsunie,
Ak je nastavený na 1, stránka dostáva „druhú šancu“,
referenčný bit sa znuluje a stránka sa presunie na koniec frontu. Modifikovaný algoritmus druhej šance Ako u algoritmu druhej šance, ale spoužitím dvoch bitov,
jeden pri odkaze na stránku (R),
druhý pri zápise na stránku (W)
00 - na stránku nebolo odkazované a nebola modifikovaná, najlepšia pre nahradenie,
01 - na stránku nebolo odkazované, ale bolo na ňu zapisované, jej obsah bude musieť zapísať na disk,
10 - na stránku bolo odkazované, ale nebolo na ňu zapisované, pravdepodobne bude v najbližšej dobe znova použitá,
11 - na stránku bolo odkazované a bolo na ňu zapisované, pravdepodobne bude v najbližšej dobe znova použitá a jej obsah sa bude musieť zapísať na disk.