0%

Linux并发与同步(一)自旋锁

原图

经典自旋锁

如果临界区中只有一个変量,那么原子变量可以解決问题,但是临界区有一个数据操作的集合,需要通过锁机制来保障,自旋锁( spinlock)是 Linux内核中最常见的锁机制。

  • 忙等待的锁机制。操作系统中锁的机制分为两类,一类是忙等待,另一类是睡眠等待
  • 同一时刻只能有一个内核代码路径可以获得该锁
  • 要求自旋锁持有者尽快完成临界区的执行任务,特别是自旋锁临界区里不能睡眠
  • 自旋锁可以在中断上下文中使用

自旋锁的实现

先看 spinlock数据结构的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
<include/linux/spinlock_types.h>
typedef struct spinlock {
union {
struct raw_spinlock rlock;

#ifdef CONFIG_DEBUG_LOCK_ALLOC
# define LOCK_PADSIZE (offsetof(struct raw_spinlock, dep_map))
struct {
u8 __padding[LOCK_PADSIZE];
struct lockdep_map dep_map;
};
#endif
};
} spinlock_t;
...
typedef struct raw_spinlock {
arch_spinlock_t raw_lock;
#ifdef CONFIG_DEBUG_SPINLOCK
unsigned int magic, owner_cpu;
void *owner;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
} raw_spinlock_t;
...
typedef struct {
union {
u32 slock;
struct __raw_tickets {
#ifdef __ARMEB__
u16 next;
u16 owner;
#else
u16 owner;
u16 next;
#endif
} tickets;
};
} arch_spinlock_t;

spinlock数据结构的定义既考虑到了不同处理器架构的支持和实时性内核的要求,还定义了raw_spinlock和arch_spinlock_t数据结构,其中arch_spinlock_t数据结构和架构有关。在 Linux2.6.25内核之前, spinlock数据结构就是一个简单的无符号类型变量。若 slock值为1,表示锁未被持有;若为0,表示锁被持有。这会存在两个严重问题,不公平和效率低下。因此在 Liux2.6.25内核后,自旋锁实现了“基于排队的FIFO”算法的自旋锁机制,称为基于排队的自旋锁。

基于排队的自旋锁仍然使用原来的数据结构,但slock域被拆分成两个部分,如下图:

owner表示自旋锁持有者的牌号,next表示外面排队的队列中末尾者的牌号。当有线程要获取锁时next++,当持有锁的线程释放锁时owner++。当owner和next相等时,该线程将获得自旋锁。

自旋锁的原型定义在 include/linux/spinlock.h头文件中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<include/linux/spin_lock. h>
static __always_inline void spin_lock(spinlock_t *lock)
{
raw_spin_lock(&lock->rlock);
}
#define raw_spin_lock(lock) _raw_spin_lock(lock)
void __lockfunc _raw_spin_lock(raw_spinlock_t *lock)
{
__raw_spin_lock(lock);
}
static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
preempt_disable();
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

spin_locke函数最终调用 __raw_spin_lock()函数来实現。首先关闭内核抢占,这是自旋锁实现的关键点之一。那么为什么自旋锁临界区中不允许发生抢占呢?如果自旋锁临界区中允许抢占,假设在临界区内发生中断,中断返回时会检查抢占调度,这里将有两个问题、一是抢占调度会导致持有锁的进程睡眠,这违背了自旋锁不能睡眠和快速执行完成的设计语义;二是抢占调度进程也可能会申请自旋锁,这样会导致发生死锁。

自旋锁的变体

