锁实现分析：从glibc到futex

发表于 更新于 阅读次数： 本文字数： 14k 阅读时长 ≈ 13 分钟

之前在理解条件变量时在futex上误入歧途，导致犯下死锁的错误，并且写下了错误的博文，见浅析条件变量

所以打算重新理解一下futex

虽然初衷是futex，但是由于futex最初是为了优化锁的性能而提出，因此深入理解futex实际上是对锁概念的深入了理解

因此本篇的大纲

源码分析从c++的mutex开始，然后是glibc的nptl库pthread_mutex，接着是linux内核的futex实现

在源码分析完成以后，尝试对锁这个概念进行深入的分析，说明futex的诞生原因

C++的std::mutex源码分析

先看下g++版本

1
2
$ g++ --version
g++ (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0

然后在/usr/include/c++/9/bits/std_mutex.h有如下代码，做了一些可读性调整

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
class __mutex_base {
protected:
    typedef __gthread_mutex_t			__native_type;
    __native_type  _M_mutex = __GTHREAD_MUTEX_INIT;

    constexpr __mutex_base() noexcept = default;
    ...
};
class mutex : private __mutex_base {
  public:
    typedef __native_type* 			native_handle_type;
    ...
    void lock() {
      int __e = __gthread_mutex_lock(&_M_mutex);

      // EINVAL, EAGAIN, EBUSY, EINVAL, EDEADLK(may)
      if (__e)
		__throw_system_error(__e);
    }
    void unlock() {
      // XXX EINVAL, EAGAIN, EPERM
      __gthread_mutex_unlock(&_M_mutex);
    }
    ...
};
typedef pthread_mutex_t __gthread_mutex_t;
#define __GTHREAD_MUTEX_INIT PTHREAD_MUTEX_INITIALIZER
# define PTHREAD_MUTEX_INITIALIZER \
  { { 0, 0, 0, 0, 0, __PTHREAD_SPINS, { 0, 0 } } }
# define __PTHREAD_SPINS             0, 0

//__gthread_mutex_lock 差不多是pthread_mutex_lock，__gthread_mutex_unlock同理

可以看到c++的std::mutex几乎没有任何逻辑，就只是简单的对pthread的封装

持有了一个pthread_mutex_t类型的_M_mutex，并对其pthread_mutex_lock和pthread_mutex_unlock

glibc的mutex源码分析

pthread的实现实际上是glibc的NPTL代码

NPTL是Native POSIX Thread Library的缩写。这是Linux的一个线程库，它提供了一种实现POSIX线程（或称为Pthreads）的方法。NPTL被设计为可以提供高性能并发，特别是在多处理器和多核心系统中，并提供与POSIX标准更一致的行为。

NPTL是作为早期Linux线程实现LinuxThreads的替代品在2002年由IBM开发的，现在已经become了Linux系统上的默认POSIX线程库。在NPTL中，每个线程都是一个系统调度的实体，有独立的进程ID，这允许更有效率更一致的线程同步和并发。

像pthread_create这样的Pthreads API函数，实际上就是在使用NPTL（除非在非常老的Linux系统上可能是使用LinuxThreads）

这部分代码可以在https://github.com/bminor/glibc/tree/glibc-2.25/nptl中查看

首先查看x86上的pthread_mutex_t结构，代码在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/x86/bits/pthreadtypes.h#L128

主要看x86_64的代码

1
2
3
4
5
6
7
8
9
typedef union
{
  struct __pthread_mutex_s
  {
      ...
  } __data;
  char __size[__SIZEOF_PTHREAD_MUTEX_T];
  long int __align;
} pthread_mutex_t;

pthread_mutex_t是对__pthread_mutex_s的union跨平台封装

其中__size[__SIZEOF_PTHREAD_MUTEX_T]，这是用于标识__pthread_mutex_s的大小的

1
2
3
4
5
6
7
8
#ifdef __x86_64__
# if __WORDSIZE == 64
#  define __SIZEOF_PTHREAD_MUTEX_T 40
# else
#  define __SIZEOF_PTHREAD_MUTEX_T 32
#else
# define __SIZEOF_PTHREAD_MUTEX_T 24
#endif

而long int __align则是为了确保整个 pthread_mutex_t 结构体在内存中根据 long int 的对齐规则进行对齐，以提高cpu的运行效率

所以核心部分就在__pthread_mutex_s上了

1
2
3
4
5
6
7
8
9
10
11
struct __pthread_mutex_s
{
    int __lock; //表示互斥锁的状态，0表示未上锁，1表示已上锁，2表示发生了竞争。
    unsigned int __count; //表示重复获取此锁的次数，可用于实现可递归的互斥锁。
    int __owner; //表示当前持有该锁的线程的ID。
    unsigned int __nusers; //表示正在使用或等待此互斥锁的线程数。
    int __kind; //表示互斥锁的类型。
    short __spins; //一般在使用该锁的线程多于一个时，新请求锁的线程会自旋等待这个字段的次数，然后进入内核态等待，减少了线程上下文切换。
    short __elision; //对应硬件事务内存(htm)中的展开次数，如果为非零，新事务会直接展开，而不是使用锁。
    __pthread_list_t __list; //用于维护处于等待状态的线程列表。如果有多个线程在等待这个锁，它们将被添加到这个链表当中。
} __data;

  • __lock字段是这部分的重点内容了

    不是简单的0，1表示是否上锁，还有个2状态表示发生了竞争，需要陷入内核进行裁决

  • __kind字段的1-7位表示锁类型，例如默认的非递归锁PTHREAD_MUTEX_NORMAL（等价于PTHREAD_MUTEX_TIMED_NP，见这里），以及可重入锁PTHREAD_MUTEX_RECURSIVE。

    而8位表示互斥锁是被进程内的线程共享，还是跨进程共享。一般使用pthread_mutexattr_setpshared函数来设置该属性。如果是进程间的同步，需要开辟一个共享内存，将mutex放入共享内存中，然后不同进程才能操作同一个mutex。

    另外还有一些状态位是用于标识是否支持优先级继承等

pthread_mutex_lock

在https://github.com/bminor/glibc/blob/glibc-2.25/nptl/pthread_mutex_lock.c#L600可以看到

pthread_mutex_lock是一个指向__pthread_mutex_lock的强符号（这是一个gcc的概念，强符号声明可以覆盖弱符号，当不存在强符号时才会使用弱符号，详见Weak symbol）

1
2
3
4
#ifndef __pthread_mutex_lock
strong_alias (__pthread_mutex_lock, pthread_mutex_lock)
hidden_def (__pthread_mutex_lock)
#endif

在默认的锁类型PTHREAD_MUTEX_NORMAL（PTHREAD_MUTEX_TIMED_NP）下，https://github.com/bminor/glibc/blob/glibc-2.25/nptl/pthread_mutex_lock.c#L63所运行的流程如下

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
#define PTHREAD_MUTEX_TYPE_ELISION(m) \ //取mutex第8位获取锁类型
  (atomic_load_relaxed (&((m)->__data.__kind))	\
   & (127 | PTHREAD_MUTEX_ELISION_NP))

#ifndef LLL_MUTEX_LOCK
# define LLL_MUTEX_LOCK(mutex) \
  lll_lock ((mutex)->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex))
