资源描述
（一）进程与线程（一）进程与线程（二）处理机调度（二）处理机调度（三）同步与互斥（三）同步与互斥（四）死锁（四）死锁第二部分第二部分进程管理进程管理1（三）同步与互斥（三）同步与互斥21.进程同步的基本概念进程同步的基本概念多道程序系统中，进程之间有两种形式的制约关系：多道程序系统中，进程之间有两种形式的制约关系：（1）间接相互制约：源于资源共享）间接相互制约：源于资源共享（2）直接相互制约：源于进程合作）直接相互制约：源于进程合作进程同步：主要源于进程合作进程同步：主要源于进程合作是进程之间的直接制约关系是进程之间的直接制约关系进程互斥：主要源于进程共享进程互斥：主要源于进程共享是进程之间的间接制约关系是进程之间的间接制约关系3临界资源：一次只允许一个进程使用的资源。临界资源：一次只允许一个进程使用的资源。如：打印机，公共变量如：打印机，公共变量临界区：在每个进程中，访问临界资源的那段程序。临界区：在每个进程中，访问临界资源的那段程序。同步机制遵循的准则：同步机制遵循的准则：空闲让进，忙则等待，有限等待，让权等待空闲让进，忙则等待，有限等待，让权等待当临界区空闲时，进程可以立即进入，以便有效利用临界资源当已有进程进入临界区时，其它进程必须等待，以保证互斥对要求进入的进程，应在有限的时间内使之进入，以避免“死等”对于等待的进程，它必须立即释放处理机，以避免进程忙等42.实现临界区互斥的基本方法实现临界区互斥的基本方法进程互斥的硬件方法进程互斥的硬件方法（1）检测和设置（）检测和设置（TS）指令）指令（2）swap指令（或指令（或exchange）交换两个字（字节）交换两个字（字节）的内容的内容用软件实现的同步互斥机制用软件实现的同步互斥机制在进入区设置和检查一些标志在进入区设置和检查一些标志（1）算法一：单标志法）算法一：单标志法（2）算法二：双标志法先检查）算法二：双标志法先检查（3）算法三：双标志法后检查）算法三：双标志法后检查（4）算法四：）算法四：Peterson算法算法5【例1】（错误解法）（turn是int型的变量，初始化为i或j）算法一能够保证同一时刻只有一个进程在临界区中，但是却要求进程Pi和进程Pj轮流地访问临界区，若进程Pi不打算进入临界区，那么进程Pj在进入过一次临界区后就再也不能进入。所以不满足空闲让进和有限等待不满足空闲让进和有限等待的两个准则。6【例2】（错误解法）（flag2是bool型的数组，两个元素初始化为false）算法二消除了算法一中需要两个进程轮流访问临界区的错误，但却存在两个进程都进不了临界区的可能性，仍然不不能满足空闲让进和有限等待。能满足空闲让进和有限等待。7【例【例3】算法三（正确解法，又称为】算法三（正确解法，又称为Dekker算法）算法）（turn是是int型的变量，初始化为型的变量，初始化为i或或j；flag2是是bool型的数组，型的数组，两个元素初始化为两个元素初始化为false）Dekker算法结合了算法一和算法二，实现了空闲让进和忙则等算法结合了算法一和算法二，实现了空闲让进和忙则等待。基本上待。基本上Dekker算法是个正确的算法，能够正常工作。算法是个正确的算法，能够正常工作。8【例【例4】算法四（正确解法，又称为】算法四（正确解法，又称为Peterson算法）算法）（turn是是int型的变量，初始化为型的变量，初始化为i或或j；flag2是是bool型的数型的数组，两个元素初始化为组，两个元素初始化为false）Peterson算法与算法与Dekker算法类似，实现了空闲让进、忙则等待和有限等算法类似，实现了空闲让进、忙则等待和有限等待。相比而言，待。相比而言，Dekker算法比较复杂，证明起来也比较困难，而算法比较复杂，证明起来也比较困难，而Peterson算法较简洁。算法较简洁。9【例11】（2010年联考第27题）进程P0和P1的共享变量定义及其初值为：boolean falg2;int turn=0;falg0=FALSE;falg1=FALSE;若进程P0和P1访问临界资源的类C伪代码实现如下：void P0()/进程P0while(TRUE)flag0=TRUE;turn=1;while(flag1&turn=1);临界区;flag0=FALSE;void P1()/进程P1while(TRUE)flag1=TRUE;turn=0;while(flag0&turn=0);临界区;flag1=FALSE;则并发执行进程则并发执行进程P0和和P1时产生的情形是时产生的情形是A.不能保证进程互斥进入临界区、会出现不能保证进程互斥进入临界区、会出现“饥饿饥饿”现象现象B.不能保证进程互斥进入临界区、不会出现不能保证进程互斥进入临界区、不会出现“饥饿饥饿”现现象象C.能保证进程互斥进入临界区、会出现能保证进程互斥进入临界区、会出现“饥饿饥饿”现象现象D.能保证进程互斥进入临界区、不会出现能保证进程互斥进入临界区、不会出现“饥饿饥饿”现象现象00000000103.信号量信号量信号量机制由：信号量机制由：信号量信号量”“wait操作（操作（P操作）、操作）、signal操作操作(V操作操作)”两部分组成，可用来解决进程的互斥与同步。两部分组成，可用来解决进程的互斥与同步。P、V操作是原子操作，不可中断。操作是原子操作，不可中断。（1）整型信号量）整型信号量定定义：表示：表示资源的个数的整型量源的个数的整型量S。除初始化外，。除初始化外，仅能通能通过以下两个原子操作来以下两个原子操作来访问。wait(S)（P操作）:While(S=0);S=S-1;signal(S)（V操作）:S=S+1;113.信号量信号量（2）记录型信号量）记录型信号量在记录型信号量中，引入了代表资源数目的整在记录型信号量中，引入了代表资源数目的整型变量型变量value和用于链接所有等待该资源的进程链表和用于链接所有等待该资源的进程链表L，记录型数据结构如下所示：，记录型数据结构如下所示：Typedefstructintvalue;QueueL;semaphore;若有若有semaphoreS;相应的相应的wait(S)和和signal(S)操作可描述为：操作可描述为：wait(S)S.value=S.value-1;if(S.value0)block(S.L);signal(S)S.value=S.value+1;if(S.value0表示有表示有S.value个资源可用；个资源可用；S.value=0表示无资源可用；表示无资源可用；S.value0B.=0D.0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。【分析】本题目考查进程的同步与互斥。本题目是苹果【分析】本题目考查进程的同步与互斥。本题目是苹果-桔子问题的变形。桔子问题的变形。进程进程P1可以看做是生产者，进程可以看做是生产者，进程P2和和P3可看做是消费者，可看做是消费者，进程进程P1和和P2、P3共享大小为共享大小为N的缓冲区。的缓冲区。进程进程P1、P2和和P3需互斥使用缓冲区，需互斥使用缓冲区，P1进程需要与进程需要与P2进程、进程、P3进程同步。进程同步。2627282930【例【例11】在一辆公共汽车上，司机和售票员各行其职，在一辆公共汽车上，司机和售票员各行其职，司机负责开车和到站停车；售票员负责售票和开、关门，当司机负责开车和到站停车；售票员负责售票和开、关门，当售票员关好车门后，司机才能继续开车行驶。试用售票员关好车门后，司机才能继续开车行驶。试用P、V操操作实现司机与售票员之间的同步。作实现司机与售票员之间的同步。【分析】这里存在两种同步关系：【分析】这里存在两种同步关系：司机到站停车后，售票员才能开门；司机到站停车后，售票员才能开门；售票员关好车门后，司机才能启动汽车。售票员关好车门后，司机才能启动汽车。31设初始状态为停车，车门开。设初始状态为停车，车门开。设信号量：设信号量：close表示门是否已关，能否启动车辆表示门是否已关，能否启动车辆stop表示车是否已停，能否开车门表示车是否已停，能否开车门semaphoreclose=0,stop=1;main()Cobegindrive()While(true)P(close);启动车辆启动车辆;正常行驶正常行驶;到站停车到站停车;V(stop);Conductor()While(true)关车门；关车门；V(close);售票售票;P(stop);开车门开车门;上下乘客上下乘客;32【例【例12】（】（2011年联考第年联考第45题）某银行提供一个服务窗口和题）某银行提供一个服务窗口和10个供顾客等待个供顾客等待的座位。顾客到达银行时，若有空座位则到取号机上领取一个号，等待叫号。取的座位。顾客到达银行时，若有空座位则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：其服务。顾客和营业员的活动过程描述如下：CobeginProcess顾客顾客i从取号机获得一个号码；从取号机获得一个号码；等待叫号；等待叫号；获得服务；获得服务；Process营业员营业员while(TRUE)叫号；叫号；为顾客服务；为顾客服务；Coend请添加必要的信号量和请添加必要的信号量和P、V（或（或wait()、signal()）操作，实现上述过程中的）操作，实现上述过程中的互斥与同步。要求写出完整过程，说明信号量的含义并赋初值。互斥与同步。要求写出完整过程，说明信号量的含义并赋初值。【分析】【分析】（1）互斥关系：顾客需互斥使用取号机，）互斥关系：顾客需互斥使用取号机，设一互斥信号量设一互斥信号量mutex，初值为，初值为1;（2）同步关系：顾客需要获得空座位等）同步关系：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位待叫号，当营业员空闲时，将选取一位顾客并为其服务。顾客并为其服务。33Semaphoremutex=1;/互斥使用取号机互斥使用取号机Semaphoreempty=10;/空座位的数量空座位的数量Semaphorefull=0;/已占座位的数量已占座位的数量Semaphoreservice=0;/等待叫号等待叫号Cobeginprocess顾客顾客iP(empty);P(mutex);从取号机获得一个号；从取号机获得一个号；V(mutex);V(full);P(service);/等待叫号等待叫号获得服务；获得服务；process营业员营业员while(TRUE)P(full);V(empty);V(service);/叫号叫号为顾客服务；为顾客服务；34【例【例13】有桥如图所示，车流如箭头所示，桥上】有桥如图所示，车流如箭头所示，桥上不允许两车交汇，但允许同方向多辆车依次通过不允许两车交汇，但允许同方向多辆车依次通过（即桥上可以有多个同方向的车）。用（即桥上可以有多个同方向的车）。用P、V操操作实现交通管理以防止桥上堵塞。作实现交通管理以防止桥上堵塞。桥桥北北南南【分析】本题目类似【分析】本题目类似“读者读者写作写作”问题，但又有所不同。问题，但又有所不同。这个题目要解决：这个题目要解决：南、北互斥（桥上不允许两车交汇，相当于南、北互斥（桥上不允许两车交汇，相当于“读、写互斥读、写互斥”），），需要设置一个互斥信号量需要设置一个互斥信号量mutex，初值为，初值为1；南、南共享（相当于南、南共享（相当于“读、读共享读、读共享”），套用实现），套用实现“读、读共享读、读共享”的模式，需要设置一个共享变量的模式，需要设置一个共享变量south，用于记录当前桥上向，用于记录当前桥上向南行驶过桥的车辆数目，初值为南行驶过桥的车辆数目，初值为0，再设置一个互斥信号量，再设置一个互斥信号量smutex，实现对，实现对south的互斥访问；的互斥访问；北、北共享（也相当于北、北共享（也相当于“读、读共享读、读共享”），需要设置一个共享变），需要设置一个共享变量量north，用于记录当前桥上向北行驶过桥的车辆数目，初值为，用于记录当前桥上向北行驶过桥的车辆数目，初值为0，再设置一个互斥信号量，再设置一个互斥信号量nmutex，实现对，实现对north的互斥访问。的互斥访问。35semaphore mutex=1,smutex=1,nmutex=1;int south=0,north=0;main()CobeginTosouth();Tonorth();CoendTosouth()While(1)P(smutex);if(south=0)P(mutex);/*当第1辆向南的车辆过桥时，阻止向北车辆过桥*/south+V(smutex);过桥；P(smutex);south-;If(south=0)V(mutex);/*当最后1辆向南的车辆过桥后，允许向北车辆过桥*/V(smutex);Tonorth()While(1)P(nmutex);If(north=0)P(mutex);/*当第1辆向北的车辆过桥时，阻止向南车辆过桥*/north+V(nmutex);过桥；P(nmutex);north-;If(north=0)V(mutex);/*当最后1辆向北的车辆过桥后，允许向南车辆过桥*/V(nmutex);361.（2010年联考第年联考第25题）题）设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是（）。A.0、1 B.1、0 C.1、2 D.2、0【答案】【答案】B练习练习372.设两个进程共用一个临界资源的互斥信号量mutex，当mutex=-1 时表示（）。A.一个进程进入了临界区，另一个进程等待 B.没有一个进程进入临界区C.两个进程都进入了临界区 D.两个进程都在等待【答案】【答案】A练习练习383、（2011年联考第32题）有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。/加1操作 /减1操作 Load R1,x /取x到寄存器中Load R2,xInc R1 dec R2Store x,R1/将R的内容存入x Store x,R2两个操作完成后，x的值（）。A.可能为-1 B.只能为1 C.可能为0、1、2 D.可能为-1、0、1、2【答案】【答案】C练习练习394、某车站售票厅，任何时刻最多可容纳 20 名购票者进入，当售票厅中少于 20 名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用 PV 操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，利用PV操作写出能正确并发执行的进程。(3)若欲购票者最多为 n 个人，写出信号量可能的变化范围(最大值和最小值)。404.【分析】本题目考查进程的同步问题。【答案】(1)定义一信号量 S，初始值为 20。S0 S 的值表示可继续进入售票厅的人数 S=0 表示售票厅中已有 20 名顾客(购票者)S0|S|的值为等待进入售票厅的人数（2）COBEGIN Pi(i=1，2，)P(S)；进入售票厅；购票；退出；V(S)；COEND(3)S 的最大值为 20 S 的最小值为 20-N415.在公共汽车上，司机负责开车、停车和驾驶，售票员负责门的开门、关门和售票。基本操作规则是:只有停车后，售票员才能开门；只有售票员关门后，司机才能开车。汽车初始状态处于行驶之中。当只有1个司机、2个售票员、2个门、每个售票员负责一个门时的协调操作。请使用P、V原语实现售票员与司机之间的协调操作，说明每个信号量的含义、初值和值的范围。42driver()do while T P(Door1)；P(Door2)；启动车辆；正常行车；到站停车；busserver 1()do while T 售票；开前门；关前门；busserver 2()do while T 售票；开后门；关后门；【分析】本题目考查进程的同步问题。司机的启动、停车操作需要与两个售票员的关门、售票、开门操作同步.确定确定P、V操作的位置操作的位置司机操作中，是否关前门？没关则等待，这是一个司机操作中，是否关前门？没关则等待，这是一个P操作，操作，P(Door1)；是否关后门？没关则等待，这是一个是否关后门？没关则等待，这是一个P操作，操作，P(Door2)；43driver()do while T P(Door1)；P(Door2)；启动车辆；正常行车；到站停车；busserver 1()do while T 售票；开前门；关前门；V(Door1)；busserver 2()do while T 售票；开后门；关后门；V(Door2)；【分析】本题目考查进程的同步问题。司机的启动、停车操作需要与两个售票员的关门、售票、开门操作同步.确定确定P、V操作的位置操作的位置前门售票员关门操作中，设立关门标志，这是一个V操作，V(Door1)；后门售票员关门操作中，设立关门标志，这是一个V操作，V(Door2)；44driver()do while T P(Door1)；P(Door2)；启动车辆；V(T1)；V(T2)；正常行车；到站停车；V(S1)；V(S2)；busserver 1()do while T 售票；开前门；关前门；V(Door1)；busserver 2()do while T 售票；开后门；关后门；V(Door2)；【分析】本题目考查进程的同步问题。司机的启动、停车操作需要与两个售票员的关门、售票、开门操作同步.确定确定P、V操作的位置操作的位置司机操作中，设立启动标志，通知前、后门售票员可以售票，这是两个V操作，V(T1)，V(T2)；司机操作中，设立停车标志，通知前、后门售票员可以开门，这是两个V操作，V(S1)，V(S2)；由于汽车初始状态处于行驶之中，所以Door1=Door2=0，T1=T2=0（不严格），S1=S2=0，所有信号量的取值范围都是-11。45 Semaphore Door1=Door2=1;Semaphore S1=S2=0;Semaphore T1=T2=1;main()cobegindriver();busserver 1();busserver 2();coenddriver()do while T P(Door1)；P(Door2)；启动车辆；V(T1)；V(T2)；正常行车；到站停车；V(S1)；V(S2);busserver 1()do while T P(T1)；售票；P(S1)；开前门；关前门；V(Door1)；busserver 2()do while T P(T2)；售票；P(S2)；开后门；关后门；V(Door2)；466设，两个火车站之间是单轨连接的，现有许多列车同时到A站,需经A站到达B站，列车出B站后又可分路行驶（如图）。为保证行驶安全，请设计一个自动调度系统保证系统安全。提示：可用P、V操作设计。6A.有一个东西方向的独木桥，每次只能有一人通过，且不允许人在桥上停留。东西两端各有若干人在等待过桥。请用P、V操作来实现东西两端的人过桥的问题。477.一个理发店，由一间有N张沙发的等候室和一间放有一个理发椅的工作室组成。如果没有顾客，理发师就去睡觉。如果顾客来时所有的沙发都有人，那么顾客就离去。如果理发师在忙而有空闲的沙发，那么顾客就会坐在其中的一个空闲的沙发上等待。如果理发师在睡觉，顾客会唤醒他。在理完发后，顾客必须付费，直到理发师收费后才能离开理发店。请利用信号量（semaphores），写个程序来协调理发师和顾客进程。4849写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日
展开阅读全文