五章节处理机管理CPUScheduling.ppt

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

1、五章节处理机管理CPUScheduling Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望处理机调度的目的w处理机的高利用率High processor utilizationw高吞吐量High throughputnumber of processes completed per unit timew快速的响应时间Low response timetime elapse from the submission of a request to the beginn

2、ing of the response调度的类型w作业调度(Long-term scheduling)w中级调度(Medium-term scheduling)w进程调度(Short-term scheduling)作业及作业步的概念w作业OS为用户服务，用户交给计算机做的工作称为作业作业由程序、数据、作业说明书三部分组成程序是问题求解的算法描述数据是程序加工的对象，但有些程序未必使用数据；作业说明书是告诉操作系统本作业的程序和数据按什么样的控制要求使之执行。w作业步一个作业的一次活动中若干相对独立的加工步骤编译原程序连接装配程序运行程序作业的状态1 提交状态作业从输入设备进入外存储器时的状态

3、2 后备状态作业的全部信息调入外存后,系统将其加入后备作业队列时的状态系统将为每个作业建立一个作业控制表(JCT)3 运行状态作业被调度程序选中,并分配到它所需要的资源时调入内存运行时的状态4 完成状态作业正常运行结束或因发生错误而终止时,释放占有的所有资源,准备离开系统时的状态作业的状态转换执行等待就绪运行后备提交完成进程调度程序作业注册程序作业调度程序作业终止程序作业控制块JCB作业名作业类型资源要求资源使用情况 优先级当前状态其它作业调度及其功能w作业调度是按照某种调度算法从后备作业队列中选择作业装入内存运行，并当作业运行结束后做后续处理。选择作业分配资源：分配内存和外设资源建立作业的进

4、程建立其它相关表格作业后续处理(收回资源/撤消PCB和JCB)w作业调度又称为宏观调度w在实时系统和分时系统中通常不配置作业调度中级(交换)调度w为了提高内存利用率和系统吞吐量w实施的方法是“挂起”和“解挂”w是存储器管理中的对换功能w常配置在具有挂起功能的OS中w可改善内存的利用率进程调度w又称为微调度w通常几十毫秒运行一次w往往以原语方式存在wCPU及I/O 猝发(Burst)周期Process execution consists of a cycle of CPU execution and I/O waitw任何一种操作系统中都必须配置该级调度进程调度的方式wCPU scheduli

5、ng decisions may take place when a process:1.Switches from running to waiting state,e.g.,I/O request,wait for an event to occur(child completion,system object:semaphore,message queue,socket)2.Switches from running to ready state,e.g.,interrupt3.Switches from waiting to ready.4.Terminates.wScheduling

6、 under 1 and 4 is nonpreemptive.(非抢占)wAll other scheduling is preemptive.(抢占)进程调度方式（续）w非抢占调度方式（nonpreemptive）实现简单，系统开销小，适用于批处理系统环境难于满足紧近任务立即执行的要求，实时系统中不宜采用w抢占调度方式（preemptive）适用于分时系统和实时系统调度方式的原则时间片原则优先级原则短进程优先原则调度队列模型w仅具有进程调度的调度队列模型等待事件（阻塞）等待事件（阻塞）事件发生（被唤醒）事件发生（被唤醒）时间片用完时间片用完交互用户交互用户调度队列模型w具有作业调度和进程调

7、度的调度队列模型等待事件n等待事件2等待事件2相应事件发生则唤醒相应进程队列中的进程作业调度调度队列模型w具有作业和进程和中级调度的调度队列模型被挂起事件发生被唤醒被挂起被激活事件发生调度算法的选择w选择时考虑的因素系统各类资源的均衡使用用户作业到达系统的时间用户作业估计执行的时间用户公平并使用户满意作业的优先级作业对内存和外设的要求及整个系统的效率w各因素间往往相互矛盾算法选择时主要考虑4个方面1 系统设计目标批处理系统主要追求大的系统吞吐量实时系统主要关心实时处理分时系统主要注重保证用户请求的及时响应2 均衡处理系统和用户的要求选择算法时不应使一个作业被无限期的推迟常采用优先级可变方式即作

