七处理机调度.ppt

,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第七章 处理机调度,授课教师：付勇智,fuyongzhi,西南林学院 基础部数理教研室,问题提纲,多任务操作系统是如何在多个任务间分配,CPU,的？,微观串行，宏观并行是如何实现的？,调度算法都有哪些？各算法有何特点？,调度算法的评价指标都有哪些，各是什么意义？,如何让程序消耗固定比例的,CPU,资源？,调度程序与调度算法,当有多个进程就绪时，操作系统必须决定先运行哪一个，,OS,中作出这种决定的部分称作,调度程序,。,调度程序从就绪队列中选取进程投入运行的策略，称为,调度算法,。,调度算法的评价标准,公平性确保每个作业获得合理的,CPU,份额,效率,CPU,真正用于运行作业的时间和总,CPU,时间之比（使,CPU,使用率尽可能高,),响应时间作业从提交到首次获得,CPU,使用权之间的时间间隔（使交互用户的响应时间尽可能短）,周转时间作业从提交到运行完毕之间的时间间隔（使批处理用户等待输出的时间尽可能短）,吞吐量单位时间内完成的作业数目（每小时处理作业数最多）,进程调度的原理,为了保证不让进程运行得太久，几乎所有的计算机都内置了一个电子定时器或时钟，时钟周期性的发出中断信号，通常每秒,50,或,60,次。每发生一次时钟中断，,OS,都将运行，并决定当前进程是否应该继续运行，还是它已经占用了足够长的,CPU,时间，应该暂停让其他进程运行。,调度算法的分类,允许将逻辑上可运行的程序暂时挂起的策略称作可剥夺调度（,preemptive scheduling,）抢先式调度，抢占式调度,一个进程一旦运行则一直占用,CPU,，直到无法继续运行阻塞或终止退出才进行调度的方法称为非剥夺调度（,nonpreemptive scheduling,）非抢先式调度,MSDOS,采用非剥夺调度,Windows,和,Unix,采用可剥夺调度,先来先服务（,FCFS,）,将用户作业和就绪进程按提交顺序，或变为就绪状态的顺序先后排成队列，并按照先来先服务（,first come first serve,）的方式进行调度处理。,直观看，该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中的等待时间长短来决定它们是否优先享受服务。,不过，对于那些执行时间较短的作业或进程来说，如果他们在某些执行时间很长的进程之后到达，则它们将等待很长时间。,轮转法（,Round-Robin,）,一种最古老、最简单、最公平且使用最广泛的算法是时间片轮转调度算法。,轮转法将,CPU,时间划分成若干个短的时间片断（通常小于,100ms,），将这些时间片断轮流分配给各个就绪进程使用。如果时间片结束时，进程还没有运行完，则,CPU,将被剥夺并分配给另一个就绪进程使用；如果进程在时间片结束前阻塞或结束，则,CPU,理解发生切换。,Window,和,UNIX,操作系统都是使用轮转法，或者轮转法的变形算法进行处理器调度的。,优先级调度（带优先级的轮转法）,在一个现实系统中，通常不同用户的进程需要得到的服务是不一样的，系统调度程序在保证部分公平性的基础上，应该尽量为重要性高的进程提供更好的服务。,调度思想：每个进程被赋予一个优先级，优先级最高的就绪进程率先被运行。,为了防止高优先级的进程无休止的运行下去，调度程序可以在每一个时钟中断适当降低当前进程的优先级。如果这时运行进程优先级低于次高优先级进程，则将进行进程切换。,对于高级别的用户进程，给予高的运行优先级,对于高优先级的用户作业收取运行费用相应也高,对于,I/O,密集型作业，给予比,CPU,密集型作业更高的运行优先级,例如：一个在后台收发电子邮件的进程进程应被赋予一个较低的优先级，而在屏幕上实时播放电影的进程因改被赋予较高的优先级。,多重队列,设立优先级类：属于最高级类的进程运行,1,个时间片，属于次高优先级类的进程运行,2,个时间片，再次以及,4,个时间片，依次类推。,当一个进程用完分配的时间片后，它被移到下一类。,例如：一个进程需要运行,100,个时间片。它最初被分配,1,个时间片，然后被换出。下次获得,2,个时间片，接下来分别是,4,、,8,、,16,、,32,、,64,。最后一次它只使用,64,个时间片中的,37,个便结束，该进程总共需要,7,次交换。,练习,2.24,在,CTSS,上运行的一个进程需要,30,个时间片方能结束，则它需要被换入多少次？包括第一次，即开始运行之前。,最短作业优先（,Shortest Job Fist,）,对于各进程运行时间可预知的系统，可采用最短作业优先算法,当输入队列中有若干个同等重要的进程将被启动时，调度程序选择预计运行时间最短的进程投入运行,最短作业优先特点：系统吞吐量最大，平均周转时间最短，但对耗时进程造成不公平。,例：四个作业,A,、,B,、,C,、,D,运行时间分别为,8,、,4,、,4,、,4,分钟。若按图（,a,）所示顺序运行，则平均周转时间为：,(8+12+16+20)/4=14,分钟,若按图（,b,）所示顺序运行，则平均周转时间为：,(4+8+12+20)/4=11,分钟,可见最短作业优先算法的平均周转时间最短,THANK YOU,SUCCESS,2025/1/14 周二,15,可编辑,练习,2.23,有,5,个批处理任务,A,到,E,几乎同时到达一计算中心。其预计运行时间分别为,10,、,6,、,2,、,4,、,8,分钟。其优先级分别为,3,、,5,、,2,、,1,、,4,。对于下列每种调度算法，计算其平均进程周转时间,先来先服务,时间片轮转,优先级调度,最短作业优先,彩票调度算法基于概率调度,基本思想：为进程发放针对系统各种资源（如,CPU,时间）的彩票。当调度程序需作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。,所有进程都是平等的，更重要的进程被赋予更多的额外彩票，以增加其中奖概率，如果共发出,100,张彩票，而一个进程持有,20,张，它就有,20,的中奖概率，对于长时间运行，它将获得大约,20,的,CPU,时间。,实时调度,实时系统是那些时间因素非常关键的系统,实时系统可分为硬实时系统和软实时系统。硬实时系统必须严格满足时间限制，例如：核反应堆控制系统，汽车自动刹车系统。软实时系统偶尔超过时间限制是可以容忍的，如,CD,音乐播放系统。,实时系统可调度条件,有,m,个周期性事件，事件,i,的周期为,P,i,，其中每个事件需要,C,i,秒的,CPU,时间来处理。则只有满足以下条件时，才能处理所有的系统负荷：,练习,2.26,一个软实时系统有,4,个周期性事件，其周期分别为,50,、,100,、,300,、,250ms,，假设其处理分别需要,35,、,20,、,10,、,Xms,，则该系统可调度所允许的,X,的最大值是多少？,发生率单调算法,事先为每个进程分配一个与事件发生频率成正比的优先级。例如：周期为,20ms,的进程优先级为,50,，而周期为,100ms,的进程优先级为,10,。运行时，调度程序总是调度优先级最高的就绪进程，必要时将剥夺当前进程。,实时系统的最早截止算法,当一个事件发生时，对应进程被加入到就绪队列中。该队列按照截止期限排序，对于一个周期性事件，其截止期限即为事件下次发生的事件。该算法首先运行队首进程，即截止事件最近的那个。,最少裕度算法,首先计算各进程的富余事件，称作裕度。如果一个进程需要运行,200ms,，而它必须在,250ms,内完成，则其裕度为,50ms,，最少裕度算法即选择运行裕度最少的进程。,Minix,进程结构,微软技术面试试题,写一程序，能够按任意给定的比例使用,CPU,本例中，按,30%,的比例占用，任意比例可以比较容易修改,思考：死循环只能按,100,占用,CPU,，如何按某个给定比例使用,CPU,呢？问题的关键就是进程的调度和进程的状态转换,实现关键,在系统中没有其他进程竞争,CPU,的情况下，则,CPU,时间完全由某个进程占用，而一旦这个进程满负荷运行则会使得,CPU,使用率达到,100,为了按某个比例使用,CPU,，则相应进程必须采取运行一会儿又睡眠一会儿的策略，则进程状态必须在运行态和睡眠态之间不停转换，使得：,运行时间,/(,运行时间,+,睡眠时间,),30,此外，由于,Window,系统任务管理器的统计是在较短时间间隔进行的，因此睡眠态和运行态的转换周期必须非产短，在,1,秒钟以内。,#include,#include,#include,int APIENTRY WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPSTR lpCmdLine,int nCmdShow),int i,j=0;,clock_t timestart,timestop;,int elapsetime;,float Ocu_percent=0.3;,int milisec_to_sleep;,Sleep(10000);,timestart=clock();,for(i=0;i30000000;i+)j+;,timestop=clock();,elapsetime=(timestop-timestart);,milisec_to_sleep=elapsetime/Ocu_percent*(1-Ocu_percent);,while(1),j=0;,for(i=0;i30000000;i+)j+;,Sleep(milisec_to_sleep);,return 0;,THANK YOU,SUCCESS,2025/1/14 周二,29,可编辑,