<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p><font face="Helvetica, Arial, sans-serif">Dear Mr. Tuma,</font></p>
<p><font face="Helvetica, Arial, sans-serif">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.</font></p>
<p><font face="Helvetica, Arial, sans-serif"><b>Implement a
semaphore with passive waiting. You can rely on the existence
of spin locks and suitable functions that</b><b><br>
</b><b>can make a thread or a process go to sleep and wake up,
together with common data types such as collections, but with</b><b><br>
</b><b>no support for concurrent access.</b></font></p>
<pre class="verbatim" style="text-align: left; margin-left: 0ex; margin-right: auto; color: rgb(232, 231, 227); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(23, 24, 28); text-decoration-style: initial; text-decoration-color: initial;"><font face="Helvetica, Arial, sans-serif"><span style="font-size: medium;">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);
}
</span><span style="font-size: medium;">void signal(Sem *semaphore)
{
lock(semaphore->spinlock);
semaphore->value++;
if (semaphore->value <= 0) {
semaphore->wakeups++;
cond_signal(semaphore->cond);
}
unlock(semaphore->spinlock);
}</span>
<i>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?
</i><b>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.</b><i>
getProcesstoRun:
if (ReadyQueue.isEmpty) return Exception;
process highest;
for (process p in ReadyQueue):
if (highest is unassigned OR </i><i><i>getPrio(p) > getPrio(highest)</i>):
highest = p;
return highest;
"Details" targets the way Prioritys are dynamicly altered? For Example CFS?
</i><b>Imagine you have just implemented a binary search tree. Each tree node is represented by an instance of class Node,</b><b>
</b><b>which has exactly three attributes â a pointer to the value stored in the node, and two pointers to the left and right</b><b>
</b><b>subtrees. The individual objects are allocated on a standard heap. Estimate memory consumption when the tree is used</b><b>
</b><b>to store 1000 integer values. Choose reasonable values for details such as the size of a pointer or the size of an integer,</b><b>
</b><b>and justify your estimate.
</b><i>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.
<b>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 ?
</b></i>
</font><font face="Helvetica, Arial, sans-serif"><font style="vertical-align: inherit;"><font style="vertical-align: inherit;"><i>Would for example 1000 kHz be reasonable choice, so every tick equals exactly one millisecond?</i>
</font></font></font></pre>
<font face="Helvetica, Arial, sans-serif">
</font>
<pre class="verbatim" style="text-align: left; margin-left: 0ex; margin-right: auto; color: rgb(232, 231, 227); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(23, 24, 28); text-decoration-style: initial; text-decoration-color: initial;"><font face="Helvetica, Arial, sans-serif"><i><b>
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 ?</b></i>
<i>Initial Value: 2^32 + 2^31 + ... 2^0 - 1000 -> Every Rotation is one second</i>
<b>Pick a file system. Assume an application that keeps a large list of files in memory, each file is in a different directory,</b><b>
</b><b>the directory depth is always 4 (for example â/A/B/C/D/e.txtâ). The application accesses the files from the list in a</b><b>
</b><b>random order, and always reads the first 16 bytes before going to the next file. Estimate the average number of disk</b><b>
</b><b>accesses (counted as individual sector reads) that the operating system has to make per file.
</b><i>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
</i><b></b></font></pre>
<pre class="verbatim" style="text-align: left; margin-left: 0ex; margin-right: auto; color: rgb(232, 231, 227); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(23, 24, 28); text-decoration-style: initial; text-decoration-color: initial;"><font face="Helvetica, Arial, sans-serif"><b>
</b><span style="font-size: medium;"></span></font></pre>
<div class="moz-cite-prefix"><font face="Helvetica, Arial,
sans-serif">On 06.02.19 08:28, Petr Tůma wrote:<br>
</font></div>
<blockquote type="cite"
cite="mid:57cd0675-857a-6ff2-b705-6c69747b8b67@d3s.mff.cuni.cz"><font
face="Helvetica, Arial, sans-serif">Dobry den,
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
</font>
<blockquote type="cite">
<blockquote type="cite"><font face="Helvetica, Arial,
sans-serif">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Ã
<br>
(co a proÄ bude kolikrát rychlejÅ¡Ã nebo pomalejÅ¡Ã),
konkrétnÃ
<br>
hodnoty majà pouze rámcový význam.
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif">Vzhledem k tomu, ze
kazde vlakno bezi na svem procesoru, muzeme bez ujmy na
obecnosti prohlasit, ze jakakoliv situace, ktera muze
<br>
nastat, bude ekvivalentni situaci, ve ktere se prvnimu vlaknu
vzdycky
<br>
podari zamknout zamek a inkrementovat promennou a ostatnim
vlaknum se
<br>
zamek nikdy nepodari zamknout? Pokud ano, muzeme prohlasit, ze
pro
<br>
jednu inkrementaci promenne je potreba zamek prave jednou
odemknout
<br>
a zamknout. Pokud celkovy pocet operaci na odemknuti a
zamknuti
<br>
zamku oznacime jako X, muzeme prohlasit, ze se hodnota
promenne bude zvetsovat X-krat pomaleji, protoze samotnou
rezii inkrementace
<br>
muzeme zanedbat?
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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".
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
</font>
<blockquote type="cite">
<blockquote type="cite"><font face="Helvetica, Arial,
sans-serif">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
<br>
skládá z jedné programem Ätené hodnoty typu int a jednoho
ukazatele
<br>
na dalšà položku, poslednà položka má tento ukazatel
nastaven na
<br>
NULL. Uvažujte pouze pÅÃstup k datům, nikoliv k instrukcÃm
<br>
programu
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif">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?
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif"><br>
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).
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
</font>
<blockquote type="cite">
<blockquote type="cite"><font face="Helvetica, Arial,
sans-serif">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
<br>
bloku (jako kdyby alokované bloky nemÄly hlaviÄky a nebyly
<br>
zarovnávané). Máte k dispozici 1000000 bajtů heapu.
NavrhnÄte
<br>
postup (naÄrtnÄte pseudokód), kterým na tomto heapu obsadÃte
co
<br>
nejménÄ pamÄti, ale pÅitom již nepůjde alokovat žádný blok s
<br>
velikostà 100 bajtů nebo vÃce. NemusÃte ÅeÅ¡it, kam uložit
pÅÃpadné
<br>
pomocné datové struktury
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif">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,
<br>
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,
<br>
nasledne je 1 bajt naalokovany, nasledne je dalsich 99 volnych
bajtu
<br>
a takto az do konce heapu? Pokud ano, byl by spravny
algoritmus na
<br>
vyrobu takove haldy napriklad malloc 100 bajtu a nasledne
postupne
<br>
uvolneni 99 bajtu?
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif"><br>
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).
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
</font>
<blockquote type="cite">
<blockquote type="cite"><font face="Helvetica, Arial,
sans-serif">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
<br>
uloženà souborů již nebude k dispozici pro jiné využitÃ).
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif">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?
<br>
</font></blockquote>
<font face="Helvetica, Arial, sans-serif"><br>
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).
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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 :-)
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
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.
<br>
</font>
<font face="Helvetica, Arial, sans-serif"><br>
Petr Tuma
<br>
_______________________________________________
<br>
NSWI004 mailing list
<br>
<a class="moz-txt-link-abbreviated" href="mailto:NSWI004@d3s.mff.cuni.cz">NSWI004@d3s.mff.cuni.cz</a>
<br>
<a class="moz-txt-link-freetext" href="https://d3s.mff.cuni.cz/mailman/listinfo/nswi004">https://d3s.mff.cuni.cz/mailman/listinfo/nswi004</a>
<br>
</font>
</blockquote>
</body>
</html>