操作系统第4章

1、1第四章、处理机调度第四章、处理机调度4.1分级调度分级调度4.2作业调度作业调度4.3进程调度进程调度4.4调度算法调度算法4.6实时系统调度算法实时系统调度算法24.1、分级调度、分级调度一、调度的层次：一、调度的层次：1、作业调度（宏观、高级）、作业调度（宏观、高级）2、交换调度（中级）、交换调度（中级）3、进程调度（微观、低级）、进程调度（微观、低级）4、线程调度、线程调度3二、状态转换图：二、状态转换图：44.2、作业调度、作业调度一、作业状态：一、作业状态：1、收容（后备）状态：、收容（后备）状态：输入外存、建立输入外存、建立JCB、进入后备队列、进入后备队列：把：把JCB用表格或

2、指针组成的队列，按优先级大小或用表格或指针组成的队列，按优先级大小或作业到达系统的时间顺序排列。作业到达系统的时间顺序排列。2、执行状态：、执行状态：获得所需资源、调入内存、创建进程获得所需资源、调入内存、创建进程3、完成状态：、完成状态：正常正常/异常结束、结果输出、回收资源、释放异常结束、结果输出、回收资源、释放JCB5二、作业调度二、作业调度按一定调度规则，从后备作业队列中选择一个或多个作业进入按一定调度规则，从后备作业队列中选择一个或多个作业进入“执行状态执行状态”；作业执行完毕后，回收资源。；作业执行完毕后，回收资源。1、考虑因素：、考虑因素：1）系统目标：）系统目标：2）作业优先级

3、：）作业优先级：3）资源均衡使用：）资源均衡使用：4）公平合理：）公平合理：5）指标衡量：）指标衡量： （平均）周转时间、（平均）带权周转时间（平均）周转时间、（平均）带权周转时间2、调度算法：、调度算法：1）先来先服务调度算法（）先来先服务调度算法（FCFS：First Come First Serve）2）最短作业优先算法（）最短作业优先算法（SJF：Shortest Job First)3）响应比高者优先算法（）响应比高者优先算法（HRN：Highest Response_ratio Next)4）优先级高者优先算法）优先级高者优先算法63、调度步骤、调度步骤调度算法选择一个作业调度算法

4、选择一个作业是否获得所需资源（是否获得所需资源（CPU除外）除外）分配要求资源分配要求资源为其创建进程为其创建进程进程调度（获得进程调度（获得CPU）回收占用资源回收占用资源计算费用计算费用撤消进程及撤消进程及JCB调度下一个作业调度下一个作业74.3、进程调度、进程调度一、进程状态及其转换一、进程状态及其转换1、就绪状态、就绪状态ready：已获得除：已获得除CPU之外的所有必要资源。之外的所有必要资源。2、执行状态、执行状态excute：占有：占有CPU正在执行。正在执行。3、等待（阻塞）状态、等待（阻塞）状态blocked：因某事件（请求：因某事件（请求I/O）而暂停执行，处）而暂停执行

5、，处于等待执行的状态。于等待执行的状态。8二、进程调度的功能二、进程调度的功能1、记录系统中所有进程的状态：、记录系统中所有进程的状态：PCB2、在就绪队列中选择占有处理机的进程：、在就绪队列中选择占有处理机的进程：调度算法调度算法3、进行新老进程的、进行新老进程的上下文切换上下文切换：1）是否允许进行上下文切换？）是否允许进行上下文切换？2）保存当前进程上下文；）保存当前进程上下文；3）在就绪队列中选择占有处理机的进程；）在就绪队列中选择占有处理机的进程；4）装配所选进程的上下文。）装配所选进程的上下文。9进程控制块进程控制块PCB基本内容基本内容现行状态现行状态进程标识符进程标识符现场保护

