处理机的Cache一致性

主讲人：处理机的Cache一致性主要内容问题的提出一，多个cache不一致的原因二，如何解决Cache一致性问题2.1监听协议2.2基于目录的协议问题提出•Cache（高速缓冲存储器）：•它的设计是为了解决cpu与主存之间速度差距太大的矛盾；•Cache的工作原理是基于程序访问的局部性。cpu主存cache外存在多核和多处理器系统中，多个Cache对应的copy内容应该一致，如下图：MemoryCachecoreCachecore……Cachecore这几个copy应该一致一、多个Cache不一致的原因共享可写的数据进程迁移I/O传输要解决多处理机的Cache一致性问题，首先要研究一致性问题的由来。出现不一致的原因有3个：1.共享可写数据引起的不一致性以拥有两个处理机的系统为例，处理机带有各自的私有Cache，并共享一个主存储器。P1XP2XXP1XP2XXP1和P2的本地高速缓存存储器C1和C2中分别有共享主存的某个数据X的拷贝。P1改写C1中的X，使之变为X’。X’若P1采用“写通过”策略，即处理机改写Cache中的数据时同时修改内存中相应的数据，那么，内存中的X也同时变为X’，但是，处理机P2的本地高速缓冲存储器C2中的X仍然是X。X’当P2要读X时，它是从C2中去读取，这就导致了P2从C2中读取的X同内存中的X’不一致。P1XP2XX’X若P1采用“写回”策略，即处理改写Cache中的数据时并不同时修改内存中相应的数据，而是在包含该数据的数据块调出Cache时才写回内存，那么，内存中的X还是X导致C1中的X’同内存中的X的不一致2.进程迁移引起的不一致性情况一：P1XP2X若P1的进程对X进行了修改，使之变为X’X’采用“写回”策略，暂时没有对内存中的X进行修改。由于某种原因，该进程迁移到了P2上运行P2上的该进程运行时将从内存中读取X并将X调入C2那么，这个迁移了的进程此时读取的是X，而不是它先前修改过的X’。XP1的C1中有共享数据X的拷贝，而P2的C2中没有该共享数据情况二：以上两种情况都是由于进程迁移引起的数据不一致。P1XP2XXP1的C1和P2的C2中都有共享数据X的拷贝X’P2的进程修改了C2中的X，改变为X’并采用“写通过”策略，使内存中的X也修改为X’X’由于某种原因该进程迁移到P1上此时P1的C1中仍然是X，而不是它先修改过的X’。3.I/O传输引起的不一致性若P1的C1和P2的C2中都有共享数据X的拷贝P1P2XXXI/O存储器X’I/O处理机将一个新的数据X’写入内存代替XX’内存和Cache之间的数据不一致性。P1XP2XXI/O存储器处理机P1运行过程中修改了X的值，使之变为X’X’P1采用“写回”策略，那么，C1中的X’同内存中的X是不一致的若I/O处理机要求输出X，那么，内存就会将内存中的X的值传送给I/O处理机X传送给I/O处理机的将不是修改后的X’若C1和C2中都有X的拷贝二，如何解决Cache一致性问题为了解决多处理机Cache一致性问题，提出了两类解决Cache一致性问题的协议机制：监听协议和基于目录的协议。监听协议基于目录的协议。•概述•采用写通过策略的Cache状态•采用写回策略的Cache状态•写一次协议2.1，监听协议概述监听协议通过总线监听机制实现高速缓存和共享存储器之间的数据一致性监听协议的两种策略•写无效(Write-Invalidate)策略写无效策略是在本地Cache的数据块修改时,使所有相应的远程数据块拷贝都无效•写更新(Write-Update)策略写更新策略是在本地Cache的数据块修改时,通过总线把改写的数据块广播到含有该数据块拷贝的所有其他Cache监听协议的两种策略1.写无效（writeinvalidate）任一core写它的私有Cache时，它都使所有其它的Cache中的副本失效。–对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。–对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。2.写更新（writeupdate）任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。–对Write-through，它也更新主存储器中的副本。–对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。例子Write-Update监听协议分别采用写无效策略和写更新策略的区别P1P2XXX更新之前X’X’Write-InvalidateI写无效策略则将远程高速缓存C2中的X变成无效（无效数据块用I表示）写更新策略将包含X1的新数据块通过总线广播到所有的高速缓存，更新其中的X为X1X’数据块的两种状态:采用写通过策略的Cache状态•有效表示该数据块内容正确•无效表示该数据块内容已“过时”或不在本地Cache中处理机P1对本地高速缓存C1中数据块的读操作R1和写操作W1,以及其他处理机Pr对它的高速缓存Cr中同一数据块拷贝的读操作Rr和写操作Wr都可能引起高速缓存C1中该数据块的状态变化.状态转移图•对有效块的所有读操作R1，Rr之后，数据块仍然是有效块•P1对C1中的有效块X写操作W1，使C1中的X变为X1’•若P1对本地高速缓存C1中无效数据块读操作R1和写操作W1时，则将该数据块由无效转变为有效。但是，其他处理机Pr对自己的高速缓存Cr中数据块读操作Rr和写操作Wr时，C1中的无效数据块拷贝仍无效R1,W1,RrRr,WrR1W1Wr写通过策略的Cache状态图有效无效说明：采用写回策略的Cache状态•Cache采用写回策略Cache中的数据块被修改时不同时修改内存中相应的数据块拷贝，当Cache中的数据块被替换时，才将该数据块写回内存。•Cache中数据块的两种有效状态：读/写状态该数据块至少被修改过一次，尚未写回，内存中的相应数据块还没有被修改，在整个系统中只有一个数据块拷贝是正确的只读状态整个系统中不止一个数据块拷贝是正确的采用写回策略的Cache状态图R1,W1Rr,R1W1WrW1WrWr,RrR1Rr采用写回策略的Cache状态图读-写无效只读•P1对C1中的X读操作R1，C1仍为读-写状态•P1对C1中的X写操作W1，使X修改为X’，但此时X’未写回内存,C1的数据块X’状态仍为读/写状态•其他处理机Pr对自己的高速缓存Cr中的数据块拷贝X读操作Rr,C1数据块状态改为只读状态•Pr对Cr中的X写操作Wr，使Cr中的X修改为X1，且未写回内存,C1中的数据块X状态改为无效P1的本地高速缓存C1中的数据块X为读-写状态C1中的数据块X为只读状态•P1对C1中的X读操作R1，不会改变其状态，仍为只读状态•Pr对Cr中的X读操作Rr，不会改变C1中的X的只读状态•P1对C1中的X写操作W1，使X修改为X1，且未写回内存,系统中只有一个正确拷贝，即C1中刚修改的X1,C1中的数据块X1状态改为读-写状态•Pr对Cr中的X写操作Wr，使Cr中的X修改为X1，故而C1中的数据块拷贝X过时了，所以，C1中的数据块X状态改为无效C1中的数据块X为无效状态•P1对C1中的X读操作R1,C1中的数据块状态改为只读状态•P1对C1中的X写操作W1,使C1中的X修改为X1，但此时X1未写回内存,C1中的相应的数据块状态仍为无效•Pr对Cr中的数据块读操作Rr和写操作Wr，C1中的相应的数据块状态仍为无效采用写回策略的监听协议保持Cache一致性的方法•当内存拥有一个数据块时，每个高速缓存只有该数据块的只读状态的拷贝，有拷贝的本地处理机P1和远程处理机Pr都可以安全地读这份拷贝,本地的写操作W1使其拷贝变为读/写状态，远程的写操作Wr使本地高速缓存的拷贝变为无效状态•如果某个Cache中的某个数据块处于有效状态（读-写或只读），则远程写操作Wr，使该Cache中的这个数据块变为无效•系统中可能拥有一份处于读/写状态的数据块拷贝。对于处于读-写状态的数据块，本地的读/写操作（R1和W1）都是安全的，远程读操作Rr使其变为只读状态，远程写操作Wr使其变为无效两种策略的缺点1，写无效的问题–主要开销在两个方面：–（1）作废各Cache副本的开销；–（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。后果：–如果一个Core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。2，写更新的问题•由于更新时，所有的副本均需要更新，开销很大。写一次协议•特点是：为了减少总线流量，Cache的第一次写采取写通过策略，其后的写则采取写回策略•为了区分是否第一次写，协议把读-写状态分为两种状态：保留和重写写一次协议的Cache中的数据块的4种状态•有效（Valid）：从内存读入的并与内存拷贝一致的Cache数据块是有效状态•无效（Invalid）：在Cache中找不到或Cache中的数据块内容已过时的块是无效状态•保留（Reserved）：若数据块从内存读入Cache后只被写过一次，且Cache中的拷贝与内存中的拷贝一致且正确，则是保留状态•重写（Dirty）：若Cache中的数据块不只一次被写过，且它是系统中唯一正确的数据块，则是重写状态写一次协议的状态图无效有效重写保留Rr,WrR1,W1R1WrW1RrR1,RrW1RrWrR1W1Wr写一次协议的优缺点•优点是：第一次写采用写通过策略，以后的写操作都采用写回策略，由协议规定的状态，此时整个系统中只有本地Cache的数据块是唯一正确的拷贝，它的状态是重写状态。因此，减少了总线的无效操作，降低了总线的流量，提高了总线的效率•缺点是：当内存中的数据块无效时，读缺失引起的总线读操作必须禁止对内存的操作，而大多数总线不支持这种操作基本思想：使用Cache目录来存放有关数据块拷贝驻留在Cache中的信息，把使其他Cache数据块无效的一致性命令只发给存放有相应数据块的Cache，从而支持Cache的一致性。根据目录的结构特点，基于目录的协议可分为3类：全映射（full-map）目录、有限(limited)目录和链式（chained）目录。I.全映射目录协议II.有限目录协议III.链式目录2.2，基于目录的协议全映射目录协议2020/1/18全映射目录协议规定共享存储器中的每个数据块都有由若干位组成的目录项，每个目录项中有一位重写位C和N个处理机位。1.若重写位C=1，则表示该数据块已重写；2.若C=0，则表示该数据块未被重写。N个处理机位分别表示对应N个处理机的Cache中是否有该数据块的拷贝，若某个处理机位=1，则表示对应的处理机Cache中有该数据块拷贝。?全映射目录协议是怎样保持Cache一致性的。(1)处理机从存储器调入Cache块(2)处理机写Cache块第1步使该数据块目录项的重写位C=1，相应处理机位=1。第2步使调入Cache的数据块的有效位=1，允许写位=0。①若Cache块的有效位=1，允许写位=0，那么，执行下述过程：第1步Cache向存储器模块发出写请求，并暂停处理机的工作；第2步存储器根据该数据块目录项中N位处理机位的值，向那些处理位=1的相应Cache发出无效请求，使相应Cache中的该块拷贝的有效位=0，并发回答信号给存储器；第3步存储器收到回答信号后，使该块目录项的重写位C=1，并置其他处理机位=0，发允许写信号给相应Cache；第4步Cache收到允许写信号后，使该块允许写位=1，并激活处理机执行暂停的写操作。可见，对Cache块写操作时，系统根据Cache块目录项提供的指针将所有其他有相同内容的数据块拷贝置为无效来保持Cache的一致性。②若Cache块的