《计算机软件及应用处理机的Cache一致性课件》由会员分享，可在线阅读，更多相关《计算机软件及应用处理机的Cache一致性课件（35页珍藏版）》请在金锄头文库上搜索。
1、处理机的处理机的Cache一致性一致性计算机软件及应用处理机的Cache一致性主要内容问题的提出一，多个cache不一致的原因二，如何解决Cache一致性问题 2.1 监听协议 2.2 基于目录的协议计算机软件及应用处理机的Cache一致性问题提出Cache（高速缓冲存储器）：它的设计是为了解决cpu与主存之间速度差距太大的矛盾；Cache的工作原理是基于程序访问的局部性。 cpu主存cache外存计算机软件及应用处理机的Cache一致性在多核和多处理器系统中，多个Cache对应的copy内容应该一致，如下图：MemoryCachecoreCachecoreCachecore这几个copy应该
2、一致计算机软件及应用处理机的Cache一致性一、多个一、多个Cache不一致的原因不一致的原因 共享可写的数据 进程迁移 I/O传输 要解决多处理机的Cache一致性问题，首先要研究一致性问题的由来。出现不一致的原因有3个：计算机软件及应用处理机的Cache一致性1.共享可写数据共享可写数据引起的不一致性引起的不一致性 以拥有两个处理机的系统为例，处理机带有各自的私有Cache，并共享一个主存储器。P1XP2XX计算机软件及应用处理机的Cache一致性P1XP2XX P1和P2的本地高速缓存存储器C1和C2中分别有共享主存的某个数据X的拷贝。P1改写C1中的X，使之变为X。X 若P1采用“写通
3、过”策略，即处理机改写Cache中的数据时同时修改内存中相应的数据，那么，内存中的X也同时变为X，但是，处理机P2的本地高速缓冲存储器C2中的X仍然是X。X 当P2要读X时，它是从C2中去读取，这就导致了P2从C2中读取的X同内存中的X不一致。计算机软件及应用处理机的Cache一致性P1XP2XXX 若P1采用“写回”策略，即处理改写Cache中的数据时并不同时修改内存中相应的数据，而是在包含该数据的数据块调出Cache时才写回内存，那么，内存中的X还是X 导致C1中的X同内存中的X的不一致计算机软件及应用处理机的Cache一致性2.进程迁移进程迁移引起的不一致性引起的不一致性 情况一：情况一
4、：情况一：情况一：P1XP2X若P1的进程对X进行了修改，使之变为XX采用“写回”策略，暂时没有对内存中的X进行修改。由于某种原因，该进程迁移到了P2上运行P2上的该进程运行时将从内存中读取X并将X调入C2那么，这个迁移了的进程此时读取的是X，而不是它先前修改过的X。X P1的C1中有共享数据X的拷贝，而P2的C2中没有该共享数据计算机软件及应用处理机的Cache一致性情况二：情况二：情况二：情况二：以上两种情况都是由于进程迁移引起的数据不一致。P1XP2XXP1的C1和P2的C2中都有共享数据X的拷贝XP2的进程修改了C2中的X，改变为X并采用“写通过”策略，使内存中的X也修改为XX 由于某
5、种原因该进程迁移到P1上此时P1的C1中仍然是X，而不是它先修改过的X。计算机软件及应用处理机的Cache一致性3. I/O传输传输引起的不一致性引起的不一致性 若P1的C1和P2的C2中都有共享数据X的拷贝P1P2XXXI/O存储器XI/O处理机将一个新的数据X写入内存代替XX内存和Cache之间的数据不一致性。计算机软件及应用处理机的Cache一致性P1XP2XXI/O存储器处理机P1运行过程中修改了X的值，使之变为XXP1采用“写回”策略，那么，C1中的X同内存中的X是不一致的若I/O处理机要求输出X，那么，内存就会将内存中的X的值传送给I/O处理机X传送给I/O处理机的将不是修改后的X
6、若C1和C2中都有X的拷贝计算机软件及应用处理机的Cache一致性 二，如何解决Cache一致性问题为了解决多处理机Cache一致性问题，提出了两类解决Cache一致性问题的协议机制：监听协议和基于目录的协议。 监听协议 基于目录的协议。计算机软件及应用处理机的Cache一致性概述采用写通过策略的Cache状态采用写回策略的Cache状态写一次协议2.1，监听协议计算机软件及应用处理机的Cache一致性概述 监听协议通过总线监听机制实现高速缓存和共享存储器之间的数据一致性 监听协议的两种策略 写无效(Write-Invalidate)策略 写无效策略是在本地Cache的数据块修改时,使所有相应
7、的远程数据块拷贝都无效 写更新(Write-Update)策略 写更新策略是在本地Cache的数据块修改时,通过总线把改写的数据块广播到含有该数据块拷贝的所有其他Cache 计算机软件及应用处理机的Cache一致性监听协议的两种策略1.写无效（write invalidate） 任一core写它的私有Cache时，它都使所有其它的Cache中的副本失效。对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。计算机软件及应用处理机的
8、Cache一致性2.写更新（write update）任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。对Write-through，它也更新主存储器中的副本。对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。计算机软件及应用处理机的Cache一致性例子Write-Update监听协议分别采用写无效策略和写更新策略的区别 P1P2XXX更新之前XXP1将它的高速缓存C1中的X修改成X Write-InvalidateCache的写通过策略同时将内存中的X也修改成X I写无效策略则将远程高速缓存C2中的X变成无效（无效数据块用I表示） 写更新
9、策略将包含X1的新数据块通过总线广播到所有的高速缓存，更新其中的X为X1 X计算机软件及应用处理机的Cache一致性数据块的两种状态:采用写通过策略的Cache状态 有效 表示该数据块内容正确 无效 表示该数据块内容已“过时”或不在本地Cache中 处理机P1对本地高速缓存C1中数据块的读操作R1和写操作W1,以及其他处理机Pr对它的高速缓存Cr中同一数据块拷贝的读操作Rr和写操作Wr都可能引起高速缓存C1中该数据块的状态变化.状态转移图计算机软件及应用处理机的Cache一致性对有效块的所有读操作R1，Rr之后，数据块仍然是有效块 P1对C1中的有效块X写操作W1，使C1中的X变为X1若P1对
10、本地高速缓存C1中无效数据块读操作R1和写操作W1时，则将该数据块由无效转变为有效。但是，其他处理机Pr对自己的高速缓存Cr中数据块读操作Rr和写操作Wr时，C1中的无效数据块拷贝仍无效 R1,W1,RrRr,WrR1 W1Wr写通过策略的Cache状态图有效无效说明：计算机软件及应用处理机的Cache一致性采用写回策略的Cache状态 Cache采用写回策略 Cache中的数据块被修改时不同时修改内存中相应的数据块拷贝，当Cache中的数据块被替换时，才将该数据块写回内存。 Cache中数据块的两种有效状态： 读/写状态 该数据块至少被修改过一次，尚未写回，内存中的相应数据块还没有被修改，在
11、整个系统中只有一个数据块拷贝是正确的 只读状态整个系统中不止一个数据块拷贝是正确的 采用写回策略的Cache状态图计算机软件及应用处理机的Cache一致性采用写回策略的监听协议保持Cache一致性的方法 当内存拥有一个数据块时，每个高速缓存只有该数据块的只读状态的拷贝，有拷贝的本地处理机P1和远程处理机Pr都可以安全地读这份拷贝,本地的写操作W1使其拷贝变为读/写状态，远程的写操作Wr使本地高速缓存的拷贝变为无效状态 如果某个Cache中的某个数据块处于有效状态（读-写或只读），则远程写操作Wr，使该Cache中的这个数据块变为无效 系统中可能拥有一份处于读/写状态的数据块拷贝。对于处于读-写
12、状态的数据块，本地的读/写操作（R1和W1）都是安全的，远程读操作Rr使其变为只读状态，远程写操作Wr使其变为无效 计算机软件及应用处理机的Cache一致性两种策略的缺点1，写无效的问题主要开销在两个方面：（1）作废各Cache副本的开销；（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。后果：如果一个Core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比
13、较大时，这种颠簸现象更为严重。计算机软件及应用处理机的Cache一致性2，写更新的问题由于更新时，所有的副本均需要更新，开销很大。计算机软件及应用处理机的Cache一致性写一次协议特点是：为了减少总线流量，Cache的第一次写采取写通过策略，其后的写则采取写回策略 为了区分是否第一次写，协议把读-写状态分为两种状态：保留和重写 写一次协议的Cache中的数据块的4种状态 有效（Valid）：从内存读入的并与内存拷贝一致的Cache数据块是有效状态 无效（Invalid）：在Cache中找不到或Cache中的数据块内容已过时的块是无效状态 保留（Reserved）：若数据块从内存读入Cache后
14、只被写过一次，且Cache中的拷贝与内存中的拷贝一致且正确，则是保留状态 重写（Dirty）：若Cache中的数据块不只一次被写过，且它是系统中唯一正确的数据块，则是重写状态 计算机软件及应用处理机的Cache一致性写一次协议的状态图无效有效重写保留Rr,WrR1,W1R1WrW1 Rr R1,RrW1RrWrR1W1Wr计算机软件及应用处理机的Cache一致性写一次协议的优缺点 优点是：第一次写采用写通过策略，以后的写操作都采用写回策略，由协议规定的状态，此时整个系统中只有本地Cache的数据块是唯一正确的拷贝，它的状态是重写状态。因此，减少了总线的无效操作，降低了总线的流量，提高了总线的效
15、率 缺点是：当内存中的数据块无效时，读缺失引起的总线读操作必须禁止对内存的操作，而大多数总线不支持这种操作 计算机软件及应用处理机的Cache一致性基本思想： 使用Cache目录来存放有关数据块拷贝驻留在Cache中的信息，把使其他Cache数据块无效的一致性命令只发给存放有相应数据块的Cache，从而支持Cache的一致性。根据目录的结构特点，基于目录的协议可分为3类：全映射（full-map）目录、有限(limited)目录和链式（chained）目录。I.全映射目录协议II.有限目录协议III. 链式目录 2.2，基于目录的协议计算机软件及应用处理机的Cache一致性 全映射目录协议20
16、24/7/19 全映射目录协议规定共享存储器中的每个数据块都有由若干位组成的目录项，每个目录项中有一位重写位C和N个处理机位。 1.若重写位C=1，则表示该数据块已重写； 2.若C=0，则表示该数据块未被重写。 N个处理机位分别表示对应N个处理机的Cache中是否有该数据块的拷贝，若某个处理机位=1，则表示对应的处理机Cache中有该数据块拷贝。? 全映射目录协议是怎样保持Cache一致性的。计算机软件及应用处理机的Cache一致性若Cache块的有效位=1，允许写位=1，则可直接执行写操作。若Cache块的有效位=0，则触发写缺失，需要从存储器调入相应Cache块。 (3) 处理机读Cach
17、e块若Cache块的有效位=1，则可直接执行读操作。 若Cache块的有效位=0，则触发读缺失，需要从存储器调入相应的Cache块。 计算机软件及应用处理机的Cache一致性 有限目录协议 有限目录的目录项中，除一位的重写位C之外，有数目固定的若干处理机指针，每个指针实际上是一个处理机编号。若有N个处理机，则每个处理机指针为log2N位，因此，目录项的大小正比于Nlog2N，目录的存储器开销为O(Nlog2N)。当某个处理机从存储器调入一个Cache块时，就将该处理机编号记入该数据块目录项的一个指针域中，建立该指针。有N个指针域的目录项只能允许该数据块最多可装入N个Cache中。虽然目录项中指
18、针域的数目是固定的，但指针域并不是与处理机是一一对应关系，任何一个指针域可为任何要求装入该数据块的处理机建立指针，因此，有限目录具有可扩展性。 需要指出的是，若某个目录项的所有指针域都已建立指针后，另有一个处理机要求装入该数据块，那么，有限目录协议需要对这个目录项实行指针替换，这种指针替换过程称为驱逐。 以目录项只有两个指针域为例说明驱逐 计算机软件及应用处理机的Cache一致性链式目录链式目录的优点在于既不限制共享数据块的拷贝数目，又保持了可扩展性。其主要方法是通过维护一个目录指针链来跟踪共享的数据块拷贝。 链式目录的目录指针链若采用最简单的单向链，那么，目录项中除一位重写位C之外，只需要一
19、个指针域。因此，目录的存储器开销为O(Nlog2N)。采用单向链的链式目录如下图所示。 计算机软件及应用处理机的Cache一致性链式目录协议与前两种的异同：链式目录协议与前两种的异同： 链式目录协议保持Cache一致性的操作类似全映射目录协议，只是当处理机Pi 写Ci中的X时，Ci向存储器发出写请求后，存储器将沿X的目录链发送无效信号，将链上的其他X拷贝置为无效，由链尾的有结束标志（CT）的处理机发回答信号给存储器，使X的目录项重写位C置位，此后，存储器才给处理机Pi写允许权。 链式目录协议具有可扩展性，目录的存储器开销也低于前述的两种目录协议的存储器开销。但是，当Cache中的数据块需要替换
20、时，需要把该Cache的被替换块从它的目录链中卸下来并保持目录链的连通。可行的解决办法是：沿着链发送一个消息，修改Ci+1中相应数据块X的指针，使之指向Ci-1，从而把Ci中的数据块X从目录链中卸下，此时就可对Ci的X进行替换了。 计算机软件及应用处理机的Cache一致性本节小结 基于目录的协议是使用目录来维护Cache的一致性。若一个处理机对Cache块写操作时，系统根据目录的指针把其他有相同内容的Cache块拷贝置为无效，并置重写位为“重写”。若处理机对Cache块读操作时，如果重写位未置位，则说明该块未经重写。此时，若Cache读缺失，则从存储器中或拥有正确内容的Cache中读入该块拷贝并修改目录；若读命中，则直接读即可。 计算机软件及应用处理机的Cache一致性谢谢大家！计算机软件及应用处理机的Cache一致性
