制作人员许婷朱晓华白婧.ppt

制作人员：许婷 朱晓华 白婧,处理机的Cache一致性,Cache作为提高系统性能的一种常用手段在计算机系统中得到普遍的使用。但是，在多处理机中，不仅Cache同共享存储器中同一数据拷贝可能不一致，而且由于多个处理机异步地相互独立操作，也使多个Cache中同一份存储块的拷贝可能不一致，这就是Cache一致性问题。,问题提出,一、Cache一致性问题的原因,共享可写的数据 进程迁移 I/O传输,要解决多处理机的Cache一致性问题，首先要研究一致性问题的由来。出现不一致的原因有3个：,1.共享可写数据引起的不一致性,以拥有两个处理机的系统为例，处理机带有各自的私有Cache，并共享一个主存储器。,P1,X,P2,X,X,P1,X,P2,X,X,P1和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不一致。,P1,X,P2,X,X,X,若P1采用“写回”策略，即处理改写Cache中的数据时并不同时修改内存中相应的数据，而是在包含该数据的数据块调出Cache时才写回内存，那么，内存中的X还是X,导致C1中的X同内存中的X的不一致,2.进程迁移引起的不一致性,情况一：,P1,X,P2,X,若P1的进程对X进行了修改，使之变为X,X,采用“写回”策略，暂时没有对内存中的X进行修改。,由于某种原因，该进程迁移到了P2上运行,P2上的该进程运行时将从内存中读取X并将X调入C2,那么，这个迁移了的进程此时读取的是X，而不是它先前修改过的X。,X,P1的C1中有共享数据X的拷贝，而P2的C2中没有该共享数据,情况二：,以上两种情况都是由于进程迁移引起的数据不一致。,P1,X,P2,X,X,P1的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的拷贝,P1,P2,X,X,X,I/O,存储器,X,I/O处理机将一个新的数据X写入内存代替X,X,内存和Cache之间的数据不一致性。,P1,X,P2,X,X,I/O,存储器,处理机P1运行过程中修改了X的值，使之变为X,X,P1采用“写回”策略，那么，C1中的X同内存中的X是不一致的,若I/O处理机要求输出X，那么，内存就会将内存中的X的值传送给I/O处理机,X,传送给I/O处理机的将不是修改后的X,若C1和C2中都有X的拷贝,I/O传输引起数据不一致是因为处理机P1和P2共享I/O处理机，I/O传输发生在I/O处理机和内存之间。,把I/O处理机（IOP1和IOP2）分别连接到私有高速缓存C1和C2上，使处理机和I/O处理机共享高速缓存。这样，只要能保证各Cache之间以及Cache和内存之间的数据一致性，就能够保证I/O操作不会引起不一致。,一种解决I/O操作引起不一致的方法：,为了解决多处理机Cache一致性问题，提出了两类解决Cache一致性问题的协议机制：监听协议和基于目录的协议。,监听协议 基于目录的协议。,概述 采用写通过策略的Cache状态 采用写回策略的Cache状态 写一次协议,二、 监听协议,概述,监听协议通过总线监听机制实现高速缓存和共享存储器之间的数据一致性,监听协议的两种策略 写无效(Write-Invalidate)策略 写无效策略是在本地Cache的数据块修改时,使所有相应的远程数据块拷贝都无效 写更新(Write-Update)策略 写更新策略是在本地Cache的数据块修改时,通过总线把改写的数据块广播到含有该数据块拷贝的所有其他Cache,例子,Write-Update,监听协议分别采用写无效策略和写更新策略的区别,P1,P2,X,X,X,更新之前,X,X,P1将它的高速缓存C1中的X修改成X,Write-Invalidate,Cache的写通过策略同时将内存中的X也修改成X,I,写无效策略则将远程高速缓存C2中的X变成无效（无效数据块用I表示）,写更新策略将包含X1的新数据块通过总线广播到所有的高速缓存，更新其中的X为X1,X,数据块的两种状态:,采用写通过策略的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,Rr,Rr,Wr,R1 W1,Wr,写通过策略的Cache状态图,有效,无效,说明：,采用写回策略的Cache状态,Cache采用写回策略 Cache中的数据块被修改时不同时修改内存中相应的数据块拷贝，当Cache中的数据块被替换时，才将该数据块写回内存。 Cache中数据块的两种有效状态： 读/写状态 该数据块至少被修改过一次，尚未写回，内存中的相应数据块还没有被修改，在整个系统中只有一个数据块拷贝是正确的 只读状态整个系统中不止一个数据块拷贝是正确的,采用写回策略的Cache状态图,R1,W1,Rr,R1,W1,Wr,W1,Wr,Wr,Rr,R1,Rr,采用写回策略的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使其变为无效,写一次协议,特点是：为了减少总线流量，Cache的第一次写采取写通过策略，其后的写则采取写回策略 为了区分是否第一次写，协议把读-写状态分为两种状态：保留和重写,写一次协议的Cache中的数据块的4种状态 有效（Valid）：从内存读入的并与内存拷贝一致的Cache数据块是有效状态 无效（Invalid）：在Cache中找不到或Cache中的数据块内容已过时的块是无效状态 保留（Reserved）：若数据块从内存读入Cache后只被写过一次，且Cache中的拷贝与内存中的拷贝一致且正确，则是保留状态 重写（Dirty）：若Cache中的数据块不只一次被写过，且它是系统中唯一正确的数据块，则是重写状态,写一次协议的状态图,无效,有效,重写,保留,Rr,Wr,R1,W1,R1,Wr,W1 Rr,R1,Rr,W1,Rr,Wr,R1,W1,Wr,写一次协议的优缺点,优点是：第一次写采用写通过策略，以后的写操作都采用写回策略，由协议规定的状态，此时整个系统中只有本地Cache的数据块是唯一正确的拷贝，它的状态是重写状态。因此，减少了总线的无效操作，降低了总线的流量，提高了总线的效率 缺点是：当内存中的数据块无效时，读缺失引起的总线读操作必须禁止对内存的操作，而大多数总线不支持这种操作,基于目录的协议,基本思想：,使用Cache目录来存放有关数据块拷贝驻留在Cache中的信息，把使其他Cache数据块无效的一致性命令只发给存放有相应数据块的Cache，从而支持Cache的一致性。根据目录的结构特点，基于目录的协议可分为3类：全映射（full-map）目录、有限(limited)目录和链式（chained）目录。,全映射目录协议,有限目录协议,链式目录,全映射目录协议,2019/7/10,全映射目录协议规定共享存储器中的每个数据块都有由若干位组成的目录项，每个目录项中有一位重写位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块的有效位=1，允许写位=1，则可直接执行写操作。 若Cache块的有效位=0，则触发写缺失，需要从存储器调入 相应Cache块。,(3) 处理机读Cache块,若Cache块的有效位=1，则可直接执行读操作。 若Cache块的有效位=0，则触发读缺失，需要从存储器调入相应的Cache块。,举个例子吧,X,C - - - 数据,共享数据库,Cache,Cache,Cache,P1,P2,P3,1中系统中所有的Cache都没有数据块X的拷贝。,当3个处理机都对X有读请求之后，目录协议的状态如第二个图所示，X的目录项中3个处理机位都被置为1，表示3个Cache中都有X的拷贝。,X,C - - - 数据,共享数据库,Cache,Cache,Cache,P1,P2,P3,ReadX ReadX ReadX,Write,X,C 数据,共享数据库,Cache,Cache,Cache,P1,P2,P3,当处理机P3对X有写请求之后，目录协议的状态如第三个图所示，该状态表示P3获得了对X的写权利，此状态下，P3就可以写X了。,全映射目录协议的目录的存储器容量开销与处理机数目N的平方成正比。因为目录项的项数与处理机数N成正比，而目录项的大小又与N成正比，所以目录的存储器开销为O(N)。由于全映射目录项中的处理机位是同处理机一一对应的，增加处理机就要随之增加所有目录项的处理机位，所以全映射目录协议不具有可扩展性。,结论：,返回,有限目录协议,有限目录的目录项中，除一位的重写位C之外，有数目固定的若干处理机指针，每个指针实际上是一个处理机编号。若有N个处理机，则每个处理机指针为log2N位，因此，目录项的大小正比于Nlog2N，目录的存储器开销为O(Nlog2N)。当某个处理机从存储器调入一个Cache块时，就将该处理机编号记入该数据块目录项的一个指针域中，建立该指针。有N个指针域的目录项只能允许该数据块最多可装入N个Cache中。虽然目录项中指针域的数目是固定的，但指针域并不是与处理机是一一对应关系，任何一个指针域可为任何要求装入该数据块的处理机建立指针，因此，有限目录具有可扩展性。 需要指出的是，若某个目录项的所有指针域都已建立指针后，另有一个处理机要求装入该数据块，那么，有限目录协议需要对这个目录项实行指针替换，这种指针替换过程称为驱逐。,以目录项只有两个指针域为例说明驱逐,X,C 数据,共享数据库,Cache,Cache,Cache,P1,P2,P3,ReadX,P1和P2的Cache中都有X的拷贝,若P3请求X的拷贝，则协议必须在C1和C2中选择一个X拷贝使之无效，并用P3的指针替换无效X的指针。,链式目录,链式目录的优点在于既不限制共享数据块的拷贝数目，又保持了可扩展性。其主要方法是通过维护一个目录指针链来跟踪共享的数据块拷贝。,链式目录的目录指针链若采用最简单的单向链，那么，目录项中除一位重写位C之外，只需要一个指针域。因此，目录的存储器开销为O(Nlog2N)。,采用单向链的链式目录如下图所示。,X,C 数据,X Cache,CT,P1,P2,P3,共享存储器,P1是第一个读X的处理机,存储器送一份X拷贝给C1，并附加一个链结束标志