处理机调度ppt课件

1、 (一) 处置机的多级调度 (二) 作业调度 (三) 进程调度 第六章第六章 处置机调度处置机调度 (一一) 处置机的多级调度处置机的多级调度 一一. 处置机调度的功能处置机调度的功能 确定数据构造确定数据构造 制定调度战略制定调度战略 (调度原那么调度原那么) 给出调度算法给出调度算法 详细的实施处置机分派详细的实施处置机分派 不同类型的操作系统往往采用不同的处置机不同类型的操作系统往往采用不同的处置机分配方法。分配方法。 二二. 批处置系统中的处置机调度批处置系统中的处置机调度 处置机调度分为两级：作业调度和进程调度。处置机调度分为两级：作业调度和进程调度。 1. 作业调度作业调度 作业调

2、度又称为宏观调度。作业调度又称为宏观调度。 义务义务对存放在辅存设备上的大量作业，以一对存放在辅存设备上的大量作业，以一定的战略进展挑选，分配主存等必要的资源，建立定的战略进展挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运转。作业对应的进程，使其投入运转。 2. 进程调度进程调度 进程调度又称为微观调度进程调度又称为微观调度 。 义务义务对进入主存的一切进程，确定哪个进程对进入主存的一切进程，确定哪个进程在什么时候获得处置机，运用多长时间。在什么时候获得处置机，运用多长时间。 三三. 多义务操作系统中的处置机调度多义务操作系统中的处置机调度 在分时系统或支持多义务并发执行个人计算机

3、在分时系统或支持多义务并发执行个人计算机操作系统中，系统将用户提交的义务处置为进程，操作系统中，系统将用户提交的义务处置为进程，一个进程又可以创建多个子进程，构成可以并发一个进程又可以创建多个子进程，构成可以并发执行的多进程。执行的多进程。 进程调度的义务是：当处置机空闲时，以某种进程调度的义务是：当处置机空闲时，以某种战略选择一个就绪进程去运转，并分配处置机的战略选择一个就绪进程去运转，并分配处置机的时间。时间。 四四. 多线程操作系统中的处置机调度多线程操作系统中的处置机调度 在支持多线程运转的系统中，一个进程可以创在支持多线程运转的系统中，一个进程可以创建一个线程，也可以创建多个线程。系

4、统为进程建一个线程，也可以创建多个线程。系统为进程分配它所需求的资源，而处置机的分配单位那么分配它所需求的资源，而处置机的分配单位那么为线程。为线程。 系统提供线程调度程序，其功能是当处置机空系统提供线程调度程序，其功能是当处置机空闲时，以某种战略选择一个就绪线程去运转，并闲时，以某种战略选择一个就绪线程去运转，并分配处置机时间。分配处置机时间。 运转就绪完成等待后备提交作业调度作业调度作业录入执行 二二. 作业调度的功能作业调度的功能 1. 确定数据构造确定数据构造 建立作业控制块建立作业控制块jcb (job control block)。 作业控制块记录了每个作业类型、形状、资源作业控制

5、块记录了每个作业类型、形状、资源恳求及分配情况恳求及分配情况 。 2. 确定调度战略与调度算法确定调度战略与调度算法 3. 分配资源分配资源 为选中的作业分配所需求的系统资源。为选中的作业分配所需求的系统资源。 4. 善后处置善后处置 收回该作业所占用的全部资源，吊销作业控制收回该作业所占用的全部资源，吊销作业控制块以及与该作业有关的全部进程。块以及与该作业有关的全部进程。 三三. 作业控制块作业控制块 作业控制块作业控制块jcb存在于系统的整个过程中，存在于系统的整个过程中，jcb是一个作业是一个作业存在的标志。存在的标志。jcb的主要内容如下：的主要内容如下： 作作 业业 名名 资资 源源

6、 要要 求求 资资 源源 使使 用用 情况情况 估计执行时间估计执行时间 进入系统时间进入系统时间 最迟完成时间最迟完成时间 开场执行时间开场执行时间 要求的主存量要求的主存量 已执行时间已执行时间 要求外设的类型及台数要求外设的类型及台数 主存地址主存地址 要求文件量和输出量要求文件量和输出量 外设台号外设台号 类类 型型 优优 先先 级级 控制方式控制方式 状状 态态 作业类型作业类型 四四. 作业调度算法性能的衡量作业调度算法性能的衡量 采用平均周转时间和平均带权周转时间来衡量采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏。作业调度算法性能的好坏。 1. 周转时间周转时间

