sobota 6. května 2006

Souhrn z logiky

Hruby vytah ze skript z logiky od prof. stepanka - pouze vety a axiomy bez dukazu a jen tam, kam jsme dosli na cvicenich. Vhodne jako pomucka na pisemku. U kazde vety je cislo stranky, na ktere ji lze najit ve skriptech.

Donwload:logika-souhrn.pdf 90.9kB

Zaklady zakladu operacnich systemu

Otazky, co zde nejsou, mi prosim poslete (pokud mozno i s resenim :) ). Opravy chyb (faktickych i preklepu) samozrejme vitam.

Zkouska ze ZOS probihala takto: Byli jsme rozesazeni (mista bylo dost), dostali jsme zadani - jedna A4 z jedne strany potistena. Prvnich 6 otazek bylo zaskrtavacich, dalsi 3 okecavaci. V zaskrtavaci casti je vzdy prave jedna odpoved spravne. Nekteri odevzdali jiz za par minut, ale prumerny cas bych odhadla tak na 30-40 minut. Odevzdavalo se na stul primo Yaghobovi na hromadku, ten to opravoval spravedlive odspodu. Obcas se tvaril, ze se dozvida skutecne nove veci :)

Pokud mi poslete opravy a doplneni, budu moc rada (i kdyz mi provedeni opravy obcas trva trochu dele, nez by bylo slusne).

Zde uvedene informace jsem ukradla z techto materialu:

Dekuju za ne, bez nich bych to ani nezkousela dat dohromady.

Nejdrive otazky zaskrtavaci. V testu jsou vzdy moznosti, ale protoze se obcas nezachovaly, byvaji tu pouze spravne odpovedi.



Raid

0. otazka:
kolik disku muze vypadnout pri raid X? (misto X je konkretni hodnota)
odpoved:
jbod - 0 (nekolik disku za sebou poskladanych, tvari se jako jeden)
raid 0 - 0 (pouze stripovani => pouze zrychleni - data se ctou z vice disku soucasne)
raid 1 - vhodne zvolena polovina (2 disky, druhy disk je kopii prvniho)
raid 0+1 (raid 10) - vhodne zvolena polovina (2+2 disky, dvojice jsou si kopii, stripovani)
raid 5 - 1 (distribuovana parita (po stripech))
raid 50 - jeden z kazde poloviny (dva stejne raid 5 spojeny k sobe)
raid 2 - 1 (7 disku, haminguv paritni kod)
raid 3 - 1 (5 disku, z toho 1 paritni)
raid 4 - 1 (5 disku, z toho 1 paritni, stripovani)
raid 6 - 2 (2 paritni disky, distribuovana parita)

vyhladoveni

1. otazka:
co je to vyhladoveni?
odpoved:
sice to porad neco dela, ale nic uzitecneho - viz filozofove (pokladaji a berou vidlicky vsichni soucasne)

problem obedvajicich filozofu: pet filozofu sedi okolo kulateho stolu. kazdy filozof ma pred sebou talir spaget a jednu vidlicku. spagety jsou bohuzel slizke a je treba je jist dvema vidlickami. zivot filozofa sestava z obdobi jidla a obdobi premysleni. kdyz dostane hlad, pokusi se vzit dve vidlicky. kdyz se mu to podari, naji se a vydlicky odlozi.
jezeni je kriticke - kdyz ji jeden filozof, nemohou jist ti vedle. operace zvednuti vidlicky je blokujici, protoze se snadno stane, ze vsichni drzi vidlicky nahore a cekaji. nabizi se moznost reseni: pokud nemuzu jist, vidlicku polozim a zkusim znovu. to ovsem neni spravne - filozofove neustale (vsichni soucasne) berou vidlicky a pokladaji je na stul. a tato situace se nazyva vyhladovenim.

semafory

2. otazka:
kdy se proces zablokuje na semaforu - citac je cele cislo. jaka je hodnota citace pred operaci down?
odpoved:
<=0 u celociselnych semaforu: je-li hodnota citace >= 0, pokracuje proces dal, jinak se zablokuje.
3. otazka:
kdy nastave zablokovani u nezaporneho semaforu pri DOWN?
odpoved:
pokud je citac roven 0

u kladnych semaforu: proces pokracuje dal, pokud je jeho citac > 0. pokud se stane nulovym, proces se zablokuje, i operace DOWN.


vypadky stranek

postup reseni napsal david

Fakt:
Nejvyssi uroven strankovacich tabulek je vzdy v nestrankovana pameti.

Pozorovani 1:
Data se presouvaji, tudiz velikost pameti, se kterou se pracuje je 2-krat velikost dat. Z jedne poloviny velikosti dat se data ctou, do druhe se zapisuji.

Pozorovani 2:
Vypadek stranky muze nastat na ctyrech mistech.

  • Vykonavana instrukce nemusi byt v pameti.
  • Pamet, ze ktere se ctou data nemusi byt v pameti.
  • Pamet, kam se zapisuje nemusi byt v pameti.
  • Strankovaci tabulky druhe a vyssi urovne nemusi byt v pameti.
Tvrzeni:
Pri (K-1)-urovnovem strankovani je maximalni pocet vypadku roven poctu vypadku pri K-urovnovem strankovani bez vypadku v druhe urovni strankovani.
4. otazka:
jaky je maximalni pocet vypadku? 2B instrukce, 8kB dat, 4kB stranka, 3 urovne strankovani, tabulky maji 1024 polozek.

