Il Sistema Operativo Introduzione Gestione dei processi...
Transcript of Il Sistema Operativo Introduzione Gestione dei processi...
Il Sistema Operativo
Introduzione
Gestione dei processi
Gestione della memoria
Memoria cache (cenni)
Informatica Informatica Informatica Informatica B B B B –––– Prof. A. MorzentiProf. A. MorzentiProf. A. MorzentiProf. A. Morzenti
2
Il sistema OperativoIl sistema OperativoIl sistema OperativoIl sistema Operativo
� Il sistema operativo (SO) è uno strato software che nasconde agli utenti i dettagli dell’architettura hardware del calcolatore
� Fornisce diverse funzionalità ad alto livello che facilitano l’accesso alle risorse del calcolatore
� Supporta l’esecuzione dei programmi applicativi definendo una macchina virtuale, cioè un modello ideale del calcolatore, sollevando il software applicativo dal compito di gestire i limiti delle risorse disponibili
3
Architettura del sistema operativoArchitettura del sistema operativoArchitettura del sistema operativoArchitettura del sistema operativo
� Il SO è tipicamente organizzato a strati
� Ciascun strato costituisceuna macchina virtuale che gestisceuna risorsa del calcolatore
� Le principali funzionalità offerte sono:
La gestione dei processi
La gestione della memoria
La gestione delle periferiche
La gestione del file system
La gestione della rete
La gestione dell’interfaccia utente
� Le prime tre funzionalità sono indispensabili per il funzionamento del sistema e pertanto costituiscono il nucleo del SO (Kernel)
Macchina fisica
Gestione dei processi
Gestione della memoria
Gestione delle periferiche
File system
Interprete comandi
Programmi utente
Kernel
4
Tipi di Sistema OperativoTipi di Sistema OperativoTipi di Sistema OperativoTipi di Sistema Operativo
� Esistono diversi tipi di sistema operativo, ma in generale si possono dividere in:
Monoutente e monoprogrammato
• Esecuzione un solo programma applicativo alla volta
• Viene utilizzato da un solo utente per volta
• Esempio: DOS
Monoutente e multiprogrammato (multitasking)
• Consente di eseguire contemporaneamente più programmi applicativi
• Esempio: Windows 95
Multiutente
• Consente l’utilizzo contemporaneo da parte di più utenti
• E’ inerentemente multiprogrammato
• Esempio: Linux
5
Gestione dei processiGestione dei processiGestione dei processiGestione dei processi
� Il SO si occupa di gestire l’esecuzione concorrente di piùprogrammi utente
� La CPU del calcolatore (o le CPU nei sistemi multiprocessore) deve essere distribuita in maniera opportuna fra i programmi da eseguire
� Ogni programma eseguito ha a disposizione una macchina virtuale realizzata dal SO che ne consente l’esecuzione come se la CPU del calcolatore fosse interamente dedicata a esso
6
Gestione della memoriaGestione della memoriaGestione della memoriaGestione della memoria
� La gestione concorrente di molti programmi applicativicomporta la presenza di molti programmi in memoria centrale
� Il SO offre a ogni programma applicativo la visione di una memoria virtuale, che può avere dimensioni maggiori di quella fisica
� Per gestire la memoria virtuale il SO dispone di diversi meccanismi:
Rilocazione
Paginazione
Segmentazione
7
Gestione del file system Gestione del file system Gestione del file system Gestione del file system
� Il SO si occupa di gestire i file sulla memoria di massa:
Creare un file
Dargli un nome
Collocarlo in un opportuno spazio nella memoria di massa
Accedervi in lettura e scrittura
� Gestione dei file indipendente dalle caratteristiche fisiche della memoria di massa
� I file vengono inclusi all’interno di directory (o cartelle, o cataloghi):
Hanno una tipica organizzazione ad albero
Alcuni sistemi operativi permettono una struttura a grafo
8
La struttura ad alberoLa struttura ad alberoLa struttura ad alberoLa struttura ad albero
9
Organizzazione dei file Organizzazione dei file Organizzazione dei file Organizzazione dei file
� A ciascun utente è normalmente associata una directory specifica, detta home directory
� Il livello di protezione di un file indica quali operazioni possono essere eseguite da ciascun utente
� Ciascun file ha un pathname (o nome completo) che include l’intero cammino dalla radice dell’albero
� Il contesto di un utente all’interno del file system è la directory in cui correntemente si trova
10
Gestione delle Gestione delle Gestione delle Gestione delle periferiche: i DRIVERperiferiche: i DRIVERperiferiche: i DRIVERperiferiche: i DRIVER
� I Driver sono meccanismi software a cui è affidato il compito di trasferire dati da e verso le periferiche
� Consentono ai programmi applicativi di leggere o scrivere i dati con primitive di alto livello che nascondono la struttura fisica delle periferiche (e.g., nel sistema Unix le periferiche sono viste come file speciali)
� Danno all’utente l’impressione che la periferica sia dedicata all’utente
11
Gestione dellGestione dellGestione dellGestione dell’’’’interfaccia utenteinterfaccia utenteinterfaccia utenteinterfaccia utente
� Il SO fornisce un interprete dei comandi inseriti dall’utente attraverso la tastiera o il mouse
� L’interfaccia utente può essere
Testuale (esempio: DOS)
Grafica (esempio: Windows)
� Consente l’inserimento di diversi comandi:
Esecuzione di programmi applicativi
Operazioni sulle periferiche
Configurazione dei servizi del SO
Operazioni sul file system (creazione, rimozione, copia, ricerca, ecc.)
12
Che cosa Che cosa Che cosa Che cosa èèèè un processo per il SO?un processo per il SO?un processo per il SO?un processo per il SO?
� Processo ≠ programma !
� Processo = esecuzione di un programma, composto da:
codice eseguibile (il programma stesso)
dati dell’esecuzione del programma
informazioni relative al suo funzionamento (stato)
� Lo stesso programma può essere associato a piùprocessi:
Un programma può essere scomposto in varie parti e ognuna di esse può essere associata a un diverso processo
Lo stesso programma può essere associato a diversi processi quando esso viene eseguito piùvolte, anche simultaneamente
13
Lo stato di un processoLo stato di un processoLo stato di un processoLo stato di un processo
� Lo stato del processo può essere distinto fra stato interno e stato esterno.
� Lo stato interno indica:
la prossima istruzione del programma che deve essere eseguita;
i valori delle variabili e dei registri utilizzati dal processo.
� Lo stato esterno indica se il processo è:
in attesa di un evento, ad es. la lettura da disco o l’inserimento di dati da tastiera;
in esecuzione;
pronto per l’esecuzione, e quindi in attesa di accedere allaCPU.
14
Il sistema operativo e le macchine virtualiIl sistema operativo e le macchine virtualiIl sistema operativo e le macchine virtualiIl sistema operativo e le macchine virtuali
� Il sistema operativo può gestire più processi simultaneamente
� Rende quindi visibile ad ogni processo una macchina virtuale ad esso interamente dedicata e quindi con risorse proprie
CPU A RAM A
OD A
HD A
Rete A I/O A
pro
c. A
CPU B RAM B
OD B
HD B
Rete B I/O B
pro
c. B
CPU D RAM D
OD D
HD D
Rete D I/O D
pro
c. D
CPU C RAM C
OD C
HD C
Rete C I/O C
pro
c. C
bus
15
Il sistema operativo e la macchina realeIl sistema operativo e la macchina realeIl sistema operativo e la macchina realeIl sistema operativo e la macchina reale
CPU
A, B, C, D
RAM
ABCD
HD
ABCD
OD
ABCD
Rete
A, B, C, D
I/O
A, B, C, D
bus
utilizzo a rotazione suddivisione in blocchi suddivisione in blocchi
suddivisione in blocchi utilizzo a rotazione utilizzo a rotazione
16
I processi I processi I processi I processi eeee il sistema operativoil sistema operativoil sistema operativoil sistema operativo
� Anche il sistema operativo è implementato tramite processi;
� Il sistema operativo è garante che i conflitti tra i processi siano controllati e gestiti correttamente;
� Il sistema operativo viene eseguito in modalità privilegiata (kernel mode o supervisor), così da poter controllare gli altri processi eseguiti in modalità user.
Kernel Kernel Kernel Kernel (o SupervisorSupervisorSupervisorSupervisor) modemodemodemode: la CPU può eseguire qualsiasi istruzione, iniziare qss. operazione I/O, accedere a qss. area di memoria, etc.
User modeUser modeUser modeUser mode: certe istruzioni, che alterano lo stato globale della macchina, non sono permesse: operazioni I/O, accesso a certe aree di memoria, etc.
17
Chiamate al Chiamate al Chiamate al Chiamate al supervisorsupervisorsupervisorsupervisor
� I processi utente per eseguire operazioni privilegiate(accesso a file, accesso ad altre risorse, operazioni di I/O, ecc.) invocano il supervisor tramite chiamate di sistema
� Perché usare la modalità privilegiata (supervisor)?
Le operazioni di I/O sono operazioni riservate:• un processo A non deve poter andare a scrivere messaggi su un terminale non associato allo stesso processo A;
• un processo A non deve poter leggere caratteri immessi da un terminale non associato allo stesso processo A.
Un processo non deve poter sconfinare al di fuori del proprio spazio di memoria:• per non accedere allo spazio di memoria associato a un altro processo, modificando codice e dati di quest’ultimo;
• per non occupare tutta la memoria disponibile nel sistema, bloccandolo e rendendolo così inutilizzabile da altri processi.
La condivisione di risorse (dischi, CPU, ecc.) deve essere tale da cautelare i dati di ogni utente;
18
Stato di un processo (1)Stato di un processo (1)Stato di un processo (1)Stato di un processo (1)
� In esecuzione: assegnato al processore ed eseguito da esso
� Pronto: può andare in esecuzione, se il gestore dei processi lo decide
� In attesa: attende il verificarsi di un evento esterno per andare in stato di pronto
Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
19
Stato di un processo (2)Stato di un processo (2)Stato di un processo (2)Stato di un processo (2)
� I processi appena creati sono messi in stato di pronto
� Il nucleo decide quale processo pronto mettere in stato di esecuzione
� Il nucleo assegna il processore a un processo per un quanto di tempo
Coda dei processi pronti
Round-robin
Priorità dei processi
Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
P1 P2
20
Stato di un processo (3)Stato di un processo (3)Stato di un processo (3)Stato di un processo (3)
� Il processo in esecuzione passa in stato di attesa se richiede operazioni di I/O (interruzione interna)
� Corrisponde alla esecuzione dell’istruzione “chiamata a supervisore”(SuperVisor Call, SVC) Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
P1
P2
21
Stato di un processo (4)Stato di un processo (4)Stato di un processo (4)Stato di un processo (4)
Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
P1
P2� Cambiamento di contesto:
Salvare il contesto di P1nel suo descrittore di processo
� Il processore è ora libero, un altro processo passerà in esecuzione
22
Stati di un processo (5)Stati di un processo (5)Stati di un processo (5)Stati di un processo (5)
Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
P1
P2
� Quando l’operazione di I/O è finita viene generata un’interruzione esterna
� Il processo in esecuzione viene interrotto
� Il nucleo esegue il gestore delle interruzioni che esegue le azioni opportune
� P1 può tornare pronto
� Il nucleo sceglie qualeprocesso mandare inesecuzione
23
Stato di un processo (6)Stato di un processo (6)Stato di un processo (6)Stato di un processo (6)
Processo in
esecuzione
Processo
pronto
Processo in
attesa
Inizio esecuzione
Primo processo
pronto
- Fine quanto di tempo
- Interruzione esterna
Interruzione interna
Evento esterno
atteso
- Fine esecuzione
- Abort per errore
P1
P2� Pre-emption: quando il quanto di tempo èscaduto, il nucleo interrompe il processo in esecuzione
� Si cerca di garantire un uso equo della CPU a tutti i processi
24
La gestione del quanto di tempo La gestione del quanto di tempo La gestione del quanto di tempo La gestione del quanto di tempo
� Il quanto di tempo è gestito da una particolare interruzione, generata dall’orologio di sistema:
a una frequenza definita, il dispositivo che realizza l’orologio di sistema genera un’interruzione. La routine di risposta relativa incrementa una variabile opportuna che contiene il tempo di esecuzione del processo corrente
se il quanto di tempo non è scaduto la routine termina e, se non ci sono interruzioni annidate, il processo prosegue nell’esecuzione
se invece il quanto di tempo è scaduto viene invocata una particolare funzione del nucleo (preempt) che cambia lo stato del processo da esecuzione a pronto, salva il contesto del processo e attiva una particolare funzione del nucleo (change) che esegue una commutazione di contesto e manda in esecuzione un processo pronto.
25
Il S.O. e la gestione della memoriaIl S.O. e la gestione della memoriaIl S.O. e la gestione della memoriaIl S.O. e la gestione della memoria
� E’ un modello lineare
� La memoria è una sequenza di celle numerate da 0 fino a un valore massimo M
� Il numero che identifica ogni cella è detto indirizzo
� La dimensione della cella dipende dal tipo di calcolatore (per noi sarà di 8 bit, ossia un byte)
MEMORIA
0
1
2
M
Il modello della memoriaIl modello della memoriaIl modello della memoriaIl modello della memoria
26
Spazio di Spazio di Spazio di Spazio di indirizzamentoindirizzamentoindirizzamentoindirizzamento
� Lo spazio di indirizzamento è il numero massimo di indirizzi possibili della memoria
� Dipende dalla lunghezza in bit degli indirizzi
� Se gli indirizzi sono lunghi N bit, lo spazio di indirizzamento è di 2N celle
� Tutte le celle devono essere indirizzabili (cioè devono avere un indirizzo), quindi Dimensione memoria ≤ Spazio indirizzamento
� Le dimensioni della memoria sono generalmente espresse in:
KB (Kilobyte) = 210 byte
MB (Megabyte) = 220 byte
GB (Gigabyte) = 230 byte
27
Memoria virtuale vs. fisicaMemoria virtuale vs. fisicaMemoria virtuale vs. fisicaMemoria virtuale vs. fisica
� Gli indirizzi contenuti in un programma eseguibile sono indirizzi virtuali e danno riferimento alla memoria virtuale
� La memoria effettivamente presente nel calcolatore è la memoria fisica e i suoi indirizzi sono detti indirizzi fisici
� La rilocazione dinamica è uno dei meccanismi di trasformazione da indirizzo virtuale (detto anche rilocabile) afisico
Registro base
Indirizzo
virtuale
(rilocabile)
+Indirizzo
calcolato
(fisico)
28
MEMORIA
PC3
RB1000
PROCESSORE
999
1000
1001
1002
1003
1004
+
processo in esecuzione
0
1
2
3
indirizzi virtualiindirizzi fisici
29
Memoria virtuale vs. fisicaMemoria virtuale vs. fisicaMemoria virtuale vs. fisicaMemoria virtuale vs. fisica
� La memoria virtuale e quella fisica non coincidono per i seguenti motivi:
nella memoria fisica risiedono contemporaneamente il s.o.e i diversi processi
conviene mantenere nella memoria fisica una sola copia di parti di programmi che sono uguali in diversi processi (memoria condivisa)
� per evitare la frammentazione della memoria (spazi vuoti in memoria inutilizzabili) è utile allocare i programmi suddividendoli in pezzi
� la memoria fisica può essere insufficiente a contenere la memoria virtuale di tutti processi
30
MEMORIA
Processo P
Soluzione al problema della frammentazioneSoluzione al problema della frammentazioneSoluzione al problema della frammentazioneSoluzione al problema della frammentazione
Sistema Operativo
Processo Q
Processo R
Processo S
MEMORIA
Sistema Operativo
Processo P
Processo Q
Processo R
Processo S (1)
Processo S (2)
31
PaginazionePaginazionePaginazionePaginazione
� Si rinuncia ad avere una zona contigua della memoria fisica per ciascun processo
� La memoria virtuale del programma viene suddivisa in porzioni (pagine virtuali) di lunghezza fissa (potenza di 2, es: 4K)
� La memoria fisica viene divisa in pagine fisiche della stessa dimensione
� Le pagine virtuali di un programma vengono caricate in altrettante pagine fisiche, non necessariamente contigue
32
MEMORIAVIRTUALE Q
MEMORIAVIRTUALE P
MEMORIAFISICA
dimensione pagina
33
Struttura degli indirizzi virtualiStruttura degli indirizzi virtualiStruttura degli indirizzi virtualiStruttura degli indirizzi virtuali
� Un indirizzo virtuale è costituito da un numero di pagina virtuale (NPV) e da uno spiazzamento (offset) all’interno della pagina
� NB: se (come succede sempre in pratica) la dimensione della pagina è una potenza di 2, giustapponendo giustapponendo giustapponendo giustapponendo numero pagina e offset si calcola la somma base_pagina+offset
NPV offset
indirizzo virtuale
34
Struttura degli indirizzi fisiciStruttura degli indirizzi fisiciStruttura degli indirizzi fisiciStruttura degli indirizzi fisici
� E’ del tutto analoga: si hanno un numero di pagina fisica (NPF) e da uno spiazzamento (offset) all’interno della pagina
NPF offset
indirizzo fisico
35
Traduzione dal virtuale al fisicoTraduzione dal virtuale al fisicoTraduzione dal virtuale al fisicoTraduzione dal virtuale al fisico
NPV offset
indirizzo virtuale
NPF offset
indirizzo fisico
traduzione
le pagine virtuali e quelle fisiche hanno la stessa dimensione, quindi l’offset è lo stesso
36
EsempioEsempioEsempioEsempio
� Spazio di indirizzamento virtuale: indirizzi da 32 bit � 2
32 indirizzi
� Dimensione di pagina: 4K parole (o celle) � 2
12byte (1 cella occupa 1 byte)
Offset � numero di bit necessari per indirizzare una cella all'interno di una pagina = log2(dimensione_pagina)=12
� Numero di pagine dello spazio di indirizzamentovirtuale = 2
32 / 2
12= 2
20pagine
� Spazio di indirizzamento fisico: 4M parole (o celle) � 222
indirizzi
� Numero di pagine dello spazio di indirizzamento fisico = 2
22/ 2
12= 2
10pagine
37
Esempio (segue)Esempio (segue)Esempio (segue)Esempio (segue)
NPV offset
indirizzo virtuale
NPF offset
indirizzo fisico
12bit20bit
10bit 12bit
38
La tabella delle pagineLa tabella delle pagineLa tabella delle pagineLa tabella delle pagine
� E’ il meccanismo più semplice per la traduzione da virtuale a fisico
NPV = 0 offset
indirizzo virtuale
NPF offset
indirizzo fisico
3333
2222
1111
0000
NPFNPFNPFNPFNPVNPVNPVNPV
C’è una tabella delle pagine per ciascun processo
39
MemoryMemoryMemoryMemory Management Management Management Management UnitUnitUnitUnit
� Per accelerare la traduzione da NPV a NPF si ricorre allora alla MMU
� La MMU è una memoria particolarmente veloce (memoria associativa) dalle dimensioni ridotte, contenente solo le informazioni sulle pagine più utilizzate
� Visto che gli NPV e gli NPF si riferiscono alle pagine di un processo, ogni volta che il processo in esecuzione cambia la MMU dovrebbe essere tutta riscritta
� Per evitare ciò si aggiunge una colonna che dice a quale processo appartengono le pagine e un registro che dice qual è il processo attualmente in esecuzione
40
Pagine residenti e nonPagine residenti e nonPagine residenti e nonPagine residenti e non
� Durante l’esecuzione di un programma solo un certo numero delle sue pagine virtuali è caricato in altrettante pagine fisiche
� Tali pagine sono dette pagine residenti
� A ogni accesso alla memoria si controlla che all’indirizzo virtuale corrisponda una pagina residente, altrimenti si produce un interrupt di segnalazione di errore detto page-fault
� Il processo viene sospeso in attesa che la pagina richiesta venga caricata in memoria, eventualmente scaricando su disco una pagina già residente per liberare lo spazio necessario
41
LA MEMORIA CACHELA MEMORIA CACHELA MEMORIA CACHELA MEMORIA CACHE
� Obiettivo:
fornire agli utenti una memoria grande e veloce
fornire al processore i dati alla velocità con cui è in grado di elaborarli
� Problema: Il tasso di crescita nella velocità dei processori non è stato seguito da quello delle memorie
Tempo di accesso alle SRAM: 2 - 25ns al costo di $100 -$250 per Mbyte.Tempo di accesso alle DRAM: 60-120ns al costo di $5 -$10 per Mbyte.Tempo di accesso al disco: da 10 a 20 million ns al costodi $0.10 - $0.20 per Mbyte.
IlIlIlIl problema della problema della problema della problema della memoria: costo vs. prestazionimemoria: costo vs. prestazionimemoria: costo vs. prestazionimemoria: costo vs. prestazioni
42
Prestazioni di processori e cachePrestazioni di processori e cachePrestazioni di processori e cachePrestazioni di processori e cache
µProc60%/anno(2X/1.5yr)
DRAM9%/anno(2X/10yr)
Tempo
1
10
100
1000
1980
1981
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
DRAM
CPU1982
Divario di prestazioniProcessore-Memoria(cresce 50% / anno)
Pre
sta
zio
ni Legge di Moore
43
Soluzione: gerarchia di memoriaSoluzione: gerarchia di memoriaSoluzione: gerarchia di memoriaSoluzione: gerarchia di memoria
Utilizzare diversi
livelli di memoria, con
tecnologie diverse in
modo da ottenere un
buon compromesso
costo/prestazioni
CPU
Incremento del
tempo di
accesso da
parte della
CPU
Dimensioni della memoria ad ogni livello
Livelli della
gerarchia di
memoria
Livello 2
Livello 1
Livello n
44
LLLLivelliivelliivelliivelli della gerarchia di memoriadella gerarchia di memoriadella gerarchia di memoriadella gerarchia di memoria
Registri CPUh Bytes<10s ns
CacheK Bytes10-100 ns1-0.1 cents/bit
Memoria centraleM Bytes200ns- 500ns$.0001-.00001 cents /bit
DiscoG Bytes, 10 ms (10,000,000 ns)10E-6 – 10E-5 cents/bit
CapacitàTempo di accessoCosto
Nastroinfinitosec-min10E-8 cent/bit
Registri
Cache
Memoria
Disco
Nastro
Istr. Operandi
Blocchi
Pagine
Files
PredisposizioneUnità di trasf.
prog./compilatore1-8 bytes
Controllore cache8-128 bytes
OS512-4K bytes
utenteMbytes
Livello superiore
Livelloinferiore
+ veloce
+ grande
45
LocalitLocalitLocalitLocalitàààà
� E’ la proprietà fondamentale dei programmi che rende possibile sfruttare l’organizzazione gerarchica della memoria per incrementarne le prestazioni
� Località: in ogni istante di tempo un programma accede a una parte relativamente piccola del suo spazio di indirizzamento
� Esistono due diversi tipi di località: temporale e spaziale
46
Il principio di localitIl principio di localitIl principio di localitIl principio di localitàààà
� Località temporale: se un dato viene referenziato in un dato istante, è probabile che lo stesso dato venga nuovamente richiesto entro breve
� Località Spaziale: Se un dato viene utilizzato in un dato istante, è probabile che dati posizionati in celle di memoria adiacenti vengano anch’essi richiesti entro breve
� Negli ultimi 15 anni, le tecniche di miglioramento delle prestazioni nell’hardware si sono basate sul principio di località
47
Gerarchia di memoriaGerarchia di memoriaGerarchia di memoriaGerarchia di memoria
� Si considerino solo due livelli di gerarchia:
� Il processore richiede un dato al sistema di memoria:
La richiesta viene prima inviata al livello di memoria superiore (più vicino al processore)
Se il dato non è presente nel livello superiore (fallimento della richiesta) la ricerca viene effettuata nel livello inferiore
Livello inf
di memoriaLivello sup.
di memoriaAl Processore
Dal Processore
blocco X
blocco Y
48
Gerarchia di memoriaGerarchia di memoriaGerarchia di memoriaGerarchia di memoria: : : : definizionidefinizionidefinizionidefinizioni
� Hit (successo): dati presenti in un blocco del livello superiore (esempio: Blocco X)
Hit Rate (tasso di successo): numero di accessi a memoria che trovano il dato nel livello superiore sul numero totale di accessi
Hit Time (tempo di successo): tempo per accedere al dato nel livello superiore della gerarchia:
Tempo di accesso alla Tempo di accesso alla Tempo di accesso alla Tempo di accesso alla CACHECACHECACHECACHE + + + + tempo per tempo per tempo per tempo per determinare successo/fallimento della richiestadeterminare successo/fallimento della richiestadeterminare successo/fallimento della richiestadeterminare successo/fallimento della richiesta
49
Gerarchia di memoriaGerarchia di memoriaGerarchia di memoriaGerarchia di memoria: : : : definizionidefinizionidefinizionidefinizioni
�Miss (fallimento): i dati devono essere recuperati dal livello inferiore della memoria (Blocco Y)
Miss Rate (tasso di fallimento) = 1 - (Hit Rate)
Miss Penalty (tempo di fallimento): tempo per determinare il MISS + tempo necessario a sosituire un blocco nel livello superiore + tempo per trasferire il blocco al processore
tipicamente si ha: Hit Time << Miss Penalty
� Tempo medio di accesso in presenza di memoria cache: semplicemente la media pesata con le probabilità
HitTime*HitRate + MissRate*MissPenalty
50
CacheCacheCacheCache
� Memoria al livello superiore della gerarchia
� Sfruttare il principio di località dei programmi e tenere in memoria cache i dati utilizzati più di recente
� Obiettivo: fornire dati al processore in uno o due cicli di clock
� Memoria cache: veloce nei tempi di accesso ma di dimensioni ridotte
51
Cache e principio di localitCache e principio di localitCache e principio di localitCache e principio di localitàààà
� Le memorie cache sfruttano il principio di localitàspaziale trasferendo dal livello inferiore della gerarchia più dati di quanti non ne siano stati strettamente richiesti (blocco o linea di cache)
� La località temporale viene sfruttata nella scelta del blocco da sostituire nella gestione di un fallimento (es: sostituire il blocco a cui si è fatto accesso meno di recente)