7、 一个作业提交给计算机系统到该作业的结果前一个作业提交给计算机系统到该作业的结果前往给用户所需求的时间。往给用户所需求的时间。 (1) 定义定义 ti = tci - tsi ti作业作业i的周转时间的周转时间 tsi作业作业i的提交时间，的提交时间， tci作业作业i的完成时间。的完成时间。 (2) 意义意义 阐明作业阐明作业I在系统中停留时间的长短。在系统中停留时间的长短。 (3)平均周转时间平均周转时间 t = niti1n1 2. 带权周转时间带权周转时间 (1) 定义定义 一个作业的周转时间与其运转时间的比值。一个作业的周转时间与其运转时间的比值。 wi = (2) 意义意义 阐明作

8、业阐明作业i在系统中相对等待时间。在系统中相对等待时间。 (3) 平均带权周转时间平均带权周转时间 t = tritiniwi1n1 五五. 作业调度算法作业调度算法 1. 先来先效力调度算法先来先效力调度算法(FCFS) (1) 战略：按作业来到的先后次序进展调度。战略：按作业来到的先后次序进展调度。 (2) 特点：特点： 简单，易实现。简单，易实现。 (3) 讨论在先来先服调度算法下的周转时间与带权讨论在先来先服调度算法下的周转时间与带权周转时间周转时间 作业作业 提交时间提交时间 执行时间执行时间 开场时间开场时间 完成时间完成时间 周周转时间转时间 带权周转时间带权周转时间 1 8.0

9、0 2.00 28.50 0.50 39.00 0.10 4 9.50 0.20 8.00 10.00 2.00 1 10.00 10.50 2.00 4 10.50 10.60 1.60 16 10.60 10.80 1.30 6.5 平均周转时间 t = 平均带权周转时间 w=1.7256.875 五五. 作业调度算法作业调度算法 2. 短作业优先调度算法短作业优先调度算法 (1) 战略：按作业按作业恳求运转的时间长短进展战略：按作业按作业恳求运转的时间长短进展调度。调度。 (2) 特点：易实现，系统吞吐量高；只照顾短作业，特点：易实现，系统吞吐量高；只照顾短作业，而没有思索长作业的利益易

10、实现。而没有思索长作业的利益易实现。 (3) 讨论短作业优先调度算法下的周转时间与带权讨论短作业优先调度算法下的周转时间与带权周转时间周转时间 作业作业 提交时间提交时间 执行时间执行时间 开场时间开场时间 完成时间完成时间 周周转时间转时间 带权周转时间带权周转时间 1 8.00 2.00 28.50 0.50 39.00 0.10 4 9.50 0.20 平均周转时间 t = 平均带权周转时间 w=1.555.15 8.00 10.00 2.00 1 10.30 10.80 2.30 4.6 10.00 10.10 1.10 11 10.10 10.30 0.80 4 3. 调度调度分派构

11、造图分派构造图 ready_q scheduler susp wakeup receive Lpcb6Lpcb4pcb3pcb2pcb1 dispatcher CPU 二二. 进程调度的功能进程调度的功能 1. 记录进程的有关情况和形状特征记录进程的有关情况和形状特征 2. 决议调度战略决议调度战略 优先调度原那么优先调度原那么 进程就绪队列按进程优先级高低排序进程就绪队列按进程优先级高低排序 先来先效力原那么先来先效力原那么 进程就绪队列按进程来到的先后次序排序进程就绪队列按进程来到的先后次序排序 3. 实施处置机的分配和回收实施处置机的分配和回收 三三. 进程调度方式进程调度方式 1. 什