odpoved:
20

Zajima nas maximalni pocet stranek, tudiz pocitame worst-case. Samotna instrukce je na 2B, muze se tedy vyskytnout na rozhrani 2 stranek a zpusobit dva vypadky. Ve treti urovni strankovani na kazdou tuto stranku ukazuje pointer. Pro dve stranky muze tato informace byt opet na rozhrani dvou stranek a tudiz zpusobit dalsi 2 vypadky stranky. Pro tyto dve stranky je pak v druhe urovni totez, tudiz dalsi dva vypadky jsou mozne v druhe urovni strankovani. Pro tyto dve stranky je pak v prvni urovni totez, ale tam jsou dle Faktu udaje vzdy nestrankovane. Samotna instrukce tak zpusobi az 2+2+2=6 vypadku. Podle Tvrzeni by pri dvouurovnovem strankovani bylo na instrukci maximalne 2+2=4 vypadku a pri jednourovnovem pouze 2 vypadky.

Nyni pocitame data. Podle Pozorovani 1 a 2 je zrejme, ze staci spocitat pouze vypadky pro jednu datovou cast. U druhe bude maximalni pocet vypadku stejny a staci tedy vynasobit pocet pro jedny data dvema. Takze 8kb dat lze nasklad maximalne do tri 4kb stranek. To jsou tri vypadky. Tyto tri stranky jsou ve treti urovni referencovany maximalne na rozhrani dvou stranek a tudiz zde mohou zpusobit 2 vypadky. Stejne jako u instrukce pak v druhe urovni mohou nastat take 2 vypadky. Celkem tedy na tato data pripadne az 3+2+2=7 vypadku stranek. Celkem na data tedy az 14 vypadku pri triurovnovem strankovani. Opet podle Tvrzeni je pocet vypadku pri dvou urovnich strankovani maximalne 10 a pri jedne urovni 6.

Celkovy pocet vypadku je tedy az 20 pro tri urovne strankovani, 14 pri dvou urovnich a 8 pri jedne urovni.
5. otazka:
jaky je maximalni pocet vypadku? 2B instrukce, 8MB dat, 4kB stranka, 3 urovne strankovani, tabulky maji 1024 polozek.

odpoved:
4114

Resi se podobne jako s 8kb. Vypadky pro instrukci jsou totozne. Pro data je vsak treba znat pocet polozek posledni urovne strankovani. V zadanich je 1024. 8MB dat se da rozlozit az do 2049 stranek. To by znamenalo, ze jsou treba 3 bloky (3 stranky - stranka ma 4096, je zde 1024 polozek, coz odpovida realne 4 byte na polozku, coz odpovida 32-bitovym pointerum) strankovani posledni urovne, protoze je jich pouze 1024 v bloku. To dava 2049 vypadku za data a 3 vypadky za posledni uroven strankovani. Dal jiz je postup totozny a pro druhou uroven vychazi opet jen 2 vypadky.

Celkovy pocet vypadku pro tri urovne je tedy 6 za instrukce a 2*(2049 za data, 3 za treti uroven, 2 za druhou uroven) to je dohromady 6+4098+6+4 = 4114 vypadku. Opet podle Tvrzeni se dopocitame 4108 vypadku pro dve urovne strankovani a 4100 vypadku pro jednu uroven.

6. otazka:
kolik vypadku stranek muze maximalne nastat? 2B instrukce, 4kB stranky, 1 uroven strankovani, presouva se 8MB
odpoved:
4100
7. otazka:
kolik vypadku stranek muze maximalne nastat? 2B instrukce, 4kB stranky, 2 urovne strankovani, presun 8MB
a) 4108
b) 4102
c) 4106
d) 4096
odpoved:
a
8. otazka:
kolik vypadku stranek muze maximalne nastat? 2B instrukce, 4kB stranky, 1 uroven strankovani, presouva se 8kB
odpoved:
8
9. otazka:
kolik vypadku stranek muze maximalne nastat? 2B instrukce, 4kB stranky, 2 urovne strankovani, presun 8kB
a) 8
b) 10
c) 14
d) 12
odpoved:
c
10. otazka:
co je vypadek stranky?
a) vypadnuti listu ze sesitu
b) nenalezeni klice v asociativni pameti
c) vyhozeni stranky z pameti
d) udalost, ktera nastane pri neexistenci mapovani
odpoved:
d
11. otazka:
mame 4 ramce (na zacatku prazdne), sekvenci pristupu nize zadanou, pouzivame metodu LRU. ke kolika vypadkum dojde?
sekvence: 1 2 3 4 5 6 2 4 2 3 1
odpoved:
9

LRU ... pro ucely tohoto prikladu (pro vypocet na papire):
kazda stranka ma citac, do ktereho se pri kazdem pouziti zapise cas. obeti vyhazovu se potom stane ta stranka, ktera je 'nejstarsi' (nejdele nebyla pouzita). tedy budeme si zapisovat stranky do rady, ty starsi vlevo, mladsi vpravo. reseni po krocich:
1) 1 2 3 4 (4 vypadky)
2) 2 3 4 5 (1 vypadek)
3) 3 4 5 6 (1 vypadek)
4) 4 5 6 2 (1 vypadek)
5) 5 6 2 4 (bez vypadku)
6) 5 6 4 2 (bez vypadku)
7) 6 4 2 3 (1 vypadek)
8) 4 2 3 1 (1 vypadek)
celkem tedy: 9 vypadku
12. otazka:
mame 4 ramce (na zacatku prazdne), sekvenci pristupu nize zadanou, pouzivame metodu LRU. ke kolika vypadkum dojde?
sekvence: 1 3 5 7 2 3 4 5 2 4 6 8
a) 5
b) 9
c) 10
d) 8
odpoved:
b

