操作系统课件

1、第五章第五章 调度与死锁调度与死锁 多道程序系统中，一个作多道程序系统中，一个作 业从提交到执行通常都要业从提交到执行通常都要 经过处理器调度。本章将经过处理器调度。本章将 讨论高、中、低三级调度讨论高、中、低三级调度 以及进程的死锁。以及进程的死锁。 5.1 三级调度的概念 一、高级调度一、高级调度 v为作业调度，又称为长程（宏观）调度为作业调度，又称为长程（宏观）调度 v作业的四个状态：作业的四个状态： 提交、后备（收容）、运行、完成提交、后备（收容）、运行、完成 提交提交后备后备运行运行 完成完成 5.1 三级调度的概念 提交提交后备 注册 作业调度作业调度 运行 运行运行 阻塞阻塞就绪

2、就绪 完成完成 就绪就绪阻塞阻塞 外存 进程调度进程调度 交换调度交换调度 内存 5.1 三级调度的概念 v作业调度：按一定原则从外存后备作业中选若干作业调度：按一定原则从外存后备作业中选若干 个进入内存运行个进入内存运行 二、低级调度二、低级调度 v为进程调度，又称短程（微观）调度为进程调度，又称短程（微观）调度 v进程调度：按一定策略从就绪队列中选一个到进程调度：按一定策略从就绪队列中选一个到cpucpu 上运行上运行 5.1 三级调度的概念 三、中级调度三、中级调度 v为交换调度，又称中程调度为交换调度，又称中程调度 v交换调度：按一定原则，在内外存间进行进程对交换调度：按一定原则，在内

3、外存间进行进程对 换换 说明：说明： 1 1）三级调度不是必须的）三级调度不是必须的 2 2）三级调度的频率是不同的）三级调度的频率是不同的 5.1 三级调度的概念 四、调度队列模型四、调度队列模型 1.1.仅由进程调度的调度队列模型仅由进程调度的调度队列模型 2.2.具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 3.3.具有三级调度的调度队列模型具有三级调度的调度队列模型 5.1 三级调度的概念 五、选择调度方式和调度算法的准则五、选择调度方式和调度算法的准则 1.1.进程调度采用的两种调度方式进程调度采用的两种调度方式 （1 1）非抢占方式）非抢占方式 （2 2）抢占方

4、式）抢占方式 2.2.准则准则 （1 1）面向系统的准则）面向系统的准则 提高吞吐量、提高资源利用率提高吞吐量、提高资源利用率 5.1 三级调度的概念 （2 2）面向用户的准则）面向用户的准则 A A 周转时间短周转时间短 周转时间：是作业从提交给系统开始，到作业完成周转时间：是作业从提交给系统开始，到作业完成 为止的时间间隔。为止的时间间隔。 周转时间包括四个部分：周转时间包括四个部分： 作业在外存后备队列上的等待时间作业在外存后备队列上的等待时间 进程在内存就绪队列上的等待时间进程在内存就绪队列上的等待时间 进程在进程在cpucpu上的执行时间上的执行时间 进程等待进程等待I/OI/O的时

5、间的时间 5.1 三级调度的概念 v 若若TiTi为第为第i i个作业的周转时间，则个作业的周转时间，则 Ti TiTeiTeiTsiTsi 其中其中TeiTei是作业完成时间，是作业完成时间， Tsi Tsi是作业提交时间是作业提交时间 v 平均周转时间平均周转时间T T v 作业带权周转时间作业带权周转时间WiWi v 作业的平均带权周转时间作业的平均带权周转时间 W W n 1 n 1 n i Ti 1 Tri Ti n i Tri Ti 1 5.1 三级调度的概念 B B 响应时间快响应时间快 C C 截至时间的保证截至时间的保证 D D 优先权的准则优先权的准则 : :让紧急的任务优

6、先处理让紧急的任务优先处理 5.2 常用调度算法 一、先来先服务（一、先来先服务（FCFSFCFS） 1.1.算法算法 First Come First ServedFirst Come First Served 作业调度作业调度 进程调度进程调度 5.2 常用调度算法 2.2.举例举例 设有设有3 3个作业依次到达单道系统，若作业调度采用个作业依次到达单道系统，若作业调度采用 FCFSFCFS算法，则填写下表算法，则填写下表 作业名作业名到达到达 时间时间 运行运行 时间时间 完成完成 时间时间 周转周转 时间时间 带权周带权周 转时间转时间 A A8.08.01.51.5 B B9.09.

