Sistemi Operativi - Home di homes.di.unimi.ithomes.di.unimi.it/sisop/lucidi/Solez8-0203.pdfAA...

Sistemi Operativi

Lezione 8

La gestione della memoria

AA 2002/03©Bruschi, Rosti

Sistemi OperativiCorso di laurea in Informatica

2

La memoria come risorsa

• La memoria centrale è una risorsafondamentale di un sistema di calcolo

• L’accesso a memoria centrale è unadelle operazioni più frequenti• Accesso ai dati e al codice

• La tecnica di gestione della memoria haun effetto determinante sulle prestazionidel sistema



3

Requisiti della gestione dellamemoria

• Rilocazione

• Protezione

• Condivisione

• Organizzazione logica

• Organizzazione fisica



4


• Rilocazione• Il programmatore non sa dove il programma verrà

caricato in memoria per essere eseguito

• Durante l’esecuzione, il programma può essserescaricato sul disco e ricaricato successivamente inmemoria ad un indirizzo diverso (rilocazione)

• Gli indirizzi di memoria nel codice devono esseretradotti in indirizzi fisici di memoria



5


• Protezione• I processi non devono poter accedere ad aree di

memoria di altri processi senza permesso• Deve esere impossibile controllare indirizzi fisici

assoluti nei programmi dato che un programmapuò essere rilocato

• I riferimenti alla memoria devono essere verificatidurante l’esecuzione

• Il sistema operativo non può prevedere tutti i riferimentialla memoria che un programma farà



6


• Condivisione• Permettere a vari processi l’accesso ad

aree di memoria condivise

• Permettere a ciascun processo l’accessoalla stessa copia di un programmapiuttosto che dare a ciascuno una copiaprivata



7


• Organizzazione logica• I programmi sono scritti a moduli

• I moduli possono essere scritti e compilatiindipendentemente

• I moduili possono avere gradi diversi diprotezione (read-only, execute-only)

• Condivisione di moduli



8


• Organizzazione fisica• La memoria allocata ad un programma e la

sua area dati possono essere insufficienti

• I programmatori non sanno quantamemoria sarà disponibile



9

Schemi elementari di gestionedella memoria

• Partizione fissa unica• Un solo programma in esecuzione oltre al

sistema operativo• Sistemi monoprogrammati

• Partizioni fisse multiple• Fino a k programmi in esecuzione

simultaneamente• Se non c’e` una partizione disponibile il job

aspetta



10

Partizione fissa unica

mainframeminicomputer

primi PC con MS-DOS

sistemi embedded,palmtop



11

Partizioni multiple fisse

• Code separate per ogni partizione• possibile sottoutilizzo del sistema

• Singola coda di input



12

Partizioni fisse

• Questo schema di gestione dellamemoria richiede alcuni accorgimentinella fase di preparazione deiprogrammi e generazione del codice• Compilatore• Linker• Loader

• statico• dinamico



13

Traduzione• Compilatore

• Traduce un programma scritto in linguaggio adalto livello nel suo corrispettivo in linguaggioassembly

• Assemblatore• Traduce un programma scritto in linguaggio

assembly nel suo corrispettivo in linguaggiomacchina

• Prodotti aggiuntivi della traduzione• Symbol table• Informazioni sulle dimensioni del modulo oggetto• Informazioni per il debugging



14

Linker• Collega i moduli oggetto compilati

indipendentemente• Statico

• Tutti i riferimenti sono risolti e tradotti in indirizzi logici dopo lacompilazione, prima del caricamento

• Dinamico• A tempo di caricamento

• Moduli esterni (target) sono aggiunti all’applicazione dopo averlaletta in memoria dal loader

• A tempo di esecuzione• I moduli target sono caricati e i riferimenti risolti solo durante

l’esecuzione al momento in cui vengono richiamati

• Con linking dinamico si facilita l’aggiornamento deimoduli target e la condivisione del codice



15

Loader

• Carica un programma in memoria• Usa le informazioni nella symbol table

• Caricamento assoluto• Gli indirizzi usati dal programma sono fissati a tempo di

compilazione

• Caricamento rilocabile• Gli indirizzi generati dal compilatore sono tutti relativi ad

un punto di inzio (indirizzi logici) e vengono tradotti inindirizzi fisici prima del caricamento del programma

• Caricamento dinamico a tempo di esecuzione• I riferimenti alla memoria sono mantenuti in formato

relativo e tradotti in indirizzi assoluti solo nel momento incui vengono utilizzati



16

Partizioni fisse

• Le partizioni fisse hanno avuto un certosuccesso in sistemi di tipo batch• Relativa staticità dei programmi

• Con l’avvento dei sistemi time sharing, si èposto il problema di dover gestire nelcomplesso processi la cui dimensione era digran lunga superiore di quella della memoriacentrale

• Servono schemi piu` sofisticati di gestionedella memoria delle partizioni fisse



