进程调度算法和死锁解除方法

1、计算机操作系统计算机操作系统主讲教师：主讲教师：曹建秋 贺清碧贺清碧课程主要内容课程主要内容操作系统引论（操作系统引论（1 1章）章）进程管理（进程管理（2-32-3章）章）存储管理（存储管理（4 4章）章）设备管理（设备管理（5 5章）章）文件管理（文件管理（6 6章）章）操作系统接口（操作系统接口（7 7章）章）系统安全性（系统安全性（9 9章）章）* *分布式操作系统分布式操作系统Process Management Process Management 进程管理进程管理u 进程的基本概念与控制进程的基本概念与控制v进程的基本概念进程的基本概念v进程控制进程控制v线程的基本概念线程的基本

2、概念vUNIXUNIX中进程的描述与控制中进程的描述与控制u 进程同步与通信进程同步与通信v进程同步进程同步v经典进程的同步问题经典进程的同步问题v管程机制管程机制v进程通信进程通信vUNIXUNIX中进程的同步与通信中进程的同步与通信u 处理机调度与死锁（第处理机调度与死锁（第3 3章）章）第第3 3章章 处理机调度与死锁处理机调度与死锁 在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等。而系统的运行性能在很大程序上取决于调度，因此调度便成为多道程序的关键。 在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，

3、然而，多个进程的并发执行也带来了新的问题-死锁。第第3 3章章 处理机调度与死锁处理机调度与死锁u 处理机调度的基本概念处理机调度的基本概念u 调度算法调度算法u * *实时调度实时调度u UNIXUNIX系统中进程的调系统中进程的调度度v产生死锁的原因和必要条件产生死锁的原因和必要条件v预防死锁的方法预防死锁的方法v死锁的检测与解除死锁的检测与解除v本章作业本章作业3.1 3.1 处理机调度的基本概念处理机调度的基本概念 在多道程序环境下，一个作业从提交直到完成，往往要经历多级调度。但在不同操作系统中所采用的调度层次不完全相同。在有的系统中仅采用一级调度，而在另一些系统中则可能采用两级或三级

4、调度，在执行调度时所采用的调度算法也可能不同。v调度的层调度的层次次v调度队列模型调度队列模型v选择调度方式和算法的若干准则选择调度方式和算法的若干准则返回目录一、一、调度的层次调度的层次 如图所示。Process Management进程管理-processes 进程 作业调度作业调度中级调度中级调度运行就绪阻塞 进程调度进程调度挂起阻塞挂起就绪创建退出一、一、调度的层次调度的层次 一个作业从提交开始，往往要经历三级调度：高级调度高级调度、低级调度低级调度、中级调度中级调度。1 1、高级调度、高级调度（长程/作业/宏观调度）（1）从外存后备队列中选择作业进入就绪队列或挂起就绪. （2）在批处

5、理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置.（3）作业调度执行频率很低,通常为几分钟一次,甚至更久。Process Management进程管理-processes 进程 一、一、调度的层次调度的层次-高级调度（长程高级调度（长程/作业作业/宏观调度）宏观调度）u 高级调度需解决的问题高级调度需解决的问题（1）主要任务是从外存后备队列中选择多少作业选择多少作业进入就绪队列或挂起就绪，即允许多少作业同时在内存中运行，它控制着多道程序的“道或度” 。若作业太多，则可能会影响系统的服务质量（如周转时间太长），若太少，又将导致系统资源利用率和吞吐量的下降。 因此，应根据系统的规模

6、和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度。（2）应将哪些作业从外存调入内存将哪些作业从外存调入内存，将取决于调度算法（先来先服务、短作业优先等）。 Process Management进程管理-processes 进程 2 2、低级调度（短程、低级调度（短程/CPU/CPU/进程进程/ /微观调度微观调度）（1）主要任务就是从就绪队列中选择一个进程来执行并分配处理机。（2）是OS中最基本的调度。（3）调度频率非常高，一般几十毫秒一次。（4）常采用非抢占（非剥夺）方式非抢占（非剥夺）方式和抢占抢占（剥夺剥夺）方式方式两种。（5）引起进程调度的因素：v进程正常终止或导常终止v正

7、在执行的进程因某种原因而阻塞v在引入时间片的系统中，时间片用完。v在抢占调度方式中，就绪队列中某进程的优先权变得比当前正执行的进程高。非抢占式进程调度、抢占式进程调度非抢占式进程调度、抢占式进程调度u 非抢占方式非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。 实现简单，系统开销小，常用于批处理系统；但不利于处理紧急任务，故实时、分时系统不宜采用。u 抢占方式抢占方式: : 允许调度程序根据某种原则（时间片、优先权、短进程优先），停止正在停止正在执行的进程，而将处理机重新分配

