软设计师培训3OSppt课件

1、软件设计师培训软件设计师培训软件设计师软件设计师3.3.操作系统知识操作系统知识大纲要求：大纲要求：l 操作系统的内核（中断控制）、进程、线程概念操作系统的内核（中断控制）、进程、线程概念l 处理机管理（状态转换、共享与互斥、分时轮转、抢占、死锁）处理机管理（状态转换、共享与互斥、分时轮转、抢占、死锁）l 存储管理（主存保护、动态连接分配、分段、分页、虚存）存储管理（主存保护、动态连接分配、分段、分页、虚存）l 设备管理（设备管理（i/oi/o控制、假脱机）控制、假脱机）l 文件管理（文件目录、文件组织、存取方法、存取控制、恢复处理）文件管理（文件目录、文件组织、存取方法、存取控制、恢复处理）

2、l 作业管理（作业调度、作业控制语言（作业管理（作业调度、作业控制语言（jcljcl）、多道程序设计）、多道程序设计）l 汉字处理，多媒体处理，人机界面汉字处理，多媒体处理，人机界面l 网络操作系统和嵌入式操作系统基础知识网络操作系统和嵌入式操作系统基础知识l 操作系统的配置操作系统的配置软件设计师软件设计师3.1 3.1 操作系统的基本概念操作系统的基本概念l 操作系统的定义操作系统的定义 能有效地组织和管理系统中的各种软、硬件资源，合理地能有效地组织和管理系统中的各种软、硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提组织计算机系统工作流程，控制程序的执行，并且向用户提

3、供一个良好的工作环境和友好的接口。供一个良好的工作环境和友好的接口。硬件资源：包括硬件资源：包括cpucpu，存储器，输入，存储器，输入/ /输出资源等物理设备。输出资源等物理设备。软件资源：以文件形式保存在存储器上的程序和数据等信息。软件资源：以文件形式保存在存储器上的程序和数据等信息。软件设计师软件设计师l 操作系统的操作系统的2 2个重要作用个重要作用: :(1) (1) 通过资源管理提高计算机系统的效率通过资源管理提高计算机系统的效率(2) (2) 改善人机界面，向用户提供友好的工作环境改善人机界面，向用户提供友好的工作环境软件设计师软件设计师l 操作系统的操作系统的4 4个特征个特征

4、(1)(1)并发性：计算机系统存在着许多并发执行的活动并发性：计算机系统存在着许多并发执行的活动p1c1i1i2c2p2i1i2i3i4c1c2c3c4p1p2p3p4软件设计师软件设计师(2)(2)共享性：系统中各个并发活动要共享计算机系统中的各共享性：系统中各个并发活动要共享计算机系统中的各 种软，硬件资源。种软，硬件资源。(3)(3)虚拟性：虚拟是操作系统中的重要特征，所谓虚拟就是虚拟性：虚拟是操作系统中的重要特征，所谓虚拟就是 把物理上的一台设备变成逻辑上的多台设备。把物理上的一台设备变成逻辑上的多台设备。(4)(4)不确定性不确定性( (异步性异步性) )：指进程的执行顺序和执行时间

5、及执：指进程的执行顺序和执行时间及执 行结果的不确定性。行结果的不确定性。软件设计师软件设计师l 操作系统的操作系统的5 5大管理功能大管理功能 (1) (1) 进程管理进程管理 (2) (2) 存储管理存储管理 (3) (3) 设备管理设备管理 (4) (4) 文件管理文件管理 (5) (5) 作业管理作业管理软件设计师软件设计师l基本概念基本概念 多道程序设计原理多道程序设计原理：在计算机内存中同时存放几道相互：在计算机内存中同时存放几道相互 独立的程序，它们在管理程序的控制下相互穿插地运独立的程序，它们在管理程序的控制下相互穿插地运 行，共享行，共享cpucpu和外设等资源。和外设等资源