17

Schemi sofisticati di gestionedella memoria

• Le soluzioni possibili sono due• Swapping

• Un processo viene caricato interamente inmemoria centrale, esegue per un periodo ditempo e poi viene scaricato su disco,rimpiazzandolo con un altro

• Memoria virtuale• Un processo viene caricato parzialmente in

memoria ed eseguito come se fosseinteramente presente



18

Swapping

• Numero, dimensione e posizione delle partizionicambiano col variare dei processi in memoria

• Lo stato della memoria si modifica continuamente• I processi accedono alla memoria centrale• Lasciano la memoria per poi rientrarvi, non necessariamente nello

stesso posto occupato in precedenza



19

Swapping

• Le dimensioni di un processo cambianodurante l’esecuzione• Dati dinamici

• Prevedere spazio per l’espansione quandolo si alloca in memoria



20

Swapping con partizioni multiplevariabili

• Problemi• Necessità di un meccanismo dinamico di

rilocazione e protezione delle zone dimemoria

• Gestione delle zone libere e occupate dellamemoria centrale

• Frammentazione esterna• Degli spazi liberi



21

Rilocazione e Protezione

• Si usano dei registri hw che contengonol’indirizzo di base e quello limite delprocesso in esecuzione• Gli indirizzi logici vengono sommati al

valore contenuto nel registro base perottenere l’indirizzo fisico di una locazione

• Indirizzi logici il cui valore superi quellocontenuto nel registro limite generanoerrore



22

Gestione Holes e Processi

• Le strutture dati usate in questi casi sono• Bit map

• Liste linkate



23

Partizioni multiple variabili

• Un ulteriore problema• Quale area libera della memoria

scegliere quando si carica unprogramma



24


• Strategie di scelta possibili• Ottimizzare il tempo di ricerca: First fit

• cerco il primo buco che può contenere ilprogramma

• Ottimizzare lo spazio usato: Best fit• cerco tra tutti i buchi che possono contenere il

programma quello di dimensione minima

• Ottimizzare lo spazio avanzato: Worst fit• cerco tra tutti i buchi che possono contenere il

programma quello di dimensione massima



25


• La soluzione che fornisce le prestazionimigliori è First Fit

• Risultati sperimentali mostrano che trale tre strategie la peggiore è BF• Tende a riempire la memoria di troppi

buchi piccoli inutilizzabili

• Anche worst fit non ottiene buoneprestazioni



26

Frammentazione esterna

• Frazionamento della memoria libera inpiccoli pezzi inutilizzabili

• Una possibile soluzione è l’adozione distrategie di compressione dellamemoria centrale• Operazione molto costosa in termini di

efficienza del sistema

• Non esistono strategie ottimali



27

Memoria virtuale

• Abbiamo sinora assunto che durantel’esecuzione di un programma, lo stessodovesse risiedere completamente in MC

• Intorno alla metà degli anni ’70 vieneperò osservato che questo non è unrequisito fondamentale per consentirel’esecuzione di un programma



28

Principio di Località

• Durante la loro esecuzione i programmi godono didue importanti proprietà• Località temporale: se un elemento x viene referenziato

all’istante t, la probabilità che x venga referenziato ancheall’istante t+t’ cresce al tendere di t’‡0

• Località spaziale: se un elemento x di posizione s vienereferenziato all’istante t, la probabilità che venga referenziatoun elemento x’ di posizione s’,

all’istante t+t’ cresce al tendere di t’ ‡0

D£- 'ss



29

Località

