Sistemi Operativi V · Appunti Universitari

01 Jul 2004

Riassunto gerarchico delle nozioni del corso 2003-2004 di Sistemi Operativi del Prof. Francesco Aymerich - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

la memoria
- per motivi di costi ed efficienza la maggior parte dei computer fa uso di una gerarchia di memorie:
  - memoria tampone (cache)
    - molto veloce, costosa e volatile
    - unità di misura KB
  - memoria principale (RAM)
    - media velocità, medio costo e volatile
    - unità di misura MB
  - memoria disco
    - lenta, economica e non volatile
    - unità di misura GB
- il sistema operativo ha il compito di coordinare l'uso di queste memorie.
- la gestione della memoria è lo strato successivo della "cipolla"
  - lo poniamo vicino al nucleo in quanto senza memoria nessun programma potrebbe essere eseguito e neanche le operazioni di I/O (necessitano di buffer)
- la parte del sistema operativo che gestisce la gerarchia di memoria viene chiamata il gestore della memoria.
  - ha il compito di sapere, istante per istante, quali parti di memoria sono in uso e quali no, allocare la memoria ai processi quando ne hanno bisogno e deallocarla quando hanno terminato, e gestire lo swapping tra la memoria principale e il disco quando la prima è troppo piccola per contenere tutti i processi.
obiettivi nella gestione della memoria
- rilocazione
  - in ogni istante la memoria disponibile viene suddivisa tra i vari processi
    - non è possibile sapere a priori la parte di memoria locata per il singolo processo
  - con l'avvicinarsi dei processi al loro completamento, lo spazio utilizzato si libera, diventando disponibile per altri processi
  - per ottimizzare il successivo utilizzo della memoria potrebbe risultare necessario cambiare posizione ai processi esistenti in memoria
    - potrebbe tornare comodo spostare i processi in modo tale da unire piccole zone non contigue di memoria libera, formando un'unica area disponibile, di estensione ed utilità maggiori
      - la precedente operazione prende il nome di deframmentazione
  - la regione di memoria destinata ad un processo può così variare durante la vita dello stesso ed il sistema deve occuparsi della trasformazione degli indirizzi impiegati dal programmatore in quegli indirizzi che realmente si riferiscono all'ubicazione fisica del processo
- protezione
  - è necessario impedire che un processo acceda in scrittura alle locazioni di memoria destinate ad un altro processo
    - a meno che non gli sia esplicitamente concesso
  - il gestore della memoria deve controllare tutti i riferimenti di memoria generati da un processo
  - solitamente si controllano solo i permessi in scrittura
  - talvolta anche quelli in lettura per garantire la riservatezza delle informazioni
- condivisione
  - il gestore della memoria deve consentire l'accesso controllato ad aree di memoria in condivisione senza compromettere la funzione essenziale di protezione
- organizzazione logica
  - l'elaboratore tradizionale possiede uno spazio di indirizzamento monodimensionale, ovvero lineare
    - gli indirizzi sono numerati sequenzialmente da zero fino al limite superiore della memoria
  - questa organizzazione rispecchia l'hardware della macchina ma non il modo in cui sono scritti i programmi
    - la maggior parte di essi sono strutturati in moduli o procedure che fanno riferimento a zone diverse di memoria contenenti dati modificabili o meno
  - se le suddivisioni logiche esistenti nel programma e nei dati rispecchiano la segmentazione corrispondente allo spazio di indirizzamento, se ne possono trarre parecchi vantaggi:
    - possibilità di codificare i segmenti indipendentemente gli uni dagli altri
    - prevedere che tutti i rimandi da un segmento all'altro vengano compilati dal sistema nella fase di esecuzione.
    - garantire livelli diversi di protezione a segmenti distinti, senza appesantire il sistema.
    - è possibile introdurre meccanismi tramite i quali i segmenti siano in grado di essere condivisi tra processi
- organizzazione fisica
  - quasi tutti i sistemi fanno uso di sistemi di memorizzazione a due o più livelli:
    - RAM, memoria ad accesso diretto
      - realizzata con l'impiego dei semiconduttori
      - tempo di accesso nell'ordine dei nanosecondi
    - memoria di massa
      - realizzata solitamente su dischi magnetici
      - tempo di accesso nell'ordine dei millisecondi
  - nei sistemi generalmente è possibile accedere direttamente solo alle informazioni contenute in memoria centrale
  - l'organizzazione del flusso di informazioni tra le memorie principali e quelle di massa riveste un carattere di importanza primaria
    - inizialmente si faceva gravare quest'onere sul singolo programmatore (overlay programming)
      - prassi non indicata per due buoni motivi
        
        il programmatore non vuole impegnare gran parte delle proprie capacità nello sforzo di scrivere sovrapposizioni complesse
        
        compilatori realizzati in modo razionale possono generare automaticamente il codice di sovrapposizione nei punti più opportuni del programma anche se in molti casi il compilatore non ha informazioni sufficienti per sapere quando saranno richieste le sovrapposizioni
        
        a causa della rilocazione dinamica, al programmatore non è dato sapere, al momento di scrivere il programma, quanto spazio sarà disponibile e dove sarà ubicato nell'ambito della memoria
    - il compito di effettuare spostamenti di informazioni tra i due livelli di memoria dovrebbe ricadere sul sistema stesso
la memoria virtuale
- spazio di indirizzamento
  - consiste nell'insieme degli indirizzi di programma, detto anche spazio di denominazione
  - può non essere lineare
  - può avere estensione inferiore uguale o maggiore dello spazio di memoria
- spazio di memoria
  - è la gamma delle locazioni di memoria dell'elaboratore
  - negli elaboratori attuali è lineare
    - le locazioni di memoria sono numerate sequenzialmente a partire da zero
  - la sua estensione equivale alla quantità di memoria centrale
- mappa di indirizzamento
  - meccanismo col quale si trasformano gli indirizzi usati dal programmatore nelle corrispondenti locazioni di memoria fisica realmente allocate per il programma
  - indicando lo spazio di indirizzamento con N e lo spazio di memoria con M, la mappa di indirizzamento può essere così definita:
    - f->N := M
    - ossia è una funzione da N in M
  - può anche essere considerato un metodo per consentire al programmatore di servirsi di una gamma di indirizzi di programma anche molto diversa da quella delle locazioni disponibili in memoria
    - il programmatore "vede" una memoria virtuale con caratteristiche differenti da quelle della memoria reale
- La mappa di indirizzamento è concepita in modo da produrre una memoria virtuale conveniente per il programmatore
- lo schema più semplice di gestione della memoria è quello che prevede l'esecuzione di un programma alla volta che condivide la RAM col sistema operativo
  - Alcuni esempi sono:
    - a) Sistema Operativo in RAM - programma utente
      - il sistema operativo è in fondo alla memoria RAM
    - b) programma utente - sistema operativo in ROM
      - la ROM è posta in cima alla memoria
    - c) sistema operativo in RAM - programma utente - device driver in ROM
      - i device driver sono in cima alla memoria, all'interno di una ROM e il resto del sistema in basso, all'interno della RAM
      - viene usato nei piccoli sistemi MS-DOS
  - sui PC IBM la porzione del sistema contenuta nella ROM viene chiamata BIOS (Basic Input Output System)
  - quando il sistema è organizzato in questo modo un solo processo alla volta può essere in esecuzione.
    - non appena l'utente batte un comando, il sistema operativo carica in memoria il programma richiesto, leggendolo dal disco, e lo esegue.
    - quando il processo termina, il sistema operativo stampa il carattere di prompt e attende un nuovo comando.
    - quando riceve il comando, carica in memoria un nuovo programma, sovrascrivendo il primo.