7、01.01.0 C C9.39.30.60.6 9.5 10.5 11.1 1.5 1.5 1.8 1 1.5 3 5.2 常用调度算法 v平均周转时间：平均周转时间： T=(1.5+1.5+1.8)/3=1.6 (T=(1.5+1.5+1.8)/3=1.6 (小时小时) ) v平均带权周转时间：平均带权周转时间： W=(1+1.5+3)/3=1.83W=(1+1.5+3)/3=1.83 优缺点：优缺点： 优点：容易，公平优点：容易，公平 缺点：有利于长作业缺点：有利于长作业/进程，不利于短作业进程，不利于短作业/进程进程 5.2 常用调度算法 二、短作业（进程）优先调度算法（二、短作业（进程

8、）优先调度算法（SJF/SPFSJF/SPF） 1.1.算法算法 Short JobShort Job（ProcessProcess）FirstFirst 作业调度作业调度 进程调度进程调度 5.2 常用调度算法 2.2.举例举例 设有设有3 3个作业依次到达单道系统，若作业调度采用个作业依次到达单道系统，若作业调度采用 SJFSJF算法，则填写下表算法，则填写下表 作业名作业名到达时间到达时间运行时间运行时间完成时间完成时间周转时周转时 间间 带权周转带权周转 时间时间 A A8.08.01.51.5 B B9.09.01.01.0 C C9.39.30.60.6 9.5 10.1 11.1

9、 1.5 2.1 0.8 1 2.1 1.3 5.2 常用调度算法 v平均周转时间：平均周转时间： T=(1.5+2.1+0.8)/3=1.46 (T=(1.5+2.1+0.8)/3=1.46 (小时小时) ) v平均带权周转时间：平均带权周转时间： W=(2.1+1.3+1)/3=1.46W=(2.1+1.3+1)/3=1.46 优缺点：优缺点： 优点：对短作业（进程）有利优点：对短作业（进程）有利 缺点：不利于长作业（进程），运行时间为估计值，缺点：不利于长作业（进程），运行时间为估计值， 可能虚假，未考虑紧迫作业（进程）可能虚假，未考虑紧迫作业（进程） 5.2 常用调度算法 三、高优先权

10、优先调度算法（三、高优先权优先调度算法（HPFHPF） 1.1.算法算法 设置优先权（优先级）设置优先权（优先级） 作业调度作业调度 进程调度进程调度 （1 1）抢占式优先权调度算法）抢占式优先权调度算法 （2 2）非抢占式优先权调度算法）非抢占式优先权调度算法 5.2 常用调度算法 2.2.优先权的类型优先权的类型 （1 1）静态优先权）静态优先权 优先数优先数 简单但不灵活简单但不灵活 （2 2）动态优先权）动态优先权 优先权随着进程的调度而变化优先权随着进程的调度而变化 灵活，防止某些进程长期得不得调度灵活，防止某些进程长期得不得调度 5.2 常用调度算法 3.3.举例（举例（静态优先权

11、）静态优先权） 设数值小的优先权高设数值小的优先权高 作业名作业名到达到达 时间时间 运行运行 时间时间 优先权优先权完成完成 时间时间 周转周转 时间时间 带权周转带权周转 时间时间 A A8.08.01.51.51 1 B B9.09.01.01.03 3 C C9.39.30.60.62 2 9.5 10.1 11.1 1.5 2.1 0.8 1 2.1 1.3 5.2 常用调度算法 四、高响应比优先调度算法四、高响应比优先调度算法 （动态优先权调度算法）（动态优先权调度算法） 1.1.算法算法 响应比作业响应时间响应比作业响应时间/ /估计运行时间估计运行时间 作业响应时间等待时间估计

