操作系统——信号量例题
有一个仓库，可以存放 a 和 b 两种产品，仓库的存储空间足够大，但要求: (1)一次只能存入一种产品(a 或 b); (2)-n < (a 产品数量-b 产品数量) < m。 其中，n 和 m 是正整数。试用“存放 a”和“存放 b”以及 p、v 操作描述产品 a 与 产品 b 的入库过程。
semaphore sa = m - 1;
semaphore sb = n - 1;
//代表还能存入的数量
semaphore mutex = 1;
process_a() {
while(1){
p(sa); //取一个a产品准备入库
p(mutex);
a产品入库;
// a产品入库后还能存入a产品数量-1
v(mutex);
v(sb); //还能存入b产品数量+1
}
}
process_b() {
while(1){
p(sb); //取一个b产品准备入库
p(mutex);
b产品入库;
// b产品入库后还能存入b产品数量-1
v(mutex);
v(sa); //还能存入a产品数量+1
}
}
桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子放苹果（ apple），妈妈专向盘子中放桔子（ orange）；两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用 p、 v 操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。
semaphore mutex = 1; //互斥信号量, 其初值为1
semaphore empty = 2; //记录允许向盘子中放入水果的个数，初值为2
semaphore orange = 0; //盘子中已放入的苹果的个数，初值为0
semaphore apple = 0; //盘子中已放入的桔子的个数，初值为0
main()
{
cobegin
{
father //父亲进程
{
while (true)
{
p(empty); //减少盘中可放入的水果数
p(mutex); //申请向盘中取、放水果
向盘中放苹果;
v(mutex); //允许向盘中取、放水果
v(apple); //递增盘中的苹果数
}
}
mother //母亲进程
{
while (true)
{
p(empty); //减少盘中可放入的水果数
p(mutex); //申请向盘中取、放水果
向盘中放桔子;
v(mutex); //允许向盘中取、放水果
v(orange); //递增盘中的桔子数
}
}
daughteri（i=1,2） //两女儿进程
{
while (true)
{
p(apple); //减少盘中苹果数
p(mutex); //申请向盘中取、放水果
取盘中苹果;
v(mutex); //允许向盘中取、放水果
v(empty); //递增盘中可放入的水果数
}
}
sonj（j=1,2） //两儿子进程
{
while (true)
{
p(orange); //减少盘中桔子数
p(mutex); //申请向盘中取、放水果
取盘中桔子;
v(mutex); ／/允许向盘中取、放水果
v(empty); //递增盘中可放入的水果数
}
}
}
coend
}
有一个理发师，一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发师椅子上睡觉；当一个顾客到来时，必须唤醒理发师进行理发；如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他就坐下来等，如果没有空椅子，他就离开。为理发师和顾客各编一段程序（伪代码）描述他们的行为，要求不能带有竞争条件。
semaphore mutex = 1; //互斥信号量，初值为1.
semaphore wait = 0; //等待服务的顾客数
semaphore barbers= 0; //等待顾客的理发师数
int custnum = 0; //等待的顾客(还没理发的)
costumer()
{
while(true)
{
p(mutex); //申请理发
if(custnum>0)
{
if(custnum<n) //若等待人数小于n
{
v(mutex); //释放进程等待
custnum++； //增加等待人数
}
else //若等待人数超过n
{
v(mutex); //释放进程等待
离开；
}
}
else //若目前无人等待
{
v(mutex); //释放进程等待
v(barbers)； //如果必要的话，唤醒理发师
理发；
离开；
p(mutex); //要求进程等待
custnum--； //顾客人数减1
v(mutex); //释放进程等待
v(wait); //等待人数减1
}
}
}
barber()
{
while(true)
{
p(mutex); //要求进程等待
if(custnum ==0) //目前无顾客
{
v(mutex); //释放进程等待
p(barbers); //理发师睡觉
}
else
{
v(mutex); //释放进程等待
理发;
}
}
}
吸烟者问题。三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。
semaphore s = 1; //供应者
semaphore s1,s2,s3; //三个吸烟者
s1 = s2 = s3 = 0;
bool flag1,flag2,fiag3; //三种吸烟原料
fiag1=flag2=flag3=true;
apply() //供应者
{
while(true)
{
p(s);
取两样香烟原料放桌上，由flagi标记；
if (flag2 && flag3) //供纸和火柴
{
v(s1); //唤醒吸烟者一
}
else if(flag1 && fiag3) //供烟草和火柴
{
v(s2); //唤醒吸烟者二
}
else //供烟草和纸
{
v(s3); //唤醒吸烟者三
}
}
}
smoker1() //吸烟者一
{
while(true)
{
p(s1);
取原料；
做香烟；
v(s); //唤醒供应者
吸香烟；
}
}
smoker2() //吸烟者二
{
while(true)
{
p(s2);
取原料；
做香烟；
v(s); //唤醒供应者
吸香烟;
}
}
smoker3() //吸烟者三
{
while(true)
{
p(s3);
取原料；
做香烟；
v(s); //唤醒供应者
吸香烟;
}
}
面包师问题。面包师有很多面包和蛋糕，由 n 个销售人员销售。每个顾客进店后先取一个号，并且等着叫号。当一个销售人员空闲下来，就叫下一个号。请分别编写销售人员和顾客进程的程序。
semaphore buyer= 0; //顾客人数
semaphore seller = n; //销售人员数
semaphore mutex_s = 1; //用于销售人员的互斥信号量
semaphore mutex_b = 1; //用于顾客的互斥信号量
int count_s = 0; //记录取号的值
int count_b = 0; //记录叫号的值
void buy() //顾客进程
{
进店；
p(mutex_b); //取号
count_b++;
v(mutex_b);
v(buyer);
p(seller); //等待叫号
买面包；
离开
}
void sell()
{
while(true)
{
p(buyer);
p(mutex_s); //叫号
count_s++;
叫编号为count_s的顾客；
v(mutex_s);
v(seller)；
}
}
桌上有一空盘，运行存放一只水果，爸爸可向盘中放苹果，也可放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一个水果供吃者取用，用 p,v 原语实现爸爸儿子和女儿 3 个并发进程的同步。
semaphore s = 1; //s 表示盘子是否为空；
semaphore sa = 0; //sa 表示盘中是否有苹果；
semaphore sb = 0; //sb 表示盘中是否有桔子；
father() //父亲进程
{
while(true)
{
p(s);
将水果放入盘中;
if (放入的是桔子)
v(sb);
else
v(sa);
}
}
son() //儿子进程
{
while(true)
{
p(sb);
从盘中取出桔子；
v(s);
吃桔子;
}
}
daughter() //女儿进程
{
while(true)
{
p(sa);
从盘中取出苹果；
v(s);
吃苹果;
}
}
写者优先的读者－－写者问题。读者-写者问题为数据库访问建立了一个模型。例如,一个系统,其中有许多竞争的进程试图读写其中的数据,多个进程同时读是可以接受的,但如果一个进程正在更新数据库,则所有的其他进程都不能访问数据库，即使读操作也不行。写者优先是指当一个写者到达时，将阻止其后面的读者进入数据库，直到其离开为止。
semaphore mut1, mut2, wmutex, fmutex; //互斥信号量
int rcount, wcount; //读写者人数
mut1 = mut2 = wmutex = fmutex = 1;
rcount = wcount = 0;
writer() //写者进程
{
while(true)
{
p(mut1);
wcount=wcount+1；
if (wcount==1)
{
p(fmutex); //如有读者，写者阻塞在此处
}
v(mut1);
p(wmutex);
写；
v(wmutex);
p(mut1);
wcount=wcount-1;
if (wcount==0)
{
v(fmutex);
}
v(mut1);
}
}
reader() //读者进程
{
while(true)
{
p(mut2);
rcount=rcount+1;
if (rcount==1)
{
p(fmutex);
}
v(mut2);
读；
p(mut2);
rcount=rcount-1;
if (rcount==0)
{
v(fmutex);
}
v(mut2);
}
}
在天津大学与南开大学之间有一条弯曲的小路，这条路上每次每个方向上只允许一辆自行车通过。但其中有一个小的安全岛 m，同时允许两辆自行车停留，可供两辆自行车已从两端进入小路的情况下错车使用。如图所示。
下面的算法可以使来往的自行车均可顺利通过。其中使用了 4 个信号量， t 代表天大路口资源， s 代表南开路口资源， l 代表从天大到安全岛一段路的资源， k 代表从南开到安全岛一段路的资源。程序如下，请在空白位置处填写适当的 pv 操作语句，每处空白可能包含若干个 pv 操作语句。
begin
t:=1;s:=1;l:=1;k:=1;
cobegin
从天大到南开的进程
begin
______(1)______
通过 l 路段;
进入安全岛 m；
______(2)______
通过 k 路段
______(3)______
end
从南开到天大的进程
begin
略，与“从天大到南开的进程”相反。
end
coend
end
解答：
(1) p(t); p(l);
(2) v(l); p(k);
(3) v(k); v(t);
三个进程 p1、 p2、 p3 互斥使用一个包含 n(n>0)个单元的缓冲区。 p1 每次用 produce()生成一个正整数并用 put()送入缓冲区某一空单元中;p2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数;p3 每次用 geteven()从该缓冲区中取出一个偶数并用 counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动,并说明所定义信号量的含义。要求用伪代码描述。
p1()
{
while(true)
{
x = produce(); //生成一个数
p(empty); //是否有空单元格
p(mutex); //进入临界区
put();
if(x%2 == 0)
v(s2); //如果是偶数，向p3发出信号
else
v(s1); //如果是奇数，向p2发出信号
v(mutex); //离开临界区，释放互斥信号量
}
}
p2()
{
while(true)
{
p(s1); //收到p1发送来的信号，已产生奇数
p(mutex); //进入临界区
getodd();
countodd():=countodd()+1;
v(mutex);
v(empty); //离开临界区，释放互斥信号量
}
}
p3()
{
while(true)
{
p(s2) //收到p1发送来的信号，已产生偶数
p(mutex); //进入临界区
geteven();
counteven():=counteven()+1;
v(mutex);
v(empty); //离开临界区，释放互斥信号量
}
}
上一篇： 用规划模型求解指派问题
下一篇： 全国大学高校基础信息 API 接口