操作系统课件(2.6 信号量与 PV 操作)

操作系统OperatingSystems徐小龙////xuxl@南京邮电大学NanjingUniversityofPostsandTelecommunicationsOS2023/1/112课程回顾上节课的重点内容引入进程并发提高系统效率进程异步执行资源共享使用导致程序结果不可再现引入进程同步机制进程有序合作（同步）资源合理共享（互斥）结果确定化基于进程间协商的同步机制有何问题？2023/1/113信号量与P/V操作本讲内容1、信号量(Semaphore)2、P(Proberen)、V(Verhogen)操作3、典型问题的解决方法4、问题思考与拓展学习2023/1/114信号量与P/V操作1、信号量(Semaphore)（1）信号量的提出荷兰著名科学家、计算机图灵奖获得者E.W.Dijkstra提出了一种卓有成效的进程互斥同步工具：信号量（Semaphore）机制，广泛应用于现代计算机系统中。E.W.Dijkstra2023/1/115信号量与P/V操作1、信号量(Semaphore)（2）信号量的构成Structsemaphore{

intvalue; //信号量值pointer_PCBqueue; //信号量队列指针}s.value信号量值进程1进程2进程3s.queue信号量队列指针2023/1/116信号量与P/V操作本讲内容1、信号量(Semaphore)2、P(Proberen)、V(Verhogen)操作3、典型问题的解决方法4、问题思考与拓展学习2023/1/117信号量与P/V操作2、P、V操作（1）P(Proberen)操作P(s){s.value=s.value－1;//s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{该进程状态置为等待状态;将该进程加入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)2023/1/118信号量与P/V操作2、P、V操作（1）P(Proberen)操作P(s){s.value=s.value－1;//s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{该进程状态置为等待状态;将该进程加入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)2023/1/119信号量与P/V操作2、P、V操作（1）P(Proberen)操作P(s){s.value=s.value－1;//s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{该进程状态置为等待状态;将该进程加入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)2023/1/1110信号量与P/V操作2、P、V操作（1）P(Proberen)操作P(s){s.value=s.value－1;//s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{该进程状态置为等待状态;将该进程加入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)2023/1/1111信号量与P/V操作2、P、V操作（1）P(Proberen)操作P(s){s.value=s.value－1;//s.value减1if(s.value<0) //该进程被阻塞，进入相应队列，然后转进程调度

{该进程状态置为等待状态;将该进程加入相应的等待队列s.queue的末尾;} //若s.value减1后仍大于或等于零，则进程继续执行

}

