1
J´ adro operaˇ cn´ıho syst´ emu
Operaˇ cn´ı syst´ em je most mezi HW a (uˇzivatelsk´ ym) programem, vytv´aˇr´ı prostˇred´ı pro bˇeh program˚ u. Poskytuje tak abstrakce pro pˇr´ıstup k HW (ˇcti soubor nam´ısto instrukc´ı in). Operaˇ cn´ı syst´ em = j´ adro OS + syst´emov´e programy; Dle rozdˇelen´ı klasifikujeme (mikroj´adro, d´avkov´ y syst´em apod.). Pˇ r´ınosy OS: 1. Abstrakce – rozˇs´ıˇren´ı instrukˇcn´ıho reperto´aru o vyˇsˇs´ı operace 2. Virtualizace – sd´ılen´ı prostˇredk˚ u, izolace, iluze samostatnosti 3. Spr´ ava prostˇredk˚ u – optimalizace v´ ykonu, spravedlnost, ˇreˇsen´ı konflikt˚ u Sluˇ zby operaˇ cn´ıho syst´ emu: • Syst´emov´e sluˇzby • Komunikace (s´ıt’, s´eriov´ a linka, . . . ) • Autentizace a u ´ˇctov´ an´ı • Rozhran´ı pro uˇzivatele J´ adro OS je sloˇzit´ y asynchronn´ı paraleln´ı program, zaveden pˇri startu a celou dobu v pamˇeti, ˇr´ıd´ı hardware a vol´ a syst´emov´e programy. Typy OS: 1. Monoprogramov´e – aktivn´ı jen jeden proces, nen´ı soubˇeˇznost, vˇetˇsinou jeden uˇzivatel, MS-DOS 2. Multiprogramov´e – v´ıce proces˚ u souˇcasnˇe, nutn´e pro v´ıceuˇzivatelsk´ y OS, lepˇs´ı vyuˇzit´ı prostˇredk˚ u (a) Jednoprocesorov´e (b) V´ıceprocesorov´e i. Symetrick´e (rovnocenn´e procesory) ii. Nesymetrick´e (procesory pro r˚ uzn´e u ´ˇcely) Reˇ zim sd´ılen´ı ˇ casu (timesharing) je zp˚ usob emulace paraleln´ıho bˇehu na jednom procesoru. V jeden okamˇzik se vykon´ av´ a jedin´ y proces, ale bˇeˇz´ı pouze chv´ıli (timeslice) a pak se ˇr´ızen´ı pˇred´a dalˇs´ımu. V delˇs´ım intervalu je v´ ysledek stejn´ y, jako by bˇeˇzely paralelnˇe. OS mus´ı umˇet proces pozastavit a uloˇzit stav. OS a ochrana proti proces˚ um – OS nesm´ı b´ yt procesy modifikov´an, je tˇreba procesy omezit: • Privilegovan´e intrukce • Omezen pˇr´ıstup k pamˇeti • Nemoˇznost prov´ adˇen´ı I/O operac´ı pˇr´ımo • Ochrana proti chyb´ am – nucen´e odebr´an´ı procesoru, je-li tˇreba Potˇ rebn´ a podpora v HW: • Pˇreruˇsovac´ı subsyst´em – po pˇreruˇsen´ı se procesor pˇrepne do reˇzimu j´adra • Dva reˇzimy procesoru – privilegovan´e instrukce jen v reˇzimu j´adra 1
• Ochrana pamˇeti – pˇr´ıstup mimo meze vyvol´a pˇreruˇsen´ı • Gener´ ator pˇreruˇsen´ı – ˇcasovaˇc • DMA pro I/O Pˇ reruˇ sovac´ı syst´ em je potˇrebn´ y kv˚ uli mal´e rychlosti I/O zaˇr´ızen´ı. J´adro mus´ı umˇet pˇreruˇsen´ı zpracovat (zablokovat dalˇs´ı pˇreruˇsen´ı, pozastavit bˇeh, obslouˇzit a znovu spustit): 1. Klasick´e j´ adro – obsluha pˇreruˇsen´ı je v j´adˇre, pokud jiˇz bˇeˇzelo, je potˇreba spinlock (kr´atkodob´ y z´ amek) 2. Mikroj´ adro – obsluhou je proces, staˇc´ı jej odblokovat 1. N´ avrat do uˇzivatelsk´eho reˇzimu – jednoduch´ y, nav´ıc m˚ uˇze j´adro jeˇstˇe chv´ıli pracovat na sv´em 2. N´ avrat do j´ adra – bud’ na stejn´e m´ısto (nepreemptivn´ı j´adro) nebo i jinam (preemptivn´ı), ale je to n´ aroˇcn´e Pˇ rechod mezi reˇ zimy (syst´emov´ y a uˇzivatelsk´ y) prob´ıh´a pˇreruˇsen´ım a n´avratem z obsluhy nebo vol´an´ım sluˇzby j´ adra a n´ avratem. Vol´ an´ı j´ adra je jedin´ y zp˚ usob kontaktu mezi uˇzivatelsk´ ym reˇzimem a j´adrem (implementov´ an jako pˇreruˇsen´ı). Rozhran´ı j´ adra definuje zp˚ usob vol´ an´ı j´ adra – bin´arnˇe (ˇc´ıslo IRQ, poloˇzky z´asobn´ıku) nebo zdrojovˇe (vol´ an´ı funkce). Bin´ arn´ı je z´ avisl´e na HW, zdrojov´e je nyn´ı nez´avisl´e, ale nebylo tomu tak vˇzdy, byla potˇreba sjednotit rozhran´ı – dnes IEEE/ISO POSIX 1003.1 POSIX 1003.1 je standardizovan´e rozhran´ı j´adra operaˇcn´ıho syst´emu pro jazyk C. Mˇelo v´ıce reviz´ı, pˇrid´ avaly se vlastnosti (vl´ akna). Spr´ ava procesoru se star´ a o vytv´ aˇren´ı a ruˇsen´ı proces˚ u, jejich pozastaven´ı, spuˇstˇen´ı a pˇrepnut´ı kontextu, synchronizaci a komunikaci. Proces vyuˇz´ıv´ a virtu´ aln´ı procesor s´am pro sebe. Stav procesoru uloˇzen´ y pˇri pˇrepnut´ı zahrnuje vˇsechny registry a virtu´aln´ı adresov´ y prostor (opˇet iluze izolovanosti). Pˇ repnut´ı kontextu nast´ av´ a pˇri vyˇcerp´ an´ı ˇcasov´eho kvanta, vol´an´ı j´adra (zahrnuje ˇcek´an´ı na I/O nebo explicitn´ı pozastaven´ı sleep a wait) nebo m´ a-li bˇeˇzet proces s vyˇsˇs´ı prioritou. Spr´ ava pamˇ eti se star´ a o vytv´ aˇren´ı virtu´aln´ı pamˇeti pro procesy a pˇreklad adres na adresu fyzickou, tak´e str´ ankov´ an´ı nebo segmentaci, swapov´ an´ı a ochranu pamˇeti. Monolitick´ e j´ adro (monitor) je jeden program, kde nejen sluˇzby OS, ale i procesy jsou procedury jednoho programu. Vˇetˇsinou neexistuje rozd´ıl mezi uˇzivatelsk´ ym a jadern´ ym reˇzimem. Klasick´ e j´ adro obsahuje sluˇzby jako podprogramy; rozhran´ı mezi procesy a j´adrem je striktn´ı, obsluha ud´ alost´ı, kter´e nejsou spjaty s procesy je probl´emov´a (prov´ad´ı se pˇred n´avratem z pˇreruˇsen´ı jakoby ”vloˇzenˇe”). Mikroj´ adro m´ a moduly ˇc´ asteˇcnˇe v uˇzivatelsk´em a ˇc´asteˇcnˇe v jadern´em reˇzimu; j´adro obsahuje jen pˇrep´ın´ an´ı kontextu, pˇridˇelov´ an´ı pamˇeti a ochranu, zbytek obsluhuj´ı procesy (tedy i sluˇzby j´adra); komunikace s ˇc´ astmi j´ adra nen´ı vol´ an´ı podprogramu, ale zas´ıl´an´ı zpr´av → probl´em. Virtu´ aln´ı stroj je speci´ alnˇe upraven´e j´ adro, kter´e um´ı pouˇstˇet jin´ y OS jako uˇzivatelsk´ y proces. V syst´emov´em reˇzimu bˇeˇz´ı monitor virtu´ aln´ıho stroje, kter´ y odchyt´av´a pˇreruˇsen´ı a zpracov´av´a je jiˇz norm´aln´ı proces (hostovan´ y OS). 2
2
Procesy a vl´ akna
Program je statick´ y k´ od s daty uloˇzen´ y v souboru. Proces je instance programu v pamˇeti, kter´ a se vykon´av´a. M´a jednoznaˇcnou identifikaci (PID). Stav procesu zahrnuje registry, virtu´ aln´ı pamˇet’ov´ y prostor, z´asobn´ık a syst´emov´e prostˇredky (deskriptory apod.). Hierarchie – jelikoˇz procesy vznikaj´ı duplikac´ı bˇeˇz´ıc´ıho procesu, existuje vztah otec-syn. Nejvyˇsˇs´ım prarodiˇcem je proces init. Pˇri ukonˇcen´ı otce se synov´e pˇresouvaj´ı k init. Pˇri ukonˇcen´ı syna si otec vybere stav. Pokud otec na stav neˇcek´ a, stav vis´ı v pamˇeti a syn se st´av´a zombie. Vl´ akno je samostatnˇe prov´ adˇen´ a ˇc´ ast programu v r´amci jednoho procesu. Takto m˚ uˇze jeden proces bˇeˇzet na v´ıce procesorech paralelnˇe. Proces s vl´ akny je pak jen obalov´ a jednotka pro vl´akna, kter´a jsou ”procesy” z pohledu procesoru. Proces tak pouze uchov´ av´ a vnˇejˇs´ı stav (PID, deskriptory apod.). Rychlost: spuˇstˇen´ı vl´ akna je 10-100x rychlejˇs´ı neˇz fork() (jinak by nemˇela vl´akna moc smysl). Prostˇ redky: vl´ akna sd´ılej´ı cel´ y adresov´ y prostor (procesy jen k´od popˇr sd´ılenou pamˇet’), z´asobn´ıky jsou sice oddˇeleny, ale jen jin´ ym offsetem (mohou se pˇrepsat). Z´asobn´ık je jedin´e m´ısto, kde vl´akno nemus´ı ˇreˇsit v´ıcen´ asobn´ y pˇr´ıstup. V UNIXu je tedy proces jednotkou pˇridˇelov´ an´ı prostˇredk˚ u a vl´akno jednotkou pˇridˇelov´an´ı procesoru. HyperThreading pˇrin´ aˇs´ı v´ıce kontext˚ u na jednom procesoru, ale bˇeh je st´ale bez paralelizace, procesor se pak tv´ aˇr´ı jako 2 CPU. Pˇ ridˇ elov´ an´ı procesoru vl´ akn˚ um m˚ uˇze b´ yt glob´ aln´ı (kaˇzd´e vl´akno je nez´avisl´e) nebo lok´ aln´ı (obalov´ y proces rozhoduje o pˇridˇelov´ an´ı vl´ akn˚ um). Pthreads je implementace vl´ aken podle POSIX. Vl´akno se spouˇst´ı vol´an´ım funkce, kter´a obsahuje k´ od vl´ akna (volaj´ıc´ı je pak pokraˇcuje d´ al jako p˚ uvodn´ı vl´akno). Vol´a se pomoc´ı pthread_create(), je moˇzn´e nastavit atributy vl´ akna. Ukonˇcuje se pthread_join() a je identifikov´ano pthread_t. Atributy pthreads zahrnuj´ı lok´ aln´ı/glob´ aln´ı pl´anov´an´ı, pl´anovac´ı algoritmus, moˇznost ukonˇcen´ı bez ˇcek´ an´ı na stav, velikost z´ asobn´ıku apod. Probl´ emy implementace – vl´ akna sd´ılej´ı pamˇet’, starˇs´ı konstrukce pak koliduj´ı (errno, localtime, strtok), nutnost definovat _REENTRANT. Typick´ e pouˇ zit´ı: I/O vl´ akno vedle v´ ypoˇct˚ u, GUI, u v´ıce procesor˚ u nutnost pro v´ ykon, . . .
3
Implementace vl´ aken
Moˇ zn´ e implementace: 1. N:N (1:1) – vˇsechna vl´ akna jsou na u ´rovni OS: OS/2, WinNT, LinuxThreads, NPTL + vol´ an´ı j´ adra je pˇr´ım´e a rychl´e + pln´e vyuˇzit´ı multiprocessingu 3
- j´ adro mus´ı vˇsechna vl´ akna evidovat, zab´ıraj´ı jadernou pamˇet’ - pˇri pˇrepnut´ı vl´ akna vˇetˇs´ı reˇzie pˇrepnut´ı (jde pˇres j´adro) 2. N:1 – OS vid´ı jen procesy, vl´ akna jsou v userspace pomoc´ı knihoven: FreeBSD < 5.x + n´ızk´ a reˇzie vl´ akna (pamˇet’ov´ a i ˇcasov´a) + pln´ a kontrola pl´ anov´ an´ı (nezasahuje OS) - blokuj´ıc´ı vol´ an´ı j´ adra se zapouzdˇruj´ı - nejde pouˇz´ıt pro v´ıce procesor˚ u (CPU dostane cel´ y proces) 3. N:M – kombinovan´ y pˇr´ıstup, OS vid´ı M vl´aken z N: Solaris, AIX, Irix, FreeBSD + OS vid´ı jen potˇrebn´ a vl´ akna (vˇetˇsinou podle poˇctu CPU) + ˇcekaj´ıc´ı vl´ akna uˇz OS nevid´ı, bez reˇzie + z´ aroveˇ n lze pˇrep´ınat kontext i v userspace + lze simulovat N:N i N:1 - velmi problematick´ a implementace LWP (Lightweight Process) je implementace M:N (Solaris). Jedno vl´akno na u ´rovni procesoru obsahuje staticky nˇekolik uˇzivatelsk´ ych. Pl´ anov´ an´ı je probl´em, userspace nev´ı moc o tom, co se dˇeje v j´adˇre s LWP. LWP jsou pro j´ adro norm´ aln´ımi procesy (chov´ a se k nim jako ke star´ ym proces˚ um). KSE (Kernel Scheduler Entities) je nov´ a implementace pomoc´ı konceptu Scheduler Activations (FreeBSD > 5.x). • Procesor se pˇridˇeluje skupin´ am KSE. • Skupina obsahuje 1 aˇz (poˇcet CPU) aktivn´ıch KSE. • Vl´ akna, kter´ a je potˇreba prov´ adˇet, dostanou pˇridˇeleno jedno KSE. • Pokud je vl´ akno pozastaveno, probud´ı se jin´e a je to ohl´aˇseno userspace.
4
Z´ akladn´ı pojmy pro soubˇ eˇ znost
Nedeterminismus se projevuje v paralelnˇe bˇeˇz´ıc´ıch procesech (a vl´aknech), pˇri prov´adˇen´ı nen´ı jasn´a posloupnost akc´ı. Synchronizace je zajiˇstˇen´ı kooperace pomoc´ı synchronizaˇcn´ıch okamˇzik˚ u (procesy ˇcekaj´ı na ostatn´ı). Race condition chyba vznikaj´ıc´ı kv˚ uli r˚ uzn´e rychlosti paraleln´ıch proces˚ u, je potˇreba zav´est synchronizaci. Atomick´ a operace je takov´ a, kter´ a se provede cel´a najednou nebo v˚ ubec. Zajiˇst’uje konzistenci dat. Atomick´ e operace v CPU: • read,write – atomick´e pro slovo (d´ano architekturou) zarovnan´e na hranici pˇr´ıstupu (vˇetˇsinou str´ anka) • Instrukce s jedn´ım operandem v pamˇeti – opˇet pozor na zarovn´an´ı • Speci´ aln´ı instrukce Vz´ ajemn´ e vylouˇ cen´ı uˇz´ıv´ a synchronizaci k tomu, aby danou operaci mohl prov´adˇet jedin´ y proces. Kritick´ a sekce je u ´sek programu, jehoˇz prov´adˇen´ı je vz´ajemnˇe vylouˇcen´e.
4
• V´ ypoˇcty pˇred a po KS mohou trvat libovolnˇe dlouho. • KS mus´ı b´ yt provedena v koneˇcn´em ˇcase (oˇsetˇren´ı ukonˇcen´ı procesu). • Proces m˚ uˇze do KS vstoupit nekoneˇcnˇe kr´at. • Pokud v KS nikdo nen´ı, mus´ı do n´ı j´ıt vstoupit okamˇzitˇe. • Pˇridˇelov´ an´ı procesoru je spravedliv´e. Spravedlnost (fairness) pˇ ridˇ elen´ı CPU: • Unconditional – kaˇzd´ y nepodm´ınˇen´ y atomick´ y pˇr´ıkaz bude nˇekdy proveden • Weak – tak´e kaˇzd´ y podm´ınˇen´ y atomick´ y pˇr´ıkaz bude proveden, pokud nabyde hodnoty TRUE a nebude se mˇenit • Strong – provedou se i pˇr´ıkazy, jejichˇz hodnoty podm´ınek se nekoneˇcnˇe kr´at zmˇen´ı, pak se tak´e pˇr´ıkaz nekoneˇcnˇe kr´ at provede Bezpeˇ cn´ y (safe) algoritmus zaruˇcuje vz´ ajemn´e vylouˇcen´ı. ˇ y (live) algoritmus je bez uv´ Ziv´ aznut´ı (deadlock), blokov´an´ı (blocking) a st´arnut´ı/vyhladovˇen´ı (starving) Uv´ aznut´ı je stav, kdy vˇsechny procesy ˇcekaj´ı na odemˇcen´ı vstupu do KS, ale proces kter´ y by odemkl ˇcek´ a tak´e. Obt´ıˇzn´ a detekce, nenast´ av´ a deterministicky. Blokov´ an´ı je stav, kdy proces ˇcek´ a na hodnotu, kterou mus´ı nastavit proces jin´ y a ten ji nenastav´ı i kdyˇz je KS voln´ a. Druh´ y proces tak blokuje vstup. St´ arnut´ı je ˇcek´ an´ı na splnˇen´ı podm´ınky vstupu do KS, ale nenast´av´a, jelikoˇz v n´ı neust´ale nˇekdo je (napˇr. pˇredb´ıh´ an´ı). M˚ uˇze b´ yt tolerov´ ano, pokud je vylouˇceno praktick´ ym nasazen´ım. Synchronizaˇ cn´ı n´ astroje: z´ amky, semafory, monitory, zpr´avy Synchronizaˇ cn´ı techniky: ˇcten´ı/z´ apis, z´ akaz pˇreruˇsen´ı, instrukce (implementuj´ı n´astroje)
5
Vz´ ajemn´ e vylouˇ cen´ı pro 1 CPU
Atomick´ y k´ od je u ´sek k´ odu, pˇri kter´em nem˚ uˇze doj´ıt k pˇreruˇsen´ı nebo pˇrepnut´ı kontextu. Zak´ az´ an´ı pˇ reruˇ sen´ı zaruˇcuje, ˇze obsluha pˇreruˇsen´ı nenaruˇs´ı KS. Probl´em je, ˇze komunikace s ˇradiˇcem trv´ a moc dlouho, takˇze vypnut´ı a zapnut´ı m´ a vysokou reˇzii. Lze obej´ıt tak, ˇze se zaznamen´a blokov´an´ı a pokud IRQ pˇrijde, tak se neobslouˇz´ı, ale uloˇz´ı k obslouˇzen´ı pozdˇeji. Zak´ az´ an´ı pˇ repnut´ı kontextu v j´ adˇ re lze pomoc´ı z´akazu pˇreruˇsen´ı, ale tak se zak´aˇze i I/O. Lepˇs´ı je zak´ azat preemptivn´ı pˇrep´ın´ an´ı kontextu, pak st´ale funguje pˇrep´ın´an´ı explicitn´ı, ale to nen´ı v´ ykonovˇe v´ yhodn´e pro syst´em. Je tedy lepˇs´ı ponechat preempci a pouˇz´ıvat bin´arn´ı semafory (z´amky). Uˇ zivatelsk´ e procesy dˇr´ıve pouˇz´ıvaly n´ astroje v j´adˇre (semafory apod.), ale vol´an´ı j´adra m´a pˇr´ıliˇs velkou ˇreˇzii, proto se pouˇz´ıv´ a futex (Fast Userspace Mutex), kter´ y j´adro vol´a pouze, pokud je jiˇz z´amek uzamˇcen, jinak se pouze atomicky testuje hodnota.
5
6
Vz´ ajemn´ e vylouˇ cen´ı pro v´ıce CPU
V´ıceprocesorov´ e prostˇ red´ı pˇr´ın´ aˇs´ı dalˇs´ı probl´emy. Vypnut´ı pˇreruˇsen´ı nezabr´an´ı bˇehu proces˚ u na ostatn´ıch procesorech. Kr´ atkodob´ e vylouˇ cen´ı je speci´ aln´ı pro kritick´e sekce, kter´e jsou kr´ atk´e, neblokuj´ıc´ı a bez preempce (nesm´ı se pˇreruˇsit jej´ı bˇeh). Je moˇzn´e i aktivn´ı ˇcek´ an´ı, protoˇze pˇrepnut´ı by mˇelo vysokou reˇzii. Je potˇreba pro implementaci dalˇs´ıch n´ astroj˚ u. 1. Implementace ˇcten´ım a z´ apisem – pro v´ıce procesor˚ u moc sloˇzit´e 2. Speci´ aln´ı atomick´e instrukce – instrukce nedˇeliteln´eho ˇcten´ı a z´apisu • Test and Set (XCHG, Compare&Swap) • Load Linked & Store Conditional Probl´ emy: instrukce zatˇeˇzuj´ı pamˇet’ovou sbˇernici (st´ale nˇeco testuj´ı), u HT se blokuje druh´ y kontext aktivn´ım ˇ ˇcek´ an´ım, tak´e moˇznost st´ arnut´ı. Reˇsen´ım je vyuˇzit´ı cache a pro HT speci´aln´ı instrukce Dlouhodob´ e vylouˇ cen´ı vyuˇz´ıv´ a bin´ arn´ı z´amek (prvn´ı sekce zamkne a odemkne pˇri odchodu). Implementace pomoc´ı Test&Set. Pˇ r´ıstup do pamˇ eti: 1. Siln´ a konzistence – Pˇr´ıstupy v poˇrad´ı, v jak´em procesory ˇz´adaly je pomal´e. 2. TSO (Total Store Ordering) – Poˇrad´ı zachov´ano jen na jednom procesoru. 3. PSO (Partial Store Ordering) – Proh´azeno i na procesoru. Bari´ era je m´ısto, na kter´em ˇcekaj´ı procesy, dokud se nesejdou vˇsechny.
7
Bin´ arn´ı semafor a mutex
Bin´ arn´ı semafor je z´ amek stˇreˇz´ıc´ı kritickou sekci. • Operace init(), lock() a unlock(). • Nelze ˇc´ıst jeho hodnotu (nem´ a smysl, mohla by se zmˇenit potom). • Pasivn´ı ˇcek´ an´ı ve funkci lock(). • Operace lock() a unlock() jsou atomick´e. • Odemykat m˚ uˇze i jin´ y proces neˇz ten, co zamknul (pˇred´av´an´ı z´amku). • Siln´ y nebo slab´ y semafor (m´ a nebo nem´a st´arnut´ı). • Pouˇzit´ı jak pro vz´ ajemn´e vylouˇcen´ı tak sign´aly (nevhodn´e). Mutex je speci´ aln´ı bin´ arn´ı semafor pro vz´ ajemn´e vylouˇcen´ı, kter´ y nelze pˇred´avat. Implementace: pthread_mutex_t a funkce ..._init(m,v), ..._destroy(m), ..._lock(m), ..._unlock(m) a ..._trylock(m)
6
8
Obecn´ y semafor
Obecn´ y semafor obsahuje celoˇc´ıselnou hodnotu, pokud je nula, je zamˇcen a ˇcek´a se na nav´ yˇsen´ı hodnoty. • Operace down() se ˇcek´ a na hodnotu vˇetˇs´ı neˇz 0 a pak ji sn´ıˇz´ı a m˚ uˇze pokraˇcovat. • Operace up() zv´ yˇs´ı hodnotu a t´ım pˇr´ıpadnˇe odblokuje dalˇs´ı proces. • Pouˇz´ıv´ a pasivn´ı ˇcek´ an´ı ve funkci down(). • Tak´e definov´ ano jako P() a V() nebo wait() a signal(). • Pouˇzit´ı pro vz´ ajemn´e vylouˇcen´ı (inicializace na 1) nebo sign´aly (udrˇz´ı i poˇcet neobslouˇzen´ ych). Implementace v UNIXov´ ych syst´emech nen´ı, pouˇz´ıv´a se monitor. Obecnˇe je implementov´an pomoc´ı spinlocku a testov´ an´ı hodnoty ˇc´ıtaˇce. Pozastaven´e procesy se pˇrid´avaj´ı na konec fronty. Zamyk´ an´ı v jednom procesu (napˇr. putchar() v printf()) se implementuje jako ˇc´ıtaˇc rekurze. Pokud z´ amek zamkl stejn´ y proces tak se pouze mˇen´ı tento ˇc´ıtaˇc a ne z´amek. Simulace: bin´ arn´ı semafor lze simulovat dvˇema ˇc´ıseln´ ymi se sd´ılen´ ymi promˇenn´ ymi; obecn´ y lze simulovat tˇremi bin´ arn´ımi a sd´ılenou hodnotou
9
Inverze priority pˇ ri synchronizaci
Inverze priority nast´ av´ a v syst´emech s pl´ anov´an´ım s prioritou. Je-li v KS proces s niˇzˇs´ı prioritou a proces s vyˇsˇs´ı prioritou chce vstoupit, nem˚ uˇze to udˇelat d´ıky zamˇcen´ı KS. Z´aroveˇ n proces s niˇzˇs´ı prioritou nem˚ uˇze bˇeˇzet a odemknout, protoˇze proces s prioritou vyˇsˇs´ı m´a pr´avo na procesor. Dˇ edˇ en´ı priority pˇri vstupu do KS pˇridˇel´ı procesu prioritu nejvyˇsˇs´ıho procesu, kter´ y na KS ˇcek´a. + Priorita se nemˇen´ı, pokud je proces osamocen. - Je potˇreba pˇrepoˇc´ıt´ avat maxim´ aln´ı prioritu pˇri kaˇzd´em blokuj´ıc´ım zamyk´an´ı. Horn´ı mez priority pˇridˇel´ı procesu v KS prioritu pevnou. + Jednoduch´ a implementace, jedin´ a hodnota. - Priorita se zvyˇsuje vˇzdy, i kdyˇz to nen´ı nutn´e. Pouˇ zito pro bin´ arn´ı semafor, mutex, monitor; obecn´ y semafor a condition pˇresnˇe neurˇcuj´ı, kdo blokuje
10
Monitor
Monitor je abstraktn´ı datov´ y typ, kter´ y oddˇeluje ˇcek´an´ı a operace se sd´ılen´ ymi promˇenn´ ymi. Semafory jsou pˇr´ıliˇs obecn´e a maj´ı sloˇzit´e probl´emy. • Sd´ılen´e promˇenn´e dostupn´e pouze operacemi monitoru. • Operace jednoho monitoru (up(),down()) jsou vz´ajemnˇe vylouˇceny, atomick´e. ˇ an´ı je pasivn´ı, monitor obsahuje frontu condition. • Cek´ • Operace nad frontou wait() se monitoru vzd´a, signal() odblokuje ˇcekaj´ıc´ı proces.
7
• Pouˇz´ıv´ a se nam´ısto obecn´ ych semafor˚ u v UNIXu (vylouˇcen´ı i sign´aly). Probl´ em: proces, kter´ y odblokoval je jeˇstˇe v monitoru – bud’to se pozastav´ı a je odblokov´an aˇz dalˇs´ı proces dokonˇc´ı pr´ aci a nebo existuje operace notify().
11
Synchronizaˇ cn´ı n´ astroje dle POSIX 1003.1/1996
Pthreads: pthread_cond_t je typ pro condition (ˇcek´an´ı na situaci), kter´ y je vˇzdy pouˇzit se vz´ajemn´ ym vylouˇcen´ım typu pthread_mutex_t → spolu tvoˇr´ı monitor. Operace wait(): pthread_cond_wait(condition, mutex) atomicky uvoln´ı mutex a ˇcek´a na splnˇen´ı podm´ınky. Pˇ r´ıklad: pthread_mutex_lock(&mutex); while (suma == 0) { /* podm´ ınka splnˇ ena? */ pthread_cond_wait(&cond, &mutex); /* ne, ˇ cekat */ } /* kritick´ a sekce */ pthread_mutex_unlock(&mutex); Ostatn´ı operace: pthread_cond_signal(cond), pthread_cond_broadcast(cond). Implementace semaforu je jednoduch´ a, init() inicializuje condition a mutex, down() je pˇredchoz´ı pˇr´ıklad, kde v KS je sn´ıˇzen´ı sd´ılen´e hodnoty a up() zamkne mutex, zv´ yˇs´ı hodnotu, signalizuje zmˇenu podm´ınky a odemkne mutex. Opaˇcn´ y postup (semafor na monitor) je mnohem sloˇzitˇejˇs´ı.
12
Sign´ aly v Unixu
Sign´ aly jsou ve standardu ISO jazyka C, p˚ uvodem z UNIXu. Implicitn´ı chov´ an´ı po pˇr´ıjmu sign´ alu je vˇetˇsinou nastaveno na ukonˇcen´ı procesu, kromˇe sign´al˚ u SIGKILL a SIGSTOP lze pˇredefinovat. Zpracov´ an´ı sign´ alu: 1. Sign´ al je odesl´ an pomoc´ı vol´ an´ı kill(). 2. Pokud je proces v j´ adˇre a vol´ an´ı bylo pˇreruˇsiteln´e, konˇc´ı chybovˇe (EINTR) a proces pˇrech´az´ı zpˇet do uˇzivatelsk´eho reˇzimu. 3. Pokud vol´ an´ı nelze pˇreruˇsit, sign´ al se pouze zaznamen´a do doby pˇrechodu. 4. Pokud proces ˇcek´ a na pˇridˇelen´ı procesoru nebo bˇeˇz´ı, sign´al se zaznamen´a do doby pˇrechodu ze syst´emov´eho do uˇzivatelsk´eho reˇzimu (pˇrepnut´ı kontextu). 5. Pokud pˇri pˇrechodu do uˇzivatelsk´eho reˇzimu jsou ˇcekaj´ıc´ı sign´aly, oˇsetˇr´ı se: (a) Implicitnˇe – vˇetˇsinou ukonˇcen´ı procesu (b) Ignorov´ an´ı – lze nastavit, nˇekter´e impicitnˇe (c) Oˇsetˇruj´ıc´ı funkce – souˇc´ ast uˇzivatelsk´eho programu 8
Oˇ setˇ ruj´ıc´ı funkce ANSI C: • Tvar void (*sighandler_t)(int);, speci´aln´ı ukazatele SIG_DFL a SIG_IGN. • Nastavena funkc´ı sighandler_t signal(int signo, sighandler_t func);. • Pˇred vol´ an´ım funkce se nastaven´ı obnov´ı na SIG_DFL! • Funkce pak mus´ı znovu nastavit oˇsetˇren´ı – race condition. • Proces se pozastav´ı a n´ avratov´ a adresa se nastav´ı na oˇsetˇruj´ıc´ı funkci. • N´ avrat prob´ıh´ a standardnˇe pomoc´ı return nebo exit(), abort(), longjmp(). • Funkce standardn´ı knohovny nesm´ı b´ yt pouˇzity (kromˇe uveden´ ych v´ yˇse). • Nelze blokovat pˇr´ıjem sign´ alu po dobu oˇsetˇren´ı, takˇze se m˚ uˇze funkce volat paralelnˇe. • Nejsou reentrantn´ı. • V oˇsetˇren´ı sign´ alu m˚ uˇze tento pˇrij´ıt pˇred znovunastaven´ım. ˇ an´ı na pˇr´ıchod lze pouze pˇres sd´ılenou promˇennou (kterou nastav´ı oˇsetˇren´ı sign´alu) a sleep(), coˇz • Cek´ nen´ı bezpeˇcn´e. Oˇ setˇ ruj´ıc´ı funkce POSIX: • Tvar void (*sa_handler)(int);, alternativnˇe void (*sa_sigaction)(int, siginfo_t*, void*) (1003.1b). • Nastvena funkc´ı int sigaction(int sig, const struct sigaction* act, struct sigaction* oldact);. • P˚ uvodn´ı nastaven´ı je ozn´ ameno pˇres struct sigaction* oldact. • Nastaven´ı se nevrac´ı na SIG_DFL. • Po dobu vykon´ av´ an´ı je sign´ al blokov´an a pˇr´ıpadnˇe uloˇzen do fronty. Je moˇzn´e blokovat i dalˇs´ı sign´ aly. • Je moˇzn´e blokovat mnoˇzinu sign´ al˚ u i jindy – hlavnˇe pˇri nastaven´ı oˇsetˇren´ı je to nutnost. • Bezpeˇcn´e ˇcek´ an´ı na mnoˇzinu sign´ al˚ u pomoc´ı int sigsuspend(const sigset_t* sigset);. • Operace nad bitovou mnoˇzinou sign´al˚ u, nastaven´ı blokov´an´ı sigprocmask().
13
Pˇ ridˇ elov´ an´ı procesoru
Pˇ ridˇ elov´ an´ı procesoru znamen´ a pˇrepnut´ı kontextu mezi dvˇema procesy, vykon´av´a dispatcher. Pl´ anov´ an´ı (scheduling) je volba strategie a ˇrazen´ı proces˚ u do fronty. • Minimalizuje odezvu program˚ u (u desktopov´ ych syst´em˚ u menˇs´ı ˇcasov´a kvanta). • Efektivn´ı vyuˇzit´ı prostˇredk˚ u (u server˚ u delˇs´ı kvanta a priority). • Spravedliv´e pˇridˇelov´ an´ı. • Zv´ yˇsen´ı pr˚ uchodnosti (transakc´ı v ˇcase). Univerz´ aln´ı pl´ anovaˇ c je zaloˇzen na prioritˇe proces˚ u. • Interval rozhodov´ an´ı urˇcuje interval mezi vol´an´ım pl´anovaˇce. V tomto intervalu se nem˚ uˇze mˇenit poˇrad´ı proces˚ u. 1. Nepreemptivn´ı – proces bˇeˇz´ı do ukonˇcen´ı nebo ˇcek´an´ı, jednoduch´e, mal´a reˇzie, ale ˇspatn´ a odezva, nepouˇziteln´e pro realtime OS 9
2. Preemptivn´ı – procesu je odebr´an procesor po uplynut´ı kvanta, pˇr´ıchodu nov´eho procesu nebo odblokov´ an´ı prioritn´ıho procesu 3. Selektivn´ı preempce – nˇekter´e procesy mohou b´ yt pˇreruˇseny, nˇekter´e mohou pˇreruˇsovat, individu´ aln´ı nastaven´ı • Prioritn´ı funkce urˇcuje priortu procesu dle parametr˚ u. – Pamˇet’ov´e poˇzadavky, – spotˇrebovan´ y ˇcas procesoru, – doba ˇcek´ an´ı na procesor, – celkov´ a doba v syst´emu, – extern´ı priorita, – z´ atˇeˇz syst´emu, . . . • V´ybˇerov´e pravidlo vyb´ır´ a z v´ıce proces˚ u se stejnou prioritou. – N´ ahodnˇe – Cyklicky – FIFO Algoritmus FIFO (FCFS) je nepreemptivn´ı, nech´a bˇeˇzet vˇzdy prvn´ı proces, kter´ y vstoupil. + jednoduch´ y, mal´ a reˇzie pˇrepnut´ı + deterministick´ a odezva - kr´ atk´e procesy ˇcekaj´ı neˇz starˇs´ı dlouh´ y skonˇc´ı - dlouh´ a odezva a doba zpracov´ an´ı Algoritmus LIFO je nepreemptivn´ı, nech´ a bˇeˇzet nejnovˇejˇs´ı proces. - ohromn´e mnoˇzstv´ı st´ arnut´ı Algoritmus SJF (Shortest Job First) je nepreemptivn´ı, nech´a bˇeˇzet proces s nejkratˇs´ı dobou zpracov´an´ı. + celkov´ a doba zpracov´ an´ı je mal´ a + fronta ˇcekaj´ıc´ıch proces˚ u je mal´ a - mus´ı se odhadovat doba zpracov´ an´ı - dlouh´e procesy st´ arnou Algoritmus SRT (Shortest Remaining Time) je preemptivn´ı. nech´a bˇeˇzet proces s nejkratˇs´ı zb´yvaj´ıc´ı dobou zpracov´ an´ı. + minim´ aln´ı celkov´ a doba zpracov´ an´ı - mus´ı se odhadovat (v praxi nejde) doba zpracov´an´ı Algoritmus statick´ e priority je preemptivn´ı (kvanta) i nepreemptivn´ı, typick´ y pro realtime OS, dvˇe u ´rovnˇe priority (vyˇsˇs´ı je nepreemptivn´ı) Algoritmus Round Robin je preemptivn´ı (kvanta), cyklicky a stejnomˇernˇe pˇridˇeluje procesor. + dobr´ a odezva 10
+ naprosto spravedliv´ y - dlouh´ a doba zpracov´ an´ı - probl´em nastaven´ı kvanta (mal´e – velk´a reˇzie; velk´e – dlouh´a odezva) Algoritmus MLF (Multilevel Feedback) je preemptivn´ı (kvanta), m´a nˇekolik u ´rovn´ı priorit a na nich pracuje cyklicky. ´ • Uroveˇ n s vyˇsˇs´ı prioritou m´ a kratˇs´ı kvantum. • Pˇri vyprˇsen´ı kvanta se procesu priorita sn´ıˇz´ı (delˇs´ı kvantum pˇr´ıˇstˇe). • Pˇri pˇrekroˇcen´ı u ´rovnˇe bud’ konec nebo znovu (nic moc ˇreˇsen´ı). • Dlouho bˇeˇz´ıc´ı procesy maj´ı vˇzdy n´ızkou prioritu (nen´ı dobr´e). • Z´ aklad pro dalˇs´ı pl´ anovaˇce (podobn´ y ve FreeBSD 4.4, SVR4).
14
Uv´ aznut´ı pˇ ri pˇ ridˇ elov´ an´ı prostˇ redk˚ u
Pˇ ridˇ elov´ an´ı prostˇ redk˚ u se zab´ yv´ a obecn´ ymi prostˇredky (uplatn´ı se na pamˇet’, I/O, syst´emov´e prostˇredky apod.). Uv´ aznut´ı je ˇcek´ an´ı na ud´ alost, kter´ a nenastane. V tomto kontextu tedy na prostˇredek, kter´ y nebude nikdy pˇridˇelen. Prostˇ redky jsou opakovatelnˇe pouˇziteln´e (SR) nebo jednor´azovˇe pouˇziteln´e (CR). Kdy nast´ av´ a uv´ aznut´ı: 1. Zamyk´ an´ı z´ amk˚ u, semafor˚ u, soubor˚ u apod. – P1: lock(1);lock(2);
P2: lock(2);lock(1);
2. Pˇridˇelov´ an´ı pamˇeti (nebo buffer˚ u) – pokud je m´alo pamˇeti a procesy maj´ıc´ı p˚ ulku pamˇeti chtˇej´ı dalˇs´ı, uv´ aznou. 3. Zas´ıl´ an´ı zpr´ av – vˇsechny procesy ˇcekaj´ı na zpr´avy, kter´e vz´ajemnˇe poˇslou aˇz pot´e. Pˇ r´ıˇ ciny uv´ aznut´ı: • Pouze jeden proces m˚ uˇze prostˇredek pouˇz´ıvat, ostatn´ı ˇcekaj´ı. • Proces, kter´ y m´ a prostˇredky pˇridˇeleny se pˇri ne´ uspˇeˇsn´e alokaci dalˇs´ıch se tˇechto nevzd´a. • Proces z´ısk´ av´ a prostˇredky sekvenˇcnˇe. • Prostˇredek nem˚ uˇze b´ yt preemptivnˇe odebr´an, mus´ı jej odevzdat proces. Stav syst´ emu ud´ av´ a stav alokace prostˇredk˚ u, je mˇenˇen procesy pˇri poˇzadavku, z´ısk´an´ı a uvolnˇen´ı prostˇredku. • Proces je blokovan´ y, pokud nem˚ uˇze mˇenit stav syst´emu (ˇcek´a na prostˇredek). • Proces uv´ aznul, je-li blokovan´ y a ˇza´dn´e zmˇeny stavu jej neodblokuj´ı. • Omezen´ım pˇrechod˚ u mezi stavy tak, aby nedoˇslo k uv´aznut´ı se uv´aznut´ı ˇreˇs´ı. • Konstrukce grafu nen´ı v bˇeˇz´ıc´ım syst´emu moˇzn´a, jelikoˇz nejsou pˇredem zn´amy poˇzadavky.
11
15
Uv´ aznut´ı u SR prostˇ redk˚ u
SR prostˇ redky (Serially Reusable): • Prostˇredek se skl´ ad´ a z konstantn´ıho poˇctu stejn´ ych jednotek • Jednotka je bud’to voln´ a nebo pˇridˇelen´a. • Proces m˚ uˇze uvolnit jednotku, pokud ji m´a pˇridˇelenu. Graf alokace SR prostˇ redk˚ u ukazuje stav syst´emu pro SR prostˇredky. Prostˇredek m˚ uˇze b´ yt pˇridˇelen do maxim´ aln´ı kapacity a lze ˇz´ adat maxim´ alnˇe o jeho celou kapacitu.
Detekce uv´ aznut´ı hled´ a procesy, kter´e nejsou zablokov´any a mohou pˇriv´est syst´em do jin´eho stavu. Procesy jsou zablokov´ any, pokud jejich poˇzadavek nem˚ uˇze b´ yt uspokojen ani nemohou uvolnit prostˇredky. Redukce grafu nezablokovan´ ym procesem p odstraˇ nuje hrany z/do p pˇridˇelen´ım poˇzadovan´ ych prostˇredk˚ u a n´ aslednˇe jejich uvolnˇen´ım. Neredukovateln´ y graf nelze ˇz´ adn´ ym procesem redukovat – stav uv´aznut´ı. Plnˇ e redukovateln´ y graf je moˇzn´e naprosto oprostit od hran. Vˇsechny sekvence ostraˇ nov´an´ı jsou ekvivalentn´ı. Algoritmus detekce: postupnˇe proch´ az´ı graf a redukuje jej s vyuˇzit´ım znalosti poˇctu poˇzadovan´ ych a pˇridˇelen´ ych prostˇredk˚ u, sloˇzitost O(mn). Syst´ em s okamˇ zit´ ym pˇ ridˇ elen´ım pˇridˇeluje prostˇredky ihned, graf tak obsahuje pouze poˇzadavky, pak staˇc´ı hledat knot grafu. Syst´ em s prostˇ redky kapacity 1 uv´ azne pouze pˇri existenci cyklu grafu. Syst´ em s jednotkov´ ymi poˇ zadavky lze tak´e ovˇeˇrovat existenc´ı knotu. Zotaven´ı z uv´ aznut´ı – n´ asiln´ ym ukonˇcen´ım procesu nebo odebr´an´ım prostˇredk˚ u. Proces se vybere podle ceny (priorita, cena znovuproveden´ı, typ procesu). Po odebr´an´ı se zmˇen´ı stav (graf) a pˇrepoˇc´ıt´a se. Odebr´ an´ı prostˇ redk˚ u: 1. Pˇr´ım´e – blokuj´ıc´ı poˇzadavek na prostˇredky je ukonˇcen chybou ”prostˇredky odebr´any” 2. Nepˇr´ıme – n´ avrat k pˇredchoz´ımu stavu (rollback) Prevence proti uv´ aznut´ı omezuje pˇrechody tak, aby se uv´aznut´ı vyhnula: 12
1. Sd´ılen´ı prostˇredk˚ u (ale to poruˇsuje podm´ınku v´ yluˇcnosti). 2. Pˇridˇelit prostˇredky jedin´emu procesu (ale pˇr´ıliˇs omezuj´ıc´ı). 3. Jedin´ y poˇzadavek od procesu, dostane vˇzdy vˇsechny jednotky (neefektivn´ı). 4. Pˇri poˇzadavku dalˇs´ı jednotky se nejprve vˇsech vzd´at a ˇz´adat najednou (ne vˇzdy moˇzn´e). 5. Poˇzadavek je blokuj´ıc´ı pouze, pokud ˇz´adn´e jednotky proces nevlastn´ı, jinak neblokuj´ıc´ı a pˇri ne´ uspˇechu se mus´ı vzd´ at star´ ych, aby mohl zkusit znovu. 6. Prostˇredky ˇz´ adat oˇc´ıslovanˇe ve vzr˚ ustaj´ıc´ım poˇrad´ı, pak nem˚ uˇze vzniknout blokace (nejpouˇz´ıvanˇejˇs´ı). Bank´ eˇ r˚ uv algoritmus omezuje maxim´ aln´ı poˇcet poˇzadavk˚ u
16
Organizace pamˇ eti
Jeden u ´ sek pamˇ eti – LAP=FAP, OS m´ a pˇridˇelenu ˇc´ast, zbytek jednomu programu (MS-DOS), nen´ı ochrana, monoprogramov´ an´ı, posl´eze zavedeny segmenty Spoleˇ cn´ y adresov´ y prostor – vˇsechny programy maj´ı stejn´ y prostor mapovan´ y na fyzickou pamˇet’, pouze jsou zavedeny na jin´ a m´ısta. Bez ochrany, programy se mohou pˇrepisovat, je potˇreba relokace, ale jednoduch´ a spr´ ava a pˇridˇelov´ an´ı pamˇeti. Ochrana pamˇ eti pˇri multiprogramov´ an´ı ve spoleˇcn´ ych LAP – mezn´ı registr a chr´anˇen´ y reˇzim OS (programy maj´ı ale omezen´ y LAP). Oddˇ elen´ e adresov´ e prostory – kaˇzd´ y program m´a k dispozici cel´ y LAP, ochrana oddˇelen´ım pˇri mapov´ an´ı, ale mapov´ an´ı sloˇzitˇejˇs´ı (podpora hardware). Adresov´ y prostor j´ adra je oddˇelen´ y LAP (vol´an´ı j´adra mus´ı pˇrepoˇc´ıtat adresy), ale je tak´e sd´ılen´ y s volan´ ym programem (chr´ anˇen´ y). ´ Useky pevn´ e velikosti dˇel´ı FAP na pevn´e u ´seky, kam se programy musej´ı vl´ezt. Fronty ˇcekaj´ıc´ıch proces˚ u na u ´sek, intern´ı fragmentace. ´ Useky promˇ enn´ e velikosti mˇen´ı velikost dynamicky (spojov´an´ı sousedn´ıch voln´ ych nebo dˇelen´ı pˇri zaveden´ı programu), extern´ı fragmentace. Segmentace pˇridˇeluje kaˇzd´emu procesu u ´seky promˇenn´e velikosti, kter´e maj´ı adresu b´aze a limit. Tabulka segment˚ u m˚ uˇze b´ yt glob´ aln´ı nebo pro kaˇzd´ y proces zvl´aˇst’. Umoˇzn ˇuje r˚ uznou ochranu segment˚ u, ale st´ale extern´ı fragmentace. Str´ ankov´ an´ı dˇel´ı FAP na r´ amce a LAP na str´ anky stejn´e velikosti. Tabulka str´anek pak urˇcuje mapov´an´ı, logick´ a adresa urˇcuje ˇc´ıslo str´ anky. Je zamezeno extern´ı fragmentaci (v LAP), ochrana na u ´rovni str´anek. Segmentace se str´ ankov´ an´ım – segmenty jsou str´ankov´any
13
17
Str´ ankov´ an´ı
Tabulka str´ ankek obsahuje mj. ˇc´ıslo r´ amce, flagy z´apisu, syst´emov´e str´anky, oznaˇcen´ı dirty a pˇr´ıtomnosti v pamˇeti. Virtualizace – ne vˇsechny str´ anky jsou v pamˇeti, pokud se pouˇzije nepˇr´ıtomn´a str´anka, jedn´a se o v´ypadek str´ anky. V´ ypadek str´ anky vyvol´ a pˇreruˇsen´ı a syst´em mus´ı tabulku naˇc´ıst z disku (swap), pot´e se instrukce, kter´a v´ ypadek vyvolala restartuje. Nahrazovac´ı algoritmus urˇcuje, kter´ a str´ anka se m´a z pamˇeti ostranit, aby bylo m´ısto pro ˇz´adanou str´ anku. Organizace tabulky str´ anek: 1. Rychlost – pˇreklad pˇri kaˇzd´e instrukci → podpora hardware (TLB) 2. Velikost – pro 32b adresy a 4kB str´anky m´a tabulka 1M poloˇzek → u ´rovnˇe Translation Look-Aside Buffer (TLB) je vyrovn´avac´ı pamˇet’ v HW pro pˇreklad adres, posledn´ı adresy jsou ˇ ım vˇetˇs´ı u uloˇzeny v rychl´e (SRAM) asociativn´ı pamˇeti. Pˇr´ıstup je zredukov´an z 50ns na 5ns. C´ ´spˇeˇsnost TLB, t´ım rychlejˇs´ı pr˚ umˇern´ y pˇr´ıstup. Pˇri pˇrepnut´ı kontextu se TLB vypr´azdn´ı (SPARC ne, pˇrid´av´a poloˇzk´ am i ˇc´ıslo procesu). V´ıce´ urovˇ nov´ a organizace str´ anek – adresa obsahuje indexy tabulek, poloˇzky tabulek pak vyb´ıraj´ı b´azi n´ asleduj´ıc´ı tabulky. Intel – Page Directory a Page Table, AMD64 m´a 4 u ´rovnˇe. Inverzn´ı tabulka str´ anek indexuje podle r´amc˚ u a obsahuje, komu je r´amec pˇridˇelen a ˇc´ıslo str´anky, kterou proces vid´ı. Mnohem jednoduˇsˇs´ı tabulka a mal´a reˇzie, ale hled´an´ı je komplikovan´e a sd´ılen´ı pamˇeti jeˇstˇe v´ıce. Str´ ankovac´ı algoritmus ud´ av´ a, kdy a kolik str´anek se zavede, kter´e r´amce se jim pˇriˇrad´ı a pˇr´ıpadnˇe, kter´e str´ anky maj´ı b´ yt odstranˇeny. Snaha minimalizovat v´ ypadky (nahrazen´ım nepouˇz´ıvan´ ych apod.). V´ ybˇ er zav´ adˇ en´ ych str´ anek je moˇzn´e prov´adˇet prefetchingem (dopˇredu), pouˇz´ıv´a se zav´adˇen´ı na ˇz´adost (pˇri v´ ypadku). Poˇ cet zav´ adˇ en´ ych str´ anek: cel´ y LAP (neefektivn´ı), jedin´a str´anka (neefektivn´ı), str´anky a okol´ı (pˇredv´ıd´ a se pˇr´ıstup na sousedn´ı str´ anky). Um´ıst’ov´ an´ı str´ anek nem´ a vliv na v´ ypadky, ale na rychlost odkl´ad´an´ı (souvisl´ y kus se odloˇz´ı rychleji). 14
Swapping je umist’ov´ an´ı vyˇrazen´ ych str´ anek na disk do swapu (swap se nemus´ı pouˇz´ıt, ale pak nelze str´ anky vyˇradit a dojde pamˇet’). Thrashing je stav, kdy poˇcet v´ ypadk˚ u pˇrekraˇcuje pˇr´ıpustnou mez, vˇetˇsinu v´ ykonu spotˇrebuje reˇzie str´anek (nejen algoritmus, ale i I/O swapu).
18
Nahrazovac´ı algoritmy
Nahrazovac´ı algoritmus urˇcuje, kter´e str´anky vyˇradit z pamˇeti, snaha o minimalizaci n´asledn´ ych v´ ypadk˚ u. Probl´em je, ˇze nezn´ a n´ asleduj´ıc´ı sled str´anek, takˇze pouze odhaduje z minulosti. Klasifikace: 1. Lok´ aln´ı – vyˇrazuje pouze str´ anky procesu, kter´ y nyn´ı chce str´anku zav´est 2. Glob´ aln´ı – nerozliˇsuje str´ anky podle procesu 1. Pevn´y poˇcet r´ amc˚ u – poˇcet str´ anek v pamˇeti je stejn´ y 2. Promˇenn´y poˇcet r´ amc˚ u – poˇcet str´ anek v pamˇeti se mˇen´ı Princip lokality • Prostorov´ a lokalita – pˇri bˇehu programu, nejsou najednou potˇreba vˇsechny str´anky LAP, ale je vysok´ a pravdˇepodobnost, ˇze n´ asleduj´ıc´ı adresa bude smˇeˇrovat do stejn´e nebo sousedn´ı str´anky (sekvenˇcn´ı k´ od, struktury a pole, promˇenn´e jsou u sebe). ˇ • Casov´ a lokalita – pˇri bˇehu programu se nˇekter´e promˇenn´e pouˇz´ıvaj´ı opakovanˇe (cykly, funkˇcn´ı promˇenn´e) Neplat´ı-li princip lokality (optimalizace k´ odu a dat), sebelepˇs´ı pouˇz´ıvan´ y algoritmus nebude fungovat.
19
Nahrazovac´ı algoritmy s pevn´ ym poˇ ctem r´ amc˚ u
Optim´ aln´ı algoritmus: • Vyb´ır´ a str´ anku, kter´ a bude nejd´ele nepouˇz´ıv´ana. • Vyˇzaduje znalost budoucnosti (nen´ı re´aln´ y). • Minim´ aln´ı moˇzn´ y poˇcet v´ ypadk˚ u str´anek. LRU (Least Recently Used): • Vyb´ır´ a str´ anku, kter´ a byla nejd´ele nepouˇzita. • Aproximuje optim´ aln´ı algoritmus (princip lokality). • Implementov´ an jako z´ asobn´ık, pˇri pouˇzit´ı pˇresun nahoru, vyhazuje se nejspodnˇejˇs´ı. NRU (Not Recently Used): • Aproximuje LRU jedn´ım bitem. • Pˇri zaveden´ı a pouˇzit´ı je bit nastaven. • Bit je nulov´ an po uplynut´ı intervalu. 15
LFU (Least Frequently Used): • Odstranˇena nejm´enˇe pouˇz´ıvan´ a str´ anka. • M˚ uˇze ale nahradit i pr´ avˇe pouˇzitou str´anku. • V pˇr´ıpadˇe rovnosti pouˇzije LRU. FIFO: • Odstran´ı str´ anku, kter´ a byla nejd´ele v pamˇeti. • Mohla tam b´ yt proto, ˇze je neust´ ale pouˇz´ıv´ana. LIFO • Odstran´ı str´ anku, kter´ a je v pamˇeni nejkratˇs´ı dobu. • Dojde do stavu, kdy se pouze vyhazuje posledn´ı str´anka a ostatn´ı z˚ ust´avaj´ı. Clock: • Cyklick´ y seznam str´ anek s jednobitov´ ym pˇr´ıznakem. • Ukazatel na aktu´ aln´ı pozici. • Pˇri hled´ an´ı se testuje bit. • Je-li nastaven, vynuluje se a posune ukazatel. • Pokud nen´ı nastaven, naˇsla se str´ anka (a posune se ukazatel). Second Chance NRU: • Zaloˇzen na Clock, ale m´ a kromˇe pˇr´ıznaku pouˇzit´ı i pˇr´ıznak modifikace. • Nen´ı-li bit uˇzit´ı nastaven a je nastaven z´apisov´ y, str´anka se pouze zap´ıˇse na disk, bit se vynuluje a posune se ukazatel.
20
Nahrazovac´ı algoritmy s promˇ enn´ ym poˇ ctem r´ amc˚ u
VMIN: • Optim´ aln´ı nerealizovateln´ y algoritmus. • Udrˇzuje pouze str´ anky, kter´e budou potˇreba (znalost budoucnosti). WS (Working Set): • V pamˇeti je pouze pracovn´ı mnoˇzina str´anek, tedy str´anky, kter´e byly pouˇzity v dan´em intervalu. • Sloˇzit´ a implementace, pˇri kaˇzd´em odkazu str´anky (nejen v´ ypadku) se mus´ı aktualizovat. Page Fault Frequency: • Vol´ı velikost pracovn´ı mnoˇziny podle frekvence v´ ypadk˚ u. • Pˇri vysok´e frekvenci v´ ypadk˚ u je moˇzn´e pˇridat dalˇs´ı prvek mnoˇziny. • Pˇri n´ızk´e frekvenci se odeberou vˇsechny str´anky nepouˇzit´e od posledn´ıho v´ ypadku.
16
21
Str´ ankov´ an´ı v praxi
Pamˇ et’ j´ adra je potˇrebn´ a okamˇzitˇe (napˇr. pˇri I/O), nem˚ uˇze se ˇcekat na nahrazen´ı. Nahrazov´ an´ı prob´ıh´ a uˇz dr´ıve neˇz nastanou v´ ypadky (vˇetˇsinou 75%). Tak´e se udrˇzuje seznam aktivn´ıch a neaktivn´ıch str´ anek. Zamyk´ an´ı str´ ankek je nutn´e pro DMA a realtime OS. Privilegovan´e funkce mlock() a munlock(). Spouˇ stˇ en´ı procesu vol´ an´ım fork() vytv´ aˇr´ı kopii procesu a jeho LAP, prostˇredk˚ u apod. Vˇetˇsinou ale n´ asleduje vol´ an´ı exec(), kter´e LAP pˇrep´ıˇse naˇcten´ ym k´odem programu – zbyteˇcn´a kopie. Vol´ an´ı vfork(): pozastrav´ı rodiˇce do vol´ an´ı exec() a sd´ıl´ı jeho LAP. Nebezpeˇcn´e, pokud se ˇspatnˇe pouˇzije. Copy on Write je kopie str´ anky takov´ a, ˇze ukazuje na stejn´e m´ısto v pamˇeti, ale pokud dojde k z´apisu, vytvoˇr´ı se kopie na m´ıstˇe jin´em a teprve tam se zap´ıˇse. Umoˇzn ˇuje sd´ılet cel´e tabulky str´anek (efektivita). Sd´ılen´ı str´ anek: • Sd´ılen´ı k´ odu – str´ anky jen pro ˇcten´ı, instance program˚ u sd´ılej´ı, uˇsetˇr´ı mnoho pamˇeti • Poziˇcnˇe nez´ avisl´y k´ od – adresy jsou relativn´ı podle GOF (Global Offset Table), vyuˇz´ıv´a EBX jako b´ azovou adresu, Wndows nemaj´ı, v´ıce instanc´ı na r˚ uzn´ ych relokovaln´ ych adres´ach. • Explicitn´ı sd´ılen´ı – na poˇz´ ad´ an´ı procesu, vyuˇzito pro komunikaci, r˚ uzn´a rozhran´ı SVR3: sd´ılen´ a pamˇet’ oznaˇcen´ a kl´ıˇcem shmget(), shmat(), omezen´a velikost. BSD 4.4: mapov´ an´ı soubor˚ u do LAP, ale sd´ılen´ı pouze s fork() soubory, mmap(). POSIX 1003.1b: mapov´ an´ı pˇres soubory, ale lze vytvoˇrit sd´ılenou pamˇet’ kl´ıˇcem pomoc´ı shm_open(). Virtualizace soubor˚ u – pouˇzit´ım mmap() lze soubor namapovat jako souˇc´ast LAP, pak se chov´a jako swapovac´ı m´ısto dan´e ˇc´ asti pamˇeti. Uˇsetˇr´ı se syst´emov´a vol´an´ı read() a write(). V´ yhodn´e pro n´ahodn´ y pˇr´ıstup a pˇr´ıstup po mal´ ych ˇc´ astech, ale zab´ır´ a v´ıce pamˇeti. Lze mapovat jen pro ˇcten´ı (MAP_PRIVATE) a pak se swapuje do swapu.
22
Syst´ emy soubor˚ u
Soubor je abstraktn´ı jednotka obsahuj´ıc´ı data, kter´a m´a jednoznaˇcnou identifikaci. Fyzick´ a abstrakce souboru: I/O po sektorech disku, adresa fyzick´eho sektoru, bez pr´av a ochran Logick´ a abstrakce souboru: I/O po bajtech (nebo z´aznamech), identifikace souboru, pr´ava souboru Syst´ em soubor˚ u poskytuje: strukturu soubor˚ u, alokaci diskov´eho prostoru, souborov´e operace, ochranu Logick´ a struktura souboru je na u ´rovn´ı j´adra OS 1. Bez struktury – pouh´e pole bajt˚ u (Unix) 2. Logick´e z´ aznamy s pevnou d´elkou – rychl´ y n´ahodn´ y pˇr´ıstup, lehk´e zmˇeny, nevyuˇzit prostor 3. Logick´e z´ aznamy s promˇennou d´elkou – pomal´ y pˇr´ıstup, ˇspatn´a aktualizace, pln´e vyuˇzit´ı 4. Indexsekvenˇcn´ı soubory – z´ aznamy promˇenn´e d´elky a index podle kl´ıˇce 17
Vnitˇ rn´ı struktura souboru je na u ´rovni I/O • Soubor je pole alokaˇcn´ıch blok˚ u. • Alokaˇcn´ı blok je nˇekolik sektor˚ u. • Je potˇreba pˇreklad z logick´eho adresov´an´ı na adresy blok˚ u. • Velikost alokaˇcn´ıho bloku ovlivˇ nuje rychlost a vyuˇzit´ı m´ısta. Souvisle alokovan´ e soubory: + rychl´ y pˇr´ıstup k cel´emu souboru i pˇri n´ahodn´em pˇr´ıstupu - nutn´ a prealokace m´ısta - pˇri alokaci po u ´sec´ıch velk´ a intern´ı fragmentace - probl´em vkl´ ad´ an´ı dat jinam neˇz na konec Soubory jako line´ arn´ı seznamy: + jednoduch´e vkl´ ad´ an´ı, pˇrid´ av´ an´ı, ruˇsen´ı dat - n´ ahodn´ y pˇr´ıstup pˇr´ıliˇs pomal´ y, nutn´e proch´azen´ı - obrovsk´ a extern´ı fragmentace Indexsekvenˇ cn´ı uloˇ zen´ı souboru: • Index obsahuje seznam alokaˇcn´ıch blok˚ u a jejich offset. • Tabulka m˚ uˇze b´ yt velk´ a... • Glob´ aln´ı tabulka (FAT) • V´ıce´ urovˇ nov´ a tabulka (UFS) je rychlejˇs´ı, ale nev´ yhodn´a pro mal´e soubory. • Pro mal´e soubory se index nepouˇzije (sloˇzitˇejˇs´ı implementace). • S promˇennou alokaˇcn´ı jednotkou – XFS, JFS Alokace diskov´ eho prostoru v OS mus´ı nejen volit um´ıstˇen´ı a velikost jednotek, ale tak´e m´ıt pˇrehled o voln´em m´ıstˇe a rozloˇzen´ı subor˚ u. • Voln´e m´ısto – souvisl´ a alokace nebo alokace pevn´ ych blok˚ u eviduje voln´e bloky; alokace promˇenn´e d´elky mus´ı evidovat voln´e u ´seky a spojovat je nebo dˇelit • Okamˇzik alokace – prealokace omezuje fragmentaci souboru, ale neˇsetˇr´ı m´ısto; dynamick´a alokace pˇri z´ apisu m˚ uˇze vyvolat konflikt s jin´ ym souborem; odloˇzen´a alokace ˇcek´a aˇz na uloˇzen´ı str´anky pamˇeti • Velikost jednotky – 512B vyuˇzije prostor na 95%, ale vˇetˇs´ı reˇzie Organizace soubor˚ u b´ yv´ a hierarchick´ a, je nutn´ y (v´ıce´ urovˇ nov´ y) adres´aˇr soubor˚ u (mapuje jm´eno na identifikaci). Vyhled´ av´ an´ı podle seznamu, stromu nebo hash tabulky. Operace se soubory: • Zpˇr´ıstupnˇen´ı – vyhled´ an´ı souboru, ˇcten´ı metadat ˇ ı a z´ • Cten´ apis – na z´ akladˇe identifikace • Manipulace – zmˇeny metadat 18
Um´ıstˇ en´ı metadat m˚ uˇze b´ yt pˇr´ımo v adres´aˇri nebo jak zvl´aˇstn´ı datov´a jednotka (i-node). Odolnost FS proti v´ ypadku je vynucena existenc´ı v´ıce m´ıst, kde je nutn´a zmˇena (smaz´an´ı souboru mus´ı zmˇenit adres´ aˇr, seznam voln´ ych blok˚ u a seznam i-node). • Synchronn´ı zmˇeny – v poˇrad´ı, pˇri v´ ypadku lze detekovat a opravit, hodnˇe pomal´e • Soft metadata update – pokud I/O vykon´a nˇeco asynchronnˇe, zmˇen´ı se ostatn´ı data tak, aby to reflektovala • Transakˇcn´ı zpracov´ an´ı – vyˇzaduje ˇzurn´alov´an´ı
19