- lo schema più semplice per realizzare la multiprogrammazione consiste nel dividere la memoria in n partizioni (eventualmente uguali)
  - questo partizionamento può, ad esempio essere effettuato manualmente all'avviamento del sistema
  - usando più code
    - quando arriva un job può essere inserito nella coda di ingresso per la partizione più piccola in grado di contenerlo.
      - poiché in questo schema le partizioni sono fisse, qualsiasi spazio che appartenga a una partizione e non sia utilizzato da un job viene perso
    - lo svantaggio dell'ordinare i job in arrivo in code separate diventa evidente quando la coda per una partizione grande è vuota mentre la coda per una partizione piccola è piena
  - usando una sola coda
    - ogni volta che si libera una partizione, il job più vicino alla testa della coda e di dimensioni inferiori alla partizione appena liberata potrebbe essere caricato nella partizione vuota ed eseguito
implementazione della memoria virtuale
- registri base e limite
  - il registro base, o registro di riferimento, indica la prima locazione di memoria allocata al processo
    - la mappa di indirizzamento consiste nel sommare l'indirizzo base, B, all'indirizzo di programma, a
      - f(a) := B+a
    - la rilocazione avviene semplicemente spostando il processo e ripristinando l'indirizzo base sul valore appropriato
  - il registro limite consente di implementare il meccanismo di protezione della memoria e contiene a seconda delle implementazioni
    - l'ultima locazione di memoria allocata per il processo
      - la mappa di indirizzamento, eseguita dall'hardware segue il seguente schema
        
        if a < 0 then violazione di memoria
        
        else {
        
        a' := B+a
        
        if a' > limite then violazione della memoria
        
        else a' è la locazione richiesta
        
        }
      - che lo spazio di indirizzamento mappato tramite questo schema è lineare e la sua estensione, data dalla differenza tra il registro base e quello limite, è necessariamente minore o uguale a quella dello spazio di memoria
    - la dimensione dell'area di memoria allocata per il processo
      - la mappa di indirizzamento, eseguita dall'hardware segue il seguente schema
        
        if a < 0 || a > limite then violazione memoria
        
        else {
        
        a' := B+a
        
        a' è la locazione richiesta
        
        }
      - il controllo del limite non dipende più dal risultato dell'addizione e così sia i controlli che le addizioni possono essere eseguiti in parallelo.
      - l'addizione viene interrotta (aborted) se si verifica una violazione di memoria
  - affinché l'operazione di mapping degli indirizzi non sia eccessivamente dispendiosa in termini di tempo, il registro base ed il registro limite devono essere implementati con un hardware di tipo veloce.
  - per motivi economici, non è praticamente fattibile l'inserimento di una coppia di registri base e registri limite per ogni processo eventualmente presente in memoria.
    - in sostituzione, per ogni processore viene fornita una singola coppia di registri che viene caricata con l'indirizzo base e l'indirizzo limite relativo al processo attivo correntemente.
    - questi valori fanno parte dell'ambiente volatile del processo e vengono memorizzati al momento della sospensione dello stesso
  - la condivisione di programmi rientranti può essere realizzata fornendo due coppie di registri, anzichè una sola:
    - una coppia serve a delimitare lo spazio occupato in memoria dal codice di rientro ed i valori contenuti in essa sono comuni a tutti i processi che utilizzano il codice
    - l'altra coppia serve a delimitare le aree dati relative al codice e contiene valori diversi per ogni processo interessato.
    - Il primo DEC System-10 è un esempio di macchina che fa uso di questa tecnica
