[so] [Tema5]Cum functioneaza swapper-ul? ( si testerul, ca tot suntem aici... )

Razvan Deaconescu razvand at cs.pub.ro
Sun Jan 14 00:46:44 EET 2007


Florin wrote:
> Citat din enuntul temei: "Daca nu mai sunt pagini fizice libere,
> biblioteca trebuie sa evacueze o pagina fizica in swap. Paginile din
> swap trebuie aduse in memoria fizica, atunci cand ele sunt accesate."
> 
> 
> In tema nu se specifica insa nicaieri <<pe ce pozitie in swap>> se va
> evacua pagina fizica.

Nu intereseaza.

> Din pacate, eu am ales varianta in care sa
> mentin intr-o tabela, similara cu page table-ul, indicii paginilor
> din swap la care se gasesc pagini din memoria virtuala. Dupa ce m-am
> uitat atent pe codul test.c, mi-am dat seama ca alegerea facuta de
> mine a fost proasta, avand in vedere modul in care se face testarea.
> Si anume, citez din test.c, functia check_swap:
>

for (i = 0; i < ppages; i++) {
                 lseek (ram_fd, i * p_sz + offset, SEEK_SET);
                 for (j = 0; j < checks; j++) {
                         read (ram_fd, &read_val, 4);
                         if (j == 0) {
                                 page_id = read_val >> 16;
                                 mapped_vpages[i] = page_id;  /// POS #1
                         }
[.....]
                  swap_count++;
                 lseek (swap_fd, i * p_sz + offset, SEEK_SET);
                 for (j = 0; j < checks; j++) {
                         read (swap_fd, &read_val, 4);
                         if (j == 0) {
                                 page_id = read_val >> 16; /// POS#2
                         }
                         for (k = 0; k < ppages; k++)
                                 if (page_id == mapped_vpages[k] && 
have_count != 0) /// POS#3
                                         check = 0;
                         check &= !(page_id ^ (read_val >> 16));

> 
> Dupa cat am inteles eu din codul functiei check_swap, dupa cum se
> vede la POS#1 , se memoreaza in mapped_vpages niste id-uri de pagini
> virtuale, care se calculeaza pe baza valorilor stocate in RAM ( ugly
> hack, btw ).

Pe pozitia data din RAM se stocheaza pe primii doi octeti numarul 
paginii virtuale stocate si pe ultimii doi octeti offset-ul in cadrul 
paginii (adica pozitia unde se face stocarea ... ugly but simple hack 
... am vrut sa aplic MD5 peste intreaga pagina si sa stochez aici 
rezultatul, dar am zis ca e mai simplu asa :-P)

In structura mapped_vpages retinem de fapt identificatorul paginilor 
virtuale stocate in RAM. Daca mapped_vpages[2] = 3 atunci in ce-a de-a 
treia pagina fizica a fost stocata a 4-a pagina virtuala (numerotarea 
incepe de la 0)

> Apoi, in bucla de verificare a swap-ului, se calculeaza
> page_id-ul paginiii aflate in swap tot pe baza valorii citite din
> pagina din swap - vezi POS#2.

Se cauta pagina virtuala stocata in swap la pozitia data. page_id 
reprezinta aici identificatorul paginii virtuale stocate la pozitia i in 
swap.

> Testul se asteapta, apoi, ca valoarile sa coincida - vezi POS#3.

You got it wrong here!
Testul if (page_id == mapped_vpages[k]) verifica daca o pagina virtuala 
care se gaseste in swap (identificata prin page_id) se gaseste si in RAM 
  (caz clar de functionare invalida a temei ... o pagina virtuala nu se 
poate afla simultan in RAM si swap).

> 
> Daca da , atunci eu consider ca macar acest lucru trebuia specificat
> clar in enuntul temei, pt ca este un detaliu de implementare care
> poate impiedica trecerea anumitor teste. Nu consider ca este
> corect/...  ca, inainte sa ne apucam de o tema, noi sa trebuiasca mai
> intai sa citim testele si sa deducem de acolo cum ar trebui sa se
> comporte programul la rulare.
> 

Doamne Fereste! asta NU a fost niciodata ideea ... voi ati facut sa fie 
asta ideea :-) ... testul este complicat pentru ca e destul de greu sa 
verifici o astfel de tema (in implementarea mea testul este mai complex 
si mai dificil de implementat decat tema) ... daca tema urmeaza regulile 
de bun simt ale swapping-ului (o simpla parcurgere a cursului de memorie 
virtuala sau Tanenbaum) va merge brici.

Din pacate, s-a pornit pe ideea ca tema este super complicata si ca sunt 
niste nenorociri de teste facute de cineva pe masura ca sa va incurce. 
Asa ca ati incercat sa adaptati cat mai bine tema la teste, in loc sa o 
faceti fara a avea un suport de testare in spate si de a incerca sa 
respectati plafonul teoretic. Rezultatul a fost ca pierdeti mai mult 
timp pe evaluarea fisierului de test decat pe implementarea efectiva a 
temei si pe intelegerea conceptului de memorie virtuala/swapping.

> Eu am ales ca pagina #tz sa fie mapata la swap_table[#tz], care poate
> fi diferint de #tz. Ma mir insa de ce nu imi pica testul...

Poate fi mapata oriunde; pe test nu il intereseaza acest lucru.

> 
> Dar , in mod surprinzator, nu din aceasta cauza tema mea pica
> testele... Se pica la testul init2, subtestul swap_count. Acest test
> verifica daca swap_count ==have_count:
> 

acolo e bug-ul :-)

> if (have_count != 0) test ("swap_count", swap_count == have_count);
> 
> Acuma, sa ne uitam cum se calculeaza swap_count:
> 

de ce nu te-ai uitat cand se apeleaza check_swap - functia in cadrul 
careia apare testul "swap_count"?

lemme show ya:

...............
         read_write (2, PAGE_FAULT, rand_pos);
         write_read (2, NO_PAGE_FAULT, rand_pos + 4);
         read_write (2, NO_PAGE_FAULT, rand_pos + 8);

         ram_sync ();
         check_ram (rand_pos, 3, 3);

         write_read (3, PAGE_FAULT, rand_pos);
         read_write (3, NO_PAGE_FAULT, rand_pos + 4);
         write_read (3, NO_PAGE_FAULT, rand_pos + 8);

         ram_sync ();
         check_swap (rand_pos, 4, 3, 3, 1);
...............

reamintesc ca e vorba de 4 pagini virtuale si 3 pagini fizice;
pana la pasul write_read (3, ...), primele 3 pagini virtuale (1, 2, 3) 
se gaseau in RAM; cand apare write_read (3, ...) se va incerca 
pozitionarea celei de-a patra pagini virtuale in RAM ... dar tot RAM-ul 
e plin ... deci facem swapping la o pagina (NU ma intereseaza care)

check_swap verifica daca la pozitia rand_pos din cadrul celor 4 pagini 
virtuale si 3 fizice sa gaseste valoarea (page_id << 16 | rand_pos) in 3 
randuri (adica la rand_pos, rand_pos + 4, rand_pos + 8). Astia sunt cei 
4 parametri. Ultimul parametru este 'atat de batatorul de cap' have_swap.

> [.............................] swap_count = 0; for (i = 0; i <
> vpages; i++) {
> 
> lseek (swap_fd, i * p_sz + offset, SEEK_SET); read (swap_fd,
> &read_val, 4); if (read_val == SWAP_POISON) continue;
> 

if (read_val == SWAP_POISON)
         continue;
swap_count++;

SAYS IT ALL!

> 
> Din ce am inteles eu, swap_count este egal cu vpages la finalul
> buclei, asta doar daca nu avem SWAP_POISON, si nu avem asa ceva in
> testul init2.

Nu ai inteles bine.

> 
> Intrebarea : de ce asa ??? Ce rol are have_count asta, ca din cod eu
> personal nu pot sa inteleg.
> 

Sper ca acuma sa intelegi care este rolul lui have_count.

Razvan

Insist sa intelegeti ca rolul temei nu este sa cautati "farmece" in test 
ci sa implementati un swapper/pager ... daca ati inteles conceptele si 
notiunile teoretice tema va va iesi din prima si testele vor fi trecute. 
In momentul in care un test pica, va recomand sa va uitati in codul 
vostru si sa reanalizati design-ul, nu sa stati sa luati la bani marunti 
testul (se pare ca faptul ca nu l-am comentat nu v-a impiedicat de la 
acest lucru ... poate ar fi trebuit sa-l scriu in assembly :-p:-p)

Florin, apreciez capacitatea ta de a analiza codul altora - e o calitate 
buna! Dar, in cazul de fata, depui prea mult efort cu rezultate minime.


More information about the so mailing list