6、。 程序程序：具有特定功能的一组指令集合，它指出了处理器：具有特定功能的一组指令集合，它指出了处理器 执行操作的步骤。执行操作的步骤。 进程进程：进程是一个程序在一个数据集合上的一次执行。：进程是一个程序在一个数据集合上的一次执行。3.2 3.2 进程管理进程管理软件设计师软件设计师程序和进程区别程序和进程区别：(1)(1)程序是动态的，进程是动态的。程序是动态的，进程是动态的。(2)(2)进程与程序的对应关系：通过多次执行，一个程序可进程与程序的对应关系：通过多次执行，一个程序可 对应多个进程；通过调用关系，一个进程可包括多个对应多个进程；通过调用关系，一个进程可包括多个 程序。程序。(3)

7、(3)进程是暂时的，程序的永久的：进程是一个状态变化进程是暂时的，程序的永久的：进程是一个状态变化 的过程，程序可长久保存。的过程，程序可长久保存。(4)(4)进程与程序的组成不同：进程的组成包括程序、数据进程与程序的组成不同：进程的组成包括程序、数据 进程控制块（即进程状态信息）。进程控制块（即进程状态信息）。软件设计师软件设计师 进程通常由三部分组成：进程通常由三部分组成： (1)(1)程序：描述了进程所要完成的功能，是进程执行时不可程序：描述了进程所要完成的功能，是进程执行时不可 修改的部分。修改的部分。 (2)(2)数据集合：程序执行时所需要的数据和工作区，为一个数据集合：程序执行时所

8、需要的数据和工作区，为一个 进程专用，可修改。进程专用，可修改。 (3)(3)进程控制块进程控制块pcb (process control block)pcb (process control block)：包含了：包含了 进进 程的描述信息和控制信息，是进程的动态特性的集中反程的描述信息和控制信息，是进程的动态特性的集中反 映。映。pcbpcb包含以下几类信息：进程描述信息、进程控制包含以下几类信息：进程描述信息、进程控制 信息、资源占用信息、信息、资源占用信息、cpucpu现场保护结构：现场保护结构：软件设计师软件设计师l 进程的基本状态及转换：进程的基本状态及转换： 进程在生命期内处于且

9、仅处于三种基本状态之一：进程在生命期内处于且仅处于三种基本状态之一： 运行态运行态: :当一个进程在处理机上运行时，则称该进程处于当一个进程在处理机上运行时，则称该进程处于运行状态。运行状态。 就绪态就绪态: :一个进程获得了除处理机外的一切所需资源，一一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。旦得到处理机即可运行，则称此进程处于就绪状态。 阻塞态阻塞态: :当一个进程正在等待某一事件发生（例如请求当一个进程正在等待某一事件发生（例如请求i io o而等待而等待i io o完成等）而暂时停止运行，这时即使把处理完成等）而暂时停止运行，这时即使把处理

10、机分配给进程也无法运行，故称该进程处于阻塞状态。注机分配给进程也无法运行，故称该进程处于阻塞状态。注意与就绪状态的不同在于即使处理机处于空闲状态也无法意与就绪状态的不同在于即使处理机处于空闲状态也无法运行。运行。 软件设计师软件设计师运行运行就绪就绪阻塞阻塞调度调度i/oi/o完成完成时间片到时间片到i/oi/o请求请求 就绪就绪运行：运行：调度程序选择一个新的进程运行调度程序选择一个新的进程运行. . 运行运行就绪：就绪：运行进程用完时间片被中断或在抢占调度运行进程用完时间片被中断或在抢占调度 方式中方式中, , 因为一高优先级进程进入就绪状态因为一高优先级进程进入就绪状态 运行运行阻塞：阻

11、塞：进程发生进程发生i/oi/o请求或等待某事件时请求或等待某事件时 阻塞阻塞就绪：就绪：当当i/oi/o完成或所等待的事件发生时完成或所等待的事件发生时软件设计师软件设计师l 进程调度进程调度 在多道程序环境下，系统中有多个进程同时运行。多在多道程序环境下，系统中有多个进程同时运行。多个的进程竞争处理机，就要求系统提供进程调度功能，个的进程竞争处理机，就要求系统提供进程调度功能，将处理机动态地分配给系统中的各个进程，使之能够协将处理机动态地分配给系统中的各个进程，使之能够协调一致的运行。调一致的运行。进程调度程序进程调度程序：主要任务是按照一定的调度算法从就绪：主要任务是按照一定的调度算法从