8、给另一进程。 有利于处理紧急任务，故实时与分时系统中常采用。3 3、中级调度（中程、中级调度（中程/ /交换调度交换调度）Process Management进程管理-processes 进程 在内存和外存对换区之间按照给定的原则和策略选择进程对换选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。返回本节二、二、调度队列模型调度队列模型 在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。v仅有进程调度的调度队列模型仅有进程调度的调度队列模型v具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型v

9、同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型Process Management进程管理-processes 进程 返回本节1 1、仅有进程调度的调度队列模型、仅有进程调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列进程调度进程调度时间片完时间片完CPU进程完成进程完成等待事件等待事件事事件件出出现现交互用户交互用户返回2 2、具有高级和低级调度的调度队列模型、具有高级和低级调度的调度队列模型就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完后后备备队队列列进程调度进程调度CPU进程完成进程完成事事件件出出现现等待事件等待事件1等待事件等待事件2等待事件

10、等待事件n作业作业调度调度返回3 3、同时具有三级调度的调度队列模型、同时具有三级调度的调度队列模型就就 绪绪 队队 列列就就 绪绪 挂挂 起起 队队 列列时间片完时间片完阻阻 塞塞 队队 列列后后备备队队列列进程调度进程调度CPU进程完成进程完成事事件件出出现现等待事件等待事件作业作业调度调度阻阻 塞塞 挂挂 起起 队队 列列中程调度中程调度返回三、三、选择调度方式和算法的若干准则选择调度方式和算法的若干准则 在一个操作系统的设计中，应如何选择调度方式和算法，在很大程度上取决于操作系统的类型及其目标，选择选择调度方式和算法的准则有：u 面向用户的准则面向用户的准则v周转时间短v响应时间快v截

11、止时间的保证v优先权准则u 面向系统的准则面向系统的准则v系统吞吐量v处理机利用率好v各类资源平衡利用Process Management进程管理-processes 进程 u 最优准则最优准则v 最大的CPU利用率v 最大的吞吐量v 最短的周转时间v 最短的等待时间v 最短的响应时间返回本节3.2 3.2 调度算法调度算法u 先来先服务调度算法先来先服务调度算法u 短作业短作业/ /进程优先调度算法进程优先调度算法u 时间片轮转调度算法时间片轮转调度算法u 优先权调度算法优先权调度算法u 高响应比优先调度算法高响应比优先调度算法u 多级队列调度算法多级队列调度算法u 多级反馈队列调度算法多级

12、反馈队列调度算法返回目录 进程调度的核心问题就是采用什么样的算法将处理机分配给进程，常用的进程调度算法有：一、先来先服务调度算法一、先来先服务调度算法FCFSu 基本思想:按照进程进入就绪队列的先后次序来分配处理机。 一般采用非剥夺的调度方式。u Example:进程名 到达时间 服务时间 A 0 1 B 1 100 C 2 1 D 3 100u 该调度的Gantt图为:u 平均周转时间:(1-0)+(101-1)+(102-2)+(202-3)）/4=100u 平均等待时间:(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5Process Management进程管理-

13、 CPU Scheduling CPU调度DBCA0 1 2 3 101 102 202 0 1 2 3 101 102 202 一、一、FCFSFCFS调度算法（续）调度算法（续）u 改变到达顺序改变到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A A 0 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 该调度的该调度的GanttGantt图为图为: :u 平均周转时间平均周转时间: :（(1-0)+(101-1)+(202-3)+(201-2)(1-0)+(101-1)+(202-3)+(201-2)）/4=124.2

14、5/4=124.25u 平均等待时间平均等待时间: (: (0(0-0)-0)+ +(1-1)(1-1)+ +(201-3)+(101-2)(201-3)+(101-2)/4 = )/4 = 74.2574.25Process Management进程管理- CPU Scheduling CPU调度ABDC周转周转T100100124.25124.25等待等待T49.549.574.2574.250 1 2 3 101 201 202 0 1 2 3 101 201 202 FCFSFCFS调度算法存在的问题调度算法存在的问题 从表面上，先来先服务于所有作业是公平的，即按照它们到来的先后次序进

15、程服务。但若一个长作业先到达系统，就会使许多短作业等待很长的时间，从而引起许多短作业用户的不满。 所以，现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。Process Management进程管理- CPU Scheduling CPU调度返回二、短作业二、短作业/ /进程优先调度算法进程优先调度算法SJF/SPFSJF/SPFu 短作业优先调度算法（短作业优先调度算法（SJFSJF）v用于作业调度用于作业调度v主要任务是从后备队列中选择一个或若干个估计运行主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内

16、存运行。时间最短的作业，将它们调入内存运行。u 短进程优先调度算法（短进程优先调度算法（SPFSPF）v用于进程调度用于进程调度v主要任务是从就绪队列中选出一估计运行时间最短的主要任务是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。进程，将处理机分配给它。v可采用抢占（剥夺）或者非抢占（非剥夺）调度方式。可采用抢占（剥夺）或者非抢占（非剥夺）调度方式。Process Management进程管理- CPU Scheduling CPU调度二、二、SJSJ（P P）F F _ _非抢占式非抢占式u 到达顺序到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A A 0

17、 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 该调度的该调度的GanttGantt图为图为: :u 平均周转时间平均周转时间: :(1-0)+(101-1)+(102-3)+(202-2)/4=(1-0)+(101-1)+(102-3)+(202-2)/4=100100u 平均等待时间平均等待时间: : (0 0-0)-0)+ +(1-1)(1-1)+ +(101-3)+(102-2)(101-3)+(102-2)/4 = )/4 = 49.549.5Process Management进程管理- CPU Scheduling CPU调度

