Appunti di Fabio Missagia parte 3.pdf

9. Gestione della memoria Un compito fondamentale di ogni SO è la gestione della memoria, in particolare la condivisione della memoria da parte di più processi è essenziale per l'efficienza del sistema. In particolare, in seguito all'introduzione della multiprogrammazione è diventata necessaria la...

9. Gestione della memoria Un compito fondamentale di ogni SO è la gestione della memoria, in particolare la condivisione della memoria da parte di più processi è essenziale per l'efficienza del sistema. In particolare, in seguito all'introduzione della multiprogrammazione è diventata necessaria la definizione di uno spazio di indirizzamento, ovvero l'insieme degli spazi di memoria indirizzabili da un processo, e la sua protezione, poichè se non gestita può portare al sovrapporsi degli spazi di indirizzamento tra due o più processi. Le tecniche di gestione utilizzabili sono generalmente dipendenti dall'hardware, in quanto questo implementa apposite istruzioni e algoritmi di gestione. Dal punto di vista di un processo, la maggior parte degli accessi in memoria avviene tramite decodifica degli indirizzi, ovvero la traduzione di un indirizzo logico (come una variabile) in un indirizzo fisico, che corrisponde ad una vera e propria locazione in memoria. Ogni programma deve essere portato in memoria ed essere trasformato in processo per essere eseguito È importante però ricordare che il programma diventa un processo solo quando raggiunge la memoria. Solo una volta che il processo ha terminato, la memoria viene rilasciata. Vediamo ora le diverse fasi della traduzione da programma a processo. Gli indirizzi hanno diverse rappresentazioni nelle varie fasi di costruzione di un programma. Binding Prima abbiamo accennato che per effettuare un accesso in memoria dobbiamo prima tradurre un indirizzo logico in un indirizzo fisico. Questa operazione è chiamata binding e può avvenire in differenti modi e tempi: a tempo di compilazione: deve essere già nota la locazione del programma, pertanto gli indirizzi fisici sono scritti direttamente nel codice. Il binding avviene a compile time ed è definito statico in quanto gli indirizzi fisici e logici sono uguali e se questi cambiano il codice deve essere ricompilato. a tempo di caricamento: nel codice si specifica un indirizzo assoluto come primo indirizzo di allocazione e gli altri sono scritti in relazione a quest'ultimo (offset). Anche questo tipo di binding è statico, ma il codice va ricompilato solo se cambia l'indirizzo di riferimento. a tempo di esecuzione: non sono presenti indirizzi assoluti (fisici) nel codice, perchè la locazione in memoria potrebbe cambiare anche durante l'esecuzione. Questo tipo di binding è definito dinamico ed è utilizzato oggi nella maggior parte dei SO, ma richiede HW apposito per essere efficiente, ovvero la Memory Management Unit (MMU). In breve, è un dispositivo hardware che mappa indirizzi virtuali (logici) in indirizzi fisici. Ha un suo registro base (chiamiamolo r) il cui valore viene aggiunto ad ogni indirizzo generato da un processo, e inviato alla memoria. Il programma utente interagisce con gli indirizzi logici (da 0 a max) ma non vede mai gli indirizzi fisici reali (da r a r+max). In questo modo il programma è indipendente da informazioni specifiche della memoria (valore di rilocazione, capacità della memoria, …). Nota  Per assicurare che non ci siano accessi illegali alla memoria, ogni processo è associato ad un registro base e ad un registro limite. Il registro base contiene il più basso valore indirizzabile da un processo, mentre il registro limite contiene il totale di indirizzi specificabili dal programma, in modo tale che (reg. base + reg. limite) diano il più piccolo valore non indirizzabile dal programma, il limite superiore dello spazio degli indirizzi. Pertanto un indirizzo logico (generato dalla CPU, detto anche indirizzo virtuale) è sempre minore del registro limite e gli indirizzi fisici (indirizzo visto dalla memoria) devono essere compresi tra reg. di base e (reg. di base + reg. limite). Nel caso di binding dinamico, o a run time, basta cambiare il valore del registro di base, tutti gli indirizzi fisici saranno calcolati durante le operazioni con uno spiazzamento sugli indirizzi logici, in particolare ind. fisico = ind. logico + reg. base. Invece nel binding a compile o load-time indirizzo fisico e logico coincidono, visto che sono fissi e se cambiano bisogna ricompilare il programma. Dynamic linking and loading Le operazioni di linking e di loading viste nell'immagine sopra possono essere effettuate in modo statico o dinamico. Linking: associazione a librerie esterne, il metodo statico prevede di creare una copia del codice delle librerie usate. Nel metodo dinamico il codice è invece sostituito da stub, ovvero riferimenti alla specifica libreria. Se questa viene richiamata, lo stub carica in memoria la libreria. Si ha la possibilità di avere librerie condivise se ci sono più processi che utilizzano le stesse. In questo modo si ha un generale risparmio di codice, d'altro canto, in quanto questo e condiviso, si ha la necessità di supervisione da parte del SO. Loading: associazione a librerie di sistema, con il metodo statico tutto il codice delle routine è caricato insieme al programma al tempo dell'esecuzione, anche il codice inutile, come per il linking statico. Con il metodo dinamico, il caricamento è posticipato al momento del primo utilizzo del metodo e il codice non utilizzato non viene caricato. Risulta così molto efficiente, specie se si fa uso di codice usato molto raramente, come le routine di errore. In conclusione, in un sistema multiprogrammato non è possibile conoscere in anticipo dove un processo può essere posizionato in memoria, dunque il binding a tempo di compilazione non è possibile. Inoltre l’esigenza di avere lo swap impedisce di poter utilizzare indirizzi rilocati in modo statico quindi nemmeno il binding a tempo di caricamento è possibile. Pertanto, nei sistemi general-purpose si usa soltanto il binding a tempo di esecuzione (detto anche rilocazione dinamica) e da ora in poi assumiamo che quest'ultimo sia usato e che tutto il processo debba essere caricato in memoria. Allocazione della memoria Esistono differenti politiche per il caricamento dei processi in memoria e per riservare loro lo spazio. Gli obiettivi principali di questo ambito di gestione sono l'aumentare l'utilizzo della memoria, allocando più processi possibili ed aumentando il grado di multiprogrammazione. Vediamo ora 4 schemi di gestione della memoria. Allocazione contigua I processi vengono allocati in memoria in posizioni contigue all’interno di una partizione. Inoltre tutta la memoria è suddivisa in partizioni, che possono essere di dimensione fissa o variabile. Distinguiamo quindi i 2 casi, vedendo prima la tecnica delle partizioni fisse e successivamente quella a partizioni variabili. Partizioni Fisse Il SO crea appositamente delle partizioni di dimensione fissa e predeterminata all'avvio, ma che possono avere dimensione diversa tra loro. L'assegnazione della memoria è effettuata dallo scheduling a lungo termine e possiamo implementarla in 2 modi: 1. Una coda per partizione: il processo viene assegnato alla partizione più piccola in grado di contenerlo. È una soluzione poco flessibile visto che possono esserci partizioni vuote. 2. Coda unica: un'unica queue, con la quale le partizioni vengono assegnate con differenti algoritmi come: FCFS: Facile, ma vi è un basso utilizzo della memoria Scansione della coda Best-fit-only: Scelta del job con dimensioni più simili alla partizione First-available-fit: Scelta del primo job che può stare nella partizione Vantaggi Relativa semplicità Svantaggi Il grado di multiprogrammazione è limitato dal n° di partizioni; per esempio se la ram ha 20 partizioni allora può contenere massimo 20 processi Abbiamo il problema della frammentazione, che porta ad uno spreco di memoria. Essa può essere interna (alla partizione) se la dimensione della partizione è più grande della dimensione del job, ossia la partizione non viene riempita del tutto e si spreca un po' di spazio, oppure esterna se la dimensione della partizione è più piccola della dimensione del job, ossia alcune partizioni non vengono utilizzate e rimangono vuote. Partizioni variabili Il SO crea partizioni di dimensioni identiche a quelle dei processi, cercando così di eliminare la frammentazione interna. Quando arriva un processo, viene messo nella prima buca (blocco di memoria disponibile) che può contenerlo. Dunque il S.O. deve mantenere informazioni sulle partizioni allocate e sulle buche. L'assegnazione della memoria possiamo implementarla in 3 modi: First-fit: il processo viene allocato nella prima buca grande a sufficienza (metodo migliore) Best-fit: il processo viene allocato nella buca più piccola che può contenerlo (minimizza lo spreco ma è troppo lento, visto che bisogna scansionare tutte le buche) Worst-fit: processo allocato nella buca più grande trovata (spreca memoria ed è troppo lento, visto che bisogna scansionare tutte le buche) Vantaggi Non produce frammentazione interna (in realtà c'è sempre un po' frammentazione interna, ma è minimizzata, non si può fare meglio), in quanto ogni partizione ha dimensione pari a quella richiesta dal processo. Svantaggi Tuttavia in media aumenta la frammentazione esterna, in quanto si producono molte partizioni di piccola dimensione. Si stima infatti che con il first-fit, dati N blocchi allocati, 0.5 ⋅ N blocchi vanno persi. Quale può essere una soluzione intuitiva per risolvere questo problema? La compattazione! Si può quindi spostare il contenuto della memoria in modo da rendere contigue tutte le partizioni. Questo tuttavia è possibile solo se la rilocazione è dinamica e richiede la modifica del registro base. Per questo potrebbe risultare anche abbastanza costoso. Tecnica del buddy system È un compromesso tra partizioni fisse e variabili. Essenzialmente la memoria è vista come una serie di blocchi di dimensione 2 , con L < k < U , dove K 2 L è il più piccolo blocco allocato mentre 2 U è il più grande blocco allocato (es. tutta la memoria). All'inizio tutta la memoria è disponibile, dunque ci sarà un blocco unico di dimensione 2. Quando arriva U una richiesta di dimensione s, si cerca un blocco libero con dimensione “adatta” purché sia pari a una potenza del 2. In parole semplici, se dividendo per 2 il blocco la richiesta non ci sta più allora la piazzo nel blocco corrente, altrimenti posso dividere il blocco in 2 e rifare ricorsivamente il controllo, finchè appunto non arriverò ad allocare un blocco di dimensione 2 < s ≤ 2 , quindi grande più o meno quanto la U −1 U richiesta. Quando invece un processo rilascia la memoria, il suo blocco torna a far parte della lista dei blocchi di dimensione corrispondente. Se si formano 2 blocchi adiacenti di dimensione 2 , è possibile compattarli K ottenendo un unico blocco libero di dimensione 2. Di seguito è riportato un esempio. K+1 Vantaggi La compattazione richiede solo di scorrere la lista dei blocchi di dimensione 2 K , quindi è veloce. Svantaggi La frammentazione interna è ampiamente ridotta rispetto all'allocazione a partizioni fisse, ma persiste, come si può notare nell'esempio sopra. Paginazione Questa tecnica evita del tutto la frammentazione esterna (come le partizioni variabili) in quanto permette l'allocazione dei processi non contigua. Questo è possibile con la divisione della memoria fisica in frame e la memoria logica in pagine di uguale dimensione. Quando un processo richiede memoria gli vengono assegnate delle pagine, per cui la frammentazione interna è limitata al più ad una pagina per processo. Per esempio, se la dimensione della pagina è pari a 1KB, la dimensione del programma pari a 2.3KB, saranno necessarie 3 pagine per allocare il processo e dell’ultima pagina si userà solo 0.3KB. Dunque è ancora possibile della frammentazione interna, ma solo nell’ultima pagina. Le corrispondenze pagine-frame sono registrate in un'apposita page table salvata in memoria, che ogni processo possiede. Quando la CPU legge un indirizzo logico, la MMU effettua la traduzione grazie alla tabella. Come avviene la traduzione da indirizzo logico ad indirizzo fisico? L’indirizzo generato dalla CPU viene diviso in due parti: numero di pagina (p): ci indica la pagina in sè offset (d): ci indica i bit che dobbiamo leggere di quella pagina Esempio In questo esempio abbiamo una memoria di 8KB divisa in pagine da 1KB ciascuna. Dunque la pagina 0 va da 0 a 1023 , la pagina 1 da 1024 a 2047 ecc. 1. Come viene tradotto l'indirizzo logico 936? L'indirizzo appartiene alla pagina 0, visto che ⌊ 936 1024 ⌋ = 0 , e l'offset sarà proprio di 936. Dunque visto che le pagine partono da 0 e i frame da 1, la pagina 0 viene tradotta proprio nel frame 1 (che vanno da 1024 a 2047). Dunque l'indirizzo fisico sarà 1024 + of f set = 1024 + 936 = 1960 2. Come viene tradotto l'indirizzo logico 2049 ? L'indirizzo appartiene alla pagina 2, visto che ⌊ 2049 1024 ⌋ = 2 , e l'offset sarà di 2049 mod 2048 = 1. Dunque visto che le pagine partono da 0 e i frame da 1, la pagina 2 viene tradotta nel frame 3 (che vanno da 3072 a 4095 ). Dunque l'indirizzo fisico sarà 3072 + of f set = 3072 + 1 = 3073 Tale metodo ha un'efficienza accettabile solo se la tabella è ad accesso rapido, altrimenti il costo di accesso risulta proibitivo. Vediamo ora le 2 alternative per l'implementazione della paginazione. Implementazione tramite registri Le entry (righe) della tabella delle pagine sono memorizzate in appositi registri della CPU. La velocità di accesso è massima, ma questa soluzione causa parecchio overhead nel context switch. Il problema principale, tuttavia, è lo scarso numero di registri disponibili e quindi delle entry memorizzabili. Implementazione in memoria Questo metodo prevede di tenere in memoria la tabella di ogni processo in esecuzione. La locazione della tabella è memorizzata in un apposito registro detto Page Table Base Register (PTBR). Questo riduce di molto l'overhead in quanto, durante il context switch, la CPU dovrà solo cambiare il valore del PTBR. Opzionalmente è disponibile anche il registro Page-table length register (PTLR), che contiene la dimensione della tabella delle pagine. Il problema principale di questo approccio è il tempo di accesso alla memoria, in quanto ogni traduzione richiede un accesso per leggere la tabella ed un accesso per l'indirizzo fisico. Per risolvere questo problema si utilizza una cache apposita detta Translation Lookaside Buffer (TLB), che consiste in una serie di coppie chiave-valore, contenente le associazioni pagina-frame. La realizzazione HW di tale cache permette il confronto parallelo di tutte le entry e risulta pertanto estremamente veloce. Se un'associazione non viene trovata nel TLB, si procede ad un accesso in memoria e si copia l'associazione nella TLB. Sebbene questa possa contenere un numero limitato di entry visto che è molto costoso, la sua hit ratio è molto alta, riducendo così il tempo di accesso sensibilmente. Generalmente, il TLB viene ripulito ad ogni context switch per evitare mapping di indirizzi errati. In alternativa, è possibile memorizzare in ogni tupla un ID del processo, per evitare di smontare ogni volta la cache. Riassumendo, durante un accesso alla memoria: se la pagina cercata è nel TLB, il TLB restituisce il numero di frame con un singolo accesso. In questo modo il tempo richiesto è minore del 10% del tempo richiesto in assenza di TLB altrimenti è necessario accedere alla tabella delle pagine in memoria Possiamo allora calcolare il tempo di accesso effettivo alla pagina. Nella formula sottostante α rappresenta l'hit ratio, ovvero la percentuale delle volte in cui una pagina si trova nel TLB. EAT = (T T LB + T M EM ) ⋅ α + (T T LB + 2 ⋅ T M EM ) ⋅ (1 − α) dove T T LB rappresenta il tempo di accesso al TLB, mentre T M EM il tempo di accesso alla memoria. Protezione Per garantire sicurezza è possibile aggiungere bit di flag alle entry della tabella delle pagine: bit di validità: alle volte (spesso) un processo non usa tutti gli indirizzi logici del proprio spazio e pertanto alcune pagine rimangono vuote. Questo bit segnala tali pagine, i tentativi di accedere ad esse sono bloccati. bit di accesso: utilizzabili per marcare una pagina come eseguibile, read-only, read/write, etc. In generale per definire i diritti di accesso. Pagine Condivise Possibilità interessante che si apre con la paginazione è la condivisione di pagine fra più processi. Dunque vi è un’unica copia fisica, ma più copie logiche (una per processo). Il requisito è che tali pagine contengano solo codice read-only. Questo meccanismo può essere usato per esempio quando si esegue lo stesso programma più volte con dati diversi. Per esempio, se apro 3 processi di Word, il 90% del codice viene caricato dalla stessa pagina. Paginazione multilivello L'evoluzione dell'hardware ha portato ad un aumento esponenziale dello spazio di indirizzamento logico e di conseguenza anche della dimensione della tabella delle pagine. Per limitare la dimensione e risparmiare spazio in memoria, è possibile adottare una struttura gerarchica per la tabella, ovvero le tabelle portano ad altre tabelle. Inoltre solo alcune parti delle tabelle delle pagine sono memorizzate in memoria, le altre sono su disco. Si deve però tenere conto che ogni livello aggiuntivo richiede un ulteriore accesso in memoria, quindi si limita di solito questo tipo di struttura ad un massimo di due o tre livelli (costo troppo elevato in caso di cache miss nel TLB). Tabella delle pagine invertita Altra tecnica pensata per far fronte ai problemi della gestione di page table di grandi dimensioni. Anzichè avere una tabella per ogni singolo processo, si ha un'unica tabella di sistema dove le associazioni sono invertite: non sono più pagina → frame, ma frame → pagina, dunque abbiamo un entry per ogni frame. Diventa necessario memorizzare anche il PID del processo che detiene il frame, dunque ogni entry conterrà la coppia e ogni indirizzo logico è una tripla. In generale, con questa tecnica si ha un risparmio di memoria, ma vi è un aumento del tempo necessario per cercare un riferimento ad una pagina. Quindi visto che sarebbe da pazzi usare una ricerca sequenziale, generalmente si opta per usare una tabella di hash che rende il tempo di look-up O(1). In pratica, è necessario un meccanismo per gestire le collisioni quando diversi indirizzi virtuali corrispondono allo stesso frame. Inoltre, persiste comunque il problema della frammentazione esterna. Segmentazione La segmentazione permette la divisione dello spazio di indirizzamento di un processo in segmenti di dimensione variabile, creati dal compilatore. Solitamente questi rispecchiano la visione che ha l'utente del processo, pertanto si avranno, per esempio, un segmento per il codice, uno per i dati, etc. Similmente alla paginazione, si ha una tabella dei segmenti chiamata segment table che mappa indirizzi logici bidimensionali in indirizzi fisici unidimensionali. Nello specifico, ogni entry contiene una coppia di valori , rappresentanti rispettivamente l'indirizzo di partenza del segmento e la dimensione dello stesso. Gli indirizzi logici sono formati dal numero di segmento (posizione della entry nella tabella) e dall'offset interno allo stesso. Questo rende immediato il controllo di legalità dell'indirizzo. Anche qui, come nella paginazione, sono presenti 2 registri contenenti informazioni sulla tabella dei segmenti. Abbiamo il Segment-table base register (STBR) che punta alla locazione della tabella dei segmenti in memoria, e il Segment-table length register (STLR) che indica il numero di segmenti usati da un programma (è obbligatorio, non opzionale). Ovviamente un indirizzo logico (dove s è il numero di segmento e d l'offset) è valido se s < STLR, ovvero il suo numero identificativo non può superare il numero totale di segmenti. Come facciamo invece a recuperare un indirizzo specifico dalla tabella dei segmenti? Basterà sommare STBR, che punta al primo segmento della tabella, a s, ottenendo così l'indirizzo del segmento desiderato. Infine, come per la paginazione, viene usata una cache TLB per memorizzare le entry maggiormente usate. Esempio Proviamo ad effettuare una traduzione da indirizzo logico ad indirizzo fisico. Tabella dei segmenti: Segmento Limite Base 0 600 219 1 14 2300 2 100 90 3 580 1327 1. Come viene tradotto l'indirizzo logico ? L'indirizzo appartiene al segmento 0 ed ha un offset di 430. L'indirizzo limite è 600 e visto che 430 < 600 , questo è un indirizzo valido. Pertanto l'indirizzo fisico sarà 430 + base = 430 + 219 = 649 2. Come viene tradotto l'indirizzo logico ? L'indirizzo appartiene al segmento 1 ed ha un offset di 20. L'indirizzo limite è 14 e visto che 20 ≰ 14 , questo non è un indirizzo valido. Protezione Per come è strutturata, la segmentazione supporta naturalmente la protezione e la condivisione di codice. Come per la paginazione ad ogni segmento sono associati i bit di bit di accesso (read/write/execute) e i bit di validità (0 ⇒ segmento non legale). Svantaggi Uno svantaggio sta nel fatto che il SO deve allocare tutti i segmenti e si può incorrere in frammentazione esterna, visto che i segmenti hanno lunghezza variabile. Segmentazione paginata Ancora una volta, la soluzione è combinare i due schemi prendendo i lati positivi di ognuno. Si arriva così alla segmentazione paginata, cioè una tecnica mista che consiste nel paginare segmenti di memoria. Nello specifico: Ogni segmento è suddiviso in pagine Ogni segmento possiede la sua tabella delle pagine La tabella dei segmenti non contiene più l’indirizzo base di ogni segmento, ma l’indirizzo base delle tabelle delle pagine per ogni segmento Si elimina così il problema dell'allocazione e della frammentazione esterna. 1. È l'indirizzo generato dalla CPU, anche definito come indirizzo virtuale. Gli indirizzi logici sono trattati dai programmi utente, gli indirizzi fisici fanno riferimento alla effettiva posizione del dato nella memoria.↩︎ 10. Memoria virtuale Le tecniche viste in memoria prevedono che tutti i dati di un processo siano caricati in memoria al momento della sua esecuzione. Con l'evoluzione del software, caricare tutto in memoria, con software di grandi dimensioni, non sempre è possibile, ma soprattutto non è sempre necessario. Basti pensare che molti programmi moderni pesano molti più GB di quanto la RAM sia fisicamente in grado di contenere. E come se non bastasse, un programma pesa di più dentro la RAM perché diventando un processo verranno aggiunte informazioni aggiuntive, come la stack (vedi 4. Gestione dei processi e threads > Da cosa è formato un processo?). Per risolvere questo problema è dunque stata introdotta la memoria virtuale, con cui è possibile considerare parte del disco come memoria primaria (quindi Memoria virtuale = RAM + parte di disco) e caricare in memoria solo le parti del programma necessarie per l'esecuzione attuale. Sebbene generalmente complessa da implementare, la memoria virtuale permette di caricare più processi in memoria, aumentando quindi il throughput, ed inoltre permette facilmente la condivisione di risorse fra processi. Esistono varie tecniche per realizzare la memoria virtuale, ma si vedrà che, come per la paginazione, la memoria virtuale sembri quasi una naturale evoluzione. Paginazione su richiesta (on demand) Sostanzialmente mi permette di eseguire programmi più grandi della RAM caricando dentro quest'ultima solo una parte delle pagine e solo quando necessario. Le pagine restanti vengono caricate su disco (backing store) e prese tramite swapping. Per capire se una pagina è dentro la ram o su disco utilizzo i bit di validità presenti nella page table: bit a 1: pagina in memoria bit a 0: pagina NON in memoria Inizialmente i bit di validità sono tutti 0. Dunque, ad ogni istruzione, se la pagina richiesta è presente in memoria si va avanti normalmente, altrimenti si verifica un cosiddetto page fault. Page fault Un page fault causa un interrupt al SO che avviene in queste 5 fasi: 1. Il S.O. stabilisce la validità del riferimento del processo chiamante. Se non è valido abortisce il page fault. 2. Cerca un frame vuoto nella RAM o dal quale rimuovere una pagina 3. Effettua lo swap dal disco della pagina richiesta 4. Modifica il bit di validità a 1 perché ora la pagina è in memoria 5. Ripristina l'istruzione che ha causato il page fault Come detto sopra, il primo accesso in memoria di un programma risulta sempre in page fault (perché la tabella è ancora vuota). Effective Access Time (EAT) Ovviamente la paginazione su domanda influenza il tempo di accesso effettivo alla memoria (Effective Access Time, EAT), visto che la velocità dipende da quanti page fault avvengono, e quindi se trovo la pagina già in memoria o no. Possiamo allora calcolare il tempo di accesso effettivo alla pagina. Nella formula sottostante p rappresenta il tasso di page fault, ovvero la probabilità che un page fault si verifichi. Ovviamente 0 ≤ p ≤ 1, dove p = 0 significa nessun page fault, mentre p = 1 ogni accesso è un page fault. EAT = (1 − p) ⋅ t mem + p ⋅ t pagef ault  Dove t pagef ault è dato da tre componenti: il servizio dell’interrupt, lo swap in (lettura della pagina), e costo di riavvio del processo (e lo swap out (opzionale)). Invece t mem rappresenta il tempo di accesso alla memoria. Esempio Dati: t mem = 100 ns 6 t page f ault = 1 ms (10 ns) Dunque 6 6 EAT = (1 − p) ⋅ 100 + p ⋅ 10 = 100–100 ⋅ p + 10 ⋅ p = 100 ⋅ (1 + 9999 ⋅ p) ns Vediamo quanto deve valere p per mantenere un peggioramento al massimo del 10% rispetto al tempo di accesso standard: Accesso standard alla memoria      −4 100 ⋅ (1.1) > 100 ⋅ (1 + 9999 ⋅ p) ↔ p < 0.0001 ≈ 10 Dunque circa 1 page fault ogni 10000 accessi! Ne segue che è fondamentale tenere basso il livello di page fault. Vediamo ora cosa succede se non ci sono pagine libere da rimpiazzare. Rimpiazzamento delle pagine Se non ci sono pagine libere si cercano pagine (frame) in memoria e si fa lo swap su disco di tali pagine. Per far questo è necessario un algoritmo che massimizzi le prestazioni minimizzando il numero di page fault. Vediamo quindi il funzionamento del rimpiazzamento delle pagine. In caso di assenza di frame liberi nel caso di un page fault il sistema operativo verifica su una tabella associata al processo se si tratta di page fault o violazione di accesso. Se è una violazione di accesso fa un abort, altrimenti cerca un frame vuoto e se non c’è usa un algoritmo di rimpiazzamento delle pagine per scegliere un frame vittima. Saranno necessari quindi 2 accessi alla memoria, uno per per fare lo swap out della vittima (nel disco) e uno per fare lo swap in del frame da caricare (in memoria). Quindi una volta scelta la vittima, fa lo swap out di essa su disco, lo swap in della pagina nel frame da disco, modifica le tabelle e ripristina l’istruzione che ha causato il page fault. Si noti come in assenza di frame liberi il tempo di page fault si raddoppia. Pertanto si ottimizza utilizzando un bit nella page table detto bit di modifica o dirty bit che vale 1 se la pagina è stata modificata dal momento in cui viene ricaricata e solo le pagine che vengono modificate vengono scritte su disco quando diventano vittime. Problematiche Dunque le problematiche della paginazione su domanda sono la scelta della pagina da rimpiazzare e l’allocazione del numero di frame ad un processo al momento dell’esecuzione. Vediamo ora come risolvere questi 2 problemi. Algoritmi di rimpiazzamento delle pagine Il tasso di page fault, che deve essere tenuto basso per non compromettere le prestazioni, dipende molto da come viene scelta la pagina da rimpiazzare. Dunque l’obiettivo di questi algoritmi è di minimizzare il numero di page fault. Si valuta l’esecuzione di una particolare stringa di riferimenti a memoria detta reference string e si calcolano il numero di page fault sulla stringa. È sempre necessario sapere il numero di frame disponibili per il processo. Il tasso di page fault è inversamente proporzionale al numero di frame (più frame → più spazio per tutti). Algoritmo FIFO (first-in-first-out) In questo algoritmo la prima pagina introdotta è la prima ad essere rimossa. L’algoritmo è cieco in quanto non viene valutata l’importanza (frequenza di riferimento) della pagina rimossa. Tende ad aumentare il tasso di page fault e soffre dell’anomalia di Belady. anomalia di Belady Nell’anomalia di Belady il numero di page fault non può decrescere all’aumentare del numero di frame usando FIFO, mentre a volte più frames equivalgono a più page fault. Esempio 1 In questo esempio abbiamo 3 frame e con una reference string lunga solamente 20 abbiamo 15 page fault! Esempio 2 In questo esempio abbiamo 3 frame e con una reference string lunga solamente 12 abbiamo 9 page fault! Algoritmo ideale Come sarebbe fatto quindi un algoritmo ideale? Garantisce il minimo numero di page fault rimpiazzando le pagine che non saranno usate per il periodo di tempo più lungo. Questa informazione richiede una conoscenza anticipata della stringa dei riferimenti e ci si ritrova in una situazione simile a SJF e pertanto l’implementazione è impossibile a meno di approssimazioni. Rimane comunque un utile riferimento per altri algoritmi. Esempio In questo esempio abbiamo 3 frame e con una reference string lunga solamente 20 avremmo solamente 9 page fault. Viene rimpiazzata la pagina che sarà riusata in seguito alle altre 2 pagine nei frame. Algoritmo least recently used (LRU) Questo algoritmo è un’approssimazione dell’algoritmo ottimo e usa il passato recente come previsione del futuro rimpiazzando la pagina che non viene usata da più tempo. È di difficile implementazione in quanto non è banale ricavare il tempo dell’ultimo utilizzo e può richiedere notevole hardware addizionale. Esempio In questo esempio abbiamo 4 frame e con una reference string lunga solamente 12 abbiamo 8 page fault. Dunque è decisamente migliore del FIFO ma peggiore dell'algoritmo ideale (ovviamente). Implementazioni Vediamo ora delle possibili implementazioni di questo algoritmo. Tramite contatore Ad ogni pagina è associato un contatore e ogni volta che la pagina viene referenziata il clock di sistema è copiato nel contatore. Si rimpiazza la pagina con il valore più piccolo del contatore. Si noti come tale pagina vada cercata. Tramite stack Viene mantenuto uno stack di numeri di pagina e quando si fa riferimento ad una pagina questa viene estratta dalla sua posizione e messa in cima. L’aggiornamento richiede l’estrazione di un elemento interno allo stack. Al fondo dello stack si trova la pagina LRT. Si noti come in questo caso non è necessaria alcuna ricerca, in quanto la pagina designata è sempre in fondo, ma aggiornare il riferimento, rimuovendo un elemento dal centro, richiede una ricerca O(n). Uso del bit di reference Che viene associato ad ogni pagina inizialmente a 0. Quando la pagina è referenziata, il bit di reference viene impostato a 1 dall’hardware. Per il rimpiazzamento si sceglie una pagina che ha il bit a 0. Si noti come è approssimato in quanto non viene verificato l’ordine di riferimento delle pagine. In alternativa, si usano più bit di reference (registro di scorrimento) per ogni pagina. I bit vengono aggiornati periodicamente e si usano i bit come valori interi per scegliere la LRU, ovvero quella con il valore più basso di registro di scorrimento. Approssimazioni Le tecniche viste sopra implementano deterministicamente il LRU, ma sono costose in termini di HW. Esistono implementazioni alternative meno costose, che sono tuttavia a loro volta delle approssimazioni. Algoritmo LFU (Least Frequently Used) Mantiene un conteggio del numero di riferimenti fatti ad ogni pagina e rimpiazza quella con il conteggio più basso. Può non corrispondere al “LRU”, visto che, se per esempio ho molti riferimenti iniziali, una pagina può avere conteggio alto e non essere eseguita da molto tempo. Algoritmo MFU (Most Frequently Used) È l'opposto di LFU, la pagina con il conteggio più basso è probabilmente stata appena caricata e dovrà essere presumibilmente usata ancora (località dei riferimenti). Algoritmo second chance (clock) Si basa su una FIFO circolare basata su bit di reference: se il bit è a 0 si rimpiazza, se a 1 si mette a 0 e si analizza la pagina successiva. Variante: Si usano più bit di reference. Allocazione dei frame Data una memoria con N frame e M processi è importante scegliere quanti frame allocare ad ogni processo non violando il fatto che ogni processo necessita di un minimo numero di pagine per poter essere eseguito in quanto l’istruzione interrotta da un page fault deve esser fatta ripartire. Pertanto il numero di pagine deve essere uguale al massimo numero di indirizzi specificabile in un’istruzione. I valori tipici vanno da 2 a 4 frame. Inoltre lo schema di allocazione può essere fisso, in cui un processo ha sempre lo stesso numero di frame, o variabile, in cui il numero di frame allocati può variare durante l’esecuzione. Se il numero di pagine è minore al massimo numero di indirizzi specificabile in un’istruzione, si potrebbe verificare una situazione di costante page fault per il processo. Una volta specificato questo vincolo, è possibile classificare gli algoritmi in due famiglie, a seconda della politica di allocazione dei frame: rimpiazzamento locale o globale. Nel primo caso i frame vittima possono essere scelti solo tra i frame allocati dal processo stesso (sceglie la vittima tra i frame che ha); in questo modo il numero di frame per processo rimane fisso. Se si parla di rimpiazzamento globale, la vittima può essere scelta tra tutti i frame in memoria, quindi anche degli altri processi. In questo modo è più difficile tracciare il tasso di page fault, ma in generale questo metodo dinamico aumenta il throughput ed è per questo preferito. Vediamo un po' più in dettaglio la differenza tra allocazione fissa e variabile. Allocazione fissa Allocazione in parti uguali Dati m frame e n processi si alloca ad ogni processo m n frame. Allocazione proporzionale Alloca secondo la dimensione del processo, parametro non sempre significativo in quanto la priorità può essere più significativa. Allocazione variabile Permette di modificare dinamicamente le allocazioni ai vari processi. Dobbiamo però capire in che modo effettuare le allocazioni. Esse avvengono in base al calcolo del working set o della page fault frequency (PFF). Calcolo del working set Si definisce working set la quantità di memoria che un processo richiede per svolgere le proprie funzioni in un dato istante t. Il working set dipende dalla località del programma (un processo passa da una località di indirizzi all’altra durante la sua esecuzione come array, procedure e moduli) ed è per questo definito in funzione del tempo. Quindi un criterio per rimodulare l’allocazione dei frame consiste nel calcolare quali sono le richieste effettive di ogni processo in base al modello della località. Idealmente un processo necessita di un numero di frame pari alla sua località. Ma come la misuro? Effettuando una stima! Modello del working set Per la stima del working set, un metodo semplice quanto veloce consiste nel considerare un dato intervallo di riferimenti Δ: tutte le pagine che compaiono nell'intervallo (chiamato finestra del working set) fanno parte del working set ed il numero ne costituisce la cardinalità (dimensione). Ovviamente si deve prestare attenzione alla dimensione di Δ. Se è troppo piccolo è poco significativo, se è troppo grande copre varie località e se vale infinito comprende tutto il programma. Vediamo ora come calcolare approssimativamente il working set. Il working set viene calcolato approssimando tramite timer e bit di reference: si usa un timer che interrompe periodicamente la CPU; all’inizio di ogni periodo i bit di reference vengono posti a 0 e ad ogni interruzione del timer le pagine vengono scansionate; quelle con bit di reference a 1 si trovano nel working set, quelle con valore 0 vengono scartate. L’accuratezza aumenta in base al numero di bit e alla frequenza di interruzioni. La richiesta totale di frame è D = ∑ W SS i i , dove W SS è la dimensione del W S. Se D è maggiore del numero totale di frame si verifica i i un fenomeno chiamato thrashing in cui un processo spende tempo di CPU continuando a swappare pagine da e verso la memoria. Di conseguenza i nuovi processi "rubano" frame ai vecchi processi aumentando il numero di page fault, portando ad un declino costante dell'utilizzo della CPU. Si deve pertanto stimare con esattezza il numero di frame necessari a un processo per non entrare in thrashing. Frequenza dei page fault Una soluzione alternativa e più accurata del working set è la frequenza dei page fault: si stabilisce un tasso di page fault accettabile. Se quello effettivo è troppo basso il processo rilascia dei frame, se è troppo alto ne ottiene altri. Conclusioni La selezione della dimensione della pagina deve essere fatta accuratamente in quanto si deve sempre fare un trade-off: Pagine piccole: Frammentazione. Molte entry nella page table. Costo di lettura e scrittura non ammortizzato. Località. Pagine grandi: Frammentazione interna significativa. Grande dimensione della page table. I/O overhead. Grande granularità, si deve anche trasferire ciò che non è necessario. Naturalmente la struttura dei programmi influisce sul numero di page fault e in alcuni casi esistono frame che non devono essere mai rimpiazzati come frame corrispondenti a pagine del kernel e altri corrispondenti a pagine usate per trasferire dati da e verso I/O. Questi subiscono il blocco di frame (frame locking). 11. Gestione della memoria secondaria Tipologie di supporto Vediamo le principali tipologie di supporto e le loro caratteristiche. Nastri magnetici Uno dei primi tipi di memoria secondaria è il nastro magnetico, una sottile striscia in materiale plastico, rivestita da un materiale magnetizzabile. Questo tipo di memoria ha avuto una massima capacità di circa 5TB nel 2011, arrivata poi a 45TB nel 2021. Tuttavia, l'accesso a questa memoria è sequenziale, il che significa che è molto più lento rispetto alla memoria principale e ai dischi magnetici in termini di tempo di accesso. Il riposizionamento della testina di lettura richiede decine di secondi, il che lo rende un processo abbastanza lento. A causa di queste limitazioni, le memorie magnetiche di questo tipo sono state rimpiazzate dai dischi magnetici e dalle memorie a stato solido, che offrono prestazioni migliori. I dischi magnetici e le memorie a stato solido hanno una capacità di archiviazione tre ordini di grandezza superiore rispetto a questo tipo di memoria. Oggi, le sottili strisce magnetiche sono ormai usate solo per scopi di backup. Dischi magnetici Sono piatti di alluminio o di altro materiale ricoperti di materiale ferromagnetico con una massima capienza di 4 T B (nel 2011). Il fattore di forma o diametro è sempre più piccolo in modo da raggiungere maggiori velocità di rotazione. Parte da 3:5 pollici per i sistemi desktop e fino a 1 pollice per i mobili. La lettura e la scrittura avvengono tramite una testina sospesa sulla superficie magnetica. Nella scrittura il passaggio di corrente positiva o negativa attraverso la testina magnetizza la superficie, mentre nella lettura il passaggio sopra un’area magnetizzata induce una corrente positiva o negativa nella testina. Struttura di un disco Da un punto di vista fisico il disco è costituito da superfici (platter, i dischi), cilindri (cylinder, le tracce di tutti i dischi con la stessa posizione), tracce (cerchi di settori all’interno di un disco) e settori (sottoaree del disco disposte in cerchi concentrici). Settore Il settore è l’unita più piccola di informazione che può essere letta o scritta su disco. Ha una dimensione variabile tra i 32 byte e i 4KB (tipicamente di 512 byte). Sono generalmente raggruppati logicamente in cluster per aumentare l’efficienza. La dimensione dei cluster dipende dalla grandezza del disco e dal sistema operativo (da 2KB a 32KB). Un file occupa sempre almeno un cluster. Per accedere a un settore si necessita di sapere la superficie, la traccia e il settore stesso. Tempo di accesso al disco Il tempo di accesso è la somma del seek time (tempo necessario a spostare la testina sulla traccia), del latency time (latenza, il tempo necessario a posizionare il settore desiderato sotto la testina che dipende dalla velocità di rotazione) e del transfer time (il tempo necessario al settore per passare sotto la testina). Il seek time va da 3ms fino a 15ms, mediamente 9ms per dischi desktop. La latenza, considerando in media mezza rotazione del disco per ogni accesso è 0.5 ⋅ ( 60 à di rotazione velocit. Per un disco da 7200 rpm è di 4.16 ms. Il transfer time è il rapporto tra la dimensione del blocco e la velocità di trasferimento. Per un disco da 7200 rpm si ha: disk-to-buffer 1030 M bits sec e buffer-to-computer 300 MB sec. Dunque, mettendo tutti questi dati, mediamente abbiamo una velocità di trasferimento pari a 40M B/s , velocità di rotazione pari a 10000rpm = 166rps , rotazione media pari a 1 2 traccia, una dimensione del blocco pari a 512 Byte ed un seek time pari a 5 ms. Possiamo quindi calcolare il tempo di accesso, pari a: 0.5 0.5 KB Tempo di accesso = 5 ms + + = 5 ms + 3 ms + 0.0000125 = 8.0000125 ms 166 40 M B Si noti come il seek time è dominante e pertanto dato il grande numero di processi che accedono al disco è necessario minimizzare il seek time tramite algoritmi di scheduling per ordinare gli accessi al disco in modo da minimizzare il tempo di accesso totale (riducendo lo spostamento della testina) o massimizzare la banda, che è il numero di byte trasferiti nell’unità di tempo (misura la velocità effettiva). Dispositivi a stato solido Utilizzano chip NVRAM o memorie flash NAND per memorizzare dati in modo non volatile. Usano la stessa interfaccia dei dischi fissi e pertanto possono rimpiazzarli facilmente. Hanno una capacità fino a 2TB. Performance delle flash memory Hanno letture simili a DRAM negli ordini dei nanosecondi e scritture simili ai dischi magnetici nell’ordine dei millisecondi. Rispetto ai dischi fissi sono meno soggette a danni, ma con un limite sul numero di write (1-5 milioni), più silenziosi, più efficienti nel tempo di accesso, non necessitano di essere deframmentate e sono più costose. Scheduling degli accessi a disco Logicamente il disco può essere considerato come un vettore unidimensionale di blocchi logici. Un blocco o cluster è l’unità minima di trasferimento. Il vettore è mappato sequenzialmente sui settori del disco. Il settore 0 è il primo settore della prima traccia del cilindro più esterno e la numerazione procede gerarchicamente per settore, tracce e piatti. Disk scheduling Un processo che necessita di eseguire un'operazione di I/O esegue una system call. In seguito, il sistema operativo utilizza la vista logica del disco per gestire le richieste I/O. Queste richieste contengono informazioni come l'indice del vettore (posizione di memoria) a cui accedere, il tipo di accesso (lettura o scrittura), l'indirizzo di memoria destinazione o di origine e la quantità di dati da trasferire. Tutto ciò consente al sistema operativo di effettuare operazioni di I/O efficienti e controllate. Algoritmi di disk scheduling In questi algoritmi bisogna sempre tenere conto del compromesso tra costo ed efficacia. Sono valutati tramite una sequenza di accessi. First-come-first-served (FCFS) In questo algoritmo le richieste sono processate nell’ordine di arrivo. Esempio Shortest seek time first (SSTF) In questo algoritmo si fa la scelta più efficiente localmente: si seleziona la richiesta con il minimo spostamento rispetto alla posizione attuale della testina. Simile al SJF con possibilità di starvation di alcune richieste, visto che le richieste più lontane potrebbero essere ignorate all'infinito. Esempio SCAN La natura dinamica delle richieste porta all’algoritmo SCAN, in cui la testina parte da un’estremità del disco, si sposta verso l’altra estremità servendo tutte le richieste correnti. Arrivato all’altra estremità riparte nella direzione opposta servendo le nuove richieste. Viene detto algoritmo dell’ascensore. Esempio SCAN circolare (CSCAN) Come SCAN, ma quando la testina arriva ad un’estremità riparte immediatamente da 0 senza servire altre richieste. Il disco viene considerato come lista circolare e il tempo di attesa è più uniforme rispetto a SCAN. Alla fine di una scansione ci saranno più richieste all’altro estremo. Esempio (C-)LOOK, variante dello SCAN La testina non arriva fino all’estremità del disco. Cambia direzione (LOOK) o riparte dalla prima traccia (C- LOOK) non appena non ci sono più richieste in quella direzione. Esempio N-step SCAN, variante dello SCAN Per evitare che la testina rimanga sempre nella stessa zona, la coda delle richieste viene partizionata in più code di dimensione massima N. Quando una coda viene processata per il servizio (scan in una direzione), gli accessi in arrivo riempiono altre code. Dopo che una coda è stata riempita non è possibile riordinare le richieste. Le code sature vengono servite nello scan successivo. Per N grandi degenera in SCAN, mentre per N = 1 degenera in FCFS. FSCAN è simile ma con due sole code. Esempio Last-in-last-out (LIFO) In certi casi può essere utile schedulare gli accessi in base all’ordine inverso di arrivo. È utile nel caso di accessi con elevata località, ma offre possibilità di starvation. Analisi degli algoritmi Nessuno degli algoritmi considerati è ottimo, in quanto quello ottimo sarebbe poco efficiente. L’analisi è influenzata dalla distribuzione di numero e dimensione degli accessi, in quanto più l’accesso è grande più il peso relativo del seek time diminuisce e dall’organizzazione delle informazioni su disco (il file system) e l’accesso alla directory essenziale tipicamente lontane dalle estremità del disco. In generale SCAN e C-SCAN sono migliori per sistemi con molti accessi a disco. Il disk-scheduling viene spesso implementato come modulo indipendente dal sistema operativo con diverse scelte di algoritmo. Formattazione del disco La formattazione è un processo che crea su un disco le strutture e le suddivisioni in settori necessarie per l’utilizzo da parte del SO. Tale operazione si suddivide in formattazione fisica e logica. Formattazione fisica Nella formattazione di basso livello o fisica, il disco viene diviso in settori che il controllore può leggere o scrivere. Ogni settore è provvisto di un header contenente un numero di settore ed un trailer con un Error Correction Code (ECC), che fornisce un sistema limitato di correzione degli errori. Generalmente tale formattazione è effettuata in fabbrica. Formattazione logica Per quanto riguarda la formattazione logica, questa prevede la suddivisione del disco in partizioni e la definizione del file system montato su ciascuna di esse, con le relative strutture di supporto. Questo processo definisce anche eventuali partizioni speciali, come quella dedicata per i file di swap, i boot blocks del disco, le zone di memoria del bootstrap, contenenti le routine di avvio del SO. Gestione dei blocchi difettosi (bad block) L’ECC (error correction code) serve a capire in lettura o scrittura se un settore contiene dati corretti o meno. Come utilizziamo questo codice? Per esempio, nella fase di lettura, quello che avviene è che il controllore legge un settore (nel quale è incluso anche l’ECC) e calcola l’ECC per i dati appena letti. Se il risultato è diverso si trova un errore, ovvero un bad block. L’errore va segnalato e il bad block va gestito. Esistono principalmente due tecniche di gestione dei bad block. Gestione offline dei bad block Durante la formattazione logica del disco, vengono individuati i bad block e inseriti in una lista dedicata. Inoltre, vengono rimossi dalla lista dei blocchi disponibili per l'uso. Successivamente, viene effettuata una modifica nell'entry della File Allocation Table (FAT) corrispondente a tali blocchi. Segnando l'entry corrispondente ai bad block nella FAT, si indica che questi blocchi non devono essere utilizzati per l'archiviazione di dati. Successivamente, è possibile eseguire un'utilità specifica per isolare ulteriormente i bad block. Ciò significa che il sistema operativo non userà più questi blocchi per l'archiviazione di dati, evitando così possibili errori o corruzioni. Questo algoritmo per la gestione dei bad block è tipico dei controllori IDE (Integrated Drive Electronics). Gestione online dei bad block Il controllore mappa il bad block su un blocco buono non usato. Si deve pertanto disporre di blocchi di scorta riservati (sector sparing). Quando il sistema operativo richiede il bad block, il controllore mappa in modo trasparente l’accesso al bad block sul blocco di scorta. Siccome questo potrebbe andare in conflitto con l'algoritmo di disk scheduling, si cerca di allocare degli spare block in ogni cilindro. Gestione dello spazio di swap Lo spazio di swap viene usato dalla memoria virtuale come estensione della RAM. Si può ricavare dal file system attraverso comuni primitive di accesso ai file, ma è inefficiente in quanto esiste un costo addizionale per l’attraversamento delle strutture dati per le directory e i file. Si può porre in una partizione separata che non contiene informazioni e strutture relative al file system e usa uno speciale gestore detto swap daemon. Lo spazio di swap può essere allocato quando il processo viene creato e viene assegnato spazio per pagine di istruzioni e di dati. Il kernel usa due mappe di swap per tracciare l’uso dello spazio di swap. Oppure può essere allocato quando una pagina viene forzata fuori dalla memoria fisica. Infine, lo spazio di swap può essere allocato in due modi. Può essere assegnato durante la creazione di un processo, fornendo al processo stesso uno spazio iniziale nel quale memorizzare le sue pagine di istruzioni e dati. Può essere allocato dinamicamente quando una pagina viene "forzata" fuori dalla memoria fisica per liberare spazio.