12、就绪队列中选取一个进程，把处理机分配给此进程使用。队列中选取一个进程，把处理机分配给此进程使用。软件设计师软件设计师 进程调度方式进程调度方式(1) (1) 非抢占方式：在非抢占方式下，调度程序一旦把非抢占方式：在非抢占方式下，调度程序一旦把 cpucpu分分配给某一进程后便让它一直运行下去，直到进程完成或发配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将生某事件而不能运行时，才将cpucpu分给其它进程。分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。是简单、系统开销小。(2) (2)

13、 抢占方式：当一个进程正在执行时，系统可以基于某种抢占方式：当一个进程正在执行时，系统可以基于某种策略剥夺策略剥夺cpucpu给其它进程。剥夺的原则有：给其它进程。剥夺的原则有：优先权原则、优先权原则、短进程优先原则和时间片原则。短进程优先原则和时间片原则。 这种调度方式多用在分时系统和实时系统中，以便及这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。时响应各进程的请求。软件设计师软件设计师进程调度算法进程调度算法(1)(1)先来先服务先来先服务fcfs(fcfs(先进先出调度算法，先进先出调度算法，fifo)fifo)【算法思想】【算法思想】: :最简单的算法最简单的算法按

14、照进程进入就绪队列的按照进程进入就绪队列的先后次序先后次序，分派，分派cpucpu；当前进程占用当前进程占用cpucpu，直到执行完或阻塞直到执行完或阻塞，才出让，才出让cpucpu（非抢占方式）。（非抢占方式）。在进程在进程唤醒后唤醒后（如（如i/oi/o完成），并不立即恢复执行，完成），并不立即恢复执行，通常等到当前进程出让通常等到当前进程出让cpucpu。【特点】：【特点】：比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。有利于有利于cpucpu繁忙的作业，而不利于繁忙的作业，而不利于i/oi/o繁忙的作业。繁忙的作业。软件设计师软件设计师(2)(2)短进程优先调度算

15、法短进程优先调度算法(sjf,spf)(sjf,spf)【算法思想】【算法思想】：选择就绪队列中估计运行时间最短的进程选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业投入运行。通常后来的短作业不抢先不抢先正在执行的作业。正在执行的作业。【优点】【优点】：比比fcfsfcfs改善改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩，缩短作业的等待时间；短作业的等待时间；提高系统的提高系统的吞吐量吞吐量； 【缺点】【缺点】：对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行；未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来

16、划分执行的优先级；难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影响，从而影响调度性能。调度性能。软件设计师软件设计师(3)(3)优先权调度算法优先权调度算法(hpf(hpfhighest priority first)highest priority first)【算法思想】【算法思想】：优先选择就绪队列中优先级最高的进程投：优先选择就绪队列中优先级最高的进程投入运行。分为：入运行。分为：非抢占式优先级算法非抢占式优先级算法：仅发生在进程放弃：仅发生在进程放弃cpucpu。抢占式优先级算法抢占式优先级算法：可剥夺当前运行进程：可剥夺当前运行进程cpucpu。【 优

17、先权的类型】优先权的类型】静态优先级静态优先级：在进程创建时指定优先级：在进程创建时指定优先级, , 在进程运在进程运行时优先数不变。行时优先数不变。动态优先级动态优先级：在进程创建时创立一个优先级，但在：在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长其生命周期内优先数可以动态变化。如等待时间长优先数可改变。优先数可改变。【确定优先级的依据】【确定优先级的依据】 进程类型、对资源的需求、根据用户要求。进程类型、对资源的需求、根据用户要求。软件设计师软件设计师(4)(4)高响应比优先高响应比优先 (hrrn, highest response ratio next

18、)： hrrn是是fcfs和和sjf的折衷算法，响应比的折衷算法，响应比r用下式动态计用下式动态计算：算： 响应比响应比r =【特点】：【特点】： 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高, 有利于有利于短作业。短作业。 要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近似于先近似于先来先服务。来先服务。 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作业也会得长作业也会得到执行。到执行。等待时间等待时间+要求服务时间要求服务时间 要求服务时间要求服务时间软件设计师软件设计师(5)(5)时间片

