同步通常是使用硬件提供的有关同步指令通过用户级软课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7.5 同 步,通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。,7.5.1 基本硬件原语,在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。,第章 多处理机,7.5 同 步第章 多处理机,1,功能：,将一个存储单元的值和一个寄存器的值,进行交换。建立一个锁，锁值为“0”表示开锁，为“1”表示上锁。,处理器加锁时，将对应于该锁的存储单元的值 交换为某个寄存器的值“1”。如果返回值为“0”，存储单元的值此时已置换为“1”，防止了别的进 程竞争该锁。,实现同步的关键:,操作的原子性,1.,典型操作:原子交换（atomic exchange）,7.5 同 步,功能：将一个存储单元的值和一个寄存器的值1.典型操作:原,2,2.,测试并置定（test_and_set）,先测试一个值，如果符合条件则修改其值。,3.,读取并加1（fetch_and_increment）,它返回存储单元的值并自动增加该值。,4.,使用指令对,LL(load linked或load locked)的取指令,SC(store conditional)的特殊存指令,7.5 同 步,2.测试并置定（test_and_set）LL(load,3,例,实现对由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 同 步,例实现对由R1指出的存储单元进行原子交换操作7.5 同 步,4,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 同 步,llsc机制的一个优点：可用来构造别的同步原语7.5 同,5,7.5.2 用一致性实现锁,采用多处理机的一致性机制来实现旋转锁。,旋转锁,处理器环绕一个锁不停地旋转而请求获得该锁。,1.,无Cache一致性机制,在存储器中保存锁变量，处理器可以不断地通,过一个原子操作请求加锁，比如先交换，再测试返,回值从而知道锁的状况。释放锁的时候，处理器可,简单地将锁置为“0”。,7.5 同 步,7.5.2 用一致性实现锁 采用多处理机的一致性机制来实现,6,li R2，1,lockit：exch R2,0(R1)；原子交换,bnez R2，lockit ；是否已加锁?,2.,机器支持Cache一致性,将锁缓冲进入Cache，并通过一致性机制使锁值保,持一致。,7.5 同 步,2.机器支持Cache一致性7.5 同 步,7,优点,可使“环绕”的进程对本地Cache块进行操作；,可利用锁访问的局部性，即处理器最近使用过,的锁不久又会使用。,改进旋转锁(获得第一条好处),使其环绕过程仅对本地Cache中锁的拷贝进行读，,直到它返回“0”确认锁可用，然后再进行加锁交换操,作。使用锁完毕后新竞争又开始进行。,7.5 同 步,可使“环绕”的进程对本地Cache块进行操作；改进,8,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 同 步,lockit：lw R2，0(R1)；取锁,9,表7.5 三个处理机对锁的使用,步骤,处理器,P0,处理器,P1,处理器,P2,锁状态,总线/目录操作,1,占有锁,环绕测试lock=0,环绕测试lock=0,Shared,无,2,将锁置为0,（收到作废命令）,(,收到作废命令),Exclusive,P0发锁变量作废消息,3,Cache失效,Cache失效,Shared,总线/目录处理P2,Cache失效,锁从P0写回,4,总线/目录忙则等待,Lock=0,Shared,P2 Cache,失效处理,5,Lock=0,执行交换，导致,Cache失效,Shared,P1Cache,失效处理,6,执行交换，导致,Cache失效,交换完毕，返回0,置lock=1,Exclusive,总线/目录处理P2,Cache失效,发作废消息,7,交换完毕，返回1,进入关键处理段,Shared,总线/目录处理P2,Cache失效，写回,8,环绕测试lock=0,无,7.5 同 步,表7.5 三个处理机对锁的使用步骤,10,llsc原语的另一个状态：读写操作明显分开。,Ll,不产生总线数据传送，这使下面代码与使用经,过优化交换的代码具有相同的特点：,lockit：ll R2，0(R1)；,load-linked,bnez R2，lockit ；锁无效,li R2,，1 ；加锁值,sc R2，0(R1)；存,beqz R2，lockit ；如存失败转移,第一个分支形成环绕的循环体，第二个分支解决了两个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并且具有强制性，但难以将它扩展到处理器数量很多的情况。,7.5 同 步,llsc原语的另一个状态：读写操作明显分开。7.5 同,11,7.5.3 同步性能问题,简单旋转锁不能很好地适应可伸缩性。大规模机器,中所有的处理器会产生出大量的竞争问题。,例7.3：,设总线上有10个处理器同时准备对同一变量加锁。假设每个总线事务处理(读失效或写失效)是100个时钟周期，忽略实际的Cache块锁的读写时间以及加锁的时间，求10个处理器请求加锁所需的总线事务数目。设时间为0时锁已释放并且所有处理器在旋转，求处理这10个请求时间为多长?假设总线在新的请求到达之前已服务完挂起的所有请求，并且处理器速度相同。,7.5 同 步,7.5.3 同步性能问题7.5 同 步,12,解,当i个处理器竞争锁的时候，他们完成下列操作序列，每一个操作产生一个总线事务：,访问该锁的i个LL指令操作；,试图锁住该锁的i个SC指令操作；,1个释放锁的存操作指令。,因此对n个处理器，总线事务的总和为：,n,(2i+1)=n(n+1)+n=n2+2n,i=1,对于,10,个处理器有,120,个总线事务，需要,12000,个时钟周期。,7.5 同 步,解 当i个处理器竞争锁的时候，他们完成下列操作序列，每一个,13,本例中,问题的根源,是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。,旋转锁的,主要优点:,对于总线或网络开销较低,7.5 同 步,本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总,14,并行循环的程序中另一个常用的同步操作:,栅栏,栅栏强制所有到达的进程进行等待，直到全部的,进程到达栅栏，然后释放全部的进程，从而形成同步。,栅栏的典型实现,用两个旋转锁,(1)用来记录到达栅栏的进程数,(2)用来封锁进程直至最后一个进程到达栅栏,栅栏的实现要不停地探测指定的变量，,直到它满足规定的条件。,一种典型的实现，其中lock和unlock提供基本的,旋转锁，total是要到达栅栏的进程总数。,7.5 同 步,并行循环的程序中另一个常用的同步操作:栅栏 栅栏的典型实,15,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 同 步,Lock(counterlock)；*,16,对counterlock加锁保证增量操作的原子性，变,量 count记录着已到达栅栏的进程数，变量,release用来封锁进程直到最后一个进程到达栅栏。,实际情况中会出现的问题,可能反复使用一个栅栏，栅栏释放的进程运行,一段后又会再次返回栅栏，这样有可能出现某个进,程永远离不开栅栏的状况(它停在旋转操作上)。,7.5 同 步,对counterlock加锁保证增量,17,例如：,OS调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开。这样所有的进程在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达不到total。,7.5 同 步,例如：OS调度进程，可能一个进程速度较快，当它第二次,18,一种解决方法,当进程离开栅栏时进行计数，在上次栅栏使用中,的所有进程离开之前不允许任何进程重用并初始化本,栅栏。,另一种解决办法,sense_reversing栅栏，每个进程均使用一个私,有变量local_sense，初始化为1。,7.5 同 步,一种解决方法7.5 同 步,19,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.5 同 步,20,例7.4,假设总线上10个处理器同时执行一个栅栏，设每个总线事务需100个时钟周期，忽略Cache块中锁的读、写实际花费的时间，以及栅栏实现中非同步操作的时间，计算10个处理器全部到达栅栏，被释放及离开栅栏所需的总线事务数。设总线完全公平，整个过程需多长时间?,答：,下表给出一个处理器通过栅栏发出的事件序列，设第一个获得总线的进程并未拥有锁。,7.5 同 步,例7.4 假设总线上10个处理器同时执行一个栅栏，设每个总线,21,表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 同 步,表7.6 第i个处理器通过栅栏产生的事件,22,当竞争不激烈且同步操作较少时，我们主要关心的,是一个同步原语操作的延迟。,基本的旋转锁操作可在两个总线周期内完成：,一个读锁，一个写锁。我们可用多种方法改进形成,在一个单周期内完成操作。,同步操作,