Linux内核设计与实现(11)---内核同步方法

内核产生竞争条件是比较复杂的，幸运的是，Linux内核提供了一组相当完备的同步方法，这些方法可以帮助内核开发者们能编写出高效而有自由竞争的代码；So, 尽量用Linux提供的接口函数, 不要造轮子.

1.原子操作

原子操作可以保证指令以原子的方式执行: 执行的过程不被打断，两个原子操作绝对不可能并发地访问同一个变量。

1.1 原子整数操作

针对整数的原子操作只能对atomic_t类型数据进行处理，这是为了确保编译器不对相应的值进行访问优化，也可以屏蔽在不同体系结构上实现原子操作时的差异；

atomic_t在中定义

typedef struct {
       volatile int counter;
} atomic_t;

原子操作函数在文件中

atomic_t v; //定义 v
atomic_t u = ATOMIC_INIT(0); //定义u 并把它初始化为0
操作也很简单:
atomic_set(&v,1);  // v=1,原子地
atomic_add(2, &v); //v= v+2原子地
atomic_inc(&v);    //v原子的加1
如果需要将atomic_t转换成int型，可以使用atomic_read();
printk(“%d\n”,atomic_read(&v));

原子操作常见的函数如下表：

原子性和顺序性

原子性确保指令执行期间不被打断，要么全部执行完，要么不执行；顺序性确保即使两条或更多条指令出现在独立的执行线程中，甚至独立的处理器上，它们本该的执行顺序却依然要保持(顺序性通过屏障barrier来实现)。

在编写代码时，能使用原子操作时，就尽量不要使用复杂的枷锁机制，相对加锁，原子操作给系统带来的开销小，对高速缓存行的影响也小。

1.2 64位原子操作

64位的原子变量跟32位功能几乎一样，定义在

#ifdef CONFIG_64BIT
typedef struct {
       volatile long counter;
} atomic64_t;
#endif

1.3 原子位操作

由于原子位操作是对普通指针进行的操作，所以没有特殊的数据类型，只要指针指向了任何你希望的数据，就可以对它进行操作。

函数定义在

unsigned long word = 0;
set_bit(0,&word);     //第0位被设置，原子地
clear_bit(1,&word);   //清空第一位
change_bit(2, &word); //反转第2位

内核还提供了一组与上述操作对应的非原子操作，在函数名前多加两个下划线,比如test_bit()对应的非原子形式是__test_bit();非原子为操作函数执行会更快些；

 

2.自旋锁

现实世界里，临界区可能是跨越多个函数的，这就需要使用更为复杂的同步方法—锁来提供保护。

Linux内核最常见的锁是自旋锁(spin lock)，自旋锁最多只能被一个可执行线程池持有，若一个执行线程试图获得一个被已经持有(即争用)的自旋锁，那么该线程就会一直进行忙循环，旋转，等待锁重新可用。要是锁未被争用，请求锁的线程立即得到锁，继续执行。

自旋锁主要特点是，被争用的自旋锁使得请求它的线程在等待锁重新可用是自旋，这特别消耗处理器，所以自旋锁不应该被长期持有，持有自旋锁时间最好小于完成两次上下文切换时间。

2.1 自旋锁方法

自旋锁的实现与体系结构密切相关，一般通过汇编实现，在，接口定义在定义，基本形式：

DEFINE_SPINLOCK(mr_lock);
spin_lock(&mr_lock);
/*临界区…*/
spin_unlock(&mr_lock);

自旋锁同一时刻至多被一个执行线程持有。

在单处理器上，编译的时候并不会加入自旋锁，它仅仅被当作一个设置内核抢占机制是否被启用的开关，如果禁止内核抢占，那么在编译时自旋锁会被完全剔除出内核。

自旋锁是不可以递归的，如果试图得到一个自己持有的锁，就会被锁死。

自旋锁可以使用在中断处理程序中(此处不能使用信号量，它会导致休眠)，但是一定要在获取锁之前，首先禁止本地中断(当前处理器中断请求)，否则持有锁代码可能被中断打断，有可能试图去争用这个中断持有的锁，导致双重请求死锁。如果中断发生在不同的处理器上，即使中断程序在同一锁上自旋，也不会妨碍锁的持有者最终释放锁。
用自旋锁的大原则：针对代码加锁会使得程序难以理解，并且容易引发竞争条件，正确的做法是对数据而非代码加锁。

内核提供了禁止中断同时请求锁的接口：