19、轮转调度算法时间片轮转调度算法【算法思想】：【算法思想】：通过时间片轮转，提高进程通过时间片轮转，提高进程并发性并发性和和响应时响应时间间特性，从而提高特性，从而提高资源利用率资源利用率。将系统中所有的就绪进程按照将系统中所有的就绪进程按照fcfsfcfs原则，排成一个原则，排成一个队列队列。 每次调度时将每次调度时将cpucpu分派给分派给队首进程队首进程，让其，让其执行一个时间执行一个时间 片片。时间片的。时间片的长度长度从几个从几个msms到几百到几百msms。在一个时间片结束时，发生在一个时间片结束时，发生时钟中断时钟中断。调度程序据此调度程序据此暂停当前进程的执行暂停当前进程的执行，

20、将其送到，将其送到就绪队列就绪队列 的末尾的末尾，并通过，并通过cpucpu现场切换现场切换执行当前的队首进程执行当前的队首进程。进程可以进程可以未使用完一个时间片未使用完一个时间片，就，就出让出让cpucpu（如阻塞）。（如阻塞）。 软件设计师软件设计师(6)(6)多级反馈队列算法多级反馈队列算法( (多队列轮转法多队列轮转法) )【算法思想】：【算法思想】： 设置设置多个就绪队列多个就绪队列，分别赋予，分别赋予不同的优先级不同的优先级，队列，队列1 1的的优先级最高，其他逐级降低。每队列分配优先级最高，其他逐级降低。每队列分配不同的时间片不同的时间片，规定优先级越低则时间片越长。规定优先级

21、越低则时间片越长。 新进程就绪后，新进程就绪后，先投入队列先投入队列1 1的末尾的末尾，按，按fcfsfcfs算法调度。算法调度。若一个时间片未能执行完，则若一个时间片未能执行完，则降低降低投入到队列投入到队列2 2的末尾；的末尾；依此类推，依此类推，降低到最后的队列降低到最后的队列，则按，则按“时间片轮转时间片轮转”算法算法调度直到完成。调度直到完成。软件设计师软件设计师 进程由于等待事件而放弃进程由于等待事件而放弃cpucpu后后, , 进入等待队列进入等待队列, , 一一旦等待的事件发生旦等待的事件发生, , 则回到原来的就绪队列。则回到原来的就绪队列。仅当仅当较高优先级的队列为空较高优

22、先级的队列为空，才调度较低优先级的队，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则优先级的队列，则抢先抢先执行新进程，并把执行新进程，并把被抢先的进被抢先的进程投入原队列的末尾程投入原队列的末尾。软件设计师软件设计师l 进程同步和互斥进程同步和互斥 在计算机系统中，多个进程可以并发执行，因在计算机系统中，多个进程可以并发执行，因此进程间必然存在资源共享和相互合作的问题。此进程间必然存在资源共享和相互合作的问题。软件设计师软件设计师例：例：共享数据变量资源造成的错误共享数据变量资源造成的错误终端售票处理进程：终端

23、售票处理进程：process pi(i=1,2,3,n) /* pi为顾客服务的处理进程为顾客服务的处理进程*/begin 按旅客订票要求找到按旅客订票要求找到aj; /* aj为公共数据区为公共数据区*/ ri:=aj; /* ri为各进程执行时所用的工作单元为各进程执行时所用的工作单元*/ if ri1 then begin ri:=ri-1; aj:=ri; 输出一张票输出一张票； end else输出输出“票已售完票已售完”;end软件设计师软件设计师进程互斥进程互斥是指当有若干进程都要使用某一资源是指当有若干进程都要使用某一资源时，任何时刻最多只允许一个进程去使用，其他时，任何时刻最

24、多只允许一个进程去使用，其他要使用该资源的进程必须等待，直到占用资源者要使用该资源的进程必须等待，直到占用资源者释放了该资源。释放了该资源。 这样的资源称为称为互斥资源这样的资源称为称为互斥资源打印机，打印机，共享变量等。共享变量等。软件设计师软件设计师 共享资源的互斥的使用就是限定并发进程互共享资源的互斥的使用就是限定并发进程互斥的进入相关临界区。斥的进入相关临界区。 临界区临界区 并发进程中与共享变量有关的程序段。并发进程中与共享变量有关的程序段。 如例题中的临界区：如例题中的临界区： ri:=aj; if ri1 then begin ri:=ri-1; aj:=ri; pv操作操作 就

