Chap3 进程调度与死锁-1

《Chap3 进程调度与死锁-1》由会员分享，可在线阅读，更多相关《Chap3 进程调度与死锁-1（24页珍藏版）》请在金锄头文库上搜索。

1、操作系统第三章 进程调度与死锁第三章 进程调度与死锁计算机学院软件工程系 舒新峰计算机学院软件工程系 舒新峰 第三章 进程调度与死锁第三章 进程调度与死锁在多道程序环境下，系统中有多个进程同时运行。多个的进程竞争处理机，就要求系统提供进程调度功能，将处理机动态地分配给系统中的各个进程，使之能够协调一致的运行。在多道程序环境下，系统中有多个进程同时运行。多个的进程竞争处理机，就要求系统提供进程调度功能，将处理机动态地分配给系统中的各个进程，使之能够协调一致的运行。Part1：进程调度Part1：进程调度 3.1 进程调度概述3.1 进程调度概述 3.2 进程调度算法3.2 进程调度算法 3.3

2、CPU调度过程3.3 CPU调度过程31 进程调度概述进程调度概述要解决的问题要解决的问题WHAT：按什么原则分配：按什么原则分配CPU进程调度算法进程调度算法WHEN：何时分配：何时分配CPU进程调度的时机进程调度的时机HOW： 如何分配： 如何分配CPUCPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）1、进程调度的功能1、进程调度的功能 记录系统中所有进程的状态、优先数和资源的需求情况。记录系统中所有进程的状态、优先数和资源的需求情况。 确定调度算法。决定将CPU分配给哪个进程及多长时间。确定调度算法。决定将CPU分配给哪个进程及多长时间。 分配处理机给进程。进行CPU现场的

3、保护和移交，并实现CPU使用权的移交。 处理机是计算机最重要的资源, 如何提高处理机的利用率及改善系统性能, 在很大程度上取决于分配处理机给进程。进行CPU现场的保护和移交，并实现CPU使用权的移交。 处理机是计算机最重要的资源, 如何提高处理机的利用率及改善系统性能, 在很大程度上取决于进程调度（进程调度（亦称亦称处理机调度）处理机调度）性能的好坏, 性能的好坏, 进程调度成为操作系统设计中心工作进程调度成为操作系统设计中心工作。31 进程调度概述进程调度概述2、进程调度方式2、进程调度方式 （1）非抢占方式(Non preemptive mode)：（1）非抢占方式(Non preempt

4、ive mode)： 在非抢占方式下，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。在非抢占方式下，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件而不能运行时，才将CPU分给其它进程。 这种调度方式通常用在批处理系统中。它的主要优点是简单、系统开销小。 （2）抢占方式(Preemptive mode)：（2）抢占方式(Preemptive mode)： 当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的

5、原则有：当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其它进程。剥夺的原则有：优先权原则、短进程优先原则和时间片原则。优先权原则、短进程优先原则和时间片原则。 这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。这种调度方式多用在分时系统和实时系统中，以便及时响应各进程的请求。31 进程调度进程调度3、引进进程调度的时机3、引进进程调度的时机 进程调度的时机是与进程调度的方式有关的进程调度的时机是与进程调度的方式有关的。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度：。通常当发现以下情况时，当前运行进程的CPU被收回，需要重新进行进程调度： 正在执

6、行的进程正确完成, 或由于某种错误而终止运行(陷阱或中断)；正在执行的进程正确完成, 或由于某种错误而终止运行(陷阱或中断)； 执行中的进程提出I/O请求, 等待I/O完成时;执行中的进程提出I/O请求, 等待I/O完成时; 在分时系统中，分给进程的时间片用完时；在分时系统中，分给进程的时间片用完时； 按照优先级调度时, 有更高优先级进程变为就绪时(抢占方式)；按照优先级调度时, 有更高优先级进程变为就绪时(抢占方式)； 在进程通讯中, 执行中的进程执行了某种原语操作, 如wait操作、阻塞原语和唤醒原语时, 都可能引起进程调度。在进程通讯中, 执行中的进程执行了某种原语操作, 如wait操作

7、、阻塞原语和唤醒原语时, 都可能引起进程调度。31 进程调度进程调度4、进程调度算法的评价准则4、进程调度算法的评价准则 我们可从不同的角度来判断处理机调度算法的性能。实际的处理机调度算法选择是一个综合的判断结果。我们可从不同的角度来判断处理机调度算法的性能。实际的处理机调度算法选择是一个综合的判断结果。 1）面向系统的调度性能准则1）面向系统的调度性能准则 吞吐量：吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系批处理系统。批处理系统。 注意：平均周转时间不是吞吐量的倒数注意：平均周转时间不是吞吐量的倒数，因为并发执

8、行的作业在时间上可以重叠。如在2小时内完成4个作业，每个周转时间是1小时，吞吐量是2个作业/小时。，因为并发执行的作业在时间上可以重叠。如在2小时内完成4个作业，每个周转时间是1小时，吞吐量是2个作业/小时。 处理机利用率：处理机利用率：大中型主机大中型主机 各种设备的均衡利用：各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配大中型主机。大中型主机。31 进程调度进程调度2）面向用户的调度性能准则2）面向用户的调度性能准则 周转时间：周转时间：作业从提交到完成所经历的时间作业从提交到完成所经历的

