Laborator 1

Enunt laborator

Am ajuns la stadiul in care sistemul nostru de operare are nevoie de un algoritm cat mai eficient pentru inlocuirea paginilor de memorie putin utilizate de catre programele utilizator. Algoritmul pe care l-ati studiat semestrul trecut, the clock algorithm, functioneaza scanand lista de pagini circular (ca si cand ar fi dispuse pe circumferinta unui ceas), iar la prima trecere, cand pointerul indica un cadru de pagina, bitul de utilizare este resetat (setat pe 0); la a doua trecere, fiecare cadru de pagina care nu a fost accesat de la prima trecere va avea bitul de utilizare tot resetat, si va fi plasat pe lista pentru eliberare (dupa ce este scris pe disk, daca este dirty - ce inseamna ca un cadru de pagina este dirty? ). Un cadru de pagina din lista cu cadrele ce urmeaza a fi eliberate ii retine continutul, care poate fi astfel recuperat daca acel cadru de pagina este accesat inainte de a fi suprascris.

Din pacate pentru sistemele de operare care pot accesa cantitati mari de memorie, algoritmul dureaza prea mult. Prin urmare, s-a ales simplificarea acestuia printr-un algoritm derivat. Sistemul de operare Berkeley UNIX foloseste un algoritm de inlocuire a paginilor de tipul two-handed clock algorithm. In acest algoritm, page daemon din Linux (ce este acest page daemon?) mentine doi pointeri la harta memoriei; cand ruleaza, seteaza pe 0 bitul de utilizare de la primul capat, si apoi verifica bitul de utilizare de la capatul celalalt, dupa care avanseaza cu ambii pointeri. Astfel, daca cei doi pointeri sunt apropiati unul de celalalt, atunci doar paginile accesate foarte frecvent vor avea sansa de a fi accesate intre timpul parcurgerii de catre cei doi pointeri pe care ii foloseste algoritmul.

Sarcina voastra, ca proiectanti ai sistemului de operare, este sa implementati algoritmul two-handed clock algorithm , plecand de la descrierea acestuia enuntata anterior.

Ce trebuie sa faca programul vostru:

• Vom pleca de la urmatoarele structuri de date pe care le veti folosi in implementare (puteti folosi si propriile structuri, atata timp cat utilizati eficient memoria):

#define MAXPAGES 100 /* numarul de pagini utilizate, si generate aleator de program */
struct page {
             int referenced /* pagina a fost accesata? */,
                 present /* pagina e prezenta fizic in memorie? */,
                 pageid; /* identificatorul paginii curente */
             /* ... */
             struct page *next;
            }; /* structura de pagina de memorie */
struct page *list; /* structura noastra de pagini */

• Pentru simplitate, la inceputul executiei, programul va popula aleator lista de pagini din memorie, afisand-o pe ecran intr-un format simplu de forma:

pageid = 0, referenced = 0, present = 0
pageid = 1, referenced = 0, present = 1
etc.

• Dupa generarea aleatoare a paginilor, se va aplica algoritmul de inlocuire a paginilor si vor fi afisate pe ecran paginile care vor fi inlocuite. Algoritmul se termina la parcurgerea tuturor paginilor din memorie. La final se afiseaza coada cu paginile care se doresc a fi eliberate (vezi mai jos).

Observatii:

• Alegeti o distanta intre cei doi pointeri folosit de algoritm dupa cum doriti, dar de minim 3 pagini intre pagina spre care indica primul pointer, si pagina spre care indica cel de-al doilea pointer din algoritm.
• Separat de programul principal, veti crea un fir de executie care va modifica campul referenced din lista de pagini, setandu-l pe valoarea on cu probabilitatea de 66.6% si pe off cu probabilitatea de 33.4%.
• Toate paginile marcate pentru eliberare vor fi inserate intr-o coada de pagini, a carei structura o definiti voi. Un exemplu de structura ce poate fi folosita:

struct listToRemove {
              int pageid; /* pagina marcata pentru eliberare SAU... */
              struct page *page_to_remove; /* ...prin acces direct la pagina care urmeaza a fi eliberata */
              struct listToRemove *next;
             }; /* structura de pagina de memorie */
struct listToRemove *queue; /* structura noastra de pagini */

Problemele se rezolva individual.

Timp de lucru: 1h 20m

Punctaj

• Din oficiu: 1p
• Compilarea si rularea programului: 2p
• Implementare algoritmica corecta: 5p
• Implementare eficienta si utilizare eficienta a memoriei: 2p