七处理机调度

第七章处理机调度授课教师：付勇智fuyongzhi@西南林学院基础部数理教研室问题提纲多任务操作系统是如何在多个任务间分配CPU的？微观串行，宏观并行是如何实现的？调度算法都有哪些？各算法有何特点？调度算法的评价指标都有哪些，各是什么意义？如何让程序消耗固定比例的CPU资源？调度程序与调度算法当有多个进程就绪时，操作系统必须决定先运行哪一个，OS中作出这种决定的部分称作调度程序。调度程序从就绪队列中选取进程投入运行的策略，称为调度算法。调度算法的评价标准公平性－确保每个作业获得合理的CPU份额效率－CPU真正用于运行作业的时间和总CPU时间之比（使CPU使用率尽可能高)响应时间－作业从提交到首次获得CPU使用权之间的时间间隔（使交互用户的响应时间尽可能短）周转时间－作业从提交到运行完毕之间的时间间隔（使批处理用户等待输出的时间尽可能短）吞吐量－单位时间内完成的作业数目（每小时处理作业数最多）进程调度的原理为了保证不让进程运行得太久，几乎所有的计算机都内置了一个电子定时器或时钟，时钟周期性的发出中断信号，通常每秒50或60次。每发生一次时钟中断，OS都将运行，并决定当前进程是否应该继续运行，还是它已经占用了足够长的CPU时间，应该暂停让其他进程运行。调度算法的分类允许将逻辑上可运行的程序暂时挂起的策略称作可剥夺调度（preemptivescheduling）抢先式调度，抢占式调度一个进程一旦运行则一直占用CPU，直到无法继续运行阻塞或终止退出才进行调度的方法称为非剥夺调度（nonpreemptivescheduling）非抢先式调度MSDOS采用非剥夺调度Windows和Unix采用可剥夺调度先来先服务（FCFS）将用户作业和就绪进程按提交顺序，或变为就绪状态的顺序先后排成队列，并按照先来先服务（firstcomefirstserve）的方式进行调度处理。直观看，该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中的等待时间长短来决定它们是否优先享受服务。不过，对于那些执行时间较短的作业或进程来说，如果他们在某些执行时间很长的进程之后到达，则它们将等待很长时间。轮转法（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个时间片方能结束，则它需要被换入多少次？包括第一次，即开始运行之前。最短作业优先（ShortestJobFist）对于各进程运行时间可预知的系统，可采用最短作业优先算法当输入队列中有若干个同等重要的进程将被启动时，调度程序选择预计运行时间最短的进程投入运行最短作业优先特点：系统吞吐量最大，平均周转时间最短，但对耗时进程造成不公平。例：四个作业A、B、C、D运行时间分别为8、4、4、4分钟。若按图（a）所示顺序运行，则平均周转时间为：(8+12+16+20)/4=14分钟若按图（b）所示顺序运行，则平均周转时间为：(4+8+12+20)/4=11分钟可见最短作业优先算法的平均周转时间最短THANKYOUSUCCESS2023/11/2815可编辑练习2.23有5个批处理任务A到E几乎同时到达一计算中心。其预计运行时间分别为10、6、2、4、8分钟。其优先级分别为3、5、2、1、4。对于下列每种调度算法，计算其平均进程周转时间先来先服务时间片轮转优先级调度最短作业优先彩票调度算法－基于概率调度基本思想：为进程发放针对系统各种资源（如CPU时间）的彩票。当调度程序需作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。所有进程都是平等的，更重要的进程被赋予更多的额外彩票，以增加其中奖概率，如果共发出100张彩票，而一个进程持有20张，它就有20％的中奖概率，对于长时间运行，它将获得大约20％的CPU时间。实时调度实时系统是那些时间因素非常关键的系统实时系统可分为硬实时系统和软实时系统。硬实时系统必须严格满足时间限制，例如：核反应堆控制系统，汽车自动刹车系统。软实时系统偶尔超过时间限制是可以容忍的，如CD音乐播放系统。实时系统可调度条件有m个周期性事件，事件i的周期为Pi，其中每个事件需要Ci秒的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<windows.h>#include<stdio.h>#include<time.h>intAPIENTRYWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,LPSTRlpCmdLine,intnCmdShow){ inti,j=0; clock_ttimestart,timestop; intelapsetime; floatOcu_percent=0.3; intmilisec_to_sleep; Sleep(10000); timestart=clock(); for(i=0;i<30000000;i++)j++; timestop=clock(); elapsetime=(timestop