一、生产者–消费者问题
生产着消费者问题即多个生产者和消费者对n个缓冲区的使用。
若不考虑互斥、同步问题会导致counter计数错误。
- 无论生产者、消费者使用缓冲池时应保证互斥使用（互斥信号量mutex ）
- 生产者和消费者间交叉有序：
①有序的控制最根源在产品数量上。
②设置两个信号量：分别针对生产者、消费者设置不同的信号量，empty和full分别表示缓冲池中空缓冲池和满缓冲池（即产品）的数量。
- 利用记录型信号量解决生产者–消费者问题
//mutex: 生产者间，消费者间互斥使用缓冲区的互斥信号量
//empty: 缓冲区的空闲容量
//full: 缓冲区的已占容量
buffer: array[0, ..., n-1] of item;
in, out: integer := 0, 0;
var mutex, empty, full: semaphore := 1, n, 0;
producer: //生产者
begin
repeat
...
produce an item in nextp; //生产一个产品放入nextp
...
//进入区
wait(empty);
wait(mutex);
//临界区
buffer(in) := nextp;
in := (in+1) mod n;
//退出区
signal(mutex);
signal(full);
until false;
end
consumer: //消费者
begin
repeat
//进入区
wait(full);
wait(mutex);
//临界区
mextc := buffer(out);
out := (out+1) mod n;
//退出区
signal(mutex);
signal(empty);
//剩余区
consume the item in nexc; //消费nextc中的产品
until false;
end
注意：
1)每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对出现。
2)控制顺序的资源信号量empty和full的wait和signal操作，需要成对出现在不同的程序中。
3)在每个程序中的多个wait操作顺序不颠倒。应先申请资源信号量(wait操作)，后申请互斥信号量(wait操作)，否则可能引起进程死锁。
- 利用AND信号量解决生产者–消费者问题
//mutex: 生产者间，消费者间互斥使用缓冲区的互斥信号量
//empty: 缓冲区的空闲容量
//full: 缓冲区的已占容量
buffer: array[0, ..., n-1] of item;
in, out: integer := 0, 0;
var mutex, empty, full: semaphore := 1, n, 0;
producer: //生产者
begin
repeat
...
produce an item in nextp; //生产一个产品放入nextp
...
//进入区
Swait(empty, mutex); //不必考虑信号量先后问题
//临界区
buffer(in) := nextp;
in := (in+1) mod n;
//退出区
Ssignal(mutex, full);
until false;
end
consumer: //消费者
begin
repeat
//进入区
Swait(full, mutex); //不必考虑信号量先后问题
//临界区
mextc := buffer(out);
out := (out+1) mod n;
//退出区
Ssignal(mutex, empty);
//剩余区
consume the item in nexc; //消费nextc中的产品
until false;
end
二、哲学家进餐问题
五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五支筷子，他们的生方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。
可见：
相邻两位不能同时进餐；最多只能有两人同时进餐。
- 利用记录型信号量解决哲学家时餐问题
放在桌子的筷子是临界资源，在一段时间内只允许一个哲学家使用。为实现对筷子的互斥使用，用一个信号量表示一只筷子，五个信号量构成信号量数组。
var chopstick: array[0, …, 4] of semaphore := 1
所有信号量均被初始化为1。
Var chopstick: array[0, ..., 4] of semaphore := 1
//第i位哲学家的活动可描述为：
repeat
//进入区
wait(chopstick[i]);
wait(chopstick[(i+1) mod 5]);
//临界区
...
eat;
...
//退出区
signal(chopstick[i]);
signal(chopstick[(i+1) mod 5]);
//剩余区
...
think;
until false;
以上算法虽能保证相邻两位不会同时进餐，但可能引起就餐死锁问题。
例如五拉哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0，都将因无筷子可拿而无限等待。
解决方法：
①最多同时允许4位哲学家拿左边筷子（能够保证至少一位哲学家能够进餐）
Var chopstick: array[0, ..., 4] of semaphore := 1;
var count: semaphore := 4; //资源信号量
repeat
//进入区
wait(count);
wait(chopstick[i]);
wait(chopstick[(i+1) mod 5]);
//临界区
...
eat;
...
//退出区
signal(chopstick[i]);
signal(chopstick[(i+1) mod 5]);
signal(count);
//剩余区
...
think;
until false;
②要求每个哲学家先获得两个临界资源（筷子）后方能进餐，否则释放已拿到的筷子
本质上是AND信号量同步问题。
var chopstick: array[0, ..., 4] of semaphore := (1, 1, 1, 1, 1); //表示chopstick[i]可用
philosopher i;
repeat
think;
//进入区
Swait(chopstick[(i+1) mod 5], chopstick[i]);
//临界区
eat;
//退出区
Ssignal(chopstick[(i+1) mod 5], chopstick[i]);
until false;
③奇数号哲学家先拿左边筷子，再拿右边筷子；偶数号哲学家先拿右边筷子，再拿左边筷子
var chopstick: array[0, ..., 4] of semaphore := 1;
var i: integer;
repeat
//进入区
if i mod 2=1 then
begin
wait(chopstick[i]); //先拿左边筷子
wait(chopstick[(i+1) mod 5]); //再拿右边筷子
end
else
begin
wait(chopstick[(i+1) mod 5]); //先拿右边筷子
wait(chopstick[i]); //再拿左边筷子
end
end
//临界区
eat;
//退出区
signal(chopstick[i]);
signal(chopstick[(i+1) mod 5]);
//剩余区
...
think;
until false;
程序代码参考：
三、读者–写者问题
- 一个数据文件或记录可被多个进程共享。
- 允许多个进程同进读一个共享对象，但Writer进程和其他Reader进程或Writer进程不允许同时访问共享对象。
- 存在互斥关系：读–读共享，写–写互斥，写–读互斥。
- 利用记录型信号量解决读者–写者问题（读者优先）
//Wmutex：读-写互斥；写-写互斥
//Rmutex：读间访问Readcount互斥
//Readcount：记录记者进程数，表示正在读的进程数目。
var wmutex, rmutex: semaphore := 1, 1;
Readcount: integer := 0;
Writer: //写进程
repeat
wait(wnutex);
写;
signal(wnutex);
until false;
end
Reader: //读进程
repeat
//进入区
wait(rmutex); //子进入区
if Readcount=0 then wait(wmutex);
Readcount := Readcount + 1; //子临界区
signal(rmutex); //子退出区
//临界区
...
读;
...
//退出区
wait(rmutex);
Readcount := Readcount - 1;
if Readcount=0 then signal(wmutex);
signal(rmutex);
until false;
end
理解：由于只有一个Reader进程在读，便不允许Writer进程写。所以仅当Readcount=0（即无Reader进程在读）时，Reader才需要执行Wait(wmutex)操作。若Wait(wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount-1=0时，才需要执行signal(wmutex)操作，以便让Writer进程写。
- ==》写者优先 方式
//Wmutex：读-写互斥；写-写互斥
//Rmutex：读间访问Readcount互斥
//s：读-写起作用
//Readcount：记录记者进程数，表示正在读的进程数目。
var wmutex, rmutex,s : semaphore := 1, 1,1;
Readcount: integer := 0;
Writer: //写进程
repeat
if writecount=0 then wait(s);
writecount:=writecount+1
wait(wmutex);
写；
signal(wmutex);
writecount:=writecount-1
if writecount=0 then signal(s);
until false;
end
Reader: //读进程
repeat
//进入区
wait(rmutex); //子进入区
wait(s);
if Readcount=0 then wait(wmutex);
Readcount := Readcount + 1; //子临界区
signal(s);
signal(rmutex); //子退出区
//临界区
...
读;
...
//退出区
wait(rmutex);
Readcount := Readcount - 1;
if Readcount=0 then signal(wmutex);
signal(rmutex);
until false;
end
四、黑白棋子问题
两个人下棋，一方执黑棋，一方执白棋。要求双方轮流下子。
semaphore
bfg=1; //黑色棋子互斥量
wfg=0; //白色棋子互斥量
m=1； //黑白互斥量
boolean fg=FALSE;
void main() {
black();
white();
}
void black()
{
wait(m);
if (!fg)
{ bfg=1; wfg=0; fg=TURE；}
signal(m);
while(1)
{
wait(bfg);
if whereput()
{ put a black qizi;
signal(wfg); }
else
{ signal(wfg); break; }
}
}
void white()
{
wait(m);
if (!fg)
{ bfg=0; wfg=1; fg=TURE；}
signal(m);
while(1)
{
wait(wfg);
put a white qizi;
signal(bfg);
}
}
五、练习题
- 多个生产者和消费者，共享一个能存放100个产品的环形缓冲区（初始为空）。若缓冲区未满生产者可放入一个产品，否则等待。要求每个消费者连续取10件产品才能让其他消费者取。请用信号量机制写伪代码实现进程的互斥和同步实现，要求说明所用信号量含义和初值。
semaphore
mutex=1; //生产者和消费者之间互斥
cmutex=1; //消费者和消费者之间互斥
empty=100; //判断环形区域是否为空
full=0;
int in=0,out=0,n=100;
item buffer[n];
void main() {
Producer();
Consumer();
}
void Producer() { //生产者代码和经典问题相比并无变化
do {
producer an item in
nextp;
...
wait(empty);
wait(mutex);
buffer[in]=nextp;
in = (in+1)%n;
signal(mutex);
signal(full);
}while(true);
}
void Consumer() {
do {
wait(cmutex); //消费者和消费者之间互斥
for(int i=0;i<10;i++) { //一个消费者循环执行10次
wait(full);
wait(mutex);
nextc=buffer[out];
out = (out+1)%n;
signal(mutex);
sigal(empty);
consumer the item in nextc;
...
}
signal(cmutex); //释放cmutex，下一个消费者可进来
}while(true);
}
- 两个搬运工人向卡车中装纯净水，每车最多20箱。卡车装满即开走，需装10辆车。给出简单的同步分析及算法，写明信号量的含义和初值。（信号量和普通变量结合使用）
semaphore
water=0;
mutex=1; //抢车位，10辆车互斥
wmutex=1; //工人与工人互斥
go=0;
int count; //计数
void main() {
for(int i=0;i<10;i++)
car();
worker();
}
//控制车
void car() {
while(1) {
wait(mutex); //10辆车互斥
车进入装水位;
for(int i=0;i<20;i++)
signal(water); //一辆车释放20箱水
wait(go); //等待着车装满20箱水
车走;
signal(mutex); //唤醒下一辆车
}
}
//控制工人
void worker() {
while(1) {
wait(water);
装水;
wait(wmutex); //两个工人对in计数的互斥
count++;
if(count==20) {
count=0;
signal(go); //20箱水装满，给车信号
}
signal(wmutex); //一个工人对in+1完成之后释放资源
}
}
- 设有一自助餐厅，可容纳10名顾客就餐，餐厅满时顾客需在门外排队等候；顾客若能进入则自取食物后到款台付款；收款员负责在收款台等待顾客付款，付款完毕顾客自行就餐后离开。分析该问题中的同步关系，试写出顾客进程和收款员进程信号量机制下的同步算法，注意写明信号量的初值和作用
【分析】顾客存在争抢进店的竞争关系，设置一个资源信号量r，初值为10；收款员与顾客间存在双向有序合作关系，收款员需等待顾客付款，顾客需等待收款员确认付款完毕，需设置两个同步信号量money，ok，初值均为0.
semaphore r=10，money=0，ok=0；
顾客:
void custom（）{
while（true）{
wait（r）;
//资源信号量操作成对正确
enter;
take something;
signal（money）;
pay money;
wait(ok);
signal(r);
leave;
}
}
售货员:
void seller（）{
while（true）{
wait（money）;
//同步信号操作配对正确
accept money，give changes
signal（ok）；
//同步信号操作配对正确
}
}
版权声明：本文为qq_41814413原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。