La gestione della memoria

La gestione della memoria

Quando un processo diventa Running, è necessario che tutto il suo codice e i dati su cui opera siano residenti nella cosiddetta memoria centrale dell'elaboratore, gestita attraverso tecniche di gestione della memoria classificabili a seconda che la memoria centrale sia intesa coincidente con la RAM oppure come combinazione di RAM e memoria di massa, e in quest'ultimo caso si parla comunemente di memoria virtuale.

Ogni accesso alla memoria centrale (istruzione o dato) avviene nella pratica sempre attraverso un indirizzo assoluto. Il codice di un programma può tuttavia contenere (nelle istruzioni di salto e di caricamento / salvataggio di dati) in toto o in parte indirizzi logici riferiti ad uno spazio di indirizzamento virtuale, che a tempo opportuno saranno trasformati o tradotti in indirizzi assoluti. Tale mappatura degli indirizzi logici in assoluti, detta Binding (legatura), deve certamente avvenire prima che la singola istruzione che fa uso dell'indirizzo venga eseguita, ma in teoria può essere effettuata in una qualunque delle 4 fasi attraverso le quali passa un programma sorgente  fino a diventare Running.

A tempo di compilazione (1) un compilatore/assemblatore traduce un programma sorgente dal linguaggio di alto livello in linguaggio macchina producendo un modulo oggetto, un segmento contenente codice macchina e informazioni per il linker, queste ultime consistenti in definizioni di simboli, in particolare simboli definiti o esportati ovvero variabili/funzioni definite nel modulo e rese disponibili all'uso per altri moduli, e simboli non definiti o importati ovvero variabili/funzioni utilizzate nel modulo ma non definite in esso, che ci si attende siano definite in altri moduli; normalmente il compilatore non conosce l'area di memoria in cui risiederà in fase di esecuzione il codice di un particolare modulo, per cui ipotizza un indirizzo fisso (per esempio zero) che dovrà essere modificato nel momento in cui tutti i moduli oggetto verranno combinati insieme in un unico modulo eseguibile. A tempo di collegamento (2) il linker o linkage editor collega più moduli oggetto in un unico programma eseguibile, risolvendo i collegamenti incrociati ai simboli esterni (in modo da sostituire a ciascun simbolo referenziato il corrispondente indirizzo effettivo del simbolo stesso, ricercando i simboli nei moduli linkati ma anche nelle librerie incluse nel progetto); nell'ambito del collegamento tra i moduli, il linker può farsi carico di rilocare segmenti di codice da un indirizzo ad un altro, ricalcolando ed aggiornando gli indirizzi delle istruzioni di salto e di caricamento/salvataggio di dati in memoria contenute in quel segmento: il codice prodotto dal linker è detto quindi modulo rilocabile. I moderni SO utilizzano anche il cosiddetto dynamic linking, che consiste nel risolvere eventuali riferimenti a simboli non definiti solo a tempo di esecuzione, cercandoli all'interno di una lista di moduli oggetto o librerie che è possibile caricare in modo dinamico in fase di boot: tale approccio risulta vantaggioso perchè consente di memorizzare le librerie standard di sistema (più spesso utilizzate) una sola volta in un'unica locazione di memoria e non necessariamente all'interno di ogni singolo programma eseguibile che ne fa uso, inoltre se all'interno di una libreria si presenta un errore tutti i programmi che la usano dinamicamente possono benificiare della correzione dell'errore già al successivo riavvio mentre i programmi che la includono in modo statico vanno necessariamente re-linkati. A tempo di caricamento (3) il loader si occupa di caricare il codice eseguibile in memoria, effettuando se necessario una nuova rilocazione del modulo eseguibile (si parla in questo caso di relocating loader) a seconda di "dove" risulti fisicamente residente il programma in fase di esecuzione. A tempo di esecuzione (4) il programma (uno o più processi) viene eseguito attraverso il normale ciclo fetch-execute della CPU nel quale iteritavamente viene letto (dal registro PC) l'indirizzo della prossima istruzione da eseguire, questa viene prelevata (fetch) dalla locazione di memoria corrispondente all'indirizzo letto e depositata in un apposito registro CIR (Current Instruction Register), viene interpretata (decode) ed infine eseguita (execute

Se il binding viene completato in una qualunque delle prime tre fasi citate (a valle di una o più fasi di rilocazione) e comunque NON a tempo di esecuzione, si dice che viene generato un codice assoluto, che una volta caricato in uno specifico segmento di memoria non potrà per ovvi motivi ulteriormente essere spostato in altro segmento; viceversa, nel caso estremo in cui il binding avvenga solo in fase di esecuzione, si parla di binding dinamico, il che comporta che lo spazio di indirizzamento di riferimento rimanga, ancora a tempo di esecuzione, uno spazio logico, suscettibile di rilocazioni  e mappature dinamiche sullo spazio fisico secondo necessità.

Il meccanismo più banale e conosciuto di binding è l'associazione dinamica degli indirizzi, che fa uso di una base e di una costante di spiazzamento: l'indirizzo logico costituisce il displacement (spiazzamento), un opportuno registro base o registro di rilocazione (la cui presenza è quindi un requisito hardware minimale) memorizza invece l'indirizzo della prima locazione utile dell'area di memoria riservata, l'indirizzo assoluto si ottiene quindi sommando l'indirizzo logico al valore del registro base; chiaramente possono esserci molteplici registri base, ciascuno per un diverso spazio logico, dal momento che ad esempio un processo potrebbe contenere indirizzi logici riferiti ad uno spazio logico istruzioni, ad uno spazio logico dati e ad un ancora distinto spazio logico stack, per cui sarebbero necessari tre distinti registri base (nulla vieta comunque che in fase di caricamento essi vengano mappati su un unico spazio logico): ad ogni cambio di contesto, il loro contenuto corrente viene salvato nel PCB del processo sospeso e ripristinato dal PCB del nuovo processo in esecuzione; si noti ancora che differenti processori hanno in generale un numero diverso di registri base: il vecchio Univac 1100 vede solo due distinti spazi logici ben precisi (il MSB, most significant bit, dell'indirizzo logico determina a quale dei due esso fa riferimento, 0 per lo spazio logico istruzioni e 1 per lo spazio logico dati) mentre i processori Intel hanno almeno 4 distinti registri base; infine, allo scopo di prevenire le violazioni, di evitare cioè che due processi si sovrappongano in una medesima area di memoria (col rischio di generare corruzione delle istruzioni o inconsistenza dei dati ivi memorizzati), ad ogni spazio logico di indirizzamento viene associato un limite logico superiore (il limite inferiore è banalmente sempre zero) anch'esso memorizzato in un opportuno registro limite di memoria o registro fence (steccato) salvato/ripristinato ad ogni cambio di contesto, e il tentativo di effettuare il binding di un indirizzo logico che ecceda tale limite logico produrrà una trap.

Un gestore della memoria di un SO multiprogrammato sovrintende alla coesistenza di più processi in memoria centrale, garantendo a ciascuno il controllo su un'area di memoria sufficientemente estesa da contenere le sue istruzioni, i suoi dati e il suo stack. Di seguito l'analisi delle tecniche di gestione di memoria (nel seguito GDM) utilizzabili in assenza di memoria virtuale

La GDM a partizioni è la più semplice tecnica di gestione della memoria, secondo la quale ogni processo occupa una propria partizione in memoria: generalmente si distingue tra partizioni fisse e partizioni variabili. La GDM a partizioni fisse si usa solo in piccoli sistemi, prevede che le partizioni della memoria siano costanti nel numero e nell'estensione e generalmente il programma in memoria utilizza indirizzi assoluti e non logici, inizializzati al più in fase di caricamento. La tecnica di GDM più banale (e per questo più semplice) è proprio un caso particolare della precedente, ovvero la GDM ad unica partizione o a partizione singola (ovviamente fissa): in tale modello il SO (si pensi all'MS-DOS) risiede tipicamente nella memoria bassa mentre un singolo processo utente è in esecuzione nella memoria alta, eventuali pericoli di sovrapposizione tra le due aree di memoria vengono scongiurati dall'uso di un opportuno registro limite; il problema fondamentale che si può porre in un tale modello è che il programma in esecuzione sia, da solo, più grande della memoria alta disponibile: in tal caso si usa (in realtà si usava, fino a diversi anni fa, nei piccoli sistemi con RAM di dimensioni molto ridotte) la tecnica dell'overlay. Nell'Overlay (sovrapposizione) il problema dell'insufficienza di memoria viene risolto (al pari delle moderne tecniche di GDM basate sulla memoria virtuale) con uno spostamento (codice o dati) tra la RAM e la memoria di massa, tuttavia al contrario delle moderne tecniche, tale travaso non è gestito dal SO bensì direttamente dall'utente: in luogo di un programma completo ma troppo esteso per essere contenuto totalmente nella RAM disponibile, si opta per un programma snello contenente soltanto le istruzioni/dati essenziali alla sua partenza (aggiungendo eventualmente anche quelli d'uso più frequente, sempre che non si ecceda la dimensione massima a disposizione) e un piccolo modulo di gestione overlay, mentre tutto il resto del codice e dei dati viene impacchettato in uno o più overlay files caricati singolarmente a tempo di esecuzione, in modo da sovrascrivere letteralmente una specifica porzione (grande abbastanza da contenere il più grande dei moduli overlay) dell'intera memoria occupata dal programma destinata ad ospitare questo codice intercambiabile secondo le necessità. La GDM a partizioni variabili prevede invece che le partizioni della memoria siano variabili nel numero e nell'estensione e che i processi cui queste partizioni vengono allocate usino (come sarà chiaro tra breve) necessariamente indirizzi logici per consentirne la rilocabilità: ogni volta che un nuovo processo viene sottomesso al sistema, ad esso viene allocata una nuova partizione (sempre aldisopra della memoria bassa occupata dal SO) di ampiezza sufficiente a contenerne codice dati e stack, e tendenzialmente consecutiva alle partizioni precedentemente allocate; quando almeno un processo termina, la corrispondente partizione si libera e produce un "buco" nello spazio allocabile, più buchi adiacenti costituiscono banalmente un unico buco più grande, ma più buchi isolati tra loro determinano la cosiddetta frammentazione esterna della memoria; quando un nuovo processo richiede un'allocazione in presenza di memoria esternamente frammentata, occorre adottare un criterio d'assegnazione dei buchi liberi ad un processo richiedente: la strategia First-Fit analizza nell'ordine tutti i buchi disponibili, partendo dal principio o dal punto d'arrivo dell'ultima ricerca effettuata e allocando al processo il primo buco sufficientemente grande, al che la ricerca si interrompe: tende a minimizzare il tempo di allocazione; la strategia Best-Fit alloca il più piccolo buco idoneo a contenere il processo e richiede comunque l'analisi di tutti i buchi: tende a minimizzare gli spazi vuoti ma introduce la cosiddetta frammentazione interna (ovvero tende a produrre buchi talmente piccoli da essere non solo inutilizzabili, ma addirittura gestibili in un modo necessariamente inefficiente, dacchè lo spazio richiesto per la catalogazione in apposita tabella del buco è più grande dell'estensione stessa del buco); la strategia Worst-Fit alloca il buco più grande e ancora richiede l'analisi di tutti i buchi: tende a massimizzare lo spazio compatto disponibile per altri processi. In realtà nessuna delle tre strategie elencate può essere definita ottimale, così come nessuna di esse garantisce che non si arrivi ad una situazione in cui, pur essendo disponibile uno spazio sufficiente (somma delle estensioni di tutti i buchi liberi) in memoria, a causa della frammentazione esterna nessun buco libero sia singolarmente tanto grande da ospitare un nuovo processo; una possibile soluzione consiste nell'attuare un meccanismo di compattazione dello spazio libero che preveda una migrazione (condotta mediante un apposito canale hardware che operi sui registri di base delle partizioni spostate e che sollevi la CPU da questo compito riducendo l'overhead complessivo) delle partizioni già allocate verso un'estremità della memoria, e a tale scopo si richiede ovviamente che i processi siano rilocabili e che usino quindi indirizzi relativi e non assoluti (in caso contrario la compattazione non sarebbe possibile); un'altra possibile soluzione (al problema di non avere un buco sufficientemente grande per l'intero processo da allocare) consiste nel tentare di sfruttare buchi più piccoli per allocare separatamente l'area codice, l'area dati e l'area stack, con conseguente utilizzo di più registri base e un pari numero di registri fence per ciascun processo, una strategia questa che introduce il concetto di codice condiviso (due processi possono condividere l'area codice pur operando su distinte aree dati

La GDM a paginazione o paging (ormai tecnica d'elezione dei processori Intel che in precedenza utilizzavano la GDM a partizioni) è una tecnica secondo la quale la memoria fisica viene suddivisa in blocchi di dimensione fissa (dipendente dall'hardware, in generale una potenza di 2) detti frame e analogamente ciascun processo vede un distinto spazio logico (indipendente da quello visto dagli altri processi) suddiviso in altrettanti blocchi di dimensione fissa detti pagine (ogni pagina è grande quanto un frame): quando un processo deve essere eseguito, le pagine che ne contengono il codice, i dati e lo stack vengono caricate in uno o più frame della RAM. Ogni indirizzo logico di un generico processo, espresso su N bit, si riferisce ad una precisa locazione di una specifica pagina e le due coordinate di indirizzamento P e D ovvero numero di pagina e offset di pagina (essendo l'indirizzo logico espresso in forma binaria ed essendo la dimensione delle pagine una potenza di 2) vengono banalmente contenute nei suoi bit rispettivamente più e meno significativi; ad ogni pagina di ogni processo è associato un frame di memoria all'interno di una opportuna tabella delle pagine o Page Table Entry (PTE), una diversa per ogni processo, dal momento che ciascun processo utilizza gli indirizzi logici come se fosse il solo ad utilizzare la memoria (l'indirizzo logico 0 per esempio è utilizzato da tutti i processi, ma ciascun processo intende con 0 referenziare una locazione di memoria in uno specifico frame) e la corrispondenza indirizzo logico  indirizzo fisico è univoca solo nel contesto del singolo processo. Tipicamente, al fianco delle PTE, il SO deve poter accedere ad una opportuna tabella dei frame (dimensionata sul loro numero totale, dipendente dalla RAM disponibile e dalla dimensione di pagina / frame) che indichi lo stato di ciascun frame (se è libero, il processo cui è assegnato, se è stato modificato). Il binding, che è dinamico (avviene a tempo di esecuzione), viene realizzato prelevando P e D (MSBs e LSBs) dall'indirizzo logico del processo attivo, usando P come entry della PTE per ricavare il numero F di frame corrispondente e infine a quest'ultimo il D (che continuerà a rappresentare il displacement anche per il frame dacchè pagine e frame hanno la stessa dimensione) viene giustapposto, non sommato (l'ALU quindi non viene scomodata. In realtà esiste un altro tipo di mapping più sofisticato adottato dai processori Intel 8086 che prevede che le pagine non siano disgiunte e che quindi sia possibile accedere ad uno stesso indirizzo logico da più pagine), per completare l'indirizzamento: l'indirizzo logico è praticamente un numero progressivo indice di uno spazio logico lineare, la doppia coordinata F / D rende invece lo spazio fisico in sostanza bidimensionale. Il binding viene nella pratica implementato da un apposito dispositivo hardware detto Memory Management Unit (MMU) - che può essere esterno alla CPU (d'obbligo se viene meno l'ipotesi che le pagine siano disgiunte e il mapping si complica) ma che più spesso è interno ad essa - la cui costituzione interna dipende dalla specifica strategia di interazione con la PTE adottata: una prima soluzione prevede che l'MMU disponga di una intera batteria di registri atta a contenere l'intera PTE del processo attivo (il cui contenuto viene quindi aggiornato ad ogni cambio di contesto) e che su questo array venga eseguita la ricerca della corrispondenza P  F con un unico accesso F=R[P]; una seconda soluzione prevede che le PTE dei processi attivi risiedano tutte interamente nella memoria (non si pone quindi l'eventualità che la batteria di registri dell'MMU non sia grande abbastanza da contenere la singola PTE) a partire da una specifica locazione, che l'MMU contenga un unico registro (il cui valore viene aggiornato ad ogni cambio di contesto, che risulta quindi più breve perchè l'aggiornamento qui coinvolge un solo registro e non una batteria) che punta alla prima locazione utile della PTE relativa al processo attivo, che l'indirizzamento F=M[R+PxSize_of_Page sia quindi indiretto e che richieda una somma (quindi l'intervento dell'ALU) e un accesso (lento) in memoria; una terza soluzione, intermedia tra le precedenti, prevede che la MMU possieda una propria memoria associativa (detta anche CAM, Content Addressable Memory, in cui la ricerca non avviene per indirizzo bensì per chiave, CONTEMPORANEAMENTE su tutte le chiavi, quindi con un'unica operazione), il che fa certamente levitare i costi di realizzazione ma abbatte quelli di ricerca; una quarta soluzione (ibrida tra la seconda e la terza) prevede che l'MMU disponga di una piccola memoria associativa contenente solo una parte della PTE (quella più spesso utilizzata) mentre la PTE intera continua a risiedere in RAM: la ricerca avviene in parallelo sulla memoria associativa (tempo Tau) e nella PTE in RAM (tempo T); se la corrispondenza viene trovata nella memoria associativa la ricerca in RAM viene abortita e l'unico accesso in RAM necessario è quello M[F+D] (che consente di accedere alla locazione di memoria desiderata) in un tempo totale nel caso migliore di Tau+T; se la ricerca nella memoria associativa non ha successo, la ricerca in RAM continua e gli accessi in memoria M[R+PxSize_of_Page e M[F+D] diventano due, in un tempo totale nel caso peggiore di 2T; posta p la probabilità di trovare la chiave nella memoria associativa, il tempo medio totale di accesso alla locazione fisica puntata dall'indirizzo logico è pari a Tm = (Tau+T)p + 2T(1-p) e poichè p vale (con una memoria associativa costituita da 16 registri) tra 0.8 e 0.9 nella quasi totalità dei programmi, si ottiene un Tm pari a circa 1.2T (20% in più del tempo migliore). Nella GDM a paginazione non esiste - banalmente - il problema della frammentazione esterna, mentre esiste quello della frammentazione interna, poichè l'ultimo frame di ogni processo viene occupato mediamente solo per la metà: a parità di RAM disponibile, aumentare il numero di frame diminuendone la dimensione consente di diminuire l'impatto della frammentazione interna ma rende la gestione più onerosa. La protezione della memoria (prevenzione delle violazioni) viene realizzata in modo naturale senza usare uno specifico registro fence per ogni frame, dal momento che il displacement D (per costruzione) assume valori nell'intervallo [0, Size_of_Page-1] e quindi un overflow di pagina/frame è semplicemente impossibile: nel caso in cui le PTE siano in RAM si usa un unico registro limite con il valore del quale viene confrontato il numero P di pagina richiesta per evitare traboccamenti nell'accesso alla singola PTE (che infatti, per quanto grande possa essere, ha comunque una dimensione massima limitata); nel caso in cui la PTE (o una sua parte) sia in memoria associativa, il numero di pagine in essa memorizzato può essere indirettamente indicato associando ad ogni pagina un bit di validità (le pagine non assegnate avranno ad esempio tale bit settato a 0); è possibile infine inserire nella PTE (indipendentemente da dove essa venga memorizzata) più bit supplementari allo scopo di definire per ciascuna pagina differenti e selettivi diritti di accesso. La differenza fondamentale tra la GDM a partizioni e la GDM a paginazione è che, mentre nella prima lo spazio fisico (su cui viene mappato lo spazio logico) è un blocco monolitico di locazioni consecutive, nel secondo caso lo stesso spazio fisico viene frammentato in blocchi (di dimensione fissa) allocabili a macchia di leopardo: nell'ipotesi che il codice di un processo occupi interamente una o più pagine (in altre parole non ci devono essere pagine che contengono contemporaneamente codice e dati) e che esso sia rientrante (cioè non modifichi se stesso), ciò rende possibile considerare il codice di un processo condiviso tra più processi, peculiarità questa comune anche alla GDM a partizioni variabili.

La GDM a segmentazione (generalizzando l'approccio della GDM a paginazione) è una tecnica secondo la quale la memoria fisica viene ancora suddivisa in blocchi ma stavolta di dimensione variabile, e analogamente ciascun processo vede un distinto spazio logico (indipendente da quello visto dagli altri processi) suddiviso in altrettanti blocchi di dimensione variabile: gli uni e gli altri sono detti segmenti e chiaramente i segmenti di memoria fisica vengono allocati dinamicamente in modo tale da avere le stesse dimensioni dei segmenti logici che su di essi devono essere mappati. La segmentazione è normalmente supportata da quei compilatori che mettono in segmenti differenti le variabili globali, lo stack, il codice, e che generano per ciascun processo uno spazio logico bidimensionale (contrariamente ai compilatori che generano un normale spazio logico lineare, senza sapere come esso sarà poi effettivamente mappato sullo spazio fisico) strutturato in segmenti distinti, con indirizzi logici costituiti dalle coordinate S e D ovvero numero di segmento e offset di segmento; lo spazio fisico è ovviamente anch'esso bidimensionale (come nella paginazione), ad ogni segmento logico è associato un segmento fisico di memoria all'interno di una opportuna tabella dei segmenti (anche qui una diversa per ogni processo per i motivi già citati a proposito della paginazione, e comunque normalmente più ampia di una PTE) ed ogni segmento fisico è definito attraverso le coordinate B ed L ovvero l'indirizzo base del segmento fisico e la lunghezza del segmento fisico. Il binding, anche qui dinamico (avviene a tempo di esecuzione), viene realizzato cercando nella tabella dei segmenti la corrispondenza S  (B, L), verificando che D<L e infine accedendo a M[B+D]. Il binding viene anche qui implementato da un apposito dispositivo hardware (che deve comprendere un array che memorizza le coppie B-L, un comparatore e un addizionatore) e le strategie di interazione con la tabella dei segmenti ricalcano quelle già viste per la paginazione (tipicamente si usa la soluzione ibrida memoria associativa + tabella intera in memoria RAM) così come l'uso in essa dei bit di validtà e di bit supplementari che definiscano diritti di accesso diversificati per ciascun segmento. Si osservi inoltre che la segmentazione consente, per sua stessa natura, di generalizzare al massimo il concetto di condivisione del codice: nella paginazione è possibile rendere condiviso (salve le restrizioni già citate) l'intero codice condividendo tra più processi tutte le pagine che lo contengono ma non singoli pezzi di codice, viceversa con la segmentazione si può definire già a livello logico porzioni di codice (anche singole routine) da condividere individualmente e a tali porzioni corrisponderanno chiaramente segmenti indipendenti che sarà possibile, singolarmente, rendere disponibili a più processi. Nella GDM a segmentazione non esiste chiaramente il problema della frammentazione interna (presente nella paginazione) dal momento che ogni segmento ha sempre l'esatta dimensione del segmento logico che deve contenere, mentre esiste la frammentazione esterna (assente nella paginazione): in alternativa all'esecuzione di periodiche ed onerose compattazioni dello spazio libero si può usare la tecnica mista della segmentazione paginata, in cui ogni segmento è organizzato in pagine.

Laddove la memoria centrale non coincida con la RAM (è il caso più frequente e interessante) e sia quindi costituita anche da parte della memoria di massa, il gestore della memoria deve coordinare lo spostamento dei processi dentro/fuori la RAM e la loro rilocazione dinamica: siamo in presenza di memoria virtuale.

Lo Swapping (di cui si è già parlato a proposito dello scheduling a medio termine) è il meccanismo che consente di gestire lo spostamento dei processi dalla memoria di massa alla RAM e viceversa (in teoria sarebbe sufficiente che in RAM si trovi di volta in volta la sola istruzione corrente, ma una strategia orientata a questo scopo sarebbe fortemente svantaggiosa nella pratica). L'idea che sta dietro alla sua applicazione è che, tipicamente, il kernel ha un numero di processi aperti così numerosi da non poter essere contemporaneamente conservati nella RAM, perciò alcuni di essi possono essere selettivamente spostati da/in un'area riservata della memoria di massa (tipicamente indipendente dal File System, allocata sull'unità a disco più veloce dell'intero sistema) detta Area di Swap, con operazioni di Swap-In e Swap-Out nella/dalla RAM normalmente eseguite seguendo 3 regole di validità generale: se lo Swap-In di un nuovo processo ad imminente esecuzione non è possibile a causa di una mancanza di spazio in RAM, esso viene preceduto dallo Swap-Out di un processo sospeso; i processi Ready dovrebbero trovarsi sempre in RAM allo scopo di velocizzare l'imminente transizione allo stato Running e comunque l'eventuale Swap-In di un processo andrebbe sempre eseguito prima che lo schedulatore a breve termine lo faccia diventare Running, in caso contrario, laddove ad ogni transizione Ready-Running debba costantemente corrispondere un'operazione di Swap-Out ed una di Swap-In, l'overhead introdotto produrrebbe, in luogo di un maggiore livello di multiprogrammazione, soltanto una evidente inefficienza; un processo in stato di Wait, ovvero sospeso in attesa di un'operazione di I/O, può subire uno Swap-Out solo se le comunicazioni tra esso e il dispositivo di I/O avvengono attraverso un buffer interno al kernel: se viceversa il dispositivo accedesse in modo asincrono alla memoria controllata dal processo, e anche solo una parte di questa fosse swappata, il dispositivo potrebbe violare uno spazio di memoria controllato da un altro processo con conseguenze imprevedibili. Si osservi che esistono diverse interpretazioni dello swapping a seconda del tipo di scheduling adottato dal SO: in presenza di una disciplina RR, dopo ogni quanto di tempo uno dei processi sospesi subisce uno Swap-Out ed un altro subentra al suo posto con uno Swap-In, ma è auspicabile che il prossimo processo schedulato per l'esecuzione si trovi già in RAM; in presenza di una disciplina basata su priorità, lo swapping prende anche il nome di rolling e, se un processo a maggiore priorità interrompe quello attualmente in esecuzione, può accadere che quest'ultimo, pur essendo diventato Ready, subisca uno Swap-Out (o Roll-Out) lasciando il posto al nuovo arrivato, per essere ripristinato con uno Swap-In (o Roll-In) subito dopo la terminazione di questo.

Una tecnica di GDM basata sulla memoria virtuale può essere applicata sia ad una memoria paginata sia ad una memoria segmentata: abbiamo analizzato il primo caso, ma il secondo può essere ricavato dal primo essendo note le differenze tra memoria paginata e memoria segmentata. In un sistema con memoria virtuale paginata si può assumere che la stragrande maggioranza delle pagine risieda normalmente su disco, che in RAM risiedano solo le pagine necessarie all'esecuzione di almeno un processo e che il SO preveda un meccanismo automatico e trasparente (nei confronti dell'utente) per lo swapping delle pagine: dato un processo in esecuzione, il PC punta alla prossima istruzione da eseguire, in fase di fetch l'istruzione viene prelevata e contestualmente analizzata alla ricerca di indirizzi (logici), a ciascun indirizzo corrisponde un numero P di pagina di cui occorre verificare la validità (attraverso un meccanismo hardware di basso livello come quelli descritti in precedenza, con memoria associativa, RAM, registri fence, ), se P eccede il valore del registro limite fissato per la PTE corrente viene generata una trap di indirizzo scorretto e il processo viene abortito, se P corrisponde ad una pagina esistente nella PTE occorre controllarne il bit di validità associato, se tale bit è alto il binding avviene correttamente e così l'esecuzione dell'istruzione, viceversa se tale bit è basso significa che la pagina P non è caricata in alcun frame, il binding fallisce, viene generata una trap (il processo non viene abortito, solo sospeso) detta di page fault, il kernel avvia il demanding page che produce lo Swap-In della pagina richiesta, dopodichè l'esecuzione dell'istruzione riprende; se all'atto dello Swap-In esiste già un frame libero si parla di paginazione pura, nell'ipotesi invece in cui non vi siano frame liberi, lo Swap-In deve in generale esser preceduto dallo Swap-Out di un'altra pagina - selezionata con opportuni algoritmi di sostituzione - e quindi si ha un vero e proprio meccanismo di sostituzione, salvo il caso che nella tabella dei frame il bit di modifica, associato al frame da liberare, segnali (valore 0) che esso non è mai stato modificato da quando è in RAM: in tale circostanza lo Swap-Out non è necessario e il frame da liberare può subire una semplice sovrascrittura. Si osservi che il controllo di validità delle pagine associate agli indirizzi logici di un'istruzione, ipotizzata in fase di fetch, può in teoria avvenire anche in fase di operand-assembly e in questo caso, dopo la trap, occorre normalmente ripetere anche la fase di fetch. Addirittura, il page fault può verificarsi anche in piena fase di execute e in tal caso si ha a che fare con un'istruzione solo parzialmente eseguita: è opportuno che PRIMA della trap che segue il page fault, vengano attuate opportune procedure che consentano di eseguire un rollback (disfacimento) di tale istruzione parzialmente eseguita prima di rieseguirla nuovamente (caso classico è l'istruzione MVC che sposta fino a 256B da un punto all'altro della memoria se la copia coinvolge aree che si sovrappongono e se uno dei due blocchi di origine/destinazione fuoriesce dal confine di una pagina e occorre caricarne un'altra, è necessario che prima della trap che caricherà la pagina mancante, tutti i vecchi valori siano ripristinati nel blocco d'origine/destinazione, al fine di evitare potenziali inconsistenze dei dati ivi memorizzati

Un algoritmo di sostituzione deve essere in grado di individuare nel modo più efficace ed efficiente la pagina vittima su cui eseguire lo Swap-Out, può essere Locale (ASL) - con la pagina vittima che viene cercata solo tra le pagine dello stesso processo che richiede lo Swap-In - o Globale (ASG) - con la pagina vittima che può essere una pagina qualunque - e può essere eseguito nell'ambito di due distinte strategie, che privilegiano uno stato di Pagine Piene (lazy swapping o paginazione su richiesta) in cui lo swapping viene eseguito solo quando non c'è più alcun frame libero (si può usare ASL o ASG), oppure di Pagine Vuote in cui si tende a conservare un serbatoio di frame vacanti, con l'algoritmo di sostituzione (necessariamente un ASG) che entra in gioco solo periodicamente eseguendo lo Swap-Out di un intero gruppo di frame (in Unix si occupa di questo un Daemon che crea un pool di frame liberi da consumare fino al prossimo timer). Di seguito la descrizione dei principali algoritmi di sostituzione

Un AS FIFO indica nella tabella dei frame il tempo in cui ciascuna pagina è stata caricata in RAM e seleziona la pagina vittima tra quelle più anziane: è poco efficiente perchè non tiene conto del fatto che una pagina presente in RAM da molto tempo potrebbe servire ancora a breve termine.

Un AS ottimale sceglie come pagina vittima quella che, dal momento della sostituzione in avanti, non verrà referenziata per il maggior tempo: ovviamente tale AS è puramente teorico perchè l'informazione richiesta risulta di fatto conoscibile soltanto a posteriori, però si può assumere che un AS sia tanto migliore quanto più approssima l'AS ottimale appena descritto.

Un AS LRU (Last Recently Used) privilegia la conservazione in RAM delle pagine accedute più di recente, pertanto sceglie come pagina vittima quella che da più tempo non viene utilizzata: il principio di località temporale alla base di questo AS suggerisce l'ìdea che se una pagina mi è appena servita molto probabilmente mi servirà ancora. Esistono modi diversi di implementare un AS del genere, il più semplice (da un punto di vista logico, ma oneroso da un punto di vista della realizzazione pratica) richiederebbe avere un campo supplementare nella tabella dei frame in cui, ad ogni accesso ad una specifica pagina, viene copiato il valore di un timer: la pagina vittima è sempre quella [associata al frame] con il valore di questo campo più basso. Una variante consiste nell'utilizzare, anzichè un timer, un contatore incrementato ad ogni accesso alla memoria: anche qui la pagina vittima è sempre quella con il valore di questo campo più basso (ma l'efficienza rimane bassa). Un'alternativa consiste nell'utilizzare un meccanismo hardware specifico che riordini la lista delle pagine candidate alla rimozione (tutte quelle in RAM per un ASG, solo quelle di uno specifico processo per un ASL) ad ogni accesso, nel senso che ogni volta che una pagina viene referenziata, essa diventa la prima della lista scalzando le altre: in ogni momento la pagina vittima è sempre quella in fondo (anche questo sistema è oneroso e quasi mai utilizzato). Una quarta ed elegante soluzione richiede un timer che produca uno scatto ogni volta che un intervallo di tempo X trascorre e uno shift register di cardinalità N associato ad ogni riga della tabella dei frame: ogni volta che la pagina contenuta in un frame viene acceduta (lettura o scrittura) il MSB dello shift register viene settato a 1, ogni volta che il timer fa uno scatto lo shift register subisce uno shift right con valore entrante 0; in pratica, per ogni frame, lo shift register contiene nei suoi bit l'informazione quantizzata (se in un intervallo il frame è stato acceduto più di una volta tale informazione non viene salvata) sugli accessi effettuati negli ultimi N intervalli di durata X, con il MSB pari al bit di riferimento dell'ultimo intervallo: la pagina vittima è in ogni momento quella [associata al frame] con il minor numero di "1" nello shift register e, a parità di "1", si sceglie lo shift register che memorizza il numero binario più piccolo, ovvero quello i cui ultimi accessi sono più lontani nel tempo.

L'AS detto della Seconda Chance si basa su un caso particolare del precedente AS, nel quale lo shift register di ogni frame si riduce ad un unico bit (N=1). In Unix tutti i bit di riferimento sono raccolti in una coda circolare, su cui agisce un daemon (un processo attivo in background su cui l'utente non ha un controllo diretto) attraverso un puntatore, e chiaramente ogni volta che la pagina contenuta in un frame viene acceduta il corrispondente bit viene settato. Unix adotta una strategia a pagine libere per la quale a fronte di un numero totale di frame pari a Max, almeno Min di essi devono essere liberi: ad ogni intervallo X il daemon verifica che ci siano almeno Min frame liberi e in caso contrario ne libera un numero M tale da riportarle ad un valore  Min. Ogni volta che il daemon interviene, comincia leggendo il bit della coda circolare attualmente puntato dal suo puntatore, se tale bit è alto signfica che dall'ultimo intervento del daemon (un numero intero di intervalli X fa) tale frame ha avuto almeno un accesso per cui lo resetta e passa oltre dandogli una "seconda possibilità", in caso contrario (cioè se il bit è basso) libera il frame corrispondente e passa oltre, e procede iterativamente in questo modo finquando M pagine non sono state liberate. Nessuna previsione comunque si può fare sul tempo che una pagina può permanere in RAM pur essendo stata acceduta nell'ultimo intervallo X, ovvero sulla durata della seconda chance concessa dal daemon: in realtà essa può tranquillamente essere pari a 0 intervalli di tempo, in quanto se M (il numero di frame da liberare) è maggiore del numero Q di frame che hanno il bit di riferimento resettato, il daemon, dopo aver liberato Q frame, avrà completato la visita di ogni bit della coda (circolare), tornerà esattamente sul primo bit graziato all'inizio e sarà costretto a liberare i prossimi M-Q frame che incontra, nonostante avesse dato loro una seconda chance (in effetti questi saranno liberati come se la seconda chance non fosse mai stata concessa

Un AS LFU (Last Frequently Used) privilegia la conservazione in RAM delle pagine accedute più di frequente, pertanto sceglie come pagina vittima quella che presenta la più bassa frequenza d'uso: il principio di località temporale alla base di questo AS suggerisce l'ìdea che se una pagina finora mi è servita spesso continuerà a servirmi altrettanto spesso anche in futuro. Un modo di implementare un AS del genere è quello di associare ad ogni pagina un contatore che (partendo da zero, al momento in cui viene caricata per la prima volta in RAM) si incrementa ad ogni accesso, tuttavia potrebbe succedere che una pagina con un'alta frequenza d'uso abbia meno punti di una acceduta più raramente ma presente da più tempo in RAM: per risolvere questo problema, si potrebbe pensare di diminuire (dimezzare per esempio) periodicamente il contatore associato alle pagine in modo da penalizzare quelle in RAM da più tempo tuttavia ciò costituirebbe comunque una soluzione ibrida, che tiene conto anche da quanto tempo non si fanno accessi e quindi non propriamente LFU.

Supponendo che per ciascuna pagina sia disponibile un certo numero di bit di riferimento e un bit di modifica, è possibile suddividere le pagine (a seconda che sia ASL o ASG) candidate alla sostituzione (indipendentemente dall'AS scelto) in quattro classi, elencate in ordine decrescente di sacrificabilità, utilizzando una semplice strategia FIFO per discriminare nella medesima classe le pagine che presentano pari requisiti alla sostituzione: prima si possono sostituire le pagine mai accedute (dopo la prima volta che le ha portate in RAM) e mai modificate, poi quelle mai accedute ma modificate (al primo accesso che le ha portate in RAM), poi quelle accedute ma mai modificate e infine quelle sia utilizzate che modificate. Ulteriori accorgimenti possono comunque essere adottati per migliorare l'efficienza degli AS: uno di questi, in Unix, consiste nel tenere memoria dell'identità (cioè in sostanza del contenuto) delle pagine memorizzate nei frame liberati dal daemon ma che non siano state ancora sovrascritte, in modo da poterle resuscitare senza eseguire un vero e proprio Swap-In.

Dato il problema importante di definire il numero di pagine da assegnare ad un processo una volta che questo sia caricato in memoria, le soluzioni sono molteplici: il numero minimo di pagine che consente al processo di iniziare l'esecuzione, un numero costante per tutti i processi, un numero proporzionale alla dimensione del processo, un numero proporzionale alla sua priorità oppure proporzionale ad entrambe. In presenza di troppi page fault, può verificarsi il fenomeno del trashing per il quale almeno un processo richiede più risorse per le operazioni di swapping che non per la sua normale esecuzione, il che accade essenzialmente perchè il numero di pagine ad esso assegnate è insufficiente. Nell'ambito di una strategia a pagine piene, adottando un ASL, un processo che genera molti fault è incapace di risollevarsi da questa situazione in quanto la sostituzione avviene sempre solo nell'ambito delle sue stesse pagine (trashing locale), viceversa adottando un ASG il processo in difficoltà finisce per "rubare" pagine ad un altro processo, il quale a sua volta entrato in trashing alimenterà un circolo vizioso (trashing globale). I sistemi il cui livello di multiprogrammazione è regolato automaticamente sulla base dell'uso della CPU, possono involontariamente alimentare un trashing globale: se si innesca un trashing, inevitabilmente il livello d'uso della CPU si abbassa, ma se questo abbassamento viene male interpretato (per esempio si assume dovuto ad una eccessiva prevalenza di processi I/O bound) e il livello di multiprogrammazione viene innalzato, l'ingresso di nuovi processi in RAM non fa altro che esasperare il trashing stesso; una soluzione consiste, in questi casi, nel selezionare un certo numero di processi in blocco e di eseguirne uno Swap-Out completo: quando il singolo processo totalmente swappato viene ricaricato nella RAM, è opportuno che gli venga concesso comunque un numero di pagine almeno pari a quelle che aveva al momento della sua rimozione (prepaging). Per tentare di risolvere a monte il problema del trashing, si può valutare dinamicamente il cosiddetto working-set di un processo, cioè l'insieme delle pagine accedute dal processo almeno una volta negli ultimi X riferimenti più recenti: se il working-set di un processo, ad un certo punto, dimostra di diventare obsoleto poichè questo comincia a referenziare delle nuove pagine, è possibile che qualche vecchia pagina non venga più referenziata e può essere eliminata dalla RAM; viceversa se il processo continua a referenziare le pagine del suo working-set ma la sua frequenza di paginazione aumenta significa che il numero di pagine ad esso riservate è insufficiente e che occorre allargare il suo working-set. Una modulazione dinamica dei working-set può essere fatta, semplicemente, monitorando i page fault generati dai vari processi: se i fault di un processo aumentano sopra una certa soglia può significare che ha bisogno di più pagine, cosicchè nei page fault successivi verranno sostituite le pagine di altri processi e non le sue, se la frequenza di paginazione si mantiene costante il numero di pagine assegnato al processo si può ritenere sufficiente, se infine la diminuisce, le pagine del processo in questione saranno candidate alla sostituzione (modulazioni più sofisticate possono essere effettuate sulla falsa riga degli AS, cioè valutando in modo opportuno, periodicamente, i bit di riferimento delle pagine di ciascun processo). Se un processo è bloccato perchè ha richiesto una operazione I/O che coinvolge una pagina P, tale pagina andrà segnalata come "non sostituibile" settando un opportuno bit di interlock (così fa Unix). Infine, allo scopo di ottimizzare le prestazioni del sistema, occorre definire con attenzione la dimensione delle pagine, tenendo conto che pagine piccole consentono di sfruttare ad una più alta definizione la memoria, perchè tasselli più piccoli consentono di coprire meglio il flusso di controllo di un processo anche se diventa più onerosa la loro gestione (quando le dimensioni delle pagine diventano confrontabili con le dimensioni dei settori di disco, sul tempo totale di paging cominciano a pesare i ritardi legati ai tempi di seek e di latenza), mentre pagine grandi diminuiscono la probabilità dei page fault per il singolo processo ma limitano il livello di multiprogrammazione.