podobne reseni jako v predchazejicim prikalde:
1) 1 3 5 7 (4)
2) 3 5 7 2 (1)
3) 5 7 2 3 (0)
4) 7 2 3 4 (1)
5) 2 3 4 5 (1)
6) 3 4 5 2 (0)
7) 3 5 2 4 (0)
8) 5 2 4 6 (1)
9) 2 4 6 8 (1)
celkem: 9
13. otazka:
mame 4 ramce (na zacatku prazdne), sekvenci pristupu nize zadanou, pouzivame metodu LRU. ke kolika vypadkum dojde?
sekvence: 1 2 3 4 5 6 3 6 2 5 1
a) 5
b) 9
c) 10
d) 8
odpoved:
d

podobne reseni jako v predchazejicim prikalde

deadlock

14. otazka:
mame procesy A, B, C, D a zarizeni 1, 2, 3, 4. Ve kterem kroku se zablokuji?
1) A zada 2
2) A zada 3
3) B zada 1
4) A uvolnuje 2
5) C zada 4
6) D zada 4
7) C zada 2
8) C uvolnuje 4
9) B zada 4
10) D zada 3
11) A zada 1
12) C zada 1

moznosti:
a) 6
b) 10
c) 11
d) 9
odpoved:
c

algoritmus reseni: budeme kreslit graf. vrcholy: procesy a prostredky. v nasem pripade A, B, C, D a 1, 2, 3, 4.
  • pozadavek - pokud napr. "A zada 1":
    • pokud z 1 nevede hrana, nakreslime hranu z 1 do A (1 jiz nekomu venuje pozornost)
    • pokud z 1 hrana vede, nakreslime hranu z A do 1 (A touzi po 1)
  • uvolneni - napr. "A uvolnuje 1" smazeme sipku z 1 do A a
    • vedeli do 1 nejaka sipka, jednu vyber a otoc ji.
opakujeme, dokud je zadani :) pokud v nejakem tomto kroku vznikne v garfu orientovana kruznice, nastal deadlock.

pro tento pripad konkretne bude postupovat takto:
0) nakreslime graf:



A B C D



1 2 3 4

1) A zada 2

A<-+ B C D
|
|
|
1 +--2 3 4

2) A zada 3 ... pridame hranu 3 -> A
3) B zada 1 ... pridame 1 -> 1
4) A uvolnuje 2 ... odebereme 2 -> A
5) C zada 4 ... pridame 4 -> C
6) D zada 4 ... pridame D -> 4
7) C zada 2 ... pridame 2-> C
8) C uvolnuje 4 ... odebereme 4 -> C; otocime D -> 4 na 4 -> D
9) B zada 4 .., pridame B -> 4
10) D zada 3 ... pridame D -> 3
11) A zada 1 ... pridame A -> 1 a POZOR, uz mame cyklus: A - 1 - B - 4 - D - 3 - A
tedy v kroku 11 nastane deadlock
15. otazka:
mame procesy A, B, C, D a zarizeni 1, 2, 3, 4. Ve kterem kroku se zablokuji?
1) A zada 2
2) A zada 3
3) B zada 1
4) A zada 4
5) D zada 4
6) C zada 4
7) A uvolnuje 4
8) D zada 1
9) B zada 3
10) A zada 4
11) A zada 1
12) C zada 1

moznosti:
a) 6
b) 10
c) 11
d) 9
odpoved:
b

reseni stejnym postupem, jako predchozi priklad
16. otazka:
algoritmus bankere je jednou z moznosti pro:
a) urceni stranky, ktera bude odstranena z pameti
b) detekce zablokovani a zotaveni ze zablokovani
c) predchazeni (napadani coffmanovych podminek) zablokovani
d) predchazeni (vyhnuti se) zablokovani
odpoved:
d

bankeruv algoritmus: banker ma klienty a tem slibil jistou vysku uveru. banker vi, ze ne vsichni klienti potrebuji plnou vysi uveru najednou. klienti obcas navstivi banku a zadaji posupne o prostredky do maximalni vysky uveru. az klient skonci s obchodem, vrati bance vpujcene penize. banker penize pujci pouze tehdy, zustane-li banka v bezpecnem stavu.
17. otazka:
mezi coffmanovy podminky nepatri:
a) nepreemptivni prodelovani
b) cekani v kruhu
c) preemptivni pridelovani
d) postupne pridelovani
odpoved:
c

coffmanovy podminky ... podminky pro vznik zablokovani
jejich zneni:
1) vzajemne vylouceni (kazdy prostredek je bud vlastnen prave jednim procesem, nebo je volny)
2) drz a cekej (proces nemusi uvolnit prostredky, ktere drzi, kdyz zada o dalsi)
3) neodnimatelnost (nepreemptivnost, proces muze vratit prosredek pouze dobrovolne, nemuse mu byt odebran)
4) cekani do kruhu (existuje kruhovy retez procesu, kde kazdy z nich ceka na prostredek vlastneny dalsim clenem v retezu)

zpravy

