4 链式目录

　　链式目录的优点在于即不限制共享数据块的拷贝数目，又保持了可扩展性。其主要方法是通过维护一个目录指针链来跟踪共享数据拷贝。
　　链式目录有两种实现方法。其中比较简单的一种是单链法，图8.21是单链法的工作原理。

　　假设没有单元X的共享拷贝，如果处理机要读单元X，则存储器送一份拷贝给，同时送给一个链结束指针（CT），存储器也保存一个指向的指针。之后，当处理机P2读单元X时，存储器送一份拷贝给，同时送给一个指向的指针。存储器则保存一个指向的指针。当某一个处理机需要写X时，它必须沿这个目录链发送一个数据无效信息。在有链结束指针的处理机没有回答无效信号之前，存储器模块不给该处理机写允许权。
　　与另外两种协议不同，链式目录协议存在一个新的问题。当Cache的数据块需要替换时，需要把该Cache从目录链中"卸"下来。这里就涉及链中某一项的删除问题。有两种解决这个问题的办法：
　　1、沿着链发送一个消息，使得Ci+1的指针指向Ci-1，把Ci从链中去掉。这时Ci中存放别的数据块了。
　　2、使Ci及在链中位于其后的所有Cache中的单元X无效。
　　解决替换问题的另一种方法是使用双向链。即每个Cache目录项都有向前链和向后链两个指针。这样在执行替换时就不再需要遍历整个链。虽然双向链优化了替换操作 ，但是其指针增加了一倍，占用了更多的资源，一致性协议也更复杂了。
　　链式目录的复杂程度超过了前两种目录。但是链式目录具有前两种目录所不具有的一个重要特性：可扩展性。其指针的大小以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。