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

2006年2月@秦杰 郑丽萍 张庆辉7.5 同 步 通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的 7.5.1 基本硬件原语 在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语它们能够自动读／修改单元通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数 第７章 多处理机12006年2月@秦杰 郑丽萍 张庆辉Ø 功能：将一个存储单元的值和一个寄存器的值 进行交换建立一个锁，锁值为“0”表示开锁， 为“1”表示上锁Ø 处理器加锁时，将对应于该锁的存储单元的值 交换为某个寄存器的值“1”如果返回值为“0”， 存储单元的值此时已置换为“1”，防止了别的进 程竞争该锁Ø 实现同步的关键: 操作的原子性1. 典型操作:原子交换（atomic exchange）7.5 同 步22006年2月@秦杰 郑丽萍 张庆辉2. 测试并置定（test_and_set） 先测试一个值，如果符合条件则修改其值先测试一个值，如果符合条件则修改其值3. 读取并加1（fetch_and_increment） 它返回存储单元的值并自动增加该值。

它返回存储单元的值并自动增加该值4. 使用指令对q LL(load linkedLL(load linked或或load locked)load locked)的取指令的取指令q SC(store conditional)SC(store conditional)的特殊存指令的特殊存指令7.5 同 步32006年2月@秦杰 郑丽萍 张庆辉例例　实现对由　实现对由R1R1指出的存储单元进行原子交换操作指出的存储单元进行原子交换操作 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之之间间如如有有别别的的处处理理器器插插入入并并修修改改了了存存储储单单元元的的值值，，scsc将将返返回回“0”“0”并并存存入入R3R3中中，，从从而而使使指指令令序序列列再再重重新新循循环环。

7.5 同 步42006年2月@秦杰 郑丽萍 张庆辉Ø ll／sc机制的一个优点：可用来构造别的同步原语 例如：例如：原子的原子的fetch-and-incrementfetch-and-increment try try：： llll R2,0(R1) R2,0(R1) ；；load linkedload linked addiaddi R2,R2, R2,R2,＃＃1 1 ；；增加增加 sc R2,0(R1) sc R2,0(R1) ；；store conditionalstore conditional beqzbeqz R2,try R2,try ；；存失败转移存失败转移Ø 指令对的实现必须跟踪地址 由由llll指令指定一个寄存器，该寄存器存放着一个指令指定一个寄存器，该寄存器存放着一个 单元地址，这个寄存器常称为单元地址，这个寄存器常称为连接寄存器连接寄存器。

7.5 同 步52006年2月@秦杰 郑丽萍 张庆辉7.5.2 用一致性实现锁Ø 采用多处理机的一致性机制来实现旋转锁Ø 旋转锁 处理器环绕一个锁不停地旋转而请求获得该锁处理器环绕一个锁不停地旋转而请求获得该锁1. 无Cache一致性机制 在存储器中保存锁变量，处理器可以不断地通在存储器中保存锁变量，处理器可以不断地通 过一个原子操作请求加锁，比如先交换，再测试返过一个原子操作请求加锁，比如先交换，再测试返 回值从而知道锁的状况释放锁的时候，处理器可回值从而知道锁的状况释放锁的时候，处理器可 简单地将锁置为简单地将锁置为“0” “0” 7.5 同 步62006年2月@秦杰 郑丽萍 张庆辉 li R2 li R2，＃，＃1 1lockitlockit：： exch R2,0(R1) exch R2,0(R1) ；原子交换；原子交换 bnez R2 bnez R2，，lockit lockit ；是否已加锁；是否已加锁? ?2. 机器支持Cache一致性 将锁缓冲进入将锁缓冲进入CacheCache，并通过一致性机制使锁值保，并通过一致性机制使锁值保 持一致。