18. otazka:
randez-vous je:
a) setkani dvou entit na jednom miste v kodu pomoci synchronizacnich primitiv...
b) zablokovani dvou procesu pomoci synchronizacnich primitiv...
d) rande
odpoved:
asi a

specialni situace pri posilani zprav - pokud ma schranka nulovou velikost. v takovem pripade je po odeslani zpravy zablokovan i odesilatel (po SEND). odesilatel ceka na prijemce, az si zpravu vyzvedne. po probehnuti RECEIVE (po prijmuti zpravy) se oba procesy odblokuji a rozebehnou.
19. otazka:
randez-vous je:
a) cekani na zpravu
b) odeslani zpravy
c) odeslani zpravy bez vyrovnavacich front zprav
d) odeslani s vyrovnavacimi frontami zprav
odpoved:
c

vysvetleni v predchozi otazce

pamet

20. otazka:
co resi tabulka stranek?
a) prepocet realne adresy na fyzickou
b) prepocet fyzicke adresy na virtualni
c) prepocet cisla ramce na cislo stranky
d) prepocet cisla stranky na cislo ramce
odpoved:
d

stranky jsou useky ve virtualni pameti, ramce jsou useky fyzicke pameti.
21. otazka:
co je asociativni pamet?
a) pamet s postupnym prohledavanim podle klice
b) pamet s paralelnim pristupem na adresu
c) pamet s paralelnim hledanim podle klice
d) pame s dvojitym paralelnim prohledavanim cele pameti
odpoved:
c

asociativni pamet vyuziva toho, ze v kratkem case potrebuje program jen malo stranek. aderuje se klicem. v plne asociativni pameti probiha hledani ve vsech radcich paralelne. uklada se do ni aktualni mapovani - rychleji s v ni hleda (bez pristupu do pameti se dozvim cislo ramce). pokud v ni neni namapovano zrovna, tak se najde pres tabulky stranek a namapuje se i sem.
22. otazka:
jake jsou zakladni hw pozadavky pro podporu strankovani?
a) prepocet cisla stranky na cislo ramce, rozpoznani vypadku stranky
b) prepocet cisla stranky na cislo ramce, rozpoznani vypadku stranky, asociaivni pamet
c) rozpoznani vypadku stranky, viceurovnove strankovani
d) prepocet cisla stranky na cislo ramce, asociativni pamet
odpoved:
a

asociativni pamet a viceurovnove strankovani nejsou nutne

cekani

23. otazka:
k cemu je vhodne aktivni cekani?
odpoved:
pro predpokladane kratke doby cekani

aktivni cekani znamena, ze se cekajici aktivne v intervalech pta "uz?", "uz?", "porad ne?", "uz?". pokladani takovychto dotazu je narocne.

kriticke sekce

24. otazka:
co se pouziva pro velmi rychly pristup ke kriticke sekci?
odpoved:
spinlock

proc, to se ke me jeste nedoneslo, tak jeslti nekdo vite, napiste mi prosim.
okecavaci otazky

bezpecnost

25. otazka:
druhy kryptografickych systemu
odpoved:
symetricke a asymetricke.
symetricke: blokove sifry (DES, AES, IDEA), prudove sifry (SEAL). vyhody: kratke klice, vysoka datova propustnost, slucovani vice sifer vytvari silnejsi sifru. nevyhody: nutnost utajeni klicu na obou konich, je treba casto menit klice, porebna overena treti strana (TTP - Truste Third-Party)
asymetricke: verejny a privatni klic, RSA, DSA. vyhody: tajny je pouze privatni klic, neni potreba tak caste meneni klice, neni potreba TTP. nevyhody: mnohem pomalejsi, nez symetricke sifry, mnohem delsi klice, o zadnem schematu verejneho klice nebylo dokazano, ze je bezpecne.
26. otazka:
model utocnika podle doleva a yao
odpoved:
  • moznost ziskat libovolnou zpravu putujici po siti
  • je pravoplatnym uzivatelem site, tedy muze zahajit komunikaci s jinymi uzivateli
  • muze se stat prijemcem zprav kohokoli
  • muze zasilat zpravy komukoliv zosobnenim se za jineho uzivatele
  • nemuze uhadnout nahodne cislo z dosatecne velikeho prostoru
  • bez spravneho klice nemuze najit zpravu k sifrovane zprave ani vytvori platnou sifrovanou zpravu z dane zpravy. vse vzhledek k nejakemu sifrovacimu algoritmu
27. otazka:
utoky na kryptograficke protokoly
odpoved:
  • prehrani zprav: utocnik odposlechne zpravy a znovu je posle (reseni casovym razitkem)
  • man in the middle: utocnik se pro A vydava za B a pro B vypada jako A (reseni overenim identyty - napr. ssh)
  • paralelni spojeni: nekolik behu protokolu provadenych soucasne pod rizenim utocnika
  • odrazeni: A zahaji komunikaci, utocnik ji zachyti, upravi a posle zpet A
  • prokladani: nekolik behu protokolu pod rizenim utocnika - zpravy z jednoho posila do jineho atd.
  • chyba typu: nedodrzeni presneho semantickeho vyznamu zpravy
  • vypusteni jmena: pokud v protokolu neni poznat, kdo za to muze
  • chybne pouziti sifrovaci sluzby: spatny algoritmus pouzity na nevhodnem miste
