Home

OSTEP笔记:锁

posted at 2019-07-01
最近在读一本书:Operating Systems: Three Easy Pieces (译:操作系统三个简单的部分??), aka OSTEP. 这本书是由威斯康星大学计算机系的几位教授编写的,书的全部内容都免费托管在官网上。

这本书从三个方面:虚拟化(Virtualization),并发(Concurrency)和存储(Persistence)介绍了操作系统原理,内容由浅入深,可以列入我个人的the books I wish I had read years ago清单。

截止到写这篇文章前,我还没有读完整本书,这篇文章主要内容集中在第二部分,即并发部分的,可以说这篇文章是笔记而非博客🤦。

并发为了解决的问题

计算机由人类设计,为人类服务。并发的出现是为了“榨干”机器的资源,充分利用计算机资源,由于CPU的虚拟化,即使在单核系统上也能使用多线程在I/O频繁场景下来提升应用性能,更不用说多核系统了。

并发带来的问题

举一个简单的例子(Ruby代码):

counter = 0
100.times.map do
  Thread.new do
    counter += 1
  end
end.each(&:join)

这段代码在单线程下运行没有任何问题,但是如果开多个线程运行上面的代码就会导致counter的值不是预期的10。

让我们来从操作系统和计算机硬件的角度审视counter += 1的问题出现在什么地方。
注:Ruby世界是先将代码转换为Ruby字节码然后由Ruby VM执行指令,以后写文章深究Ruby的VM。这里直接用书中用C写的例子。


counter += 1 这段代码最终翻译成汇编指令的结果大致如下:

100 mov 0x8049a1c, %eax
105 add $0x1, %eax
108 mov %eax, 0x8049a1c

翻译成可读的语言:

从内存地址0x8049a1c取值,放入eax寄存器(eat: extended accumulator register 扩展累加寄存器)
对eax寄存器的值加1
把值放回地址位0x8049a1c

寄存器是CPU内部元件,用来执行算数及逻辑运算

假设有两个线程同时运行,counter的初始值是50。以为CPU调度是不可控的,下面列出的是可能出现的执行顺序

线程一运行:

  1. 从0x8049a1c取值得到50,放入eax寄存器
  2. 50 + 1得到51,这时时发生了上下文切换,Program counter记录当前thread执行至sequence 2,即地址位105,OS保存当前运行状态(PC,寄存器)至线程一的TCB(thread control block),线程一暂停运行

线程二运行:

  1. 因为线程一在sequence 2时发生上下文切换,新值未写回地址,因此线程二从0x8049a1c取值得到的依然是50,放入eax寄存器
  2. 50 + 1得51,寄存器eax此时存放的值为51
  3. 将1写回地址0x8049a1c

此时上下文切换再次发生,OS根据线程一的TCB存储的寄存器和PC信息,继续运行此前暂停的线程一:

  1. PC记录线程一此前执行至sequence 2,并且eax寄存器存储的值为51
  2. 将51写回地址0x8049a1c

这就导致了counter加了两次1,但是结果是加了一次1的原因。

以上演示的过程即为最常见的多线程程序运行出现的问题(race condition, more specifically data race)。


DraggedImage.png 252 KB

多线程除了带来两个问题:共享数据和等待行为,上面的例子说的是共享数据的问题,等待行为则发生于某些业务场景,如需要等待I/O完成后进行某些行为。因此对于多线程问题的研究集中于,如何保证共享数据的原子性以及如何实现休眠/唤醒机制。

我们把访问共享资源的代码叫做critical section,为了保障原子性需要使用锁。

如何实现一个线程锁?
方案一(错误的方案):

typedef struct __lock_t {
  int flag;
} lock_t;

void init(lock_t * mutex) {
  // 0 -> lock is available, 1 -> held
  mutex->flag = 0;
}

void lock(lock_t * mutex) {
  while (mutex->flag == 1) // TEST the flag 
    ; // spin-wait (do nothing)

  mutex->flag = 1; // now SET it!
}

