04第四章 处理机调度.ppt

《04第四章 处理机调度.ppt》由会员分享，可在线阅读，更多相关《04第四章 处理机调度.ppt（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、操作系统讲义操作系统讲义第四章第四章 处理机调度处理机调度vCPU是计算机系统中一个十分重要的资源，在早期的计算机是计算机系统中一个十分重要的资源，在早期的计算机系统中，因为系统只有一个作业在运行。所以，不存在处理系统中，因为系统只有一个作业在运行。所以，不存在处理机的分配和调度问题。但在多道程序设计环境下，不同的机的分配和调度问题。但在多道程序设计环境下，不同的CPU管理方法将为用户提供不同性能的操作系统。管理方法将为用户提供不同性能的操作系统。vCPU调度的基本原则是：调度的基本原则是：尽量提高尽量提高CPU的效率和增加作业的吞吐率。这样，在考虑的效率和增加作业的吞吐率。这样，在考虑作业调

2、度算法时，要尽可能使作业搭配合理。作业调度算法时，要尽可能使作业搭配合理。v例如：运算量大的作业和例如：运算量大的作业和I/O量大的作业在一起运行，这样量大的作业在一起运行，这样可使各种资源得到充分利用。可使各种资源得到充分利用。1操作系统讲义操作系统讲义 4.1 4.1 分级调度分级调度 4.2 4.2 作业调度作业调度 4.3 4.3 进程调度进程调度 4.4 4.4 调度算法调度算法 4.5 4.5 算法评价算法评价 4.6 4.6 实时系统调度算法实时系统调度算法2操作系统讲义操作系统讲义4.1 4.1 分级调度分级调度1.1.作业状态及其转换图作业状态及其转换图线程调度线程调度进程调

3、度进程调度提交状态收容状态完成状态就绪执行等待就绪等待外存内存作业作业调度调度交换调度交换调度3操作系统讲义操作系统讲义2.2.调度的层次调度的层次v作业调度：作业调度：又称为宏观调度或高级调度，其主要任务是按一定的又称为宏观调度或高级调度，其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要资源，并建立了相应的进程，以使配内存、输入输出设备等必要资源，并建立了相应的进程，以使该作业的进程获得竞争处理机的权利。该作业的进程获得竞争处理机的权利。v交换调度：交换调度：又称为中级调度，其主要任

4、务是按一定的原则和策略，又称为中级调度，其主要任务是按一定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区，交换调度主要涉及内存管理与扩充。交换调度主要涉及内存管理与扩充。v进程调度进程调度:又称为微观调度或低级调度，其主要任务是按照某种又称为微观调度或低级调度，其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。策略和方法选取一个处于就绪状态的进程占用处理机。v线程调度。线程调度。4

5、操作系统讲义操作系统讲义4.2 4.2 作业调度作业调度1.1.作业调度的功能作业调度的功能 记录系统中各作业的状况；记录系统中各作业的状况；从后备队列中挑选出一部分作业投入运行；从后备队列中挑选出一部分作业投入运行；为选中的作业做好执行前的准备工作；为选中的作业做好执行前的准备工作；在作业执行结束时做善后处理工作在作业执行结束时做善后处理工作(如：撤销该作业的如：撤销该作业的全部进程全部进程PCBPCB和作业控制块和作业控制块JCB)JCB)。2.2.作业调度的目标作业调度的目标 对所有的作业应该是公平合理的；对所有的作业应该是公平合理的；应使设备具有较高的利用率；应使设备具有较高的利用率；

6、单位时间内执行尽可能多的作业；单位时间内执行尽可能多的作业；有较快的响应时间。有较快的响应时间。5操作系统讲义操作系统讲义 3.3.衡量调度算法优劣的标准衡量调度算法优劣的标准(1)(1)周转时间：周转时间：作作业业i i的周转时间的周转时间TiTi为为:Ti=Tei-Tsi:Ti=Tei-Tsi 其中：其中：TsiTsi为作业的提交时间为作业的提交时间 TeiTei为作业的完成时间为作业的完成时间 所有所有作业的平均周转时间为作业的平均周转时间为 T=/nT=/n 其中：其中：n n为作业数（为作业数（T T越小越好）越小越好）(2)(2)带权周转时间：带权周转时间：带权周转时间是作业周转时