28. otazka:
kryptograficky system - definice
odpoved:
  • M: prostor zprav (plaintext)
  • C: prostor sifrovanych zprav (ciphertext)
  • K: prostory sifrovacich a desifrovacich klicu (K, K')
  • G: efektivni algoritmus generovani klicu G: N -> KxK'
  • E: efektivni algoritmus sifrovani E: MxK -> C
  • D: efektivni algoritmus desifrovani D: CxK' -> M
  • pro ke z K a m z M: c=E_ke(m)
  • pro kd z K' a c z M: m=D_kd(c)
  • pro vsechny m z M a pro vsechny ke z K musi esxistovat kd tak, ze D_kd(E_ke(m))=m
29. otazka:
cile bezpecnostnich utoku
odpoved:
  1. duvernost dat: zjisteni obsahu
  2. celistvost dat: zmena nebo poskozeni dat
  3. dostupnost sytemu: system je zaneprazdnen cimsi nesmyslnym a uzivatele ignoruje

procesy

30. otazka:
procesy a vlakna
odpoved:
identifikace procesu podle id, hierarchie procesu jen na nekterych systemech(unix ano, windows ne).
vlakna: 3 urovne implementace:
  • uzivatelsky prostor: os o vlaknech nevi, stara se o to knihovna
  • jadro: velky pocet vlaken zbusoboval potize
  • hybrid: os zna vlakna a umi s nimi pracovat, ale navic pomaha i knihovna (planuje uzivaelska vlakna)
pri spusteni dostane proces jedno vlakno , umi si vytvorit dalsi. proces sdruzuje prostredky sdilene vlakny. na unixu skutecne vlakno neni, kazdy proces je vlakno, jen se tvari jako proces :) a procesy mezi sebou mohou sdilet prostredky
31. otazka:
definujte, co jsou zpravy a k nim prislusna systemova volani
odpoved:
zpravy: systemova volani SEND a RECEIVE pro zasilani a prijem zprav. zprava je nejaka prenasena informace mezi odesilatelem a prijemcem.
SEND zasle zpravu. nikdy se nezablokuje. pokud na zpravu ceka prijemce operaci RECEIVE, je mu zprava dorucena a prijemce odblokovan.
RECEIVE zpravu prijima. pokud zadna zprava neni dostupna, prijimajici proces je zablokovan.

SEND a RECEIVE musi byt atomicke.

je treba vyresit problem adresace, tj. urceni odesilatele a prijemce. lze resit napr. identifikaci procesu na danem pocitaci. jinym resenim je zavedeni schranek (mailboxu) a adresace pomoci identifikace schranky. schranka je vyrovnavaci pamet typicky pevne delky. do ni jsou zpravy ukladany operaci SEND a z ni vybirany operaci RECEIVE. schranka modifikuje operaci SEND: pokud je schranka plna, zablokuje se i SEND.

zajimavym pripadem je situace, kdy je schránka nulove velikosti. pokud je odesilatelem proveden SEND a jeste tam neni zadny prijemce, cekajici operaci RECEIVE, musi odesilatel pockat. podobne prijemce ceka na odesilatele, az neco zasle. po predani zpravy, tj. je provedeni operace SEND i RECEIVE na jednu schranku, se oba procesy opet rozbehnou. tento pripad se nazyva dostavenicko (randezvous).

synchronizace

32. otazka:
definujte monitor
odpoved:
pro zjednoduseni prace a zamezeni chyb pri pouziti semaforu bylo navreno synchronizacni primitivum monitor. monitor je soubor funkci, promennych a datovych struktur, ktere jsou sdruzeny do zvlastniho baliku. procesy smi volat funkce z monitoru, kdykoliv chteji, ale nemaji pristup k promennym monitoru z funkci mimo monitor. navic monitor zarucuje, ze v jednom okamziku muze byt aktivni nejvyse jeden proces v jedne instanci monitoru.

monitor je konstrukci programovaciho jazyka a prekladac tudiz vi, ze funkce monitoru je treba prekladat jinak. zalezi na prekladaci, jak implementuje monitory (typicky pomoci semaforu). protoze vzajemne vylouceni zarizuje prekladac a ne programator, zabrani se mnoha chybam. staci pouze vedet, ze vsechny kriticke operace je treba provadet v monitorech. blokovani procesu uvnitr funkci monitoru pomoci podminenych promennych a operacemi WAIT a SIGNAL na nich definovanych. podminene promenne nejsou citace (na rozdil od semaforu, je tam fronta zablokovanych procesu). kdyz funkce monitoru zjisti, ze nemuze pokracovat, vola operaci WAIT a zablokuje aktivni proces v monitoru. to umozni jinemu procesu vniknout do monitoru. jiny proces muze byt probuzen pomoci operace SIGNAL (jeden zcekajicich z mnoziny zablokovanych procesu na dane podminene promenne). tady ale vznika problem, ze v jednom okamziku jsou dva procesy v jedne instanci monitoru.
existuji dve reseni: spustit probuzeny proces a druhy uspat, nebo proces volajici SIGNAL okamzite opusti monitor.
33. otazka:
zneni znamych synchronizacnich problemu
odpoved:
  • problem producent-konzument: producent (tovarna) produkuje predmety. konzument (obchod) je spotrebovava (prodava). mezi nimi je sklad pevne velikosti. konzument nema co prodavat, kdyz je sklad prazdny. producent prestane vyrabet, kdyz je sklad plny.
  • problem obedvajicich filosofu: pet filozofu sedi okolo kulateho stolu. kazdy filozof ma pred sebou talir spaget a jednu vidlicku. spagety jsou bohuzel slizke a je treba je jist dvema vidlickami. zivot filozofa sestava z obdobi jidla a obdobi premysleni. kdyz dostane hlad, pokusi se vzit dve vidlicky. kdyz se mu to podari, naji se a vydlicky odlozi.
    jezeni je kriticke - kdyz ji jeden filozof, nemohou jist ti vedle. operace zvednuti vidlicky je blokujici, protoze se snadno stane, ze vsichni drzi vidlicky nahore a cekaji. nabizi se moznost reseni: pokud nemuzu jist, vidlicku polozim a zkusim znovu. to ovsem neni spravne - filozofove neustale (vsichni soucasne) berou vidlicky a pokladaji je na stul.
  • problem ospaleho holice: holic ma ve sve oficirne kreslo na holeni zakaznika a pevny pocet sedacek pro cekajici zakazniky. pokud v oficirne nikdo neni, holic se posadi a spi. pokud prijde prvni zakaznik a holic spi, holic seprobudi a posadi si zakaznika do kresla. pokud prijde zakaznik a holic uz striha a je volne misto v cekarne, posadi se, jinak odejde.
