沧海月明

With great power comes great responsibility

0%

操作系统并发

Terms

  • Critical section: piece of code that accesses a shared resource.
  • Race condition: 多个线程同时进去 critical section。
  • Indeterminate:指程序在多线程情况下,程序结果不唯一。
  • Mutual exclusion:排他。

Locks

Evaluating Locks

  • Mutual exclusion
  • Fairness 当大量线程同时访问时,是否存在某些 thread starve 的可能。
  • Performance

Controlling Interrupts

就是 lock 的时候直接关闭系统中断,但是这样很危险,而且不靠谱。因为一旦关闭中断,操作系统也无法获得操作权利。

而且不支持多核处理器。

image-20210511122124949

所以这种方法只有在某些地方用用了。

Simple Spin Lock

image-20210511132750354

这种 lock 方式由两个问题:

correctness:不正确

image-20210511132953632

performance:spin wait 的方式会消耗大量的 CPU 时间片。

Spin Lock with Test-And-Set

硬件层面提供了如下原子操作:

image-20210511133309929

image-20210511134948170

Spin Lock With Compare-And-Swap

image-20210511135433031

image-20210511141310262

和 Test-And-Set 差不多,Java 里面的 CAS 就是 Compare-And-Swap。

Fetch-And-Add

有些硬件提供这种 premitive。

image-20210511141603678

可以基于这个,开发一个 ticket lock。ticket lock 的好处就是维持了 fairness,保证每个 thread 一定能够被执行到,不会被 starve。

image-20210511141656163

解决 spin lock 性能低下

解决办法很简单,就是要开始自旋的时候,放弃 CPU,进入 sleep 状态。然后把 thread id 放一个队列里面。当别的 thread 执行完成后,唤醒队列中的一个 thread。

image-20210511145454675

除此之外,spin lock 还有一个缺点:priority inversion 。假设两个 thread,分别为 T1 和 T2。T2 的 priority 大于 T1。然后一开始,T2先运行,因为它优先级高。然后因为某种 IO 操作,blocked。此时操作系统让 T1 开始运行,然后 T1 hold 一个 T2 将来要用的 lock。然后 T2 IO 操作完毕,开始执行,操作系统将 T1 sleep 了,然而此时 T1 的 lock 并没有释放,结果使得 T2 卡在那里,等着 T1 的 lock,然而 T1 已经 sleep,永远不会释放 lock。

Two-Phase Locks

spin lock 也不是一无是处,因为如果你知道某些锁很快就会被释放,推荐就使用 spin lock,这样性能更高,

Two-phase lock 就是一开始先自旋一会,然后如果还是得不到 lock,就会采用 second plan,睡觉。

Condition Variables

wait() thread 希望 sleep。signal() 通知唤醒。

image-20210512214802381

说明几点:

  • 为什么要用变量 done:当假设没有 done 变量时,child 线程直接开始执行(在 thr_join() 之前),并且执行了 thr_exit() ,当他尝试 signal 线程时,因为没有线程 sleep,所以直接跳过。而此时 thr_join() 开始执行,然后睡着了,然而永远不会有线程去 signal 它了。
  • 为什么要用 mutex 锁:假设没有了 mutex,此时先执行了 thr_join(),到 20 行,还没有开始 wait。此时 OS 调度子线程,直接执行完成了 thr_exit()。然后切换回 parent thread 执行后面的 wait,与上面一样,永远不会被唤醒了。

下面是基于 Java 的生产者消费者模型。

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
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Study {

private static Lock lock = new ReentrantLock();
static Condition empty = lock.newCondition();
static Condition fill = lock.newCondition();

private static int count = 0;
private static int buf = 0;

public static void main(String[] args) {
Thread p = new Thread(new Producer());
p.start();
for (int i=0; i<10; i++) {
new Thread(new Consumer()).start();
}

try {
Thread.sleep(5000);
} catch (InterruptedException e) {}
}

private static class Consumer implements Runnable {
@Override
public void run() {
for (int i=0; i<10; i++) {
lock.lock();
while (count == 0) {
try {
empty.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println(Thread.currentThread().getName() + ":" + buf);
count = 0;
fill.signal();
lock.unlock();
}
}
}

private static class Producer implements Runnable {
@Override
public void run() {
for (int i=0; i<100; i++) {
lock.lock();
while (count == 1) {
try {
fill.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
buf = i;
System.out.println("produce: " + buf);
count = 1;
empty.signal();
lock.unlock();
}
}
}
}

在上面的代码中我们要注意,一定要使用 while 循环来判断 count==0count ==1 这两个条件。比如 consumer 中,如果使用 if,count==0 进入后,睡眠了,然后被唤醒,就直接执行后面的语句了,而没有循环再次检查一遍 count 的值(因为有可能在你唤醒的过程中,这个 count 的值被其他线程消费了)。

在条件变量这块,用 while 肯定不会出错,用 if 反而有可能出错。

Semaphore

image-20210513120734444

信号量使用 condition variable 和 mutex 实现

image-20210513121524798

Event-based Concurrency

select, poll