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

《通常是使用硬件提供的有关同步指令》由会员分享，可在线阅读，更多相关《通常是使用硬件提供的有关同步指令（36页珍藏版）》请在金锄头文库上搜索。

1、2006年2月秦杰 郑丽萍 张庆辉7.5 同 步通常是使用硬件提供的有关同步指令，通过用户级软件例程建立的。7.5.1 基本硬件原语在多处理器同步中，主要功能是一组能自动读出后并进行写存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。第章 多处理机2006年2月秦杰 郑丽萍 张庆辉 功能：将一个存储单元的值和一个寄存器的值进行交换。建立一个锁，锁值为“0”表示开锁，为“1”表示上锁。 处理器加锁时，将对应于该锁的存储单元的值交换为某个寄存器的值“1”。如果返回值为“0”，存储单元的值此时已置换为“1”，防止了别的进程竞

2、争该锁。 实现同步的关键: 操作的原子性1. 典型操作:原子交换（atomic exchange）7.5 同 步2006年2月秦杰 郑丽萍 张庆辉2. 测试并置定（test_and_set）先测试一个值，如果符合条件则修改其值。3. 读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。4. 使用指令对q LL(load linked或load locked)的取指令q SC(store conditional)的特殊存指令7.5 同 步2006年2月秦杰 郑丽萍 张庆辉例 实现对由R1指出的存储单元进行原子交换操作try：mov R3,R4 ；送交换值ll R

3、2,0(R1) ；load linkedsc R3,0(R1) ；store conditionalbeqz R3,try ；存失败转移mov R4,R2 ；将取的值送往R4 最终R4和由R1指向的单元值进行原子交换，在ll和 sc之间如有别的处理器插入并修改了存储单元的值，sc 将返回“0”并存入R3中，从而使指令序列再重新循环 。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉 llsc机制的一个优点：可用来构造别的同步原语例如：原子的fetch-and-incrementtry： ll R2,0(R1) ；load linkedaddi R2,R2,1 ；增加sc R2,0(R1) ；s

4、tore conditionalbeqz R2,try ；存失败转移 指令对的实现必须跟踪地址由ll指令指定一个寄存器，该寄存器存放着一个 单元地址，这个寄存器常称为连接寄存器。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉7.5.2 用一致性实现锁 采用多处理机的一致性机制来实现旋转锁。 旋转锁处理器环绕一个锁不停地旋转而请求获得该锁。1. 无Cache一致性机制在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁置为“0” 。 7.5 同 步2006年2月秦杰 郑丽萍 张庆辉li R2，1 lockit

5、： exch R2,0(R1) ；原子交换bnez R2，lockit ；是否已加锁?2. 机器支持Cache一致性将锁缓冲进入Cache，并通过一致性机制使锁值保持一致。 7.5 同 步2006年2月秦杰 郑丽萍 张庆辉 优点q 可使“环绕”的进程对本地Cache块进行操作；q 可利用锁访问的局部性，即处理器最近使用过 的锁不久又会使用。 改进旋转锁(获得第一条好处)使其环绕过程仅对本地Cache中锁的拷贝进行读，直到它返回“0”确认锁可用，然后再进行加锁交换操作。使用锁完毕后新竞争又开始进行。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉lockit：lw R2，0(R1) ；取锁值bn

6、ez R2，lockit ；锁不可用li R2，1 ；存入锁值exch R2，0(R1) ；交换bnez R2，lockit ;如锁不为0转移 上面给出了对于三个处理器竞争锁的操作。一旦处理器存入“0”释放锁，所有别的Cache对应块均被 作废，必须取新的值来更新它们锁的拷贝。一个处理器Cache会先获得未加锁值并执行交换操 作，当别的Cache失效处理完后，它们会发现已被加锁 ，所以又必须不停地测试环绕。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉表7.5 三个处理机对锁的使用步骤 处理器P0处理器P1处理器P2锁状态总线/目录操作1占有锁环绕测试lock=0环绕测试lock=0Shar

7、ed无2将锁置为 0（收到作废命令 ）(收到作废命令)ExclusiveP0发锁变量作废消息3 Cache失效Cache失效Shared总线/目录处理P2 Cache失效,锁从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 同

8、步2006年2月秦杰 郑丽萍 张庆辉 llsc原语的另一个状态：读写操作明显分开。Ll不产生总线数据传送，这使下面代码与使用经过优化交换的代码具有相同的特点：lockit： ll R2，0(R1) ；load-linked bnez R2，lockit ；锁无效li R2,，1 ；加锁值sc R2，0(R1) ；存beqz R2，lockit ；如存失败转移 第一个分支形成环绕的循环体，第二个分支解决了两 个同时请求锁的处理器竞争问题。尽管旋转锁机制简单并 且具有强制性，但难以将它扩展到处理器数量很多的情况 。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉7.5.3 同步性能问题q 简单旋转