34. otazka:
definujte semafor
odpoved:
implementovan OS, kazdy ma vlastni frontu, citac a fronta uspanych procesu, atomicke operace DOWN/UP.

nezaporny semafor:
DOWN: kdyz je citac vetsi nez 0, zmensi se o jedna a pokracuje se. pokud je roven 0, tak zablokovani a proces do fronty cekajicich.
UP: pokud neprazdna fronta, probudi nejaky proces za DOWN, jinak zvetsi citac

nebo

celociselny semafor (i zaporny):
DOWN: vzdy zmensi citac, kdyz citac>=0, pokracuje, jinak zablokovani
UP: vzdy zvetsi citac, pokud citac<=0 a neprazdna fronta, tak se odblokuje libovolny proces

souborovy system

35. otazka:
ukoly souboroveho systemu
odpoved:
  • uchovani perzistentnich dat
  • udrzovani informace o volnem miste
  • vytvoreni adresarove struktury
36. otazka:
ukladanie suborov na disk
odpoved:
  1. souvisla alokace: souvisly sled bloku, staci si pamatovat cislo prvniho bloku
    • lepsi prace s diskem
    • problem pri hledani volneho mista
    • problem pri zvetsovani souboru
  2. spojovana alokace:
    • pospojovani bloku pouzitych pro soubor
    • modifikace FAT - premisteni spojoveho seznamu do specialni oblasti disku
  3. indexova alokace: UNIX a i-node

pamet

37. otazka:
segmentace
odpoved:
strankovani chape adresovy prostor jako jednorozmerny. segmentace zavadi druhy rozmer. segment je nezavisly adresovy prostor sestavajici z adres od 0 do limitu segmentu. segmenty mohou mit ruzne velikosti, ktere se mohou v prubehu casu i menit. segment ma sve umisteni ve fyzicke pameti (neviditelne pro procesy). kazda adresa je pak dvojici (s,d), kde s je cislo segmentu a d je adresa a segmentu. segmenty mohou byt pritomny i nepritomny (vypadek, jako u strankovani). pri alokacio segmentu se pouzivaji algoritmy typu first-fit. moznost kombinace strankovani a segmentace.
38. otazka:
asociativni pamet
odpoved:
reií problem rychlosti pristupu do strankovacich tabulek v pameti. vyuziva lokality programu, tj. program v jistem casovém useku vyuziva pouze nekolik stranek pameti. asociativni pamet predchazi pruchodu strankovacimi tabulkami pri kazdem pametovem odkazu. obsahuje nekolik polozek (radove desitky) a kazda polozka je delena na dve casti: klic a hodnotu. V klici jsou cisla stranek a hodnoty jsou cisla rámcu. pri prevodu virtualni adresy na fyzickou adresu se nejprve paralelne prohledáva asociativni pamet na cislo stranky podle klice. pokud tento dotaz na asociativni pamet uspeje, jiz se nepristupuje do strankovacich tabulek. pokud v asociativni pameti hledane cislo stranky neni, pouzije procesor strankovaci tabulky pro nalezena mapovani. pokud mapovani uspeje, je zapsano do asociativni pameti (na ukor jine polozky). pokud ne, nastane vypadek stranky.
39. otazka:
strankovani a segmentace, rozdil mezi strankovanim a segmentaci
odpoved:
zaklady strankovani:
virtualni adresovy prostor (vap) je rozdelen na useky stejne delky - stranky (velikost je mocnina 2). fyzicky adresovy prostor (fap) je rozdelen na useky stejne delky jako stranky - rámce. pomoci strankovacich tabulek se prevadi vap adresa na fap adresu. pokud neni pozadovana fap namapovana ve vap (virtualni adresa neni ve vap), nastava vypadek stranky. je potreba znovu nacist stranku do ramce, zavest mapovani a obnovit kontext. strankovaci tabulky jsou umisteny v hlavni pameti (problém - velke, pomale) => viceurovnove strankovani.
nulaurovnove strankovani: vyuziva pouze TLB (asociativni pamet)
inverzni strankovaci tabulky: FAP mensi nez VAP (64-bit CPU) - pomocí hashování
hashTable: velikost jako fyz.pameti procesu, muze nastat kolize, ta se resi spojakem, kdyz hledam stranku, musim ho projit. byvaji kratke, 1-2 polozky.

