并发进程及死锁问题

西安理工大学2006年第五章并发进程及死锁问题•进程间的联系•进程的同步机制──信号量及P.V操作（解决进程同步互斥问题）西安理工大学2006年5.1进程间的制约关系相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程西安理工大学2006年直接作用和间接作用直接作用：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间西安理工大学2006年相互感知程度交互关系一个进程对其他进程的影响相互不感知(完全不了解其它进程的存在)竞争(competition)一个进程的操作对其他进程的结果无影响间接感知(双方都与第三方交互，如共享资源)通过共享进行协作一个进程的结果依赖于从其他进程获得的信息直接感知(双方直接交互，如通信)通过通信进行协作一个进程的结果依赖于从其他进程获得的信息西安理工大学2006年进程的同步（直接作用）进程的同步：synchronism指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态西安理工大学2006年例:司机P1售票员P2while(true)while(true){{启动车辆；关门；正常运行；售票；到站停车；开门；}}西安理工大学2006年进程的互斥（间接作用）mutualexclusion由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥临界资源：criticalresource系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量西安理工大学2006年临界区（互斥区）：criticalsection一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区西安理工大学2006年a:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa0thena:=a+1elsea:=a-1P3互斥进程的互斥（间接作用）西安理工大学2006年程序段1程序段2程序段n共享变量西安理工大学2006年使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权西安理工大学2006年使用互斥区的原则：前提：任何进程无权停止其它进程的运行进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:•由竞争各方平等协商•引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）西安理工大学2006年进程互斥的软件方法•通过平等协商方式实现进程互斥的最初方法是软件方法•其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志•其中的主要问题是设置什么标志和如何检查标志西安理工大学2006年软件解法(1)free:表示临界区标志true:有进程在临界区false:无进程在临界区(初值)....while(free);free=true;临界区free=false;西安理工大学2006年软件解法(2)turn:trueP进入临界区falseQ进入临界区....P:while(notturn);临界区turn=false;Q:while(turn);临界区turn=true;西安理工大学2006年软件解法的缺点：1.忙等待2.实现过于复杂，需要高的编程技巧西安理工大学2006年硬件解法(1)“测试并设置”指令booleanTS(boolean*lock){booleanold;old=*lock;*lock=true;}whileTS(&lock);临界区lock=false;西安理工大学2006年硬件解法(2)“交换”指令voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);临界区lock:=false;西安理工大学2006年硬件解法(3)“开关中断”指令进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令西安理工大学2006年5.2进程的同步机制──信号量及P.V操作（解决进程同步与互斥）5.2.1概念同步机制：信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）西安理工大学2006年信号量分类公用信号量私用信号量二元信号量一般信号量西安理工大学2006年同步机制应满足的基本要求：*描述能力*可以实现*效率高*使用方便西安理工大学2006年信号量：semaphore•是一个数据结构•定义如下：strucsemaphore{intvalue;pointer_PCBqueue;}•信号量说明：semaphores;西安理工大学2006年P、V操作P(s){s.value=s.value--;if(s.value0){该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.queue;}}西安理工大学2006年P、V操作V(s){s.value=s.value++;if(s.value=0){唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪态并将其插入就绪队列}}西安理工大学2006年P、V操作为原语操作原语：primitiveoratomicaction是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性即原语的执行必须是连续的，在执行过程中不允许被中断实现：开关中断西安理工大学2006年信号量的使用：必须置一次且只能置一次初值初值不能为负数只能执行P、V操作西安理工大学2006年用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3互斥区P(mutex)P(mutex)V(mutex)V(mutex)西安理工大学2006年经典的生产者─消费者问题消费者生产者西安理工大学2006年经典的生产者─消费者问题同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为S1Q进程不能从“空”的缓冲区中取产品，设置信号量S2西安理工大学2006年S1初值为1，S2初值为0P：Q：while(true){while(true){生产一个产品;P(s2);P(s1);从缓冲区取产品;送产品到缓冲区;V(s1);V(s2);消费产品;};};单缓冲区生产者-消费者问题西安理工大学2006年......PQ放消息取消息nn个缓冲区(Buffer)ij西安理工大学2006年多个缓冲区的生产者和消费者P：i=0;while(true){生产产品;P(S1);往Buffer[i]放产品;V(S2);i=(i+1)%n;};Q：j=0;while(true){P(S2);从Buffer[j]取产品;V(S1);消费产品;j=(j+1)%n;};西安理工大学2006年【思考题】要不要对缓冲区（临界资源）进行互斥操作？西安理工大学2006年Q：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;V(mutex);V(S1);消费产品;j=(j+1)%n;};n个缓冲区、m个生产者和k个消费者P：i=0;while(true){生产产品;P(S1);P(mutex);往Buffer[i]放产品;V(mutex);V(S2);i=(i+1)%n;};有错误？若颠倒两个P操作的顺序？西安理工大学2006年Q：j=0;while(true){P(S2);P(mutex);从Buffer[j]取产品;j=(j+1)%n;V(mutex);V(S1);消费产品;};n个缓冲区、m个生产者和k个消费者P：i=0;while(true){生产产品;P(S1);P(mutex);往Buffer[i]放产品;i=(i+1)%n;V(mutex);V(S2);};正确西安理工大学2006年P.V操作讨论1)信号量的物理含义：S0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于0西安理工大学2006年2)P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要西安理工大学2006年3）P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂西安理工大学2006年当同时需要多种资源时怎么办?单个信号量使用很不方便，容易产生混乱,且前面已经提到对多个信号量进行P操作时,如果顺序稍有差错会导致错误发生，因此可以采用信号量集的方法西安理工大学2006年信号量集——AND型信号量集•AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作•AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配•AND型信号量集P原语为Swait•AND型信号量集V原语为Ssignal西安理工大学2006年Swait(S1,S2,…,Sn)//P原语；{while(TRUE){if(S1=1&&S2=1&&…&&Sn=1){//满足资源要求时的处理；for(i=1;i=n;++i)-–Si;//注：与P的处理不同，这里是在确信可满足//资源要求时，才进行减1操作；break;}else{//某些资源不够时的处理；调用进程进入第一个小于1信号量的等待队列Sj.queue;阻塞调用进程;}}}西安理工大学2006年Ssignal(S1,S2,…,Sn){for(i=1;i=n;++i){++Si;//释放占用的资源；for(在Si.queue中等待的每一个进程P)//检查每种资源的等待队列的所有进程；{从等待队列Si.queue中取出进程P;西安理工大学2006年if(判断进程P是否通过Swait中的测试)//注：与signal不同，这里要进行重新判断；{//通过检查（资源够用）时的处理；进程P进入就绪队列;}else{//未通过检查（资源不够用）时的处理；进程P进入某等待队列；}}}}西安理工大学2006年一般“信号量集”•一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理•一般信号量集的基本思路就是在AND型信号量集的基础上进行扩充，在一次原语操作中完成所有的资源申请西安理工大学2006年•进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：–Swait(S1,t1,d1;...;Sn,tn,dn);–Ssignal(S1,d1;...;Sn,dn);西安理工大学2006年一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：•Swait(S,d,d)表示每