并行与分布式系统中的分布式共享内存：基于目录的缓存一致性协议（Directory-Based Cache Coherence Protocol）

题目描述
在共享内存的多处理器系统中，每个处理器拥有本地缓存。当多个处理器并行访问同一内存块时，可能出现缓存不一致问题（例如：处理器P1修改了数据，但P2的缓存中仍是旧值）。基于目录的协议通过维护一个中央目录来跟踪每个内存块的状态及其缓存副本的分布，确保数据一致性。问题要求设计一个支持“读/写操作”的目录协议，并处理以下场景：

1. 处理器请求读数据，但数据未被缓存或已被其他处理器修改；
2. 处理器请求写数据，但其他处理器可能持有该数据的副本。

解题过程循序渐进讲解

步骤1: 定义内存块状态与目录结构

• 每个内存块在目录中有三种状态：
  • UNCACHED: 无处理器缓存该块。
  • SHARED: 一个或多个处理器以只读方式缓存该块。
  • EXCLUSIVE: 仅一个处理器以可写方式缓存该块（独占修改权）。
• 目录为每个内存块维护一个位向量（bit vector），每位对应一个处理器，标记其是否缓存该块。
• 额外字段记录当前独占所有者（若有）。

示例：假设系统有4个处理器（P0–P3），内存块M的目录条目初始为：

• 状态: UNCACHED
• 位向量: [0, 0, 0, 0]
• 所有者: NULL

步骤2: 处理读请求（Read Miss）
若处理器Pᵢ请求读取内存块M：

1. 检查目录状态：
   • 若状态为UNCACHED：
     • 将数据从内存发送给Pᵢ。
     • 更新目录：状态→SHARED，位向量中设置Pᵢ的位为1。
   • 若状态为SHARED：
     • 直接发送数据给Pᵢ（其他处理器可能有副本）。
     • 更新位向量，标记Pᵢ已缓存。
   • 若状态为EXCLUSIVE：
     • 向当前所有者Pⱼ发送“无效化请求”（Invalidate），强制其将数据写回内存。
     • 更新目录：状态→SHARED，清除Pⱼ的独占权，位向量中设置Pᵢ和Pⱼ的位为1。
     • 将最新数据发送给Pᵢ。

示例：

• 初始状态：M处于UNCACHED。
• P1读M → 目录发送数据，状态变为SHARED，位向量=[0,1,0,0]。
• P2读M → 目录直接发送数据，位向量更新为[0,1,1,0]。

步骤3: 处理写请求（Write Miss）
若处理器Pᵢ请求写入内存块M：

1. 检查目录状态：
   • 若状态为UNCACHED：
     • 将数据发送给Pᵢ，并授予独占权。
     • 更新目录：状态→EXCLUSIVE，所有者=Pᵢ，位向量中设置Pᵢ的位为1。
   • 若状态为SHARED：
     • 向所有缓存副本的处理器发送“无效化消息”（Invalidation），使其本地副本失效。
     • 等待所有处理器确认无效化后，将数据发送给Pᵢ。
     • 更新目录：状态→EXCLUSIVE，所有者=Pᵢ，位向量中仅Pᵢ的位为1。
   • 若状态为EXCLUSIVE且所有者不是Pᵢ：
     • 向当前所有者Pⱼ发送“写回请求”（Write-Back），强制其将数据写回内存。
     • 然后将数据发送给Pᵢ，并转移独占权。
     • 目录所有者更新为Pᵢ，位向量相应调整。

示例：

• 当前状态：M处于SHARED，位向量=[0,1,1,0]（P1、P2缓存）。
• P3写M → 目录向P1、P2发送无效化消息，等待确认后授予P3独占权。
• 更新目录：状态→EXCLUSIVE，所有者=P3，位向量=[0,0,0,1]。

步骤4: 处理写回与替换
当处理器需要逐出缓存块时（如缓存满）：

• 若处理器Pᵢ缓存的块处于EXCLUSIVE状态且被修改过：
  • Pᵢ必须将数据写回内存，并通知目录。
  • 目录更新状态为UNCACHED，清除位向量和所有者。
• 若块处于SHARED状态：直接逐出，无需写回（因未修改），但需通知目录清除位向量中Pᵢ的位。

步骤5: 协议优化与扩展

• 减少消息数：目录可记录共享者数量而非完整位向量（但需维护列表以支持无效化）。
• 可扩展性：大型系统中目录可分层或分布式部署（如链式目录）。
• 容错：通过冗余目录或日志应对目录服务器故障。

总结
基于目录的协议通过集中式状态管理，以额外存储开销换取较低的网络流量（相比广播式协议）。关键点在于通过目录协调所有缓存操作，确保读写冲突时通过无效化/写回机制维持一致性。