One cache slot can cache one contiguous range of addresses
For multiple contiguous ranges of addresses, need a multi-slot cache
Examples?
Processor cache! Many non-contiguous ranges of interesting addresses,
including the most recent stack frame for local variables, part of the
heap for active dynamic objects, and part of the text segment for
instructions.
Multi-slot caches introduce interesting questions
Which cache slot should an access use?
Multi-slot cache abstraction
Many aspects of multi-slot cache design are independent of addresses and the
type of underlying data
Abstract these away into a reference string
A list of addresses, each representing one access
Multi-slot cache diagram: reference string on top, each slot is a row
Column gives a snapshot of the cache’s contents after that access
1
2
3
4
1
2
5
1
2
3
4
5
A
①
1
1
④
4
4
⑤
5
5
5
5
5
B
②
2
2
①
1
1
1
1
③
3
3
C
③
3
3
②
2
2
2
2
④
4
FIFO, 3 slots, hit rate 3/12
Associativity
Some caches have limitations on which slot can be used for an underlying
address
Direct-mapped cache
An address A can fit in exactly one slot S(A)
Fully associative cache
Any address can fit in any slot
Software must choose a slot
Set-associative cache
An address A can fit in one of a set of slots SS(A)
Covers other two as special cases
Eviction
Freeing a slot for reuse is called eviction
An eviction policy chooses which slot to evict
For instance, if new data needs to be cached
Direct-mapped caches have a trivial eviction policy
A good eviction policy gets rid of data that isn’t needed in the near future
Hits and misses
A hit is an access that can use data already in the cache
A miss is an access that cannot use data already in the cache
A read miss requires filling the cache from underlying storage
A write miss may require flushing data from the cache to underlying storage
Both kinds of miss may require eviction
The hit rate is the percentage of accesses that are hits
Eviction policies for fully-associative caches
When a slot is needed, evict the slot that:
FIFO (First In, First Out)
…was least recently filled (or assigned)
Are there others?
Eviction policies for fully-associative caches
When a slot is needed, evict the slot that:
FIFO (First In, First Out)
…was least recently filled (or assigned)
LIFO (Last In, First Out)
…was most recently filled
LRU (Least Recently Used)
…was least recently used
MRU (Most Recently Used)
…was most recently used
LFU (Least Frequently Used)
…was used least often
Priority, aging, …
Question
Can you come up with reference strings that work well for each of those
policies?
The optimal eviction algorithm
When a slot is needed, evict the slot that:
Bélády’s Optimal Algorithm
…contains the data that will be used farthest in the future
Example
1
2
3
4
1
2
5
1
2
3
4
5
A
①
B
②
C
③
Optimal
1
2
3
4
1
2
5
1
2
3
4
5
A
①
1
1
③
B
②
2
2
④
C
③
④
⑤
5
Optimal, 3 slots, hit rate 5/12
When can you predict the future?
More slots means better hit rate!
1
2
3
4
1
2
5
1
2
3
4
5
A
①
④
⑤
5
B
②
①
1
③
C
③
②
2
④
FIFO, 3 slots, hit rate 3/12
1
2
3
4
1
2
5
1
2
3
4
5
A
①
B
②
C
③
D
④
FIFO, 4 slots, hit rate ?
1
2
3
4
1
2
5
1
2
3
4
5
A
①
1
⑤
④
B
②
2
①
⑤
C
③
②
D
④
③
FIFO, 4 slots, hit rate 2/12
Well, maybe not.
This is called Bélády’s anomaly
More slots means better hit rate for LRU
1
2
3
4
1
2
5
1
2
3
4
5
A
①
④
⑤
③
B
②
①
1
④
C
③
②
2
⑤
LRU, 3 slots, hit rate 2/12
1
2
3
4
1
2
5
1
2
3
4
5
A
①
1
1
⑤
B
②
2
2
C
③
⑤
④
D
④
③
LRU, 4 slots, hit rate 4/12
Eviction and writes
A write cache may have dirty slots
A dirty slot contains data newer than underlying storage
To evict a dirty slot, it must be written first
Write modified data to underlying storage
Sometimes called “flush”
Streams vs. random-access files
The Unix file descriptor abstraction models many sources of data as file
descriptors
Unix’s big idea: Everything is a file
But not all sources of data are the same
Compare a stone tablet and a speech
Random-access file
Has a file position
Seekable
Usually mappable
Finite
Example: Files on drives
Stream
Does not have a file position
Not seekable (lseek returns -1)
Not mappable
Possibly infinite
Example: Typed characters, program output
Special files
/dev/null: Contains nothing
Any read returns end of file
Any write succeeds
/dev/urandom: Contains random data
Any read returns random bytes
/dev/zero: Contains zero bytes
Any read returns all zeros
Streams
program1 | program2
Network connections
Write semantics
Always safe to read more data than requested
Not necessarily safe to write more data than requested!
Safe with coherent caches, not safe with incoherent caches