12、运行时间作业响应时间等待时间估计运行时间 响应比响应比1 1等待时间等待时间/ /估计运行时间估计运行时间 5.2 常用调度算法 2.2.例例1 1 作业名作业名到达到达 时间时间 运行运行 时间时间 完成完成 时间时间 周转周转 时间时间 带权周转时带权周转时 间间 A A8.08.01.51.5 B B9.09.01.01.0 C C9.39.30.60.6 9.5 A完成后，B的响应比：0.5/1.0+1=1.5 C的响应比：0.2/0.6+1=1.3 10.5 11.1 5.2 常用调度算法 例例2 2 进程名进程名到达到达 时间时间 运行运行 时间时间 完成完成 时间时间 周转周转

13、时间时间 带权周转时带权周转时 间间 A A0 03 3 B B1 14 4 C C2 25 5 D D3 32 2 3 响应比： B：1.5 C：1.2 D：1 7 C：2 D：3 9 14 3 6 12 6 1 1.5 2.4 3 5.2 常用调度算法 五、基于时间片的轮转调度算法五、基于时间片的轮转调度算法 1.1.时间片轮转法（时间片轮转法（Round RobinRound Robin） 2.2.多级反馈队列调度算法多级反馈队列调度算法 1) 1)算法：照顾短作业，照顾终端型作业算法：照顾短作业，照顾终端型作业 2) 2)实施过程：设置多级就绪队列，各队列具有不实施过程：设置多级就绪队

14、列，各队列具有不 同的时间片同的时间片 5.2 常用调度算法 3 3）性能评价：）性能评价： 能照顾到终端型用户的要求能照顾到终端型用户的要求 能照顾到短批处理作业用户的要求能照顾到短批处理作业用户的要求 能照顾到长批处理作业用户的要求能照顾到长批处理作业用户的要求 练习 v 5 5个进程同时到达，用个进程同时到达，用SPFSPF和和HPFHPF计算平均周转时间计算平均周转时间T T和平和平 均带权周转时间均带权周转时间W W。( (数值越小优先级越高数值越小优先级越高) ) 进程名进程名运行时间运行时间(min)(min)优先级优先级 P1P110103 3 P2P26 65 5 P3P32

15、 22 2 P4P44 44 4 P5P58 81 1 5.3 UNIX进程调度 一、进程调度的时机一、进程调度的时机 1 1、时间片完、时间片完 2 2、进程自动放弃处理器、进程自动放弃处理器 3 3、进程由核心态返回用户态、进程由核心态返回用户态 5.3 UNIX进程调度 二、调度的实现二、调度的实现 1 1、检查是否允许调度、检查是否允许调度 2 2、切换到、切换到0 0进程进程 3 3、切换到被选中进程的上下文中执行、切换到被选中进程的上下文中执行 三、调度算法三、调度算法 动态优先数轮转调度算法动态优先数轮转调度算法 四、四、UNIXUNIX进程优先级的分类进程优先级的分类 等待磁盘

16、I/O 对换 等待缓冲区 等待终端输入 等待终端输出 等待子进程退出 用户级0 用户级1 用户级n 优先级 不 可 中 断 可 中 断 用户态 优先级 核心态 优先级 5.3 UNIX进程调度 五、优先级的计算五、优先级的计算 与优先级有关的字段；与优先级有关的字段； P_pri:P_pri:当前的调度优先级当前的调度优先级 P_userpriP_userpri：用户态优先级用户态优先级 P_cpu:P_cpu:最近一段时间最近一段时间cpucpu使用情况的度量（一般用使用情况的度量（一般用 使用时间作为度量）使用时间作为度量） P_nice:P_nice:用户可控的用户可控的nicenice

17、因子因子 5.3 UNIX进程调度 公式：公式： P_pri=P_cpu/2 +P_nice+基本用户优先数 或 P_pri=P_cpu/2 +基本用户优先数 decay(P_cpu)=P_cpu/2 decay(P_cpu)=P_cpu/2 5.3 UNIX进程调度 v例：有两个进程例：有两个进程A A、B B同时被创建，基本优先数为同时被创建，基本优先数为 6060（忽略（忽略nicenice），），时钟中断每秒发生时钟中断每秒发生6060次，每次次，每次 中断对正在运行的进程计数器加中断对正在运行的进程计数器加1 1，（假设没有其，（假设没有其 他进程阻塞和就绪），一秒调度一次，衰减函数

