Tu sú vypracované otázky k predmetu [[SWI004]]... Originálna verzia (pravdepodobne zozbieraná z rôznych zdrojov) je z http://gask.oktawa.net/QU.html .
'''Pozor !!! Jde pouze o Questions, Excercices tu chybi.'''
= Process Alone =
== Explain what is a process. ==
* proces je abstrakce, pokud nemáme vlákna, můžeme brát za proces spuštěný program (tj. program nahraný do paměti) a stavy zdrojů jenž využívá
* pokud máme vlákna, tak proces může být brán jako pasivní obal (tj. sám o sobě neběží), který obsahuje vlákna.
* instrukce, registry, paměť
* někdy má vlastní virtuální adresový prostor
== Explain how the operating system or the first application process gets started when a computer is switched on. ==
* v HW (procesoru) je napevno zadrátovaná adresa, od které se začínají vykonávat na CPU instrukce
* => tzv. bootstrap program, vypálený typicky v některé z pamětí (eprom, rom, apod.)
* bootstrap inicializuje HW, načítá program code a statické proměnné, tzv. program image (image dalšího programu)
EDIT: Otázka je, jak se tam dostane OS. Bootstrap načte většinou jen další zavaděč někde na začátku disku. Ten pak načte zavaděč z oddílu(protože ten tupý zavaděč BIOS nemá drivery pro file systémy a neví, kde má najít boot oddíl), a ten teprve slavnostně načte zavaděč pro OS. Je to proto, že boot sectory jsou většinou fixní a krátké.
== Explain what it means to relocate a program and when and how a program is relocated. ==
* absolutní adresování - adresy v programu jsou zapsané přímo absolutní hodnotou - problém nastává, když se program nenahrává na stejné místo v paměti
* relokace - proces úpravy image programů, tak že posune jednotlivé adresy programu o daný offset (podle toho, kam se program nahraje)
* ?program se relokuje při zavedení programu do paměti?
* samotná relokace spočívá v tom, že se z fixup table berou jednotlivé odkazy do kódu na adresy, které je třeba změnit a k nim se připočte base register
* pokud má každý proces virtuální adresový prostor, tak se samotný program relokovat nemusí (např. program začíná vždy na adrese 0x0)
vs.
* relativní adresování - adresy v programu jsou psány stylem adresa + offset podle globální tabulky symbolů vzniká nám tak position independent code, ale vzniká tak více instrukcí
EDIT: Kdy se to dělá? Tak u sdílených knihoven je občas nutnost mít je na jiných adresách, třeba proto, že se bijí s jinými knihovnami. A další důvod je randomizace, pro zabránění útoků. Když chce útočník skočit na fixní adresu, kde očekává specifický kód.
== Explain what information is needed to relocate a program and where it is kept. ==
* fixup table – tabulka s pointery na adresy v kódu, kde je třeba opravit při relokaci adresy
* může se nacházet v hlavičce obj file, sama tabulka je relativní, takže i pointery v ní musí být pozměněny
* může se nacházet v sekci binárky, například ve formátu ELF v části .rel
* mrkněte sem: http://www.linuxforums.org/articles/understanding-elf-using-readelf-and-objdump_125.html
== Explain what it means to link a program and when and how a program is linked. ==
* merge obj souborů, každý poskytuje tabulku symbolů
* resolve externals - znamená průchod tabulkami a nahrazování referencí z jednoho souboru do druhého
* relocate symbols – konečná relokace souborů
* statické linkování - při překladu souboru se nahraje celá knihovna k binárce a patřičně se upraví tabulky symbolů
* dynamické linkování - při překladu se k binárce dají pouze tabulky symbolů, vlastní překlad tabulek symbolů probíhá až při spuštění, za nahrávání knihoven je zodpovědný dynamic loader - součást OS
== Explain what information is needed to link a program and where it is kept. ==
* tabulka s informacemi, které symboly které obj soubory poskytují a kde se uvnitř nacházejí
* ve formátu binárky ELF jsou to např. sekce symtab a dynsym pro statické a dynamické linkování
== Explain what the interface between processes and the operating system looks like, both for the case when the operating system code resides in the user space and for the case when the operating system code resides in the kernel space. ==
* volání systému jsou zabalena do knihovních funkcí, takže se používají v kódu jako klasické funkce
* syscall je speciální rutina s vyššími právy, volaná většinou kódem s nižšími právy, obsahuje kontrolu zda vůbec dovolí rutinu spustit
* samotný syscall – například uložení číslo volané služby do registru a vyvolání přerušení, popřípadě vykonání speciálních instrukcí sysenter a sysexit
* rozhraní musí být efektivní (rychlé přepínání módů), robustní (kvůli škodlivému kódu - raději hodně funkcí, než nějaký bezpečnostní hacky) a flexibilní (aby se později při přidání nových služeb nemuselo měnit)
== Propose an interface through which a process can start another process and wait for termination of another process. ==
* POSIX
** pid_t fork(void) - rodič forkuje, potomek, ale pořád vykonává kód rodiče
** int execve(const char *filename, char *const arvg[], char *const env[]) - potomek začne vykonávat kód programu (kód rodiče je přepsán nově nataženým ze souboru, vrací hodnotu pouze při chybě
** pid_t wait (int *stat_loc) - čeká na ukončení libovolného synovského procesu a vrací jeho pid, případně značí chybu, status = adresa kam nahrát návratovou hodnotu
** pid_t waitpid (pid_t id, int *stat_loc, int options) - obecnejsi verze volani, da se pres ni naprogramovat wait
** void exit(int status) - ukoncuje proces zapisuje navratovnou hodnotu (0 = OK, cokoliv jineho chyba)
* WIN
** bool CreateProcess(), WaitForSingleObject(PID, timeout)
= Achieving Parallelism =
== Explain how multiple processes can run concurrently on a single processor hardware. ==
* multiprocessing – OS umí pustit proces a po určité době ho odstavit, uloží jeho stav/kontext (PC, registry, stack pointer), flushne TLB nebo lépe změní ASID pro nový proces, načte jeho kontext a pustí jej.
* je-li střídání dostatečně rychlé, nastává iluze více běžících procesů zároveň
== Explain what is a thread and what is the relationship between threads and processes. ==
* vlákno je běžící program, aktivita uvnitř procesu, akt vykonávání programu
* proces je pasivní obálka, poskytující běžícím vláknu uvnitř zdroje, kód a paměť
* vlákna jsou vykonávané instrukce uvnitř procesu, vláken v jednom procesu může být více, sdílejí paměť a kód, ale mají každé svůj vlastní zásobník a popřípadě i thread local storage.
== Explain what happens when the thread context is switched. ==
* kontext přepíná zásadně operační systém (čti kód v operačním systému)
* při přepnutí kontextu vlákna uloží operační systém CPU kontext (global purposes registers, flags, stack pointer, program counter) - ukládá ho většinou na stack. Následně se přepne na stack nově naplánovaného threadu, nahraje si z něj registry a pokračuje dále. EDIT: Pozor, také se musí přepínat virtuální paměť, pokud jej thready nesdílí (tedy jsou ty thready z jiných procesů například). Ale to už není tak moc o context switchy ale o přeplánování. Proto bych to raději nepopisoval tak vágně.
* v principu tedy pouze přepnutí na jinou sadu registrů
* Některé procesory mají několik speciálních instrukcí, které přepnutí značně urychlí - intel
* Jiné procesory na to nejsou příliš optimalizované - mips
EDIT: Speciální instrukce pro context switch na procesoru se hodí především proto, že se často různé verze liší počty a typy registrů. Proto, aby to OS nemusel tak složitě handlovat a byla tam zpětná kompatibilita, usnadní ty speciální instrukce život.
== Explain what happens when the process context is switched. ==
* během volání OS je uložen program counter na zásobník, procesor uklácá originální hodnotu na zásobník toho procesu, který bude odstaven
* OS se ujme řízení, uloží ostatní registry na zásobník odstavovaného procesu
* OS přepne zásobník na zásobník procesu který bude pokračovat v běhu
* ze zásobníku se obnoví registry CPU
* '''přepnou se "process dependent" datové struktury, tedy mapování stránek, mapy zdrojů užívaných aktuálním procesem, flushnutí TLB a ostatních cache, etc.'''
* EDIT: K tomu výše. To tak úplně není pravda. Context switch není nutně přeplánování, je to mnohem obecnější pojem. Může jít o nutnost vyřídit interrupt nebo přímo syscall. Ale také o přeplánování. Pokud se tedy do toho vlákna zase vrátím, není nutné mu flushovat TLB (tedy ani měnit process dependent struktury). To se pak týká přeplánování, a ani tam není nutné flushovat TLB, máme-li něco jako ASID. A po každém switchy vypláchnout cache? To by bylo zlý. Zajímavost, pokud jen handluju interrupt, tak se dokonce ani všechny registry nemusí zálohovat. Například některé extended 128bit registry atd. se neočekávají, že by handler potřeboval. Pokud ano, vyvolá se výjimka a teprve potom se to douloží.
* jako poslední se obnoví PC, tedy ukazatel na instrukci, kterou se bude pokračovat v běhu programu, na jehož kontext OS právě přepnul
== Using a step by step description of a context switch, show how an implementation of threads in the user space and an implementation of threads in the kernel space differ in the way the context is switched. Na popisu přepnutí kontextu krok po kroku ukažte, jak se implementace vláken v uživatelském prostoru a implementace vláken v prostoru jádra liší ve způsobu přepínání kontextu. ==
* user threads – uživatelem naprogramovaná vlákna, může být součástí aplikace
* výhody: šetří se režie na volání kernelu, šetří se paměť kernelu, lze naimplementovat „na míru“, přepínání vláken může být kooperativní
* nevýhody: pokud některé vlákno zavolá kernel a zůstane v něm, nemá kdo by vlákno přepnul na jiné, protože aplikace co uživatelská vlákna přepíná se nedostane k lizu; thready nemůžou bez podpory kernelu využívat více procesorů
* kernel threads – vlákna uvnitř kernelu, nebo vlákna spravované kernelem, které používá aplikace
* výhody: lze uzpůsobit plánování vláken na konkrétní procesory, není problém s odnímáním běhu jednotlivým vláknům (spravuje je přeci kernel), není problém s reentrantností knihoven (malloc apod.)
* nevýhody: je to napevno navržené, nelze doimplementovat další fíčury, musí to být opravu bulletproof (pokažený thread v jvm vs. pokažený thread v kernelu)
== Explain how the requirements of interactive and batch processes on the process scheduling can contradict each other. ==
Interaktivní procesy většinu času čekají na vstup a nic nedělají, ale pokud se něco stane, na co mají reagovat, musí se ke slovu dostat rychle. Naproti tomu, akce, kterou musí provést je typicky nenáročná a stačí jim kratší kvanta.
Dávkové procesy to mají přesně naopak. Většinu času něco počítají a, aby pracovaly trochu efektivně (měly data v cache apod.), potřebují, aby je chvilku nikdo nepřerušoval -> vyžadují delší kvanta. Na druhou stranu nepotřebují být plánovány rychle.
== List the typical requirements of an interactive process on the process scheduling. ==
* responsiveness – reakce na to, že se něco děje, reakce na asynchronní události – user input, network requests apod.
* fairness – spravedlivost, procesy s podobnými parametry (priorita, časové kvantum) budou také podobně plánovány a žádný nebude upřednostněn
== List the typical requirements of a batch process on the process scheduling. ==
* efficiency – efektivní využití a rozložení zdrojů (například plánování procesů na více procesorů)
== List the typical requirements of a realtime process on the process scheduling. ==
* predictability – předvídatelnost, systém garantuje určité chování scheduleru, je důležité pro realtime aplikace
* turnaroud – co nejmenší délka úlohy, aby nikdo neblokoval ostatní
== Explain the difference between soft and hard realtime scheduling requirements. ==
* hard realtime – úloha se MUSÍ stihnout do daného limitu - Příklad: algoritmus pro ABS, řídící systém družice.
* soft realtime – úloha se musí stihnout do daného limitu, ale je povolen statistický limit prošvihnutí úloh (třeba jedna úloha ze sta) - Příklad: Přehrávání videa.
== Define typical phases of a process lifecycle and draw a transition diagram explaining when and how a process passes from one phase to another. ==
* init; runing in kernel (return) running in user mode (syscall, int) running in kernel (quantum expires, yield) ready (schedule) running in kernel (wait) waiting (end of wait) ready; zombie
* na 6. strane je pekný obrázok (stavový diagram) [http://www.inf.ufsc.br/~fernando/ine5355/linux-process.pdf stavov v linuxe]
lépe je to videt v materiálech k [http://www.ms.mff.cuni.cz/~forst/IPOVER05.PPT Úvodu do Unixu], je tam i hezky obrázek, který se hodí k popisu inodu
== Explain cooperative context switching and its advantages. ==
* procesy se střídají na procesoru tak, že se každý vzdá po určité době běhu sám
* výhody: menší režie, nejsou nevhodná přeplánování
== Explain preemptive context switching and its advantages. ==
* procesy se střídají na procesoru, ale plánovač má možnost po době dané časovým kvantem každého procesu mu CPU odebrat
* výhody: nikdo si neuzurpuje CPU, robusntější systém odolný proti záměrně „náročným programům
== Explain the round robin scheduling algorithm by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled. ==
* kruhová fronta ready to run procesů, plánovány jsou ty ze začátku fronty, po ukončení nebo vypršení časového kvanta jsou řazeny na konec
GetProcessToRun ( pid = get_first_in_queue_and_rotate(); shedule(pid); )
== Explain the simple priority scheduling algorithm with static priorities by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled. ==
* více round robin front, pro každou prioritu třeba dvě, když je program přeplánován před vyčerpáním časového kvanta, je zařazen do active fronty, když vyčerpá, je zařazen do expired fronty
* vybírá se z fronty s nejnižší prioritou, nejprve z active, potom z expired
* pokud je active prázdná a v expired něco je, fronty se prohodí, přejmenují
Processes are assigned static priorities, the process with the highest priority is scheduled.
Either constant quantum is used or shorter quantum is coupled with higher
priority and vice versa.
== Explain the simple priority scheduling algorithm with dynamically adjusted priorities by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled. ==
* pro každou prioritu jedna fronta, když je program přeplánován před vyčerpáním časového kvanta (chce běžet déle), je posunut nahoru (zvášení priority, interaktivní procesy, žádají o IO), pokud se přeplánuje po vypršení kvanta (chce běžet dlouho), potřebuje delší kvantum, zařadí se o patro níž (kvantum zvýšeno, priorita snížena, mezi procesy co chtějí CPU)
Processes are assigned initial priorities, actual priorities are calculated from the initial
priorities and the times recently spent executing, the process with the highest actual
priority is scheduled.
== Explain the earliest deadline first scheduling algorithm by outlining the code of a function GetProcessToRun that will return a process to be scheduled and a time after which another process should be scheduled. ==
* tupě prioritní round robin, proces s nejnižší deadline vždy musí doběhnout jako první, bude se tedy řadit dle deadline
Procesy mají deadlines do kdy musí nˇeco udˇelat, plánuje se vždy proces s nejbližší
deadline. Deadlines se zpravidla rozdˇelují do hard realtime deadlines , ty jsou krátké
a nesmí se prošvihnout, soft realtime deadlines , ty jsou krátké a obˇcas se prošvihnout
m°užou dokud bude možné zaruˇcit nˇejaký statistický limit prošvihnutí, timesharing
deadlines , ty v podstatˇe nemají pevný ˇcasový limit alemˇely by se do nˇekdy stát, batch
deadlines , ty mají limity v hodinách a obvykle s nimi nebývají problémy.
== Explain the function of the Solaris process scheduler by describing how the algorithm decides what process to run and for how long. ==
* priority 0-160, pro každou round robin,
* timesharing, interactive a realtime classes
* kernel je mostly preemptive
* timesharing: 0-59 (nižší priority mají delší kvantum), priorita se zvyšuje při čekání na něco nebo když proces nespotřebuje své kvantum, priorita se snižuje po spotřebování kvanty, změny priority určuje tabulka
* system stejné jako timesharing, 60-99
* realtime 100-159
* vybírá se proces s nejvyšší prioritou
* poskytuje volání, které požádá kernel o dočasné neodebírání procesoru
== Explain the function of the Linux process scheduler by describing how the algorithm decides what process to run and for how long. ==
* časová složitost plánovače je O(1)
* priority 1-140 , pro každou dvě round robin fronty (active a expired)
* program je v active frontě, pokud byl odstaven před vypršením svého kvanta,
* po vypršení kvanta je v zařazen do expired fronty
* vybírá se fronta s nejnižší prioritou, active fronta má přednost před expire
* je-li active fronta prázdná a v expired něco je, fronty se prohodí
* podpora metriky pro interaktivitu – počítá se podle toho, jak dlouho proces čeká na IO; ty co čekají na IO jsou odměněny, ty které chtějí hodně počítat jsou penalizovány
* program co čeká na IO se z active fronty nevyhazuje
== Explain the function of theWindows process scheduler by describing how the algorithm decides what process to run and for how long. ==
* třídy priorit IDLE, NORMAL, HIGH, REALTIME
* uvnitř každé třídy relativní priorita IDLE, LOWEST, BELOW_NORMAL, NORMAL, ABOVE_NORMAL, HIGHEST, TIME_CRITICAL
* formule pro určení definitivního numera pro prioritu není rozumně hezká
* perlička – třídy normal obdrží boost při přepnutí na foreground
* plánuje se thread s nejvyšší prioritou, na stejné prioritě funguje round robin
* zohledňuje se afinita na SMP
* plánují se thready, nikoli procesy
* priority TIME_CRITICAL smějí uzurpovat procesor
* datové struktury: round robin pro každou prioritu, 32-bitová maska označující neprázdné fronty, 32-bitová maska volných CPU
== Define processor affinity and explain how a scheduler observes it. ==
* svázanost procesu k procesoru – pokud proces běžel na nějakém CPU, v registrech, cachích apod. zůstala pravděpodobně užitečná data. Proto je vhodné při dalším plánování toho procesu jej umístit na naposledy navštívený CPU
* scheduler si může pamatovat, kam který proces umístil
* Windows: každé vlákno má dvě čísla – ideální CPU (generováno třeba náhodně při vzniku) a poslední CPU (dle toho, kde vlákno běželo). Kam naplánovat? Pokud je nějaký CPU volný, plánuje se v pořadí ideální – poslední – aktuální – libovolný. Pokud není volný CPU, hledá se vhodná oběť – ideální – poslední – nejvyšší z možných.
== Propose an interface through which a thread can start another thread and wait for termination of another thread, including passing the initial arguments and the termination result of the thread. ==
* například Windows:
HANDLE CreateThread(...)
* parametry: start address, stack size, argumenty, flags
WaitForSingleObject(...)
* nebo viz semestrálka
* int thread_create (thread_t * thread_ptr, void (* thread_start) (void *), void * data)
* int thread_join (thread_t thr)
* int thread_join_timeout (thread_t thr, const unsigned int usec)
= Process Communication =
== Propose an interface through which a process can set up a shared memory block with another process. ==
int shmget (key_t key, size_t size, int shmemflag)
* allocates a shared memory segment
* vrací identifikátor segmentu sdílené paměti asociované s argumentem key
void *shmat (int shmid, const void *shmaddr, int shmemflag)
* attaches the shared memory segment identified by shmid to the address space of the calling process.
* připojuje sdílenou paměť identifikovanou shmid do adresového prostoru volajícího procesu (attach)
int shmdt(const void *shmaddr)
* detachuje sdílenou paměť
== Define synchronous and asynchronous message passing. ==
* synchronní - procedura co zprávu poslala nemůže pokračovat, dokud jí nedojde odpověď
* asynchronní – procedura nečeká na doručení zprávy a může pokračovat, aniž by dostala odpověď
EDIT: Nevím, proč je to v poznámkách formulováno takhle nešťastně. Ale reálně to mělo znamenat toto.
* synchronní - procedura co zprávu poslala vyžaduje odpověď - je jedno, jestli se blokne nebo ji dostane callbackem.
* asynchronní – procedura nečeká na doručení zprávy.
Sémantika je asi jasná, že pokud čekám na odpověď, tak bez ní nepokračuji dále jako kdybych měl jistotu že došla. Ale není nutné, aby synchronní volání bylo blokující.
== Define blocking and non blocking message sending and reception. ==
* blokující – procedura co zprávu odeslala nebo obdržela čeká na vyprázdnění odesílacíhu bufferu, než může skončit
* neblokující – čekání po odeslání nebo přijetí není možné
EDIT: Tohle je také nějaké zmatené. Navíc se bavíme dosti v obecné rovině. Správně by to podle mě mělo být takto.
* blokující – procedura se muže bloknout čekáním na odpověď.
* neblokující – procedura se nesmí blouknout čekáním na odpověď.
A pokud chci mít proceduru, která není blokující, ale chci čekat na odpověď tak mám jako možnost callback či polling (periodicky se ptám na výsledek).
== Explain how polling can be used to achieve non blocking message reception. ==
* neustále odesílatele dráždím, jestli už něco poslal
* mohu mít tedy blokující proceduru, ale ta je bloknutá jenom po dobu co se ptám. Potom vykonávám něco jiného a po chvilce se opět zeptám, jestli už je zpráva pro mne připravena
EDIT: Tady bych tedy neřekl, že "dráždím" odesílatele. Spíše se dotazuji komunikačního frameworku na mé straně, jestli pro mě již eviduje nějakou odpověď od odesílatele. To by byl šílený overhead, pokud bych se odesílatele neustále ptal, jestli už pro mě má odpověď.
== Explain how callbacks can be used to achieve non blocking message reception. ==
* ve správě kterou odešlu specifikuji svou funkci nebo proceduru
* jakmile zpráva adresátovi dorazí, zavolá mi přes RPC mojí proceduru
* přidám svůj názor (ne možná zcela správný): při zavolání procedury čtení zprávy je v rozhraní této procedury pointer na callback funkci, která bude zavolána v okamžiku přijetí zprávy. Tím pádem se můžu okamžitě vrátit a vlastní přijetí zprávy mi bude oznámeno právě vykonáním callback funkce (typické je ve Widličkách nastavení eventu), ale může se jednat o v podstatě libovonou akci.
== Explain when a synchronous message sending blocks the sender. ==
* odesílatel odešle zprávu a ta nedorazí příjemci
== Explain when an asynchronous message sending blocks the sender. ==
* odesílatel pošle zprávu, ale ta (vinou nějaké chyby) odesílatele ani neopustí
== Propose a blocking interface through which a process can send a message to another process. Use synchronous message passing with direct addressing. ==
direct addressing - přímo adresa příjemce (asymetrické) případně i odesílatele(symetrické)
MPI_SEND(buf, count, datatype, dest, tag)
* IN buf initial address of send buffer (choice)
* IN count number of elements in send buffer (nonnegative integer)
* IN datatype datatype of each send buffer element (handle)
* IN dest rank of destination (integer)
* IN tag message tag (integer)
== Propose a blocking interface through which a process can send a message to another process. Use asynchronous message passing with indirect addressing. ==
indirect addressing - příjemce i odesílatel specifikůjí adresu fronty, do které budou sypat a číst zprávy
MPI_SEND(length, msg, tag, comm)
* IN comm communicator (handle)
= Process Synchronization =
== Explain what is a race condition. ==
* chyba při komunikaci procesů, která se projeví jen někdy – závisí na přeplánování, komunikaci může představovat i psaní nebo čtení z/do sdílené proměnné
* chyba, která nastává, když dva processy přistupují současně ke sdíleným zdrojům, navíc se nemusí vždycky projevit
* EDIT: Pokud výsledek závisí na načasování nebo pořadí neovlivnitelných operací/událostí. Jakýsi nedeterminismus.
== Explain what is a critical section. ==
* místo v kódu, kde může nastat race condition
EDIT: Race condition není nutně critical section. Například při logování mohu logovat události v jiném pořadí a né nutně je to pro mě critical section, pokud je append do souboru atomická operace, nemusím zamykat. Korektnější definicí je, že critical section je oblast v kódu, která nesmí být vykonávána paralelně více než jedním vláknem.
== Explain the conditions under which a simple I++ code fragment on an integer variable can lead to a race condition when executed by multiple threads. ==
* předpokládám neatomickou inkrementaci, potom lze I++ v assebleru zapsat: hodnotu načtu | přičtu 1 | zapíšu
* v když dojde v místě označeném jako | k přeplánování a někdo bude pracovat s proměnnou I a změní jí, došlo k race condition
* EDIT: Může to třeba být tím, že chybí volatille.
== Explain the conditions under which omitting the volatile declaration on an integer variable can lead to a race condition when the variable is accessed by multiple threads. ==
Vynechání volatile by mohlo vadit například u stavové proměnné zámku. Pokud by se překladač, nedej Bože, rozhodl práci s ní vyoptimalizovat a nechat její hodnotu jen v registru, protože se stejně za chvíli zase bude měnit, tak zámky přestanou fungovat. Volatile tenhle druh optimalizace zakáže.
== Describe the Mutual Exclusion synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application. ==
* úkolem je, aby dva procesy, které vykonávají svůj kód souběžně, nevstupovaly do svých kritických sekcí
* příklad: inkrementace nějakého čítače (neuvažuji atomickou inkrementaci)
* [http://dsrg.mff.cuni.cz/~ceres/sch/osy/text/petri-mutual-exclusion.png petriho sieť pre vzájomné vylúčenie (zo slajdov)]
* vic o petriho sitich viz [http://en.wikipedia.org/wiki/Petri_net wiki]
== Describe the Rendez Vous synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application. ==
* úkolem je, aby se dva procesy navzájem nepředběhly, tedy aby se v určitý okamžik oba setkaly na jedom místě a teprve potom oba najednou pokračovaly v běhu
* příklad: předání jednoduché proměnné mezi dvěma procesy. Randezvous dostane jako parametry tag a hodnotu. Tag je typicky adresa v paměti sdílené mezi oběma procesy. Volání randezvous způsobí uspání volajícího dokud nenastave volání randezvous se stejným tagem jiným procesem. Poté si hodnotu vymění a oba jsou probuzeni.
* [http://dsrg.mff.cuni.cz/~ceres/sch/osy/text/petri-rendez-vous.png petriho sieť pre rendez vouz (zo slajdov)]
== Describe the Producer And Consumer synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application. ==
* úkolem je zajistit, aby buffer, který využívají dva procesy (producent, konzument) ani nepřetekl, ani nepodtekl, tedy producent nevyrábí když nemá kam výrobek uložit a konzument nebude bouchat na dveře prázdného skladu :)
* příklad: server s pevnou frontou zpráv
* sit viz. [http://scg.unibe.ch/download/petitpetri/Images/boundedBuffer.png treba tady]
== Describe the Readers And Writers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application. ==
* úkolem je zajistit možnost více čtenářům číst sdílenou proměnnou (paměť) a zamezit zapisovatelům, aby zapisoval v jednu chvíli více než jeden. Když se zapisuje, nikdo v tu chvíli nesmí číst.
* příklad: čtení sdílené paměti
* sit viz. [http://luk.unas.cz/img/Petri.png tady], nebo [http://www.cs.cmu.edu/afs/cs/academic/class/15671-f97/www/lectures/18-PetriNets2/img020.gif tady]
== Describe the Dining Philosophers synchronization task. Draw a Petri net illustrating the synchronization task and present an example of the task in a parallel application. ==
* úkolem je umožnit několika procesům exkluzivně sdílet prostředky
příklad: několik procesů se uchází o exkluzivní vlastnictví prostředků, kdo má resource, tak si jej zamkne. Chce-li stejný zdroj jiný proces, uspí se, dokud není prostředek znovu odemčen.
* sit viz. [http://luk.unas.cz/img/Filo.png na foru]
== Explain how a deadlock can occur in the Dining Philosophers synchronization task. Propose a modification of the synchronization task that will remove the possibility of the deadlock. ==
* například proces potřebuje ke psaní dva soubory, takových procesů je více. Jestliže si každý proces zamkne jeden soubor, nikdo nepoběží (deadlock)
* rešení 1: když zamkne, nebude mít možnost psát a tak odemkne a to budou dělat všichni, nikdo zase nic nenapíše, ale systém bude maximálně vytížen. Řeší se sice deadlock, ale nastává starvation.
* řešení 2: očísluju filosofy i vidličky. Px smí použít nejdříve Fx, teprve když jí vlastní, tak Fx+1. Tím se dedalock odstraní, ale je to neefektivní – všichni mohou držet jednu vidličku a dívat se na stejnou stranu, jak jeden jí a všichni čekají až položí vidličku.
* řešení 3: na začátku mají všichni jednu špinavou vidličku. Když chce filosof jíst, řekne si těm vedle sebe o vidličku. Filosof vedle mu jí podá, pouze pokud jí má a je špinavá (tedy před chvílí s ní jedl), protože je slušný, cestou jí vyčistí. Kdyby měl čistou, nedá mu jí. Po dojedení jsou obě vidličky špinavé. Jedná se o velmi efektivní algoritmus!
== Explain the difference between active and passive waiting. Describe when active waiting and when passive waiting is more suitable. ==
* aktivní čekání: neustále se testuje nějaká podmínka, tím se vlastně čeká. Hodí se pro krátké časy čekání, nebo pokud není k dispozici vhodný signál na ukončení pasivního čekání. Nevýhody – žere čas CPU. Výhody: krátká doba, neobtěžuje OS, rychlejší
* pasivní čekání: proces který čeká na nějakou podmínku je uspán. Probouzí se podnětem z vnějšku, tedy pokud v jiném procesu nastala sledovaná událost. Hodí se pokud se čeká dlouhý čas, tedy nehraje roli zpoždění způsobené uspáním a opětovným probuzením procesu. Musí být také k dispozici vhodný signál na ukončení pasivního čekání.
* pasivní čekání lze také řešit zakázáním přerušení – nedělá se
== Present a trivial solution to the mutual exclusion problem without considering liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable. ==
* sdílená proměnná bude obsazeno
while (obsazeno); //čekám dokud je obsazeno
obsazeno=1;
//kritická sekce
obsazeno=0;
* na přístup ke sdílené proměnné není kladen žádný nárok. Pokud bychom chtěli a měli podporu hardware v instrukcích test and set lock, mohli bychom předcházející kód implementovat stejně, byl by funkční, ale nespravedlivý (nějaký proces by mohl setrvávat příliš dlouho ve své kritické sekci)
ze slidu:
<pre>
while(true) {
bIWantToEnter = true;
if (!bHeWantsToEnter) break;
bIWantToEnter = false;
}
//critical
bIWantToEnter = false;
</pre>
Není to fér a nemusí se nikdo dostat k lizu, ale oproti predchozim prikladu je to bezpecny
== Present a solution to the mutual exclusion problem of two processes including liveness and fairness. Use active waiting over a shared variable. Explain the requirements that your solution has on the operations that access the shared variable. ==
* prinicp: na řadě je vždy ten druhý, když nechce, jdu já – Dekkerův algoritmus
<pre>
MOJE_OBSAZENO = TRUE;
while (JEHO_OBSAZENO)
{
if (NA_RADE != JA)
{
MOJE_OBSAZENO = FALSE;
while (NA_RADE != JA) { };
MOJE_OBSAZENO = TRUE;
}
}
AKCE ();
NA_RADE = ON;
MOJE_OBSAZENO = FALSE;
</pre>
* požadavky na sdílenou proměnnou: spravedlivá implementace pro N procesů musí používat minimálně N sdílených proměnných, které lze číst a zapisovat, nebo N/2 proměnných, které lze číst, zapisovat a měnit pomocí compare & swap
Peterson'ov algoritmus:
<pre>
jaChcemVstúpiť = true; // deklarujem, že mám záujem vstúpiť do kritickej sekcie
jeNaRade = ON; // ale dám prednosť druhému procesu (ak bude chcieť)
while ( onChceVstúpiť && ( jeNaRade != JA ) ) {
// kým druhý proces stále javí záujem, že chce byť v kritickej sekcii
// a nie som na rade ja tak čakám
}
// buď nastala situácia, že druhý proces dokončil svoju kritickú sekciu,
// alebo ma iný proces pustil (nastavil, že na rade som ja)
_KRITICKA SEKCIA_
jaChcemVstúpiť = false;
</pre>
== Describe the priority inversion problem. ==
* velká nevýhoda aktivního čekání – proces s nižší prioritou může zablokovat proces s vyšší prioritou (například tím, že bude pracovat se zdrojem, který proces s vyšší prioritou potřebuje). Tím se vlastně invertuje priorita těch procesů
== Explain how priority inheritance can solve the priority inversion problem for simple synchronization primitives. ==
* řešení 1: když proces začne na něco čekat, jeho priorita se propůjčí procesu vlastnícímu to, na co se čeká – funguje dobře u zámků, u synchronizačních primitiv semafor a conditional variables už ne, protože není jasné, komu by se měla priorita propůjčit, kdo to vlastně odblokuje (nevíme, kdo jako poslední vybere něco ze skladu...)
== Present a formal definition of a deadlock. ==
* 2 nebo více procesů čeká na uvolnění zámku, který je zamčený jiným procesem, který také čeká na uvolnění zámku a nikdo tak nemůže pokračovat v běhu.
* podmínka na níž je blokováno dva nebo více procesů, každý čeká na uvolnění zámku vlastněným tím druhým procesem
* ---
* procesy musí čekat na prostředky v cyklu
* procesy musí prostředky vlastnit výhradně
* procesy musí být schopny přibírat si vlastnictví prostředků
* prostředky nesmí být možné vrátit
== Present a formal definition of starvation. ==
* běžícímu procesu jsou neustále nedostupné potřebné prostředky, bez kterých nemůže skončit úlohu. Nastává v případě, že proces drží prostředky jinému a nechce nebo není schopen se jich vzdát. Druhý proces tedy běží, žádá o prostředky, ale doběhnout nemůže.
== Present a formal definition of a wait free algorithm. ==
A solution to a synchronization problem is said to be wait free when every process is guaranteed to finish in a finite number of its own steps.
Wait-free algoritmus zaručuje, že všechny zúčastněné procesy skončí v konečném počtu kroků
== Describe the interface of a lock and the sematics of its methods. ==
* zámek – mutex
* init_mutex – vytvoří nový zámek, vrací pointer na mutex, parametry jsou atributy (zda se při opakovaném pokusu o uzamčení vygeneruje chyba, bude se ukládat koikrát se zamknulo apod.)
* destroy_mutex – zničí odemčený zámek, parametrem je pointer na zámek
* lock_mutex – uzamkce mutex, paramterem je pointer na mutex
* unock_mutex – odemkne mutex, paramterem je pointer na mutex
* trylock – vrací true, pokud je možné zámek uzamnknout, parametrem je pointer na mutex
* void mutex_init (struct mutex * mtx)
Funkce inicializuje mutex do stavu odemceno.
* void mutex_destroy (struct mutex * mtx)
Funkce provede uklid ridici struktury mutexu. Pokud je rusen mutex,
na kterem jsou jeste zablokovana nejaka vlakna, funkce vyvola panic.
* void mutex_lock (struct mutex * mtx)
* int mutex_lock_timeout (struct mutex * mtx, const unsigned int usec)
Funkce se pokusi zamknout mutex, pokud to neni mozne, zablokuje
vlakno na mutexu.
Varianta _timeout ceka na zamknuti mutexu nejdele usec mikrosekund.
Pokud se behem teto doby podari mutex zamknout, vraci EOK, jinak
ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi.
* void mutex_unlock (struct mutex * mtx)
Funkce odemkne zadany mutex a vzbudi vlakna, ktera byla zablokovana
pri zamykani mutexu. Pokud je symbol DEBUG_MUTEX >= 1, bude
implementace mutexu hlidat, zda je odemykan vlaknem, ktere ho puvodne
zamknulo. Pokud bude mutex odemykat jine vlakno, vyvola panic.
== Describe the interface of a read-write lock and the sematics of its methods. ==
* rwlock_init – inicializuje počet čtenářů, vytváří mutex a vrací pointer na rwlock
* rwlock_write_lock – vstup písaře do kritické sekce, uzamčeno pro zápis
* rwlock_read_lock – inkrementuje počet čtenářů, vstup do kritické sekce
* rwlock_write_unlock – oznámení ukončení psaní
* rwlock_read_unlock – odchod jednoho čtenáře z kritické sekce
* možné ještě trylock a lock_timeout
* void rwlock_init (struct rwlock * rwl)
Funkce inicializuje ridici strukturu r/w zamku do stavu odemceno.
* void rwlock_destroy(struct rwlock * rwl)
Funkce provede uklid ridici struktury zamku. Pokud je rusen zamek,
na kterem jsou jeste zablokovana nejaka vlakna, funkce vyvola panic.
* void rwlock_read_lock (struct rwlock * rwl)
* void rwlock_write_lock (struct rwlock * rwl)
* int rwlock_read_lock_timeout (struct rwlock * rwl, const unsigned int usec)
* int rwlock_write_lock_timeout (struct rwlock * rwl, const unsigned int usec)
Funkce se pokusi zamknout zamek v pozadovanem rezimu, pokud to neni
mozne, zablokuje volajici vlakno na zamku.
Varianta _timeout ceka na zamknuti zamku nejdele usec mikrosekund.
Pokud se behem teto doby podari zamek zamknout, vraci EOK, jinak
ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi.
* void rwlock_write_unlock (struct rwlock * rwl)
* void rwlock_read_unlock (struct rwlock * rwl)
Funkce odemkne zamek a odblokuje vlakna zablokovana na zamku.
== Explain when a lock is a spin lock. ==
* zámek čeká na uvolnění aktivně, spinning označuje opakované testování přístupu
== Explain when a lock is a recursive lock. ==
* zámek lze zamknout vícekrát stejným threadem – vlastníkem, odemknout se musí tolikrát, kolikrát byl zamknut
== Explain why Windows offer Mutex and CriticalSection as two implementations of a lock. ==
* critical sections ve Windows NT si pamatují vlastníka, je možné je zamknout jedním threadm několikrát, jsou poměrně rychlé, ale fungují pouze v rámci jednoho procesu
* mutexy – pro synchronizaci mezi procesy – mají také vlastníka a lock count
== Implement a solution for the mutual exclusion synchronization problem using locks. ==
* oba sdílí jeden zámek, před vstupem do kritické sekce proces zámek zamkne, pro ukončení kritické sekce se zámek zase odemkne
== Describe the interface of a semaphore and the sematics of its methods. ==
* sem_init – vrací pointer na nově vytvořený semafor s hodnotou danou parametrem
* sem_down – sníží atomicky hodnotu semaforu, pokud už byla nula, je proces který semafor volal uspán a čeká na semaforu (vyčerpal jsem kvótu danou semaforem)
* sem_up – je-li na semaforu nějaký čekající proces je odblokován, jinak se zvyšuje hodnota semaforu
* sem_destroy – zničí semafor, je možné různé chování v případě, že na semaforu někdo čeká (všichni se probudí, vyhodí se chyba...)
* sem_trydown – vrací true pokud je možné semafor snížit
* sem_down_timeout – po určitou dobu se bude pokoušet semafor snížit
* - semafor (s casovym limitem)
* void sem_init (struct semaphore * sem, const int value)
Funkce inicializuje semafor a nastavi ho na zadanou hodnotu.
* void sem_destroy (struct semaphore * sem)
Funkce provede uklid ridici struktury semaforu. Pokud je rusen
semafor, na kterem jsou jeste zablokovany nejake thready, funkce
vyvola panic.
* int sem_get_value (struct semaphore * sem)
Funkce vrati hodnotu semaforu >= 0.
* void sem_up (struct semaphore * sem)
Funkce inkrementuje hodnotu semaforu a pripadne odblokuje jedno z
vlaken na nem zablokovanych.
* void sem_down (struct semaphore * sem)
* void sem_down_timeout (struct semaphore * sem, const unsigned int usec)
Funkce dekrementuje hodnotu semaforu pokud je to mozne, jinak
vlakno na semaforu zablokuje.
Varianta _timeout ceka na dekrementovani hodnoty semaforu nejdele
usec mikrosekund. Pokud se behem teto doby podari semafor dekrementovat,
vraci EOK, jinak ETIMEDOUT. Pokud je casovy limit 0, k zablokovani
vlakna nedochazi.
== Implement a solution for the producer and consumer synchronization problem over a cyclic buffer using semaphores. ==
* semafory budou tři – mutex, empty a full
<pre>
semaphore mutex = 1; //slouží k atomickému přístupu do skladu
semaphore empty = N;
semaphore full = 0;
PRODUCER:
produce_item(&item)
down(&empty)
down(&mutex)
enter_item(item)
up(&mutex)
up(&full)
CONSUMER:
down(full)
down(mutex)
remove_item(&item)
up(&mutex)
up(&empty)
consume_item(item)
</pre>
== Describe the interface of a condition variable and the sematics of its methods. ==
* pro potřeby čekání na nějakou složitější podmínku, než jen například plný X prázdný buffer
* cond_init – inicializace podmíněné proměnné, vrací pointer na condvar
* cond_signal – pokud někdo spí na podmíněné proměnné, je jeden proces probuzen
* cond_broadcast – všechny procesy spící na podmíněné proměnné jsou probuzeny
* cond_wait – volající proces se na podmíněné proměnné uspí
* cond_timedwait – pokud před koncem doby nebude podmínka splněna, proces se uspí
* cond_destroy
* void cond_init (struct cond * cvar)
Funkce inicializuje ridici strukturu condition variable.
* void cond_destroy (struct cond * cvar)
Funkce provede uklid struktury condition variable. Pokud je rusena
condition variable, na ktere jsou jeste zablokovany nejake thready,
funkce vyvola panic.
* void cond_signal (struct cond * cvar)
* void cond_broadcast (struct cond * cvar)
Funkce odblokuje jedno resp. vsechna vlakna cekajici na
condition variable.
* void cond_wait (struct cond * cvar, struct * mtx)
* int cond_wait_timeout (struct cond * cvar, struct mutex * mtx, const unsigned int usec)
Funkce atomicky odemkne mutex a zablokuje volajici vlakno na
condition variable. Po odblokovani opet zamkne mutex a vrati
rizeni volajicimu.
(mutex chrání testování podmínky)
Varianta _timeout zablokuje vlakno nejdele na usec mikrosekund, resp.
na dobu odpovidajici limitu a dobu nutnou k opetovnemu zamceni mutexu.
Pokud behem teto doby dojde k odblokovani vlakna, vraci EOK, jinak
ETIMEDOUT. Pokud je casovy limit 0, k zablokovani vlakna nedochazi,
ale pred opetovnym zamcenim mutexu se vlakno jednou vzda procesoru.
== Explain what is a monitor as a synchronization tool and what methods it provides. ==
* skládá se z procedur schopných pracovat se sdílenou proměnnou, mutexu, proměnnou asociovanou se zdrojem (kvůli kterému se synchronizuje) a invariantu, který definuje podmínku potřebnou pro vyhnutí se race condition
* voláním procedury se zamyká zámek, který si proces ponechává do doby, než procedura naskončí, nebo se čeká na platnost podmínky
* každá procedura garantuje, že invariant je v době jejího skončení platný, tím pádem žádný proces nemůže převzít zdroj ve stavu, kdy by mohlo nastat race condition
= Management Among Processes =
== Internal fragmentation leads to poor utilization of memory that is marked as used by the operating system. Explain how internal fragmentation occurs and how it can be dealt with. ==
Interní fragmentace nastává, pokud uživatel dostane větší blok paměti, než si objednal / využívá. To se stává například u heap alokátorů, které umí přidělovat bloky jen o velikostech v násobcích nějaké konstanty. Například buddy systém, který umí jen mocniny dvojky může docílit toho, že proces chce 17B paměti, ale dostane 32B, tedy skoro 50% interní fragmentace. Řešení zas tak moc asi není, jenom přidělovat bloky co nejbližších velikostí jako požadované. Uživatel typicky neví, že má víc paměti, než chtěl, tak s tím moc neudělá.
== External fragmentation leads to poor utilization of memory that is marked as free by the operating system. Explain how external fragmentation occurs and how it can be dealt with. ==
Externí fragmentace spočívá v tom, že v paměti jsou mezi velkými bloky roztroušeny malé, které jsou ale tak malé, že je nikdo nechce. V součtu má tedy systém stále hafo volné paměti, ta je ale rozdrobena do nepoužitelných kousků. Stává se to například zase u těch heap alokátorů, když se hodně alokuje / uvolňuje. Řešení je například bloky setřepat a tím volné místo spojit, to ale jde jenom tehdy, pokud v kódu nejsou absolutní adresy.
== Explain how memory virtualization through paging works and what kind of hardware and operating system support it requires. ==
Procesy nepracují přímo s fyzickou pamětí počítače. Místo toho se jejich virtuální adresní prostor mapuje na fyzický. Pro tyto účely jsou jak virtuální tak fyzický prostor rozděleny do bloků relativně malé pevné velikosti (stránek). Fyzické i virtuální stránky jsou stejně velké. Když proces přistupuje na nějakou adresu, tak ta se nejprve přeloží na fyzickou a s tou se teprve pracuje. Problém je právě v tom překladu a na to je potřeba podpora HW a OS. HW musí vědět, že adresy jsou virtuální a musí mít nějakou jednotku, která se stará o překlady. OS musí dát HW k dispozici data k překladu do stránkovacích tabulek. Musí tyto tabulky vyplňovat a udržovat, přepínat je při přepnutí paměťového kontextu a případně taky stránky swapovat.
== At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that only has the Translation Lookaside Buffer. Explain the role of the operating system in this process. ==
Při překladu adresy se vezme počáteční úsek bitů adresy a zkusí se vyhledat v TLB. Délka tohoto úseku závisí na velikosti stránky a samozřejmě na délce adresy (při 32bit adresách, 4kB stránkách je to 20 bitů). Pokud se mapování v TLB najde, tak se k číslu rámce z TLB přičte zbytek bitů adresy, které tvoří offset do stránky a to dá výslednou fyzickou adresu.
Bity, které typicky ještě ovlivňují vyhledávání:
Global bit - mapování je globální, platí ve všech adresních prostorech
ASID - Address Space Identifier, pokud není nastaven global bit, při hledání mapování se porovnává ještě identifikátor aktuálního adresního prostoru
Valid bit - Indikuje, zda je mapování platné
Present bit - Indikuje, zda je stránka v paměti, nebo je odswapovaná
Role operačního systému je udržovat TLB platnou a naplňovat jí, pokud v TLB není nalezeno mapování.
To kolika stupňové je stránkování a jak probíhá překlad řeší na mipsu operační systém, na některých jiných architekturách existuje určitá hw podpora.
== At the level of individual address bits and entry flags, describe the process of obtaining physical address from virtual address on a processor that supports multilevel page tables. Explain the role of an operating system in this process. ==
Při n úrovňových stránkovacích tabulkách se virtuální adresa rozdělí na n+1 úseků, z nichž prvních n (od nejvyšších řádů) slouží jako indexy do stránkovacích tabulek příslušné úrovně a poslední úsek je opět offset do stránky. První úsek slouží jako index do adresáře stránkovacích tabulek, který jediný musí být vždy namapovaný. Flagy jsou podobné jako u TLB. Role systému je vyplňování a udržování stránkovacích tabulek a taky přepnutí adresáře stránek při přepínání paměťového kontextu.
== Explain the relation between the page size and the size of the information describing the mapping of virtual addresses to physical memory and list the advantages and disadvantages associated with using smaller and larger page sizes. ==
* velikost stránky je rozhodující pro velikost tabulky pro překlad
* pro adresový prostor 32 bitů určuje 12 bitů offset do stránky, tedy stránka bude mít 4KB. Zbývá 20 bitů na adresu stránky, tedy 2^20 položek. Bude-li mít položka velikost 4 byte, potřebujeme tabulku 4MB
* velké stránky nám ukrojí moc velkou část na offset, naopak malé stránky neúnosně zvětšují překladovou tabulku
* EDIT: A v čem nám vadí mít ukrojenou velkou část na offset? 16KiB page = 14 offset -> 9, 9 indexy do tabulek. Bude fungovat v pohodě. Navíc se nám vejde do jedné stránky 4x tolik, takže možná i menší počet výpadků v TLB. Ten hlavní problém tohohle použití je ten, že hrozí větší interní fragmentace. Sekundární je ten, že ta velikost stránky je dneska zadrátovaná na X místech v os a blbě se to mění. A ta formulace toho, že malé stránky neúnosně zvětšují překladovou tabulku by chtěla upřesnit. Oni především mohou vynucovat větší počet úrovní. Což prodlužuje page walking. Obskurní příklad: 1KiB page = 10 offset, 256 záznamů na tabulku => 8 bitu na index do tabulky -> 6,8,8 indexy a 10 offset. Zbytečně jsme si vynutili další úroveň.
== List the advantages and disadvantages of using multilevel page table as a data structure for storing the mapping of virtual to physical memory. ==
* výhody – není třeba rezervovat prostoru pro tabulku stránek celé virtuální paměti, stačí pro použitou část, části tabulky mohou být stránkovány, tabulky v první úrovni mohou mít záznam „not present“, čímž se šetří místo pro tabulky na nižších úrovních, na které by ten záznam ukazoval
* nevýhody – zvyšuje se počet přístupů do paměti, zpomaluje procesor
== List the advantages and disadvantages of inverse page table as a data structure for storing the mapping of virtual to physical memory. ==
Inverted hash tables - mapuje fyzické stránky na virtuální, něco na styl asociativní paměti, pro překlad virt->phy hašování
* výhody – je to rychlé, velikost tabulky závisí na velikosti fyzické, nikoli virtuální paměti
* nevýhody – špatně se prohledávají – hašováním, řešit kolize by bylo nákladné a tak je třeba ještě dodatečných datových struktrur, které využívá OS. Ztěžuje sdílení paměti.
== Explain what a Translation Lookaside Buffer is used for. ==
* cache pro překlad virtuálních na fyzické adresy, první místo, kam se procesor dívá, zdali existuje mapování. Pokud ne, zkoumá překladové tabulky nebo dráždí OS
== Describe the hardware realization of a Translation Lookaside Buffer and explain the principle and advantages of limited associativity. ==
* položky TLB jsou rozděleny do množin (bank) s velikostí N, kde N udává číslo asociativity. Samotné asociativní prohledávání spočívá v HW realizaci pomocí komparátorů, paměť je tedy asociativní pouze v rámci každé množiny - limited cache associativity
* plnně asociatvní paměti jsou drahé, protože jdou špatně vyrobit (fyzika, přetížení obvodů)
výhoda – je to levnější než fully associativity
Co se tím vlastně myslí:
* mám nějakou cache, v ní 50 položek a potřebuju najít rychle položku podle klíče
* mám 5000 komparátorů, kterými postupně ten klíč prochází -> najdu danou položku
* komparátory jsou drahé, tak si to výrobci HW rozdělí
* prohledám prvních 10 (30 komparátorů)
* prohledám dalších 10 (30 komparátorů)
* ...
Výhody: snížení počtu komparátorů -> levnější, nevýhody pomalejší
EDIT: Pardon, ale tohle je totální nesmysl. Neprohledávám postupně jednu množinu za druhou, to by pak trvalo O(|TLB size|/|N|). V reálu to trvá O(1). Funguje to tak, že vezmu adresu a určím v jaké bance hledat (třeba modulo počtem bank). A v té bance potom spustím hledání s plnou asociativitou. Tzn. je to kombinace: indexace + plně asociativní search. Nevýhody jsou takové, že pokud mám n-asociativní TLB. Tak riskuji, že mi záznamy budou padat často do jedné banky, která je velká n a bude se to tam vyhazovat mezi sebou. Na druhou stranu ji mohu mít větší, než kdyby byla plně asociativní. Plně asociativní má třeba MIPS. V podstatě je to stejná anabáze jako s asociativitou u standardní cache. A poslední věc. TLB mohou mít i několik úrovní. Takže teď třeba střílím, ale první by mohla být malá a plně asociativní, druhá třeba n-cestně a poslední jen indexovací.
== How does the switching of process context influence the contents of the Translation Lookaside Buffer ? Describe ways to minimize the influence. ==
* při přepnutí kontextu je třeba invalidovat i TLB (instrukce TLB_INVALIDATE) - většinou se z tabulek vše vyhodí a poté se znovu naplní
* na multiprocesorech má každý CPU svou TLB, musí se vyprázdnit všechny (musí se dát vědět všem virtuálním adresovým prostorům, aby nikde nezůstaly neplatné virtuální adresy)
* lze zlepšit tagovanim stranek tak, že jsou některé namapovány ve všech adresních prostorech a z TLB se nevyhazují
Tohle je celkem hloupost.
* Pří context switchi není potřeba flushovat TLB na všech procesorech. Mapovaní adress spacu danýho procesu se nemění (nevolá se nějaký vma_alloc, vma_free atd.) -> tj. pokud mi tam běží dvě vlákna na dvou procesorech se stejným virt. adress spacem, tak bohatě stačí invalidovat tlb vlákna, co se přepíná.
Zlepšení :
* pokud je v HW věc jako na mipsu ASID, tak tak se zaznamy při přepnutí kontextu nemusí invalidovat, pokud nemáme pro dva různé procesy stejný ASID
* pokud thread co běží a thread, co bude běžet, mají stejný adress space, tak se tlb vůbec nemusí invalidovat
* z toho pak vychází odvážná myšlenka - snažit se, aby thready, které pouštíme na jednom procesoru byly asociovány s co nejmenším počtem různých adress spaců
== Provide at least two criteria that can be used to evaluate the performance of a page replacement algorithm. ==
* kolik informací je potřeba skladovat, aby algoritmus vůbec mohl rozumně běžet
* počty výpadků stránek za běhu aplikace
* rychlost algoritmu – dlouhé hledání volných stránek je mi na tužku
* Já bych ještě dodal zátěž na pozadí. Příklad: při přeplánování musím projít celé mapování a podle accessed, dirty bitů a na základě dat s historie si spočítat histogramy, pstní koláčky a počasí na příští týden :)
== Explain the principle of the First In First Out page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages. ==
* princip: vyhodí se ta stránka, která přišla před nejdelší dobou, je nejdéle v paměti
* realizace: velmi dobrá, drží se pointer na nejstarší stránku a po jejím vyhození se posune
* výhody: je rychlý, snadno realizovatelný
* nevýhody: Beladyho anomálie (012301401234), nezohledňuje využívání stránek procesem – například stránka s velice často využívanými proměnnými bude určitě vyhozena a bude se muset znovu zavádět
== Explain the principle of the Not Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages. ==
* princip: na kterou stránku se nikdo dlouho nedíval ani do ní nepsal, tu asi nikdo nebude potřebovat i v nejbližsí době – princip lokality, algoritmus předpokládá, že referncovaná stránka je důležitější než změněná
* realizace: množiny stránek rozdělené do čtyř kategorií podle nastavených Access a Dirty bitů – (A0D0, A0D1, A1D0, A1D1), vyhazují se vždy stránky z nejnižší kategorie. Podmínka – HW periodicky schazuje Access bit, například po určitém počtu přerušení od timeru, A i D bity se nahazují/shazují hardwarově, na čtyři skupiny si stránky dělí OS
výhody :
* asi žádné velké, strategie se moc nepoužívá (nejspíš kvůli nutnosti neustále měnit bity podle signálu z časovače -> příliš velká režie)
* jinak nejspíš se tím dá zajistit statisticky nižší pravděpodobnost výpadku stránky než při FIFO
== Explain the principle of the Least Recently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages. ==
* princip: stránky používané před krátkým okamžikem budou asi opět brzy použity, budeme si tedy pamatovat dobu, kdy byly stránky použity naposledy a vyhazujeme ty s největší hodnotou čítače – nejdéle nepřistoupené stránky se vyhazují
* realizace: v HW – 64-bitový čítač inkrementovaný po každé instrukci, moc se nepoužívá, v SW – linked list (nepoužívá se, moc velká režie), další možnost – matice n krát n podle počtu rámců, při použití rámce k nastavit řádek k na samé jedničky a vynulovat sloupec k. Při výpadku se pak vybírá rámec s nejnižší binární hodnotou.
* výhody: dá se statisticky zpracovat, dokázalo se, že LRU nezpůsobí nikdy víc než n-krát víc výpadků oproti optimálnímu algoritmu
* nevýhody: známé případy, kdy algoritmus selhává – například aplikace, která bude procházet N+1 stránek způsobí výpadek při každém přístupu
== Explain the principle of the Least Frequently Used page replacement algorithm and evaluate the feasibility of its implementation on contemporary hardware along with its advantages and disadvantages. ==
* princip: stránka s nejmenší frekvencí přístupů za poslední dobu se vyhodí
* realizace: v současném HW je velmi bídná
* nevýhody: informace o počtu přístupů za časovou jednotu je stěží k dispozici, používají se odhady a aproximace, špatné chování algoritmu při změně vytížení stránek (například po startu systému kdy už startovací stránky nebudou potřeba, ale nevyhazují se, protože byly intenzivně využívány)
* výhody: samy o sobě nejsou, strategie různých algoritmů se musí kombinovat
== Explain what is a working set of a process. ==
* množina stránek ve fyzické paměti, které patří určitému procesu, mění se s během procesu
* pokud je working set příliš velký, může běžet zároveň méně procesů, když příliš malý, musí se častěji spouštět swapování
== Explain what is a locality of reference and how it can be exploited to design or enhance a page replacement algorithm. ==
* předpokládá se, že se program v určitých částech bude stále „motat na místě jako vítr v bedně“, tedy je vhodné nejčastěji přistupované stránky za poslední dobu nebo naposledy navštěvované stránky nevyhazovat
* souvisí s cachováním i s tlb
== Explain what is thrashing and what causes it. Describe what can the operating system do to prevent thrashing and how can the system detect it. ==
* v případě že se working sets běžících procesů nevejdou do paměti, jedna stránka se vyhodí a začne se swapovat, jenže proces jemuž byla stránka vyhozena chce běžet a tak se začne swapovat stránka zpátky a tak pořád dokolečka – nakonec se jen swapuje a neudělá se nic
* řešení: vyswapuje se celý jeden proces (obětní beránek) a nepoběží vůbec, zvýšení RAM
* detekce: ponechá se rezerva, přes kterou už nebudu povolovat ukládání do paměti. Jakmile se překročí, začne se swapovat „dopředu“
== Explain the concept of memory mapped files. ==
* díky virtuální paměti máme možnost namapovat velký externí soubor do paměti a přistupovat k němu, jako by byl v paměti celý – urychluje to práci se soubory, protože se nepřistupuje k externím pamětem
* podstatné je, že pro práci s MMF není třeba volat systém, ale používají se běžné instrukce pro práci s pamětí
== Explain the priciple of the copy-on-write mechanism and provide an example of its application in an operating system. ==
* když více procesů chce sdílet stejná data (mapování souboru s flagem private například), OS je do paměti namapuje pouze jednou a označí je read-only a jakmile chce na stránku někdo psát, vyvolá se vyjímka, OS se ujme řízení a stránka je okopírována jinam do paměti, kde se do ní zapíše)
* používá se to například při sdílení stringů - jakmile pouze čteme stačí namapovat sdílenou paměť, jakmile chceme měnit, budeme to muset zkopírovat
= Allocation Within A Process =
== Identify where the following function relies on the virtual address space to store executable code, static data, heap and stack. ==
<strong>void *SafeAlloc (size_t iSize)</strong> // funkce = staticka data - v kodu, parametry na stacku
<strong>{</strong>
<strong> void *pResult = malloc (iSize);</strong> // dynamicky alokovane veci na heapu, lokalni prom. na stacku
<strong> if (pResult == NULL)</strong>
<strong> {</strong>
<strong> printf ("Failed to allocate %z bytes.\n", iSize);</strong> // static. data (string) v kodu
<strong> exit (ENOMEM);</strong>
<strong> }</strong>
<strong> return (pResult);</strong> // vysledek funkce na stack
<strong>}</strong>
== List four distinct types of content that reside in a virtual address space of a typical process . ==
* executable code – strojový kód v instrukcích procesoru
* static data – staticky alokované proměnné
* heap – halda, dynamicky alokovaná data
* stack – zásobník, pro ukládání návratových adres, argumentů procedur, registrů a lokálně alokovaných dat
a) Executable code.
contains the machine code instructions to be executed by the processor.
It is often write protected and shared among processes that use the same main program or the same shared libraries.
b) Static data.
contains the statically allocated variables to be used by the process.
c) Heap.
contains the dynamically allocated variables to be used by the process.
d) Stack.
contains the stack to be used by the process for storing items such as return addresses, procedure arguments, temporarily saved registers or locally allocated variables.
Kod a static data su nemenne a ich poloha je determinovana compilerom. Stack a heap su dynamicke a rastu oproti sebe (stack dole a heap smerom hore).
pozn. Vsechno jde menit, zalezi kam se zapise.
Jinak staticka data jsou i globalni promene, takze se meni pomerne casto.
Stack a heap rostou tim smerem, jak si to porgramator naprogramuje...
== Explain the advantages of segmentation over flat virtual memory address space. ==
* není třeba řešit rozložení heap X zásobník a jiné bloky paměti
* to co je důležíté je, že každý blok paměti (executable code, heap, stack..) bude jeden segmet
* to nám umožní i efektivně zjišťovat, zda například program nesahá „nad“ zásobník, při porovnávání adresy se segment registrem by se to zjistilo a proces který tak učinil by byl zastřelen
* No page faults -- whole segment is present at once -- only access violations need to be trapped
* No internal fragmentation -- segment size is customized to each process
* Easier to implement virtual OS
* per segment protection (ochrana pameti)
* snadnejsi sdileni dat (sdilim funkci/ ne naky stranky)
* virtual space
EDIT: Otázkou je porovnání proti ploché virtuální paměti. Ta také zaručuje separaci a bezpečnost. Heap vs. zásobník se řešit ani moc nemusí, když jsou proti sobě, tak prostě jakmile se potkají došla paměť. V tom segmentace nepomůže. Hlavní přínos segmentace oproti ploché virtuální paměti přichází ve chvíli, kdy mám více threadů v jednom adresním prostoru. Pak nelze moc hezky umístit zásobníky. Segmentace mi umožní je snadno přemisťovat na základě toho, jak rostou. A další výhodou je snadná realokace kódu. A pokud mám segmentaci over VAS, pak mám také výpadky stránek a nic mi to neusnadňuje, což dnes typicky mám. Záleží, jak byla otázka myšlena.
== Explain why random placement of allocated blocks in the virtual address space of a process can contribute to improved security. ==
* útočník nemůže dělat žádné závěry o tom, kde bude blok v paměti uložen, a to mu znesnadňuje „buffer overflow attack“
* útok spočívá v zápisu hodnoty delší než je alokovaná vstupní proměnná, čímž se přepíše jiná hodnota na zásobníku, která leží pod vstupní proměnnou. Při návratu z procedure je návratový kód vyzvedávaný ze zásobníku jiný a může směřovat na sadu škodlivých, útočníkem podsunutýc instrukcí
Prevencia proti exploitom - napr buffer overflow. S kazdym spustenim programu ho rozhadze po pamati randomne, teda sa neda predpokladat ze bude napr. buffer overflow fungovat.
== Explain what the processor stack is used for with typical compiled procedural programming languages. ==
* používá se pro uschovávání návratových adres, argumentů procedur a funkcí, dočasně uložených registrů procesoru a lokálně alokovaných proměnných
* k přístupu k zásobníku se používá stack pointer, regist obsažený v CPU
The process stack is typically used for return addresses, procedure arguments, temporarily saved registers and locally allocated variables. The processor typically contains a register that points to the top of the stack. This register is called the stack pointer and is implicitly used by machine code instructions that call a procedure, return from a procedure, store a data item on the stack and fetch a data item from the stack.
== For a contemporary processor, explain how the same machine instructions with the same arguments can access local variables and arguments of a procedure regardless of their absolute address in the virtual address space. Explain why this is important. ==
* příklad na Intel IA32
* instrukce push and pop – při volání procedury se sníží ESP register o velikost návratové adresy a ta se uloží
* k adresování lokálních proměnnch a argumentů se využívá EBP – base pointer. Ten je po volání procedury uložen na zásobník a zároveň je do EBP uložena hodnota ESP
* na zásobníku se vyhradí místo pro proměnné tím, že se k SP přičte tolik byte, kolik lokální proměnné zabírají. Proměnné se uloží nad ESP, argumenty se uloží pod ESP
* stack roste od větších k menším adresám, to má tu výhodu, že může být umístěn na konci paměťového prostoru. Nepoužívají se absolutní adresy do VAP, ale pouze relativní vzhledem EBP
The use of stack for procedure arguments and locally allocated variables relies on the fact that the arguments and the variables reside in a constant position relative to the top of the stack. The processor typically allows addressing data relative to the top of the stack, making it possible to use the same machine code instructions to access the procedure arguments and the locally allocated variables regardless on their absolute addresses in the virtual address space, as long as their addresses relative to the top of the stack do not change.
Importance: shared libraries.
== Explain what is the function of a heap allocator. ==
* určuje kam se umístí dynamicky alokovaná proměnná
* pracuje nad strukturou bloků s informacemi, které kusy haldy jsou prázdné a které volnépožadavky na alokátor – rychlost, malá režie, úspornost, a dodatečné fíčury (rezise, garbage collector, debugging, zero-fill, align)
The process heap is used for dynamically allocated variables. The heap is stored in one or several continuous blocks of memory within the virtual address space. These blocks include a data structure used to keep track of what parts of the blocks are used and what parts of the blocks are free. This data structure is managed by the heap allocator of the process.
In a sense, the heap allocator duplicates the function of the virtual memory manager, for they are both responsible for keeping track of blocks of memory. Typically, however, the blocks managed by the heap allocator are many, small, short-lived and aligned on cache boundaries, while the blocks managed by the virtual memory manager are few, large, long-lived and aligned on page boundaries. This distinction makes it possible to design the heap allocator so that it is better suited for managing blocks containing dynamically allocated variables than the virtual memory manager.
Usually, the heap allocator resides within a shared library used by the processes of the operating system. The kernel of the operating system has a separate heap allocator.
== Explain why the implementation of the heap allocator for user processes usually resides in user space rather than kernel space. ==
Od heap alokátoru se typicky očekává rychlost a volá se často, proto by bylo neefektivní na každé jeho zavolání ještě přikládat celou režii kolem syscallů. To je podle mne hlavní důvod.
Ještě bych dodal jeden menší důvod a to sice ten, že pokud si proces tu paměť poškodí, tak hrozí riziko, že poškodí i struktury toho mallocu a pokud by byl ten malloc puštěn jako privilegovaný, tak by mohl shodit kernel přístupem na špatnou adresu. Což by vyžadovalo neustále detekce toho, zda je heap konzistentní a pointery v interních strukturách nemíří ven, což se využívá asi spíše jen v debug módu, protože za runtimu to žere čas.
== Design an interface of a heap allocator. ==
* void *malloc(size_t size);
* void free(void *pointer);
void * malloc(size_t size);
void free(void *ptr);
size_t get_size(void *ptr);
== Explain the problems a heap allocator implementation must solve on multiprocessor hardware and sketch appropriate solutions. ==
* kdyby sloužil pro všechny procesory naráz, stal byse heap allocator úzkým hrdlem – při hledání volného místa by brzdil ostatní procesory
* řešením je hierarchický alokátor, který si udržuje „local free block pools“, tedy nabídku pro jednotlivé procesory s tím, že když na vrcholu hierarchie dojde místo, přelévají se z local do global free block poolu
Multiprocesorové systémy mají u alokátoru podobné problémy jako plánovace nad ready frontou, tedy prílią mnoho soubehu je zpomaluje. Proto se delají hierarchické alokátory, local free block pools, které se v prípade potreby prelévají do global free block poolu.
== Explain the rationale behind the Buddy Allocator and describe the function of the allocation algorithm. ==
* princip je půlení paměti – někdo požaduje blok paměť, kterou půlíme do té doby, než nemáme blok minimální možné velikosti, nebo velikosti větší než požadovaná paměť
* pro volné X obsazené bloky máme bitmapu – pro každou možnou velikost bloku jednu bitmapu, alternativní řešení je v hlavičce každého bloku uchovávat infromace o blocích a seznamech volných bloků
* při odalokování bloku se uvolněný se sousedním spojí (pokud je soused prázdný) a budou se spojovat dokud neuvolní celou paměť, nebo nenarazí na obsazený blok
* výhody – je jasně daná velikost bloků, přijatelná doba na alokování – dealokoání paměti
* nevýhoda – vysoká fragmentace, je daná pevnou sadou délek bloků
Pamět rozdělena na bloky o velikosti 2n. Bloky stejné velikosti v seznamu. Při přidělení zaokrouhlit na nejbliľąí 2n. Pokud není volný, rozątípnou se větąí bloky na přísluąné menąí velikosti. Při uvolnění paměti se slučují sousední bloky (buddy).
Klady - Rozdelenie aj zlucovanie rychle. Moze byt pouzity binary tree pre pamatanie si volnych a plnych blokov.
Zapory - internal (chcem 66kb - da mi 128kb) a external fragmentation (vela 64kb blokov roztrusenych ale ziadny 128kb blok).
== Explain the rationale behind the Slab Allocator and describe the function of the allocation algorithm. ==
* prinicp: nejčastěji se alokují malá data, trik je v tom, že nejčastěji používané objekty jsou již připravené na stránkách, to snižuje režii odstraněním alokace těchto objektů, jedna stránka tak obsahuje řadu objektů, čímž se šetří paměť a snižuje se interní fragmentace
* použití: unix
* terminologie: slab je kontejner na objekty a je tvořen několika stránkami, cache se skládají ze slabů, objekt je nejmenší jednotka alokace, nachází se ve slabu
EDIT: Lidsky řečeno, tak jak to mám v poznámkách. Pamatuje si objekty na kterých byly zavolány destruktory. A pokud budeme chtít new objekt stejného typu, tak nám ho rovnou vrátí, bez alokace a bez volání konstruktoru. Musí ale zajistit, že objekt byl ve stejném stavu jako po zavolání konstruktoru. Tohle mi přijde divné, ale nějak tak to popisoval.
== Describe what a heap allocator can do to reduce the overhead of the virtual memory manager. ==
* je výhodné, aby alokátor udržoval lokalitu, tedy aby nedávno alokované bloky umisťoval blízko sebe, protože budou pravděpodobně používány společně
* v případě přestránkování tedy mechanismus virtualizace nebude muset vyhazovat hodně stránek
* alokátor nejprve zkouší exact fit, v případě že to není možné zkusí rozdělit volný blok, ze kterého se přidělovalo naposledy
* tj. lepší mít naalokovaný bloky co nejvíc namačkaný u sebe, než roztroušený po paměti
Statistiky overheadu pro konkrétní aplikace uvádejí 4% pro best fist, 7% pro first fit na FIFO seznamu volných bloku, 50% pro first fit na LIFO seznamu volných bloku, 60% pro buddy system.
== Explain the function of a garbage collector. ==
* garbage collector sám uvolňuje paměť, kterou už žádný proces nevyužívá
* vyhazuje z paměti ty bloky, na které už nemáme ukazatel, ne ty bloky, které už nepotřebujeme
A garbage collector replaces the explicit freeing of blocks with an automatic freeing of blocks that are no longer used.
A garbage collector needs to recognize when a block on the heap is no longer used.
A garbage collectors determines whether a block is no longer used by determining
whether it is reachable, that is, whether a process can follow a chain of references from statically or locally allocated variables, called roots, to reach the block.
== Define precisely the conditions under which a memory block can be freed by a reference tracing garbage collector. ==
* dosažitelnost – pokud proces může sledovat retěz referení od staticky nebo lokálně alokovaných proměnných, tzv. roots tak, že dojde ke každému bloku (jsou dosažitelné referencí z call stacku, nebo globálních proměnných); funguje tranzitivita
What is reachable object:
# A distinguished set of objects are assumed to be reachable -- these are known as the roots. Typically, these include all the objects referenced from anywhere in the call stack (that is, all local variables and parameters in the functions currently being invoked), and any global variables.
# Anything referenced from a reachable object is itself reachable. This is referred to as transitivity.
Predpokladam ze vsetko non-reachable moze ist do /dev/null
== Describe the algorithm of a copying garbage collector. ==
* paměť je rozdělena na dvě části, při alokování se zaplňuje jen jedna (from space a to space), jakmile paměť dojde, jsou všechny dosažitelné proměnné kopírovány do druhé části, takto se neustále přelévá
* nevýhoda je potřeba velké souvislé části paměti ve chvíli, kdy garbage collector pracuje
Vsetko sa alokuje v oblasti 1. Ked sa zaplni, tzn. "root" mnozina objektov sa skopiruje do oblasti 2, a vsetky objekty, na ktore sa da dostat z root setu sa tam skopiruju tiez, a tak dalej az po vsetky dosiahnutelne objekty. Potom sa alokuje uz iba do oblasti 2 (v oblasti 1 nam zostali objekty, ktore boli nedosiahnutelne, cela oblast sa oznaci za cistu), a ked sa 2ka zaplni, zase to iste do oblasti 1.
== Describe the algorithm of a mark and sweep garbage collector. ==
* běh programu se zastaví, naleznou se všechny „živé“ objekty metodou dosažitelnosti a následně se uvolní všechny „neživé“
A "mark and sweep" garbage collector maintains a bit (or two) with each object to record whether it is white or black; the grey set is either maintained as a separate list or using another bit. As the reference tree is traversed during a collection cycle, these bits are manipulated by the collector to reflect the current state. The mark and sweep strategy has the advantage that, once the unreachable set is determined, either a moving or non-moving collection strategy can be pursued; this choice of strategy can even be made at runtime, as available memory permits. It has the disadvantage of "bloating" objects by a small amount.
== Describe the algorithm of a generational garbage collector. Assume knowledge of a basic copying garbage collector. ==
* pozorování: 1) mnoho objektů se stane odpadem krátce po svém vzniku, a 2) jen malé procento referencí ve „starších“ objektech ukazuje na objekty mladší
* garbage collector si paměť dělí na části - generace, objekty se začínají vytvářet jako nejmladší generace, v případě že se zaplní, všechny dosažitelné objekty se přesunou (označí) do starší generace
* intervaly úklidů jsou různé pro různé generace, typicky velmi krátké pro nejmladší generaci, strategie úklidu může být různá pro různé generace
* velmi pěkný článek o generational GC: [http://www.ibm.com/developerworks/java/library/j-jtp11253/ http://www.ibm.com/developerworks/java/library/j-jtp11253/]
It has been empirically observed that in many programs, the most recently created objects are also those most likely to quickly become unreachable (known as infant mortality or the generational hypothesis). A generational GC divides objects into generations and, on most cycles, will place only the objects of a subset of generations into the initial white (condemned) set. Furthermore, the runtime system maintains knowledge of when references cross generations by observing the creation and overwriting of references. When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree. If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects.
= Device Drivers =
== Popište obecnou architekturu ovladače zařízení a vysvětlete, jak tato architektura dovoluje zpracovávat současně asynchronní požadavky od hardware a synchronní požadavky od software. ==
Pro označení těchto dvou částí driveru se používají termíny bottom half (asynchronně volaná část driveru, která se stará převážně o požadavky hardware) a top half (synchronně volaná část driveru, která se stará převážně o požadavky software).
Tento problém se řeší použitím mechanismů, které dovolují naplánovat na později vykonání operací, které jsou součástí obsluhy přerušení od hardware (v Linuxu bottom half handlers a tasklets, ve Windows deferred procedure calls, v Solarisu pinned interrupt thread pools).
Bottom half a top half většinou pracují přes fronty bufferů (občas mohou nastat problémy se zamykáním - obsluha přerušení od hw může běžet ve stejné chvíli jako obsluha přerušení od sw)
== Popište obvyklý průběh obsluhy přerušení jako asynchronního požadavku na obsluhu hardware ovladačem zařízení. Průběh popište od okamžiku přerušení do okamžiku ukončení obsluhy. Předpokládejte obvyklou architekturu ovladače, kde spolu asynchronně a synchronně volané části ovladače komunikují přes sdílenou frontu požadavků. Každý krok popište tak, aby bylo zřejmé, kdo jsou jeho účastníci a kde získají informace potřebné pro vykonání daného kroku. ==
Windows kernel provides the option of postponing work done while servicing an interrupt through the deferred procedure call mechanism. The interrupt service routine can register a deferred procedure call, which gets executed later. The decision when to execute a deferred procedure call depends on the importance of the call, the depth of the queue and the rate of the interrupts.
== Popište obvyklý průběh systémového volání jako synchronního požadavku na obsluhu software ovladačem zařízení. Předpokládejte obvyklou architekturu ovladače, kde spolu asynchronně a synchronně volané části ovladače komunikují přes sdílenou frontu požadavků. Průběh popište od okamžiku volání do okamžiku ukončení obsluhy. Každý krok popište tak, aby bylo zřejmé, kdo jsou jeho účastníci a kde získají informace potřebné pro vykonání daného kroku. ==
Nejsem si úplně jistý, co tu chce všechno mít, ale tak nástřel:
Uživ. vlákno vyvolá obslužnou funkci přes rozhraní systémových volání (syscall, int 80h, ...). Tím vstoupí do režimu jádra a zde zavolá potřebnou rutinu na ovladači zařízení.Ta vloží požadavek do fronty požadavků (což případně může znamenat nějaké čekání na zámku, protože o frontu se perou jak další procesy, které něco chtějí, tak asynchronní obsluha zařízení, která z ní tahá požadavky po vyřízení předchozích). Poté se volající vlákno uspí a čeká na vyřízení svého požadavku. Po vyřízení ho asynchronní obsluha přerušení vzbudí, vlákno případně ještě někam přeuloží získaná data, vrátí se z rutiny ovladače a opustí režim jádra.
= Devices =
== List the features that a hardware device that represent a bus typically provides. ==
* sběrnice = dráty + řadič
* Parametry: datová šířka, kapacita, rychlost, technika přenosu - DMA
* In computer architecture, a bus is a subsystem that transfers data or power between computer components inside a computer or between computers and typically is controlled by device driver software. Unlike a point-to-point connection, a bus can logically connect several peripherals over the same set of wires. Each bus defines its set of connectors to physically plug devices, cards or cables together.
* Although busses are not devices in the usual sense, devices that represent busses are sometimes available to control selected features of the busses. Most notable are features for bus configuration.
* Common features of busses include listing devices connected to the bus and drivers associated witthe bus, matching drivers to devices, hotplugging devices, suspend- ing and resuming devices.
== List the features that a hardware clock device typically provides. ==
* Využití hodin, kalendár, plánování procesu v preemptivním multitaskingu, účtování strojového času, alarmy pro user procesy, watchdogs pro systém, profilování, rízení.
* Principy hodinového hardware, odvození od síte a od krystalového oscilátoru.
* Možné funkce hardware, tedy samotný čítač, one time counter, periodic counter,
kalendár.
* Využití hodinového hardware pro ruzné využití hodin - pro kalendár - pro plánování (ekvidistantní tiky, chce interrupt) - pro eventy (nastavování one time counteru je nejlepší, lze i jinak) - watchdog timer - profiling (bud statisticky koukat, kde je program, nebo presne merit).
== List the features that a hardware keyboard device typically provides. ==
Klasický příklad character device. Klávesnice bez řadiče. Klávesnice s řadičem, překódování kláves, type ahead buffer, přepínání focusu.
Keyboards are designed for the input of text and characters and also to control the operation of a computer.
== List the features that a hardware mouse device typically provides. ==
Computer-users usually utilize a mouse to control the motion of a cursor in two dimensions in a graphical user interface.
== List the features that a hardware terminal device with command interface typically provides. ==
Standardy řídících příkazů.
ANSI Escape Sequences třeba ESC [ <n> J (clear screen, 0 from cursor, 1 to cursor, 2 entire), ESC [ <line> ; <column> H (goto line and column), něco na barvy atd.
* nejspíš se tímhle myslí čtení command line přes serial port - občas jediná možnost jak ziskat nejaky vystup z ruznych fw
== List the features that a hardware terminal device with memory mapped interface typically provides. ==
Popis terminálů s memory mapped interface, znakové a grafické displeje, práce s video RAM, akcelerátory, hardwarová podpora kurzoru, kreslení apod.
* připojení klasického monitoru přes vga,...
== List the features that a hardware disk device typically provides. ==
A disk is a device that can read and write fixed length sectors. Various flavors of disks differ in how sectors are organized.
* skladuje fixed length sektory, data, aj po vypnuti kompu, poskytuje read, write.
* Možná by sem šlo započítat nějaký diskový řadič, který například umožňuje realizovat hw raid
== Explain the properties that a hardware disk interface must have to support hardware ordering of disk access requests. ==
Podporuju ma vacsina SCSI a SATA diskov, avsak vacsina ATA diskov tuto podporu nemaju.
Most versions of the ATA interface do not support issuing a new request to the disk before the previous request is completed, and therefore cannot implement any strategy to process the queue of requests. On the contrary, most versions of the SCSI and the SATA interfaces do support issuing a new request to the disk before the previous request is completed.
EDIT: Jaké parametry takový hardware musí mít? No musí umět přijímat nové requesty, zatímco nějaký zpracovává. Musí mít nějaké vnitřní buffery a reorder jednotku.
== Describe at least three strategies for ordering disk access requests. Evaluate how the strategies optimize the total time to execute the requests. ==
* The FIFO strategy of processing requests directs the disk to always service the first of the waiting requests. The strategy can suffer from excessive seeking Gross tracks.
* The Shortest Seek First strategy of processing requests directs the disk to service the request that has the shortest distance from the current position of the disk head. The strategy can suffer from letting too distant requests starve.
* The Bidirectional Elevator strategy of processing requests directs the disk to service the request that has the shortest distance from the current position of the disk head in the selected direction, which changes when no more requests in the selected direction are waiting. The strategy lets too distant requests starve at most two passes over the disk in both directions.
== Explain the role of a disk partition table. ==
Diskové oddíly slouží k rozdělení fyzického disku na logické oddíly, se kterými je možné nezávisle manipulovat.
Rozdělení fyzického disku na logické diskové oddíly bývá uvedeno v tzv. Partition Table, která se nachází na úplně prvním sektoru disku (tzv. Master boot record). Nejčastější verze této tabulky umožňuje pouze čtyři záznamy, ale v případě většího
počtu diskových oddílů na jednom médiu je možné v hlavní (primární) tabulce odkázat na takzvaný
rozšířený diskový oddíl (extendend partition), na jehož začátku se opět nachází MBR s další tabulkou,
ve které je uvedeno rozdělení extended partition na další oddíly.
<br>
Featurky:
* Instalaci více operačních systémů na jeden disk.
* Obcházet omezení souborového systému. Mnoho souborových systémů má omezení velikosti
logického oddílu, ať už ve smyslu limitu, nebo ve smyslu rostoucí neefektivity metadat
(například u NTFS rozsáhlejší MFT tabulka způsobuje, že přístup k souborům na jednom
velkém oddílu je pomalejší než na dvou menších).
* Použití různých souborových systémů nebo jejich parametrů pro různé účely.
* Ochranu izolací souborů.
V MBR je zavaděč, který rozhoduje, ze kterého oddílu bude následně zaveden operační systém.
[http://cs.wikipedia.org/wiki/Partition_Table zdroj]
== List the features that a network interface hardware device typically provides. ==
Hm, asi odešli data někam, scatter-gather, nějaké kontrolní součty
Scatter gather. Checksumming. Segmentation.
[http://en.wikipedia.org/wiki/Vectored_I/O scatter gather]
* Lepší síťové karty umí DMA, nebo má nemapovanou paměť (variace na stejné téma).
* Scatter/gather – Scatter – rozsekání a uložení na několik míst do paměti (TCP/IP hlavičky); Gather –
„vysosnutí― dat z několika míst paměti a slepení dohromady.
* Nabízí služby typu odešli/přijmi data; Umí odpovídat na PING. Počítá kontrolní součty
= Abstractions And Operations =
== Popište obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací čtení a zápisu. Funkce rozhraní uvedťe včetně argumentů a sémantiky. ==
* int open (const char *pathname, int flags);
* off_t lseek (int fildes, off_t offset, int whence);
* ssize_t read (int fd, void *buf, size_t count);
* ssize_t write (int fd, const void *buf, size_t count);
* int close (int fd);
* otevreni int open (const char *pathname, int flags ,{mode_t mode});
* otevreni + vytvoreni int creat (const char *pathname, mode_t mode);
O_RDONLY, O_WRONLY, O_RDWR.
* zavreni int close (int fd);
* nastaveni pozice off_t lseek (int fildes, off_t offset, int whence);
SEEK_SET, SEEK_CUR nebo SEEK_END,
* zapis ssize_t write (int fd, const void *buf, size_t count);
* cteni ssize_t read (int fd, void *buf, size_t count);
== Vysvětlete, proč obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací čtení a zápisu odděluje operace otevření a zavření souboru a operaci nastavení aktuální pozice v souboru od vlastních operací čtení a zápisu. ==
Důvody pro pětici operací jsou možnost odstranit při běžném způsobu práce se soubory opakování operací:
* jako je nalezení pozice na disku ze jména souboru a pozice v souboru
* možnost spojit otevírání souboru s dalšími operacemi jako je zamykání nebo kontrola oprávnění.
* Důvodem pro dvojici operací je možnost implementovat file systém bezestavově, což přináší výhody v distribuovaných systémech.
== Popište obvyklé rozhraní operačního systému pro přístup k souborům pomocí operací mapování do paměti. Funkce rozhraní uvedťe včetně argumentů a sémantiky. ==
* void *mmap (void *start, size_t length, int protection, int flags, int fd, off_t offset);
* int munmap (void *start, size_t length);
* void *mremap (void *old_address, size_t old_size, size_t new_size, unsigned long flags);
* OS da moznost spojit stranky s konkretnimi daty na disku.
* void *mmap (void *start, size_t length,int prot, int flags, int fd, off_t offset);
ochrana dat PROT_READ, PROT_WRITE, PROT_EXEC;
flags MAP_SHARED, MAP_PRIVATE (copy-on-write), MAP_FIXED
*int munmap (void *start, size_t length);
== Popište obvyklé rozhraní operačního systému pro práci s adresáři. Funkce rozhraní uvedťe včetně argumentů a sémantiky. ==
* DIR *opendir (const char *name);
* int closedir (DIR *dir);
* struct dirent *readdir (DIR *dir);
* …
* Základní operace na adresářích jsou otevření a zavření a čtení či prohledávání obsahu. Pro zápis obsahu jsou zvláštní funkce, které vytvářejí, přejmenovávají a mažou adresáře a soubory a nastavují jejich atributy, aby aplikace nemohly poškodit strukturu adresáře.
* DIR *opendir (const char *name);
* int closedir (DIR *dir);
* struct dirent *readdir (DIR *dir);
* int scandir (const char *dir, struct dirent ***namelist, int (*select) (const struct dirent *), int (*compar) (const struct dirent **,const struct dirent **));
select - ktere polozky
compar - jak je usporadat
dirent obsahuje 0 terminated jmeno a inode souboru
== Popište obvyklé rozhraní operačního systému pro zamykání souborů. Funkce rozhraní uvedťe včetně argumentů a sémantiky. ==
int flock(int fd, int operation);
pomoci fcntl v UNIXU, zada se offset, delka zamykaneho kusu a rezim zamykani(shared, exclusive).
musi se pamatovat seznam zamku na souboru
int fcntl(int fd,int cmd,struct flock *lock);
== Vysvětlete rozdíl mezi advisory a mandatory zámky pro zamykání souborů. Vysvětlete, proč tyto druhy zámků existují. ==
Unix rozlišuje advisory a mandatory locking. Od začátku implementované jsou pouze advisory locks, totiž zámky, které se projeví pouze pokud se na ně proces zeptá. To samozřejmě není příliš bezpečné, a tak se doplnily ještě mandatory locks, které kontroluje kernel. Aby mandatory locks neblokovaly ve chvílích, kdy to stávající aplikace nečekaly, řeklo se, že budou automaticky nasazené na soubory s nastaveným group ID bitem a shozeným group execute bitem.
* advisory : to jsou zamky, ktere se projevi pouze pokud se na ne proces zepta
* mandatory: pro bezpecnost, kontroluje je kernel maji slozitejsi semantiku,mohou vest k deadlocku (NFS)
= File Subsystem Internals =
== Vysvětlete hlediska ovlivňující volbu velikosti bloků jako alokačních jednotek na disku. ==
Přidělování volného místa, problém velikosti bloků. Hlediska pro větší bloky, rychlost, malá režie, hlediska pro menší bloky, malá fragmentace.
Soubory se ukládají na disk po blocích. Disky jsou organizovány po sektorech
Velké bloky
rychlejší práce s diskem,nebezpečí velké vnitřní fragmentace,průměrná velikost souboru ?1500B
Malé bloky
pomalejší práce s diskem,větší režie na udržení informace o volných blocích
== Uvedťe, jakými způsoby lze na disku ukládat informaci o blocích, ve kterých jsou umístěna data souborů. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnotťe. ==
Přechod z pásek na disky, první nápad se sekvenčním ukládáním souborů. Má to dvě výhody, totiž rychlost a malou režii. Nevýhodou je potřeba znát předem délku souboru a pochopitelně fragmentace.
První nápad jak tohle odstranit je udělat linked list. C64 měl tohle na floppy, nevýhody jsou zřejmé. Extrémně pomalý random access, velikost bloků není mocnina dvou, špatně se maže a tak.
Další modifikace je nechat linked list, ale vytáhnout ho z bloků a dát do tabulky. Typické řešení MS-DOSu. Nevýhodné to začne být, když se celá tahle tabulka nevejde do paměti, lidi napadlo mít jí po kouskách u souborů, výsledek je třeba CP/M nebo UNIX. Co dělat když je tahle tabulka moc velká, CP/M přidává lineárně další bloky, UNIX stromově větví I-nodes.
* souvisla alokace - souvisly sled bloku, informace ulozeni se sklada pouze z cisla prvniho bloku
+ lepsi prace s diskem
- hledani volneho mista, zvetsovani velikosti
* spojovana alokace - FAT
* indexova alokace - inode
== Uvedťe, jakými způsoby lze na disku ukládat strukturu adresářů. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnotťe. ==
Triviální případ jednoúrovňového adresáře, koncept ROOTu v MS-DOSu. Hierarchické adresáře, ukládání podadresářů do nadřazených adresářů. DOSácká klasika, totéž u UNIXu. Jak do adresáře zadělat linky, koncept hard linku a symbolic linku.
Záznamy pevné velikosti
* FAT - Spojový seznam
- delší jména - nutnost specialnich skrytych souboru
- pomalé hledání
* B-stromy
- rychlé hledání
- Win NT
== Vysvětlete rozdíl mezi hard linkem a symbolic linkem. Porovnejte výhody a nevýhody obou typů linků. ==
A symbolic link (often shortened to symlink and also known as a soft link) consists of a special type of file that serves as a reference to another file or directory. A hard link is a reference, or pointer, to physical data on a storage volume.
hard link = is a reference, or pointer, to physical data on a storage volume.
more than one name can be associated with the same data.
can only refer to data that exists on the same file system.
simbolic link = reference to another file or directory
does not point directly to data, but merely contains a symbolic path which an operating system uses to identify a hard link (or another symbolic link)
can use symbolic links to refer to files even on other mounted file systems
The term orphan refers to a symbolic link whose target does not exist.
Výhody a nevýhody hardlinku, rychlost, špatné mazání, neprekrocí hranici file systému.
Symbolický link, totéž. Drobnost pri zálohování a kopírování souboru, nutnost
služby rozeznávající link od normálního souboru.
* hard link = Odkaz na fyzická data.
* symbolic link = Soubor obsahující jméno souboru na které odkazuje.
* Hard link nejde vytvářet mezi FS, soft linku to nevadí. Používání hard linků zvýší režii při mazání.
== Uvedťe, jakými způsoby lze na disku ukládat informaci o volných blocích. Jednotlivé způsoby ilustrujte na existujících systémech souborů a zhodnotťe. ==
Evidence volného místa, seznam volných bloků a bitmapy. Funkce bitmap je jasná, seznam volných bloků se zdá být nevýhodný, až na schopnost mít v paměti jen malou část tablice a přesto uspokojovat velký počet dotazů na volné bloky, a možnost ukládání právě ve volném místě. Možnost využití seznamu alá FAT. Evidence vadných bloků, vadný soubor, označení vadných bloků.
* Bitmapa - HPFS, EXT
** bloky pevné velikosti
* Spojový seznam volných bloků - FAT
** seznam volných bloků
** spojování uvolněného bloku se sousedy
EDIT: Spojový seznam volných clusterů obsahuje až exFAT, původní verze mají to, že se musí projít FAT tabulka a na každý záznam se kouknout, jestli je volný, tedy je tam nula. Více na anglické wiki.
== Popište způsob uložení informace o umístění dat souborů v systému souborů FAT. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
* boot sektor s rozmery filesystému, za ním dvakrát FAT, za ní root directory,za ním data area.
* Adresárová položka obsahuje name, attributes, first cluster. Bad clusters mají extra známku ve FAT.
* FAT tabulka obsahuje spojovy seznam pouzitych clusteru, polozka fat muze obsahovat priznak 0 = volny, cislo dalsiho clusteru pripadne oznaceni souboru jako vadny, konec souboru ..
* minusy
** slozitost operaci (velka rezie na velke clustery)
** chybi indexy adresaru - linearni prochazeni
** metadata jsou fyzicky daleko od dat
** fragmentace (vzhedem k clusterum)
** FAT(je velká, nelze z ní snadno vytáhnout data týkající se jednoho souboru)
** krátká jména souboru, málo atributu, možnost fragmentace adresáru vymazanými jmény
* plusy
** snadna implementace
== Popište způsob uložení informace o struktuře adresářů v systému souborů FAT. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
to same co 132,
* adresar je soubor, co ma nastaveny bit
* obsahuje directory entries - info o souborech, ktere sam ma
** nazev
** typ(adresar/soubor)
** cislo prvniho bloku, kde jsou data
== Popište způsob uložení informace o umístění volných bloků v systému souborů FAT. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
na zacatku jmena 0x00 prazdne, 0xE5 smazane
ve FAT tabulce hodnota 0 - prázdný cluster
pro nalezení volného bloku se musí v nejhorším případě projít celá FAT tabulka
* pomale vyhledavani volneho mista -> prochazim spoustu clusteru (mohou byt i jinde na disku)
* pri mazani souboru musim projit vsechny clustery a zmenit flag (mohou byt i jinde na disku)
vs. bitmapa - je to na jednom miste
== Popište způsob uložení informace o umístění dat souborů v systému souborů EXT2. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
* A file is represented by an inode. The inode contains information such as file type, access rights, owners, timestamps, size, and the allocation map. The allocation map contains pointers to direct blocks, a pointer to a single level indirect block, which contains pointers to direct blocks, a pointer to a double level indirect block, which contains pointers to single level indirect blocks, and a pointer to a triple level indirect block, which contains pointers to double level indirect blocks. By default, 12 pointers to direct blocks reside in the inode, 1024 pointers to indirect blocks reside in a block.
* Some versions of the filesystem could store file tails in block fragments. The inode structure therefore contains block fragment related fields, which, however, are not used in the current filesystem implementations.
* A quick overview of other features includes a bad block map kept in reserved inode
1, an administrator space reservation.
* Pro odhad, v Linuxu je na 8GB partition celkem 1M I-nodes, z toho jsou pro bežné
soubory tak 4% použitých, každý blok má 130MB. Extra atributy se dají císt a menit pres lsattr a chattr, patrí mezi ne IMM (immutable), APP (append only), SYNC (synchronous update), COMPRESS, UNDELETE, SAFEDEL (tyto tri ale kernel ignoruje ?).
* Journalling mode for data is either writeback, ordered, or journal. Writeback means data are not journalled. Ordered means data are written to normal location before corresponding metadata are journalled. Journal means both data and metadata are journalled. Journalling is done to a special file.
Struktura fs:
* Boot sector, poté je disk rozdělen do groups; V každé groups jsou: FBB (free block bitmap):FIB (free inode bitmap), IN (tabulka Inodů): data.
* Soubory reprezentují INody, pro každý soubor existuje právě jeden INode. Na začátku inodu se nachází různé atributy jako typ, práva, vlastník, časové razítko…
* Za nimi se nachází odkazy do datové části. Odkazy až na poslední tři jsou přímo na data;
** odkaz (n-2). je odkaz na tabulku odkazů,
** (n-1). je odkaz na tabulku, kde je kazdy odkaz odkaz na tabulku
** poslední je tříúrovňový.
* Mapa vadných bloků je udržována v inodu číslo 11.
struct ext2_inode {
__u16 i_mode; /* File mode */
__u16 i_uid; /* Owner ID */
__u32 i_size; /* Size in bytes */
__u32 i_atime; /* Access time */
__u32 i_ctime; /* Creation time */
__u32 i_mtime; /* Modification time */
__u32 i_dtime; /* Deletion Time */
__u16 i_gid; /* Group ID */
__u16 i_links_count; /* Links count */
__u32 i_blocks; /* Blocks count */
__u32 i_flags; /* File flags */
__u32 i_block [EXT2_N_BLOCKS]; /* Ptrs to blocks */
__u32 i_version; /* File version for NFS */
__u32 i_file_acl; /* File ACL */
__u32 i_dir_acl; /* Directory ACL */
__u32 i_faddr; /* Fragment address */
__u8 l_i_frag; /* Fragment number */
__u8 l_i_fsize; /* Fragment size */
};
== Popište způsob uložení informace o struktuře adresářů v systému souborů EXT2. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Directories are stored either unsorted, or with hash tree indices.
struct ext2_dir_entry_2 {
__u32 inode; /* Inode number */
__u16 rec_len; /* Directory entry length */
__u8 name_len; /* Name length */
__u8 file_type; /* File type */
char name [EXT2_NAME_LEN]; /* File name */
};
== Popište způsob uložení informace o umístění volných bloků v systému souborů EXT2. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Free space is allocated by blocks. A free block bitmap is used to keep track of free blocks.
Bitmapa volného místa per group. Je to blíže k datům, ale zase to není "spojitý"
== Popište způsob uložení informace o umístění dat souborů v systému souborů NTFS. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Na disku neleží nic než soubory, informace o nich jsou uloženy v MFT aneb Master File Table. Každý soubor je jednoznačně identifikován indexem do MFT, MFT sama je také soubor s indexem 0, další význačné indexy jsou 1 pro MFT mirror, 2 pro transaction log, 3 pro root directory, 4 pro allocation bitmap, 5 pro bootstrap, 6 for bad cluster file atd.
Na zacátku disku je jen bootsektor s rozmery disku a pointerem na MFT, jeho kopie je uložena ješte kdesi na (konci ?) partition. Celý zbytek disku se adresuje po clusterech, které jsou podobne jako u FAT mocninné násobky sektor u. Na disku neleží nic než soubory, informace o nich jsou uloženy v MFT aneb Master File Table. Každý soubor je jednoznacne identifikován indexem do MFT, MFT sama je také soubor s indexem 0, další význacné indexy jsou 1 pro MFT mirror, 2 pro transaction log, 3 pro root directory, 4 pro allocation bitmap, 5 pro bootstrap, 6 for bad cluster file atd.
Nekteré ze skrytých souboru lze vypsat, chodí príkazy dir /ah $bitmap, dir /ah
$badclus, dir /ah $mftmirr atd. (ovšem krom vypsání v root adresári už tuším nic
nejde). Ve Windows 2000 už zdá se nejde ani tohle.
Každý soubor je set of attributes, jeden z atributu je default, to je data stream. Každý záznam v MFT obsahuje magic, update sequence (podobná NFS, je potreba aby pri reuse záznamu bylo možné poznat staré reference), reference count, flags, potenciálne pointer na base file record pokud toto je extension file record (když se vše nevejde do base file recordu). Následují file attributes, u nich záznam obsahuje jméno, typ a data, data mohou být bud resident, v tom prípade následují prímo v záznamu, nebo non-resident, v tom prípade následuje v záznamu run list, což je sekvence bloku clusteru podobne jako u HPFS.
Adresáre jsou uložené jako soubory, jejichž obsah je B strom s referencemi na obsažené soubory.
Mírne zjednodušeno. Nejvetší nevýhodou se zdá být fragmentace. To prevent fragmentation of MFT, NTFS makes sure a free area called MFT zone exists after MFT. Each time the disk becomes full, MFT zone is halved.
== Popište způsob uložení informace o struktuře adresářů v systému souborů NTFS. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Adresáře jsou uložené jako soubory, jejichž obsah je B strom s referencemi na obsažené soubory.
Na zacátku disku je jen bootsektor s rozmery disku a pointerem na MFT, jeho kopie je uložena ješte kdesi na (konci ?) partition. Celý zbytek disku se adresuje po clusterech, které jsou podobne jako u FAT mocninné násobky sektor u. Na disku neleží nic než soubory, informace o nich jsou uloženy v MFT aneb Master File Table. Každý soubor je jednoznacne identifikován indexem do MFT, MFT sama je také soubor s indexem 0, další význacné indexy jsou 1 pro MFT mirror, 2 pro transaction log, 3 pro root directory, 4 pro allocation bitmap, 5 pro bootstrap, 6 for bad cluster file atd.
Nekteré ze skrytých souboru lze vypsat, chodí príkazy dir /ah $bitmap, dir /ah
$badclus, dir /ah $mftmirr atd. (ovšem krom vypsání v root adresári už tuším nic
nejde). Ve Windows 2000 už zdá se nejde ani tohle.
Každý soubor je set of attributes, jeden z atributu je default, to je data stream. Každý záznam v MFT obsahuje magic, update sequence (podobná NFS, je potreba aby pri reuse záznamu bylo možné poznat staré reference), reference count, flags, potenciálne pointer na base file record pokud toto je extension file record (když se vše nevejde do base file recordu). Následují file attributes, u nich záznam obsahuje jméno, typ a data, data mohou být bud resident, v tom prípade následují prímo v záznamu, nebo non-resident, v tom prípade následuje v záznamu run list, což je sekvence bloku clusteru podobne jako u HPFS.
Adresáre jsou uložené jako soubory, jejichž obsah je B strom s referencemi na obsažené soubory.
Mírne zjednodušeno. Nejvetší nevýhodou se zdá být fragmentace. To prevent fragmentation of MFT, NTFS makes sure a free area called MFT zone exists after MFT. Each time the disk becomes full, MFT zone is halved.
== Popište způsob uložení informace o umístění dat souborů v systému souborů na CD. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Standard ISO9660 a ECMA119. Disk rozdelen na sektory zpravidla 2048 bytes, prvních 16 sektoru prázdných pro bootstrap loader. Zbytek disku je popsán sekvencí volume descriptors, jeden per sektor, neduležitejší je Primary Volume Descriptor s adresou root directory, path table a dalšími zbytecnostmi (copyright, abstract, bibinfo). Adresáre jsou usual stuff, name of 30 chars max, attributes, soubor je udán pocátecním sektorem a délkou (teoreticky je možné uvést víc adresárových položek pro soubor z více fragmentu, ale nepoužívá se, stejne jako se zdá se nepoužívá interleaving).
Jedním zajímavým detailem v ISO9660 jsou path tables. Aby se adresáre nemusely prohledávat item by item, uloží se do path table serazený (podle hloubky a dalších kritérií) seznam všech cest na disku, pro každou cestu obsahuje path table sektor príslušného adresáre a jeho parenta.
Podpora multisession disků: Deskriptor obsahuje navíc políčko verze, ten s nejvyšším číslem verze
vyhrává. Deskriptory můžu ukládat na víc míst (například na konec).
The standard imposes a number of weird limits on the file system structure, such as maximum directory nesting depth of 8, only capital letters, digits and underscores in file names, no extensions in directory names, etc. For this reason, extensions such as Joliet and Rock Ridge have appeared.
== Popište způsob uložení informace o struktuře adresářů v systému souborů na CD. Uvedťe přednosti a nedostatky tohoto způsobu uložení informace. ==
Aby se adresáře nemusely prohledávat item by item, uloží se do path table seřazený (podle hloubky a dalších kritérií) seznam všech cest na disku, pro každou cestu obsahuje path table sektor příslušného adresáře a jeho parenta.
The standard imposes a number of weird limits on the file system structure, such as maximum directory nesting depth of 8, only capital letters, digits and underscores in file names, no extensions in directory names, etc. For this reason, extensions such as Joliet and Rock Ridge have appeared.
Standard ISO9660 a ECMA119. Disk rozdelen na sektory zpravidla 2048 bytes, prvních 16 sektoru prázdných pro bootstrap loader. Zbytek disku je popsán sekvencí volume descriptors, jeden per sektor, neduležitejší je Primary Volume
Descriptor s adresou root directory, path table a dalšími zbytecnostmi (copyright, abstract, bibinfo). Adresáre jsou usual stuff, name of 30 chars max, attributes, soubor je udán pocátecním sektorem a délkou (teoreticky je možné uvést víc adresárových položek pro soubor z více fragmentu, ale nepoužívá se, stejne jako se zdá se nepoužívá interleaving).
Jedním zajímavým detailem v ISO9660 jsou path tables. Aby se adresáre nemusely prohledávat item by item, uloží se do path table serazený (podle hloubky a dalších kritérií) seznam všech cest na disku, pro každou cestu obsahuje path table sektor príslušného adresáre a jeho parenta.
The standard imposes a number of weird limits on the file system structure, such as maximum directory nesting depth of 8, only capital letters, digits and underscores in file names, no extensions in directory names, etc. For this reason, extensions such as Joliet and Rock Ridge have appeared.
== Vysvětlete princip integrace více systémů souborů v operačním systému do jednoho prostoru jmen. ==
Provedení v Linuxu je přímočaré. Při volání open se systém podívá na začátek jména souboru a podle toho zda je absolutní či relativní vezme dentry bud’ root directory nebo current directory. Pak už se jen postupně parsuje jméno a každá jeho část se zkusí najít v dentry cache, pokud tam není, tak se použije lookup funkce parent dentry.
Do tohoto mechanizmu celkem přímočaře zapadá i mounting. Pokud se do adresáře něco namountuje, jeho dentry bude obsahovat pointer na root dentry namontovaného file systému. Tento dentry zústane díky busy locku vždy v dentry cache. Při parsování cesty se pak u každého dentry ještě kontroluje, zda nemá mounted file systém, pokud ano, vezme se jeho root dentry.
Zmínit integraci více file systému do kernelu, princip mount points pro poskytnutí jednoho prostoru jmen. Stackable file systems pres V-nodes.
DOC:
Provedení v Linuxu je přímočaré. Při volání open se systém podívá na začátek jména souboru a podle toho zda je absolutní či relativní vezme dentry bud root directory nebo current directory.
Pak už se jen postupně parsuje jméno a každá jeho část se zkusí najít v dentry cache, pokud tam není, tak se použije lookup funkce parent dentry.
Do tohoto mechanizmu celkem přímočaře zapadá i mounting. Pokud se do adresáře něco namountuje, jeho dentry bude obsahovat pointer na root dentry namontovaného file systému. Tento dentry zústane díky busy locku vždy v dentry cache. Při parsování cesty se pak u každého dentry ještě kontroluje, zda nemá mounted file systém, pokud ano, vezme se jeho root dentry.
Virtual File System (rozhraní, reálný OS implementuje toto rozhraní). => podpora více file systémů
pod jedním Operačním Systémem.
Ve Windows může mít každý logický disk svůj FS.
Provedení v Linuxu je přímočaré. Při volání open se systém podívá na začátek jména souboru a podle
toho zda je absolutní či relativní vezme dentry bud’ root directory nebo current directory. Pak už se jen
postupně parsuje jméno a každá jeho část se zkusí najít v dentry cache, pokud tam není, tak se použije
lookup funkce parent dentry.
Do tohoto mechanizmu celkem přímočaře zapadá i mounting. Pokud se do adresáře něco namountuje,
jeho dentry bude obsahovat pointer na root dentry namontovaného file systému. Tento dentry zůstane
díky busy locku (caused by bus locking and cache invalidation when test-and-set operation needs to
access memory atomically) vždy v dentry cache. Při parsování cesty se pak u každého dentry ještě
kontroluje, zda nemá mounted file systém, pokud ano, vezme se jeho root dentry. Navíc mám
negativní dentry – tenhle soubor neexistuje
Stackable FS (Union FS)
Obsahuje disjunktní podstromy (pro každý FS), celkem složí celý strom. Vrstvový model.
= Network Subsystem =
== Popište socket jako abstrakci rozhraní operačního systému pro přístup k síti podle Berkeley sockets. Uvedťe základní funkce tohoto rozhraní včetně hlavních argumentů a sémantiky. ==
The Berkeley socket interface centers around the concept of a socket as an object that facilitates communication. The socket can be bound to a local address and connected to a remote address. Data can be sent and received over a socket.
* int socket (int domain, int type, int protocol);
Domain specifies socket protocol class.
Type specifies socket semantics.
Protocol specifies socket protokol.
The socket call creates the socket object. An error is returned if the combination of class, type, protocol is not supported.
* int bind (int sockfd, struct sockaddr *my_addr, socklen_t addrlen);
The bind call binds the socket to a given local address. The binding is typically necessary to tell the socket what local address to listen on for incoming connections.
* int listen (int sockfd, int backlog);
The listen call tells the socket to listen for incoming connections and sets the length of the incoming connection queue.
* int accept (int sockfd, struct sockaddr *addr, socklen_t *addrlen);
The accept call accepts an incoming connection on a listening socket that is SOCK_STREAM, SOCK_RDM, SOCK_SEQPACKET. The function returns a new socket and an address that the new socket is connected to and keeps the original socket untouched.
* int connect (int sockfd, const struct sockaddr *serv_addr, socklen_t addrlen);
The connect call connects a socket that is SOCK_STREAM, SOCK_RDM, SOCK_SEQPACKET to a remote address, and sets a remote address of the socket otherwise.
* ssize_t send (int sockfd, const void *buf, size_t len, int flags);
* ssize_t sendto (int sockfd, const void *buf, size_t len, int flags, const struct sockaddr *to, socklen_t tolen);
* ssize_t sendmsg (int sockfd, const struct msghdr *msg, int flags);
The send family of calls sends data over a socket. Either the socket is connected or the remote address is specified. The write call can also be used but the flags cannot be specified in that case.
* ssize_t recv (int sockfd, void *buf, size_t len, int flags);
* ssize_t recvfrom (int sockfd, void *buf, size_t len, int flags,
* struct sockaddr *from, socklen_t *fromlen);
* ssize_t recvmsg (int sockfd, struct msghdr *msg, int flags);
The recv family of calls receives data over a socket. The read call can also be used but the flags cannot be specified in that case.
* int select (int setsize, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
* int poll (struct pollfd *ufds, unsigned int nfds, int timeout);
The select call is used to wait for data on several sockets at the same time. The arguments are sets of file descriptors, usually implemented as bitmaps. The file descriptors in readfds are waited for until a read would not block, the file descriptors in writefds are waited for until a write would not block, the file descriptors in exceptfds are waited for until an exceptional condition occurs. The call returns the number of file descriptors that meet the condition of the wait. The poll call makes it possible to more precisely distinguish what events to wait for.
* int getsockopt (int sockfd, int level, int optname, void *optval, socklen_t *optlen);
* int setsockopt (int sockfd, int level, int optname, const void *optval, socklen_t optlen);
== Vysvětlete účel funkce select v rozhraní operačního systému pro přístup k síti podle Berkeley sockets. ==
viz predchozi otazka
== Vysvětlete, k čemu slouží sockety v doméně PF_UNIX . ==
Unix sockets represent a class of sockets used for local communication between processes.
The sockets are represented by a file name or an abstract socket name.
* prostě socket na lokalnim stroji
== Vysvětlete, k čemu slouží sockety v doméně PF_NETLINK . ==
Netlink sockets represent a class of sockets used for communication between processes
and kernel. The sockets are represented by a netlink family that is specified in
place of protocol when creating the socket.
* zvláštní druh komunikace přes sockety mezi kernelem a procesy (co vím tak pouze na linuxu)
== Popište princip funkce mechanismu vzdáleného volání procedur a načrtněte obvyklou architekturu jeho implementace. ==
RPC) is a technology that allows a computer program to cause a subroutine or procedure to exekute in another address space (commonly on another computer on a shared network) without the programmer explicitly coding the details for this remote interaction.
RPC is an easy and popular paradigm for implementing the client-server model of distributed computing. An RPC is initiated by the client sending a request message to a known remote server in order to execute a specified procedure using supplied parameters. A response is returned to the client where the application continues along with its process.
== Vysvětlete, proč při implementaci přístupu k síti v operačním systému může kopírování přenášených dat být problém. Zhodnotťe míru tohoto problému a uvedťe, jakým způsobem jej lze odstranit. ==
The individual modules that process packets may need to add headers or footers to the data, which may prompt a need for moving the data to make room for the headers or footers. With top desktop systems moving data in memory in hundreds to thousands of MB per second and top network systems moving data in wires in thousands of MB per second, even a small amount of data copying
may be a problem.
Pitfalls can be sidestepped by using smart hardware.
To avoid data copying, the individual modules that process packets keep data in the sk_buff structure. The structure reserves space before and after data so that headers or footers can be addend without data copying.
ztrata vykonu pri mnoha modulech pracujicich s packety:
jednotlive moduly mohou zpusobit presun dat pri pridavani headers a footers
reseni smart hardware : linux - data ve sk_buff structure, ktera ma misto pred a za daty pro pridavani headers a footers bez nutnosti kopirovani.
Úplně ideální je mít síťovku, která podporuje scatter / gather a DMA, pak se nemusí takovýhle hacky s poloprázdnýma strukturama provádět
== Vysvětlete roli filtrování paketů v operačním systému. Uvedťe příklady kritérií, podle kterých mohou být pakety filtrovány a příklady akcí, které mohou filtry s pakety vykonávat. ==
The networking layer must decide what to do with each packet. A packet can be delivered to a local recipient, forwarded to a remote recipient, or even dropped. This mechanism is configurable to avoid abuse of default rules for delivering, forwarding, discarding.
Each point contains a sequence of rules. A rule can classify packets using information from packet header (source and destination address, protocol ...) or from packet processing (source and destination interface ...). Modules that classify packets can be added, available modules include file conditions, connection marks, connection rates, connection state, security context, random and others.
Actions:
ACCEPT means process packet, DROP means discard, QUEUE means queue for user space application to decide, RETURN means continue previous chain.
sitova vrstva OS rozhoduje co s pakety.
pakety muze predat lokalnimu prijemci, forwardnout dal, nebo zahodit.
paket normalni(filter), pro novou komunikaci(net), potrebujici specialni modifikaci(mangle)
* maškaráda pro NATku postrouting
* maškaráda pro port forwarding prerouting
* spousta rozšíření - např filtrování podle uid uživatele
* ...
== Vysvětlete roli plánovače paketů v operačním systému. ==
Given that neither the network capacity nor the queues capacity is infinite, it is possible to overload the network or the queues with packets. To prevent that, packet policing is used to discard input packets and packet scheduling is used to time output packets.
casuje output packety (aby se predeslo preplneni front a site)
== Popište Token Bucket algoritmus pro plánování paketů a vysvětlete, co je jeho cílem. ==
The token bucket algorithm is used when single flow needs to observe bandwidth. The flow is assigned a bucket for tokens with a defined maximum capacity. Tokens are added regularly and removed when data is sent, no tokens are added to a full bucket, no data can be sent when no tokens are available. The speed of adding tokens determines bandwidth limit. The capacity of token bucket determines fluctuation limit.
Kdyz mam jeden tok na obslouzeni pasma. Tok je jako bucket pevne velikost. Data jsou pridavany pravidelne a odebirany. Kdyz nejake prijdou a bucket je plny, nic se neprida. Nic se neposle, kdyz je bucket prazdny. Rychlost pridavani zavisi na sirce pasma a kapacita bucketu na limitu proudu :-)
HTB
* používá se to na traffic shaping (pouze tcp) podle: portů zdrojové adresy, atd
* dá se nastavit i min průtok - tj. tenhle průtok bude vždycky zajištěný a nad tím můžeme dostat něco z kbelíku
Volný překlad anglické wiki:
* Algoritmus funguje tak, že každou 1/r s se podívá, kolik má ve frontě tokenů. Pokud jich je méně než b, tak jeden přidá.
* Když přijde požadavek odeslání zprávy o n bitech, tak se podívá do fronty tokenů. Pokud jich je více rovno n, tak jich n odstraní z fronty a zprávu odešle.
* Pokud tokenů ve frontě je méně než n, je zpráva označena jako non-conformant a může být zahozena, pozdržena do doby než bude dostatek tokenů ve frontě, případně odeslána s příznakem non-conformant.
== Popište Stochastic Fair Queuing algoritmus pro plánování paketů a vysvětlete, co je jeho cílem. ==
The stochastic fair queuing algorithm is used when many flows need to compete for
bandwidth. The algorithm approximates having a queue for each flow and sending
data from the queues in a round robin fashion. Rather than having as many queues
as flows, however, the algorithm hashes a potentially large number of flows to a
relatively small number of queues. To compensate for the possibility of a collision
that would make multiple flows share one queue, the algorithm changes the hash
function periodically.
SFQ se používá v situaci, kdy se spousta datových toků pere o jednu šířku pásma. Funguje to tak, že algoritmus se navenek (pro datové toky tváří), že každý má svou frontu, do které cpe data, a ty se round-robin procházejí a odesílají se z nich data. Ve skutečnosti má ale relativně málo front a identifikace jednotlivých toků na ně hašuje. Protože takhle samozřejmě může docházet ke kolizím, tak čas od času mění hašovací funkci, aby žádné dva toky příliš dlouho nepadaly do stejné fronty.
== Popište Class Based Queuing algoritmus pro plánování paketů a vysvětlete, co je jeho cílem. ==
The class based queuing algorithm is used when multiple flows need to share bandwidth. The flows are separated into hierarchical classes that specify their bandwidth requirements and can borrow unused bandwidth from each other.
A class has a level. The level of a leaf class is 1, the level of a parent class is one higher than the maximum level of its children.
A class is under limit if it transmits below the allocated capacity. A class is over limit if it transmits above the allocated capacity. A class is on limit otherwise.
A class is unsatisfied if it is under limit and it or its siblings have data to transmit. A class is satisfied otherwise.
A class is regulated if the class based queuing algorithm prevents it from sending data. A class is unregulated otherwise.
* V klasické Formal Sharing implementaci může třída zůstat unregulated pokud není over limit, nebo pokud má předka na úrovni i, který není over limit a ve stromu nejsou žádné unsatisfied třídy úrovně nižší než i.
* Drobný nedostatek algoritmu je příliš složitá podmínka regulace. Proto se definuje Ancestor Only Sharing, ve kterém třída zůstává unregulated pokud není over limit, nebo pokud má předka, který je under limit. Nevýhodou tohoto přístupu pochopitelně je, že bude omezovat over limit třídy i tehdy, pokud tyto momentálně nikomu nevadí.
* vice toku na jedno pasmo.
* jednotlive toky jsou prirazeny do hierarchickych class podle jejich pozadavku. Tyto tridi mohou sdilet bandwidth.
* trida ma level (list 1 a rodic o 1 vic nez nejvetsi syn)
class je under limit kdyz prenasi pod alloc capacitou
over nad
on jinak
unsatisfied kdyz je pod limitem a deti maji data na vysilani
satisfied jinak
regulated kdyz ji algoritmus zakaze vysilat
unregulated jinak
- slozita podminka regulace
viz treba obrazek [http://files.myopera.com/blu3c4t/blog/cbq_graph.jpg CBQ]
BTW CBQ se běžně používá taky při schedulingu
== Popište Random Early Detection algoritmus pro plánování paketů a vysvětlete, co je jeho cílem. ==
The goal of the random early detection queuing algorithm is to avoid anomalies associated with algorithms that fill a queue first and drop a queue tail when the queue is filled. A weighted average of the queue length is kept and within a range of minimum and maximum queue lengths, packets are marked or dropped with a probability proportional to the current weighted average of the queue length. This gives the flow control algorithms of the transport protocols an early warning before the queue is filled.
chce se vyhnout vyhazovani paketu z konce front, kdyz uz je plna.
Udrzuje se minimalni, maximalni a prumerna delka fronty. Pakety jsou oznaceny nebo vyhozeny s pravdepodobnosti aktualni prumerne delky fronty. Dava to brzke varovani naplneni fronty. TCP si pak zmenší svoje okénko -> zpomalí
== Popište architekturu síťového systému souborů NFS včetně používaných protokol ů a hlavních operací těchto protokolů. ==
Version 2 of the NFS protocol introduces the NFS protocol and the mount protocol, both built over RPC. Mount protokol dovoluje klientovi poslat mount request na server, server odpoví zasláním file handle na mounted directory (operace jsou MNT, UMNT, UMNTALL, DUMP mount list, EXPORT export list). File handle by měl čistě teoreticky být opaque 32 bytes pro klienta, typicky obsahuje file system ID, I-node, generation ID. NFS protokol pak nabízí běžné souborové operace s výjimkou open a close, protože je stateless (GET/SET na atributy, LOOKUP, READ, WRITE, CREATE, REMOVE, MK/RM na directories ...).
Version 3 of the NFS protocol introduces the NLM protocol for managing locks, which can be used with any version of the NFS protocol. Recovery of locks after crash is solved by introducing lease and grace periods. The server only grants a lock for a lease period. The server enters grace period longer than any lease period after crash and only grants lock renewals during the grace period.
Version 4 of the NFS protocol abandons statelessness and integrates the mount, NFS
and NLM protocols, and introduces security, compound operations that can pass file
handle to each other, extended attributes, replication and migration, client caching.
== Vysvětlete, co to je a jaké položky zpravidla obsahuje file handle v síťovém systému souborů NFS. ==
Viz 155.
file system ID, I-node, generation ID
[http://blog.julipedia.org/2005/09/nfs-file-handles.html http://blog.julipedia.org/2005/09/nfs-file-handles.html]
== Vysvětlete, jaké problémy přináší bezstavovost NFS při testování přístupových práv a jak jsou tyto problémy řešeny. ==
Bezstavovost s sebou samozřejmě nese určité problémy. První jsou file permissions, UNIX je standardně testuje pouze při otevření, NFS musí pořád (jako řešení se permissions při otevření testují na klientovi a sdílí se prostor UID a GID a relaxují se některé kontroly (vlastník souboru může vše, právo execute implikuje právo read)).
== Vysvětlete, jaké problémy přináší bezstavovost NFS při mazání otevřených souborů a jak jsou tyto problémy řešeny. ==
Další je mazání otevřených souborů (opět se řeší na klientovi). Může se vyřešit například zámky, ale pouze od V3.
Poslední zmíněná je atomista operací, při limitu 8k na RPC request se musí některé operace rozdělit (neřeší se). .
== Vysvětlete, jaké problémy přináší bezstavovost NFS při zamykání souborů a jak jsou tyto problémy řešeny. ==
Recovery of locks after crash is solved by introducing lease and grace periods. The server only grants a lock for a lease period. The server enters grace period longer than any lease period after crash and only grants lock renewals during the grace period.
Problém může nastat, když to spadne. Proto se zámky přidělují pouze na omezenou dobu (max na
LEASE). Po restartu je systém ve speciálním módu, kdy pouze potvrzuje prodloužení zámků (a tak si
je rekonstruuje), avšak odmítá zámky nové. V tomto stavu je po dobu LEASE. Poté pokračuji, jako
kdyby se nic nestalo. Samozřejmě, pokud někdo bude chtít škodit (obnovit zámky na vše), tak může!
= Security Subsystem =
== Vysvětlete termín authentication . ==
Authentication je problém oveření toho, zda je aktivita (proces, uživatel) tím, za koho se vydává. Zpravidla se používá kombinace jména a hesla, typicky je pak v systému nějaká centrální autorita, která toto ověřuje, ostatní se už jen ptají téhle autority.
== Vysvětlete termín authorization . ==
Authorization je problém rozhodnutí, zda je daná aktivita (proces, uživatel) oprávněna udělat nějakou akci nad nějakým prostředkem (soubor, zařízení).
== Vysvětlete, co to je access control list . ==
Access control lists je technika, kde se s každým prostředkem uloží seznam aktivit a jim dovolených akcí. ACL umí leckteré UNIXy, v těch jsou zpravidla jako aktivity bráni users nebo groups a akce jsou klasické RWX nad soubory. Z téhož principu vlastně vycházejí i standardní atributy u UNIX souborů.
== Vysvětlete, co to je capability . ==
Capabilities je technika, kdy si každá aktivita nese seznam prostředků a nad nimi povolených akcí. Při přístupu k prostředku se pak aktivita prokáže svou capability, kterou systém verifikuje. Toto je mechanizmus, který běžné systémy příliš často nemívají, ale u distribuovaných systémů nachází značné uplatnění, příklady jsou capabilities u Amoeby, Machu či EROSu nebo credentials v CORBE.
