操作系统 | PV操作

待我称王封你为后i 2024-04-17 06:03 35阅读 0赞

**写在前面**：这篇是为了练习pv操作在csdn上面找到的各种题目，对于推免复试来说，难度应该够了，接下来几天把这几道题目熟练默写即可。

--------------------

**哲学家问题**  
其他解法：https://blog.csdn.net/qq\_37457202/article/details/80977619  
有n(n>=3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m(m>=1)个碗，没两位哲学家之间有1根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作(wait(),signal()操作)描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。（408真题2019）

//信号量
    semaphore bowl;   //用于协调哲学家对碗的使用
    semaphore chopsticks[n];用于协调哲学家对筷子的使用
    for(int i =0;i<n;i++)
       chopsticks[i].value =1;//设置两个哲学家之间筷子的数量
    bowl.value=min(n-1,m);//bowl.value<=n-1,确保不死锁
    CoBegin
    while(True){                //哲学家i的程序
         思考：
         P(bowl);            //取碗
         P(chopsticks[i]);      //取左边筷子
         P(chopsticks[(i+1)MOD n]);       //取右边筷子
    就餐；
    V(chopsticks[i]);
    V(chopsticks[(i+1)MOD n]);
    V(bowl);
    }
    CoEnd

--------------------

**和尚打水问题**  
原文链接：https://blog.csdn.net/Yun\_Ge/article/details/89043419

某寺庙,有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用.水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个水桶取水.水桶总数为3个。每次入水、取水仅为一桶,且不可同时进行。试给出有关取水、入水的PV算法描述。  
分析：

*  由题可知，水井窄，只能容纳一人使用，所以需设一个互斥信号量mutex1来代表井
 *  每次入水取水不可同时进行，所以需设一个互斥信号量mutex2来代表缸
 *  桶为资源信号量，设为count。
 *  缸中水的数量和老和尚小和尚都有关，需设置两个不同的信号量，用empty资源信号量来告知小和尚是否可以提水入缸。
 *  用full资源信号量来告知老和尚是否可以从缸中取水。

设：mutex1=1,mutex2=1,count=3,empty=10,full=0;

void little_monk( )
    { 
    	while(true)
    	{ 
    		wait(empty);
    		wait(count);
    		wait(mutex1);
    		//此期间为取水阶段
    		signal(mutex1);
    		wait(mutex2);
    		//此期间为倒水入缸阶段
    		signal(mutex2);
    		signal(count);//还桶
    		signal(full);//发消息告知老和尚缸里有水
    	}
    } 
    void old_monk( )
    { 
    	while(true)
    	{ 
    		wait(full);
    		wait(count);
    		wait(mutex2);
    		//此期间为从缸中取水阶段
    		signal(mutex2);
    		signal(count);//还桶
    		signal(empty);//发消息告知小和尚可以取水了
    	}
    }

--------------------

**合作进程计算**  
原文链接：https://blog.csdn.net/bufanq/article/details/65990312  
有两个合作进程P1、P2，它们从同一台独占输入设备读入数据  
P1进程负责读入数据a，完成计算:x= a+b；P2进程负责读入数据b,完成计算：y=a\*b；计算完成后，结果x与y由进程P1负责输出，请使用信号量机制实现P1、P2进程的同步算法。

解答：

*  定义4个信号量：mutext用于互斥访问输入设备，
 *  初始值为1；m\_a、m\_b和m\_y用于P1和P2进程同步，
 *  m\_a表示数据a是否被读入，初始值为0；
 *  m\_b表示数据b是否被读入，初始值为0；
 *  m\_y表示y是否计算完成，初始值为0。

P1:   begin                                   P2 ：  begin
      	   P(mutex)                                       P(mutex)
           读数据a                                        读数据b
          V(mutex)                                       V(mutex)
          V(m_a)                                         V(m_b)
          P(m_b)                                         P(m_a)
          计算x=a+b                                   计算y=a*b
          P(m_y)                                         V(m_y)
          输出x和y                                       end
          end

--------------------

**阅览室**  
原文链接：https://blog.csdn.net/fuziwang/article/details/79884501  
有一阅览室，共有100个座位。读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。读者离开时要注销掉登记内容。试用wait和signal原语描述读者进程的同步问题。

semaphore empty = 100;// 记录空座位
    semaphore mutex = 1;// 作为互斥的访问登记和注销操作
    void reader()
    { 
    	while(true)
    	{ 
    		wait(empty);
    		wait(mutex);
    		// 登记
    		signal(mutex);
    		// read
    		wait(mutex);
    		// 注销
    		signal(mutex);
    		signal(empty);
    	}
    }

--------------------

有一只铁笼子，每次只能放入一只动物，猎手向笼子里放入老虎，农民向笼子里放入猪；动物园等待取笼子里的老虎，饭店等待取笼子里的猪。现请用wait和signal操作写出能同步执行的程序。

semaphore box = 1;// 记录笼子是否为空
    semaphore tiger = 0,pig = 0;// 作为老虎和猪的同步信号量
    void hunter()
    { 
    	while(true)
    	{ 
    		wait(box);
    		// 放入老虎
    		signal(tiger);
    	}
    }
    void farmer()
    { 
    	while(true)
    	{ 
    		wait(box);
    		// 放入猪
    		signal(pig);
    	}
    }
    void zoo()
    { 
    	while(true)
    	{ 
    		wait(tiger);
    		// 取走老虎
    		signal(box);
    	}
    }
    void restaurant()
    { 
    	while(true)
    	{ 
    		wait(pig);
    		// 取走猪
    		signal(box);
    	}
    }

--------------------

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题

(1)用PV操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。  
(2)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。

*  定义一信号量S，初始值为20。  
    S＞0，S的值表示可继续进入售票厅的人数;  
    S=0，表示售票厅中已有20名顾客(购票者)  
    S＜0，|S|的值为等待进入售票厅的人数。
 *  由于s的值表示的是在售票厅有多少个座位，因此最大值为s（表示没有人）最小值为s-n（根据n来决定）

--------------------

**公共汽车售票**  
在公共汽车上，司机负责开车、停车和驾驶，售票员负责门的开门、关门和售票。基本操作规则是只有停车后售票员才能开门只有售票员关门后司机才能开车。汽车初始状态处于行驶之中。当只有1个司机、2个售票员、2个门、每个售票员负责一个门时的协调操作。请使用P、V原语实现售票员与司机之间的协调操作说明每个信号量的含义、初值和值的范围。【燕山大学 2006复试】

semaphore full1 = 0,full2 = 0;// 作为司机和售票员的同步信号量
    semaphore door1 = 1,door2 = 1;//作为记录门的同步信号量
    void driver()
    { 
    	while(true)
    	{ 
    		wait(door1);// 只有售票员关门后司机才能开车
    		wait(door2);
    		// 启动车辆;
    		// 正常行车;
    		// 到站停车;
    		signal(full1);//只有停车后售票员才能开门
    		signal(full2);
    	}
    }
    void seller1()
    { 
    	while(true)
    	{ 
    		wait(full1);//只有停车后售票员才能开门
    		// 开门
    		// 关门
    		signal(door1);
    		// 售票
    	}
    }
    void seller2()
    { 
    	while(true)
    	{ 
    		wait(full2);//只有停车后售票员才能开门
    		// 开门
    		// 关门
    		signal(door2);
    		// 售票
    	}
    }

--------------------

**银行叫号**  
某银行有人民币储蓄业务由n个柜员负责，有1台取号机。每个顾客进入银行后先取一个号，若有人取号则需等他人取完后才能取,取到号后等待叫号当一个柜员人员空闲下来，就叫下一个号。试用P、V操作正确编写柜台人员和顾客进程的程序。【昆明理工大学 2006】

semaphore mutex = 1;// 互斥信号量 充当一台取号机的作用
    semaphore empty = 1;// 叫号机的使用
    semaphore full = 0;// 顾客和服务人员的同步信号量
    semaphore sell = n;// 记录是否有空闲的顾客
    void customer()
    { 
    	while(true)
    	{ 
    		wait(mutex);
    		// 取号
    		signal(mutex);
    		// 等待叫号
    		signal(full);
    		wait(sell);
    	}
    }
    void seller()
    { 
    	while(true)
    	{ 
    		wait(full);
    		wait(mutex);
    		// 叫号
    		signal(mutex);
    		// 服务
    		signal(sell);
    	}
    }

--------------------

**随身听**  
在一间酒吧里有三个音乐爱好者队列，第一个音乐爱好者只有随身听，第二个只有音乐磁带，第三个只有电池，而要听音乐就必须有随身听，音乐磁带和电池这三种物品。酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品并听完乐曲后，酒吧老板才能再一次出售这三种物品中任意两种，于是第二名音乐爱好者得到这三种物品。并开始听乐曲，全部买卖就这样进行下去。使用P,V操作正确解决这一买卖。（北京大学1999）

semaphore s = 1;// 作为是否有顾客来的标志
    bool flag1,flag2,flag3 = true;// 标识是否有资源
    semaphore s1 = 0,s2 = 0,s3 = 0;// 作为和爱好者进行同步的信号量
    void boss()
    { 
    	while(true)
    	{ 
    		wait(s);
    		if(flag2&flag3)
    			signal(s1);
    		else if(flag1&flag3)
    			signal(s2); 
    		else
    			signal(s3); 
    	}
    }
    void hobby1()
    { 
    	while(true)
    	{ 
    		wait(s1);
    		// 购买物品听乐曲
    		signal(s);// 可以有顾客去你们店了
    	}
    }
    void hobby2()
    { 
    	while(true)
    	{ 
    		wait(s2);
    		// 购买物品听乐曲
    		signal(s);// 可以有顾客去你们店了
    	}
    }
    void hobby3()
    { 
    	while(true)
    	{ 
    		wait(s3);
    		// 购买物品听乐曲
    		signal(s);// 可以有顾客去你们店了
    	}
    }

还看到一篇代码特长的，有空可以看一下：  
[操作系统-经典PV代码操作总结][-_PV]

[-_PV]: https://blog.csdn.net/qq_38181970/article/details/80574899