《通常是使用硬件提供有关同步指令.pptx》由会员分享，可在线阅读，更多相关《通常是使用硬件提供有关同步指令.pptx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 功能：将一个存储单元的值和一个寄存器的值 进行交换。建立一个锁，锁值为“0”表示开锁，为“1”表示上锁。处理器加锁时，将对应于该锁的存储单元的值 交换为某个寄存器的值“1”。如果返回值为“0”，存储单元的值此时已置换为“1”，防止了别的进 程竞争该锁。实现同步的关键:操作的原子性1.典型操作:原子交换（atomic exchange）7.5 同 步第1页/共36页2.测试并置定（test_and_set）先测试一个值，如果符合条件则修改其值。3.读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。4.使用指令对q LL(load linked LL(load
2、 linked或load locked)load locked)的取指令q SC(store conditional)SC(store conditional)的特殊存指令7.5 同 步第2页/共36页例实现对由R1R1指出的存储单元进行原子交换操作 trytry：mov R3,R4 mov R3,R4 ；送交换值 ll R2,0(R1)ll R2,0(R1)；load linkedload linked sc R3,0(R1)sc R3,0(R1)；store conditionalstore conditional beqz R3,try beqz R3,try ；存失败转移 mov R4
3、,R2 mov R4,R2 ；将取的值送往R4R4 最终R4R4和由R1R1指向的单元值进行原子交换，在llll和scsc之间如有别的处理器插入并修改了存储单元的值，scsc将返回“0 0”并存入R3R3中，从而使指令序列再重新循环。7.5 同 步第3页/共36页 llsc机制的一个优点：可用来构造别的同步原语 例如：例如：原子的原子的fetch-and-incrementfetch-and-increment try try：ll R2,0(R1)ll R2,0(R1)；load linkedload linked addi R2,R2,addi R2,R2,1 1 ；增加；增加 sc R2
4、,0(R1)sc R2,0(R1)；store conditionalstore conditional beqz R2,try beqz R2,try ；存失败转移；存失败转移 指令对的实现必须跟踪地址 由由llll指令指定一个寄存器，该寄存器存放着一个指令指定一个寄存器，该寄存器存放着一个 单元地址，这个寄存器常称为单元地址，这个寄存器常称为连接寄存器连接寄存器。7.5 同 步第4页/共36页7.5.2 用一致性实现锁 采用多处理机的一致性机制来实现旋转锁。旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁。1.无Cache一致性机制 在存储器中保存锁变量，处理器可以不断地通 过一个原子操作
5、请求加锁，比如先交换，再测试返 回值从而知道锁的状况。释放锁的时候，处理器可 简单地将锁置为“0 0”。7.5 同 步第5页/共36页 li R2 li R2，1 1lockitlockit：exch R2,0(R1)exch R2,0(R1)；原子交换 bnez R2bnez R2，lockit lockit ；是否已加锁?2.机器支持Cache一致性 将锁缓冲进入CacheCache，并通过一致性机制使锁值保 持一致。7.5 同 步第6页/共36页 优点q 可使“环绕”的进程对本地CacheCache块进行操作；q 可利用锁访问的局部性，即处理器最近使用过 的锁不久又会使用。改进旋转锁(获
6、得第一条好处)使其环绕过程仅对本地Cache中锁的拷贝进行读，直到它返回“0”确认锁可用，然后再进行加锁交换操 作。使用锁完毕后新竞争又开始进行。7.5 同 步第7页/共36页 lockitlockit：lw R2lw R2，0(R1)0(R1)；取锁值 bnez R2bnez R2，lockit lockit ；锁不可用 li R2li R2，1 1 ；存入锁值 exch R2exch R2，0(R1)0(R1)；交换 bnez R2bnez R2，lockit ;lockit ;如锁不为0 0转移上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0 0”释放锁，所有别的CacheCac
7、he对应块均被作废，必须取新的值来更新它们锁的拷贝。一个处理器CacheCache会先获得未加锁值并执行交换操作，当别的CacheCache失效处理完后，它们会发现已被加锁，所以又必须不停地测试环绕。7.5 同 步第8页/共36页表7.5 7.5 三个处理机对锁的使用步骤步骤处理器处理器P0处理器处理器P1处理器处理器P2锁状态锁状态总线总线/目录操作目录操作1占有锁占有锁环绕测试环绕测试lock=0环绕测试环绕测试lock=0Shared无无2将将锁锁置置为为0（收到作废命令）（收到作废命令）(收到作废命令收到作废命令)ExclusiveP0发锁变量作废消息发锁变量作废消息3Cache失效失
8、效Cache失效失效Shared总总线线/目目录录处处理理P2Cache失效失效,锁从锁从P0写回写回4总总线线/目目录录忙忙则则等等待待Lock=0SharedP2Cache失效处理失效处理5Lock=0执执行行交交换换，导导致致Cache失效失效SharedP1Cache失效处理失效处理6执行交换，导致执行交换，导致Cache失效失效交交换换完完毕毕，返返回回0置置lock=1Exclusive总总线线/目目录录处处理理P2Cache失效失效,发作废消息发作废消息7交换完毕，返回交换完毕，返回1进进入入关关键键处处理理段段Shared总总线线/目目录录处处理理P2Cache失效，写回失效，
9、写回8环绕测试环绕测试lock=0无无7.5 同 步第9页/共36页 llsc原语的另一个状态：读写操作明显分开。Ll不产生总线数据传送，这使下面代码与使用经 过优化交换的代码具有相同的特点：lockitlockit：ll R2ll R2，0(R1)0(R1)；load-linked bnez R2 bnez R2，lockit lockit ；锁无效 li R2,li R2,，1 1 ；加锁值 sc R2sc R2，0(R1)0(R1)；存 beqz R2beqz R2，lockit lockit ；如存失败转移第一个分支形成环绕的循环体，第二个分支解决了两个同时请求锁的处理器竞争问题。尽管
10、旋转锁机制简单并且具有强制性，但难以将它扩展到处理器数量很多的情况。7.5 同 步第10页/共36页7.5.3 同步性能问题q 简单旋转锁不能很好地适应可伸缩性。大规模机器 中所有的处理器会产生出大量的竞争问题。例7.37.3：设总线上有1010个处理器同时准备对同一变量加锁。假设每个总线事务处理(读失效或写失效)是100100个时钟周期，忽略实际的CacheCache块锁的读写时间以及加锁的时间，求1010个处理器请求加锁所需的总线事务数目。设时间为0 0时锁已释放并且所有处理器在旋转，求处理这1010个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。7
11、.5 同 步第11页/共36页解 当i i个处理器竞争锁的时候，他们完成下列操作序列，每一个操作产生一个总线事务：访问该锁的i i个LLLL指令操作；试图锁住该锁的i i个SCSC指令操作；1 1个释放锁的存操作指令。因此对n n个处理器，总线事务的总和为：n n (2i+1)=n(n+1)+n=n2+2n(2i+1)=n(n+1)+n=n2+2n i=1 i=1对于1010个处理器有120120个总线事务，需要1200012000个时钟周期。7.5 同 步第12页/共36页 本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。旋转锁的主要优点:对于总线或网络开销较低7.5
12、同 步第13页/共36页q 并行循环的程序中另一个常用的同步操作:栅栏 栅栏强制所有到达的进程进行等待，直到全部的 进程到达栅栏，然后释放全部的进程，从而形成同步。栅栏的典型实现 用两个旋转锁 (1)(1)用来记录到达栅栏的进程数 (2)(2)用来封锁进程直至最后一个进程到达栅栏 栅栏的实现要不停地探测指定的变量，直到它满足规定的条件。一种典型的实现，其中lock和unlock提供基本的 旋转锁，total是要到达栅栏的进程总数。7.5 同 步第14页/共36页Lock(counterlock)Lock(counterlock)；*确保更新的原子性*if(count=0)release=0if
13、(count=0)release=0；*第一个进程则重置release*release*count=count+1count=count+1；*到达进程记数*unlock(counterlock)unlock(counterlock)；*释放锁*if(count=total)if(count=total)*进程全部到达*count=0count=0；*重置计数器*release=1release=1；*释放进程*else else *还有进程未到达*spin(release=1)spin(release=1)；*等待别的进程到达*7.5 同 步第15页/共36页 对counterlockcou
14、nterlock加锁保证增量操作的原子性，变 量 countcount记录着已到达栅栏的进程数，变量 releaserelease用来封锁进程直到最后一个进程到达栅栏。实际情况中会出现的问题 可能反复使用一个栅栏，栅栏释放的进程运行 一段后又会再次返回栅栏，这样有可能出现某个进 程永远离不开栅栏的状况(它停在旋转操作上)。7.5 同 步第16页/共36页 例如：OSOS调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开。这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达不到totaltotal。7.5 同 步第17页/共36页q 一
15、种解决方法 当进程离开栅栏时进行计数，在上次栅栏使用中 的所有进程离开之前不允许任何进程重用并初始化本 栅栏。q 另一种解决办法 sense_reversingsense_reversing栅栏，每个进程均使用一个私 有变量local_senselocal_sense，初始化为1 1。7.5 同 步第18页/共36页Local_sense=!Local_senseLocal_sense=!Local_sense；*local-senselocal-sense取反*lock(counterlock)lock(counterlock)；*确保增加的原子性*count+count+；*记算到达进程数
16、*unlock(counterlock)unlock(counterlock)；*解锁*if(count=total)if(count=total)*进程全部到达*count=0count=0；*重置计数器*release=local_senserelease=local_sense；*释放进程*else else *还有进程未到达*spin(release=local_sense)spin(release=local_sense)；*等待信号*7.5 同 步第19页/共36页例7.47.4 假设总线上1010个处理器同时执行一个栅栏，设每个总线事务需100100个时钟周期，忽略CacheCa
17、che块中锁的读、写实际花费的时间，以及栅栏实现中非同步操作的时间，计算1010个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?答：下表给出一个处理器通过栅栏发出的事件序列，设第一个获得总线的进程并未拥有锁。7.5 同 步第20页/共36页表7.6 7.6 第i i个处理器通过栅栏产生的事件序列 事件 数量 对应源代码 说明LL i Lock(counterlock)LL i Lock(counterlock)；所有处理器抢锁SC i Lock(counterlock)SC i Lock(counterlock)；所有处理器抢锁LD 1 count=
18、count+1LD 1 count=count+1；一个成功LL i-1 Lock(counterlock)LL i-1 Lock(counterlock)；不成功的处理器再次抢锁SD 1 count=count+1SD 1 count=count+1；获得专有访问产生的失效SD 1 unlock(counterlock)SD 1 unlock(counterlock)；获得锁产生的失效LD 2 spin(release=local_sense)LD 2 spin(release=local_sense)；读释放：初次和最后写产 生的失效7.5 同 步第21页/共36页q 当竞争不激烈且同步操
19、作较少时，我们主要关心的 是一个同步原语操作的延迟。基本的旋转锁操作可在两个总线周期内完成：基本的旋转锁操作可在两个总线周期内完成：一个读锁，一个写锁。我们可用多种方法改进形成一个读锁，一个写锁。我们可用多种方法改进形成 在一个单周期内完成操作。在一个单周期内完成操作。q 同步操作最严重的问题：进程的串行性 当出现竞争时，就会出现串行性问题。它极大 地增加了同步操作的时间。总线的使用是这个问题关键所在。总线的使用是这个问题关键所在。在基于目录的在基于目录的CacheCache一致性机器中，串行性问题也一致性机器中，串行性问题也 同样严重同样严重。7.5 同 步第22页/共36页7.5.4 大规
20、模机器的同步所希望的同步机制：在无竞争的条件下延迟较小 在竞争激烈时串行性小1.软件实现 旋转锁 (1)(1)旋转锁实现的主要问题 当多个进程检测并竞争锁时引起的延迟 (2)(2)一种解决办法:当加锁失败时就人为地推延 这些进程的等待时间。(3)(3)具有指数延迟的旋转锁代码7.5 同 步第23页/共36页 li R3li R3，1 1 ；R3R3初始延迟值；lockitlockit：ll R2ll R2，0(R1)0(R1)；load linkedload linked bnez R2 bnez R2，lockit lockit ；无效 addi R2addi R2，R2R2，1 1 ；取到
21、加锁值 sc R2sc R2，0(R1)0(R1)；store conditionalstore conditional bnez R2 bnez R2，gotit gotit ；存成功转移 sll R3sll R3，R3R3，1 1 ；将延迟时间增至2 2倍 pause R3 pause R3 ；延迟R3R3中时间值 j lockitj lockitgotitgotit：使用加锁保护的数据 当scsc失败时，进程推延R3R3个时间单位。7.5 同 步第24页/共36页 先讨论采用数组进行的软件实现。为此我们给出一种更好的栅栏实现代码。q 前面栅栏机制实现中，所有的进程必须读取 release
22、release标志，形成冲突。通过组合树来减小冲突q 组合树是多个请求在局部结合起来形成树的一 种分级结构。降低冲突的原因：将大冲突化解成为并行的多 个小冲突。锁实现的另一种技术是排队锁7.5 同 步第25页/共36页q 组合树采用预定义的n n叉树结构 用变量k k表示扇入数目，实际中k=4k=4效果较 好。当k k个进程都到达树的某个结点时，则发 信号进入树的上一层。q 当全部进程到达的信号汇集在根结点时，释放 所有的进程。q 采用sense_reversingsense_reversing技术来给出下面的基于 组合树的栅栏代码。7.5 同 步第26页/共36页struct node st
23、ruct node *组合树中一个结点*int counterlockint counterlock；int countint count ；int parentint parent；struct node tree struct node tree 0.p-10.p-1；*树中各结点*int local_senseint local_sense；int releaseint release；barrier(int mynode)barrier(int mynode)lock(treemynode.counterlock)lock(treemynode.counterlock)；*保护计数器*
24、count+count+；*计数的累加*unlock(treemynode.conterlock)unlock(treemynode.conterlock)；*解锁*if(treemynode.count=k)if(treemynode.count=k)*本结点全部到达*if(treemynode.parent)=0if(treemynode.parent)=0 barrier(treemynodebarrier(treemynode.parent).parent)；elseelserelease=local_senserelease=local_sense；treemynode.countt
25、reemynode.count0 0；*为下次重用初始化*else else spin(release=local_sense)spin(release=local_sense)；local_sense=!local_senselocal_sense=!local_sense；barrier(mynode)barrier(mynode)；7.5 同 步第27页/共36页2.硬件原语支持 介绍两种硬件同步原语：(1)排队锁 可以排队记录等待的进程，当锁释放时送 出一个已确定的等待进程。第一个针对锁 第二个针对栅栏和要求进行计数或提供明确索 引的某些用户级操作7.5 同 步第28页/共36页q 硬
26、件实现q 在基于目录的机器上，通过硬件向量等方式 来进行排队和同步控制。q 在基于总线的机器中要将锁从一个进程显式 地传给另一个进程，软件实现会更好一些。q 在第一次取锁变量失效时，失效被送入同步控 制器。同步控制器可集成在存储控制器中(基 于总线的系统)或集成在目录控制器中。q 排队锁的工作过程7.5 同 步第29页/共36页q 如果锁空闲，将其交给该处理器；如果锁忙，控制 器产生一个结点请求记录，并将锁忙的标志返回给 处理器，然后该处理器不停地进行检测。q 当该锁被释放时，控制器从等待的进程排队中选出 一个使用锁，这可以通过更新所选进程CacheCache中的 锁变量来完成。7.5 同 步
27、第30页/共36页例7.57.5 如果在排队锁的使用中，失效时进行锁更新，求1010个处理器完成locklock和unlockunlock所需的时间和总线事务数。假设条件与前面例子相同。解 对n n个处理器，每个处理器都初始加锁产生1 1个总线事务，其中1 1个成功获得锁并在使用后释放锁，第1 1个处理器将有n+1n+1个总线事务。每一个后续的处理器需要2 2个总线事务：1 1个获得锁 ，另1 1个释放锁。因此总线事务的总数为(n+1)+2(n-1)=3n-1(n+1)+2(n-1)=3n-1。注意这里的总线事务总数随处理器数量成线性增长，而不是前面旋转锁那样成二次方增长。对10 10 个处理
28、器，共需要2929个总线事务或29002900个时钟周期。7.5 同 步第31页/共36页q 首先，需要识别出对锁进行初次访问的进程，从而对其进行排队操作。q 第二，等待进程队列可通过多种机制实现，在 基于目录的机器中，队列为共享集合，需用类 似目录向量的硬件来实现排队锁的操作。q 最后，必须有硬件来回收锁，因为请求加锁的 进程可能被切换时切出，并且有可能在同一处 理器上不再被调度切入。q 排队锁功能实现中有一些要考虑的关键问题7.5 同 步第32页/共36页 为减少栅栏记数时所需的时间，从而减小瓶颈的串行度，引进一种原语Fetch_and_increment，它可以原子地取值并增量。使用fe
29、tch_and_increment可以很好地改进栅栏的实现。例7.67.6：写出fetch_and_incrementfetch_and_increment栅栏的代码。条件与前面假设相同，并设一次fetch_and_incrementfetch_and_increment操作也需100100个时钟周期。计算1010个处理器通过栅栏的时间，及所需的总线周期数。(2)栅栏实现7.5 同 步第33页/共36页解 下面的程序段给出栅栏的代码。对n n 个处理器，这种实现需要进行n n次fetch_and_incrementfetch_and_increment操作，访问countcount变量的n n
30、次cachecache失效和释放时的n n次CacheCache失效，这样总共需要3n3n个总线事务。对1010个处理器，总共需要3030个总线事务或30003000个时钟周期。这里如同排队锁那样，时间与处理器个数成线性增长。当然，实现组合树栅栏时也可采用fetch_and_incrementfetch_and_increment来降低树中每个结点的串行竞争。7.5 同 步第34页/共36页 local_sense=!local_senselocal_sense=!local_sense；*local_senselocal_sense变反*fetch-and-increment(count)fetch-and-increment(count)；*原子性更新*if(count=total)if(count=total)*进程全部到达*count=0count=0；*初始化计数器*release=local_senserelease=local_sense；*释放进程*else else *还有进程未到达*spin(releaze=local_sense)spin(releaze=local_sense)；*等待信号*7.5 同 步第35页/共36页感谢您的观看！第36页/共36页