Sistemi Operativi - Appunti Teoria Seconda Parte

Lezioni di teoria SO1 (seconda parte) - Lezione 8.1

Memoria centrale

La memoria consiste in un vettore (buffer) di parole o byte, ciascuno con il proprio indirizzo. La CPU preleva le istruzioni dalla memoria sulla base del contenuto del PC (Program Counter) che possono determinare ulteriori letture (load) e scritture (store) in specifici indirizzi di memoria. La memoria vede soltanto un flusso di indirizzi e non sa come sono generati e a cosa servano.

Dispositivi essenziali

Bisogna assicurarsi che ciascun processo abbia uno spazio di memoria separato, per la protezione del SO e dei processi da accessi indesiderati dei processi in modalità utente. Quindi, occorre determinare l’intervallo degli indirizzi all’interno di esso, garantendo che un processo possa accedere solo legalmente. Si può implementare il meccanismo di protezione tramite due registri:

• Registri base: contiene il più piccolo indirizzo legale della memoria fisica.
• Registri limite: determina la dimensione dell’intervallo ammesso.

Esempio: se i registri base e limite contengono rispettivamente i valori 300040 e 120900, al programma si consente l’accesso alle locazioni di memoria di indirizzi compresi tra 300040 e 420939, estremi inclusi. Per proteggere la memoria, la CPU, o un modulo HW esterno, si confronta ciascun indirizzo generato in modalità utente con i valori contenuti nei due registri. Qualsiasi tentativo da parte di un programma eseguito in modalità utente di accedere alle aree di memoria riservate al SO o a una qualsiasi area di memoria riservata ad altri utenti, comporta l’invio di un segnale di eccezione che restituisce il controllo al SO che, a sua volta, interpreta l'evento come un errore fatale. Questo schema impedisce a qualsiasi programma utente di alterare (accidentalmente o intenzionalmente) il codice o le strutture dati, sia del SO sia degli altri utenti. Solo il SO può caricare e modificare i registri base e limite, ed impedisce la medesima operazione ai programmi utenti.

Associazione degli indirizzi

In genere un programma risiede in un disco in forma di un file binario eseguibile e, per essere eseguito, va caricato in memoria e all’interno di un processo (in Linux si usa exec). L’insieme dei processi da essere trasferiti in memoria, che attendono di essere eseguiti, forma la coda d’ingresso. Per poter caricare un programma utente in una zona di memoria, sono necessari vari passaggi, alcuni facoltativi, in cui gli indirizzi sono rappresentabili in modi diversi. Gli indirizzi del programma sorgente sono:

• Indirizzi simbolici
• Indirizzi rilocabili
• Indirizzi assoluti

Tipi di associazione:

• Compilazione: il compilatore genera indirizzi simbolici.
• Caricamento: il loader genera indirizzi assoluti.
• Esecuzione: il SO può spostare il processo da un segmento di memoria ad un altro.

Indirizzi logici e fisici

• Indirizzo logico: generato dalla CPU.
• Indirizzo fisico: generato dalla MMU.

I metodi di associazione degli indirizzi nelle fasi di compilazione e di caricamento producono indirizzi logici e fisici identici, mentre nella fase d’esecuzione, gli indirizzi logici (in questo caso chiamati indirizzi virtuali) non coincidono con quelli fisici. Questa associazione a runtime è svolta da un dispositivo detto unità di gestione della memoria (Memory Management Unit, MMU). Il registro di base è ora denominato registro di rilocazione: quando un processo utente genera un indirizzo, prima dell’invio all’unità di memoria, si somma a tale indirizzo il valore contenuto nel registro di rilocazione. Esempio: se il registro di rilocazione contiene il valore 14000, un tentativo da parte dell'utente di accedere alla locazione 0 è dinamicamente rilocato alla locazione 14000; un accesso alla locazione 346 corrisponde alla locazione 14346. Il programma utente non considera mai gli indirizzi fisici reali, ma crea un puntatore alla locazione 346, lo memorizza, lo modifica, lo confronta con altri indirizzi. Quindi esistono due diversi tipi di indirizzi: gli indirizzi logici (nell’intervallo da 0 a max) e gli indirizzi fisici (nell’intervallo da r + 0 a r + max per un valore di base r). L’utente genera solo indirizzi logici e pensa che il processo sia eseguito nelle posizioni da 0 a max.