DEFINE_SPINLOCK(mr_lock);
spin_lock_irqsave(&mr_lock, flags);
spin_lock_irqrestore(&mr_lock, flags);

在单处理器系统上，虽然编译时抛弃了锁机制，但是上面的例子仍需关闭中断，以禁止中断处理程序访问共享数据，加锁和解锁分别可以禁止和允许内核抢占。

如果确定加锁前中断是激活的，那在解锁时可以无条件激活中断，用下列函数

DEFINE_SPINLOCK(mr_lock);
spin_lock_irq(&mr_lock);
spin_unlock_irq(&mr_lock);

但是由于内核庞大而复杂，有时很难高清到底有没有激活中断，所以不推荐使用这组函数。

调试自旋锁

配置选项CONFIG_DEBUG_SPINLOCK，可以添加一些调试检测手段，比如是否使用了位初始化的锁，是否在还没加锁前就执行开锁操作，如果需要进一步全程调试锁，还应该打开CONFIG_DEBUG_LOCK_ALLOC选项。

2.2 其他针对自旋锁的操作

初始化动态创建的自旋锁，可以用spin_try_lock()函数，如果锁已被争用，该方法立刻返回非0值，而不会自旋等待锁被释放，若成功获得锁，返回0；自旋锁还有其他错做如下

2.3 自旋锁和下半部

函数spin_lock_bh()用于获取指定锁，同时禁止所有下半部的执行，spin_unlock_bh()解锁。

(1)当下半部与进程上下文共享数据时，因为下半部可以打断进程上下文，必须对共享数据加锁，且禁止下半部运行。

(2)下半部和中断处理共享数据时，因为中断可以打断下半部，所以必须获取恰当的锁同时还要禁止中断。

(3)同类tasklet不能同时运行，所以同类tasklet的共享数据不需要保护，但是当数据被不同类型的tasklet共享时，在访问下半部中的数据前线获得一个普通锁，不需要禁止下半部，因为同一处理器上tasklet不会抢占。

(3)软中断，数据被软中断共享，必须有锁保护，同一处理器上软中断不会抢占另一个软中断，所以也没必要禁止下半部。

3.读-写自旋锁

当某个数据结构的操作可以被划分为类似读/写，或者消费者/生产者两种类别时，类似读/写锁这样的机制就很适用。Linux提供了专门的读-写自旋锁，一个或多个读任务可以并发地池有读者所；写锁最多只能被一个写任务持有，而且此时不能有并发读操作。有时把读/写锁叫做共享/排斥锁，或并发/排斥锁。

DEFINE_RWLOCK(mr_rwlock);
在读者的代码分支中使用
read_lock(&mr_rwlock);
/*临界区，只读…*/
read_unlock(&mr_rwlock);
在写者的代码分支中使用
write_lock(*mr_rwlock);
/*临界区，读写*/
write_unlock(&mr_rwlock);

通常情况下读锁和写锁位于完全分隔开的代码分支中，若不能明确区分读/写，就使用普通锁。

read_lock(&mr_rwlock);

write_lock(&mr_rwlock);

上述的把读锁升级为写锁，会导致死锁。，要在一开始就明确是使用读锁，还是死锁。

最后，当使用读-写自旋锁时，要考虑这种锁照顾读比写多一点，当写者等待大量读者时，可能会处于饥饿状态。这种行为有时候有益，有时候是有害的。

4.信号量

Linux的信号量是一种睡眠锁，当一个任务试图获得一个不可用的信号量时，信号量会将其推进一个等待队列，让其睡眠，这时处理器重获自由，当持有的信号量可用(被释放)后，处于等待队列中的任务被唤醒，并获得信号量。

信号量比自旋锁提供了更好的处理器利用率，但是其开销更大(任务切换)。

从信号量的睡眠特性可以得出一些结论：

①由于争用信号量的进程在等待锁可用时会睡眠，所以信号量适用于锁会被长时间持有的情况。

②相反，锁被短时间持有时，用信号量就不合适。因为睡眠、维护等待队列以及唤醒锁话费的开销可能比锁被占用的全部时间还长。

③因为持有信号量的进程可以睡眠，所以只能在进程上下文中才能获取信号量锁，中断中不能用。

④当其他进程试图获得被占用锁时，会去睡眠，所以不会产生死锁。

⑤占用信号量的同时不能占用自旋锁，因为等待信号量时可能会睡眠，而持有自旋锁时不允许睡眠。

