IOS

Question 1

Deadlock

Answer 1

rozumíme situaci, kdy
každý proces z určité množiny je pozastaven a čeká na uvolnění zdroje s výlučným (omezeným)
přístupem vlastněného nějakým procesem z dané množiny, který jediný může tento zdroj uvolnit

Question 2

Obecna defenice Deadlocku

Answer 2

Uváznutí jako situaci, kdy každý proces z množiny procesů je pozastaven a čeká na
událost, která by mohla nastat pouze tehdy, pokud by mohl pokračovat nějaký proces z dané
množiny

Question 3

COFFMANOVY PODMÍNKY UVÁZNUTÍ

Answer 3

1. Vzájemné vyloučení při používání prostředků
2. Vlastnění alespoň jednoho zdroje, pozastavení a čekání na další
3. Prostředky vrací proces, který je vlastní a to až po jejich využití
4. Cyklická závislost na sebe čekajích procesů

Question 4

PREVENCE UVÁZNUTÍ

Answer 4

1. Nepoužívat sdílené prostředky, nebo používat takové sdílené prostředky, které umožňují
   skutečně součastný sdílený přístup a u kterých není nutné vzájemné vyloučení procesů
2. Proces může o prostředky žádat pouze v případě, že žádné nevlastní
3. Pokud proces požádá o prostředky, které momentalně nemůže získat, je pozastaven, jsou mu
   odebrány všechny prostředky a proces je zrušen, a nebo čeká do doby než mu mohou být ony
   prostředky přiděleny.
4. Prostředky jsou číslovány a je možné je získat pouze od nejnižších čísel k nejvyšším, nebo v
   jiném pořadí, které vylučuje vznik cyklické závislosti procesů

Question 5

VYHÝBÁNÍ SE UVÁZNUTÍ

Answer 5

Procesy předem deklarují určité informace o tom jakým způsobem budou využívat zdroje, v
nejjednoduším případě se jedná a maximální počet součastně požadovaných zdrojů jednotlivých
typů.
Předem známé informace o možných požadavcích jednotlivých procesů a o aktuálním stavu
přidělování se využijí k rozhodování o tom, které požadavky mohou být uspokojeny, a které si na
své uspokojení musí počkat, cílem je zamezit tomu aby nemohla vzniknout cyklická závislost na
sebe čekajících procesů i v nejhorší možné situaci, která by v budoucnu mohla vniknout při
deklarovaném chování procesů.

Question 6

Výpadky stránek

Answer 6

1. Proběhne kontrola, zda proces neodkazuje mimo přidělený adresový prostor
2. Alokace rámce
   • Pokud je nějaký rámec volný, použije se
   • Vybereme vhodnou stránku s přiděleným rámcem (victim page), stránku odložíme na swap
   • Použijeme vzniklý volný rámec
3. Inicializace stránky po alokaci závislá na předchozím stavu stránky
   • První odkaz na stránku
   • Stránka byla v minulosti uvolněna z FAP
4. Úprava tabulky stránek
   • Namapování zpřístupňěné stránky na přidělený rámec
5. Proces připraven na opakování instrukce která výpadek způsobila ( je ve stavu “připravený”)

Question 7

FIFO algoritm vyberu

Answer 7

Algoritmus FIFO (first in first out) odstraňuje stránku, která byla zavedena do paměti před nejdelší
dobou a doposud nebyla odstraňena.
Lze využít v kombinaci s odložením oběti na nějaká prostor a v případě špatného výběru se oběť
obnoví a vybere se jinak.
Výhody : Jednoduchá implementace
Nevýhody : Může odstranit starou, ale stále používanou stránku

Question 8

LRU

Answer 8

Algoritmus LRU odkládá nejdéle nepoužitou stránku, používá se aproximace LRU
Výhody : Velmi dobrá aproximace hypotetického ideálního algoritmu
Nevýhody : Někdy se uvádí problém s cyklickými průchody rozsáhlími poli, problematická
implementace (vyžadující výraznou HW podporu - označování stránek časovým razítkem
posledního přístupu, či uržování zásobníku stránek, kde je vrcholem naposledy použitá stránka)

