《Linux原理与结构》课件第9章.ppt

1、1 1第九章 互斥与同步9.1 基础操作基础操作9.2 自旋锁自旋锁9.3 序号锁序号锁9.4 RCU机制机制9.5 信号量信号量9.6 信号量集合信号量集合2 2虽然进程有各自独立的虚拟地址空间，一般情况下不会出现交叉引用的问题，但由于它们运行在同一个计算环境中，共用同一个内核，不可避免地会发生一些相互作用，如竞争独占资源、访问共享对象、协调多方动作等。独占资源(如处理器、外部设备等)同时只能由一个进程使用，对独占资源竞争的结果是一个进程获得，其它进程等待。共享对象(如共用的数据结构等)允许多个进程访问，但访问操作应是原子的，不应出现交叉重叠。相互协作的进程(如生产者与消费者进程)之间需要协

2、调动作，以便保持步调一致。3 3为了使进程之间能够和谐共处、有序竞争，操作系统需要提供保证机制，大致包括互斥(Mutual Exclusion)与同步(Synchronization)。互斥是一种竞争机制，用于保护共享的独占资源。同步是一种协调机制，用于统一进程的步调。互斥是排外的、封闭的，表示资源属于自己，不许别的进程再动，因而多使用锁(Lock)。同步是开放的、合作的，在自己完成某个动作或用完某个资源之后会主动通知合作者或唤醒等待者，因而常使用信号灯或信号量(Semaphore)。Linux内核提供了多种互斥与同步机制，如自旋锁、序号锁、RCU、信号量、信号量集合等。除信号量集合之外，其余

3、机制都是内核自己使用的，4 4用于保护被所有进程共用的内核资源、协调核内进程的动作。可以说没有互斥与同步机制，就无法保证内核的和谐与稳定。5 5为了实现多处理器或并发环境中的互斥与同步机制，内核需要提供一些基础操作，如格栅操作、原子操作、抢占屏蔽操作、进程等待操作等。格栅操作用于设定一些特殊的控制点，以保证点后指令不会在点前指令完全完成之前开始执行，从而控制指令的执行顺序。原子操作是对单个内存变量的不可分割的基本操作(如变量加、减等)，用于保证某些特殊内存操作的完整性。抢占屏蔽操作用于控制进程的调度时机，如禁止某些场合下的进程调度等。进程睡眠与等待操作用于管理进程等待队列，以便在条件成熟时唤醒

4、其中的进程。9.1 基基 础础 操操 作作6 69.1.1 格栅操作格栅操作正常情况下，编译或汇编器按序生成程序代码，处理器也按序执行程序代码，不会出现乱序现象。然而，为了提高执行速度，目前的汇编和编译器通常会对程序进行优化，如调整指令顺序等，处理器在执行指令期间也会采取一些加速措施，如高速缓存、乱序发射、并行执行等，因而进程对内存的实际访问顺序可能与程序的预定顺序不一致。大部分情况下，指令顺序的调整不会改变程序的行为，但也有一些例外，如将临界区内的指令移到临界区外执行就可能产生难以预料的后果。为了保证程序行为的一致性，Intel处理器提供了特殊指令、GCC编译器提供了优化格栅、Linux操作

5、系统提供了内存格栅操作，用于控制指令的执行顺序。7 7优化格栅用于防止编译器的过度优化，以保证所生成代码的正确性。Linux实现的优化格式是宏barrier，定义如下：#define barrier()_asm_ _volatile_(:memory)宏barrier告诉编译器三件事：将要插入一段汇编代码(_asm_)、不要将这段代码与其它代码重组(_volatile_)、所有的内存位置都已改变(memory)，因而此前保存在寄存器中的所有内存单元的内容都已失效，此后对内存的访问需要重新读入，不能用已有的寄存器内容对程序进行优化。8 8内存格栅用于保证指令的执行顺序。在Intel处理器中，有些

6、指令是串行执行的，可以作为内存格栅，如I/O指令、带lock前缀的指令、写控制寄存器的指令等。另外，Intel处理器还专门引入了三条格栅指令，其中lfence(读格栅)保证其后的读操作不会在其前的读操作完全完成之前开始，sfence(写格栅)保证其后的写操作不会在其前的写操作完全完成之前开始，mfence(读写格栅)保证其后的读写操作不会在其前的读写操作完全完成之前开始。Linux提供了多个内存格栅宏，它们其实就是对上述三条指令的包装，如下：#define mb()asm volatile(mfence:memory)/读写内存格栅9 9#define rmb()asm volatile(lf

