Upravljanje memorijom

 

Povijesno C program se sastoji od sljedećih dijelova:

-         Text segment. Ovo su strojne instrukcije koje se izvršavaju. Obično je text segment dijeljen tako da je za često izvršavane programe dovoljno da samo jedna kopija bude u memoriji. Najčešće taj segment je samo za čitanje.

-         Inicijalizirani segment podataka. Obično se samo naziva segment podataka (data segment) i sadrži varijable koje su inicijalizirane u programu Npr. deklaracija int max=99 van bilo ke funkcije uizrokuje smještanje ove varijable na data segment zajedno sa njenom vrijendosti.

-         Neinicijalizirani segment podataka. Ovaj segment se obično naziva bss segment (block started by simbol – povijesni razlozi). Podaci u ovom segmentu se inicijaliziraju pri pokretanju od strane jezgre na 0 ili na null pointer. (npr. deklaracija int sum[100]

-         Stog (Stack). Područje na koje se automatske varijable spremaju, zajedno sa informacijama koje su snimljene svaki put kada se funkcija poziva. Pri svakom pozivu sprema se adresa na koju se treba vratiti i neki podaci o okruženju pozivatelja.

-         Heap (Hrpa) – Dinamičke memorijske alokacije zauzimaju mjesto na hrpi. Povijesno hrpa se nalazi između vrha neicijilaziranog segmenta podataka i dna stoga.

Naredbom size moguće je vidjeti podatke za određeni program.

 

Unutar C-a nije moguće napraviti goto na neki label unutar neke druge funkcije. Naprviti tako nešto ipak je moguće uz pomoć dviju funkcija setjmp i longjmp(zaglavlje <setjmp.h>). Ove su funkcije korisne za rukovanje greškama koje se pojave kod duboko unutar ugnježđenih funkcija.

 

            int setjmp(jmp_buf env);

čuva tekuću poziciju stoga. Vraća 0 ako se direktno pozive, inače vraća vrijednost koja se prenijela kao parametar funckije longjmp.

            void longjmp(jmp_buf env,int val);

Vraća sadržaj stoga na vrijednost postavljenu unutar env

 

Primjer: jmp.c

 

Efekt longjmp na automatskim, registar i volatile varijablama ?

a)      cc –O jmp.c  (uključena optimizacija)

b)      cc jmp.c

 

Strategije zamjene stranica

Promotrimo sljedeću situaciju. Neka je adresni prostor pojedinog programa (logički adresni prostor) veći nego što je stvarni fizički adresni prostor. Memory managment unit (MMU) se brine oko mapiranja virtualnih adresa u prave fizičke adrese. Logički adresni prostore podijeljen je na dijelove koji se nazivaju stranice (pages), a odgovarajući fizički adresni prostor se naziva okvir (page frame). U slučaju da prilikom određenog zahtjeva za pojedinom stranicom ona nije imala uspostavljenu vezu sa nekim okvirom dolazi do greške koja se naziva promašaj (page fault). Nakon toga MMU treba uspostaviti traženu vezu.

Što se događa nakon što su svi fizički okviri već mapirani, a dođe zahtjev za mapiranjem nove stranice iz logičkog adresnog prostora. U tom trenutku MMU ukluniti jednu mapiranu vezu i postaviti novu. Za odabir stranice koju će izbaciti postoji više algoritama. Neki od njih su:

 

OPT: Optimal Page Replacement

Ovaj algoritam je najbolji i najednostavniji za opisati, ali nažalost nije ga moguće implementirati. Ovaj algoritam kaže da se prilikom odabira stranice koja se treba izbaciti odaber ona koja će se u budućnosti najmanje koristiti. U praksi je to nemoguće znati, ali ako izvedemo program na simulatoru i pratimo zahtjeve za stranicama, možemo algoritam implementirati za ponovni pokušaj (jasno s istim uvjetima) i na taj način ga usporediti s nekim od postojećih algoritama

 

FIFO: First-In, First-Out

Obično se ne koristi jer za  npr. prvu stranica koja se nalazi unutar okvira ne mora nužno vrijediti da se neće upotreblajvati (štoviše možda se najčešće upotrebljavala).

Također pati i od Beladyjeve anomalije.