Question 9

Aproximace LRU (2 druhy)

Answer 9

Aproximace pomocí omezené historie
• Refefenční bit je nastaven s každým přístupem, jádlo si vezme omezenou historii tohoto bitu pro jednotlivé stránky, periodicky posouvá obsah historie doprava
• Na nejlevější pozici se ukládá aktuální hodnota referenčího bitu a vynuluje ho, oběť je vybrána
jako stránka s nejnižší číselnou hodnotou historie
Aproximace “druhá šance”
• Stránky v kruhovém seznamu, postupuje a nuluje se refenční bit, odstraní se stránka která
referenční bit 0 už má
• Často používaný algoritmus též označovaný jako clock algorithm

Question 10

DEFINICE OPERAČNÍHO SYSTÉMU

Answer 10

kolekce programů která vytváří spojující vrstvu mezi

hardwarem počítače ( ten může být buď fyzický nebo virtualizovaný ) a uživateli a jejich aplikacemi

Question 11

CÍLE OS

Answer 11

1. Maximální využití zdrojů ( zejména dříve kdy byl velmi drahý hardware a levná pracovní síla)
2. Snadnost použití ( zejména dnes, kdy je levný hardware a drahá pracovní síla )

Question 12

ROLE OS

Answer 12

1. Správce protředků ( dovoluje bezpečné a efektivní sdílení prostředků )
2. Tvůrce virtuálního počítače ( Poskytuje standartní rozhraní, poskytuje abstrakce )

Question 13

JÁDRO

Answer 13

• Nejnižší správa prostředku a tvorba prostředí pro zbytek OS a uživatelské aplikace ( nejnižší anejzákladnější část OS )
• Zavádí se jako první a běží po celou dobu běhu hardware
• Navazuje přímo na hardware ( který může být i virtualizovaný )
• Obvykle běží v privilegovaném režimu

Question 14

MIKROJÁDRA

Answer 14

Minimalizují rozsah jádra a nabízí jednoduché rozhraní s jednoduchými abstrakcemi a malým
počtem služeb )
• Většína služeb monolitického jádra implementována formou serverů mimo režim jádra
Výhody :
• Flexibilita ( spouštění, zastavování serverů.. )
• Bezpečnost ( útok na server neovládne celé jádro )
Nevýhody : Vyšší režie ( nižší efektivita )

Question 15

NEPREEMPITVNÍ PLÁNOVÁNÍ

Answer 15

Ke zmeně běžícího procesu může dojít pouze tehdy, pokud to běžící proces umožní předáním
řízení jádru ( žádá o službu typicky I/O operaci, končí nebo se sám vzdává procesoru )

Question 16

PREEMPTIVNÍ PLÁNOVÁNÍ

Answer 16

Ke změně běžícího procesu může dojít i bez nápomoci přepnutí kontextu a to na základě
přerušení ( typicky od časovače, ale může se jednat i o jiné přerušení )

Question 17

FCFS ( First come, first served )

Answer 17

• Procesy čekají ve FIFO frontě
• Nepreemptivní - proces se jádra musí vzdát sám
• Pokud se proces ve svém průběhu vzdá procesoru, předá řízení a jde na konec fronty
( procesor se přiděluje procesu na začátku fronty )

Question 18

Round-robin

Answer 18

• Preemptivní obdoba FCFS
• Pracuje podobně jako FCFS, ale navíc má každý proces přiděleno časové kvantum po jehož
vypršení je mu odebrán procesor a jde na konec fronty

Question 19

SJF ( Shortest job first)

Answer 19

o Přiděluje procesor procesu, který požaduje nejkratší dobu pro své další
provádění na procesoru bez I/O operací
o Nepreemptivní algoritmus
o Minimalizuje průměrnou dobu čekání, zvyšuje propustnost systému
o Nutno znát dopředu dobu běhu procesu na procesoru nebo mít možnost tuto
dobu rozumně odhadnout na základě předchozího chování
o Používá se ve specializovaných systémech
o Hrozí stárnutí (hladovění) procesů mající dlouhé výpočetní fáze