18、ABCDFCFSFCFSSPFSPF周转周转T124.25124.25100100等待等待T74.2574.2549.549.50 1 2 3 101 102 202 0 1 2 3 101 102 202 二、短作业二、短作业/ /进程优先调度算法进程优先调度算法_ _抢占式抢占式u 到达顺序到达顺序: : 进程名进程名 到达时间到达时间 服务时间服务时间 A A 0 1 0 1 B B 1 1 100100 D D 2 100 2 100 C C 3 3 1 1u 该调度的该调度的GanttGantt图为图为: :u 平均周转时间平均周转时间=(1-0)+(102-1)+(4-3)+(20

19、2-2)=(1-0)+(102-1)+(4-3)+(202-2)）/4=75.75/4=75.75u 平均等待时间平均等待时间= =( (0-(0-0)+0)+(4-3)(4-3)+ +(3-3)+(102-2)(3-3)+(102-2)/4 = )/4 = 25.2525.25Process Management进程管理- CPU Scheduling CPU调度ABBCBD0 1 2 3 4 102 202 0 1 2 3 4 102 202 FCFSFCFSSPF-SPF-非非SPF-SPF-抢抢周转周转T124.25124.2510010075.7575.75等待等待T74.2574.

20、2549.549.525.2525.25uEgEg： 进程进程 到达时间到达时间 服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (非抢占式非抢占式) )u平均周转时间平均周转时间=(7-0)+(12-2)+(8-4)+(16-5)/4=8=(7-0)+(12-2)+(8-4)+(16-5)/4=8u平均等待时间平均等待时间 = (0-0)+(8-2)+(7-4)+(12-5)/4 = 4= (0-0)+(8-2)+(7-4)+(12-5)/4 = 4SPFSPF（非抢占式）调度（

21、非抢占式）调度73160812P1P3P2P4Process Management进程管理- CPU Scheduling CPU调度SPFSPF抢占式调度抢占式调度进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (抢占式抢占式) )u平均周转时间平均周转时间=(16-0)+(7-2)+(5-4)+(11-5)/4=7=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平均等待时间平均等待时间=(11-2)+(5-4)+(4-4)+(7-5)/4

22、= 3=(11-2)+(5-4)+(4-4)+(7-5)/4 = 3P1P3P242110P457P2P116Process Management进程管理- CPU Scheduling CPU调度FCFSFCFS先来先服务调度先来先服务调度进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uFCFSFCFSu平均周转时间平均周转时间=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75u平均等待时

