操作系统——信号量例题
有一个仓库,可以存放 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); //离开临界区,释放互斥信号量 } }
下一篇: php&mysql插入数据时提醒?