Gestione della Memoria

Testi di riferimento:
Tanenbaum, Cap. 4
Peterson Silbershatz cap. 5 e 6
Deitel cap. 7,8,9
Brinch Hansen cap. 5 paragrafi 3 e 4

Cosa significa Gestione della Memoria

Algoritmi che consentono un utilizzo efficiente della risorsa "memoria":

tracciano quale parte è utilizzata e quale è libera;
concedono memoria ai processi che la richiedono;
scaricano su disco (e ricaricano) parti di memoria quando essa non basta.

Tengono conto di:

• caratteristiche dell’architettura sottostante
• caratteristiche degli ambienti di programmazione:
• • compilatore
  • linker
  • loader
  • codice eseguibile

Evoluzione "storica" dei gestori della memoria:

Macchina "nuda" ovvero: assenza del memory manager

• i programmi accedono a tutto lo spazio di memoria disponibile
• i compilatori generano codice assoluto (no rilocazione)

uso: semplici sistemi dedicati

Monitor residente, monoprogrammazione:

La parte "bassa" della memoria è dedicata al sistema operativo; il rimanente è per l’utente. Su alcune macchine invece il contrario: il monitor occupa le memorie "alte", ad es. perché vi sono i vettori di interruzione. Per MS-DOS, lo schema invece prevede di utilizzare la parte bassa della memoria (driver dei periferici, in ROM, detti BIOS) e la parte alta, in RAM, per il sistema vero e proprio.

Protezione: Un registro speciale, fence, marca il valore "limite" per gli indirizzi utente. In questo modo accessi errati al monitor da parte dei programmi utente possono venire bloccati. Il monitor invece può accedere a tutta la memoria disponibile e può modificare il valore di fence.

Rilocazione: Se la dimensione del monitor (quindi il valore di fence) è nota a tempo di compilazione, si può generare codice con indirizzi assoluti, a partire da fence +1. In alternativa, il codice sarà rilocabile, e verrà rilocato dal loader (ad es. sommando il valore attuale di fence a tutti gli indirizzi presenti nel codice).

Una alternativa al fence è rappresentata dal registro di rilocazione o registro base. I programmi utente generano indirizzi a partire da 0; ogni accesso a memoria è "traslato" del valore contenuto nel registro di rilocazione. Il programma utente usa quindi indirizzi logici, che l’hardware trasforma in indirizzi fisici.

Il monitor invece può

• accedere a ogni locazione di memoria con l’indirizzo fisico;
• assegnare i valori al registro base
• tradurre gli indirizzi utente (ad es. accedere a parametri delle system call)

Partizioni multiple

In memoria risiedono contemporaneamente più programmi utente; il controllo passa dall’uno all’altro quando uno di essi si blocca per richiedere operazioni di I/O. In questo modo mentre i periferici eseguono l’I/O, la CPU lavora per altri processi e risulta occupata per una maggior quantità di tempo.

Vediamo di quantificare tale guadagno:

Supponiamo di avere in memoria 5 processi che usano la CPU ciascuno per il 20% del proprio tempo, e per l’80% del tempo usano l’I/O (questo è un comportamento tipico per processi interattivi, cioè che attendono che l’utente digiti dei comandi alla tastiera). SE potessimo sempre sovrapporre perfettamente i tempi di I/O di quattro con il tempo di CPU di uno, la CPU sarebbe utilizzata al 100%!

In realtà ci saranno dei momenti in cui tutti saranno in attesa di I/O, in generale dati n processi, se p è la percentuale di tempo di I/O di ciascun processo, la CPU sarà inattiva quando tutti e n saranno in attesa di I/O, con probabilità pⁿ . La CPU quindi sarà utilizzata per una percentuale di tempo pari a 1-pⁿ.

La memoria viene divisa in un certo numero di regioni, dette partizioni, in ciascuna delle quali può risiedere un programma. Se la regione è libera, verrà scelto un programma tra quelli in coda che possa essere caricato ed eseguito lì. Al termine di tale programma, la regione torna libera.

La scelta delle partizioni può essere:

• statica, ovvero compiuta una volta per tutte, al caricamento del sistema operativo (o alla sua compilazione);
• dinamica, ovvero il numero e la dimensione delle partizioni può variare a seconda delle richieste al sistema.

Il primo sistema operativo in cui queste strategie furono realizzate fu il "famoso" OS/360 dell’IBM (anni ’60), le due versioni del sistema si chiamavano rispettivamente

• MFT (Multiprogramming with Fixed number of Tasks) e
• MVT (Multiprogramming with Variable number of Tasks).

Questi due nomi sono rimasti per identificare le due strategie. L’ambiente tipico prevedeva un carico batch ed eventualmente anche processi interattivi.

Protezione: E’ necessario proteggere la partizione di ogni utente da accessi da parte degli altri utenti, allo scopo si usano due registri.

• Upper bound e lower bound: gli indirizzi fisici del programma sono confrontati con i due indirizzi ivi contenuti
• Base e limite: gli indirizzi del programma sono offset, confrontati col valore limite, e sommati al valore base.

MFT

Né il numero né le dimensioni delle partizioni cambiano in esecuzione. Quando un processo entra nel sistema, esso viene classificato come adatto ad una partizione (in genere in base alla sua dimensione) e posto in coda per tale partizione. Al suo turno, verrà rilocato, caricato in memoria ed eseguito (in multiprogrammazione con i processi delle altre partizioni). Al termine lascerà il posto al processo in coda sulla stessa partizione.

Esempio: tre partizioni (e tre code)

La coda Q2 contiene i processi piccoli, di dimensione minore di 2K
La coda Q6 contiene i processi medi, di dimensione tra 2K e 6K
La coda Q12 contiene i processi grandi, di dimensione tra 6K e 12K.

Problema: nella situazione della figura, supponiamo che i processi in coda Q12 terminino molto rapidamente, mentre in coda Q6 ci sono ancora processi presenti. Sarebbe allora vantaggioso poter eseguire il processo da 3K nella partizione da 12K, ma questa tecnica non lo consente!

Una strategia alternativa è quella in cui il sistema gestisce una sola coda da cui preleva i processi. Quando una partizione si libera, viene scelto un processo adatto per quella partizione (a partire dal primo della coda, ma se non adatto si passa al secondo ecc.)

In questo caso supponiamo di partire con il sistema vuoto e la coda Q che contiene i processi sopra elencati nell’ordine. Il processo P1 può partire nella partizione 2, il processo P2 può partire nella partizione 1.

Dopodiché si può fare:

• best fit only: si sceglie P4 per la partizione 3 (e P3 attende la fine di P1)
• best available fit: si carica P3 nella partizione 3

NON si può invece caricare nella partizione 3 sia P3 sia P4!!!

Problema fondamentale: quante e quanto grandi sono le partizioni?

La scelta iniziale è fatta in base a una stima del carico "tipico" del sistema. Raccogliendo informazioni (statistiche di utilizzo) si può periodicamente valutare la bontà di tale scelta ed eventualmente modificarla (compiendo una modifica del sistema operativo).

Frammentazione

Un processo richiede m posizioni di memoria, e viene eseguito in una partizione di dimensione n. La quantità n-m è detta frammentazione interna e rappresenta la memoria non usata in una partizione "occupata".

Se invece una partizione è inutilizzata, ma sono presenti in coda processi (non adatti al caricamento, ad es. perché è una partizione troppo piccola), si parla di frammentazione esterna, cioè di memoria di sistema non utilizzata.

MFT presenta tutti e due i tipi di frammentazione.

Vediamolo su un esempio. Abbiamo quattro partizioni (quindi al più 4 processi presenti in memoria)

La coda dei processi contiene:

Allocazione possibile:

Totale inutilizzati 12K, utilizzo della memoria: 10K/22K = 45% circa

Supponendo invece di avere:

• la stessa coda di processi
• una strategia di scheduling "best available fit"
• le partizioni:

era possibile l’allocazione:

Totale inutilizzati 6K, utilizzo della memoria 16K/22K = 73% circa (e multiprogrammazione superiore!)

Questo esempio mostra come sia difficile scegliere "bene" le partizioni e quale inefficienza si può ricavare da una scelta sbagliata.

MVT