信号量不会禁止内核抢占，持有信号量的代码可以被抢占，持有信号量不会对调度的等待时间带来负面影响。

4.1 计数信号量和二值信号量

信号量同时允许的持有者数量可以在申明信号量时指定，这个值称为使用者数量。计数数量等于1的信号量，叫做二值信号量或互斥信号量。大于1的信号量叫做计数信号量。但这汇总信号量在内核使用机会不多，内核用到的信号量，基本上都是互斥信号量。

信号量支持两个原子操作，P()和V()，也可以叫down()和up()操作。Down一个信号量就等于获取该信号量，当临界区完成操作后，up()操作用提升count值释放信号量，如果该信号量上的等待队列不为空，那么处于队列中的等待任务在被唤醒的同时会获得该信号量。

4.2 创建和初始化信号量

信号量的实现与体系结构相关，在定义

struct semaphore name;
sema_init(&name, count);//name 位信号量名字，count位信号量初值
还可以用更快捷的方式静态创建互斥信号量
static DECLARE_MUTEX(name);
初始化一个动态创建的互斥信号量时可以用
init_MUTEX(sem);

4.3 使用信号量

函数down_interruptible()试图获取指定的信号量，若信号量被占用，它将调用进程设置成TASK_INTERRUPTIBLE状态，进入睡眠。

函数down()函数会让进程在TASK_UNINTERRUPTIBLE状态下睡眠(不能被信号唤醒，一般不用)。

函数down_trylock()，尝试以堵塞方式来获取指定信号量，信号量被占用，立刻返回非0值，否则它返回0，让你持有信号量锁。

释放信号量用up()函数。

static DECLARE_MUTEX(mr_sem);

if (down_interruptible(&mr_sem)) {
       /*信号被接收，信号量还未获取*/
}
/*临界区*/
up(&mr_sem);

5.读-写信号量

如果代码中的读和写可以明白无误地分割开来，也可以使用类似于读写自旋锁的读-写信号量，在定义

静态创建：Static DECLARE_RWSEM(name);

初始化动态创建：init_rwsem(struct rw_semaphore *sem);

