《【教学课件】第三章进程管理.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第三章进程管理.ppt（130页珍藏版）》请在三一办公上搜索。
1、,第三章 进程管理,3.1 为什么要引入进程的概念 3.2 进程的表示和调度状态 3.3 进程的控制 3.4 进程调度 3.5 线程及其管理 3.6 进程通讯 3.7 死锁,3.1 为什么要引入进程的概念,3.1.1 从顺序程序设计谈起,图 3.1 程序的顺序执行,程序的顺序执行具有如下特性：(1)当顺序程序在处理机上执行时，处理机严格地顺序执行程序规定的动作。每个动作都必须在前一动作结束后才能开始。除了人为的干预造成机器暂时停顿外，前一动作的结束就意味着后一动作的开始。程序和机器执行程序的活动严格一一对应。(2)一个程序在机器中执行时，它独占全机资源，除了初始状态外，只有程序本身规定的动作才
2、能改变这些资源的状态。(3)程序的执行结果与其执行速度无关。,3.1.2 程序的并发执行和资源共享,1.程序的并发执行,图 3.2 程序段并发执行的有向图,在该例中I1先于C1和I2;C1先于P1和C2;P1先于P2;I2先于C2和I3。说明了某些程序段必须在其它程序段之前完成，此外从图中可以看出：I2和C1;I3和C2和P1;I4和C3和P2;是重叠的。,2.资源共享 资源共享是现代操作系统另一基本特性。所谓资源共享是指系统中的硬件资源和软件资源不再为单个用户程序所独占，而由几道用户程序共同使用。于是，这些资源的状态不再取决于一道程序，而是由多道程序的活动所决定。这就从根本上打破了一道程序封
3、闭于一个系统中执行的局面。程序并发执行和资源共享之间互为依存条件。一方面，资源共享是以程序并发执行为条件的，因为若系统不允许程序并发，也就不存在资源共享问题；另一方面，若系统不能对共享资源进行有效的管理，也就降低了程序并发执行的效果。,3.1.3 程序并发执行的特性,1.失去了程序的封闭性,设有观察者和报告者并行工作。在一条单向行驶的公路上经常有卡车通过。观察者不断观察并对通过的卡车计数。报告者定时地将观察者的计数值打印出来，然后将计数器重新清“0”。此时我们可以写出如下程序，其中Cobegin和Coend表示它们之间的程序可以并发执行。,begin countinteger;count=0;
4、cobegin,observer begin L1；observe next car;count=count+1;go to L1 end reporter begin L2:print count;count=0 go to l2 end coendend,由于观察者和报告者各自独立地并行工作，count=count+1 的操作，既可以在报告者的print count和count=0 操作之前，也可以在其后，还可以在print count和count=0 之间。即可能出现以下三种执行序列：(1)count=count+1;print count;count=0;(2)print count;
5、count=0;count=count+1;(3)print count;count=count+1,count=0。,假设在开始某个循环之前，count的值为n，则在完成一个循环后，对上述三个执行序列打印机打印的count值和执行后的count值如下表所示：,2.程序和机器执行程序的活动不再一一对应 程序和机器执行程序的活动是两个概念。程序是指令的有序集合，是静态的概念；而机器执行程序的活动是指指令序列在处理机上的执行过程，或处理机按照程序执行指令序列的过程。通常把机器执行程序的活动，称为“计算”。3.并发程序间的相互制约 资源共享和程序的并发执行(或称并发活动)使得系统的工作情况变得相当错
6、综复杂，尤其表现在系统中并发程序间的相互依赖和制约方面。,3.1.4 进程概念的引入,(1)行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程(Dijkstra)。(2)一个进程是一系列逐一执行的操作，而操作的确切含义则有赖于我们以何种详尽程度来描述进程(Brinch.Hansen)。(3)进程是这样的计算部分，它可以与别的进程并发执行(Madnick and Donovan)。(4)顺序进程(有时称为任务)是一个程序与其数据集一道顺序通过处理机的执行所发生的活动(Alan C.Shaw)。(5)一个进程是由伪处理机执行的一个程序(J.H.Saltzer)。,3.2 进程的表示和
7、调度状态,3.2.1 进程的表示,1.进程的组成,图 3.3 进程的表示,2.进程控制块,为描述进程的动态变化，便于系统对进程进行有效的控制和管理，系统中为每一进程设置一个进程控制块。进程控制块是进程存在的一个惟一标志。当系统创建一个进程时，系统为其建立一个PCB，当进程被撤消时，系统收回它的PCB，随之该进程也就消亡了。,在通常的操作系统中，PCB应包含如下一些信息：进程标识名或标识数。(2)位置信息。(3)状态信息。(4)进程的优先级。(5)进程现场保护区。(6)资源清单。(7)队列指针或链接字。(8)其它。,3.2.2 进程的调度状态,1.进程的基本调度状态,运行状态。(2)就绪状态。(
8、3)阻塞状态。,图 3.4 进程的基本调度状态及其转换,2.细分的进程调度状态,图 3.5 细分的进程状态转换图,图 3.6 具有挂起操作的进程状态转换图,3.3 进 程 的 控 制,3.3.1 进程的控制机构,1.原语的定义 所谓“原语”，是指由若干条机器指令构成的并用以完成特定功能的一段程序，这段程序在执行期间是不可分割的。,2.进程控制原语 操作系统的内核是操作系统中最接近裸机的部分。通常内核只占整个操作系统代码中的一小部分。内核的各项功能是通过执行原语来实现的。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其它方面的原语。属于进程控制方面的原语有进程创建原语、进程
9、撤消原语、进程挂起原语、进程激活原语、进程阻塞原语以及进程唤醒原语等。,3.3.2 进程控制原语,1.进程的建立,图 3.7 进程的树型结构,树型结构系统的主要优点是：资源分配严格。(2)进程控制灵活。(3)进程层次清晰，关系明确。,创建原语的功能是用来创建子进程。其具体作法是：先向PCB集合索取一张空白PCB，并获得PCB的内部标识数。若该进程的程序不在内存，应将其调入内存。然后，把创建者提供的PCB参数(如进程外部标识名，初始CPU状态，优先数及资源清单等)以及父进程的内部标识数填入PCB中，并设置记帐信息，再置该进程状态为“静止就绪”，最后把它插入进程家族和就绪队列中。这样，子进程就建立
10、起来了。,2.状态转换原语(1)挂起原语。当需要把某个进程挂起时可调用挂起原语。挂起原语的具体作法是：以被挂起的进程标识名为索引，到PCB集合中查找该进程的PCB，得到该进程的内部标识数，并检查该进程的状态。若状态为“运行”，则中断处理机，把CPU状态保存在PCB中，停止运行该进程；若状态为活跃阻塞，则改为静止阻塞；若状态为活跃就绪，则改为静止就绪；若状态为运行，则从活跃就绪队列中按某种算法选一进程投入运行。,(2)激活原语。在挂起原语的作用下，进程的状态由活跃转为静止。激活原语则使处于静止状态的进程变成活跃，即把“静止就绪”变成“活跃就绪”，把“静止阻塞”变成“活跃阻塞”。一旦被激活的进程处
11、于“活跃就绪”时，便引起处理机的重新调度。激活原语只能激活某进程自己的子孙。同样，激活原语也可以有多种激活方式：如激活一个具有指定标识名的进程，或者激活某进程及其所有的子孙进程。由创建原语所创建的子进程处于“静止就绪”，若希望该进程尽快获得处理机，应在创建原语后紧跟一个激活原语，使之变成活跃就绪，从而引起调度程序的重新调度。,(3)阻塞原语和唤醒原语。由运行到活跃阻塞，由活跃阻塞到活跃就绪通常是在资源管理原语“请求”和“释放”的作用下完成的。但在有的系统中，使用了阻塞原语和唤醒原语完成上述状态的转换。当一进程所期待的某一事件尚未出现时，该进程调用阻塞原语把自己阻塞起来，阻塞原语的操作过程如下：
12、由于进程正处于运行状态，故应中断处理机，把CPU状态保护到PCB中，停止运行该进程。然后把“活跃阻塞”赋予该进程，并把它插入到该事件的等待队列中，再从活跃就绪队列中按一定算法选取一进程投入运行。,3.进程的撤消 当一个进程在完成其规定的任务后，应予以撤消。撤消也有两种方式：仅撤消一个具有指定标识名的进程，或撤消该进程及其所有子孙。前者可能导致被撤消的进程子孙与进程家族隔离，成为不可控的。因此，撤消原语应采用第二种方式。撤消原语的操作过程如下：以调用者提供的进程标识名为索引，到PCB集合中寻找相应的PCB，获得该进程的内部标识数和状态。若该进程处于运行状态，则中断处理机，保护CPU现场，停止执行
13、该进程，并设置重新调度标志。根据状态指出的该进程所在队列，将其从队列中消去。而且凡属于该进程的所有子孙也一律撤消。对于被撤消者所占有的资源，若它们是属于撤消者或其祖先的，都应归还。凡是属于被撤消者自己的，则消去它的资源描述块，最后消去被撤消者的PCB，若重新调度标志已置位，则重新调度。,3.4 进程调度,3.4.1 交通控制程序和进程调度程序1.交通控制程序,交通控制程序(Traffic Controller)是J.H.Saltzer于 1966 年起的名字。他把操作系统中指挥各个进程的工作比作一个交通警察，而把各个进程比作车辆。它们之间有时要竞争，有时要合作，交通警察就要保证它们协调一致，互
14、不冲突。在操作系统中，交通控制程序的主要职能是管理进程状态之间的转变和协调进程间的通讯。,2.进程调度程序 在进程状态的变化中，从就绪到运行的转变是由一个专门的程序来完成的，该程序称为进程调度程序。进程调度称为“低级”调度，是相对作业调度而言的。进程调度程序所要完成的是把一台物理的CPU转变为多台虚拟的CPU或者多台逻辑的CPU。,3.进程调度程序的功能(1)记住系统中所有进程的状态、优先数和资源需求情况。对于动态优先数，还须按一定算法定期地对它进行计算。(2)确定调度算法，决定把处理机分配给哪个进程和分配多长时间。某个进程正在运行时，如果有优先级更高的进程进入就绪队列，是继续运行原进程还是分
15、配处理机给优先级更高的进程，由调度方式确定。(3)分配处理机给进程。,3.4.2 进程调度算法的设计,1.引进进程调度的时机 当发现下述情况时，现运行进程使用的处理机被收回。(1)现运行进程运行结束或者因任务完成而正常结束，或者因出现错误而异常结束。(2)现运行进程因某种原因，比如I/O请求，从运行进入阻塞状态。(3)现运行进程执行某种原语操作，如P操作、阻塞原语等，进入阻塞状态。(4)一个具有更高优先级的进程要求使用处理机，即进入就绪队列。(5)分配给该进程运行的时间片已用完。,2.进程调度方式 所谓进程调度方式，是指当一个进程正在处理机上运行时，若有某个更为紧迫或更为重要的进程需要进行处理
16、，或者说，如果有更高优先级的进程进入就绪队列时，如何分配处理机。通常有两种进程调度方式：(1)非剥夺方式。(2)剥夺方式。,3.进程调度算法的选择,进程调度的主要任务就是按照一定的调度算法从就绪队列中选出一个进程，把CPU分配给它。调度算法的选择与系统的设计目标和系统工作效率密切相关。例如，有的算法有利于系统资源的充分作用，有的算法有利于系统处理能力的充分发挥，有的算法有利于公平地响应用户的服务请求，如此等等。与作业调度算法的选择类似，进程调度算法的选择也要综合各方面的因素，从中选择一种切合实际、行之有效的算法。进程调度算法基本分为两大类：优先数法和时间片轮转法，,4.进程队列的组织,图 3.
17、8 PCB的组织方式,3.4.3 常用的进程调度算法,1.静态优先级法,按进程类型确定。(2)按作业的资源要求确定。(3)按作业到达时间确定。(4)按用户类型和要求确定。,2.动态优先级法,3.时间片轮转法,在时间片轮转法中，时间片是一个重要的参数。系统的响应时间和时间片的关系，可以表示为：T=Nq，其中T为系统的响应时间，q为时间片的大小，N为就绪队列中的进程数。显然，时间片的大小对进程调度有很大影响。如果q取得足够大，以致所有进程都能在分得的一个时间片内执行完毕，则此时的轮转法就变成了FCFS法。这对于短作业，对于I/O操作多的作业都很不利。q的减小，可使调度效果得到改善，但是，q值很小时
18、，则从一个进程到另一个进程的转换时间就不可忽略。换言之，过小的q值会导致系统开销的增加。因此，时间片的选择必须适当，通常为 100 ms。,时间片的长短通常由以下因素确定：(1)系统的响应时间；(2)就绪队列中的进程数；(3)进程的转换时间；(4)计算机的处理能力，计算机的速度越高，时间片就可越短。简单轮转法的优点是方法简单，但由于采用固定时间片和仅有一个就绪队列，故服务质量不够理想。为进一步改变轮转法的调度性能应作两方面改进：将固定时间片改为可变时间片；将单就绪队列改变为多就绪队列。,可变时间片轮转法，可采用如下措施：(1)系统的响应时间固定，每次计算就绪队列中的进程数，记为Nmax，则时间
19、片为q=T/Nmax。在这种方式中，每一轮开始时，系统便根据就绪队列中已有的进程数，计算一次q值，然后进行轮转。在此期间所到达的进程都暂不进入就绪队列，等此次轮转完毕再一并进入。系统根据此时就绪队列中的进程数重新计算q值，然后开始下一轮循环。这种方法称为固定周期轮转法。,(2)时间片的长短取决于优先级的高低。优先级高的进程分得的时间片长，优先级低的进程分得的时间片短。(3)短作业的时间片短，长作业的时间片长。,3.4.4 作业、进程和程序之间的区别和联系,1.用户作业、进程和程序之间的联系 所谓一个作业，就是用户在一次算题过程或一个事务处理中要求计算机系统所做工作的总和。在一个多道程序并发执行
20、的系统中，一个作业就是独立于其它作业的工作单位。一个用户作业通常包括程序、数据和操作说明书三部分。,2.进程和程序的区别,(1)进程是程序的一次执行，属于一种动态概念，而程序是一组有序的指令，是一种静态概念。(2)一个进程可以执行一个或几个程序；反之，同一程序可能由几个进程同时执行。(3)程序可以作为一种软件资源长期保留，而进程是程序的一次执行过程，是暂时的。(4)进程具有并发性，它能与其它进程并发运行。(5)进程是一个独立的运行单位，也是系统进行资源分配和调度的一个独立单位。,3.5 线程及其管理,3.5.1 线程概念的引入 3.5.2 什么是线程,线程可定义为“进程内的一个执行单位”，或者
21、定义为“进程内的一个可调度的实体”。在具有多线程机制的操作系统中，处理机调度的基本单位不是进程而是线程。负责处理机调度的程序称为线程调度程序，它是操作系统内核的重要组成部分，线程调度也是内核的主要功能之一。,1.线程的定义,2.进程和线程的关系(1)线程是进程的一个组成部分。每个进程在创建时通常只有一个线程，需要时这个线程可以创建其它线程。(2)进程的多线程都在进程的地址空间活动。(3)资源是分给进程的，而不是分给线程的，线程在执行中需要资源时，系统从进程的资源配额中扣除并分配给它。(4)处理机调度的基本单位是线程，线程之间竞争处理机，真正在处理机上运行的是线程。(5)线程在执行过程中，需要同
22、步。,3.5.3 Windows-NT中的进程和线程,1.Windows NT中的进程,(1)一个可执行的程序，它定义了初始代码和数据。(2)一个私用地址空间，即进程的虚拟地址空间。(3)系统资源，例如信号量、通信端口、文件等。它们是在程序执行时，由操作系统分配给它的。(4)至少有一个执行进程。,2.Windows NT中的线程 Windows NT中，线程和进程一样，也用对象来实现。线程由对象管理程序创建或删除。一个线程的基本组成是：(1)一个惟一的标识符，称之为客户ID。(2)描述处理机状态的一组寄存器内容。(3)两个栈，分别用于用户态和核心态下执行。(4)一个私用的存储区。,图 3.9
23、线程的调度状态及其转换,3.Windows NT中的线程调度,3.6 进 程 通 讯,3.6.1 进程间的同步和互斥,1.进程间的同步 一般来说，一个进程相对另一进程的运行速度是不确定的。也就是说，进程之间是在异步环境下运行的，每个进程都以各自独立的、不可预知的速度向运行的终点推进。但是相互合作的几个进程需要在某些确定点上协调它们的工作。一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等待这些操作的结束。这就是进程间的同步。,图 3.10 司机和售票员的同步,又如，有用户作业程序，其形式是：Z=func 1(x)*func 2(y)其中func 1(x)，func 2(
24、y)均是一个复杂函数，为了加快本题的计算速度，可用两个进程P1、P2 各计算一个函数。进程P2 计算func 2(y)，进程P1 在计算完func 1(x)之后，与进程P2 的计算结果相乘，以获得最终结果Z。,图 3.11 进程P1 和P2 间的同步,2.进程间的互斥,图 3.12 资源互斥使用例,又如，设有两个进程P1、P2，它们共享同一变量count,P1、P2 的主要操作如下：P1：R1=count;P2:R2=count;R1=R1+1;R2=R2+1;count=R1;count=R2;其中，R1 和R2 是处理机的两个通用寄存器。,它们可以按各自独立的速度前进，所以运行的顺序也可能
25、是：P1:R1=count;P2:R2=count;P1:R1=R1+1;count=R1;P2:R2=R2+1;count=R2;,3.实现临界区互斥的锁操作法(1)当有若干进程要求进入它们的临界区时，应在有限时间内使一进程进入临界区。换句话说，它们不应相互等待而致使谁都不能进入。(2)每次最多有一个进程处于临界区内。(3)进程在临界区内逗留应在有限时间范围内。,下面给出实现临界区互斥的锁操作法：这种方法使用了一个物理实体，称为锁，用W来表示。锁有两种状态：W=0 表示锁已打开；W=1 表示锁被关闭。加锁原语用LOCK(W)表示，其操作为：测试W，若W=1，表示资源正在使用，继续反复测试；若
26、W=0，置W=1(加锁)。加锁原语用LOCK(W)表示，可描述为 L:if W=1 then go to L else WKG-*8=1;开锁原语用UNLOCK(W)表示，可描述为 W=0；,于是，两个进程P1，P2使用如下程序实施进程的互斥：进程P1 进程P2 LOCK(W)LOCK(W)S1 S2UNLOCK(W)UNLOCK(W)其中S1和S2分别为进程P1 和P2 的临界区。,在有些系统中，上述的加锁、开锁操作可用机器硬件指令完成。例如IBM/370 中就有一条称为“测试并置位”指令TS。该指令的功能是按第二操作域指出的地址从主存中取出一个字节，其最高位(最左边的位)为 0 时，置条件
27、码为 0；否则置条件码为 1，并将该字节的所有位均置 1。于是加锁原语LOCK(W)可用指令TS WBNZ*-4,来代替，其中BNZ表示不等于 0 转移，*-4 表示本指令地址减 4(BNZ本身是 4 字节指令)。即当W不为 0 时转移到上一条指令TS继续测试，否则停止测试，进入临界区。请注意，测试W和置W=1 是在一个指令周期内完成的。开锁原语UNLOCK(W)用指令 MVI W，X00来完成，MVI将一个全 0 的字节送入W中。,3.6.2 信号量和P、V操作,1.信号量及P、V操作,信号量或信号灯，是交通管理中的一种常用设备。交通管理人员利用信号灯的颜色(红、绿)实现交通管理。在操作系统
28、中，信号量是表示资源的实体，是一个与队列有关的整型变量，其值仅能由P、V操作来改变。操作系统利用信号量对进程和资源进行控制和管理。根据用途不同，分为公用信号量和私用信号量。公用信号量通常用于实现进程之间的互斥，初值为 1，它所联系的一组并发进程均可对其实施P、V操作；私用信号量一般用于实现进程间的同步，初值为 0 或为某个正整数n，仅允许拥有它的进程对其实施P操作。,P、V操作是定义在信号量S上的两个操作，其定义如下：P(S)：S=S-1;若S0，则调用P(S)的进程继续运行；若S0，则调用V(S)的进程继续运行；若S0，从等待信号量S的阻塞队列中唤醒头一个进程，然后调用V(S)的进程继续运行
29、。,P、V操作可表示为如下两个过程：,Procedure P(Var S:Semaphore);begin S=S-1;if S0 then W(S)end;PProcedure V(Var S:Semaphore);begin S=S+1;if S0 then R(S)end;V,2.利用信号量实现进程的互斥 利用信号量可以方便地解决临界区问题。设S为两进程互斥的公用信号量，初值赋予 1，表明该临界资源未被占用。只需把临界区的程序段置于P(S)和V(S)之间，即可实现两进程的互斥。例如进程P1 和进程P2 按如下安排，即可实现互斥：,进程P1 进程P2P(S)P(S)S1 S2V(S)V(S
30、),例 1 前面例子中的公用变量count,也是一个临界资源。两个并发进程对count的操作必须互斥地执行。对此，可写出如下程序：,begin count:integer;S:semaphore;count=0;S=1;cobegin process p1 R1:register;begin P(S);,R1=count;R1=R1+1;count=R1;V(S)end;process P2 R2:register;begin P(S);R2=count;R2=R2+1;count=R2;V(S)end;coend;end;,例 2 设一民航航班售票系统有n个售票处。每个售票处通过终端访问系统
31、中的公用数据区，假定公共数据区中一些单元xk(k=1,2,)分别存放月日次航班的现存票数。设P1，P2，Pn表示各售票处的处理进程，R1,R2,Rn表示各进程执行时所用的工作单元。用信号量实现进程间互斥的程序如下：,beginS:Semaphore;S=1cobegin,Process Pi(i=1,2,n)begin按旅客订票要求找到xk;P(S)Ri=xk;if Ri1 then begin Ri=Ri-1;xk=R1;V(S)输出一张票 end else begin V(S);输出“票已售完”end end;coend;end;,3.利用信号量实现进程间的同步 一般来说，信号量初值为 0
32、，两个进程之间的同步模型如下：,进程P1 进程P2 L1：P(S)L2：V(S),例 1 用信号量实现司机和售票员的同步。设S1和S2分别为司机和售票员的私用信号量，初值均为0，则司机和售票员的同步过程描述如下：,例 2 设进程A、B是两个相互合作的进程，共用一个缓冲区。进程A负责从卡片输入机读入卡片送到缓冲区，进程B取走缓冲区中的卡片信息进行加工处理。进程A在完成将卡片送入缓冲区后，给进程B发一信号。进程B收到信号后，取走卡片信息进行加工处理。反之，进程B取走卡片信息后，给进程A发一信号，进程A再将卡片信息读入缓冲区。为此，我们利用两个私用信号量S1和S2，其初值均为 0，信号量S1表示缓冲
33、区是否有卡片信息，信号量S2表示缓冲区信息是否被取走。利用P、V操作实施进程A、B的同步过程如下：,4.生产者消费者问题(Producer-Consumer Problems),图 3.13 生产者消费者问题,了实现上述两组进程互斥地进入临界区，我们设置两个私用信号量和一个公用信号量如下：(1)公用信号量S，初值为 1，表示没有进程进入临界区，它用于实现进程互斥；(2)私用信号量S0，用以表示产品数目，初值为 0；(3)私用信号量Sn，用以表示可用缓冲区数，初值为n。生产者消费者进程描述如下：,生产者和消费者可按如下方式并发执行：,begin B:array0n-1 of integer;P,
34、R:integer;S,Sn,S0:semaphore;p=R=0 S=1;Sn=n;S0=0;cobegin process producer i(i=1,2,m)begin L1:produce a product;P(Sn);P(S);BP=product;P=(P+1)mod n;V(S0);,go to L1 end;process consumer j(j=1,2,k)begin L2:P(S0);P(S);take a product from BR;R=(R+1)mod n;V(Sn);V(S);consume go to L2 end coend;end;,5.读者与写者问题
35、(ReaderWriter Problems),为了实现读者与写者的同步和互斥，我们设置一个信号量S，用于读者与写者之间或写者与写者之间的互斥，初值为“1”。用一个变量rc表示当前正在读的读者个数，当进程可以去读或读结束后都要改变rc的值，因此rc又成为若干读进程的共享变量，它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr，初值也是“1”。读者写者问题可描述如下：,begin S,Sr:semaphore;rc:integer;S=Sr=1;rc=0;,cobegin process Reader i(i=1,2,m)begin P(Sr);rc=rc+1;if rc=1 then
36、 P(S);V(Sr);read file F;P(Sr)rc=rc-1;if rc=0 then V(S);V(Sr)end process Writer j(j=1,2,k),beginP(S);Write file F;V(S)end;coend;end,在这个程序中，当有进程在读而使一个请求写的进程阻塞时，如果仍有进程不断地请求读则写进程将被长期地推迟运行。但在实际的系统中往往希望让写者优先。即当有进程在读文件时，如果有进程请求写，那么新的读者被拒绝，待现有读者完成读操作后立即让写者运行，只当无写者工作时才让读者工作。下面是写者优先的程序。其中信号量S，初值为 1，用于读者与写者或写者
37、与写者之间的互斥，另一信号量Sn，初值为n,表示系统中最多有n个进程可同时进行读操作：,Begin S,Sn:Semaphore;S=1;Sn=n;cobegin process Reader i(i=1,2,n)beginP(S);P(Sn);V(S);read file F;V(Sn)end;process Writer j(j=1,2,k),beginP(S)for i=1 to n do P(Sn);Write file F;for i=1 to n do V(Sn);V(S)end;coend;end;,3.6.3 高级通讯原语,1.消息缓冲通讯 消息缓冲区作为进程间通讯的一个基本单
38、位。消息缓冲区是包含如下信息的缓冲区：发送者进程标识符：sender消息长度：size消息正文：text指向下一消息缓冲区的指针：next,当一个发送进程欲发送消息时，便形成一个消息，并发送给指定的接收进程。由于接收进程可能会收到几个进程发来的消息，故应将所有的消息缓冲区链成一个队列，其队头由接收进程PCB中的队列队首指针mq来指出。此外在PCB中还应增加如下的数据项：消息队列队首指针：mq消息队列互斥信号量：mutex消息队列资源信号量：Sn,图 3.14 消息缓冲通讯,2.信箱通讯 信箱用于存放信件，而信件是一进程发送给另一进程的消息。1)信箱通讯过程,图 3.15信箱通讯方式,2)信箱的
39、数据结构 信箱是一种数据结构，逻辑上可分为两部分：信箱头和信箱体。信箱头是信箱的描述部分；信箱体由若干格子组成，其中每一格子可存放一个信件。信箱头包括如下信息：信箱名：boxname;信箱大小：boxsize;已存信件数：mesnum;空的格子数：fromnum;,图 3.16 信箱的数据结构,进程调用send原语发送信件前，必须事先组织好信件，然后再调用send原语并在调用时给出参数：信箱名和信件内容或信件存放地址。同样，调用receive原语时，也要给出参数：信箱名和信件取出后的存放地址。由此，send和receive原语格式如下：send(boxname,msg)receive(boxn
40、ame,msg),4)原语的实现 发送原语的执行过程是：根据send原语中的第一个参数信箱名，找到相应的信箱，若信箱有空的格子，则按第二个参数指出的地址把信件送入该信箱中，如果有进程在等待该信箱中的信件，则将其唤醒；若该信箱已满，则调用send原语的进程被阻塞并插入等信箱队列。接收原语的执行过程是：根据receive原语中的第一个参数信箱名，找到相应的信箱，若信箱中有信件，则取出一封信放入按第二个参数给出的地址中。如果有进程在等信箱，则将其唤醒，若信箱中无信件，则调用receive原语的进程被阻塞，并插入等信件队列。,send(bosname,msg)beginlocal X;根据 boxna
41、me找到信箱；P(fromnum)；选择标志为空的格子；把消息 msg 放入空的格子X中；置格子X为满标志；V(mesnum);end,receive(boxname,msg)beginlocal X;根据 boxname找到信箱；P(mesnum)；选择标志为满的格子X；将格子X中的信件取出放入 msg中；置格子X的标志空；V(fromnum);end,3.7 死 锁,3.7.1 死锁的起因和产生死锁的必要条件,图 3.17 两个进程死锁的典型例子,图 3.18 进程A、B对资源的请求和释放,图 3.19 进程死锁的环路表示,2.产生死锁的必要条件互斥控制。(2)非剥夺控制。(3)逐次请求。
42、(4)环路条件。,3.7.2 死锁举例,例 1 P、V操作引起的死锁。P、V操作是实现进程间通讯的原语，它能有效地实现进程间的同步和互斥，但由于P、V操作使用不当，也会导致系统死锁。例如，在用P、V操作实现进程间同步的例子中，设S1,S2是初值为 0 的两个信号量，如果进程A、B的程序安排是：,类似地，S1,S2是两个初值为 1 的信号量，则如下的两个进程就会发生死锁：,进程A于r1 处变成阻塞状态，而进程B于r2 处变成阻塞状态。,例 2 存储器共享的死锁。,图 3.20 存储器共享的死锁,假定系统中有m个单位的存储器，它为n个进程所共享。若每个进程都要求i个存储单位，当mni时就可能发生死
43、锁。假定m=4,n=4,i=2，当每个进程首先轮流要求 1 单位，那么第一次请求就把存储器分配完了，而第二次请求时，各进程都进入阻塞状态，结果这四个进程谁也不能向前推进，而形成死锁(图 3.20(a)。当m=2,n=3,i=2 时，P1、P2 第一次请求就把存储器分配完了，P3 在第一次请求后就处于阻塞状态，当P1、P2 第二次请求时纷纷进入阻塞状态。,例 3 加锁法引起的死锁。在加锁法中，我们用加锁LOCK(W)和开锁UNLOCK(W)实现进程的互斥控制。,进程P1 进程P2LOCK(W)LOCK(W)S1 S2UNLOCK(W)UNLOCK(W),例 4 信息传送的死锁。一般把系统中的资源
44、分为两类：一类称为可逐次再使用资源，也称做永久性资源，记以SR，它可供进程逐次使用，例如处理机、主存、I/O设备等，都是永久性资源。另一类资源是消耗性资源，也叫做临时性资源，记以CR，这类资源由一进程产生而被另一进程消耗掉，只能使用短暂的时间。例如进程间同步时交换的信息、数据文件等。,图 3.21 信息传送引起的死锁,设进程P1 产生信息S1，而要求从P3 接收信息S3；进程P2 产生信息S2，而要求从P1 接收信息S1;进程P3产生信息S3，而要求从P2 接收信息S2。如果信息通讯按下述进行：P1：释放S1,请求S3;P2:释放S2,请求S1;P3:释放S3,请求S2;则不会出现死锁。,若按
45、下述顺序进行：P1:请求S3,释放S1;P2:请求S1,释放S2;P3:请求S2,释放S3;则必然出现死锁。,图 3.22五个哲学家吃通心面问题引起的死锁,例 5 哲学家吃通心面问题(Dining Philosophers Problem)。,begin S1，S2,S3,S4,S5:semaphore;S1=S2=S3=S4=S5=1Cobrgin process Pi(i=1,2,3,4)begin Li:thinking;hungry;P(Si);pickup ri;P(Si+1);,pickup ri+1;eating;putdown ri;putdown ri+1;V(Si);V(S
46、i+1);go to Li end;process P5 begin L5:thinking;hungry;P(S5);,pickup r5;P(S1);pickup r1;eating;putdown r5;putdown r1;V(S5);V(S1);go to L5 end;coend;end,3.7.3 对死锁采取的对策,鸵鸟策略。(2)预防策略。(3)避免策略。(4)检测和解除。,3.7.4 死锁的预防,(1)资源静态分配法。(2)资源顺序分配法。这种方法的基本思想是对系统的全部资源加以全局编号：例如1:卡片读入机2：打印机3：绘图仪4：磁带驱动器5：卡片穿孔机 然后规定一条规则：进
47、程任何时候都能够申请资源，不过所有的申请必须按编号增加的顺序进行。,3.7.5 死锁的避免,1.单项资源的银行家算法,例如，设系统中有 10 台磁带机，由三个进程A、B、C共享。假定A、B、C已分别占用了 2 台、3 台、3 台，它们的最大需求量分别为4 台、6 台、8 台。这一要求如下表所示，并假定只有当满足了最大需求量后才能释放所占用的全部资源。,图 3.23单项资源的银行家算法,2.多种资源的银行家算法 现在考虑多种资源的银行家算法。假设系统有四类资源：磁带驱动器、绘图仪、打印机和卡片穿孔机。各类资源的总数用W=(6,3,4,2)表示，即有 6 台磁带驱动器，3 台绘图仪，4 台打印机，
48、2 台卡片穿孔机。现有五个进程A、B、C、D和E，已获得的资源的种类及数量用矩阵R表示：,尚需资源的种类和数量用矩阵Q表示：,现在给出多种资源的银行家算法如下：(1)如果某一进程对某一种资源提出请求，就假定预先分配给它，然后修改矩阵R、Q以及向量S；(2)在矩阵Q中找出一行，使该行向量小于等于S。倘若不存在这样的向量，就说明没有进程能够获得全部资源运行到完成，将会引起系统死锁；(3)假设被选到的那一行的进程获得了全部资源而运行到结束，则设置该进程“能运行完”标志，并把它的资源全部加入向量S；(4)重复步骤(2)和(3)，直到下述情况之一出现：或者所有进程都设置“能运行完”标志，则系统是安全的，
49、可以进行实际分配；或者发生死锁，则预先分配是不安全的，应予以撤消。,3.7.6 系统模型,1.系统状态图,(1)系统状态图是一组系统状态=S1,S1,)和一组进程=P1,P2,)构成的一个数对(,)。图 3.24 表示了一个极为简单的状态图(，)，其中=S,T,U,V,=P1,P2。,图 3.24一个简单的系统状态图,(2)系统由一种状态S演变为另一种状态T，是由于某个进程Pi对资源实施了请求、获得或释放的单个操作的结果。图 3.24 中有,等状态变化。我们把进程Pi在单个操作下，系统由S状态可能过渡到的状态的集合表示为Pi(S)。,由图 3.24 中可以看出,P1(S)=T、UP1(T)=P
50、1(U)=VP2(S)=UP2(T)=S、VP2(V)=,其中表示无意义。,在一般情况下，系统由一个状态过渡到另一个状态，是由于不同进程执行了若干次操作的结果，此时状态的演变表示为：S W。显然它可以包括：,*,(3)一个进程Pi在状态S是阻塞的，是指不存在状态T，使得ST，即进程Pi在那个状态下不能执行任何操作。(4)一个进程Pi在状态S是死锁的，是指对任何使ST的T，Pi在状态T是阻塞的。换句话说，进程Pi在状态S是死锁的，必定是它在状态S以及由它可能到达的所有未来状态T都是阻塞的。例如图 3.24 中P2在状态U是死锁的，因为P2 无论在状态U还是在状态V都是阻塞的。同样，P2 在状态V
