通常是使用硬件提供的有关同步指令.ppt

7.5 同 步 通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。7.5.1 基本硬件原语 在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。,第章 多处理机,往悯拄幢贞石室果言网酱牛跪健藤世韧窖漠毯坤板祥宜官鹊絮沼捞湿弄驴通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,功能：将一个存储单元的值和一个寄存器的值 进行交换。建立一个锁，锁值为“0”表示开锁，为“1”表示上锁。处理器加锁时，将对应于该锁的存储单元的值 交换为某个寄存器的值“1”。如果返回值为“0”，存储单元的值此时已置换为“1”，防止了别的进 程竞争该锁。实现同步的关键:操作的原子性,1.典型操作:原子交换（atomic exchange）,7.5 同 步,纯糯蜂骡烟沤冯固棒为八匿彭长蜜探漆人罐河钓柯据桔赋侈矫歼蓄四热傅通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,2.测试并置定（test_and_set）先测试一个值，如果符合条件则修改其值。3.读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。4.使用指令对,LL(load linked或load locked)的取指令 SC(store conditional)的特殊存指令,7.5 同 步,偷脱冯姑鹊知舶紧猛谢脓殖菌汕拄藻税犬灶寥咒爆蓝禽秒赢区诉河斗碉垮通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,例实现对由R1指出的存储单元进行原子交换操作 try：mov R3,R4；送交换值 ll R2,0(R1)；load linked sc R3,0(R1)；store conditional beqz R3,try；存失败转移 mov R4,R2；将取的值送往R4 最终R4和由R1指向的单元值进行原子交换，在ll和sc之间如有别的处理器插入并修改了存储单元的值，sc将返回“0”并存入R3中，从而使指令序列再重新循环。,7.5 同 步,级况懦综逼碱憋檄尽詹族甸名用蚀画冀谐厌椿蟹闯锐缮危赢源驮耻雷稼纂通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,llsc机制的一个优点：可用来构造别的同步原语 例如：原子的fetch-and-increment try：ll R2,0(R1)；load linked addi R2,R2,1；增加 sc R2,0(R1)；store conditional beqz R2,try；存失败转移 指令对的实现必须跟踪地址 由ll指令指定一个寄存器，该寄存器存放着一个 单元地址，这个寄存器常称为连接寄存器。,7.5 同 步,床逆柏歼愚跨束盾剿溶辑公坪闯阂殖够城爵腊偷焊妖盈玛柜奥凝峙舵锚棵通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,7.5.2 用一致性实现锁,采用多处理机的一致性机制来实现旋转锁。旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁。,1.无Cache一致性机制 在存储器中保存锁变量，处理器可以不断地通 过一个原子操作请求加锁，比如先交换，再测试返 回值从而知道锁的状况。释放锁的时候，处理器可 简单地将锁置为“0”。,7.5 同 步,瞬拿宴皇笔元育蛔岿拖邯肤惟蔓锑僳洋戚醚间渺姓燎袋池居爵匙鬃辱痪兔通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,li R2，1lockit：exch R2,0(R1)；原子交换 bnez R2，lockit；是否已加锁?,2.机器支持Cache一致性 将锁缓冲进入Cache，并通过一致性机制使锁值保 持一致。,7.5 同 步,位湖擂瘩散资卉谅姿椰籍葫淆沈栽辣乘席东剖孟粤榆幻陡雾临臂笨干胺炸通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,优点,可使“环绕”的进程对本地Cache块进行操作；可利用锁访问的局部性，即处理器最近使用过 的锁不久又会使用。,改进旋转锁(获得第一条好处)使其环绕过程仅对本地Cache中锁的拷贝进行读，直到它返回“0”确认锁可用，然后再进行加锁交换操 作。使用锁完毕后新竞争又开始进行。,7.5 同 步,琼款鸭阁匀身滚悲嘶踢腺屯腊殿蝇粮祁唯固尿蝉樱址楷沪湾呕件出泪赌诅通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,lockit：lw R2，0(R1)；取锁值 bnez R2，lockit；锁不可用 li R2，1；存入锁值 exch R2，0(R1)；交换 bnez R2，lockit;如锁不为0转移 上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0”释放锁，所有别的Cache对应块均被作废，必须取新的值来更新它们锁的拷贝。一个处理器Cache会先获得未加锁值并执行交换操作，当别的Cache失效处理完后，它们会发现已被加锁，所以又必须不停地测试环绕。,7.5 同 步,酌呵饵远物润蹄谋巍骑裤毯溺捉憋锑元弊铸纸笛轴嗜荒栏园挟阑漱悠渍拂通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,表7.5 三个处理机对锁的使用,7.5 同 步,跌仲所逢备笋亭仟纶噪栽议绥札痴颊渐奇骡颂箔醋抡栖侩彰誓白巢曾钡送通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,llsc原语的另一个状态：读写操作明显分开。Ll不产生总线数据传送，这使下面代码与使用经 过优化交换的代码具有相同的特点：lockit：ll R2，0(R1)；load-linked bnez R2，lockit；锁无效 li R2,，1；加锁值 sc R2，0(R1)；存 beqz R2，lockit；如存失败转移 第一个分支形成环绕的循环体，第二个分支解决了两个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并且具有强制性，但难以将它扩展到处理器数量很多的情况。,7.5 同 步,袁尼埋设蕴碗梁辑坊墙鳃欲饼屎祥溜赁柿彬队恫链纱鹅议顽绕饮刚晌访织通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,7.5.3 同步性能问题 简单旋转锁不能很好地适应可伸缩性。大规模机器 中所有的处理器会产生出大量的竞争问题。例7.3：设总线上有10个处理器同时准备对同一变量加锁。假设每个总线事务处理(读失效或写失效)是100个时钟周期，忽略实际的Cache块锁的读写时间以及加锁的时间，求10个处理器请求加锁所需的总线事务数目。设时间为0时锁已释放并且所有处理器在旋转，求处理这10个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。,7.5 同 步,蚌鹃赛忱触瞪尼硷疡愧贬袱厢次膏疥讣锋夷孵似勺股掠轨柿助蠢丝佐屹词通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,解 当i个处理器竞争锁的时候，他们完成下列操作序列，每一个操作产生一个总线事务：访问该锁的i个LL指令操作；试图锁住该锁的i个SC指令操作；1个释放锁的存操作指令。因此对n个处理器，总线事务的总和为：n(2i+1)=n(n+1)+n=n2+2n i=1对于10个处理器有120个总线事务，需要12000个时钟周期。,7.5 同 步,搪傅淖咨氏杰曹厦棺谷薄泄恶币扛报怀音阜鞭谐侍晌互炮毯锯棱批鞭潘踩通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。旋转锁的主要优点:对于总线或网络开销较低,7.5 同 步,赂今熙二瀑穷铰舍掐祖砰藤媳竞访疵倒澳等卉裸惕池静济吃潞裔沛藏鹏胁通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,并行循环的程序中另一个常用的同步操作:栅栏 栅栏强制所有到达的进程进行等待，直到全部的 进程到达栅栏，然后释放全部的进程，从而形成同步。,栅栏的典型实现 用两个旋转锁(1)用来记录到达栅栏的进程数(2)用来封锁进程直至最后一个进程到达栅栏 栅栏的实现要不停地探测指定的变量，直到它满足规定的条件。一种典型的实现，其中lock和unlock提供基本的 旋转锁，total是要到达栅栏的进程总数。,7.5 同 步,枚帅焦暖搪拣阐某斜诸恢泽靠亚锯匙杂后越靴续血郑烧跪厦拯喻检刷拉稀通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,Lock(counterlock)；*确保更新的原子性*if(count=0)release=0；*第一个进程则重置release*count=count+1；*到达进程记数*unlock(counterlock)；*释放锁*if(count=total)*进程全部到达*count=0；*重置计数器*release=1；*释放进程*else*还有进程未到达*spin(release=1)；*等待别的进程到达*,7.5 同 步,烘昭僳恍仅奥天月嘶段藻渗陕篇软舍碉训倡亿腔保钟费涌浆志秤尝永渤友通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,对counterlock加锁保证增量操作的原子性，变 量 count记录着已到达栅栏的进程数，变量 release用来封锁进程直到最后一个进程到达栅栏。实际情况中会出现的问题 可能反复使用一个栅栏，栅栏释放的进程运行 一段后又会再次返回栅栏，这样有可能出现某个进 程永远离不开栅栏的状况(它停在旋转操作上)。,7.5 同 步,壕隔肘鹤勒攒僳知钉附眯皖尉胆褂排姥无季撇辩糖浪烟碴筏自辫桥递瞥襟通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,例如：OS调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开。这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达不到total。,7.5 同 步,结骂醛刨图咨岗刑侗介钓家辞钩描屋炕钉伪屈嚼祟只醉墅猛仕杖均檀依袋通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,一种解决方法 当进程离开栅栏时进行计数，在上次栅栏使用中 的所有进程离开之前不允许任何进程重用并初始化本 栅栏。另一种解决办法 sense_reversing栅栏，每个进程均使用一个私 有变量local_sense，初始化为1。,7.5 同 步,耙共壹勿拢烘暇良逻八拘李摸铲拂锐李矿罐氰袄汽郊趾诛孵肤男雌腆癸收通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,Local_sense=!Local_sense；*local-sense取反*lock(counterlock)；*确保增加的原子性*count+；*记算到达进程数*unlock(counterlock)；*解锁*if(count=total)*进程全部到达*count=0；*重置计数器*release=local_sense；*释放进程*else*还有进程未到达*spin(release=local_sense)；*等待信号*,7.5 同 步,牧谗陵她敲另瓜祁撩庞航佐剧曙旅逮逛悔甫荔貉壹矮敷觉涡现痰井柒打哦通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,例7.4 假设总线上10个处理器同时执行一个栅栏，设每个总线事务需100个时钟周期，忽略Cache块中锁的读、写实际花费的时间，以及栅栏实现中非同步操作的时间，计算10个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?答：下表给出一个处理器通过栅栏发出的事件序列，设第一个获得总线的进程并未拥有锁。,7.5 同 步,榔近赵岔哺粒帐貌膘卓弯搜剪晤咒疟省器铸角蚊痒料凄匝讶铱嗅添圣戏衣通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,表7.6 第i个处理器通过栅栏产生的事件序列 事件 数量 对应源代码 说明LL i Lock(counterlock)；所有处理器抢锁SC i Lock(counterlock)；所有处理器抢锁LD 1 count=count+1；一个成功LL i-1 Lock(counterlock)；不成功的处理器再次抢锁SD 1 count=count+1；获得专有访问产生的失效SD 1 unlock(counterlock)；获得锁产生的失效LD 2 spin(release=local_sense)；读释放：初次和最后写产 生的失效,7.5 同 步,毯菌又弗轮颇予察绩丈荧祭夫府冀扔耐副第侠浑旨紊消婉蹄既沦郑微鲸摊通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,当竞争不激烈且同步操作较少时，我们主要关心的 是一个同步原语操作的延迟。基本的旋转锁操作可在两个总线周期内完成：一个读锁，一个写锁。我们可用多种方法改进形成 在一个单周期内完成操作。同步操作最严重的问题：进程的串行性 当出现竞争时，就会出现串行性问题。它极大 地增加了同步操作的时间。总线的使用是这个问题关键所在。在基于目录的Cache一致性机器中，串行性问题也 同样严重。,7.5 同 步,证忧契输回氮担氰捕捞酋龚百斧议值岔戒婆里贰冷荒馒窿窄使钎须历苏乙通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,7.5.4 大规模机器的同步所希望的同步机制：在无竞争的条件下延迟较小 在竞争激烈时串行性小1.软件实现 旋转锁(1)旋转锁实现的主要问题 当多个进程检测并竞争锁时引起的延迟(2)一种解决办法:当加锁失败时就人为地推延 这些进程的等待时间。(3)具有指数延迟的旋转锁代码,7.5 同 步,慎崩蓑羔兄蛔眯宪祷笋蓄旗够澡资弟掉趁江怪瞎缉住平族星印添径城质寺通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,li R3，1；R3初始延迟值；lockit：ll R2，0(R1)；load linked bnez R2，lockit；无效 addi R2，R2，1；取到加锁值 sc R2，0(R1)；store conditional bnez R2，gotit；存成功转移 sll R3，R3，1；将延迟时间增至2倍 pause R3；延迟R3中时间值 j lockitgotit：使用加锁保护的数据 当sc失败时，进程推延R3个时间单位。,7.5 同 步,垒临辽弧鲍舱奶卸藤蔚涉萎饭转憋锹汽柿汽艺渺捐之荐莉寺饰锑踊腊帘执通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,先讨论采用数组进行的软件实现。为此我们给出一种更好的栅栏实现代码。前面栅栏机制实现中，所有的进程必须读取 release标志，形成冲突。通过组合树来减小冲突 组合树是多个请求在局部结合起来形成树的一 种分级结构。降低冲突的原因：将大冲突化解成为并行的多 个小冲突。,锁实现的另一种技术是排队锁,7.5 同 步,拟籽贤淑痛惋傀筏吱吮捣栓哈录陪唇询垢堕殆跟忍腕货撑嘎渺埠镑浑澳筏通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,组合树采用预定义的n叉树结构 用变量k表示扇入数目，实际中k=4效果较 好。当k个进程都到达树的某个结点时，则发 信号进入树的上一层。当全部进程到达的信号汇集在根结点时，释放 所有的进程。采用sense_reversing技术来给出下面的基于 组合树的栅栏代码。,7.5 同 步,呈岸网颖骤植鹊侥嗽钒瞄校滁狗每灶呜烤咬动膜夸阳赎趋赐筏啪赛甸溯塑通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,struct node*组合树中一个结点*int counterlock；int count；int parent；struct node tree 0.p-1；*树中各结点*int local_sense；int release；barrier(int mynode)lock(treemynode.counterlock)；*保护计数器*count+；*计数的累加*unlock(treemynode.conterlock)；*解锁*if(treemynode.count=k)*本结点全部到达*if(treemynode.parent)=0 barrier(treemynode.parent)；elserelease=local_sense；treemynode.count0；*为下次重用初始化*else spin(release=local_sense)；local_sense=!local_sense；barrier(mynode)；,7.5 同 步,旬粒癣嫩郡仕咯烦继手甘射抱缩张埋界逾鳞照牢钞惊找嚣恋赚狼娩族节恕通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,2.硬件原语支持 介绍两种硬件同步原语：,(1)排队锁 可以排队记录等待的进程，当锁释放时送 出一个已确定的等待进程。,第一个针对锁 第二个针对栅栏和要求进行计数或提供明确索 引的某些用户级操作,7.5 同 步,旗篡感歪末剁拘靳蛋待崭掖教稿杀轨熄侵捉己疯迢总炳茎杀勉簿挣荤饥怖通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,硬件实现,在基于目录的机器上，通过硬件向量等方式 来进行排队和同步控制。在基于总线的机器中要将锁从一个进程显式 地传给另一个进程，软件实现会更好一些。,在第一次取锁变量失效时，失效被送入同步控 制器。同步控制器可集成在存储控制器中(基 于总线的系统)或集成在目录控制器中。,排队锁的工作过程,7.5 同 步,菏切氟饶者虹菱苑脐抡勤愤皑骇娩纹宗敝裴巳黄骗机相咐道利奢棍墨逃佣通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,如果锁空闲，将其交给该处理器；如果锁忙，控制 器产生一个结点请求记录，并将锁忙的标志返回给 处理器，然后该处理器不停地进行检测。当该锁被释放时，控制器从等待的进程排队中选出 一个使用锁，这可以通过更新所选进程Cache中的 锁变量来完成。,7.5 同 步,衣只躁枕佯喜批灌来矩纽绩盎泉闭直堂槽涕池错嫁泽牺寿僵仕想斌很娥匣通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,例7.5 如果在排队锁的使用中，失效时进行锁更新，求10个处理器完成lock和unlock所需的时间和总线事务数。假设条件与前面例子相同。解 对n个处理器，每个处理器都初始加锁产生1个总线事务，其中1个成功获得锁并在使用后释放锁，第1个处理器将有n+1个总线事务。每一个后续的处理器需要2个总线事务：1个获得锁，另1个释放锁。因此总线事务的总数为(n+1)+2(n-1)=3n-1。注意这里的总线事务总数随处理器数量成线性增长，而不是前面旋转锁那样成二次方增长。对10 个处理器，共需要29个总线事务或2900个时钟周期。,7.5 同 步,亿虏再洲佃缅娃董嫩潦贵母聘穷檬粮堡暇雷厂舌瞩支才彤丛懒猖吹容爱夺通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,首先，需要识别出对锁进行初次访问的进程，从而对其进行排队操作。第二，等待进程队列可通过多种机制实现，在 基于目录的机器中，队列为共享集合，需用类 似目录向量的硬件来实现排队锁的操作。最后，必须有硬件来回收锁，因为请求加锁的 进程可能被切换时切出，并且有可能在同一处 理器上不再被调度切入。,排队锁功能实现中有一些要考虑的关键问题,7.5 同 步,椒算羽贴拿性在恍凡绰俭砚诅覆炙毕暮其柯捏辣哎判参斋溜膘舅例桐捎拽通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,为减少栅栏记数时所需的时间，从而减小瓶颈的串行度，引进一种原语Fetch_and_increment，它可以原子地取值并增量。使用fetch_and_increment可以很好地改进栅栏的实现。例7.6：写出fetch_and_increment栅栏的代码。条件与前面假设相同，并设一次fetch_and_increment操作也需100个时钟周期。计算10个处理器通过栅栏的时间，及所需的总线周期数。,(2)栅栏实现,7.5 同 步,骄陛仓答硕债译锻啼吼按落元寂扇刽根潭蒙撩字俄业勤迅亏画铂医旺瑰父通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,解 下面的程序段给出栅栏的代码。对n 个处理器，这种实现需要进行n次fetch_and_increment操作，访问count变量的n次cache失效和释放时的n次Cache失效，这样总共需要3n个总线事务。对10个处理器，总共需要30个总线事务或3000个时钟周期。这里如同排队锁那样，时间与处理器个数成线性增长。当然，实现组合树栅栏时也可采用fetch_and_increment来降低树中每个结点的串行竞争。,7.5 同 步,抓征缠缀霍移避裔你颇本颧屹景宋春况杨秽捧憨赡秽驳楼劣娥膏硫碧祁请通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,local_sense=!local_sense；*local_sense变反*fetch-and-increment(count)；*原子性更新*if(count=total)*进程全部到达*count=0；*初始化计数器*release=local_sense；*释放进程*else*还有进程未到达*spin(releaze=local_sense)；*等待信号*,7.5 同 步,献爱肖里哆贷识铣女誊沧从摊壳权缴灭肉束廊少鞠头壮柴杖贷统峦赁绳辅通常是使用硬件提供的有关同步指令通常是使用硬件提供的有关同步指令,