6、区现场保护区程序与数据地址程序与数据地址互斥和同步机构互斥和同步机构进程通信机构进程通信机构进程优先数进程优先数资源清单资源清单家族关系家族关系链接字链接字进程上下文进程上下文 进程执行活动过程的静态描述，是进程执行所依赖的环境。进程执行活动过程的静态描述，是进程执行所依赖的环境。 当系统调度新进程占有处理机时，新老进程的上下文发生转换。当系统调度新进程占有处理机时，新老进程的上下文发生转换。1111三、进程调度的方式三、进程调度的方式1、非剥夺方式：、非剥夺方式：不允许强行剥夺当前执行进程的不允许强行剥夺当前执行进程的CPU，直至其运，直至其运行完毕或时间片用完或因某时间而阻塞。行完毕或时间

7、片用完或因某时间而阻塞。优点：设计简单，系统开销小。优点：设计简单，系统开销小。缺点：系统性能恶化；紧急任务不能及时处理；不利缺点：系统性能恶化；紧急任务不能及时处理；不利于短作业。于短作业。2、可剥夺方式：、可剥夺方式：可以根据某原则剥夺正在运行程序的可以根据某原则剥夺正在运行程序的CPU，分配，分配给另进程。给另进程。剥夺原则剥夺原则: 1）优先权原则）优先权原则2）短进程优先原则）短进程优先原则3）时间片原则）时间片原则12四、进程调度的时机四、进程调度的时机1、正在执行的进程执行完毕；、正在执行的进程执行完毕；2、进程调用阻塞原语将自己阻塞；、进程调用阻塞原语将自己阻塞；3、调用、调用

8、P原语而阻塞，调用原语而阻塞，调用V原语唤醒一等待进程；原语唤醒一等待进程；4、执行进程提出、执行进程提出I/O请求而阻塞；请求而阻塞；5、分时系统中时间片用完；、分时系统中时间片用完；6、执行系统调用后有系统程序返回用户程序，调度新进程；、执行系统调用后有系统程序返回用户程序，调度新进程；7、就绪队列中某进程优先级高于当前执行进程优先级。、就绪队列中某进程优先级高于当前执行进程优先级。13UNIX SystemV进程调度的时机进程调度的时机1、当前进程自己调用、当前进程自己调用sleep,wait进入睡眠状态；进入睡眠状态；2、当前进程从系统态返回用户态时，优先级低、当前进程从系统态返回用户

9、态时，优先级低于其他就绪进程，或调度标志被置位；于其他就绪进程，或调度标志被置位；3、当前进程时间片用完，且优先级低于其他就、当前进程时间片用完，且优先级低于其他就绪进程；绪进程；4、当前进程调用、当前进程调用exit自我终止。自我终止。14五、进程调度的实现五、进程调度的实现 确定引起调度的因素确定引起调度的因素 调度算法的选择设计调度算法的选择设计 就就 绪绪 队队 列列 的的 组组 织织决定哪个进程获得决定哪个进程获得CPU分派程序完成分派程序完成CPU分配分配15六、线程调度六、线程调度线程控制块线程控制块TCB的内容的内容1、线程的状态；、线程的状态；2、CPU现场信息：现场信息：P

10、C、PSW、通用寄存器、堆栈指针、通用寄存器、堆栈指针164.4、调度算法、调度算法1、先来先服务调度算法、先来先服务调度算法（FCFS：First Come First Serve）2、最短作业（、最短作业（CPU运行期）优先算法运行期）优先算法（SJF：Shortest Job First)3、响应比高者优先算法、响应比高者优先算法（HRN：Highest Response_ratio Next)4、优先级高者优先算法、优先级高者优先算法5、轮转法、轮转法（round robin）6、多级反馈轮转法（、多级反馈轮转法（ round robin with multiple feedback）

11、作业调度：作业调度：1、2、3、4进程调度：进程调度：1、2、4、5、617 1、先来先服务调度算法先来先服务调度算法原则：原则：按照作业到达系统或进程进入就绪队列的先后顺序来按照作业到达系统或进程进入就绪队列的先后顺序来选择。选择。缺点：缺点：提高了平均的作业周转时间，不利于短作业。提高了平均的作业周转时间，不利于短作业。例：有四个作业几乎同时到达，进入系统的先后顺序及运行时间依次是：例：有四个作业几乎同时到达，进入系统的先后顺序及运行时间依次是：1# 2分钟、分钟、2 # 60分钟、分钟、3# 4分钟、分钟、4# 10 分钟分钟按此顺序调度运行后每个作业的周转时间和运行时间之比分别是：按此