Caricamento dinamico (Dynamic loading) e librerie condivise

Per migliorare l’utilizzo della memoria si può ricorrere al caricamento dinamico mediante il quale si carica in memoria una procedura del programma solo quando viene richiamata. Vantaggio: una procedura che non si adopera non viene caricata. Questo metodo è utile soprattutto quando servono grandi quantità di codice per gestire casi non frequenti (es le procedure di gestione degli errori). Il caricamento dinamico non richiede particolare intervento del SO, ma spetta agli utenti progettare i programmi.

Librerie collegate staticamente: Sono trattate come moduli oggetto, nel binario del programma.

Librerie dinamiche: Vengono collegate al programma solo al momento dell’esecuzione. Nel programma c’è uno stub (porzione di codice di riferimento) che indica come localizzare la libreria. Lo stub controlla se la procedura richiesta è in memoria, altrimenti la carica. Questo in seguito sostituisce sé stesso con l’indirizzo esatto della procedura, che poi viene eseguita senza costi aggiuntivi per il collegamento dinamico. Tutti i processi usano la stessa copia della libreria.

Overlay

Si mantengono in memoria solo le istruzioni e i dati che vengono richiesti ad un dato istante. Quando sono necessarie altre istruzioni, queste vengono caricate nello spazio che era precedentemente occupato dalle istruzioni che non vengono più utilizzate. L’overlay è richiesto quando un processo è più grande della memoria allocatagli. L’esecuzione è rallentata a causa dell’operazione di I/O necessaria per caricare l’overlay. Viene implementato dall’utente e non viene richiesto alcun supporto speciale da parte del SO. Il progetto di programmi con strutture di overlay è complesso.

Avvicendamento dei processi

Swapping

Il gestore di memoria scarica il processo appena terminato e carica un nuovo processo nello spazio libero. Ogni processo viene scambiato con un altro quando termina il quanto di tempo o se viene prelazionato.

• Si deve caricare nello stesso spazio solo se l’associazione degli indirizzi è a livello di caricamento.
• Si deve caricare in uno spazio diverso solo se l’associazione degli indirizzi è nella fase d’esecuzione, poiché gli indirizzi fisici si calcolano in questa fase.

Se lo scheduler della CPU decide di eseguire un processo, richiama il dispatcher, che controlla se il primo processo della coda si trova in memoria. Se non c’è spazio libero, il dispatcher scarica un processo dalla memoria e vi carica il processo richiesto dallo scheduler. Ricarica poi i registri e trasferisce il controllo al processo selezionato. Per essere eseguito, un processo deve trovarsi in memoria centrale, ma si può trasferire temporaneamente nella coda dei processi pronti della memoria ausiliaria o secondaria (deve esserci) quando non è in esecuzione. Quando riprende l’esecuzione, si riporta il processo in memoria centrale.

Esempi:

• Caso di scheduling circolare (round-robin). Un processo che termina il suo quanto può essere scaricato dalla memoria e nello spazio di memoria appena liberato viene caricato un altro processo (swapping o avvicendamento dei processi in memoria).
• Caso di scheduling a priorità. Si scaricano dalla memoria i processi con priorità più bassa per far spazio a quelli con priorità più alta (roll in, roll out). Quando quest’ultimo termina, si può ricaricare quello con priorità più bassa.

Il quanto di tempo deve essere sufficientemente lungo da permettere che un processo, prima d’essere sostituito, esegua una quantità ragionevole di calcolo. In questo sistema, il tempo di avvicendamento (cambio di contesto/context switch time) è dominato dal tempo di trasferimento (es. processo utente di 100 MB di memoria). Per scaricare un processo dalla memoria è necessario essere certi che sia completamente inattivo. In caso di I/O asincrono pendente: un processo che si vuole scaricare può essere nell’attesa del completamento di un’operazione di I/O, quindi non è scaricabile. Lo swapping deve richiedere pochi movimenti di testina dell’harddisk, si usa quindi una porzione di disco dedicata, separata dal file system.

L’avvicendamento accade se viene lanciato un processo e non c’è spazio disponibile in memoria centrale:

• L’utente decide quando si può scaricare il processo, non lo scheduler (per questo non è un vero e proprio avvicendamento).
• Ciascun processo swapped out (scaricato) rimane tale finché l’utente non lo riseleziona per l’esecuzione.

