Esercizio - Programmi che scorrono array, stringhe di riferimenti e page fault (eserciziario, esercizi 50, 73 e 77)

---

Il metodo

1. Si scrive l'ordine in cui il programma tocca la memoria, istruzione per istruzione: di solito prima le letture (nell'ordine di valutazione) e poi la scrittura.
2. Per ogni indice, si calcola la pagina: $\lfloor\text{indice}\cdot\text{byte per elemento}/\text{dimensione pagina}\rfloor$ (o, per le matrici, la posizione lineare in memoria).
3. Si comprime la stringa dei riferimenti (accessi consecutivi alla stessa pagina non contano come nuovi fault) e si applica l'algoritmo di sostituzione.

Esercizio 50 (matrice per righe, LRU, 3 frame)

La matrice è memorizzata per righe: A[0][0], A[0][1], …, A[99][99]. Ha $100\cdot100=10\,000$ elementi da 1 B e comincia alla locazione 200: occupa le locazioni da 200 a 10 199, cioè $10\,000/200=50$ pagine, a partire dalla pagina 1 (la pagina 0, le locazioni 0-199, contiene il codice).

Ad ogni iterazione si accede al codice (pagina 0, per leggere l'istruzione) e a un elemento di A. Poiché ad ogni passo si riferisce la pagina 0, questa è sempre la più recente: non viene mai scelta come vittima. Delle altre due pagine si alternano i due frame:

• i primi 200 azzeramenti (A[0][0]…A[1][99], righe 0 e 1) accedono alla pagina 1;
• i successivi 200 alla pagina 2, e così via: ogni 200 elementi si cambia pagina.

Page fault: 1 per caricare il codice (pagina 0) e 50 (una per ciascuna delle 50 pagine della matrice, quando vi si accede la prima volta), in totale

$$1+50=\mathbf{51\ page\ fault}.$$

La pagina matrice usata meno di recente è quella vecchia, quindi la sostituzione toglie sempre una pagina già finita di scorrere. Il valore è lo stesso (51) per la soluzione del corso.

(Se la matrice fosse scandita per colonne, for j … for i …, ogni elemento sarebbe in una pagina diversa dal precedente: salti di 100 posizioni, due righe ogni pagina: molti più fault; il caso esteso è nel laboratorio 7.)

Esercizio 73

(1) Stringa dei riferimenti. Ogni iterazione calcola A[i*j] = A[2*i] + C[2*j] e quindi legge A[2*i], legge C[2*j] e scrive A[i*j].

• A[2*i]: con $i=1$ è A[2] (pagina 0); con $i=2$ è A[4] (pagina 0).
• C[2*j]: $2j<256$ per $j<128$ (pagina 2), $2j\ge256$ per $j\ge128$ (pagina 3).
• A[i*j]: con $i=1$ è A[j], indice $<256$: pagina 0. Con $i=2$ è A[2j]: pagina 0 per $j<128$, pagina 1 per $j\ge128$ ($2j\in[256,510]$).

Stringa compressa: $(0\,2\,0)^{128}\,(0\,3\,0)^{128}\,(0\,2\,0)^{128}\,(0\,3\,1)^{128}$.

(2) Tabella delle pagine. I frame sono 3.

FIFO (5 fault):

• primo accesso alla pagina 0: fault; poi la pagina 2: fault ($i=1,j=0$);
• $i=1,j=128$: la pagina 3 entra nel terzo frame: fault. Ora i frame hanno 0, 2, 3 (in ordine di caricamento: 0 la più vecchia);
• $i=2,j=128$: la pagina 1 è nuova: fault; FIFO toglie la 0 (la più vecchia);
• subito dopo la pagina 0 serve di nuovo (iterazione $j=129$): fault; FIFO toglie la 2.

Totale 5 fault. Alla fine in memoria: pagine 1, 0, 3 (la 2 non c'è più).

LRU (4 fault): come FIFO fino a $i=2,j=128$. Qui si deve inserire la 1; nella stessa iterazione le pagine 0 (A[4]) e 3 (C[256]) sono appena state riferite, quindi la meno recente fra 0, 2, 3 è la 2: LRU toglie la 2 e non la 0, e non c'è il fault aggiuntivo. Totale 4 fault. Alla fine in memoria: pagine 0, 1, 3.

La differenza è in una pagina (la 0) riferita continuamente: FIFO guarda solo quando è stata caricata (per prima), LRU guarda che è sempre in uso.

Esercizio 77

(a) Gli elementi a[0..127] sono nella pagina 0, a[128..255] nella 1, a[256..383] nella 2, a[384..511] nella 3. Ogni iterazione riferisce a[2*i], a[N-i-1] e scrive a[i]: tre riferimenti, in totale $256\cdot3=768$ riferimenti.

Con LRU e 3 frame:

1. $i=0$: la pagina 0 (fault), la 3 (fault);
2. $i=64$: la pagina 1 (fault): frame 0, 3, 1; da qui $i$ fino a 127 si usano 0, 1, 3;
3. $i=128$: a[256] è nella pagina 2 (fault): si toglie la meno recente, la 1; ma la scrittura a[128] della stessa iterazione richiede subito la pagina 1, quindi un altro fault, che toglie la meno recente fra 0, 3, 2, cioè la 3;
4. $i=192$: la pagina 3 (fault, si toglie la 0 non più usata).

In totale 6 page fault, e $768-6=762$ riferimenti validi (senza fault). (Il risultato coincide con la soluzione del corso: 6 fault e 762 riferimenti.)

(b) Tempo medio di accesso con paginazione su richiesta:

$$\text{EAT}=\frac{6}{768}\cdot25\ \text{ms}+\frac{762}{768}\cdot100\ \mu\text{s}=0{,}1953\ \text{ms}+0{,}0992\ \text{ms}=0{,}2945\ \text{ms}\approx\mathbf{0{,}294\ ms}.$$

(La soluzione scrive $0{,}294\cdot10^{-3}$ s.)

---

Errori tipici

• Dimenticare l'accesso al codice nell'esercizio 50: la pagina 0 occupa un frame e si carica una volta.
• Compressione sbagliata della stringa: accessi consecutivi alla stessa pagina sono hit, non nuovi riferimenti da ripetere.
• Calcolare la pagina di A[i*j] senza distinguere $i=1$ e $i=2$ nell'esercizio 73.
• Non scrivere la scrittura a[i] fra i riferimenti.