Linux信号量机制分析

背景

Read the fucking source code!
A picture is worth a thousand words.

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

semaphore

本文将分析信号量与读写信号量的机制，开始吧。

2. 信号量

2.1 流程分析

• 可以将信号量比喻成一个盒子，初始化时在盒子里放入N把钥匙，钥匙先到先得，当N把钥匙都被拿走完后，再来拿钥匙的人就需要等待了，只有等到有人将钥匙归还了，等待的人才能拿到钥匙；

信号量的实现很简单，先看一下数据结构：

struct semaphore {
	raw_spinlock_t		lock;       //自旋锁，用于count值的互斥访问
	unsigned int		count;      //计数值，能同时允许访问的数量，也就是上文中的N把锁
	struct list_head	wait_list;      //不能立即获取到信号量的访问者，都会加入到等待列表中
};

struct semaphore_waiter {
	struct list_head list;      //用于添加到信号量的等待列表中
	struct task_struct *task;   //用于指向等待的进程，在实际实现中，指向current
	bool up;                    //用于标识是否已经释放
};

流程如下：

• down 接口用于获取信号量， up 用于释放信号量；
• 调用 down 时，如果 sem->count > 0 时，也就是盒子里边还有多余的锁，直接自减并返回了，当 sem->count == 0 时，表明盒子里边的锁被用完了，当前任务会加入信号量的等待列表中，设置进程的状态，并调用 schedule_timeout 来睡眠指定时间，实际上这个时间设置的无限等待，也就是只能等着被唤醒，当前任务才能继续运行；
• 调用 up 时，如果等待列表为空，表明没有多余的任务在等待信号量，直接将 sem->count 自加即可。如果等待列表非空，表明有任务正在等待信号量，那就需要对等待列表中的第一个任务（等待时间最长）进行唤醒操作，并从等待列表中将需要被唤醒的任务进行删除操作；

2.2 信号量缺点

• 对比下 《Linux Mutex机制分析》 说过的 Mutex ， Semaphore 与 Mutex 在实现上有一个重大的区别： ownership 。 Mutex 被持有后有一个明确的 owner ，而 Semaphore 并没有 owner ，当一个进程阻塞在某个信号量上时，它没法知道自己阻塞在哪个进程（线程）之上；
• 没有 ownership 会带来以下几个问题：
  1. 在保护临界区的时候，无法进行优先级反转的处理；
  2. 系统无法对其进行跟踪断言处理，比如死锁检测等；
  3. 信号量的调试变得更加麻烦；

因此，在 Mutex 能满足要求的情况下，优先使用 Mutex 。

2.3 其他接口

信号量提供了多种不同的信号量获取的接口，介绍如下：

/* 未获取信号量时，进程轻度睡眠： TASK_INTERRUPTIBLE */
int down_interruptible(struct semaphore *sem)
/* 未获取到信号量时，进程中度睡眠： TASK_KILLABLE */
int down_killable(struct semaphore *sem)
/* 非等待的方式去获取信号量 */
int down_trylock(struct semaphore *sem)
/* 获取信号量，并指定等待时间 */
int down_timeout(struct semaphore *sem, long timeout)

3. 读写信号量

【原创】linux spinlock/rwlock/seqlock原理剖析（基于ARM64） 文章中，我们分析过读写自旋锁，读写信号量的功能类似，它能有效提高并发性，我们先明确下它的特点：

• 允许多个读者同时进入临界区；
• 读者与写者不能同时进入临界区（读者与写者互斥）；
• 写者与写者不能同时进入临界区（写者与写者互斥）；

3.1 数据结构

读写信号量的数据结构与信号量的结构比较相似：

struct rw_semaphore {
	atomic_long_t count;        //用于表示读写信号量的计数
	struct list_head wait_list;     //等待列表，用于管理在该信号量上睡眠的任务
	raw_spinlock_t wait_lock;   //锁，用于保护count值的操作
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* spinner MCS lock */    //MCS锁，参考上一篇文章Mutex中的介绍
	/*
	 * Write owner. Used as a speculative check to see
	 * if the owner is running on the cpu.
	 */
	struct task_struct *owner;      //当写者成功获取锁时，owner会指向锁的持有者
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map	dep_map;
#endif
};

• 最关键的需要看一下 count 字段，掌握了这个字段的处理，才能比较好理解读写信号量的机制；
• 【原创】linux spinlock/rwlock/seqlock原理剖析（基于ARM64） 文章中提到过读写自旋锁，读写自旋锁中的 lock 字段，bit[31]用于写锁的标记，bit[30:0]用于读锁的统计，而读写信号量的 count 字段也大体类似；

• 以32位的count值为例，高16bit代表的是 waiting part ，低16bit代表的是 active part ；
• RWSEM_UNLOCKED_VALUE ：值为0，表示锁未被持有，没有读者也没有写者；
• RWSEM_ACTIVE_BIAS ：值为1，，该值用于定义 RWSEM_ACTIVE_READ_BIAS 和 RWSEM_ACTIVE_WRITE_BIAS ；
• RWSEM_WAITING_BIAS ：值为-65536，当有任务需要加入到等待列表中时，count值需要加 RWSEM_WAITING_BIAS ，有任务需要从等待列表中移除时，count值需要减去 RWSEM_WAITING_BIAS ；
• RWSEM_ACTIVE_READ_BIAS ：值为1，当有读者去获取锁的时候，count值将加 RWSEM_ACTIVE_READ_BIAS ，释放锁的时候，count值将减去 RWSEM_ACTIVE_READ_BIAS ；
• RWSEM_ACTIVE_WRITE_BIAS ，值为-65535，当有写者去获取锁的时候，count值将加 RWSEM_ACTIVE_WRITE_BIAS ，释放锁的时候，count值需要减去 RWSEM_ACTIVE_WRITE_BIAS ；

