Teoretické otázky (pravda / nepravda)¶

Teoretická část zkoušky BI-OSY je test tvrzení, u kterých student rozhoduje PRAVDA / NEPRAVDA, případně krátké teoretické otázky s výběrem jedné správné možnosti. Na ProgTestu se generuje náhodný výběr otázek z poolu, takže se vyplatí projít všechny typy.

Jak stránku používat

Přečti si tvrzení / otázku.
Sám se rozhodni, zda je PRAVDA nebo NEPRAVDA (případně urči správnou možnost).
Rozbal blok Odpověď a porovnej se zdůvodněním.

Tvrzení jsou seskupena podle kapitol skript a deduplikována — ekvivalentní tvrzení z různých termínů jsou uvedena jen jednou.

Obsah stránky

Operační systémy obecně
Procesy a vlákna
Synchronizace
Uváznutí (deadlock)
Plánování procesů
Správa paměti
Datová úložiště a souborové systémy

Operační systémy obecně¶

Tvrzení o jádru, systémových voláních, režimech CPU a architektuře počítače.

Standardní knihovna C je součástí operačního systému.

Odpověď

NEPRAVDA — standardní knihovna C není součástí OS; přes ABI (Application Binary Interface) pouze zprostředkuje aplikaci přístup ke službám jádra (systémovým voláním).
Procesor po resetu začíná vykonávat instrukce v user módu a do kernel módu se musí později sám přepnout.

Odpověď

NEPRAVDA — po resetu procesor startuje v privilegovaném (kernel/supervisor) režimu, aby mohl provést inicializaci systému.
Procesor může odmítnout požadavek na přístup k I/O zařízení, pokud není v privilegovaném režimu — v tom případě vyvolá výjimku.

Odpověď

PRAVDA — privilegované instrukce (přístup k I/O, správa přerušení apod.) lze provést jen v kernel módu; pokus v user módu vede k výjimce.
Přetečení časovače je jedním ze zdrojů vnějšího přerušení.

Odpověď

PRAVDA — časovač je hardwarové zařízení mimo CPU a jeho přetečení generuje vnější (hardwarové) přerušení, na kterém stojí mj. plánování procesů.
Vyberte správné tvrzení: V jakém režimu běží jádro (kernel) operačního systému?

Odpověď

Správně: „Kernel běží typicky v režimu supervisor.“ — Nepravdivé jsou varianty tvrdící, že kernel běží v user módu, že moduly/ovladače běží jen v user módu nebo že ve virtuálním stroji běží jen v user módu.
Vyberte správné tvrzení: V jakém režimu běží uživatelský proces?

Odpověď

Správně: „Uživatelský proces běží typicky v režimu user.“ — Nepravdivé jsou varianty „pokud běží jako root, běží v supervisor“ nebo „v supervisor“; spuštění jako root nemění režim CPU, mění jen oprávnění v rámci OS.
Které z následujících instrukcí jsou na procesoru x86 dostupné v režimu user: LIDT, CLI, OUT dx, eax, MOV ax, bx, SHL eax, 3?

Odpověď

Dostupné v user módu: MOV ax, bx a SHL eax, 3 (běžné výpočetní instrukce). Privilegované (jen kernel mód): LIDT (načtení tabulky přerušení), CLI (zákaz přerušení), OUT (zápis na periferii).
Moderní víceprocesorový počítač (např. notebook s vícejádrovým CPU) je architektury MIMD.

Odpověď

PRAVDA — víceprocesorové/vícejádrové počítače vykonávají více instrukčních proudů nad více datovými proudy, tedy MIMD.
Operační systém Windows na běžném vícejádrovém počítači podporuje SMP (symetrický multiprocesoring).

Odpověď

PRAVDA — moderní OS podporují SMP, kde jsou si všechna jádra/procesory rovnocenná.
Plánování procesů a přepínání kontextu řídí část jádra, která reaguje na přerušení časovače nebo na události (I/O, sleep()) a rozhoduje, který proces poběží dál.

Odpověď