#endif

int __pthread_mutex_lock (pthread_mutex_t *mutex) {
	assert (sizeof (mutex->__size) >= sizeof (mutex->__data)); //检查size数组有没有bug
  	unsigned int type = PTHREAD_MUTEX_TYPE_ELISION (mutex); //获取锁类型
  	LIBC_PROBE (mutex_entry, 1, mutex); //用于给SystemTap工具跟踪和分析锁相关的性能，标记开始加锁的探测点
	if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_NP)) {				
      FORCE_ELISION (mutex, goto elision); //尝试硬件事务性内存来完成锁消除
      /* Normal mutex.  */
      LLL_MUTEX_LOCK (mutex); //核心逻辑
      assert (mutex->__data.__owner == 0); //检查bug，是不是还没有owner持有
    }
    pid_t id = THREAD_GETMEM (THREAD_SELF, tid); //获取当前的线程id
	/* Record the ownership.  */
	mutex->__data.__owner = id; //将id写入owner变量
	LIBC_PROBE (mutex_acquired, 1, mutex); //标记开始加锁成功，所有权转移之后的探测点
	return 0;
}

可以看到除了事务性内存看不太明白，这里大部分都是一些边缘逻辑，写入owner变量，设置探测点等等，核心逻辑全在LLL_MUTEX_LOCK指向的lll_lock中了