12、么是调度方式什么是调度方式 当一进程正在处置机上执行时，假设有某个更当一进程正在处置机上执行时，假设有某个更为为“重要而紧迫的进程需求进展运转，系统如何重要而紧迫的进程需求进展运转，系统如何分配处置机。分配处置机。 2. 非剥夺方式非剥夺方式 一种是让正在执行的进程继续执行，直到该进一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入程完成或发生某事件而进入“完成或完成或“阻塞形阻塞形状时，才把处置机分配给状时，才把处置机分配给“重要而紧迫的进程。重要而紧迫的进程。 3. 剥夺方式剥夺方式 当当“重要而紧迫的进程一到，便暂停正在执行重要而紧迫的进程一到，便暂停正在执行的进程，立刻把

13、处置机分配给优先级更高的进程。的进程，立刻把处置机分配给优先级更高的进程。 四四. 进程调度算法进程调度算法 1. 进程优先数调度算法进程优先数调度算法 (1) 什么是进程优先数调度算法什么是进程优先数调度算法 预先确定各进程的优先数，系统把处置机的运用权赋予预先确定各进程的优先数，系统把处置机的运用权赋予就绪队列中具备最高优先权就绪队列中具备最高优先权(优先数和一定的优先级相对优先数和一定的优先级相对应应)的就绪进程。的就绪进程。 (2) 优先数的分类及确定优先数的分类及确定 静态优先数静态优先数 * 在进程被创建时确定，且一经确定后在整个进程运转期在进程被创建时确定，且一经确定后在整个进程

14、运转期间不再改动。间不再改动。 * 静态优先数确实定 优先数根据进程所需运用的资源来计算 优先数基于程序运转时间的估计 优先数基于进程的类型 动态优先数 * 进程优先数在进程运转期间可以改动。 * 动态优先数确实定 进程运用CPU超越一定数值时，降低优先数； 进程进展I/O操作后，添加优先数 进程等待时间超越一定数值时，提高优先数 2. 循环轮转调度算法 (1) 什么是循环轮转调度算法 当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。 该队列排序的原那么是什么？ pcb1pcb2pcbnCPU完成 (2) 简单循环轮转调度简单循环轮转调度

15、 就绪队列中的一切进程以等速度向前进展就绪队列中的一切进程以等速度向前进展 q = t/n t 为呼应时间，为呼应时间，n为进入系统的进程数目。为进入系统的进程数目。 q值如何确定值如何确定? (3) 循环轮转调度算法的开展循环轮转调度算法的开展 可变时间片轮转调度、多重时间片循环调度可变时间片轮转调度、多重时间片循环调度 五五. 调度用的进程调度变化图调度用的进程调度变化图运转500ms100ms因 IO而等待高优先 就绪 低优先 就绪进程调度进程调度时间片到恳求I/OI/O完成 1. 队列构造队列构造 I/O等待队列等待队列 一个进程假设恳求一个进程假设恳求I/O，进入，进入I/O等待队列

16、等待队列 低优先就绪队列低优先就绪队列 一个进程假设在运转中超越了它的时间量，进入低优先一个进程假设在运转中超越了它的时间量，进入低优先就绪队列就绪队列 高优先就绪队列高优先就绪队列 当进程从等待形状变为就绪形状时，进入高优先就绪队当进程从等待形状变为就绪形状时，进入高优先就绪队列列 2. 进程调度算法进程调度算法 优先调度与时间片调度相结合的调度战略优先调度与时间片调度相结合的调度战略 (1) 当当CPU空闲时，假设高优先就绪队列非空，那么从高空闲时，假设高优先就绪队列非空，那么从高优先就绪队列中选择一个进程运转，分配时间片为优先就绪队列中选择一个进程运转，分配时间片为100ms。 (2) 当当CPU空闲时，假设高优先就绪队列为空，那么从低空闲时，假设高优先就绪队列为空，那么从低优先就绪队列中选择一个进程运转，分配时间片为优先就绪队列中选择一个进程运转，分配时间片为500ms。 3. 调度效果调度效果 优先照顾了优先照顾了IO量大的进程；量大的进程； 适当照顾了计算量大的进程。适当照顾了计算量大的进程。 第六章第六章 小结小结一一. 处置机的两级调度处置机的两级调度 二二. 作业调度作业调度 1. 作业的四种形状作业的四种形状 2. 作业控制块作业控制块 3. 周