1 信号量

Q: What’s semaphore？
A: Semaphore is a single primitive for all things related to synchronization, and one can use semaphores as both locks and condition variables. To be specific, a semaphore is an boject with an integer value that we can manipulate with two routines (in POSIX standard, these routines are sem_wait() and sem_post())

6LeQdr

互斥锁是信号量的特例。

Q: How to use semaphore to solve producer-consumer problem?
A:

Consider what the unit source (like a ball in the above picture) stands for?

Producer/consumer = put a ball from one bag to another bag.

void producer() {
    P(&producer_bag);
    print("(");
    V(&consumer_bag);
}

void consumer() {
    P(&consumer_bag);
    print(")");
    V(&producer_bag);
}

Q: It seems that we can write elegant codes for synchronization problems with semaphore. But in practice, in which situation we may prefer semaphore to other tools like lock and condition variable.
A:
vqJMEo
s5reTm
For below picture, we use one semaphore, and order is not considered, but we can get the finished time for each thread.
G8l0ny
But for this picture, we use several semaphore, and we can control the order.
luvdeg

TODO: search more infomation.
Q: 理解信号量和条件变量的关系。
A: semaphore可以被视为locks的generalization，但细究起来并不是conditional variable的generalization. condition variable才刻画了同步的本质.

2 哲学家吃饭问题

2.1 问题描述

哲学家吃饭是一个很有代表性的同步问题, 其描述如下: 有5个哲学家围绕一个圆桌吃饭, 每个人左右手边都有一个叉子(如下图所示), 只有同时拿到左右手的叉子时才能进食。请问应该如何设计才能保证每个哲学家都可以正常吃到食物。
GFSE9F

2.2 使用条件变量的解法

遇上任何同步问题，都可以考虑用条件变量去解决，只要能够正确地把条件表达出来。下面这个方法就是用条件变量来处理

#define CAN_EAT (avail[lhs] && avil[rhs])
/* get_forks() implementaiton */
mutex_lock(&mutex);
while (!CAN_EAT)
    // 如果不满足条件, 在sleep前会释放锁
    // 当接受到signal, 在被唤醒(wake up)前会重新获得锁
    cond_wait(&cv, &mutex);
avail[lhs] = avail[rhs] = false;
mutex_unlock(&mutex);
// ... eat for some while ...

/* put_forks() implementation */
mutex_lock(&mutex);
avail[lhs] = avail[rhs] = true;
cond_broadcast(&cv);
mutex_unlock(&mutex);

但是条件变量会带来一个问题, 它会broadcast，但是线程多的时候会带来性能问题.

2.3 使用信号量的解法

一种简单但是不正确的方法: 将信号量当互斥锁来解决。这种方法会产生死锁（所有人都拿起了左边的叉子时）。

/* get_forks() implementaiton */
void get_forks(int p) {
    // left[p]表示第p个哲学家左边叉子的编号
    // ref: Three easy pieces
    sem_wait(&forks[left[p]]);
    sem_wait(&forks[right[p]]);
}

/* put_forks() implementation */
void put_forks(int p) {
    sem_post(&forks[left[p]]);
    sem_post(&forks[right[p]]);
}