7、间与作业执行时间之比。带权周转时间是作业周转时间与作业执行时间之比。Wi=Ti/Tri Wi=Ti/Tri 其中：其中：TriTri作业的执行时间作业的执行时间 平均带权周转时间为：平均带权周转时间为：W=/nW=/n6操作系统讲义操作系统讲义4.3 4.3 进程调度进程调度 1.1.进程调度的功能进程调度的功能v记录系统中所有进程的执行情况。操作系统的进程管理模块必记录系统中所有进程的执行情况。操作系统的进程管理模块必须将系统中各进程的执行情况和运行状态记录在各进程的须将系统中各进程的执行情况和运行状态记录在各进程的PCBPCB表中。表中。v选择占有处理机的进程。进程管理模块按照一定的策略选

8、择一选择占有处理机的进程。进程管理模块按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。个处于就绪状态的进程，使其获得处理机执行。v进行进程上下文的切换。一个进程的上下文包括进程的状态、进行进程上下文的切换。一个进程的上下文包括进程的状态、有关变量和数据结构的值、硬件寄存器的值和有关变量和数据结构的值、硬件寄存器的值和PCBPCB以及程序等，以及程序等，一个进程的执行是在进程的上下文中执行，当正在执行的进程一个进程的执行是在进程的上下文中执行，当正在执行的进程由于某种原因要让出处理机时，系统要进行上下文的切换，以由于某种原因要让出处理机时，系统要进行上下文的切换，以使另一个进程在使

9、另一个进程在CPUCPU上运行。上运行。7操作系统讲义操作系统讲义2.2.进程调度的时机进程调度的时机 引起进程调度的原因主要包括以下几类：引起进程调度的原因主要包括以下几类：（1 1）正在执行的进程执行完毕。）正在执行的进程执行完毕。（2 2）执行中的进程自己调用阻塞原语将自己阻塞起来进入睡）执行中的进程自己调用阻塞原语将自己阻塞起来进入睡眠状态。眠状态。（3 3）执行中的进程因申请外部设备而没有得到被阻塞。）执行中的进程因申请外部设备而没有得到被阻塞。（4 4）使用）使用CPUCPU的时间片到。的时间片到。（5 5）就绪队列中的某进程的优先级变得高于当前执行进程的）就绪队列中的某进程的优先

10、级变得高于当前执行进程的优先级，从而也将引发进程调度。优先级，从而也将引发进程调度。8操作系统讲义操作系统讲义3.3.进程上下文切换进程上下文切换 进程上下文切换的步骤进程上下文切换的步骤 1)1)决定是否做上下文切换以及是否允许做上下文切换。决定是否做上下文切换以及是否允许做上下文切换。2)2)保存当前执行进程的上下文。保存当前执行进程的上下文。3)3)依据一定的调度算法选择一个处于就绪状态的进程。依据一定的调度算法选择一个处于就绪状态的进程。4)4)恢复或装配所选进程的上下文，将恢复或装配所选进程的上下文，将CPUCPU控制权交给所控制权交给所选进程。选进程。进程上下文内容包括：进程上下文

11、内容包括：（1）计算机系统执行该进程有关各种寄存器（通用寄存器、程序计）计算机系统执行该进程有关各种寄存器（通用寄存器、程序计 数器数器PC、程序状态字、程序状态字PS等）的值；等）的值；（2）程序段的机器指令代码集）程序段的机器指令代码集(正文段正文段)、数据集、数据集;（3）各种堆栈值和）各种堆栈值和PCB结构。结构。9操作系统讲义操作系统讲义4.4.进程调度性能评价进程调度性能评价 进程调度性能的衡量方法：有定形和定量两种方法。进程调度性能的衡量方法：有定形和定量两种方法。v定形衡量定形衡量：（1 1）可靠性。包括一次进程调度是否可能引起数据结构的破）可靠性。包括一次进程调度是否可能引起

