因为某人被信号量整抑郁了一下午，这里就放一些比较容易考的板子以及一些例题+个人解答：

（全是手写的，只是拿AI查了一下对错但AI真的在这种问题上面特别难用……经常会胡乱回答……）

模板

生产者-消费者问题（有界缓冲区问题）

Semaphore:
sem_produce=N
sem_consume=0
mutex=1

Producer:
while(1) {
    P(sem_produce);
    P(mutex);
    produce();
    V(mutex);
    V(sem_consume);
}

Consumer:
while(1) {
    P(sem_consume);
    P(mutex);
    consume();
    V(mutex);
    V(sem_produce);
}

理发师（睡眠助教）问题

Semaphore:
serve=0
rest=0
mutex=1

Var:
int count = N;

TA:
while(1) {
    P(rest);
    //Call in a student
    P(mutex);
    count++;
    V(mutex);
    V(serve); //Activate the student
    //Serve the student
}

Student:
P(mutex);
if(count > 0) {
    count--;
    V(mutex);
    V(rest); //Notify the TA
    P(serve); //Wait for the TA to serve
    //Get Served
} else {
    V(mutex);
    //Leave
}

读者-写者问题

读者优先

Semaphore:
mutexReadCount = 1
r = 1

Var:
int readCount = 0

Writer:
P(r);
//WRITING...
V(r);

Reader:
P(mutexReadCount);
readCount++;
if(readCount == 1) {
    P(r);
}
V(mutexReadCount);
//READING...
P(mutexReadCount);
readCount--;
if(readCount == 0) {    
    V(r);
}
V(mutexReadCount);

公平读写

增加了一个queue

Semaphore:
mutexReadCount = 1
r = 1
queue = 1

Var:
int readCount = 0

Writer:
P(queue);
P(r);
//WRITING...
V(r);
V(queue);

Reader:
P(queue);
P(mutexReadCount);
readCount++;
if(readCount == 1) {
    P(r);
}
V(mutexReadCount);
V(queue);
//READING...
P(mutexReadCount);
readCount--;
if(readCount == 0) {    
    V(r);
}
V(mutexReadCount);

写者优先

公平读写者为基础，写者queue改成第一个阻塞读者，读者queue中间加P(r)V(r)

Semaphore:
mutexReadCount = 1
mutexWriteCount = 1
r = 1
w = 1
queue = 1

Var:
int readCount = 0
int writeCount = 0

Writer:
P(mutexWriteCount);
writeCount++;
if(writeCount == 1) {
    P(r);
}
V(mutexWriteCount);
P(w);
//WRITING...
V(w);
P(mutexWriteCount);
writeCount--;
if(writeCount == 0) {
    V(r);
}
V(mutexWriteCount);

Reader:
P(queue);
P(r);
P(mutexReadCount);
readCount++;
if(readCount == 1) {
    P(w);
}
V(mutexReadCount);
V(r);
V(queue);
//READING...
P(mutexReadCount);
readCount--;
if(readCount == 0) {    
    V(w);
}
V(mutexReadCount);

独木桥问题（读者-写者变形）

虽然是读者-写者变形，但是第一次做应该会比较难有思路

Semaphore:
bridge = 1
mutexAB = 1
mutexBA = 1
count = N

Var:
ABCount = 0
BACount = 0

Car:
A->B:
P(mutexAB);
ABCount++;
if(ABCount == 1) {
    P(bridge);
}
V(mutexAB);
P(count);
//PASS THE BRIDGE...
V(count);
P(mutexAB);
ABCount--;
if(ABCount == 0) {
    V(bridge);
}
V(mutexAB);

B->A:
P(mutexBA);
BACount++;
if(BACount == 1) {
    P(bridge);
}
V(mutexBA);
P(count);
//PASS THE BRIDGE...
V(count);
P(mutexBA);
BACount--;
if(BACount == 0) {
    V(bridge);
}
V(mutexBA);

哲学家问题

无死锁预防版本

Semaphore:
chopstic[5] = {1,1,1,1,1}

Phi:
while(1) {
    //THINKING...
    P(chopstic[i]);
    P(chopstic[(i+1)%5]);
    //EATING...
    V(chopstic[i]);
    V(chopstic[(i+1)%5]);
}

死锁预防版本

Semaphore:
chopstic[5] = {1,1,1,1,1}
count = 4

Phi:
while(1) {
    //THINKING...
    P(count); //最多只允许4个哲学家同时拿左手边的筷子
    P(chopstic[i]);
    P(chopstic[(i+1)%5]);
    //EATING...
    V(chopstic[i]);
    V(count);
    V(chopstic[(i+1)%5]);
}

例题

例1（生产者-消费者）