• I principi di località suggeriscono unimportante accorgimento nella gestionedella memoria• non è necessario caricare un programma

interamente in memoria per poterloeseguire, è sufficiente caricarlo località perlocalità



30

Località: i vantaggi

• Si svincolano le dimensioni di unprogramma dalla dimensione dellamemoria centrale

• Si può aumentare il livello dimultiprogrammazione, a parità dimemoria centrale disponibile

• Maggiore velocità nelle operazioni diswapping



31

Memoria virtuale: implementazione

• Paginazione• Suddividere la memoria fisica e lo spazio di

indirizzi di un programma in blocchi didimensioni uguali

• I primi sono detti “frame”

• Gli altri “pagine”

• Un programma genera indirizzi virtuali cheformano il suo spazio virtuale

• Il sistema traduce l’indirizzo virtuale in unindirizzo fisico



32

Paginazione

Schema di funzionamento



33

Paginazione

La pagina con gli indirizzida 44K a 48K occupa ilframe 7 in memoria

Esempio di calcolo di ind.Ind. Logico 20500: si trovanella pagina 5 (20K-24K)La pagina 5 si trova nel frame 3 (12K-16K), quindi

20500 = 20480 + 20diventa12288 + 20 = 12308



34

Paginazione

• Servono le seguenti strutture dati• Tabella dei frame (spazi di memoria fisica)

• Tabella delle pagine• definisce l’associazione pagina ‡ frame

• una per ogni processo in esecuzione o inattesa di esecuzione

• Tabella delle pagine del processo inesecuzione

• Caricata nella tabella delle pagine di sistema



35

Tabella delle pagine



36

Tabella delle pagine

Elemento di una tabella delle pagine



37

Tabella delle pagine di sistema• Tre alternative per implementarla

• Registri specializzati• Molto efficiente in esecuzione ma molto costosa per

tabelle di grosse dimensioni, soprattutto in context switch

• La tabella sta in memoria e un registro indirizza latabella delle pagine del processo in esecuzione,tra quelle di tutti i processi del sistema

• Lenta richiede due accessi a memoria centrale perrecuperare le informazioni

• Registri associativi• Implementano un Translation Lookaside Buffer di 8-64

elementi



38

TLBs – Translation Lookaside Buffers



39

TLB



40

Calcolo degli indirizzi

• Con pagine di dimensione 2k, per il calcolodegli indirizzi fisici si sfrutta l’indirizzo logico• I k bit bassi dell’indirizzo individuano lo

spiazzamento all’interno della pagina• I restanti bit alti individuano il numero di pagina• Il numero di pagina si usa come indice nella

tabella delle pagine• Il valore trovato in corrispondenza è il numero di

page frame associato alla pagina• Se la pagina è presente in memoria, il numero di

page frame è copiato nei bit alti del registro dioutput e concatenato ai k bit bassi dell’offset



41

Demand Paging• Sistema completamente automatico per

realizzare memoria virtuale• Il programmatore non è coinvolto

• Uno schema elementare può essere ilseguente (lazy swapper)• Si carica la prima pagina del programma

da eseguire

• Quando una nuova pagina vienereferenziata, la si carica in memoria



42

Demand paging