在驱动中很多操作都需要访问和更新链表,如open、 ioctl等,因此操作链表的地方就是一个临界区,需要自旋锁来保护。若在临界区中发生了外部硬件中断,系统暂停当前进程的执行转而处理该中断。假设中断处理程序恰巧也要操作该链表,链表的操作是一个临界区,所以在操作之前要调用spin_lock()函数来对该链表进行保护。中断处理程序试图获取该自旋锁,但因为它己经被其他CPU持有了,于是中断处理程序进入忙等待状态或者wfe睡眠状态。在中断上下文中出现忙等待或者睡眠状态是致命的,中断处理程序要求“短”和“快”,自旋锁的持有者因为被中断打断而不能尽快释放锁,而中断处理程序一直在忙等待该锁,从而导致死锁的发生。 Linux内核的自旋锁的变体 spin_lock_irq()函数通过在获取自旋锁时关闭本地CPU中断,可以解决该问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static __always_inline void spin_lock_irq(spinlock_t *lock)
{
raw_spin_lock_irq(&lock->rlock);
}
...
#define raw_spin_lock_irq(lock) _raw_spin_lock_irq(lock)
...
void __lockfunc _raw_spin_lock_irq(raw_spinlock_t *lock)
{
__raw_spin_lock_irq(lock);
}
...
static inline void __raw_spin_lock_irq(raw_spinlock_t *lock)
{
local_irq_disable();
preempt_disable();
spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
}

spin_lock_irq()函数的实现比 spin_lock()函数多了一个local_irq_disable()函数。local_irq_disable()函数用于关闭本地处理器中断,这样在获取自旋锁时可以确保不会发生中断,从而避免发生死锁问题,即 local_irq_disable()函数主要防止本地中断处理程序和自旋锁持有者之间产生锁的争用。

可能有的读者会有疑问,既然关闭了本地CPU的中断,那么别的CPU依然可以响应外部中断,这会不会也可能导致死锁呢?自旋锁持有者在CPUO上,CPU1响应了外部中断且中断处理程序同样试图去获取该锁,因为CPU0上的自旋锁持有者也在继续执行,所以它很快会离开临界区并释放锁,这样CPU1上的中断处理程序可以很快获得该锁。

自旋锁还有另外一个常用的变体-- spin_lock_bh()函数,用于处理进程和延迟处理机制导致的并发访问的互斥问题。

spin_lock()和 raw_spin_lock()函数

这要从Linux内核的实时补丁( Rt-patch)说起。实时补丁旨在提升Linux内核的实时性它允许在自旋锁的临界区内抢占锁,且在临界区内允许进程睡眠。这样会导致自旋锁语义被修改。当时内核中大约有10000处使用了自旋锁,直接修改自旋锁的工作量巨大,但是可以修改那些真正不允许抢占和睡眠的地方,大概有100处,因此改为使用 raw_spin_lock()。

spin_lock()和 raw_spin_lock()函数的区别如下:

  • 在绝对不允许抢占和睡眠的临界区,应该使用raw_spin_lock()函数,否则使用 spin_lock()
  • 对于没有更新实时补丁的 Linux内核来说,spin_lock()函数可以直接调用raw_spin_lock(),对于更新实时补丁的 Linux内核来说, spin_lock()会变成可抢占和睡眠的锁,这需要特别注意

效率

根据硬件维护的cache一致性协议,如果spinlock的值没有更改,那么在busy wait时,试图获取spinlock的CPU,只需要不断地读取自己包含这个spinlock变量的cache line上的值就可以了,不需要从spinlock变量所在的内存位置读取。

但是,当spinlock的值被更改时,所有试图获取spinlock的CPU对应的cache line都会被invalidate,因为这些CPU会不停地读取这个spinlock的值,所以"invalidate"状态意味着此时,它们必须重新从内存读取新的spinlock的值到自己的cache line中。

而事实上,其中只会有一个CPU,也就是队列中最先达到的那个CPU,接下来可以获得spinlock,也只有它的cache line被invalidate才是有意义的,对于其他的CPU来说,这就是做无用功。内存比cache慢那么多,开销可不小。

MCS锁