23、间平均等待时间 =(0+(7-2)+(11-4)+(12-5)/4 =4.75=(0+(7-2)+(11-4)+(12-5)/4 =4.75Process Management进程管理- CPU Scheduling CPU调度P142110P257P41612P3SPFSPF与与FCFSFCFS的比较的比较FCFSFCFS非抢占非抢占SPFSPF抢占抢占SPFSPF吞吐量吞吐量0-70-7msms1 11 12 2平均周转时间平均周转时间8.758.758 87 7平均等待时间平均等待时间4.754.754 43 3SF(P)FSF(P)F短作业短作业/ /进程优先调度的优缺点进程优先调度的

24、优缺点优点：优点： 1 1）能有效降低作业的平均等待时间；）能有效降低作业的平均等待时间； 2 2）提高吞吐量；）提高吞吐量； 3 3）能有效缩短进程的周转时间；）能有效缩短进程的周转时间；缺点：缺点： 1 1）对长作业不利；）对长作业不利； 2 2）不考虑）不考虑作业的紧迫程度作业的紧迫程度； 3 3）作业执行时间、剩余时间仅为）作业执行时间、剩余时间仅为估计估计* *； 故故SJ(P)FSJ(P)F算法虽然是优化的，但在算法虽然是优化的，但在CPUCPU调度中很难实现。调度中很难实现。返回三、时间片轮转调度算法三、时间片轮转调度算法RRRRProcess Management进程管理- C

25、PU Scheduling CPU调度 应用于分时应用于分时OSOS中，能保证及时响应用户的请求，是中，能保证及时响应用户的请求，是早期采用的一种调度算法；进入早期采用的一种调度算法；进入9090年代后，广泛采用多年代后，广泛采用多级反馈队列调度算法。级反馈队列调度算法。q时间片轮转法：时间片轮转法：系统将所有原就绪进程按系统将所有原就绪进程按FCFSFCFS的原则，的原则，排成一个队列，依次调度，把排成一个队列，依次调度，把CPUCPU分配给队首进程，并令分配给队首进程，并令其执行一个时间片其执行一个时间片/CPU/CPU时间，通常为时间，通常为10-10010-100msms。时间片。时间

26、片用完后，该进程将用完后，该进程将被抢占被抢占并插入就绪队列末尾。并插入就绪队列末尾。三、时间片轮转调度算法三、时间片轮转调度算法RRRR注：注：（1 1）保证了就绪队列中的所有进程在给定的时间内，均能获）保证了就绪队列中的所有进程在给定的时间内，均能获得一时间片来执行，即系统在给定的时间内，响应所有用户得一时间片来执行，即系统在给定的时间内，响应所有用户的请求。的请求。（2 2）若进程的执行时间少于时间片，则自愿释放）若进程的执行时间少于时间片，则自愿释放CPUCPU。（3 3）时间片将影响：）时间片将影响：q调度算法（太长调度算法（太长-FCFS-FCFS）；）；q上下文切换（太短上下文切

27、换（太短-上下文切换频繁，如下页上下文切换频繁，如下页）；）；q平均周转时间平均周转时间。短时间片增加上下文切换频率短时间片增加上下文切换频率周转时间随时间片变化周转时间随时间片变化三、时间片轮转调度算法三、时间片轮转调度算法例例(1)(1)EGEG：进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uRRRR（时间片为（时间片为1 1）u平均周转时间平均周转时间=(15-0)+(12-2)+(6-4)+(16-5)/4=9.5=(15-0)+(12-2)+(6-4)+(16-5

28、)/4=9.5u平均等待时间平均等待时间=(8+6+1+7)/4 = 5.5=(8+6+1+7)/4 = 5.5Process Management进程管理- CPU Scheduling CPU调度P1P2P20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16P4P1P1P1P3P2P1P4P2P4P1P4三、时间片轮转调度算法三、时间片轮转调度算法例例(2)(2)EGEG：进程进程到达时间到达时间服务时间服务时间P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uRRRR（时间片为（时

29、间片为4 4）u平均周转时间平均周转时间=(12-0)+(8-2)+(9-4)+(16-5)/4=8.5=(12-0)+(8-2)+(9-4)+(16-5)/4=8.5u平均等待时间平均等待时间=(5+2+4+7)/4 = 4.5=(5+2+4+7)/4 = 4.5Process Management进程管理- CPU Scheduling CPU调度P1P20 4 5 6 7 8 9 10 11 12 13 14 15 16P4P3P1FCFSFCFS非抢占非抢占SPFSPF抢占抢占SPFSPFRR-1RR-1RR-RR-4 4平均周转时间平均周转时间8.758.758 87 79.59.5

30、8.58.5平均等待时间平均等待时间4.754.754 43 35.55.54.54.5Example: RR with Time Quantum = 20Example: RR with Time Quantum = 20ProcessProcessBurst TimeBurst TimeP P1 15353 P P2 2 1717 P P3 36868 P P4 4 2424uGantt : Gantt : uRRRR的平均周转时间比的平均周转时间比SPFSPF长，但响应时间要短一些长，但响应时间要短一些. .P1P2P3P4P1P3P4P1P3P302037577797117121 13

31、4154 162返回四、优先权调度算法四、优先权调度算法Process Management进程管理- CPU Scheduling CPU调度非抢占式优先权算法非抢占式优先权算法：系统一旦把处理机分配给就绪队列中系统一旦把处理机分配给就绪队列中优先权最高优先权最高的进程后，该进程便一直执行下去，直到完成的进程后，该进程便一直执行下去，直到完成/ /因发生因发生某事件而放弃处理机时，系统方可重新分配处理机。某事件而放弃处理机时，系统方可重新分配处理机。抢占式优先权算法抢占式优先权算法：系统把处理机分配给就绪队列中优先机系统把处理机分配给就绪队列中优先机最高的进程，使之执行。但在其执行期间，只要

32、出现了另一个优最高的进程，使之执行。但在其执行期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。新将处理机分配给新到的优先权最高的进程。非抢占式优先权算法非抢占式优先权算法例例EGEG：进程进程到达时间到达时间 服务时间服务时间 优先权优先权P P1 10.00.0 7 3 7 3 P P2 22.02.0 4 2 4 2 P P3 34.04.0 1 4 1 4 P P4 45.05.0 4 4 1 1uGanttGantt图图u平均周转时间平均周转时间=(7-0)+

33、(15-2)+(16-4)+(11-5)/4=8.5=(7-0)+(15-2)+(16-4)+(11-5)/4=8.5u平均等待时间平均等待时间=(0+9+11+2)/4 = 5.5=(0+9+11+2)/4 = 5.5Process Management进程管理- CPU Scheduling CPU调度P1P20 2 4 5 7 11 15 16P4P3FCFSFCFSSJF-SJF-非非SJF-SJF-抢抢RR-RR-4 4优优- -非非平均周转时间平均周转时间8.758.758 84 48.58.59.59.5平均等待时间平均等待时间4.754.754 43 34.54.55.55.5

34、抢占式优先权算法抢占式优先权算法例例EGEG：进程进程到达时间到达时间 服务时间服务时间 优先权优先权P P1 10.00.0 7 3 7 3 P P2 22.02.0 4 2 4 2 P P3 34.04.0 1 4 1 4 P P4 45.05.0 4 4 1 1uGanttGantt图图u平均周转时间平均周转时间=(11-0)+(9-2)+(16-4)+(8-5)/4=8.25=(11-0)+(9-2)+(16-4)+(8-5)/4=8.25u平均等待时间平均等待时间=(7+3+11+0)/4 = 5.25=(7+3+11+0)/4 = 5.25Process Management进程管

35、理- CPU Scheduling CPU调度FCFSFCFSSJF-SJF-非非SJF-SJF-抢抢RR-4RR-4优优- -非非优优- -抢抢平均周转时间平均周转时间8.758.758 84 48.58.59.59.58.258.25平均等待时间平均等待时间4.754.754 43 34.54.55.55.55.255.25P1P20 2 4 5 8 9 11 15 16P4P3P2P1优先权的类型优先权的类型Process Management进程管理- CPU Scheduling CPU调度静态优先权静态优先权 优先权在创建进程时确定，且在进程的整个运行期间优先权在创建进程时确定，且

36、在进程的整个运行期间保持不变。一般用一整数表示，小表优先级高。保持不变。一般用一整数表示，小表优先级高。动态优先权动态优先权 优先权在创建进程时确定，但在进程的运行期间会发优先权在创建进程时确定，但在进程的运行期间会发生变化。生变化。 返回五、高响应比优先权调度算法五、高响应比优先权调度算法Process Management进程管理- CPU Scheduling CPU调度v优先权的变化为优先权的变化为 PR要求服务时间响应时间要求服务时间要求服务时间等待时间优先权PR为响应比。为响应比。注：注： 1)1)如等待时间相同如等待时间相同, ,则要求服务时间愈短则要求服务时间愈短, ,其优先权

