Cache 一致性协议
按照学习手册最后的模拟。
\(\text{Exclusive} / \text{Shared}\) 只有编号最小的返回，但都要改变状态。
\(\text{Modified}\) 的所有的都要返回且改变状态。
Cache 替换算法
这里说一下 \(\text{PLRU}\) 算法。
对于每次，先找是否命中。
如果是否，就在二叉搜索树上找到叶子更改。
不论是否命中，最终都要根据叶子向上跳，把祖先的边不指向指定叶子。
标签：THUWC,指向,题解,Cache,Day3,Invalid,2020,text From： https://www.cnblogs.com/Nazq/p/18667108不会出现存在 \(\text{Invalid}\) 却替换的情况。
若存在 \(\text{Invalid}\)，根节点会指向 \(\text{Invalid}\) 多的一边，儿子会指向 \(\text{Invalid}\)。
这样递归下去指向 \(\text{Invalid}\)。