OSTEP [并发] Chapt. 31 - 信号量

分类:Operating System, 发布于:2019-04-15 18:11:04, 更新于:2019-04-19 00:09:40。 评论

"Goto Statements Considered Harmful" - Edsger Dijkstra

信号量的定义

信号量(semaphore)是一个能够用两种方式操纵的整数。在POSIX标准中,这两种程序是sem_wait()sem_post()。使用信号量前必须要进行初始化,如

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

sem_init()的第三个参数表示初始值1;第二个参数为0表示这个信号量在同一个进程的所有线程之间共享。查看man page来获取信号量的更多用法以及第二个参数的其他取值。

信号量初始化后,就可以调用上面的两个操作来控制它了。两个函数的功能如下:

int sem_wait(sem_t &s) {
  // decrement the value of semaphore s by one
  // wait if value of semaphore s is negative
}

int sem_post(sem_t &s) {
  // increment the value of semaphore s by one
  // if there are one or more threads waiting, wake one
}

sem_wait()可能马上返回,或者会导致调用者暂停执行,等待下一个post调用。

sem_post()不会等待任何条件,直接增加信号量的值,如果有线程在等待,就选择一个唤醒。

当信号量的值为负数时,(绝对值)等于正在等待的线程的数量。

二元信号量

一个简单的二元信号量锁的实现方式如下:(假设信号量函数已经用原子性操作实现了)

sem_t m;
sem_init(&m, 0, 1); // 初始化信号量为1(书本原代码此处为问题)

sem_wait(&m);
// critical section here
sem_post(&m);

当线程0进入临界区时,信号量降为0;如果线程1企图进入临界区,信号量会降为-1,线程1进入睡眠状态。线程0退出临界区时,信号量自增并唤醒等待的线程1,最后线程1退出,信号量恢复为1。

由此,信号量可以当作锁来使用,而锁只有空闲、占用两种状态,因此这个信号量又被称为二元信号量(binary semaphore)。

信号量用于线程安排

信号量可用于等待其他进程,代码如下:

sem_t s;

void *child(void *arg) {
  // do something
  sem_post(&s); // signal here: child is done
  return NULL;
}

int main(int argc, char *argv[]) {
  sem_init(&s, 0, 0); // 初始值为0,原文为问题
  // do something
  pthread_t c;
  pthread_create(&c, NULL, child, NULL);
  sem_wait(&s);
  // do something
  return 0;
}

对上面的代码分析分为两种情况:

  • 父进程继续执行,调用sem_wait(),信号量变为-1并进入睡眠;此时子进程开始执行。子进程执行结束后唤醒父进程,父进程继续执行。
  • 子进程直接执行,结束后信号量变为1。之后父进程继续执行,将信号量自减为0,无等待过程。

生产者/消费者问题

第一种尝试使用信号量解决此问题的代码使用了两个信号量:emptyfull,线程通过这两个信号量来指示缓冲区为空或为满。

生产者首先等待缓冲区为空,再往里面放商品;而消费者首先等待缓冲区满,然后再消费商品。首先假设缓冲区只能放1个商品,即MAX = 1。

消费者消费时,首先等待full信号,然后消费一个商品,将empty减为-1,最后进入睡眠状态等待full信号,符合要求。

生产者生产时,先等待empty信号,开始生产,先将empty修改为0,然后生产一个商品,最后修改full的值为0,唤醒消费者。

此时会出现两种情况:如果生产者继续执行,就会循环并执行P1行的代码,等待empty信号并进入睡眠。否则,消费者先开始执行,发现此时缓冲区已满,消费商品。两种情况的行为都符合预期。

但如果缓冲区大小大于1(比方说10),且有多个生产者、消费者,就会出现竞争。(书中提示:注意put()get()的代码)两个生产者$P_a$$P_b$几乎同时调用了put(),那么就有机会这两个线程往相同的内存写入了值,导致最后只生产了一个商品。(详细的解释:$P_a$知道没有商品,所以它要往0号位填充商品,但此时被$P_b$打断,$P_b$也往0号位生产商品,最后就两个生产者只生产了一个商品。)

解决方法:添加互斥锁。图31-11给生产、消费上了互斥锁,但却导致了新的问题:死锁。如果消费者$C$上互斥锁后发现没有商品,它就会等待full信号,但此时等待并没有解开互斥锁。随后生产者$P$被唤醒,永远无法获得互斥锁,$C$也永远无法获得full信号。

解决方案:先等信号,再上锁。

理解互斥锁、信号量以及如何解决死锁的重要性(书中原文):

Understand it now; use it later. You will thank us for years to come. Or at least, you will thank us when the same question is asked on the final exam.

读写锁(Reader-Writer Locks)

我们希望能有一种更加灵活的上锁方式:不同的数据操作需要不同的锁。例如,可以插入和读取的链表在读取时只需要保证没有插入操作即可,这样就可以同时进行多个读操作。这种锁被称为reader-write lock

当一个线程想要获得第一把读锁时,它同时会获取写锁,直到它结束后才会释放写锁。这样,如果有线程想要获得写锁,就必须等待所有的读线程退出临界区。

TIP: Simple is Better

Although something like reader/writer locks sounds cool, they are complex, and complex can mean slow. Thus, always try the simple and dumb approach first.

读写锁在公平性上存在巨大的问题:读线程能够轻松的阻塞写线程。在效率方面,读写锁通常带来巨大额外开销,反而使得性能开 倒 车不如普通互斥锁。

哲 学 家吃饭问题

Ah ♂ That's Gooooooood

Indeed, you might be asked about it on some interview, and you'd really hate your OS professor if you miss that question and don't get the job. Conversely, if you get the job, please feel free to send your OS professor a nice note, or some stock options.

问题的基本内容:5个哲学家围绕桌子而坐,相邻哲学家之间有一把叉子。当哲学家思考时,他不需要叉子;但当他们吃饭时,需要左手边和右手边的两把叉子。叉子的竞争和可能出现的同步问题使得吃饭问题在并发编程领域中有研究意义。

对于每个哲学家,他的行为构成循环:

while (1) {
  think();
  getforks();
  eat();
  putforks();
}

这个问题的关键难点在于如何保证getforks()putforks()不出现死锁、没有哲学家吃不到饭饿死,并且还要保证高并发性(尽可能让更多的哲学家同时吃饭)。

在解决问题前,需要定义两个简单的辅助函数:

int left(int p)  { return p; }
int right(int p) { return (p + 1) % 5; }

同时,对每个叉子有一个信号量:sem_t forks[5]

上图尝试中,每个信号量的初始值均为1。直观上的解决方案为:先拿左边的叉子,再拿右边的叉子;吃完之后再把叉子放回去。

但这个简单的方案是错误的,因为会造成死锁:如果每个哲学家都同时拿左手的叉子,而没人先拿到右手的叉子,那么没有人就可以拿到右手边的叉子了。

解决方案:打破依赖(Dijkstra的解决方法)。假设最高编号的哲学家(4号)先拿右手边的叉子,其他人都先拿左手边的叉子,即

void getforks() {
  if (p == 4) {
    sem_wait(forks[right(p)]);
    sem_wait(forks[left(p)]);
  } else {
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
  }
}

这样就没有可能哲学家相互等待造成死锁了。类似的问题包括抽烟者问题、睡觉的理发师问题等。

如何实现信号量

一把锁、一个条件变量,一个bug改一天

注意此处的(山寨)信号量的值不会低于0,实现更简单,也和Linux实现方式一致,但并非Dijkstra所定义的信号量。

TIP: Be Careful With Generalization

"Don't generalize; generalizations are generally wrong." - Lampson

评论