Linux内核设计与实现ch10 内核同步方法

发表于 更新于 Changyan：
本文字数： 8.6k 阅读时长 ≈ 8 分钟

Linux内核设计与实现ch10 内核同步方法

10.1 原子操作

原子操作可以保证命令以原子方式执行，不会被打断。内核提供了两组原子操作接口——一组针对整数进行操作，一组针对单独位进行操作。在Linux支持的所有体系结构上都实现了这两组接口。大多数体系结构都会提供支持原子操作的简单算数指令，而有些体系结构缺少简单的原子操作指令，但是也提供了锁存总线的指令。

10.1.1 原子整数操作

针对原子整数操作只能对atomic_t（定义在<linux/types.h>中）的数据类型进行处理，在64位系统中也存在类似的atomic64_t。在这里没有直接使用c语言的int类型，是处于几个方面考虑：

  • 一是希望原子操作只对这种特殊类型起作用，而且该类型的数据不会传给任何非原子数。
  • 二是确保了编译器不会对相应的值做出优化——使得原子操作最后能收到正确的地址而非别名。
  • 三是希望在不同结构体系上实现原子操作的时候，atomic_t可以屏蔽其间的差异。

其定义如下：

1
2
3
4
5
6
7
8
9
typedef struct {
        int counter;
} atomic_t;

#ifdef CONFIG_64BIT
typedef struct {
        s64 counter;
} atomic64_t;
#endif

尽管Linux支持的所有机器的整形数据都是32位，但是atomic_t只将该类型的数据作为24位来使用。这个限制是因为在SPRAC体系结构上，原子操作实现与其他体系不同。32位int类型的低八位被嵌入了一个锁。SPRAC结构缺乏对原子操作指令集的支持，所以只能用锁来避免原子类型数据被并发访问

使用原子操作需要的类型声明存放在<arch/体系结构名称/include/asm/atomic.h>中。有些体系结构会提供一些只能在该体系结构上的额外原子操作方法，但所有体系结构都能保证内核上使用到的操作的最小集。

定义一个atomic_t类型的数据很平常，可以在定义的时候给他赋初值。

1
2
atomic_t v;
atomic_t u = ATOMIC_INT(0);   /*init and set to zero*/

下表列出了所有的标准原子操作，某些特定的体系结构上实现的操作可以在atomic.h中找到。

操作函数 描述
ATOMIC_INIT(int i) 声明一个atoimic_t变量时将其初始化为i
int atomic_read(atomic_t *v) 读取原子变量v并返回其int值
void atomic_set(atomic_t *v, int i) 原子的将v值设置为i
void atomic_add(int i, atomic_t *v) 原子地给v加上i
void atomic_sub(int i, atomic_t *v) 原子地给v减去i
int atomic_inc(atomic_t *v) 原子地给v加上1
int atomic_dec(atomic_t *v) 原子地给v减去1
void atomic_add_return(int i, atomic_t *v) 原子地给v加上i，且返回结果
void atomic_sub_return(int i, atomic_t *v) 原子地给v减去i，且返回结果
int atomic_inc_return(atomic_t *v) 原子地给v加上1，且返回结果
int atomic_dec_return(atomic_t *v) 原子地给v减去1，且返回结果
bool atomic_inc_and_test(atomic_t *v) 原子地给v加上1，如果结果为0，返回真，否则返回假
bool atomic_dec_and_test(atomic_t *v) 原子地给v减去1，如果结果为0，返回真，否则返回假

原子操作往往是内联函数，通过内嵌汇编指令来实现的。如果某个函数本身就是原子的，那么往往会定义一个宏。例如在大部分体系结构上，读取一个字节本身就是原子操作。

64位的函数只需要在所有的函数中的atomic后面加64，例如atomic64_sub()

10.1.2 原子位操作

与原子位操作相关的函数定义在<arch/体系结构名称/include/asm/atomic.h>中。这里的位操作函数是对普通的内存地址进行操作的，形参是一个指针加一个位号。并且对位号没有做限制。例如在32位上31位是最高有效位，但可以指定32为下一个字的最低有效位。下面给出了原子位操作的表

原子位操作 描述
void set_bit(int nr, void *addr) 原子地设置addr所指对象的第nr位
void clear_bit(int nr, void *addr) 原子地清空addr所指对象的第nr位
void change_bit(int nr, void *addr) 原子地翻转addr所指对象的第nr位
int test_and_set_bit(int nr, void *addr) 原子地设置addr所指对象的第nr位，并返回原先的值
int test_and_clear_bit(int nr, void *addr) 原子地清空addr所指对象的第nr位，并返回原先的值
int test_and_change_bit(int nr, void *addr) 原子地翻转addr所指对象的第nr位，并返回原先的值
int test_bit(int nr, void *addr) 原子地返回addr所指对象的第nr位