持一致 7.5 同 步72006年2月@秦杰 郑丽萍 张庆辉 Ø 优点q 可使可使““环绕环绕””的进程对本地的进程对本地CacheCache块进行操作；块进行操作；q 可利用锁访问的局部性，即处理器最近使用过可利用锁访问的局部性，即处理器最近使用过 的锁不久又会使用的锁不久又会使用Ø 改进旋转锁(获得第一条好处) 使其环绕过程仅对本地Cache中锁的拷贝进行读， 直到它返回“0”确认锁可用，然后再进行加锁交换操 作使用锁完毕后新竞争又开始进行7.5 同 步82006年2月@秦杰 郑丽萍 张庆辉 lockitlockit：：lw R2lw R2，，0(R1) 0(R1) ；取锁值；取锁值 bnez R2 bnez R2，，lockit lockit ；锁不可用；锁不可用 li R2 li R2，＃，＃1 1 ；存入锁值；存入锁值 exch R2 exch R2，，0(R1) 0(R1) ；交换；交换 bnez R2 bnez R2，，lockit ;lockit ;如锁不为如锁不为0 0转移转移 上上面面给给出出了了对对于于三三个个处处理理器器竞竞争争锁锁的的操操作作。

一一旦旦处处理理器器存存入入“0”“0”释释放放锁锁，，所所有有别别的的CacheCache对对应应块块均均被被作废，必须取新的值来更新它们锁的拷贝作废，必须取新的值来更新它们锁的拷贝 一一个个处处理理器器CacheCache会会先先获获得得未未加加锁锁值值并并执执行行交交换换操操作作，，当当别别的的CacheCache失失效效处处理理完完后后，，它它们们会会发发现现已已被被加加锁锁，，所以又必须不停地测试环绕所以又必须不停地测试环绕7.5 同 步92006年2月@秦杰 郑丽萍 张庆辉表表7.5 7.5 三个处理机对锁的使用三个处理机对锁的使用步骤步骤 处理器处理器P0处理器处理器P1处理器处理器P2锁状态锁状态总线总线/目录操作目录操作1占有锁占有锁环绕测试环绕测试lock=0环绕测试环绕测试lock=0Shared无无2将将锁锁置置为为0（收到作废命令）（收到作废命令）(收收到到作作废废命命令令)ExclusiveP0发锁变量作废消息发锁变量作废消息3Cache失效失效Cache失效失效Shared总总线线/目目录录处处理理P2 Cache失效失效,锁从锁从P0写回写回4总总线线/目目录录忙忙则则等等待待Lock=0SharedP2 Cache失效处理失效处理5Lock=0执执行行交交换换，，导导致致 Cache失效失效SharedP1Cache失效处理失效处理6执行交换，导致执行交换，导致 Cache失效失效 交交换换完完毕毕，，返返回回0置置lock=1Exclusive总总线线/目目录录处处理理P2 Cache失效失效,发作废消息发作废消息7交换完毕，返回交换完毕，返回1进进入入关关键键处处理理段段Shared总总线线/目目录录处处理理P2 Cache失效，写回失效，写回8环绕测试环绕测试lock=0无无7.5 同 步102006年2月@秦杰 郑丽萍 张庆辉Ø ll／sc原语的另一个状态：读写操作明显分开。

Ll不产生总线数据传送，这使下面代码与使用经不产生总线数据传送，这使下面代码与使用经 过优化交换的代码具有相同的特点：过优化交换的代码具有相同的特点： lockitlockit：： llll R2 R2，，0(R1) 0(R1) ；；load-linked bnezbnez R2 R2，，lockitlockit ；；锁无效锁无效 lili R2, R2,，＃，＃1 1 ；；加锁值加锁值 sc R2sc R2，，0(R1) 0(R1) ；；存存 beqzbeqz R2 R2，，lockitlockit ；；如存失败转移如存失败转移 第第一一个个分分支支形形成成环环绕绕的的循循环环体体，，第第二二个个分分支支解解决决了了两两个个同同时时请请求求锁锁的的处处理理器器竞竞争争问问题题。