某寺庙，有小和尚、老和尚若干。有一水缸，由小和尚提水入缸，老和尚从缸中取水饮用。水缸可容纳10桶水，水取自同一水井中，水井径窄，每次只能容一个水桶取水。水桶总数为3个，每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的算法描述。

Semaphore:
water = 0 //通知消费者信号量
bucket = 3
well = 1
p_pot = 10 //通知生产者信号量
mutex_pot = 1

Put_Water:
    P(p_pot);
    //Get a bucket
    P(bucket);
    //Go to the well
    P(well);
    //Get water from the well
    V(well);
    //Go to the pot
    P(mutex_pot);
    //Pour water into the pot
    V(water);
    V(mutex_pot);
    //Return the bucket
    V(bucket);


Get_Water:
    P(water);
    P(bucket);
    P(mutex_pot);
    //Get water...
    V(p_pot);
    V(mutex_pot);
    V(bucket);
    //Done...

注意同步信号量一般在互斥信号量的外面。

例2（写者优先读者-写者）

某男⼦⾜球俱乐部，有教练、队员若⼲。每次⾜球训练开始之前，教练、球员都需要先进⼊更⾐室换⾐服，可惜俱乐部只有⼀个更⾐室。教练们脸⽪薄，⽆法接受和别⼈共⽤更⾐室。队员们脸⽪厚，可以和其他队员⼀起使⽤更⾐室。如果队员和教练都要使⽤更⾐室，则应该让教练优先。请使⽤ P、V 操作描述上述过程的互斥与同步，并说明所⽤信号量及初值的含义。

Semaphore:
w = 1
r = 1
mutex_coach = 1
mutex_member = 1
queue = 1

Var:
member_count=0
coach_count=0

Coach:
P(mutex_coach);
coach_count++;
if(coach_count==1) {
    P(r);
}
V(mutex_coach);
P(w);
//USE...
V(w);
P(mutex_coach);
coach_count--;
if(coach_count==0) {
    V(r);
}
V(mutex_coach);

Member:
P(queue);
P(r);
P(mutex_member);
member_count++;
if(member_count==1) {
    P(w);
}
V(mutex_member);
V(r);
V(queue);
//USE...
P(mutex_member);
member_count--;
if(member_count==0) {
    V(w);
}
V(mutex_member);

例3（独木桥简单变形）

假设一个录像厅有 0,1,2 三种不同的录像片可由观众选择放映。录像厅的放映规则为：

任何时刻最多只能放映一种录像片，正在放映的录像片是自动循环放映的。最后一个观众主动离开时结束当前录像片的放映。

选择当前正在放映录像片的观众可立即进入，允许同时有多位选择同一中录像片的观众同时观看，同时观看的观众数量不受限制。

等待观看其他录像片的观众按到达顺序排队，当一种新的录像片开始放映时，所有等待观看该录像片的观众可一次进入录像厅同时观看。

Semaphore:
r = 1
mutex_q1 = 1
mutex_q2 = 1
mutex_q3 = 1

Vars:
count_q1 = 0
count_q2 = 0
count_q3 = 0


Audience1:
P(mutex_q1);
count_q1++;
if(count_q1==1) {
    P(r);
}
V(mutex_q1);
//Watch the movie...
P(mutex_q1);
count_q1--;
if(count_q1==0) {
    V(r);
}
V(mutex_q1);

2,3同理
1对应影片0,2对应影片1,3对应影片2.

例4（独木桥PRO MAX）

源自某学院操作系统开卷的一年的考题……

（就是这题弄得道心破碎了）

个人解答，可能有不是很正确的地方，但真的是燃尽了之后的：

Semaphore:
road = 1
mutexAB = 1
queue = 1

Var:
ABCount = 0
status = FREE //取值为两个常量：FREE和ONE_WAY

Car (Assert AB): //BA对称，此处只对AB方向进行描述
P(queue);
if(status == FREE) {
    if(need_Park()) {
        status = ONE_WAY;
        V(queue);
        //后面变为单行道，后续进入临界区的线程都将进入ONE_WAY逻辑
        buy_groceries();
        P(queue); //排队准备恢复道路状态
        status = FREE;
    }
    V(queue);
    //因为后面的车发生什么和已经通过的车都无关，此处可直接释放queue然后直接正常通过
    leave();
}
else if(status == ONE_WAY) {
    if(need_Park()) {
        deny_signal(); //拒绝停车请求
    }
    V(queue);
    pass_AB();
}

func pass_AB: //单边桥问题模板
P(mutexAB);
ABCount++;
if (ABCount == 1) {
    P(road);
}
V(mutexAB);
pass();
P(mutexAB);
ABCount--;
if (ABCount == 0) {
    V(road);
}
V(mutexAB);

模板