第10讲处理器管理

1、第第 1 页页/89教学目标教学目标l了解处理器管理的基本概念及功了解处理器管理的基本概念及功能能l理解进程的概念及作业调度、进理解进程的概念及作业调度、进程调度方法程调度方法l了解用户接口的概念及功能了解用户接口的概念及功能第第 2 页页/89教学内容教学内容 （一）基本概念（一）基本概念 特权指令特权指令 管态管态 目态目态 p129 进程、程序的关系和区别 进程的类型、性质和状态 进程调度的策略和常用算法 静、动态优先数法、轮转法、分级调度法 进程的控制与管理 进程控制块pcb （二）进程的同步与互斥（二）进程的同步与互斥 （三）死锁（三）死锁 (四四) 作业管理与控制作业管理与控制第第

2、 3 页页/89教学内容及本单元涉及的章节教学内容及本单元涉及的章节l3.3 处理器管理处理器管理l3.6 操作系统的用户接口操作系统的用户接口第第 4 页页/89一、基本概念一、基本概念l程序 单道程序、多道程序、顺序程序、并发程序 顺序程序与并发程序的特征l进程 进程的特征、性质、状态及转换 进程控制 进程调度第第 5 页页/891、程序的有关概念、程序的有关概念程序 （ program） 是为解决某个问题用计算机语言或命令设计、 编写的一系列指令的有序集合。程序的顺序执行 一个程序通常分为若干个具有一定独立性的程序段，这些程序段是按逻辑步骤编排的，只有当当前程序段执行完成后，才将控制权转

3、交到下一个程序段并执行下一个程序段。第第 6 页页/89程序顺序执行举例一程序顺序执行举例一设有一个程序有三个程序段，分别执行 i（输入）、c（计算）和p（输出）操作。执行顺序为： i c p 只有输入了数据 ，才能计算这些数据，也只有计算产生了结果，才能输出它们。这些逻辑关系（顺序）是不能随意改变的。 结果结果 数据数据第第 7 页页/89 程序顺序执行举例二程序顺序执行举例二 假设有n个作业，每个作业都由三个程序段：输入段ii、计算段ci、输出段pi。在早期单道程序系统中，作业执行流为： 作业1 i1 c1 p1 作业2 i2 c2 p2 作业n in cn pn作作业业执执行行顺顺序序第

4、第 8 页页/89单道程序处理及特性单道程序处理及特性l一次只处理一个程序。 该程序独享系统资源。l单个程序的特性： 1、顺序性 操作按程序规定的顺序执行。 2、封闭性 程序在执行过程中独享系统资源，不受外界因素的干扰和影响。 3、可再现性 只要初始条件相同，无论以何种方式、速度、重复执行多少次，结果是相同的。第第 9 页页/89多道程序处理及特性多道程序处理及特性l同时将多个程序装入内存，并同时处理它们，整个系统资源为多个程序共享。l由于多道程序具有并发并发的特点，在任一时刻，系统内部（内存）同时运行着多个程序；受系统资源的制约，每个程序处理过程的行为是不确定的（系统内部状态因此而不同）。输

