Please enable JavaScript.
Coggle requires JavaScript to display documents.
Memoria di Massa - Coggle Diagram
Memoria di Massa
STRATEGIE SOSTITUZIONE
BLOCCHI
Casuale
NO efficienza
veloce da implementare
FIFO
First In First Out
strategia delle code
facile implementazione
località temporale non considerata
tiene conto del momento in cui ho trasferito il blocco
LFU
Least Frequently Used
sorta di coda con priorità
conto volte in cui ho accesso in un determinato blocco e sfruttare i least
più complesso da implementare
ultimi che entrano rischiano di uscire per primi
LRU
Least Recently Used
come una linked list
non si conta il numero di accessi ma il tempo di accesso
Strategia Marker
cerca di compensare difficoltà implementazione e efficienza
associa ad ogni blocco una booleana inizializzata False
se il programma accede ad un blocco già nella cache, mette il marker True
se il blocco non è nella cache, il programma ne sfratta uno marcato False
se tutti i blocchi in cache sono True, si resettano tutti a False
Tipi di Memoria
Livelli di Cache
capacità limitata
piuttosto veloci in
lettura e scrittura
Ram
più capiente
ma comunque limitata
memoria interna
della nostra macchina
Registri di Memoria
uniche su cui può
reagire il processore
capacità minime
Disk
arbitrariamente grande
LOCALITA' DEI RIFERIMENTI
sfruttate per velocizzare
le operazioni di massa
Temporale
se ho accesso tante volte ad alcune posizioni di memoria, è probabile che lo rifaccia in seguito
Spaziale
se accedo a determinate posizioni, è probabile che io acceda a quelle vicine
Come sfruttarle?
Memoria Virtuale
indirizzare uno spazio di memoria grande
trasferendo nella memoria di 1° livello
quelli nel secondo livello
Caching
trasferimento dati nella memoria
di primo livello
Blocking
traferire intero blocco informazioni...
Cache lines
blocchi scambiati tra cache e RAM
Pagine
blocchi scambiati tra RAM e memoria esterna
ANALISI COMPETITIVA
confronto algoritmi on line con algoritmi ottimi offline
algoritmi on line
risponde a sequenze di
richieste servizi non note a priori
algoritmo offline
richieste servizi note a priori
FIFO e LRU hanno rapporto
m competitivo
Strategia Marker competitivo O(log(m)) per una cahe con m blocchi
Dimensioni del
Blocco Trasferito
velocità aumenta dal disco alla CPU
diminuiscono dal disco alla CPU