Salut!<br>Pentru că au fost cerute destul de la unison, îmi permit să postez aici rezolvarea subiectelor de la examen. Îl rog pe Răzvan sau pe Tavi să arunce un ochi să verifice dacă rezolvările sunt corecte (they should be, chiar dacă la examen am buşit câteva :D) şi să corecteze/completeze dacă e cazul :).<br>
<br>1. De ce dimensiunea unui microkernel este mult mai mică decât cea a unui kernel monolitic?<br>A: În cazul unui microkernel, kernelul are mult mai puţine de făcut (în principiu doar partea de message passing), multe din taskurile care într-un kernel monolitic au loc în kernel fiind în cazul microkernelului realizare de către servere (inclusiv memoria virtuală, networking, etc.)<br>
<br>2. Fie un sistem cu 4 procesoare şi o aplicaţie cu 4 fire de execuţie ce foloseşte un sistem de threaduri implementat <b>în user-space</b>. Presupunând că nu mai există alte procese/threaduri în sistem şi că fiecare thread rulează timp de 10ms, după care aşteaptă la IO 10ms după care aşteaptă încă 10ms, determinaţi timpul minim de execuţie al aplicaţiei.<br>
A: 120ms (fiind threaduri implementate în user-space, kernelul nu „le vede" şi deci nu le poate planifica pe procesoare diferite => T = 4 x (T_rulare + T_IO + T_rulare) )<span style="font-family: courier new,monospace;"><br>
</span><br>3. Modificaţi următoare sectenţă de cod astfel încât să poată fi rulată dintr-un mediu multi-threaded:<br>(răspunsul l-am inclus în secvenţa de cod:)<br><br>
<span style="font-family: courier new,monospace;">elem_t *v[MAX_V];<br>
int free_entry(int i)<br>
{<br><i><b>
lock(&mem_mutex); /* THIS IS ADDED */</b></i><br>
if (i < 0 || i >= MAX_V || !v[i])<br>
{<br><i><b>
unlock(&mem_mutex); /* THIS IS ADDED */</b></i><br>
return -1;<br>
}<br>
v[i] = NULL;<br><i>
<b>unlock(&mem_mutex); /* THIS IS ADDED */</b></i><br>
return 0;<br>
}<br><br>int alloc_entry(void)<br>{<br></span><span style="font-family: courier new,monospace;"><i><b>
lock(&mem_mutex); /* THIS IS ADDED */</b></i></span><br><span style="font-family: courier new,monospace;"> for(i = 0; i < MAX_V; i++)<br> {<br> if (!v[i])<br> {<br> elem_t *e = malloc(sizeof(*e));<br>
if (!e)<br> {<br></span><span style="font-family: courier new,monospace;"><i> <b>unlock(&mem_mutex); /* THIS IS ADDED */<br></b></i> return -1;<i><b><br></b></i></span><span style="font-family: courier new,monospace;"> }<br>
v[i] = e;<br></span><span style="font-family: courier new,monospace;"><i> <b>unlock(&mem_mutex); /* THIS IS ADDED */</b></i></span><br><span style="font-family: courier new,monospace;"> return i;<br> }<br>
}<br></span><span style="font-family: courier new,monospace;"><i>
<b>unlock(&mem_mutex); /* THIS IS ADDED */</b></i></span><br><span style="font-family: courier new,monospace;"> return -1;<br>}<br></span><br>4. Fie un sistem în care avem 1 proces server, 10 procese client şi 10 alte procese. Procesele client trimit spre procesare o cerere serverului şi apoi aşteaptă un răspuns. Presupunând că sistemul are cuanta de timp de 100ms, toate procesele (non-client/server - n.a.) sunt CPU intensive, avem un singur procesor, determinaţi numărul de cereri pe secundă rezolvate de server în cazul unei planificări round-robin (fără priorităţi) şi în cazul unei planificări prin loterie în care clienţii şi serverul colaborează.<br>
A: lămuriri suplimentare:<br> * timpul de procesare/creare a unei cereri este de 1ms<br> * cerinţa cu planificarea prin loterie era greşită, deci s-a punctat doar planificarea round-robin.<br>Ideea este să vedem cât durează un ciclu în care sunt planificate toate procesele (la round-robin un proces nu poate fi replanificat până ce nu au fost planificate toate celelalte procese).<br>
T_ciclu = 10 x 100ms (procesele CPU intensive) + 10 x 1ms (crearea cererii şi trimiterea ei de către clienţi) + 10 x 1ms (rezolvarea cererilor de către server) = 1020 ms<br>N_cereri/sec = 10/1.02 = 9.803<br><br>5. De ce o bibliotecă dinamică are nevoie de relocări la încărcare? De ce intră acest lucru în conflict cu partajarea codului şi a datelor read-only între instanţele folosite în mai multe procese? Ce soluţie este folosită în cazul bibliotecilor dinamice partajabile?<br>
A: - (vezi finalul mailului ;-) )<br clear="all"><br>6. Fie următoarea secvenţă de (pseudo)cod:<br><span style="font-family: courier new,monospace;"><br>int u[512*1024*1024];<br><br>for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)<br>
{<br> u[i] = i;<br>}<br><br>if (fork() == 0)<br>{<br></span><span style="font-family: courier new,monospace;"> for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)<br> {<br> if (u[i] == 0)<br> u[i]++;<br> }<br></span><span style="font-family: courier new,monospace;"><br>
</span><span style="font-family: courier new,monospace;"> for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)<br> {<br> if (u[i] != 0)<br>
u[i]++;<br> }</span><br><span style="font-family: courier new,monospace;">}<br></span><br>Unul din cele 2 cicluri for de după fork() se execută mai rapid. Explicaţi care şi de ce.<br><br>A: Primul ciclu se execută mai rapid. Asta din cauză că se intră în if doar o dată (doar primul element e zero - vezi iniţializarea) iar vectorul are 2GB (4 x 512 mega). Astfel, la copy-on-write se copiază în spaţiul de memorie al procesului copil doar prima pagină, nu toate. În al doilea for se intră de fiecare dată în if (acum nici un element nu mai e zero) şi toţi cei 2giga trebuie copiaţi în spaţiul de adresă al procesului copil.<br>
<br>7. Cât spaţiu de swap poate fi folosit pe un sistem cu registre de adresare de 32biţi şi 2GB RAM?<br>A: Oricât :) (Fiecare proces vede un spaţiu de adrese de 4GB „doar al lui" şi pot avea un număr nelimitat (sau oricum foarte mare) de procese).<br>
<br>8. Într-un sistem de fişiere Unix-like, un inode conţine 16 locaţii de adresare directă a unui bloc de date, 4 de adresare indirectă şi o locaţie pentru indirectare dublă. Ştiind că numele unui fişier este limitat la 255 caractere, superblocul ocupă 4kB, adresa unui bloc ocupă 32biţi şi un bloc are 4kB, care e dimensiunea maximă a unui fişier?<br>
A: MAX = 16 x 4kB + 4 x IND + 1x D.IND<br>IND = 4kB / 4 (câte adrese de bloc „intră" într-un bloc) x 4kB = 1024 x 4kB - indirectarea simplă<br>D.IND = 4kB / 4(câte adrese de bloc „intră" într-un bloc) x 4kB/4 x 4kB = 1024 x 1024 x 4kB - indirectarea dublă<br>
MAX = (16 + 1024 + 1024x1024) x 4kB<br><br>9. Care sunt motivele pentru care în sistemele SMP se folosesc mai multe cozi de planificare (câte una per procesor)?<br>A: - nu mai trebuie folosit un lock global pentru protejarea cozii de planificare<br>
- processor affinity şi keeping the cache hot (dacă replanifici un proces pe acelaşi procesor sunt mari şansele să mai găsesască în cache linii valide).<br><br><br>Cam astea ar fi. La punctul 5 nu mă simt în stare să dau o explicaţie coerentă aşa că-i rog pe cei care au dat problema :D / au rezolvat la examen să revină cu o explicaţie cât de sumară :)<br>
<br>Numai bine & vacanţă plăcută,<br>Mihai<br><br>-- <br>Balan Mihail-Alexandru<br>Faculty of Automatic Control and Computers<br>Politehnica University of Bucharest<br><br>Blog: <a href="http://michou.is.dreaming.org/">http://michou.is.dreaming.org/</a><br>
Photoblog: <a href="http://mihaibalan.wordpress.com/">http://mihaibalan.wordpress.com/</a>