IOS Semestrálka Flashcards
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):
○ Použití více stránek, než je oficiální kapacita
○ 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é
○ Samostatné uvolňování stránek v rámci SSD
Plánování přístupu na disk
● Příchozí I/O požadavky jsou ukládány do vyrovnávací paměti a jejich pořadí je měněno s cílem minimalizovat režie diskových operací
● Výtahový algoritmus: pohybuje hlavičkami od středu k okraji ploten a zpět, požadavky na I/O vyřizuje v pořadí odpovídajícím pohybu hlaviček
Plánování přístupu na disk - heuristiky
○ Circular SCAN ○ LOOK, C-LOOK(NOOP,...) ○ sdružování operací ○ vyvažování operací různých procesů ○ priority operací ○ odkládání operací ○ časové limity operací
CFS (Completely Fair Scheduler)
● explicitně se snaží poskytnout procesům odpovídající % strojového času
● u procesů sleduje spotřebovaný čas (jejich strávený procesorový čas)
● vede si minimální spotřebovaný čas, pro nově připravené procesy
● procesy udržuje ve vyhledávací stromové struktuře, podle jejich spotřebovaného procesorového času
● vybírá proces s nejmenším spotřebovaným časem
● délka přidělovaného kvanta je ovlivněna prioritou
● podporuje skupinové plánování - rozděluje čas spravedlivě pro procesy spuštěné z jiných terminálů
Akce OS při operaci close()
● kontrola platnosti fd
● uvolní položku v tabulce desktriptorů, sníží počítadlo odkazů v tabulce otevřených souborů
● pokud je počitadlo odkazů nulové, uvolní položku, sníží počet odkazů ve v-uzlu
● pokud je počitadlo odkazů nulové, i-uzel se z v-uzlu okopíruje do VP (virtuální paměť) a uvolní
● vrací 0, nebo při chybě -1
Úč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
Akce při výpadku str.
● kontrola, zda se proces neodkazuje mimo přidělený adresový prostor
● alokace rámce: použijeme volný rámec, pokud nějaký je
○ pokud není vybereme vhodnou stránku s přiděleným rámcem (victim page)
○ tu odložíme na swap (je-li to nutné: příznak modifikace v tabulce stránek)
○ použijeme uvolněný rámec
● inicializace stránky po alokaci je závislá na předchozím stavu stránky
➔ první odkaz na stránku:
○ kód a inicializovaná data: načteme z programu
○ vše ostatní: vynulujeme (nelze ponechat původní obsah z bezpečnostních důvodů)
➔ stránka byla v minulosti uvolněna z FAP
○ kód a konstantní data znovu načteme z programu
○ ostatní: pokud byla stránka modifikována je ve swapu a musí se načíst do FAP
● úprava tab. str. (namapování zpřístupňované stránky na přidělený rámec)
● restart instrukce (proces je ve stavu připravený)
LRU, Least Recently Used
● odkládá nejdéle nepoužitou stránku
● velmi dobrá aproximace hypotetického ideálního algoritmu (znal by budoucnost a dle budoucích požadavků by se rozhodoval, co odložit)
● problematická implementace -> vyžaduje výraznou HW podporu (&označování stránek časovým razítkem posledního přístupu či udržování zásobníku stránek)
● používají se aproximace LRU
● Aproximace LRU pomocí omezené historie
○ při každém přístupu HW nastaví referenční bit stránky
○ jádro si vede omezenou historii tohoto bitu pro stránky
○ periodicky posouvá obsah doprava -> na pozici úplně vlevo (na začátek) uloží aktuální hodnotu ref. bitu a vynuluje ho
○ oběť (victim page) je vybrána jako stránka s nejnižší číselnou hodnotou historie
● Aproximace LRU algoritmem druhé šance
○ stránky jsou v kruhovém seznamu
○ postupujeme a nulujeme ref. bit
○ odstraníme první stránku, která již nulový referenční bit má
○ často používaný algoritmus (clock algorithm)
● výhody LRU: často používaný, velmi dobrá aproximace
● nevýhody LRU: problematická implementace (vyžaduje výraznou HW podporu)
FIFO, First In, First Out
● Jednoduchá implementace
● Může odstranit “starou”, ale stále často používanou stránku
● Trpí tzv. Beladyho anomálií
● Odstraňuje stránku, která byla zavedena do paměti před nejdelší dobou a dosud nebyla odstraněna
Plánování
● preemptivní: ke změně běžícího procesu může dojít na základě přerušení (typicky od časovače, ale může se jednat i o jiné přerušení)
● nepreemptivní: ke změně běžícího procesu může dojít pouze tehdy, pokud to běžící proces umožní, předáním řízení jádru (I/O operace, nebo se sám vzdá procesoru - volání yield)
● FCFS - nepreempt. FIFO. Při vzniku procesu, jeho uvolnění z čekání, nebo vzdá-li se proces procesoru, je tento proces zařazen na konec fronty. Procesor se přiděluje prvnímu procesu ve frontě.
● Round-robin - preempt. FIFO. Obdoba FCFS, navíc má ale každý proces přiděleno časové kvantum, po jehož vypršení je mu odebrán procesor a proces je zařazen na konec fronty připravených procesů.
● Víceúrovňové plánování: procesy jsou rozděleny do skupin (typicky dle priority), v každé skupině může být jiný plánovací algoritmus (FCFS..), další plánovací algoritmus se používá pro určení skupiny, ze které se vybere proces, který má běžet (ale typicky na základě priority), může hrozit hladovění.
● Víceúrovňové se zpětnou vazbou: skupiny procesů rozdělené dle priorit, nově vzniklý proces je ve frontě s nejvyšší prioritou, postupně klesá, nakonec je plánován Round-Robin v nejnižší úrovni.
○ modifikace: proces zařazen do fronty na základě statické priority, dynamická priorita se zvyšuje, pokud hodně čeká na I/O, nebo naopak snižuje, pokud spotřebovává hodně času CPU. Cíl: rychlá reakce interaktivních procesů.
Kroky systému při volání open()
● vyhodnocení cesty ● vytvoření v-uzlu ● nová položka v tab. otevření souborů naplněna: ○ odkazem na položku tabulky v-uzlů ○ režimem otevření ○ pozicí v souboru ○ čítačem odkazů na tuto položku ● deskriptor ● návrat indexu
Deadlock - definice
● Uváznutím při přístupu ke zdrojům s omezeným přístupem označujeme situaci, kdy každý proces z určité množiny procesů je pozastaven a čeká na uvolnění zdroje s omezeným přístupem, vlastněného nějakým procesem z dané množiny, který jediný může tento zdroj uvolnit.
● Obecná definice uváznutí: je situace, kdy každý proces z určité množiny procesů je pozastaven a čeká na událost, která by mohla nastat, pouze pokud by byl uvolněn nějaký proces z dané množiny procesů.
Deadlock - Coffmanovy podmínky
● Vzájemné vyloučení při používání prostředků
● Vlastnictví alespoň jednoho zdroje, pozastavení a čekání na další
● Prostředky vrací proces, který je vlastní, a to po dokončení jejich využití
● Cyklická závislost na sebe čekajících procesů
Deadlock - řešení
● Prevence uváznutí
● Vyhýbání se uváznutí
● Detekce a zotavení
● (ověření, že uváznutí nemůže nastat)
Deadlock - prevence
(Zrušíme platnost některé z podmínek nutných pro uváznutí)
● Nepoužívat sdílené prostředky nebo používat sdílené prostředky, které umožňují (skutečně současný) sdílený přístup a u kterých není tedy nutné vzájemné vyloučení procesů.
● Proces může žádat o prostředky pouze, pokud žádné nevlastní
● Pokud proces žádá o prostředky, které nemůže momentálně získat, je pozastaven, všechny prostředky jsou mu odebrány a proces je zrušen, nebo se čeká, až mu mohou být všechny potřebné prostředky přiděleny
● Prostředky jsou číslovány a je možné je získávat pouze od nejnižších čísel k vyšším, nebo jiným způsobem vylučujícím cyklickou závislost na sebe čekající procesů