而关于其中的事务性内存，首先需要打开gcc选项-fgnu-tm才能使用，其次相关的FORCE_ELISION宏的逻辑，最终执行的代码LLL_MUTEX_LOCK_ELISION实际上已经废弃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifdef HAVE_ELISION
  else if (__glibc_likely (type == PTHREAD_MUTEX_TIMED_ELISION_NP))
    {
  elision: __attribute__((unused))
      /* This case can never happen on a system without elision,
         as the mutex type initialization functions will not
	 allow to set the elision flags.  */
      /* Don't record owner or users for elision case.  This is a
         tail call.  */
      return LLL_MUTEX_LOCK_ELISION (mutex);
    }
#endif

/* Not actually elided so far. Needed? */
#define LLL_MUTEX_LOCK_ELISION(mutex)  \
  ({ lll_cond_lock ((mutex)->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex)); 0; })

lll_lock

在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/nptl/lowlevellock.h#L88中定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and
   return.  Otherwise, ensure that it is >1 (acquired, possibly with waiters)
   and then block until we acquire the lock, at which point FUTEX will still be
   >1.  The lock is always acquired on return.  */
#define __lll_lock(futex, private)                                      \
  ((void)                                                               \
   ({                                                                   \
     int *__futex = (futex);                                            \
     if (__glibc_unlikely                                               \
         (atomic_compare_and_exchange_bool_acq (__futex, 1, 0)))        \
       {                                                                \
         if (__builtin_constant_p (private) && (private) == LLL_PRIVATE) \
           __lll_lock_wait_private (__futex);                           \
         else                                                           \
           __lll_lock_wait (__futex, private);                          \
       }                                                                \
   }))
#define lll_unlock(futex, private)	\
  __lll_unlock (&(futex), private)

atomic_compare_and_exchange_bool_acq是glibc的bool类型的CAS宏

原型大致是

1
2
3
4
5
6
atomic_compare_and_exchange_bool_acq(type *ptr, type desired, type *expected)
type *ptr： 这是指向要比较和可能交换值的指针
type *expected：这是指向存储 ptr 所指向的预期值的位置的指针
type desired：如果 ptr所指向的实际值等于 expected的值，则该值将被存储到 ptr 指向的位置

返回值则始终是ptr指向的旧值

因此当__futex

  • 如果为0
    • 代表目前是未锁定状态
    • 那么交换成功，返回0，函数继续运行
    • __futex的值为1，说明进入锁定状态
  • 如果为1或者2（在__lll_lock_wait_private设置为2）
    • 代表目前是锁定状态
    • 那么交换失败，返回1，函数进入__lll_lock_wait(_private)，进行进程(线程)等待
    • 这是因为__futex为1或者2，已经有线程进入临界区，新线程需要进入锁定状态
__lll_lock_wait_private

在https://github.com/bminor/glibc/blob/glibc-2.25/nptl/lowlevellock.c#L26中定义

1
2
3
4
5
6
7
8
void __lll_lock_wait_private (int *futex)
{
  if (*futex == 2)
    lll_futex_wait (futex, 2, LLL_PRIVATE); /* Wait if *futex == 2.  */

  while (atomic_exchange_acq (futex, 2) != 0)
    lll_futex_wait (futex, 2, LLL_PRIVATE); /* Wait if *futex == 2.  */
}

其中lll_futex_wait在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/unix/sysv/linux/lowlevellock-futex.h#L92中定义

1
2
3
4
5
6
7
#define lll_futex_wait(futexp, val, private) \
  lll_futex_timed_wait (futexp, val, NULL, private)

#define lll_futex_timed_wait(futexp, val, timeout, private)     \
  lll_futex_syscall (4, futexp,                                 \
		     __lll_private_flag (FUTEX_WAIT, private),  \
		     val, timeout)

lll_futex_wait就是对syscall调用futex的简单封装，通过传入LLL_PRIVATE来决定调用FUTEX_WAIT_PRIVATE还是FUTEX_WAIT