PRAVDA — to je přesně role plánovače (scheduler) jako součásti jádra.

Skripta → Úvod

Procesy a vlákna¶

Tvrzení o procesech, vláknech, systémových voláních fork/exec/wait a sdílených prostředcích.

Vlákna v rámci jednoho procesu sdílejí globální proměnné a otevřené soubory.

Odpověď

PRAVDA — vlákna jednoho procesu sdílejí adresní prostor (data, halda, kód) i tabulku otevřených souborů; vlastní mají jen zásobník a registry.
Volání execve() přepne běžící vlákno do jiného již existujícího procesu.

Odpověď

NEPRAVDA — execve() nahradí obraz aktuálního procesu novým programem; nevytváří nový proces ani se nepřepíná do jiného existujícího procesu.
Když potomek skončí dříve než rodič a rodič se ukončí bez volání wait(), zůstane potomek trvale zombie a nepůjde odstranit.

Odpověď

NEPRAVDA — osiřelý proces (i zombie) převezme proces init (PID 1), který za něj zavolá wait() a uklidí ho.
Thread Control Block (TCB) obsahuje identifikaci vlákna (TID), informace pro přepínání kontextu (obsah registrů, ukazatel zásobníku) a informace pro plánování (priorita, plánovací algoritmus).

Odpověď

PRAVDA — to je přesně obsah TCB.
Vícevláknový proces s N vlákny sdílí jednu stránkovací tabulku, a tedy i stejný virtuální adresní prostor.

Odpověď

PRAVDA — všechna vlákna procesu sdílejí stejný virtuální adresní prostor a tím i stránkovací tabulku.
V C se po fork() rodiči vrátí PID potomka (kladné číslo) a potomkovi 0.

Odpověď

PRAVDA — fork() vrací 0 v potomkovi, kladný PID potomka v rodiči a -1 při chybě.
Po neúspěšném fork() (např. při dosažení limitu počtu procesů) vrátí volání hodnotu -1.

Odpověď

PRAVDA — po vyčerpání limitu procesů/vláken fork() selže a vrací -1; nový proces nevznikne.
Staticky alokované pole (např. char a[N]) se umisťuje na zásobník, dynamicky alokovaná paměť přes malloc() na haldu.

Odpověď

PRAVDA — lokální pole jde na zásobník (stack), malloc() alokuje na haldě (heap).
Potomek vytvořený fork() dostává kopii adresního prostoru rodiče, takže globální proměnná má v rodiči i potomkovi stejnou adresu, ale zápis do ní v jednom procesu se neprojeví v druhém.

Odpověď

PRAVDA — po fork() má potomek vlastní (zkopírovaný) adresní prostor; virtuální adresa proměnné je stejná, ale fyzicky jde o oddělené paměti, takže změny nejsou viditelné v druhém procesu.

Skripta → Procesy a vlákna

Synchronizace¶

Tvrzení o zámcích, semaforech, kritické sekci, aktivním čekání a časově závislých chybách.

Kritická sekce je jakákoliv část kódu mezi uzamčením a odemčením zámku (např. mezi pthread_mutex_lock() a pthread_mutex_unlock()).

Odpověď

PRAVDA — kritická sekce je úsek kódu chráněný zámkem, ve kterém smí být současně nejvýše jedno vlákno.
Jeden mutex chrání jeden nebo skupinu sdílených prostředků, ale nelze používat více různých mutexů k ochraně téhož sdíleného prostředku (bez vnořeného zamykání).

Odpověď

PRAVDA — pokud by tentýž prostředek chránily různé mutexy nezávisle, ztratí se vzájemné vyloučení; vzájemné vyloučení garantuje jen jeden společný mutex.
Program, který ze dvou a více vláken současně zapisuje do sdílené proměnné bez dostatečné synchronizace, obsahuje časově závislou chybu (data race).

Odpověď

PRAVDA — současný zápis více vláken bez ochrany kritické sekce je klasická časově závislá chyba.
Pokud je semafor inicializován hodnotou ≥ 2, může do kritické sekce chráněné jen tímto semaforem vstoupit současně více vláken, což u operace typu „přičti ke sdílené proměnné“ způsobuje časově závislou chybu.

