[so] Rezolvarea subiectelor de la examen

[Mihai Balan]

Salut!
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
:).

1. De ce dimensiunea unui microkernel este mult mai mică decât cea a unui
kernel monolitic?
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.)

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 *în user-space*. 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.
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) )

3. Modificaţi următoare sectenţă de cod astfel încât să poată fi rulată
dintr-un mediu multi-threaded:
(răspunsul l-am inclus în secvenţa de cod:)

elem_t *v[MAX_V];
int free_entry(int i)
{
*   lock(&mem_mutex); /* THIS IS ADDED */*
  if (i < 0 || i >= MAX_V || !v[i])
  {
*      unlock(&mem_mutex); /* THIS IS ADDED */*
     return -1;
  }
  v[i] = NULL;
*   unlock(&mem_mutex);  /* THIS IS ADDED */*
  return 0;
}

int alloc_entry(void)
{
*   lock(&mem_mutex); /* THIS IS ADDED */*
  for(i = 0; i < MAX_V; i++)
  {
    if (!v[i])
    {
      elem_t *e = malloc(sizeof(*e));
      if (!e)
      {
*        unlock(&mem_mutex);  /* THIS IS ADDED */
*        return -1;*
*      }
      v[i] = e;
*      unlock(&mem_mutex);  /* THIS IS ADDED */*
      return i;
    }
  }
*   unlock(&mem_mutex);  /* THIS IS ADDED */*
  return -1;
}

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ă.
A: lămuriri suplimentare:
    * timpul de procesare/creare a unei cereri este de 1ms
    * cerinţa cu planificarea prin loterie era greşită, deci s-a punctat
doar planificarea round-robin.
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).
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
N_cereri/sec = 10/1.02 = 9.803

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?
A: - (vezi finalul mailului ;-) )

6. Fie următoarea secvenţă de (pseudo)cod:

int u[512*1024*1024];

for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)
{
  u[i] = i;
}

if (fork() == 0)
{
  for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)
  {
    if (u[i] == 0)
      u[i]++;
  }

  for (i = 0; i < sizeof(u)/sizeof(u[0]); i++)
  {
    if (u[i] != 0)
      u[i]++;
  }
}

Unul din cele 2 cicluri for de după fork() se execută mai rapid. Explicaţi
care şi de ce.

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.

7. Cât spaţiu de swap poate fi folosit pe un sistem cu registre de adresare
de 32biţi şi 2GB RAM?
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).

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?
A: MAX = 16 x 4kB + 4 x IND + 1x D.IND
IND = 4kB / 4 (câte adrese de bloc „intră" într-un bloc) x 4kB = 1024 x 4kB
- indirectarea simplă
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ă
MAX = (16 + 1024 + 1024x1024) x 4kB

9. Care sunt motivele pentru care în sistemele SMP se folosesc mai multe
cozi de planificare (câte una per procesor)?
A: - nu mai trebuie folosit un lock global pentru protejarea cozii de
planificare
- 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).


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ă :)

Numai bine & vacanţă plăcută,
Mihai

-- 
Balan Mihail-Alexandru
Faculty of Automatic Control and Computers
Politehnica University of Bucharest

Blog: http://michou.is.dreaming.org/
Photoblog: http://mihaibalan.wordpress.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cursuri.cs.pub.ro/pipermail/so/attachments/20080217/18c93e43/attachment.html