Cache Replacement Policies: LRU, FIFO, and Randomized Strategies Quiz Quiz

Explore key concepts of cache replacement policies, including LRU, FIFO, and randomized strategies, to sharpen your understanding of memory management algorithms and their performance implications. This quiz covers practical scenarios and essential characteristics relevant to computer architecture and caching systems.

1. Identifying LRU Policy

   Which cache replacement policy evicts the data that has not been used for the longest period of time?

   1. LRU
   2. Randomized
   3. MRU
   4. FIFO

   Explanation: LRU stands for Least Recently Used and removes the entry that hasn't been accessed in the longest time. FIFO (First In, First Out) always removes the oldest entry regardless of usage. Randomized chooses any entry at random, and MRU (Most Recently Used) removes the item accessed most recently instead, which is different from LRU.

2. Understanding FIFO Policy

   If a cache uses the policy of removing the item that was loaded earliest, regardless of whether it was used recently, which policy is this?

   1. LRU
   2. LFU
   3. FIFO
   4. Randomized

   Explanation: FIFO, or First In, First Out, evicts the item that has been in the cache the longest without considering its usage. LRU looks at the least recently used data, LFU (Least Frequently Used) chooses the least used, and Randomized does not follow a fixed order.

3. Choosing the Best Policy for Predictable Access Patterns

   Which cache replacement strategy often works best when data is accessed in loops with predictable patterns?

   1. LFU
   2. Randomized
   3. FIFO
   4. LRU

   Explanation: LRU tends to perform efficiently with repeated and predictable access patterns, as it retains recently used data. FIFO ignores access frequency and order after insertion, Randomized is unpredictable and not tailored for access patterns, and LFU focuses on usage count, which is different from recency.

4. Impact of Randomized Policy

   What is the main characteristic of a randomized cache replacement policy?

   1. Always removes the least accessed item
   2. Removes the item accessed most recently
   3. Evicts items in the order they entered
   4. Selects an item to replace at random

   Explanation: A randomized policy picks any cache block for replacement regardless of recency or frequency, which provides simplicity but less predictability. Removing the least accessed item is LFU, FIFO removes in entry order, and MRU removes the most recently used, none of which occur randomly.

5. Replacement Policy Behavior Example

   If you insert three items A, B, and C into a cache and then insert D, which replacement policy will remove A if no items were accessed again?

   1. Randomized
   2. LRU
   3. LFU
   4. FIFO

   Explanation: With FIFO, the first inserted item (A) is removed since it was the earliest loaded, regardless of how often it was used. Randomized could remove any, LFU would need frequency information, and LRU removes the least recently used, but since none were accessed again, both FIFO and LRU could be correct, but FIFO is the most specific based on insertion order.

6. Application of Randomized Replacement

   Why might a caching system use a randomized replacement policy instead of LRU or FIFO?

   1. Always gives higher cache hit rates
   2. Requires more tracking information
   3. Ensures items stay longest in cache
   4. Reduces implementation complexity

   Explanation: Randomized replacement is simple and requires little overhead, making it attractive for hardware with limited resources. It does not guarantee higher hit rates, nor does it ensure data persistence. In fact, it requires less, not more, tracking information compared to policies like LRU.

7. Unique Aspect of LRU

   What special information must a cache track to implement the LRU policy correctly?

   1. Insertion time
   2. Access frequency
   3. Random number
   4. Access recency

   Explanation: LRU requires tracking of the most recent access times for each cache item, making it possible to evict the least recently accessed. Insertion time is used in FIFO, frequency is for LFU, and random numbers are used for randomized replacement, not LRU.

8. FIFO vs LRU in Sequential Access Patterns

   During a sequential scan of data much larger than the cache, which policy is likely to perform similarly to FIFO in terms of cache misses?

   1. MRU
   2. LRU
   3. Randomized
   4. LFU

   Explanation: In long sequential scans, both FIFO and LRU tend to experience cache misses at similar rates because items are accessed only once before eviction. LFU depends on frequency, which is low for all, Randomized provides unpredictable results, and MRU behaves differently, sometimes causing even worse performance.

9. Eviction Decision in LRU Policy

   If a cache using LRU contains entries P, Q, R, S and P was the last accessed, which will be replaced next on a miss?

   1. S
   2. Q
   3. R
   4. P

   Explanation: In LRU, the item not accessed for the longest period is evicted, which is Q if all others have been accessed more recently. P is least likely as it was just accessed, while R and S are more recent than Q. This distinguishes LRU’s focus on recency from FIFO or other policies.

10. Cache Replacement Policy Overhead

    Which cache replacement policy typically requires the least amount of internal bookkeeping or tracking?

    1. FIFO
    2. LFU
    3. LRU
    4. Randomized

    Explanation: Randomized replacement only needs to select a slot randomly and does not track timing or usage data, minimizing overhead. FIFO needs a queue for insertion order, LRU tracks access history, and LFU tracks access counts, all of which increase complexity compared to Randomized.