ZOS Flashcards
Struktura OS
- modul pro správu procesů
• program, proces, vlákno, plánování procesů a vláken
• kritická sekce, souběh, synchronizace (semafory, …)
• deadlock, vyhladovění - modul pro správu paměti
• virtuální paměť: stránkování, segmentace - modul pro správu I/O
- modul pro spr ávu souborů
- síťování
- ochrana a bezpečnost
- uživatelské rozhraní
Režimy
- Jádro OS běží v tzv. privilegovaném režimu CPU
• Všechny instrukce CPU jsou zde povoleny - Aplikace v uživatelském režimu CPU
- Některé instrukce zakázány (tzv. privilegované instrukce) např. není přímý přístup k disku, narušitel –> formátování
- Při pokusu o vykonání privilegované instrukce = => chyba, výjimka
- Aplikace musí požádat OS o přístup k souboru, ten rozhodne zda jej povolí
CPU ví, v jakém je režimu podle bitu ve stavovém registru CPU (0 = priv., 1 = uživ.) - CS (code segment) registr;;
Přerušení
Přerušení
Definice:
Metoda pro asynchronní obsluhu událostí, kdy procesor
přeruší vykonávání sledu instrukcí, vykoná obsluhu
přerušení a pak pokračuje v předchozí činnosti.
Rozdělení:
• HW přerušení (vnější) obsluha HW zařízení
• SW přerušení synchronní, instrukcí INT x v kódu procesu
• Vnitřní přerušení (výjimky) procesor oznamuje chyby
při vykonávání instrukcí (dělení nulou)
Systémové volání
vyvolání služby OS poskytované jádrem; aplikace volá službu sys. volání přímo (open, creat), knihovní funkcí (fopen)
Vektor přerušení
index do pole, obsahující adresu obslužné rutiny, vykonané při daném typu přerušení
Maskování přerušení
v době obsluhy přerušení lze zamaskovat méně důležitá přerušení, ale SW přerušení jsou nemaskovatelná (NMI)
Příchod přerušení
dokončí se rozpracovaná strojová instrukce, na zásobník se uloží adresa následující instrukce (CS:IP) tj. kde jsme skončili a kde budeme chtít pokračovat, z vektoru přerušení se zjistí adresa podprogramu pro obsluhu přerušení, přepnutí do priv. režimu, na zásobník se uloží hodnoty registrů, obsluha, instrukce návratu RET (IRET) a přepnutí do uživ. režimu
Jádro
OS = (jádro + systémové nástroje)
- monolitické (= 1 funkční celek) - LINUX
- mikrojádro - model klient-server (malé jádro, oddělitelné části pracují jako samostatné procesy v user space) - HURD
- hybridní - kombinace (Windows)
Přístup k souboru
pomocí ACL nebo základní unixová práva (UGO - rwx)
IRQ
signál, kterým zařízení žádá procesor o přerušení zpracovávaného procesu, IRQL - priorita přerušovacího požadavku
Proces
instance běžícího programu; adresní prostor procesu - MMU (zajišťuje soukromí), kód programu, data, zásobník; stavové informace procesu (registry - PC, SP)
Registry
obecné (EAX…), segmentové (CS, DS…), speciální (IP…)
Pseudoparalelní běh
v jednu chvíli aktivní pouze jeden proces, po určité době pozastaven a spuštěn další (1 CPU)
Stavy procesu
- běžící - využívá CPU
- připravený - pozastaven, aby mohl jiný proces pokračovat, čeká na CPU
- blokovaný - neschopný běhu, dokud nenastane externí událost (čeká na zdroj nebo zprávu)
- nový - právě vytvořený proces
- ukončený
- zombie - proces dokončí svůj kód, pořád má záznam v tabulce procesů, čekání, dokud rodič nepřečte exit status voláním wait
- sirotek - jeho kód stále běží, ale skončil rodičovský proces, adoptován procesem init
Přechody stavů procesu
- plánovač vybere nějaký proces
- proces je pozastaven, plánovač vybere jiný proces (např. vypršelo časové kvantum)
- proces se zablokuje, protože čeká na událost
- nastala očekávaná událost
PCB
info o procesu v tabulce procesů
Ukončení procesu
- proces úspěšně vykoná kód programu
- skončí rodičovský proces
- proces překročí limit nějakého zdroje
MMU
více procesů v paměti a každý má paměť pro sebe, program pracuje s virtuálními adresami a MMU je převede na fyzické adresy
Procesy a vlákna
každý proces svůj vlastní PID, PGID, UID, GID, adresový prostor a místo, kde leží (bod běhu), instrukce programu, registry, zásobník, haldu, popisovače souborů, signal actions, shared libraries, IPC, aktuální prioritu, výši priority (nice), celkovou velikost, velikost použité fyzické paměti, stav, %CPU; PID atd. uložený v PCB (včetně kontextu procesu) v tabulce procesů, ta je v RAM a je to datová struktura jádra OS
Vlákna
v procesu sdílejí adresní prostor, otevřené soubory; každé vlákno má svůj zásobník, čítač instrukcí, obsah registrů, zásobník, lokální proměnné, množinu blokovaných signálů, plánovací vlastnosti
Plánování procesů
stupeň multiprogramování = počet procesů v paměti
- nepreemptivní - proces skončí, nebo běžící -> blokovaný;
- preemptivní - navíc přechod běžící -> připravený (uplynulo časové kvantum), k odstavení procesu může dojít v nevhodný čas
Modely vláken
1:1 - vlákna v jádře
M:1 - vlákna jen v user space
M:N - komerční unixy (Solaris)
Kritická sekce
místo v programu, kde je prováděn přístup ke společným datům
Pravidla pro řešení časového souběhu
- vzájemné vyloučení - uvnitř KS vždy jen 1 proces
- proces mimo KS nesmí blokovat jiné procesy (bránit ve vstupu do KS)
- žádný proces nesmí na vstup do KS čekat nekonečně dlouho
Aktivní čekání
průběžné testování proměnné ve smyčce, dokud nenabyde očekávanou hodnotu, ale plýtvá časem CPU, tak se používá, jen pokud předpokládáme krátké čekání (spin lock)
Spin lock s instrukcí TSL
instrukce, která otestuje hodnotu a nastaví paměťové místo v jedné nedělitelné operaci (Test and Set Lock)
Semafor
tvořen celočíselnou proměnnou „s“ (obsahující nezáporné celé číslo, hodnotu lze přiřadit pouze při deklaraci, 0 = sem. je zablokovaný, nenula = kolik procesů může zavolat P(), aniž by se blokly) a frontou procesů, které na něj čekají; nad semafory pouze operace P(s) a V(s) - nedělitelné operace
P - blokuje, snižuje;; V - odblokuje, zvyšuje;;
Mutex
(binární semafor, vzájemné vyloučení), spin_lock bez aktivního čekání; implementace pomocí yield - dobrovolně se vzdává CPU, šetří čas
Monitor
v jednu chvíli aktivní pouze jeden proces
výhody - automaticky řeší vzájemné vyloučení, větší odolnost proti chybám programátora;
tvořen podmínkami (definovány a použity pouze uvnitř bloku, nejsou proměnné v klasickém smyslu, neobsahují hodnotu, představují frontu procesů, které na danou podmínku čekají) -
c. wait - volající bude pozastaven nad podmínkou c, pokud je některý proces připraven vstoupit do monitoru, bude mu to dovoleno;
c. signal - pokud existují procesy pozastavené nad podmínkou c, reaktivuje jeden z pozastavených procesů a bude mu dovoleno pokračovat v běhu uvnitř monitoru,, pokud nad podmínkou nespí žádný proces, nedělá nic;;
Reakce na signal
Hoare - proces volající c.signal se pozastaví, vzbudí se až poté, co předchozí reaktivovaný proces opustí monitor nebo se pozastaví;
Hansen - signal smí být uveden pouze jako poslední příkaz v monitoru, po volání signal musí proces opustit monitor
Meziprocesová komunikace
přes sdílenou paměť, zasíláním zpráv, signály (jen v Linuxu, speciální zpráva zaslaná jádrem OS procesu, asynchronní);;
Sdílená paměť
vyžaduje umístění objektu ve sdílené paměti, někdy nevhodné (bezpečnost - globální data přístupná kterémukoliv procesu bez ohledu na semafor), někdy nemožné (procesy běží na různých strojích, komunikují spolu po síti)
Předávání zpráv
send(adresát, zpráva) - neblokující,
receive(odesílatel, zpráva) - blokující;
blokující send - čeká na převzetí zprávy příjemcem, neblokující send - vrací se ihned po odeslání zprávy
blokující receive - není-li ve frontě žádná zpráva, zablokuje se
neblokující receive - není-li zpráva, vrací chybu;
Adresování
skupinové (multicast) - zprávu pošleme skupině procesů, obdrží ji každý proces;
všesměrové (broadcast) - zprávu posíláme všem procesům, více nespecifikovaným příjemcům
Délka fronty zpráv
nulová - žádná zpráva nemůže čekat, odesílatel se zablokuje (rendezvous);
omezená - blokování při dosažení kapacity
neomezená - odesílatel se nikdy nezablokuje
Doručování zpráv
v pořadí FIFO, neztrácejí se
Určení adresáta
procesy nejsou trvalé entity, proto neadresujeme proces, ale frontu zpráv (nepřímá komunikace)
Fronta zpráv
mailbox - více odesílatelů a příjemců
port - omezená forma mailboxu, zprávy může vybírat pouze 1 příjemce
Ztráta zprávy
řeší potvrzení o přijetí; pokud vysílač nedostane potvrzení do nějakého časového okamžiku, zprávu pošle znovu
ztráta potvrzení - zpráva dojde ok, ztratí se potvrzení - řeší číslování zpráv, duplicitní zprávy se ignorují
Problém autentizace
zprávy možno šifrovat, klíč známý pouze autorizovaným uživatelům (procesům), zašifrovaná zpráva obsahuje redundanci (umožní detekovat změnu zašifrované zprávy)
Lokální komunikace
- na stejném stroji, snížení režie;
dvojí kopírování (z procesu odesílatele do fronty v jádře, z jádra do procesu příjemce);
rendezvous - eliminuje frontu zpráv, zpráva se zkopíruje z odesílatele přímo do příjemce
virtuální paměť - paměť obsahující zprávu je přemapována (z procesu odesílatele do procesu příjemce), zpráva se nekopíruje
Struktura klient-server
klient požaduje vykonat práci, server práci vykoná
RPC
dovolit procesům (klientům) volat procedury umístěné v jiném procesu (serveru)
Kroky komunikace klient - server
- klient zavolá spojku klienta (reprezentující vzdálenou proceduru)
- spojková procedura argumenty zabalí do zprávy a pošle ji serveru
- spojka serveru zprávu přijme, vezme argumenty a zavolá proceduru
- procedura se vrátí, návratovou hodnotu pošle spojka serveru zpět klientovi
- spojka klienta přijme zprávu obsahující návratovou hodnotu a předá ji volajícímu;;
RPC více procedur
spojka klienta ve zprávě předá kromě parametrů i číslo požadované procedury
Bariéry
synchronizační mechanismus pro skupiny procesů, skládá se z fází (žádný proces nesmí do následující fáze, dokud všechny procesy nedokončily fázi předchozí), na konci každé fáze synchronizace na bariéře (volajícího pozastaví, dokud všechny procesy také nezavolají barrier), všechny procesy opustí bariéru současně
Čtenáři-písaři
řešení s předností čtenářů (písaři musí čekat, až všichni čtenáři skončí);;
Zámky v OS a DB
přístup procesu k souboru nebo záznamu databázi;
výhradní zámek (pro zápis) - nikdo další nesmí přistupovat
sdílený zámek (pro čtení) - mohou o něj žádat další procesy;
granularita zamykání - celý soubor vs. část souboru, tabulka vs. řádka v tabulce;;
Plánovač
určí, který proces (vlákno) by měl běžet nyní
Dispatcher
provede vlastní přepnutí z aktuálního běžícího procesu na nově vybraný proces
CPU, IO burst
CPU burst - vykonávání kódu,
I/O burst - čekání,
CPU-vázaný proces - hodně času tráví výpočtem,
I/O-vázaný proces - hodně času tráví čekáním na I/O
Plánování
nepreemptivní - každý proces dokončí svůj CPU burst;
preemptivní - (u interaktivních systémů) proces lze přerušit kdykoliv během CPU burstu a naplánovat jiný, vyžaduje speciální hardware (timer - generuje přerušení),, nejen u uživatelských procesů, ale i u jádra
Cíle plánování
spravedlnost - srovnatelné procesy srovnatelně obsloužené;
balance - snaha o maximální vytížení CPU (+ RAM a periferií), páč čas CPU… je drahý,, u dávkových systémů
propustnost - maximalizovat počet úloh dokončených za jednotku čas
doba obrátky - minimalizovat čas mezi přijetím úlohy do systému a jejím dokončením
Prioritní funkce
bere v úvahu čas, jak dlouho proces využíval CPU, aktuální zatížení systému, paměťové požadavky procesu, čas strávený v systému, celkovou dobu provádění úlohy, urgenci;
statická priorita - přiřazena při startu procesu;
dynamická priorita - za běhu, dle chování procesu (dlouho čekal); plánovač snižuje dynamickou prioritu běžící procesu při každém tiku časovače
Rozhodovací pravidlo
malá pst stejné priority (náhodný výběr), velká pst (cyklické přidělování kvanta, chronologický výběr - FIFO)
Plánovací algoritmy
FCFS (nepreemptivní FIFO) - nově příchozí úloha na konec fronty připravených a běží, dokud neskončí (když neprovádí I/O, jinak do stavu blokovaný,, až provede I/O, jde na konec fronty připravených);
SJF - nepreemptivní, nejkratší úloha jako první, ale musíme dopředu přibližně znát dobu trvání úloh
SRT - preemptivní, plánovač vždy vybere úlohu, jejíž zbývající doba běhu je nejkratší;
MLF - nepreemptivní, N prioritních úrovní, každá úroveň má svou frontu úloh, úloha vstoupí do systému do fronty s nejvyšší prioritou, na každé prioritní úrovni stanoveno max času CPU, který může úloha obdržet,, proces obsluhuje nejvyšší neprázdnou frontu; upřednostňuje I/O vázané
Plánování procesů v interaktivních systémech
proces nesmí běžet příliš dlouho, každý proces je jedinečný a nepředvídatelný;
Round Robin - každému procesu přiřazeno časové kvantum, po které může běžet,, pokud proces nevyužije celé časové kvantum, nebo se zablokuje před uplynutím kvanta (dobrovolně se vzdá CPU), nebo vyprší časové kvantum (odebrán CPU nedobrovolně, přejde do stavu připravený), naplánuje se další proces
Časové kvantum
nemusí být konstantní;
krátké - snižuje efektivitu (velká režie s přeplánováním),
dlouhé - zhoršuje dobu odpovědi na interaktivní požadavky
Dynamická priorita
1/f (f = velikost části kvanta, kterou proces naposledy použil), zvýhodní I/O vázané
Spravedlivé sdílení
přidělovat čas každému uživateli (vláknu) proporcionálně, bez ohledu na to, kolik má procesů (N uživatelů, každý dostane 1/N času)
Loterie
procesy obdrží tickety (losy), plánovač vybere náhodně 1 tiket, vítězný proces obdrží cenu - 1 kvantum času CPU, důležitější procesy - více tiketů, aby se zvýšila šance na výhru; výhody - spolupracující procesy si mohou předávat losy, rozdělení času mezi procesy v určitém poměru
Afinita
určení jader CPU, na kterých může proces běžet
hard afinity - seznam jader
soft afinity - vlákno přednostně plánováno na procesor, kde běželo naposledy
Zdroje
žádost, použití, uvolnění
Podmínky vzniku uvíznutí
musí být splněny všechny 4 podmínky:
- vzájemné vyloučení - každý zdroj je buď dostupný, nebo přiřazen právě 1 procesu (spooling - soutěžení o tiskárnu);
- hold and wait - proces držící přiřazené zdroje může požadovat další;
- nemožnost odejmutí - přiřazené zdroje nemohou být procesu násilně odejmuty (musí je sám uvolnit);
- cyklické čekání - cyklický řetězec procesů, kde každý čeká na zdroj držený dalším členem;
Uvíznutí
cyklus v grafu je nutnou a postačující podmínkou pro vznik uvíznutí; pokud by procesy žádaly o zdroje ve stejném pořadí, uvíznutí nenastane
Vypořádání se s uvíznutím
- ignorace - předstíráme, že problém neexistuje (pštrosí algoritmus), vysoká cena za eliminaci uvíznutí; u uživatelských procesů uvíznutí neřešíme, ale snažíme se, aby k uvíznutí nedošlo v jádře OS;
- detekce a zotavení - systém se nesnaží zabránit vzniku uvíznutí, jen ho detekuje a pokud nastane, provede akci pro zotavení; zotavení pomocí preempce - vlastníkovi dočasně odebrat zdroj; zotavení pomocí zrušení změn (checkpointing) - zápis stavu procesů do souboru, aby proces mohl být v případě potřeby vrácen do uloženého stavu; zrušení procesu - nejhorší způsob;
- dynamické zabránění - většinou procesy žádají o zdroje po jednom; je třeba rozhodnout, zda je přiřazení zdroje bezpečné, pokud ne, pozastaví se žádající proces; stav je bezpečný, pokud existuje min. 1 posloupnost, ve které mohou procesy doběhnout bez uvíznutí (ale i když není bezpečný, uvíznutí nastat nemusí) - bankéřův algoritmus (v praxi nepoužitelný);
- prevence uvíznutí - 4 Coffmanovy podmínky;;
Vyhladovění
procesy požadují zdroje, ale proces zdroj nikdy nemusí obdržet (filosofové zvedají a pokládají vidličku, SJF) - řešení: FIFO