3 - 1. opravný.md

1. opravný 2016

Skupina C

Odpovězte stručně

1. (6b) Charakterizujte základní myšlenku a princip činnosti plánovače CFS (Complely Fair Scheduler) implementovaného v Linuxu 2.6. (limit: cca 6 rozvitých vět)
2. (7b) Jaký je maximální počet výpadků stránek v systému se stránkami o velikosti L KiB (L >= 2). N-úrovňovou tabulkou stránek (N >= 2), u které pouze dílčí tabulka nejvyšší úrovně je chráněná proti výpadku, při provádění předem nenačtené instrukce o délce 64 bitů, která posouvá v paměti RAM o jednu stránku blok o velikosti M bajtů. Uvedený posun lze chápat jako čtení a následný zápis na adresu vyšší o jednu stránku (neboli o právě L KiB). Předpokládejte M >= 2, ale M je současně menší než polovina počtu položek v každé z dílčích tabulek stránek. Odvozený vztah zdůvodněte. (limity: 1 vztah a cca 7 rozvitých vět [vztah bez zdůvodnení: 8b])
3. (10b) Definujte pojmy: a) diskový sektor, b) alokační blok, c) extent. U extentu zmiňte (stručně), co je hlavním přínosem jeho použití. Předpokládejte velikost diskového bloku 4 KiB a uveďte, kolik bloků zabere na čerstvě naformátovaném disku se souborovým systémem EXT4 soubor o veliosti 4 096 001 B. Uvedený údaj zdůvodněte! (limity: cca 5 rozvitých vět + 1 číslo [bez zdůvodnění za 0b])
4. (12b) Pomocí semaforů implementujte jednoduchý synchronizační mechanismus typu bariéra s následujícím chováním. Procesy budou vstupovat do bariéry voláním void barrier (struct sBarrier *b). Vstupující procesy budou v tomto volání pasivně čekat, dokud do bariéry nevstoupí N procesů (N ≥ 2 je konstanta). Proces, po jehož vstupu dosáhne počet procesů v bariéře hodnotu N, uvolní postupně procesy, které do bariéry vstoupily před ním. Poté, jakmile si může být jist, že všechny uvolněné procesy mohou již bez další synchronizace dokončit provádění funkce barrier (tedy jsou před návratem z této funkce nebo již její provádění ukončily), uvolní bariéru pro další synchronizační cyklus. Položky struktury sBarrier doplňte dle vlastního uvážení. (limity: cca 12 řádků kódu + příslušná struktura)
5. (10b) Uvažujte práci s prostou hashovací tabulkou stránek (tedy nikoliv kombinaci hashovaní tabulky s tabulkou invertovanou) sdílenou všemi běžícími procesy a to s využitím regionů procesů (lokálních regionů) mapovaných do systémových (globálních) regionů. Předpokládejte, že pro práci s touto tabulkou je definován typ tPgN reprezentující čísla stránek a rámců, typ tPID reprezentující čísla procesů a typ tReg reprezentující číslo lokálních a globálních regionů. Dále předpokládejte, že je definována funkce tReg loc_to_glob_reg (tPID pid, tReg loc_reg), která pro proces s daným pid převede lokální číslo regionu na globální. Konečně předpokládejte, že je definována vhodná funkce int hashPg (...), která vrací odkaz do tabulky hashTb, deklarované jako HashTbRec *hashTb[SIZE]. Typ tHashTbRec je deklarován pomocí typedef struct sHashTbRec {...} tHashTbRec.
   • Doplňte vhodně parametry funkce int hashPg (...)
   • Doplňte patřičné členy struktury sHashTbRec
   • Implementujte v jazyce C funkci tPgN pg2fr (tPID pid, tReg reg, tPgN pg), která převede zadané číslo stránky na odpovídající číslo rámce, případně vrátí PAGE_FAULT, není-li možné převod provést. (limity: cca parametry int hashPg (...), členy struktury sHashTbRec a cca 7 řádků kódu)

Rozveďte

1. (15b) Definujte pojem uváznutí (deadlock) při práci se sdílenými zdroji a uveďte 4 nutné (tzv. Coffmanovy podmínky) jeho vzniku. Uveďte základní princip prevence uváznutí a popište co nejdetailněji různé přístupy, které se k tomuto účelu používají. Uveďte základní princip vyhýbání se uváznutí a zvláštní pozornost pak věnujte pečlivému popisu grafu alokace zdrojů a jeho použití pro vyhýbání se uváznutí. Jaký další klasický mechanismus řešení problému uváznutí se používá (neuvažujeme-li využití verifikace k ověření, že uváznutí nemůže nastat)M Stručně charakterizujte.