5、输 入入计计 算算 计计 算算计计 算算打打 印印 计计 算算打打 印印a(优先级高）优先级高）ca1a2b1b2b3c1c2多多 道道 程程 序序 并并 行行 运运 行行 示示 意意 图图a1 输输 入入b1 c1 打打 印印osb2osb3 打打 印印 a2 cpuoscpuc2cpucpucpucpucpub 程序并发执行举例程序并发执行举例第第 11 页页/89单道和多道程序处理的区别单道和多道程序处理的区别l在单道程序处理环境下，各逻辑步骤之间的关系是确定的、不受外界影响而改变的。l在多道程序处理环境下，并发处理机制中必然存在着直接或间接的相互依赖和相互制约的关系，从而使被处理的多道

6、程序失去了程序固有的特性：封闭性、可再现性。 第第 12 页页/89程序并发处理特征程序并发处理特征 1、失去了程序的封闭性，请分析下列程序 begin 用 cobegin和 coend表示程 n: integer 序能并发执行。 n：= 0 cobegin begin begin l1：program a l2：program b n := n + 1 print n goto l1 n :=0 end goto l2 coend end end 并发程序段并发程序段a 并发程序段并发程序段b加1打印清零第第 13 页页/89程序并发处理特征程序并发处理特征失去了程序的封闭性失去了程序的封闭

7、性分析：l若先执行程序a，n值大于0；再执行程序b时，先输出一个大于0的n值，然后，n值变为0。l若先执行程序b，n值等于0，先输出一个 0的n值；再执行程序a时，n值变为1。l由于程序a和程序b都是以各自独立的速度运行，则因速度不同而结果不同。所以并发执行程序失去了顺序程序的封闭性。 第第 14 页页/89程序并发处理特征程序并发处理特征程序与计算结果不再一一对应程序与计算结果不再一一对应l程序在顺序执行时，程序与“计算”间有着一一对应的关系。l在并发执行时，一个共享程序可为多个用户作业调度，而使程序处于多个执行中，从而形成了多个“计算”。因此，程序和计算间一一对应的关系不复存在。l如何表示

8、并发程序的特性？如何表示并发程序的特性？第第 15 页页/892 2、进程及有关概念、进程及有关概念进程 （process）就是程序的一次执行过程，是系统进行资源分配和调度的一个独立单位。“进程进程”这个概念是1966年美国麻省理工学院的j.h.sallexer提出的。l处理器（cpu）管理又称处理器调度。处理器是计算机系统中的重要资源，所以它管理的好坏在很大程度上直接影响系统的效率。l处理器管理又分两级：作业调度和进程调度。l进程管理是由程序管理进化而来，是和程序管理密不可分的。作业调度作业调度 见本见本ppt87第第 16 页页/89进程的性质进程的性质1）动态性）动态性 进程有自己的生命

9、周期。2）并发性）并发性 在系统中可以同时存在多个进程； os同时接受和处理多个进程。3）异步性）异步性 不同进程在逻辑上相互独立，有各自的运行“轨迹”。4）制约性）制约性 由于计算机资源是有限的，不同进程 共享cpu和i/o通道及设备，因此相 互制约。第第 17 页页/89进程与程序的区别进程与程序的区别进程是动态概念，程序是静止概念。进程是动态概念，程序是静止概念。进程的存在是暂时的，程序的存在是永久的。进程的存在是暂时的，程序的存在是永久的。如果程序是剧本，那么表演过程就是进程；如果程序是如果程序是剧本，那么表演过程就是进程；如果程序是菜谱，那么烹调过程就是进程菜谱，那么烹调过程就是进程

10、 ；电影胶片呢通过多次执行，一个程序可对应多个进程；通过调用关通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序系，一个进程可包括多个程序(父进程和子进程）父进程和子进程） 进程在结构上是由程序、数据集、进程控制块（进程在结构上是由程序、数据集、进程控制块（pcb）三部分组成的。三部分组成的。 pcb程程序序数数据据第第 18 页页/89进程的状态进程的状态l进程在其存在的过程中，它们的状态是不断发生变化的。一般来说，进程有三种基本状态：就绪状态、运行状态、等待状态。就绪状态就绪状态 已经获得投入运行所必需的一切资源，一旦分配到cpu，就可以立即执行。这是一种逻辑上可运

11、行状态（“万事俱备，只欠东风”）。运行状态运行状态 进程获得了cpu及其它一切所需资源，正在cpu上运行着,也是唯一在运行的。阻塞状态阻塞状态 由于资源得不到满足，进程运行受阻，处于暂停状态，等待资源分配后，再投入运行。第第 19 页页/89进程状态转换示意图进程状态转换示意图 运行状态运行状态阻塞状态阻塞状态 就绪状态就绪状态 进程调度进程调度 等待资源等待资源时间用完时间用完获得资源获得资源 进程调度进程调度 程序程序 来自作业来自作业 调度调度 交作业交作业 管理管理进程在整个生存周期中，由进程调度程序控制，在这进程在整个生存周期中，由进程调度程序控制，在这三种状态之间进行转换。三种状态

12、之间进行转换。第第 20 页页/893、进程管理、进程管理l进程管理的核心是进程的控制控制和调度调度。进程自投入运行时起，即交由进程调度程序管理。l根据什么标准选择怎样的进程投入运行？如何管理不同类型进程的资源？ 采用什么策略进行分配资源？ 。l这些都是进程管理的问题。第第 21 页页/89进程控制进程控制l进程控制的职责是对系统中全部进程实进程控制的职责是对系统中全部进程实行有效的管理；它应该具有行有效的管理；它应该具有创建进程、创建进程、撤消进程、改变进程状态撤消进程、改变进程状态的能力。的能力。l为便于对进程进行管理，进程具有特殊为便于对进程进行管理，进程具有特殊的构成形式。的构成形式。

13、pcb程程序序数数据据进程进程名名优先优先数数当前状态当前状态寄存器内容寄存器内容指向下一个指向下一个pcbpcb说明信息说明信息保留信息保留信息第第 22 页页/89进程的组成进程的组成l进程是程序在一个数据集合上的运行过程，它由三部分组成： 程序程序 它主要用于描述进程所要完成的功能。 数据集合数据集合 它包括程序执行时所需要的数据和工作区。 进程控制块进程控制块 （pcbprocess control block) 它记录进程控制信息，是进程动态特性的反映。第第 23 页页/89进程控制块进程控制块pcbl进程控制块pcb是进程的唯一标识。当创建一个新进程时，系统就建立一个pcb；它记录

14、和描述该进程的运行变化过程及参数变化。实际上，系统是通过实际上，系统是通过pcb对进程进行实际控制和管理的。通过感知对进程进行实际控制和管理的。通过感知pcb，感知，感知进程的存在。进程的存在。 pcb中包括： 进程名进程名 进程唯一的代号 进程优先级进程优先级 标明该进程要求cpu的迫切程度 进程当前状态进程当前状态 记录进程当前状态 寄存器内容寄存器内容 记录中断现场信息，以备恢复用第第 24 页页/89进程控制块进程控制块pcb的组织形式的组织形式 为了便于对进程调度管理，必须对进程进行合理的组织。进程控制块pcb是定长记录（类似于unix中的i索引结点表），采用两种组织方式。 线性表结

15、构 pcb组织形式 链表结构第第 25 页页/89pcb链表结构链表结构 运行队列运行队列 就绪队列就绪队列 阻塞队列阻塞队列pcbr队头队头指针指针pcbspcbs+1pcbs+2pcbtpcbt+1pcbt+2唯一在运行的第第 26 页页/89进程控制的实现进程控制的实现通过进程控制原语原语由若干条机器指令构成的，用以完成某一特定功能的一段程序。原语在执行期间是不可分割的。（1）创建原语：按进程调用者提供的参数，形成 pcb。（2）挂起（阻塞）原语：将某进程置于阻塞状态。（3）激活（唤醒）原语：将某进程置为就绪状态，等待 cpu。（4）撤消原语：撤消进程，释放所占用的所有资源，删除该程序的

16、pcb。第第 27 页页/894. 进程调度的任务及功能进程调度的任务及功能l进程调度任务 按一定的算法，动态地将处理器（cpu）分配给就绪队列中的某个进程，使之执行。l进程调度功能 记录系统中所有进程的状态、优先数和所用资源的情况。 当cpu空闲时，按一定的算法将cpu分配给某一进程、并确定cpu时间片的长度。 动态地调度进程、修改进程的状态、以及修改相应的排队队列。第第 28 页页/89进程调度方式进程调度方式剥夺方式 当“重要”或“系统”的进程出现时，便暂停正在执行的进程，立即将cpu分配给“重要”或“系统” 的进程。非剥夺方式 让正在执行的进程继续执行，直到该进程完成或发生其它事件，而

17、改变为其它状态后，才移交cpu控制权。 第第 29 页页/89进程调度算法进程调度算法l考虑进程调度算法的因素有： 1、尽量提高资源利用率，减少cpu空闲时间； 2、对一般作业采用较合理的平均响应时间； 3、应避免有的作业长期得不到响应的情况。l进程调度算法：优先数法轮转调度法分级调度法第第 30 页页/89常用的算法是把cpu分配给具有最高优先数的进程。静态优先数法进程优先数是在系统创建进程时确定的，一经确定，在进程运行期间就不再改变。动态优先数法进程优先数在进程运行中，随进程特性的变化不断修改进程的优先数，实现更精确的调度。优先数法优先数法第第 31 页页/89轮转调度法（动态法）轮转调度

18、法（动态法）l先将就绪态进程按fifo规则排成一个队列，将cpu划分为等长的时间片，分配给队列中的每个进程。l进程在运行了一个时间片q后，排至队尾，如此循环。l时间片q 的取值为： q 过小，系统开销增加； q 过大，又退化为fifo法。 一般来说， q 值取为 ： q = 100ms 为宜。第第 32 页页/89分级调度法（动态法）分级调度法（动态法）结合优先数法和轮转调度法分为具有较高优先数的前台队列和较低优先数的后台队列进程调度以固定的时间片把处理器分配给前台队列中的进程，仅当前台队列中的进程已全部完成或等待i/o操作时，才把处理器分配给后台进程。 第第 33 页页/89临界资源：临界资

19、源：一次仅允许一个进程使用的资源 。如打印机、读卡机、缓冲区、变量等。临界区：临界区：进程中使用临界资源的那段程序。各进程之间存在着相互制约、相互依赖的关系： 同同 步步: 两个事件的发生存在某种时序关系，如果系统中若干个进程要完成同一个任务，则进程之间要协调其推进的速度，以便正确完成作业运行，此即同步。请看两个例子请看两个例子 互互 斥：斥：对于某一临界资源，一组进程不能同时进入临界区去使用它。一个进入，其他必须等待。请看请看两个例子两个例子进程同步和互斥的实现方法进程同步和互斥的实现方法二、进程的同步与互斥二、进程的同步与互斥例例 1：进程同步的例子进程同步的例子电子邮件信箱电子邮件信箱发

20、送进程发送进程 a接收进程接收进程 b当信箱满时，发送进程只有等待接收进程取走信件，当信箱满时，发送进程只有等待接收进程取走信件，当信箱空时，接收进程必须等待发送进程发送信件。当信箱空时，接收进程必须等待发送进程发送信件。1 2n34例例2:x = fun1(y)*fun2(z)计算计算fun1(y)进程进程p2算完算完fun2(z)?取用取用p2计算结果计算结果计算计算fun2(z)设置计算完成标志设置计算完成标志终终 止止yn进程进程p1进程进程p2 两个协同工作进程的同步两个协同工作进程的同步 35例例1:公共地段交通十字路口的控制：公共地段互斥交通十字路口的控制：公共地段互斥36例例2

21、:x=countx=x+1 count=xy=county=y+1 count=y临界区临界区临界区临界区进进 程程 a进进 程程 b 进程进程a与与b对公共变量对公共变量count进行互斥操作，最终实现进行互斥操作，最终实现count增增加加2。若。若a与与b按下面顺序推进，结果按下面顺序推进，结果count只实现只实现增加增加1。a: x=count； a: x=x+1; count=x；b: y=count； b: y=y+1; count=y； 用用p-v原语对进程中信号量进行操作的方法（简称原语对进程中信号量进行操作的方法（简称p-v操作）。操作）。原语：由若干条机器指令构成，完成某

22、一特定功能的一段程序。原语：由若干条机器指令构成，完成某一特定功能的一段程序。p原语操作过程：原语操作过程： p操作记为操作记为 p（s），其中，其中s为一信号量，其执行顺序完成以下为一信号量，其执行顺序完成以下两个动作：两个动作：（1） s：=s 1，表示申请使用一个资源；，表示申请使用一个资源；（2） 若若s 0，表示系统中有资源可用，现进程可继续执行。表示系统中有资源可用，现进程可继续执行。（3） 若若s 0，表示系统中没有可用资源，则置该进程阻塞状表示系统中没有可用资源，则置该进程阻塞状 态，到态，到s信号量信号量 的队列中去的队列中去等等待，直到其他进程在待，直到其他进程在s上上 执

23、行执行v操作释放它为止。操作释放它为止。 信号量的概念和信号量的概念和p、v原语是荷兰科学家提出的。把交通原语是荷兰科学家提出的。把交通管理的信号灯方法搬到了操作系统中。管理的信号灯方法搬到了操作系统中。所谓信号量是一个与队列有关的整型变量，表示系统中某类所谓信号量是一个与队列有关的整型变量，表示系统中某类资源的数量。当其值大于资源的数量。当其值大于0时，表示系统中尚有可用资源；当时，表示系统中尚有可用资源；当其值为负时，其绝对值表示还欠缺的资源数。信号量的值仅其值为负时，其绝对值表示还欠缺的资源数。信号量的值仅能由能由p操作和操作和v操作来改变，操作系统利用它的状态对进程和操作来改变，操作系

24、统利用它的状态对进程和资源进行管理。资源进行管理。进程的同步与互斥的实现方法进程的同步与互斥的实现方法v原语操作过程：原语操作过程： v操作记为操作记为 v（s），），其中其中s为一信号量，其执行顺序完成为一信号量，其执行顺序完成以下两个动作：以下两个动作：（1） s：=s+1，表示释放一个资源；，表示释放一个资源；（2） 若若s 0，表示系统中没有等待该资源的进程，现进程表示系统中没有等待该资源的进程，现进程 可继续执行（可继续执行（走走）。）。（3） 若若s 0，表示系统中有等待该资源的进程，则唤醒表示系统中有等待该资源的进程，则唤醒s信信 号量队列中的第一个进程，使其插入到就绪队列，现号

25、量队列中的第一个进程，使其插入到就绪队列，现 进程继续执行。进程继续执行。 39第第 40 页页/89（1）实现进程同步（）实现进程同步（a）非对称制约）非对称制约（2）实现进程同步（）实现进程同步（b）双向制约）双向制约生产者与消费者问题生产者与消费者问题（3）实现进程互斥）实现进程互斥 (1)直接通信（消息缓冲区）直接通信（消息缓冲区） (2)信箱通信信箱通信 (3)基于共享数据结构或共享存储区通信基于共享数据结构或共享存储区通信p-v操作的应用操作的应用进程通信进程通信s=0把把 p-v p-v 操操 作作 用用 于于 进进 程程 同同 步步 进程进程ac: p(s)同步点同步点同步条件

26、同步条件 进程进程bv(s)假定进程假定进程a前进到前进到c点时，必须等到进程点时，必须等到进程b执行完同步条件才能继续前执行完同步条件才能继续前进进。为了实现进程为了实现进程a与进程与进程b在在c点同步，设置信号量点同步，设置信号量s初始值为初始值为0。在进程。在进程a的的c点处设置点处设置p操作，在进程操作，在进程b设置设置v操作。假定操作。假定a先于先于b到达到达c点，它要在点，它要在s上执行上执行p操作，使操作，使s=-10表示表示有数据有数据；s2表示缓冲区中的数据是否被取走，表示缓冲区中的数据是否被取走， s20表示已取走，表示已取走，有有空空的缓冲的缓冲区区；初初 值值 ：s1=

27、0， s2=0；查询进程查询进程s把查询结果把查询结果写到缓冲区写到缓冲区v(s1)p(s2 ) 打印进程打印进程pp(s1) 把缓冲区内把缓冲区内容打印输出容打印输出v(s2) 42生产者进程生产者进程l1:生产物品生产物品p(s1)缓冲区缓冲区 物品物品v(s2)消费者进程消费者进程c1:p(s2)从缓冲区取物品从缓冲区取物品v(s1)消费物品消费物品s1=1;s2=0;43为使这段操作能互斥进行，设置为使这段操作能互斥进行，设置s1初值为初值为1， s2初值为初值为0。 其中：其中：s1缓冲区中是否有空，缓冲区中是否有空， s10 有空有空缓冲缓冲区区；s2 缓冲区中是否有物品可供消费，

28、缓冲区中是否有物品可供消费， s20有物品有物品。则无论在何处中断，均能进行协调工作。则无论在何处中断，均能进行协调工作。s=1进程进程a的的临界区临界区p(s)进程进程av(s)进程进程b的的临界区临界区p(s)进程进程bv(s)为使这段操作能互斥进行，设置一个信号量为使这段操作能互斥进行，设置一个信号量s初值为初值为1，在每个地段的入口处，安，在每个地段的入口处，安排对排对s的的p操作，出口处做操作，出口处做v操作。谁先对操作。谁先对s做做p操作，就会使操作，就会使s的值由的值由1变为变为0，且，且自己获准进入临界区。另一进程再对自己获准进入临界区。另一进程再对s进行进行p操作，试图进入自

29、己的临界地段，操作，试图进入自己的临界地段，就会因为就会因为s的值由的值由0变为变为-1 而受到阻挡。只有等到在临界地段内的进程退出临界而受到阻挡。只有等到在临界地段内的进程退出临界地段时对地段时对s做做v操作，使操作，使s的值由的值由-1变为变为0，才会解除这一阻挡而放行，从而实现，才会解除这一阻挡而放行，从而实现进程的互斥。进程的互斥。44y=county=y+1count=y临界区临界区v(s)p(s)进程进程bx=countx=x+1count=x临界区临界区v(s)p(s)进程进程a设置设置s，初值为，初值为145da发发送送区区senddbreceive接接收收区区1a进程进程b进

30、程进程pcbb进程进程 直直 接接 通通 信信 p136.send(b, da).b5hello第一个消息缓冲区第一个消息缓冲区a5hellonptr h-ptra5hello.receive(a,db)46mutexssmsendp(sml)申请格子申请格子把信件从信件发送把信件从信件发送区读到信箱格子中区读到信箱格子中v(sm2)receivep(sm2)控制是否有信件控制是否有信件把第一个格子中的信把第一个格子中的信件读到信件接收区件读到信件接收区v(sm1)申请格子由信号量申请格子由信号量sm1控制（控制（有格子有格子）sm2控制格子里控制格子里是否是否有信件有信件47信信箱箱通通信信

31、初值初值sm1=1， sm2=0、死锁产生的原因（四个必要条件）、死锁产生的原因（四个必要条件） （）资源不能共享（资源独占性）。（）资源不能共享（资源独占性）。 （）资源采用动态分配原则：资源在等待新资源时，继续占（）资源采用动态分配原则：资源在等待新资源时，继续占有已分配到的资源。有已分配到的资源。 （c）资源的不可剥夺性：一个进程占有的资源不能被别的进）资源的不可剥夺性：一个进程占有的资源不能被别的进程强行抢占。程强行抢占。 （d）允许进程间非法交叉推进顺序的存在：导致循环等待资）允许进程间非法交叉推进顺序的存在：导致循环等待资 源，无法前进。源，无法前进。 48三、死三、死 锁锁死锁死

32、锁：每个进程所要求的资源都已被另一个进程占用，出现没每个进程所要求的资源都已被另一个进程占用，出现没有一个进程能继续运行，这种情况称有一个进程能继续运行，这种情况称“死锁死锁”。打印机打印机进程进程a进程进程b读卡机读卡机进程进程a申请到打印机申请到打印机进程进程a需要读卡机需要读卡机进程进程b申请到读卡机申请到读卡机进程进程b需要打印机需要打印机49例如：进程例如：进程a和和b以下面的推进速度前进，导致死锁。以下面的推进速度前进，导致死锁。 1. a：申请打印机：申请打印机 2. b：申请读卡机：申请读卡机 3. a：申请读卡机：申请读卡机 4. b：申请打印机：申请打印机第第 50 页页/

33、89*死锁的检测与恢复死锁的检测与恢复允许死锁产生，当死锁发生时允许死锁产生，当死锁发生时能检测出来，并且有能力处理，进行恢复。能检测出来，并且有能力处理，进行恢复。 关于资源独占性：采用可以使非共享设备变为共享设关于资源独占性：采用可以使非共享设备变为共享设备。备。解决死锁的办法解决死锁的办法*死锁的预防死锁的预防破坏产生死锁的破坏产生死锁的4个必要条件中的任何一个。个必要条件中的任何一个。 破坏破坏“资源的不可剥夺性资源的不可剥夺性”（申请不到资源时，释放（申请不到资源时，释放原先已占有的，进入等待，以后再一起申请）。原先已占有的，进入等待，以后再一起申请）。 破坏对资源采用动态的部分分配

34、原则（每个进程必须提破坏对资源采用动态的部分分配原则（每个进程必须提出它所需要的全部资源，只有完全满足时，才能启动）。出它所需要的全部资源，只有完全满足时，才能启动）。 破坏循环等待。破坏循环等待。* 死锁的避免死锁的避免躲避死锁的发生。躲避死锁的发生。采用虚拟技术，使采用虚拟技术，使非共享设备变成共享设备非共享设备变成共享设备，以避免死锁。，以避免死锁。用户用户1用户用户2用户用户3输出输出输出输出输出输出打印打印打印机打印机主主 机机51破坏资源独占性破坏资源独占性假脱机技术（教材假脱机技术（教材p153）系统资源进行统一编号。进程申请使用资源时，系统资源进行统一编号。进程申请使用资源时，

35、必须严格按照编号的升序进行。必须严格按照编号的升序进行。 进进 程程资资 源源abc1、卡片输入机卡片输入机 （3台）台） 2、行式打印机行式打印机 （2台）台）*3、磁带机、磁带机（1台）台）*52破坏循环等待破坏循环等待打破环路条件：将所有资源编号，申请时按顺序打破环路条件：将所有资源编号，申请时按顺序申请，先申请小号，再申请大号，这样，能保证申请，先申请小号，再申请大号，这样，能保证申请到最大号者，肯定运行完成。申请到最大号者，肯定运行完成。第第 53 页页/89例：三个进程例：三个进程p1,p2,和和p3,所需要磁带机分别为所需要磁带机分别为10，4，9台，系统中共台，系统中共12台。

36、台。t0时刻时刻 最大需求最大需求p110p24p39t0时刻存在一个安全序列时刻存在一个安全序列 所以系统安全。所以系统安全。如果如果 p3 请求请求 1 台台, 状态发生变化状态发生变化. 已分配已分配 522可用可用3还需还需527找不到一个安全序列找不到一个安全序列. 状态不安全状态不安全. 请求不能满足。请求不能满足。 如果如果 p1 请求请求 1 台台, 状态发生变化状态发生变化. 结果如何？结果如何？如果如果 p2 请求请求 1 台台, 状态发生变化状态发生变化. 结果又如何？结果又如何？若把题中的若把题中的12改为改为11，则，则t0时刻系统是不安全的，因为这时时刻系统是不安全

37、的，因为这时系统中虽有系统中虽有2台可用设备，但不存在安全序列。当然，若不台可用设备，但不存在安全序列。当然，若不按照安全序列分配资源，安全状态可能变为不安全状态。按照安全序列分配资源，安全状态可能变为不安全状态。第第 54 页页/89死锁的避免 l死锁的避免是这样一种对付死锁的办法：系统在运行死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取过程中采取动态的资源分配策略，保证系统不进入可动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。死锁发生。l常用的避免死锁的算法是常用的避免死锁的算法是“银行家

38、算法银行家算法”，系统采用，系统采用此法给进程分配资源时，需先判断此法给进程分配资源时，需先判断“如果分配，系统如果分配，系统状态是否安全状态是否安全”，这很像银行家，这很像银行家放贷前的思考过程放贷前的思考过程。 第第 55 页页/89(1)(1)安全状态与安全序列安全状态与安全序列 l1)1)安全状态安全状态 若在某一时刻，系统能按某种进程顺序，如若在某一时刻，系统能按某种进程顺序，如，来为每个进程分配其所需的资源，直至最大需求，使每个进程来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为均可顺利完成。则称此时系统的状态为安全状态安全状态，称这样的一，

