搜索
第5章并发进程及死锁本章6学时第5章主要教学内容5.1并发进程之间的制约关系5.2用信号量机制实现进程的同步与互斥5.3进程通信5.4死锁5.1并发进程(线程)之间的制约关系在多道系统(多线程)环境中，由于资源共享与进程合作，使得并发执行的进程之间可能产生相互制约关系，这些制约关系可分为两类：竞争与协作。竞争关系体现为进程互斥(排挤：要是你们都死光，光剩我一个就好了)协作关系体现为进程同步(配合：没你们我还真办不成事)多线程——至少俩程序1Y=Y+1output程序2Y=Y+2output内存共享区Ypcb1pcb2并发进程之间的制约(同步？互斥？)关系举例：要点：1.read/write2.lvalue5.1.1并发进程之间的同步关系进程同步是完成同一任务的伙伴进程间因需要在某些位置上协调(领导对下属、master对workers、同事之间)它们的工作或相互交换信息(环节之间)所产生的进程之间的直接制约关系。1.什么是进程同步进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤醒。2.同步关系分类同步关系一般分为两类：A类是一组合作进程因逻辑上所要求的执行顺序而引起的同步，即多个进程的并发过程中，在某些点上有着某种时序上的先后关系(同事之间、领导对下属、master对workers)B类是共享缓冲区的合作进程而引起的同步(环节之间)A类：人跟人打交道B类(比较宅)：我只跟物打交道人——线程；物——数据进程P2进程P1计算f1(x)置计算完成标志终止计算f2(x)P1算完f1(x)?取用P1的计算结果汇总终止YN图5.1两个合作进程P1与P2之间的同步例5-1：有个作业，其任务是计算：z=f1(x)+f2(y)其中的f1(x)和f2(y)均是一个复杂的函数。非对称同步：主线程P2创建一个新线程P1执行函数调用f1(x)，自己执行f2(x)与加法、赋值例5-2：假定进程A专门负责启动卡片输入机，每读入一张卡片后，将卡片数据送到缓冲区；进程B则专门负责将缓冲区的卡片数据输出到磁盘存储，如果有一叠卡片需要进程A、B合作进行处理，显然，进程A和进程B之间必须保持同步操作才能正确地完成任务。如图5.2所示。输入进程A缓冲区输出进程B图5.2共享缓冲区的合作进程之间的同步对称同步5.1.2并发进程之间的互斥关系1.什么是进程互斥进程互斥是指若干进程都要使用同一个临界资源(criticalresource)时，任何时刻最多允许一个进程使用，其它要使用该资源的进程必须等待，直到占有资源的进程释放该资源。Acriticalsituationisveryseriousanddangerous.是危险、关键的意思。好奇怪的名字进程互斥是并发进程之间因相互竞争使用资源(临界资源)所产生的间接制约关系。2.临界资源和临界区（1）临界资源(CriticalResource)：把一次只允许一个进程使用的资源称为临界资源。如：独占性硬件资源卡片输入机、打印机等；若干个并发进程共享的变量、表格、队列、栈、文件等软件资源也是临界资源。（2）临界区(Criticalsection)把每个进程中访问临界资源的那段代码称为临界区。即临界区是指对临界资源实施操作的程序代码段。（3）相关临界区相关临界区是指并发进程中涉及相同临界资源的临界区。显然，相关临界区必须互斥执行。例5-3：进程间争夺资源R而导致一方使用结束后另一方才可使用。使用R（阻塞）图5.3资源互斥使用示例①请求R③释放R进程P1进程P2②请求R④释放R资源R分配拒绝唤醒3.相关临界区的管理原则（1）对于临界区的协调的准则是：①当有若干个进程同时要求进入临界区时，应在有限时间内使一个进程进入(两个司机可以互不相让，但交警必须分出高低)②每次最多有一个进程处于相关临界区内③进程在临界区内应逗留有限时间(人家要是进去偏不出来你os还有啥办法？这是程序员的责任！)程序员的责任（2）遵循以上准则，得到临界区的调度原则是：①当无进程处于临界区内时，允许一个进程立即进入；②已有进程在临界区时，其它试图进入临界区的进程必须等待；③当一个进程离开临界区时，若还有等待者进程，则允许其中一个等待者进入临界区。操作系统的责任4.实现临界区互斥的锁操作法通过对相关临界区进行加锁和开锁是一种最简单的实现进程互斥的机制。用一个锁变量W来代表某种临界资源的状态：W=0表示资源空闲可用；W=1表示资源正被使用。对临界区使用之前应测试W值，若W=1表示资源已被占用，返回重新测试；若W=0则表示资源可用。在使用临界资源之前为了防止别的进程进入，设置W=1(关锁)；若临界资源使用完后退出临界区时，设置W=0(开锁)，这样别的进程就可以使用该临界资源了。在火车上上厕所，你不锁门会发生什么事？卫生间——criticalresource（1）加锁和开锁原语加锁原语lock(W)可描述为：L：ifW=1thengotoLelseW=1；开锁原语unlock(W)可描述为：W=0（2）用加锁和开锁原语解决进程互斥的模型设n个进程P1，P2，…，Pn的相关临界区分别为CS1，CS2，…，CSn，只要在每个进程的临界区两端放上加锁和开锁原语即可实现临界区互斥。W初值为0，表示临界资源空闲可用，互斥的模型如右：Pi（i=1,2,3,…,n）……LOCK(W)CSiUNLOCK(W)……举例(W初值为0）P1初始化程序的其它部分代码开锁lock（W）Lock（W）访问临界资源代码程序的其它部分W≠0W=1P2初始化程序的其它部分代码开锁lock（W）Lock（W）访问临界资源代码程序的其它部分W≠0W=1W=0W=0欢迎来到卫生间5.2用信号量机制实现进程的同步与互斥5.2.1信号量机制5.2.2利用信号量机制实现进程互斥5.2.3利用信号量机制解决进程的同步5.2.4经典的同步与互斥问题5.2.1信号量机制1.信号量的含义2.P、V操作的定义3.信号量和P、V操作的物理意义1.信号量的含义概念上，信号量是表示物理资源数量的实体，它是一个与队列有关的整型变量。实现上，信号量是一种记录型数据结构(结构体)，有两个分量：一个是信号量的值，另一个是等待该信号量的进程队列的头指针。图5.4信号量的结构和含义信号量的值(-2)信号量队列指针PCBiPCBj信号量按其用途分为两类：公用信号量：与公用信号量联系的一组并发进程均可对它实施P、V操作。私有信号量：只允许信号量的拥有者进程对它实施P操作，与信号量的拥有者进程合作的进程对它实施V操作。信号量按其取值分为两类：二元信号量：信号量只能取0,1两个值一般信号量：取值范围：…，-3，-2，-1,0,1,2,3，…2.P、V操作的定义设S为信号量，q为对资源S操作的进程，Q为S的等待队列。（1）P操作原语P(S)可描述为：①S=S-1；②若S≥0，则调用P（S）的进程q继续运行；③若S＜0，则调用P（S）的进程q将进入阻塞状态，并放入S的等待队列Q中。（2）V操作原语V(S)可描述为：①S=S+1；②若S＞0，则调用V（S）的进程q继续运行；③若S≤0，则从S的等待队列中唤醒头一个进程，然后，调用V（S）的进程q继续运行。V操作不会影响调用它的线程，但P操作有可能3.信号量和P、V操作的物理意义（1）信号量（用S表示）是代表资源的实体，是一个与进程队列Q有关的整形变量，除信号量的非负初值外，信号量的值只能由P操作和V操作来改变。操作系统利用信号量实施对进程的控制和对资源的管理。3.信号量和P、V操作的物理意义（2）信号量S的取值表示系统中某类资源的数目。当S0时：(有现货——只要888，xx带回家)其值表示系统中当前可用的某类资源数量；当S=0时：(无现货)表示系统中当前已无某类资源可用；当S0时：(无货也要预售——雷布斯)其绝对值表示系统中因请求该类资源而被阻塞的进程数量或登记排列在该信号量s队列之中等待的进程个数。3.信号量和P、V操作的物理意义（3）通常，P操作意味着请求一个资源，因此描述为S=S-1；V操作意味着释放一个资源(二手机？资源是可回收的)，因此描述为S=S+1。S=0时，P操作必定导致调用进程阻塞；S0时,V操作必定唤醒某个阻塞进程；3.信号量和P、V操作的物理意义（4）P操作原语为请求资源而设，V操作原语为释放资源而设；P操作即可充当资源申请原语的作用，也可以充当进程阻塞原语的作用(谁没事会阻塞自己？二元信号量——当开关用。卫生间)；V操作即可充当资源释放原语的作用，也可以当作进程唤醒原语的作用；在整个系统中，P、V操作必须成对出现。5.2.2利用信号量机制实现进程互斥的模型设n个进程P1，P2，…，Pn的相关临界区分别为CS1，CS2，…，CSn，只要在每个进程的临界区两端放上P、V操作原语即可实现临界区互斥。假设信号量S的初值为1，则，互斥的模型如下：Pi（i=1,2,3,…,n）……P（S）Csi(临界区)V（S）……所谓临界资源——就这一个资源，大家还不能同时用——卫生间。利用信号量机制实现进程互斥的模型：s:semaphore;s:=1;cobegin……processPibegin……P(s);临界区；V(s);……end;……coend;这是站在整个系统(将操作系统、所有用户进程视为一体)的角度来看发生的事情例5-5（互斥问题）民航售票系统有n个售票处，各个售票处均需访问公共数据区存放的现有票数。试用信号量和P、V操作控制n个并发的售票进程的正确执行。分析：假定公共数据区Aj(j=1,2,…,m)存放X月X日X次航班的现有票数，那么，只要把公共数据区Aj当作临界资源对待，n个并发售票进程互斥访问临界区即可。信号量和PV操作解决机票问题VarA:ARRAY[1..m]OFinteger;S:semaphore;S:=1;cobeginprocessPi（I=1,2,…,n)varXi:integer;beginL1:按旅客定票要求找到A[j]；P(S)Xi:=A[j];ifXi=1{Xi:=Xi-1;A[j]:=Xi;V(S);输出一张票；}else{V(S);输出票已售完；}gotoL1;coend;5.2.3利用信号量机制解决进程的同步模型设信号量S的初值为0，P1与P2同步的模型如下：进程P1L1：V（S）．．．．．．进程P2．．．．．．L2：P（S）说明：进程P1在L1点完成了P2等待的事件，调用V（S）操作；进程P2在L2点检测事件是否发生调用P（S）操作。一开始就没有“资源”，而P2需要一个资源例5-6：(同步问题）设3个合作进程P1，P2，P3。要求P1和P2可以并发执行，但P1，P2结束以后，P3才可以执行。用信号量机制实现P1，P2，P3的同步。为了描述方便，可以用一个图来表示进程集合的执行次序。其中S表示系统中某一任务的开始，F表示系统中某一任务的完成。如图5.5所示。用信号量机制实现P1，P2，P3的同步描述如下：SFP1P2P3图5.5进程P1、P2和P3的关系BeginS1=S2=0;//两个二元信号量CobeginProcessP1BegindoallworkV(S1)//我完了EndProcessP2BegindoallworkV(S2)//我也完了EndProcessP3BeginP(S1)//我就等你俩呢P(S2)doallworkEndCoendEnd把P1、P2、P3画成带箭头的线，而不是节点，更有thread的感觉。5.2.4经典的IPC问题1.生产者--消费者问题有界缓冲区问题的建模2.读者--写者问题数据库互斥访问问题的建模3.理发师问题CS模式进程同步问题的建模4.哲学家进餐问题多进程同步导致死锁问题的建模进程通信（IPC）进程间的关系完全无关（异步）：不同进程间无任何关联使用共享数据（互斥）：应有效保护各