37、愈高其优先权愈高-SPF.SPF.2)2)如要求服务时间相同如要求服务时间相同, ,优先权决定于等待时间优先权决定于等待时间-FCFSFCFS。3)3)对长作业对长作业, ,若等待时间足够长，优先权也高，也能获得若等待时间足够长，优先权也高，也能获得CPUCPU。返回六、多级队列调度算法六、多级队列调度算法Process Management进程管理- CPU Scheduling CPU调度q基本思想基本思想: :根据作业的性质或类型，将就绪队列划分为若干个独立的队根据作业的性质或类型，将就绪队列划分为若干个独立的队列，每个作业固定地分属一个队列。每个队列采用一种调度列，每个作业固定地分属一

38、个队列。每个队列采用一种调度算法，不同的队列可以采用不同的调度算法。算法，不同的队列可以采用不同的调度算法。 如：交互型作业设置一队列如：交互型作业设置一队列-时间片轮转调度算法时间片轮转调度算法 批处理作业设置一队列批处理作业设置一队列-FCFS-FCFS调度算法调度算法q前台前台 交互式交互式 - RRRRq后台后台 批处理批处理 -优先权、优先权、SPFSPF或或 FCFSFCFS返回q基本思想基本思想： 多级反馈队列调度算法是时间片轮转算法和优先级多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时调度算法的综合和发展，通过动态调整进程优先级和时

39、间片大小，不必事先估计进程的执行时间，多级反馈队间片大小，不必事先估计进程的执行时间，多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。进程调度算法。七、多级反馈队列调度算法七、多级反馈队列调度算法七、七、多级反馈队列调度算法多级反馈队列调度算法- - -实现思想实现思想就绪队列1就绪队列2就绪队列nCPUCPUCPU完成完成完成（1 1）设置）设置多个就绪队列多个就绪队列，并为每个队列赋予，并为每个队列赋予不同的优先级不同的优先级。队列。队列1 1的优先级最高，其余队列逐个降低。的优先级最高，其余队列逐个降低。（2 2）每