39、称这样的一个进程序列个进程序列为为安全序列安全序列。l2)2)不安全状态不安全状态 若在某时刻，系统无法找到一个安全序列，则称系统处于若在某时刻，系统无法找到一个安全序列，则称系统处于不不安全状态安全状态。第第 56 页页/89注意：注意： （1）系统在某一时刻的安全序列可能不唯一，但这不）系统在某一时刻的安全序列可能不唯一，但这不影响对系统安全性的判断。影响对系统安全性的判断。（2）安全状态是非死锁状态，而不安全状态并不一定）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅有可

40、能进入死锁状态。而系统处于不安全状态则仅仅有可能进入死锁状态。 安全状态安全状态不安全状态不安全状态死锁状态死锁状态第第 57 页页/89l银行家算法银行家算法 银行家拥有一笔周转资金银行家拥有一笔周转资金 客户要求分期贷款，如果客户能够得到各期客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不贷款，就一定能够归还贷款，否则就一定不能归还贷款能归还贷款 银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐l用银行家算法避免死锁用银行家算法避免死锁操作系统操作系统 比作比作（银行家）（银行家）操作系统管理的资源操作系统管理的资源 比作比作( (周转资金周转资

41、金) )进程进程 比作比作（要求贷款的客户）（要求贷款的客户） 为了避免死锁的发生，系统对进程提出的每一个资源请为了避免死锁的发生，系统对进程提出的每一个资源请求，先不是真正去分配，而是根据当时资源的使用情况，按求，先不是真正去分配，而是根据当时资源的使用情况，按一定的算法去进行模拟分配后的结果。只有当探测结果不会一定的算法去进行模拟分配后的结果。只有当探测结果不会导致死锁，才真正接收进程提出的这一请求。导致死锁，才真正接收进程提出的这一请求。类似下棋类似下棋 常用的算法是常用的算法是“银行家算法银行家算法” （1965年提出）。年提出）。银行家算法的思想银行家算法的思想: （假定（假定在在单

