《计算机系统结构—第七章（多处理机）》由会员分享，可在线阅读，更多相关《计算机系统结构—第七章（多处理机）（75页珍藏版）》请在金锄头文库上搜索。
1、多处理机什么是多处理机？多处理机结构一致性问题同步程序并行化多处理机性能 什么是多处理机？本章内容2 之 1 具有若干台处理机，在统一的操作系统控制下，在硬件和软件各级上相互作用，来协同求解一个大而复杂的问题。根据Flynn分类法多处理机是MIMD。 利用多任务处理可以提高处理速度，利用系统的重组能力可以提高可靠性。提 示本章内容2 之 2 因为多处理机系统结构是一个巨大而多样的领域，其中很多领域仍处于不成熟的阶段，所以本课程集中于多处理机设计的主流进行讨论：由少量到中等数量的处理机（128）组成的机器。多处理机结构本章内容 根据存储器的组织形式，多处理机有两种基本结构：w集中式共享存储器结构
2、集中式共享存储器结构w分布式共享存储器结构分布式共享存储器结构集中式共享存储器结构多处理机本章内容多处理机结构 存储器是一个独立的子系统，通过互连网络（交叉开关/总线）为所有的处理机共享，任何两台处理机都可以通过访问共享的存储器单元实现通信。 由于共享存储器对每个处理机都是对称关系，而且所有处理机对共享存储器的访问时间都相同，这种结构的多处理机也称为对称多处理机（SMP）和均匀存储器存取（UMA）。2 之 1图 示本章内容多处理机结构2 之 2处理机处理机处理机处理机1级级/多级多级Cache存储器存储器存储器存储器处理机处理机处理机处理机1级级/多级多级Cache处理机处理机处理机处理机1级
3、级/多级多级Cache处理机处理机处理机处理机1级级/多级多级CacheI/OI/O系统系统系统系统分布式共享存储器结构(DSM)多处理机本章内容多处理机结构 存储器分布在各处理机中，但这些存储器在逻辑上统一编址，形成一个为所有处理机共享的虚拟共享存储器。处理机之间信息交换的物理实现仍然是通过点-点的通信。 由于任何一个处理机访问本地存储器都较快，但是访问分布在其他处理机的远程存储器则较慢，这种结构的多处理机也称为非均匀存储器存取（NUMA）。3 之 1图 示本章内容多处理机结构3 之 2处理机处理机+Cache存储器存储器存储器存储器互互 连连 网网 络络I/O处理机处理机+Cache存储器
4、存储器存储器存储器I/O处理机处理机+Cache存储器存储器存储器存储器I/O处理机处理机+Cache存储器存储器存储器存储器I/O处理机处理机+Cache存储器存储器存储器存储器I/O处理机处理机+Cache存储器存储器存储器存储器I/O比 较本章内容多处理机结构3 之 3集中共享集中共享分布共享分布共享处理机数处理机数303010001000限制限制结点间间距和延迟结点间间距和延迟数据局部性数据局部性一致性问题本章内容Cache一致性存储一致性Cache一致性本章内容一致性问题问题现象原因分析解决方法问题现象本章内容一致性问题Cache一致性 Cache一致性是指私有Cache中共享数据的
5、副本和共享存储器中共享数据之间的一致性。u:7u:?P1C u:5主存主存 CCP2P3特征特征特征特征 多处理器多处理器对相同存储对相同存储单元的操作单元的操作引起的一致引起的一致性。性。u:5u:5u:7原因分析本章内容一致性问题Cache一致性共享可写数据引起的不一致性进程迁移引起的数据不一致性I/O传输造成的数据不一致性共享可写数据引起的不一致性 不同处理器对相同单元在各自Cache的拷贝的异步写操作。本章内容一致性问题Cache一致性原因分析P1XXP2X处理机处理机Cache共享存共享存储器储器更新之前更新之前P1XXXP2XX更新之后更新之后（写通过）（写通过）P1XXP2XX更
6、新之后更新之后（写回）（写回）进程迁移引起的数据不一致性本章内容一致性问题Cache一致性原因分析 多处理器中的进程迁移，而又不互相通报。P1XXP2X处理机处理机Cache共享存共享存储器储器初始状态初始状态P1XXXP2XX迁移之前迁移之前（写通过）（写通过）进程进程P1XXXP2XX迁移之后迁移之后（写通过）（写通过）进程进程进程进程I/O传输造成的数据不一致性本章内容一致性问题Cache一致性原因分析绕过Cache拷贝拥有者的I/O操作。P1XX处理机处理机Cache共享存储器共享存储器I/O前前P2XI/OP1XXXI/O后后XXP2XP1XXXI/O后（写回）后（写回）XP2X共享
7、存储器共享存储器输入输入共享存储器共享存储器输出输出解决方法前两种原因监听法目录法第三种原因禁止法刷新法本章内容一致性问题Cache一致性监听协议基本原理具体实现采用写通过策略的Cache采用写回策略的Cache写一次（Write-Once）协议本章内容一致性问题Cache一致性解决方法基本原理本章内容一致性问题Cache一致性解决方法监听协议4 之 1 本方法只适用于采用基于总线互连结构的系统中，由于系统中每个处理机都能觉察到存储器系统正在进行的活动，在某个活动破坏了Cache的一致性时， Cache控制器将采取相应的动作使有关的拷贝无效或更新。写无效/写更新本章内容一致性问题Cache一致
8、性解决方法监听协议4 之 2 使用监听协议来保持Cache一致性有两种方法：方法一：写无效（方法一：写无效（Write InvalidateWrite Invalidate）策略策略 在本地Cache的数据块修改时使远程数据块都无效。方法二：写更新（方法二：写更新（Write UpdateWrite Update）策略策略 在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache。提示：提示：采用写无效或写更新策略与Cache采用写回还是写通过方式无关。图 示本章内容一致性问题Cache一致性解决方法监听协议4 之 3P1XXP2X处理机处理机Cache共享存共享存储器
9、储器更新之前更新之前P1XXI IP2XX更新之后更新之后(Write-Invalidate)P1XXXXP2XX更新之后更新之后(Write-Update)应用情况本章内容一致性问题Cache一致性解决方法监听协议4 之 4 由于写更新法在本地Cache修改时需要通过总线把修改过的数据块的内容广播给所有含该数据块的其他Cache，增加了总线的负担，所以在一般的应用系统中，极少使用写更新法。 本方法实现简单，但只适用于总线式互连的多处理机，而且写无效法和写更新法都要占用总线不少时间，因此只能用于机数少的多处理机中。采用写通过策略的Cache本章内容一致性问题Cache一致性解决方法监听协议 C
10、ache数据块有两种状态: 有效有效和无效无效，有效有效状态表示该数据块内容正确，无效无效状态表示该数据块内容已“过时”或不在Cache中。R RL L、WWL L表示本地处理机对Cache的读和写操作，R RR R、WWR R表示远程处理机对Cache中相同内容数据的读和写操作。采用写回策略的Cache本章内容一致性问题Cache一致性解决方法监听协议2 之 1采用写回策略的Cache Cache数据块有三种状态: 只读只读、读写读写和无效无效。只读只读状态表示整个系统中有多个数据块拷贝是正确的；读写读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，在整个系统中只有一个数据块
11、拷贝是正确的；无效无效状态表示该数据块内容已“过时”或不在Cache中。 R RL L、WWL L表示本地处理机对Cache的读和写操作，R RR R、WWR R表示远程处理机对Cache中相同内容数据的读和写操作。本章内容一致性问题Cache一致性解决方法监听协议2 之 2写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之 1 本方法为了降低总线流量，结合了写回和写通过策略的优点。在第一次写Cache采用写通过策略，以后写Cache采用写回策略，此时整个系统中只有一份正确的拷贝。写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之 2RR写一次协议本章内容一致性
12、问题Cache一致性解决方法监听协议4 之 3 Cache数据块有四种状态: 有效有效、保留保留、重写重写和无效无效。有效有效状态表示整个系统中有多个数据块拷贝是正确的；保留保留状态表示数据从存储器读入Cache后只被写过一次，Cache和存储器中拷贝都正确；重写重写状态表示Cache中的数据块被写过多次，而且是唯一正确的数据块；无效无效状态表示该数据块内容已“过时”或不在Cache中。 R RL L、WWL L表示本地处理机对Cache的读和写操作，R RR R、WWR R表示远程处理机对Cache中相同内容数据的读和写操作。写一次协议本章内容一致性问题Cache一致性解决方法监听协议4 之
13、 4 主要优点：主要优点： 减少大量的无效操作，提高了总线效率。 主要缺点：主要缺点： 当主存储器的内容无效时,读缺失引起的总线读操作必须禁止主存储器的操作（以免造成总线冲突），而大多数总线不支持这种操作。IEEE Futurebus+总线支持该操作。目录协议基本原理具体实现全映射目录协议有限目录协议链式目录协议本章内容一致性问题Cache一致性解决方法基本原理本章内容一致性问题Cache一致性解决方法目录协议 监听协议涉及大量广播通信及收集状态信息的任务，即使是总线型网络也会使总线流量大大增加。 如果使无效信息只发给有关的数据块，可以避免广播，这需要有一套管理数据块的结构，这就是Cache一
14、致性目录协议方案。3 之 1基本原理 建立目录表建立目录表 为Cache在共享存储器建立一个目录表，用于保存每个数据块的状态：包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否有，另外再设置一个标志位（重写位）用以指明是否有一个Cache允许将有关数据写入。本章内容一致性问题Cache一致性解决方法目录协议3 之 2 目录协议用在实现广播功能比较困难的网络目录协议用在实现广播功能比较困难的网络目录协议用在实现广播功能比较困难的网络目录协议用在实现广播功能比较困难的网络。主要思想为：主要思想为：基本原理 使用目录表使用目录表 在CPU对Cache进行写操作时，系统根据目录
15、表中的信息将所有其它存有相同内容的Cache拷贝无效，并置重写位。在CPU对Cache进行读操作时，如果重写未置位，则说明该内容未经重写，此时若Cache读缺失，则从主存储器中或拥有正确内容的Cache中读入块并修改目录即可；如果读命中，则直接读即可。本章内容一致性问题Cache一致性解决方法目录协议3 之 3全映射目录协议本章内容一致性问题Cache一致性解决方法目录协议5 之 1目录项：目录项： 重写位重写位 存在位存在位 数据块数据块C101X共享存储器共享存储器CacheP2VCacheP1VXCacheP3VXV-V-有效位有效位有效位有效位：0-无效；无效；1-有效有效C-C-重写
16、位重写位重写位重写位：0-不许；不许；1-允许允许存在位存在位存在位存在位：0-不存在；不存在；1-存在存在 位数等于处理机数位数等于处理机数举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 2目录项：目录项： 重写位重写位 存在位存在位 数据块数据块0000X共享存储器共享存储器CacheP20CacheP10CacheP30 所有所有所有所有CacheCache都没有块都没有块都没有块都没有块X X的拷贝的拷贝的拷贝的拷贝有效位有效位有效位有效位有效位有效位举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 3目录项：目录项： 重写位重写位 存在位存在位 数据块数
17、据块0111X共享存储器共享存储器CacheP21XCacheP11XCacheP31X 三个处理机都读过块三个处理机都读过块三个处理机都读过块三个处理机都读过块X X后后后后有效位有效位有效位有效位有效位有效位举 例本章内容一致性问题Cache一致性解决方法目录协议5 之 4目录项：目录项： 重写位重写位 存在位存在位 数据块数据块1001X共享存储器共享存储器CacheP20CacheP10CacheP31X P3P3获得写块获得写块获得写块获得写块X X权力后权力后权力后权力后有效位有效位有效位有效位有效位有效位特 点 全映射目录协议的效率比较高，但是其目录开销比较大，与处理器数平方成正
18、比（因为目录项的多少与处理器数成正比，而且每个目录项的大小也与处理器数成正比），不具有可扩展性。本章内容一致性问题Cache一致性解决方法目录协议5 之 5有限目录协议本章内容一致性问题Cache一致性解决方法目录协议4 之 1目录项：目录项： 重写位重写位 存在位存在位 数据块数据块C11X共享存储器共享存储器CacheP2VCacheP1VXCacheP3VXV-V-有效位有效位有效位有效位：0-无效；无效；1-有效有效C-C-重写位重写位重写位重写位：0-不许；不许；1-允许允许存在位存在位存在位存在位： 0-不存在；不存在；1-存在存在 位数位数 等于等于 log2处理机数处理机数举
19、例本章内容一致性问题Cache一致性解决方法目录协议4 之 2目录项：目录项： 重写位重写位 存在位存在位 数据块数据块011X共享存储器共享存储器CacheP20CacheP11XCacheP31X 当当当当P1P1、P3P3的的的的CacheCache中都有块中都有块中都有块中都有块X X的拷贝时的拷贝时的拷贝时的拷贝时举 例本章内容一致性问题Cache一致性解决方法目录协议4 之 3目录项：目录项： 重写位重写位 存在位存在位 数据块数据块011X共享存储器共享存储器CacheP21XCacheP10CacheP31X P2P2请求块请求块请求块请求块X X的拷贝（存在驱逐问题的拷贝（存
20、在驱逐问题的拷贝（存在驱逐问题的拷贝（存在驱逐问题）特 点 有限目录协议解决了目录过大的问题，其目录开销与Nlog2N成正比，N为处理器数（因为目录项的多少与处理器数成正比，而且每个目录项的大小与log2N成正比），但效率有所下降。本章内容一致性问题Cache一致性解决方法目录协议4 之 4链式目录协议本章内容一致性问题Cache一致性解决方法目录协议2 之 1目录项：目录项：重写位重写位指针指针 数据块数据块CX共享存储器共享存储器CacheP2CacheP1VXCacheP3V-V-有效位有效位有效位有效位：0-无效；无效；1-有效有效C-C-重写位重写位重写位重写位：0-不许；不许；1-
21、允许允许VXVXCT特 点 链式目录协议的复杂程度超过前两种目录协议，但它具有前两种目录协议所没有的重要特性：可扩展性。其指针的大小以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关。本章内容一致性问题Cache一致性解决方法目录协议2 之 2I/O与Cache的一致性本章内容一致性问题Cache一致性解决方法 禁止法 存储空间中的某些段不允许进入Cache。 刷新法 操作系统在I/O操作前，将有关的段先从Cache刷新过来，然后再进行I/O操作。存储一致性本章内容一致性问题问题现象解决方法问题现象本章内容一致性问题存储一致性 存储一致性是指多个处理机程序的执行次序与
22、共享存储器中共享数据存取次序之间的一致性。特征特征特征特征 不同处理机对不同不同处理机对不同存储单元的操作引存储单元的操作引起的一致性。起的一致性。a. A :=1b. print B,Cc. B :=1d. print A,Ce. C :=1f. print A,BA、B、C 为共享变量为共享变量(初始状态均为初始状态均为0)处理机处理机1处理机处理机2处理机处理机3共享存储器共享存储器解决方法本章内容一致性问题存储一致性 顺序一致性（顺序一致性（SCSC） 任何执行结果认为是在多线程顺序机器上各操作交错执行的结果。 处理机一致性（处理机一致性（PCPC） 每台处理机发出的写操作顺序不会乱，
23、但两台处理机发出的写操作顺序可能会不一样。 弱一致性（弱一致性（WCWC） 程序员利用同步操作确保顺序一致性。 释放一致性（释放一致性（RCRC） 具有获得和释放两类同步操作的弱一致性，每类操作保证处理机一致性。同 步本章内容 为什么要同步？为什么要同步？ 在多处理机中，进程之间可以通过使用共享变量来实现信息交流，共享变量每次只能被一个进程访问，因此当两个或两个以上的进程同时访问某个共享变量时，必须采用同步措施来协调并行执行的进程。 如何实现同步？如何实现同步？ 一般来说，同步机制是通过用户级的软件例程来构造的，而这些例程要使用硬件提供的同步指令。2 之 1同 步本章内容基本硬件原语用户级的同
24、步操作2 之 2基本硬件原语本章内容同步在多处理机中实现同步，所需的主要功能是：一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读修改单元。通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编制同步库函数。7 之 1原子交换（atomic exchange）本章内容同步 功能功能 将一个存储单元的值和一个寄存器的值进行交换。 例子例子 可以利用它构建一个简单的锁：0表示该锁未被占用，1表示该锁已被占用。如果某处理机想占用该锁，将对应于该锁的存储单元的值与存放在某个寄存器中的1进行交换，返回结果为0则占用成功，为1则未占用成功。 实现同步的关键实现同步的关键 操作
25、的原子性（交换操作是不可再细分的）。7 之 2测试并置定（test_and_set）本章内容同步功能 先测试一个存储单元的值，如果符合条件则修改其值。例子 可以定义一个测试0和设置1的操作，该操作的使用方法与原子交换类似。7 之 3读取并加1（fetch_and_increment）本章内容同步功能功能 返回存储器中的值并以原子操作的方式使存储器中的值增1。例子例子 如果用0表示同步变量未被占用，就可以象使用原子交换一样使用“取并增1”操作。7 之 4使用指令对:LL/SC本章内容同步LL(load linkedLL(load linked或或load locked)load locked)：
26、特殊的取指令SC(store conditional)SC(store conditional)：特殊的存指令指令对功能：指令对功能：如果由LL指明的存储单元的内容在SC对其进行写之前已被其他指令改写过，则第二条指令SC执行失败。如果在两条指令间进行切换也会导致SC执行失败。SC将返回一个值来指出该指令操作是否成功：“1”表示成功，“0”表示不成功LL则返回该存储单元初始值。 7 之 5LL/SC指令对举例本章内容同步利用利用LLLL和和SCSC指令实现指令实现“ “原子交换原子交换” ”操作操作 实现R4和由R1指出的存储单元进行原子交换操作。try：ORR3, R4, R0 LLR2, 0
27、(R1) SCR3, 0(R1) BEQZ R3, try MOVR4, R27 之 6LL/SC指令对举例本章内容同步利用利用LLLL和和SCSC指令实现指令实现“ “取并增取并增1”1”操作操作 LL/SC机制的一个优点：用来构造别的同步原语。try： LLR2, 0(R1) DADDIUR2, R2, #1 SCR2, 0(R1) BEQZR2, try7 之 7用户级的同步操作本章内容同步旋转锁栅栏旋转锁本章内容同步用户级的同步操作思想思想 处理机环绕一个锁不停地旋转而请求获得该锁。即：处理机围绕该锁反复地执行循环程序，直至获得该锁。适合场合适合场合 锁被占用的时间很少，在获得锁后加锁
28、过程延迟很小，因为处理机一直在循环等待获得锁。11 之 1旋转锁的实现本章内容同步用户级的同步操作无无CacheCache一致性机制一致性机制 在存储器存储器中保存锁变量，处理机可以不断地通过一个原子交换原子交换请求使用权。 占用锁占用锁 DADDIUR2, R0, #1 lockit： EXCH R2, 0(R1) /原子交换 BNEZR2, lockit 释放锁释放锁 处理机只需将0放入锁中即可。11 之 2旋转锁的实现本章内容同步用户级的同步操作无无CacheCache一致性机制一致性机制 在存储器存储器中保存锁变量，处理机可以不断地通过一个原子交换原子交换请求使用权。 缺点缺点 每次交
29、换（EXCH指令）都产生一次写操作，如果多个处理机试图占用一个锁时，则大多数写操作都会导致写无效，因为每个处理机都想以独占的方式获得锁变量。11 之 3旋转锁的实现本章内容同步用户级的同步操作支持Cache一致性将锁变量调入CacheCache，并通过一致性机制一致性机制使锁值保持一致。优点：每次尝试占用锁都可以在本地Cache中进行，而不需进行全局存储访问；大多数对锁的访问有局限性，这样做可以大大减少获取锁所需的时间。11 之 4旋转锁的实现本章内容同步用户级的同步操作支持支持CacheCache一致性一致性采用采用“ “原子交换原子交换” ”原语实现（改进）原语实现（改进）：只对本地Cac
30、he中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其他处理器上的进程争用该锁变量。 lockit： LD R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 EXCH R2, 0(R1) /原子交换 BNEZ R2, lockit11 之 5步骤步骤 处理机处理机P0 P0 处理机处理机P1 P1 处理机处理机P2 P2 锁的状态锁的状态 总线总线/ /目录操作目录操作 1 1占有锁占有锁 环绕测试环绕测试是否是否lock=0lock=0？环绕测试环绕测试是否是否lock=0lock=0？ 共享共享 无无 2 2将锁置
31、为将锁置为0 0 （收到作废命令）（收到作废命令） （收到作废命令）（收到作废命令）专有专有(P0)(P0) P0P0发出对锁变量的发出对锁变量的作废消息作废消息 3 3CacheCache失效失效 CacheCache失效失效 共享共享总线总线/ /目录收到目录收到P2 P2 CacheCache失效；锁从失效；锁从P0P0写回写回 4 4（因总线（因总线/ /目录忙目录忙而等待）而等待）lock=0lock=0共享共享P2 CacheP2 Cache失效被处失效被处理理 5 5Lock=0 Lock=0 执行交换，执行交换，导致导致CacheCache失效失效共享共享P1 CacheP1
32、Cache失效被处失效被处理理 6 6执行交换，执行交换，导致导致CacheCache失效失效 交换完毕：返回交换完毕：返回0 0并置并置lock=1 lock=1 专有专有(P2)(P2) 总线总线/ /目录收到目录收到P2 P2 CacheCache失效；发作废失效；发作废消息消息 7 7交换完毕：交换完毕：返回返回1 1 进入关键程序段进入关键程序段 专有专有(P1)(P1)总线总线/ /目录处理目录处理P1 P1 CacheCache失效；写回失效；写回 8 8环绕测试环绕测试是否是否lock=0lock=0？ 无无3 3个处理机利用原子交换争用旋转锁所进行的操作个处理机利用原子交换争
33、用旋转锁所进行的操作 11 之 6旋转锁的实现本章内容同步用户级的同步操作支持支持CacheCache一致性一致性采用采用LL/SCLL/SC原语实现原语实现：读/写操作明显分开，而且LL原语不产生总线数据传送，这使下面代码与前面方法具有相同的特点。 lockit：LL R2, 0(R1) BNEZ R2, lockit DADDIU R2, R0, #1 SC R2, 0(R1) BEQZ R2, lockit11 之 7同步性能问题本章内容同步用户级的同步操作 简单旋转锁不能很好地适应可扩缩性。大规模多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。11 之 8定
34、量分析本章内容同步用户级的同步操作例：假设某条总线上有10个处理机同时准备对同一变量加锁。如果每个总线事务处理（读失效或写失效）的时间是100个时钟周期，而且忽略对已调入Cache中的锁进行读写的时间以及占用该锁的时间。(1) 假设该锁在时间为0时被释放，并且所有处理机都在旋转等待该锁。问：所有10个处理机都获得该锁所需的总线事务数目是多少？(2) 假设总线是非常公平的，在处理新请求之前，要先全部处理好已有的请求。并且各处理机的速度相同。问：处理10个请求大概需要多少时间？11 之 9定量分析本章内容同步用户级的同步操作解：当i个处理器争用锁的时候，它们都各自完成以下操作序列，每一个操作产生一
35、个总线事务：访问该锁的i个LL指令操作试图占用该锁（并上锁）的i个SC指令操作1个释放锁的存操作指令 因此对于i个处理器来说，一个处理器获得该锁所要进行的总线事务的个数为2i+1。 由此可知，对n个处理器，总的总线事务个数为： 对于10个处理器来说，其总线事务数为120个，需要12000个时钟周期。11 之 10问题分析本章内容同步用户级的同步操作本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一个处理器重用时具有很好的性能。旋转锁的两个主要优点在本例中都没有得到体现11 之 11栅 栏本章内容同步用户级的同步操作
36、 栅栏思想栅栏思想 栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。 典型实现典型实现 用两个旋转锁：一个用来保护一个计数器，它记录已到达该栅栏的进程数；另一个用来封锁进程直至最后一个进程到达该栅栏。 6 之 1一种典型的实现本章内容同步用户级的同步操作lock（counterlock）； /确保更新的原子性if（count=0）release=0； /第一个进程则重置releasecount=count+1； /到达进程数加1unlock（counterlock）； /释放锁if（count=total） /进程全部到达count=0； /重置
37、计数器release=1； /释放进程 else /还有进程未到达spin（release=1）；/等待别的进程到达 6 之 2解 释本章内容同步用户级的同步操作counterlockcounterlock用来保护计数器，使其以原子操作的方式递增。变量变量countcount计算到达栅栏的进程数目。totaltotal规定了要到达栅栏的进程总数 变量变量releaserelease用于标识最后一个处理机是否到达栅栏。Spin(release)Spin(release)操作使处理机等待直到所有处理机到达栅栏。6 之 3问题及解决本章内容同步用户级的同步操作 问题问题 栅栏经常在循环内使用，因此有
38、可能在最后一个进程离开栅栏之前最先得到调度的进程再次到达同一栅栏，然后先被调度的进程通过重置release标志又将未调度的进程陷在栅栏中。这样这些进程会永远等在这个栅栏上，因为有一个进程还未从上一次栅栏中出来，故而进程数目无法到达total值。 解决解决 方法方法1 1：计算离开栅栏的进程数目，直到所有进程都离开栅栏之前不允许任何进程再次进入栅栏或初始化栅栏。 方法方法2 2：采用“判断-回转栅栏”6 之 4判断-回转栅栏（sense-reversing barrier）本章内容同步用户级的同步操作local_sense=! local_sense； /local-sense取反lock（co
39、unterlock）； /确保更新的原子性count+； /到达进程数加1unlock（counterlock）； /释放锁if（count=total） /进程全部到达count=0；/重置计数器release=local_sense；/释放进程 else /还有进程未到达spin（release=local_sense）；/等待信号 6 之 5解 释本章内容同步用户级的同步操作每个进程均使用一个私有变量私有变量local_senselocal_sense，该变量初始化为1。优缺点：优缺点：使用安全，但性能比较差。 对于10个处理器来说，当同时进行栅栏操作时，如果忽略对Cache的访问时间以及其他非同步操作所需的时间，则其总线事务数为204个，如果每个总线事物需要100个时钟周期，则总共需要20400个时钟周期。 6 之 6
