Rationale for I/O Cache Structure
Goal: maintain K slots in memory as a cache over a collection of m items on secondary storage (K << m).
1. What happens on the first access to each item?
Fetch it into some slot of the cache, use it, and leave it there to speed up access if it is needed again later.
2. How to determine if an item is resident in the cache?
Maintain a directory of items in the cache: a hash table.
Hash on a unique identifier (tag) for the item (fully associative).
3. How to find a slot for an item fetched into the cache?
Choose an unused slot, or select an item to replace according to some policy, and evict it from the cache, freeing its slot.