资源预览内容
第1页 / 共99页
第2页 / 共99页
第3页 / 共99页
第4页 / 共99页
第5页 / 共99页
第6页 / 共99页
第7页 / 共99页
第8页 / 共99页
第9页 / 共99页
第10页 / 共99页
亲,该文档总共99页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第 4 章 进程的同步和死锁,4.1 进程的同步和互斥,4.1.1 进程的同步 1.进程同步举例 例.公共汽车中的司机和售票员。,司机 P1 售票员 P2 while (true) while (true) 启动车辆; 关门; 正常运行; 售票; 到站停车; 开门; ,4.1 进程的同步和互斥,2.进程同步的概念 进程的同步是指系统中多个进程中发生的事件存在某种时序关系,需要相互合作,共同完成一项任务。具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后被唤醒进入就绪态。 通常,把共同完成一个任务的若干进程称为合作进程。合作进程在并发执行时必须同步推进才能得到正确的执行结果。,4.1 进程的同步和互斥,4.1.2 进程互斥 1.进程互斥举例 假定系统中只有一台打印机,进程p1,p2都需要使用打印机,如果让它们同时使用,则两个进程的输出交织在一起,打印出的结果无法使用。 为了解决这一问题,进程使用之前先要提出申请,一旦系统将打印机分配给它,就一直由它独占使用,其它申请使用打印机的进程则必须等待。 进程p1和p2在逻辑上完全独立,毫无关系,只是由于竞争同一个物理资源而相互制约。这种进程之间的间接制约关系不具有时间次序的特征,谁先向系统提出申请,谁就先执行。这种对共享资源的排他性的使用关系就是进程的互斥关系。,4.1 进程的同步和互斥,2.临界资源 在计算机的资源中,有些资源,如上面提到的打印机资源,一次能被一个进程使用,这类资源称为临界资源(Critical Resource)。 临界资源可能是硬件,也可能是软件:变量,数据,表格,队列等。它们虽然可以被若干个进程所共享,但一次能为一个进程所利用。 为了保证共享临界资源的各个进程能正确运行,当临界资源由一个进程占用后,其它进程如果要使用它,必须等待占用进程使用完毕并把它释放后,才能由另一个进程使用。多个进程在共享临界资源时的这种制约关系称为进程的互斥。,4.1 进程的同步和互斥,3.临界区的概念 一个程序片段的集合,这些程序片段分散在不同的进程中,对某个共享的数据结构(共享资源)进行操作。在进程中涉及到临界资源的程序段叫临界区或临界段。 对临界区操作的诸进程必须互斥地进入临界区。,4.1 进程的同步和互斥,临界区是对某一临界资源而言的,对于不同临界资源的临界区,它们之间不相交,所以不必互斥地执行,而相对于同一临界资源的若干个临界区,则必须互斥的进入,即对临界资源的操作必须互斥地执行。 例如有程序段A、B是关于变量X的临界区,而C、D是关于变量Y的临界区,那么,A、B之间需要互斥执行,C、D之间也要互斥执行,而A与C、B与D之间不用互斥执行。,4.1 进程的同步和互斥,临界区进入准则: 空闲让进。当无进程处于临界区时,表明临界资源处于空闲状态,应允许一个请求进入临界区的进程立即进入自己的临界区。 忙则等待。当已有进程进入临界区时,表明临界资源正在被访问,因而其他试图进入临界区的进程必须等待。 有限等待。对任何要求访问临界资源的进程,应保证在有限的时间内能进入自己的临界区,以免陷入“死等”状态。 让权等待。当进程不能进入自己的临界区,应立即放弃占用CPU,以使其他进程有机会得到CPU的使用权,以免陷入“忙等”。,4.1 进程的同步和互斥,4.进程同步和互斥的区别 互斥的各个进程在各自单独执行时都可以得到正确的运行结果,但是当它们在临界区内交叉执行时就可能出现问题。 而同步的各个进程,如果各自单独执行将不会完成作业的特定任务,只要当它们互相配合、共同协调推进时才能得到正确的运行结果。 互斥的进程只要求它们不能同时进入临界区,而至于哪个进程先进入则不会产生运行的错误。但同步的进程的协调关系是建立在它们之间执行时序的基础上,所以,各个进程必须按照严格的先后次序执行。 一般情况下,互斥的进程并不知道对方的存在,而同步的进程不仅知道其它进程的存在,还要通过与其它进程的通信来达到相互的协调。,4.1 进程的同步和互斥,4.1.3 信号量机制 信号量(Semaphore)机制是荷兰学者E.W.Dijkstra在1965年提出的一种解决进程同步、互斥问题的更通用工具,并在THE操作系统中得到实现。 信号量S是个整数变量,除了初始化外,它只能通过两个标准的原子操作wait和signal来访问。这两个操作原来被称为P(用于wait,表测试)和V(用于signal,表增加)操作。,4.1 进程的同步和互斥,wait的经典定义可用伪代码表示为: wait(s) while (s=0) ; / no.op s - - . .; signal的经典定义可用伪代码表示为: signal (s) s + +; ,4.1 进程的同步和互斥,1.信号量的使用 可使用信号量来解决n个进程的临界区问题。这n个进程共享一个信号量mutex,并初始化为1。每个进程Pi的组织结构如下:,wait(mutex) 临界区(CS) signal(mutex),4.1 进程的同步和互斥,也可以使用信号量来解决各种同步问题。例如,考虑两个正在执行的并发进程:p1有语句s1,而p2有语句s2。假设要求只有在s1执行完之后才执行s2,可以很容易地实现这一要求:让p1和p2共享一个共同信号量synch,且初始化为0。 在进程p1中插入语句: s1; signal (synch); 在进程p2中插入语句: wait(synch); s2;,4.1 进程的同步和互斥,2.信号量的实现 上面定义的信号量虽然能够用来解决进程的同步和互斥问题,但存在一个明显的缺陷,即该机制没有遵循“让权等待”的原则,而是使进程处于“忙等”状态。 为了克服这个缺点,可定义一个结构体信号量: typedef struct int value; struct process *L; /进程链表 semaphore;,4.1 进程的同步和互斥,信号量操作wait现在可按如下来定义: void wait (semaphore S) S.value - -; if (S.value 0) add this process to S.L; block(); 信号量操作signal现在可按如下来定义: void signal (semaphore S) S.value + +; if (S.value = 0) remove a process P from S.L; wakeup(P); ,4.1 进程的同步和互斥,信号量的说明: 在信号量的实现中,S.value的初值表示系统某类资源的数目,因而又称为资源信号量,对它的每次wait操作,意味着进程请求一个单位的该类资源。 当S.value0时,表示该类资源已分配完毕,因而进程调用block原语,进行自我阻塞,放弃处理机,并插入到信号量链表S.L中。此时,S.value的绝对值表示在该信号量链表中已阻塞进程的个数、亦即恰好等于对信号量S实施wait操作而被封锁起来并进入信号量S队列的进程数。 对信号量的每次signal操作,表示执行进程释放一个单位资源。,4.1 进程的同步和互斥,3. AND型信号量 (1)问题的引入 假定有两个进程A和B,它们都要求访问共享数据D和E。当然,共享数据都应作为临界资源。为此,可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex,并令它们的初值都是1。相应地,在两个进程中都要包含两个对Dmutex和Emutex的操作,即 process A: process B: wait (Dmutex); wait(Emutex); wait (Emutex); wait(Dmutex); 若进程A和B按下述次序交替执行wait操作: process A: wait(Dmutex);于是Dmutex=0 process B: wait(Emutex);于是Emutex=0 process A: wait(Emutex);于是Emutex=-1,A阻塞 process B: wait(Dmutex);于是Dmutex=-1,B阻塞,4.1 进程的同步和互斥,(2)AND型信号量的基本思想 上述例子出现死锁的原因主要在于进程运行时需要多个资源,在为每个进程分配所需的全部资源时,不能保证原子操作,从而导致进程之间相互等待对方释放所占资源的死锁状态。为了解决进程同时需要多种资源且每种资源要占用一段时间的问题,人们提出了AND型信号量同步机制。 AND型信号量的基本思想:将进程在整个运行过程中需要的所有资源,一次性全部地分配给进程,待进程使用完后再一起释放。只要尚有一个资源未能分配给进程,其他所有可能为之分配的资源,也不分配给它。亦即,对若干个临界资源的分配,采取了原子操作方式:要么全部分配给进程,要么一个也不分配。,4.1 进程的同步和互斥,AND型信号量wait原语为Swait,其定义如下: Swait(S1, S2, , Sn) if(S1 =1 ,4.1 进程的同步和互斥,AND型信号量集signal原语为Ssignal, 其定义如下: 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进入某等待队列; ,4.1 进程的同步和互斥,引入AND信号量后,上面的例子就可以简单改写为: process A: process B: Swait(Dmutex,Emutex); Swait(Emutex,Dmetux); Ssignal(Dmutex,Emutex); Ssignal(Emutex,Dmutex); 这样也就不会出现死锁问题。,4.1 进程的同步和互斥,4. 信号量的应用 利用信号量可以很好的解决进程之间的同步问题。一般同步问题可分为两类:一类是保证一组合作进程按逻辑需要所确定的次序执行;另一类是保证共享缓冲区(或共享数据)的合作进程的同步。 (1)合作进程的执行次序 若干个进程为了完成一个共同任务而并发执行,然而,这些并发进程之间根据逻辑上的需要,有的操作可以没有时间上的先后次序,即不论谁先做,最后的计算结果都是正确的。但有的操作有一定的先后次序,也就是说它们必须遵循一定的同步规则,只有这样,并发执行的最后结果才是正确的。,4.1 进程的同步和互斥,为了描述方便,可以用一个图来表示进程集合的执行次序。图的连接描述了进程开始和结束的次序约束。此图称为进程流图。如果用s表示系统中某一任务启动,f表示完成,则可以下列的进程流图来表示这一组合作进程执行的先后顺序。,4.1 进程的同步和互斥,例题:假设某个程序段包含如下语句: int a,b,c,d,e,f; int t1,t2,t3,t4,t5; t1=a+b; t2=c+d; t3=e/f; t4=t1*t2; t5=t4-t3;,4.1 进程的同步和互斥,例题4-1:进程pa,pb,pc为一组合作进程,其进程流图如右图所示,使用信号量机制来实现这三个进程的同步。,分析: 从图可以看出,进程pb、pc只有在进程pa执行完成以后才能执行,进程pb、pc可以并发执行。 为确保这三个进程的执行顺序,设两个同步信号量SB、SC分别表示进程pb
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号