Altro esempio: in vecchi sistemi UNIX, si abilitava solo oltre una quantità limite di memoria.

Allocazione contigua della memoria

La memoria centrale deve contenere due partizioni: sia il SO sia i vari processi utenti. Perciò è necessario assegnare le diverse parti della memoria centrale nel modo più efficiente. Ci sono due metodi per l’allocazione della memoria:

• MFT: suddivide la memoria in partizioni di dimensione fissa e ognuna deve contenere esattamente un processo, quindi il grado di multiprogrammazione è limitato dal numero di partizioni. Si usava nel sistema IBM OS/360, ma non è più in uso.
• MVT: suddivide la memoria in partizioni di dimensione variabile ed è una generalizzazione dell’MFT. Si usa una tabella di partizioni di memoria occupate e libere: inizialmente tutta la memoria è a disposizione dei processi utente. Si tratta di un grande blocco di memoria disponibile, un buco (hole). Al caricamento di un processo si cerca un buco abbastanza grande, la parte rimanente si usa in futuro. Si crea una alternanza di zone occupate da processi e buchi. Quando entrano nel sistema, i processi vengono inseriti in una coda d’ingresso (scheduling). La memoria si assegna ai processi in coda finché si possono soddisfare i requisiti del processo (cioè finché c’è un buco grande abbastanza). Se non c’è un buco grande si attende, altrimenti si cerca nella coda un altro processo.

Questa strategia prevede una allocazione dinamica della memoria. Il sistema cerca nella memoria un buco di dimensioni sufficienti per contenere un processo che necessita di tale memoria. Se il buco è più grande della memoria richiesta (cioè sempre) si divide in due: un nuovo buco più piccolo e un segmento di memoria allocata per il processo. Quando termina, un processo rilascia il blocco di memoria, che si reinserisce nell’insieme dei buchi; se si trova accanto ad altri buchi, si uniscono tutti i buchi adiacenti per formarne uno più grande. Si crea però il problema della frammentazione esterna: Per n blocchi assegnati se ne perdono 0,5*n per la frammentazione. Quando si caricano e si rimuovono i processi dalla memoria, si frammenta lo spazio libero della memoria in tante piccole parti. Si ha la frammentazione esterna se lo spazio di memoria totale è sufficiente per soddisfare una richiesta, ma non è contiguo. Questo problema può essere molto grave: nel caso peggiore può verificarsi un blocco di memoria libera sprecata. Se tutti questi piccoli pezzi di memoria costituissero un unico blocco libero di grandi dimensioni, si potrebbero eseguire molti più processi. Una soluzione è la compattazione, cioè riunire la memoria libera in un unico grosso blocco. Tuttavia non è sempre possibile. Ci sono strategie per scegliere il buco [la 1 e la 2 sono migliori della 3]:

• First-fit. Si assegna il primo buco abbastanza grande. La ricerca può cominciare sia dall’inizio dell’insieme di buchi sia dal punto in cui era terminata la ricerca precedente (velocità +, efficienza +).
• Best-fit. Si assegna il più piccolo buco in grado di contenere il processo. Si deve compiere la ricerca in tutta la lista sempre che questa non sia ordinata per dimensione (velocità -, efficienza +).
• Worst-fit. Si assegna il buco più grande. Si esamina tutta la lista, se non è già ordinata per dimensione (velocità -, efficienza -).

Paginazione

La paginazione è un metodo di gestione della memoria che permette che lo spazio degli indirizzi fisici di un processo non sia contiguo. Elimina il problema della sistemazione di blocchi di memoria di diverse dimensioni in memoria ausiliaria, che riguarda la maggior parte dei metodi di gestione della memoria analizzati.

La memoria logica viene suddivisa in blocchi di pari dimensione (pagine) mentre la memoria fisica in blocchi di dimensione fissa (frame o pagine fisiche). Quando si deve eseguire un processo, si caricano le sue pagine nei frame disponibili dello spazio fisico, prendendole dalla memoria ausiliaria. Ogni indirizzo generato dalla CPU è diviso in due parti:

• Numero di pagina (p): indice di riga per la tabella delle pagine, contenente l’indirizzo del frame base in memoria fisica di ogni pagina.
• Scostamento di pagina (d): l’indirizzo del frame si combina con lo scostamento di pagina per definire l’indirizzo della memoria fisica, che poi s’invia all’unità di memoria.

