JasonWang's Blog

Linux内核中的锁

字数统计: 3.2k阅读时长: 11 min
2020/10/23

在看Linux内核代码时,经常会遇到各种锁(lock)的使用。对于像spin_lock_irq/spin_lock_irqsave的区别感到困惑,每次都要重新查一下资料。遂决定写一篇文章记录下内核中使用到的锁,以及使用的场景。

与应用中的锁类似,内核中的锁也只是为了保护某个内核数据结构或者内存区域在多个并发执行路径时不被破坏,确保数据的一致性。Linux内核作为应用层服务的提供者,一方面要为应用提供系统调用接口(system call),代表用户进程执行任务,即process context, 在进程上下文中可以休眠,执行调度;同时与硬件直接交互,要响应硬件中断的请求,处理诸如网卡数据/串口数据等请求,即Interrupt Context,在中断上下文内核不能休眠,无法重新调度. 内核就是在进程上下文/中断上下文直接来回切换,执行相应的任务请求。这就自然产生了数据的并发访问,产生了竞争条件(race condition)。另一方面,目前大多数的系统都是多核CPU、支持多进程,多个CPU、多个进程同时访问内核数据也同样会产生竞争条件。

简单来说,内核中锁要做的事情就是确保临界区<critical section>始终只有一个执行路径,就是说在有锁保护的情况下,临界区的执行不会被其他执行路径中断; 接下来,就分别看一看内核中常用的几个锁保护机制<对应的代码实现在/kernel/locking/>:

  • semaphore(信号量)
  • Spin Lock(自旋锁)
  • Mutex(互斥锁)
  • Atomic(原子操作)
  • Readers-Writer Lock(读写锁,包括rw_semaphore/rwlock)
  • Seqlock(序列锁)
  • Read-Copy-Update(RCU)(读/拷贝-更新)

Semaphore(信号量)

semaphore是很常见的同步资源访问的方法,可以用于多个资源的访问控制;一般用于多个内核路径试图控制某个数据的并发访问,内核中对应的头文件在linux/semaphore.h:

1
2
3
4
5
6
7
8

struct semaphore {
raw_spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};


上述中count就是需要同步访问的资源个数,一般在内核中都设置为1,即等同于互斥锁。semaphore有两个常用的操作方法:

  • down: 获取锁,读应可用的资源减少,通常获取锁会将阻塞所执行的路径,让任务进入等待状态; 内核实现了好几种方法供调用:
    • down: 如果锁已被持有,则执行任务会被阻塞,在内核中不推荐使用该方法
    • down_interruptible: 允许获取锁时被中断,在接收到中断信号后,返回中断错误-EINTR
    • down_killable: 执行任务阻塞时如果发生错误,则被中断返回-EINTR
    • down_trylock: 尝试获取锁,如果已被占用,则直接返回,该方法支持在中断上下文中使用
    • down_timeout: 设置一个超时时间,超过该等待时间未获取到锁则返回-ETIME
  • up: 释放锁,可以在任何执行路径执行该方法,即使未执行过down也可以进行锁的释放

相比下文中讲到的自旋锁、顺序锁等,信号量在锁持有期间是可以执行调度的,就是说无法获取到琐时,进程会加入到等待队列进入休眠状态,此时调度器调度其他进程。因此,不能在中断上下文中使用,如果必须要用,也只能调用down_trylock确保中断处理不阻塞。

spin lock(自旋锁)

spin lock是内核中最常用的同步方法,通常用于多个CPU执行路径尝试访问同一个内存数据时的同步并且执行任务不能休眠的场景。与其他如semaphore不同的是,spin lock不会让锁等待者进入休眠状态,而是执行一个简单的循环等待,如果此时锁被释放,则会尝试获取锁,这样就避免了上下文切换,从而提升效率。一般如果锁等待的时间如果超过系统上下文切换的时间,使用spin lock则会减少任务的等待时间,改善系统性能。