Odpověď

PRAVDA — semafor s počáteční hodnotou 2 pustí dovnitř dvě vlákna zároveň; pro vzájemné vyloučení by musel být inicializován na 1 (binární semafor / mutex). Proto úlohy se sem_init(&sem, 0, 2) obsahují data race.
Semafor lze implementovat pomocí mutexu a podmíněné proměnné.

Odpověď

PRAVDA — semafor se dá sestavit z čítače chráněného mutexem a podmíněné proměnné, na které vlákna čekají, je-li čítač nulový.
Při buzení čekajícího vlákna je u implementace semaforu vhodnější pthread_cond_signal() než pthread_cond_broadcast().

Odpověď

PRAVDA — stačí probudit jedno vlákno; broadcast probudí zbytečně všechna vlákna (i když principiálně korektní, je to neefektivní).
Vzájemné vyloučení lze řešit aktivním čekáním pomocí atomické instrukce TSL nebo XCHG.

Odpověď

PRAVDA — TSL/XCHG atomicky přečte a nastaví zámek; vstup do kritické sekce se realizuje smyčkou testující zámek (busy waiting).
Při optimálním a korektním řešení problému spících holičů (N holičů, M zákazníků) stačí 3 semafory: mutex pro sdílené proměnné, jeden pro uspání holičů a jeden pro uspání zákazníků.

Odpověď

PRAVDA — klasické řešení používá tři semafory: binární mutex a dva synchronizační semafory.
Pro problém inverze priorit: nastane, když proces s nízkou prioritou drží zámek potřebný procesu s vysokou prioritou a je přitom předbíhán procesy se střední prioritou.

Odpověď

PRAVDA — inverze priorit nastává u pevných (statických) priorit, kdy proces s vysokou prioritou nepřímo čeká na proces s nízkou prioritou.

Skripta → Synchronizace

Uváznutí (deadlock)¶

Tvrzení o uváznutí, Coffmanových podmínkách, bankéřově algoritmu, prevenci uváznutí a livelocku.

Pokud bankéřův algoritmus neoznačí aktuální stav za bezpečný, znamená to, že systém je právě v uváznutí.

Odpověď

NEPRAVDA — nebezpečný stav znamená jen, že může dojít k uváznutí; systém v uváznutí ještě nemusí být.
Neodnímatelné prostředky lze procesu odebrat bez rizika narušení konzistence jeho výpočtu.

Odpověď

NEPRAVDA — neodnímatelný prostředek z definice nelze bezpečně odebrat; jeho odejmutí by narušilo probíhající operaci. (Neodnímatelnost je jedna z Coffmanových podmínek.)
Prevence uváznutí číslováním prostředků: prostředky se alokují jen v předem stanoveném pořadí, čímž se eliminuje kruhové čekání.

Odpověď

PRAVDA — pevné pořadí alokace znemožní vznik cyklu v grafu čekání, a tím i kruhové čekání.
Systém je v bezpečném stavu, pokud existuje pořadí, ve kterém lze postupně uspokojit všechny procesy/vlákna.

Odpověď

PRAVDA — bezpečný stav je definován existencí bezpečné posloupnosti uspokojení všech procesů.
Jsou-li splněny všechny čtyři Coffmanovy podmínky, je systém vždy v uváznutí.

Odpověď

NEPRAVDA — splnění všech čtyř Coffmanových podmínek je nutné, ne postačující; systém může být i bezpečný (zkouškové úlohy explicitně uvádějí variantu „bezpečný stav, přestože všechny Coffmanovy podmínky jsou splněné“).
Pokud graf alokačních závislostí neobsahuje cyklus, systém není v uváznutí (je v bezpečném stavu).

Odpověď

PRAVDA — pro prostředky s jednou instancí platí, že absence cyklu znamená absenci uváznutí. (U více instancí na typ je třeba ověřit bankéřovým algoritmem.)
Vyhladovění (livelock/starvation) je totéž jako deadlock.