入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)2023/1/1112信号量与P/V操作2、P、V操作（2）V(Verhogen)操作V(s){s.value=s.value+1;//s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度{唤醒相应等待队列s.queue中等待的一个进程;将其状态修改为就绪态，并将其插入就绪队列;}//若相加结果大于零，进程继续执行} 入口s.value=s.value+1返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)2023/1/1113信号量与P/V操作2、P、V操作（2）V(Verhogen)操作V(s){s.value=s.value+1;//s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度{唤醒相应等待队列s.queue中等待的一个进程;将其状态修改为就绪态，并将其插入就绪队列;}//若相加结果大于零，进程继续执行} 入口s.value=s.value+1返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)2023/1/1114信号量与P/V操作2、P、V操作（2）V(Verhogen)操作V(s){s.value=s.value+1;//s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度{唤醒相应等待队列s.queue中等待的一个进程;将其状态修改为就绪态，并将其插入就绪队列;}//若相加结果大于零，进程继续执行} 入口s.value=s.value+1返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)2023/1/1115信号量与P/V操作2、P、V操作（2）V(Verhogen)操作V(s){s.value=s.value+1;//s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度{唤醒相应等待队列s.queue中等待的一个进程;将其状态修改为就绪态，并将其插入就绪队列;}//若相加结果大于零，进程继续执行} 入口s.value=s.value+1返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)2023/1/1116信号量与P/V操作2、P、V操作（2）V(Verhogen)操作V(s){s.value=s.value+1;//s.value加1if(s.value<=0)//从队列中唤醒一等待进程，然后继续执行或转进程调度{唤醒相应等待队列s.queue中等待的一个进程;将其状态修改为就绪态，并将其插入就绪队列;}//若相加结果大于零，进程继续执行} 入口s.value=s.value+1返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)2023/1/1117信号量与P/V操作本讲内容1、信号量(Semaphore)2、P(Proberen)、V(Verhogen)操作3、典型问题的解决方法4、问题思考与拓展学习2023/1/1118信号量与P/V操作3、典型问题的解决方法苹果桔子问题问题描述：（1）桌上有一只盘子，每次只能放入一只水果；（2）爸爸专向盘子中放苹果，妈妈专向盘子中放桔子；（3）儿子专等吃盘子中的桔子，女儿专等吃盘子里的苹果。2023/1/1119信号量与P/V操作3、典型问题的解决方法苹果桔子问题对应的计算机系统问题：多个进程共享同一个缓冲区实现定向通信P1P2C1C22023/1/1120信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（1）信号量的设置s代表可用的空盘子数，初值为1g1代表盘子里有无桔子，初值为0g2代表盘子里有无苹果，初值为0

2023/1/1121信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;processmother

beginL2:剥一个桔子；

P(s);放桔子；

V(g1);gotoL2;end;processson

beginL3:P(g1);取桔子；

V(s);吃桔子；gotoL3;end;2023/1/1122信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;2023/1/1123信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;2023/1/1124信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)s.value=12023/1/1125信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)s.value=02023/1/1126信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;入口s.value=s.value-1转进程调度将进程加入s.queue指向的等待队列s.value<0?返回否是

P(s)s.value=02023/1/1127信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;s.value=0入口返回或转进程调度唤醒g2.queue指向的等待队列中某进程g2.value<0?返回否是

V(g2)g2.value=g2.value+1g2.value=02023/1/1128信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;s.value=0入口g2.value=g2.value+1返回或转进程调度唤醒g2.queue指向的等待队列中某进程g2.value<0?返回否是

V(g2)g2.value=12023/1/1129信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=0g2.value=1processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;2023/1/1130信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=0g2.value=1processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;入口g2.value=g2.value-1转进程调度将进程加入g2.queue指向的等待队列g2.value<0?返回否是

P(g2)2023/1/1131信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=0g2.value=0processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;入口g2.value=g2.value-1转进程调度将进程加入g2.queue指向的等待队列g2.value<0?返回否是

P(g2)2023/1/1132信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=0g2.value=0processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;入口g2.value=g2.value-1转进程调度将进程加入g2.queue指向的等待队列g2.value<0?返回否是

P(g2)2023/1/1133信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=0g2.value=0processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;入口返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)s.value=s.value+12023/1/1134信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（2）P、V操作的部署s.value=1g2.value=0processdaughter

beginL4:P(g2);取苹果；

V(s);吃苹果；gotoL4;end;入口返回或转进程调度唤醒s.queue指向的等待队列中某进程s.value<0?返回否是

V(s)s.value=s.value+12023/1/1135信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（3）异常情况processfather

beginL1:削一个苹果；

P(s);放苹果;

V(g2);gotoL1;end;s.value=0g2.value=12023/1/1136信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（3）异常情况s.value=0g2.value=1processson

beginL3:P(g1);取桔子；

V(s);吃桔子；gotoL3;end;2023/1/1137信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（3）异常情况s.value=0g2.value=1processson

beginL3:P(g1);取桔子；

V(s);吃桔子；gotoL3;end;入口g1.value=g1.value-1转进程调度将进程加入g1.queue指向的等待队列g1.value<0?返回否是

P(g1)g1.value=02023/1/1138信号量与P/V操作3、典型问题的解决方法苹果桔子问题—解决思路—>（3）异常情况s.value=0g2.value=1processson

beginL3:P(g1);取桔子；

V(s);吃桔子；gotoL3;end;入口