- swapping
  - tecnica intermedia tra quella a registri base e limite e le tecniche di memoria virtuale vera e propria
  - consiste nel
    - caricare in memoria ciascun processo per intero
    - eseguirlo per un po'
    - scaricarlo sul disco alternando l'uso della memoria con un altro processo e riprenderlo successivamente
  - per essere applicata richiede che il gestore della memoria abbia a disposizione una bitmap o una lista di tutte le porzioni di spazio di memoria allocabili
    - possono essere un piccolo numero di words o segmenti più grandi e di dimensioni variabili
  - la gestione della bitmap o della lista dei segmenti viene fatta contrassegnando ciascuna di queste porzioni di memoria con un bit di assegnazione.
  - poiché i processi possono richiedere nel corso del tempo di allocare nuovo spazio, normalmente a ciascun processo viene allocato in partenza uno spazio maggiore di quello richiesto (per l'area dati e per lo stack), per consentire al sistema operativo di rispondere senza particolari interventi alla richiesta di nuovo spazio.
  - in un certo istante lo stato della memoria si presenterà così, dall'alto verso il basso:
    - stack_1 (down)
    - spazio_per_estensione
    - dati_1 (up)
    - programma_1
    - sistema operativo
  - un istante dopo
    - stack_2 (down)
    - spazio_per_estensione
    - dati_2 (up)
    - programma_2
    - sistema operativo
  - la zona dati cresce verso l'alto
  - lo stack cresce verso il basso
- paginazione
  - tecnica che consente di fornire al programmatore una memoria virtuale più ampia di quella fisica a disposizione
    - la memoria secondaria viene trattata come un'estensione della memoria centrale, si parla di memoria ad un livello
    - lo spazio virtuale degli indirizzi e la memoria centrale vengono suddivisi in pagine della stessa dimensione
    - le pagina in memoria centrale vengono condivise tra i processi esistenti
      - in un dato istante un processo ha in memoria centrale solo le poche pagine attive, quelle rimanenti (le pagine inattive) risiedono su memoria secondaria
  - page frame
    - corrisponde ad una pagina della memoria centrale
  - mappa d'indirizzamento
    - consente di eliminare la distinzione tra memoria centrale e secondaria
    - rimanda dai numeri di pagina e di word alla locazione fisica in memoria
    - si realizza per mezzo di una page table
      - nella quale la variabile p-esima contiene la locazione p' relativa alla page frame che contiene la pagina numero p
      - sono presenti ulteriori bit associati ad ogni voce in tabella utilizzati per effettuare lo swapout di una pagina dalla memoria principale
        
        tali informazioni possono riferirsi a
        
        numero di volte che si è fatto riferimento ad una pagina;
        
        l'ultima volta che si è fatto riferimento alla pagina;
        
        se la pagina è stata oggetto di scrittura, o meno
  - funzioni svolte dalla tecnica di paginazione
    - mapping degli indirizzi, determinare a quale pagina di programma si riferisce l'indirizzo e trova l'eventuale locazione di memoria centrale da essa occupato
      - i bit più significativi di un indirizzo di memoria vengono interpretati come il numero di pagina, i restanti bit come il numero della word all'interno della pagina
        
        quindi imponendo pagine da 2 ⁿ word, gli n bit meno significativi identificheranno la word all'interno della pagina, i restanti bit identificheranno la pagina
      - la divisione dell'indirizzo in numero di pagina e di word è effettuata in hardware ed è del tutto trasparente al programmatore che per quanto lo riguarda ha a disposizione l'intero spazio sequenziale di indirizzamento
      - si ottiene la locazione di memoria richiesta operando come segue
        
        sia a l'indirizzo di programma specificato
        
        siano p e w la scomposizione pagina e word dell'indirizzo a
        
        p è la parte intera del rapporto a/Z
        
        w è il resto del rapporto a/Z
        
        Z è la dimensione della pagina
        
        sia p' la locazione di memoria fisica associata alla pagina p-esima all'interno della page table
        
        se la pagina p è presente in memoria centrale, p' è diverso da null
        
        la locazione cercata è mappata fisicamente in memoria all'indirizzo p' + w
        
        se la pagina p non è presente in memoria centrale, p' è uguale a null
        
        viene venerato un interrupt di page fault
        
        il meccanismo di paginazione avvia il caricamento in memoria centrale della pagina mancante (presente in quel momento sulla memoria secondaria)
        
        la locazione della pagina all'interno della memoria secondaria può essere
        
        contenuta in una tabella separata
        
        contenuta nella stessa page table
        
        si aggiunge un "bit di presenza" in ciascuna variabile della page table, per indicare se la pagina è presente o meno in memoria centrale e se il campo dell'istruzione relativa all'indirizzo va inteso come rappresentante una pagina libera o una locazione di memoria di massa
        
        se non ci sono pagine libere in memoria principale si dovrà spostare qualche pagina verso la memoria secondaria per liberare lo spazio necessario
        
        questa operazione prende il nome di swapout
        
        la scelta della pagina da scaricare è determinata dal risultato di un algoritmo di paginazione
        
        nell'implementazione pratica le cose si complicano un po' rispetto alle spiegazioni precedenti:
        
        il tempo necessario per effettuare qualsiasi accesso in memoria viene raddoppiato dalla necessità di accedere dapprima alla page table
        
        si può ovviare il problema mantenendo la page table in un serie di registri veloci piuttosto che nella memoria ordinaria
        
        la dimensione della page table è proporzionale a quella dello spazio di indirizzamento e perciò il numero dei registri necessari diventerebbe troppo vasto
        
        viene messo in attesa di eventi il processo corrente fino a che non si è compiuto il caricamento
        
        viene aggiornata la page table
      - esempio, ATLAS
        
        gli indirizzi sono a 20 bit, abbiamo 2 ²⁰ possibili valori per un'indirizzo (dimensione della memoria virtuale)
        
        ogni pagina è costituita da 2 ⁹ word, gli n bit meno significativi determinano il numero di word
        
        gli 11 bit più significativi determinano il numero di pagina per un totale di 2 ¹¹ = 2048 pagine
        
        nella memoria fisica c'è spazio solo per 32 pagine
    - trasferire le pagine dalla memoria secondaria alla centrale quando è necessario e riportarle su memoria di massa una volta terminato il loro utilizzo
  - questa tecnica è stata introdotta per la prima volta nel 1960 sull'ATLAS all'Università di Manchester
  - MMU - Memory Management Unit
  - l'intera operazione di mapping degli indirizzi viene svolta dall'hardware (La page table è contenuta nella MMU), a parte il caso in cui una pagina deve essere riportata in memoria centrale dalla memoria secondaria.
    - in quest'ultima evenienza, l'applicazione dell'algoritmo di paginazione e la modifica della page table vengono eseguiti dal software
  - registro PAR, Page Address Register
    - è costituito dai seguenti campi
      - v
      - pf
      - prot
      - mod
      - pv
  - il problema di performance nell'accesso alle pagine attive può essere risolto con l'uso di un ridotto numero di PAR (memoria associativa)
    - ogni PAR contiene il numero di una pagina attiva
    - è possibile effettuare ricerche simultanee per ogni numero di pagina relativo ad una particolare istruzione di programma
    - esempio di funzionamento
      - un istruzione del programma è la word 243 della pagina 3, 3 243
      - si suppone, per comodità, che la dimensione della pagina sia di 1000 word
      - il numero di pagina, 3, viene raffrontato con tutti i PAR
      - si riscontra una corrispondenza nel PAR numero 5
      - l'informazione che si ricava è che la pagina 3 occupa in quel momento il page frame numero 5
      - pertanto la locazione logica richiesta risulta pagina 5 word 243, 5 243
    - l'impiego di una memoria associativa riduce l'appesantimento della mappa di indirizzamento di un ordine di grandezza rispetto a quello sostenuto per via di una page table contenuta in memoria centrale
    - affinché tutte le pagine attive facciano riferimento ad un PAR, c'è bisogno di tanti PAR quante sono le pagine libere in memoria
      - per motivi economici o pratici questo non è sempre possibile
      - una soluzione di compromesso consiste nel tenere in memoria una page table completa per ogni processo ed utilizzare una piccola memoria associativa per fare riferimento ad un numero limitato di pagine relative ai processi che sono stati più attivi recentemente
        
        è necessario aggiungere al PAR un campo che indichi la pagina libera a cui fa riferimento il PAR stesso
        
        l'hardware di indirizzamento della memoria svolge, quindi, l'operazione di mapping degli indirizzi
        
        l'intervento software è necessario solo per la sostituzione della pagina
    - è necessario poter distinguere, nell'ambito della memoria associativa, le pagine pertinenti al processo corrente e quelle appartenenti ad altri processi
      - si può risolvere il problema in vari modi:
        
        includendo nel PAR l'id del processo e il numero di pagina (bit di pagina)
        
        amplio i PAR di un solo bit che viene settato ad uno per le istruzioni del processo corrente ed a zero negli altri casi
        
        questa soluzione comporta necessariamente la disponibilità di una memoria associativa distinta per ogni processore presente nella configurazione
        
        è consigliabile prevederla comunque affinché la logica di indirizzamento della memoria non rappresenti una strozzatura (bottleneck) tra i processori e la memoria stessa
    - risulta chiaramente auspicabile che la memoria associativa contenga i numeri di quelle pagine cui, con più probabilità, si farà riferimento
      - purtroppo non esiste alcun algoritmo generico in grado di garantire l'avverarsi ditale situazione
      - in pratica, la memoria associativa solitamente viene riempita ciclicamente con gli indirizzi delle pagine cui si è fatto riferimento più di recente.
        
        questo algoritmo piuttosto rudimentale in pratica risulta decisamente efficace; con una memoria associativa formata solamente da 8 o 16 registri, a seconda dell'estensione della memoria centrale, si può prevedere un hit rate medio superiore al 99%
  - ridurre la dimensione della page table
    - è possibile se si accede alla stessa con indirizzamento diretto e non per mezzo di indici
      - in questo caso si inseriscono nella page table solo le pagine che sono state usate, invece di una voce per ogni pagina presente nello spazio di indirizzamento
    - ogniqualvolta si porta in memoria centrale una pagina nuova, il suo numero e l'indirizzo della pagina libera corrispondente vengono inseriti nella page table, nel punto determinato da un'opportuna funzione di indirizzamento casuale
    - questa stessa funzione può essere impiegata per localizzare le pagine durante l'operazione di mapping degli indirizzi
    - lo svantaggio consiste in un aumento del tempo d'accesso alla memoria necessario per alcuni riferimenti:
      - da un lato bisogna considerare il tempo utilizzato per il calcolo della stessa funzione di indirizzamento casuale
      - dall'altro, nel caso in cui siano in contrasto le voci della page table determinata dalla funzione, può darsi che sia necessario accedervi più di una volta prima di localizzare la pagina richiesta
    - questo schema può divenire fattibile servendosi di una memoria associativa che è in grado di diminuire, fino a circa 1'1% del totale, il numero di riferimenti alla page table, ed eseguendo l'operazione di indirizzamento casuale tramite hardware
- segmentazione
  - consente di far rispecchiare le suddivisioni logiche fra programmi e dati nell'organizzazione dello spazio di indirizzamento
  - il concetto consiste nel dividere in segmenti lo spazio di indirizzamento, ciascuno dei quali corrisponde ad una procedura, un modulo di programma o una raccolta di dati
    - vi si può riuscire in modo semplice, aggiungendo a ciascun processore svariate coppie di registri limite e base, cosicché sia possibile delimitare altrettante zone entro lo spazio di indirizzamento
      - il difetto di questa implementazione è di ordine economico, il numero dei segmenti è necessariamente limitato ed è indispensabile stabilire una convenzione per determinare quali segmenti sono utilizzati ed a quale scopo.
    - una soluzione più elastica consiste nel fornire al programmatore la possibilità di usare un vasto numero di segmenti
      - ogni segmento è individuato da un nome assegnato dal programmatore stesso
      - lo spazio di indirizzamento diviene bidimensionale poichè le singole istruzioni del programma sono individuate attribuendovi sia un nome di segmento che un indirizzo dentro al segmento relativo
        
        per motivi di convenienza in fase di implementazione, il sistema operativo sostituisce il nome del segmento con un numero unico, quando vi fa riferimento per la prima volta
      - in ultima analisi, un'istruzione di programma è formata da una coppia di valori (s, a)
        
        in cui s è il numero di segmento ed a è l'indirizzo dentro il segmento stesso
      - segment table (tabella dei segmenti)
        
        ogni riga i della tabella contiene le informazioni relative al segmento i-esimo
        
        ogni riga della tabella è composta dai seguenti campi
        
        l : lunghezza del segmento
        
        b : indirizzo base del segmento
        
        informazioni addizionali : permessi di accesso al segmento, ...
      - la mappa di indirizzamento può essere implementata prevedendo per ogni processo una segment table (tabella dei segmenti) la cui voce s-esima contiene la locazione di base, b, e la lunghezza, l, del segmento s-esimo del processo
        
        operazione di mapping (forma semplificata)
        
        1) preleva l'istruzione di programma (s, a);
        
        2) utilizza s per indicizzare la segment table;
        
        si ottiene dalla segment table l'indirizzo di base, b, e la lunghezza, l, del segmento
        
        3) se a < 0 oppure se a > l, allora violazione di memoria;
        
        si attua la protezione da eventuali violazioni di memoria raffrontando l'indirizzo di word con la lunghezza l del segmento
        
        si può prevedere una protezione maggiore, inserendo in ciascun descrittore di segmento un numero di bit di protezione indicanti le modalità secondo cui si può accedere al segmento corrispondente
        
        4) (b+a) è la locazione di memoria richiesta
        
        un segmento può essere facilmente condiviso tra più processi basta prevedere un descrittore per il segmento interessato, all'interno della segment table di ogni processo.
        
        i bit di protezione presenti in ogni descrittore possono essere diversi, in modo che, ad esempio, un processo possa accedere ad un segmento in condivisione con modo "solo lettura", mentre un altro processo potrebbe essere in grado di effettuarvi anche operazioni di scrittura
      - la segmentazione consente così una condivisione elastica di programmi e dati tra i processi
      - in pratica, l'operazione di mapping degli indirizzi non è semplice come sembra suggerire quanto detto in precedenza!
        
        la maggiore complicazione è data dal fatto che per programmi di grosse dimensioni può non essere possibile contenere in memoria centrale tutti i segmenti, specialmente a causa della condivisione della stessa tra i vari processi.
        
        effettivamente si tratta di una situazione in cui la memoria virtuale è più ampia della memoria fisica e la si può gestire o impiegando la paginazione, oppure caricando e scaricando interi segmenti dalla memoria, a seconda delle esigenze
  - differenze tra mappa di indirizzamento per la paginazione e mappa di indirizzamento per la segmentazione:
    - scopo
      - nella segmentazione consiste nella suddivisione logica dello spazio di indirizzamento
      - nella paginazione consiste nella divisione fisica della memoria per realizzarne una ad un livello;
    - dimensioni
      - i segmenti possono essere di una qualsiasi dimensione stabilita dall'utente
      - le pagine hanno un'estensione fissa determinata dall'architettura della macchina
    - gestione dell'overflow
      - la divisione in numero di segmento e numero di word è di tipo logico e non vi è passaggio automatico al segmento successivo nell'eventualità di un overflow nel numero di word (se ciò avviene si genera una violazione di memoria).
      - la suddivisione dell'istruzione di programma in numero di word e numero di pagina è una funzione dell' hardware e nel caso in cui il numero di word superi un determinato valore, si provoca automaticamente l'incremento del numero di pagina
  - esempio, elaboratore Modular-One
    - possedeva tre coppie di registri ed i tre segmenti relativi sono utilizzati rispettivamente per il programma, i dati riservati ad un processo e quelli in condivisione tra più processi
  - altri sistemi che usavano questa tecnica
    - grosse macchine Burroughs (come il B6700)
    - PDP-ll/45