Question 20

Víceúrovňové plánování

Answer 20

• Procesy jsou rozděleny do různých skupin ( typicky podle priorit, typu .. )
• V rámci každé skupiny může být použit jiný plánovací algoritmus
• Hrozí zde hladovění procesů s nízkou prioritou

Question 21

Víceúrovňové plánování se zpětnou vazbou

Answer 21

• Víceúrovňové plánování se skupinami procesů rozdělených dle priorit
• Nový proces je zařazen do fronty s nejvyšší prioritou a postupně klesá, do nižších prioritních
front a nakonec plánován round-robin na nejnížší úrovni
• Modifikace kdy je zařazen na základě statické priority, postupně podle dynamické klesá pokud
bere hodně času nebo stoupá pokud šeká na mnoho I/O operací
• Cílem je zajistim rychlou reakci interaktivních procesů

Question 22

Plánovač v Linuxu verze 2.6

Answer 22

• Priority procesů 1-99 pro procesy reálného času plánované FCFS nebo round-robin
• Priorita 0 pro bežné procesy plánované CFS plánovačem
• V rámci úrovně 0 se dále používají podúrovně v rozmezí -20 (nejvyšší) az 19 (nejnižší) nastavené
uživatelem

Question 23

CFS ( Completely Fair Scheduler)

Answer 23

1) Snaží se explicitně každému procesu poskytnout odpovídající procento strojového času (dle jejich priorit)
2) Vede si u každého procesu údaj o tom, kolik (virtuálního) procesorového času strávil.
3) Navíc si vede údaj o minimálním stráveném procesorovém čase, který dává nově připraveným procesům.
4) Procesy udržuje ve vyhledávací stromové struktuře podlevyu žitého procesorového času.
5) Vybírá jednoduše proces s nejmenším stráveným časem.
6) Procesy nechává běžet po dobu časového kvanta spočteného na základě priorit a pak je zařadí zpět do plánovacího stromu.
7) Obsahuje podporu pro skupinové plánování: Může rozdělovat čas spravedlivě pro procesy spuštěné z různých terminálů

Question 24

PROBLÉM INVERZE PRIORIT

Answer 24

• Nízkoprioritní proces si naalokuje nějaký zdroj, více prioritní procesy ho předbíhají a nemůže dokončit práci s tímto zdrojem
• Časem tento zdroj mohou potřebovat více prioritní procesy, jsou nutně zablokovány a musí čekat na nízko prioritní proces
• Pokud jsou v systému středně prioritní procesy, které nepotřebují daný zdroj budou nadále předbíhat nízkoprioritní proces
• Tímto způsobem uvedené středně a nízkoprioritní procesy získávají efektivně vyšší prioritu

Question 25

ŘEŠENÍ INVERZE PRIORIT A KOMPLIKACE PLÁNOVÁNÍ

Answer 25

1)Priority ceiling : procesy v kritické sekci dostávají nejvyšší prioritu 2)Priority inheritance : proces v kritické sekci, který blokuje výše prioritní proces dostává (dědí) prioritu čekajícího procesu s nejvyšší prioritou 3)Zákaz přerušení po dobu běhu v kritické sekci : proces získá v podstatě vyšší prioritu než všichni ostatní 1) Víceprocesorové systémy : nutnost vyvažovat výko, respektivě obsah casche procesorů 2) Hard real-time-systémy : nutnost zajistit garantovanou odezvu

Question 26

Plánovač diskových operací

Answer 26

Pořádí bloků čtených/zapisovaných na disk má na starosti plánovač diskových operací Přenos z / na disk je řízen řadičem disku příméno přístupu do paměti ( DMA ) O ukončení či chybách operace informuje řadič procesor ( jádro ) pomocí přerušení • Přicházejí požadavky na čtení/zápis a ty jsou ukládány do vyrovnávací paměti a jejich pořadí je případně měněno tak, aby se minimalizovala režie diskových operací • Plánovač také může sdružovat operace, odkádat operace v naději, že bude možné je později propojit, impementovat časové omezení na provedení operací, impelementovat priority operací ..

