chap进程管理.ppt

第三章: 进程管理,为什么要引入进程的概念 进程的表示和调度状态 进程的控制 进程调度 进程通讯 死锁,3.1 为什么要进入进程的概念,前趋图的定义 顺序程序 程序的并发执行和资源共享 程序并发执行的特性 进程概念的引入,一、前趋图的定义,前趋图(procedence graph)是一个有向无环图DAG (directed acyclic graph)。图中的每一个顶点可表示一条语句、一个程序段或进程, 弧则表示两顶点之间的偏序 (partial order) 或前趋关系 (procedence relation)。无前趋的顶点为初始顶点, 无后继的顶点称为终止顶点, 每个顶点还有一个权值, 它表示顶点执行所需的时间。如,它的每一种拓扑排序都是顺序执行时正确得到结果的顺序,有路经的两顶点必须按前趋关系顺序执行,无路经的两顶点则可以并发执行。,程序顺序执行： 程序执行时, 必须按某种先后次序, 只有当前操作完成后才能执行后继操作, 它体现了某种算法。如： S1: a:=x+y; S2: b:=a-5; S3: c:=b+1; 各程序段与此相同, 以 I C P分别代表输入计算和输出, 则前趋图：,前趋图,S1,S2,S3,I1,C1,P1,I2,C2,P2,二、程序顺序执行,顺序环境：在计算机系统中只有一个程序在运行，这个程序独占系统中所有资源，其执行不受外界影响 特征： 程序执行的顺序性 程序执行的封闭性 独占资源，执行过程中不受外界影响 程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同,三、程序的并发执行和资源共享,程序的并发执行 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的 并发执行是指两个程序的执行在时间上是重叠的,多个程序的并发执行： 在一定时间内物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。宏观上同时处于运行状态微观上各程序交替地间断运行。,前趋关系: IiCi , PiPi+1 CiPi , IiIi+1 CiCi+1,Ii+1, Ci, Pi-1 是重叠的,举例说明: 假如系统中有两道程序AA和BB： program AA; program BB; begin begin AN BN N:=N+1; AA+1 N:=N+1; BB+1 NA NB End; end; int N=1; 是AA和BB都能访问的外部公共变量,这两个程序在并发执行, N:=N+1;可分解为3条机器指令,它们的执行顺序不同有可能导致N的值结果不同。,时间 T0 T1 T2 T3 T4 T5,程序,A,AN,AA+1,NA,程序,B,BN,BB+1,NB,N的值 1 1 2 2 2 3,(a) 顺序 执行,时间 T0 T1 T2 T3 T4 T5,程序,A,程序,B,N的值 1 1 1 1 2 2,(b) 交叉 执行,时间 T0 T1 T2 T3 T4 T5,程序,A,程序,B,N的值 1 1 1 1 2 2,(c) 交叉 执行,NB,BB+1,BN,AN,AA+1,NA,AN,NA,AA+1,NB,BB+1,BN,资源共享 系统中硬件和软件资源不再为单个用户程序所独占，而由几个用户程序共同使用。 程序并发执行和资源共享是现代操作系统的基本特性，它们之间互为依存。 并发的特征 程序结果的不可再现性：并发程序执行的结果与其执行的相对速度有关，是不确定的 在并发环境下程序的执行是间断性的：执行停执行 程序和机器执行程序的活动不再一一对应 并发程序间的相互制约,四、进程概念的引入,进程概念的引入 “程序”这个静态概念已不能如实反映程序并发执行过程中的特征。 进程的定义 从不同的角度对进程的各种定义 进程是程序的一次执行 进程是可以和别的计算并发执行的计算 进程是一个数据结构及能在其上进行操作的程序 进程是程序及其数据在处理机上顺序执行的活动 进程是程序在某一数据集合上的运行过程 程序的一次执行，该程序可与其它程序并发执行。（可并发执行的程序在一个数据集合上的执行过程.),结构性： 由程序+数据+进程控制块组成了进程实体, 称之为进程映像。进程控制块是进程存在的标志。 动态性 进程是进程实体的执行过程, 它由创建而产生, 由调度而执行,因某事件而暂停, 由撤销而消亡。在生命周期内, 进程在三种基本状态之间动态转换 并发性 多个进程同时存于内存中,一起向前推进,并发执行 独立性 进程是独立获得资源和独立调度的基本单位 异步性 各进程都各自独立的不可预知的速度向前推进,进程的特征,程序与进程之间的区别： 进程更能真实地描述并发，而程序不能 进程是由程序、数据和进程控制块三部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程，反之亦然 进程具有创建其他进程的功能，而程序没有,3.2 进程的表示和调度状态,进程的表示 进程的组成 进程控制块 调度状态 进程的基本调度状态 细分的进程调度状态,一、进程的组成,进程由程序、数据集合和PCB三部分组成 程序部分描述了进程所要完成的功能。 数据集合包括程序在执行时所需要的数据和工作区 进程控制块（PCB）：用来描述进程当前状态的数据结构，是进程的动态特性的集中反映。随着进程的创建而产生，进程的撤销而被收回。,二、进程控制块PCB,PCB应包含如下一些信息： 进程表示名或标示数 位置信息 状态信息 进程的优先级 现场保护区 资源清单 队列指针或链接字 进程同步和通信等其它信息,三、进程的调度状态,进程的三种基本状态： 运行状态：进程占有CPU，并在CPU上运行 就绪状态：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行） 阻塞状态：指进程因等待某种事件的发生而暂时不能运行的状态 （即使CPU空闲，该进程也不可运行） 进程在生命消亡前处于且仅处于三种基本状态之一,进程状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换 就绪 运行 时间一到，调度程序选择一个新的进程运行 运行 就绪 运行进程用完了时间片 运行进程被中断，因为一高优先级进程处于就绪状态 运行 阻塞 当一进程所需的东西必须等待时 OS尚未完成服务 对一资源的访问尚不能进行 初始化I/O 且必须等待结果 等待某一进程提供输入 (IPC) 阻塞 运行 当所等待的事件发生时,七状态进程模型,3.3 进程的控制,创建、撤消进程以及完成进程各状态之间的转换。由具有特定功能的原语完成。 内核的各项功能是通过执行原语来实现的 原语的定义是指若干条机器指令构成的并用以完成特定功能的一段程序，这段程序在执行期间是不可分割的 由以下原语完成： 进程创建原语 进程撤消原语 阻塞原语、唤醒原语 挂起原语、激活(解挂)原语(选学),1.进程图 进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。,一、进程的创建,2.进程何时创建? 引起创建进程的事件： 用户登录、作业调度、提供服务、应用请求 用户登录时, 由OS为合法终端创建一个进程 调度到某个批处理作业时,由作业调度程序创建 运行程序请求提供服务(如:打印文件),由OS创建 运行中进程因自己的需要,由它自己创建子进程,3.进程的创建过程 一旦发现了要求创建新进程的事件,OS便调用创建原语, 按以下过程创建新进程。,分配一个唯一的进程标识符,索取一个空白PCB 为新进程的程序和数据分配内存空间 初始化进程控制块 初始化标识符信息(填入)、处理机的状态信息(指令指针, 栈指针)和控制信息(状态,优先级.) 设置相应的链接 如: 把新进程加到就绪队列的链表中,1. 进程何时终止? 正常结束 批处理系统中,进程已运行完成遇到 Halt 指令 分时系统中, 用户退出登录 异常结束 本进程发生出错和故障事件 存储区越界、保护性错(如:写只读文件)、特权 指令错、非法指令(如:程序错转到数据区)、算 术运算错、运行超时、等待超过时、I/O 失败、 外界干预 操作系统干预、父进程请求、父进程终止,二、 进程的终止(撤消),2. 进程的终止过程 一旦发生终止进程的事件,OS便调用撤消原语,按以下过程终止该进程。 从PCB中读取进程的状态 若进程处于执行态, 应立即终止该进程的执行,并置调度标志为真(以便该进程终止后系统重新进行调度,将处理机分配给新选择的进程) 若有子孙进程则将它们全部终止,以防它们失控 将该进程所占有的全部资源还给父进程或系统 将该进程的PCB从所在队列中移出,三、 进程的阻塞、唤醒、挂起与激活,1.进程的阻塞,处于运行状态的进程, 在其运行过程中期待某一事件发生, 如:请求系统服务、等待键盘输入、等待数据传输完成、等待其它进程发送消息, 当被等待的事件未发生时, 由进程调用阻塞原语(block), 将自己阻塞。 阻塞原语使处于运行态的进程停止运行, 将运行现场保存在其 PCB 的 CPU 现场保护区, 然后将 PCB中的现行状态由运行态变为阻塞态, 并将该进程插入到相应事件的阻塞队列中。最后, 转进程调度程序重新调度, 将处理机分配给一个就绪进程, 按新进程 PCB 中的处理机状态设置CPU环境, 使它投入运行。,2. 进程的唤醒 当被阻塞进程期待的事件到来时, 由中断处理进程或其它产生该事件的进程调用唤醒原语(wakeup), 将期待该事件的进程唤醒。 唤醒原语执行时, 将被阻塞进程从相应等队列中移出, 并将其 PCB中的现行状态由阻塞改为就绪态, 然后将该进程插入就绪队列中。 若事件是等待 I/O 完成, 则由硬件提出中断请求, CPU响应中断, 暂停当前进程的执行, 转去中断处理。检查有无等待该 I/O完成的进程。若有, 则将它唤醒。然后结束中断处理。返回被中断进程或重新调度。 若事件是等待某进程发一个信息, 则由发送进程把该等待进程唤醒。,3. 进程的挂起 当进程请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语(suspend), 将指定进程挂起。 执行过程: 检查要挂起进程的状态, 若处于活动就绪态就将其改为静止就绪态, 对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。 4. 进程的激活 要激活指定进程时,调用激活原语(active)将它激活 执行过程: 将要激活的进程调入内存, 并检查它的状态, 若是静止就绪态则将其改为活动就绪态,若为静止阻塞态就将其改为活动阻塞态。如果采用的是抢占调度策略,被激活的进程优先级高则引起重新调度。,3.4 进程调度,无论在多道批处理系统还是分时系统中，系统中的用户进程数都远远超过处理机数，除用户进程要占用处理机外，操作系统还要建立若干个系统进程完成系统功能。这么多的进程竞争处理机，就要求系统提供进程调度功能，以便采用一些策略，将处理机动态地分配给系统中的各个就绪进程，使之执行。分配处理机的任务是由进程调度程序完成的。处理机是计算机最重要的资源，如何提高处理机的利用率，在很大程度上取决于进程调度。进程调度性能的好坏，直接影响操作系统的性能。,一、交通控制程序,交通控制程序是J.H.Saltzer于1966年起的名字。 主要职能是管理进程状态之间的转变和协调进程间的通讯 大多数的操作系统并未单独设置交通控制程序，而是将其功能分散到各处，以原语或广义指令的面貌出现。,二、进程调度程序,进程调度的任务是控制协调进程对CPU的竞争即按照一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。进程调度是通过进程调度程序来完成的。进程调度程序的主要功能可描述如下： 1. 记录系统中各进程的执行状况 为了很好地实现进程调度，进程调度程序首先必须管理系统中各进程的PCB，将进程的状态变化及资源需求情况及时地记录到PCB中。通过PCB变化来准确地掌握系统中所有进程的执行情况和状态特征。,2. 选择进程真正占有CPU 这是进程调度的实质。即按照系统规定的调度策略从就绪队列中选择一个进程占有CPU执行。进程调度依据的算法是与系统的设计目标相一致。对于不同的系统，通常采用不同的调度策略。对于批处理系统常采用短进程的进程优先，以减少各进程的周转时间。对于分时系统，更多地采用时间片轮转。 3. 进行进程上下文的切换 当进程调度选中一个进程占有CPU时，进程调度程序要做的主要工作则是进行进程上下文切换：将正在执行进程的上下文保留在该进程的PCB中，以便以后该进程恢复执行。将刚选中进程的运行现场恢复起来，并将CPU的控制权交给被选中进程，使其执行。,三、 进程调度方式 (1)非剥夺方式(Non preemptive mode) 在非剥夺方式下, 调度程序一旦把CPU分配给某一进程后便让它一直运行下去, 直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。 (2)剥夺方式(Preemptive mode) 与非剥夺方式不同，这种方式规定，当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的情况有：优先级策略和时间片策略。显然这种调度方式通常用在分时系统和实时系统中，以便及时响应各进程的请求。,四、 进程调度的时机 所谓进程调度的时机，是指什么情况下引起进程调度程序工作。进程调度的时机是与进程调度的方式有关的。进程调度的时机如下：,正在执行的进程正确完成, 或由于某种错误而终止运行(陷阱或中断) ； 执行中的进程提出I/O请求, 等待I/O完成时; 在分时系统中, 按照时间片轮转, 分给进程的时间片用完时； 按照优先级调度时, 有更高优先级进程变为就绪时(剥夺方式)； 在进程通讯中, 执行中的进程执行了某种原语操作, 如P操作、阻塞原语和唤醒原语时, 都可能引起进程调度。,五、 进程控制块的组织方式 PCB表: 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度 （注: 多道程序中的道数与系统并发度不同） PCB表组织方式有两种： 链接方式、索引方式,1) 链接方式： 对具有相同状态的进程，分别各自链接起来组成进程PCB链队列： 运行队列、就绪队列、阻塞队列、空闲队列,2) 索引方式： 对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址,六、进程调度算法,1.先进先出进程调度算法(FIFO) (先来先服务FCFS) 按照进程就绪的先后次序来调度进程 优点:实现简单 缺点:没考虑进程的优先级,也没考虑作业的长短 2.短作业(进程)优先调度算法(SJF SPF) 选择就绪队列中估计运行时间最短的进程投入运行 优点:平均周转时间,带权平均周转时间都改善 缺点:对长作业非常不利 不能保证紧迫性进程得到及时处理 估计运行时间不准确,把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行 分时系统中常用时间片轮转法 时间片选择问题： 固定时间片、可变时间片(随) 确定时间片大小的因素： 系统响应时间、就绪进程个数、CPU能力,3.时间片轮转调度算法(RRRound Robin),4. 优先权调度算法(HPFHighest Priority First) 优先选择就绪队列中优先权最高的进程投入运行 非抢占式优先权算法:仅在事件发生放弃处理机时 抢占式优先权算法: 可将正在运行的运行权剥夺 优先权的类型 静态优先权: 在进程创建时指定优先权, 在进程运行时优先数不变 动态优先权: 在进程创建时创立一个优先权，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变 确定优先权的依据 进程类型、对资源的需求、根据用户要求,5. 高响应比优先调度算法： 改进短作业(进程)优先调度算法,优先权用下式动态计算出来 优先权= = 上式可看出 等待时间相同要求服务的时间越短优先权越高, 有利于短作业 要求服务时间相同,等待时间越长优先权越高,近似于先来先服务 长作业的优先权会随等待时间加长而升高,长作业也会得到执行,6.多队列反馈调度算法： 系统按优先级设置多级就绪队列第一级优先级最高 各就绪队列分配不同的时间片,优先级高的第一级队列时间片最小, 随着队列优先级的降低, 时间片加大 各个队列按照先进先出调度算法 一个新进程就绪后进入第一级就绪队列 进程由于等待事件而放弃CPU后, 进入等待队列, 一旦等待的事件发生, 则回到原来的就绪队列 当有一个优先级更高的进程就绪时, 可以抢占CPU,被抢占进程回到原来一级就绪队列末尾 当第一级队列空时, 就去调度第二级队列, 如此类推 时间片用完后进程放弃CPU, 进入下一级就绪队列,3.6 进程通讯,一、进程之间的两种相互制约关系 进程的并发执行虽然提高了资源利用率, 但由于进程的异步性, 会给系统造成混乱。为了使并发执行的各进程都能正确执行, 使它们之间能有效地共享资源和相互合作, 必须研究并发执行的各进程之间的相互制约关系, 采取一定的措施使系统中诸进程有条不紊的同步向前推进。进程之间有两种相互制约关系： 间接相互制约关系(资源共享关系) 直接相互制约关系(功能合作关系),1) 间接相互制约关系(资源共享关系、互斥关系) 由于共享资源, 使得系统中本来没有逻辑关系的进程, 因相互竞争资源而产生了制约关系。 例如: 进程 P1和P2在运行中都要使用打印机, 为了保证各进程输出的完整, 打印机必须互斥访问 (独占使用)。即一个进程使用完后, 另一进程才能使用。这样,一旦系统将打印机分配给进程 P1, 进程P2就必须等待, 直到P1用完打印机并释放后, P2才能使用。 这种因共享资源而使并发执行的各进程之间产生的关系, 叫做间接制约关系, 又叫做互斥关系。这种关系可以用“进程-资源-进程”来描述。 进程的互斥(mutual exclusion),2)直接制约关系(相互功能合作关系、同步关系) 通常, 一个用户作业要涉及一组并发进程(输入、计算和输出进程), 这些进程必须相互协作共同完成这项任务。 具体说, 在运行过程中, 某进程可能要在某些同步点上等待另一伙伴(协作进程)为它提供消息, 在未获得消息之前, 该进程处于等待状态, 获得消息后被唤醒进入就绪态, 此后, 才能继续运行。进程之间的这种制约关系叫做直接制约关系,又叫同步关系。这种关系可用“进程-进程”来描述。,进程的同步(synchronism) 例: 司机 P1 售票员 P2 REPEAT REPEAT 启动 关门 正常行驶 售票 到站停 开门 UNTIL FALSE UNTIL FALSE,3） 临界资源和临界区,进程的互斥是由于共享资源而引起的, 为了描述这类情况, 我们引入临界资源和临界区的概念。 临界资源(互斥资源)：critical resource 系统中一次只允许一个进程访问的资源。这些资源既包括I/O设备, 如打印机等资源, 也包括软件资源, 如共享变量、共享文件等。 临界区(互斥区): critical section 并发执行的进程中, 访问临界资源的必须互斥执行的程序段叫临界区。 临界区分散在每个要并发执行的进程中, 它们都对某个共享的数据结构(共享资源)进行访问。,变量a是临界资源 C1、C2、C3是临界区 对a应互斥访问,二、实现临界区互斥的锁操作法,为禁止两个进程同时进入临界区，必须有一相应机构来协调它们，且遵循下述原则： 当有若干进程要求进入它们的临界区时，应在有限时间内使一个进程进入临界区。 每次最多有一个进程处于临界区内。 进程在临界区内逗留应在有限时间范围内。,用锁操作原语实现互斥 关锁执行临界区程序开锁 锁有两种状态：w=0表示锁已打开；w=1表示锁被关闭。 加锁原语用Lock(w)表示；开锁原语用unlock(w)表示。 LOCK(W)原语 L:if W=1 then go to L else W:=1; UNLOCK(W)原语 W:=0;,例：两个进程P1，P2使用如下程序实施进程的互斥： 进程P1 进程P2 LOCK(w) LOCK(w) S1 S2 UNLOCK(w) UNLOCK(w) S1和S2分别为进程P1和P2的临界区。 特点：用加锁和开锁的方法实现临界区互斥，其效率很低。因为只要一个进程进入临界区后，其他企图进入临界区的进程，在执行LOCK(W)时，因不断测试W造成处理机时间的浪费。,三、信号量和P、V操作,管理和控制铁路交通的重要工具是信号灯。利用信号灯的状态(颜色)控制火车的正常通行。单段铁路任何时刻只允许一列火车通行(相当于临界区)，遇到红灯(表示区内有火车)应等待，变为绿灯时可进入行驶(同时红灯亮禁止其它火车进入)，火车驶出临界区绿灯亮允许火车进入。同样, 为了管理各并发进程对共享资源的使用, 引入了信号灯(信号量)的概念; 将信号量定义为一个整型量 S; S0表示资源可用(无进程在临界区相当于绿灯亮)。某进程企图进入区时, S0可以进入。信号量 S 只能通过两个标准原子操作(不可中断) P-V操作来访问。,根据用途不同，分为公用信号量和私用信号量。 公用信号量通常用于实现进程之间的互斥，初值为1 私用信号量通常用于实现进程间的同步，初值为0或为某个正整数n,P、V操作原语,P操作原语的定义： P（S）：顺序执行下述两个动作： 信号量的值减1，即S=S-1； 如果S 0，则该进程继续执行； 如果S0，则把该进程的状态设置为阻塞态，把它相应的PCB放入相应队列中，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止） Procedure P(Var S:Semaphore) begin S:=S-1; if S0 then W(S) end;,特点： 1、P操作是为请求资源而设立的，只有请求 2、如果信号量S=0，表示资源够用； 等于0表示正好够用； 小于0表示资源不够用，S的绝对值表示等待使用资源的进程个数 3、P操作起到了限制一次只有一个进程进入临界区的作用,V操作原语的定义： V（S）顺序执行下述两个动作： S值加1，即S=S+1 如果S0，则该进程继续运行； 如果S 0，则唤醒等待信号量S阻塞队列中的头一个进程（把阻塞态改为就绪态），执行V操作的进程继续运行。 Procedure V(Var S:Semaphore) begin S:=S+1; if S=0 then R(S) end;,特点： 1、V操作是为释放系统资源而设立的，V操作可以唤醒等待进程 2、使用的信号量必须与同它对应的P操作相同 3、P、V操作在系统里必须成对出现，可以在不同的框图中,四、用信号量解决互斥模型,进程P1 进程P2 . . . . P(S) P(S) 临界区 临界区 V（S) V(S) . . . .,五、用信号量实现互斥实例,用P，V操作实现互斥时应注意： （1）在每个程序中用于实现互斥的P(S)和V(S)必须成对出现，即先做P，进临界区；后做V，出临界区。 （2）互斥信号量S的初值一般为1,例 前面举例中的公用变量N，也是一个临界资源。两个并发进程对N的操作必须互斥执行。,设信号量S，初值为1，表示互斥的使用公用变量N；N的初值为1； 则AA： BB P(S) P(S) A=N; B=N; A=A+1; B=B+1; N=A; N=B; V(S) V(S),六、用信号量实现同步,信号量初值为0，两个进程之间的同步模型如下： 进程P1 进程P2 L1：P（S） L2：V(S) 在这种同步操作中，进程p1受到进程P2的制约，而进程P2却不受进程P1的制约，所以是非对称的。,用信号量实现同步时应注意：,分析进程间的制约关系，确定信号量种类 信号量的初值与相应资源数量有关，也与P，V操作在程序代码中出现的位置有关 同一信号量的P，V操作要成对出现，但它们分别在不同的进程代码中,例：A（计算） B（打印） 设信号量SA，初值为1，表示是否已取走计算的结果 信号量SB，初值为0，表示是否有可打印的结果,单缓冲区,缓冲区空，对A表示有资源，对B无资源； 缓冲区满，对A表示无资源，对B有资源；,利用P、V操作实现对进程A、B的同步,计算进程A： 打印进程B:,七、经典进程同步问题,1、生产者消费者问题 问题描述：一群生产者向一个有界缓冲区放入产品，只要缓冲区未满就可以存放，又有一群消费者从有界缓冲区取走产品，只要缓冲区未空就可以取走。 要求：存存、取取、存取都不能同时进行，缓冲区满时停存，缓冲区空时停取，生产与消费等放。,缓冲区,消费者,生产者,解决方法 设三个信号量 1、信号量S，初值为1，表示没有产品进入临界区，用于互斥； 2、信号量n1，表示可用缓冲区个数，初值为k 3、信号量n2，表示产品个数，初值为0,2、读者写者问题（选学）,问题描述： (1) 一个数据对象被多个读者、写者进程共享； (2) 允许多个读者进程可以共享这个数据对象，因为读操作不会使数据文件混乱； (3) 写者与写者、写者与读者必须互斥使用数据对象；,解决方法： (1) 设ReadCount是整型变量，初值为0，最大值是RN，表示读者个数； (2) 设信号量r，初值为1，表示读者互斥使用ReadCount； (3) 设信号量w，写者与写者互斥，写者与第一读者互斥,读者：,写者：,P(w),写操作,V(w),返回,3、哲学家就餐问题,问题描述：五个哲学家围坐在一圆桌旁, 桌中央有一盘通心粉, 每人面前有一只空盘子, 每两人之间放一只筷子。 每个人的行为是思考, 感到饥饿, 然后吃通心粉。 为了吃通心粉, 每个人必须拿到两只筷子, 并且每个人只能直接从自己的左边或右边去取筷子。,解决：筷子是临界资源，一段时间内只允许一个哲学家使用，可以用一个信号量表示一个筷子 C(1)， C(2)， C(3)， C(4)， C(5),八、高级通讯原语,问题的提出： P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息 两种进程通信的方式消息缓冲和信箱通讯 本质是共享内存 相互通信的进程间设有公共内存，一组进程向该公共内存中写，另一组进程从公共内存中读，通过这种方式实现两组进程间的信息交换,消息缓冲区中包含的信息： Name：发送消息的进程名或标识号 size ：消息长度 text：消息正文 next：下个缓冲区的地址,消息：可以用来传递一定信息。 消息本身是一组信息，但信息只用通过消息传递才是消息。,1、消息通信,下一个要解决的问题是：消息传递 系统为进程提供了两个高级通讯原语send和receive send：当要进行消息传递时执行send receive：当接收者要接收消息时执行receive,通信过程：发送进程在自己的空间里制造一个消息，用发送原语将此消息发送出去；接收进程在自己的空间里开辟一个消息接收区，利用接收原语将此消息从消息队列队首复制到指定的接收区。,进程PCB中与消息通信相关的域,mutex：消息队列互斥信号量。消息队列是临界资源，不允许两个或两个以上的进程对它同时访问。 Sm ：私有信号量,表示已接收的消息数。用于接受消息进程与发送消息进程进行同步，其值表示消息队列中的消息数目。 Pm：指向该进程的消息队列中的消息缓冲链，如下图。,PCB与消息缓冲链,消息缓冲区队列,Send程序流程图,receive程序流程图,2、信箱通讯（选学）,信箱用于存放信件，而信件是一进程发送给另一进程的消息。信箱为接收进程所拥有。,信箱的数据结构： 信箱名：boxname; 信箱大小：boxsize; 已存信件数：mesnum; 接收进程的私用信号量，初值0 空的格子数：fromnum; 发送进程的私用信号量，初值为格子数 用发送和接受原语实现,Send(boxname,msg) 根据boxname找到信箱； 判断信箱是否有空格子p(fromnum)：若有则按第二个参数指出的地址把信件送入该信箱。,Receive(boxname,msg) (1)根据boxname找到信箱； (2) 判断信箱中是否有信件P(mesnum)：若有则取出一封信放入按第二个参数给出的进程中。,3.7 死锁,死锁(Deadlock)的定义： 一组进程中，每个进程都无限等待被该组中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程 说明: 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,一、死锁产生的原因 1.竞争资源引起 永久性资源:可以被多个进程多次使用(可再用资源) 剥夺性资源(CPU、内存） 非剥夺性资源(磁带机、打印机) 竞争非剥夺性资源会引起死锁 临时性资源:只可使用一次的资源； 如信号量,中断信号,同步信号等(可消耗性资源) 竞争临时性资源也会引起死锁 2. 进程推进顺序不当引起 对资源采用“申请-分配-使用-释放”模式, 由于推进顺序不当两进程都要申请对方已占有的资源,二、产生死锁的四个必要条件,1) 互斥条件（资源独占）： 一个资源每次只能给一个进程使用 2) 不可剥夺条件（不可强占）： 资源申请者不能强行的从资源占有者手中夺取资源, 资源只能由占有者自愿释放 3) 请求和保持条件: (部分分配,占有申请) 在申请新的资源的同时保持对原有资源的占有。 4) 循环等待条件： 存在一个进程-等待资源环形链 P1 , P2 , , Pn, 其中P1等待P2占有的资源, P2等待P3占有的资源, , Pn等待P1占有的资源。,P1： 申请打印机 申请扫描仪 使用 释放打印机 释放扫描仪 ,P2： 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 ,死锁的例子:竞争非剥夺性资源引起死锁,三、对死锁采取的对策,鸵鸟策略 采取不理睬的策略 预防策略 破坏死锁的四个必要条件 避免策略 精心地分配资源，动态地回避死锁 检测和解除 一旦发生死锁，及时检测出来，并采取措施解除死锁。,四、死锁的预防,系统设计时确定资源分配算法,保证不发生死锁。做法是破坏产生死锁的四个必要条件之一。 1. 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定, 一个进程在申请新的资源不能立即满足而变为等待状态之前, 必须释放已占有的全部资源, 若需要再重新申请。 2.破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。,3.破坏“循环等待”条件 采用资源有序分配法: 把系统中所有资源编号, 进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配。,4、破坏“互斥性”条件， 允许一个资源可由多个进程同时使用 缺点：对有的资源行不通，例如打印机,五、避免死锁的算法,系统运行过程中, 对进程发出的每一个资源申请进行动态检查,根据检查结果决定是否分配资源, 若分配可能引起系统死锁, 则不予分配,否则予以分配。 安全序列与安全状态： 如果在某时刻系统中所有进程可以排列一个安全序列:P1,P2,Pn,刚称此时,系统处于安全状态. 所谓安全序列P1,P2,.,Pn是指对于Pi(1in),都有它所尚需最大资源数量不超过系统剩余的资源量与所有Pj (j i )所占的资源量之和 。 若系统不存在这样一个安全序列, 则称系统处于不安全状态,不安全状态可能引起系统死锁。,例如：,避免死锁的实质是如何使系统不进入不安全状态。,银行家算法(发贷款先给足能及时还者) 数据结构： n：系统中进程的总数; m：资源类总数 可用资源向量 Available: ARRAY1m of integer; 最大需求矩阵Max: ARRAY1n,1m of integer; 分配矩阵Allocation: ARRAY1n,1m of integer; 需求矩阵Need: ARRAY1n,1m of integer; Needi,j=MAXi,j-Allocatini,j 请求矩阵Request: ARRAY1n,1m of integer; 简记符号： Available, Maxi, Allocationi, Needi, Requesti,算法: 当进程pi提出资源申请时, 系统执行下列步骤: (1).若RequestiNeedi,转(2)否则错误返回 (2).若RequestiAvailable, 转(3)否则进程等待 (3).假设系统分配资源, 则有: Available:=Available-Requesti; Allocationi:=Allocationi+Requesti; Needi:=Needi-Requesti; 若系统新状态是安全的, 则分配完成 若系统新状态是不安全的, 则恢复原状态, 进程等待,为进行安全性检查, 定义数据结构： 工作向量Work:系统可提供给进程继续运行所需的各 类资源数目,有m个元素, 其初值为多少？ Finish:系统是否有足够的资源分配给进程,使之完成; 安全性检查的步骤： (1) Work:=Available; Finish:=false; (2) 寻找满足条件的i： a.Finishi=false; b.NeediWork; 如果不存在，则转(4) (3) Work:=Work+Allocationi; Finishi:=true; 转(1) (4) 若对所有i,Finishi=true,则系统处于安全状态, 否则处于不安全状态,进程 最大需求 已分配 尚需要 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7,银行家算法实例(一种资源)：,安全序列: P2, P1, P3,银行家算法实例(多种资源)： 假定系统有五个进程P0, P1, P2, P3, P4和三类资源ABC资源总数为10,5,7, T0时刻资源分配情况为:,1) 检查T0时刻的安全性,P1 3 3 2 2 0 0 1 2 2 5 3 2 true,安全,P3 5 3 2 2 1 1 0 1 1 7 4 3 true,P4 7 4