并发性互斥同步课件

第八章 并发性 互斥、同步进程间的联系进程间的联系v相交进程与无关进程相交进程与无关进程相交进程：指多个并发进程在逻辑上有某种联系相交进程：指多个并发进程在逻辑上有某种联系无关进程（不相交进程）：在逻辑上无任何联系的进程无关进程（不相交进程）：在逻辑上无任何联系的进程直接作用和间接作用直接作用和间接作用v直接作用：直接作用：进程间的相互联系是有意识的安排的，进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间直接作用只发生在相交进程间v间接作用：间接作用：进程间要通过某种中介发生联系，是无进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，意识安排的，可发生在相交进程之间，也可发生在无关进程之间也可发生在无关进程之间相互感知程度相互感知程度 交互关系交互关系 一个进程对其他进一个进程对其他进程程的影响的影响 相互不感知相互不感知(完全不完全不了解其它进程的存了解其它进程的存在在)竞争竞争(competition)一个进程的操作对一个进程的操作对其他进程的结果无其他进程的结果无影响影响 间接感知间接感知(双方都与双方都与第三方交互，如共第三方交互，如共享资源享资源)通过共享进行协作通过共享进行协作 一个进程的结果依一个进程的结果依赖于从其他进程获赖于从其他进程获得的信息得的信息 直接感知直接感知(双方直接双方直接交互，如通信交互，如通信)通过通信进行协作通过通信进行协作 一个进程的结果依一个进程的结果依赖于从其他进程获赖于从其他进程获得的信息得的信息 进程的同步（直接作用）进程的同步：进程的同步：synchronism指系统中多个进程中发生的事件存在某指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成种时序关系，需要相互合作，共同完成一项任务。一项任务。具体说，一个进程运行到某具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态态，获得消息后被唤醒进入就绪态例例:司机司机 P1 售票员售票员 P2 while(true)while(true)启动车辆；启动车辆；关门；关门；正常运行；正常运行；售票；售票；到站停车；到站停车；开门；开门；进程的互斥（间接作用）进程的互斥（间接作用）mutual exclusion 由于各进程要求共享资源，而有些资源需由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥资源，进程的这种关系为进程的互斥临界资源：临界资源：critical resource 系统中某些资源一次只允许一个进程使系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源用，称这样的资源为临界资源或互斥资源或共享变量或共享变量临界区（互斥区）：临界区（互斥区）：critical section 一个程序片段的集合，这些程序片一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作数据结构（共享资源）进行操作,在进程在进程中涉及到临界资源的程序段叫中涉及到临界资源的程序段叫临界区临界区 多个进程的临界区称为多个进程的临界区称为相关临界区相关临界区a:=a-1 print(a)a:=a+1 print(a)P1互斥互斥P2互斥互斥If a 0then a:=a+1else a:=a-1P3互斥互斥 进程的互斥进程的互斥（间接作用）（间接作用）使用互斥区的原则：有空让进有空让进：当无进程在互斥区时，任何有权使用互斥区：当无进程在互斥区时，任何有权使用互斥区的进程可进入的进程可进入无空等待无空等待：不允许两个以上的进程同时进入互斥区：不允许两个以上的进程同时进入互斥区多中择一多中择一：当没有进程在临界区，而同时有多个进程要：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程求进入临界区，只能让其中之一进入临界区，其他进程必须等待必须等待有限等待有限等待：任何进入互斥区的要求应在有限的时间内得：任何进入互斥区的要求应在有限的时间内得到满足到满足让权等待让权等待：处于等待状态的进程应放弃占用：处于等待状态的进程应放弃占用CPUCPU，以使，以使其他进程有机会得到其他进程有机会得到CPUCPU的使用权的使用权使用互斥区的原则：使用互斥区的原则：前提：任何进程无权停止其它进程的运行前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程之间相对运行速度无硬性规定进程互斥的解决有两种做法进程互斥的解决有两种做法:由竞争各方平等协商由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥引入进程管理者，由管理者来协调竞争各方对互斥资源的使用资源的使用具体方法：具体方法：硬件（当一个进程进入临界区硬件（当一个进程进入临界区,就屏蔽所有中断，就屏蔽所有中断，但成本高）但成本高）软件（用编程解决，但常常忙等待软件（用编程解决，但常常忙等待 ）进程互斥的软件方法v通过平等协商方式实现进程互斥的最初方法是通过平等协商方式实现进程互斥的最初方法是软件方法软件方法 v其基本思路是在进入临界区时检查和设置一些其基本思路是在进入临界区时检查和设置一些标志，如果已有进程在临界区，则在进入区通标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志过循环检查进行等待；在退出区修改标志 v其中的主要问题是设置什么标志和如何检查标其中的主要问题是设置什么标志和如何检查标志志软件解法（1）free:free:表示临界区标志表示临界区标志 true:true:有进程在临界区有进程在临界区 false:false:无进程在临界区无进程在临界区(初值初值).while(free while(free););free=false;free=false;临界区临界区 free=true;free=true;软件解法（2）Turn Turn true:P true:P进入临界区进入临界区 false:Qfalse:Q进入临界区进入临界区 .while(not turn);while(not turn);临界区临界区 turn=false;turn=false;while(turn);while(turn);临界区临界区 turn=true;turn=true;P:Q：软件解法（3）PturnPturn，qturnqturn：初值为：初值为falsefalseP P进入临界区条件：进入临界区条件：pturnpturn not qturnnot qturnQ Q进入临界区条件：进入临界区条件：not pturn not pturn qturn qturn .pturn=trun pturn=trun；whilewhile（qtrunqtrun）；）；临界区临界区 pturn=false;pturn=false;P:Q：pturn=truepturn=true；;while while（pturnpturn）；）；临界区临界区qturn=false;qturn=false;软件解法的缺点：软件解法的缺点：1.1.忙等待忙等待 2.2.实现过于复杂，需要高的编程技巧实现过于复杂，需要高的编程技巧硬件解法“测试并设置”指令 boolean TS(boolean boolean TS(boolean *lock)*lock)boolean boolean old;old;old=*lock;old=*lock;*lock=true;*lock=true;while TS(&lock);while TS(&lock);临界区临界区 lock=false;lock=false;硬件解法 “开关中断”指令进入临界区前执行：进入临界区前执行：执行执行“关中断关中断”指令指令离开临界区后执行：离开临界区后执行：执行执行“开中断开中断”指令指令进程的同步机制信号量及P.V操作（解决进程同步）同步机制：同步机制：信号量及信号量及P P、V V操作；管程；条件临界操作；管程；条件临界域；路径表达式等（用于集中式系统中）域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）程过程调用等（适用于分布式系统中）信号量：semaphorev是一个数据结构是一个数据结构v定义如下：定义如下：strucstruc semaphore semaphore intint value;value;pointer_PCB queue;pointer_PCB queue;v信号量说明：信号量说明：semaphore s;semaphore s;P、V操作P(s)P(s)s.value=s.value-;s.value=s.value-;if(s.value 0)if(s.value 0)该进程状态置为等待状态该进程状态置为等待状态 将该进程的将该进程的PCBPCB插入相应的等待队列末尾插入相应的等待队列末尾s.queue;s.queue;P、V操作V(s)V(s)s.value=s.value+;s.value=s.value+;if(s.value =0)if(s.value 0表示有S个资源可用S=0表示无资源可用S0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于02)P.V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定操作就一定有一个有一个V操作操作.当为互斥操作时，它们同处于同一进程当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现当为同步操作时，则不在同一进程中出现 如果如果P(S1)和和P(S2)两个操作在一起，那么两个操作在一起，那么P操作的顺序至关重要操作的顺序至关重要,一个同步一个同步P操作与一个互操作与一个互斥斥P操作在一起时同步操作在一起时同步P操作在互斥操作在互斥P操作前操作前3）P.V操作的优缺点操作的优缺点优点：优点：简单，而且表达能力简单，而且表达能力强强（用（用P.V操作可解决操作可解决任何同步互斥问题）任何同步互斥问题）缺点：缺点：不够安全；不够安全；P.V操作使用不当会出现死锁；操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂遇到复杂同步互斥问题时实现复杂【思考题】1.用P.V操作解决下图之同步问题:getcopyput用P.V操作解决司机与售票员的问题司机进程：司机进程：while while(true)(true)启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车 售票员进程：售票员进程：while while(true)(true)关门关门售票售票开门开门 练习用PV操作控制(1)猎人捕虎，农民养猪，他们共用一个笼子放虎和放猪，动物园从笼中取虎，餐馆从笼中取猪，如何控制？(2)p1p5p3p4p6p2练习用PV操作控制 桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。作业v1、P109 2 和3