尽尽管管旋旋转转锁锁机机制制简简单单并并且具有强制性，但难以将它扩展到处理器数量很多的情况且具有强制性，但难以将它扩展到处理器数量很多的情况7.5 同 步112006年2月@秦杰 郑丽萍 张庆辉7.5.3 同步性能问题q 简单旋转锁不能很好地适应可伸缩性大规模机器 中所有的处理器会产生出大量的竞争问题 例例7.37.3：：设设总总线线上上有有1010个个处处理理器器同同时时准准备备对对同同一一变变量量加加锁锁假假设设每每个个总总线线事事务务处处理理( (读读失失效效或或写写失失效效) )是是100100个个时时钟钟周周期期，，忽忽略略实实际际的的CacheCache块块锁锁的的读读写写时时间间以以及及加加锁锁的的时时间间，，求求1010个个处处理理器器请请求求加加锁锁所所需需的的总总线线事事务务数数目目设设时时间间为为0 0时时锁锁已已释释放放并并且且所所有有处处理理器器在在旋旋转转，，求求处处理理这这1010个个请请求求时时间间为为多多长长? ?假假设设总总线线在在新新的的请请求求到到达达之之前前已已服服务务完完挂挂起起的的所所有有请请求求，，并并且且处处理理器器速速度度相相同。

同7.5 同 步122006年2月@秦杰 郑丽萍 张庆辉解解 当当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 同 步132006年2月@秦杰 郑丽萍 张庆辉 本本例例中中问问题题的的根根源源是是锁锁的的竞竞争争、、存存储储器器中中锁锁访访问问的串行性以及总线访问的延迟。