42、类资源的分配单类资源的分配上实行这一算法）。上实行这一算法）。死锁的避免死锁的避免每个用户必须预先申请它所需的贷款总数，且此数值不能超过银每个用户必须预先申请它所需的贷款总数，且此数值不能超过银行资金总数；行资金总数；每个用户每次只能向银行申请一个单位贷款数；每个用户每次只能向银行申请一个单位贷款数；银行根据当时的资金情况，可能立即满足用户申请，或者需要用银行根据当时的资金情况，可能立即满足用户申请，或者需要用户等待一段时间；户等待一段时间；当用户贷款总数达到申请数后，必须在有限时间内一次归还所有当用户贷款总数达到申请数后，必须在有限时间内一次归还所有贷款。贷款。第第 59 页页/89 如果所

43、有进程的如果所有进程的“能执行完能执行完”均为均为1，表示接受这次请求是安全的；否则暂时，表示接受这次请求是安全的；否则暂时不能接受进程的这次资源请求。不能接受进程的这次资源请求。 如果找到了，就假设它获得如果找到了，就假设它获得了最大资源数，并运行结束。于是了最大资源数，并运行结束。于是把它的把它的“能执行完能执行完”标志置为标志置为1。这样就能假定收回它使用的所有资这样就能假定收回它使用的所有资源，使系统剩余资源数增加。源，使系统剩余资源数增加。 在这一假设下，检查每个进程对资源的还需要数。在这一假设下，检查每个进程对资源的还需要数。看能否找到一个进程，其还需数目小于系统剩余资源数。看能否

