Z´ aklady operaˇ cn´ıch syst´ em˚ u 1
Rozdˇ elen´ı OS, architektura a komponenty OS, z´ akladn´ı funkce OS
Operaˇcn´ı syst´em je v informatice z´ akladn´ı programov´e vybaven´ı poˇc´ıtaˇce (tj. software), kter´e je zavedeno do pamˇeti poˇc´ıtaˇce pˇri jeho startu a z˚ ust´ av´ a v ˇcinnosti aˇz do jeho vypnut´ı. Skl´ad´a se z j´adra (kernel) a pomocn´ ych syst´emov´ ych n´ astroj˚ u. Hlavn´ım u ´kolem operaˇcn´ıho syst´emu je zajistit uˇzivateli moˇznost ovl´adat poˇc´ıtaˇc, vytvoˇrit pro procesy stabiln´ı aplikaˇcn´ı rozhran´ı (API) a pˇridˇelovat jim syst´emov´e zdroje. Operaˇcn´ı syst´em je velmi komplexn´ı software, jehoˇz v´ yvoj je mnohem sloˇzitˇejˇs´ı a n´ aroˇcnˇejˇs´ı, neˇz v´ yvoj obyˇcejn´ ych program˚ u.
1.1
Rozdˇ elen´ı OS
Dle u ´ rovnˇ e sd´ılen´ı CPU • Jednoprocesov´ y – MS DOS, v dan´em ˇcase v pamˇeti aktivn´ı 1 program • Multiprocesov´ y – Efektivnost vyuˇzit´ı zdroj˚ u – Pr´ace v´ıce uˇzivatel˚ u Dle typu interakce • D´ avkov´ y syst´em – Sekvenˇcn´ı d´ avky, nen´ı interakce • Interaktivn´ı – Interakce uˇzivatel – u ´loha – V´ıceprocesov´e – interakce max. do nˇekolika sekund (Win, Linux, ..) Dle velikosti HW • Superpoˇc´ıtaˇc • telefon • ˇcipov´ a karta M´ıra distribuovanosti • Klasick´e - centralizovan´e 1 and more CPU • Paraleln´ı • S´ıt’ov´e • Distribuovan´e virtu´ aln´ı uniprocesor Uˇzivatel nev´ı kde bˇeˇz´ı programy, kde jsou soubory
1.2
Architektura a komponenty OS
Podle architektury operaˇcn´ıho syst´emu se typicky rozliˇsuje mikrokernel (mikroj´adro, j´adro je velice jednoduch´e a obsahuje pouze zcela z´ akladn´ı funkce, zbytek operaˇcn´ıho syst´emu je mimo toto j´adro v aplikac´ıch) a makrokernel (monolitick´e j´ adro, j´ adro je rozs´ ahl´e, obsahuje velk´e mnoˇzstv´ı funkc´ı pro vˇsechny aspekty ˇcinnosti operaˇcn´ıho syst´emu vˇcetnˇe napˇr´ıklad souborov´eho syst´emu). Jak´ ymsi kompromisem je modul´arn´ı j´adro, kter´e je fakticky makroj´ adrem (cel´e bˇeˇz´ı v privilegovan´em reˇzimu) ovˇsem jeho znaˇcn´a ˇc´ast je tvoˇrena takzvan´ ymi moduly, kter´e je moˇzn´e pˇrid´ avat a odeb´ırat za bˇehu syst´emu. 1.2.1
Komponenty OS
• procesy • spr´ ava hlavn´ı pamˇeti • soubory • I/O subsyst´em • s´ıt’ (networking) • ochrana a bezpeˇcnost • uˇzivatelsk´e rozhran´ı 1
1.3
Funkce
• Operaˇcn´ı syst´em pln´ı tˇri z´ akladn´ı funkce: • ovl´ ad´ an´ı poˇc´ıtaˇce – umoˇzn ˇuje uˇzivateli spouˇstˇet programy, pˇred´avat jim vstupy a z´ısk´avat jejich v´ ystupy s v´ ysledky • abstrakce hardware – vytv´ aˇr´ı rozhran´ı pro programy, kter´e abstrahuje ovl´ad´an´ı hardware a dalˇs´ıch funkc´ı do snadno pouˇziteln´ ych funkc´ı (API) • spr´ ava prostˇredk˚ u – pˇridˇeluje a odeb´ır´ a proces˚ um syst´emov´e prostˇredky poˇc´ıtaˇce 1.3.1
Ovl´ ad´ an´ı poˇ c´ıtaˇ ce
Pˇri definici operaˇcn´ıho syst´emu se obvykle omezuje ovl´ad´an´ı poˇc´ıtaˇce na schopnost spustit program, pˇredat mu vstupn´ı data a umoˇznit v´ ystup v´ ysledk˚ u na v´ ystupn´ı zaˇr´ızen´ı. Nˇekdy je vˇsak pojem operaˇcn´ı syst´em rozˇs´ıˇren i na grafick´e uˇzivatelsk´e rozhran´ı, coˇz m˚ uˇze b´ yt z d˚ uvod˚ u marketingov´ ych, ale i probl´emu nejasn´e hranice mezi operaˇcn´ım syst´emem a aplikacemi. U syst´em˚ u, kter´e disponuj´ı jedin´ ym grafick´ ym rozhran´ım (Microsoft Windows, Symbian OS, . . . ) je ˇcasto grafick´e rozhran´ı zahrnov´ ano do operaˇcn´ıho syst´emu. U syst´em˚ u, kde je uˇzivatelsk´e rozhran´ı moˇzn´e vytvoˇrit nˇekolika nez´ avisl´ ymi zp˚ usoby nebo r˚ uzn´ ymi aplikacemi, je bˇeˇzn´e nepovaˇzovat ho za souˇc´ast syst´emu (unixov´e syst´emy). 1.3.2
Abstrakce hardware
Operaˇcn´ı syst´em skr´ yv´ a detaily ovl´ ad´ an´ı jednotliv´ ych zaˇr´ızen´ı v poˇc´ıtaˇci (tzv. hardware) a definuje standardn´ı rozhran´ı pro vol´ an´ı syst´emov´ ych sluˇzeb tak, ˇze vytv´aˇr´ı abstraktn´ı vrstvu s jednoduch´ ymi funkcemi (tzv. API), kter´e vyuˇz´ıvaj´ı program´ atoˇri aplikac´ı. T´ım nejen zjednoduˇsuje program´ator˚ um vytv´aˇren´ı program˚ u, ale umoˇzn ˇuje program˚ um pracovat i se zaˇr´ızen´ımi, kter´e v dobˇe vzniku programu neexistovaly (napˇr´ıklad z hlediska program´ atora nen´ı rozd´ıl mezi otevˇren´ım souboru na pevn´em disku, CD, DVD, flash, s´ıt’ov´em disku nebo Blu-ray). Nˇekdy je uvnitˇr operaˇcn´ıho syst´emu vytv´ aˇrena podobn´ a abstraktn´ı mezivrstva, kter´a usnadˇ nuje programov´an´ı ovladaˇc˚ u jednotliv´ ych zaˇr´ızen´ı (tzv. HAL, anglicky Hardware Abstraction Layer). 1.3.3
Spr´ ava zdroj˚ u
Operaˇcn´ı syst´em pˇridˇeluje spuˇstˇen´ ym program˚ um syst´emov´e prostˇredky (operaˇcn´ı pamˇet’, procesor, pevn´ y disk, vstupnˇe-v´ ystupn´ı zaˇr´ızen´ı). V pˇr´ıpadˇe potˇreby m˚ uˇze operaˇcn´ı syst´em proces˚ um pˇridˇelen´e prostˇredky n´asilnˇe odebrat (preempce). Operaˇcn´ı syst´em vyuˇz´ıv´ a schopnosti procesoru k ochranˇe sebe sam´eho, ale i k oddˇelen´ı pracovn´ıho prostoru jednotliv´ ych proces˚ u.
2
Vyvol´ an´ı sluˇ zeb OS, zpracov´ an´ı pˇ reruˇ sen´ı
Syst´em nastav´ı ˇcasovaˇc – pravidelnˇe pˇreruˇsen´ı Na pˇredem definovan´em m´ıstˇe – adresa obsluˇzn´eho programu pˇreruˇsen´ı CPU po pˇ r´ıchodu pˇ reruˇ sen´ı provede: • Uloˇz´ı ˇc´ıtaˇc instrukc´ı PC do z´ asobn´ıku • Naˇcte do PC adresu obsluˇz. programu pˇreruˇsen´ı • Pˇrepne do reˇzimu j´ adra • Vyvol´ ana obsluha pˇreruˇsen´ı – Uloˇz´ı obsah registr˚ u do z´ asobn´ıku – Nastav´ı nov´ y z´ asobn´ık • Pl´ anovaˇc nastav´ı proces jako ready, vybere nov´ y proces pro spuˇstˇen´ı • Pˇrepnut´ı kontextu – Nastav´ı mapu pamˇeti nov´eho procesu 2
– Nastav´ı z´ asobn´ık, naˇcte obsah registr˚ u – Provede n´ avrat z pˇreruˇsen´ı – RET (do PC adresa ze z´asobn´ıku, pˇrepne do uˇzivatelsk´eho reˇzimu)
3
Proces, implementace procesu, konstrukce pro vytv´ aˇ ren´ı proces˚ u
3.1
Proces
• instance bˇeˇz´ıc´ıho programu • Adresn´ı prostor procesu – MMU zajiˇstuje soukrom´ı – k´ od spustiteln´eho programu, data, z´asobn´ık • S procesem sdruˇzeny registry a dalˇs´ı info potˇrebn´e k bˇehu procesu = stavov´e informace – registry – ˇc´ıtaˇc instrukc´ı PC, ukazatel z´asobn´ıku SP, univerz´aln´ı registry
3.2
Implementace procesu
• Vytvoˇren´ı nov´eho procesu – fork v UNIXu, CreateProcess ve Win32 • Ukonˇcen´ı procesu – exit v UNIXu, ExitProcess ve Win32 ˇ an´ı na dokonˇcen´ı potomka • Cek´ – wait (waitpid) v UNIXu, WaitForSingleObject ve Win32 • Alokace a uvolnˇen´ı pamˇeti procesu • Komunikace mezi procesy (IPC) • Identifikace ve v´ıceuˇzivatel. syst´emech – identifik´ ator uˇzivatele (UID) – skupina uˇzivatele (GID) – proces bˇeˇz´ı s UID toho, kdo ho spustil – v UNIXu – UID, GID – cel´ a ˇc´ısla • Probl´em uv´ıznut´ı procesu
4
Paraleln´ı procesy, prostˇ redky pro popis paraleln´ıch proces˚ u, vl´ akna • Bˇeˇz´ıc´ı SW – organizov´ an jako mnoˇzina sekvenˇcn´ıch proces˚ u • Proces – bˇeˇz´ıc´ı program vˇcetnˇe obsahu ˇc´ıtaˇce instrukc´ı, registr˚ u, promˇenn´ ych; bˇeˇz´ı ve vlastn´ı pamˇeti • Koncepˇcnˇe kaˇzd´ y proces – vlastn´ı virtu´ aln´ı CPU • Re´ aln´ y procesor – pˇrep´ın´ a mezi procesy (multiprogramov´an´ı) • Pˇredstava mnoˇziny proces˚ u bˇeˇz´ıc´ıch (pseudo)paralelnˇe
Z´ akladn´ı stavy procesu • Bˇeˇz´ıc´ı (running) – skuteˇcnˇe vyuˇz´ıv´ a CPU, vykon´av´a instrukce 3
• Pˇripraven (ready, runnable) – doˇcasnˇe pozastaven, aby mohl jin´ y proces pokraˇcovat • Blokov´ an (blocked, waiting) – neschopn´ y bˇehu, dokud nenastane extern´ı ud´alost Vl´ akna • Vl´ akna v procesu sd´ılej´ı adresn´ı prostor, otevˇren´e soubory (atributy procesu) • Vl´ akna maj´ı soukrom´ y ˇc´ıtaˇc instrukc´ı, obsah registr˚ u, soukrom´ y z´asobn´ık • Mohou m´ıt soukrom´e lok´ aln´ı promˇenn´e • P˚ uvodnˇe vyuˇz´ıv´ ana zejm´ena pro VT v´ ypoˇcty na multiprocesorech (kaˇzd´e vl´akno vlastn´ı CPU, spoleˇcn´ a data)
5
Probl´ em kritick´ e sekce • Sekvenˇcn´ı procesy komunikace pˇres spoleˇcnou datovou oblast • kritick´ a sekce (critical section, region) m´ısto v programu, kde je prov´adˇen pˇr´ıstup ke spoleˇcn´ ym dat˚ um • u ´loha – jak implementovat, aby byl v kritick´e sekci v dan´ y okamˇzik pouze 1 proces
ˇ sen´ı ˇ Reˇ casov´ eho soubˇ ehu - pravidla • Vz´ ajemn´e vylouˇcen´ı - ˇz´ adn´e dva procesy nesmˇej´ı b´ yt souˇcasnˇe uvnitˇr sv´e kritick´e sekce • Proces bˇeˇz´ıc´ı mimo kritickou sekci nesm´ı blokovat jin´e procesy (napˇr. jim br´anit ve vstupu do kritick´e sekce) ˇ adn´ • Z´ y proces nesm´ı na vstup do sv´e kritick´e sekce ˇcekat nekoneˇcnˇe dlouho (jin´ y vstupuje opakovanˇe, neum´ı se dohodnout v koneˇcn´em ˇcase, kdo vstoup´ı prvn´ı) Moˇ znosti ˇ reˇ sen´ı • Z´ akaz pˇreruˇsen´ı • Aktivn´ı ˇcek´ an´ı • Zablokov´ an´ı procesu
6
Prosˇ redky pro synchronizaci proces˚ u
6.1
Aktivn´ı ˇ cek´ an´ı
• Pr˚ ubˇeˇzn´e testov´ an´ı promˇenn´e ve smyˇcce, dokud nenabude oˇcek´avanou hodnotu • Vˇetˇsinou se snaˇz´ıme vyhnout pl´ ytv´ a ˇcasem CPU • Pouˇz´ıv´ a se, pokud pˇredpokl´ ad´ ame kr´ atk´e ˇcek´an´ı spin lock
6.2
Spin lock s instrukc´ı TSL
• hw podpora • vˇetˇsina poˇc´ıtaˇc˚ u – instrukci, kter´ a otestuje hodnotu a nastav´ı pamˇet’ov´e m´ısto v jedn´e nedˇeliteln´e operaci • operace Test and Set Lock – TSL, TS: • TSL R, lock – – – –
R je registr CPU lock – buˇ nka pamˇeti, 0 false nebo 1 true; boolean; prov´ad´ı: LD R, lock LD lock, 1
• Probl´em inverze priorit, proces s niˇzˇs´ı prioritou blokuje procesu s vyˇsˇs´ı vstup 4
7
Semafory, jejich pouˇ zit´ı a implementace
Semafor je synchronizaˇcn´ı primitivum obsahuj´ıc´ı celoˇc´ıseln´ y ˇc´ıtaˇc, kter´ y si lze pˇredstavit napˇr´ıklad jako poˇc´ıtadlo voln´ ych prostˇredk˚ u. Poskytuje atomick´e operace up“ a down“. Operace down“ sn´ıˇz´ı ˇc´ıtaˇc o jedniˇcku, v pˇr´ıpadˇe, ” ” ” ˇze uˇz je nulov´ y (nedost´ av´ a se prostˇredk˚ u), se proces zablokuje a pˇrid´a do fronty proces˚ u ˇcekaj´ıc´ıch na dan´ y semafor. Operace up“ zkontroluje frontu, a v pˇr´ıpadˇe, ˇze je nepr´azdn´a, vybere jeden proces ˇcekaj´ıc´ı ve frontˇe a odblokuje ” jej (ten pak pokraˇcuje za svou operac´ı down“); je-li fronta pr´azdn´a, zv´ yˇs´ı hodnotu ˇc´ıtaˇce o jedniˇcku. ” Pˇ r´ıklad implementace v pseudok´ odu: P(Semaphore s) { ˇcekej dokud nen´ı s > 0 pak s = s-1; /* mus´ı b´ yt atomick´e jakmile je zjiˇstˇeno, ˇze s > 0 */ } V(Semaphore s) { s = s+1; /* mus´ı b´ yt atomick´e */ } Init(Semaphore s, Integer v) { s = v; } N´ azvy operac´ı P a V jsou tradiˇcn´ı a poch´ az´ı od Edsgera Dijkstry, kter´ y semafory vymyslel. Jsou odvozeny od holandsk´ ych slov prolaag“ (sloˇzeno z probeer te verlagen, zkus a sniˇz) a verhoog“, zvyˇs. ” ”
8
Monitory
Monitor je synchronizaˇcn´ı primitivum, kter´e se pouˇz´ıv´a pro ˇr´ızen´ı pˇr´ıstupu ke sd´ılen´ ym prostˇredk˚ um. Jeho zvl´ aˇstnost´ı je, ˇze jde o speci´ aln´ı konstrukci programovac´ıho jazyka (mus´ı ho tedy implementovat pˇrekladaˇc), typicky implementovanou pomoc´ı jin´eho synchronizaˇcn´ıho primitiva. V´ yhodou monitoru oproti jin´ ym primitiv˚ um je jeho vysoko´ urovˇ novost – snadnˇeji se pouˇz´ıv´ a a je bezpeˇcnˇejˇs´ı. Pˇri jeho pouˇzit´ı je m´enˇe pravdˇepodobn´e, ˇze program´ ator udˇel´ a chybu. Monitor se skl´ ad´ a z dat, ke kter´ ym je potˇreba ˇr´ıdit pˇr´ıstup, a mnoˇziny funkc´ı, kter´e nad tˇemito daty operuj´ı. Pˇ r´ıklad v Javˇ e: class Kan´ al { private int data; private boolean naplnˇen = false; public synchronized int pˇrijmout() { while (!naplnˇen) { try { wait(); } catch (InterruptedException e) {} } naplnˇen = false; return data; } public synchronized void poslat(int hodnota) { data = hodnota; naplnˇen = true; notify(); } }
9
Probl´ em uv´ıznut´ı proces˚ u, graf alokace zdroj˚ u
Uv´ıznut´ı - definice • Obecn´ y term´ın zdroj – zaˇr´ızen´ı, z´ aznam, ...
5
• V mnoˇzinˇe proces˚ u nastalo uv´ıznut´ı, jestliˇze kaˇzd´ y proces mnoˇziny ˇcek´a na ud´alost, kterou m˚ uˇze zp˚ usobit jin´ y proces mnoˇziny • Vˇsichni ˇcekaj´ı – nikdo ud´ alost nevygeneruje, nevzbud´ı jin´ y proces Jak se vypoˇ r´ adat s uv´ıznut´ım • Probl´em uv´ıznut´ı je zcela ignorov´ an • Detekce a zotaven´ı • Dynamick´e zabr´ anˇen´ı pomoc´ı peˇcliv´e alokace zdroj˚ u • Prevence, pomoc´ı struktur´ aln´ı negace jedn´e z dˇr´ıve uveden´ ych nutn´ ych podm´ınek pro vznik uv´ıznut´ı Podm´ınky vzniku uv´ıznut´ı • vz´ ajemn´ e vylouˇ cen´ı Kaˇzd´ y zdroj je bud’ dostupn´ y nebo je v´ yhradnˇe pˇriˇrazen pr´avˇe jednomu procesu • hold and wait Proces drˇz´ıc´ı v´ yhradnˇe pˇriˇrazen´e zdroje m˚ uˇze poˇzadovat dalˇs´ı zdroje • nemoˇ znost odejmut´ı Jednou pˇriˇrazen´e zdroje nemohou b´ yt procesu n´asilnˇe odejmuty (proces je mus´ı s´am uvolnit) • cyklick´ eˇ cek´ an´ı Mus´ı b´ yt cyklick´ y ˇretˇezec 2 nebo v´ıce proces˚ u, kde kaˇzd´ y z nich ˇcek´a na zdroj drˇzen´ y dalˇs´ım ˇclenem Pro vznik uv´ıznut´ı – musej´ı b´ yt splnˇ eny vˇ sechny 4 podm´ınky 1. aˇz 3. pˇredpoklady, za nich je definov´ ana 4. podm´ınka. Pokud jedna z podm´ınek nen´ı splnˇena, uv´ıznut´ı nenastane. Detekce cyklu Pˇri ˇz´ adostech o zdroj OS konstruuje graf alokace zdroj˚ u. Detekce cyklu pozn´a, zda nastalo uv´ıznut´ı. R˚ uzn´e algoritmy (teorie graf˚ u) Napˇr. prohled´ av´ an´ı do hloubky z kaˇzd´eho uzlu, dojdeme-li do uzlu, kter´ y jsme jiˇz proˇsli cyklus. Vyhladovˇ en´ı Procesy poˇzaduj´ı zdroje – pravidlo pro jejich pˇriˇrazen´ı. M˚ uˇze se st´at, ˇze nˇekter´ y proces zdroj nikdy neobdrˇz´ı, kdyˇz nenastalo uv´ıznut´ı !
10
Klasick´ e probl´ emy meziprocesov´ e komunikace, producent konzument aj.
Meziprocesov´ a komunikace: • Pˇred´ av´ an´ı zpr´ av • Primitiva send, receive • Mailbox, port • RPC • Ekvivalence semafor˚ u, zpr´ av, ... • Bari´era, probl´em veˇceˇr´ıc´ıch filozof˚ u Probl´ em sd´ılen´ e pamˇ eti • Uveden´e mechanismy 6
– um´ıstˇen´ı objektu ve sd´ılen´e pamˇeti • Nˇekdy nen´ı vhodn´e – Bezpeˇcnost – glob´ aln´ı data pˇr´ıstupn´a kter´emukoliv procesu bez ohledu na semafor • Nˇekdy nen´ı moˇzn´e – Procesy bˇeˇz´ı na r˚ uzn´ ych stroj´ıch, komunikuj´ı spolu po s´ıti ˇ sen´ı – pˇred´ • Reˇ avan´ı zpr´ av Pˇ red´ av´ an´ı zpr´ av – send, receive • Zavedeme 2 primitiva – send (adres´ at, zpr´ ava) - odesl´ an´ı zpr´avy – receive(odesilatel, zpr´ ava) - pˇr´ıjem zpr´avy – Send Zpr´ ava (lib. datov´ y objekt) bude zasl´ana adres´atovi – Receive Pˇr´ıjem zpr´ avy od urˇcen´eho odesilatele Pˇrijat´a zpr´ava se uloˇz´ı do promˇenn´e zpr´ava“ ” Producent-konzument pomoc´ı pˇ red´ av´ an´ı zpr´ av cobegin while true do { producent } begin produkuj z´ aznam; receive(konzument, m); // ˇcek´ a na pr´ azdnou poloˇzku m := z´ aznam; // vytvoˇr´ı zpr´ avu send(konzument, m); // poˇsle poloˇzku konzumentovi end {while} || for i:=1 to N do { inicializace } send(producent, e); // poˇsleme N pr´ azdn´ ych poloˇzek while true do { konzument } begin receive(producent, m); // pˇrijme zpr´ avu obsahuj´ıc´ı data z´ aznam := m; send(producent, e); // pr´ azdnou poloˇzku poˇsleme zpˇet zpracuj z´aznam; end {while} coend
11
Pl´ anov´ an´ı u ´ loh a proces˚ u v d´ avkov´ ych syst´ emech
• pr˚ uchodnost (throughput) – poˇcet u ´loh dokonˇcen´ ych za ˇcasovou jednotku • pr˚ umˇern´ a doba obr´ atky (turnaround time) – pr˚ umˇern´a doba od zad´an´ı u ´lohy do syst´emu do dokonˇcen´ı u ´lohy • vyuˇzit´ı CPU • maximalizace pr˚ uchodnosti nemus´ı nutnˇe minimalizovat dobu obr´atky • dlouh´e u ´lohy n´ asledovan´e kr´ atk´ ymi • upˇrednostˇ nov´ an´ı kr´ atk´ ych • dobr´ a pr˚ uchodnost • dlouh´e u ´lohy se nevykonaj´ı – doba obr´ atky bude nekoneˇcn´ a 7
12
Pl´ anov´ an´ı proces˚ u v interaktivn´ıch syst´ emech
Z´ akladn´ı stavy procesu • bˇeˇz´ıc´ı • pˇripraven -ˇcek´ a na CPU • blokov´ an – ˇcek´ a na zdroj nebo zpr´ avu • nov´ y (new) – proces byl pr´ avˇe vytvoˇren • ukonˇcen´ y (terminated) – proces byl ukonˇcen Spr´ avce proces˚ u – udrˇzuje tabulku proces˚ u. Z´ aznam o konkr´etn´ım procesu – PCB (Process Control Block) – souhrn dat potˇrebn´ ych k ˇr´ızen´ı proces˚ u. pl´ anovaˇ c vs. dispatcher • dispatcher pˇred´ av´ a ˇr´ızen´ı procesu vybran´emu short time pl´anovaˇcem – pˇrepnut´ı kontextu – pˇrepnut´ı do user modu – skok na vhodnou instrukci dan´eho programu • v´ıce pˇripraven´ ych proces˚ u k bˇehu – pl´ anovaˇc vybere, kter´ y spust´ı jako prvn´ı • pl´ anovaˇc proces˚ u (scheduler) - pouˇz´ıv´ a pl´anovac´ı algoritmus (scheduling algorithm) • Preemptivn´ı vs. non-preemptive pl´ anov´ an´ı
13
Spr´ ava hlavn´ı pamˇ eti, metody pˇ ridˇ elov´ an´ı pamˇ eti, virtu´ aln´ı pamˇ et’
• Ide´ al program´ atora – Pamˇet’ nekoneˇcnˇe velk´ a, rychl´ a, levn´a – Z´ aroveˇ n persistentn´ı (uchov´ av´ a obsah po vypnut´ı) – Bohuˇzel neexistuje • Re´ aln´ y poˇc´ıtaˇc – hierarchie pamˇet´ı ( pyramida“) ” – Registry CPU – Mal´e mnoˇzstv´ı rychl´e cache pamˇeti – Stovky MB aˇz gigabajty RAM pamˇeti – GB na pomal´ ych, levn´ ych, persistentn´ıch disc´ıch • Jednoprogramov´ e syst´ emy – Spouˇst´ıme pouze jeden program v jednom ˇcase – Uˇzivatel – pˇr´ıkaz , OS zavede program do pamˇeti – Dovoluje pouˇz´ıt veˇskerou pamˇet’, kterou nepotˇrebuje OS – Po skonˇcen´ı procesu lze spustit dalˇs´ı proces • Tˇ ri varianty rozdˇ elen´ı pamˇ eti – OS ve spodn´ı ˇc´ asti adresn´ıho prostoru v RAM (minipoˇc´ıtaˇce) – OS v horn´ı ˇc´ asti adresn´ıho prostoru v ROM (zapouzdˇren´e 2. syst´emy) 8
– OS v RAM, ovladaˇce v ROM (PC – MS DOS v RAM, BIOS v 3. ROM) • Modul pro spr´ avu pamˇ eti – informace o pˇridˇelen´ı pamˇeti – kter´ a ˇc´ ast je voln´ a pˇridˇelen´ a (a kter´emu procesu) • pˇridˇelov´ an´ı pamˇeti na ˇz´ adost • uvolnˇen´ı pamˇeti, zaˇrazen´ı k voln´e pamˇeti • odeb´ır´ a pamˇet’ proces˚ um • ochrana pamˇeti – pˇr´ıstup k pamˇeti jin´eho procesu – pˇr´ıstup k pamˇeti OS • Funkce MMU • Dost´ av´ a adresu od CPU, pˇrev´ ad´ı na adresu do fyzick´e pamˇeti • Nejprve zkontroluje, zda adresa nen´ı vˇetˇs´ı neˇz limit Ano – v´ yjimka, Ne – k adrese pˇriˇcte b´azi • Pokud b´ aze 1000, limit 60 – Adresa 55 – ok, v´ ysledek 1055 – Adresa 66 – nen´ı ok, v´ yjimka • Virtu´ aln´ı pamˇ et’ – program vˇetˇs´ı neˇz dostupn´ a fyzick´ a pamˇet’ – mechanismus pˇrekr´ yv´ an´ı (overlays) Virtu´ aln´ı adresy fyzick´ a pamˇet’ slouˇz´ı jako cache virtu´ aln´ıho adresn´ıho prostoru proces˚ u. Procesor pouˇz´ıv´a virtu´aln´ı adresy.P oˇzadovan´ a ˇc´ ast VA prostoru JE ve fyzick´e pamˇeti -> MMU pˇrevede VA=>FA, pˇr´ıstup k pamˇeti. Poˇzadovan´a ˇc´ast NEN´I ve fyzick´e pamˇeti -> OS ji mus´ı pˇreˇc´ıst z disku I/O operace – pˇridˇelen´ı CPU jin´emu procesu vˇetˇsina syst´em˚ u virtu´ aln´ı pamˇeti pouˇz´ıv´ a str´ ankov´ an´ı.
14
Algoritmy nahrazov´ an´ı str´ anek v pamˇ eti
Algoritmus MIN / OPT • optim´ aln´ı – nejmenˇs´ı moˇzn´ y v´ ypadek str´anek • Vyhod´ıme zboˇz´ı, kter´e nejdelˇs´ı dobu nikdo nebude poˇzadovat. • str´ anka oznaˇcena poˇctem instrukc´ı, po kter´ y se k n´ı nebude pˇristupovat • p[0] = 5, p[1] = 20, p[3] = 100 • v´ ypadek str´ anky – vybere s nejvyˇsˇs´ım oznaˇcen´ım • vybere se str´ anka, kter´ a bude zapotˇreb´ı nejpozdˇeji v budoucnosti • nen´ı realizovateln´ y (kˇriˇst´ alov´ a kole) jak zjistit dopˇredu kter´a str´anka bude potˇreba? • algoritmus pro srovn´ an´ı s realizovateln´ ymi bˇeh programu v simul´atoru uchov´avaj´ı se odkazy na str´anky spoˇcte se poˇcet v´ ypadk˚ u pro MIN/OPT srovn´ an´ı
9
Least Recently Used (LRU, LUR) • nejd´ele nepouˇzit´ a (pohled do minulosti) • princip lokality – str´ anky pouˇz´ıvan´e v posledn´ıch instrukc´ıch se budou pravdˇepodobnˇe pouˇz´ıvat i v n´asleduj´ıc´ıch – pokud se str´ anka dlouho nepouˇz´ıvala, pravdˇepodobnˇe nebude brzy zapotˇreb´ı • Vyhazovat zboˇz´ı, na kter´em je v prodejnˇe nejv´ıce prachu = nejd´ele nebylo poˇzadov´ano • Obt´ıˇzn´ a implementace • sw ˇreˇsen´ı (nen´ı pouˇziteln´e) – seznam str´ anek v poˇrad´ı referenc´ı – v´ ypadek – vyhozen´ı str´ anky ze zaˇca´tku seznamu – zpomalen´ı cca 10x, nutn´ a podpora hw • hw ˇ reˇ sen´ı – ˇ c´ıtaˇ c • MMU obsahuje ˇc´ıtaˇc (64bit), pˇri kaˇzd´em pˇr´ıstupu do pamˇeti zvˇetˇsen • kaˇzd´ a poloˇzka v tabulce str´ anek – pole pro uloˇzen´ı ˇc´ıtaˇce • odkaz do pamˇeti – obsah ˇc´ıtaˇce se zap´ıˇse do poloˇzky pro odkazovanou str´anku • v´ ypadek str´ anky – vyhod´ı se str´ anka s nejniˇzˇs´ım ˇc´ıslem Not-Recently-Used (NRU, NUR) • snaha vyhazovat nepouˇz´ıvan´e str´ anky • HW podpora u syst´em˚ u s VM – stavov´e bity Referenced (R) a Dirty (M = modified) – v tabulce str´ anek • bity nastavovan´e HW dle zp˚ usobu pˇr´ıstupu ke str´ance • bit R – nastaven na 1 pˇri ˇcten´ı nebo z´ apisu do str´anky • bit M – na 1 pˇri z´ apisu do str´ anky str´ anku je tˇreba pˇri vyhozen´ı zapsat na disk • bit z˚ ustane na 1, dokud ho SW nenastav´ı zpˇet na 0 • NRU pˇredpokl´ ad´ a – lepˇs´ı je vyhodit modifikovanou str´anku, kter´a nebyla pouˇzita 1 tik, neˇz nemodifikovanou str´ anku, kter´ a se pr´ avˇe pouˇz´ıv´ a • v´ yhody jednoduchost, srozumitelnost efektivnˇe implementovan´ y • nev´ yhody v´ ykonnost (jsou i lepˇs´ı algoritmy)
10
Algoritmy Second Chance a Clock • vych´ azej´ı z FIFO • FIFO – obchod vyhazuje zboˇz´ı zaveden´e pˇred nejdelˇs´ı dobou, at’ uˇz ho nˇekdo chce nebo ne • Second Chance – evidovat, jestli zboˇz´ı v posledn´ı dobˇe nˇekdo koupil (ano – prohl´as´ıme za ˇcerstv´e zboˇz´ı) modifikace FIFO – zabr´ anit vyhozen´ı ˇcasto pouˇz´ıvan´e – dle bitu R nejstarˇs´ı str´ anky R = 0 ... str´anka je nejstarˇs´ı, nepouˇz´ıvan´a – vyhod´ıme R = 1 ... nastav´ıme R=0, pˇresuneme na konec seznamu str´anek (jako by byla novˇe zavedena) Algoritmus Clock • Optimalizace datov´ ych struktur algoritmu Second Chance • Str´ anky udrˇzov´ any v kruhov´em seznamu • Ukazatel na nejstarˇs´ı str´ anku – ruˇciˇcka hodin“ ” • V´ ypadek str´ anky – naj´ıt str´ anku k vyhozen´ı • Str´ anka kam ukazuje ruˇciˇcka – m´ a-li R=0, str´ anku vyhod´ıme a ruˇciˇcku posuneme o jednu pozici – m´ a-li R=1, nastav´ıme R na 0, ruˇciˇcku posuneme o 1 pozici, opakov´an´ı,.. • Od SC se liˇs´ı pouze implementac´ı • Varianty Clock pouˇz´ıvaj´ı napˇr. BSD UNIX
15
Ovl´ ad´ an´ı perifern´ıch zaˇ r´ızen´ı, RAID
• RAID 0 – nen´ı redundantn´ı – ztr´ ata 1 disku – ztr´ ata cel´eho pole – d˚ uvod pouˇzit´ı – v´ ykon napˇr. stˇrih videa • RAID 1 mirroring – zrcadlen´ı na 2 disky stejn´ ych kapacit – totoˇzn´e informace – v´ ypadek 1 disku – nevad´ı – jednoduch´ a implementace – ˇcasto ˇcistˇe sw – nev´ yhoda – vyuˇzijeme jen polovinu kapacity z´apis – pomalejˇs´ı (2x) ˇcten´ı – rychlejˇs´ı (ˇradiˇc - lze stˇr´ıdat poˇzadavky mezi disky) • RAID 5 – redundantn´ı pole s distribuovanou paritou – minim´ alnˇe 3 disky – reˇzie: 1 disk z pole n disk˚ u 5 disk˚ u 100GB, 400GB pro data – v´ ypadek 1 disku nevad´ı ˇcten´ı – v´ ykon ok z´apis – pomalejˇs´ı 1 z´apis – ˇcten´ı star´ ych dat, ˇcten´ı star´e parity, v´ ypoˇcet nov´e parity, z´ apis nov´ ych dat, z´apis nov´e parity • RAID 6 11
– RAID 5 + nav´ıc dalˇs´ı paritn´ı disk – odoln´e proti v´ ypadku dvou disk˚ u – rekonstrukce pole pˇri v´ ypadku – trv´a dlouho po dobu rekonstrukce nen´ı pole chr´anˇeno proti v´ ypadku dalˇs´ıho disku n´ aroˇcn´ a ˇcinnost – m˚ uˇze se objevit dalˇs´ı chyba, ˇradiˇc disk odpoj´ı a ... • RAID 10 – kombinace RAID 0 (stripe) a RAID 1 (zrcadlo) – min. poˇcet disk˚ u 4 reˇzie 100% diskov´e kapacity nav´ıc – nejvyˇsˇs´ı v´ ykon v bezpeˇcn´ ych typech pol´ıch podstatnˇe rychlejˇs´ı neˇz RAID 5, pˇri z´apisu odolnost proti ztr´ atˇe aˇz 50% disk˚ u x RAID 5 • Principy I/O software • typicky strukturov´ an do 4 u ´rovn´ı – obsluha pˇreruˇsen´ı (nejniˇzˇs´ı u ´roveˇ n v OS) – ovladaˇc zaˇr´ızen´ı – SW vrstva OS nez´ avisl´ a na zaˇr´ızen´ı – uˇzivatelsk´ y I/O SW 4. • Funkce ovladaˇ ce zaˇ r´ızen´ı • ovladaˇci pˇred´ an pˇr´ıkaz vyˇsˇs´ı vrstvou napˇr. zapiˇs data do bloku n • nov´ y poˇzadavek zaˇrazen do fronty – m˚ uˇze jeˇstˇe obsluhovat pˇredchoz´ı • ovladaˇc zad´ a pˇr´ıkazy ˇradiˇci (poˇzadavek pˇrijde na ˇradu) – napˇr. nastaven´ı hlavy, pˇreˇcten´ı sektoru • zablokuje se do vykon´ an´ı poˇzadavku – neblokuje pˇri rychl´ ych operac´ıch – napˇr. z´apis do registru • vzbuzen´ı obsluhou pˇreruˇsen´ı (dokonˇcen´ı operace) – zkontroluje, zda nenastala chyba • pokud OK, pˇred´ a v´ ysledek (status + data) vyˇsˇs´ı vrstvˇe status – datov´a struktura pro hl´aˇsen´ı chyb dalˇs´ı poˇzadavky ve frontˇe – jeden vybere a spust´ı
16
Syst´ emy soubor˚ u
potˇreba aplikac´ı trvale uchov´ avat data • hlavn´ı poˇzadavky – moˇznost uloˇzit velk´e mnoˇzstv´ı dat – informace zachov´ ana i po ukonˇcen´ı procesu – data pˇr´ıstupn´ a v´ıce proces˚ um • spoleˇcn´e probl´emy pˇri pˇr´ıstupu k zaˇr´ızen´ı – alokace prostoru na disku – pojmenov´ an´ı dat – ochrana dat pˇred neopr´ avnˇen´ ym pˇr´ıstupem 12
– zotaven´ı po hav´ arii (v´ ypadek nap´ ajen´ı) Souborov´ y syst´ em (anglicky filesystem) je oznaˇcen´ı pro zp˚ usob organizace informac´ı (ve formˇe soubor˚ u) tak, aby bylo moˇzn´e je snadno naj´ıt a pˇristupovat k nim. Souborov´e syst´emy mohou pouˇz´ıvat pamˇet’ov´a m´edia jako pevn´ y disk nebo CD, mohou poskytovat pˇr´ıstup k dat˚ um uloˇzen´ ym na serveru (s´ıt’ov´e souborov´e syst´emy, napˇr. NFS, SMB nebo 9P) nebo mohou poskytovat pˇr´ıstup k ˇcistˇe virtu´aln´ım dat˚ um (napˇr. procfs v Linuxu). Souborov´ y syst´em umoˇzn ˇuje ukl´ adat data do soubor˚ u, kter´e jsou oznaˇceny n´azvy. Obvykle tak´e umoˇzn ˇuje vytv´aˇret adres´ aˇre, pomoc´ı kter´ ych lze soubory organizovat do stromov´e struktury.
17
Kontrola konzistence souborov´ eho syst´ emu, mechanismy ochrany pˇ red neopr´ avnˇ en´ ym pˇ r´ıstupem
OS precte blok souboru, zmenı ho, zapıˇse.Co kdyz nastane hav´arie pred tım, nez jsou vˇsechny modifikovan´e bloky zaps´ any? => fs muze b´ yt v nekonzistentnım stavu.S vetˇsinou OS se dod´av´a syst´emov´ y program, kter´ y kontroluje konzistenci fs (UNIX: fsck, Windows: scandisk resp. chkdsk). Program je automaticky spuˇsten pri startu po hav´ arii syst´emu. Program muze prov´ adet n´ asledujıcı testy konzistence fs: - konzistence informace o diskov´ ych blocıch souboru (ve vetˇsine fs muze blok patrit pouze jednomu souboru nebo b´ yt voln´ y) - konzistence adres´arov´e struktury (jsou vˇsechny adres´ are a soubory dostupn´e? apod.) kontrola konzistence adres´ arov´e struktury - tabulka cıtacu, jedna polozka pro kazd´ y soubor - program proch´ azı rekurzivne cel´ y adres´ arov´ y strom - polozku pro soubor program zv´ yˇsı pro kazd´ y v´ yskyt souboru v adres´ ari - pak zkontroluje zda odpovıd´ a pocet odkazu v i-uzlu (”i”) s poctem v´ yskytu v adres´arıch (”a”). Kontrola konzistence fs muze pro rozs´ ahl´e disky trvat minuty, prıpadne i hodiny. Jako c´astecn´e reˇsenı tohoto probl´emu vznikly modernı tzv. zurn´ alujıcı fs (v Linuxu jsou to napr. souborov´e syst´emy ext3 (coz je zurn´ alujıcı rozˇsırenı ext2), ReiserFS a dalˇsı). Zurn´ alujıcı fs pred kazd´ ym z´apisem na disk vytvorı na disku z´aznam popisujıcı pl´ anovan´e operace; pak operace provede a z´ aznam zruˇsı. V prıpade v´ ypadku nap´ajenı lze na disku najıt informaci (zurn´ al) o vˇsech operacıch kter´e mohly b´ yt v dobe hav´arie rozpracovan´e, coz znacne zjednoduˇsuje kontrolu konzistence fs. Mechanismy ochrany • soubory je treba chr´ anit pred neopr´ avnen´ ym prıstupem • krome souboru existujı v OS dalˇsı objekty, kter´e je treba chr´anit - muze b´ yt HW (segmenty pameti, I/O zarızenı), - SW objekty (procesy, semafory...) • syst´em musı uchov´ avat informace o prıstupov´ ych pr´avech subjektu k objektum - subjekt = entita schopn´ a pristupovat k objektum (vetˇsinou proces) - prıstupov´e pr´avo je pr´avo vykonat jednu z mozn´ ych operacı, naprıklad Read, Write, Execute, Delete... - objekt = cokoli k cemu je treba omezovat prıstup pomocı prıstupov´ ych pr´ av • informace o prıstupov´ ych pr´ avech muze b´ yt ve dvou ruzn´ ych podob´ach: ACL nebo capability list - ACL = s objektem sdruzen seznam subjektu a jejich prıstupov´ ych pr´av - capability list (cti [kejpa-]) = se subjektem je sdruzen seznam objektu a prıstupov´ ych pr´av k nim Mechanismus ACL (Access Control Lists) • s kazd´ ym objektem sdruzen seznam subjektu kter´e mohou k objektu pristupovat (zde subjekt = uzivatel, resp. jeho procesy), - pro kazd´ y uveden´ y subjekt je v ACL mnozina prıstupov´ ych pr´av k objektu • Mechanismus capability lists (C-seznamy) • s kazd´ ym subjektem (procesem) sdruzen seznam objektu ke kter´ ym muze pristupovat a jak´ ym zpusobem (tj. prıstupov´ a pr´ ava) • seznam naz´ yv´ an ”capability list” (C-list = C-seznam) a jednotliv´e polozky ”capabilities” • struktura ”capability” m´ a prvky: - typ objektu - pr´ava - obvykle bitov´a mapa popisujıcı dovolen´e operace nad objektem - odkaz na objekt, napr. cıslo i-uzlu, cıslo segmentu apod. • probl´em - zjiˇstenı, kdo vˇsechno m´ a k objektu prıstup + zruˇsenı prıstupu velmi obtızn´e - znamenalo by to najıt pro objekt vˇsechny capability + odejmout pr´ava
13
• reˇsenı - odkaz neukazuje na objekt, ale na neprım´ y objekt; syst´em muze zruˇsit neprım´ y objekt, tım zneplatnı odkazy na objekt ze vˇsech C-seznamu • C-seznamy zacnou b´ yt zajımav´e pokud jsou jedin´ y zpusob odkazu na objekt (capability ch´ap´ana jako bezpecn´ y ukazatel; n´ azev ”capability-based addressing) - ruˇsı rozdıl mezi objekty na disku, v pameti (segmenty) nebo na jin´em stroji (objekty by se dokonce mohly presouvat za behu) - proto mechanismus C-seznamu najdeme v nekter´ ych distribuovan´ ych syst´emech (napr. Hydra, Mach apod.)
14