的串行性以及总线访问的延迟 旋转锁的旋转锁的主要优点主要优点: 对于总线或网络开销较低对于总线或网络开销较低7.5 同 步142006年2月@秦杰 郑丽萍 张庆辉q 并行循环的程序中另一个常用的同步操作: 栅栏 栅栏强制所有到达的进程进行等待，直到全部的栅栏强制所有到达的进程进行等待，直到全部的 进程到达栅栏，然后释放全部的进程，从而形成同步进程到达栅栏，然后释放全部的进程，从而形成同步Ø 栅栏的典型实现 用两个旋转锁用两个旋转锁 (1) (1) 用来记录到达栅栏的进程数用来记录到达栅栏的进程数 (2) (2) 用来封锁进程直至最后一个进程到达栅栏用来封锁进程直至最后一个进程到达栅栏 栅栏的实现要不停地探测指定的变量，栅栏的实现要不停地探测指定的变量， 直到它满足规定的条件直到它满足规定的条件Ø 一种典型的实现，其中lock和unlock提供基本的 旋转锁，total是要到达栅栏的进程总数7.5 同 步152006年2月@秦杰 郑丽萍 张庆辉Lock(counterlock)Lock(counterlock)；； ／／* *确保更新的原子性确保更新的原子性* *／／if(count=0) release=0if(count=0) release=0；； ／／* *第一个进程则重置第一个进程则重置release*release*／／count=count+1count=count+1；； ／／* *到达进程记数到达进程记数* *／／unlock(counterlock)unlock(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 同 步162006年2月@秦杰 郑丽萍 张庆辉 对对counterlockcounterlock加锁保证增量操作的原子性，变加锁保证增量操作的原子性，变 量量 count count记录着已到达栅栏的进程数，变量记录着已到达栅栏的进程数，变量 release release用来封锁进程直到最后一个进程到达栅栏。

用来封锁进程直到最后一个进程到达栅栏Ø 实际情况中会出现的问题 可能反复使用一个栅栏，栅栏释放的进程运行可能反复使用一个栅栏，栅栏释放的进程运行 一段后又会再次返回栅栏，这样有可能出现某个进一段后又会再次返回栅栏，这样有可能出现某个进 程永远离不开栅栏的状况程永远离不开栅栏的状况( (它停在旋转操作上它停在旋转操作上) )7.5 同 步172006年2月@秦杰 郑丽萍 张庆辉 例如：例如：OSOS调度进程，可能一个进程速度较快，调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开这样所有的进程在这个栅栏的第二次中未能离开这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达使用中都处于无限等待状态，因为进程的数目永达不到不到totaltotal7.5 同 步182006年2月@秦杰 郑丽萍 张庆辉q 一种解决方法一种解决方法 当进程离开栅栏时进行计数，在上次栅栏使用中当进程离开栅栏时进行计数，在上次栅栏使用中 的所有进程离开之前不允许任何进程重用并初始化本的所有进程离开之前不允许任何进程重用并初始化本 栅栏。

栅栏q 另一种解决办法另一种解决办法 sense_reversingsense_reversing栅栏，每个进程均使用一个私栅栏，每个进程均使用一个私 有变量有变量local_senselocal_sense，，初始化为初始化为1 17.5 同 步192006年2月@秦杰 郑丽萍 张庆辉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 count=0；； ／／* *重置计数器重置计数器* *／／ release=local_sense release=local_sense；； ／／* *释放进程释放进程* *／／ ｝｝else { else { ／／* *还有进程未到达还有进程未到达* *／／ spin(release=local_sense) spin(release=local_sense)；； ／／* *等待信号等待信号* *／／ ｝｝ 7.5 同 步202006年2月@秦杰 郑丽萍 张庆辉例例7.47.4 假假设设总总线线上上1010个个处处理理器器同同时时执执行行一一个个栅栅栏栏，，设设每每个个总总线线事事务务需需100100个个时时钟钟周周期期，，忽忽略略CacheCache块块中中锁锁的的读读、、写写实实际际花花费费的的时时间间，，以以及及栅栅栏栏实实现现中中非非同同步步操操作作的的时时间间，，计计算算1010个个处处理理器器全全部部到到达达栅栅栏栏，，被被释释放放及及离离开开栅栅栏栏所所需需的的总总线线事事务务数数。

设设总总线线完完全全公公平平，，整整个个过过程程需需多多长长时时间间? ?答答：：下下表表给给出出一一个个处处理理器器通通过过栅栅栏栏发发出出的的事事件件序序列列，，设设第一个获得总线的进程并未拥有锁第一个获得总线的进程并未拥有锁7.5 同 步212006年2月@秦杰 郑丽萍 张庆辉 表表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=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 同 步222006年2月@秦杰 郑丽萍 张庆辉q 当竞争不激烈且同步操作较少时，我们主要关心的 是一个同步原语操作的延迟。

基本的旋转锁操作可在两个总线周期内完成：基本的旋转锁操作可在两个总线周期内完成： 一个读锁，一个写锁我们可用多种方法改进形成一个读锁，一个写锁我们可用多种方法改进形成 在一个单周期内完成操作在一个单周期内完成操作q 同步操作最严重的问题：进程的串行性 当出现竞争时，就会出现串行性问题它极大 地增加了同步操作的时间Ø 总线的使用是这个问题关键所在总线的使用是这个问题关键所在Ø 在基于目录的在基于目录的CacheCache一致性机器中，串行性问题也一致性机器中，串行性问题也 同样严重同样严重7.5 同 步232006年2月@秦杰 郑丽萍 张庆辉7.5.4 大规模机器的同步所希望的同步机制：在无竞争的条件下延迟较小 在竞争激烈时串行性小1. 软件实现Ø 旋转锁 (1) (1) 旋转锁实现的旋转锁实现的主要问题主要问题 当多个进程检测并竞争锁时引起的延迟当多个进程检测并竞争锁时引起的延迟 (2) (2) 一种解决办法一种解决办法: : 当加锁失败时就人为地推延当加锁失败时就人为地推延 这些进程的等待时间。

这些进程的等待时间 (3) (3) 具有指数延迟的旋转锁代码具有指数延迟的旋转锁代码7.5 同 步242006年2月@秦杰 郑丽萍 张庆辉 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 gotit ；存成功转移；存成功转移 sll R3 sll R3，，R3R3，，1 1 ；将延迟时间增至；将延迟时间增至2 2倍倍 pause R3 pause R3 ；延迟；延迟R3R3中时间值中时间值 j lockit j lockitgotitgotit：： 使用加锁保护的数据使用加锁保护的数据 当当scsc失败时，进程推延失败时，进程推延R3R3个时间单位。

个时间单位7.5 同 步252006年2月@秦杰 郑丽萍 张庆辉 先讨论采用数组进行的软件实现为此我们给出一种更好的栅栏实现代码q 前面栅栏机制实现中，所有的进程必须读取前面栅栏机制实现中，所有的进程必须读取 releaserelease标志，形成冲突标志，形成冲突 通过组合树来减小冲突通过组合树来减小冲突q 组合树是多个请求在局部结合起来形成树的一组合树是多个请求在局部结合起来形成树的一 种分级结构种分级结构 降低冲突的原因：将大冲突化解成为并行的多降低冲突的原因：将大冲突化解成为并行的多 个小冲突个小冲突 Ø 锁实现的另一种技术是排队锁7.5 同 步262006年2月@秦杰 郑丽萍 张庆辉q 组合树采用预定义的组合树采用预定义的n n叉树结构叉树结构 用变量用变量k k表示扇入数目，实际中表示扇入数目，实际中k=4k=4效果较效果较 好当k k个进程都到达树的某个结点时，则发个进程都到达树的某个结点时，则发 信号进入树的上一层。

信号进入树的上一层q 当全部进程到达的信号汇集在根结点时，释当全部进程到达的信号汇集在根结点时，释放放 所有的进程所有的进程q 采用采用sense_reversingsense_reversing技术来给出下面的基于技术来给出下面的基于 组合树的栅栏代码组合树的栅栏代码7.5 同 步272006年2月@秦杰 郑丽萍 张庆辉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_sense int local_sense；；int releaseint release；； barrier(int mynode) barrier(int mynode) ｛｛ lock(tree[mynode].counterlock) lock(tree[mynode].counterlock)；／；／* *保护计数器保护计数器* *／／ count++ count++；； ／／* *计数的累加计数的累加* *／／ unlock(tree[mynode].conterlock) unlock(tree[mynode].conterlock)；／；／* *解锁解锁* *／／ if(tree[mynode].count==k) if(tree[mynode].count==k)｛｛ ／／* *本结点全部到达本结点全部到达* *／／ if(tree[mynode].parent)>=0 if(tree[mynode].parent)>=0｛｛ barrier(tree[mynode barrier(tree[mynode］］.parent).parent)；； ｝｝elseelse｛｛release=local_senserelease=local_sense；； ｝｝ tree[mynode].count tree[mynode].count＝＝0 0；｝；｝ ／／* *为下次重用初始化为下次重用初始化* *／／ else else ｛｛ spin(release=local_sense) spin(release=local_sense)；｝；｝；；｝；｝； local_sense= ! local_sense local_sense= ! local_sense；；barrier (mynode)barrier (mynode)；；7.5 同 步282006年2月@秦杰 郑丽萍 张庆辉2. 硬件原语支持 介绍两种硬件同步原语：(1) 排队锁 可以排队记录等待的进程，当锁释放时送 出一个已确定的等待进程。

Ø 第一个针对锁Ø 第二个针对栅栏和要求进行计数或提供明确索 引的某些用户级操作7.5 同 步292006年2月@秦杰 郑丽萍 张庆辉q 硬件实现q 在基于目录的机器上，通过硬件向量等方在基于目录的机器上，通过硬件向量等方式式 来进行排队和同步控制来进行排队和同步控制q 在基于总线的机器中要将锁从一个进程显在基于总线的机器中要将锁从一个进程显式式 地传给另一个进程，软件实现会更好一些地传给另一个进程，软件实现会更好一些q 在第一次取锁变量失效时，失效被送入同步在第一次取锁变量失效时，失效被送入同步控控 制器同步控制器可集成在存储控制器中制器同步控制器可集成在存储控制器中( (基基 于总线的系统于总线的系统) )或集成在目录控制器中或集成在目录控制器中q 排队锁的工作过程7.5 同 步302006年2月@秦杰 郑丽萍 张庆辉q 如果锁空闲，将其交给该处理器；如果锁忙，控如果锁空闲，将其交给该处理器；如果锁忙，控制制 器产生一个结点请求记录，并将锁忙的标志返回给器产生一个结点请求记录，并将锁忙的标志返回给 处理器，然后该处理器不停地进行检测。

处理器，然后该处理器不停地进行检测q 当该锁被释放时，控制器从等待的进程排队中选当该锁被释放时，控制器从等待的进程排队中选出出 一个使用锁，这可以通过更新所选进程一个使用锁，这可以通过更新所选进程CacheCache中的中的 锁变量来完成锁变量来完成7.5 同 步312006年2月@秦杰 郑丽萍 张庆辉例例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 个处理器，共需要个处理器，共需要2929个总个总线事务或线事务或29002900个时钟周期个时钟周期7.5 同 步322006年2月@秦杰 郑丽萍 张庆辉q 首先，需要识别出对锁进行初次访问的进程，首先，需要识别出对锁进行初次访问的进程， 从而对其进行排队操作从而对其进行排队操作q 第二，等待进程队列可通过多种机制实现，在第二，等待进程队列可通过多种机制实现，在 基于目录的机器中，队列为共享集合，需用类基于目录的机器中，队列为共享集合，需用类 似目录向量的硬件来实现排队锁的操作似目录向量的硬件来实现排队锁的操作q 最后，必须有硬件来回收锁，因为请求加锁的最后，必须有硬件来回收锁，因为请求加锁的 进程可能被切换时切出，并且有可能在同一处进程可能被切换时切出，并且有可能在同一处 理器上不再理器上不再被调度切入被调度切入 q 排队锁功能实现中有一些要考虑的关键问题7.5 同 步332006年2月@秦杰 郑丽萍 张庆辉 为减少栅栏记数时所需的时间，从而减小瓶颈的串行度，引进一种原语Fetch_and_increment，它可以原子地取值并增量。

使用fetch_and_increment可以很好地改进栅栏的实现例例7.67.6：：写出写出fetch_and_incrementfetch_and_increment栅栏的代码条件栅栏的代码条件与前面假设相同，并设一次与前面假设相同，并设一次fetch_and_incrementfetch_and_increment操操作也需作也需100100个时钟周期计算个时钟周期计算1010个处理器通过栅栏的个处理器通过栅栏的时间，及所需的总线周期数时间，及所需的总线周期数2) 栅栏实现7.5 同 步342006年2月@秦杰 郑丽萍 张庆辉解解 下下面面的的程程序序段段给给出出栅栅栏栏的的代代码码对对n n 个个处处理理器器，，这这种种实实现现需需要要进进行行n n次次fetch_and_incrementfetch_and_increment操操作作，，访访问问countcount变变量量的的n n次次cachecache失失效效和和释释放放时时的的n n次次CacheCache失失效效，，这这样样总总共共需需要要3n3n个个总总线线事事务务对对1010个个处处理理器器，，总总共共需需要要3030个个总总线线事事务务或或30003000个个时时钟钟周周期期。

这这里里如如同同排排队锁那样，时间与处理器个数成线性增长队锁那样，时间与处理器个数成线性增长 当当 然然 ，， 实实 现现 组组 合合 树树 栅栅 栏栏 时时 也也 可可 采采 用用fetch_and_incrementfetch_and_increment来来降降低低树树中中每每个个结结点点的的串串行行竞竞争7.5 同 步352006年2月@秦杰 郑丽萍 张庆辉 local_sense= ! local_senselocal_sense= ! local_sense；； ／／*local_sense*local_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 同 步36。