44、找到一个进程，其还需数目小于系统剩余资源数。如果找不到，那么系统就有可能死锁，因如果找不到，那么系统就有可能死锁，因为任何进程都无法运行结束。为任何进程都无法运行结束。 在安全状态下，系统接到进程的资源请求后，在安全状态下，系统接到进程的资源请求后，先假定接受这一请求，把需要的资源分配给这个进程。先假定接受这一请求，把需要的资源分配给这个进程。 单种资源银行家算法的基本思想单种资源银行家算法的基本思想单种资源银行家算法：单种资源银行家算法：将所有进程的“能执行完”标志清0假定接受该请求,把资源分配给进程将系统当前所有剩余资源与”能执行完”标志为0的进程还需资源数比较,找出一个能满足其所有需求的

45、进程找到了吗？将该进程的”能执行完”标志置为1,系统收回它所要求的全部资源数yn检查所有进程的“能执行完”标志还有” 能执行完 ”标志为0的进程吗？这一请求不安全,暂时不予接受yn这一请求是安全的,可以分配. 在在“能执行完能执行完”标志为标志为0的进程中重复以上两步，直的进程中重复以上两步，直到找不到资源还需数小于系统剩余资源数的进程时为止。到找不到资源还需数小于系统剩余资源数的进程时为止。 进程已分配数还需要数a13b42c53系统剩余2进程已分配数 还需要数a22b42c53系统剩余1例例1：假定某系统有：假定某系统有12台磁带机，台磁带机，a 最大需要量最大需要量4 b 最大需要量最大

