Implementing a Basic Cache Coherence Protocol

In multi-processor systems, multiple CPUs might have their own local caches to speed up memory access. Cache coherence ensures that all processors have a consistent view of shared data, even when that data is modified in one of the caches. This challenge requires you to simulate a simplified cache coherence mechanism in Python.

Problem Description

You will implement a system that simulates multiple "processors," each with its own cache, accessing a shared "main memory." The goal is to maintain coherence between these caches and main memory when data is read and written. We will use a simplified "write-invalidate" protocol.

Key Requirements:

Cache Structure: Each processor will have a cache represented as a dictionary (or similar structure) mapping memory addresses to their cached values.
Main Memory: A shared dictionary will represent main memory, mapping memory addresses to their values.
Processor Operations: Implement functions for a processor to:
- read(address): Reads data from a given address. If the data is in the cache, return it. If not, fetch it from main memory, store it in the cache, and then return it.
- write(address, value): Writes a new value to a given address.
  - If the address is in the cache, update its value.
  - Crucially, before updating the cache and propagating the write, this operation must invalidate any other processor's cached copy of this address.
  - Finally, update the value in main memory.
Invalidation Mechanism: When a processor writes to an address, it must notify all other processors to "invalidate" their cached copy of that address. Invalidation means marking the cached entry as stale or removing it. For simplicity, we'll remove it.

Expected Behavior:

Reads should be fast if data is in the cache.
Writes should trigger an invalidation process for other caches.
After a write, subsequent reads by other processors for that address should result in a cache miss and a fetch from main memory.

Edge Cases:

Reading from an address not yet present in main memory or any cache.
Writing to an address not yet present in any cache.
Multiple processors writing to the same address concurrently (simulate sequentially in this challenge).

Examples

Example 1:

# Setup
memory = {}
processors = [Processor(0, memory, {}), Processor(1, memory, {})] # Processor 0 and 1

# Operation
processors[0].write(0x100, 42)
print(f"P0 Cache: {processors[0].cache}")
print(f"P1 Cache: {processors[1].cache}")
print(f"Memory: {memory}")

# Expected Output:
# P0 Cache: {0x100: 42}
# P1 Cache: {}
# Memory: {0x100: 42}

# Explanation: P0 writes 42 to address 0x100. This is added to P0's cache and main memory.
# P1's cache remains empty. No invalidation was needed for P1 as it didn't have the data.

Example 2:

# Setup (Continuing from Example 1)
processors[0].write(0x100, 42) # Assume this has already run

# Operation
value_at_0x100 = processors[1].read(0x100)
print(f"Value read by P1 at 0x100: {value_at_0x100}")
print(f"P0 Cache: {processors[0].cache}")
print(f"P1 Cache: {processors[1].cache}")
print(f"Memory: {memory}")

# Expected Output:
# Value read by P1 at 0x100: 42
# P0 Cache: {0x100: 42}
# P1 Cache: {0x100: 42}
# Memory: {0x100: 42}

# Explanation: P1 reads from 0x100. It's not in its cache, so it fetches from main memory (which has 42).
# The value is then cached in P1.

Example 3:

# Setup (Continuing from Example 2)
processors[0].write(0x100, 42) # Assume this has already run
processors[1].read(0x100)      # Assume this has already run, caching 42 in P1

# Operation
processors[0].write(0x100, 99) # P0 writes a new value
print(f"P0 Cache: {processors[0].cache}")
print(f"P1 Cache: {processors[1].cache}")
print(f"Memory: {memory}")

value_at_0x100_by_p1 = processors[1].read(0x100) # P1 reads again
print(f"Value read by P1 at 0x100 after P0 write: {value_at_0x100_by_p1}")
print(f"P1 Cache: {processors[1].cache}")

# Expected Output:
# P0 Cache: {0x100: 99}
# P1 Cache: {}
# Memory: {0x100: 99}
# Value read by P1 at 0x100 after P0 write: 99
# P1 Cache: {0x100: 99}

# Explanation:
# 1. P0 writes 99 to 0x100. This invalidates P1's cache entry for 0x100.
# 2. P0's cache is updated to {0x100: 99}.
# 3. Main memory is updated to {0x100: 99}.
# 4. P1 then attempts to read 0x100. Its cache entry was invalidated, so it's a cache miss.
# 5. P1 fetches the value (99) from main memory and caches it.

Constraints

The system will simulate at most 4 processors.
Memory addresses will be integers.
Values stored in memory and caches will be integers.
The total number of distinct memory addresses accessed will not exceed 100.
The simulation of concurrent operations will be done sequentially. You don't need to implement threading or actual concurrency.

Notes

You'll need to design a Processor class. This class should hold its own cache and have access to the shared memory and a way to communicate with other processors for invalidation.
Consider how to pass the "other processors" to a Processor instance so it can invalidate their caches.
The invalidation mechanism can be a simple method call on other Processor objects.
Think about how to represent the "invalidated" state. For this simplified model, removing the entry from the cache dictionary is sufficient.
You will need to implement the Processor class and the logic for read and write that incorporates cache lookup, main memory interaction, and the invalidation protocol.