Inizialmente il sistema parte con una unica zona libera per i programmi utente. Quando arriva un processo, si cerca una zona libera che possa contenerlo. Se la zona che lo contiene ha dimensione maggiore di quella necessaria al processo, rimane una porzione ancora libera.

Esempio: situazione iniziale:

Supponiamo che arrivino nell’ordine i processi:

La memoria libera ci consente di attivare P1, P2, P3. (i disegni seguenti non sono "in scala"!)

Non abbiamo (mai!) frammentazione interna, la frammentazione esterna è 26K, l’utilizzo 90%.
Supponendo che i processi "avanzino" alla stessa velocità, il primo a terminare sarà P2. Nella zona liberata subentra P4.

Frammentazione esterna=56K; utilizzo=78%.
Le due zone di memoria libere non sono contigue, quindi anche se ho più di 50K liberi, non riesco ad allocare il processo P5.

In generale, si formeranno più zone di memoria libere (hole) non contigue. All’arrivo di un processo, si cercherà una(*) zona sufficiente a contenerlo, e rimarrà una ulteriore zona libera, più piccola. Al termine di un processo, la zona che occupava dovrà essere considerata libera, ed eventualmente "immersa" in zone libere adiacenti.

(*) Strategie per la gestione degli hole: utilizzando liste

• First fit: mantengo una lista delle zone libere in ordine di indirizzo; all’arrivo del processo lo si alloca nel primo spazio libero sufficiente.
• Best fit: mantengo una lista delle zone libere in ordine crescente di dimensione; all’arrivo del processo lo si alloca nel primo spazio libero sufficiente (quindi nel più piccolo spazio sufficiente).
• Worst fit: mantengo una lista delle zone libere in ordine decrescente di dimensione; all’arrivo del processo lo si alloca nel primo spazio libero (se sufficiente).

Esempio: Supponiamo che arrivi il processo P che occupa 13K mentre la memoria è in questa situazione:

First fit:
la lista delle zone libere è: (a,16K), (c,14K), (e,5K), (g,30K)
à Alloco a partire da a e rimangono 3K liberi

Best fit:
la lista delle zone libere è: (e,5K), (c,14K), (a,16K), (g,30K)
à Alloco a partire da c e rimane 1K libero

Worst fit:
la lista delle zone libere è: (g,30K), (a,16K), (c,14K), (e,5K)
à Alloco a partire da g e rimangono 17K liberi

Note:

• Si può implementare MFT e MVT sulla stessa architettura
• Può esserci (poca) frammentazione interna anche per MVT:

esempio: un processo richiede 18460 bytes, c’è una zona libera di 18470 bytes. In genere non si lascia una zona libera di 10 bytes, bensì al di sotto di una certa "taglia minima" l’intera zona si marca come occupata. Nel OS/360 tale "taglia minima" necessaria a poter inserire un processo era stimata a 2K.

In generale MVT dà risultati migliori di MFT in termini di utilizzo.
La scelta tra best-, first-, e worst-fit dipende dalle caratteristiche tipiche dei processi. Nessuna delle tre tecniche è in grado di eliminare la frammentazione esterna.

Compattazione

Tecnica che elimina la frammentazione esterna rendendo adiacenti tutte le zone libere, dopo aver spostato le aree occupate (cioè i processi). E’ possibile solo se si può fare rilocazione dinamica per hardware. Gli algoritmi sono costosi e raffinati.

Esempio: Da una situazione iniziale (figura di sinistra) vediamo tre diverse strategie di compattazione e i relativi costi.

La prima strategia trasla 600K(processi 3 e 4), la seconda 400K(il solo processo 4), la terza 200K(il solo processo 3: lo spazio libero è "in mezzo" a processi adiacenti)

In alcune macchine, per diminuire la frammentazione esterna, la zona di memoria di un processo si divide in:

• area read-only (istruzioni, costanti, ...)
• area read-write (dati, stack, ...)

Vantaggi:

• è più facile trovare due zone libere "piccole" di una grande;
• è possibile per più processi condividere un’area codice ed avere area dati separata (es. compilatore, editor, ...)

Sono necessari:

• due coppie di registri per processo;
• protezione hardware per zone read-only;
• software per generare due aree per processo (compilatore, assemblatore, linker, ...)

Swapping

Una estensione di MVT consente di gestire più efficacemente diversi utenti in time-sharing: ad intervalli fissati (dallo scheduler), il contenuto della memoria utente è ricopiato su un disco (detto backing store) e dallo stesso disco si ricupera il contenuto della memoria di un altro processo utente, il quale viene così riattivato. Il backing store è un disco utilizzato esclusivamente per la gestione dei processi, e non per la gestione di file (sovente può essere una partizione di un grande disco fisso).

Nella figura seguente l'operazione di swap è illustrata in due fasi, la memoria è a sinistra e il backing store a destra (consideriamo il caso di uno scambio tra due processi, tralasciando gli altri):

1: swap out dell’utente A;
2: swap in dell’utente B.

• Il monitor deve mantenere una coda di processi ready le cui immagini sono nel backing store.
• Il backing store deve essere sufficientemente grande per contenere le immagini di tutti i possibili processi utente, e sufficientemente veloce per svolgere swap in e swap out in tempi "ragionevoli".

Questa tecnica può anche servire per realizzare una forma di compattazione tramite swap out – swap in ad altri indirizzi.

Paginazione

La paginazione elimina la necessità di avere grandi spazi di memoria contigui per caricarvi i processi: consente infatti di sfruttare zone non contigue per allocare i processi (e di fatto, annulla la necessità di compattazione). Essa però richiede un apposito hardware per la gestione della memoria (al giorno d’oggi detto MMU).

Terminologia:

• indirizzi logici divisi in page number ed offset (nella pagina);
• frame unità di gestione della memoria fisica
• page table struttura che memorizza la corrispondenza tra frame e numeri di pagina

Attenzione: ogni processo avrà una page table diversa dagli altri. Infatti alla pagina 0 del processo P1 corrisponde un frame diverso da quello della pagina 0 del processo P2!

I registri (nella MMU) dedicati a contenere la page table (in tutto, in parte, o "puntatori" per accedervi) verranno caricati con la page table del processo attivo (cambiandola ad ogni switch di contesto). La MMU così traduce ad ogni accesso alla memoria gli indirizzi logici in indirizzi fisici.

Possono inoltre essere presenti particolari dispositivi per velocizzare l’accesso alle pagine di uso più frequente del processo attivo (TLB). Infatti, in caso di tabelle delle pagine molto grandi, esse verranno per lo più mantenute in memoria fisica, caricando nel TLB solo le corrispondenze di uso più frequente, in numero fisso e solitamente piccolo.

Il sistema operativo solitamente mantiene una "lista" dei frame liberi (unica nel sistema). Può accedere alle page table dei processi se ad es. deve calcolare gli indirizzi fisici dei parametri di una system call (passati come indirizzi logici entro il processo).

Protezione

Ad ogni pagina si associa (almeno) un bit di protezione:

• pagina read-only
• pagina read/write

Sovente i bit di protezione sono tre, ciascuno che abilita o non abilita una funzione tra read-write-execute. Non tutte le combinazioni di valori sono "sensate, ma le seguenti si:

I bit di protezione si associano alle pagine nella page table (del processo). Un tentativo di accesso per operazione non consentita (es. uso di puntatore scorretto) causa una TRAP.

Memoria virtuale

Tecniche per eseguire processi che non sono interamente contenuti in memoria.

Metodo fondamentale è la Paginazione a richiesta (demand paging). Supponiamo di avere un backing store che implementa lo swapping, ma dotato di swapper pigro: non si caricano le pagine in memoria fintantoché non è richiesto il loro contenuto. In ogni istante, è presente in memoria solo un sottoinsieme delle pagine del processo (ma tutta la sua page table è accessibile).

Al primo tentativo di usare una pagina non presente in memoria (in particolare questo capita per la prima istruzione di ogni programma, che inizialmente starà tutto sul backing store) la page table non riesce a tradurre l’indirizzo logico in indirizzo fisico: TRAP pagina non valida (page fault).

La pagina necessaria verrà allora copiata in memoria (in un frame libero) e nel frattempo il processo sarà mantenuto in coda, considerato in attesa di I/O, e si eseguirà un altro processo.