Odpověď

NEPRAVDA — při deadlocku jsou vlákna trvale zablokována a nic nedělají; při livelocku vlákna stále něco vykonávají (reagují na sebe), ale nepostupují kupředu.

Ověřit

Konkrétní úlohy s kódem typu lock_guard nad polem mutexů (g_M[pos % 4], g_M[(pos+1) % 4], …) mají odpovědi (deadlock / livelock / busy waiting / možné hodnoty proměnné) závislé na konkrétních hodnotách pos a pořadí zamykání. Vyhodnocuj je vždy individuálně podle zadaného příkladu — obecně platí jen, že zamykání více mutexů v různém pořadí může vést k deadlocku, a že lock_guard nad jediným hromadným lock(...) (atomické uzamčení více zámků) deadlocku zabrání, ale může vést k livelocku.

Skripta → Uváznutí (deadlock)

Plánování procesů¶

Tvrzení o plánovači, prioritách, časovém kvantu a přepínání kontextu.

Při plánování s dynamickou prioritou se obvykle sníží priorita i časové kvantum procesu, který v posledním běhu vyčerpal celé své časové kvantum.

Odpověď

PRAVDA — proces, který spotřebuje celé kvantum (CPU-bound), je typicky penalizován snížením priority; I/O-bound proces, který kvantum nevyčerpá, je naopak zvýhodněn.
Přepnutí kontextu mezi vlákny je v Linuxu implementováno výhradně pomocí systémového volání sched_yield().

Odpověď

NEPRAVDA — přepnutí kontextu nastává hlavně při přerušení časovače, při blokujících operacích (I/O, sleep()) apod.; sched_yield() je jen jeden z mnoha možných spouštěčů, nikoli jediný.
Při statické (pevné) prioritě se proces s nízkou prioritou nemusí vůbec dostat na CPU, pokud jsou stále připraveny procesy s vyšší prioritou.

Odpověď

PRAVDA — pevné priority mohou vést k vyhladovění nízkoprioritních procesů.
Pokud běh vícevláknového procesu probíhá většinu času ve stavu BLOCKED, zrychlení procesoru ani přidání jader dobu jeho běhu výrazně nezkrátí.

Odpověď

PRAVDA — doba běhu I/O-bound procesu (vlákna převážně BLOCKED) je dána čekáním, ne výpočetním výkonem, takže rychlejší/další jádra nepomohou.
Pokud jsou vlákna procesu většinu času ve stavu READY/RUNNING (CPU-bound) a běží na omezeném počtu jader, je celkový výpočetní výkon konstantní — proto lze dobu běhu přepočítat trojčlenkou podle počtu dostupných vláken procesoru.

Odpověď

PRAVDA — celkový potřebný výpočet (vlákna × čas) je konstanta; doba běhu se mění nepřímo úměrně počtu dostupných hardwarových vláken.

Skripta → Plánování procesů

Správa paměti¶

Tvrzení o virtuální paměti, stránkování, TLB, tabulkách stránek, algoritmech náhrady stránek a alokátorech.

Bit „present“ v záznamu stránkové tabulky indikuje, zda je stránka aktuálně namapována do fyzické paměti.

Odpověď

PRAVDA — present bit říká, zda je stránka přítomna ve fyzické paměti; je-li 0, přístup vyvolá výpadek stránky (page fault).
Když dojde k výpadku stránky (page fault), systém ukončí běžící proces, protože nelze pokračovat.

Odpověď

NEPRAVDA — page fault běžně obslouží jádro: chybějící stránku nahraje do fyzické paměti (případně vyhodí jinou) a běh procesu pokračuje.
Algoritmus LRU (Least Recently Used) pro náhradu stránek nelze implementovat.

Odpověď

NEPRAVDA — LRU implementovat lze (např. čítače, seznam); jen je nákladný, proto se v praxi používají aproximace (NRU, Clock, Aging, Second chance).
Algoritmus pro náhradu stránek se spouští vždy, když MMU vygeneruje výjimku/trap.

