zos/p8mm.d
24. listopadu 2003
KIV/ZOS 2003/2004 Pr ˇedna ´s ˇka 8 Obecne ˇ existujı ´ 4 strategie zacha ´zenı ´ s uvı ´znutı ´m: 1. 2. 3. 4.
Proble ´m uvı ´znutı ´ je zcela ignorova ´n Detekce a zotavenı ´ Dynamicke ´ zabra ´ne ˇnı ´ pomocı ´ pec ˇlive ´ alokace zdroju ˚ Prevence, pomocı ´ struktura ´lnı ´ negace jedne ´ z vy ´s ˇe uvedeny ´ch 4 nutny ´ch podmı ´nek pro vznik uvı ´znutı ´
1. Ignorova ´nı ´ proble ´mu ---------------------* ”ps ˇtrosı ´ algoritmus: strc ˇı ´me hlavy do pı ´sku a pr ˇedstı ´ra ´me, z ˇe proble ´m neexistuje” :-) * cena za eliminaci uvı ´znutı ´ je vysoka ´ (napr ˇ. c ˇinnost uz ˇivatelsky ´ch procesu ˚ je nepr ˇı ´jemne ˇ omezena apod.) => neexistuje vs ˇeobecne ˇ pr ˇijı ´mane ´ r ˇes ˇenı ´ * z ˇa ´dny ´ ze zna ´my ´ch OS se nezaby ´va ´ uvı ´znutı ´m uz ˇivatelsky ´ch procesu ˚ (ve ˇts ˇina OS ale snaha o eliminaci uvı ´znutı ´ pro c ˇinnosti ja ´dra) 2. Detekce a zotavenı ´ --------------------* syste ´m se nesnaz ˇı ´ zabra ´nit vzniku, ale detekuje, po detekci provede akci pro zotavenı ´ Detekce uvı ´znutı ´ pro jeden zdroj kaz ˇde ´ho typu ............................................. * pr ˇi z ˇa ´dostech o zdroj/pr ˇir ˇazenı ´ zdroje OS konstruuje graf alokace zdroju ˚ * detekce cyklu => nastalo uvı ´znutı ´ * pro detekci cyklu ˚ ru ˚ zne ´ algoritmy (viz teorie grafu ˚) - jednoduchy ´ algoritmus: prohleda ´va ´nı ´ do hloubky z kaz ˇde ´ho uzlu (pokud dojdeme do uzlu, ktery ´ jsme jiz ˇ jednou pros ˇli, je cyklus) Zotavenı ´ z uvı ´znutı ´ ................... * zotavenı ´ pomocı ´ preempce - vlastnı ´kovi zdroj doc ˇasne ˇ odejmout - za ´visı ´ na typu zdroje, c ˇasto obtı ´z ˇne ´ az ˇ nemoz ˇne ´ - napr ˇı ´klad tiska ´rna - po dotis ˇte ˇnı ´ stra ´nky proces pozastavit, odejmout mu tiska ´rnu a pr ˇir ˇadit jine ´mu (vyz ˇaduje ruc ˇnı ´ intervenci - vyjmout jiz ˇ vytis ˇte ˇne ´ stra ´nky) * zotavenı ´ pomocı ´ zrus ˇenı ´ zme ˇn (rollback) - pokud jsou uvı ´znutı ´ c ˇasta ´, mu ˚z ˇe syste ´m v pravidelny ´ch intervalech prova ´de ˇt checkpointing procesu ˚ = za ´pis stavu procesu ˚ do souboru, aby proces mohl by ´t v pr ˇı ´pade ˇ potr ˇeby ”vra ´cen” do uloz ˇene ´ho stavu - po detekci uvı ´znutı ´ je proces vlastnı ´cı ´ zdroje vra ´cen zpe ˇt nastavenı ´ na ne ˇktery ´ jeho dr ˇı ´ve ˇjs ˇı ´ checkpoint, kdy jes ˇte ˇ zdroj nevlastnil (pra ´ce procesu od checkpointu je tı ´m ztracena) - zdroj pr ˇir ˇadı ´me uvı ´zle ´mu procesu => zrus ˇı ´me deadlock - proces, ktere ´mu jsme zdroj odebrali, se ho pokusı ´ alokovat => usne * zotavenı ´ pomocı ´ zrus ˇenı ´ procesu - nejhrozne ˇjs ˇı ´ zpu ˚sob - zrus ˇı ´me jeden nebo vı ´ce procesu ˚ - zrus ˇit proces v cyklu; pokud nepomu ˚z ˇe, zrus ˇı ´me dals ˇı ´ atd. - nenı ´ pr ˇı ´lis ˇ dobre ´ r ˇes ˇenı ´; c ˇasto alespon ˇ snaha zrus ˇit procesy, ktere ´ je moz ˇne ´ spustit znovu od zac ˇa ´tku 3. Dynamicke ´ zabra ´ne ˇnı ´ ---------------------* * * *
ve ve ˇts ˇine ˇ syste ´mu ˚ procesy z ˇa ´dajı ´ o zdroje po jednom syste ´m rozhodne, zda je pr ˇir ˇazenı ´ zdroje bezpec ˇne ´ nebo hrozı ´ uvı ´znutı ´ pokud bezpec ˇne ´, zdroj pr ˇir ˇadı ´, jinak proces pozastavı ´ z ˇa ´dajı ´cı ´ proces stav je bezpec ˇny ´, pokud existuje alespon ˇ jedna posloupnost, ve ktere ´ mohou
73
24. listopadu 2003
74
zos/p8mm.d
procesy dobe ˇhnout aniz ˇ by nastalo uvı ´znutı ´ I kdyz ˇ stav nenı ´ bezpec ˇny ´, uvı ´znutı ´ nemusı ´ nastat nutne ˇ - uvidı ´me da ´le. Banke ´r ˇ˚ uv algoritmus pro jeden typ zdroje ........................................ * zde pr ˇedpokla ´da ´me vı ´ce zdroju ˚ stejne ´ho typu (!) * napr ˇı ´klad N magnetopa ´skovy ´ch jednotek apod. * algoritmus pla ´nova ´nı ´, ktery ´ se doka ´z ˇe ”vyhnout” uvı ´znutı ´ (Dijkstra 1965) * banke ´r ˇ na male ´m me ˇste ˇ, ma ´ 4 za ´kaznı ´ky A, B, C a D, kaz ˇde ´mu garantuje pu ˚ jc ˇku dane ´ velikosti (6, 5, 4, 7), dohromady 22 (napr ˇ. K$) * banke ´r ˇ vı ´, z ˇe vs ˇichni za ´kaznı ´ci nebudou chtı ´t pu ˚jc ˇku souc ˇasne ˇ, pro obsluhu za ´kaznı ´ku ˚ si ponecha ´va ´ pouze 10 * stav:
za ´k. ma ´ max.; 2 volne ´ jednotky A 1 6 B 1 5 C 2 4 D 4 7 - stav bezpec ˇny ´, protoz ˇe banke ´r ˇ mu ˚z ˇe pozastavit vs ˇechny poz ˇadavky krome ˇ C - da ´ C 2 jednotky, C skonc ˇı ´ a uvolnı ´ 4, mu ˚z ˇeme pouz ˇı ´t pro D nebo B atd.
* co kdybychom B dali 1 jednotku oproti vy ´s ˇe uvedene ´mu? - stav: za ´k. ma ´ max.; 1 volna ´ jednotka A 1 6 B 2 5 C 2 4 D 4 7 - stav nenı ´ bezpec ˇny ´, protoz ˇe kdyby vs ˇichni za ´kaznı ´ci poz ˇa ´dali o maxima ´lnı ´ pu ˚jc ˇku, banke ´r ˇ by nemohl uspokojit z ˇa ´dne ´ho => nastalo by uvı ´znutı ´ (uvı ´znutı ´ nemusı ´ nastat nutne ˇ, ale s tı ´m banke ´r ˇ nemu ˚z ˇe poc ˇı ´tat) * banke ´r ˇ uvaz ˇuje pro kaz ˇdy ´ poz ˇadavek, zda vede k bezpec ˇne ´mu stavu na ´sledujı ´cı ´m zpu ˚sobem: 1. banke ´r ˇ pr ˇedpokla ´da ´, z ˇe poz ˇadovany ´ zdroj byl procesu pr ˇir ˇazen a z ˇe vs ˇechny procesy poz ˇa ´daly o vs ˇechny banke ´r ˇem garantovane ´ zdroje 2. banke ´r ˇ zjistı ´, zda je dostatek zdroju ˚ pro uspokojenı ´ ne ˇktere ´ho za ´kaznı ´ka; pokud je dostatek zdroju ˚, pr ˇedpokla ´da ´, z ˇe za ´kaznı ´kovi byla suma vyplacena, skonc ˇil a uvolnil (vra ´til) vs ˇechny zdroje 3. banke ´r ˇ opakuje krok (2); pokud mohou vs ˇichni za ´kaznı ´ci skonc ˇit, je stav bezpec ˇny ´ * poz ˇadavek je vykona ´n (zdroje poskytnuty) pouze pokud vede k bezpec ˇne ´mu stavu, jinak je odloz ˇen na pozde ˇji (proces je pozastaven) Banke ´r ˇ˚ uv algoritmus pro vı ´ce typu ˚ zdroju ˚ ........................................ * banke ´r ˇ˚ uv algoritmus mu ˚z ˇe by ´t zobecne ˇn pro vı ´ce typu ˚ zdroju ˚ * uva ´dı ´m pouze pro zajı ´mavost * pouz ˇı ´va ´me dve ˇ matice (sloupce pr ˇedstavujı ´ tr ˇı ´dy zdroju ˚, r ˇa ´dky za ´kaznı ´ky) - matice pr ˇir ˇazeny ´ch zdroju ˚ (current allocation matrix) - ktery ´ za ´kaznı ´k ma ´ ktere ´ zdroje - matice jes ˇte ˇ poz ˇadovany ´ch zdroju ˚ (request matrix) - kolik zdroju ˚ ktere ´ho typu budou procesy jes ˇte ˇ chtı ´t Napr ˇı ´klad:
matice pr ˇir ˇazeny ´ch zdroju ˚
zdroje: za ´k.A za ´k.B za ´k.C za ´k.D
R 3 0 1 1
S 0 1 1 1
T 1 0 1 0
matice jes ˇte ˇ poz ˇadovany ´ch zdroju ˚
zdroje: za ´k.A za ´k.B za ´k.C za ´k.D
R 1 0 3 0
S 1 1 1 0
T 0 1 0 1
zos/p8mm.d
24. listopadu 2003
* zavedeme vektor A volny ´ch zdroju ˚ (available resources) napr ˇ. A = (1, 0, 1) znamena ´ jeden volny ´ zdroj typu R, z ˇa ´dny ´ typu S atd. Algoritmus pro urc ˇenı ´, zda je stav bezpec ˇny ´: 1. V matici jes ˇte ˇ poz ˇadovany ´ch zdroju ˚ (request matrix) hleda ´me r ˇa ´dek, ktery ´ je mens ˇı ´ nebo roven A. Pokud takovy ´ r ˇa ´dek neexistuje, nastalo by uvı ´znutı ´. 2. Pr ˇedpokla ´dejme, z ˇe proces obdrz ˇel vs ˇechny poz ˇadovane ´ zdroje a skonc ˇil. Oznac ˇı ´me proces jako ukonc ˇeny ´ a pr ˇic ˇteme vs ˇechny jeho zdroje k vektoru A. 3. Opakujeme kroky 1 a 2, dokud vs ˇechny procesy neskonc ˇı ´ (tj. pu ˚ vodnı ´ stav byl bezpec ˇny ´) nebo dokud nenastalo uvı ´znutı ´ (pu ˚vodnı ´ stav nebyl bezpec ˇny ´)
* Od 1965, kdy byl banke ´r ˇ˚ uv algoritmus publikova ´n, se objevuje ve vs ˇech uc ˇebnicı ´ch OS (+ mnoho odborny ´ch c ˇla ´nku ˚ apod.) * v praxi v podstate ˇ nepouz ˇitelny ´, protoz ˇe: - procesy zr ˇı ´dka ve ˇdı ´ dopr ˇedu, jake ´ budou jejich maxima ´lnı ´ poz ˇadavky na zdroje - poc ˇet procesu ˚ nenı ´ konstantnı ´, ale me ˇnı ´ se v pru ˚be ˇhu c ˇasu (uz ˇivatele ´ se pr ˇihlas ˇujı ´, spous ˇte ˇjı ´ procesy, odhlas ˇujı ´ se...) - zdroje mohou ”zmizet” - tiska ´rne ˇ dojde papı ´r... * nevı ´m o z ˇa ´dne ´m prakticke ´m pouz ˇitı ´ banke ´r ˇova algoritmu pro zabra ´ne ˇnı ´ uvı ´znutı ´ * algoritmy odvozene ´ od banke ´r ˇova algoritmu lze pouz ˇı ´t pro detekci uvı ´znutı ´ pr ˇi vı ´ce zdrojı ´ch stejne ´ho typu
4. Prevence uvı ´znutı ´ -------------------* jak skutec ˇne ´ syste ´my zabran ˇujı ´ uvı ´znutı ´? * podı ´va ´me se zpe ˇt na Coffmanovy 4 podmı ´nky vzniku uvı ´znutı ´: 1. 2. 3. 4.
vza ´jemne ´ vylouc ˇenı ´ - vy ´hradnı ´ pr ˇir ˇazova ´nı ´ zdroju ˚ ”hold and wait”: proces drz ˇı ´cı ´ zdroje mu ˚z ˇe poz ˇadovat dals ˇı ´ nemoz ˇnost zdroje odejmout cyklicke ´ c ˇeka ´nı ´
* pokud ne ˇktera ´ podmı ´nka nebude nikdy splne ˇna, je uvı ´znutı ´ struktura ´lne ˇ nemoz ˇne ´ 1. Vza ´jemne ´ vylouc ˇenı ´ ..................... * zdroj nikdy nepr ˇir ˇadit vy ´hradne ˇ * byl by proble ´m pro ne ˇktere ´ zdroje (tiska ´rna) => spooling - pouze daemon pr ˇistupuje k tiska ´rne ˇ, nikdy nepoz ˇaduje dals ˇı ´ zdroje => nenı ´ uvı ´znutı ´ pro tiska ´rnu Proble ´my: * spooling nenı ´ moz ˇny ´ pro vs ˇechny zdroje (za ´znamy v databa ´zi) * spooling pr ˇeva ´dı ´ soute ˇz ˇenı ´ o tiska ´rnu na soute ˇz ˇenı ´ o diskovy ´ prostor: - napr ˇ. 2 procesy zaplnı ´ kaz ˇdy ´ polovinu disku, z ˇa ´dny ´ nemu ˚z ˇe skonc ˇit 2. Podmı ´nka ”hold and wait” ........................... * proble ´m, z ˇe proces drz ˇı ´cı ´ vy ´hradne ˇ pr ˇir ˇazene ´ zdroje mu ˚z ˇe poz ˇadovat dals ˇı ´ zdroje * r ˇes ˇenı ´: - poz ˇadovat, aby procesy alokovaly vs ˇechny zdroje pr ˇed svy ´m spous ˇte ˇnı ´m . procesy ve ˇts ˇinou neve ˇdı ´, ktere ´ zdroje budou chtı ´t, a i kdyby ve ˇde ˇly, tak je poz ˇadavek pr ˇı ´lis ˇ restriktivnı ´ . ne ˇktere ´ da ´vkove ´ syste ´my; i kdyz ˇ popsane ´ nevy ´hody, deadlocku zabran ˇuje - variace - pokud proces poz ˇaduje nove ´ zdroje, musı ´ uvolnit zdroje
75
24. listopadu 2003
76
ktere ´ drz ˇı ´ a o vs ˇechny zdroje poz ˇa ´dat v jedine ´m poz ˇadavku 3. Nemoz ˇnost zdroje odejmout ............................ * odejı ´mat zdroje pome ˇrne ˇ obtı ´z ˇne ´ 4. Cyklicke ´ c ˇeka ´nı ´ .................. * proces mu ˚z ˇe mı ´t jediny ´ zdroj, a pokud chce jiny ´, musı ´ pr ˇedchozı ´ uvolnit - pone ˇkud restriktivnı ´ * vs ˇechny zdroje oc ˇı ´slova ´ny, poz ˇadavky musejı ´ by ´t prova ´de ˇny v c ˇı ´selne ´m por ˇadı ´ - alokac ˇnı ´ graf nemu ˚z ˇe mı ´t cykly - proble ´m: je te ˇz ˇke ´ nale ´zt vhodne ´ oc ˇı ´slova ´nı ´ pro vs ˇechny zdroje - nenı ´ obecne ˇ pouz ˇitelne ´, ale ve specia ´lnı ´ch pr ˇı ´padech (napr ˇ. uvnitr ˇ OS, databa ´zove ´ho syste ´mu) je vy ´hodne ´ pouz ˇı ´t Pr ˇı ´klad: dvoufa ´zove ´ zamyka ´nı ´ (pouz ˇı ´va ´ se v databa ´zovy ´ch syste ´mech) * prvnı ´ fa ´ze - zamknutı ´ vs ˇech potr ˇebny ´ch za ´znamu ˚ v c ˇı ´selne ´m por ˇadı ´ - pokud je ne ˇktery ´ zamknut jiny ´m procesem, uvolnı ´ vs ˇechny za ´mky a zkusı ´ znovu * druha ´ fa ´ze - c ˇtenı ´/za ´pis & uvoln ˇova ´nı ´ za ´mku ˚ * protoz ˇe se zamyka ´ vz ˇdy v c ˇı ´selne ´m por ˇadı ´, uvı ´znutı ´ nemu ˚z ˇe nastat Shrnutı ´ pr ˇı ´stupu ˚ k uvı ´znutı ´ ........................... 1. Ignorova ´nı ´ proble ´mu - ve ˇts ˇina OS ignoruje uvı ´znutı ´ uz ˇivatelsky ´ch procesu ˚ 2. Detekce a zotavenı ´ - pokud uvı ´znutı ´ nastane, detekujeme a ne ˇco s tı ´m ude ˇla ´me (vra ´tı ´me c ˇas zpa ´tky - rollback, nebo zrus ˇı ´me proces) 3. Dynamicke ´ zabra ´ne ˇnı ´ - zdroj pr ˇir ˇadı ´me pouze pokud bude stav bezpec ˇny ´ (banke ´r ˇ˚ uv algoritmus - jedine ´ se ty ´kalo vı ´ce zdroju ˚ stejne ´ho typu) 4. Prevence - struktura ´lne ˇ negujeme jednu z Coffmanovy ´ch podmı ´nek: - vza ´jemne ´ vylouc ˇenı ´ - spooling vs ˇeho - ”hold and wait” - procesy poz ˇadujı ´ vs ˇechny zdroje na zac ˇa ´tku - nemoz ˇnost odejmutı ´ - odejmi (nefunguje) - cyklicke ´ c ˇeka ´nı ´ - zdroje oc ˇı ´slujeme a z ˇa ´da ´me v c ˇı ´selne ´m por ˇadı ´.
Vyhladove ˇnı ´ =========== * procesy poz ˇadujı ´ zdroje, musı ´ existovat pravidlo pro jejich pr ˇir ˇazenı ´ * mu ˚z ˇe se sta ´t, z ˇe ne ˇktery ´ proces zdroj nikdy neobdrz ˇı ´, i kdyz ˇ nenastalo uvı ´znutı ´ * napr ˇı ´klad vec ˇer ˇı ´cı ´ filosofove ´ v jiz ˇ uvedene ´m pr ˇı ´kladu - kaz ˇdy ´ zvedne levou vidlic ˇku, pokud je prava ´ obsazena ´ tak levou poloz ˇı ´ - vyhladove ˇnı ´, pokud vs ˇichni zvedajı ´ a pokla ´dajı ´ souc ˇasne ˇ * nebo pokud pr ˇir ˇazujeme zdroje podle strategie SJF - napr ˇı ´klad tiska ´rnu dostane proces, ktery ´ chce vytisknout nejkrats ˇı ´ soubor - pokud ne ˇktery ´ proces chce vytisknout velky ´ soubor a je mnoho maly ´ch poz ˇadavku ˚ - mu ˚z ˇe dojı ´t k vyhladove ˇnı ´ - r ˇes ˇenı ´ - FIFO, nebo oznac ˇı ´me poz ˇadavek c ˇasem pr ˇı ´chodu a pr ˇi pr ˇekroc ˇenı ´ povolene ´ doby setrva ´nı ´ v syste ´mu bude obslouz ˇen
Terminologicke ´ rozdı ´ly ====================== V c ˇes ˇtine ˇ nenı ´ pro ne ˇktere ´ pojmy OS usta ´lena ´ terminologie. Na ´sledujı ´cı ´ tabulka se bude snaz ˇit upozornit na terminologicke ´ rozdı ´ly mezi mnou a texty, se ktery ´mi se mu ˚z ˇete setkat.
zos/p8mm.d
zos/p8mm.d
24. listopadu 2003
blokovany ´ (za ´kladnı ´ stav procesu, z angl. blocked, ne ˇkdy waiting) Mra ´zek a ne ˇkter ˇı ´ dals ˇı ´: c ˇekajı ´cı ´ uvı ´znutı ´, uva ´znutı ´, v c ˇeske ´ literatur ˇe se uz ˇı ´va ´ i angl. deadlock (neomezene ´ c ˇeka ´nı ´ na uda ´lost) Mra ´zek: zablokova ´nı ´ vyhladove ˇnı ´ (programy be ˇz ˇı ´ ale nemohou vykonat z ˇa ´danou c ˇinnost; z angl. starvation) Mra ´zek: umor ˇenı ´ aktivnı ´ c ˇeka ´nı ´ (busy wait) s pr ˇedbı ´ha ´nı ´m (preemptive)
Spra ´va hlavnı ´ pame ˇti ==================== * idea ´lnı ´ pr ˇa ´nı ´ programa ´tora - mı ´t nekonec ˇne ˇ velkou a rychlou pame ˇt’ a levnou, ktera ´ je za ´roven ˇ perzistentnı ´, tj. uchova ´ obsah po vypnutı ´ * takova ´ pame ˇt’ ale neexistuje * ve ˇts ˇina poc ˇı ´tac ˇ˚ u ma ´ hierarchii pame ˇtı ´ - male ´ mnoz ˇstvı ´ rychle ´ cache - desı ´tky az ˇ stovky MB str ˇedne ˇ rychle ´ a str ˇedne ˇ drahe ´ RAM - desı ´tky az ˇ stovky GB na pomaly ´ch, ale levny ´ch a perzistentnı ´ch discı ´ch * c ˇa ´st OS, ktera ´ spravuje pame ˇt’ se nazy ´va ´ spra ´vce pame ˇti - udrz ˇuje informaci, ktere ´ c ˇa ´sti pame ˇti se pouz ˇı ´vajı ´ a ktere ´ jsou volne ´ - alokuje pame ˇt’ procesu ˚ m podle potr ˇeby (napr ˇ. jako du ˚sledek Pascalske ´ho ”new” nebo ”malloc” v jazyce C) - zar ˇazuje pame ˇt’ do volne ´ pame ˇti po uvolne ˇnı ´ procesem (napr ˇ. po ”release” v Pascalu nebo ”free” v jazyce C) * v te ´to c ˇa ´sti probereme ru ˚zne ´ mechanismy spra ´vy pame ˇti * postupne ˇ od nejjednodus ˇs ˇı ´ch (”program ma ´ ves ˇkerou pame ˇt’”) po propracovana ´ sche ´mata (napr ˇ. ”stra ´nkova ´nı ´ se segmentacı ´”) * mechanismy pro spra ´vu pame ˇti lze rozde ˇlit do dvou kategoriı ´ - program je v pame ˇti po celou dobu be ˇhu - ”za ´kladnı ´ mechanismy” - programy jsou pr ˇesouva ´ny mezi hlavnı ´ pame ˇtı ´ a diskem - ”mechanismy s odkla ´da ´nı ´m” * nejdr ˇı ´ve probereme za ´kladnı ´ mechanismy - jsou jednodus ˇs ˇı ´
Za ´kladnı ´ mechanismy pro spra ´vu pame ˇti ===================================== * za ´kladnı ´ mechanismy = spra ´va pame ˇti bez odkla ´da ´nı ´ a stra ´nkova ´nı ´ Jednoprogramove ´ syste ´my bez odkla ´da ´nı ´ a stra ´nkova ´nı ´ --------------------------------------------------* * * *
nejjednodus ˇs ˇı ´ - spous ˇtı ´me pouze jeden program v jednom c ˇase uz ˇivatel zada ´ pr ˇı ´kaz, OS zavede odpovı ´dajı ´cı ´ program do pame ˇti dovoluje procesu pouz ˇı ´t ves ˇkerou pame ˇt’, kterou nepotr ˇebuje OS po skonc ˇenı ´ procesu je moz ˇne ´ spustit dals ˇı ´ proces
* jako pr ˇı ´klad tr ˇi varianty, jak mu ˚z ˇe vypadat rozde ˇlenı ´ pame ˇti: - OS je ve spodnı ´ c ˇa ´sti adresnı ´ho prostoru v RAM, dr ˇı ´ve na minipoc ˇı ´tac ˇı ´ch apod. - OS je v hornı ´ c ˇa ´sti adresnı ´ho prostoru v ROM - napr ˇ. zapouzdr ˇene ´ syste ´my - OS je v RAM, ovladac ˇe v ROM, dr ˇı ´ve osobnı ´ poc ˇı ´tac ˇe (MS DOS v RAM, BIOS v ROM)
77
24. listopadu 2003
78 0FFFFh
OS in ROM
zos/p8mm.d
0FFFFh
drivers in ROM
0FFFFh
free/program free/program
free/program OS in RAM a)
OS in RAM
0
0 b)
0
c)
Multiprogramova ´nı ´ s pevny ´m pr ˇide ˇlenı ´m pame ˇti -------------------------------------------* ve ˇts ˇina souc ˇasny ´ch syste ´mu ˚ dovoluje paralelnı ´ nebo pseudoparalelnı ´ be ˇh vı ´ce procesu ˚ = multiprogramova ´nı ´ * napr ˇ. kvu ˚li souc ˇasne ´ pra ´ci vı ´ce uz ˇivatelu ˚ , maxima ´lnı ´mu vyuz ˇitı ´ CPU apod. * nejjednodus ˇs ˇı ´ sche ´ma - rozde ˇlit pame ˇt’ na n oblastı ´ (mohou by ´t i ru ˚zne ´ velikosti) - v historicky ´ch syste ´mech se prova ´de ˇlo napr ˇ. ruc ˇne ˇ pr ˇi startu stroje - po nac ˇtenı ´ ´ ulohy do oblasti je obvykle c ˇa ´st oblasti nevyuz ˇita ´ - proto snaha umı ´stit ´ ulohu do nejmens ˇı ´ oblasti, do ktere ´ se vejde * ne ˇkolik strategiı ´:
processes
1. vı ´ce front, kaz ˇda ´ ´ uloha do fronty nejmens ˇı ´ oblasti, kam se vejde 2. jedna fronta - po uvolne ˇnı ´ oblasti z fronty vybrat nejve ˇts ˇı ´ ´ ulohu, ktera ´ se vejde
processes
common queue
separate queues
* v pr ˇı ´pade ˇ (1) se mu ˚z ˇe sta ´t, z ˇe existuje pra ´zdna ´ oblast, ktera ´ se nevyuz ˇije, protoz ˇe ´ ulohy c ˇekajı ´ na jine ´ oblasti * algoritmus (2) diskriminuje male ´ ´ ulohy, ale pr ˇitom je obvykle dobre ´ poskytnout maly ´m ´ uloha ´m nejleps ˇı ´ sluz ˇbu - jedno r ˇes ˇenı ´ je vz ˇdy mı ´t malou oblast, kde mohou be ˇz ˇet male ´ ´ ulohy - druhe ´ r ˇes ˇenı ´ je s kaz ˇdou ´ ulohou ve fronte ˇ sdruz ˇit ”c ˇı ´tac ˇ pr ˇeskoc ˇenı ´”, ktery ´ bude zve ˇts ˇen pr ˇi kaz ˇde ´m pr ˇeskoc ˇenı ´ ´ ulohy; po dosaz ˇenı ´ meznı ´ hodnoty uz ˇ nesmı ´ by ´t ´ uloha pr ˇeskoc ˇena Syste ´m s pevny ´m rozde ˇlenı ´m pame ˇti (Multiprogramming with Fixed Number of Tasks) se pouz ˇı ´val napr ˇ. v syste ´mu OS/360. Pozna ´mka (multiprogramova ´nı ´ a velikost pame ˇti) .............................................. * multiprogramova ´nı ´ take ´ zvys ˇuje vyuz ˇitı ´ CPU - pr ˇedpokla ´dejme, z ˇe proces stra ´vı ´ c ˇa ´st p sve ´ho c ˇasu c ˇeka ´nı ´m na dokonc ˇenı ´ I/O - pr ˇi n procesech bude pravde ˇpodobnost, z ˇe vs ˇech n procesu ˚ c ˇeka ´ na dokonc ˇenı ´ I/O pˆn - tj. vyuz ˇitı ´ CPU je u = 1 - pˆn - napr ˇ. pokud proces tra ´vı ´ 80% c ˇasu c ˇeka ´nı ´m, pak p=0.8: n=1 => u=0.2 (20% c ˇasu CPU vyuz ˇito) n=2 => u=0.36 (36%)
zos/p8mm.d
24. listopadu 2003
79
n=3 => u=0.488 (49%) n=4 => u=0.5904 (59%) ... n je tzv. stupen ˇ multiprogramova ´nı ´ (Pozor, je to zjednodus ˇenı ´, protoz ˇe pr ˇedpokla ´da ´me, z ˇe procesy be ˇz ˇı ´ navza ´jem neza ´visle, coz ˇ pr ˇi jednom CPU nenı ´ pravda.) * pr ˇi multiprogramova ´nı ´ je nutne ´ mı ´t vs ˇechny procesy (alespon ˇ c ˇa ´stec ˇne ˇ) zavedeny v pame ˇti, jinak je neefektivnı ´ * vy ´s ˇe uvedeny ´ pr ˇedpoklad o vy ´konnosti stac ˇı ´ pro odhad potr ˇebne ´ velikosti pame ˇti * napr ˇ. pr ˇedpokla ´dejme poc ˇı ´tac ˇ s 32 MB RAM, OS zabı ´ra ´ 16 MB a kaz ˇdy ´ uz ˇivatelsky ´ program 4 MB (tj. max. 4 programy v pame ˇti) * pokud c ˇeka ´nı ´ na I/O 80% c ˇasu, je vyuz ˇitı ´ CPU u = 1 - 0.8ˆ4 = 0.5904 * pr ˇida ´nı ´m dals ˇı ´ch 16 MB bychom zvy ´s ˇili stupen ˇ multiprogramova ´nı ´ na 8, vyuz ˇitı ´ CPU u = 1 - 0.8ˆ8 = 0.83222784 * pr ˇida ´nı ´m dals ˇı ´ch 16 MB na 12 procesu ˚, u = 0.9313 * tj. prvnı ´m pr ˇida ´nı ´m zvy ´s ˇı ´me pru ˚chodnost cca 1.4x (tj. o 40%), druhy ´m pr ˇida ´nı ´m 1.12x (tj. o 12%) - druhe ´ pr ˇida ´nı ´ pame ˇti se asi nevyplatı ´ [] Multiprogramova ´nı ´ s prome ˇnnou velikostı ´ oblasti ----------------------------------------------* kaz ˇde ´ ´ uloze je pr ˇide ˇlena pame ˇt’ podle poz ˇadavku * obsazenı ´ pame ˇti se postupne ˇ me ˇnı ´, jak ´ ulohy pr ˇicha ´zejı ´ a konc ˇı ´ Pr ˇı ´klad: new = proces vytvor ˇen end = proces ukonc ˇen
A
1. new A
D
D
D
A
A
B
B
B
B
C
C
C
C
C
3. new C
4. end A
5. new D
6. end B
7. new E
2. new B
E
[Obra ´zek je za ´roven ˇ pr ˇı ´klad algoritmu first fit, popsane ´ho da ´le.] * hlavnı ´ rozdı ´l od pevny ´ch oblastı ´ - poc ˇet, velikost, umı ´ste ˇnı ´ oblastı ´ se me ˇnı ´ s c ˇasem * zleps ˇuje vyuz ˇitı ´ pame ˇti - nejsme omezeni existujı ´cı ´mi oblastmi * komplikuje alokaci/dealokaci pame ˇti * postupem c ˇasu mu ˚z ˇe vznikat mnoho maly ´ch volny ´ch oblastı ´ (”de ˇr”) * teoreticky moz ˇne ´ pr ˇesunout vs ˇechny procesy sme ˇrem dolu ˚ - kompakce pame ˇti (memory compaction) * kompakce je ale draha ´ (napr ˇ. pokud pr ˇesun 1 byte 10 ns, 256 MB 2.7 sec) * proto se obvykle neprova ´dı ´, pokud nenı ´ k dispozici specia ´lnı ´ HW * OS musı ´ ve ˇde ˇt, ktera ´ pame ˇt’ je volna ´ a ktera ´ alokovana ´ * nejpouz ˇı ´vane ˇjs ˇı ´ zpu ˚soby zajis ˇte ˇnı ´ spra ´vy pame ˇti jsou: - pomocı ´ bitovy ´ch map - pomocı ´ seznamu ˚ - ”buddy systems”. Spra ´va pame ˇti pomocı ´ bitovy ´ch map ................................. * pame ˇt’ rozde ˇlena do alokac ˇnı ´ch jednotek stejne ´ de ´lky (velikost od ne ˇkolika bytu ˚ do ne ˇkolika KB)
24. listopadu 2003
80
zos/p8mm.d
* s kaz ˇdou alokac ˇnı ´ jednotkou sdruz ˇen 1 bit (napr ˇ. 0 = volno, 1 = obsazeno)
A
B
0 1 1 1 0 0 1 1 1
C
1 0 0 1 1
* mens ˇı ´ alokac ˇnı ´ jednotky = ve ˇts ˇı ´ bitmapa (a obra ´cene ˇ) * ve ˇts ˇ´ ı alokac ˇnı ´ jednotky = vı ´ce nevyuz ˇite ´ pame ˇti, protoz ˇe velikost procesu nebude pr ˇesne ˇ na ´sobek alokac ˇnı ´ jednotky Napr ˇı ´klad pr ˇi velikosti alokac ˇnı ´ jednotky 4 byty (32 bitu ˚) bude bitova ´ mapa zabı ´rat 1/33 pame ˇti, tj. ani pr ˇi male ´ alokac ˇnı ´ jednotce nenı ´ neu ´nosne ´. * vy ´hoda - konstantnı ´ velikost bitmapy * nevy ´hoda - pokud poz ˇadujeme ´ usek pame ˇti velikost N alokac ˇnı ´ch jednotek, musı ´ se v bitmape ˇ vyhledat N po sobe ˇ na ´sledujı ´cı ´ch nulovy ´ch bitu ˚ - draha ´ operace - proto se v praxi pro spra ´vu hlavnı ´ pame ˇti pr ˇı ´lis ˇ c ˇasto nepouz ˇı ´va ´. Spra ´va pame ˇti pomocı ´ seznamu ˚ ............................ * mys ˇlenka udrz ˇovat seznam alokovany ´ch a volny ´ch oblastı ´ (”procesu ˚” a ”de ˇr”) * kaz ˇda ´ poloz ˇka seznamu obsahuje: - informaci, zda se jedna ´ o ”proces” (P) nebo ”dı ´ru” (H) - poc ˇa ´tec ˇnı ´ adresu oblasti - de ´lku oblasti
A
hole starts at 0 size is 10 H 0 10
P 10 33
H 43 25
B
P 68 40
C
H 108 20
P 128 21
* pra ´ce se seznamem - pokud proces skonc ˇı ´, P se nahradı ´ H - pokud jsou 2H vedle sebe - slouc ˇı ´ se * seznam je dobre ´ mı ´t ser ˇazeny ´ podle poc ˇa ´tec ˇnı ´ adresy oblasti * je leps ˇı ´ mı ´t jako dvojite ˇ va ´zany ´ seznam - zna ´me polohu nove ´ H, podı ´va ´me se zda je pr ˇedchozı ´ nebo na ´sledujı ´cı ´ poloz ˇka take ´ H (pokud ano, slouc ˇı ´me) Jak alokovat pame ˇt’ pro procesy? Pokud jsou procesy a dı ´ry udrz ˇova ´ny v seznamu ser ˇazene ´m podle adresy oblasti, mu ˚z ˇeme pame ˇt’ pro procesy alokovat ne ˇktery ´m z na ´sledujı ´cı ´ch zpu ˚sobu ˚: * algoritmus first fit, c ˇesky ”prvnı ´ vhodna ´” - nejjednodus ˇs ˇı ´, prohleda ´va ´nı ´ seznamu dokud se nenajde dostatec ˇne ˇ velka ´ dı ´ra - dı ´ra se rozde ˇlı ´ na c ˇa ´st pro proces a nepouz ˇitou oblast (krome ˇ ma ´lo pravde ˇpodobne ´ho pr ˇı ´padu, z ˇe sedne pr ˇesne ˇ) - algoritmus je rychly ´, protoz ˇe prohleda ´va ´ co nejme ´ne ˇ. * algoritmus next fit, c ˇesky ”dals ˇı ´ vhodna ´” - mala ´ zme ˇna - prohleda ´va ´nı ´ zac ˇne tam, kde skonc ˇilo pr ˇedchozı ´ - simulace uka ´zaly, z ˇe next fit je jen o ma ´lo hors ˇı ´ nez ˇ first fit * algoritmus best fit, c ˇesky ”nejmens ˇı ´ vhodna ´” nebo ”nejleps ˇı ´ volna ´” - prohleda ´ cely ´ seznam, vezme nejmens ˇı ´ dı ´ru, do ktere ´ se proces vejde - algoritmus je pomalejs ˇı ´ (prohleda ´va ´ cely ´ seznam) - podle simulacı ´ take ´ vı ´ce ztracene ´ pame ˇti nez ˇ first fit nebo next fit, protoz ˇe zapln ˇuje pame ˇt’ maly ´mi nepouz ˇitelny ´mi dı ´rami. Mohli bychom jes ˇte ˇ uvaz ˇovat o variante ˇ worst fit (vz ˇdy vybere nejve ˇts ˇı ´ dı ´ru), simulace vs ˇak uka ´zaly, z ˇe to nenı ´ dobra ´ mys ˇlenka. Urychlenı ´ algoritmu ˚:
zos/p8mm.d
24. listopadu 2003
* vy ´s ˇe uvedene ´ algoritmy alokace mohou by ´t urychleny odde ˇleny ´mi seznamy pro proces a dı ´ry, za cenu sloz ˇitosti a rychlosti pr ˇi dealokaci - pr ˇi alokaci prohleda ´va ´me pouze seznam de ˇr - pr ˇi dealokaci musı ´ by ´t uvolne ˇna ´ oblast pr ˇesunuta ze seznamu procesu ˚ do seznamu de ˇr - ne ˇkdy se ale pr ˇesto vyplatı ´ (napr ˇ. v pr ˇı ´pade ˇ alokace pame ˇti pro data pr ˇicha ´zejı ´cı ´ od I/O zar ˇı ´zenı ´ - alokace musı ´ by ´t rychla ´) * dals ˇı ´ optimalizace algoritmu best fit - pokud odde ˇlene ´ seznamy, seznam de ˇr mu ˚ˇ ze by ´t podle velikosti (od nejmens ˇı ´ do nejve ˇts ˇı ´) - pr ˇi nalezenı ´ prvnı ´ vhodne ´ vı ´me, z ˇe je nejmens ˇı ´ vhodna ´ - stejne ˇ rychle ´ jako first fit, ale vys ˇˇ sı ´ rez ˇie na dealokaci (sousednı ´ dı ´ry nemusı ´ by ´t sousednı ´ v seznamu) Pokud jsou zna ´my dals ˇı ´ vlastnosti (resp. pravde ˇpodobnost distribuce poz ˇadovany ´ch vlastnostı ´) jsou moz ˇne ´ dals ˇı ´ algoritmy. Pozna ´mka pro zajı ´mavost (algoritmus quick fit) .............................................. Algoritmus quick fit udrz ˇuje samostatne ´ seznamy pro dı ´ry ne ˇktery ´ch c ˇaste ˇji poz ˇadovany ´ch de ´lek. Jako centra ´lnı ´ datovou strukturu mu ˚z ˇeme mı ´t tabulku, jejı ´z ˇ prvnı ´ poloz ˇka ukazuje na hlavu seznamu de ˇr velikosti 4 KB, dals ˇı ´ 8 KB, ... napr ˇ. dı ´ry ostatnı ´ch velikostı ´ mohou by ´t v samostatne ´m seznamu. Alokace poz ˇadovane ´ velikosti je velmi rychla ´, ale ope ˇt je obtı ´z ˇne ´ sdruz ˇova ´nı ´ sousedu ˚. [] * jak us ˇetr ˇit pame ˇt’ - mı ´sto samostatne ´ho seznamu de ˇr mohou by ´t vyuz ˇity dı ´ry - prvnı ´ slovo dı ´ry mu ˚z ˇe obsahovat velikost dı ´ry, druhe ´ ukazatel na na dals ˇı ´ dı ´ru - takto funguje napr ˇ. aloka ´tor pame ˇti pro proces v jazyce C pod UNIXem (pouz ˇı ´va ´ algoritmus next fit, viz pr ˇı ´klad 8.7 v [Kernighan & Ritchie]) Pozna ´mka (asymetrie mezi procesy a dı ´rami) Dve ˇ sousedı ´cı ´ volne ´ oblasti (H) se slouc ˇı ´, zatı ´mco dva procesy (P) se neslouc ˇı ´ - pr ˇi norma ´lnı ´m be ˇhu je poc ˇet H polovic ˇnı ´ oproti poc ˇtu P. [] Mechanismus ”buddy system” .......................... * me ˇjme seznamy volny ´ch bloku ˚ velikosti 1, 2, 4, 8, 16 ... alokac ˇnı ´ch jednotek az ˇ do seznamu bloku ˚ velikosti cele ´ pame ˇti * na zac ˇa ´tku ves ˇkera ´ pame ˇt’ volna ´, vs ˇechny seznamy jsou pra ´zdne ´ krome ˇ seznamu obsahujı ´cı ´ho 1 poloz ˇku velikosti pame ˇti * napr ˇ. alokac ˇnı ´ jednotka 1 KB, pame ˇt’ velikosti 64 KB (7 seznamu ˚) * pr ˇijde-li poz ˇadavek, zaokrouhlı ´ se nahoru na mocninu 2 (napr ˇ. poz ˇadavek na 7 KB se zaokrouhlı ´ na 8 KB) * blok velikosti 64 KB se rozde ˇlı ´ na 2 bloky velikosti 32 KB, tzv. ”buddies” * protoz ˇe jes ˇte ˇ moc velke ´, jeden z nich (ten s niz ˇs ˇı ´ adresou) se rozde ˇlı ´ na 2 bloky 16 KB, jeden z nich na 2 bloky 8 KB, jeden z nich alokova ´n
81
24. listopadu 2003
82
32
32
32
32
16
16
16
64 32 16
zos/p8mm.d
32
32
32
32
32
8 8
8 4 4
8 4 4
8 4 4
8 4 4
8
8
8
8
8
8
8
8
8
8
8
8
16
* poz ˇadavek na 5 KB (tj. 8 KB), je pr ˇide ˇlen druhy ´ 8 KB blok * poz ˇadavek na 3 KB (tj. 4 KB), dals ˇı ´ 16 KB blok se rozde ˇlı ´ na 8+8 K, niz ˇs ˇı ´ 8 K blok se rozde ˇlı ´ na 4+4 K, niz ˇs ˇı ´ se pr ˇide ˇlı ´ (tj. nejmens ˇı ´ dostatec ˇne ˇ velky ´ blok se rozde ˇlı ´) * uvolne ˇnı ´ pame ˇti: pokud jsou volne ´ oba sousednı ´ bloky stejne ´ velikosti (”buddies”), spojı ´ se do jednoho ve ˇts ˇı ´ho bloku Neefektivnı ´ ve vyuz ˇitı ´ pame ˇti (chci-li 9 K, dostanu 16 K), ale rychly ´: * alokace pame ˇti - vyhleda ´nı ´ v seznamu dostatec ˇne ˇ velky ´ch de ˇr * sluc ˇova ´nı ´ - vyhleda ´nı ´ buddy.
Pozna ´mka: Vy ´s ˇe uvedena ´ sche ´mata (pevne ´ pr ˇide ˇlenı ´, prome ˇnne ´ oblasti) se pouz ˇı ´vala v historicky ´ch da ´vkovy ´ch syste ´mech. V modernı ´ch univerza ´lnı ´ch syste ´mech se uvedena ´ sche ´mata pro alokaci pame ˇti procesu ˚m nepouz ˇı ´vajı ´, protoz ˇe je zastupuje mechanismus virtua ´lnı ´ pame ˇti (o ktere ´m budeme hovor ˇit zanedlouho). Uvedene ´ algoritmy (first fit, ...) vs ˇak majı ´ obecne ˇjs ˇı ´ platnost. V souc ˇasny ´ch syste ´mech se tyto algoritmy pouz ˇı ´vajı ´ pro alokaci pame ˇti uvnitr ˇ ja ´dra OS nebo uvnitr ˇ procesu. Pr ˇı ´klad: Ja ´dro syste ´mu Linux be ˇz ˇı ´ ve fyzicke ´ pame ˇti, pro spra ´vu pame ˇti ja ´dra pouz ˇı ´va ´ buddy system. Pr ˇı ´klad: Fce malloc(3) v jazyce C z ˇa ´da ´ OS o ve ˇts ˇı ´ blok pame ˇti a zı ´skanou pame ˇt’ pak aplikaci pr ˇide ˇluje napr ˇ. algoritmem first fit. Algoritmy majı ´ ovs ˇem obecne ˇjs ˇı ´ platnost a lze je pouz ˇı ´vat i v jiny ´ch kontextech. Pr ˇı ´klad: Linux spravuje pomocı ´ odkla ´dacı ´ prostor pomocı ´ bitove ´ mapy algoritmem next fit. []
❉
