前言


我的上一篇博客的案例中,请求锁的线程如果发现锁已经被其他线程占用,它是通过自旋的方式来等待的,也就是不断地尝试直到成功。本篇就讨论一下另一种方式,那就是挂起以等待唤醒。

注:相关代码都来自《Operating System: Three Easy Pieces》这本书。

自旋哪里不好?

先说明一下,自旋也有它的好处,不过这里先不讲,我们先讲它可能存在哪些问题。


我们考虑一个极端的场景,某个电脑只有一个CPU,这时候有2个线程竞争锁,线程A获得了锁,进入临界区,开始执行临界区的代码(由于只有一个CPU,线程A在执行的时候,线程B只能在就绪队列中等待)。结果线程A还没执行完临界区的代码,时间片就用完了,于是发生上下文切换,线程A被换了出去,现在开始执行线程B,线程B就开始尝试获取锁。



这时候尴尬的事情就来了,拥有锁的线程没在运行,也就不能释放锁。而占据CPU的线程由于获取不到锁,就只能自旋直到用完它的时间片。

这还只是2个线程的情况,如果等待的线程有100多个呢,那在轮询调度器的场景下,线程A是不是要等到这100多个线程全部空转完才能运行,这浪费可就大了!

用yield()让出CPU怎么样?


 yield()方法是把调用线程之间切出,放回就绪队列。这个方法与前面的不同就在于,当线程B恢复执行的时候,它只会尝试一次,如果失败,则直接退出,而不会用完它的整个时间片。也就是说被调度的线程最多只会尝试一次。这样虽然会比自旋好一点。但是开销还是不小,对于100多个等待线程的情况,每个都要进行一遍run-and-yield操作。上下文切换的开销也是不容小觑的。

直接挂起,等待唤醒

前面有之所以还会有过多的上下文切换,就是因为等待的线程还是会不断尝试,只是没之前那么频繁罢了。

那不让这些等待线程执行不就好了?

可以啊,只需要将这些线程移出就绪队列,它们就不会被OS调度,也就不会被运行。

挂起是可以了,还得想想谁来唤醒,怎么唤醒?


唤醒操作肯定由释放锁的线程处理。另一方面,我们把线程挂起的时候,肯定得用一个数据结构把这个线程的信息记录下来,不然要唤醒的时候都不知道该唤醒谁。而这个数据结构肯定得跟锁对象关联起来,这样释放锁的线程也就知道该从哪里拿这些数据。
typedef struct __lock_t { int flag; //标识,锁是否被占用 int guard; //守护字段 queue_t *q;
//等待队列,用于存储等待的线程信息 } lock_t; void lock_init(lock_t *m) { m->flag = 0; m->guard =
0; queue_init(m->q); } void lock(lock_t *m) { while(TestAndSet(&m->guard, 1) ==
1) ;//通过自旋获得guard if (m->flag == 0) { m->flag = 1; m->guard = 0; } else {
queue_add(m->q, gettid()); m->guard = 0; //注意:在park()之前调用 park(); //
park()调用之前,线程已经成功加入队列 } } void unlock(lock_t *m) { while(TestAndSet(&m->guard,
1) == 1) ;//通过自旋获取guard if(queue_empty(m->q)) //如果没有等待的线程,则将锁标识为“空闲” m->flag = 0
;else unpark(queue_remove(m->q)); //唤醒一个等待线程,此时锁标识仍为“已占用” m->guard = 0; }
park()与unpark(threadID)

park()与unpark(threadID)是Solaris系统提供的原语,用于挂起和恢复线程。其他系统一般也会提供,但是细节可能有所不同。

park()  => 将当前调用线程挂起

uppark(threadID)  => 根据线程ID唤醒指定线程。

guard字段的用途

我在看这段代码的时候有一个疑问,那就是这个queue_t是在哪里定义的,它到底是什么样子?这个队列内部是不是要做同步操作?不同步的话,
多个线程同时访问,队列的数据结构就可能被破坏。实际上,仔细看代码就会发现,在操作队列的时候,线程需要先获得guard。也就是说,同一时刻只能有一个线程能够访问队列。所以这个队列是安全的,它自身并不需要提供同步。所以,书上才没有贴出源码。随便一个队列实现就可以了。

实际上guard字段用于控制多线程对lock对象的访问,同一时刻只能有一个线程能够对lock对象的其他信息(除guard字段外)进行修改。

上述代码存在的问题


由代码可知,当guard被释放的时候,其他线程就能访问Lock对象了。那就可能出现一种情况,即释放了guard,但还没来得及执行park()就发生了上下文切换。这个时候存在什么问题呢,我们来看下图:



由于上下文切换的缘故,Thread A 已经加入了等待队列,但并没有执行挂起操作。结果占有锁的线程释放的时候,刚好从队列中取出Thread A,Thread
A被唤醒,放入就绪队列,等到下次调度的时候执行。Thread A恢复,继续向下执行,调用park()方法。结果就是Thead A被永久地挂起!!!。
因为这个时候它已经从等待队列中移除了,谁也不知道它被挂起了。

OS提供的解决方法

OS提供一个setpark()函数来标识某个线程将要执行park()操作。如果在这个线程(比如Thread
A)执行park()操作之前,其他线程(如Thread B)对其执行了unpark(threadID)方法,则该线程(Thread
A)在执行park()会立即返回。更改如下:
... queue_add(m->q, gettid()); setpark(); m->guard=0; park(); ...

PS:实际上这个setpark()函数应该也只是在底层的Thread对象中设置了一个flag,park()函数内会查看一下这个flag。只不过这个底层的Thread对象我们访问不到罢了。