18、他进程阻塞和就绪），一秒调度一次，衰减函数 为除为除2 2衰减，衰减， 求求1 14 4秒进程的调度次序。秒进程的调度次序。 P_pri=P_cpu/2+基本用户优先数基本用户优先数 =p_cpu/2+60 decay(P_cpu)=P_cpu/2 进程进程A进程进程B P_pri P_priP_cpuP_cput/s 0 1 2 3 4 060600 1 600 30 75 060 60 3075 30 15 67 16 75 3778 30 15 67 75 3778 37 1869 5.3 UNIX进程调度 5.4 死锁及其必要条件 一、死锁的概念一、死锁的概念 死锁（死锁（deadlo

19、ckdeadlock）是指多个进程在运行过程中，因是指多个进程在运行过程中，因 争夺资源而造成的一种僵局，若无外力作用，这争夺资源而造成的一种僵局，若无外力作用，这 些进程都将无法向前推进。些进程都将无法向前推进。 5.4 死锁及其必要条件 例如：例如： 生产者生产者 ：P(mutex); 消费者：消费者：P(mutex); P(empty); P(full); v(mutex); v(mutex); v(empty); v(full); 5.4 死锁及其必要条件 v又如，系统中有一台打印机和一台扫描仪，进程又如，系统中有一台打印机和一台扫描仪，进程A A 占用扫描仪，进程占用扫描仪，进程B

20、B占用打印机，二者在未释放已占用打印机，二者在未释放已 占有资源前均提出申请另一台设备，将导致死锁。占有资源前均提出申请另一台设备，将导致死锁。 5.4 死锁及其必要条件 二、死锁产生的原因二、死锁产生的原因 1.1.竞争资源引起进程死锁竞争资源引起进程死锁 （1 1）资源的两种分类）资源的两种分类 可剥夺性资源：如可剥夺性资源：如cpucpu 非剥夺性资源：如打印机非剥夺性资源：如打印机 临时性资源：如消息临时性资源：如消息 永久性资源：如打印机永久性资源：如打印机 5.4 死锁及其必要条件 （2 2）竞争非剥夺性资源引起死锁）竞争非剥夺性资源引起死锁 A 打印机打印机扫描仪扫描仪 B 5.

21、4 死锁及其必要条件 （3 3）竞争临时性资源引起死锁）竞争临时性资源引起死锁 P1 P2 P3 M1 M2 M3 5.4 死锁及其必要条件 2.2.进程推进顺序不当引起死锁进程推进顺序不当引起死锁 P1 P2 申请申请A 申请申请B释放释放A释放释放B 申请申请B 申请申请A 释放释放B 释放释放A 1 2 3 4 死锁死锁 5.4 死锁及其必要条件 三、死锁产生的必要条件三、死锁产生的必要条件 1.1.互斥条件互斥条件 2.2.请求和保持请求和保持 3.3.不剥夺条件不剥夺条件 4.4.环路等待条件环路等待条件 5.4 死锁及其必要条件 四、处理死锁的基本方法四、处理死锁的基本方法 1.1

22、.鸵鸟算法鸵鸟算法 2.2.预防死锁：限制条件严格，影响进程并发预防死锁：限制条件严格，影响进程并发 3.3.避免死锁：条件宽松，有利于进程并发避免死锁：条件宽松，有利于进程并发 4.4.检测死锁检测死锁 5.5.解除死锁解除死锁 5.5 死锁的预防 一、摒弃互斥条件一、摒弃互斥条件 无法实现无法实现 二、摒弃请求和保持条件二、摒弃请求和保持条件 采用资源的静态分配法采用资源的静态分配法 缺点：必须事先申请所有资源 系统资源得不到充分利用 进程延迟运行 5.5 死锁的预防 三、摒弃不剥夺条件三、摒弃不剥夺条件 请求的资源得不到满足时，释放已得到的资源请求的资源得不到满足时，释放已得到的资源 缺