所有读写信号量都是互斥信号量，对于读者可以多数，但是对于写者，只能一个进程持有。由于所有读-写锁的睡眠都不会被信号打断，所以都只有一个版本down(0操作。

static DECLARE_RWSEM(mr_rwsem);
down_read(&mr_rwsem);
/*临界区*/
up_read(&mr_rwsem);
down_write(&mr_rwsem);
/*临界区*/
up_write(&mr_rwsem)

读-写信号量比读-写自旋锁多一个操作，downgrade_write()，这个函数可以动态地将获取的写锁转换为读锁。

 

6.互斥体

互斥体是一种比信号量更简单的睡眠锁，mutex指的是任何可以睡眠的强制互斥锁。

静态声明：DEFINE_MUTEX(name);
动态初始化：mutex_init(&mutex);
mutex_lock(&mutex);
/*…*/
mutex_unlock(&mutex);

实际就是一个简化版的信号量，它的其他方法如下

mutex的简洁和高效性源于比信号量更多的限制：

①任何时刻只有一个任务可以持有mutex;

②给mutex上锁这必须负责给其再解锁，这个限制使得mutex不适合内核同用户空间复杂的同步场景，最常用的方式是，在同一上下文上锁和解锁；

③递归地上锁和解锁是不允许的；

④当持有一个mutex时，进程不可以退出；

⑤mutex不能在中断或下半部中使用，即使使用mutex_trylock()也不行；

⑥mutex只能通过官方API管理，不可被拷贝，手动初始化或者重复初始化；

通过一个特殊的调试模式，配置CONFIG_DEBUG_MUTEXES, 内核可以检查和警告任何践踏其约束法则的不老实行为。

6.1 信号量与互斥体

互斥体和信号量很相似，容易混淆，所幸，它们的标准使用方式都有简单的规范：除非mutex的某个约束妨碍你使用，否则相比信号量优先使用mutex。只有碰到特殊场合才需要使用信号量，一般首选mutex。

6.2 自旋锁与互斥体

在中断上下文中只能使用自旋锁，而在任务睡眠时只能使用互斥体

7.完成变量

如果在内核中一个任务需要发出信号通知另一任务发生了某个特定事件，利用完成量是使两个任务的一同步的简单方法。例如当子进程执行或退出时，vfork()系统调用使用完成变量唤醒父进程。

完成变量由completion表示，在定义

DECLARE_COMPLETION(mr_comp);

也可以通过init_completion动态创建并初始化完成变量。

在一个指定事件发生后，需要等待的任务调用wait_for_completion()来等待特定事件，当特定事件发生后，产生事件的任务调用complete()来发送信号唤醒正在等待的任务

完成变量的例子可以参考 kernel/sched.c和 kernel/fork.c。

 

8.大内核锁BLK

BKL是一个全局的自旋锁，使用它主要是为了方便实现从Linux最初的SMP过渡到细粒度加锁机制。特点如下：

①持有BKL的任务仍然可以睡眠；

②BKL是一种递归锁

③BKL只可以用在进程上下文中；

④新代码已经不再使用BKL;

BKL在定义：

lock_kernel();
/*临界区*/
unlock_kernel();

函数kernel_locked()用于检测，若锁被持有返回非0值，否则返回0；

 

9.顺序锁

简称seq锁，这种锁，用于读写共享数据，实现这种锁主要依靠一个序列计数器。在读取数据之前和之后，序列号都被读取，若相同说明读取过程没有被写操作打断。如果读取的值是偶数，表明写操作没有发生（锁初值是0，所以写锁会使值称为奇数，释放时变成偶数）。

seqlock_t mr_seq_lock = DEFINE_SEQLOCK(mr_seq_lck);
写锁方法如下：
write_seqlock(&mr_seq_lock);
/*写锁被获取*/
write_sequnlock(&mr_seq_lock);
这和普通自旋锁类似，不同情况发生在读时
unsigned long seq;
do {
       seq = read_seqbegin(&mr_seq_lock);
}while (read_seqretry(&mr_seq_lock, seq));

seq锁在以下情况时最适用：

①你的数据存在很多读者；

②你的数据写者很少；

③虽然写者很少， 但是你希望写优先于读，而且不允许读者让写者饥饿；

④你的数据结构简单，甚至是简单的整型（某些场合，不能使用原子操作）；

Linux中seq锁的实例是jiffies

u64 get_jiffies_64(void)
{
       unsigned long seq;
       u64 ret;

       do {
              seq = read_seqbegin(&xtime_lock);
              ret = jiffies_64;
       } while (read_seqretry(&xtime_lock, seq));
       return ret;
}

定时器中断会更新jiffies的值

write_seqlock(&xtime_lock);
jiffies_64 += 1;
write_sequnlock(&xtime_lock);

10.禁止抢占

为了防止当处理器上的伪并发(单处理器没加自旋锁)，可以通过preempt_disable()禁止内核抢占。这个函数可以嵌套，但每次调用都必须有一个相应的preempt_enable()调用，当最后一次preempt_enable()被调用后，内核抢占才重新启动。

preempt_disable()；
/*抢占被禁止*/
preempt_enable()；

抢占计数存放着被持有锁的数量和preempt_disable()的调用次数，如果计数是0，那么内核可以抢占，如果为1或更大，内核不会进行抢占。这个技术非常有用—它是一种对原子操作和睡眠很有效的雕花死方法。内核抢占相关的函数：

为了更简洁的方法来解决每个处理器上的数据访问问题，可以通过get_cpu()获取处理器编号，这个函数在返回当前处理器号前首先会关闭内核抢占。

int cpu;
//禁止内核抢占，并将CPU设置为当前处理器
cpu = get_cpu();
/* 对每个处理器的数据进行操作*/
put_cpu(); //再给予内核抢占性

11.顺序和屏障

当处理多处理器之间或硬件设备之间的同步问题时，有时需要代码按指定的顺序发出读写内存指令。而编译器和处理器为了提高效率，可能对读和写重新排序。为保证数据的安全，有时必须引入可以指示编译器不对给定点周围代码重新排序的机器指令，这些确保顺序的指令就是屏障(barriers).

rmb()方法提供了一个“读”内存屏障，它确保跨越rmb()的载入动作不会发生重排序。

wmb()提供一个“写”内存屏障，功能与rmb()类似，但是仅针对存储而非载入，它确保跨越屏障的存储不发生重排序。

read_barrier_depends()是rmb()的变种，它仅针对后续读操作所依靠的那些载入。在有的体系结构上read_barrier_depends()会执行的快一些。

barrier()方法可以防止编译器跨屏障对载入或存储操作进行优化，编译器屏障要比内存屏障轻量的多(执行的快)。

内核中所有体系机构提供的完整内存和编译器屏障方法如下