假设在一个锁争用激烈的系统中,所有等待自旋锁的线程都在同一个共享变量上自旋,申请和释放锁都在同一个变量上修改,高速内存一致性原理(如MESI协议)导致参与自旋的CPU中的高速缓存行变得无效。在锁争用的激烈过程中,可能导致严重的CPU高速缓存行颠簸现象( CPU cacheline bouncing),即多个CPU上的高速缓存行反复失效,大大降低系统整体性能。

MCS算法可以解决自旋锁遇到的问题,显著缓解CPU高速缓存行颠簸问题。

MCS算法的核心思想是每个锁的申请者只在本地CPU的变量上自旋,而不是全局的变量上,大大降低锁的争用。

OSQ锁

早期MCS算法的实现需要比较大的数据结构,在 Linux4.2内核中引进了基于MCS算法的排队自旋锁(One Spinlock, Qspinlock)OSQ锁的实现需要两个数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<include/linux/osq_lock.h>

/*
* An MCS like lock especially tailored for optimistic spinning for sleeping
* lock implementations (mutex, rwsem, etc).
*/
struct optimistic_spin_node {
struct optimistic_spin_node *next, *prev;
int locked; /* 1 if lock acquired */
int cpu; /* encoded CPU # + 1 value */
};

struct optimistic_spin_queue {
/*
* Stores an encoded value of the CPU # of the tail node in the queue.
* If the queue is empty, then it's set to OSQ_UNLOCKED_VAL.
*/
atomic_t tail;
};

每个MCS锁有一个optimistic_spin_queue数据结构,该数据结构只有一个成员tail,初始化为0。 optimistic_spin_node数据结构表示本地CPU上的节点,它可以组织成一个双向链表包含next和prev指针, locked成员用于表示加锁状态,cpu成员用于重新编码CPU编号,表示该节点在哪个CPU上。 optimistic_spin_node数据结构会定义成per-CPU变量,即每个CPU有一个节点结构。

1
2
3
4
5
6
7
8
9
10
<kernel/locking/osq_lock.c>
/*
* An MCS like lock especially tailored for optimistic spinning for sleeping
* lock implementations (mutex, rwsem, etc).
*
* Using a single mcs node per CPU is safe because sleeping locks should not be
* called from interrupt context and we have preemption disabled while
* spinning.
*/
static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node);

MCS锁在 osq_lock_init()函数中初始化。如互斥锁会初始化为一个MCS锁,因为 __mutex_init()函数会调用 osq_lock_init()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<kernel/locking/mutex.c>
void
__mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)
{
atomic_long_set(&lock->owner, 0);
raw_spin_lock_init(&lock->wait_lock);
INIT_LIST_HEAD(&lock->wait_list);
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
osq_lock_init(&lock->osq);
#endif

debug_mutex_init(lock, name, key);
}
EXPORT_SYMBOL(__mutex_init);

OSQ自旋锁的特点:

  • 集成MCS算法到自旋锁中,继承了MCS算法的所有优点,有效解决了CPU高速缓存行颠簸问题
  • 没有增加 spinlock数据结构的大小,把val细分成多个域,完美实现了MCS算法
  • 当只有两个CPU试图获取自旋锁时,使用 pending域就可以完美解决问题,第2CPU只需要设置 pending域,然后自旋等待锁释放。当有第3个或者更多CPU来争用时,则需要使用额外的MCS节点。第3个CPU会自旋等待锁被释放,即 pending域和 locked域被清零,而第4个CPU和后面的CPU只能在MCS节点中自旋等待 locked域被置1,直到前继节点把 locked控制器过继给自己才能有机会自旋等待自旋锁的释放,从而完美解决激烈锁争用带来的高速缓存行颠簸问题16信号量
  • 解决MCS锁占内存大的问题

参考文献

《奔跑吧Linux内核》
https://zhuanlan.zhihu.com/p/80727111
https://zhuanlan.zhihu.com/p/89058726
https://zhuanlan.zhihu.com/p/100546935