- segmentazione con paginazione
  - ogni segmento è, in genere, formato da varie pagine e possiede la propria page table
  - se alcune delle pagine del segmento si trovano in memoria centrale, la voce della segment table indica la page table del segmento
    - in caso contrario la relativa voce della segmente table è vuota
  - l'operazione di mapping, svolta dall'hardware di indirizzamento, è la seguente:
    - a) preleva l'istruzione di programma (s, a);
    - b) utilizza s per indicizzare la segment table;
    - c) se la s-esima voce è vuota, allora crea una nuova (vuota) page table, altrimenti preleva l'indirizzo della page table;
    - d) separa l'indirizzo di word a nel numero di pagina p e nel numero di word w;
    - e) utilizza p per indicizzare la page table;
    - f) se la voce p-esima è vuota, allora cerca e preleva la pagina dalla memoria di massa, altrimenti preleva l'indirizzo di pagina libera p';
    - g) aggiungi p' al numero di parola w per ottenere la locazione richiesta
  - note sull'operazione di mapping
    - i passi (a), (b) e (c) rappresentano il mapping dovuto a segmentazione;
    - i passi (d), (e), (f) e (g), rappresentano il mapping dovuto alla paginazione dei segmenti.
  - per incrementare le performance è possibile ricorrere ad una memoria associativa (TLB - Translation Lookaside Buffer)
    - consente di evitare i riferimenti aggiuntivi di memoria richiesti per accedere alla segment table ed alla page table
    - ciascun elemento della memoria associativa contiene il numero di segmento e il numero di pagina per quelle pagine cui si è avuto accesso più recentemente
    - i bit di segmento e di pagina per ogni istruzione di programma vengono cercati nella memoria associativa
      - se si trova riscontro, il numero di parola viene aggiunto all'indirizzo della pagina libera corrispondente, ottenendo la locazione di memoria richiesta.
      - se non si trova riscontro viene chiamata l'intera operazione di mapping descritta in antecedenza
  - un errore dovuto alla mancanza di un segmento fa sì che venga portato in memoria centrale l'intero segmento richiesto, mentre può darsi che qualche altro segmento venga relegato su memoria di massa al fine di creare spazio a sufficienza per contenere quello desiderato
  - vantaggi di questa tecnica
    - non è necessario che l'intero segmento sia presente in memoria centrale (vi devono essere sistemate solo le pagine in uso corrente)
    - non è necessario che le pagine occupino zone contigue di memoria
      - possono essere distribuite in tutta la memoria ed ubicate laddove si trovi una pagina libera appropriata
  - svantaggi
    - grande complessità della mappa di indirizzamento
    - appesantimento sul sistema determinato dalle page table
  - Esempi di sistemi che adottano questa tecnica
    - Honeywell 645
    - ICL 2900
    - IBM 370 (alcune versioni)