12、顺序调度运行后每个作业的周转时间和运行时间之比分别是：1#：2/22#：62/603#：66/44#：76/10平均周转时间平均周转时间=（2+62+66+76）/4 = 51.5应用：应用：不用于分时和实时系统，常结合其他调度策略使用，不用于分时和实时系统，常结合其他调度策略使用，而不作为主要的调度策略，而不作为主要的调度策略，182、最短作业（、最短作业（CPU运行期）优先算法运行期）优先算法原则：原则：从作业后备队列（进程就绪队列）中挑选所需运行从作业后备队列（进程就绪队列）中挑选所需运行时间（下一个时间（下一个CPU运行期）最短的作业进入内存运行。运行期）最短的作业进入内存运行。缺点：

13、缺点：利于短作业（进程），不利于长作业（进程），且利于短作业（进程），不利于长作业（进程），且作业（进程）运行时间要能估计。作业（进程）运行时间要能估计。前例：前例：1# 2分钟、分钟、2 # 60分钟、分钟、3# 4分钟、分钟、4# 10 分钟分钟按最短作业优先顺序调度运行后，周转时间和运行时间之比分别是：按最短作业优先顺序调度运行后，周转时间和运行时间之比分别是：1#：2/23#：6/4 4#：18/102#：78/60平均周转时间平均周转时间=（2+6+18+78）/4 = 26应用：应用：不适用于分时系统。不适用于分时系统。193、响应比高者优先算法、响应比高者优先算法响应比响应比R=

14、（作业等待时间（作业等待时间W+作业要求运行时间作业要求运行时间T）/ T = 1 + W / T原则：原则：响应比高者得到优先调度。响应比高者得到优先调度。特点：特点：考虑了来到先后和运行时间长短，折衷，开考虑了来到先后和运行时间长短，折衷，开销大。销大。204、优先级高者优先算法、优先级高者优先算法原则：原则：按照进程的优先级大小来调度，高优先级进按照进程的优先级大小来调度，高优先级进程得到优先处理。程得到优先处理。关键：关键：以什么原则确定进程的优先级？以什么原则确定进程的优先级？1）静态优先级：）静态优先级：进程创建时确定，运行期间不变。进程创建时确定，运行期间不变。确定依据：确定依据

15、：进程类型、进程对资源的要求、用户要求的优先级进程类型、进程对资源的要求、用户要求的优先级特点：特点：简单易行，但不精确，各进程特性可能动态变化。简单易行，但不精确，各进程特性可能动态变化。212）动态优先级）动态优先级：进程的优先级可以随时间而变化。进程的优先级可以随时间而变化。变化依据：变化依据：进程占有进程占有CPU时间的长短时间的长短就绪进程等待就绪进程等待CPU的长短的长短优点：优点：调度性能好：优先级相同的进程先进的优先，优先级低调度性能好：优先级相同的进程先进的优先，优先级低的经一段时间的等待而运行，防止大进程垄断运行。的经一段时间的等待而运行，防止大进程垄断运行。225、轮转法

16、、轮转法（round robin）原理：原理：把就绪进程按先进先出原则排成队列，队首进程执把就绪进程按先进先出原则排成队列，队首进程执行一个时间片后释放行一个时间片后释放CPU ，排到就绪队列末尾，把，排到就绪队列末尾，把CPU分给新的队首进程，以此类推。分给新的队首进程，以此类推。23优点：优点：各进程可以在一段时间内及时得到响应。各进程可以在一段时间内及时得到响应。关键：关键：时间片长度的选取时间片长度的选取: q = R / Nmax缺点：缺点：所有进程一视同仁，不区分急缓、长短。所有进程一视同仁，不区分急缓、长短。改进：改进：1）可变时间片轮转法）可变时间片轮转法2）多级反馈轮转法）多