25、是一种实现相关临界区的管理，实就是一种实现相关临界区的管理，实现进程互斥的方法。现进程互斥的方法。 软件设计师软件设计师 pvpv操作操作进程的互斥进程的互斥 pvpv操作由操作由p p操作操作和和v v操作操作组成，组成，p p操作和操作和v v操是两个在操是两个在信号量信号量s s上进行的操作。定义如下：上进行的操作。定义如下： procedure p(s)procedure p(s) begin s:=s-1; begin s:=s-1; if s0 then if s0 then 则该进程进入等待队列；则该进程进入等待队列； end;pend;p procedure v(s) proc

26、edure v(s) begin s:=s+1; begin s:=s+1; if s if s0 then 0 then 唤醒一个等待队列中的进程进入就绪；唤醒一个等待队列中的进程进入就绪； end;vend;v软件设计师软件设计师begin s：semaphore s：=1cobegin process pi(i=1,2,3,n) 按旅客订票要求找到按旅客订票要求找到aj; p（s） ri:=aj; if ri1 then begin ri:=ri-1; aj:=ri; v（s） 输出一张票输出一张票； end else begin v（s） 输出输出“票已售完票已售完”; coenden

27、d软件设计师软件设计师例：共享缓存器资源造成的错误例：共享缓存器资源造成的错误a进程进程b进程进程记录记录缓存器缓存器读读写写取取处理处理(1)a(1)a的执行速度操作的执行速度操作b b的执行速度，造成缓存器中的数的执行速度，造成缓存器中的数据还没拿走，据还没拿走，a a又读入新数据覆盖了原有数据。又读入新数据覆盖了原有数据。(2)b(2)b的执行速度操作的执行速度操作a a的执行速度，的执行速度，b b从缓存器取出一个从缓存器取出一个记录并加工后，记录并加工后，a a还没有读入新数据，造成还没有读入新数据，造成b b在缓存器中在缓存器中重复取同一个记录加工。重复取同一个记录加工。软件设计师

28、软件设计师进程同步进程同步是指并发进程之间存在一种制约关系，是指并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。到达才被唤醒。软件设计师软件设计师 pvpv操作操作进程的互斥进程的互斥1.1.调用调用p p操作测试消息是否到达。若消息尚未到达则操作测试消息是否到达。若消息尚未到达则s=0s=0，调，调用用p(s)p(s)后，让调用者称为等待信号量后，让调用者称为等待信号量s s的状态；若消息已的状态；若消息已经存在则经存在则

29、s0s0，调用，调用p(s)p(s)后进程不会成为等待状态而可继后进程不会成为等待状态而可继续执行。续执行。2.2.调用调用v v操作发送消息。任何进程要向进程发送消息时可调操作发送消息。任何进程要向进程发送消息时可调用用v v操作。若调用操作。若调用v v操作之前操作之前s=0s=0，表示消息产生且无等待，表示消息产生且无等待消息进程，这是调用消息进程，这是调用v(s),v(s),执行执行s:=s+1s:=s+1使使s0s0，意味着消，意味着消息已存在。若调用息已存在。若调用v v操作之前操作之前s s0 0，表示消息未产生前已，表示消息未产生前已有进程在等待消息，这是调用有进程在等待消息，

30、这是调用v(s)v(s)后释放一个等待消息者，后释放一个等待消息者，即表示该进程等待的消息已经到达可以继续执行。即表示该进程等待的消息已经到达可以继续执行。软件设计师软件设计师beginbeginbufferbuffer：integerinteger；sp,sg:semaphoresp,sg:semaphore；sp:=1; sg:=0;sp:=1; sg:=0;cobegincobegin process producer process producerbeginbegin l1 l1：produce a productproduce a product p p（spsp）；）； buff

31、erbuffer：=product=product； v v（sgsg）；）； goto l1goto l1endend；process consumerprocess consumerbeginbegin l2 l2： p p（sgsg）；）； take a product from buffertake a product from buffer； v v（spsp）；）； consumeconsume goto l2 goto l2endend；coendcoend；endend；软件设计师软件设计师【软件设计师考试【软件设计师考试20042004年年5 5月上午试题月上午试题23-24