- segmentazione con paginazione nel Pentium Intel
  - la memoria virtuale del Pentium (e del Pentium pro) ha molte analogie con quella del MULTICS
    - in entrambi i casi abbiamo un organizzazione segmentata e paginata
    - il MULTICS ha 256K segmenti indipendenti
      - ogni segmento contiene fino a 64K word a 36 bit
    - il Pentium ha 16K segmenti indipendenti
      - ogni segmento contiene fino a 1 miliardo di word a 32bit
    - benché vi siano meno segmenti, nel Pentium, la maggiore dimensione del segmento è di gran lunga più importante!
      - infatti pochi programmi richiedono più di 1000 segmenti, ma molti programmi necessitano di segmenti in grado di contenere alcuni megabyte
  - il cuore della memoria virtuale del Pentium consiste di due tabelle
    - Local Descriptor Table - LDT
      - ogni programma ha la sua LDT
      - descrive i segmenti locali a ogni programma, compresi il suo codice, i suoi dati, il suo stack e così via
      - può contenere fino ad un massimo di 8K descrittori di segmento
    - Global Descriptor Table - GDT
      - esiste una sola GDT condivisa da tutti i programmi
      - descrive i segmenti di sistema, compreso il sistema operativo stesso
      - può contenere fino ad un massimo di 8K descrittori di segmento
  - selettore del segmento
    - è un numero a 16 bit, composto da 3 campi
      - 1) 13 bit indicano l'indice del descrittore all'interno della tabella LDT o GDT
        
        l'indice 0 non è consentito, esso può essere tranquillamente caricato in un registro di segmento per indicare che il registro di segmento non è attualmente disponibile
        
        questo registro, se usato, provoca un'eccezione
      - 2) 1 bit indica se il segmento è locale o globale (risiede nella LDT o GDT rispettivamente)
        
        0 = GDT
        
        1 = LDT
      - 3) 2 bit stabiliscono il livello di privilegio di accesso al segmento
  - descrittore di segmento
    - è un numero di 8 byte 2 word a 32bit
      - word 1
        
        Base 0-15 (16 bit) del segmento
        
        Limite 0-15 (16 bit) del segmento
      - word 2
        
        Base 24-31 (8 bit)
        
        G (1 bit)
        
        0 : il campo limite è in byte
        
        1 : il campo limite è in pagine
        
        D (1 bit)
        
        0 : segmenti da 16 bit
        
        1 : segmenti da 32 bit
        
        0 (1 bit)
        
        non viene specificato l'utilizzo nello schema
        
        1 bit
        
        non viene specificato l'utilizzo nello schema
        
        Limite 16-19 (4 bit)
        
        P (1 bit)
        
        0 : segmento non in memoria
        
        1 : segmento in memoria
        
        DPL - Descriptor Privilege Level (2 bit)
        
        S (1 bit)
        
        0 : sistema
        
        1 : applicativo
        
        Type (4 bit)
        
        tipo di segmento e protezione
        
        Base 16-23 (8 bit)
    - il campo Base è formato da 32 bit, (0-15), (16-23), (24-31)
      - è spezzato in tre parti e sparso all'interno del descrittore per compatibilità con il 286, nel quale il campo Base è costituito da soli 24 bit
      - consente di iniziare ogni segmento in un punto arbitrario all'interno dello spazio di indirizzamento lineare a 32 bit
    - il campo Limite è formato da 20 bit, (0-15), (16-19)
  - accedere ad un segmento
    - un programma Pentium carica innanzitutto il selettore del segmento in uno dei sei registri di segmento della macchina
    - durante l'esecuzione
      - il registro CS contiene il selettore del segmento codice
      - il registro DS contiene il selettore del segmento dati
      - gli altri segmenti sono meno importanti
    - nell'istante in cui si carica un selettore in un registro di segmento, il descrittore corrispondente viene estratto dalla LDT o GDT e immagazzinato in registri da un microprogramma, in modo da potervi accedere velocemente
    - il formato del selettore è stato scelto per facilitare l'individuazione del descrittore:
      - prima si seleziona o la LDT o la GDT, sulla base del bit 2 del selettore
      - il selettore viene poi copiato in un registro interno di lavoro, e i 3 bit di ordine inferiore vengono posti a 0.
      - infine, l'indirizzo della LDT o della GDT viene aggiunto al valore nel registro per ottenere un puntatore diretto al descrittore
        
        se per esempio il selettore 72 si riferisce alla voce 9 della GDT, posizionata all'indirizzo GDT+72
  - meccanismo di conversione della coppia (selettore, offset) in indirizzo fisico
    - appena il microprogramma sa qual è il registro di segmento usato, esso può individuare il descrittore completo corrispondente a tale selettore nei suoi registri interni.
      - se il segmento non esiste (selettore 0) o è attualmente memorizzato in una pagina sul disco, si ha un'eccezione (trap)
    - a questo punto il microprogramma controlla se l'offset oltrepassa il limite del segmento, nel qual caso si ha un'altra eccezione.
      - in teoria il descrittore dovrebbe semplicemente contenere un campo a 32 bit che fornisca la dimensione del segmento ma in realtà sono solo 20 i bit a disposizione per il Limite.
        
        occorre utilizzare il seguente schema:
        
        se il campo G (nel descrittore del segmento) è 0 il campo Limite contiene la dimensione esatta del segmento, fino al massimo di 1MB
        
        se il campo G è impostato a 1, il campo Limite da la dimensione del segmento in pagine invece che in MByte
        
        la dimensione di una pagina è fissata a 4KB (2 ¹² byte), così sono sufficienti 20 bit per segmenti che arrivano fino a 2 ³² byte
    - se il segmento è presente in memoria e l'offset entro i limiti
      - il Pentium aggiunge il campo Base (32 bit), contenuto nel descrittore, all'offset, per formare quello che viene chiamato indirizzo lineare
        
        se la paginazione viene disabilitata (usando un bit nel Global Control Register), l'indirizzo lineare viene interpretato come indirizzo fisico e viene direttamente inviato alla memoria per la lettura o la scrittura dei dati.
        
        in questo caso abbiamo uno schema a segmentazione puro, in cui l'indirizzo base di ogni segmento viene fornito all'interno del suo descrittore.
        
        i segmenti possono incidentalmente sovrapporsi, probabilmente perché costerebbe troppa fatica e prenderebbe troppo tempo verificare che essi siano disgiunti
        
        se la paginazione è abilitata, l'indirizzo lineare viene interpretato come indirizzo virtuale e tradotto nel corrispondente indirizzo fisico usando le page table, come avviene nei nostri esempi precedenti.
        
        la sola vera complicazione è che, con un indirizzo virtuale a 32 bit e una pagina di 4K, un segmento può contenere i milione di pagine: pertanto si usa uno schema di corrispondenza con tabelle a due livelli per ridurre la dimensione della tabella delle pagine dei segmenti piccoli
      - ogni programma in esecuzione ha una directory delle pagine che consiste in 1024 elementi a 32 bit.
        
        essa è posizionata in un indirizzo puntato da un registro globale.
        
        ogni elemento punta a una page table contenente anch'essa 1024 elementi a 32 bit.
        
        gli elementi nella page table puntano ai page frame (pagine fisiche)
  - indirizzo lineare (32 bit)
    - Dir (10 bit)
      - viene usato come indice nella directory delle pagine per individuare un puntatore alla page table opportuna
    - Page (10 bit)
      - viene usato come indice nella page table per individuare la page frame
    - Offset (12 bit)
      - viene sommato all'indirizzo della page frame per ottenere l'indirizzo della word o byte che è stata indirizzata
  - page table
    - ogni elemento è costituito da 32 bit
    - 20 bit contengono un indice di page frame
    - i bit rimanenti contengono i bit di accesso e i bit di modifica, posti a 1 dall'hardware a vantaggio del sistema operativo, i bit di protezione e altri bit di utilità
    - ogni page table può contenere 1024 elementi ossia 1024 riferimenti a page frame
      - poichè ogni page frame ha dimensione 4KB ogni page table può gestire fino 4 MByte di memoria
    - un segmento più corto di 4MB avrà una directory delle pagine con un solo elemento, ovvero puntatore alla sua unica e sola tabella delle pagine.
      - in questo modo, la memoria necessaria per le tabelle dei segmenti più corti è di sole due pagine, invece del milione di pagine che sarebbero necessarie in una tabella delle pagine a un solo livello
  - per evitare di eseguire continui riferimenti in memoria, il Pentium, come il MULTICS, ha un piccolo TLB (Translation Lookaside Buffer) ossia memoria associativa, che traduce direttamente la combinazioni Dir-Pagina usate più recentemente in indirizzi di pagina fisica
    - solo quando la pagina richiesta non è presente nel TLB viene utilizzato il meccanismo completo illustrato in precedenza e si aggiorna il TLB
      - in pratica le miss su TLB sono rare e le prestazioni buone
  - se un'applicazione non necessita della segmentazione e si accontenta di uno spazio di indirizzamento singolo paginato a 32 bit, tutti i registri di segmento possono essere caricati con uno stesso selettore, il cui descrittore ha Base=0 e Limite impostato al valore massimo
    - l'offset dell'istruzione sarà poi l'indirizzo lineare e vi sarà un solo spazio in uso (come accade nella paginazione pura)
      - tutti i sistemi operativi per Pentium funzionano in questa maniera, l'unico che faceva eccezione era OS/2
  - per mantenere la compatibilità col 286 è consentita anche la segmentazione pura (la paginazione è disabilitata)