17、级反馈轮转法246、多级反馈轮转法、多级反馈轮转法原理：原理：设多个就绪队列，设多个就绪队列，赋予不同的优先级，赋予不同的优先级，先对高优先级队列中先对高优先级队列中的进程轮转，队列空的进程轮转，队列空时再对低优先级队列时再对低优先级队列轮转；若在某级队列轮转；若在某级队列中轮转时，有新进程中轮转时，有新进程进入更高优先级的队进入更高优先级的队列，将重新调度，把列，将重新调度，把CPU分给新进程。分给新进程。25注意：注意：1、队列时间片随优先级的由高到低而由小到大；、队列时间片随优先级的由高到低而由小到大；2、不同类型作业的优先级设置：、不同类型作业的优先级设置： 交互型作业交互型作业 优先

18、级高优先级高 批处理作业批处理作业 优先级低优先级低 提高系统吞吐量，降低平均等待时间提高系统吞吐量，降低平均等待时间 提高提高I/O设备利用率，及时响应交互用户设备利用率，及时响应交互用户3、各队列采取时间片轮转法，最低优先级队列可以、各队列采取时间片轮转法，最低优先级队列可以采取其他调度法；采取其他调度法；优点：优点：较好满足各种用户的要求。较好满足各种用户的要求。26例：例：在一个批处理系统中，有一个作业序列，其到达时在一个批处理系统中，有一个作业序列，其到达时间及估计运行时间表如下。系统间及估计运行时间表如下。系统只允许有两个作业进程只允许有两个作业进程。系统采用系统采用最短作业优先的

19、作业调度最短作业优先的作业调度算法，算法，进程调度采用进程调度采用最高优先级优先的抢占式最高优先级优先的抢占式调度算法（优先数越小，优先调度算法（优先数越小，优先级越高）。级越高）。1）列出各作业的执行时间段；）列出各作业的执行时间段；2）计算这批作业的平均周转时间。）计算这批作业的平均周转时间。作业作业到达时刻到达时刻估计运行时间估计运行时间优先数优先数110：00405210：20303310：30504410：5020627分析分析两个层次调度（竞争）两个层次调度（竞争）1、作业调度作业调度进入内存的竞争进入内存的竞争策略：策略：最短作业优先最短作业优先调度调度2、进程调度进程调度拥有拥

20、有CPU的竞争的竞争策略：策略：最高优先级优先最高优先级优先抢占式调度抢占式调度28过程分析过程分析10:00 J1运行运行10:20 J1余余20分，分，J2到，需到，需30分，分， J2 优先级高，优先级高，J2运行运行，J1 就绪等待就绪等待10:30 J3到，需到，需50分，分，J1余余20分，分， J2余余20分继续运行分继续运行10:50 J2结束结束，J4到，需到，需20分，分，J4进入，进入， J4优先级低于优先级低于J1，J1重新运行重新运行11:10 J1结束结束，J3进入，优先级高于进入，优先级高于J4，J3运行运行12:00 J3结束结束, J4运行运行12:20 J4

21、结束结束29平均周转时间：平均周转时间：280 / 4 = 70作业作业到达时刻到达时刻结束时刻结束时刻周转时间周转时间J110:0011:1070J210:2010:5030J310:3012:0090J410:5012:2090304.6 、实时系统调度算法、实时系统调度算法一、实时系统特点：一、实时系统特点： 1、有限等待时间、有限等待时间2、有限响应时间、有限响应时间3、用户控制、用户控制4、可靠性高、可靠性高5、系统出错处理能力强、系统出错处理能力强31二、实时系统设计要求：二、实时系统设计要求：1、很快的进程或线程切换速度；、很快的进程或线程切换速度；2、快速的外部中断响应能力；、快速的外部中断响应能力；3、基于优先级的随时抢先式调度策略：、基于优先级的随时抢先式调度策略：1）优先级）优先级+时间片轮转调度策略时间片轮转调度策略2）基于优先级的非抢先式调度策略）基于优先级的非抢先式调度策略3）基于优先级的固定点抢先式调度策略）基于优先级的固定点抢先式调度策略4）基于优先级的随时抢先式调度策略）基于优先级的随时抢先式调度策略主要主要32三、实时调度算法三、实时调度算法1、静态表格驱动类、静态表格驱动类