46、需要量6 c 最大需要量最大需要量8单种资源单种资源银行家算法实例银行家算法实例(a)(b)经过若干次申请、分经过若干次申请、分配，系统的状态配，系统的状态（a）状态时，若进程）状态时，若进程a提出提出申请申请1台磁带机后，采用银行台磁带机后，采用银行家算法系统假定分配后的状家算法系统假定分配后的状态态一个安全序列一个安全序列b a c状态不安全. 请求不能满足第第 61 页页/89例例2 42 4个客户每个都有一个贷款额度个客户每个都有一个贷款额度单种资源单种资源银行家算法的基本思想银行家算法的基本思想已使用已使用：已分配；：已分配；最大最大：一共需求：一共需求（b）一个安全序列）一个安全序

47、列m b a s（c)在（在（b）状态下答应）状态下答应barbara的申请，将不安全的申请，将不安全第第 62 页页/89l对每个请求进行检查，是否会导致不安全状态。对每个请求进行检查，是否会导致不安全状态。若是，则不满足该请求；否则便满足若是，则不满足该请求；否则便满足l检查状态是否安全的方法：是看它是否有足够检查状态是否安全的方法：是看它是否有足够的资源满足一个距最大需求最近的客户，如此的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。状态是安全的，最初的请求可以批准。 系统拥有某类资

