Jungle's Blog
📚 文章 🏷️ 标签 🗃️ 分类 👴 关于
Jungle's Blog

目录

Operating System Chapter5 并发控制：互斥

Jungle 出版于 Operating System
   约 7068 字   预计阅读 15 分钟 

Operating System

$Nanjing\ University\rightarrow Yanyan\ Jiang\newline$

Update

Update in 2023-03-08 17:30

继续看，并发真™️👨

Overview

复习

  • 状态机、状态机、状态机

本次课回答的问题

  • Q: 如何在多处理器上实现线程互斥？

本次课主要内容

  • 自旋锁的实现
  • 互斥锁的实现

共享内存上的互斥

回顾：并发编程

理解并发的工具

  • 线程 = 人 (大脑能完成局部存储和计算)
  • 共享内存 = 物理世界 (物理世界天生并行)
  • 一切都是状态机

回顾：互斥算法

互斥 (mutual exclusion)，“互相排斥”

  • 实现 lock_t 数据结构和 lock/unlock API:
1
2
3
4
5

typedef struct {
  ...
} lock_t;
void lock(lock_t *lk);
void unlock(lock_t *lk);

一把 “排他性” 的锁——对于锁对象 lk

  • 如果某个线程持有锁，则其他线程的 lock 不能返回

在共享内存上实现互斥

失败的尝试

(部分) 成功的尝试

实现互斥的根本困难：不能同时读/写共享内存

  • load (环顾四周) 的时候不能写，只能 “看一眼就把眼睛闭上”
    • 看到的东西马上就过时了
  • store (改变物理世界状态) 的时候不能读，只能 “闭着眼睛动手”
    • 也不知道把什么改成了什么
  • 这是简单、粗暴 (稳定)、有效的《操作系统》课

自旋锁 (Spin Lock)

解决问题的两种方法

提出算法、解决问题 (Dekker/Peterson/…’s Protocols)

或者……

改变假设 (软件不够，硬件来凑$\Longrightarrow$ x86架构的风格，软件指令做不好直接写一个指令集让硬件这么做hhh)

假设硬件能为我们提供一条 “瞬间完成” 的读 + 写指令

  • 请所有人闭上眼睛，看一眼 (load)，然后贴上标签 (store)
    • 如果多人同时请求，硬件选出一个 “胜者”
    • “败者” 要等 “胜者” 完成后才能继续执行

x86 原子操作：LOCK 指令前缀

例子：sum-atomic.c

  • sum = 200000000

Atomic exchange (load + store)

1
2
3
4
5
6

int xchg(volatile int *addr, int newval) {
  int result;
  asm volatile ("lock xchg %0, %1"
    : "+m"(*addr), "=a"(result) : "1"(newval));
  return result;
}

  • 重点就是asm内联汇编那句，这里是“一气呵成”的

  • 更多的原子指令：stdatomic.h (C11)

用 xchg 实现互斥（也就是自旋锁的本质实现过程）

  • xchg在之前的文章中有提到过

如何协调宿舍若干位同学上厕所问题？

  • 在厕所门口放一个桌子 (共享变量)
    • 初始时，桌上是 🔑

实现互斥的协议

  • 想上厕所的同学 (一条 xchg 指令)
    • 天黑请闭眼
    • 看一眼桌子上有什么 (🔑 或 🔞)
    • 把 🔞 放到桌上 (覆盖之前有的任何东西)
    • 天亮请睁眼；看到 🔑 才可以进厕所哦
  • 出厕所的同学
    • 把 🔑 放到桌上

实现互斥：自旋锁

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int table = YES;

void lock() {
retry:
  int got = xchg(&table, NOPE);
  if (got == NOPE)
    goto retry;
  assert(got == YES);
}

void unlock() {
  xchg(&table, YES)
}


int locked = 0;
void lock() { while (xchg(&locked, 1)) ; }
void unlock() { xchg(&locked, 0); }
  • 重要的还是xchg这个东西，保证那一步是原子性的，就没有其他事情了

