11 CACHES Flashcards
What is the primary purpose of caches?
To alleviate high data access costs by storing data closer to the computation.
What do we mean when we say data is local?
Data is stored closer to the processor and thus quickly available for processing.
What is a cache hit?
When the requested data is found in the cache.
What is a cache miss?
When the requested data is not found in the cache.
What is the least recently used (LRU) cache strategy?
A caching strategy that stores recently used information and evicts the least recently used items when full.
What are the two main operations required for an LRU cache?
- Looking up an arbitrary element
- Finding the least recently used element for eviction
How does an LRU cache determine which data to evict?
By tracking which items have not been used recently and removing the oldest item when full.
What two data structures are used to implement an LRU cache?
- Hash table
- Queue
What does the cache structure typically contain in an LRU cache?
- Key
- Value
- Pointer to the corresponding node in the queue
What happens when the cache is full and a new item needs to be added?
The oldest item is evicted from the cache.
Fill in the blank: A cache is a step before accessing _______ data.
expensive
True or False: Caches can store all data without limitations.
False
What is the tradeoff involved in using a cache?
Memory used versus the speedup provided.
What does the term ‘eviction’ refer to in the context of caches?
The process of removing data from the cache to make space for new data.
What is a common caching strategy used in web browsers?
Caching commonly accessed data such as images or logos.
What type of data storage is the fastest but has limited capacity?
Memory on the CPU (registers or local caches).
What is the effect of using slower storage for larger cache sizes?
It can reduce the overall speed of data access.
How does the barista analogy relate to caching?
It illustrates the importance of storing popular items nearby to reduce retrieval time.
What happens to the cache when a cache hit occurs?
The data is accessed directly and its location is updated in the queue.
What is the role of the hash table in an LRU cache?
To perform fast lookups and store composite data structures.
What is the QueueListNode in the cache entry structure?
A pointer to the corresponding node in the queue.
What is an example of a caching strategy discussed in the chapter?
Least Recently Used (LRU) cache.
What is the primary purpose of a cache?
To alleviate access costs when dealing with expensive storage mediums.
What is the eviction strategy used in the cache discussed?
Least Recently Used (LRU) eviction strategy.