回到__lll_lock_wait_private函数

  • 首先，代码检查 futex 所指向的值是否为2，如果是，那么它调用 lll_futex_wait 函数，等待 futex 所指向的值不再为2。
  • 如果 futex 所指向的值不是2，函数就进入一个循环，在这个循环中，它试图通过原子操作 atomic_exchange_acq 将 futex 所指向的值设为2。原子操作 atomic_exchange_acq 会返回 futex 所指向的旧值。
  • 如果 atomic_exchange_acq 返回的旧值不为0（意味着锁被占用），那么代码就会再次调用 lll_futex_wait 函数，等待 futex 所指向的值不再为2。

这里的逻辑要配合unlock一起看才能看得懂，见后续的时序分析

另外，由于虚假唤醒的存在，futex系统调用有可能返回EAGAIN，因此futex系统调用是必须用while循环包住的，这里巧妙的先不进行cas判断来让当前线程陷入futex_wait，从而提高一点性能

pthread_mutex_unlock

pthread_mutex_unlock是一个指向__pthread_mutex_unlock的强符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int __pthread_mutex_unlock (pthread_mutex_t *mutex) {
	return __pthread_mutex_unlock_usercnt (mutex, 1);
}
int internal_function attribute_hidden
__pthread_mutex_unlock_usercnt (pthread_mutex_t *mutex, int decr) {
    int type = PTHREAD_MUTEX_TYPE_ELISION (mutex); //获取锁类型
    if (__builtin_expect (type, PTHREAD_MUTEX_TIMED_NP)
        == PTHREAD_MUTEX_TIMED_NP) {
        /* Always reset the owner field.  */
		mutex->__data.__owner = 0; //对应pthread_mutex_lock，解锁前先设置owner为空
		if (decr) //从__pthread_mutex_unlock进来，这个值为1，必定执行该条件
            /* One less user.  */
            --mutex->__data.__nusers; //减少一个等待该线程的线程数
        	/* Unlock.  */
        	lll_unlock (mutex->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex)); //核心逻辑
			LIBC_PROBE (mutex_release, 1, mutex); //标记解锁成功的探测点
			return 0;
    	}
}

lll_unlock

在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/nptl/lowlevellock.h#L154中定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* Unconditionally set FUTEX to 0 (not acquired), releasing the lock.  If FUTEX
   was >1 (acquired, possibly with waiters), then wake any waiters.  The waiter
   that acquires the lock will set FUTEX to >1.
   Evaluate PRIVATE before releasing the lock so that we do not violate the
   mutex destruction requirements.  Specifically, we need to ensure that
   another thread can destroy the mutex (and reuse its memory) once it
   acquires the lock and when there will be no further lock acquisitions;
   thus, we must not access the lock after releasing it, or those accesses
   could be concurrent with mutex destruction or reuse of the memory.  */
#define __lll_unlock(futex, private)                    \
  ((void)                                               \
   ({                                                   \
     int *__futex = (futex);                            \
     int __private = (private);                         \
     int __oldval = atomic_exchange_rel (__futex, 0);   \
     if (__glibc_unlikely (__oldval > 1))               \
       lll_futex_wake (__futex, 1, __private);          \
   }))
#define lll_unlock(futex, private)	\
  __lll_unlock (&(futex), private)

lll_futex_wake和__lll_lock_wait_private不同，没有任何逻辑，在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/unix/sysv/linux/lowlevellock-futex.h#L107中定义

1
2
3
#define lll_futex_wake(futexp, nr, private)                             \
  lll_futex_syscall (4, futexp,                                         \
		     __lll_private_flag (FUTEX_WAKE, private), nr, 0)
  • 首先将 futex 的值设置为 0，表示锁已释放。
  • 然后检查如果原先的 futex 值大于 1，即表示锁原本是被获取的（可能有等待者），那么唤醒任何一个等待者

时序分析

对于复杂的多线程情况，进行时序分析是最有助于理解问题的

  • 首先是没有发生线程争用的情况
线程1 线程2
1 lll_lock：
if (atomic_compare_and_exchange_bool_acq (futex, 1, 0))
lll_lock_wait_private (futex);
此时futex为0，因此返回1，函数直接退出，进入锁保护的临界区
2 lll_unlock：
if (atomic_exchange_rel (futex, 0) > 1)
lll_futex_wake (futex, 1, private);
此时futex为1，因此返回1，函数直接退出
3 同1
4 同2
  • 接着是发生了线程争用的情况