7、ence:memory)/读内存格栅#define wmb()asm volatile(sfence:memory)/写内存格栅因而，格栅就是屏障，只有当前面的指令完全执行完之后其后的指令才会开始执行。在程序中插入格栅可以保证程序的执行顺序，虽然会影响程序的执行性能。10 109.1.2 原子操作原子操作由于机器指令的功能过于简单，一个稍微复杂的操作通常都必须用多条指令完成。如操作x=x+3通常被翻译成三条指令：将x的值读入到某个寄存器、将寄存器的值加3、将寄存器的内容写回x。考虑如下情形：(1)在第一条指令完成之后、第三条指令完成之前出现了中断；(2)在中断返回之前处理器再次访问了变量x，如

8、执行了x=x+5。此时，x值的变化会出现不一致性，其结果是x+3而不是x+8。11 11出现上述问题的原因是操作的原子性(不可分割)被破坏了。由于中断的出现，一个完整操作的中间被随机地插入了其它操作。这一问题的解决方法比较简单，关闭中断即可避免这种操作插入现象。更复杂的情况出现在多处理器环境中，此时，一个变量可能被多个处理器同时访问。如两个处理器同时执行x=x+3操作，其结果将是x+3而不是x+6。引起这一问题的原因仍然是操作的原子性被破坏了(在x上同时施加了两个操作)。这一问题的解决需要处理器的支持，并需要操作系统提供相应的手段。12 12Intel处理器提供了lock前缀，用于将一条内存访

9、问指令(如add、sub、inc、dec等)转化成原子指令。如果某条指令之前有lock前缀，那么在执行该指令期间处理器会锁住内存总线，以保证不会出现多个处理器同时访问一个内存变量的现象。为了保证C语言操作的原子性，Linux定义了原子类型atomic_t并提供了一组该类型上的原子操作。原子类型实际就是整型，多被嵌入在其它结构中，定义如下：13 13typedef struct int counter;atomic_t;在Intel处理器上，原子加法操作由atomic_add实现，其实现代码如下：static inline void atomic_add(int i,atomic_t*v)asm

