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