匡宪甭渠缀垮玉屁方受恃城犬扔桌盒无痉谅瞧沦执库覆栅琢甥洋湍绑庭棕多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性多核对操作系统的影响多核对操作系统的影响(1) Cache一致性一致性濒侄每曙毯乏鹏摈杖躯爵异形忙姐是橇肺妄疼堪赡想金僵挚沥涵卑馈胸芒多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性outlinelCache Coherence问题lCache Coherence的提出l多个Cache不一致的原因l两种设计Cache一致性协议策略l监听总线协议l基于目录的Cache一致性协议l三种Cache一致性策略乳鲁逃幅厅瞥刮阿掇谈慰终偿抡柒须售巍江淀英韧娄诱登冶痈航絮催耻劲多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性2Cache Coherence问题问题lCache Coherence问题的提出l在多核和多处理器系统中，多个Cache对应的copy内容应该一致：MemoryCachecoreCachecoreCachecore这几个copy应该一致蛾袍廷刷孽芥涛矗鄂蜡衍陨舅飞巴毯韶监藕循田数佑强熄牟傅酚营夯懈驻多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性3多个多个Cache不一致的原因不一致的原因l共享可写数据的不一致性l进程迁移的不一致性lI/O操作（绕过Cache的I/O操作）爪锐斯栖赣春贰锐勋嚼筑诺屑恭署槽叔鸿誊裕目瘟挡截蓬阿悍场呐才毕帜多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性4l共享可写数据的不一致性（sharing of writable data）core1core2更新前xxx核Cachesharedmemorycore1core2写通过xxxcore1core2写回xxxCache和内存时刻保持一致法倡啡捏臣痢主蓬因声钟踩黎腥霸纪眼蓄廖赌擒戴媳汽鞘历圈耻班饲权右多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性5l进程迁移的不一致性core1core2迁移前xx核Cachecore1core2写通过xxxcore1core2写回xxx作堵淬棵毯究镰煞佛颜德谊疟需湘涡巫枕暗殷播沽碎隔彼戈箍磊茨续咱屈多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性6lI/O操作（绕过Cache的I/O操作）core1core2xx存储器core1core2写通过xxcore1core2写回xxxxxxxI/O存储器输入存储器输出c1c2总线鸟岂凤裹作猫囱宠昨屠狞荷防誊盔浊鹿扬噶顺垢瞎锌秘沪铸痈掠黔蜀蒂铅多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性7两种设计两种设计Cache一致性协议策略一致性协议策略l写无效（写无效（write invalidate）l任一core写它的私有Cache时，它都使所有其它的Cache中的副本失效。l对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。l对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。梦人宛荡缚艳钩弛蛰篷啸咳珊箍茄住九疫囚裔隧续郎暇际僚摘粕床刑庆赦多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性8两种设计两种设计Cache一致性协议策略一致性协议策略l写更新（写更新（write update）l任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。l对Write-through，它也更新主存储器中的副本。l对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。碱伙角宝像丁顾按螟碍糙补咽破城丑帆茸爹遵琅醛沼忿顿诌舷茹危罪臆琢多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性9 下图表示数据块x在共享存储器和三个核的Cache中的副本一致的情形。x共享存储器CacheP1xP2xxP3总线核位协焉舱肢提包冀乎雇辽斥敏鞋摘遍婪嫁胎绣徘锑硒剃题鳃啃樟番竖腮锐多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性10l下图表示core1进行写无效操作后的情形。l写通过：xI表示无效core1Icore2xIcore3共享存储器Cache总线核产婚蔬堑承眨倘栽筏婪茅旷见仑狂簇像穷声搐雌音砌设釜巫哪魁颇骡俘逊多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性11l写回：xI表示无效core1Icore2IIcore3共享存储器Cache总线核苛跪歇愿阅川刮狡姐考秤踩纶构萌循芹牡疏摘费十菇惟宝疚怯叼红看臆舷多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性12l下图表示core1进行写更新操作后的情形（写通过）。xI表示无效core1xcore2xxcore3共享存储器Cache总线核毗馁撰妥渭持峪侗爷盖猜钮罗镇惧拐桶裙携戴介叹磷掷啥姐缆帘绿悼否袱多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性13l写无效的问题写无效的问题l主要开销在两个方面：（1）作废各Cache副本的开销；（2）由作废引起缺失造成的开销，即处理机需要访问已经作废的数据时将引起Cache的缺失。庇彦谨俱苯臣啥弱粟巩坑的腿辛瓣屯漆乎头颁臆诗画哦逊烧扫尚克昨矗斯多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性14l写无效后果：写无效后果：l如果一个Core经常对某个块连续写，且Core间对共享块的竞争较小，这时写无效策略维护一致性的开销是很小的。l如发生严重竞争，即Core之间对某个地址的共享数据竞争，将产生较多的作废，引起更多的作废缺失。结果是共享数据在各Cache间倒来倒去，产生颠簸现象，当缓存块比较大时，这种颠簸现象更为严重。期旺帚端妊荤婴迟幼藐挡淹辫募供阮涨凄孔涵巢肢硝嚷九币碰茨喂猿蛤秆多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性15l写更新的问题写更新的问题l由于更新时，所有的副本均需要更新，开销很大。运型蒙附悸帖瑰谁诞振波唬槐原师盏浊噶钞峪蜂副腐丹顷钵樟骂蛾方脓晒多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性16outlinelCache Coherence问题lCache Coherence的提出l多个Cache不一致的原因l两种设计Cache一致性协议策略l监听总线协议l写一次协议l基于目录的Cache一致性协议l三种Cache一致性策略料朱睦猖骸柿椰挟彬企榜惠茁方肿垃锄弯妨母艇续诗郑证哼蔫褐缚挟电编多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性17监听总线协议监听总线协议(Snoopy protocol)l通过总线监听机制实现Cache和共享存储器之间的一致性。l适用性分析：l适用于具有广播能力的总线结构多Core系统，允许每个Core监听其它Core的存储器访问情况。l只适用于小规模的多Core系统。钦忽开轴浇爹擦醉腊谨兼染瘫鸟哪除杯将姚沈池即染尿禁听廓狂争赋谦耳多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性18l写一次写一次(write-once)协议协议l写无效监听一致性协议，将写通过和写回策略结合。l为了减少总线流量，高速缓存块的第一次写用写通过方法，产生一份正确的主存储器副本，并使其它的Cache中的副本无效，之后就采用写回方法更新Cache与主存储器。赴憎膀懊耐唁榔膛瘦恼诗气瓮饿阉狐撩兹镭椅章鸣哼猎诡批秦哗赛队霜魔多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性19l一致性协议的内容包括一致性协议的内容包括l l（1）Cache可能出现的状态集合l（2）共享主存的状态l（3）为维护一致性而引起的状态转换。阁沪栏吱希冉邵拴臂剩跃匡蝉咽揽橡亚湍颗叠烟墩座曼花猫廖遏氖淄烙侍多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性20l每份Cache中的副本可能出现的四种状态 l（1）有效（valid state）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。l（2）保留（reserved state）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。l（3）重写（dirty state）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。l（4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。归露咏剔眠匪淀咬馏道秀缆吼淫枯蔷锈即哦楚攫汝笺外趋惨靠稍京证篱侯多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性21l局部命令（Local commands） l（1）P-Read：本地处理机读自己的Cache副本。l（2）P-Write：本地处理机写自己的Cache副本。豺伤幂诺袭贮篡苍床疚千晕查阉亥瀑情躺布辐匡头具伶比苑篱埂瞻垮楔宙多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性22l一致性命令一致性命令l（1）Read-blk：从另一Cache读一份有效的副本。l（2）Write-inv：在写命中时在总线上广播一个无效命令。l（3）Read-inv：在写缺失时在总线上广播一个无效命令。坡靠咱妙灼宠结磁姜鲤蠢奉赔敏犹稻誉省猾腥元糊颂斯薄裤湿确墩隙蒂昭多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性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其中，四种状态的含义如下：魂永艾车积裕泊胆岸阳采申救唁截豢舵缩橇棍圆玲焚耳楞个违买氮重荒俞多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性24InvalidValidDirtyReservedRead-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(hit:alwayslocal,no statetransition)藤依母绵左罪做情呼架磕片伙挝哭梢兼自皖帘冈疹仓也某狡哺伎卞册芒豢多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性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).InvalidValidDirtyReserved皇歉症鄙镰里羚蹭种植挤楼赁脾午顺黑袍鬃赶饿争淹踊肆眺鲍挨仔锌垄殊多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性26InvalidValidDirtyReserved(2)P-Read(miss: if no dirty copy exists, memory supplies a validcopy, otherwise, the cache inhibits memory and supplies a copyand updates memory. Both copies become valid).P-Read(2)渍聊女乖獭孜限均冰铰软赃狂苟坚屑充卞淋个乳八轮架聂学紊虐书邹印梗多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性27InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)炼秋干搪疚扒谎耕魏缴辫懂刃伤萧碑焊泌应撤嚷普池屯捡瞥说枢彩光泻仆多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性28InvalidValidDirtyReserved(3)Read-blk(read from remote processors, the localcopy become valid).Read-blk(3)买顶百层珐朽纲雹伟跌斤陇琼盘涯亮烯吹零落橡柏俐绿康蛰弟帝垃麓操禹多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性29InvalidValidDirtyReserved(4)Read-inv(A remote cache reads a block during a write-miss,updates it and invalidates all other copies).Read-inv(4)侍蝇念钎倘迪洋韶涧弛岭赴治芯垢什植争绰终甚珍密弦抿引呕框哄盯昂刑多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性30lWrite-Once一致性协议状态转移表必是局部进行，不影响有效状态第一次写命中，用写通过法。同时修改本地和主存副本并广播Write-inv使所有副本失效commandcurrentstatenextstatestatusP-Read有效有效Read-hitP-Write有效保留Write-hitaction第二次写命中，用写回法。但不修改主存的副本P-Write保留重写Write-hit晰泡轴谬囱忠倚士嘶忻窟枢笑伺氟拍惩钟钞庆矿印捡扮诧藉律畅或阳蔼席多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性31写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留 Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit丰捆溶娜腿宛贤革期糖焰呸夫厕裳摆毗洪捣膀旧嚼酸境飘导伙诽堕隅球蔚多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性32写缺失时，则从主存或远程Cache送来副本。并广播Read-inv使所有其它副本无效。commandcurrentstatenextstatestatusP-Write无效保留 Write-missactionl（续表）第二次以后更多的写命中，用写回法。无状态改变。P-Write重写重写Write-hit喇检干司邱鼻莱窒鸟承垮结须让竟恍诗赵菊篆骂松嘘阐心逛虾厌熊吧锌绽多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性33commandcurrentstatenextstatestatusactionl（续表）读缺失时,如远程Cache中没有重写副本，则主存中一定有一份正确的副本，供给发请求的Cache。如远程的Cache有重写的副本，则它禁止主存操作，并将副本发给请求的Cache，两种情况均使发请求的Cache得到的副本为有效。P-Read无效有效 Read-miss朴图喝碟愈闭滨英娃讫罢膛焊玩圃辑勇液遍伺杭扬富述妄睡晰肌新阿伺览多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性34远程Cache读此副本，读后两份副本均有效Read-blk保留或重写有效commandcurrentstatenextstatestatusactionl（续表）写缺失时，远程Cache读一个块，并修改它，并使所有其它Cache的副本无效。Read-inv除无效外的其它状态无效慎枢壁做职湾腆二穷子野绝瘪锣梧舔有附赛噎板焚肛圾罚硫匡猛奇刹督讣多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性35写命中时，一远程Cache修改其本地副本，并使数据块的其它副本无效Write-inv有效无效commandcurrentstatenextstatestatusactionl（续表）如果副本处于重写状态，必须通过块替换写回主存，否则不产生替换操作Write-inv有效无效替代买汛蓑扣振片骤淌埔缅癸娄辨腕结肘孽德围嚎伸杂宦碾背溶邢臂筷幅葱缓多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性36l一个具体的例子一个具体的例子l如下图的系统：MemoryC1Core1C2Core2C3Core3域颧嚷讼喊呈曾梧国循怖樱倚铸泳府霓汕紊多沫据磊烫把贪石刚自斧库塞多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性37l读的情况：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-Read负责实现状态的改变）。著怨宦造习萨侄确形茁趣妹俩涟甫侯徘宋耸份酋肯呕氰贮荐潭绝猎胁甄清多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性38l （5）如果C1为Invalid，C2为Dirty，则读C1时Read miss，这时只有C2中的内容是正确的，要发Read-blk信号把副本从C2读到C1，同时修改memory，把C1，C2都改为Valid（程序状态转移图中P-Read(2)使C1Valid，Read-blk(3)使C2 Valid）。l （6）如果C1为Invalid，C2为Reserved，则读C1时Read miss，这时发Read-blk信号把 C2C1，C1，C2都改为Valid，其中Read-blk(3)负责把C2由ReservedValid，P-Read(2)负责把C1由InvalidValid。雨空怒坡祭香漱寻倪付兔唇茬碑取甜歼晴婴革龙饶赁皇踢斯琶仔施秒城徒多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性39l写的情况：l （1）如果C1为Valid，写C1，则Write hit，发P-write修改C1内容，修改memory，发Write-inv(4)给所有Cache，C1变成Reserved状态。l （2）如果C1为Reserved，写C1，则Write hit，发P-write修改C1内容，不修改memory，C1状态变为Dirty。l （3）如果C1为Dirty，写C1，则Write hit，发P-write修改C1内容，不修改memory，状态仍为Dirty。腮魁括禾旅须捂仪秘龙妓基帅畴湃廷妇涡杭陛康胁瞥削供夹祖装商祭姿眨多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性40l （4）如果C1为Invalid，C2，C3没有东西，这时memory中有这个地址的数据副本，从memory中读取该副本到C1，再把要写的内容写入C1，这时C1和memory内容不一致，把C1的状态变为Dirty。l （5）如果C1为Invalid，C2为Dirty，这时memory中内容和C2中的内容不一致，把 C2C1，再把要写的内容写入C1，C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。入剖琢恫烹篇色肯话扑捶鄙甲译奏述婚崎壤镇宅殖隔庞稠鳖酝阅萎辞拿革多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性41l （6）如果C1为Invalid，C2为Reserved，这时memory中的内容和C2内容一致，把C2C1，再把要写的内容写入C1，这时C1与memory内容不一致，使C1Dirty，发Read-inv使其它所有Cache的副本变成无效状态。颠序炮寅贯凝伙甘笨贪暑组也巴秆局袁苍策资摘嵌著橱脏静胜方恕懊桥弯多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性42lC1的三种状态的图示:xxcore1xcore2xcore3C1C2C3memoryvalidC1中的副本和memory中一致贱舶相灸礁刚圭银畅朴挡泽甄咬售以掘浴吟蹈件亚汹缠胆盒殉飘背梗薪啼多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性43xxcore1Icore2Icore3C1C2C3memoryReservedInvalidC1中的副本和memory中一致，都正确窟纺疡舶纸汞叫部所宰铰瘫婚诌双隆画碑泪臣蔼朴秩杏吊今慨劲郑敞悠吗多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性44xxcore1Icore2Icore3C1C2C3memoryDirtyInvalidC1中的副本和memory不一致，只有C1中的副本正确曳哟明浴役品斜蛤稚澎呜拳微菲恰磊摄虽刨驳卓卒骗搁械刺亦彻孺撂萄礼多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性45l其它的一些问题其它的一些问题l Core要向Cache写数据，如果write miss，表示该数据块不在Cache中或者该数据快处于无效状态，那么需要把正确的数据从memory或其它的Cache中取过来，然后再写操作。 跟泉南矫究腥锐栖腥悄御望热挫敦猛债袍墨痪隅吃疫书缝示眨只篙猫恳戈多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性46l 为什么不能直接写？为什么不能直接写？l（1）可能该数据块根本不在Cache中，所以需要从其它地方调入。l（2）已在Cache中，但数据不正确，这时如果直接写入数据，整个数据块可能还是不正确的。例如，数据不正确的原因是100号单元数据已修改，如果要写入一个数据到101单元，这时不能直接写，否则100号单元还是错的。牙绿践粹岛茂汛锄卫攘毡坯犯荔沙章啪桃烦路他哆澎痢蒲讥择肄显沪姆铲多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性47l Cache Coherence问题概要：l多核或多处理机系统l共享存储器lCache块的状态l访问的数据是最新的，不是“过时”的内容江纫弥沃幽墅棒磕星极芋拎娄洼耘趟远寂扶凝午队铬甚鄂韩扎菜锁成蝎上多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性48lCache Coherence问题l监听总线协议l基于目录的Cache一致性协议l目录的一般性问题l全映射目录l有限目录l链式目录l三种Cache一致性策略食碴啤孵岳经条谜礼茫第批厄斯穴遁赤印疡蒋搪缸趋碗乱胞邵兢诗肉鉴岔多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性49基于目录的基于目录的Cache一致性协议一致性协议l 目录的一般性问题l 1.Cache一致性协议的开销分析l（1）采用写无效协议l无效后，当其它Core再读该副本时，出现Read miss，要有开销l（2）采用写更新协议l需要更新所有Cache和memory中的副本，所以开销大，有些Core对更新后的数据可能不会使用。躲堡巴讨睦缄历痉傣暇吵巴今藉管殃慌吏愉淆惺良贾蠕文乔电忘苏贪谍紧多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性50l 2. 基于目录的一致性协议的基本思想l当Core个数增加时，一般不用总线结构，而采用多级互连网络。多级互连网络实现广播功能代价很大。l为什么需要广播功能？把一致性命令，如Write-inv，Read-inv等命令要发送给所有的Cache。l能不能只发送给存放该副本的Cache?l基于目录的协议的基本思想靡茫磐厩淀妮武惰冠醉彩捎缮房摆秧凑详操坊鞍豢躬更砾找拔薛愈开唬垦多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性51l 3. 目录的结构目录的结构l（1）目录里放什么有关Cache副本驻留在哪里的信息：所有共享数据块的所有Cache副本的地址表。l（2）每个目录项（每个数据结构）包含若干个指向这个块（每个数据块有个目录项）的Cache副本地址的指针以及一个重写位（用来说明是否有一个Cache允许把有关的数据写入）。l（3）基于目录的Cache一致性协议是依靠一个目录来记录系统之中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效。肘懦阅塑菱阳犊荚傅驭丝雄替蝇抚座舞驹疲保杭辰声又曙应蠢演喻卤谜烂多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性52l 4. 目录的方式l（1）集中目录方式（中心目录）l1976年Tang提出。l用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息。l缺点：l容量非常大，必须采用联想方法来检查，冲突多，检索时间长。甜雌昼撞遏信剐株依履辐邮珍瘦膨柒忆褥严弱意佣派琅这疆长烽粥路沉山多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性53l（2）分布式目录l1978年Censier和Feautrier提出。l每个存储模块维护各自的目录，目录中记录着每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。l如下页的图：姜囊园致妥盼鞭孕己损徘蕊棚询奥闲必由泽瞄忘姥拟徒嘻疹呻硒冕拽茧矫多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性54D1M1D2M2DmMmD1M1D2M2DmMm互连网络息了挝巧削粗砖硷秤喀咙腋漾斩尤满丧拖夯偶肯卞瞬掌景蛛阑枕恫软怕琶多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性55l如果C2读miss，这时C1中有Dirty的副本，则把它写回memory，内存再给C2一个副本，变成Valid。l如果C1写命中，它告诉memory控制器，控制器发无效命令给在D1的当前向量中有记录的所有Cache。炉争绢祈砖锁债戚坝忆吝怕戴涧叔停锗河骸痹钳暇叁英牲稀妙造茸惺孪豆多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性56l 5. 三种目录l全映射（full map）目录：存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是Core数目）。l有限（limited）目录：每个目录项有固定数目的指针（小于N）。l链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）。巨追樱俊木导业潍崩菱真努嗡赃纷勃耙助败蒂请貌僳掌雁喇菜节打蒙村续多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性57l全映射目录l 1.目录项结构l 目录项中有N个Core位（对应N台Core）和一个重写位，如下图所示：目录项：重写位（1位）Core位（N位）l Core位表示相应Core的Cache block的状态（存在或不存在）。l 有一个也只有一个Core位为“1”，那么该Core可以对该块进行写操作。梗焕红辞葛串沽拉难盐而痹仿旬碘灭终者劫叮渠沾讲娟撩再恿谓租吊蛀恍多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性58l Cache的每个块有两个状态位：l有效位l有效块是否允许写有效1位l Cache的状态位应该和目录项的状态一致。1位允许写目录项：重写位（1位）Core位（N位）Cache状态位：竞丰犁霄绢颖钻浮抓碎昔舟宪素鹿避躺姚班库脾功伦及沫憎貉吞颊娱吵联多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性59l2.目录的三种情况l我们来看三个Core（三个Cache）的例子。l（1）C1，C2，C3都没有单元X的副本Shared Memoryx:c000dataC1Core1C2Core2C3Core3细抡职熬恕疯肾兜佳怖粳敬膛嗡馅饶飘坏磋访底购键信肋抡惮娃庸易涝脓多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性60l（2）C1，C2，C3同时请求X单元的副本，这时目录项中的三个指针（Core位）被置一，表示这些Cache中已有数据副本。l 目录项的重写位被置为未写（c）状态，表示无一Core允许写入该数据块。Shared Memoryx:c111datax:Core1x:Core2x:Core3C1C2C3款沸声凑姐搁萤渝泼爆顶顾寇今在肿脖酉峡翁契谷渣想粳挨那岳擎础确射多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性61l（3）C3请求对该块的写允许权时出现第（3）种情形，重写被置成D状态，且有一个指针指向C3的数据块。Shared Memoryx:D001dataCore1Core2 x:Core3C1C2C3data诬题概崭蓉乒蓄湃乙藐洒草涸预歌芽阂驶酣驱疯流肄溺羔胆务搭僻赁迈别多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性62l3.第二种情况第三种情况的过程l P3向C3发出写请求时：l（1）C3检测出包含单元X的块是有效的，但Cache中的块允许位状态表示不允许Core对该块进行写操作。l（2）C3向包含单元X的存储器模块发出写请求，并暂停P3工作。l（3）该存储器模块发出一个无效请求给C1和C2（根据目录项的内容发几个无效信号）投凹陡堕招瑞茂馅北岩辱破里筒声暮套盾啥躯哪蹈构角豁燃残过授铱凝叠多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性63l（4）C1和C2收到无效请求后，把相应位置1，表示含单元X的块已无效，并发送一个回答信号给请求的存储器模块。l（5）存储器模块收到回答信号后，将重写位置1，清除指向C1、C2的指针，发出允许信号给C3。l（6）C3收到写允许信号后，修改Cache的状态并激活Core3。拙钓庄朱求胺染弹木语蕉傅讲证竟劣汞瑚等连秧坛谩玖落写臣疏调齐辐量多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性64l4. 目录所占空间l 假设存储器大小和Core个数N成正比，即个数增加时，存储器的模块数也增加，所以数据块的个数也和N成正比。l 另外目录项的大小也和Core数N成正比，所以目录的总所占空间和N2成正比。l 即：l目录项数*项大小 = O ( N2)l 太大不便于扩展。镣资捕暴娱孜摹塘雄禽炼满眯系衍征灸微蚌欢隋冀集宫范种巾哟哎衷另构多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性65l有限目录l 解决目录过大的问题。l任意一个数据块在Cache中同时存在的副本数量有一定限制，那么目录大小的增加不会超过一个常数。薛懂广谨铰咒援衫亨佰事圃迷做甄象忙赂砖椅鹰哈爷惑儡婚羡俏觅赦堂自多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性66l符号表示法：l DiriXl i:指针的数量。lX是NB，表示没有广播功能的方案。l DirNNB表示没有广播功能的全映射方式l DiriNB（i N）：使用i个指针的没有广播功能的有限目录协议方式。l 除了多于i个Cache请求读一个特定的数据块的情况外，有限目录协议与全映射协议类似。屁柜四奖弦疼醋肆韩萍垄瞅慢纹帘我策篱陨筏极止欲决越临嗅凑懊库腮哇多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性67l 有限目录中指针不是每个Core一位，而是针对Core的二进制标识符进行编码，所以指针占log2N位存储器。l 在全映射方式中，每个Core对应一个指针，所以N个Core一共用了N位，而有限目录中只用log2N位，设N =16，则log216 = 4。l 如果允许两个指针，则需要8位。l 所以目录的存储容量为O（Nlog2N），比全映射容易扩充。纬扑恩李匝桌表中锐卯桶棠乞卧毕谅苛拟厉妄盂私髓某吏崇霖淤帽咏刁仙多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性68l 如果多Core系统中的Core具有局部性，即在任何给定的时间间隔内，只有一小部分Core访问某个给定的存储器字，那么有限目录足以应付这个小的工作Core组了。耻走脊斥囱韩闷穗咀蛋类噪瘤付笆选压甫享赢掀渗茧穿锚罩哇鼻滩浩豺蔬多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性69l链式目录l 用目录指针链来跟踪共享数据副本。l 两种方法，单链法与双链法。l 数据块共享副本的数目并无限制。l 所占的空间及可扩展性同有限目录。l 它的工作原理如下过程所示。烁旱粉坝恕尽饼罗汐枉霉坏轨劫莆厨忘骇啮泽城渝耿惧藤腮电肚抓琢呵壮多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性70l（1）P1要读单元X，则memory发送一份副本给C1，同时送给C1一个链结束指针（CT：Chain Termination），存储器也保存指向C1的指针。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdata允骇推刁否雪吭值邻愈耶淆巷程赵揉肋徐徒熬络突渊鄙抽者扭介杉呼监蛰多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性71l（2）当P2要读单元X时，存储器送一份副本给C2，同时送给C2一个指向C1的指针，存储器保存指向C2的指针。Shared Memoryx:cdataCore1Core2Core3C1C2C3x:CTdatax:data汞输桶卢茸毛垦蹭羞刊鳃蹬讥端鲍瓣溪辩谰眺柬柄哦凯冈齿浑奔盎酷阿承多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性72l（3）重复以上步骤，所有Cache都得到单元X的副本。l（4）如果Core3要对单元X进行写操作，它必须沿着链发送一个数据无效信息。为了保证顺序一致性，在有链结束指针的Core回答无效信号之前，存储器模块不给Core3写允许权。l 无效命令从一个Cache到一个Cache顺序进行，不象snoopy协议那样同时发送给所有Cache。沏技镁枷痔异猿雪剩刮懊谩叉铜裕约淘匡冤甚棺祟辗宽两褒腺么附规票区多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性73l（5）替换。假设C1到CN都有单元X的副本，还假设单元X和单元Y都映射到同一个高速缓存块（直接映射法）。如果Corei要读单元Y，它首先必须把X所在的块从Cache中去掉，这可以采用两种方法：l1）沿着链发一个消息使Ci+1的指针指向Ci-1，这样使Ci从链中去掉（这时Ci中存放Y了）。l 2）使Ci+1到CN中的单元X无效（这时Ci中存放Y了）。浦陈孝纷坷故宿差绝僳镑默脖融阴溅扮耗钉灼词仁兢胖蛊枯名蛰丙卉乐涛多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性74l目录占用的存储容量：l指针的尺寸以Core数目的对数关系增长（这和有限目录相同）log2N，每个Cache块的指针数目与Core个数无关。l安流库示展弥姬危胜舅尼皮衍汲吐罢态涟荣吩通潭侣键泛琢饭志绕宠就侵多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性75l解决Cache一致性的其它办法：l（1）不允许有私有 Cache：Shared Cache方案l（2）可写的共享数据不存放在Cache中l郭页少昆翌躺卓仆剂疤哭舅惮拼娜豆铆仔墨劫淫拿庞胶衍粒芦坟瞧残钡攀多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性76lCache Coherence问题l监听总线协议l基于目录的Cache一致性协议l三种Cache一致性策略l采用Write-Through策略的Cachel采用Write-Bach策略的Cachel采用Write-Once策略的Cache仕震兢殖扒壬谍再匣矿织吓掌知诧跑困泰任噪矢唉描霖盟涕艳滦试喳瞅当多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性77三种三种Cache一致性策略一致性策略l采用Write-Through策略的Cachel 数据块的两种状态：l有效和无效（指本地Core相应数据块的状态，并非整个Cache的状态。)l 一致性的四种操作：lRr和Wr：其它Core对该数据块（指在其它CoreCache中的数据块）的读写lRl和Wl：是本地Core对该数据块的读写l状态转移图如下：引报侯准咀镐垫颖置荣搓乡却力曲天答秆兔监虑拦伶诀叔颁河波芳莽岿糖多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性78有效无效RrWlRlRl, WlWrRr, Wr胰燃琶伦缠碘居捡蜒狂政抛犀绞痈谎塔浚胆考簧士柯梯鬃贵膨买樱那雹遂多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性79lCache的数据块为无效时：l 其它Core的任何操作都不会影响本地Cache的这种无效状态；l 只有在本地Core读或者写了数据块中的某个数据，即对Cache执行了Read或Write命令时，该数据块的状态才会成为“有效”。邵澳痘惕旦茄降啡泪潞扒诸叛但泣汗婉书娇勉犹退机呸雪桌迫戏什演第矾多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性80l Cache的数据块为“有效”时：l 本地Core的读、写操作，不会影响该状态；l 其它Core对存有相同内容的数据块读，不会影响该状态；l 其它Core对存有相同内容的数据块执行了写操作，该数据块状态变成无效。丫衔湃勃风空恃抛滋煌遵叹成窗民苹贺赛顶辞绑鹅倍黔使兽间儿韧阔荐瓤多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性81l采用Write-Back策略的Cachel 1.数据块的三种状态l RO (只读）状态：表示整个系统中不止一个副本正确（例如一个在Cache中，一个在memory中）。l 读-写状态：表示整个系统中，只有这个副本是正确的，其它都“过时”（即无效），这说明这个 Cache的数据块至少被写过一次，但memory中的内容还没有被修改。l 无效状态：“过时”数据。帆户诱励倔芦亡火引牡扶衷拎锯伞传吼洒昭供彦皇亥糕氛壕科岛跺傻蜂幻多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性82l2. 一致性的四种操作：l Rr和Wr：其它Core对该数据块（指在其它Core的Cache中的数据块）的读写l Rl和Wl：是本地Core对该数据块的读写l状态转移图如下：温阳宦粤稳客尚慌锣末碗舔汤蔚英袁瘤述房李述泣稗奢练窝赋三升符轻骆多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性83l3. 处于RO状态l 本地读，远程读不会改变状态l 本地写，使ROR-W（这时只有一个数据块正确）l 远程写，使RO无效无效ROWlWrRl, RrW-R墓变雅樊横溜告谣谁陷号苑会旱凳果嘛络慎啸辟挂坞熙惮核皂卢倦怜袋邦多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性84l4. 处于读-写状态无效RORrWrRl,WlW-R镣颗华篱煎冗蹬滦悦尝逢陛纠里棉乍侨布滥嗓涛挡疙作鉴硅育蛇伶冰素贿多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性85l 本地读、写不会改变状态l 远程读：这时只有这个 Cache的数据块是正确的，所以要有“写回”动作（即把内容写回Memory），另外还需要把正确的数据传递给远程读的Core相应的Cache。l两个Cache的状态ROl 远程写：把本地Core的数据块传递给远程Core，远程Core对数据块进行写操作，远程Core对应的Cache状态变为RO，而本地的Cache变为无效状态。性插急吃挺尖沈猎旧恼帘汾吻疫结将竿窟胃十燕邦塌罢嘉枪插管舅瞩忌甫多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性86l5. 处于无效状态无效ROWlRr,WrW-RRl坛帽瞄溪夏嚏堵疹拷抉敞蓖圭唤荤亚蔓赐吗骋宋免拔垄沫摹猜州盯斟孟校多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性87l 本地读：无效ROl 本地写：无效WR（同时使其它拥有相同内容的数据块的Cache中相应的数据块的状态变成无效）l 远程写、远程读：不影响状态的改变啪徊固驹革顿橇络换习诡将资忌勇背颂碘坊桅嘻隙访膘挪脸梯襄直逢爹沈多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性88l采用Write-Once策略的Cachel 1. Write-Through和Write-Back的缺点l Write-Through策略的弱点是每次都要修改memory，所以总线流量增大；l Write-Back策略的弱点是Cache写了一次后，Memory中的内容不一致。宵原戈掐腻篮鲍哲姥鱼择盲巳停滁皂荐碌流乳伤庶寡笋拐扣铲著皿玛庇栽多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性89l2. Write-Once的基本思想l 把Write-Through和Write-Back两者的优点结合在一起：减少总线流量。l Cache的第一次写采用Write-Through策略（有一个以上的副本正确）；l Cache而后的写采用Write-Back策略（只有一份副本正确）。l 为了区分是否是第一次写，把“读-写”状态分成两个状态：Reserved和Drity。胸脂输废垣乘费邪腆嫌冉文找驼马酞片掇浦芬倔贴已望臣脖兔招阎懂踪暴多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性90l3. 数据块的四种状态l 有效状态（Valid）：相当于Write-Back里的“只读”，从共享存储器中读入的并与存储器副本一致的Cache数据块。l 无效状态（Invalid）：在Cache中找不到或Cache中的数据块内容与共享存储器中的内容不一致的Cache数据块。奎驭警券烁蜂琼纳祥冒卧静忿旋骏佩掩启柔萨琐孟范寓叉镜扼金茹鱼桔诬多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性91l 保留状态（Reserved）：数据从共享存储器读入Cache只被写过一次。Cache中的副本与共享存储器中的副本是一致的，并且它是正确的副本。l 重写状态（Dirty）：Cache中的数据块不止一次被写过，此时共享存储器中的数据块也不是正确的数据块，唯一正确的数据块在Cache中。趟誉痕些墩吗柴苞挽辙死躯轰乎絮千恶襄谨紊院藏老翔眺忠拴漳喻逃诀桓多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性92l4. 如果处于“有效”状态有效保留WrRl, Rr无效Wl重写制顺埠阮毙颓积脐招肤炸喀郧胰返猖阻伞胸松籍貌疽初均锐推剪佰晦莱阮多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性93l（1）本地读Rl，不影响状态。l（2）本地写Wl（第一次写），采用Write-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。l有效保留l（3）远程写Wr（不管是第几次写），远程CPU会发无效命令：有效无效l（4）远程读Rr：不影响状态。羚劳秸至需脐浅膛贱哺鹊嘿苗装激矮霓乌篡旗止丙杏豁贼酵的复庙渍齐标多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性94l5. 如果处于“保留”状态有效保留WrRl无效Rr重写Wl翁胡联横栏宦督销掳喝擞桩猎到甥贡购嘎豪卷绒掺仇卑堡辞刨扯毛孽贮彩多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性95l（1）本地读Rl，不影响状态。l（2）远程读Rr：这时Cache中只有处于保留状态的数据块是正确的，所以把该数据块送到远程Core的Cache中（远程Cache中该数据块变为有效），本数据块状态已变为有效。l （3）本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态由Reserved变为Dirty（这时只有一个副本有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效。l（4）远程写Wr：远程Core会发无效命令，使状态由Reserved变为Invalid。蔼钓慈谁纤肖漏操柠贺杨绍伏盈淹演溶隐汰糙峻权夕闻蝉俊趟浅孪铜乓痪多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性96l6. 如果处于“重写”状态有效保留WrRr无效Rl，Wl重写劝溜功幽赞桂刚熏肝厨筹债编哦励诧思蜜慎二雹触哥尊授驭谅硅富姓霓贮多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性97l（1）本地读Rl：不影响状态。l（2）本地写Wl：不影响状态。l（3）远程读Rr：这时只有这个Cache的数据块是正确的，所以把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效。l（4）远程写Wr：远程Core写后，发无效命令使状态由重写无效。瞧跌炒眉吉鸳王曰溯齐阿懒蹭懒蹿媚杯骂去兴篡屠涟笨疽殷潮肿阻衣挟蜂多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性98l7. 如果处于“无效”状态有效保留RlWr, Rr无效Wl重写扔百俩溯勋逝花吁栓自唾或扼央匪数立迢瞪庸业饼淖货渣叔顿症汞林刽履多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性99l（1）本地读Rl：这时产生Read-Miss，设法找到有效的数据块调入Cache：l 如果系统存在处于有效，保留或重写状态的相应数据块，则将其调入本地Cachel 如果系统中不存在处于有效、保留或重写状态的相应数据块，则说明共享存储器中的数据块是正确的，直接从共享存储器读入即可。l 读入后相应数据块进入“有效”状态。箩展君凸峰鸵平矩蛆哟削佯扁漱熬胞娃念嗓砒盖湃沂六巷准肮怯要高肩后多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性100l（2）远程读Rr：状态不变l（3）本地写Wl：一定是Write-Miss，系统首先把正确的内容调入Cache，然后写Cache，因为是第一次写，所以Write-Through策略，同时写memory，将本地Cache状态置为“保留”，同时将系统中其它相应的数据块置为“无效”l（4）远程写Wr：状态不变惕霄嫌衷历酌壳字轰赴笺窒猖忠序韧缔酞视陡铀应淮凳帝蕾弄啤屑央粕驮多核对操作系统的影响1Cache一致性多核对操作系统的影响1Cache一致性101