9、锁不能很好地适应可伸缩性。大规模机器 中所有的处理器会产生出大量的竞争问题。例7.3：设总线上有10个处理器同时准备对同一变 量加锁。假设每个总线事务处理(读失效或写失效)是 100个时钟周期，忽略实际的Cache块锁的读写时间以 及加锁的时间，求10个处理器请求加锁所需的总线事 务数目。设时间为0时锁已释放并且所有处理器在旋转 ，求处理这10个请求时间为多长?假设总线在新的请求 到达之前已服务完挂起的所有请求，并且处理器速度相同。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉解 当i个处理器竞争锁的时候，他们完成下列操 作序列，每一个操作产生一个总线事务：访问该锁的i个LL指令操作；试图锁

10、住该锁的i个SC指令操作；1个释放锁的存操作指令。 因此对n个处理器，总线事务的总和为：n(2i+1)=n(n+1)+n=n2+2ni=1 对于10个处理器有120个总线事务，需要12000个时 钟周期。 7.5 同 步2006年2月秦杰 郑丽萍 张庆辉 本例中问题的根源是锁的竞争、存储器中锁访问的串行性以及总线访问的延迟。旋转锁的主要优点: 对于总线或网络开销较低7.5 同 步2006年2月秦杰 郑丽萍 张庆辉q 并行循环的程序中另一个常用的同步操作: 栅栏栅栏强制所有到达的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。 栅栏的典型实现用两个旋转锁 (1) 用来记录

11、到达栅栏的进程数(2) 用来封锁进程直至最后一个进程到达栅栏栅栏的实现要不停地探测指定的变量，直到它满足规定的条件。 一种典型的实现，其中lock和unlock提供基本的旋转锁，total是要到达栅栏的进程总数。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉Lock(counterlock)； *确保更新的原子性*if(count=0) release=0； *第一个进程则重置release*count=count+1； *到达进程记数*unlock(counterlock)； *释放锁*if(count=total) *进程全部到达*count=0； *重置计数器*release=1； *

12、释放进程*else *还有进程未到达*spin(release=1)； *等待别的进程到达*7.5 同 步2006年2月秦杰 郑丽萍 张庆辉对counterlock加锁保证增量操作的原子性，变量 count记录着已到达栅栏的进程数，变量release用来封锁进程直到最后一个进程到达栅栏。 实际情况中会出现的问题可能反复使用一个栅栏，栅栏释放的进程运行一段后又会再次返回栅栏，这样有可能出现某个进程永远离不开栅栏的状况(它停在旋转操作上)。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉例如：OS调度进程，可能一个进程速度较快，当它第二次到达栅栏时，第一次的进程还挂在栅栏中未能离开。这样所有的进程

13、在这个栅栏的第二次使用中都处于无限等待状态，因为进程的数目永达不到total。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉q 一种解决方法当进程离开栅栏时进行计数，在上次栅栏使用中的所有进程离开之前不允许任何进程重用并初始化本栅栏。q 另一种解决办法sense_reversing栅栏，每个进程均使用一个私有变量local_sense，初始化为1。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉Local_sense=! Local_sense； *local-sense取反* lock(counterlock)； *确保增加的原子性* count+； *记算到达进程数* unlock(co

14、unterlock)； *解锁* if(count=total) *进程全部到达*count=0； *重置计数器*release=local_sense； *释放进程* else *还有进程未到达*spin(release=local_sense)； *等待信号* 7.5 同 步2006年2月秦杰 郑丽萍 张庆辉例7.4 假设总线上10个处理器同时执行一个栅栏，设每 个总线事务需100个时钟周期，忽略Cache块中锁的读、 写实际花费的时间，以及栅栏实现中非同步操作的时间 ，计算10个处理器全部到达栅栏，被释放及离开栅栏所 需的总线事务数。设总线完全公平，整个过程需多长时 间?答：下表给出一个处理器通过栅栏发出的事件序列，设第一个获得总线的进程并未拥有锁。7.5 同 步2006年2月秦杰 郑丽萍 张庆辉表7.6 第i个处理器通过栅栏产生的事件序列 事件 数量 对应源代码 说明 LL i Lock(counterlock)； 所有处理器抢锁 SC i Lock(counterlock)； 所有