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

7.5同步通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。7.5.1基本硬件原语在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。,第章多处理机,功能：将一个存储单元的值和一个寄存器的值进行交换。建立一个锁，锁值为“0”表示开锁，为“1”表示上锁。处理器加锁时，将对应于该锁的存储单元的值交换为某个寄存器的值“1”。如果返回值为“0”，存储单元的值此时已置换为“1”，防止了别的进程竞争该锁。实现同步的关键:操作的原子性,1.典型操作:原子交换（atomicexchange）,7.5同步,2.测试并置定（test_and_set）先测试一个值，如果符合条件则修改其值。3.读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。4.使用指令对,LL(loadlinked或loadlocked)的取指令SC(storeconditional)的特殊存指令,7.5同步,例实现对由R1指出的存储单元进行原子交换操作try：movR3,R4；送交换值llR2,0(R1)；loadlinkedscR3,0(R1)；storeconditionalbeqzR3,try；存失败转移movR4,R2；将取的值送往R4最终R4和由R1指向的单元值进行原子交换，在ll和sc之间如有别的处理器插入并修改了存储单元的值，sc将返回“0”并存入R3中，从而使指令序列再重新循环。,7.5同步,llsc机制的一个优点：可用来构造别的同步原语例如：原子的fetch-and-incrementtry：llR2,0(R1)；loadlinkedaddiR2,R2,1；增加scR2,0(R1)；storeconditionalbeqzR2,try；存失败转移指令对的实现必须跟踪地址由ll指令指定一个寄存器，该寄存器存放着一个单元地址，这个寄存器常称为连接寄存器。,7.5同步,7.5.2用一致性实现锁,采用多处理机的一致性机制来实现旋转锁。旋转锁处理器环绕一个锁不停地旋转而请求获得该锁。,1.无Cache一致性机制在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁置为“0”。,7.5同步,liR2，1lockit：exchR2,0(R1)；原子交换bnezR2，lockit；是否已加锁?,2.机器支持Cache一致性将锁缓冲进入Cache，并通过一致性机制使锁值保持一致。,7.5同步,优点,可使“环绕”的进程对本地Cache块进行操作；可利用锁访问的局部性，即处理器最近使用过的锁不久又会使用。,改进旋转锁(获得第一条好处)使其环绕过程仅对本地Cache中锁的拷贝进行读，直到它返回“0”确认锁可用，然后再进行加锁交换操作。使用锁完毕后新竞争又开始进行。,7.5同步,lockit：lwR2，0(R1)；取锁值bnezR2，lockit；锁不可用liR2，1；存入锁值exchR2，0(R1)；交换bnezR2，lockit;如锁不为0转移上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0”释放锁，所有别的Cache对应块均被作废，必须取新的值来更新它们锁的拷贝。一个处理器Cache会先获得未加锁值并执行交换操作，当别的Cache失效处理完后，它们会发现已被加锁，所以又必须不停地测试环绕。,7.5同步,表7.5三个处理机对锁的使用,7.5同步,llsc原语的另一个状态：读写操作明显分开。Ll不产生总线数据传送，这使下面代码与使用经过优化交换的代码具有相同的特点：lockit：llR2，0(R1)；load-linkedbnezR2，lockit；锁无效liR2,，1；加锁值scR2，0(R1)；存beqzR2，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+2ni=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个处理器通过栅栏产生的事件序列事件数量对应源代码说明LLiLock(counterlock)；所有处理器抢锁SCiLock(counterlock)；所有处理器抢锁LD1count=count+1；一个成功LLi-1Lock(counterlock)；不成功的处理器再次抢锁SD1count=count+1；获得专有访问产生的失效SD1unlock(counterlock)；获得锁产生的失效LD2spin(release=local_sense)；读释放：初次和最后写产生的失效,7.5同步,当竞争不激烈且同步操作较少时，我们主要关心的是一个同步原语操作的延迟。基本的旋转锁操作可在两个总线周期内完成：一个读锁，一个写锁。我们可用多种方法改进形成在一个单周期内完成操作。同步操作最严重的问题：进程的串行性当出现竞争时，就会出现串行性问题。它极大地增加了同步操作的时间。总线的使用是这个问题关键所在。在基于目录的Cache一致性机器中，串行性问题也同样严重。,7.5同步,7.5.4大规模机器的同步所希望的同步机制：在无竞争的条件下延迟较小在竞争激烈时串行性小1.软件实现旋转锁(1)旋转锁实现的主要问题当多个进程检测并竞争锁时引起的延迟(2)一种解决办法:当加锁失败时就人为地推延这些进程的等待时间。(3)具有指数延迟的旋转锁代码,7.5同步,liR3，1；R3初始延迟值；lockit：llR2，0(R1)；loadlinkedbnezR2，lockit；无效addiR2，R2，1；取到加锁值scR2，0(R1)；storeconditionalbnezR2，gotit；存成功转移sllR3，R3，1；将延迟时间增至2倍pauseR3；延迟R3中时间值jlockitgotit：使用加锁保护的数据当sc失败时，进程推延R3个时间单位。,7.5同步,先讨论采用数组进行的软件实现。为此我们给出一种更好的栅栏实现代码。前面栅栏机制实现中，所有的进程必须读取release标志，形成冲突。通过组合树来减小冲突组合树是多个请求在局部结合起来形成树的一种分级结构。降低冲突的原因：将大冲突化解成为并行的多个小冲突。,锁实现的另一种技术是排队锁,7.5同步,组合树采用预定义的n叉树结构用变量k表示扇入数目，实际中k=4效果较好。当k个进程都到达树的某个结点时，则发信号进入树的上一层。当全部进程到达的信号汇集在根结点时，释放所有的进程。采用sense_reversing技术来给出下面的基于组合树的栅栏代码。,7.5同步,structnode*组合树中一个结点*intcounterlock；intcount；intparent；structnodetree0.p-1；*树中各结点*intlocal_sense；intrelease；barrier(intmynode)lock(treemynode.counterlock)；*保护计数器*count+；*计数的累加*unlock(treemynode.conterlock)；*解锁*if(treemynode.count=k)*本结点全部到达*if(treemynode.parent)=0barrier(treemynode.parent)；elserelease=local_sense；treemynode.count0；*为下次重用初始化*elsespin(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同步,