strankovani chape adresovy prostor jako jednorozmerny. segmentace zavadi druhy rozmer. segment je nezavisly adresovy prostor sestavajici z adres od 0 do limitu segmentu. segmenty mohou mit ruzne velikosti, ktere se mohou v prubehu casu i menit. segment ma sve umisteni ve fyzicke pameti (neviditelne pro procesy). kazda adresa je pak dvojici (s,d), kde s je cislo segmentu a d je adresa a segmentu. segmenty mohou byt pritomny i nepritomny (vypadek, jako u strankovani). pri alokacio segmentu se pouzivaji algoritmy typu first-fit. pri vypadku nutne vymenit cely segment a ty mohou byt velke, nabizi se tedy moznost kombinace strankovani a segmentace. segmenty lze ve FAP sesypat, nelze mit ale segment vetsi nez FAP.

kombinace segmentace a strankovani: odstranuje nevyhody segmentace, neprovadi se vypadky segmentu
40. otazka:
NRU
odpoved:
NRU ... not recetly used
kazda stranka ma priznaky A (accessed) a D (dirty) - ulozeno v TLB. typicky implementovany HW. lze simulovat softwarove, pokud CPU nepodporuje A,D. jednou za cas se smazou vsechna A, pri zapisu nastaven priznak D. pri vypadku rozdelim stránky podle A, D do tabulky. vyberu stranku z nejnizsi neprazdne tridy:
+---+---+
| A | D |
+===+===+
| 0 | 0 | 0. trida (nebyla dlouho menena, ani ctena - idelani obet)
+---+---+
| 0 | 1 | 1. trida (bylo na ni zapsano, ale uz davno)
+---+---+
| 1 | 0 | 2. trida (nedavno ctena, ale nemusi se zapisovat)
+---+---+
| 1 | 1 | 3. trida (casto pozivana a menena)
+---+---+
41. otazka:
LRU
odpoved:
LRU ... least recently used
nhodi se pro fyzickou pamet, ale treba pro asociativni. nejlepsi je implementovana hw. casto pouzivane stranky budou v nejblizsich okamzicich znovu pouzity. 64-bitovy citac, do ktereho se ulozi cas posledniho pouziti. obeti se stane ten, kdo byl nejdele nepouzit (ma nejstarsi cas, cili nejmensi casove razitko). protoze tohle hledani je velke a pomale, pouziva je jeste jina moznost: matice n x n bitu, pro n ramcu. pri pouziti ramce k nastavim k-ty radek na 1 a k-ty sloupec na 0. obeti se stava ten, kdo ma ve svem radku nejmene 1.
42. otazka:
algoritmy pridelovani pameti
odpoved:
  • First-fit: projde vsechno, najde prvni dostatecne velike misto (rychle, ale obcas zbytecne rozdeli veliky prostor)
  • Next-fit: jako first-fit, ale zacina se na posledni prohledavane pozici (rychlejsi)
  • Best-fit: najde nejmensi mozne misto, kam se to vejde (nedeli velike prostory, ale zase zanechava tak malicke zbytky, ze uz nejsou pouzitelne)
  • Worst-fit: ustipne z nejvetsiho voleneho bloku

deadlock a prostredky

43. otazka:
coffmanovy podminky a zablokovani

odpoved:
zablokovani: mnozina procesu je zablokovana, jestlize kazdy proces z teto mnoziny ceka na udalost, kterou muze zpusobit pouze jiny proces z teto mnoziny.

coffmanovy podminky ... nutne podminky pro vznik zablokovani (aby doslo k zablokovani, musi platit vsechny najednou)
jejich zneni:
1) vzajemne vylouceni (kazdy prostredek je bud vlastnen prave jednim procesem, nebo je volny)
2) drz a cekej (proces nemusi uvolnit prostredky, ktere drzi, kdyz zada o dalsi)
3) neodnimatelnost (nepreemptivnost, proces muze vratit prosredek pouze dobrovolne, nemuse mu byt odebran)
4) cekani do kruhu (existuje kruhovy retez procesu, kde kazdy z nich ceka na prostredek vlastneny dalsim clenem v retezu)
44. otazka:
prostredky
odpoved:
prostredek je cokoliv, co muze byt v jednom casovem okamziku pouzito nejvyse jednim procesem. odnimatelne mohou byt procesu odejmuty bez jakychkoliv nasledku, neodnimatelne nelze odejmout bez vaznych nasledku (vcetne selhani procesu). zablokovani zpusobuji neodnimatelne prostredky. zablokovani na odnimatelnych prostredcich muze byt odstraneno prevedenim pozadovanych prostredku z jednoho procesu na jiny.)
45. otazka:
reseni zablokovani
odpoved:
  • pstrosi algoritmu: vse se necha na uzivateli, nic se neresi. nulova rezie. windows, unix.
  • detekce a zotaveni: detekce - hledani kruznice v grafu, zotaveni - opatrne odebrani prostredku (na prechodnou dobu). rollback. pripadne zabijeni procesu z cyklu
  • vyhybani se: bezpecny stav, nebezpecny stav
  • prevence: poruseni coffmanovych podminek

architektury os

