1、多核对操作系统的影响多核对操作系统的影响(1) Cache一致性一致性outlinelCache Coherence问题lCache Coherence的提出l多个Cache不一致的原因l两种设计Cache一致性协议策略l监听总线协议l基于目录的Cache一致性协议l三种Cache一致性策略2Cache Coherence问题问题lCache Coherence问题的提出l在多核和多处理器系统中，多个Cache对应的copy内容应该一致：MemoryCachecoreCachecoreCachecore这几个copy应该一致3多个多个Cache不一致的原因不一致的原因l共享可写数据的不一致性l
2、进程迁移的不一致性lI/O操作（绕过Cache的I/O操作）4l共享可写数据的不一致性（sharing of writable data）core1core2更新前xxx核Cachesharedmemorycore1core2写通过xxxcore1core2写回xxxCache和内存时刻保持一致5l进程迁移的不一致性core1core2迁移前xx核Cachecore1core2写通过xxxcore1core2写回xxx6lI/O操作（绕过Cache的I/O操作）core1core2xx存储器core1core2写通过xxcore1core2写回xxxxxxxI/O存储器输入存储器输出c1c2总
3、线7两种设计两种设计Cache一致性协议策略一致性协议策略l写无效（写无效（write invalidate）l任一core写它的私有Cache时，它都使所有其它的Cache中的副本失效。l对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。l对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。8两种设计两种设计Cache一致性协议策略一致性协议策略l写更新（写更新（write update）l任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。l对Wri
4、te-through，它也更新主存储器中的副本。l对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。9 下图表示数据块x在共享存储器和三个核的Cache中的副本一致的情形。x共享存储器CacheP1xP2xxP3总线核10l下图表示core1进行写无效操作后的情形。l写通过：xI表示无效core1Icore2xIcore3共享存储器Cache总线核11l写回：xI表示无效core1Icore2IIcore3共享存储器Cache总线核12l下图表示core1进行写更新操作后的情形（写通过）。xI表示无效core1xcore2xxcore3共享存储器Cache总线核13
5、l写无效的问题写无效的问题l主要开销在两个方面：（1）作废各Cache副本的开销；（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。14l写无效后果：写无效后果：l如果一个Core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。l如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。15l写更新的问题写更新的问题l由于更新时，所有的副本均需要更新，开销很大。16outlinelCa
6、che Coherence问题lCache Coherence的提出l多个Cache不一致的原因l两种设计Cache一致性协议策略l监听总线协议l写一次协议l基于目录的Cache一致性协议l三种Cache一致性策略17监听总线协议监听总线协议(Snoopy protocol)l通过总线监听机制实现Cache和共享存储器之间的一致性。l适用性分析：l适用于具有广播能力的总线结构多Core系统，允许每个Core监听其它Core的存储器访问情况。l只适用于小规模的多Core系统。18l写一次写一次(write-once)协议协议l写无效监听一致性协议，将写通过和写回策略结合。l为了减少总线流量，高速
7、缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。19l一致性协议的内容包括一致性协议的内容包括l l（1）Cache可能出现的状态集合l（2）共享主存的状态l（3）为维护一致性而引起的状态转换。20l每份Cache中的副本可能出现的四种状态 l（1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。l（2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本
8、一致。l（3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。l（4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。21l局部命令（Local commands） l（1）P-Read：本地处理机读自己的Cache副本。l（2）P-Write：本地处理机写自己的Cache副本。22l一致性命令一致性命令l（1）Read-blk：从另一Cache读一份有效的副本。l（2）Write-inv：在写命中时在总
9、线上广播一个无效命令。l（3）Read-inv：在写缺失时在总线上广播一个无效命令。23lDirty: modified more than once, the only copy in the system;lInvalid: inconsistent copy;lReserved: after written once, the only copy consistent with memory;lValid: A copy consistent with the memory copy.lWrite-Once一致性协议状态转移图一致性协议状态转移图l其中，四种状态的含义如下：24Inval
10、idValidDirtyReservedRead-inv(4)P-Write(1)P-Write(hit:local still dirty)P-Write(hit:local, not memoryupdate, local copy becomes dirty)P-Write(hit:local,updatememory copy,broadcastwrite-inv to all cache,local copybecomesreserved)Read-blk(3)Read-inv(4)P-Read(2)Read-blk(3)Read-inv(4)/Write-inv(5)P-Read(
11、hit:alwayslocal,no statetransition)25P-Write(1)(1)P-Write(miss: take a dirty copy from a remote cache, or from memory; send Read-inv to invalidate all copies; update local copy into a dirty one).InvalidValidDirtyReserved26InvalidValidDirtyReserved(2)P-Read(miss: if no dirty copy exists, memory suppl
12、ies a validcopy, otherwise, the cache inhibits memory and supplies a copyand updates memory. Both copies become valid).P-Read(2)27InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)28InvalidValidDirtyReserved(3)Read-blk(read from remote processor
13、s, the localcopy become valid).Read-blk(3)29InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)30lWrite-Once一致性协议状态转移表必是局部进行，不影响有效状态第一次写命中，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextstatestatus
14、P-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次写命中，用写回法。但不修改主存的副本P-Write保留重写Write-hit31写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留 Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit32写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrents
15、tatenextstatestatusP-Write无效保留 Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit33commandcurrentstatenextstatestatusactionl（续表）读缺失时,如远程Cache中没有重写副本，则主存中一定有一份正确的副本，供给发请求的Cache。如远程的Cache有重写的副本，则它禁止主存操作，并将副本发给请求的Cache，两种情况均使发请求的Cache得到的副本为有效。P-Read无效有效 Read-miss34远程Cache读此副本，读后两份副本均有效Rea
16、d-blk保留或重写有效commandcurrentstatenextstatestatusactionl（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效35写命中时，一远程Cache修改其本地副本，并使数据块的其它副本无效Write-inv有效无效commandcurrentstatenextstatestatusactionl（续表）如果副本处于重写状态，必须通过块替换写回主存，否则不产生替换操作Write-inv有效无效替代36l一个具体的例子一个具体的例子l如下图的系统：MemoryC1Core1C2Core2C3Core337l读的情况：l（1）如果C1为Valid，读C1，则Read hit，状态不变。l（2）如果C1为Reserved，读C1，则Read hit，状态不变。l（3）如果C1为Dirty，读C1，则Read hit，状态不变。l（4）如果C1为Invalid，C2和C3没有东西，则读C1时Read miss，这时只有memory中有正确的副本，把它取到C1，C1改为Valid（P-R