实现互斥：自旋锁 (cont’d)

并发编程：千万小心

原子指令的模型

  • 保证之前的 store 都写入内存
  • 保证 load/store 不与原子指令乱序

原子指令的诞生：Bus Lock (80486)

Update

Update in 2023-03-09 10:00

早起开完SB大会，✋接着看

咖啡机里面的咖啡真提神，估计下午毛概得狠狠睡一把

  • 486 (20-50MHz) 就支持 dual-socket 了
/img/Operating System/chapter5-1.jpg
80486

  • 如果CPU1需要执行add x, 1，那么需要分成3步

    • 从memory里面load
    • 再把这个值add 1之后先放入一个内部的寄存器里
    • 再store把m的值写回内存里

  • 为什么486时代会诞生LOCK这样的指令呢？

    • 因为涉及了两个CPU面对同一个memory的状况，所以需要对memory进行lock的操作

  • 设计方法

    • x86的指令集有指令的前缀（比如rep），我们让lock也变成一个指令前缀
1

lock + |指令|
  • 当CPU开始读指令的时候，它会先读到lock指令，这个时候就上锁（也即是对应的CPU拿到了总线的锁）
  • 等到CPU拿到总线的锁之后，它会再执行后面的部分
  • 把有关指令执行完成之后再把锁释放掉

负担

  • 今天的CPU与memory之间都有各自的cache，而且cache已经和CPU集成在一个元件上面了，而且是多级cache
  • 486时代仅仅只有外面的一块cache（而且这块cache在主板上），所以说只要CPU拿到了总线🔒的控制权，就把自己和外面的一切隔离开了

  • 多级cache会使得lock变得很麻烦

  • 例子：一个数据在两个CPU的cache里面都有副本

  • 这个时候如果CPU1要lock访问m的话，就要将cache21里面的m副本“踢掉” $\Longrightarrow$ 也就是今天inter一个很大的历史包袱：缓存的一致性 $\Longrightarrow$ 解决方案：将所有的cache用总线连接起来
  • 一旦其中有一个数据需要被lock，那么总线需要遍历一遍所有CPU的cache，如果发现了该数据的副本，就要将该数据从其他CPU的cache里面“踢掉”，这是很浪费时间的

Lock 指令的现代实现

在 L1 cache 层保持一致性 (ring/mesh bus)

  • 相当于每个 cache line 有分别的锁
  • store(x) 进入 L1 缓存即保证对其他处理器可见
    • 但要小心 store buffer 和乱序执行

L1 cache line 根据状态进行协调

  • M (Modified), 脏值
  • E (Exclusive), 独占访问
  • S (Shared), 只读共享
  • I (Invalid), 不拥有 cache line

RISC-V: 另一种原子操作的设计

考虑常见的原子操作：

  • atomic test-and-set
    • reg = load(x); if (reg == XX) { store(x, YY); }
  • lock xchg
    • reg = load(x); store(x, XX);
  • lock add
    • t = load(x); t++; store(x, t);

它们的本质都是

  1. load
  2. exec (处理器本地寄存器的运算)
  3. store

Load-Reserved/Store-Conditional (LR/SC)

  • LR: 在内存上标记 reserved (盯上你了)，中断、其他处理器写入都会导致标记消除
    • 我先读，读完之后在这个物品上面做一个标记
    • 标记一直在物品上，同时在做本地的计算
    • 本地计算算完了，该写了
    • 写的时候要先检测标记，只有标记还在的时候才可以写，否则返回fail，只能再次尝试重新上锁写入
  • 本地内存的计算不重要，重要的是共享内存的计算
1
2
3

lr.w rd, (rs1)
  rd = M[rs1]
  reserve M[rs1]
  • SC: 如果 “盯上” 未被解除，则写入
1
2
3
4
5
6

sc.w rd, rs2, (rs1)
  if still reserved:
    M[rs1] = rs2
    rd = 0
  else:
    rd = nonzero

Compare-and-Swap 的 LR/SC 实现