Quando la pagina sarà stata caricata, il processo potrà essere mandato in esecuzione. La figura mostra la situazione dopo un certo tempo dall’avvio del processo 1, ma lo stesso schema vale per tutti i processi in multiprogrammazione.

Nella figura vediamo solo le pagine del processo 1 caricate nella memoria fisica. Altri frame conterranno altri processi, il sistema operativo, oppure potrebbero essere vuote.

Supponiamo che per hardware servano 3 bit per indirizzare la pagina (valori 0-7).

• Se un processo necessita di meno pagine, in corrispondenza nella page table porremo il bit "invalido" (caso delle pagine 6 e 7, che non esistono). Un tentativo di accedere a queste pagine provoca una trap ("indirizzo inesistente").

• Se invece si tenta di accedere alla pagina "B" nessun frame è associato ad essa perché è ancora nel backing store: ancora presenza di bit "invalido" e di conseguenza trap ("page fault").

NOTA: per "riferimento" alla pagina B intendiamo un qualsiasi indirizzo in cui i bit di pagina individuano B (quindi sono 001) e l’offset è qualsiasi, per istruzioni di lettura, di scrittura, o per fetch di istruzioni.

Vediamo ad esempio:

1. una "load" provoca una decodifica di indirizzo di B tramite la page table
2. il bit "invalido" causa la trap
3. il sistema “ricupera” la pagina dal backing store
4. la pagina è ricopiata in un frame libero

Al termine del caricamento, la entry relativa a B nella page table è aggiornata con il frame occupato e il bit "valido".

Osservazione: al punto 2, potremmo non avere un frame libero, situazione illustrata qui sotto.

In questo caso occorre:

• swap out di un intero processo dalla memoria, diminuendo il livello di multiprogrammazione,

oppure

• swap out di una pagina per creare un frame libero.

Questa seconda soluzione è detta Page Replacement.

Prima del punto (2) occorre quindi svolgere le seguenti azioni:

a) Verificare se esiste un frame libero, altrimenti attivare un algoritmo di page replacement per la scelta di una pagina vittima
b) Scrivere la pagina vittima sul backing store e aggiornare la page table della pagina vittima.

Osservazione: Lo swap out della pagina vittima potrebbe non essere necessario, se ad es. siamo certi che non è stata modificata rispetto alla copia presente sul backing store (ad es. una pagina di codice). Perciò la page table sovente memorizza se sono state fatte modifiche alla pagina in memoria in un apposito campo detto dirty bit o modified bit.

I campi della page table in generale variano da MMU a MMU, ma uno schema tipico potrebbe essere:

Differenza tra paginazione "pura" e paginazione a richiesta:

• la paginazione "pura" è una corrispondenza biunivoca tra indirizzi logici e indirizzi fisici;
• la paginazione a richiesta elimina la necessità di una corrispondenza totale ed è definita "istante per istante", infatti la traduzione di un indirizzo logico può essere indefinita (se la pagina non è in memoria) o definita con valori diversi in diversi momenti dell’esecuzione del processo.

Nel caso della paginazione a richiesta useremo il termine indirizzo virtuale (anziché logico) e diremo che un sistema che implementa la paginazione a richiesta supporta la memoria virtuale.

Algoritmi di Page Replacement

Vi sono due problemi da risolvere per ogni sistema che realizza la paginazione a richiesta:

1. Criteri per stabilire quante pagine assegnare a ogni processo (e di conseguenza quale è il grado di multiprogrammazione del sistema): Frame Allocation
2. Algoritmi per scegliere una pagina vittima, in modo che si abbia una frequenza di page fault più bassa possibile: Page Replacement.

Partiamo da questi ultimi.

Per confrontare tra loro vari algoritmi si sceglie di solito una stringa di riferimenti a pagina, costruita da una sequenza di riferimenti a memoria (veri o generati artificialmente) così semplificata:

• si memorizzano solo i riferimenti a pagina (eliminazione offset)
• si eliminano tutti i riferimenti consecutivi a una stessa pagina, tenendo solo il primo.

Negli esempi seguenti useremo la stringa:

e supporremo che il processo abbia a disposizione soltanto 3 frame.

Algoritmo FIFO

L’ elenco delle pagine è mantenuto in ordine di caricamento in memoria. Quando occorre sostituire una pagina, la pagina vittima è quella inserita "per prima" quindi in memoria da più tempo.

La struttura che mantiene l’elenco delle pagine è una coda FIFO. La tabella mostra il contenuto della coda (=colonna, con "head" in alto e "tail" in basso). Un asterisco marca i page fault.

Osserviamo 12 page fault sulla stringa di esempio, a cui occorre aggiungere i tre page fault iniziali per caricare le prime tre pagine.

Questo algoritmo potrebbe essere inefficiente rispetto ad altri che vedremo, ma la struttura è semplice da gestire. Inoltre la gestione della coda avviene "durante" i page fault.

Contrariamente all’intuizione, non è detto che allocando più pagine a un processo il numero di page fault diminuisca. Il fenomeno è detto Anomalia di Belady e si verifica ad esempio per la seguente stringa:

Si lascia per esercizio di verificare che:

• con tre frame disponibili si verificano 9 page fault;
• con quattro frame disponibili si verificano 10 page fault.

Algoritmo ottimo (OPT)

L’algoritmo sostituisce la pagina che non verrà richiesta per il tempo più lungo: nessun algoritmo può fare di meglio!

In questo caso vi sono soltanto 6 page fault. Per funzionare però ci vuole la ‘conoscenza del futuro’! Può servire come termine di confronto con gli altri algoritmi.

Algoritmo Least Recently Used (LRU)

Sceglie come pagina vittima quella che non è stata usata da più lungo tempo. Si suppone infatti che il "futuro" possa essere simile al "passato", ovvero che una pagina non usata da tempo non verrà più usata, e una usata di recente servirà ancora tra breve.

Se ordino la coda di pagine in funzione dell’utilizzo più recente, l’esempio diventa:

Vi sono quindi 9 page fault.

Come si può implementare l’algoritmo, mantenendo efficientemente la coda ordinata per utilizzo più recente?

Una idea potrebbe essere quella di memorizzare il clock insieme con il numero di pagina e cercare il minimo valore di clock in caso di page fault. Questo però presenta degli svantaggi, soprattutto perché bisognerebbe tenere un valore di molti bit. La memorizzazione dovrebbe essere fatta ad ogni accesso a pagina quindi gestita totalmente dall’hardware.

In alternativa si potrebbe tenere una stack dei riferimenti a pagina in cui ad ogni accesso si effettua un push, rimuovendo il valore della pagina se già presente all’interno della stack. In caso di page fault il bottom della stack è la pagina vittima. Anche questa implementazione deve prevedere un hardware dedicato altrimenti è troppo costosa.

NOTA: né OPT né LRU soffrono dell’anomalia di Belady (si può dimostrare!)

Approssimazioni di LRU

Si effettuano con uso di un hardware aggiuntivo più semplice di quello visto sopra. Ad esempio, con un Reference bit, si esegue un Set ad ogni riferimento alla pagina. Periodicamente si fa un Clear di tutti i reference bit.

In questo modo in caso di page fault non si dispone di un "ordine" totale dei riferimenti a pagina, ma si può distinguere tra pagine

• "usate di recente" (reference bit=1) e
• "non usate di recente" (reference bit=0), cioè non più usate dopo l’ultimo Clear.

Algoritmo Second Chance o dell’orologio

• Si sceglie la pagina vittima con l’algoritmo FIFO.
• Se la pagina vittima ha reference bit=0 la sostituisce.
• Se ha reference bit=1 allora:
• • pone reference bit=0
  • cerca nella coda FIFO se c’è una pagina con reference bit=0, considerando la coda come un buffer circolare, e prende quella come vittima.

Se tutte le pagine hanno reference bit a 1, diventa FIFO. Altrimenti la pagina scelta da FIFO ha una "seconda possibilità" di non essere vittima, se ce ne sono altre con reference bit=0.

