PS：要转载请注明出处，本人版权所有。
PS: 这个只是基于《我自己》的理解，
如果和你的原则及想法相冲突，请谅解，勿喷。
环境说明
无
前言
最近为了实现在android linux kernel上，是的bionic c和glibc的sem_相关的信号量接口能够相互调用的功能（例如：用bionic c wait，用glibc awake），需要去深度阅读相关c库关于sem_ posix api的实现。
最终的最终，发现主要要解决futex的问题就行。因此将其相关的概念进行了总结。
进程同步与互斥的一些基本概念
进程：
- 是操作系统调度的基本单位。
进程状态：
- 三态模型：运行、就绪、等待（阻塞/睡眠）
- 五态模型：运行、就绪、等待（阻塞/睡眠） + 新建、终止
进程调度：
- 因某些原因（io等待，自己睡眠，调度公平等等），一个或者多个进程需要进行状态切换。
进程工作特性分类：
- 计算密集型：进程的主要工作是计算某些事情。
- IO密集型：进程的主要工作是加载IO并进行处理。
并发：
- 是指多个进程同时运行，并完成一定任务。
临界区：
- 是指多个进程同时运行时，同一时刻访问相同的代码和数据。
同步：
- 强调的是进程间的执行需要按照某种先后顺序，即进程运行的时间是有序的。
互斥：
- 强调的是对于某些共享资源的访问不能同时进行，同一时间只能有一定数量的进程访问这些共享资源。
进程常见的同步机制：
- 信号量：解决了同步问题。
- 互斥量：解决了互斥问题。是信号量的一种特例，只具备0，1两种值。
锁
锁：
- 既可以解决同步问题，也可以解决互斥问题。
死锁：
- 指多个进程同时获取锁，且由于某些原因，此锁永远不会被空闲。
两种基本锁：
- 互斥锁：加锁失败后，线程会释放 CPU ，给其他线程；
- 自旋锁：加锁失败后，线程会忙等待，直到它拿到锁；
读写锁：
- 读锁：当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。
- 写锁：一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞
- 特征：读写锁在读多写少的场景，能发挥出优势。读写锁可以分为「读优先锁」和「写优先锁」
乐观锁：
- 如果多线程同时修改共享资源的概率比较低
悲观锁：
- 认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。
CAS(Compare And Swap)
CAS是一种无锁同步算法，主要用于多线程环境下面，高效的对多个线程进行同步。
首先CAS有3个重要的参数：目标地址(P)、期望值(E)、新值(N)，然后其工作原理是：
- 读取目标地址（P）的值
- 对比目标地址（P）的值与期望值（E）
- 如果P==E，则写入新值（N），如果P!=E，则不做任何操作并返回。
可以乍一看，这里有3步操作，会让我们对这个算法难以理解，所以这里还有一个重要的概念：CAS的这几步操作是原子的，一次性完成的，此外，这些特性是硬件提供的。因此，在实际使用上面，这些原子操作被编译器封装成相关的接口来使用这些硬件特性。例如gcc里面：
// https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
// 注意，原来的__sync_*系列函数的__atomic系列替代了
bool __atomic_compare_exchange (type *ptr, type *expected, type *desired, bool weak, int success_memorder, int failure_memorder)
futex 系统调用
futex是linux下用来实现各种同步机制的一个系统调用，我们先来学习看看其api：
#include <linux/futex.h>
#include <sys/time.h>
int futex(int *uaddr, int futex_op, int val, const struct timespec *timeout, /* or: uint32_t val2 */
int *uaddr2, int val3);
注意这里的看到这个api有许多的参数，但是我们常用的也是前面4个，一般来说，我们会将futex分为常用的两类，是futex_op参数指定的，分别是：FUTEX_WAIT、FUTEX_WAKE（注意，还有其他很多op类型），其他的参数根据不同的类型，有不同的一些含义：
- 对于FUTEX_WAIT来说：如果uaddr的值等于期待值（val），则将线程挂起。timeout如果是NULL，则无限等待，或者等待timeout时间。
- 对于FUTEX_WAKE来说：指定唤醒uaddr关联的并被挂起的val个线程。timeout参数忽略。
上面我们简单说明了这个系统调用的一些用法，现在我们来看看这个系统调用的内核简单实现，然后我们就基本理解了这个系统调用的工作原理：
首先来看看FUTEX_WAIT的内核部分源码，如下：
//linux kernel v4.6 kernel/futex.c
static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
__releases(&hb->lock)
{
int prio;
// ... ... 省略
plist_node_init(&q->list, prio);
plist_add(&q->list, &hb->chain);
q->task = current;
spin_unlock(&hb->lock);
}
static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
struct hrtimer_sleeper *timeout)
{
// ... ... 省略
set_current_state(TASK_INTERRUPTIBLE);//挂起
queue_me(q, hb);
// ... ... 省略
}
static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
struct futex_q *q, struct futex_hash_bucket **hb)
{
u32 uval;
int ret;
// ... ... 省略
retry:
// ... ... 省略
ret = get_futex_value_locked(&uval, uaddr);
// ... ... 省略
ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key, VERIFY_READ);
if (unlikely(ret != 0))
return ret;
// ... ... 省略
if (uval != val) {//判断值是否是期望值，并做后续操作
queue_unlock(*hb);
ret = -EWOULDBLOCK;
}
// ... ... 省略
}
static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
ktime_t *abs_time, u32 bitset)
{
struct hrtimer_sleeper timeout, *to = NULL;
struct restart_block *restart;
struct futex_hash_bucket *hb;
struct futex_q q = futex_q_init;
int ret;
// ... ... 省略
retry:
/*
* Prepare to wait on uaddr. On success, holds hb lock and increments
* q.key refs.
*/
ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
if (ret)
goto out;
/* queue_me and wait for wakeup, timeout, or a signal. */
futex_wait_queue_me(hb, &q, to);
// ... ... 省略
out:
// ... ... 省略
}
其实我们这里可以看到，关键是通过get_futex_key来根据传入的uaddr获取一个key，然后根据key，来构造一个hash list(注意，这时这个hash list被一个hash数据结构维护了，可通过key查询)，并将当前线程插入到这个list，并将线程/进程挂起。在这个过程中，还会检查*uaddr 是否等于val，否则做相关操作。
现在，其实我们基本上也可以猜到FUTEX_WAKE的实现是什么样子，现在我们先来看看其源码节选：
//linux kernel v4.6 kernel/futex.c
static inline int match_futex(union futex_key *key1, union futex_key *key2)
{
return (key1 && key2
&& key1->both.word == key2->both.word
&& key1->both.ptr == key2->both.ptr
&& key1->both.offset == key2->both.offset);
}
static int
futex_wake_op(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2,
int nr_wake, int nr_wake2, int op)
{
union futex_key key1 = FUTEX_KEY_INIT, key2 = FUTEX_KEY_INIT;
struct futex_hash_bucket *hb1, *hb2;
struct futex_q *this, *next;
int ret, op_ret;
WAKE_Q(wake_q);
retry:
ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, VERIFY_READ);//根据uaddr获取key
if (unlikely(ret != 0))
goto out;
// ... ... 省略
hb1 = hash_futex(&key1);//根据key获取hash对象
// ... ... 省略
retry_private:
// ... ... 省略
plist_for_each_entry_safe(this, next, &hb1->chain, list) {
if (match_futex (&this->key, &key1)) {//匹配符合条件的key
if (this->pi_state || this->rt_waiter) {
ret = -EINVAL;
goto out_unlock;
}
mark_wake_futex(&wake_q, this);//将符合条件的对象放入到队列wake_q
if (++ret >= nr_wake)
break;
}
}
// ... ... 省略
out_unlock:
double_unlock_hb(hb1, hb2);
wake_up_q(&wake_q); //唤醒线程/进程，wake_up_q在kernel/sched/core.c中定义
out_put_keys:
put_futex_key(&key2);
out_put_key1:
put_futex_key(&key1);
out:
return ret;
}
从这里我们可以看到，首先我们根据uaddr获取了key，然后通过hash_futex获取key对象，这个时候我们就获取了和uaddr相关的线程/进程list。然后我们遍历list，将符合条件的线程/进程放到wake_q队列中去，最后通过wake_up_q来设置TASK_WAKING，并唤醒线程/进程。
后记
从这里我们可以看到，这些概念是为了解决前置问题逐步引入的：
- 进程具备一定的状态（运行、就绪、等待（阻塞/睡眠） + 新建、终止）。
- 进程是OS调度的基本单位，调度就是调整进程的状态。
- 为了高效完成一个任务，我们需要并发，这时我们需要同步，需要信号量。
- 因为有了并发，我们需要注意临界区。
- 有了临界区，我们需要互斥量（锁）。
- 最后，CAS和futex可以实现各种信号量和锁。
完结散花。
参考文献
PS: 请尊重原创，不喜勿喷。
PS: 要转载请注明出处，本人版权所有。
PS: 有问题请留言，看到后我会第一时间回复。