第三章进程的同步与通信进程互斥基本概念c临界区(criticalsection)：临界段，在每个程序中，访问临界资源的那段程序。注意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。如有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。解决互斥的准则软件方法解决进程互斥算法1算法1的问题算法2算法2的问题算法3Pi进程：Repeatflag[i]:=true;Whileflag[j]dono_op;Criticalsectionflag[i]:=false;OthercodeUntilfalse;算法3的问题课本上的解法4算法4（正确算法）算法4（正确算法）软件解法的缺点硬件方法解决进程互斥Test-and-Set指令实现互斥2、利用TS指令实现进程互斥为每个临界资源设置一个全局布尔变量lock，并赋初值false，表示资源空闲。repeatwhileTS(lock)doskip;criticalsectionlock:=false;OthercodeUntilfalse;swap指令实现进程互斥2、利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中有局部布尔变量key。Repeatkey:=true;RepeatSwap(lock,key);Untilkey=false;Criticalsectionlock:=false;OthercodeUntilfalse;用原语实现进程互斥上锁和开锁原语用原语实现进程互斥改进的上锁原语改进的开锁原语1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)）一种卓有成效的进程同步机制最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）P、V操作是原语信号量：semaphoreP操作V操作必须置一次且只能置一次初值初值不能为负数只能执行P、V操作用P、V操作解决进程间互斥问题信号量及P、V操作讨论思考1)信号量的物理含义：S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P(S)：表示申请一个资源V(S)：表示释放一个资源。信号量的初值应该大于等于02)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要3）P、V操作的优缺点优点：简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）缺点：不够安全，P、V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂信号量集——AND型信号量集Swait(S1,S2,…,Sn)//P原语；{if(S1>=1&&S2>=1&&…&&Sn>=1){//满足资源要求时的处理；for(i=1;i<=n;++i)-–Si;}else{//某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue;阻塞调用进程;}}Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si;//释放占用的资源；for(在Si.queue中等待的每一个进程P){从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)//重新判断{进程P进入就绪队列;break；}else进程P进入某等待队列；}}}一般“信号量集”进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si>=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：进程同步合作进程的执行次序例【思考题1】解【思考题2】解【思考题3】解共享缓冲区的进程的同步分析解【思考题】解【思考题】解经典的进程同步问题生产者/消费者问题问题描述图问题分析问题的解采用AND信号量集解决生产者-消费者问题【思考题】解设信号量S1,mutex初值均为0【思考题】解读者/写者问题第一类：读者优先第一类读者写者问题的解法