32、23-24】 若有一个仓库，可以存放若有一个仓库，可以存放p1p1、p2p2两种产品，但是每次只能两种产品，但是每次只能存放一种产品要求：存放一种产品要求： w=p1 w=p1的数量的数量-p2-p2的数量的数量 -iwk (i -iwk (i、k k为正整数为正整数) )若用若用pvpv操作实现操作实现p1p1和和p2p2产品的入库过程，至少需产品的入库过程，至少需(23) (23) 个同个同步信号量及步信号量及 (24) (24) 个互斥信号量，其中，同步信号量的初个互斥信号量，其中，同步信号量的初值分别为值分别为 (25) (25) ，互斥信号量的初值分别为，互斥信号量的初值分别为 (2

33、6) (26) 。(23)a(23)a0 0b b1 1c c2 2 d d3 3(24)a(24)a0 0b b1 1c c2 2 d d3 3(25)a(25)a0 0b bi,k,0i,k,0c ci,ki,k d di-1,k-1 i-1,k-1 (26)a(26)a1 1b b1,11,1c c1,1,1 1,1,1 d di,k i,k 软件设计师软件设计师【软件设计师考试【软件设计师考试20042004年年5 5月上午试题月上午试题23-2423-24】 在某超市里有一个收银员，且同时最多允许有在某超市里有一个收银员，且同时最多允许有n n个顾客个顾客购物，我们可以将顾客和收银员

34、看成是两类不同的进程，且购物，我们可以将顾客和收银员看成是两类不同的进程，且工作流程如下图所示。为了利用工作流程如下图所示。为了利用pvpv操作正确地协调这两类进操作正确地协调这两类进程之间的工作，设置了三个信号量程之间的工作，设置了三个信号量s1s1、s2s2和和snsn，且初值分别，且初值分别为为0 0、0 0和和n n。这样图中的。这样图中的a a应填写应填写_(24)_(24)_，图中的，图中的b1b1、b2b2应应分别填写分别填写_(25)_(25)_，图中的，图中的c1c1、c2c2应分别填写应分别填写_(26)_(26)_。 软件设计师软件设计师软件设计师软件设计师(24)a.

35、p(s1) (24)a. p(s1) b bp(s2)p(s2) c cp(sn) p(sn) d dp(sn)p(sn)、 p(s1)p(s1)(25)a(25)ap(sn)p(sn)、v(s2) v(s2) b bp(sn)p(sn)、 v(s1)v(s1) c cp(s2)p(s2)、 v(s1) v(s1) d dv(s1)v(s1)、 p(s2)p(s2)(26)a(26)ap(s1)p(s1)、v(s2) v(s2) b bp(sn)p(sn)、 v(s1) v(s1) c cp(s2)p(s2)、 v(s1) v(s1) d dv(s1)v(s1)、 p(s2)p(s2)软件设计

36、师软件设计师l死锁死锁 死锁的概念死锁的概念 死锁产生的原因死锁产生的原因 死锁的必要条件死锁的必要条件 处理死锁的基本方法处理死锁的基本方法软件设计师软件设计师进程p2扫描仪打印机进程p1 t1 request( t1 request(打印机打印机) )； request(request(扫描仪扫描仪) )； t2 holding t2 holding 打印机；打印机； holding holding 扫描仪扫描仪时刻时刻 进程进程p p1 1 进程进程p p2 2 t3 request(t3 request(扫描仪扫描仪) )； t4 t4 request ( request (打印机打印

37、机) )；软件设计师软件设计师 死锁的概念：死锁的概念： 指多个进程因指多个进程因竞争资源竞争资源而造成的一种僵而造成的一种僵局，若无外力作用，这些进程都将永远不能局，若无外力作用，这些进程都将永远不能再向前推进再向前推进。死锁的基本概念 软件设计师软件设计师 死锁产生的原因死锁产生的原因 (1)(1)竞争资源竞争资源 当系统中供多个进程所共享的资源当系统中供多个进程所共享的资源, ,不足以同时满足不足以同时满足它们的需要时它们的需要时, ,引起它们对资源的竞争而产生死锁。引起它们对资源的竞争而产生死锁。 (2) (2) 进程推进顺序不当进程推进顺序不当 进程在运行过程中进程在运行过程中, ,