线程1 线程2
1 lll_lock：
if (atomic_compare_and_exchange_bool_acq (futex, 1, 0))
lll_lock_wait_private (futex);
此时futex为0，因此返回1，函数直接退出，进入锁保护的临界区
2 lll_lock：
if (atomic_compare_and_exchange_bool_acq (futex, 1, 0))
lll_lock_wait_private (futex);
此时futex为1，因此返回0，进入lll_lock_wait_private
3 lll_lock_wait_private：
while (atomic_exchange_acq (futex, 2) != 0)
lll_futex_wait (futex, 2, LLL_PRIVATE);
futex被设置为2，futex的旧值1被返回，进入lll_futex_wait
休眠直到futex不为2
4 lll_unlock：
if (atomic_exchange_rel (futex, 0) > 1)
lll_futex_wake (futex, 1, private);
离开临界区
设置futex为0，由于旧值futex为2，因此返回2，进入lll_futex_wake
唤醒任何一个休眠线程
5 lll_lock_wait_private：
while (atomic_exchange_acq (futex, 2) != 0)
lll_futex_wait (futex, 2, LLL_PRIVATE);
futex被设置为2，旧值0被返回，函数直接退出，进入锁保护的临界区
6 同2，但是有点奇怪的是，这里会造成一次无效唤醒
虽然进入futex以后由于等待列表是空的也没有什么性能损耗
  • 伪线程争用
线程1 线程2
1 lll_lock：
if (atomic_compare_and_exchange_bool_acq (futex, 1, 0))
lll_lock_wait_private (futex);
此时futex为0，因此返回1，函数直接退出，进入锁保护的临界区
2 lll_lock：
if (atomic_compare_and_exchange_bool_acq (futex, 1, 0))
lll_lock_wait_private (futex);
此时futex为1，因此返回0，进入lll_lock_wait_private
3 lll_unlock：
if (atomic_exchange_rel (futex, 0) > 1)
lll_futex_wake (futex, 1, private);
离开临界区
设置futex为0，由于旧值futex为1，因此返回1，进入lll_futex_wake
唤醒任何一个休眠线程，这里也是一次无效唤醒
4 lll_lock_wait_private：
while (atomic_exchange_acq (futex, 2) != 0)
lll_futex_wait (futex, 2, LLL_PRIVATE);
futex被设置为2，旧值0被返回，函数直接退出，进入锁保护的临界区
5 lll_unlock：
if (atomic_exchange_rel (futex, 0) > 1)
lll_futex_wake (futex, 1, private);
离开临界区
设置futex为0，由于旧值futex为2，因此返回2，进入lll_futex_wake
唤醒任何一个休眠线程，这里也是一次无效唤醒

线程争用和伪线程争用比较，可以看出当unlock的时候futex=2才是glibc争用的情况

但是也有可能是发生了伪线程争用，没有syscall就直接退出了

小结

看到这里大致模模糊糊有个概念，锁实际上是抢的一个内存地址的值

glibc通过CAS抢1来预先判断一下有没有争用，如果没有直接退出

如果抢1失败了，就设置为2，再由futex决断是否为2来休眠和唤醒

因此简化版的锁可以通过让futex决断是否为1来休眠和唤醒，如下

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <atomic>
#include <thread>
#include <unistd.h>
#include <sys/syscall.h>
#include <linux/futex.h>
#include <sys/time.h>
#include <assert.h>

constexpr int UNLOCKED = 0;
constexpr int LOCKED = 1;

class MyMutex {
public:
    void lock() {
        while(1) {
            uint32_t expected = UNLOCKED;
            if (m_lock.compare_exchange_strong(expected, LOCKED)) {
                break;
            }
            int res = syscall(SYS_futex, &m_lock, FUTEX_WAIT_PRIVATE, LOCKED, nullptr, nullptr, 0);
            if (res == -1 && errno != EAGAIN) {
                std::cout << errno << std::endl;
                assert(false);
            }
        }
    }

    void unlock() {
        m_lock = UNLOCKED;
        int res = syscall(SYS_futex, &m_lock, FUTEX_WAKE_PRIVATE, 1, nullptr, nullptr, 0);
        if (res == -1) {
            std::cout << errno << std::endl;
            assert(false);
        }
    }