为了方便起见，内核还提供了一组与上述对应的非原子性操作，其名字前有两个下华夏，例如set_bit()的非原子对应形式就是__set_bit()。如果不需要原子操作的话，非原子操作可能会执行的更快一些。

10.2 自旋锁

自旋锁是linux内核中最常见的锁。自旋锁最多只能被一个可执行进程所占有。如果一个执行线程试图获取一个被持有的自旋锁，那么该线程就会一直进行忙循环-旋转-等待锁重新可用。而锁未被持有的话，进程就会立刻得到它。自旋锁的要点是进程等待锁可用时自旋，这种行为特别浪费处理器时间。所以自旋锁不应该被长时间持有。

10.2.1 自旋锁方法

自旋锁的实现与体系结构紧密相关，往往通过汇编来实现。这些与体系相关的代码定义在文件<asm/spinlock.h>中，实际需要用到的接口文件在<linux/spinlock.h>中。自旋锁的基本使用形式如下：

1
2
3
4
DEFINE_SPINLOCK(mr_lock);
spin_lock(&mr_lock);
/*临界区*/
spin_unlock(&mr_lock);

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

与其他操作系统不同，Linux内核实现的自旋锁不可递归。所以在设计的时候要注意避免死锁问题！

自旋锁可以使用在中断处理程序中（第七章就使用了自旋锁）。在中断处理程序中使用自旋锁之前一定要先禁止本地中断（当前处理器上的中断）。否则中断处理程序就会打断持有锁的内核代码。有可能导致死锁。

内核提供了禁止中断并且请求锁的接口，使用起来很方便，其方法如下：

1
2
3
4
5
6
DEFIDEFINE_SPINLOCK(mr_lock);
unsigned long flags;

spin_lock_irqsave(&mr_lock, flags);
/*临界区*/
spin_unlock_irqrestore(&mr_lock, flags);

函数spin_lock_irqsave保存中断当前状态，并禁止本地中断，然后再去获取指定的锁。反过来spin_unlock_irqrestore对指定的锁解锁，让中断恢复到加锁前的状态。

这里的flag看起来是传值的，是因为函数实现有些部分是通过宏来实现的。在单处理器上，加锁和解锁能分别禁止和允许内核进行抢占。

配置选项CONFIG_DEBUG_SPINLOCK为使用自旋锁代码加入了许多调试手段，必须是否使用未初始化的锁以及是否还未加锁时就执行开锁操作。如果需要进一步全程调试锁，则需要打开CONFIG_DEBUG_LOCL_ALLOC选项。

10.2.2 其他针对自旋锁的操作

自旋锁的初始化可以使用spin_lock_init()来实现。spin_try_lock()试图获得某个特定的锁，如果该锁已被征用，该方法立刻返回一个非0值，不会自旋等待锁释放。如果成功获得了这个自旋锁，则函数返回0。同理，spin_is_locked()方法用于检查待定的锁当前是否被占用，若已占用返回非0值，否则返回0值。但是该方法只做判断，并不实际占用。

10.2.3 自旋锁和下半部

由于下半部可以抢占进程上下文中的代码，所以下半部和进程上下文共享数据时，必须对进程上下文中的共享数据进行保护，所以需要加锁的同时禁止下半部的执行(spin_lock_bh())。spin_unlock_bh()来执行相反操作。

由于同类的tasklet不可能同时运行，所以对于同类tasklet中的共享数据不需要保护。但是当数据被两个不同种类的tasklet共享时，就需要在访问下半部的数据中先获得一个普通的自旋锁。（因为同一个处理器上不会有testlet抢占的情况出现，所以不需要禁止下半部）

10.3 读写自旋锁

为了读写场景的不同需求，内核提供了专门的读-写自旋锁。这种锁为读和写提供了不同的锁。多个读任务可以并发的持有读者锁，而写者锁只能同时被一个写任务持有。读写锁的使用方法类似于普通的自旋锁，通过以下方法进行初始化：

1
DEFINE_RWLOCK(mr_rwlock);

在读者代码分支中使用如下函数：

1
2
3
read_lock(&mr_rwlock);
/*临界区（只读）*/
read_unlock(&mr_rwlock);

写者代码分支中使用如下函数：

1
2
3
write_lock(&mr_rwlock);
/*临界区（只读）*/
write_unlock(&mr_rwlock);

通常情况下，读锁和写锁会位于完全割离开的代码分支中，但是要注意不能将一个读锁升级为写锁，否则可能会带来死锁。如果读写不能清晰分开的话更好的方法是使用一般的自旋锁。