38、请求和释放资源的顺序不当请求和释放资源的顺序不当, ,导致导致了进程的死锁。了进程的死锁。软件设计师软件设计师扫描仪进程p1打印机进程p2软件设计师软件设计师 死锁产生的必要条件死锁产生的必要条件 (1)(1)互斥使用资源互斥使用资源 (2)(2)占有并等待资源占有并等待资源 (3)(3)不可剥夺资源不可剥夺资源 (4)(4)循环等待资源循环等待资源进程p2扫描仪打印机进程p1死死 锁锁软件设计师软件设计师l 处理死锁的基本方法处理死锁的基本方法 预防死锁预防死锁 避免死锁避免死锁 银行家算法银行家算法 检测死锁检测死锁 解除死锁解除死锁软件设计师软件设计师 避免死锁避免死锁 银行家算法银行家

39、算法 【基本步骤】【基本步骤】 (1)(1)进程首次申请时，测试该进程对资源的最大需求量，进程首次申请时，测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配，否则推迟。申请量分配，否则推迟。 (2)(2)当进程在执行中继续申请资源时，先测试该进程已占当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量，若超过了则拒绝。资源的最大需求量，若超过了则拒绝。软件设计师软件设计师(3)(3)若没有超过则再

40、测试系统现存的资源能否满足该进程若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足按当前的申请量分配资源，尚需的最大资源量，若能满足按当前的申请量分配资源，否则也要推迟分配。否则也要推迟分配。(4)(4)这样，能保证在任何时刻至少有一个进程可以得到所这样，能保证在任何时刻至少有一个进程可以得到所需要的全部资源而执行到结束，执行结束后归还的资源加需要的全部资源而执行到结束，执行结束后归还的资源加入到系统的剩余资源中，这些资源又至少可以满足一个进入到系统的剩余资源中，这些资源又至少可以满足一个进程的最大需求，最终保证了所有进程都能在有限的时间内程的最大需求，最终保证了所有进程

41、都能在有限的时间内得到需要的全部资源。得到需要的全部资源。软件设计师软件设计师【基本思想】【基本思想】 银行家算法是通过动态地检测系统中资源分配情况银行家算法是通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源的，在和进程对资源的需求情况来决定如何分配资源的，在能确保系统处于安全状态时才能把资源分配给申请者，能确保系统处于安全状态时才能把资源分配给申请者，从而避免系统发生死锁。从而避免系统发生死锁。软件设计师软件设计师【软件设计师考试【软件设计师考试20072007年年1111月上午试题】月上午试题】 某系统中有四种互斥资源某系统中有四种互斥资源r1r1、r2r2、r3r

42、3和和r4r4，可用资源数，可用资源数分别为分别为3 3、5 5、6 6和和8 8。假设在。假设在t0t0时刻有时刻有p1p1、p2p2、p3p3和和p4 p4 四个四个进程，并且这些进程对资源的最大需求量和已分配资源数如进程，并且这些进程对资源的最大需求量和已分配资源数如下表所示，那么在下表所示，那么在t0t0时刻系统中时刻系统中r1r1、r2r2、r3r3和和r4r4的剩余资源的剩余资源数分别为数分别为 （2525） 。如果从。如果从t0t0时刻开始进程按时刻开始进程按 （2626） 顺序顺序逐个调度执行，那么系统状态是安全的。逐个调度执行，那么系统状态是安全的。软件设计师软件设计师最大需

43、求量最大需求量 已分配资源数已分配资源数r1r1r2r2r4r4r3r3r1r1r2r2r3r3r4r4p1p11 12 23 36 61 11 12 24 4p2p21 11 12 22 20 01 12 22 2p3p31 12 21 11 11 11 11 10 0p4p41 11 12 23 31 11 11 11 1资源资源请求请求 系统可用资源数为系统可用资源数为: : 3 5 6 8 已分配资源数为：已分配资源数为： 3 4 6 7 系统剩余资源数为：系统剩余资源数为：0 1 0 1软件设计师软件设计师尚需资源尚需资源 已分配资源数已分配资源数r1r1r2r2r4r4r3r3r1r1r2r2r3r3r4r4p1p10 01 11 12 21 11 12 24 4p2p21 10 00 00 00 01 12 22 2p3p30 01 10 01 11 11 11 10 0p4p40 00 01 12 21 11 11 11 1资源资源请求请求系统剩余资源数为：系统剩余资源数为：0 1 0 1p3