除此之外,在某些特殊的场景比如在中断上下文与内核执行路径上共享数据时,就不能使用如semaphore这类会时执行任务休眠的同步锁,因为内核一旦在处理中断时,发生进程调度,则可能发生中断无法被处理的情况。同样地,在处理中断时,也不能使用spin lock以防止类似的情况;因此,在中断处理上下文中,使用spin lock时要将本地中断禁止。另外,在可能发生内核抢占(kernel preemption)的时候,如果被抢占任务执有spin lock,就可能导致该锁一直未被释放。总结来说,使用spin lock要注意如下几个原则:

  • 内核抢占应该被禁止,以防出现竞争条件
  • 本地中断需要被禁止,防止中断无法处理的情况
  • 持有锁的时间越短越好,避免引起性能问题
  • 不用调用任何可能导致休眠的函数,如kmalloc,copy_from_user
  • 自旋锁不可递归,获得锁之后不能再尝试获得自旋锁,否则可能导致锁死

跟上述几个场景对应,Linux中的spin lock提供了好几个函数来实现不同场景下的同步<linux/spinlock.h>:

  • spin_lock_init: 初始化自旋锁
  • spin_lock: 获取锁,如果锁被持有了,则等待
  • spin_lock_bh: 获取锁,禁止了下半部软中断,但可以响应物理中断
  • spin_lock_irq: 获取锁时打开中断
  • spin_lock_irqsave: 获取锁时禁止本地中断

上述几个函数的实现都在kernel/locking/spinlock.c中,如果不希望获取锁失败时等待,则可以通过spin_trylock*来实现。

如果只是想屏蔽、使能本地中断,可以使用local_irq_save/local_irq_restore

Mutex(互斥锁)

互斥锁(Mutex)是提供了一种资源互斥访问的机制,确保多个使用者顺序访问共享的数据。作为可睡眠(阻塞)的锁,其与二元的信号量(semaphore)类似,其在2006年时引入内核,想比较而言,互斥锁提供了更为简单清晰的接口,并且代码更为紧凑。具体的使用可以参考源码linux/mutex.h/kernel/mutex.c以及内核文档Documentation/locking/mutex-design.txt:

1
2
3
4
5
6
7

struct mutex {
atomic_long_t owner;
spinlock_t wait_lock;
struct list_head wait_list;
};

互斥锁的语义确保了:

  • 任何时候只有一个任务(进程)持有锁
  • 只有锁的持有者可以释放锁(unlock)
  • 不允许多次unlock一把锁以及递归的(recursively)获取/释放锁
  • 持有锁时任务(进程)不可退出/被锁保护的内存不可能被释放
  • 互斥锁不可用于硬件/软件中断的情况,如tasklets/timers

互斥锁提供了多种接口,很方便使用:

  • DEFINE_MUTEX(name)/mutex_init(mutex):静态/动态初始化锁
  • mutex_lock/mutex_trylock/mutex_lock_nested: 不可中断地获取锁
  • mutex_lock_interruptible_nested/mutex_lock_interruptible: 可中断获取锁
  • mutex_unlock: 释放锁
  • mutex_is_locked: 锁是否被持有

互斥锁跟自旋锁类似,不支持递归获取,而且不能用于中断上下文中。

Atomic(原子操作)

原子操作具有不可中断性,即其指令在完成之前不会被任何任务所中断,这样可以确保在多任务/多CPU状态下满足内存数据操作的一致性与顺序性。有关多任务下内存操作的一致性问题可以参考Memory Barrier以及Java中的原子操作, 内核中也有相关的文档「Documentation/memory-barriers.txt」。

内核中支持atomic_t/atomic64_t/atomic_long_t三个数据类型的原子操作, 并提供了一系列的通用接口:

  • atomic_read/atomic_set: 读取/设置某个原子数
  • atomic_{add,sub,inc,dec}:算术操作
  • atomic_xchg/atomic_cmpxchg: 数值交换

有关原子操作接口使用的细节可以参考include/linux/atomic.h以及Linux内核文档Documentation/core-api/atomic_ops.rst/Documentation/atomic_t.txt

Readers-Writer Lock(读写锁)

在并发的方式中,有RR(Read-Read)RW(Read-Write)以及WW(Write-Write)三种形式。一般情况下,RR是完全可以并发执行的。读写锁(RWL)是为了解决多个读/写任务时出现的数据不一致问题: 任何时候只允许一个Writer持有锁,但允许多个Reader持有锁,同时可以实现写锁(Writer持有的锁)降级为读锁(Reader持有的锁)。Linux内核中有两种类型的读写锁, rwlock_t/rw_semaphore:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// include/linux/rwlock_types.h
typedef struct {
arch_rwlock_t raw_lock;
#ifdef CONFIG_GENERIC_LOCKBREAK
unsigned int break_lock;
#endif
} rwlock_t;