metodi di allocazione della memoria
- consentono di ottimizzare l'utilizzo dei meccanismi di implementazione della memoria virtuale
- sono suddivisi in tre macro categorie
  - 1) metodi di sostituzione
    - determinano quali informazioni vanno rimosse dalla memoria centrale rendendo disponibili regioni di memoria
    - sono differenti a seconda che il sistema sia paginato o no
  - 2) metodi di ricerca e prelievo (fetch)
    - specificano quando le informazioni vanno caricate in memoria centrale
    - sono identici sia nel caso di sistemi paginati che di sistemi non paginati
  - 3) metodi di posizionamento
    - specificano dove vanno messe le informazioni all'interno della memoria centrale selezionando così un sottoinsieme di alcune regioni disponibili
    - sono differenti a seconda che il sistema sia paginato o no
metodi di posizionamento per sistemi segmentati
- si applicano nei casi in cui lo spazio di indirizzamento virtuale è segmentato oppure implementato tramite coppie di registri limite e base
- si indicano con la parola "segmento" i blocchi di informazioni che sono in corso di trasferimento
  - se si tratta di un singolo sistema con registri limite e base, un segmento rappresenterà nella sua interezza lo spazio di indirizzamento di un processo
- la situazione che si presenta consiste nel periodico inserimento o cancellazione di segmenti dalla memoria centrale.
  - inserimento e cancellazione si attuano facendo ricorso, rispettivamente, ai metodi di ricerca e prelievo (fetch) e di sostituzione.
- si dice che il sistema è in stato di equilibrio se, entro un certo intervallo di tempo, lo spazio liberato tramite cancellazione è uguale a quello riempito tramite inserimento
- la memoria si presenta suddivisa come una scacchiera, in un certo istante ci sarà alternanza di regioni allocate e buchi (regioni di memoria libere)
- hole list
  - è la lista delle locazioni e delle dimensioni dei "buchi" non allocati
- il metodo di posizionamento deve decidere quale buco utilizzare, aggiornando la hole list in seguito a ogni inserimento:
  - se il segmento da posizionare è più piccolo del buco da utilizzare, verrà posto dalla parte "sinistra" ovvero sul "fondo" del buco.
    - questa tattica rende minima l'entità della frammentazione.
  - se il segmento da posizionare è più vasto di qualsiasi buco disponibile, il metodo di posizionamento ha il compito di spostare i segmenti già in memoria per creare un buco largo a sufficienza
- esistono molti algoritmi di posizionamento, per esempio quello di Knuth (1968)
  - x1,x2,...,xn indicano le dimensioni dei buchi
  - s indica la dimensione del segmento da posizionare
  - i 4 più importanti algoritmi di posizionamento sono
    - a) il più adatto
      - la list hole è ordinata in maniera crescente per dimensione dei buchi, x1 <= x2 <= ... <= xn
      - posiziona il segmento nel primo buco tale che s <= xi
    - b) il meno adatto
      - la list hole è ordinata per ordine decrescente di dimensione dei buchi, x1 >= x2 >= ... >= xn
      - posiziona il segmento nel primo buco e inserisci il buco formato dallo spazio rimanente nella posizione adeguata in lista
    - c) il primo buco adatto
      - la list hole è ordinata per ordine crescente di indirizzo base dei buchi
      - posiziona il segmento nel primo buco tale che s <= xi
      - nel tempo questo algoritmo porta all'accumularsi di tanti piccoli buchi verso l'inizio della lista
        
        per evitare un tempo di ricerca eccessivo per i segmenti più grandi, la posizione di inizio ricerca si può far avanzare ciclicamente di un elemento dopo ogni operazione di ricerca
    - d) buco gemellare
      - per applicare questo algoritmo le dimensioni dei segmenti devono essere potenze di 2
      - si predispone una lista distinta per tutti i buchi aventi dimensione pari a 2 ¹ ,2 ² ,...,2 ^k
      - si può prelevare un buco dalla lista (i+1), dividerlo a metà creando in tal modo una coppia di "gemelli" con dimensione 2i da inserire nella lista (i)
      - viceversa, una coppia di gemelli può essere tolta dalla lista (i), i buchi possono essere uniti assieme e il nuovo buco può essere inserito nella lista (i+1).
      - l'algoritmo che serve a trovare un buco di dimensioni 2i è ricorsivo:
        
        procedure prendi un buco (i);
        
        begin if i = K + I then insuccesso;
        
        if lista degli i è vuota then
        
        begin prendi un buco (i+ 1);
        
        dividi il buco in due gemelli;
        
        metti i gemelli nella lista degli i
        
        end;
        
        prendi il primo buco nella lista degli i
        
        end