• Deve essere possibile stabilire a priorila presenza o meno di una pagina inmemoria• Bit di validita` per la pagina nella tabella

delle pagine

• L’evento “pagina non trovata” inmemoria è denominato page fault

• Gestire il page fault significapreoccuparsi di recuperare la pagina dadisco e portarla in memoria



43

Demand Paging

• In un sistema con memoria virtuale iltempo di page fault e la frequenza concui i page fault si verificano sonoparametri critici

• Se p è la probabilità che si verifichi unpage fault,

( ) fault page di tempop - 1 accesso di medio tempo ⋅+⋅= pma



44

Gestione del Page Fault

• Page fault quando il bit di validita` dellapagina riferita e` a 0



45

Gestione del Page Fault (1)

1. Viene generato un trap di page fault

2. Salvataggio dei registri

3. Il SO individua il numero di pagina dacaricare

4. Il SO verifica la validità di questo dato ecerca un frame libero

5. Se il frame selezionato è dirty, lo si riscrivesu disco prima di copiarvi la nuova pagina



46

Gestione del Page Fault (2)

6. Il SO trasferisce la nuova pagina inmemoria

7. La tabella delle pagine viene aggiornata

8. I registri vengono ripristinati, tenendoconto che l’istruzione che ha generato ilfault deve essere “ripristinata”

9. Il processo che ha generato il fault vienerimesso in esecuzione



47

Problemi da affrontare

• La precedente procedura presuppone lasoluzione dei seguenti problemi• Come fare il backup di un’istruzione

• Come e dove recuperare l’indirizzo dellepagine che risiedono su disco

• Quali frame scegliere di rimpiazzare



48

Backup dell’istruzione

• Valore del PC al momento del page fault• Inizio dell’istruzione• Instruzioni con autoincremento/autodecremento



49

Lock delle pagine in memoria

• La memoria virtuale può anche interagire con leoperazioni di I/O

• Un processo A esegue una read per acquisire deidati in un buffer• Mentre A è in attesa di I/O, un nuovo processo B viene

avviato• B genera un page fault• Il frame con il buffer di A può essere scelto per essere

scaricato• È necessario prevedere un meccanismo che consenta di

bloccare (lock) temporaneamente alcune pagine



50

Indirizzo delle pagine

(a) Area di swap statica(b) Back up di pagine dinamico



51

Aspetti implementativiCoinvolgimento del S.O. nella paginazione

• Fasi in cui il SO è coinvolto in attività legate allamemoria virtuale

1. Creazione dei processi- Determinare la dimensione del programma- Predisporre la tabella delle pagine

2. Esecuzione dei processi- Reset della MMU per nuovi processi- Gestione TLB

3. Page fault- Determinare l’indirizzo logico che ha causato il PF- Gestione page fault

4. Terminazione del processo- Rilascio della page table e dei frame



52

Algoritmi di rimpiazzamento dellepagine

• Durante la gestione di un page fault puòessere necessario• Individuare le pagine da scaricare su disco

• Salvare le pagine modificate durantel’esecuzione, quelle non modificatepossono essere sovrascritte



53

Algoritmo ottimo per il rimpiazzamentodelle pagine

• Sostituire, tra quelle presenti in memoria, la pagina chesarà referenziata il più tardi possibile• Ottimale ma non realizzabile

• Possibili stime• Tenere traccia dell’uso passato delle pagine e inferire il futuro

dal passato

• Anche quest’euristica è molto difficile da realizzarepraticamente



54

Algortitmo per il rimpiazzamento delle pagine“Not Recently Used”

• Ogni pagina ha un Reference bit e un Modified bit• I bit vengono asseriti (via hw) quando la pagina è acceduta

o modificata, rispettivamente

• Quattro stati possibili delle pagine1. not referenced, not modified2. not referenced, modified3. referenced, not modified4. referenced, modified

• NRU rimuove la pagina casualmente a partire dallaclasse non vuota con l’indice più basso



55

Algoritmo di rimpiazzamento delle pagineFIFO

• Mantiene una lista delle pagine cherispetta l’ordine con cui le stesse sonostate caricate in memoria• Le pagine più “anziane” sono all’inizio della

lista

• Le pagine più anziane sono le prime adessere sostituite

• Svantaggio• Sostituire una pagine che è referenziata

spesso



56

Algoritmo di rimpiazzamento delle pagine“Second Chance”

A) Le pagine sono ordinate FIFO con un bit d’uso R

B) La lista delle pagine quando si verifica un page fault all’istante 20, eA ha il bit R a 1



57

Algoritmo di rimpiazzamento delle pagine“the clock”

• Come “2nd chance” ma usa una lista circolare perevitare gli spostamenti di 2nd chance

• La lancetta punta alla pagina più vecchia



58

Least Recently Used (LRU)• Ipotesi: le pagine usate recentemene saranno usate anche

in un futuro prossimo• Elimina le pagine che non sono usate da più tempo

• Realizzazione mediante una lista linkata di pagine• Quelle usate più recentemente sono all’inizio• La lista deve essere aggiornata ad ogni riferimento

• Realizzazione mediante un contatore incrementatoautomaticamente dopo ogni istruzione• Si copia il contatore nella entry della tabella delle pagine della

pagina appena referenziata dopo ogni accesso• La pagina vittima è quella con il contatore più basso• Il contatore viene azzerato periodicamente



59

Simulazione di LRU in hardware• N page frame• Tabella NxN inizializzata a 0• Quando si fa riferimento al frame k, i bit della

riga k-esima vengono posti tutti a 1, quellidella colonna k tutti a 0

• In ciascun istante la riga con il minimo valorebinario è quella utilizzata meno di recente



60

Simulazione di LRU in hardware

LRU per 4 page frame; la sequenza dei riferimenti a pagineè 0,1,2,3,2,1,0,3,2,3



61

Simulazione di LRU via software• Non tutti i processori hanno l’hw necessario• Not Frequently Used

• Ogni pagina ha un contatore nel quale si somma ilvalore del bit R ad ogni clock tick

• Si elimina la pagina col contatore minimo• Mantiene troppa memoria

• Aging• Come NFU ma prima di sommare i bit R, si fa uno

shift a dx di 1 del contatore e R è sommato al bitpiù a sinistra

• Si elimina la pagina col contatore minimo• Memoria grossolana con un solo bit per tick



62

Simulazione di LRU in software

• L’algoritmo di aging simula LRU via software



63

Algoritmo di rimpiazzamento delle pagine“working set”

• Working set: insieme delle pagine usate dai kriferimenti alla memoria più recenti

• w(k,t): dimensione del working set al tempo t



64

Confronto di algoritmidi rimpiazzamento delle pagine

Problemi implementativi



66

Anomalia di Belady

• FIFO con 3 page frame• FIFO con 4 page frame• Le P indicano quali riferimenti danno origine a page fault



67

Politiche di allocazione globali vs locali

a) Configurazione originaleb) Rimpiazzamento delle pagine localec) Rimpiazzamento delle pagine globale



68

Politiche di allocazione globali vs locali

Frequenza dei page fault in funzione del numero dipage frame allocati



69

Thrashing

• I sistemi possono andare in thrash nonostante sianoprogettati bene

• Quando l’algortimo PFF (page fault frequency) indica che• Alcuni processsi hanno bisogno di più memoria• Nessuno processo può operare con meno memoria

• Soluzione:Ridurre il numero di processi che competono per lamemoria• Scaricare su disco uno o più processsi e dividere le pagine che

erano loro assegnate• Rivalutare il livello di multiprogrammazione



70

Dimensionamento delle pagine -pagine piccole

• Vantaggi• Minore frammentazione interna

• Migliore adattamento a varie strutture dati esezioni di codice

• Meno parti di programma inutilizzate inmemoria

• Svantaggi• Maggior numero di pagine per programma

• Tabelle delle pagine più grandi



71

Dimensione delle pagine



72

Comportamento di un processo

La segmentazione



74

Segmentazione

• La memoria virtuale vista finora èmonodimensionale

• Avere più spazi di indirizzi separati puòessere vantaggioso in presenza di aree datidistinte che crescono durante l’esecuzione• Es. Compilatore che usa aree per

• Testo sorgente• Symbol table• Tabella delle costanti intere e floating point• Albero di parsing• Stack per le chiamate di procedura del compilatore

stesso



75

Segmentazione

• Si fornisce alla macchina un insieme di spazi diindirizzi logici indipendenti detti segmenti

• I segmenti hanno dimensioni diverse epossono cambiare senza interferire gli uni congli altri

• L’utente definisce i segmenti ma non li gestisce• Semplifica le operazioni di linking

• Segmento, offset per indiciare i moduli• I segmenti sono indipendenti

• Facilita la condivisione di librerie



76

Segmentazione

Ogni tabella delle pagine cresce o decresceautonomamente



77

Segmentazione



78

Segmentazione con Paginazione: MULTICS

• Sistema con indirizzo fisico di 24 bit• Il descrittore del segmento punta alla tabella delle pagine• Esempio di descrittore di segmento

Sistemi Operativi - Home di homes.di.unimi.ithomes.di.unimi.it/sisop/lucidi/Solez8-0203.pdfAA...

Documents

Transcript of Sistemi Operativi - Home di homes.di.unimi.ithomes.di.unimi.it/sisop/lucidi/Solez8-0203.pdfAA...