分类： LINUX
2009-06-21 21:42:28
同步机制用于避免对共享数据的不安全访问而导致的数据崩溃。下面按从轻到重讲述内核同步机制。
同步是一件烦人、容易出错，最重要的是拖慢并行的事情，所以最好的同步就是不用同步——这不是废话，而是在内核设计时的重要考虑。对不同的任务，量 体裁衣，以不同的机制来处理；对每种机制，加以不同程度的限制，从而不同程度地简化用这个机制完成任务的编码难度，其中就包括减少对同步机制的需要。以下 是一些书中举出的“设计简化同步”的例子：
Interrupt handlers and tasklets need not to be coded as reentrant functions.
Per-CPU variables accessed by softirqs and tasklets only do not require synchronization.
A data structure accessed by only one kind of tasklet does not require synchronization.
第二好的同步技术，是不共享。因此我们有了每CPU变量。但注意：内核抢占可能使每CPU变量产生竞争条件，因此内核控制路径应该在禁用抢占的情况下访问每CPU变量。
具有“读-修改-写”特征的指令，如果不是原子的，就会出现竞争条件。
非对齐的内存访问不是原子的；
单处理器中，inc、dec这样的操作是原子的；
多处理器中，由于会发生内存总线被其它CPU窃用，所以这些操作要加上lock前缀（0xf0），这样可以锁定内存总线，保证一条指令的原子性；
有rep前缀(0xf2、0xf3)的指令不是原子的，每一循环控制单元都会检查挂起的中断。
Linux提供了atomic_t和一系列的宏来进行原子操作。
编译器喜欢在优化代码时重新安排代码的执行顺序，由于它对某些代码顺序执行的意义没有感知，所以可能对一些必须顺序执行的代码构成致命伤，比如把同步原语之后的指令放到同步原语之前去执行——顺便带一句，C++0x中对并行的改进正是努力使编译器能感知这些顺序的意义。
优化屏障barrier()宏，展开来是asm volatile("":::"memory") 。这是一段空汇编，但volatile关键字禁止它与程序中的其它指令重新组合，而 memory则强迫编译器认为RAM的所有内存单元都给这段汇编改过了，因此编译器不能因为懒惰和优化直接使用之前放在寄存器里的内存变量值。但 优化屏障只阻止指令组合，不足以阻止指令重新排序。
内存屏障原语mb()保证，在原语之后的操作开始执行之前，原语之前的已经完成，任何汇编语言指令都不能穿过内存屏障。
80x86处理器中，I/O操作指令，有lock前缀的指令，写控制、系统、调试寄存器的指令，自动起内存屏障的作用。Pentium 4还引入了lfence、sfence和mfence这些指令，专门实现内存屏障。
rmb()在Pentium 4之后使用lfence，之前则使用带lock的无意义指令来实现。wmb()直接展开为barrier()，因为Intel处理器不会对写内存访问重新排序。
自旋锁是一种忙等的锁，当获取锁失败，进程不会休眠，而是一直在那里自旋（spin）或者说忙等（busy waiting），不断循环执行cpu_relax()——它等价于pause指令或者rep; nop指令。
自旋锁用spinlock_t表示，其中两个字段，slock代表锁的状态（1为未锁），break_lock代表有无其它进程在忙等这个锁，这两个字段都受到原子操作的保护。
我们详细讨论一下spin_lock(slp)宏（slp代表要获取的spinlock_t）：
首先禁用内核抢占（preempt_disable()），然后调用平台相关的_raw_spin_trylock()，其中用xchg原子性地交 换了8位寄存器%al（存着0）和slp->slock，如果交换出来的是正数（说明原先未锁），那么锁已经获得（0已经写入了 slp->slock，上好了锁）。
否则，获锁失败，执行下列步骤：
1）执行preempt_enable()，这样其它进程就有可能取代正在等待自旋锁的进程。注意preempt_enable()本质上仅仅是将 显式禁用抢占的次数减一，并不意味着就一定可以抢占了，能否抢占还取决于本次禁用之前有否禁用抢占、是否正在中断处理中、是否禁用了软中断以及 PREEMPT_ACTIVE标志等等因素。就像，领导说：“我这里没问题了，你问问别的领导的意见吧。”。
2）如果break_lock==0，就置为1.这样，持有锁的进程就能感知有没人在等锁，如果它觉得自己占着太长时间了，可以提前释放。
3）执行等待循环：while (spin_is_locked(slp) && slp->break_lock) cpu_relax();
4）跳转回到“首先”，再次试图获取自旋锁。
奇怪的是，我未能在LXR中找到这段描述对应的源代码，也无从验证我由while (spin_is_locked(slp) && slp->break_lock) 产生的的一个疑问：当锁易手之后，怎么处理break_lock这个字段？
读/写自旋锁允许并发读，写锁则独占。注意：在已有读者加读锁的情况下，写者不能获得写锁。读/写自旋锁rwlock_t的32位字段lock使用 了25位，拆分为两部分，24位被设置则表示未锁，0-23位是读者计数器的补码，有读者时，0-23位不为0，有写者时，0-23位为0（写时无读 者）。
顺序锁则允许在读者正在读的时候，写者写入。这样做的优点是：写者无需等待读锁，缺点是有时读者不得不重复读取直到获得有效的副本。顺序锁 seqlock_t有两个字段：一个是spinlock_t，写者需要获取，一个是顺序计数器，写者写时其值为奇数，写完时为偶数。读者每次读，前后都会 检查顺序计数器。
顺序锁的适用场合：读者的临界区代码没有副作用，写者不常写，而且，被保护的数据结构不包括写者会改而读者会解引用（dereference, *）的指针。
锁还是少用的好：使用被所有CPU共享的锁，由于高速缓存行侦听（原书译为窃用）和失效而有很高的开销（a high overhead due to cache line-snooping and invalidation）。
RCU允许多个读者和写者并发运行，它不使用锁，但它仅能保护被动态分配并通过指针引用的数据结构，而且在被RCU保护的临界区，任何内核控制路径都不能睡眠。
读者读时执行rcu_read_lock()（仅相当于preempt_disable()），读完执行rcu_read_unlock()（仅相当于 preempt_enable( ) ）。这很轻松，但是，内核要求每个读者在执行进程切换、返回用户态执行或执行idle循环之前，必须结束读并执行 rcu_read_unlock()，原因在写者这边：
写者要更新一个数据结构的时候，会读取并制作一份拷贝，更新拷贝里的值然后修改指向旧数据的指针指向拷贝，这里会使用一个内存屏障来保证只有修改完 成，指针才进行更新。但难点是，指针更新完之后不能马上释放旧数据，因为读者可能还在读，所以，写者调用call_rcu()。
call_rcu()接受rcu_head描述符（通常嵌入在要释放的数据结构中——它自己知道自己是注定要受RCU保护的）的指针和回调函数（通常用来“析构”...）作为参数，把它们放在一个rcu_head描述符里，然后插入到一个每CPU的链表中。
每一个时钟中断，内核都会检查是否已经经过了静止状态（gone through quiescent state，即已发生进程切换、返回用户态执行或执行idle循环） ——如果已经经过了静止状态，加上每个读者都遵循了内核的要求，自然所有的读者也都读完了旧拷贝。如果所有的CPU都经过了静止状态，那么就可以大开杀戒，让本地tasklet去执行链表中的回调函数来释放旧的数据结构。
RCU是2.6的新功能，用在网络层和虚拟文件系统中。
（按：RCU描述起来可累了，尤其是原书和源代码中对静止状态都语焉不详，很难理解其确切含义，暂时只能整理成上面这种理解，以后在研究下 usage，弄清实际上应该如何理解。疑问所在：因为静止状态从字面上感觉，应该指旧数据结构仍需“静止地”残余的状态，但是由于内核后来还需要检查是否 否度过了静止阶段，那么如何检查这种“仍需”？显然更为容易的是检查进程切换什么的，所以只好把静止状态理解为还未发生进程切换、返回用户态执行或执行idle循环的状态，然后再“ 经过了 ”。怎么想怎么别扭。）
这个可不是System V的IPC信号量，仅仅是供内核路径使用的信号量。信号量对于内核而言太重了，因为获取不到锁的时候需要进程睡眠！所以中断处理程序不能用，可延迟函数也不能用...
信号量struct semaphore包含3个字段，一个是atomic_t的count，也就是我们在IPC信号量那里已经熟知的表示可用资源的一个计数器；一个是一个互 斥的等待队列，因为这里涉及了睡眠，信号量的up()原语在释放资源的同时需要唤醒一个之前心里堵得慌睡着了的进程；最后一个是sleepers，表示是 否有进程堵在那里，用于在down()里面进行细节得恐怖而又非常有效的优化（为此，作者感叹：Much of the complexity of the semaphore implementation is precisely due to the effort of avoiding costly instructions in the main branch of the execution flow.）
自然还有读/写信号量，这里不再敷述。
原书将之非常不准确地翻译为补充原语。
Completion是一种类似信号量的原语，其数据结构如下：
struct completion { unsigned int done; wait_queue_head_t wait; };
它拥有类似于up()的函数complete()和类似于down()的wait_for_completion()。
它和信号量的真正区别是如何使用等待队列中包含的自旋锁。在完成原语这边，自旋锁用来确保complete()和wait_for_completion()之间不会相互竞争（并发执行），而在信号量那边，自旋锁用于避免down()与down()的相互竞争。
那么在什么情况下up()和down()可能出现竞争呢？
其实do_fork()的源代码中就包含一个活生生的例子，用于实现vfork()，下面略去了与vfork()无关的代码：
local_irq_disable()宏使用了cli汇编指令，通过清除IF标志，关闭了本地CPU上的中断。离开临界区时，则会恢复IF标志原先的值。
禁止中断，在单CPU情形可以确保一组内核语句被当作一个临界区处理，因为这样不会受到新的中断的打扰。然而多CPU的情形中，禁止的仅是本地 CPU的中断，因此，要和自旋锁配合使用，Linux提供了一组宏来把中断激活/禁止与自旋锁结合起来，例如spin_lock_irq()、 spin_lock_bh()等。
可延迟函数禁止是中断禁止的一种弱化的形式，它通过前一篇笔记描述过的preempt_count字段来进行，具体的调用函数是local_bh_disable()。这里不再重复。
为了性能，系统的并发度应该尽可能高。它取决于同时运转的I/O设备数（这需要尽可能减短中断禁止的时间），也取决于进行有效工作的CPU数（这需要尽可能避免使用基于自旋锁的同步原语，因为它对硬件高速缓存有不良影响）。
有两种情况，既可以维持较高的并发度，也可以达到同步：
共享的数据结构是一个单独的整数值，这样原子操作就足以保护它，这是在内核中广泛使用的引用计数器；
类似将元素插入链表中这样的操作设计两次指针赋值，虽然不是原子的，但只要两次赋值依序进行，单一的一次操作仍能保证数据的一致性和完整性，因此，需要在两个指针赋值中间加入一个写内存屏障原语。
大内核锁从前被广泛使用，现在用于保护旧的代码，从前它的实现是自旋锁，2.6.11之后则变成了一种特殊的信号量kernel_sem。kernel_sem中有一个lock_depth的字段，允许一个进程多次获得BKL。
改变实现的目的是使得在被大内核锁保护的临界区内允许内核抢占或自愿切换。在自愿进程切换的情形（进程在持有BKL的情况下调用 schedule()），schedule()会为之释放锁，切换回来的时候又为之获取锁，非常周到的服务。在抢占的情 形，preempt_schedule_irq()会通过篡改lock_depth欺骗schedule()这个进程没有持有BKL，因此被抢占的进程得 以继续持有这个锁。
From：http://utensil.javaeye.com/blog/411295