void unlock(lock_t * mutex) {
  mutex->flag = 0;
}


这个方案非常简单,通过flag变量用于区别某个线程锁是否已经获取了线程锁。第一个进入critical section的线程调用lock()lock()检查mutext的flag是否为1,如果不是1,则将flag设为1,表示当前线程持锁。执行完critical section部分代码后,调用unlock()将锁释放。如果另外的线程调用lock()时,前一个线程正在执行critial section部分代码,则当前线程会进入while循环等待前一个线程释放锁。

但是这个方案有两个问题:

  1. 如图,假设线程1在调用lock(),函数执行到while (mutex->flag == 1)时发生了上下文切换到线程2,线程2调用lock(),这是的flag依然是0,因此flag被设置为1,此时上下文切换至线程1,flag再次被设置为1。这里违背了互斥锁的原则。

DraggedImage-1.png 141 KB


2. 无限循环带来的性能问题

方案二(用test-and-set instruction实现自旋锁):

不借助硬件的支持,似乎很难实现锁的机制,于是操作系统设计人员开始试图解决从硬件上解决并发锁的问题。自1960年Burroughs B5000的诞生开始,这个问题得到了解决。其中最简单的机制叫做:test-and-set instruction,aka atomic exchange。下面的代码演示了test-and-set的基本思路:

int TestAndSet(int *old_ptr, int new) {
  int old = * old_ptr; // fetch old value at old_ptr
  *old_ptr = new; // store ’new’ into old_ptr
  return old; // return the old value
}

test-and-set指令做了如下操作:调用时传两个参数:旧值的指针和新值。返回旧值,同时更新旧值为新值。这个指令的关键点在于操作是保证原子性的。

使用test-and-set实现的自旋锁代码如下:

typedef struct __lock_t {
  int flag;
} lock_t;

void init(lock_t * lock) {
  // 0 indicates that lock is available, 1 that it is held
  lock->flag = 0;
}

void lock(lock_t * lock) {
  while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin-wait (do nothing) }

void unlock(lock_t * lock) {
  lock->flag = 0;
}


让我们先来思考一下,为什么test-and-set保证线程锁工作。

场景一:

想象当一个线程调用lock()同时当前没有其他线程持锁,此时,flag为0。当这个线程调用TestAndSet(flag, 1)时,返回旧值,即0。因此当前线程不会进入while循环,此时这个线程持锁。完成critical section部分代码的执行任务后,调用unlock()把flag重置为0。

场景二:

线程一已经持锁(flag值为1),如果线程二执行lock()lock()调用TestAndSet(flag, 1)TestAndSet()返回旧值,即1,并将flag设置为新值(仍为1),此时线程会进入while 循环,等待锁被释放。
当线程一调用unlock(),线程一释放锁,flag值被置为0。线程二在while循环中调用TestAndSet(flag, 1),函数返回旧值0,并设置flag为新值1,此时线程而持锁。

由此可见 test-and-set的确可以实现自旋锁。自旋锁(spin lock)的意思是为了持有锁,不断的通过循环直到获取锁。


需要注意的是,在单核系统上,需要支持抢占式调度器的配合才能让自旋锁工作(比如定时中断线程,上下文切换运行其他线程)。

评价自旋锁

OSTEP一书指出了三个评判锁的实现的标准:
  1. correctness:是否提供mutual exclusion(互斥)支持
  2. fairness: 线程竞争是否公平
  3. performance:性能

自旋锁提供了mutal exclusion(互斥)支持,因此我们说自旋锁至少是正确的锁的一种实现。
自旋锁自身无法保证公平,一个尝试获得锁的线程可能永远在等待中,上面提到在单核计算机上,需要OS调度器支持才能保证公平。
最后一个评判的标准是性能,在单核计算机上,OS线程调度可能非常繁忙,但是自旋锁非常适合在多核计算机,前提是线程数大约等于CPU数量。