Esercizio - Sostituzione delle pagine con FIFO, LRU e OPT (eserciziario, esercizi 38, 39, 40, 48, 57, 58 e 80)

Il procedimento

Si scorre la stringa. Per ogni riferimento: se la pagina è già in un frame (hit), non succede niente (con LRU si aggiorna solo il momento dell'ultimo uso); altrimenti è un page fault e:

• c'è un frame libero: la pagina ci va;
• altrimenti si sceglie la vittima: con FIFO la pagina in memoria da più tempo (conta il momento del caricamento, un hit non lo cambia); con LRU quella usata meno recentemente (conta l'ultimo accesso); con OPT quella il cui prossimo uso è più lontano (o che non sarà mai più usata).

Nelle tabelle ogni colonna è un riferimento, ogni riga un frame, e F segna i fault.

Esercizio 38 (FIFO, 4 frame): 9 fault

• $t=1,2,3$: tre fault per riempire i frame con 2, 6, 3.
• $t=4$: la pagina 2 c'è. $t=5$: la 9 entra nel quarto frame. $t=6$: la 10 non c'è e non ci sono frame liberi: FIFO toglie la più vecchia, la 2.
• $t=7,8$: hit su 9 e 3. $t=9,\ldots,12$: ogni accesso è un fault che sostituisce, nell'ordine di arrivo, 6, 3, 9 e 10.

Totale: 9 fault.

Esercizio 39 (LRU, 3 frame): 7 fault

I primi tre accessi riempiono i frame. Il 12 sostituisce la meno recente (8), il 9 sostituisce lo 0, il 10 è un hit (e diventa la più recente), l'11 sostituisce il 12 (usato meno di recente tra 12, 9, 10) e il 3 sostituisce il 9. Gli ultimi due accessi all'11 sono hit. Totale: 7.

Esercizi 40 e 57 (LRU con prepaginazione, 4 frame): 6 fault

All'istante 0 sono già caricate le pagine 0, 1, 2, 3 nei frame $f_0,\ldots,f_3$ (con 0 la meno recente, 3 la più recente).

• $t=1$: la 15 non c'è; la meno recente è la 0, nel frame $f_0$: la 15 va in $f_0$.
• $t=3$: la 0 è appena stata scacciata, quindi è un fault; la meno recente è la 1 ($f_1$).
• $t=6$: la 11 sostituisce la meno recente tra 15 (usata a $t=2$), 0, 2, 3: è la 15.
• $t=8,9,10$: le pagine 6, 4, 14 sostituiscono rispettivamente 0, 3 e 11.

Totale: 6 fault (le due soluzioni del corso, per 40 e per 57, coincidono).

Esercizio 48 (FIFO, 4 frame): 6 fault

I primi quattro accessi riempiono i frame; il 3 sostituisce la più vecchia (0); 7, 4, 1 sono hit; lo 0 sostituisce la più vecchia, l'1; il 3 è un hit. Totale: 6 fault.

Esercizio 58 (OPT, 3 frame): 6 fault

• $t=5$ (la 7): in memoria 6, 2, 12; il prossimo uso è: 2 a $t=6$, 12 a $t=8$, 6 a $t=10$. Si toglie la 6 (la più lontana).
• $t=7$ (lo 0): tra 7 (mai più), 2 (a $t=9$), 12 (a $t=8$) si toglie il 7, perché non serve più.
• $t=10$ (la 6): nessuna delle pagine in memoria sarà più usata: si può scegliere un frame qualsiasi ($f_0$).

(1) 6 fault. (2) Con più frame i fault non possono aumentare e possono diminuire: OPT non ha l'anomalia di Belady (è un algoritmo a pila). Con 4, 5 o più frame i fault scendono a 5 (con 3 frame: 6; con 2: 7; con 1: 9): il numero minimo di fault è il numero di pagine distinte. (3) No: questa proprietà di OPT vale per qualsiasi stringa. (Si possono confrontare le conclusioni con quelle di un algoritmo che soffre dell'anomalia, come FIFO.)

Errore nella soluzione del corso. La soluzione scrive che il numero minimo di fault è "pari a sei", il numero di pagine diverse. In realtà le pagine distinte sono cinque (6, 2, 12, 7, 0), quindi il minimo possibile è 5 (si raggiunge con 5 o più frame, come mostra il conto).

Esercizio 80 (5 frame): LRU 8, OPT 7

La stringa 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

LRU (8 fault)

OPT (7 fault)

Variando i frame (soluzione del corso, verificata):

OPT è sempre il minimo e LRU sta fra OPT e FIFO.

Un simulatore in C

Il programma simula le tre politiche sulla stessa stringa e stampa a ogni riferimento il contenuto dei frame. Si compila con gcc -Wall -Wextra -o replace replace.c (compilato qui con zig cc per Linux, senza avvisi; non eseguito).

/* replace.c - simula FIFO, LRU e OPT su una stringa di riferimenti.
 * Compilare:  gcc -Wall -Wextra -o replace replace.c
 * Usare:      ./replace 3 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1
 *             (il primo numero e' quello dei frame, gli altri sono i riferimenti)
 */
#include <stdio.h>
#include <stdlib.h>

#define MAXF 16

static int cerca(const int *fr, int n, int pagina) {
    for (int i = 0; i < n; i++)
        if (fr[i] == pagina) return i;
    return -1;
}

/* politica: 'F' = FIFO, 'L' = LRU, 'O' = OPT. Restituisce i page fault. */
static int simula(char politica, int nframe, const int *rif, int len) {
    int fr[MAXF];       /* pagina contenuta in ogni frame */
    int caricata[MAXF]; /* istante in cui la pagina e' stata caricata (per FIFO) */
    int usata[MAXF];    /* istante dell'ultimo accesso (per LRU) */
    int usati = 0, fault = 0;

    printf("%c  rif  frame\n", politica);
    for (int t = 0; t < len; t++) {
        int p = rif[t];
        int i = cerca(fr, usati, p);
        int errore = (i < 0);
        if (errore) {
            fault++;
            if (usati < nframe) {
                i = usati++;                       /* c'e' un frame libero */
            } else if (politica == 'F') {
                i = 0;                             /* la piu' vecchia in memoria */
                for (int k = 1; k < usati; k++)
                    if (caricata[k] < caricata[i]) i = k;
            } else if (politica == 'L') {
                i = 0;                             /* la meno recentemente usata */
                for (int k = 1; k < usati; k++)
                    if (usata[k] < usata[i]) i = k;
            } else {                               /* OPT: il prossimo uso piu' lontano */
                int lontano = -1;
                i = 0;
                for (int k = 0; k < usati; k++) {
                    int j = t + 1;
                    while (j < len && rif[j] != fr[k]) j++;   /* j == len: mai piu' usata */
                    if (j > lontano) { lontano = j; i = k; }
                }
            }
            fr[i] = p;
            caricata[i] = t;
        }
        usata[i] = t;
        printf("   %3d ", p);
        for (int k = 0; k < usati; k++) printf(" %3d", fr[k]);
        printf("%s\n", errore ? "   <- page fault" : "");
    }
    printf("page fault: %d\n\n", fault);
    return fault;
}

int main(int argc, char **argv) {
    if (argc < 3) {
        fprintf(stderr, "uso: %s nframe rif1 rif2 ...\n", argv[0]);
        return 1;
    }
    int nframe = atoi(argv[1]);
    int len = argc - 2;
    if (nframe < 1 || nframe > MAXF) {
        fprintf(stderr, "nframe deve stare fra 1 e %d\n", MAXF);
        return 1;
    }
    int *rif = malloc((size_t)len * sizeof *rif);
    if (!rif) return 1;
    for (int i = 0; i < len; i++) rif[i] = atoi(argv[i + 2]);

    simula('F', nframe, rif, len);
    simula('L', nframe, rif, len);
    simula('O', nframe, rif, len);
    free(rif);
    return 0;
}

Con ./replace 4 2 6 3 2 9 10 9 3 11 12 3 2 (esercizio 38) il programma dà, per la riga FIFO, page fault: 9 e per LRU e OPT rispettivamente 8 e 7. Questi numeri sono stati controllati con una simulazione equivalente in Python; per il caso FIFO l'ultima riga di frame è 2 11 12 3 (lo stesso che nella tabella sopra, letto per colonna).

Come funziona la scelta della vittima: in FIFO caricata[k] conserva l'istante del caricamento e non viene aggiornato dagli hit; in LRU usata[i] = t si aggiorna a ogni accesso, hit compresi. In OPT si cerca in avanti nella stringa il primo uso di ciascuna pagina; se non c'è, $j=\text{len}$ e quella pagina vince (è la più lontana).

Errori tipici

• Aggiornare in FIFO l'ordine con gli hit (è una caratteristica di LRU).
• Contare un fault quando la pagina è già presente.
• Con la prepaginazione, partire dai frame vuoti e non dalle pagine 0-3 già caricate.
• Scegliere in OPT in base al passato invece che al futuro.
• Dire che aumentando i frame i fault non diminuiscono mai di meno: vale per LRU e OPT, non per FIFO (anomalia di Belady).