La dimensione di una pagina e di un frame è definita dall’architettura del calcolatore ed è una potenza di 2, compresa tra 512 byte e 16 MB. Se la dimensione dello spazio degli indirizzi logici è 2^m e la dimensione di una pagina è 2ⁿ unità di indirizzamento (byte o parole), allora gli m-n bit più significativi di un indirizzo logico indicano il numero di pagina, e gli n bit meno significativi indicano lo scostamento.

Esempio: con pagine di 4 byte e una memoria fisica di 32 byte (8 frame). L’indirizzo logico 0 è la pagina 0 con scostamento 0. Secondo la tabella delle pagine, la pagina 0 si trova nel frame 5. Quindi all’indirizzo logico 0 corrisponde l’indirizzo fisico 20 (= (5 * 4) + 0). All’indirizzo logico 3 (p 0, d 3) corrisponde l’indirizzo fisico 23 (= (5 * 4) + 3) ecc. Quindi la paginazione è una forma di rilocazione dinamica: di ogni indirizzo logico l’architettura di paginazione fa corrispondere un indirizzo fisico.

Paginazione e frammentazione

Con la paginazione si può evitare la frammentazione esterna: qualsiasi frame libero si può assegnare a un processo che ne ha bisogno. Non si può evitare la frammentazione interna poiché l’ultimo frame assegnato può non essere completamente pieno. Esempio: Se le pagine sono di 2048 byte, un processo di 72.766 byte necessita di 35 pagine più 1086 byte. Si assegnano 36 frame, quindi si ha una frammentazione interna di 2048 - 1086 = 962 byte. Se la dimensione del processo è indipendente dalla dimensione della pagina, ci si deve aspettare una frammentazione interna media di mezza pagina per processo. Quindi conviene usare pagine di piccole dimensioni per meno frammentazione interna. Aumenta il carico per gli elementi della tabella I/O su disco più efficiente se è maggiore il numero.

Informazioni di paginazione

Il SO mantiene le informazioni sui frame (blocchi di memoria), ognuno contenente un elemento che indica se sia libero oppure se è assegnato e a quale processo. Il SO mantiene una copia della tabella delle pagine di ciascun processo, che viene usata anche dal dispatcher per impostare l’architettura HW di paginazione quando a un processo sta per essere assegnata la CPU. La paginazione fa quindi aumentare la durata dei cambi di contesto.

Aspetto importante: La netta distinzione tra la memoria vista dall’utente e l’effettiva memoria fisica è colmata dall’architettura di traduzione degli indirizzi, che fa corrispondere gli indirizzi fisici agli indirizzi logici generati dai processi utenti. Il programma utente vede la memoria come un unico spazio contiguo, contenente solo il programma stesso; in realtà è sparso in una memoria fisica contenente anche altri programmi. Queste trasformazioni sono controllate dal SO e non sono visibili agli utenti perché non possono accedere alle zone di memoria che non gli appartengono. Quando si deve eseguire un processo, si esamina la sua dimensione espressa in pagine. Poiché ogni pagina necessita di un frame, se il processo richiede n pagine, devono essere disponibili almeno n frame che, se ci sono, si assegnano al processo stesso. Si carica la prima pagina del processo in uno dei frame assegnati e s’inserisce il numero del frame nella tabella delle pagine relativa al processo in questione. La pagina successiva si carica in un altro frame e, anche in questo caso, si inserisce il numero del frame nella tabella delle pagine, e così via.

Architettura HW di supporto alla paginazione

Ogni SO segue metodi propri per memorizzare le tabelle delle pagine e la maggior parte ne impiega una per ciascun processo. La paginazione richiede il supporto HW. Come viene gestito il rapporto tra indirizzo logico e fisico? Ci sono 3 possibilità:

• Set di registri: Si può utilizzare un set di registri dedicati per contenere le associazioni fra pagina logica e frame (tabella delle pagine). La tabella delle pagine deve essere piccola (256 pagine). La maggior parte dei SO oggi usa tabelle molto grandi, quindi non possono impiegare i registri veloci, è un'architettura superata.
• Tabella in memoria e PTBR (Page Table Base Register): Si può utilizzare una tabella nella memoria associata a un registro PTBR che contiene l'indirizzo di base della tabella delle pagine.