并行与分布式系统中的分布式共享内存：全位向量目录协议（Full-Bit Vector Directory Protocol）算法 题目描述 在分布式共享内存（DSM）系统中，多个节点通过网络共享一个逻辑内存空间。全位向量目录协议是一种用于维护缓存一致性的分布式算法，它通过一个中心目录（或分布式目录）跟踪每个内存块在所有节点缓存中的状态。每个目录项包含一个位向量（bit vector），其中每一位对应系统中的一个节点，表示该节点是否缓存了对应的内存块。当某个节点需要读写内存块时，目录会根据位向量信息协调所有缓存副本的一致性（例如，在写操作前无效化其他节点的副本）。题目要求设计并分析这一协议的消息传递流程、状态转换及性能特征。 解题过程 问题建模 假设系统有 \(N\) 个节点，每个节点有本地缓存。内存被划分为块（blocks），每个块有一个主目录（可集中或分布式存储）。 目录项包含： 状态位 ：标识内存块当前状态（如未缓存、共享、独占）。 位向量 ：长度为 \(N\) 的二进制向量，位 \(i\) 为 1 表示节点 \(i\) 缓存了该块副本。 核心需求：确保多节点缓存同一内存块时，写操作对所有副本可见，读操作能获取最新数据。 协议状态设计 内存块有三种状态： UNCACHED ：无节点缓存该块。 SHARED ：一个或多个节点以只读方式缓存。 EXCLUSIVE ：仅一个节点以可写方式缓存。 节点缓存状态包括： VALID （可读）、 INVALID （无效）、 DIRTY （已修改且唯一）。 读操作流程 节点 \(P_ i\) 读块 \(B\) 时： 若本地缓存为 VALID 或 DIRTY ，直接读取。 否则，向目录发送读请求。 目录收到请求后： 若状态为 UNCACHED ：将块发送给 \(P_ i\)，位向量中置位 \(i\)，状态转为 SHARED 。 若状态为 SHARED ：将块发送给 \(P_ i\)，位向量中置位 \(i\)，状态保持 SHARED 。 若状态为 EXCLUSIVE 且位向量指向节点 \(P_ j\)： 向 \(P_ j\) 发送“降级”消息，要求将块状态改为 VALID 并返回数据。 目录收到数据后，发送给 \(P_ i\)，位向量中置位 \(i\) 和 \(j\)，状态转为 SHARED 。 写操作流程 节点 \(P_ i\) 写块 \(B\) 时： 若本地缓存为 DIRTY ，直接写入。 否则，向目录发送写请求。 目录收到请求后： 若状态为 UNCACHED ：将块发送给 \(P_ i\)，位向量中置位 \(i\)，状态转为 EXCLUSIVE 。 若状态为 SHARED ： 向位向量中所有其他节点（如 \(P_ j, P_ k, ...\)）发送“无效化”消息。 等待所有节点确认无效化后，将块发送给 \(P_ i\)，位向量中仅置位 \(i\)，状态转为 EXCLUSIVE 。 若状态为 EXCLUSIVE 且位向量指向 \(P_ j\)： 向 \(P_ j\) 发送“召回”消息，要求返回最新数据并无效化其副本。 目录收到数据后，发送给 \(P_ i\)，位向量中仅置位 \(i\)，状态保持 EXCLUSIVE 。 优化与性能分析 优点 ：目录精确跟踪缓存副本，无效化消息仅发送给必要节点，减少网络流量。 缺点 ：位向量大小与节点数 \(N\) 成正比，大规模系统下目录存储开销大（可改用稀疏目录或指针结构优化）。 消息复杂度 ：读操作需 \(O(1)\) 或 \(O(K)\) 消息（\(K\) 为共享节点数），写操作需 \(O(K)\) 消息。