23、点：实现复杂 增加系统开销 降低系统吞吐量 四、摒弃环路等待条件四、摒弃环路等待条件 有序资源分配法有序资源分配法 缺点：不灵活 5.6 死锁的避免 系统状态分为：系统状态分为：安全安全和和不安全不安全 一、安全与不安全状态一、安全与不安全状态 1.1.安全状态安全状态 某一时刻，系统中存在安全分配序列某一时刻，系统中存在安全分配序列 如如（p1p1，p2p2，p3p3，p4p4） 则系统处于安全状态则系统处于安全状态 5.6 死锁的避免 v例：例：T0T0时刻系统中打印机的分配情况如下时刻系统中打印机的分配情况如下 进程进程已分配打印机已分配打印机 还需申请打印机还需申请打印机 系统中可用打

24、印机系统中可用打印机 P1P13 3台台2 2台台2 2台台 P2P22 2台台2 2台台 P3P31 1台台5 5台台 此时存在安全分配序列：此时存在安全分配序列： （P1，P2，P3） （P2，P1，P3）,（P1，P3，P2） 系统处于安全状态 5.6 死锁的避免 2.2.不安全状态不安全状态 某一时刻，系统中不存在一个安全分配序列。某一时刻，系统中不存在一个安全分配序列。 v例：例：T0T0时刻，时刻，P3P3申请一台打印机申请一台打印机 进程进程已分配打印机已分配打印机还需申请打印机还需申请打印机系统中可用打印机系统中可用打印机 P1P13 3台台2 2台台1 1台台 P2P22 2

25、台台2 2台台 P3P32 2台台4 4台台 系统进入不安全状态 5.6 死锁的避免 二、银行家算法二、银行家算法 1.1.银行家算法中的数据结构银行家算法中的数据结构 （1 1）可用资源向量可用资源向量AvailableAvailable 系统有系统有M M类资源（类资源（R R），），N N个进程（个进程（P P）共享共享 Availablej=k Availablej=k 表示：第表示：第j j个资源个资源RjRj目前有目前有k k个个 5.6 死锁的避免 （2 2）最大需求矩阵）最大需求矩阵MaxMax N NM M的矩阵的矩阵 Maxi,j=k Maxi,j=k 表示：第表示：第i

26、i个进程个进程PiPi需要第需要第j j类资源类资源RjRj的最大数目为的最大数目为k k个个 5.6 死锁的避免 （3 3）分配矩阵）分配矩阵AllocationAllocation N NM M的矩阵的矩阵 Allocationi,j=k Allocationi,j=k 表示：表示：第第i i个进程个进程PiPi已分配到第已分配到第j j类资源类资源RjRj的数目为的数目为k k个个 5.6 死锁的避免 （4 4）需求矩阵）需求矩阵NeedNeed N NM M的矩阵的矩阵 Needi,j=k Needi,j=k 表示：表示：第第i i个进程个进程PiPi还需要第还需要第j j类资源类资源

27、RjRj的数目为的数目为k k个个 5.6 死锁的避免 三个矩阵间有如下关系：三个矩阵间有如下关系： Needi,j+Allocationi,j=Maxi,jNeedi,j+Allocationi,j=Maxi,j 5.6 死锁的避免 2.2.银行家算法描述银行家算法描述 RequestRequesti i是进程是进程PiPi的请求向量的请求向量 RequestRequesti i j=k j=k表示表示PiPi请求请求k k个个RjRj资源资源 银行家算法思想：银行家算法思想： v 判断判断 v 试分配试分配 安全性检测，（找安全分配序列）安全性检测，（找安全分配序列） 5.6 死锁的避免

28、（1 1） RequestRequesti i j=Need j=Need i,ji,j 若成立则继续，否则认为出错若成立则继续，否则认为出错 （2 2） RequestRequesti i j=Availablej j=Availablej 若成立则继续，否则表示系统中无足够资源，若成立则继续，否则表示系统中无足够资源， 进程等待进程等待 （3 3）试分配试分配 Availablej:= Availablej- RequestAvailablej:= Availablej- Requesti i j j Allocationi,j:= Allocationi,j+RequestAllocat

