生产者消费者问题
缓冲区不满生产者才能放，缓冲区不空消费者才能拿
#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
while(TRUE) {
int item = produce_item();
down(&empty); // empty--和后面full++，一个意思两个变量
down(&mutex); // 保护临界区的mutex要写在里面
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() {
while(TRUE) {
down(&full);
down(&mutex);
int item = remove_item();
consume_item(item);
up(&mutex);
up(&empty);
}
}
读者写者问题
可以多个读，但不能同时读-写、写-写
typedef int semaphore;
semaphore data_mutex = 1; // 对写数据操作加锁
semaphore count_mutex = 1; // 对count变量加锁
int count = 0; // 读者计数
void reader() {
while(TRUE) {
down(&count_mutex);
count++;
if(count == 1) down(&data_mutex); // 第一个读者要对写数据操作加锁
up(&count_mutex);
read();
down(&count_mutex);
count--;
if(count == 0) up(&data_mutex);
up(&count_mutex);
}
}
void writer() {
while(TRUE) {
down(&data_mutex);
write();
up(&data_mutex);
}
}
哲学家就餐问题
方法一：打破"占有和等待"，必须同时拿起两根筷子。
#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N // 右邻居
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N]; // 跟踪每个哲学家的状态
semaphore mutex = 1; // 对state[]加锁
semaphore s[N]; // 每个哲学家一个信号量
void philosopher(int i) {
while(TRUE) {
think();
take_two(i);
eat();
put_two(i);
}
}
void take_two(int i) {
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void put_two(i) {
down(&mutex);
state[i] = THINKING;
test(LEFT); // 尝试唤醒邻居
test(RIGHT);
up(&mutex);
}
void test(i) { // 尝试拿起两把筷子
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
up(&s[i]);
}
}
方法二：打破“环路等待”，所有筷子从0~N-1编号，必须先拿小编号再拿大编号。这样所有哲学家先左手后右手，但某位哲学家先右手后左手。见ctci p451。
死锁检测
用锁顺序有向图检测无环
不会死锁的LockFactory类：factory中存有无环的用锁顺序有向图G。进程向factory声明一个用锁顺序，factory尝试把用锁顺序对应的边加到G上，然后在新增用锁上dfs检查是否有环（在dfs遍历时访问到VISITING状态的节点）。若有环则删除该用锁顺序对应的边；没环就允许这个用锁顺序，并在个map中记下进程id=>用锁顺序。
见ctci p453
银行家算法
已知各进程已占有多少各资源、还需要多少各资源，总共还剩多少各资源。找出还需各资源数<剩余各资源数的进程，标记为完成，释放该进程占有的资源到剩余资源中。如此继续，最后若能标记完所有进程，则无死锁。