Question 27

Výtahový algoritmus a dalsi algoritmy

Answer 27

Pohybuje hlavičkami od středu k okraji ploten a zpět a vyřizuje požadavky v pořadí odpovídajících pozici a směru hlaviček 1) Circular SCAN • Vyřizuje požadavky vždy při pohybu jedním směrem - rovnoměrnější doba obsluhy 2) LOOK • Pohybuje se jen v mezích danými aktuálními požadavky - nižší průměrná doba přístupu

Question 28

Žurnálování

Answer 28

Žurnál slouží k ukládání modifikovaných metadat ( data o datech ) před jejich zápisem na disk Cílem žournálování je zajistit atomicitidu diskových operací ( buď operace proběhnou celé nebo vůbec ) Souborové systémy se žournálem : ext3, ext4, ufs, XFS, JFS, NTFS .. Data se obvykle nežurnálují, důvodem je velká režie Žurnál umožňuje rychlejší a spolehlivější náhrat do konzistentního stavu po chybách

Question 29

Implementace na základě dokončení transakcí (REDO):

Answer 29

* Sekvence operací se uloží do žurnálu mezi značky označující začátek a konec transakce. * Poté se dílčí operace provádí na disku. * Uspějí-li všechny dílčí operace, transakce se ze žurnálu uvolní. * Při selhání se dokončí všechny transakce, které jsou v žurnálu.

Question 30

Implementace na základě anulace transakcí (UNDO):

Answer 30

* Záznam dílčích operací do žurnálu a na disk se prokládá. * Proběhne-li celá transakce, ze žurnálu se uvolní. * Při chybě se eliminují nedokončené transakce.

Question 31

Copy-on-write

Answer 31

1) nejprve zapisuje nová data/metadata na disk, pak je zpřístupní: 2) Změny provádí hierarchicky v souladu s hierarchickým popisem obsahu disku (jde o vyhledávací, nikoli adresovací strom). 3)Vytvoří kopii měněného uzlu -> upraví ji -> vytvoří kopii uzlu nadřazeného -> upraví ji tak, aby ukazovala na uzel vytvořený v předchozím kroku. 4) Na nejvyšší úrovni se udržuje několik verzí kořenového záznamu se zabezpečovacím kódem a časovými razítky. 5) Nabízí bázi pro implementaci: snímků souborového systému a klonů SS – vznikají částečně sdílené stromové struktury popisující různé verze obsahu SS

Question 32

ČASOVĚ ZÁVISLÁ CHYBA (RACE CONDITION)

Answer 32

Data race (časově závislá chyba nad daty) – dva přístupy ke zdroji s výlučným přístupem ze dvou procesů bez synchronizace, alespoň jeden přístup je pro zápis

Question 33

Kritická sekce:

Answer 33

• Sdílenými kritickými sekcemi daných procesů rozumíme ty úseky jejichž řídící program přistupuje ke sdíleným zdrojům, jehož provádění jedním procesem vylučuje současné provádění ostatními procesy. • Problém kritické sekce rozumíme problém zajištění korektní synchronizace procesů na množině sdílených kritických sekcí, což zahrnuje: 1) Vzájemné vyloučení – nanejvýš jeden (někdy víc) proces je v daném okamžiku v dané množině sdílených KS. 2) Dostupnost KS: ▪ Je-li KS volná, proces nemůže neomezeně čekat na přístup do ní. ▪ Je zapotřebí se vyhnout: • Uváznutí • Blokování • Stárnutí

Question 34

Problémy vznikající v kritické sekci:

Answer 34