1
2
3
4
5
6

int cas(int *addr, int cmp_val, int new_val) {
  int old_val = *addr;
  if (old_val == cmp_val) {
    *addr = new_val; return 0;
  } else { return 1; }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

cas:
  lr.w  t0, (a0)       # Load original value.
  bne   t0, a1, fail   # Doesn’t match, so fail.
  sc.w  t0, a2, (a0)   # Try to update.
  bnez  t0, cas        # Retry if store-conditional failed.
  li a0, 0             # Set return to success.
  jr ra                # Return.
fail:
  li a0, 1             # Set return to failure.
  jr ra                # Return
  • lr，sc还可以检测🔒的拥堵程度

LR/SC 的硬件实现

  • BOOM (Berkeley Out-of-Order Processor)

  • riscv-boom

  • lsu/dcache.scala

  • 留意s2_sc_fail的条件

    • s2 是流水线 Stage 2

  • (yzh 扒出的代码)

互斥锁 (Mutex Lock)

自旋锁的缺陷

  • 性能问题 (0)

    • 自旋 (共享变量) 会触发处理器间的缓存同步，延迟增加（总线遍历cache踢副本）

  • 性能问题 (1)

    • 除了进入临界区的线程，其他处理器上的线程都在空转（看自旋锁的实现代码，没有拿到🔒的线程在空转死循环）

      • 会造成多CPU机器利用率过低的问题（就有🔒的在工作）

    • 争抢锁的处理器越多，利用率越低

  • 性能问题 (2)

    • 获得自旋锁的线程可能被操作系统切换出去（出现在单CPU时间片轮转的条件下，轮转时间片导致拿🔒的线程休眠，相当于你拿着🔒回宿舍睡觉，全教室的人只能等着你 $\Longrightarrow$ 还在死循环里面空转）
      • 操作系统不 “感知” 线程在做什么
      • (但为什么不能呢？) $\Longrightarrow$ 课后思考

  • 实现 100% 的资源浪费

Scalability: 性能的新维度

同一份计算任务，时间 (CPU cycles) 和空间 (mapped memory) 会随处理器数量的增长而变化。

注意和数据结构里面的计算数据量n区别，这里面衡量的标准是依据处理器的数量而定的

sum-scalability.c，里面用的就是自旋锁，在自旋锁的保护下执行sum++

 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

#include "thread.h"
#include "thread-sync.h"

#define N 10000000
spinlock_t lock = SPIN_INIT();

long n, sum = 0;

void Tsum() {
  for (int i = 0; i < n; i++) {
    spin_lock(&lock);
    sum++;
    spin_unlock(&lock);
  }
}

int main(int argc, char *argv[]) {
  assert(argc == 2);
  int nthread = atoi(argv[1]);
  n = N / nthread; //nthread是线程数量，n就是平摊下来每个线程要执行的sum++（也就是🔒）的数量
  for (int i = 0; i < nthread; i++) {
    create(Tsum);
  }
  join();
  assert(sum == n * nthread);
}

自旋锁的实现(来自thread-sync.h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void spin_lock(spinlock_t *lk) {
  while (1) {
    intptr_t value = atomic_xchg(lk, 1);
    if (value == 0) {
      break;
    }
  }
}

void spin_unlock(spinlock_t *lk) {
  atomic_xchg(lk, 0);
}
Update

Update in 2023-03-09 15:20

绷不住直接😪了，睡醒继续

  • 运行
 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

gcc sum-scalability.c -O2 -lpthread

 2023-03-09 15:25:37 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 1

real    0m0.043s
user    0m0.016s
sys     0m0.021s

 2023-03-09 15:25:40 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 2

real    0m0.229s
user    0m0.337s
sys     0m0.071s

 2023-03-09 15:25:44 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 4

real    0m0.337s
user    0m0.393s
sys     0m0.166s

 2023-03-09 15:26:21 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 32

real    0m1.316s
user    0m2.176s
sys     0m0.288s

 2023-03-09 15:26:35 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 32

real    0m1.230s
user    0m2.040s
sys     0m0.255s
  • 现象：同样的工作量，线程越多，效率越低
/img/Operating System/chapter5-2.jpg
图像

自旋锁的使用场景

  • 两个重要的约束
    • 临界区几乎不“拥堵”$\Longrightarrow$ 几乎就只有一个线程进入临界区 $\Longrightarrow$ 这样争抢🔒的状况就会很少
    • 持有自旋锁时禁止执行流切换 $\Longrightarrow$ 翻译成上面的人话就是禁止拿着🔒回宿舍😴 $\Longrightarrow$ 但是，我们的应用程序是做不到这一点的（如果应用程序能够防止自己在时间片轮转的时候被切出去，那么一个while(1);就能让电脑崩溃，操作系统是绝对禁止这样的事情的）

使用场景：操作系统内核的并发数据结构 (短临界区)

  • 操作系统可以关闭中断和抢占 $\Longrightarrow$ 这就是和应用程序不一样的地方
    • 保证锁的持有者在很短的时间内可以释放锁
  • (如果是虚拟机呢…😂)
    • PAUSE 指令会触发 VM Exit $\Longrightarrow$ 防止有故障把物理机给卡死
  • 但依旧很难做好

实现线程 + 长临界区的互斥

作业那么多，与其干等 Online Judge 发布，不如把自己 (CPU) 让给其他作业 (线程) 执行？

说白了就是有事情卡住了就去干别的，别就瞎🐔8️⃣干等着这一件事（这也就是比自旋锁高明的地方）

“让” 不是 C 语言代码可以做到的 (C 代码只能计算)

  • 把锁的实现放到操作系统里就好啦！$\Longrightarrow$ 系统调用

    • syscall(SYSCALL_lock, &lk);

      • 试图获得 lk，但如果失败，就切换到其他线程 $\Longrightarrow$ 这个就是精髓

    • syscall(SYSCALL_unlock, &lk);

      • 释放 lk，如果有等待锁的线程就唤醒
Update

Update in 2023-03-09 19:15

干拌面吃完真撑的慌，下回还是吃汤面

晚上看完

实现线程 + 长临界区的互斥 (cont’d)

  • 操作系统 = 更衣室管理员

  • 先到的人 (线程)

    • 成功获得手环，进入游泳馆
    • *lock = 🔒，系统调用直接返回

  • 后到的人 (线程)

    • 不能进入游泳馆，排队等待
    • 线程放入等待队列，执行线程切换 (yield)

  • 洗完澡出来的人 (线程)

    • 交还手环给管理员；管理员把手环再交给排队的人

    • 如果等待队列不空，从等待队列中取出一个线程允许执行

    • 如果等待队列为空，*lock = ✅

  • 管理员 (OS) 使用自旋锁确保自己处理手环的过程是原子的

Futex = Spin + Mutex

关于互斥的一些分析

  • 自旋锁 (线程直接共享 locked)

    • 更快的 fast path

      • xchg 成功 → 立即进入临界区，开销很小

    • 更慢的 slow path

      • xchg 失败 → 浪费 CPU 自旋等待（交换一些不是🔒，没用的东西）

  • 睡眠（互斥）锁 (通过系统调用访问 locked)

    • 更快的 slow path

      • 上锁失败线程不再占用 CPU

    • 更慢的 fast path

      • 即便上锁成功也需要进出内核 (syscall) $\Longrightarrow$ 速度相对比较慢

Futex: Fast Userspace muTexes

解决方案：全都要

  • 性能优化的最常见技巧

    • 看 average (frequent) case 而不是 worst case $\Longrightarrow$ 这里是和算法题做对比，算法题要保证所有可能的情况都可以被高效计算（worst case），而操作系统要求的则是大部分情况都可以被快速处理，少数的情况处理地慢也可以（average）

  • POSIX 线程库中的互斥锁 (pthread_mutex) $\Longrightarrow$ 两种🔒的好处都得了

  • 我们将sum-scalability.c里面的自旋锁换成互斥锁

1

mutex_t lock = MUTEX_INIT();
  • 互斥锁的实现（通过syscall）
1
2

void mutex_lock(mutex_t *lk)   { pthread_mutex_lock(lk); }
void mutex_unlock(mutex_t *lk) { pthread_mutex_unlock(lk); }
  • 编译+测试
 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

 2023-03-09 20:11:45 ⌚  jungle-virtual-machine in ~/chapter5
○ → gcc sum-scalability.c -O2 -lpthread

 2023-03-09 20:16:06 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 1

real    0m0.065s
user    0m0.037s
sys     0m0.019s

 2023-03-09 20:16:12 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 2

real    0m0.180s
user    0m0.121s
sys     0m0.185s

 2023-03-09 20:16:26 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 4

real    0m0.179s
user    0m0.156s
sys     0m0.152s

 2023-03-09 20:16:28 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 32

real    0m0.106s
user    0m0.100s
sys     0m0.039s

 2023-03-09 20:20:18 ⌚  jungle-virtual-machine in ~/chapter5
○ → time ./a.out 64

real    0m0.087s
user    0m0.056s
sys     0m0.060s

  • 可以看到当线程数量变多的时候，pthread_mutex处理的效率要远高于自旋锁

  • 观察系统调用 (strace) $\Longrightarrow$ 太长了就复制一段

  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
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

2023-03-09 20:11:24 ⌚  jungle-virtual-machine in ~/chapter5
○ → strace -f ./a.out 64
execve("./a.out", ["./a.out", "64"], 0x7ffe8bbc7370 /* 64 vars */) = 0
brk(NULL)                               = 0x55d83eca4000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffcb38f0700) = -1 EINVAL (无效的参数)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fda56b2a000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (没有那个文件或目录)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=76495, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 76495, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fda56b17000
close(3)                                = 0
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0P\237\2\0\0\0\0\0"..., 832) = 832
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
pread64(3, "\4\0\0\0 \0\0\0\5\0\0\0GNU\0\2\0\0\300\4\0\0\0\3\0\0\0\0\0\0\0"..., 48, 848) = 48
pread64(3, "\4\0\0\0\24\0\0\0\3\0\0\0GNU\0i8\235HZ\227\223\333\350s\360\352,\223\340."..., 68, 896) = 68
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=2216304, ...}, AT_EMPTY_PATH) = 0
pread64(3, "\6\0\0\0\4\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0@\0\0\0\0\0\0\0"..., 784, 64) = 784
mmap(NULL, 2260560, PROT_READ, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fda56800000
mmap(0x7fda56828000, 1658880, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x28000) = 0x7fda56828000
mmap(0x7fda569bd000, 360448, PROT_READ, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1bd000) = 0x7fda569bd000
mmap(0x7fda56a15000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x214000) = 0x7fda56a15000
mmap(0x7fda56a1b000, 52816, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fda56a1b000
close(3)                                = 0
mmap(NULL, 12288, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fda56b14000
arch_prctl(ARCH_SET_FS, 0x7fda56b14740) = 0
set_tid_address(0x7fda56b14a10)         = 4614
set_robust_list(0x7fda56b14a20, 24)     = 0
rseq(0x7fda56b150e0, 0x20, 0, 0x53053053) = 0
mprotect(0x7fda56a15000, 16384, PROT_READ) = 0
mprotect(0x55d83cf2f000, 4096, PROT_READ) = 0
mprotect(0x7fda56b64000, 8192, PROT_READ) = 0
prlimit64(0, RLIMIT_STACK, NULL, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
munmap(0x7fda56b17000, 76495)           = 0
rt_sigaction(SIGRT_1, {sa_handler=0x7fda568918f0, sa_mask=[], sa_flags=SA_RESTORER|SA_ONSTACK|SA_RESTART|SA_SIGINFO, sa_restorer=0x7fda56842520}, NULL, 8) = 0
rt_sigprocmask(SIG_UNBLOCK, [RTMIN RT_1], NULL, 8) = 0
mmap(NULL, 8392704, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0x7fda55fff000
mprotect(0x7fda56000000, 8388608, PROT_READ|PROT_WRITE) = 0
getrandom("\xc0\x0d\x30\x79\xa6\xc0\x9a\x32", 8, GRND_NONBLOCK) = 8
brk(NULL)                               = 0x55d83eca4000
brk(0x55d83ecc5000)                     = 0x55d83ecc5000
rt_sigprocmask(SIG_BLOCK, ~[], [], 8)   = 0
clone3({flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, child_tid=0x7fda567ff910, parent_tid=0x7fda567ff910, exit_signal=0, stack=0x7fda55fff000, stack_size=0x7fff00, tls=0x7fda567ff640}strace: Process 4615 attached
 => {parent_tid=[4615]}, 88) = 4615
[pid  4614] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4615] rseq(0x7fda567fffe0, 0x20, 0, 0x53053053 <unfinished ...>
[pid  4614] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4615] <... rseq resumed>)         = 0
[pid  4614] mmap(NULL, 8392704, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0 <unfinished ...>
[pid  4615] set_robust_list(0x7fda567ff920, 24 <unfinished ...>
[pid  4614] <... mmap resumed>)         = 0x7fda557fe000
[pid  4615] <... set_robust_list resumed>) = 0
[pid  4614] mprotect(0x7fda557ff000, 8388608, PROT_READ|PROT_WRITE <unfinished ...>
[pid  4615] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4614] <... mprotect resumed>)     = 0
[pid  4615] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4614] rt_sigprocmask(SIG_BLOCK, ~[], [], 8) = 0
[pid  4614] clone3({flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, child_tid=0x7fda55ffe910, parent_tid=0x7fda55ffe910, exit_signal=0, stack=0x7fda557fe000, stack_size=0x7fff00, tls=0x7fda55ffe640}strace: Process 4616 attached
 => {parent_tid=[4616]}, 88) = 4616
[pid  4616] rseq(0x7fda55ffefe0, 0x20, 0, 0x53053053 <unfinished ...>
[pid  4614] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4616] <... rseq resumed>)         = 0
[pid  4614] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4614] mmap(NULL, 8392704, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0 <unfinished ...>
[pid  4616] set_robust_list(0x7fda55ffe920, 24 <unfinished ...>
[pid  4614] <... mmap resumed>)         = 0x7fda54ffd000
[pid  4616] <... set_robust_list resumed>) = 0
[pid  4614] mprotect(0x7fda54ffe000, 8388608, PROT_READ|PROT_WRITE <unfinished ...>
[pid  4616] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4614] <... mprotect resumed>)     = 0
[pid  4616] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4614] rt_sigprocmask(SIG_BLOCK, ~[],  <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4615] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] <... rt_sigprocmask resumed>[], 8) = 0
[pid  4616] <... futex resumed>)        = -1 EAGAIN (资源暂时不可用)
[pid  4615] <... futex resumed>)        = 0
[pid  4614] clone3({flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, child_tid=0x7fda557fd910, parent_tid=0x7fda557fd910, exit_signal=0, stack=0x7fda54ffd000, stack_size=0x7fff00, tls=0x7fda557fd640} <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4615] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1) = 0
strace: Process 4617 attached
[pid  4616] <... futex resumed>)        = -1 EAGAIN (资源暂时不可用)
[pid  4614] <... clone3 resumed> => {parent_tid=[4617]}, 88) = 4617
[pid  4616] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4617] rseq(0x7fda557fdfe0, 0x20, 0, 0x53053053 <unfinished ...>
[pid  4614] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4616] <... futex resumed>)        = 0
[pid  4614] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4617] <... rseq resumed>)         = 0
[pid  4614] mmap(NULL, 8392704, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0 <unfinished ...>
[pid  4617] set_robust_list(0x7fda557fd920, 24 <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4614] <... mmap resumed>)         = 0x7fda547fc000
[pid  4617] <... set_robust_list resumed>) = 0
[pid  4615] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] mprotect(0x7fda547fd000, 8388608, PROT_READ|PROT_WRITE <unfinished ...>
[pid  4617] rt_sigprocmask(SIG_SETMASK, [],  <unfinished ...>
[pid  4615] <... futex resumed>)        = 1
[pid  4614] <... mprotect resumed>)     = 0
[pid  4617] <... rt_sigprocmask resumed>NULL, 8) = 0
[pid  4616] <... futex resumed>)        = 0
[pid  4614] rt_sigprocmask(SIG_BLOCK, ~[],  <unfinished ...>
[pid  4617] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4614] <... rt_sigprocmask resumed>[], 8) = 0
[pid  4615] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] clone3({flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, child_tid=0x7fda54ffc910, parent_tid=0x7fda54ffc910, exit_signal=0, stack=0x7fda547fc000, stack_size=0x7fff00, tls=0x7fda54ffc640} <unfinished ...>
[pid  4617] <... futex resumed>)        = 0
[pid  4615] <... futex resumed>)        = 1
[pid  4617] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] <... clone3 resumed> => {parent_tid=[4618]}, 88) = 4618
[pid  4617] <... futex resumed>)        = 1
[pid  4616] <... futex resumed>)        = 0
[pid  4614] rt_sigprocmask(SIG_SETMASK, [], NULL, 8) = 0
[pid  4617] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] mmap(NULL, 8392704, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0 <unfinished ...>
[pid  4617] <... futex resumed>)        = 0
[pid  4616] <... futex resumed>)        = 1
[pid  4614] <... mmap resumed>)         = 0x7fda53ffb000
[pid  4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4615] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4614] mprotect(0x7fda53ffc000, 8388608, PROT_READ|PROT_WRITE <unfinished ...>
[pid  4617] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4616] <... futex resumed>)        = -1 EAGAIN (资源暂时不可用)
[pid  4614] <... mprotect resumed>)     = 0
[pid  4617] <... futex resumed>)        = 0
[pid  4616] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4615] <... futex resumed>)        = 0
[pid  4614] rt_sigprocmask(SIG_BLOCK, ~[],  <unfinished ...>
[pid  4616] <... futex resumed>)        = 0
[pid  4614] <... rt_sigprocmask resumed>[], 8) = 0
[pid  4615] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid  4614] clone3({flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, child_tid=0x7fda547fb910, parent_tid=0x7fda547fb910, exit_signal=0, stack=0x7fda53ffb000, stack_size=0x7fff00, tls=0x7fda547fb640} <unfinished ...>
[pid  4616] futex(0x55d83cf30060, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid  4615] <... futex resumed>)        = -1 EAGAIN (资源暂时不可用)
[pid  4616] <... futex resumed>)        = 0
  • 里面有很多类似73行的语句[pid 4616] futex(0x55d83cf30060, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>

一、什么是futex？

futex是Fast Userspace muTEX的缩写，该机制是由Rusty Russell、Hubertus Franke和Mathew Kirkwood在2.5.7版本的内核中引入，虽然名字中有互斥锁（mutex）的含义，但实际它是一种用于用户空间应用程序的通用同步工具（基于futex可以在userspace实现互斥锁、读写锁、condition variable等同步机制）。Futex组成包括：

  • 内核空间的等待队列
  • 用户空间层的32-bit futex word（所有平台都是32bit，包括64位平台）

在没有竞争的场景下，锁的获取和释放性能都非常高，不需要内核的参与，仅仅是通过用户空间的原子操作来修改futex word的状态即可。在有竞争的场景下，如果线程无法获取futex锁，那么把自己放入到 wait queue中（陷入内核，有系统调用的开销），而在owner task释放锁的时候，如果检测到有竞争（等待队列中有阻塞任务），就会通过系统调用来唤醒等待队列中的任务，使其恢复执行，继续去持锁。如果没有竞争，那么也无需陷入内核。

摘自：《什么是futex？》

Futex（Fast Userspace Mutex）是一种用户空间锁，它是Linux内核提供的一种同步原语，用于控制多个进程或线程之间的访问共享资源。Futex主要用于实现更高级别的同步原语，例如条件变量和读写锁。Futex提供了一种低开销的锁机制，当锁被持有时，它可以避免将线程或进程阻塞在内核空间。

在Futex中，锁的状态保存在用户空间中，而不是内核空间中，当线程或进程需要获取锁时，它会尝试将锁的状态从“未锁定”改为“锁定”状态。如果成功，线程或进程就可以访问共享资源。如果锁已被其他线程或进程占用，则它将在用户空间内忙等待，直到锁被释放。

Futex还支持一些其他的操作，例如等待一个特定的值或比较并交换值，这些操作可以用于实现条件变量和读写锁等高级别的同步原语。由于Futex的低开销和高效性，它成为了Linux系统中许多高级别同步原语的基础。

来自ChatGPT

  • 如果我们仔细观察就会发现，futex调用的数量远远小于lock和unlock的数量

  • gdb 调试

    • set scheduler-locking on, info threads, thread X

Futex: Fast Userspace muTexes (cont’d)

先在用户空间自旋

  • 如果获得锁，直接进入
  • 未能获得锁，系统调用
  • 解锁以后也需要系统调用
    • futex.py
    • 更好的设计可以在 fast-path 不进行系统调用

futex.py

 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
66
67
68
69
70
71

class Futex:
    locked, waits = '', ''

    def tryacquire(self):
        if not self.locked:
            # Test-and-set (cmpxchg)
            # Same effect, but more efficient than xchg
            self.locked = '🔒'
            return ''
        else:
            return '🔒'

    def release(self):
        if self.waits:
            self.waits = self.waits[1:]
        else:
            self.locked = ''

    @thread
    def t1(self):
        while True:
            if self.tryacquire() == '🔒':     # User
                self.waits = self.waits + '1' # Kernel
                while '1' in self.waits:      # Kernel
                    pass
            cs = True                         # User
            del cs                            # User
            self.release()                    # Kernel

    @thread
    def t2(self):
        while True:
            if self.tryacquire() == '🔒':
                self.waits = self.waits + '2'
                while '2' in self.waits:
                    pass
            cs = True
            del cs
            self.release()

    @thread
    def t3(self):
        while True:
            if self.tryacquire() == '🔒':
                self.waits = self.waits + '3'
                while '3' in self.waits:
                    pass
            cs = True
            del cs
            self.release()

    @marker
    def mark_t1(self, state):
        if localvar(state, 't1', 'cs'): return 'blue'

    @marker
    def mark_t2(self, state):
        if localvar(state, 't2', 'cs'): return 'green'

    @marker
    def mark_t3(self, state):
        if localvar(state, 't3', 'cs'): return 'yellow'

    @marker
    def mark_both(self, state):
        count = 0
        for t in ['t1', 't2', 't3']:
            if localvar(state, t, 'cs'):
                count += 1
        if count > 1:
            return 'red'

  • python代码的优势：如果你想让一句代码原子执行——>加入yield breakpoint()

  • python3 model-checker.py futex.py | python3 visualize.py -t > a.html 重定向，可视化

  • 样例仓库

RTFM (劝退)

  • futex (7), futex (2)
  • A futex overview and update (LWN)
  • Futexes are tricky (论 model checker 的重要性) $\Longrightarrow$ 同时也提示我们从最简单的写起，千万不要觉得自己行就装🖊搞大的
  • (我们不讲并发算法)

总结

本次课回答的问题

  • Q: 如何在多处理器系统上实现互斥？

Take-away message

  • 软件不够，硬件来凑 (自旋锁)
  • 用户不够，内核来凑 (互斥锁)
    • 找到你依赖的假设，并大胆地打破它
  • Fast/slow paths: 性能优化的重要途径

声明：本文章引用资料与图像均已做标注，如有侵权本人会马上删除

Operating System
更新于 2023-03-08