48、源系统拥有某类资源10个个进程进程已有资源数已有资源数还要申请资源数还要申请资源数p44q22r27a a、单项资源的银行家算法、单项资源的银行家算法第第 63 页页/89 如果存在这种进程，那么假定它已获得需要的所有资源，并完成工作，把它的“能执行完”标志设置成1。收回它占用的资源，更新向量v。 检查还需资源表中是否有一个进程的行向量小于或等于向量v。如果没有，那么系统就可能会死锁，因为现在任何进程都无法完成了。 多种资源银行家算法的执行步骤多种资源银行家算法的执行步骤 系统设两张表：“分配资源表分配资源表”，记录已分配给各进程的资源数；“还需资源还需资源表表” ，记录各进程还需要的资源数。

49、设3个向量：r记录各种资源的总数，a记录各种资源已分配数，v记录各种资源的剩余数。 进程 磁带机 绘图仪 打印机 cd-roma3011b0100c1110d1101e0000进程 磁带机 绘图仪 打印机 cd-roma1100b0112c3100d0010e2110已分配资源表还需资源表r 6 3 4 2 (资源总数)a 5 3 2 2 (已分配数)v 1 0 2 0 (剩余数).假定接受一个进程提出的资源请求，修改向量a和v。 .重复以上两步，直至再也找不到行向量小于或等于向量v的进程。 检查所有进程的 “能执行完” 标志。若这个标志都是1，则表示都能顺利地完成。因此，接受资源分配后导致的

50、新状态是安全的；如果仍存在“能执行完”标志为0的进程，则说明这一请求所导致的状态是不安全的，应暂时拒绝该请求。 多类资源的分配多类资源的分配 （habermann算法算法 p140）第第 64 页页/89b b、多项资源的银行家算法、多项资源的银行家算法先定义几个向量： resource =(r1,r2,rm) :系统各类资源的总数； available =(v1,v2,vm) :系统未分配的资源数量v向量第第 65 页页/89l最大需求矩阵最大需求矩阵-每个进程对每类资源的每个进程对每类资源的最大最大需求需求量量,c,cijij表示进程表示进程p pi i需需r rj j类资源最大数类资源最

51、大数claim=c11c12c1mc11c11c11cn1 cn1cnm第第 66 页页/89分配矩阵分配矩阵表示进程当前已分得的资源数表示进程当前已分得的资源数,a,aijij表示进程表示进程p pi i已分已分到到r rj j类资源的个数类资源的个数 allocation=a11a12a1ma21a21a21an1 an1anm第第 67 页页/89 下列关系式确保成立下列关系式确保成立r ri i=v=vi i+a+akiki 对对i=1,.,m,k=1,.,n; i=1,.,m,k=1,.,n; 表示表示所有资源要么已被分配、要么尚可分配所有资源要么已被分配、要么尚可分配 c cki

52、ki rrj j 对对i=1,.,m,k=1,.,n; i=1,.,m,k=1,.,n; 表示进表示进程申请资源数不能超过系统拥有的资源总数程申请资源数不能超过系统拥有的资源总数 a akiki c ckiki 对对i=1,.,m,k=1,.,n; i=1,.,m,k=1,.,n; 表示表示进程申请任何类资源数不能超过声明的最大进程申请任何类资源数不能超过声明的最大资源需求数资源需求数第第 68 页页/89汇总向量汇总向量r-r-总的资源、总的资源、 a-a-已分配资源、已分配资源、 v-v-剩余资源剩余资源ravppt63状态下安全判断，安全序列？状态下安全判断，安全序列？see 教材p14

53、4例题 注意f向量第第 69 页页/89总的资源总的资源r r、已分配资源、已分配资源a a、剩余资源、剩余资源v v 图示为安全状态，安全序列（图示为安全状态，安全序列（d d，a a，e e，b b，c c） rav第第 70 页页/89. 系统中有ag共7个进程，6个同类资源rw，当前的资源所属关系如下：l死锁的检测死锁的检测与与恢复恢复1. 利用资源分配图检测死锁利用资源分配图检测死锁rascdfwugtbev.a得到资源r，需要资源s；.b不占有资源，需要资源t；.c不占有资源，需要资源s；d得到资源u和s，需要资源t；.e得到资源t，需要资源v；f得到资源w，需要资源s；g得到资源

