通常是使用硬件提供的有关同步指令.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，1 lockit： 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 lockit gotit： 使用加锁保护的数据 当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 0p-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 同 步,首先，需要识别出对锁进行初次访问的进程， 从而对其进行排队操作。 第二，等待进程队列可通过多种机制实现，在 基于目录的机器中，队列为共享集合，需用类 似目录向量的硬件来实现排队锁的操作。 最后，必须有硬件来回收锁，因为请求加锁的 进程可能被切换时切出，并且有可能在同一处 理器上不再被调度切入。,排