Modulo 5: Gestione della memoria

Algoritmi di rimpiazzamento

Obiettivi

• minimizzare il numero di page fault

Valutazione

• gli algoritmi vengono valutati esaminando come si comportano quando applicati ad una stringa di riferimenti in memoria

Le stringhe di riferimenti possono essere generate esaminando il funzionamento di programmi reali o con un generatore di numeri random

Nota: la stringa di riferimenti può essere limitata ai numeri di pagina, in quanto non siamo interessati agli offset. Esempio:

• stringa di riferimento completa (in esadecimale):
  • 71,0a,13,25,0a,3f,0c,4f,21,30,00,31,21,1a,2b,03,1a,77,11
• stringa di riferimento delle pagine (in esadecimale, con pagine di 16 byte)
  • 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,1

Algoritmo FIFO

Descrizione

• quando c’è necessità di liberare un frame viene individuato come “vittima” il frame che per primo fu caricato in memoria

Vantaggi

• semplice, non richiede particolari supporti hardware

Svantaggi

• vengono talvolta scaricate pagine che sono sempre utilizzat

Esempio:

• numero di frame in memoria: 3
• numero di page fault: 15 (su 20 accessi in memoria)

• numero di frame in memoria: 3
• numero di page fault: 9 (su 12 accessi in memoria)

• numero di frame in memoria: 4
• numero di page fault: 10! (su 12 accessi in memoria)
• il numero di page fault è aumentato!

Anomalia di Belady

In alcuni algoritmi di rimpiazzamento non è detto che aumentando il numero di frame il numero di page fault diminuisca (e.g., FIFO). Questo fenomeno indesiderato si chiama Anomalia di Belady

Algoritmo MIN - Ottimale

Descrizione

• seleziona come pagina vittima una pagina che non sarà più acceduta o la pagina che verrà acceduta nel futuro più lontano

Considerazioni

• è ottimale perché fornisce il minimo numero di page fault
• è un algoritmo teorico perché richiederebbe la conoscenza a priori della stringa dei riferimenti futuri del programma
• viene utilizzato a posteriori come paragone per verificare le performance degli algoritmi di rimpiazzamento reali

Esempio:

• numero di frame in memoria: 3
• numero di page fault: 9 (su 20 accessi in memoria)

Algoritmo LRU (Least Recently Used)

Descrizione - seleziona come pagina vittima la pagina che è stata usata meno recentemente nel passato

Considerazioni

• è basato sul presupposto che la distanza tra due riferimenti successivi alla stessa pagina non vari eccessivamente
• stima la distanza nel futuro utilizzando la distanza nel passato

Esempio

• numero di frame in memoria: 3
• numero di page fault: 12 (su 20 accessi in memoria)

Implementazione LRU

Nota: E' necessario uno specifico supporto hardware

La MMU:

• deve registrare nella tabella delle pagine un time-stamp quando accede ad una pagina
• il time-stamp può essere implementato come un contatore che viene incrementato ad ogni accesso in memoria

Nota:

• bisogna gestire l'overflow dei contatori (wraparound)
• i contatori devono essere memorizzati in memoria e questo richiede accessi addizionali alla memoria
• la tabella deve essere scandita totalmente per trovare la pagina LRU

Implementazione basata su stack

• si mantiene uno stack di pagine
• tutte le volte che una pagina viene acceduta, viene rimossa dallo stack (se presente) e posta in cima allo stack stesso
• in questo modo:
  • in cima si trova la pagina utilizzata più di recente
  • in fondo si trova la pagina utilizzata meno di recente

Nota:

• l'aggiornamento di uno stack organizzato come double-linked list richiede l'aggiornamento di 6 puntatori
• la pagina LRU viene individuata con un accesso alla memoria
• esistono implementazioni hardware di questo meccanismo

Algoritmi a stack

Definizione: Data una stringa di riferimenti s, si indichi con $S_t(s,A,m)$ l'insieme delle pagine mantenute in memoria centrale al tempo $t$ dell'algoritmo $A$, data una memoria di $m$ frame relativamente alla stringa $s$. Un algoritmo di rimpiazzamento vien detto "a stack" se per ogni istante $t$ e per ogni stringa $s$ si ha: $S_t(s,A,m)\subset S_t(s,A,m+1)$

In altre parole

• se l'insieme delle pagine in memoria con m frame è sempre un sottoinsieme delle pagine in memoria con m+1 frame
• Per ogni stringa per ogni tempo per ogni ampiezza di memoria

Teorema: un algoritmo a stack non genera casi di Anomalia di Belady

Teorema: l'algoritmo di LRU è a stack: Ogni riferimento della stringa dei riferimenti sposta la pagina acceduta in cima allo stack, facendo scorrere le successive come indicato nella figura a lato. L’algoritmo LRU tiene in memoria le m pagine in cima allo stack. L’algoritmo è a stack: l’insieme delle m pagine in cima allo stack è un sotto insieme delle m+1 pagine in cima allo stack.

Stack degli algoritmi di rimpiazzamento: caso generale

Ogni riferimento della stringa dei riferimenti sposta la pagina acceduta in cima allo stack. Le pagine scorrono a seconda della loro importanza. L’algoritmo tiene in memoria le m pagine in cima allo stack  La relazione d’ordine deve dipendere solo dalla stringa di riferimenti e da t

Algoritmo LRU - Implementazione

