Compare write-back vs write-through caches

Compare write-back and write-through caching policies. Explain how each handles writes, coherence, durability, latency, and bandwidth; discuss typical use in CPU caches vs storage systems and the trade-offs (e.g., dirty bits, write amplification, and risk on power loss).

Cache Policy Simulator: Write-Back vs Write-Through

You are given a fully associative cache with LRU replacement and write-allocate on write misses. Each operation is a tuple like ('R', address) or ('W', address), where each address represents one whole cache block. Simulate both write-through and write-back policies and compare their trade-offs.

Rules:

• Every cache access costs 1 unit of latency.
• A miss must fetch the block from memory, adding read_cost latency.
• A write sent to memory adds write_cost latency and counts as one memory write.
• Write-through: every write updates memory immediately. Cache lines are always clean.
• Write-back: writes only mark the cached block dirty. Memory is updated only when a dirty block is evicted.
• On eviction, remove the least recently used block.
• Do not flush the write-back cache at the end. Instead, report how many dirty lines remain; these represent data still vulnerable to power loss.

Return a dictionary with metrics for both policies. The memory_writes value acts as a proxy for bandwidth and coherence-visible traffic.

Constraints

• 1 <= capacity <= 10^5
• 0 <= len(operations) <= 2 * 10^5
• Each operation is ('R', address) or ('W', address)
• 1 <= read_cost, write_cost <= 10^9
• Expected solution should run in O(n) time with O(capacity) extra space

Examples

Example 1

Input: (2, [], 5, 10)
Output: {'write_through': {'latency': 0, 'memory_writes': 0}, 'write_back': {'latency': 0, 'memory_writes': 0, 'dirty_lines': 0}}

Explanation: No operations means no latency, no memory writes, and no dirty lines.

Example 2

Input: (2, [('W', 1), ('W', 1)], 5, 10)
Output: {'write_through': {'latency': 27, 'memory_writes': 2}, 'write_back': {'latency': 7, 'memory_writes': 0, 'dirty_lines': 1}}

Explanation: Write-through writes to memory on both writes. Write-back loads block 1 once, then keeps it dirty in cache with no memory write yet.

Hints

1. Use a hash map plus an order-aware structure so you can test membership, update recency, and evict the LRU block in O(1) average time.
2. Both simulators share most of their logic. The key differences are what happens on a write hit and whether a dirty block generates a memory write when evicted.