// include/linux/rwsem.h
struct rw_semaphore {
atomic_long_t count;
struct list_head wait_list;
raw_spinlock_t wait_lock;
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
struct optimistic_spin_queue osq; /* spinner MCS lock */
/*
* Write owner. Used as a speculative check to see
* if the owner is running on the cpu.
*/
struct task_struct *owner;
#endif
};

rwlock_t的实现可以参考locking/spinlock.c;rw_semaphore可以参考locking/rwsem.c。这里以rw_semaphore为例说明读写锁的接口:

  • DECLARE_RWSEM(name)/init_rwsem(sem): 初始化锁的两种方式
  • down_read/down_read_trylock: 获取读锁
  • down_write/down_write_trylock: 获取写锁
  • up_read: 释放读锁
  • up_write: 释放写锁
  • downgrade_write: 降级写锁为读锁

Linux内核中读写锁都是公平的,这样确保Writer不会被饿死,具体可以参考内核文档Documentation/spinlocks.rst以及锁类型

Seqlock(顺序锁)

顺序锁类似于读写锁, 主要用于解决读写锁中writer容易被饿死的问题(writer必须等待reader释放锁后才可以持有到锁)。对于顺序锁而言,writer的优先级更高,从而可以确保被保护的变量可以快速得到更新。每次writer获取锁时,会对seqcount加一,释放时同样加一,而reader获取锁时,如果seqcount时奇数(writer正持有锁,尝试修改数据),则不断重试,否则获取到锁,进入临界区读取数据。

1
2
3
4
5
6
7
8

// include/linux/seqlock.h
typedef struct {
struct seqcount seqcount;
spinlock_t lock;
} seqlock_t;


由于reader需要等待writer完成变量更新,因此在写操作频繁的情况下,reader的性能可能下降。所以,相比读写锁,顺序锁(seqlock)更合适于读频繁,写操作很少但需要高效快速的情形。有关顺序锁的更详细介绍可以参考Linux内核同步机制之(六):Seqlock 以及LWN上的一篇简单的使用说明

Read-Copy-Update(RCU)

不管是读写锁还是序列锁,都是尝试解决reader/writer之间并行的数据一致性问题,但由于它们都是基于锁的同步,因此会消耗不必要的CPU周期。Read-Copy-Update(RCU)通过一种无需依赖锁的同步方法实现了多个reader/writer时的数据一致性问题, 其可以实现链表/树/哈希表等多种链表数据结构的同步(序列锁无法实现链表结构的数据同步)。RCU实现的基本原理如下:

  • Writer来说:

    • 创建一个新的链表结构
    • Copy(拷贝)旧的数据结构到新的链表结构中,并通过一个指针指向旧的链表结构
    • 修改新结构中的数据
    • 更新链表中的指针,使其指向新的结构体
    • 等待一段时间,确保所有reader没有再使用旧的数据结构(synchronize_rcu)
    • 唤醒后,删除旧的链表结构,完成更新
  • reader来说:

    • 通过rcu_read_lock进入临界区,访问链表结构
    • 多个reader可以同时访问结构体
    • 通过rcu_read_unlock结束临界区的访问

总的来说RCU的优势在于多个reader可以同时访问数据(即使此时writer正在更新数据),而且无需持有任何锁,从而减少了CPU的消耗,提升了系统性能的伸缩性(scalibility, 性能不会随着CPU数量的增多而降低,见what is RCU)。正是这种特性,使的RCU特别适合于多个reader,单个或者多个writer写操作并不频繁的场景(存在多个writer时需要使用锁保护)。

有关RCU的更多使用与原理的细节可以参考如下几篇文章:

另外也可以参考Linux源码(include/linux/rcupdate.h)和内核文档RCU.txt

参考文献

原文作者:Jason Wang

更新日期:2023-03-30, 07:57:30

版权声明:本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. Semaphore(信号量)
  2. 2. spin lock(自旋锁)
  3. 3. Mutex(互斥锁)
  4. 4. Atomic(原子操作)
  5. 5. Readers-Writer Lock(读写锁)
  6. 6. Seqlock(顺序锁)
  7. 7. Read-Copy-Update(RCU)
  8. 8. 参考文献