手搓OS-day7

现代处理器互斥实现

互斥（mutual exclusion）就不必多说了，简单点说就是不能同时访问。

实现互斥的基本假设：

  • 不能同时读写内存
  • 指令为不可打断的原子指令
  • 函数通过内存屏障顺序不可优化

自旋锁（Spinlock）

自旋可以认为是一种循环等待的状态，即为忙等，维基百科是这么说的：

In software engineering, a spinlock is a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available.

我们在之前学习操作系统的时候，貌似记得忙等并不是一种很好的策略，忙等会让CPU无效工作，导致CPU利用率降低。

然而，我们之前学习时并没有提到其优点，因为一直是忙等（即运行态）所以线程不会进入阻塞态，也就没有了切换的上下文开销。

OK，现在基本的概念问题解决了，下面就要开始深入实现了，结合之前的互斥实现的基本假设，开始阅读代码：

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
#include "thread.h"

#define N 100000000
#define M 10

long sum = 0;
// 总之函数实现了一个原子的交换函数
int xchg(int volatile *ptr, int newval) {
  int result;
  // 内联汇编
  asm volatile(
    "lock xchgl %0, %1"  // lock前缀确保原子性
    : "+m"(*ptr),        // 输出操作数，ptr处的内存又是输入又是输出
    "=a"(result)         // 输出操作数：result接收内存位置上的前值
    : "1"(newval)        // 输入操作数：newval是要交换的目标值
    : "memory"           // 制约操作数：表示内联汇编代码会修改内存
  );
  return result;
}

int locked = 0;

void lock() {
  while (xchg(&locked, 1)) ;
}

void unlock() {
  xchg(&locked, 0);
}

貌似这个实现也没啥（雾），当然这个东西还可以更加深入，比如如何分配等待序列，让其更公平。参考下面的拓展阅读。

无锁算法

无锁编程，即不使用锁的情

况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步。

Compare and exchange【CAS】(" test and set ")

(lock) cmpxchg SRC, DEST

1
2
3
4
5
6
7
TEMP = DEST
if accumulator == TEMP:
    ZF = 1
    DEST = SRC
else:
    ZF = 0
    accumulator = TEMP

上面是一个CAS的指令已经实现的一种伪代码（类似），比起自旋锁，CAS多了一个比较过程。

使用场景

自旋锁：临界区能够很快速的使用结束，操作系统内核的并发数据结构 (短临界区)。

互斥锁：通过系统调用获取，实现线程+长临界区互斥。

参考链接

【今日学习】7. 并发控制：互斥 (jyywiki.cn)

面试必备之深入理解自旋锁-腾讯云开发者社区-腾讯云 (tencent.com)

Spinlock - Wikipedia

CAS无锁算法 - 宇枫 - 博客园 (cnblogs.com)

拓展阅读

万字长文丨深入理解Linux自旋锁 - 知乎 (zhihu.com)