    std::atomic<uint32_t> m_lock{UNLOCKED};
};

MyMutex g_mutex;

int64_t gIndex = 0;

void thread_function() {
    for (int64_t i = 0;i < 10000000;i++) {
        g_mutex.lock();
        gIndex++;
        g_mutex.unlock();
    }
}

int main() {
    std::thread t1(thread_function);
    std::thread t2(thread_function);
    std::thread t3(thread_function);

    t1.join();
    t2.join();
    t3.join();

    std::cout << gIndex << std::endl;
    
    return 0;
}

futex源码分析

futex有两个api

  • futex_wait(int *uaddr, int val)
    • 只有当 *uaddr 等于 val 时，才进行等待。
    • 这保证了在发生上下文切换之前，值没有被另一个线程更改。如果值被改变，futex_wait 将直接返回，不会有任何等待。
  • futex_wake(int *uaddr, int n)
    • 用于唤醒在 *uaddr 上等待的 n 个进程或线程。

futex依赖的核心数据结构futex_q在https://elixir.bootlin.com/linux/v2.6.39.4/source/kernel/futex.c#L122定义

1
2
3
4
5
6
7
8
struct futex_q {
	struct plist_node list; //用于将当前 futex_q 插入到链表中

	struct task_struct *task; //指向正在等待在此futex上的任务的指针
	spinlock_t *lock_ptr; //保护链表
	union futex_key key;
	...
};

什么是锁

所谓的锁，在计算机里本质上就是一块内存空间。当这个空间被赋值为1的时候表示加锁了，被赋值为0的时候表示解锁了。

在多线程场景下，当多个线程抢一个锁，就是抢着要把这块内存赋值为1。

抢失败的线程就被休眠（或者死循环），这样就不会和抢成功的线程一起操作。

当抢成功的线程释放锁，抢失败的的线程就被唤醒抢锁（或者死循环抢锁）。

怎么实现锁

从刚才锁的本质分析可以看出来，锁分为休眠和死循环两种，也就是互斥锁和自旋锁。

自旋锁只依赖抢内存空间赋值成功，不需要唤醒抢失败者，因此实现是非常简单的。

1
2
3
4
5
6
7
spinlock() {
	while (CAS set state = 1 is failed) {
	}
}
spinUnlock() {
	CAS set state = 0
}

而互斥锁的数据结构和算法就显得复杂了很多，包含了一块待抢的内存结构，和一个抢失败线程的等待唤醒列表。

为了保证互斥锁数据结构的原子性，互斥锁本身的线程安全是由自旋锁来保证的。

纯内核态的互斥锁

最早期的互斥锁是完全的内核态的来实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
lock(){
	spinlock()
	if (set state = 1 is failed) {
  		添加wait_list并且修改线程状态为TASK_INTERRUPTIBLE
  	}
  	spinUnlock()
	执行schedule()
}
​
unlock(){
	spinlock()
	set state = 0
	从wait_list中移除任意一个阻塞线程
	接着调用wake_up_process()修改线程状态为TASK_RUNNING，然后重新添加到可运行队列中
	spinUnlock()
}

futex的诞生：用户态+内核态的互斥锁

futex全称fast userspace mutex ，顾名思义，是用户态优化性能的锁

由 Rusty Russell、Hubertus Franke 和 Mathew Kirkwood 在 2.5.7 中引入，是一种用于用户态应用程序的快速、轻量级内核辅助锁定原语。它提供非常快速的无竞争锁获取和释放。

futex 状态存储在用户空间变量中（在所有平台上都是无符号 32 位整数）。

使用原子操作是为了在无竞争的情况下更改 futex 的状态，而无需系统调用的开销。在竞争的情况下，调用内核来使任务进入睡眠状态并唤醒它们。

相关文章
  • 2019-03-14
    浅析条件变量

    本篇博客会深入分析条件变量实现来理解两个问题：

    • 为什么条件变量要配合锁来使用 — 信号丢失问题
    • 为什么条件变量需要用while循环来判断条件，而不是if — 虚假唤醒(spurious wakeup)问题

    这两个问题不仅是C会遇到，所有语言的封装几乎都不可避免

    先区分一下条件和条件变量，条件是指常用情况下，signal线程修改的值，使得cond_wait判断该值后不再阻塞