[OS] Discussion for exam questions ...

[Petr Tůma]

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