在获取释放读锁和写锁的全过程中， count 值伴随着上述这几个宏定义的加减操作，用于标识不同的状态，可以罗列如下：

• 0x0000000X ：活跃的读者和正在申请读锁的读者总共为 X 个，没有写者来干扰；
• 0x00000000 ：没有读者和写者来操作，初始化状态；
• 0xFFFF000X ：分为以下几种情况：
  1. 0xFFFF000X = RWSEM_WAITING_BIAS + X * RWSEM_ACTIVE_READ_BIAS ，表示活跃的读者和正在申请读锁的读者总共有 X 个，并且还有一个写者在睡眠等待；
  2. 0xFFFF000X = RWSEM_ACTIVE_WRITE_BIAS + (X - 1)* RWSEM_ACTIVE_READ_BIAS ，表示有一个写者在尝试获取锁，活跃的读者和正在申请读锁的读者总共有 X-1 个；
• 0xFFFF0001 ：分为以下几种情况：

  0xFFFF0001 = RWSEM_ACTIVE_WRITE_BIAS
  0xFFFF0001 = RWSEM_ACTIVE_READ_BIAS + RWSEM_WAITING_BIAS
  

3.1 读信号量

3.1.1 读者获取锁

• 特点：读者与读者可以并发执行，读者与写者互斥执行，因此当有写者持有锁的时候，读者将进入睡眠状态；
• 当 sem->count 加1后还是小于0，代表锁已经被写者持有了，读者获取锁失败，进入 rwsem_down_read_failed 函数；
• 如果 sem->wait_list 是空时，代表没有任务在等待列表中，首次加入时， sem->count 值需要加上 RWSEM_WAITING_BIAS ，表示有任务在等待列表中；
• 如果此时 sem->count == RWSEM_WAITING_BIAS 或者 count > RWSEM_WAITING_BIAS && adjustment != RWSEM_ACTIVE_READ_BIAS ，表示此时写者将锁释放了，因此需要去唤醒在等待列表中的任务；
• 如果写者没有释放锁，那就进入循环，并调用 schedule 让出CPU，直到锁被释放了，那么从代码流程中看，只有 !waiter.task 时才会跳出循环，也就是 waiter.task == NULL 时，才是获取成功，这个操作是在 __rwsem_mark_wake 中通过 smp_store_release(&waiter->task, NULL) 实现的；
• 在等待获取锁的循环中，需要对信号进行处理，如果对应的等待任务没被唤醒，那么直接跳转到 out_nolock 处，接下来的处理就是一些逆操作了，包括从等待列表中删除，如果是等待列表中的首个任务，还需要减去 RWSEM_WAITING_BIAS 等；

总结一下：

读者获取锁的时候，如果没有写者持有，那就可以支持多个读者直接获取；而如果此时写者持有了锁，读者获取失败，它将把自己添加到等待列表中，（这个等待列表中可能已经存放了其他来获取锁的读者或者写者），在将读者真正睡眠等待前，还会再一次判断此时是否有写者释放了该锁，释放了的话，那就需要对睡眠等待在该锁的任务进行唤醒操作了

3.1.2 读者释放锁

• 释放锁的时候 sem->count 值进行减1操作；
• 减1操作之后得到的 count 值小于-1，并且 active part 是全零，代表等待列表中有写任务在睡眠等待，因此需要进行唤醒操作；
• 唤醒操作中，如果有自旋等待的任务，那就可以直接返回了，毕竟人家在自旋呢，又没有睡眠；
• 没有自旋等待任务，那就去唤醒等待列表中的任务了；

3.2 写信号量

3.2.1 写者获取锁

• 写者的特点：看谁都不顺眼，跟谁都互斥，有我没你。只要有一个写者在持有锁，其他的读者与写者都无法获取；
• 在写者获取锁的时候，将 sem->count 值加上 RWSEM_ACTIVE_WRITE_BIAS ，如果这个值不等于 RWSEM_ACTIVE_WRITE_BIAS ，表示有其他的读者或写者持有锁，因此获取锁失败，调用 rwsem_down_write_failed 来处理；
• 调用 rwsem_optimistic_spin 进行乐观自旋去尝试获取锁，获取了的话，则直接返回， optimistic spin 可以参考 《Linux Mutex机制分析》 文章中的分析，它的作用也是性能的优化，认为锁的持有者会很快释放，因此当前进程选择自旋而不是让出CPU，减少上下文切换带来的开销；
• 如果等待列表中有读者任务在睡眠等待，此时假如写者释放了锁，那么需要先将读者任务都给唤醒了；如果等待列表中没有任务，也就意味着当前的写者是第一个任务，因此将 sem->count 值加上 RWSEM_WAITING_BIAS ；
• 循环等待获取锁，这个过程与 down_read 是类似的；

总结

写者获取锁时，只要锁被其他读者或者写者持有了，则获取锁失败，然后进行失败情况处理。在失败情况下，它本身会尝试进行optimistic spin去尝试获取锁，如果获取成功了，那就是皆大欢喜了，否则还是需要进入慢速路径。慢速路径中去判断等待列表中是否有任务在睡眠等待，并且会再次尝试去查看是否已经有写者释放了锁，写者释放了锁，并且只有读者在睡眠等待，那么此时应该优先让这些先等待的任务唤醒

3.2.2 写者释放锁

sem->owner
RWSEM_ACTIVE_WRITE_BIAS

3.3 总结

理解读写信号量有几个关键点：

MCS锁
count

参考

Real-world Concurrency