Cache Coherence Simulation in Python

Cache coherence is a critical problem in multi-processor systems where multiple processors share access to the same memory locations. This challenge asks you to simulate a simplified cache coherence protocol (Write-Invalidate) in Python to understand the fundamental concepts. You'll model multiple processors, a shared memory, and their individual caches, and ensure data consistency when multiple processors access and modify the same memory locations.

Problem Description

You are tasked with implementing a simplified Write-Invalidate cache coherence protocol for a system with multiple processors and a shared memory. Each processor has its own private cache. When a processor writes to a memory location, all other caches containing that location must be invalidated. The simulation should track the state of each cache line (Modified, Exclusive, Shared, Invalid) and handle read and write requests from processors, ensuring data consistency.

What needs to be achieved:

Model a shared memory space with a fixed size.
Model multiple processors, each with a private cache of a fixed size.
Implement a Write-Invalidate cache coherence protocol.
Simulate processor read and write requests to memory.
Maintain the state of each cache line (M, E, S, I).
Ensure data consistency across all caches and memory.

Key Requirements:

Cache Line States: Implement the four standard cache line states:
- Modified (M): The cache line is present only in this cache and has been modified. It is the only valid copy.
- Exclusive (E): The cache line is present only in this cache and is clean (matches memory).
- Shared (S): The cache line is present in this cache and potentially in other caches. It matches memory.
- Invalid (I): The cache line is invalid and does not contain valid data.
Write-Invalidate Protocol: When a processor writes to a cache line, all other caches containing that line must invalidate their copies.
Read and Write Operations: Simulate processor read and write requests. Reads should retrieve data from the cache if present and valid; otherwise, fetch from memory. Writes should update the cache and invalidate other caches.
Memory Consistency: Ensure that memory always holds the most up-to-date value when necessary.

Expected Behavior:

The simulation should accurately reflect the Write-Invalidate protocol. When a processor writes to a memory location, all other caches containing that location should have their corresponding cache lines marked as Invalid. Subsequent reads from those caches should fetch the data from memory (or the cache of the processor that modified it).

Edge Cases to Consider:

Cache Misses: Handle cases where a processor requests data that is not present in its cache (cache miss).
Multiple Processors Writing: Consider scenarios where multiple processors attempt to write to the same memory location concurrently (though true concurrency isn't required in this simulation, the logic should handle it correctly).
Cache Full: Handle the case where a cache is full and needs to evict a line to make space for a new one. (For simplicity, you can assume the cache is large enough to always accommodate new lines in this challenge).
Boundary Conditions: Ensure the simulation handles memory addresses and cache line indices correctly, especially at the boundaries of the memory and cache spaces.

Examples

Example 1:

Input:
memory_size = 16
cache_size = 4
num_processors = 2
memory = [0] * memory_size
cache1 = [[4, 'I'] for _ in range(cache_size)] # Cache line (address, state)
cache2 = [[4, 'I'] for _ in range(cache_size)]

processor1_writes = [(0, 10), (4, 20)]
processor2_writes = [(0, 5)]

Output:
memory[0] == 5
cache1[0][1] == 'S' #Processor 1 reads memory[0] after processor 2 writes
cache2[0][1] == 'M' #Processor 2 writes to memory[0]

Explanation: Processor 2 writes to memory[0]. Cache1, which previously had an invalid copy, now has a shared copy. Cache2 has the modified copy. Processor 1 then reads memory[0], resulting in a shared copy in Cache1.

Example 2:

Input:
memory_size = 8
cache_size = 2
num_processors = 2
memory = [0] * memory_size
cache1 = [[0, 'I'], [1, 'I']]
cache2 = [[0, 'I'], [1, 'I']]

processor1_writes = [(0, 10)]
processor2_reads = [(0,)]

Output:
memory[0] == 10
cache1[0][1] == 'M'
cache2[0][1] == 'I'

Explanation: Processor 1 writes to memory[0], invalidating the copy in Cache2.

Example 3: (Edge Case - Multiple Writes)

Input:
memory_size = 4
cache_size = 2
num_processors = 2
memory = [0] * memory_size
cache1 = [[0, 'I'], [1, 'I']]
cache2 = [[0, 'I'], [1, 'I']]

processor1_writes = [(0, 10)]
processor2_writes = [(0, 20)]

Output:
memory[0] == 20
cache1[0][1] == 'I'
cache2[0][1] == 'M'

Explanation: Processor 1 writes 10 to memory[0]. Processor 2 then writes 20 to memory[0], invalidating Processor 1's copy and making Processor 2's copy the modified copy.

Constraints

memory_size: Must be between 8 and 64 (inclusive).
cache_size: Must be between 2 and 8 (inclusive).
num_processors: Must be between 2 and 4 (inclusive).
Memory and cache addresses are integers.
The simulation should complete within a reasonable time (e.g., less than 1 second) for the given constraints.

Notes

Focus on correctly implementing the Write-Invalidate protocol.
You can simplify the simulation by assuming a single-core processor and not handling true concurrency. The order of operations is important.
Consider using dictionaries or lists to represent the memory and caches.
Think about how to efficiently update the cache states based on read and write requests.
The provided examples are meant to guide you, but you should test your implementation with various scenarios to ensure correctness.
Error handling (e.g., invalid memory addresses) is not required for this challenge.