40、个队列中）每个队列中进程执行时间片的大小进程执行时间片的大小也各不相同，进程所在队列也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。的优先级越高，其相应的时间片就越短。（3 3）当一个）当一个新进程进入新进程进入系统时，首先将它放入队列系统时，首先将它放入队列1 1的末尾，按的末尾，按FCFSFCFS等待调度。如能完成，便可准备撤离系统，反之由调度程序将等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列其转入队列2 2的末尾，按的末尾，按FCFSFCFS再次等待调度，如此下去，进入队列再次等待调度，如此下去，进入队列n n按按RRRR算法调度执行。算法调度执行。（4

41、4）仅当队列）仅当队列1 1为空时，才调度队列为空时，才调度队列2 2中的进程运行。若队列中的进程运行。若队列I I中的中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行抢占运行。原进程转移至下一队列。原进程转移至下一队列。返回3.3 3.3 实时系统中的调度实时系统中的调度u 在一个实时系统中，在一个实时系统中，时间起着非常重要的作用，即每一个实时进程或任务都有一个时间约束要求，如：在何时之前必须开始做，在何时之前必须完成等等。在一个实时应用系统，可能有多个实时进程或任务，每个实时任务都有其可能有多个实时进程或任务

42、，每个实时任务都有其时间时间约束，约束，所以需一种新的调度算法来合理地安排这些实时任务的执行次序，使它们能满足各个实时任务的的时间约束条件-实实时调度时调度。u 实时调度：满足实时任务各自时间约束条件的调度称为实时调度。一、实现实时调度的基本条件一、实现实时调度的基本条件v提供必要的调度信息（就绪时间、开始截止时间和完成截提供必要的调度信息（就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级）止时间、处理时间、资源要求、优先级）v系统处理能力强（限制条件：决定系统是否可调度，否则系统处理能力强（限制条件：决定系统是否可调度，否则减少减少C 单机单机: （m-实时任务数目，实时任务

43、数目，ci每次处理时间，每次处理时间，pi周期时间）周期时间） 多机多机: （N处理机数目，处理机数目，ci每次处理时间，每次处理时间，pi周期时间）周期时间）v采用抢占式的调度机制采用抢占式的调度机制v具有快速切换机制具有快速切换机制11 miiipcNpcmiii 1二、二、 实时调度算法的分类实时调度算法的分类u 按实时任务性质（即对时间约束强强弱程度）按实时任务性质（即对时间约束强强弱程度）v硬实时调度：必须满足任务截止期要求，错过可能导致严重后果。v软实时调度算法：期望满足任务截止期要求，错过一般可容忍。u 按调度方式按调度方式v非抢占式调度算法（如下图所示）非抢占式轮转调度算法：

44、用于工业生产的群控系统中。非抢占式优先调度算法：用于有一定时间要求的实时控制系统之中。v抢占式调度算法 （如下图所示） 按抢占发生的时间 基于时钟中断抢占的优先权调度算法立即抢占的优先权调度算法进程n实时进程进程1进程2实时进程要求调度调度实时进程运行调度时间（a）非抢占轮转调度）非抢占轮转调度实时进程要求调度时钟中断到来时调度调度时间当前进程实时进程（c）基于时钟中断抢占的优先权抢占调度）基于时钟中断抢占的优先权抢占调度实时进程要求调度当前进程运行完成调度时间当前进程实时进程（b）非抢占优先权调度）非抢占优先权调度实时进程要求调度实时进程抢占当前进程，并立即执行调度时间当前进程实时进程（d）

45、立即抢占的优先权调度）立即抢占的优先权调度实时进程调度实时进程调度与实时调度相关的几个概念与实时调度相关的几个概念u 就绪时间：实时任务产生并可以开始处理的时间。u 开始截止时间：实时任务最迟开始处理的时间。u 处理时间：实时任务处理所需要的处理机的时间。u 完成截止时间：实时任务最迟完成时间。u 发生周期：周期性实时任务的发生间隔时间。u 优先级：实时任务相对紧廹程序。三、常用的几种实时调度算法三、常用的几种实时调度算法u 最早截止时间优先算法（EDF算法）v该算法是根据任务的开始截止时间来确定任务的优先级。开始截止时间越早，其优先级越高。就绪队列中任务按其截止时间排列，队首任务先分配处理机

46、。v如：u 最低松弛度优先算法（LLF算法）2 43143212431开始截止时间任务执行任务到达最低松弛度优先算法（最低松弛度优先算法（LLFLLF算法）算法）u 该算法是根据任务紧急（或松弛）的程序，来确定任务的优先级。任务的紧急度越高，其优先级越高，并使之优先执行。该算法主要采用抢占调度方式，其调度也即具有完成截止时也即具有完成截止时间的周期性实时任务的调度间的周期性实时任务的调度u 例：在一个实时系统中，有两个周期性实时任务A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行，执行时间为25ms。其最低松弛度优先算法调度如下：A8A7A6A5A4A3A2

