[OS] Discussion for exam questions ...

[Immo]

Dear Mr. Tuma,

In this mail I'll also try to provide answers/questions to some of the 
questions from the first test and would be glad about a short notice 
about their correctness. Please excuse the potential of already asked 
questions again, because I can only roughly follow your czech 
conversation by the use of Google Translator.

*Implement a semaphore with passive waiting. You can rely on the 
existence of spin locks and suitable functions that**
**can make a thread or a process go to sleep and wake up, together with 
common data types such as collections, but with**
**no support for concurrent access.*

void wait(Sem *semaphore) { lock(semaphore->spinlock); 
semaphore->value--; if (semaphore->value < 0) { do { 
cond_wait(semaphore->cond, semaphore->spinlock); } while 
(semaphore->wakeups < 1); semaphore->wakeups--; } 
unlock(semaphore->spinlock); } void signal(Sem *semaphore) { 
lock(semaphore->spinlock); semaphore->value++; if (semaphore->value <= 
0) { semaphore->wakeups++; cond_signal(semaphore->cond); } 
unlock(semaphore->spinlock); } /I'd consider this implementation to be 
active waiting, because of the use of spinlocks. But if we can't rely on 
the existence of a mutex (not mentioned in the task description) I am 
not really sure how to make the waiting passive instead. Or is the 
waiting actually passive in this case? /*Describe the priority 
scheduling algorithm with dynamic priorities. Choose reasonable details 
and write pseudocode of a hypothetical GetProcessToRun function, called 
internally by the operating system to decide what process to run and how 
long to run it.*/getProcesstoRun: if (ReadyQueue.isEmpty) return 
Exception; process highest; for (process p in ReadyQueue): if (highest 
is unassigned OR ///getPrio(p) > getPrio(highest)/): highest = p; return 
highest; "Details" targets the way Prioritys are dynamicly altered? For 
Example CFS? /*Imagine you have just implemented a binary search tree. 
Each tree node is represented by an instance of class Node,****which has 
exactly three attributes – a pointer to the value stored in the node, 
and two pointers to the left and right****subtrees. The individual 
objects are allocated on a standard heap. Estimate memory consumption 
when the tree is used****to store 1000 integer values. Choose reasonable 
values for details such as the size of a pointer or the size of an 
integer,****and justify your estimate. */Integer & Pointer are 4 
Bytes(32bit int) each. Taking kalisto as an example each block contains 
size, free-indication, pointer to heap itself and magic each 32 bit as 
well, while the footer only contains size and magic. So one node-block 
has an estimated size of 36 bytes. -> 1000 Nodes have size of 36000 
bytes ~ 36 kB. *Assume a computer with a clock device that issues an 
interrupt request on every clock tick. Assume the clock signal period is 
configurable – what period would you choose if the signal is to be used 
in the usual way (real time tracking, scheduling, timeouts and so on) by 
the operating system ? */ /Would for example 1000 kHz be reasonable 
choice, so every tick equals exactly one millisecond?/

/*Assume further that the period is configured by programming a hardware 
counter, which gets incremented on each tick of an internal clock signal 
and issues an interrupt request (and returns to initial value) on 
overflow – what initial value would you program into the counter if the 
internal clock frequency is 1 MHz and the counter is 32 bits wide ?*/ 
/Initial Value: 2^32 + 2^31 + ... 2^0 - 1000 -> Every Rotation is one 
second/ *Pick a file system. Assume an application that keeps a large 
list of files in memory, each file is in a different directory,****the 
directory depth is always 4 (for example “/A/B/C/D/e.txt”). The 
application accesses the files from the list in a****random order, and 
always reads the first 16 bytes before going to the next file. Estimate 
the average number of disk****accesses (counted as individual sector 
reads) that the operating system has to make per file. */For each folder 
a dentry is made after it was accessed first, so the number of disc 
accesses made is two per file (dentry + fileaccess) Thank you for your 
help, kind regards, Immo Hellwig /**

**

On 06.02.19 08:28, Petr Tůma wrote:
> Dobry den,
>
>>> Zkuste hrubě odhadnout, jak rychle se bude zvětšovat hodnota 
>>> proměnné i oproti situaci, kdy by pouze jedno vlákno vykonávalo 
>>> cyklus while (true) i++;. U odhadu se očekává hlavně zdůvodnění
>>> (co a proč bude kolikrát rychlejší nebo pomalejší), konkrétní
>>> hodnoty mají pouze rámcový význam.
>> Vzhledem k tomu, ze kazde vlakno bezi na svem procesoru, muzeme bez 
>> ujmy na obecnosti prohlasit, ze jakakoliv situace, ktera muze
>> nastat, bude ekvivalentni situaci, ve ktere se prvnimu vlaknu vzdycky
>> podari zamknout zamek a inkrementovat promennou a ostatnim vlaknum se
>> zamek nikdy nepodari zamknout? Pokud ano, muzeme prohlasit, ze pro
>> jednu inkrementaci promenne je potreba zamek prave jednou odemknout
>> a zamknout. Pokud celkovy pocet operaci na odemknuti a zamknuti
>> zamku oznacime jako X, muzeme prohlasit, ze se hodnota promenne bude 
>> zvetsovat X-krat pomaleji, protoze samotnou rezii inkrementace
>> muzeme zanedbat?
>
> Tohle ramcove neni spatne, az na drobne nepresne vyjadreni ke konci 
> (presneji by bylo treba "pokud odemknuti a zamknuti zamku dohromady 
> trvaji X, oproti 1 na inkrement, pak se bude i zvetsovat X-krat 
> pomaleji" - matematikove by vam rekli, ze pokud cas na inkrementaci 
> zanedbate, pak jakmile X > 0, bude vse nekonecnekrat pomalejsi :-). 
> Ale z meho pohledu to splnuje jeden zakladni element spravne odpovedi, 
> totiz uvedomit si, ze vlakna mohou zrychlit jen vykonavani tech casti 
> programu, ktere mohou bezet paralelne, coz vnitrek kriticke sekce 
> pochopitelne neni.
>
> Dalsim krokem by mohlo byt odhadnout hodnotu X, coz lze ve velmi 
> hrubem priblizeni udelat treba pocitanim pristupu do pameti - nejmene 
> jeden R-W pristup udela lock, jeden W pristup udela unlock, jeden R-W 
> pristup udela i++, takze treba X=2 nebo X=3 nemusi na prvni pohled 
> vypadat tak nesmyslne.
>
> Pokud by chtel clovek koukat na celou otazku hloubeji, mohl by se 
> zabyvat napriklad existenci caches. Kdyz bych predpokladal klasicke 
> koherentni MESI caches u vsech jader procesoru, pak cyklus "while 
> (true) i++" v izolovanem pripade pobezi s hodnotou i v L1 cache, 
> zatimco cyklus se zamky bude muset na promennou indikujici stav zamku 
> vyvolat RFO cteni a nasledny zapis. Pokud predpokladam, ze se ostatni 
> jadra budou o danou promennou take uchazet, bude to znamenat o jeden 
> az dva rady pomalejsi pristup. Pokud se navic budou jadra stridat i v 
> pristupu k i (tedy nebude platit vas predpoklad, ze vzdy vyhraje 
> stejne vlakno), tak i tento pristup bude vyzadovat RFO cteni a 
> nasledny zapis, takze se cela uloha oproti izolovanem prikladu muze 
> zpomalit treba 200 krat. Skutecnost bude o neco lepsi podle toho, jak 
> se vlaknum bude darit se predbihat.
>
> Tuto cast uvahy bych ale u standardni odpovedi moc necekal, i kdyz 
> nekteri studenti se alespon obecne zminili, ze cela vec "muze byt 
> pomalejsi kvuli synchronizaci caches".
>
>>> Strankovani Spočítejte, kolik výpadků ve vámi zvolené TLB může v 
>>> nejlepším a v nejhorším případě způsobit program, který sekvenčně 
>>> projde zřetězený seznam o 10 položkách, kde každá položka se
>>> skládá z jedné programem čtené hodnoty typu int a jednoho ukazatele
>>> na další položku, poslední položka má tento ukazatel nastaven na
>>> NULL. Uvažujte pouze přístup k datům, nikoliv k instrukcím
>>> programu
>> Mam dohromady 10 pointeru, ktere potrebuji projit, budu tedy 
>> potrebovat 10 prekladu z virtualni adresy na fyzickou. V nejlepsim 
>> pripade budou v TLB zaznam pro kazdy pointer, nedojde tedy k zadnemu 
>> vypadku; v nejhorsim pripade v TLB nebude zadny zaznam, dojde tedy k 
>> deseti vypadkum. Je tato uvaha spravne?
>
> Nejlepsi pripad je jasny, ano, i kdyz mirne presnejsi by asi bylo 
> rict, ze v TLB bude zaznam pro stranky vsech polozek (take se muze 
> stat, ze se vsechny polozky ulozi do jedne stranky, pak bude stacit 
> jediny zaznam, coz formulace "zaznam pro kazdy pointer" nepopisuje 
> uplne dobre).
>
> Nejhorsi pripad je jeste o neco horsi, protoze kazda polozka muze 
> lezet na hranici dvou stranek, pak by doslo nejhure k 20 vypadkum v 
> TLB. Ale odhad 10 neni uplne katastrofalne spatne.
>
>>> Sprava pameti Uvažujte heap alokátor bez možnosti přesunu 
>>> alokovaných bloků, u kterého můžete zanedbat režii na alokaci
>>> bloku (jako kdyby alokované bloky neměly hlavičky a nebyly
>>> zarovnávané). Máte k dispozici 1000000 bajtů heapu. Navrhněte
>>> postup (načrtněte pseudokód), kterým na tomto heapu obsadíte co
>>> nejméně paměti, ale přitom již nepůjde alokovat žádný blok s
>>> velikostí 100 bajtů nebo více. Nemusíte řešit, kam uložit případné
>>> pomocné datové struktury
>> Chapu dobre, ze otazka je polozena tak, ze mame k dispozici neznamy 
>> heap a alokator, ktery pouziva neznamou strategii alokace a nasim 
>> ukolem je pomoci sikovne alokace a dealokce pameti dosahnout toho,
>> ze na konci bude na heapu jednak co nejvice volneho mista a druhak 
>> nepujde naalokovat blok vetsi nez 100 bajtu? Pokud ano, je spravnym 
>> resenim situace, ve ktere je prvnich 99 bajtu heapu volnych,
>> nasledne je 1 bajt naalokovany, nasledne je dalsich 99 volnych bajtu
>> a takto az do konce heapu? Pokud ano, byl by spravny algoritmus na
>> vyrobu takove haldy napriklad malloc 100 bajtu a nasledne postupne
>> uvolneni 99 bajtu?
>
> Uvaha o tom, jak ma na konci vypadat heap, je zcela spravne - idealni 
> stav je vzdy 99 bajtu volnych a 1 bajt obsazeny. Spravne jste si take 
> uvedomil, ze kdyz neznate strategii prace alokatoru, algoritmicke 
> reseni muze byt obtiznejsi nez kdybyste vedel ze alokator je napriklad 
> first fit (rada odevzdanych reseni tak nejak na first fit spolehala). 
> Vas navrzeny algoritmus je ale nepresny a nezda se, ze by fungoval - 
> pokud udelate malloc 100 bajtu najednou, pak nemuzete postupne uvolnit 
> 99 z nich, protoze alokatory predpokladaji, ze uvolnujete stejne 
> bloky, jako jste alokoval. Maximalne byste mohl zkusit doufat, ze mate 
> volani realloc, ktere zmeni velikost jiz alokovaneho bloku, pak by 
> reseni bylo alokovat 10k bloku o velikosti 100 bajtu (pozor, toto zase 
> predpoklada nejakou minimalni inteligenci na strane alokacni 
> strategie) a pak je vsechny zmenit na 1 bajt prave pomoci realloc. A 
> nebo jeste primocarejsi reseni, proste alokovat jeden milion 
> jednobajtovych bloku a pak podle jejich adresy ty spravne uvolnit tak, 
> aby vznikl vzor, ktery popisujete (toto reseni je myslim jedine mozne, 
> ktere nema zadne naroky na alokacni strategii).
>
>>> Systemy souboru Aplikace potřebuje ukládat na disk zhruba milion 
>>> souborů s délkou pouze 16 bajtů, jména souborů jsou devítimístná 
>>> čísla. Zvolte si systém souborů a odhadněte diskový prostor obsazený 
>>> tímto množstvím souborů (všechen prostor, který po
>>> uložení souborů již nebude k dispozici pro jiné využití).
>> Uvazujme ext2 a velikost fyzicke stranky 4 kB. Na jeden soubor tedy 
>> bude potreba 1 fyzicka stranka a 10 bajtu na null-terminated string 
>> pro jmeno souboru. Celkem tedy 4 GB pro stranky a 10 MB pro jmena 
>> souboru. Plus jeste overhead na samotny souborovy system (inody a 
>> tak, nicmene to asi lze zanedbat. Je tato uvaha spravna?
>
> V implementaci ext2 sice existuje vazba mezi velikosti stranky a 
> velikosti alokacnich bloku, ale tu bych mozna radeji zanedbal a bavil 
> se jen o blocich, tedy beru ze uvazujete velikost bloku 4 kB. Zakladni 
> odpoved je zhruba jak uvadite, tedy jeden blok na data kazdeho souboru 
> a jedna adresarova polozka, jejimz hlavnim komponentem je jmeno, plus 
> jeden inode na kazdy soubor (a pak drobnosti jako jeden inode na 
> adresar, ale ty uz se neresi).
>
> Pokud by clovek chtel odpovedet presneji, pak asi zacatek by byl 
> podivat se na velikost inode. Ta byva v default instalacich 128 bajtu, 
> takze jeste 128 MB na ulozeni inodes (coz, kdyz vas zajimalo 10 MB na 
> adresare, neni uplne zanedbatelne). Pak je jeste mozne, ze vas 
> filesystem byl konfigurovan s nastavenim inline_data, dostupne tusim 
> od ext4 a cca roku 2011, pak by mohla byt inode size 256 bajtu a data 
> souboru by se vesla do inode, celkova spotreba tedy 256 MB plus adresar.
>
> A konecne kdybychom chteli zpresnit ten odhad velikosti adresare, pak 
> 10 bajtu na jmeno je fajn, ale jeste budete potrebovat nejmene jeden 
> int na cislo inode, kde soubor daneho jmena lezi (to je docela zasadni 
> soucast adresarove polozky), ve skutecnosti v polozce najdete jeste 
> celkem 8 bajtu dodatecne informace a jmeno neni zero terminated, takze 
> na nej staci 9 bajtu, plus nejake pozadavky na zarovnani, ktere by asi 
> bylo primo trestuhodne pamatovat si z hlavy. Cili presnejsi odhad by 
> byl nekde kolem 20 MB na adresar. Odhad delky adresare s hash tree 
> indexem jiz necham, jak rikaji matematici, k domacimu procviceni 
> laskaveho ctenare :-)
>
> Jak jste si asi vsimnul, vsechny otazky lze zodpovedet do ruzne 
> hloubky detailu. Pri hodnoceni je mi docela jedno, jestli si dobre 
> zapamatujete delku inode v ext2, kdybyste napsal 128B nebo zhruba 100B 
> nebo 256B tak bych vse z toho akceptoval, uplne mi staci, ze z 
> odpovedi je jasne, ze vite o inodes. Pokud byste ale napriklad tvrdil, 
> ze na systemu souboru zvolite bloky 16B a tedy kazdy soubor bude 
> zabirat presne 16B, tuto odpoved bych neakceptoval, protoze dana delka 
> bloku je prakticky nesmyslna. A tak dale, i u vsech ostatnich otazek. 
> Jinymi slovy - vase odpovedi podle tohoto mailu by mozna ztratily 
> nejake male mnozstvi bodu, ale celkove bych je povazoval za spise 
> spravne.
>
> Petr Tuma
> _______________________________________________
> NSWI004 mailing list
> NSWI004 at d3s.mff.cuni.cz
> https://d3s.mff.cuni.cz/mailman/listinfo/nswi004
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://d3s.mff.cuni.cz/pipermail/nswi004/attachments/20190206/60e7f7f5/attachment-0001.html>