8、业的优先级可随等待时间的增加而提高采用优先级调度算法算法选择时主要考虑4个方面(续)3 系统资源利用率尽可能地使各种资源忙碌将科学计算型(CPU密集型)和数据处理型(I/O密集型)作业搭配运行4 优先级引入优先级机制,可让某些紧急作业得到及时处理实时系统中还需要采用抢占调度方式调度算法的性能评价1 周转时间作业i从提交时刻tsi到完成时刻tei称为作业的周转时间。Ti=Tei -Tsi 完成时刻 提交时刻一个作业的周转时间包括:作业在外存后备作业队列中等待调度的时间作业进程在就绪队列中等待获取CPU的时间作业进程在CPU上执行的时间作业等待I/O操作等阻塞或挂起的时间调度算法的性能评价作业平均

9、周转时间 T用于衡量不同调度算法对同一作业流的调度性能作业平均带权周转时间 W周转时间与实际运行时间之比用于衡量某种调度算法对不同作业流的调度性能W反映了作业对单位执行时间所付出的平均等时间TRi是作业的实际运行时间调度算法w调度算法是根据系统的资源分配策略所规定的资源分配算法实行调度w目前有很多处理机调度算法,有些适用于作业调度,有些适用于进程调度,有些两者都能适用w常用的几种调度算法先来先服务调度算法短作业(短进程)优先调度算法优先级调度算法时间片轮转调度算法多级反馈队列调度算法实时调度算法先来先服务调度算法(FCFS)First Come First Served w作业调度:选择一个或

10、多个最先进入并能被系统满足的作业装入内存,分配资源,创建相应进程,放入就绪队列w进程调度:从就绪队列中选最先进入队列的进程分配处理机,让它进入执行状态,该进程一直执行,直到完成或因等待某事件而阻塞时,才放弃处理机.FCFS调度例子w假设：用户区空间100KB，内存连续分配且运行中不能移动。作业名进入SPOOLING的时间需计算的时间（分）需要内存量（KB）A8:064215B8:183060C8:302450D8:362410E8:421220作业需时需内存A4215B3060C2450D2410E1220作业名入时间作业调度时进程开始时结束时间周转时间带权周转时间A8:068:06B8:18

11、8:18C8:309:18D8:368:36E8:429:188:06 8:48 42 42/429:18 9:42 66 66/249:42 10:06 96 96/2410:06 10:18 96 96/12T=(42+60+66+96+96)/5=72(min)W=(1+2+2.75+4+8)/5=3.55内存容量 100K8:48 9:18 60 60/30FCFS的优缺点w优点比较容易实现w缺点不公平有利于长作业(长进程)不得于短作业(短进程)w存在的问题当计算机时间长的作业选中后可能使计算机时间短的作业等待很长时间,使短作业用户不满意,而且使短作业周转时间变长,使作业平均周转时间变

12、长,降低了系统的吞能力轮转法w设定时间片,轮流将处理机分配为各就绪进程w仅适用于进程调度w时间片的选择固定法q=R/Nmax根据当前进程数量动态计算短作业(短进程)优先调度算法Shortest-Job-First/Shortest-Process-FirstwSJF短作业优先从后备作业中选择一个或若干个估计运行时间最短且当能获得所要求资源的作业装入内存wSPF短进程优先从就绪队列中选出一个估计运行时间最短的进程分配处理机,该进程立即执行并一直执行到完成或因等待事件发生而阻塞放弃处理机为止短作业/进程调度例子作业名入时间作业调度时进程开始时结束时间周转时间带权周转时间A8:068:06B8:18

13、8:18C8:309:18D8:368:36E8:429:18T=(42+60+66+108+72)/5=69.6(min)W=(1+2+11/4+9/2+6)/5=3.25作业需时需内存A4215B3060C2450D2410E12208:06 8:48 42 42/428:48 9:18 60 60/309:18 9:42 66 66/249:54 10:18 108 108/24 9:42 9:54 72 72/12非抢占式SJF调度例子Example of Non-Preemptive SJF ProcessArrival Time UseTime P1 0.0 7 P2 2.0 4

14、P3 4.0 1 P4 5.0 4SJF(non-preemptive 非抢占)Average waiting time=(0+6+3+7)/4=4T=(7+10+4+11)/4=8P1P3P273160P4812抢占式SJF调度例子Example of Preemptive SJFProcessArrival Time Use Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4SJF(preemptive 抢占)Average waiting time=(9+1+0+2)/4=3T=(16+5+1+6)/4=7P1P3P242110P457P2P116SJF/SPF优缺点w优点在平均周转时间和平均带权周转时间上比FCFS好w缺点对长作业不利（延迟不确定）紧迫作业、进程不能及时得到处理执行时间可能有虚假（估计的执行时间由用户提供）