47、A1160140120100806040200B3B2B1A和和B任务每次必须完成的时间任务每次必须完成的时间某时刻的松弛度计算：某时刻的松弛度计算： 松弛度松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间 优先调度松弛度小的任务优先调度松弛度小的任务利用最低松弛度优先算法调度情况利用最低松弛度优先算法调度情况08070605040302010B2(15)B1(20)A1(10)A2(10)B1(5)A3(10)A4(10)B2(10)t1 t2 t3 t4 t5 t6 t7 t8返回目录10.2.4 UNIX10.2.4 UNIX中进程的调度中进程的调度

48、UNIX是单纯的分时系统，无作业调度，只设置有中级调度和低级调度。常采用的是多级反馈队列轮转调度。u 引起进程调度的原因引起进程调度的原因v时钟中断处理程序对调度标志runrun的重新置位。v系统执行了wait、exit及sleep等系统调用后。v进程执行完系统调用而从核心态返回到用户态时，出现了更高优先级的进程。u 调度算法调度算法v动态优先数轮转调度算法u 进程优先级的分类进程优先级的分类v核心优先级（分为可中断和不可中断）v用户优先级（分成n+1级，0级最高）u 进程优先级的计算进程优先级的计算基本用户优先数的时间最近使用优先数 2CPU返回目录3.5 3.5 死锁的死锁的基本概念基本概

49、念 在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，多个进程的并发执行也带来了新的问题-死锁。u 例：设有一台输入机和一台输出机，进程P1和P2需要使用这两个资源。设两个进程的活动分别为：P1的活动：申请输入机申请输出机释放输出机释放输入机P2的活动：申请输出机申请输入机释放输入机释放输出机P1与与P2均因得不到资源而无法继续向前推进，这种由于进程竞争资源均因得不到资源而无法继续向前推进，这种由于进程竞争资源而引起的僵持称为死锁。而引起的僵持称为死锁。3.5 3.5 死锁的死锁的基本概念基本概念u死锁死锁u产生死锁的原因产生死锁的原因u产生死锁的必

50、要条件产生死锁的必要条件u处理死锁的基本方法处理死锁的基本方法返回目录3.5 3.5 死锁的死锁的基本概念基本概念u一、死锁一、死锁 指多个进程在运行过程中因争夺资源而造成的一种僵局（指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-deadly-Embrace)Embrace)，若无外力作用，这些进程都将无法向前推进，若无外力作用，这些进程都将无法向前推进。u如图如图R1R2P1P2注意：注意：（1 1）参与死锁的进程数至少为）参与死锁的进程数至少为2 2（2 2）参与死锁的所有进程均等待资源）参与死锁的所有进程均等待资源（3 3）参与死锁的进程至少有两个占有资源）参与死锁的进

51、程至少有两个占有资源（4 4）参与死锁的进程是系统中当前正在运行）参与死锁的进程是系统中当前正在运行进程的一部分。进程的一部分。返回二、产生死锁的原因二、产生死锁的原因u资源资源分类分类 操作系统管理着系统内所有资源，它负责分配不同类型的操作系统管理着系统内所有资源，它负责分配不同类型的资源给进程使用，系统中的资源从不同角度可分：资源给进程使用，系统中的资源从不同角度可分： 根据资源本身的性质根据资源本身的性质v可剥夺资源：如主存、可剥夺资源：如主存、CPUCPUv不可剥夺资源：如驱动器、打印机等不可剥夺资源：如驱动器、打印机等 根据资源使用期限根据资源使用期限v永久性资源：可再次使用，如所有

52、硬件。永久性资源：可再次使用，如所有硬件。v临时性临时性资源：消耗性的资源，如消息、信号和数据资源：消耗性的资源，如消息、信号和数据竞争临时性资源竞争临时性资源若按下列顺序进行无死锁产生：若按下列顺序进行无死锁产生：P1：Release(s1);Request(S3);P2：Release(s2);Request(S1);P3：Release(s3);Request(S2);但若按下列顺序进行可能产生死锁：但若按下列顺序进行可能产生死锁：P1： Request(S3); Release(s1); P2： Request(S1) ; Release(s2);P3： Request(S2) ; R