54、v，需要资源u。2. 利用表格检测死锁利用表格检测死锁环路资源 占用的进程进程 等待的资源rasctbubvaat进程 等待的资源atbcsv 通过建立“资源分配表”和“进程等待表”，随时检测资源的分配是否构成环路。假定现有3个进程ac，有5个同类型资源rv。see ppt75 资源分配表进程等待表进程等待表3. 死锁的恢复死锁的恢复 一是删除环中的若干进程，释放占用的资源，使其他进程能继续运行；二是临时把某个资源从占用者手中剥夺，给另一个进程使用；三是周期地记录各进程执行情况。一旦检测到死锁，就按记录的文件进行回退，让损失减到最小。 第第 71 页页/89当系统为进程分配资源时，若未采取任何

55、限制性措施保证不进入死锁状态，则系统必须提供解除死锁的手段。1.资源分配图资源分配图r1 r2 p1p2用方框代表资源，圆圈代表进程。画一条由资源到进程的有向边，表示把该资源分配给这个进程；画一条由进程到资源的有向边，表示该进程要申请这个资源。这样的图就是所谓的 “ 资源分配资源分配图图 ”。第第 72 页页/89r1 r2 p1p2r1 r2 p1p2r1 r2 p1p2第第 73 页页/89l例如，对于例如，对于p=p1,p2,p3，r=r1,r2,r3,r4，e=，它的资源分配图如，它的资源分配图如图所示。图所示。l 可以证明，如果资源分可以证明，如果资源分配图中没有环路，则系统中没配图

56、中没有环路，则系统中没有死锁；如果图中存在环路，有死锁；如果图中存在环路，则系统中可能存在死锁。如果则系统中可能存在死锁。如果每个资源类中均只包含一个资每个资源类中均只包含一个资源，则环路的存在即意味着死源，则环路的存在即意味着死锁的存在，此时，环路是死锁锁的存在，此时，环路是死锁的充分必要条件。在图中，有的充分必要条件。在图中，有两个环：两个环：p1p2p3r1r3r4r2第第 74 页页/89图5-7 资源分配图(含环路) p1p2p3r1r3r4r2p1r1p2r3p3r2p1 p2r3p3r2p2p1、p2、p3均处于死锁状态。均处于死锁状态。see 教材p143例题资源号资源号占有资

57、源的占有资源的进程号进程号a1b3c2d2e1进程号进程号等待资源等待资源1c2 资资 源源 分分 配配 表表进进 程程 等等 待待 表表进程号进程号等待资源等待资源1c2b3e(1)(2)(3)e132bc进程间对资源的循环等待进程间对资源的循环等待对进程对进程资源状态图的化简可通过对系统所有资源资源状态图的化简可通过对系统所有资源和进程进行编号，并设置一张资源分配表和一张进和进程进行编号，并设置一张资源分配表和一张进程等待表来实现：程等待表来实现：假设系统现在有资源为假设系统现在有资源为a、b、c、d、e。系统有。系统有3个个进程，分别用编号进程，分别用编号13表示。在某一时刻，系统资表示

58、。在某一时刻，系统资源分配表如图（源分配表如图（1）所示，假定这时各进程按下列）所示，假定这时各进程按下列方式提出申请资源：方式提出申请资源：进程进程1申请资源申请资源c 进程进程2申请资源申请资源b 进程进程3申请资源申请资源e 经过考察资源分配表并填写资源申请表，发现经过考察资源分配表并填写资源申请表，发现出现了循环等待链，产生了死锁。出现了循环等待链，产生了死锁。 一经发现死锁，一经发现死锁，必须立即解除。必须立即解除。出 现 进 程 循 环 链 的 现 象进程1ae进程3c进程2bd第第 77 页页/893 死锁定理死锁定理当且仅当当且仅当s的资源分配图是不可完全化简的，的资源分配图是

59、不可完全化简的，s为死锁状态。为死锁状态。死死锁锁的解除：的解除：1)终止死锁进程；终止死锁进程；2)按一定顺序中止进程直至释放到有足够的资源来完成按一定顺序中止进程直至释放到有足够的资源来完成剩下的进程为止；剩下的进程为止； 3)从被锁住进程中强迫剥夺资源以解除死锁。从被锁住进程中强迫剥夺资源以解除死锁。第第 78 页页/89 用户与操作系统之间的接口用户与操作系统之间的接口 程序一级的接口程序一级的接口系统调用系统调用 作业控制一级的接口作业控制一级的接口 作业状态及转换图作业状态及转换图 作业调度作业调度 作业控制作业控制四、作业管理与控制四、作业管理与控制第第 79 页页/89人机界面

60、（人机界面（hci-human computer interface）l用户接口实质上是提供了一个人机界面，包括：用户接口实质上是提供了一个人机界面，包括： 基于字符界面的接口基于字符界面的接口 基于图形用户界面接口（基于图形用户界面接口（gui-graphical user interface） 多媒体接口多媒体接口 其他特殊类型的接口其他特殊类型的接口 用用户户接接口口图形用户接口图形用户接口多媒体型接口多媒体型接口字符型及其他特殊型接口字符型及其他特殊型接口基于基于motif基于基于windows普通普通用户用户接口接口规范规范系统级或域级用户接口规范系统级或域级用户接口规范系统级或域级