12、数据结构的破坏，这要求对调度时机的选择和保存坏，这要求对调度时机的选择和保存CPUCPU现场非常谨慎；现场非常谨慎；（2 2）简洁性。要求进程调度不要产生较大的系统开销，以免）简洁性。要求进程调度不要产生较大的系统开销，以免消耗过多资源。消耗过多资源。v定量衡量：定量衡量：（1 1）CPUCPU利用率评价；利用率评价；（2 2）进程在就绪队列中等待时间与执行时间之比）进程在就绪队列中等待时间与执行时间之比10操作系统讲义操作系统讲义4.4 4.4 调度算法调度算法v先来先服务先来先服务v时间片轮转算法时间片轮转算法v短作业优先短作业优先v优先级算法优先级算法v多级队列算法多级队列算法v多级反馈

13、队列算法多级反馈队列算法11操作系统讲义操作系统讲义1.1.先来先服务先来先服务(FCFS)(FCFS)v调度的基本原则是按照作业到达系统或进程进入就绪队列的调度的基本原则是按照作业到达系统或进程进入就绪队列的先后次序来选择作业或进程；先后次序来选择作业或进程；注：注：FCFSFCFS很少用作主要的调度策略，但它常与其它调度算法很少用作主要的调度策略，但它常与其它调度算法结合使用。结合使用。12操作系统讲义操作系统讲义2.2.时间片轮转时间片轮转(Round Robin)(Round Robin)算法算法 基本思想基本思想:将处于就绪队列的进程按到达的时间来排序，将处于就绪队列的进程按到达的时

14、间来排序，进程调度总是选择队列中的第一个进程进程调度总是选择队列中的第一个进程(即按先来先服务即按先来先服务)占有占有CPU，但每个进程占有相同的时间片。，但每个进程占有相同的时间片。注：此算法最适合分时系统，关键问题是时间片长短的选注：此算法最适合分时系统，关键问题是时间片长短的选择。择。13操作系统讲义操作系统讲义3.3.短作业优先短作业优先 该算法主要用于作业调度，它是从后备作业队列中挑选那些该算法主要用于作业调度，它是从后备作业队列中挑选那些所需的运行时间（估计时间）最短的作业进入主存运行。所需的运行时间（估计时间）最短的作业进入主存运行。n优点：优点：n比比FCFSFCFS改善平均周

15、转时间和平均带权周转时间，缩短作业改善平均周转时间和平均带权周转时间，缩短作业的等待时间；的等待时间；n提高系统的吞吐量。提高系统的吞吐量。n缺点：缺点：n对长作业不利，可能长时间得不到执行；对长作业不利，可能长时间得不到执行；n未能依据作业的紧迫程度来划分执行的优先级；未能依据作业的紧迫程度来划分执行的优先级；n难以准确估计作业（进程）的执行时间，从而影响调度性难以准确估计作业（进程）的执行时间，从而影响调度性能。能。14操作系统讲义操作系统讲义4.4.优先级算法优先级算法v按照进程的优先级大小来调度，使高优先级的进程优先得到处理按照进程的优先级大小来调度，使高优先级的进程优先得到处理的调度

16、策略。的调度策略。（进程的优先级大小可由系统自动地按照一定的原（进程的优先级大小可由系统自动地按照一定的原则赋给它，也可由外部来安排；也可由用户支付高费用来购买。）则赋给它，也可由外部来安排；也可由用户支付高费用来购买。）v优先级调度算法分为两种：优先级调度算法分为两种：（1）非抢占优先级调度算法）非抢占优先级调度算法 即一旦进程占有的处理机，就一直运行下去，直到由于本即一旦进程占有的处理机，就一直运行下去，直到由于本 身的原因而主动让出处理机。身的原因而主动让出处理机。（2）可抢占优先级调度算法）可抢占优先级调度算法 任何时刻都严格按照高优先级的进程在处理机上运行的原任何时刻都严格按照高优先级的进程在处理机上运行的原 则进行进程调度，或者说在处理机上运行的进程永远是就则进行进程调度，或者说在处理机上运行的进程永远是就 绪队列中优先级最高的进程。绪队列中优先级最高的进程。15操作系统讲义操作系统讲义v此外，还有最短剩余时间优先调度算法、最高响应比优先调此外，还有最短剩余时间优先调度算法、最高响应比优先调度算法、多级反馈队列调度算法等。（略）度算法、多级反馈队列调度算法等。（略）16