Mantenere le informazione per LRU è troppo costoso Poche MMU forniscono il supporto hardware per l'algoritmo LRU, alcuni sistemi non forniscono alcun tipo di supporto, e in tal caso l'algoritmo FIFO deve essere utilizzato.

Reference bit:

• alcuni sistemi forniscono supporto sotto forma di reference bit
• tutte le volte che una pagina è acceduta, il reference bit associato alla pagina viene aggiornato a 1

Come utilizzare il reference bit:

• inizialmente, tutti i bit sono posti a zero dal s.o.
• durante l'esecuzione dei processi, le pagine in memoria vengono accedute e i reference bit vengono posti a 1
• periodicamente, è possibile osservare quali pagine sono state accedute e quali non osservando i reference bit

Nota: non conosciamo l'ordine in cui sono state usate le pagine ma possiamo comunque usare queste info per **approssimare un algoritmo LRU

Approssimare LRU: Additional-Reference-Bit-Algorithm

• possiamo aumentare le informazioni di ordine "salvando" i reference bit ad intervalli regolari (ad es., ogni 100 ms)
• esempio: manteniamo 8 bit di "storia" per ogni pagina
• il nuovo valore del reference bit viene salvato tramite shift a destra della storia ed inserimento del bit come most signif. bit
• la pagina vittima è quella con valore minore; in caso di parità, si utilizza una disciplina FIFO

Second-chance algorithm

Conosciuto anche come algoritmo dell'orologio, corrisponde ad un caso particolare dell'algoritmo precedente, dove la dimensione della storia è uguale a 1

Descrizione

• le pagine in memoria vengono gestite come una lista circolare
• a partire dalla posizione successiva all'ultima pagina caricata, si scandisce la lista con la seguente regola
• se la pagina è stata acceduta (reference bit a 1)
  • il reference bit viene messo a 0
• se la pagina non è stata acceduta (reference bit a 0)
  • la pagina selezionata è la vittima

l'idea è semplice:

• l'algoritmo seleziona le pagine in modo FIFO
• se però la pagina è stata acceduta, gli si dà una "seconda possibilità" (second chance);
• si cercano pagine successive che non sono state accedute

Se tutte le pagine sono state accedute, degenera nel meccanismo FIFO

Implementazione:

• semplice da implementare
• non richiede capacita' complesse da parte della MMU

Esempio

Altri algoritmi di rimpiazzamento

Least frequently used (LFU)

• Si mantiene un contatore di accessi ad una pagina
• La frequenza e' il valore del contatore diviso per il "tempo" di permanenza in memoria (es. il numero di accessi con quella pagina presente)
• la pagina con il val minore viene scelta come vittima

Motivazioni:

• una pagina utilizzata spesso dovrebbe avere un contatore molto alto

Implementazione:

• puo' essere approssimato tramite reference bit

Problemi

• se una pagina viene utilizzata frequentemente all'inizio e poi non viene piu usata verra' rimossa dopo molto tempo.

Allocazione

Algoritmo di allocazione (per memoria virtuale): si intende l'algoritmo utilizzato per scegliere quanti frame assegnare ad ogni singolo processo

Allocazione locale

• ogni processo ha un insieme proprio di frame
• poco flessibile

Allocazione globale

• tutti i processi possono allocare tutti i frame presenti nel sistema (sono in competizione)
• può portare a trashing

Trashing

Un processo (o un sistema) si dice che è in trashing quando spende più tempo per la paginazione che per l'esecuzione

Cause:

• in un sistema con allocazione globale, si ha trashing se i processi tendono a "rubarsi i frame a vicenda".Ovvero non riescono a tenere in memoria i frame utili a breve termine (perchè altri processi chiedono frame liberi) e quindi generano page fault ogni pochi passi di avanzamento

Esempio: Esaminiamo un sistema che accetti nuovi processi quando il grado di utilizzazione della CPU è basso, se per qualche motivo gran parte dei processi entrano in page fault:

• la ready queue si riduce
• il sistema sarebbe indotto ad accettare nuovi processi….
• E' UN ERRORE!

statisticamente, il sistema:

• genererà un maggior numero di page fault
• di conseguenza diminuirà il livello della multiprogrammazione

Working set

Definizione: si definisce working set di finestra Δ l'insieme delle pagine accedute nei più recenti $\delta$ riferimenti

Considerazione

• è una rappresentazione approssimata del concetto di località
• se una pagina non compare in $\delta$ riferimenti successivi in memoria, allora esce dal working set; non è più una pagina su cui si lavora attivamente

Esempio: $\delta$ = 5

Se l'ampiezza della finestra è ben calcolata, il working set è una buona approssimazione dell'insieme delle pagine "utili"… Sommando quindi l'ampiezza di tutti i working set dei processi attivi, questo valore deve essere sempre minore del numero di frame disponibili, altrimenti il sistema è in trashing

Se si sceglie un set ($\delta$) troppo piccolo:

• si considera non più utile ciò che in realtà serve
• Si sottovaluta il numero di pagine necessarie per il processo
• Falsi negativi di trashing

Se si sceglie un set ($\delta$) troppo grande:

• si considera utile anche ciò che non serve più
• Si sopravaluta il numero di pagine necessarie
• Falsi positivi di trashing

Come si usa il Working Set:

• serve per controllare l'allocazione dei frame ai singoli processi
• quando ci sono sufficienti frame disponibili non occupati dai working set dei processi attivi, allora si può attivare un nuovo processo
• se al contrario la somma totale dei working set supera il numero totale dei frame, si può decidere di sospendere l'esecuzione di un processo