10、 volatile(LOCK_PREFIX addl%1,%0 :+m(v-counter):ir(i);14 14在多处理器平台上，宏LOCK_PREFIX就是lock前缀，用于保证加法操作的原子性，即保证在指令add执行期间不会有其它处理器访问变量v。与原子加法操作的实现思路类似，Linux还实现了多个其它的原子操作，如表9.1所示。15 15表9.1 Linux的原子操作16 169.1.3 抢占屏蔽操作抢占屏蔽操作在当前进程未主动放弃处理器的情况下，如果系统中出现了更值得运行的进程，那么应该将处理器从当前进程手中强行收回，以便让新就绪的进程尽快运行，这一过程称为抢占调度。抢占使处理器的

11、分配更加合理，也可提升系统的反应能力，但会增加设计的复杂性。抢占条件通常由中断处理程序创造，抢占时机通常在中断返回之前。如果中断之前的处理器运行在用户态，那么在从核心态返回用户态之前进行抢占调度不会引起不一致性问题。17 17但如果中断之前的处理器运行在核心态，那么在中断返回之前进行的抢占调度就有可能导致内核数据的不一致性。如中断之前处理器正在修改内核中的某个链表，那么在修改完成之前的抢占调度有可能破坏该链表的一致性。早期的Linux禁止内核态抢占。新版本的Linux允许内核态抢占，但需要某种机制来控制抢占的时机。控制内核态抢占的一种方法是关、开中断。在修改某些关键数据结构之前将中断关闭，在修

12、改完成之后再将中断打开。但关、开中断的代价较高，因而Linux又引入了抢占计数preempt_count(位于进程的thread_info结构中，如图4.8所示)，每个进程一个，表示该进程当前是否可被抢占。18 18操作preempt_disable()将当前进程的抢占计数加1，从而禁止抢占该进程。操作preempt_enable()将当前进程的抢占计数减1，而后试图进行抢占调度。调度的条件是：当前进程上设置了TIF_NEED_RESCHED标志且当前进程的抢占计数是0且当前处理器的中断未被屏蔽。上述两个操作都带有优化格栅，保证能使后面的程序看到它们的操作结果。由操作preempt_disab

13、le()和preempt_enable()括起来的区域允许中断，但不可抢占。19 19在从中断返回到核心态之前，如果当前进程的抢占计数不是0，即使其上设置了TIF_NEED_RESCHED标志，善后处理程序也不会进行进程调度(如图4.3所示)。20209.1.4 睡眠与等待操作睡眠与等待操作正在运行的进程可以主动请求睡眠(sleep_on()，从而进入等待状态。进程可以在不可中断等待状态下睡眠，也可以在可中断等待状态下睡眠。进程可以预定一个睡眠时间，也可以不预定睡眠时间(长眠)。Linux将睡眠进程挂在自己指定的等待队列中。等待队列由类型wait_queue_head_t定义，如下：struc

14、t _wait_queue_head spinlock_tlock;/保护锁 struct list_headtask_list;/队列;21 21typedef struct _wait_queue_headwait_queue_head_t;睡眠者进程先将自己包装在一个_wait_queue结构中，而后挂在指定的等待队列上，最后请求调度(执行函数schedule()，放弃处理器，进入等待状态。struct _wait_queue unsigned int flags;/标志，总是1 void*private;/指向睡眠者进程的task_struct结构 wait_queue_func_t

15、func;/睡眠到期后的处理函数2222 struct list_head task_list;/队列节点;typedef struct _wait_queuewait_queue_t;如果进程预定了睡眠时间，Linux会为其启动一个定时器。当定时器到期时，Linux会将睡眠的进程唤醒(将其状态改为TASK_RUNNING并加入就绪队列)。如果进程在到期之前被唤醒，睡眠操作会返回剩余的睡眠时间。未预定睡眠时间的进程只能被显式唤醒(wake_up()。唤醒操作顺序执行等待队列中各2323_wait_queue结构中的func操作，唤醒等待的进程。唤醒者进程可以指定被唤醒进程的状态和一次可唤醒的进

16、程数量。除了睡眠之外，进程还可以等待某个事件(又称为条件变量)。等待者进程可以将自己置于不可中断等待状态或可中断等待状态，且可以预定一个最长等待时间。Linux用结构completion描述这种条件等待队列，如下：struct completion unsigned intdone;/0表示等待的事件未发生，0表示已发生 wait_queue_head_twait;/等待队列;2424欲等待某事件的进程通过wait_for_completion()类的操作将自己置为等待状态并挂在等待队列中，而后请求调度，放弃处理器。此后进程将一直等待，直到自己等待的事件发生(done大于1并被唤醒)或等待了足

17、够长的时间。等待事件的进程可被操作complete()或complete_all()唤醒。操作complete()将done加1并唤醒队列中的第一个进程，操作complete_all()将done加0 x7FFFFFFF而后唤醒队列中的所有进程。2525原子操作只能保证一条指令的原子性，因而仅能实现单个变量的互斥使用。若要实现一个数据结构的互斥使用，就需要保证一个程序片段的原子性，需要更复杂的互斥手段。自旋锁就是其中之一。9.2 自自 旋旋 锁锁2626在操作系统中，一次只允许一个进程使用的资源称为独占资源或临界资源(Critical resource)，访问临界资源的程序片段称为临界区(Cr

18、itical section)。自旋锁的主要作用是保证对临界资源的互斥使用，或者说保证临界区的原子性。27279.2.1 自旋锁的概念自旋锁的概念实现进程互斥的方法很多，如纯软件方法(Peterson算法)、纯硬件方法(开关中断)等，但最直观、最简洁的方法是锁(Lock)。锁用于保护使用时间很短的临界资源，每种临界资源都需要一把保护锁。进程在使用临界资源之前需要先申请到该资源的保护锁。获得锁的进程可以使用资源，但在用完之后应尽快将锁释放。在一个特定的时间点上，最多只有一个进程能获得某个特定的锁。在无法立刻获得锁时，进程忙等测试，因而又将这种保护锁称为自旋锁(spinlock)。由自旋锁保护的临

19、界区的格式如下：2828如果加锁操作成功，进程可立刻进入临界区，否则将在加锁操作中自旋等待。自旋锁一般用在多处理器环境中。申请锁的进程和持有锁的进程运行在不同的处理器上，申请锁的进程通过简单的忙等测试等待持有锁的进程释放自旋锁。在单处理器环境中，自旋锁退化成了空语句，或简单的开、关中断操作。自旋锁不能嵌套使用。持有自旋锁的进程再次申请同一个自旋锁会使程序进入死循环，导致死锁(无限期地等待自己解锁)。2929为了实现自旋锁，至少需要定义一个锁变量和一组锁操作。锁变量用于记录锁的状态(忙、闲)，锁操作用于测试和修改锁的状态，实现加锁和解锁语义。锁变量必须是共享的，使用同一个自旋锁的所有进程或处理器

20、看到的应该是同一个锁变量，因而锁通常用在内核中。当然，对锁状态的修改操作必须是原子的。30309.2.2 经典自旋锁经典自旋锁Linux用类型spinlock_t(或结构spinlock)描述自旋锁。在Intel处理器上，结构spinlock的定义如下：typedef struct arch_spinlock unsigned int slock;/记录锁状态 arch_spinlock_t;typedef struct raw_spinlock arch_spinlock_t raw_lock;raw_spinlock_t;31 31typedef struct spinlock struc

21、t raw_spinlockrlock;spinlock_t;由此可见，自旋锁实际是一个经过多层包装的无符号整型变量，其值的意义取决于加锁与解锁算法的设计。在Linux的演变过程中，自旋锁的实现算法也在不断演变。(1)算法1把锁状态看成一个整数，1表示锁闲，0表示锁忙。加锁操作将锁状态减1，如果减后的值不是负数，则获得锁，否则循环测试，直到锁的状态变成正数。解锁操作将锁状态置1。减1与置1操作都是原子的。算法1的实现流程如图9.1所示。3232图9.1 加锁解锁算法13333(2)算法2把锁状态看成一个位图，只用它的第0位，0表示锁闲，1表示锁忙。加锁操作在把第0位的值取出的同时将其置1。如果

22、取出的值是0，则获得锁，否则循环测试，直到第0位变成0。解锁操作将第0位清0。位的检测与设置(清除)操作都是原子的，由带lock前缀的指令BTS(位检测与设置)和BTR(位检测与清除)实现。上述两个算法实现了自旋锁的语义，可以保证在一个特定的时刻最多只有一个进程能获得自旋锁，但都存在着无序竞争的问题。3434假如在进程1持有锁sl期间，进程2和进程3先后申请了该锁，那么当进程1释放sl时，应该是进程2先获得，进程3后获得。但上述两种实现无法保证这一点。为此，Linux又给出了算法3。(3)算法3把锁状态看成两个无符号整数(8位或16位)，一个为申请序号req，一个为使用序号use，两个序号的初

23、值都是0。加锁操作获得锁的当前申请序号同时将其加1，而后比较自己获得的申请序号和锁的使用序号，如两者相等，则获得锁，否则忙等测试，直到锁的使用序号与自己的申请序号相等为止。解锁操作将锁的使用序号加1。算法3的实现流程如图9.2所示。3535图9.2 加锁解锁算法33636当申请序号等于使用序号时，锁空闲。当申请序号大于使用序号时，锁繁忙(req-use-1是等待自旋锁的进程数)。当有多个进程等待同一自旋锁时，它们将按申请的顺序获得锁，先申请者先得，后申请者后得，避免了无序竞争。算法3优于算法1和算法2。3737然而算法3不能避免持有锁的进程被抢占。一旦持有者进程被抢占，它将停留在自己的临界区中

24、，无法及时执行解锁操作，会导致等待该锁的其它进程(或处理器)长时间自旋。因而，完整的加、解锁实现应包括抢占屏蔽，在加锁操作中屏蔽抢占，在解锁操作中使能抢占，如下：void spin_lock(spinlock_t*lock)preempt_disable();/抢占屏蔽 arch_spin_lock(lock-rlock.raw_lock);3838void spin_unlock(spinlock_t*lock)arch_spin_unlock(lock-rlock.raw_lock);preempt_enable();/抢占使能即使进程在持有锁期间被设置了TIF_NEED_RESCHED标

25、志，抢占调度也不会立刻发生。事实上，抢占调度会被推迟到解锁之时，此时进程已退出了临界区。39399.2.3 带中断屏蔽的自旋锁带中断屏蔽的自旋锁增加了抢占屏蔽的自旋锁已经比较可靠，但仍然可能让等待锁的进程长期自旋，原因是持有者进程可能被中断。若持有锁的进程被中断，处理器将转去执行中断处理程序，从而会延长其它进程的等待时间。更严重的是，如果中断处理程序再次申请同一个自旋锁，则会导致锁的嵌套使用，使系统无法继续运行(死锁)。为解决这一问题，Linux又提供了带中断屏蔽的自旋锁，如下：void spin_lock_irq(spinlock_t*lock)4040 local_irq_disable(

26、);/关中断 spin_lock(lock);void spin_unlock_irq(spinlock_t*lock)spin_unlock(lock);local_irq_enable();/开中断41 41增加了关、开中断操作之后，可以保证持有锁的进程不会被中断，当然也就不会被抢占。然而上述两个操作对中断的处理不够精细。如果在spin_lock_irq执行之前中断已被关闭，那么在spin_unlock_irq之后无条件地打开中断就会带来问题。较好的做法是在加锁操作中保存中断状态(在EFLAGS中)，在解锁操作中恢复中断状态。为此，Linux又提供了spin_lock_irqsave(lo

27、ck,flags)和spin_unlock_irqrestore(lock,flags)。4242操作spin_lock_irqsave(lock,flags)完成三件事，一是将EFLAGS中的中断状态保存在flags中，二是关闭中断，三是执行lock上的加锁操作。操作spin_unlock_irqrestore(lock,flags)完成两件事，一是执行lock上的解锁操作，二是根据flags恢复EFLAGS中的中断状态。43439.2.4 读写自旋锁读写自旋锁增加了关、开中断之后的自旋锁已经比较完善，但仍然不够精细，因为它没有考虑进程对临界资源的使用方式。事实上，进程对临界资源的使用方式大

28、致可分为两类，一是只读使用，二是读写使用。为了保证对临界资源的可靠使用，不应该允许多个进程同时修改(写)临界资源。当一个进程在写临界资源时，其它进程不应该写，也不应该读。然而，为了提高临界资源的利用率，应该允许多个进程同时读临界资源。当有进程在读临界资源时，其它进程可以同时读，但不应该写。4444区分了读、写操作的自旋锁称为读写自旋锁。在同一时间段内，读写自旋锁保护的资源可能正在被一个进程写，也可能正在被多个进程读。读写自旋锁同样只适用于多处理器环境，在单处理器系统中，读写自旋锁或者为空，或者就是关中断和开中断。Linux用类型rwlock_t表示读写自旋锁。在Intel处理器上，rwlock

29、_t的定义如下：typedef struct unsigned int rw;arch_rwlock_t;4545typedef struct arch_rwlock_t raw_lock;rwlock_t;由此可见，读写自旋锁实际是一个经过多层包装的无符号整数，其意义取决于加、解锁算法的设计。在较早的版本中，Linux将rw分成两部分，其中的第31位用于记录写锁状态(0为空闲、1为繁忙)，其余31位用于记录读者个数(0表示无读者)，锁的初值是0。读加锁、解锁操作与写加锁、解锁操作的实现流程如图9.3所示。4646图9.3 老读写自旋锁实现算法4747在新的实现中，读写自旋锁的初值被设为0 x

30、01000000，读加锁与写加锁操作的实现算法基本相同，都是先将锁的值减去一个常数，而后判断结果的正负。非负则获得锁，负则循环等待。不同的是，写加锁操作减去的常数是0 x01000000，读加锁操作减去的常数是1。写解锁操作将锁的值加0 x01000000，读解锁操作将锁的值加1。如果锁是空闲的(既无读者也无写者)，读加锁与写加锁操作都会成功。如果有写者，读加锁与写加锁都会失败。如果有读者，只要读者个数不超过0 x01000000，4848读加锁操作都会成功，但写加锁操作肯定失败。读加锁操作成功的条件是没有写者，写加锁操作成功的条件是既无读者也无写者。新读写自旋锁的实现流程如图9.4所示。49

31、49图9.4 新读写自旋锁实现算法5050当然，真正的读写自旋锁操作还要照顾到抢占，实现的函数如下。void xx_lock(rwlock_t*lock)/xx是read或write preempt_disable();/抢占屏蔽 arch_xx_lock(lock-raw_lock);void xx_unlock(rwlock_t*lock)/xx是read或write arch_xx_unlock(lock-raw_lock);51 51 preempt_enable();/抢占使能为了照顾中断，Linux还提供了xx_lock_irq()、xx_unlock_irq()、xx_lock_

32、irqsave()、xx_unlock_irqrestore()等操作(其中的xx是read或write)。但Linux未解决读写自旋锁的无序竞争问题。由读写自旋锁的实现可知，读锁是共享的，写锁是排他的。读锁允许嵌套使用，但写锁不能嵌套。读锁不会自动升级到写锁。读写自旋锁一般用于保护读多、写少的资源。5252读写自旋锁更偏爱读者，在读多写少的情况下，写者的等待时间会更长。为了照顾写者，Linux又引入了序号锁。序号锁是一种读写锁，不过它更偏爱写者。序号锁的写者不需要等待读者，只要没有其它写者，即可开始修改资源。为了与其它写者互斥，写者在使用资源之前需要先申请序号写锁。写者使用资源的过程如下：w

33、rite_seqlock(&seq_lock);/申请序号写锁/*临界区，读、写数据*/9.3 序序 号号 锁锁5353write_sequnlock(&seq_lock);/释放序号写锁序号锁的读者不需要预先申请锁，可直接对资源进行读操作，但读出的数据可能不准确(如正在被写者修改)，因而需要对读出的结果进行测试，并在必要时重读。读者使用资源的过程如下：unsigned long seq;do seq=read_seqbegin(&seq_lock);/先获得序号 /*直接读数据，但读出的结果不一定正确，因而要测试*/5454 while(read_seqretry(&seq_lock,seq

34、);/根据序号确定读出的数据是否准确序号锁由类型seqlock_t定义，其中包含一个序号和一个经典自旋锁，如下：typedef struct unsigned sequence;/序号 spinlock_t lock;/经典自旋锁 seqlock_t;5555初始情况下，序号sequence是0，自旋锁lock处于空闲状态。写加锁、解锁算法的实现如下：void write_seqlock(seqlock_t*sl)spin_lock(&sl-lock);/申请自旋锁 +sl-sequence;/序号加1 wmb();/内存格栅，保证内存中的数据确被修改void write_sequnlock(

35、seqlock_t*sl)5656 wmb();/内存格栅，保证内存中的数据确被修改 sl-sequence+;/序号加1 spin_unlock(&sl-lock);/释放自旋锁由此可见，序号锁中的序号是单调增长的。如果序号锁正被某个写者持有，它的序号肯定是奇数，否则，序号是偶数。5757函数read_seqbegin()读出序号锁的当前序号，并保证读出的序号一定是偶数。如果序号锁的当前序号与已读出的序号相等，函数read_seqretry()的返回值是假，表示读者读出的数据是准确的，可以直接使用。如果序号锁的当前序号与已读出的序号不等，函数read_seqretry()的返回值是真，表示读

36、出的数据不准，需要重读。当然，以上述函数为基础还可以实现带中断屏蔽的序号锁等。5858锁的基本语义是互斥，即在一个特定的时间点上仅允许一个进程使用资源。这种严格的互限制会使操作串行化，且会使等待者进程空转，影响系统的性能。因而，对锁的改进大都集中在提高系统的并发性上，即在保证数据一致性的前提下尽可能地允许多个进程同时使用资源。经典自旋锁所保护的资源不允许并发使用，只有锁的持有者能够使用资源，其它进程只能空转等待。读写自旋锁所保护的资源允许多个读者并发使用，但不允许写者与读者并发使用。9.4 RCU 机机 制制5959序号锁所保护的资源允许写者与读者并发使用，但并发的结果是写者的工作有效而读者的

37、工作可能需要重做，是一种伪并发。RCU(read-copy update)机制所保护的资源允许写者和读者同时使用，并能保证读者和写者的工作同样有效。60609.4.1 RCU实现思路实现思路RCU不是严格意义上的锁，它仅是一种使用资源的方法或机制。Linux在2.5版中首次引入了RCU机制，在随后的发展中又对其进行了多次改进，形成了多个实现版本，如经典RCU、层次(树形)RCU、微型RCU等，目前缺省的实现是层次RCU。RCU的基本思想是对读者稍加限制，而对写者严格要求，因而读者的开销极小，而写者的开销稍大。所以，RCU机制更适合保护读多写少的资源。61 61RCU的读者不需要理会写者，只要需

38、要即可进入临界区执行读操作。RCU约定读者只能在临界区中使用资源，且在使用之前必须先获得对资源的引用(指针)，而后再通过引用使用(读)资源；在临界区外，对资源的引用将失效，或者说，读者不能在临界区外使用资源；在临界区中的读者不允许抢占。读者使用资源的典型过程如下：rcu_read_lock();/进入临界区p=rcu_dereference(gp);/获得对资源gp的引用6262if(p!=NULL)do_something_with(p);/通过引用p使用资源，完成预定的工作rcu_read_unlock();/退出临界区由于RCU资源可能正在被读者使用，因而写者不能直接修改资源。对写者来说

39、，修改资源就是更新资源，就是发布资源的新版本，其过程如下：6363(1)创建老资源的一个拷贝，并对拷贝进行必要的修改，形成新版本。(2)用资源的新版本替换老资源，使更新生效。(3)维护老资源直到所有的读者都不再引用它，而后释放(销毁)老资源。资源替换操作必须是原子的，因而替换完成之前的读者获得的是对老资源的引用，替换完成之后的读者获得的是对新资源的引用，新老版本并存，直到没有读者再使用老资源。写者使用资源的典型过程如下：p=gp;6464q=kmalloc(sizeof(*p),GFP_KERNEL);/创建一个新资源spin_lock(&gp_lock);/互斥写者*q=*p;/复制老资源d

40、o_something_with(q);/在新资源上完成预定的修改操作6565rcu_assign_pointer(gp,q);/替换老资源，发布新资源spin_unlock(&gp_lock);synchronize_rcu();/等待所有读者释放老资源kfree(p);/销毁老资源从读者和写者的典型使用过程可以看出，RCU的读者进程有临界区(称为读方临界区)，而写者进程没有临界区。如果读者进程位于读方临界区之外，则称它处于静止态(quiescent state)。6666如果处理器正在运行静止态的进程，则说该处理器处于静止态。显然，处于静止态的读者不再持有对RCU资源的引用，因而不会再使用

41、RCU资源。如果在写者进程发布资源之时有n个读者进程(在n个处理器上)正在读方临界区中，那么当这n个进程(或处理器)都至少经历过一次静止态之后，即可肯定已没有进程再使用老的资源，可以放心地将其释放掉了。每个处理器都至少经历一次静止态的时间间隔称为宽限期(Grace Period，GP)。写者进程在完成对资源的发布操作之后，至少需等待一个宽限期，然后才可放心地将老资源释放掉，如图9.5所示。6767在图9.5中，运行在处理器2上的写者进程在t1时刻完成了资源发布。此时，处理器0和3都在读方临界区中，可能正在引用老资源，但处理器1处于静止态，未使用老资源。因此，处理器2在完成发布操作后必须等待，直

42、到时刻t2(所有处理器都至少经历过一次静止态)之后才可以放心地释放老资源。在t1之后新进入读方临界区的处理器(如处理器1、0)引用的肯定是新资源，老资源的释放不会对它们造成影响，不需要等待它们退出临界区。6868图9.5 静止态与宽限期6969为了实现RCU机制，Linux定义了多个接口操作，大多数操作(可能是函数也可能是宏)的实现都比较简单，如下：(1)函数rcu_read_lock()用于标识读方临界区的入口，一般情况下就是一个抢占屏蔽操作preempt_disable()。(2)函数rcu_read_unlock()用于标识读方临界区的出口，一般情况下就是一个抢占使能操作preempt_

43、enable()。由rcu_read_lock()和rcu_read_unlock()界定的读方临界区可以被中断，但不许被抢占。如果Linux内核本身就不许抢占，上述两个函数等价于空操作，没有任何开销。7070RCU未提供写方临界区的界定函数rcu_write_lock()和rcu_write_unlock()，因而不能定义写方临界区。在任何时候，RCU资源的写者都不能阻止读者读资源。(3)宏rcu_dereference(p)用于获得一个被RCU保护的资源的指针，等价于参数p，在宏中所做的变换仅仅为了告诉编译器不要对其进行优化。宏rcu_dereference()只能在读方临界区中使用，所获

44、得的指针也只能在读方临界区中使用且不能修改。71 71(4)宏rcu_assign_pointer(p,v)用于替换老资源或发布新资源，其结果是让指针p指向资源v。宏rcu_assign_pointer()只能被写者使用，在其定义中包含着一个优化格栅barrier，用于保证此前对v的修改都已生效，此后对p的引用都是最新的。(5)函数synchronize_rcu()仅能被写者使用，用于等待此前位于读方临界区中的所有读者都退出临界区，或者说等待当前的宽限期终止。7272(6)函数call_rcu()仅能被写者使用，用于向RCU注册一个回调函数。当宽限期终止时，RCU会执行此回调函数，完成写者进程

45、预定的处理工作。与synchronize_rcu()不同，执行call_rcu()的写者进程不需要等待，因而call_rcu()可以用在中断处理程序中。73739.4.2 RCU管理结构管理结构显然，RCU实现的关键是如何标识宽限期的开始和终止，或者说如何追踪各处理器的当前状态(静止与否)。经典RCU定义了一个全局位图cpumask，其中的每一位对应一个处理器。在宽限期开始时，经典RCU设置位图cpumask，将各处理器的对应位都置1。此后，各处理器分别监视自己的状态，并在进入静止态时将自己在cpumask中的位清0。一旦cpumask被清空，说明所有处理器都至少经历了一次静止态，一个宽限期也

46、就随之终止。7474当然，位图cpumask不能被多个处理器同时修改，因而需要一个自旋锁的保护。然而不幸的是，随着处理器数量的增加，保护位图cpumask的自旋锁会变成竞争的焦点，限制了RCU的伸缩性。为了提高RCU的伸缩性，新版本的Linux引入了层次RCU。层次RCU将处理器分成若干组，每组称为一个节点。组中处理器的个数(FANOUT)可静态配置，缺省值为64。层次RCU为每个节点定义了一个位图和一个保护锁。系统中所有的节点被组织成一个树形结构，每个下层节点在上层节点位图中有一个对应位。当进入静止态时，处理器通常只需清除自己在所属节点中的对应位。7575只有将节点位图清空的处理器才需要清除

47、本节点在上层节点中的对应位。当根节点的位图被清空时，说明所有的处理器都至少经历了一个静止态，宽限期随之终止，如图9.6所示。7676图9.6 层次RCU管理结构7777在图9.6中，1024个处理器被分成16组，每组64个。CPU0CPU63共用node1中的位图qsmask和保护锁，CPU64CPU127共用node2中的位图qsmask和保护锁等等。节点node1node16共用根节点node0中的位图qsmask和保护锁。当进入静止态时，CPU0CPU63仅需要清除node1中的位图qsmask，CPU64CPU127仅需要清除node2中的位图qsmask，依此类推。只有将node i

48、(i=116)中的位图清空的处理器才需要清除节点i在node 0中的对应位。对node i(i=116)来说，同时竞争其中保护锁的处理器数不会超过64个。对node 0来说，同时竞争其中保护锁的处理器数不会超过16个。7878因而，层次RCU增加了保护锁的数量，减少了竞争同一个保护锁的处理器的个数，降低了保护锁的竞争压力，提高了RCU的伸缩性。经典RCU的另一个问题是必须由各处理器自己清除位图cpumask，因而不得不经常唤醒睡眠中的处理器，会影响节能效果。为解决这一问题，层次RCU在PERCPU数据区中为每个处理器定义了一个状态计数器dynticks，其初值为1。当处理器进入空闲状态时，它的

49、dynticks被加1，变成偶数；当处理器退出空闲状态时，它的dynticks被再次加1，又变成奇数。当空闲状态(dynticks为偶数)的处理器被中断时，它的dynticks被加1，变成奇数；当中断处理完毕再次进入空闲状态时，处理器的dynticks又被加1，变成偶数。7979因而，dynticks为偶数标志着处理器处于空闲状态。由于空闲处理器不会引用RCU资源，所以它在位图qsmask中的状态位可以不用检查，处理器也不用被唤醒。系统在运行过程中会多次启动宽限期，但宽限期不能重叠，一个宽限期终止之后才能启动另一个宽限期。在一个特定的时刻，系统可能在宽限期内，也可能在宽限期外。在完成资源发布需

50、要等待宽限期时，如果系统在宽限期外，写者进程可以立刻启动一个新宽限期，并在该宽限期终止时释放老资源；如果系统正在宽限期内，那么当前宽限期的终止并不代表使用老资源的进程已全部离开读方临界区，写者进程需启动下一个宽限期，并等待下一个宽限期终止，如图9.7所示。8080图9.7 重叠的宽限期81 81在图9.7中，处理器2在t1时刻启动了宽限期1(GP1)，该宽限期到t3时刻终止。假如处理器1在t2时刻完成了对资源s的替换，由于t2在宽限期1内，不能立刻启动新宽限期，所以处理器1必须等待宽限期1终止之后才能启动宽限期2(GP2，从t4到t6)。虽然在t5时刻已没有处理器再引用资源s，但对它的释放却被