要注意在内核中的读写自旋锁中，锁机制照顾读比照顾写多一点，所以如果读锁持有而未被释放时，写操作只能进行等待。但其他读者可以很轻松的占有锁。这样会导致写锁饥饿。所以在设置锁的时候要考虑到这一点。

10.4 信号量

Linux中的信号量是一种睡眠锁。如果一个任务试图获取一个不可用的信号量时，信号量将会将其推入一个等待队列，并使其休眠，从而让处理器能够执行其他代码。当持有的信号量被释放时，处于等待队列的进程被唤醒，并可以获取该信号量。但是要注意的是信号量的开销要比自旋锁更大。

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

  • 由于征用信号量的进程在等待的时候会进入睡眠，所以信号量适用于锁会被长时间持有的情况。
  • 与第一条相反，如果锁短时间持有的情况下，由于睡眠，维护等待队列以及选择唤醒的开销会比锁占有的全部时间还要长。
  • 中断上下文中是不能调度的，所以只有在进程上下文过程中才能获取信号量锁。
  • 在持有信号量时可以去睡眠，其他进程试图获取该信号量时不会因此死锁。
  • 在占用信号量的同时不能占用自旋锁。因为信号量机制允许睡眠，而自旋锁不允许睡眠。

要注意信号量不同于自旋锁的地方，信号量不会禁止内核抢占，也就意味着信号量不会对调度的等待时间产生负面影响。

下面是关于信号量的一些使用方法，这些方法定义在<asm/semaphore.h>中。struct semaphore类型来表示信号量。各种操作定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//创建信号量
struct semaphore name;
sema_init(&name, count);

//创建互斥信号量
static DECLARE_MUTEX(name);

//初始化指向信号量的间接指针
sema_init(sem, count);
init_MUTEX(sem);

//试图获取指定的信号量，
down_interruptible(&name);   //如果信号量不可用则进入睡眠。(在获取信号量之后返回-EINTR),睡眠时的状态为TASK_INTERRUPTIBLE(可被中断唤醒)
down(&name);                 //如果信号量不可用则进入睡眠。睡眠时的状态为TASK_UNINTERRUPTIBLE(不可被中断唤醒)
down_trylock(&name);         //以堵塞的方式获取指定信号量，在信号量被占用时立即返回非0值，否则返回0

up(&name);                   //释放指定信号量，如果睡眠队列不为空，则唤醒一个任务

10.5 读写信号量

读写信号量是由rw_semaphore结构表示的，定义在文件<linux/rwsem.h>中。以下是函数操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//声明读写信号量
static DECLARE_RWSEM(name);

//动态创建读写信号量
init_rwsem(struct rw_semaphore *sem);

//获取用于读的信号量
down_read(&mr_rwsem);
down_read_trylock(&mr_rwsem);   //效果类似于down_trylock(&name);

//释放信号量
up_read(&mr_rwsem);

//获取用于写的信号量
down_write(&mr_rwsem);
down_write_trylock(&mr_rwsem);   //效果类似于down_trylock(&name);

//释放信号量
up_write(&mr_rwsem);

downgrade_write(); //动态的将写锁转为读锁

10.6 互斥锁

mutex的实现方式与使用计数为一的信号量类似，但操作接口更加简单，实现也更加高效。而且使用限制更强

  • 任意一个时刻只能有一个任务可以持有mutex
  • 给mutex上锁的人要负责解锁（解锁和上锁要在同一个上下文中执行）
  • 持有一个mutex时进程不可以退出
  • mutex不能在下半部分或中断使用
  • mutex只能通过官方API管理，不可被拷贝，手动初始化或者重复初始化。
1
2
3
4
5
6
7
8
9
10
11
12
13
//静态定义mutex
DEFINE_MUTEX(name);
//动态
mutex_init(&mutex);

//锁定
mutex_lock(&mutex);

//解锁
mutex_unlock(&mutex);

mutex_trylock(&mutex);
mutex_is_locked(&mutex);

10.7 完成变量

完成变量(completion variable)是同步两个任务的简单方法，它使得内核中的一个任务可以发出信号通知另一个任务发生了某个特定事件。如果一个任务要执行一个工作时，另一个任务就会在完成变量上等待。当这个任务完成工作后，会使用完成变量去唤醒在等待的任务。

事实上，完成变量仅仅提供了代替信号量的一个简单的解决办法，例如：子进程执行或者退出时，vfork()系统调用使用完成变量唤醒父进程。