53、elease(s3);二、产生死锁的原因二、产生死锁的原因u 竞争资源竞争资源竞争非剥夺性资源竞争非剥夺性资源 竞争竞争临时性临时性资源资源R1R2P1P2竞争非剥夺性资源竞争非剥夺性资源R1R1代表系统中仅有的一台打印机代表系统中仅有的一台打印机R2R2代表系统中仅有的一台磁带机代表系统中仅有的一台磁带机P1P1、 P2P2代表可共享资源的进程代表可共享资源的进程S3S1S2P1P2P3二、产生死锁的原因二、产生死锁的原因u 进程间推进顺序非法进程间推进顺序非法S S和和Q Q是两个初值为是两个初值为1 1的信号量的信号量P P0 0P P1 1P P( (S S););P P( (Q Q)

54、;);P(P(Q Q););P(P(S S);); V(V(S S););V(V(Q Q););V(V(Q Q) )V(V(S S););u 其它原因：如两进程谦让即其它原因：如两进程谦让即“After You/ After You”After You/ After You”问题。问题。返回三、产生死锁的必要条件三、产生死锁的必要条件 产生死锁必须具备以下四个条件，这四个条件是产生死锁必须具备以下四个条件，这四个条件是Coffman首先提出的，所以称为首先提出的，所以称为Coffman 条件：条件：v互斥条件（资源独占条件）互斥条件（资源独占条件）v请求和保持条件（部分分配条件）请求和保持条件

55、（部分分配条件）v不剥夺条件不剥夺条件v循环等待条件（环路条件）循环等待条件（环路条件）返回四、四、处理死锁的基本方法处理死锁的基本方法 目前处理死锁的基本方法有四种：目前处理死锁的基本方法有四种：u 鸵鸟算法鸵鸟算法：指像鸵鸟一样对死锁视而不见，即不理睬死锁。指像鸵鸟一样对死锁视而不见，即不理睬死锁。u 预防死锁预防死锁：指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。一个或几个条件，来防止死锁的发生。u 避免死锁避免死锁：指在资源的动态分配过程中，用某种方法去防止系统进入不安全指在资源的动态分

56、配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。状态，从而避免死锁的发生。u 检测死锁检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。锁的发生，并采取适当措施加以清除。u 解除死锁解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。返回3.6 3.6 死锁的预防和避免方法死锁的预防和避免方法一、死锁的预防一、死锁的预防 破坏死锁的四个必要条件（常针对条件破坏死锁的四个必要条件（常针对条件2,3,4

57、)（1）破坏互斥条件：）破坏互斥条件：即允许多个进程同时访问资源。但由于资源本身即允许多个进程同时访问资源。但由于资源本身固有特性限制，有的资源根本不能同时访问，只能互斥访问，所以破坏固有特性限制，有的资源根本不能同时访问，只能互斥访问，所以破坏互斥条件来预防死锁，这不太可能。互斥条件来预防死锁，这不太可能。（2）破坏请求和保条件：）破坏请求和保条件：可采用预先静态分配方法，即要求进程在运可采用预先静态分配方法，即要求进程在运行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦运行后，这些资源全归其占有，同时它

58、也不再提出其它资入运行。一旦运行后，这些资源全归其占有，同时它也不再提出其它资源要求，这样可以保证系统不会发生死锁。此方法虽简单安全，但降低源要求，这样可以保证系统不会发生死锁。此方法虽简单安全，但降低了资源利用率，同时必须预知进程所需要的全部资源。了资源利用率，同时必须预知进程所需要的全部资源。3.6 3.6 死锁的预防和避免方法死锁的预防和避免方法一、死锁的预防一、死锁的预防（3）破坏不可剥夺条件：）破坏不可剥夺条件：即一个已经获得某些资源的进程，若又请求即一个已经获得某些资源的进程，若又请求新的资源时不能得到满足，则它必须释放出已获得的所有资源，以后需新的资源时不能得到满足，则它必须释放

59、出已获得的所有资源，以后需要资源时再请求。也即一个进程已获得的资源在运行过程中可被剥夺。要资源时再请求。也即一个进程已获得的资源在运行过程中可被剥夺。从而破坏了该条件。但这种方法实现较复杂，会增加系统开锁，降低系从而破坏了该条件。但这种方法实现较复杂，会增加系统开锁，降低系统吞吐量。统吞吐量。（4）破坏环路条件：）破坏环路条件：可采用可采用有序资源分配方法有序资源分配方法，即将系统中的所有资，即将系统中的所有资源都按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序源都按类型赋予一个编号，要求每一个进程均严格按照编号递增的次序来请求资源，同类资源一次申请完。也就是，只要进程提出请求资源来

60、请求资源，同类资源一次申请完。也就是，只要进程提出请求资源Ri，则在以后的请求中，只能请求则在以后的请求中，只能请求Ri后的资源，这样不会出现几个进程请求后的资源，这样不会出现几个进程请求资源而形成环路。该方法虽提高了资源的利用率，但编号难，加重进程资源而形成环路。该方法虽提高了资源的利用率，但编号难，加重进程负担及因使用资源顺序与申请顺序不同而造成资源浪费。负担及因使用资源顺序与申请顺序不同而造成资源浪费。3.6 3.6 死锁的预防和避免方法死锁的预防和避免方法u死锁的避免死锁的避免 在死锁预防的几种方法中，都施加了较强的限制条件，在死锁预防的几种方法中，都施加了较强的限制条件，严重降低了系