- alcune considerazioni:
  - l'algoritmo (a) da un punto di vista intuitivo sembra rendere minimo lo spreco di spazio frammentato per ogni buco prescelto
    - l'allocazione di uno spazio prelevato da un buco piccolo comporta la creazione di un altro buco ancora più piccolo con scarse probabilità di utilizzo
  - l'algoritmo (b) si comporta meglio dell'algoritmo (a)
    - l'allocazione di uno spazio prelevato da un buco grande ha più probabilità di lasciare a disposizione un altro buco abbastanza grande da tornare utile in seguito
  - un problema comune a tutti i metodi di posizionamento descritti consiste nella frammentazione:
    - suddivisione della memoria libera in buchi tanto piccoli da renderne impossibile l'occupazione da parte di nuovi segmenti.
    - in questo caso risulta necessario un qualche compattamento della memoria:
      - tutti i segmenti, cioè, devono essere spostati verso il basso in modo da far comparire un unico grande buco all'inizio della memoria.
    - è più agevole eseguire il compattamento se i buchi sono listati per ordine di indirizzo, come accade nell'algoritmo (c).
  - una soluzione alternativa consiste nel compattare la memoria ogniqualvolta viene prelevato un segmento, evitando così completamente il fenomeno della frammentazione;
    - l'appesantimento del sistema dovuto a frequenti operazioni di compattamento è compensato dal vantaggio di non dover effettuare operazioni di ricerca nella lista dei buchi ogniqualvolta si deve posizionare un segmento
metodi di posizionamento per sistemi paginati
- sono più semplici di quelli per sistemi segmentati
- per posizionare k pagine è necessario un semplice criterio che liberi k page frame
- non avviene frammentazione, come descritta per i sistemi segmentati, in quanto ogni pagina ha le stesse dimensioni
  - avviene una frammentazione interna dovuta al fatto che lo spazio necessario ad un processo non è mai un multiplo esatto delle pagine
    - in genere una parte, mediamente la metà, dell'ultima pagina allocata va sprecata
  - se lo spazio di indirizzamento è formato da più segmenti paginati, il grado di frammentazione interna si moltiplica per il numero dei segmenti correntemente contenuti in memoria centrale
metodi di sostituzione per sistemi paginati
- hanno il compito di decidere quali blocchi di informazioni relegare su memoria di massa al momento di trovare spazio per nuovi blocchi in memoria centrale
  - in linea di principio, si vuole sostituire quella pagina che in futuro non sarà richiamata se non dopo un lungo intervallo di tempo
  - è sempre difficile fare dei pronostici e la cosa migliore da farsi è desumere, dall'andamento precedente, qual è l'andamento che probabilmente si avrà in futuro
    - questa deduzione è tanto più accurata quanto più prevedibile è il comportamento del programma
- i tre algoritmi più comuni sono:
  - a) pagina usata meno recentemente (LRU; least recently used)
    - sostituisci la pagina usata meno recentemente.
    - alla base vi è il presupposto che il comportamento futuro segua da vicino quello più recente.
    - l'appesantimento relativo gravante sul sistema consiste nel registrare la sequenza di accesso a tutte le pagine.
  - b) Pagina usata meno frequentemente (LFU; least frequently used)
    - Sostituisci la pagina che è stata usata meno frequentemente durante l'intervallo di tempo immediatamente precedente
    - la giustificazione in questo caso è analoga a quanto detto nel precedente punto (a) e il conseguente appesantimento del sistema consiste nel prevedere un "conteggio di utilizzo" (use count) per ogni pagina.
    - uno svantaggio è dato dal fatto che, in generale, una pagina caricata recentemente avrà un numero basso di conteggio di utilizzo e potrebbe pertanto venire sostituita sconsideratamente.
      - per evitare tale fenomeno si può inibire la sostituzione di quelle pagine che sono state caricate durante l'intervallo di tempo immediatamente precedente.
  - c) FIFO (First In-First Out)
    - sostituisci la pagina che è rimasta più a lungo residente in memoria
    - si tratta di un algoritmo semplice che appesantisce il sistema solamente a causa della necessaria registrazione della sequenza di caricamento delle pagine.
    - non tiene conto, però, della possibilità che la pagina da più tempo in memoria sia anche quella cui si fa riferimento più spesso.
- studi svolti in simulazione (Colin, 1971) hanno dimostrato che i tre algoritmi hanno prestazioni differenti che raramente si discostano oltre il 15%
  - in relazione al numero di trasferimenti richiesti durante l'esecuzione di svariati lavori
- in generale, l'algoritmo (c) offre prestazioni più scarse rispetto agli altri due.
- è importante osservare che, se le pagine non sono state modificate, non è necessario riportarle su memoria secondaria, a condizione che in quest'ultima ne esista già una copia.
  - si può prendere nota dell'eventuale avvenuta modifica di una pagina particolare utilizzando un solo bit della voce della page table corrispondente.
metodi di sostituzione per sistemi non paginati (segmentati)
- hanno il compito di sostituire segmento che ha meno probabilità di venire utilizzato nell'immediato futuro
- risultano validi i 3 algoritmi visti per i sistemi paginati con l'introduzione di una restrizione dovuta al fatto che i segmenti non hanno le stesse dimensioni
  - la scelta relativa a quale segmento riportare in memoria secondaria viene influenzata dalla dimensione dello stesso
  - se si deve portare in memoria centrale un segmento piccolo, sarà necessario sostituire solo un segmento piccolo; d'altra parte, il posizionamento di un segmento più vasto richiede la sostituzione di un segmento altrettanto vasto (o di svariati segmenti più piccoli)
- algoritmo più semplice
  - si sostituisce quel segmento (sempre che esista), che assieme ad eventuali buchi contigui liberi uno spazio sufficiente al segmento entrante
  - se più segmenti soddisfano questa condizione, se ne può selezionare uno usando uno dei metodi esaminati in precedenza, per esempio il LRU.
  - se nessun segmento soddisfano questa condizione, bisognerà sostituire più segmenti;
    - una possibilità di scelta consiste nel privilegiare il più piccolo gruppo di segmenti contigui in grado di liberare lo spazio occorrente.
  - il pericolo intrinseco in un algoritmo di questo tipo è che il segmento (o gruppo di segmenti) sostituito, essendo scelto prevalentemente in base a criteri dimensionali, potrebbe risultare nuovamente necessario entro breve tempo
    - si può ridurre tale rischio selezionando i segmenti meramente sulla base del metodo LRU, ad esempio, ma poiché i segmenti prescelti probabilmente non saranno contigui, risulterà necessaria qualche forma di compattamento
- sono stati sviluppati algoritmi molto complessi per risolvere queste problematiche come quelli di Knuth (1968) e Denning (1970).
metodi di ricerca e prelievo (fetch)
- determinano quando spostare un blocco di informazioni dalla memoria secondaria in quella centrale
  - le considerazioni che seguono valgono sia per i sistemi paginati che per quelli segmentati
