第3章-处理机调度

操作系统原理PrincipleofOperatingSystem精品课程兰州理工大学计算机与通信学院第3章处理机调度3.1概述3.2作业调度3.3进程调度3.4实时调度3.5多处理机调度3.6实例：Windows调度本章主要内容操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院处理机调度（CPUscheduling）是指CPU资源在可运行实体间的分配。在多道程序系统中，通常会有多个进程或线程同时竞争CPU。如果只有一个CPU可用，就必须选择下一个可用的进程或线程。在操作系统中，完成选择工作的这一部分称为调度程序（scheduling），该程序使用的算法称为调度算法（schedulingalgorithm）。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.1概述3.1.1调度层次3.1.2调度准则操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院新建活动就绪就绪挂起阻塞挂起活动阻塞运行终止高级调度中级调度中级调度中级调度低级调度高级调度高级调度后备作业操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.1概述3.1.1调度层次3.1.2调度准则操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院为了比较CPU调度算法，人们提出了很多调度准则（也称为评价准则），用来进行比较特征对确定最佳算法时产生的影响。常用的准则如下：CPU利用率吞吐量周转时间就绪等待时间响应时间操作系统原理PrincipleofOperatingSystem精品课程兰州理工大学计算机与通信学院第3章处理机调度3.1概述3.2作业调度3.3进程调度3.4实时调度3.5多处理机调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院作业（Job）是用户提交给操作系统计算的一个独立任务。在批处理系统中，作业进入系统后先驻留在外存上，因此，需要由作业调度来将它们分批地装入内存。因此作业调度是适用于批处理系统的一种调度方式。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.2作业调度3.2.1作业控制快3.2.2作业状态3.2.3作业调度功能3.2.4作业调度时机3.2.5作业调度算法操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院在多道批处理系统中通常有上百个作业被放在输入井（外存）中。为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的JCB的组成内容有所区别，主要包括：作业名、资源要求、资源使用情况、类型级别、状态等。JCB是作业在系统中存在的唯一标志。作业进入系统时由spooling系统为每个作业建立一个JCB；当作业退出系统时，其JCB也一起被撤销。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.2作业调度3.2.1作业控制快3.2.2作业状态3.2.3作业调度功能3.2.4作业调度时机3.2.5作业调度算法操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院高级调度作业输入进程各状态运行状态完成状态后备状态输出进程调度中级调度高级调度（外存）（内存）操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.2作业调度3.2.1作业控制快3.2.2作业状态3.2.3作业调度功能3.2.4作业调度时机3.2.5作业调度算法操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院作业调度的主要功能:记录系统中各个作业的情况按照某种调度算法从后备作业队列中选取一个或多个作业为被选中的作业分配主存和外设资源为作业开始运行做好一切准备工作在作业运行完成或由于某种原因需要撤离系统时，作业调度程序还要完成作业的善后处理工作操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.2作业调度3.2.1作业控制快3.2.2作业状态3.2.3作业调度功能3.2.4作业调度时机3.2.5作业调度算法操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院调度一个作业的时机有三种：作业完成后有新作业提交处理机利用率较低操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.2作业调度3.2.1作业控制快3.2.2作业状态3.2.3作业调度功能3.2.4作业调度时机3.2.5作业调度算法操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院所谓调度算法是指系统依照某种原则或策略从后备作业队列中选取作业的方法。以单道批处理系统为例，常采用的作业调度算法有：先来先服务（FCFS）算法最短作业优先（SJF）算法（抢占式SJF-SRTF）例1：有三个作业同时到达系统，它们投入运行时所需CPU时间分别为：20ms、5ms、2ms。例2：四个作业到达系统时间/所需CPU时间：作业1-0/7，作业2-1/3，作业3-2/4，作业4-3/5。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院例3:四个作业到达系统时间/所需CPU时间:作业1-0/8，作业2-2/6，作业3-4/2，作业4-6/4。分别用FCFS、SJF和HRF算法进行调度时的调度顺序是什么？平均周转时间为多少？最高响应比优先（HRF）算法响应比＝1+已等待时间/估计运行时间均衡调度算法操作系统原理PrincipleofOperatingSystem精品课程兰州理工大学计算机与通信学院第3章处理机调度3.1概述3.2作业调度3.3进程调度3.4实时调度3.5多处理机调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院进程调度是任何一种操作系统都必须具有的功能，它在很大程度上决定了系统的性能。因此，如何把处理机有效地分配给进程、如何在多个请求进程中选择某个进程运行，都是进程调度需要解决的问题。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.3进程调度3.3.1进程调度功能3.3.2进程调度时机3.3.3进程调度方式3.3.4进程调度算法3.3.5进程调度过程3.3.6线程调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院进程调度根据PCB描述的信息进行调度，其主要功能如下：记录和保持系统中所有进程的有关情况和状态特征决定分配策略实施处理机的分配和回收操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.3进程调度3.3.1进程调度功能3.3.2进程调度时机3.3.3进程调度方式3.3.4进程调度算法3.3.5进程调度过程3.3.6线程调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院在什么情况下，现行进程放弃处理机，而重新引起处理机的调度。主要有以下几种情况：在创建一个新进程后，需要决定是运行父进程还是运行子进程在一个进程退出时必须作出调度当一个运行进程阻塞在I/O或信号量上或由于其它原因阻塞时，必须选择另一个进程运行在一个I/O中断发生时，必须作出调度在分时系统中，现行进程的时间片用完的情况下，需要重新选择新进程在处理机上运行操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.3进程调度3.3.1进程调度功能3.3.2进程调度时机3.3.3进程调度方式3.3.4进程调度算法3.3.5进程调度过程3.3.6线程调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院从调度方式上看，进程调度有两种类型：抢占式调度：又称为剥夺调度方式，指当一个进程正在处理机上执行时，系统可以根据规定的原则剥夺分配给它的CPU并分配给其它进程使用。非抢占式调度：又称为非剥夺调度方式，指挑选一个进程或线程运行后，该进程或线程一直占有CPU，直至被阻塞，或者直到该进程或线程自动释放CPU为止。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3.3进程调度3.3.1进程调度功能3.3.2进程调度时机3.3.3进程调度方式3.3.4进程调度算法3.3.5进程调度过程3.3.6线程调度操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院进程调度算法要解决两个问题，其一是选择哪个进程，其二是选中它以后，如何给它分配处理机，以及该进程能占用处理机多久。第一个问题是选择方式，第二个问题是调度方式。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院1．先来先服务（FCFS）算法FCFS算法就是每次从就绪队列中选择一个最先进入该队列的进程调度，把CPU分给它，令其投入运行。该进程一直运行下去，直至完成或者由于某些原因而被阻塞才放弃CPU。这样，当一个进程就绪队列时，它的PCB就链入就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运行。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院2．时间片轮转（TRR）算法主要用于分时系统中的进程调度。每当执行进程调度时，调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位，通常为10至100ms数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，再把CPU分给就绪队列的队首进程，同样也让它运行一个时间片。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院例：有四个进程A，B，C和D。设它们依次进入就绪队列，但彼此相差时间很少，可以近似地认为“同时”到达。四个进程分别需要运行12、5、3和6个时间单位。试表示出时间片q等于1和q等于4时的运行情况。操作系统原理PrincipleofOperatingSystem精品课程2020年9月14日星期一兰州理工大学计算机与通信学院3．高优先级优先调度算法利用优先级调度算法时，给每