9、时间 批处理系统。（公式中批处理系统。（公式中Tsi为实际运行时间）。为实际运行时间）。响应时间：响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间分时系统分时系统 截止时间：截止时间：开始截止时间和完成截止时间开始截止时间和完成截止时间实时系统，与周转时间有些相似。实时系统，与周转时间有些相似。 公平性：公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。 优先级：优先级：可以使关键任务达到更好的指标。可以使关键任

10、务达到更好的指标。31 进程调度进程调度平均周转T平均周转T ni=1Tin1 ni=1Tin1 Tsi平均带权周转平均带权周转W=3）调度算法本身的调度性能准则3）调度算法本身的调度性能准则 易于实现易于实现 执行开销比执行开销比要设计一个理想的调度算法是一件十分困难的事,在实际系统中, 调度算法往往折衷考虑要设计一个理想的调度算法是一件十分困难的事,在实际系统中, 调度算法往往折衷考虑。大多数操作系统都采用比较简单的调度算法。大多数操作系统都采用比较简单的调度算法。31 进程调度进程调度1、先来先服务FCFS(先进先出调度算法，FIFO)1、先来先服务FCFS(先进先出调度算法，FIFO)

11、 【算法思想】：【算法思想】：最简单的算法最简单的算法 按照进程进入就绪队列的按照进程进入就绪队列的先后次序先后次序，分派，分派CPU； 当前进程占用当前进程占用CPU，直到执行完或阻塞，直到执行完或阻塞，才出让才出让CPU（非抢占方式）。（非抢占方式）。 在进程在进程唤醒后唤醒后（如（如I/O完成），并不立即恢复执行，通常等到当前进程出让完成），并不立即恢复执行，通常等到当前进程出让CPU。 【特点】：【特点】： 比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。 有利于有利于CPU繁忙的作业，而不利于繁忙的作业，而不利于I/O繁忙的作业。繁忙的作业。32 进程调度算法进程

12、调度算法2、短作业（进程）优先调度算法(SJF,SPF)2、短作业（进程）优先调度算法(SJF,SPF) 【算法思想】：【算法思想】：选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业不抢占不抢占正在执行的作业。正在执行的作业。 【优点】：【优点】： 比FCFS改善比FCFS改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩短作业的等待时间；，缩短作业的等待时间； 提高系统的提高系统的吞吐量吞吐量； 【缺点】：【缺点】： 对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执行；

13、未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级来划分执行的优先级 难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影响调度性能。，从而影响调度性能。32 进程调度算法进程调度算法3、优先权调度算法3、优先权调度算法(HPF(HPFHighest Priority First) 【算法思想】：Highest Priority First) 【算法思想】：优先选择就绪队列中优先级最高的进程投入运行。分为：优先选择就绪队列中优先级最高的进程投入运行。分为： 非抢占式优先级算法：非抢占式优先级算法：仅发生在进程放弃CPU。仅发生在进程放弃CPU。 抢占式优先级

14、算法：抢占式优先级算法：可剥夺当前运行进程CPU。可剥夺当前运行进程CPU。 【优先权的类型】【优先权的类型】 静态优先级：静态优先级：在进程创建时指定优先级, 在进程运行时优先数不变。在进程创建时指定优先级, 在进程运行时优先数不变。 动态优先级：动态优先级：在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。在进程创建时创立一个优先级，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。 【确定优先级的依据】【确定优先级的依据】 进程类型、对资源的需求、根据用户要求。进程类型、对资源的需求、根据用户要求。32 进程调度算法进程调度算法4、高响

15、应比优先4、高响应比优先(HRRF, Highest Response Ratio First )：HRRF是是FCFS和和SJF的折衷算法，响应比的折衷算法，响应比R用下式动态计算：用下式动态计算： 响应比响应比R =【特点】：【特点】： 等待时间相同要求服务的时间越短优先权越高等待时间相同要求服务的时间越短优先权越高, 有利于短作业。有利于短作业。要求服务时间相同要求服务时间相同,等待时间越长优先权越高等待时间越长优先权越高,近似于先来先服务。近似于先来先服务。 长作业的优先权会随等待时间加长而升高长作业的优先权会随等待时间加长而升高,长作业也会得到执行。长作业也会得到执行。等待时间等待时

16、间+要求服务时间 要求服务时间要求服务时间 要求服务时间32 进程调度算法进程调度算法课堂练习课堂练习3.1假定在一个处理机上执行以下五个作业， 作业号12345 到达时间02 468 运行时间36 452 当分别采用FCFS、SJF(短作业优先)和HRRN（响应比高者优先）三种调度算法时，作业的调度次序以及各个作业的平均周转时间是多少？假定在一个处理机上执行以下五个作业， 作业号12345 到达时间02 468 运行时间36 452 当分别采用FCFS、SJF(短作业优先)和HRRN（响应比高者优先）三种调度算法时，作业的调度次序以及各个作业的平均周转时间是多少？5、时间片轮转调度算法（RR5、时间片轮转调度算法（RRRound Robin） 【算法思想】：Round Robin） 【算法思想】：通过通过时间片轮转时间片轮转，提高进程，提高进程并发性并发性和和响应时间响应时间