- esistono due macro categorie
  - prelievo su richiesta
    - prelevano i blocchi quando sono necessari
    - una condizione di blocco mancante (segmento o pagina che sia) genera una richiesta di ricerca e prelievo, mentre i metodi di posizionamento e/o sostituzione provvedono all'allocazione di memoria per il nuovo blocco
    - vengono di solito usati nei sistemi non paginati ed in alcuni paginati
  - prelievo anticipato
    - prelevano i blocchi precedentemente al manifestarsi delle esigenze
    - vengono di solito usati nei sistemi paginati
    - la loro efficacia si basa sull'affidabilità delle previsioni relative al futuro comportamento di un programma.
    - tali previsioni si possono basare su due fattori
      - 1) natura della costruzione dei programmi
        
        molti programmi presentano un comportamento "operativo in un contesto":
        
        suddividendo il tempo di esecuzione in tanti piccoli intervalli accade che nell'ambito di ognuno di essi un programma
        
        tende ad operare entro un modulo logico particolare
        
        trae le proprie istruzioni da un'unica procedura ed i propri dati da un'area singola
        
        i riferimenti di programma tendono così ad essere raggruppati in piccole locazioni di spazio logico
        
        la locazione di riferimento si rafforza per mezzo del frequente verificarsi di cicli iterativi; più è ridotto il ciclo, minore è la frammentazione dei riferimenti
        
        l'osservazione di questo comportamento ha condotto al postulato (Denning, 1970) del cosiddetto principio di località:
        
        i riferimenti di programma tendono ad essere raggruppati in zone di spazio logico circoscritte, le quali tendono a mutare solo in modo discontinuo e periodico
        
        la validità del principio di località varia da programma a programma;
        
        sarà maggiore, per esempio, nel caso di programmi che accedono ad array sequenziali, rispetto a programmi che accedono a strutture di dati complesse
      - 2) inferenze fondate sul comportamento del processo precedente
- i metodi su richiesta sono solitamente più semplici da implementare rispetto a quelli anticipati
- Il principio di località è stato impiegato da Denning nell'ambito di una memoria paginata per formulare il modello dell'area di lavoro relativo al comportamento dei programmi
il modello dell'area di lavoro per il comportamento dei programmi - modello Working Set (Denning, 1970)
- rappresenta il tentativo di definire una struttura portante per poter comprendere le prestazioni dei sistemi paginati in condizioni di multiprogrammazione
- i metodi di gestione della memoria descritti nel paragrafo precedente si basano sullo studio relativo al modo in cui si comportano i processi in stato di isolamento;
  - non tengono conto di eventuali interazioni che potrebbero verificarsi per il fatto di avere in macchina parecchi processi alla volta.
  - infatti, il competere per l'utilizzo dello spazio di memoria può portare i processi ad un comportamento che non si verificherebbe se ognuno di essi fosse eseguito separatamente dagli altri
- il fenomeno del trashing (Denning, 1968)
  - è la situazione in cui il canale della memoria di massa diventa saturo e la maggior parte dei processi resta bloccata in attesa di un trasferimento di pagina, il processore viene sottoutilizzato
  - si consideri un sistema dotato di un solo processore e memoria paginata, nel quale il livello di multiprogrammazione (cioè il numero di processi presenti in memoria) è in costante aumento.
  - col crescere del livello di multiprogrammazione, aumenta pure l'utilizzazione del processore
    - la routine di smistamento ha sempre maggiori probabilità di trovare un processo da mettere in esecuzione.
  - ciò è vero fintanto che il livello di multiprogrammazione viene mantenuto al di sotto di una determinata soglia, in funzione dell'estensione della memoria a disposizione.
  - tuttavia, se il livello di multiprogrammazione supera tale limite, si riscontra un marcato aumento del movimento di paginazione tra memoria centrale e secondaria, accompagnato da un'improvvisa flessione dell'utilizzazione del processore.
    - l'alto livello di multiprogrammazione rende impossibile mantenere in memoria per tutti i processi pagine sufficienti ad evitare la generazione di un numero enorme di interrupt causati da page fault
- per ogni processo è necessario mantenere in memoria centrale un numero minimo di pagine, dette area di lavoro del processo, prima che esso possa utilizzare effettivamente la CPU
  - se le pagine presenti in memoria sono inferiori a tale minimo, il processo verrà interrotto continuamente per l'assenza di pagine, il che contribuisce a dar luogo al fenomeno del thrashing
  - per evitare questa situazione, il livello di multiprogrammazione non deve superare il livello che consente di tenere in memoria centrale le aree di lavoro relative a tutti i processi.
- individuare l'area di lavoro di un processo
  - occorre osservare accuratamente la storia recente del processo interessato facendo ricorso al principio di località
  - in modo formale avremo:
    - w(k,t) è l'insieme (area di lavoro) costituito da tutte le pagine utilizzate dai k riferimenti in memoria più recenti, all'istante t
      - un riferimento in memoria può ricercare un istruzione o dati o memorizzare dei dati
    - w(k,t) è una funzione su k monotona non decrescente
    - il limite w(k,t) al crescere di k è finito, poichè un programma non può riferire più pagine di quante ne possa contenere il suo spazio di indirizzamento
    - w(k,t) cresce rapidamente per valori piccoli di k e rallentando gradatamente per valori grandi di k fino a giungere l'asintoto orizzontale
  - con l'aumentare di k (cioè, più si guarda indietro nel tempo) si prevede di riscontrare sempre meno pagine aggiuntive nell'area di lavoro.
    - ciò consente di fissare per k un valore (poniamo k0) opportunamente piccolo, nella consapevolezza che anche un valore più alto non darebbe luogo ad un aumento significativo dell'estensione dell'area di lavoro
- per quanto riguarda i metodi di sostituzione e di ricerca e prelievo si usa la seguente regola:
  - esegui un processo solo se tutta l'area di lavoro relativa si trova in memoria centrale e non spostare mai una pagina facente parte dell'area di lavoro di un processo.
- sebbene le aree di lavoro di alcuni processi siano definite in modo piuttosto arbitrario e benché il principio di località non sia valido per alcuni programmi, l'applicazione della regola suesposta può dare un contributo significativo alla prevenzione del fenomeno del thrashing.
- il modello dell'area di lavoro viene largamente usato, nonostante tra i sistemi operativi la definizione dell'area di lavoro sia piuttosto variabile.
- è importante notare che la regola data in precedenza è più di un puro metodo di gestione della memoria, infatti rende implicita la correlazione tra allocazione di memoria ed allocazione della CPU
  - nella pratica la gestione di una singola risorsa non può essere sempre disgiunta dai fattori relativi alle altre risorse
implementazione nel nostro sistema ipotetico
- al fine di applicare nel nostro sistema operativo ipotetico i meccanismi visti nel paragrafo sull'implementazione della memoria virtuale, aggiungiamo quanto segue all'ambiente volatile di ciascun processo:
  - una copia del contenuto del registro limite e del registro base oppure
  - un puntatore alla sua segment table oppure un puntatore alla sua page table
    - a seconda dell'architettura della macchina a nostra disposizione.
- se disponiamo di una macchina senza paginazione, introdurremo anche la hole list quale struttura dati a cui la tabella centrale è collegata tramite puntatore.
- lo strato relativo alla gestione della memoria nel nostro sistema è costituito da un codice per l'implementazione dei metodi presi in esame in precedenza.
  - il nuovo strato della "cipolla" abbraccia tutto lo strato precedente (costituito da FLIH, wait and signal, routine di smistamento)