Storage 3: Multi-slot caches and mmap

Overview

In this lecture, we describe cache issues that arise for multi-slot caches and memory-mapped caches.

Full lecture notes on storage — Textbook readings

Multi-slot caches

• The stdio cache is a single-slot cache
  • Still quite effective for many workloads!
• Many real caches have more than one slot
  • Processor cache, buffer cache, …

Diagramming a multi-slot cache

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

Examples

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

More examples

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 flushed
  • Write modified data to underlying storage

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
  • ./w-stdiobyterev vs. ./r-stdiobyterev

Memory mapping

• mmap system call
• r-mmapbyte, w-mmapbyte

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

• program | program