Odpověď

NEPRAVDA — algoritmus náhrady se spustí jen při výpadku stránky, kdy je potřeba uvolnit rámec a žádný volný není; ne každá výjimka MMU je page fault a ne každý page fault vyžaduje náhradu.
Virtuální adresní prostor uživatelského procesu je typicky rozdělen (od nejnižších adres k vyšším) v pořadí: Text, Data, Heap, …, Stack.

Odpověď

PRAVDA — typické rozvržení je Text (kód), Data, Heap rostoucí nahoru a Stack na vysokých adresách rostoucí dolů.
Funkce free() vždy okamžitě vrací uvolněnou paměť jádru pomocí munmap() nebo brk().

Odpověď

NEPRAVDA — free() zpravidla vrátí blok jen do uživatelského alokátoru (arény) pro budoucí použití; jádru se paměť vrací jen někdy a ne okamžitě.
Funkce free() v glibc může sloučit sousední volné bloky, ale jen v rámci stejné arény.

Odpověď

PRAVDA — slučování (coalescing) sousedních volných bloků probíhá v rámci jedné arény, kde jsou bloky správcovány společně.
Cache hit ratio TLB se může zvýšit, pokud systém použije pro proces větší stránky.

Odpověď

PRAVDA — větší stránky pokryjí stejným počtem položek TLB větší adresní prostor, čímž roste úspěšnost vyhledání v TLB.
Cache hit ratio TLB se může zvýšit, pokud systém použije pro proces menší stránky.

Odpověď

NEPRAVDA — menší stránky pokryjí méně paměti, hit ratio TLB naopak klesá.
Současné serverové a desktopové procesory umožňují používat různě velké stránky pro různé procesy.

Odpověď

PRAVDA — moderní procesory podporují více velikostí stránek (huge pages apod.).
Současné procesory umožňují aplikacím za běhu měnit velikost TLB podle potřeby.

Odpověď

NEPRAVDA — velikost TLB je pevně daná hardwarem; aplikace ji měnit nemůže.
Offset adresy definuje pozici dat uvnitř rámce (resp. stránky).

Odpověď

PRAVDA — offset určuje pozici uvnitř rámce/stránky; pro různě velké stránky má offset různý počet bitů.
Logická (virtuální) adresa se skládá z čísla stránky a offsetu; fyzická adresa z čísla rámce a offsetu.

Odpověď

PRAVDA — virtuální adresa = číslo stránky + offset, fyzická adresa = číslo rámce + offset. Velikost offsetu je u obou dána velikostí stránky/rámce.
U klasické (přímé) tabulky stránek si jádro musí pamatovat pro každý proces právě jednu tabulku stránek.

Odpověď

PRAVDA — klasická tabulka stránek je per-proces; při N procesech tedy existuje aspoň N tabulek.
U invertované tabulky stránek si jádro musí pamatovat jen jednu (společnou) tabulku stránek.

Odpověď

PRAVDA — invertovaná tabulka je jedna pro celý systém; má jeden řádek na každý fyzický rámec.
Na řádce klasické tabulky stránek je uloženo číslo rámce a bity present, modify a reference.

Odpověď

PRAVDA — řádek klasické tabulky obsahuje číslo rámce + řídicí bity (present, modify/dirty, reference). Číslo stránky se v ní neukládá (slouží jako index).
Na řádce invertované tabulky stránek je uloženo číslo stránky a číslo procesu.

Odpověď

PRAVDA — invertovaná tabulka indexovaná číslem rámce ukládá na řádku číslo stránky a číslo procesu (plus present/modify/reference). Offset se v tabulkách nikdy neukládá.
Na řádce TLB je uloženo číslo stránky, číslo rámce a bity reference/modify.

Odpověď

PRAVDA — TLB je cache mapování stránka → rámec; na řádce je číslo stránky, číslo rámce a řídicí bity. Offset v TLB není.
Při překladu adresy přes invertovanou tabulku stránek lze použít rozptylovací (hash) funkci k urychlení vyhledávání.