29、ioni,j:= Allocationi,j+Requesti i j j Needi,j:= Needi,j- Request Needi,j:= Needi,j- Requesti i j j （4 4）安全性检测安全性检测 5.6 死锁的避免 3.3.安全性检测算法安全性检测算法 目的：找安全分配序列目的：找安全分配序列 （1 1）设置两个向量）设置两个向量 v 工作向量工作向量Work,Work,表示系统可用资源数表示系统可用资源数 初始值：初始值：Work:=AvailableWork:=Available v 完成向量完成向量FinishFinish，表示进程是否完成表示进程是否完

30、成 初始值：初始值：Finish:=FalseFinish:=False 有一个进程完成，有一个进程完成，Finishi:=trueFinishi:=true 5.6 死锁的避免 （2 2）从进程集合中找一个能满足下列条件的进程：）从进程集合中找一个能满足下列条件的进程： Finish Finish i:i:FalseFalse Need i,j =Workj Need i,j =Workj （3 3）设设PiPi获得资源后运行完成并归还资源获得资源后运行完成并归还资源 Worki,j :Worki,j : Worki,j +Allocation i,j Worki,j +Allocation

31、 i,j Finish i: Finish i:truetrue goto step goto step（2 2） 5.6 死锁的避免 （4 4）若所有进程）若所有进程Finish Finish i:i:truetrue，则存在安全分配则存在安全分配 序列，系统安全，否则系统不安全序列，系统安全，否则系统不安全 试分配后系统安全，所以可以允许进程最初的请求 5.7 死锁的检测和解除 一、死锁的检测一、死锁的检测 基本思想：在OS中保存资源请求和分配信息，利用 某种算法对这些信息加以检查，判断是否存在死锁。 1.资源分配图 一组节点N 一组边E 进程节点Pp1,p2,p3,pn 资源节点Rr1,

32、r2,r3,rn 资源请求边epi,rj 资源分配边erj,pi 5.7 死锁的检测和解除 p1 p2 r1r2 5.7 死锁的检测和解除 化简资源分配图以检测死锁化简资源分配图以检测死锁 p1 p2 r1r2 1）找既非阻塞又非独立的进程节点pi 5.7 死锁的检测和解除 由于由于p1p1非阻塞，所以可以运行完成，可消去请求边和分配非阻塞，所以可以运行完成，可消去请求边和分配 边边 p1 p2 r1r2 2）再找非阻塞非独立的进程，即回到1）继续化简 5.7 死锁的检测和解除 p1 p2 r1r2 3）经过一系列化简后，若所有节点都成为了独立（孤立） 节点，则称该图是可以完全简化的。 5.7

33、 死锁的检测和解除 2.2.死锁定理死锁定理 S S为死锁状态的条件是当且仅当为死锁状态的条件是当且仅当S S状态的资源分配图状态的资源分配图 是不可完全简化的，该定理称为死锁定理。是不可完全简化的，该定理称为死锁定理。 5.7 死锁的检测和解除 二、死锁的解除二、死锁的解除 1.资源剥夺法 2.撤销进程法 撤销所有进程 撤销部分进程 作 业 v 有五个进程，到达的时间和要求计算的时间如下所示，若有五个进程，到达的时间和要求计算的时间如下所示，若 进程调度分别采用进程调度分别采用短进程优先算法短进程优先算法和和高响应比优先调度高响应比优先调度， 则五个进程完成的顺序如何？计算系统的周转时间和带

34、权则五个进程完成的顺序如何？计算系统的周转时间和带权 周转时间。（进程调度采用非抢占方式）周转时间。（进程调度采用非抢占方式） 进程名进程名到达时间到达时间计算时间计算时间 P1P18:008:002525分钟分钟 P2P28:208:201515分钟分钟 P3P38:208:203030分钟分钟 P4P48:308:302020分钟分钟 P5P58:358:351010分钟分钟 练 习 v进程调度又称为低级调度，其主要功能是（）进程调度又称为低级调度，其主要功能是（） A A 选择一个作业调入内存选择一个作业调入内存 B B 选择一个主存中的进程调出到外存选择一个主存中的进程调出到外存 C C 选择一个外存中的进程调入到主存选择一个外存中的进程调入到主存 D D 将一个就绪的进程投入运行将一个就绪的进程投入运行 v银行家算法中，下列表述正确的是（）银行家算法中，下列表述正确的是（）