Processi e memoria Ges&one della memoria •  Tu6 i processi in esecuzione necessitano della memoria centrale per memorizzare: –  le istruzioni che fanno parte del codice –  i da& su cui operano A. Ferrari Indirizzi •  Indirizzi simbolici –  nel codice sorgente gli indirizzi sono espressi in modo simbolico •  e&che@e simboliche (label) in assembler •  iden&ficatori di variabili nei linguaggi ad alto livello •  Indirizzi logici –  l'assemblatore (o il compilatore) trasforma gli indirizzi simbolici in valori binari che non rappresentano ancora però un vero indirizzo di memoria. –  In genere gli indirizzi logici sono calcola& a par&re da un indirizzo iniziale che vale in genere zero (indirizzi binari logici rela&vi a zero) •  Indirizzi virtuali –  il linker completa i riferimen& ai vari moduli e genera indirizzi che non sono ancora però riferimen& fisici alla memoria Rilocazione •  Indirizzi fisici –  Gli indirizzi virtuali possono essere finalmente trado6 in indirizzi di memoria fisica. –  Questa operazione di traduzione, in sostanza, cos&tuisce uno dei compi& fondamentali del gestore della memoria. •  La traduzione degli indirizzi virtuali in indirizzi fisici è definita rilocazione Rilocazione e protezione Memory Management Unit (MMU) •  Per evitare che un processo faccia riferimento a zone di memoria appartenen& ad al& processi mol& sistemi u&lizzano registri speciali di protezione(registri limite) per controllare ed eventualmente inibire riferimen& non autorizza&. •  Ques& metodi sono o@enibili con sistemi dota& di MMU e i registri base e limite ad esempio possono essere considera& elemen& della MMU del sistema. •  E' un componente hardware che ges&sce le richieste di accesso alla memoria generate dalla CPU •  Una Memory Management Unit (MMU) ha vari compi&, tra cui la traduzione degli indirizzi virtuali in indirizzi fisici, la protezione della memoria, il controllo della cache della CPU ... •  La MMU è integrata nei moderni microprocessori 1 Rilocazione sta&ca •  La rilocazione sta&ca è quel meccanismo per cui il caricatore del SO, dopo aver le@o l'intero programma e prima di porlo in esecuzione, rialloca in memoria tu@o il codice ada@ando gli indirizzi virtuali alle posizioni a@ualmente disponibili nella memoria fisica. •  Il caricatore in questo caso viene de@o rilocante; dopo la rilocazione sta&ca il programma in memoria ha assunto riferimen& di memoria fisica che non potranno più cambiare per tu@a la durata dell'esecuzione. Allocazione •  Tecnica con cui il SO concede ed assegna memoria ai programmi. •  Allocazione sta&ca –  processi carica& in memoria che sono alloca& una sola volta e sono revoca& dalla memoria solo al termine dell'esecuzione •  Allocazione dinamica –  processi che in esecuzione possono vedersi revocata e riallocata la memoria più volte, in genere con operazioni di swapping da e per la memoria secondaria (swap in e swap out) Memoria suddivisa in se@ori •  A ogni processo viene assegnato un se@ore di memoria compreso fra un indirizzo iniziale e uno finale •  Il gestore della memoria ges&sce una tabella di indirizzi in cui associa ad ogni processo il suo indirizzo iniziale e finale Rilocazione dinamica •  Il SO rialloca il codice durante l'esecuzione del programma, u&lizzando elemen& di MMU. •  In questo caso il caricatore non riloca gli indirizzi virtuali del linker ma li carica in memoria così come il linker li ha genera& nel file eseguibile: vengono quindi carica& gli indirizzi virtuali genera& dal linker. •  Run-­‐&me ogni indirizzo viene trado@o nel corrispondente indirizzo fisico prima di accedere alla memoria. •  A differenza della rilocazione sta&ca la rilocazione dinamica perme@e ai programmi di essere carica& in aree di memoria differen& durante l'esecuzione; sarà sufficiente modificare le informazioni contenute nel meccanismo hardware che realizza la funzione di rilocazione (meccanismo di MMU). Memoria e mul&processing •  Più processi sono a6vi contemporaneamente •  Ogni processo necessita di memoria per le istruzioni e i da& •  Il Sistema Opera&vo deve ges&re –  la protezione dei da& e delle istruzioni rela&vi a ogni singolo processo –  il riu&lizzo delle zone di memoria non più u&lizzate dai processi Se@ori: indirizzi •  Indirizzo logico (generato sta&camente) –  Il compilatore assume che l'indirizzo di partenza per i da& e le istruzioni sia l'indirizzo 0 (zero) •  Indirizzo fisico (generato dinamicamente) –  In fase di esecuzione gli indirizzi vengono trasla& sommando l'indirizzo di partenza del se@ore associato al processo (operazione effe@uata run &me dalla MMU) –  Un indirizzo di memoria con&ene una parte che iden&fica un se@ore, e una parte che specifica l'offset entro il se@ore. 2 Se@ori: problemi •  Il problema principale è la frammentazione della memoria: –  quando termina un processo viene rilasciato il suo se@ore di memoria che può essere associato a un nuovo processo che richiede una quan&tà di memoria minore o uguale a quella rilasciata –  le par& inu&lizzate dei se@ori portano a una progressiva frammentazione (potrebbe essere disponibile memoria sufficiente per allocare un processo ma non in un se@ore con&nuo) Strategie di allocazione •  Le strategie di allocazione stabiliscono il criterio scelto per creare o scegliere le par&zioni per i programmi che le richiedono. •  First fit –  Individua la prima par&zione a@a a contenere il programma e, quindi, tra le par&zioni disponibili, viene scelta quella con indirizzi più bassi. Tale tecnica è efficiente per mantenere compa@ate le zone rilasciate. •  Best first –  Ricerca nella tabella la par&zione più piccola a@a a contenere il programma. In questo modo si vengono a creare numerose par&zioni libere molto ristre@e e quindi si aumenta la frammentazione. •  Worst fit –  Tra le par&zioni libere a@e a contenere il programma, sceglie quella più ampia, per a@enuare l'effe@o della frammentazione. Compa@azione Paginazione •  In alcuni casi la riduzione della frammentazione si può o@enere con una tecnica de@a di compa@azione della memoria. •  In questo modo il SO predispone un algoritmo che periodicamente controlla lo stato della memoria e quando necessario interrompe le esecuzioni per compa@are in modo con&guo tu@a la memoria allocata eliminando i buchi e aggiornando la tabella della memoria. •  La memoria principale viene «vista» dal processore come un array di se@ori aven& tu6 la stessa dimensione predefinita. •  Il sistema opera&vo assegna a ogni processo in esecuzione un numero di pagine sufficiente per contenere il codice e i da&. •  Le pagine non sono necessariamente con&gue. Tabella delle pagine Organizzazione in pagine 3 Traslazione degli indirizzi •  Per la traslazione degli indirizzi ogni processo è dotato di una tabella di corrispondenza fra pagina logica e pagina fisica MMU e paginazione •  Il compito della MMU è più complesso •  Per la traduzione da indirizzo logico a indirizzo fisico: –  si individua la pagina logica –  poi si individua la corrispondente pagina fisica Dimensione delle pagine Il compito della MMU •  Se la dimensione di una pagina è una potenza di 2 gli indirizzi vengono di fa@o spezza& in due: –  i primi bit determinano la pagina –  i successivi determinano l’indirizzo interno alla pagina (offset) •  La traslazione sos&tuisce i bit rela&vi alla pagina fisica q quelli rela&vi alla pagina logica e lascia inaltera& i restan& bit •  Esempio: indirizzo logico (pagine da 8Kb) –  0001 -­‐ 0001 0001 0000 (pagina 1, indirizzo 0x1110) •  Indirizzo fisico: –  0100 – 0001 0001 0000 (pagina 4, indirizzo 0x1110) Frammentazione Processi in memoria •  Il problema della frammentazione è risolto •  Al termine di un processo vengono “liberate” tu@e le pagine u&lizzate da questo •  Un nuovo processo ha a disposizione tu@e le pagine rimaste “libere” 4 Dimensione della tabella delle pagine •  Gli a@uali processori indirizzano memorie di grandi dimensioni e la dimensione della tabella delle pagine risulta troppo grande per essere contenuta nella MMU •  Per esempio con RAM da 4Gb e pagine da 4Kb (sia Windows che Linux u&lizzano pagine da 4Kb) si hanno più di un milione di pagine •  La tabella viene quindi memorizzata nella RAM e solo una copia di una piccola parte di questa risiede nella MMU Pagine logiche e fisiche Memoria virtuale •  I processi a6vi in un sistema opera&vo mul&tasking sono mol& ed è probabile che il numero complessivo delle pagine richieste da tu6 i processi sia superiore al numero di pagine di memoria effe6vamente disponibili •  Pra&camente tu6 i moderni sistemi opera&vi implementano la tecnica della “memoria virtuale”: il gestore della memoria me@e a disposizione un numero di pagine superiore a quelle presen& nella memoria fisica •  Alcune pagine sono salvate temporaneamente nella memoria di massa (normalmente hard disk) •  La memoria di massa u&lizzata a questo scopo è comunemente chiamata, in ambiente Unix-­‐Linux, swap o spazio di swap, mentre, in ambiente Windows, è chiamata file di paging. Prestazioni •  La memoria di massa ha tempi di accesso estremamente più len& della memoria centrale: –  memoria centrale 50-­‐60 nanosecondi (circa 10-­‐8 secondi) –  memoria di massa 2-­‐4 microsecondi (circa 10-­‐3 secondi) •  E’ necessario quindi ridurre al minimo le operazioni di swapping (spostamento delle pagine dallo spazio di swap alla memoria fisica) Località del codice •  Normalmente un processo in ogni fase della sua esecuzione fa riferimento a istruzioni e da& contenu& in poche pagine di memoria con&gue. •  Località delle istruzioni: l’esempio classico è un ciclo che ripete più volte istruzioni consecu&ve •  Località dei da&: la stru@ura più comunemente u&lizzata è l’array in cui i da& sono con&gui in memoria Tabella delle pagine •  La MMU trasla gli indirizzi •  Se la pagina non è presente in memoria (page-­‐fault) il processo viene posto in stato di wait in a@esa che la pagina venga caricata in memoria •  Il gestore della memoria recupera la pagina, aggiorna la tabella delle pagine e riporta il processo in ready 5 Page-­‐fault •  Ogni page fault rallenta dras&camente l’esecuzione di un processo che deve transitare dallo stato di wait e deve a@endere il caricamento della pagina dalla memoria di massa •  Se non sono disponibili pagine libere in memoria centrale è necessario sos&tuire una pagina dello stesso processo (allocazione locale) o di un altro processo (allocazione globale) Strumen& per la ges&one delle poli&che •  FIFO –  è sufficiente memorizzare per ogni pagina il momento del caricamento in memoria •  LRU –  deve essere memorizzato il tempo ad ogni accesso alla pagina •  LFU –  deve essere memorizzato un contatore incrementato ad ogni accesso alla pagina –  per semplificare la ges&one si u&lizza un bit che viene se@ato se di fa accesso a una pagina (i bit vengono periodicamente azzera&) la poli&ca diventa quindi NRU (Not Recently Used) Codice condiviso Poli&che per la ges&one del page-­‐fault •  FIFO (First In First Out) –  la pagina da rimuovere è la prima che è stata caricata. L’idea è che le pagine “vecchie” non vengano più u&lizzate in futuro •  LRU (Least Recently Used) –  la pagina da rimuovere è quella inu&lizzata da più tempo. L’idea è che se non è u&lizzata da molto tempo non verrà più u&lizzata •  LFU (Least Frequently Used) –  la pagina da rimuovere è quella meno u&lizzata. L’idea è che se è stata poco u&lizzata sarà poco u&lizzata anche in futuro Swapping •  Se una pagina viene eliminata dalla memoria centrale deve essere copiata sulla memoria di massa •  Un “dirty bit” se@ato se la pagina viene modificata può essere u&lizzato per evitare questa fase di riscri@ura su disco (molto spesso per le pagine di codice) Windows e Linux •  Mol& sistemi opera&vi prevedono l’uso di funzioni condivise fra vari processi –  linux – shared objects –  windows – DLL (Dynamic Link Library) •  Queste funzioni vengono caricate solo se u&lizzate e in questo caso condivise fra i vari processi 6