Odpověď

PRAVDA — invertovaná tabulka se prohledává podle (proces, stránka); aby se nemusela procházet lineárně, používá se hašování. U klasické tabulky se hash nepoužívá (přímá indexace).
Při překladu adresy se číslo rámce používá jako index do TLB.

Odpověď

NEPRAVDA — TLB se prohledává podle čísla stránky, ne rámce; výsledkem je číslo rámce.
Počet řádků klasické tabulky stránek je dán počtem stránek (2 na velikost čísla stránky); počet řádků invertované tabulky je dán počtem rámců (2 na velikost čísla rámce).

Odpověď

PRAVDA — klasická tabulka má řádek na každou virtuální stránku, invertovaná na každý fyzický rámec.

Skripta → Správa paměti

Datová úložiště a souborové systémy¶

Tvrzení o discích, RAID, NAS, inodech, souborových systémech a typech odkazů.

SSD disky nemají pohyblivé mechanické části, zatímco HDD obsahují otáčející se plotny a pohyblivou čtecí hlavu.

Odpověď

PRAVDA — to je základní konstrukční rozdíl mezi SSD a HDD.
RAID 2, 3 a 4 se v běžných datových úložištích prakticky nepoužívají.

Odpověď

PRAVDA — v praxi převažují RAID 0, 1, 5, 6, 10; úrovně 2, 3 a 4 jsou dnes spíše historické.
Pro NAS (Network-Attached Storage) platí, že data jsou přístupná na úrovni (distribuovaného) souborového systému přes síťové protokoly.

Odpověď

PRAVDA — NAS poskytuje přístup na úrovni souborů přes protokoly jako NFS či SMB (na rozdíl od SAN, které pracuje na úrovni bloků).
RAID 10 se čtyřmi identickými disky nenabízí oproti RAID 5 (rovněž 4 disky) žádné výhody, protože hůře využívá kapacitu a rychlost čtení i zápisu je v obou případech stejná.

Odpověď

NEPRAVDA — RAID 10 sice využívá kapacitu hůře (poloviční), ale má jiný (zpravidla lepší) výkon zápisu a odlišnou odolnost proti výpadkům; rychlosti tedy nejsou v obou případech stejné.
Každý soubor je v unixovém OS jednoznačně identifikován číslem inode v rámci daného souborového systému.

Odpověď

PRAVDA — inode číslo je jednoznačné v rámci jednoho souborového systému (proto hard link nemůže přesáhnout hranici FS).
Obsah adresáře je podobně jako obsah souboru uložen v jednom nebo více datových blocích.

Odpověď

PRAVDA — adresář je speciální soubor, jehož „obsahem“ jsou položky (jméno → inode) uložené v datových blocích.
Symbolický link (soft link) může odkazovat napříč různými souborovými systémy, zatímco hard link jen v rámci téhož souborového systému.

Odpověď

PRAVDA — soft link uchovává cestu (řetězec) a může mířit kamkoliv; hard link je další jméno pro tentýž inode, a inode čísla jsou jen lokální v rámci FS.
Operační systém nemůže používat více souborových systémů současně, pokud jsou na stejném fyzickém disku.

Odpověď

NEPRAVDA — na jednom fyzickém disku může být více oddílů s různými souborovými systémy a OS je všechny může připojit a používat současně.
Při mazání souboru je třeba načíst inody celé cesty včetně mazaného souboru, ale obsah datových bloků samotného souboru se kvůli smazání číst nemusí.

Odpověď

PRAVDA — pro smazání stačí načíst inody po cestě a uvolnit bloky podle odkazů; vlastní data souboru se nečtou.
Při operaci mv mezi dvěma adresáři na témže souborovém systému se obsah souboru fyzicky nekopíruje — mění se jen adresářové položky.

Odpověď

PRAVDA — přesun v rámci jednoho FS jen přepojí adresářovou položku (inode zůstává). Mezi různými FS je mv naopak kopírováním a smazáním, takže se data přenášejí blok po bloku.

Skripta → Datová úložiště a souborové systémy