40 Flashcards
adresování HDD
CHS, LBA; sektor − nejmenší adresovatelná jednotka
alokační blok
2^n sektorů (4KB, 2^3 * 512), nejmenší logická jednotka (pro OS)
plánovač diskových operací
minimalizace diskové režie, plánuje přístupy na disk
soubor
základní organizační jednotka pro uchování dat; má metadata: jméne, velikost, práva, čas, vlastník
souborový systém
je souhrn pravidel definujících chování a vlastnosti souborů, možnosti jejich log. organizace a způsob uložení
VFS
vrstva zastřešující souborové systémy
žurnál
slouží pro záznam modifikovaných metadat, implementace jako cycklicky přepisovatelný buffer, ochranan dat před ztrátou integrity, atomické operace
fragmentace
interní − v rámci alokačního bloku (nelze zapsat soubor menší než al. blok)
externí − alokační bloky jednoho souboru nejsou za sebou
přístupová doba
doba vystavení hlad + rotační zpoždění
adresář
soubor obsahující seznam dvojit (jméno souboru, čáslo i-uzlu)
smazání souboru
smazání záznamu z adresáře a dekrementace čítače hard-links v i-uzlu
extent
posloupnost proměnného počtu bloků logicky i fyzycky za sebou (exFat, tam jde jsou B+ stromy)
UFS struktura
boot block, super block, tabulka i-uzlů, data block
i-uzel (definice)
základní datová struktura popisující soubor (~metadata)
i-uzel (obsah)
typ souboru, délka, m a c -time, UID, GID, práva, hard-links, tabulka odkazů na data
LAP (logický adresový prostor)
množina všech možných adres použitelných procesorem, každý proces a jádro má svůj LAP
FAP (fyzický adresový prostor)
skutečná velikost RAM, jen jeden a sdílený; velikost fap-lap nemusí souhlasit, s fap pracuje jen OS
Virtualizace paměti
mapování lap −> fap; umožňuje použít swap dat na disk ke zvětšení RAM
implementace systému virtuální paměti
spojité bloky, segmentace, stránkování
spojité bloky (virtualizace paměti)
procesům přidělovány spoj. bloky, uvolňováním vzikají díry -> externí fragmentace fap;
easy implementation, fast
segmentace (virtualizace paměti)
LAP tvořen několika segmenty: stack, data, code; logic adres = segment+offset; zmírnění externí fragmentace
stránkování (virtualizace paměti)
moderní přístup, Lap stránky, Fap rámce (pevná velikost obojí !!) -> malá externí fragmentace, dochází k interní; MMU mapuje lap-fap; on-demant stránkování − lap větší než fap, jen některé log. adr. se mapují do fap
tabulka stránek (u stránkování)
řeší mapování page-frame; jednoúrovňová; hierarchická
jednoúrovňová tabulka stránek
spodní bity logic. adr. = spodní bity fizick. adr; horní bity index do tabulky, kde je horní část fyzick. adr.
hierarchická tabulka stránek
spodní bity jsou stejné u logic a fyzick.; horní bity index to tabulky 1. úrovně −> ukazatel na příslušnou tabulky 2. úrovně −> jako index se použití prostřední bity log. adr. −> horní část fyzick. adr (výhoda: v paměti je jen 1. úrovň. tabulka a ostatní jen když je potřeba, pomalejší)
Algoritmy pro řízení výpadku stránek
druhá šance, fifo, LRU, LFU, Random
algoritmus druhé šance (výpadek stránky)
po druhé přístup ke stránce −> označí se (referenč. bit = 1); vyhazuje se první bit, který nemá ref. bit.
TLB (transition look-aside buffer)
cachování tabulky stránek, pro urychlení nalezení stránky
page deamon
proces jádra, odstraňuje stránky z tabulky, když se zaplní na předem def. úroveň
Správa procesů (prvky)
plánovač (scheduler), přepínač kontextu (dispatcher), správa paměti, meziproc. komunikace (IPC)
Process (co je a co obsahuje)
běžící program; uloženo ve struktuře PCB (proc. control block) − PID, stav, řídicí program, registry, zásobník
Stavy procesu
init, runnable, running, suspended, sleeping, zombified; (vytvořený, připravený, běžící, …)
Proč plánování procesů
Minimalizace využití CPU, scheduler vybírá nejvhodnější proces pro běh v daný okamžik
nepreempt a prepempt
nepreempt − běžící proces sám rozhoduje, jetsli uvolní proces;
preempt − scheduler přepíná procesy, proces nemá kontrolu nad svým během
plánovací kritéria procesů
využití procesoru, propustnost, doba běhu, čekání, odezvy
přepnutí kontextu (co se musí odehrát?)
uložení stavu aktuálního procesu (PCB), nahrání nového stavu procesu −> cca 100 až 1000 instrukcí (1−1000microsec)
vlákno
odlehčený proces, sdílejí paměť, kód, zdroje (ne registry a stack)
plánovací algoritmy
FCFS, Round-robin, SJF (shortest-job first), prioritní plánování
FCFS plánovací alg.
fifo fronta s procesy, nepreemptivní
round-robin plánovací alg.
preemptivní varianta fcfs; definováno časové kvantum pro proces (4−30 ms)
SJF plánovací alg.
zvyšuje propustnost, nepreempt, hrozí hladovění, nutno znát (odhadnout) dobu trvání procesu
prioritní plánování
procesy mají priority, OS má největší; stejná priorita FCFS, hrozí hladovění
víceúrovňové plánování
rozdělení do skupin, v rámci skupiny round-robin
víceúrovňové plánování se zpět. vazbami
nový proces jde do fronty s největší prioritou a postupně se propadává do nižších priorit, dole round-robin
linux plánování (víceurovňové se 100 statick. priorit. úrovněmi)
1−99 fcfs nebo r-r; 0 běžné procesy, dynamicky se mění priority -20−19 (priorita se snižuje, pokud vytěžuje cpu); CFS (completely fair scheduler) − vybírá proces s nejmenším stráveným časem
problémy plánování
vyhladovění − proces s nízkou prioritou neustále čeká -> časová kvanta;
inverze priorit − low-prior alokuje zdroj, přepne se kontext na vyšší, chce stejný zdroj -> priority celling, inheritance, zákaz přerušení
Komunikace procesů
signály, zprávy, roury, sockety, sdílená paměť, RPC (remote procedure call)
signály (komunikace procesů)
int zaslaný procesem speciálním rozhraním, asynchronně generovány při chybách (dělení nulou), extern událostech (časovač, I/O), na žádost cpu (kill);
SIGKILL, SIGALARM, SIGCONT (lze předefinovat obsluhu); jsou blokovat (ne KILL, STOP, CONT)
Synchronizace procesů
řešení problémů u paralelních procesů, kt. přistupují ke sdíleným zdrojům; race-condition (časově závislé chyby)
kritická sekce (co to je?)
úsek kódu, jehož korektní provádění vyžaduje vzájemné vyloučení vůči jiným úsekům kódu;
kritická sekce (co je potřeba zajistit?)
vzájemné vyloučení a dostupnost krit. sekce (každý proces by měl mít možnost vstoupit)
kritická sekce (nesmí dojík k?)
blokování (proces čeká před volnou kritickou sekcí); stárnutí (proc čeká na podmínku, kt. může, ale nemusí nastat; uváznutí (deadlock)
uváznutí (deadlock) - definice
Každý ze skupiny procesů je pozastaven a čeká na uvolnění zdroje s výlučným přístupem, který je vlastněný nějakým procesem z této skupiny.
4 nutné podmínky uváznutí (Coffmanovy)
1) vzájemné vyloučení při používání prostředků; 2) proces vlastní a je pozastaven; 3) uvolnit může pouze proces sám po dokončení využití; 4) vzniká cyklická závislost na sebe čekajících procesů
řešení deadlocku
prevence − porušení aspoň jedné podmínky;
vyhýbání − procesy dopředu deklaruje jaké zdroje a jak využije;
detekce a zotavení − dopředu nic, tvorba cyklického grafu, ukončení procesu a odebrání zdrojů;
Zajistění výlučného přístupu (mechanismy)
HW (testandset, swap atomické instrukce), SW (semafory, monitory, petersonův algoritmus)
test-and-set
atomická instrukce nad sdílenou pamětí; přečte hodnotu, kterou vrátí, ale ještě ji nastaví na true; aktivní čekání − while(testandset(lock)); 0 volný, 1 zabraný;
Semafrory
vycházení s test-and-set, ne-aktivní čekání (proces je dán do fronty a uspán); Celočíselná proměnná indikuje volnost; S > 0 může, S <= 0 nemůže; atomické operace lock() , unlock()
lock()
decrement; if (S < 0) que put, block();
unlock()
increment; if někdo čeká, activate(); if (S <= 0) que get, aktivate();
Monitory
vysoko úrovňové mechanismy nad semafory; ATD zapouzdřující sdílená data a poskytuje metody + zámek; součástí jazyka (implementuje překladač); snadněji se používá, menší pravděp. chyby
Petersonův algoritmus
Proces který chce do krit. sekce nastaví příznak zájmu, ale dá přednost protivníkovi. Ten buď nemá zájem nebo dá přednost taky.
Transakce
skupina operací, které jsou vykonaní jako celek (-> udržení konzistentního modelu);
ACID
atomicity; consistency - zavedení integrit. omezení; isolation; duratibility
Soustava lineárních rovnic
1) přímé metody: Cramerovo pravidlo, Gauss. eleminace;
2) iterační metody: Jacobiho, Gauss-Siedlova (dosazujeme hned)
Determinant 3x3
Saurussovo pravidlo
Jedna nelineární rovnice (princip)
hledáme kořen x (x náleží R), f(x) = 0; (zjistime kolik kořenů, najdeme interval s jedním kořenem (separace kořenů), metodou hledáme přibližně kořen)
Věta, kt. nám říká že na intervalu <a> leží alespoň jeden kořen</a>
f(a) * f(b) < 0
Jedna nelineární rovnice (metody)
Půlení intervalu, Regula-falsi, Sečen, Newtonova
Diferenciální rovnice
popisují fyzikální děje, obsahují derivace, poč podmínky;
Eulerova metoda (vzorec + princip)
y(i+1) = f(x) + h * f(xi, yi); spočítáme derivaci (směrnici tečny) v aktual. bodě a s touto směrnicí se posuneme o krok h; menší krok, větší přesnost;
Vícekrokové metody řešení dif. rovnic prvního řádu
počítáme přibližné řešení v dalším bodě pomocí několika předchozích; pomalý rozjezd; Adams-Bashforth
Runge-kutta 4. řádu
nejpoužívanější; počítá směrnici v polovičním kroku; pak ještě jednou, ale z předešlého vypočtu a pak určí směrnici v bodě x+h z předešlého výpočtu; k4 = f(x+h, y+hk3); pak zprůměruje věchny ‘k’ * h; yn+1=yn + h1/6(k1+2k2+2k3+k4);
Runge-kutta 2. řádu
k1 = f(xn, yn), k2 = f(xn + 1/2h, yn+1/2h*k1) yn+1= yn + h*k2
Závislost chyby na délce kroku
y~err; x~krok; numerická chyba (klesá s menším krokem) a zaokouhlovací chyba (roste s menším krokem)
Generování náhodných čísel
náhodné (fyzikálně dané, pomalé hw), pseudonáhodné (rychlé, algoritmické) - kongurentní generátor xi+1 = (axi + b) mod m
distribuční funkce
F(x); udává P(X
transformace rozložení pravděpodobnosti
převod jednoho rozložení na druhé; inverzní a vylučovací transformace
hodnost matice
počet lineárně nezávislých řádků
Kolik má a může mít kořenů soustava rovnic
0 – počet lineárně nezávislých rovnic soustavy je větší než počet neznámých
1 – počet lineárně nezávislých rovnic soustavy je rovný počtu neznámých
INF – počet lineárně nezávislých rovnic soustavy je menší než počet neznámých