完成变量由结构completion表示，定义在<linux/completion.h>中，可以通过DECLARE_COMPLETION(mr_comp)去静态的创建变量并将其初始化。或者通过init_completion()动态创建并初始化完成变量。

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

方法 描述
init_completion(struct completion *) 初始化指定的动态创建的完成变量
wait_for_completion(struct completion *) 等待指定的完成变量接收信号
complete(struct completion *) 发信号唤醒任何等待任务

使用完成变量的例子可以参考kernel/sched.c以及kernel/fork.c。完成变量的通常用法是：将完成变量作为数据结构中的一项进行动态创建，而完成数据结构初始化工作的内核代码将调用wait_for_completion()进行等待。初始化完成后，初始化函数调用completion()唤醒在等待的内核任务。

10.8 顺序锁

顺序锁，也成为seq锁，从linux 2.6版本中引入，这种锁提供了一种很简单的机制，用于读写共享数据。实现这种锁主要依靠一个序列计数器。当有疑义的数据被写入时，会得到一个锁。而且序列值会增加。在读取数据前后会读取序列号。

  • 如果读取的序列号值相同，说明在读操作进行的过程中没有被写操作打断过，
  • 如果读取的是偶数，则表明写操作没有发生

（锁的初始值是0，所以写锁会将值置为奇数，写锁释放的时候会变为偶数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//定义seq锁
seq_lock mr_seq_lock = DEFINE_SEQOCK(mr_seq_lock);

//写锁
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锁对写者更有利。只要没有其他写者，写锁总是能被成功获取。挂起的写者会使得读不断循环，直到没有写者持有锁为止。

Seq锁主要适用于以下几个方向：

  • 读者比写者多得多，写者很少
  • 希望优先读，并且不允许读者让写者饥饿
  • 数据简单，只有简单的结构或者甚至简单的标准类型

使用seq锁最具有说服力的是jiffies。该变量存储了Linux机器启动到当前时间。该方法的实现就使用了seq锁。

10.9 禁止抢占

由于内核是抢占性的，内核中的进程在任何时刻都可能停下来以便另一个具有更高优先权的进程运行。这就意味着一个任务与被抢占的任务可能会在同一个临界区运行。为了避免这种情况，内核抢占代码使用自旋锁作为非抢占区域的标记。如果一个自旋锁被持有，内核便不能进行抢占。如果自旋锁没有被持有，并且内核又是抢占式的，那么一个新的调度任务就可能会访问同一变量，从而引发问题。

通过preempt_disable()禁止内核抢占，这个函数可以调用任意次，每次调用都要有一个相应的preempt_enable()调用。当最后一次preempt_enable()调用后，内核抢占才重新启用。

10.10 顺序和屏障

当处理多处理器或者硬件设备之间的同步问题时，可能需要程序代码中以指定的顺序发出读写内存的指令。在与硬件交互时也时常需要确保一个给定的读操作发生在其他读或者写操作之前，或者在多处理器中可能需要按写数据的顺序进行读取。但是编译器为提高效率可能会对读写进行重新排序。但可能重新排序读写的处理器提供了机器指令来确保顺序要求。同样可以使得编译器不对定点周围指令进行重新排序。这些确保顺序的指令称为屏障。

屏障 描述
rmb() 阻止跨越屏障的载入动作发生重排序
read_barrier-depends() 阻止跨越屏障的具有数据依赖关系的载入动作重排序
wmb() 阻止跨越屏障的存储动作发生重排序
mb() 阻止跨越屏障的载入和存储动作发生重排序
smp_rmb() 在SMP上提供rmb()功能，在UP上提供barrier()功能
smp_read_barrier-depends() 在SMP上提供read_barrier-depends()功能，在UP上提供barrier()功能
smp_wmb() 在SMP上提供wmb()功能，在UP上提供barrier()功能
smp_mb() 在SMP上提供mb()功能，在UP上提供barrier()功能
barrier() 组织编译器跨屏障对载入或存储操作进行优化

注意：对于不同体系结构，屏障的实际效果差别很大。如果一个处理器不会执行乱序存储的话，wmb()函数实际什么都不会做。

SMP与UP

在中断处理程序中能避免并发访问的安全代码称作中断安全代码（interrupt-safe），在多对称处理的机器中能避免并发访问的安全代码称为SMP安全代码（SMP-safe），在内核抢占时能避免并发访问的安全代码称为抢占安全代码（preempt-safe）。

因为Linux内核可在编译时配置，所以可以针对指定机器进行内核剪裁，更重要的是，CONFIG_CMP没被设置时，不必要的代码就不会被编入针对单处理器的内核镜像中。这样可以使单处理器机器避免使用自旋锁带来的开销。CONFIG_PREEMPT这一选项也同样适用。