嵌入式系统教学课件：操作系统6-处理机调度.ppt

《嵌入式系统教学课件：操作系统6-处理机调度.ppt》由会员分享，可在线阅读，更多相关《嵌入式系统教学课件：操作系统6-处理机调度.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、处理机调度处理机调度 处理机调度的基本概念在多道程序环境下，进程数目往往多于处理机数目，致使在多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机。它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。统设计的中心问题之一。处理机调度的基本概念进程调度要解决的问题：进程调度要解决的问题：WHAT：按什么原则分配：按什么原则分配CPU进程调度算法进程

2、调度算法WHEN：何时分配：何时分配CPU进程调度的时机进程调度的时机HOW：如何分配如何分配CPUCPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）1.高级、中级和低级调度处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次：高级调度高级调度中级调度中级调度低级调度低级调度高级调度也称为作业调度或宏观调度高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天中级调度涉及进程在内外存间的交换中级调度涉及进程在内外存间的交换从存储器资源管理的角度来看，把进程的部分从存储器资

3、源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处入到内存。指令和数据必须在内存里才能被处理机直接访问理机直接访问低级调度也称微观调度低级调度也称微观调度从处理机资源分配的角度来看，处理机需要经从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时由于低级调

4、度算法的频繁使用，要求在实现时做到高效。做到高效。1.高级、中级和低级调度高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性接纳作业数（内存驻留数）太多周转时间T长太少系统效率低接纳策略：即采用何种调度算法：FCFS、短作业优先等1.高级、中级和低级调度低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。非抢占方式：简单，实时性差 (如win31)抢占方式时间片原则优先权原则短作业优先原则。1.高级、中级和低级调度中级调度（中程）为提高系统吞吐量和内存利用率而引

5、入的内-外存对换功能（换出时，进程为挂起或就绪驻外状态）进程调度的运行频率低中高2.进程调度的任务进程调度的任务是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。思考三种调度被引发的事件？三种调度被引发的事件？事件的表现方式？事件的表现方式？3.确定算法的原则具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量4.进程调度方式非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。剥夺方式：当一个

6、进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。5.进程调度性能衡量的指标周转时间响应时间CPU-I/O执行期6.进程调度模型1)1)只有进程调度的调度队列模型只有进程调度的调度队列模型图图 4-1 4-1 仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型图图 4-2 4-2 具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型6.进程调度模型图图 4-3 4-3 具有三级调度时的调度队列模型具有三级调度时的调度队列模型6.进程调度模型7.选择调度方式的准则面向用户的准则：周转时间短；响应

7、时间快；截止时间的保证；优先权准则面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用周转时间：作业从提交到完成的时间，分为：周转时间：作业从提交到完成的时间，分为：（1 1）驻外等待调度时间）驻外等待调度时间（2 2）驻内等待调度时间）驻内等待调度时间（3 3）执行时间）执行时间（4 4）阻塞时间）阻塞时间平均周转时间平均周转时间 平均带权平均带权 可见：带权可见：带权w w越小越好越小越好,Ts,Ts为实际服务时间。为实际服务时间。响应时间快：（对交互性作业）键盘提交请求到响应时间快：（对交互性作业）键盘提交请求到首次响应时间：首次响应时间：（1 1）输入传送时间）输入传送时间

8、（2 2）处理时间）处理时间（3 3）响应传送时间）响应传送时间3.2 调度算法调度算法实际上就是一个资源分配的问题先进先出(FIFO)算法最短CPU运行期优先调度算法最高优先权优先调度算法 轮转法 多级反馈队列 1.先进先出算法FIFO思想：把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便执行下去，直到该进程完成或阻塞时，才释放处理机。评价:优点:实现简单.缺点:没考虑进程的优先级进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.992.最短CPU运行期优先调度算

9、法思想：该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。评价：优点：可获得较好的调度性能缺点：难以准确地知道下一个CPU执行期，而只能根据每一个进行的执行历史来预测。3.FIFO与SJF的比较 作业情况调度算法进程名A B C D E平均到达时间0 1 2 3 4服务时间4 3 5 2 4FCFS（a）完成时间4 7 12 14 18周转时间4 6 10 11 149带权周转时间1 2 2 5.5 3.52.8SJF（b）完成时间4 9 18 6 13周转时间4 8 16 3 98带权周转时间1 2.67 3.1 1.5 2.252.14.最高优先权优先调度算法思想：该

10、算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权(优先级根据优先数来决定)分类：静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变。5.高响应比优先调度算法优先权的变化规律可描述为：由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为：6.轮转法思想：把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU

11、，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行。分类：简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。多级队列方法：将系统中所有进程分成若干类，每类为一级。7.时间片轮转法时间片选择问题：固定时间片可变时间片与时间片大小有关的因素：系统响应时间就绪进程个数CPU能力 简单轮转法调度模型多级反馈队列调度算法将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转

12、，其他队列采用先进先出；系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列。首先系统中设置多个就绪队列每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大各个队列按照先进先出调度算法一个新进程就绪后进入第一级队列进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾当第一级队列空时，就去调度第二级队列，如此类推

13、当时间片到后，进程放弃CPU，回到下一级队列多级反馈队列调度算法多级反馈队列调度算法最高优先权队列时间片最高优先权队列时间片I/O至至CPUCPUS S1 1次高优先权队列时间片次高优先权队列时间片至至CPUCPUS S2 2至至CPUCPUS S3 3最低优先权队列时间片最低优先权队列时间片至至CPUCPUSnSn（时间片时间片：S S1 1 S S2 2 S S3 3）8.进程调度的时机进程运行完毕，或由于某种错误而终止运行进程在运行中处于等待状态（等待I/O）分时系统中时间片到有一个优先级更高的进程就绪（可抢占式）例如：新创建一个进程，一个等待进程变成就绪在进程通信中，执行中的进程执行了

14、某种原语操作（P操作，阻塞原语，唤醒原语）何时切换进程只要OS取得对CPU的控制，进程切换就可能发生，如:超级用户调用来自程序的显式请求来自程序的显式请求(如：打开文件如：打开文件)，该进程通常会，该进程通常会被阻塞被阻塞陷阱最末一条指令导致出错，会引起进程移至退出状态最末一条指令导致出错，会引起进程移至退出状态中断 外部因素影响当前指令的执行，控制被转移至外部因素影响当前指令的执行，控制被转移至IHIH（中（中断处理程序）断处理程序）9.引起进程调度的原因正在执行的进程执行完毕或因发生某事件而不能再继续执行；执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作如P操作、阻塞、挂起原语等；在可剥夺式调度中，有比当前进程优先权更高的进程进入就绪队列；在时间片轮转法中，时间片完。通常系统是按先来先服务或优先权形式来组织调度队列。RQRQ为就绪队列指针为就绪队列指针EPEP为运行队列指针为运行队列指针10.进程调度算法THE ENDTHE END