* Data race (časově závislá chyba nad daty) – dva přístupy ke zdroji s výlučným přístupem ze dvou procesů bez synchronizace, alespoň jeden přístup je pro zápis * Blokování (blocking) při přístupu do KS – situace, kdy proces, jenž žádá o vstup do kritické sekce, musí čekat, přestože je kritická sekce volná a ani žádný další proces o ni nežádá. * Stárnutí (aneb hladovění) – situace, kdy proces čeká na podmínku, která nemusí nastat. V případě kritické sekce je umožnění vstupu do ní.

Question 35

Alokační blok, Diskový sektor, Extent

Answer 35

Diskový sektor: nejmenší jednotka, kterou disk umožňuje načíst/zapsat Alokační blok: skupina pevného počtu sektorů, typicky 2^N pro nějaké N, následujících logicky (tj. v souboru) i fyzicky (tj. na disku) za sebou, která je nejmenší jednotkou diskového prostoru se kterou umí OS (FS) pracovat. (nejmenší jednotka, kterou umožňuje OS načíst/zapsat) ● Extent - posloupnosti proměnného počtu bloků jdoucích za sebou logicky v souboru a uložených fyzicky za sebou na disku. Zrychlují práci s velkými soubory(menší indexovací struktury, menší objem metadat), naopak pro malé soubory to může znamenat zbytečně velkou režii

Question 36

Překlad logické adresy na fyzickou přes 2-úrovňovou tabulku stránek

Answer 36

● LA se rozloží na prefix p sestávající z odkazu p1 do adresáře stránek a z odkazu p2 do konkrétní tabulky stránek. Tedy p=p1.p2 ● Test zda TLB obsahuje dvojici (p,f), vyhledává se asociativně dle p (je možné částečně asociativní vyhledání), je-li položka (p,f) nalezena, je výsledná adresa (f,d). ● Přístup k položce na indexu p1 v adresáři stránek, který je v RAM na adrese uložené ve speciálním registru MMU (u intelu CR3) ● Má-li výše uvedená položka nastaven příznak neplatnosti, nastává výpadek v adresáři stránek ● Není-li tomu tak, pak se z uvedené položky získá bázová adresa dílčí tabulky stránek rovněž uložené v RAM. Použije se položka s indexem p2 této tabulky. ● Obsahuje-li položka na indexu p2 v dílčí tabulce stránek příznak neplatnosti, nastává výpadek stránky. Jinak se z položky zmíněné výše získá číslo rámce f a výsledná adresa je (f,d)

Question 37

NTFS, odlišnosti různě dlouhých souborů, 3 varianty reprezentace a adresovaní.

Answer 37

● MFT (Master File Table) ○ alespoň jeden řádek pro každý soubor ○ malé soubory jsou celé uložené v MFT (i s obsahem) ○ střední – na řádku příslušeného souboru uložené odkazy na extenty ○ velké – přes 2 řádky jsou odkazy na pomocné odkazy, ve kterých jsou uložené odkazy na extenty (adresování podobné jako u B+ stromů) ● Extent ○ posloupnoust proměnného počtu alokačních bloků logicky jdoucích za sebou v souboru a uložených fyzicky na disku ● podpora žurnálování (REDO+UNDO)

Question 38

Účel a princip dvou-úrovňové obsluhy přerušení

Answer 38

● minimalizace délky zákazu přerušení ● 1. úroveň: ○ zajišťuje minimální obsluhu HW, plánování běhu 2 úrovně ○ může být vyloučeno/zamaskováno přerušení ● 2. úroveň: ○ postupně dokončuje obsluhu zaznamenaných přerušení ○ nemusí zakazovat přerušení - vzájemné vyloučení se dá řešit běžnými synchronizačními prostředky

Question 39

Problematika přepisu dat u SSD

Answer 39

● Nutnost načíst blok do vyrovnávací paměti, změnit, na disku vymazat, zapsat zpět a to celý, byť se mění jen 1 stránka ● Řešení (lépe řečeno minimalizace problému): 1) Použití více stránek, než je oficiální kapacita 2) Příkaz TRIM - umožňuje souborovému systému sdělit SSD, které stránky nejsou používány a lze je opět považovat za prázdné 3) Samostatné uvolňování stránek v rámci SSD