Činilo se da s porastom okvira se smanjuje broj promašaja, međutim Belady je 1969. otkrio kontraprimjer u kojem se s povećanjem broja okvira povećava broj pogrešaka.

 

Primjer: Neka su stranice zahtjevane u sljedećem redoslijedu :  0 1 2 3 0 1 4 0 1 2 3 4

Sa 3 okvira broj promašaja je 9, a sa 4 okvira 10.

 

LRU: The Least Recently Used

Bazira se na pretpostavci da će se stranica koja se u prošlosti često koristila i u budućnosti često koristiti. Prilikom izbacivanja, izbacuje se najmanje korištena stranica. Ovaj algoritam je 'skup' jer mora održavati i ažurirati vezanu listu. Drugi problem je što nema odgovarajućeg harvera u kojem bi se pamtila cjelokupna povijest. -> NFU (Not Frequently Used -> određen broj bitova u koje se u svakom otkucaju sistemskog sata spremaju vrijednosti bita pristupa)

 

 

NRU: Not Recently Used

Kako bi operacijski sustav mogao voditi nekakvu statistiku o korištenju pojedine stranice za svaku stranicu se još vežu dva bita R (read) i M (modified). R se postavlja kad se pojedinoj stranici pristupa bilo za čitanje ili pisanje, a M kad se u stranicu nešto upisuje. Prilikom odabira izbacivanja odabire se stranica po sljedećem redoslijedu:

R=0 i M=0 (nije upotrebljavana, nije modificirana)

R=0 i M=1 (nije upotrebljavana, modificirana)

R=1 i M=0 (upotrebljavana, nije modificirana)

R=1 i M=1 (upotrebljavana, modificirana)

 

Second Chance

Jednostavna modifikacija FIFO algoritma. Svakoj od stranica pridružen je jedan bit koji predstavlja da li se stranica u posljednje vrijeme koristila. Ako je taj bit 0 stranica je i stara i nekorištena i biti će izbačena, a u slučaju da je 1, taj bit će biti postavljen na 0 i biti će pomaknuta na kraj reda.

 

The Clock Replacement

Iako je 'Second Chance' razuman algoritam, nepotrebno je neefikasan jer stalno pomiče stranice po listi. Bolji pristup je da se sve stranice drže u kružnoj listi, u obliku sata, gdje bi kazaljka (pokazivač) pokazivala na najstariju stranicu. O ovom slučaju nema pomicanja liste na kraj reda, veće se samo kazaljaka pomakne za jedno mjesto. Razlika u odnosu na SecondChance je samo u implementaciji.

(4BSD koristi Clock algoritam sa 2 kazaljke.Prvo čisti bit korištenja na mjestu na kojem pokazuje prva kazaljka, a zatim provjerava bir korištenja na kraju, nakon čega pomiče obje kazaljke )

 

 

Zadatak 1.

Neka računalo ima 4 okvira. Vrijeme učitavanja u okvir ,vrijeme zadnjeg pristupa i bitovi R i M su sljedeći:

Stranica

Učitana

Zadnji pristup

R

M

0

126

280

1

0

1

230

265

0

1

2

140

270

0

0

3

110

285

1

1

Koju će stranicu izbaciti sljedeći algoritmi NRU, FIFO, LRU, second chance

 

Rješenje: NRU -> 2, FIFO (stanje 3,0,2,1) ->3, LRU -> 1,

second chance: stanje 3,0,2,1, ali 3 ima R bit na 1, pa onda dobijemo 0,2,1,3 s tim da na 3 sad imam R=0. Za stranicu 0 se ponovi ista stvar => izbacit će stranicu 2

 

Zadatak 2. Računalo svakom programu dodijeli 65536 byteova adresnog prostora podijeljenog na stranice veličine 4096 byteova. Ako određeni program ima text-size 32768 byteova, data segment 16386 byteova i veličinu stoga 15870 byteova da li program stane u adresni prostor. Napomena: Pojedina stranica ne može sadržavati dijelove dvaju različitih segmenata. Da li bi program stao da su stranice bile velike 512 byteova.?

 

Zadatak 3. Ako se FIFO algoritam zamjene stranica koristi sa 4 okvira i 8 stranica, koliko promašaja će se pojaviti ako se stranicama pristupa u sljedećem nizu: 0172327103. LRU?

 

