IOS Flashcards
Deadlock
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
Obecna defenice Deadlocku
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
COFFMANOVY PODMÍNKY UVÁZNUTÍ
- Vzájemné vyloučení při používání prostředků
- Vlastnění alespoň jednoho zdroje, pozastavení a čekání na další
- Prostředky vrací proces, který je vlastní a to až po jejich využití
- Cyklická závislost na sebe čekajích procesů
PREVENCE UVÁZNUTÍ
- 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ů - Proces může o prostředky žádat pouze v případě, že žádné nevlastní
- 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. - 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ů
VYHÝBÁNÍ SE UVÁZNUTÍ
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ů.
Výpadky stránek
- Proběhne kontrola, zda proces neodkazuje mimo přidělený adresový prostor
- 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 - 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 - Úprava tabulky stránek
• Namapování zpřístupňěné stránky na přidělený rámec - Proces připraven na opakování instrukce která výpadek způsobila ( je ve stavu “připravený”)
FIFO algoritm vyberu
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
LRU
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)
Aproximace LRU (2 druhy)
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
DEFINICE OPERAČNÍHO SYSTÉMU
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
CÍLE OS
- Maximální využití zdrojů ( zejména dříve kdy byl velmi drahý hardware a levná pracovní síla)
- Snadnost použití ( zejména dnes, kdy je levný hardware a drahá pracovní síla )
ROLE OS
- Správce protředků ( dovoluje bezpečné a efektivní sdílení prostředků )
- Tvůrce virtuálního počítače ( Poskytuje standartní rozhraní, poskytuje abstrakce )
JÁDRO
- 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
MIKROJÁDRA
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 )
NEPREEMPITVNÍ PLÁNOVÁNÍ
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 )
PREEMPTIVNÍ PLÁNOVÁNÍ
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í )
FCFS ( First come, first served )
• 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 )
Round-robin
• 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
SJF ( Shortest job first)
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
Víceúrovňové plánování
- 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
Víceúrovňové plánování se zpětnou vazbou
• 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ů
Plánovač v Linuxu verze 2.6
• 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
CFS ( Completely Fair Scheduler)
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ů
PROBLÉM INVERZE PRIORIT
- 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
ŘEŠENÍ INVERZE PRIORIT A KOMPLIKACE PLÁNOVÁNÍ
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
Plánovač diskových operací
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í ..
Výtahový algoritmus a dalsi algoritmy
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
Žurnálování
Ž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
Implementace na základě dokončení transakcí (REDO):
- 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.
Implementace na základě anulace transakcí (UNDO):
- 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.
Copy-on-write
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
ČASOVĚ ZÁVISLÁ CHYBA (RACE CONDITION)
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
Kritická sekce:
• 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í
Problémy vznikající v kritické sekci:
- 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í.
Alokační blok, Diskový sektor, Extent
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
Překlad logické adresy na fyzickou přes 2-úrovňovou tabulku stránek
● 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)
NTFS, odlišnosti různě dlouhých souborů, 3 varianty reprezentace a
adresovaní.
● 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)
Účel a princip dvou-úrovňové obsluhy přerušení
● 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
Problematika přepisu dat u SSD
● 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