46. otazka:
architektury os
odpoved:
  • monoliticky system: nejstarsi, nejrychlejsi, dodnes pouzivany, UNIX, Windows. tezko se upravuje, obtizna rozsiritelnost za behu.
  • virtualni stroje: puvodne VM pro IBM 360,OS ma dve ulohy - multiprogramming a extended machine. dnes abstraktni stroje, nezalezi na skutecnem HW, pomalejsi
  • mikrojádro: nejnovejsi, experimentalni, co nejmensi, architektura klient/server, kernel zajistuje hlavne komunikaci mezi procesy, vhodny pro distribuovane OS, dnes komercni OS zalozeny na mikrojádore: napr. Chorus na ustrednach a MacOS X

zarizeni

47. otazka:
charakterizace zarizeni
odpoved:
  • druhy: blokove (disk, sitova karta), znakove (klavesnice, mys)
  • pristup: sekvencni (datova paska), nahodny (disk, CD)
  • synchronnost komunikace: synchronni (disk - na zadost), asynchronni (sitovka - poskytuje i nevyzadana data)
  • sdileni: sdilene (sitovka - preemtivni), vyhrazene (tiskarna - nepreemptivni)
  • rychlost: B/s - GB/s
  • smer dat: R/W, R/O, W/O

preruseni

48. otazka:
druhy a obsluha preruseni
odpoved:
druhy:
  • synchronni (zamerne,trap): vyjimky - nespravne chovani procesu
  • asynchronni (vnejsi udalosti)
  • polling: kontrola stavu zarizeni
obsluha:
OS se ujme rizeni
  • ulozi se stav CPU
  • analyza preruseni
  • vyvolani prislusne obsluhy
  • obslouzi se preruseni
  • obnova stavu CPU (muze preplanovat)
  • aplikace pokracuje

vstupni a vystupni systemy

49. otazka:
vrstvy I/O systemu, zpravy
odpoved:
typicky ve 4 vrstvach:
+--------------------------+
| uzivatelsky I/O software |
+--------------------------+
| I/O nezavisly subsystem |
+--------------------------+
| ovladace zarizeni |
+--------------------------+
| obsluha preruseni |
+--------------------------+
| HW |
+--------------------------+
  • Obsluha preruseni:
    1. ulozit stav CPU (kontext vlakna)
    2. potvrdit preruseni radici preruseni
    3. obsluha preruseni ovladacem
    4. preplanovat
    5. nacist stav CPU
  • Ovladac zarizeni:
    • pracuje s porty nebo s pameti
    • "rozumi" konkretnimu zarizeni
    • vytvari alespon trochu jednotne rozhrani pro vyssi vrstvy
    • typicky pouze vyrobce vi, co zariceni dela, proto ovladace poskytuji prevazne vyrobci
  • Jednotne rozhrani na zarizeni:
    1. poskytuje uzivatelskym programum jednotlive rozhrani
    2. skryva rozdily mezi jednotlivymi rozhranimi
    3. provadi pomocne ukoly pro ovladace (alokace pameti, hlaseni chyb, buffering)

planovani

50. otazka:
planovani procesu
odpoved:
entita:proces/vlákno
pridelovani CPU entitam, planovac (scheduler) rozdava procesor
  • preemt.planovani - vetsi OS
  • nepreemptivni planovani (kooperativni multitasking)
    • OS nema prostredky aby odstrihl proces od procesoru
    • aplikace komunikuje s CPU
cile:
  • kazdy proces dostane CPU
  • efektivnost - co nejvic davat CPU aplikacim
  • rychla doba odezvy

kriteria k naplanovani:
  • prace s CPU ? I/O
  • priorita =(static-dulezitost + dynamic-spravedlnost)

  • SMP(symetr.multiprocesor)
  • fronta CPU ceka na procesy(aktivne/pasivne-az je nedo vzbudi)
Real time:
  • planovani NP uplny problem
  • aplikace rizene udalostmi
  • kazdy ukol realny cas k dokonceni
stavy procesu:
+--------+    +---------+
| bezici | -> | ukoncen |
+--------+ +---------+
| ^
| |
| v
| +-----------+
| | pripraven | kdyz bezi moc dlouho a jeste by bezel,
| | | ale byl odstaven
| +-----------+
v
+-----------+
| blokovan | kdyz pozada o sluzbu, ktera bude dlouho trvat,
| | tak se zatim odstavi, nez bude zase pripraven
+-----------+


51. otazka:
planovaci algoritmy
odpoved:
  1. FIFO: nepreemptivni,kdo driv prijde, driv mele (fronta pripravenych procesu)
  2. Round Robin (RR): preemptivni, jako FIFO, ale s casovymi kvanty pro jednotlive procesy. opet bezprioritni
  3. vice front se zpetnou vazbou(FIFO,RR): "pozna", na co je proces vazany (cpu nebo i/o) a podle toho mu prirazuje kvanta a usoudi, jak casto ho k procesoru pusti
52. otazka:
Pametove mapovane soubory
odpoved:
Pojmenovana virtualni pamet. Vyhodou je, ze program pristupuje k souborum instrukcemi pro praci s pameti. Usetri se drahe kopirovani pameti.
Nevyhody:
  1. velikost souboru muze byt vetsi nezli velikost virtualni pameti
  2. zvetsovani souboru pri jejich mapovani do VAP. Reseni tzv. okno kterym se jakoby posouvame po mnohonasobne vetsim souboru. Na AMD64 tento problem odpada, tam je Single Address Space dost velky.