Zadatak 4. Neka je dan sljedeći program

int i,j,k;

int A[256][256], B[256][4], C[256][4];

for (i=0; i<256; i++){

for (j=0; j<4; j++){

for(k=0;k<256;k++){

C[i][j] = A[i][k] * B[k][j] + C[i][j];

}

}

}

 

Neka svaki cijeli broj zauzima 4 byte-a i neka je veličina stranice 4 KB. Text dio programa zauzima stranicu 0. Polja su spremljena po retcima (i to prvo A, B, pa C). Svako polje počinje na rubu neke stranice te za i,j,k nisu potrebne stranice.

 

a) Koje stranice zauzimaju pojedina polja?

A: 1-16 , B: 17 i  C: 18

stranica 1:  A[0][0], A[0][1], ... A[15][255]

stranica 2:  A[16][0], A[16][1], ... A[31][255]

...

stranica 17:  B[0][0] ... B[255][3]

stranica 18:  C[0][0] ...C[255][3]

 

b) Koji je redoslijed pozivanja stranica?

i= 0...15      16 x 4 puta sljedeća sekvenca 1,17,18,18

i= 16...31   16 x 4 puta sljedeća sekvenca  2,17,18,18

...

i=240..255  16 x 4 puta sljedeća sekvenca 16,17,18,18

 

c) Sto bi bilo da su petlje j i i zamijenile poredak?

4 x sljedeća sekvenca: (16 x 256 1,17,18, 18 , pa 16x256  2,17,18,18...pa 16x256 16,17,18,18)

 

d) Sto bi bilo da su petlje k i i zamijenile poredak?

256 x 4  sljedećih sekvenci: (16 puta 1,17,18, 18 , pa 16x 2,17,18,18 ... pa 16x 16,17,18,18 )

 

Primjetimo da će d uzrokovati najviše zamjena stranica (najčešće se stranice mijenjaju)

 

e) Ako je program alocirao 8 okvira, koji od algoritama FIFO i LRU će dati manji broj promašaja

 

Zadatak 5. Računalo ima 40 byteova memorije organiziranih po stranicamao od 10 byteova. Pristupa se sljedećim adresama: 21, 61, 65, 14, 20, 10, 17, 32, 45, 66, 70, 58, 39, 13, 41.

Kako će izgledati i koliko promašaja će davati algoritmi FIFO,LRU, OPT.

 

Zadatak 6. Sustav za upravljanje memorijm za neki proces alocirao je 3 stranice. Proces ima sljedeći niz poziva stranica: 4 4 3 4 2 5 1 3 4 1 4 2 5 1 3 4 5 2 4 1. Utvrdite koliko ima zahtjeva za učitavanje stranice ako se koriste algoritmi: FIFO, OPT i LRU brojačem. Kod OPT algoritma gledati do 5 stranica u budućnosti.

 

FIFO: (izbacuje se ona stranica koja je prva u redu)

      4 4 3 4 2 5 1 3 4 1 4 2 5 1 3 4 2 5 2 4 1

str1: 4   4   4 5 5 5 4     4 4 1 1 1 2 2     2

str2:     3   3 3 1 1 1     2 2 2 3 3 3 5     5

str3:         2 2 2 3 3     3 5 5 5 4 4 4     1

zamj: x   x   x x x x x     x x x x x x x     x

Broj promašaja: 15

 

OPT: (izbacuje se ona stranica koja će se u budućnosti najmanje koristiti)

      4 4 3 4 2 5 1 3 4 1 4 2 5 1 3 4 2 5 2 4 1

str1: 4   4   4 4 4         2 5     5 5       ?

str2:     3   3 3 3         3 3     4 4       ?

str3:         2 5 1         1 1     1 2       ?

zamj: x   x   x x x         x x     x x       x

Broj promašaja: 10

 

LRU: (izbacuje se najdulje nekorištena stranica)

      4 4 3 4 2 5 1 3 4 1 4 2 5 1 3 4 2 5 2 4 1

str1: 4   4   4 4 1 1 1     1 5 5 5 4 4 4     4

str2:     3   3 5 5 5 4     4 4 1 1 1 2 2     2

str3:         2 2 2 3 3     2 2 2 3 3 3 5     1

zamj: x   x   x x x x x     x x x x x x x     x

Broj promašaja: 15