La figura illustra la pagina vittima scelta da FIFO e quella scelta da second chance (procedendo verso il basso si azzerano tutti i reference bit). L’algoritmo prende il nome di “orologio” perché il buffer circolare viene scandito da una “lancetta”. Se l’algoritmo non usa un buffer circolare, ma una lista lineare, lo si chiama “second chance”.

Not Recently Used

Si utilizza il reference bit insieme con il dirty bit, ricavando quattro classi in cui partizionare le pagine.

Si scelgono le vittime a partire dalle classi con numero più piccolo. Se ce ne sono più di una, la vittima si sceglie con FIFO o anche a caso.

Working Set o insieme di lavoro

La paginazione a richiesta in pratica funziona bene perché i processi in generale godono di una proprietà detta località dei riferimenti: durante ogni fase di esecuzione, essi riferiscono solo un insieme relativamente piccolo di pagine.

L’insieme delle pagine attualmente usato da un processo è detto working set (insieme di lavoro): se esso è in memoria, il processo non causerà page fault (almeno finché non si dovrà aggiungere una nuova pagina all’insieme). Se non c’è spazio per caricare tutto il WS di un processo, esso causerà molti page fault, rallentando sensibilmente l’esecuzione di tutti i processi nel sistema.

Questa situazione si chiama thrashing. Per impedirla, molti sistemi cercano di “calcolare” dinamicamente il WS dei processi, e far sì che esso sia sempre in memoria (se la memoria non basta, è meglio fare swap out di un processo che rischiare il thrashing di tutti!). Se il WS di un processo cresce, e quello di un altro processo decresce, si possono implementare algoritmi di page replacement globale.

In ogni istante t, chiamiamo w(k,t) l’insieme delle pagine riferite negli ultimi k indirizzi. In generale, per la proprietà di località dei riferimenti, w non è molto sensibile al variare di k, ovvero rimane costante per molti valori di k.

Mantenere (via hardware) il vero insieme di k riferimenti è troppo costoso, quindi si usano approssimazioni:

• si tiene conto dei riferimenti nell’ultimo intervallo di tempo t e non di esattamente k riferimenti.
• t deve essere relativo al tempo di esecuzione effettivo di ogni processo, detto tempo virtuale, non al tempo reale (in cui parecchi processi si alternano nell’uso di CPU)
• c’è una interruzione di clock periodica che azzera il reference bit della page table, a frequenza inferiore a t
• c’è un campo della page table che contiene un valore approssimato dell’ultimo riferimento a tale pagina: ad ogni page fault, se si trova il reference bit a 1 (cioè se è stata usata di recente) si memorizza il tempo virtuale corrente.

Politiche di pulizia

Per molti sistemi, scatenare un algoritmo di page replacement ad ogni page fault viene evitato “procurandosi” sempre un insieme di pagine libere. Questo si ottiene realizzando un demone di paginazione che viene attivato periodicamente dal sistema e controlla, per tutti i processi, se ci sono pagine che possono essere scaricate dalla memoria e messe nella lista dei frame liberi.

Il controllo si fa tramite un qualsiasi algoritmo tra quelli visti, come WS, LRU, orologio eccetera. L’algoritmo di solito ha due parametri aggiuntivi, un numero minimo e massimo di frame liberi (cioè si attiva solo se ci sono meno pagine libere del minimo, e termina quando ha liberato tante pagine quante il numero massimo).

Questa tecnica è usata da Unix (BSD, System V) con qualche variante all’algoritmo dell’orologio, e da Linux (che ha anche un secondo demone, che scrive su disco le pagine con il dirty bit settato e poi lo azzera) che usa tre tecniche diverse, a priorità crescente, tra cui una variante dell’orologio.

Windows 2000 invece usa il concetto di working set, cercando di mantenere il numero di pagine allocate per ogni processo tra un valore minimo ed un massimo, che però possono venire cambiati dinamicamente (se il processo ha page fault troppo frequenti, si aumenta il WS). Inoltre, tiene quattro diverse liste di frame liberi (ad es. se una pagina è messa nella prima o seconda lista, ma contiene ancora le informazioni, il processo può riottenerla subito in caso di page fault, altrimenti dopo un certo tempo il suo contenuto è azzerato e il frame può effettivamente andare ad un altro processo)

.