并行与分布式系统中的分布式共享内存：目录一致性协议（Directory-Based Protocol） 题目描述 在分布式共享内存（DSM）系统中，多个节点通过网络共享一块逻辑内存空间，但物理内存分散在各节点上。目录一致性协议是一种保证数据一致性的核心方法，它通过一个中央目录（或分布式目录）跟踪每个内存块的状态和位置。本题要求设计一个基础的目录协议，处理多节点对同一内存块的读写请求，确保所有节点看到的数据是一致的。 解题过程 问题分析 目标：在无共享物理内存的分布式系统中，实现类似共享内存的编程模型。 挑战：当多个节点并发读写同一内存块时，需避免数据冲突（如节点A读到旧值，而节点B已更新数据）。 核心思路：通过目录记录每个内存块的 状态 （如共享、独占、未缓存）和 持有者列表 （哪些节点缓存了该块），在读写操作前协调节点。 基础概念定义 内存块 ：共享内存的最小单位，每个块有唯一标识。 目录条目 ：每个内存块对应一个目录条目，包含： 状态 ：包括 UNCACHED （无节点缓存）、 SHARED （多个节点只读缓存）、 EXCLUSIVE （仅一个节点可写缓存）。 持有者列表 ：缓存此块的节点ID集合。 所有者 ：当状态为 EXCLUSIVE 时，记录唯一持有该块的节点。 协议设计步骤 步骤1：处理读请求 场景：节点A请求读取块X。 过程： A向目录发送 Read_Miss 消息。 目录检查X的状态： 若为 UNCACHED ：将状态改为 SHARED ，将A加入持有者列表，从主存加载数据发送给A。 若为 SHARED ：将A加入持有者列表，直接返回数据。 若为 EXCLUSIVE ：向当前所有者节点B发送 Invalidate 消息，B将数据写回主存并清空缓存，目录将状态改为 SHARED ，将A和B加入持有者列表，数据返回给A。 步骤2：处理写请求 场景：节点A请求写入块X。 过程： A向目录发送 Write_Miss 消息。 目录检查X的状态： 若为 UNCACHED ：将状态改为 EXCLUSIVE ，设置A为所有者，数据发送给A。 若为 SHARED 或 EXCLUSIVE ：向所有持有者发送 Invalidate 消息（若为 EXCLUSIVE 还需先写回数据），清空持有者列表，将状态改为 EXCLUSIVE ，设置A为所有者，数据发送给A。 步骤3：优化与容错 减量目录 ：为节省存储，可用指针结构代替全节点列表（如有限向量或二叉树）。 分布式目录 ：将目录分片到不同节点，避免单点瓶颈（如AMD的HyperTransport协议）。 一致性验证示例 初始：块X在目录中状态为 UNCACHED 。 节点A读X：目录状态变为 SHARED ，持有者列表为{A}。 节点B写X：目录向A发送 Invalidate ，状态变为 EXCLUSIVE ，所有者变为B。 节点C读X：目录向B索要数据并转发给C，状态变为 SHARED ，持有者列表为{B,C}。 总结 目录协议通过集中式协调（或分布式分片）解决了DSM的数据一致性问题，其核心是 状态机转换 与 消息协调 。实际系统（如斯坦福DASH）会在此基础上增加缓存策略、网络优化等扩展。