Multi-Level Cache Simulator

Simulation Caching Lru

Problem Description

You are tasked with simulating a two-level cache system that mimics real-world caching behavior. The system consists of an L1 and an L2 cache, both of which use the Least Recently Used (LRU) eviction policy. Your job is to process a sequence of data requests and keep track of cache hits and misses.

How the Cache System Works:

  1. Cache Structure:

    • The system has two caches: L1 and L2. Each cache has a fixed capacity provided as input (L1_capacity and L2_capacity).

  2. Processing a Request:

    • Step 1: Check if the requested data item is in the L1 cache.
      • If it is, record a hit and update its position in L1 according to the LRU policy.
    • Step 2: If the item is not in L1, check the L2 cache.
      • If found in L2, record a hit. Then, promote the item to L1 (inserting it in L1 using LRU), and remove it from L2 if necessary.
    • Step 3: If the item is in neither cache, record a miss. Retrieve the item from main memory.
      • Insert this new item into L2 (using LRU) and then promote it to L1.

  3. Eviction Policy:

    • Both caches follow the LRU (Least Recently Used) strategy. When a cache reaches its capacity, the least recently used item in that cache should be evicted to make room for a new item.

Input:

  • Two integers representing the capacities of the L1 and L2 caches, respectively.
  • A sequence of data requests (each request can be represented by an identifier, such as a string or an integer).

Output:

After processing all requests, your program should output:

  • The total number of cache hits and cache misses.
  • The final state of the L1 cache and the L2 cache. The state should show the order of cached items from most recently used to least recently used.

Example Format:

Input:
L1_capacity = 3
L2_capacity = 5
Requests = [A, B, C, A, D, E, B, F, G, A]

Output:
Hits: <number_of_hits>
Misses: <number_of_misses>
L1 Cache: [most_recent_item, ..., least_recent_item]
L2 Cache: [most_recent_item, ..., least_recent_item]

Constraints:

  • The sequence of requests may be large (e.g., up to 10^4 requests), so your solution should be efficient.
  • The capacities of the caches are less than or equal to the number of unique items in the requests.

Develop your solution using any programming language of your choice. Be sure to simulate the caching process accurately according to the specifications above.