搜索
操作系统原理OperatingSystemPrinciples四川大学计算机学院段磊leiduan@scu.edu.cn2014Spring第3章处理器调度处理器调度指在多道程序环境下将处理器分配给各进程。在处理器调度中，合理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求。2020/1/16《计算机操作系统》-第3章3/98本章目录3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度2020/1/16《计算机操作系统》-第3章4/983.1处理器调度的层次内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念2020/1/16《计算机操作系统》-第3章5/983.1处理器调度的层次内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念2020/1/16《计算机操作系统》-第3章6/98调度的概念与本质调度：系统将计算机资源分配给进程。单道程序环境与多道程序环境处理器调度：多道程序环境下将处理器分配给各进程2020/1/16《计算机操作系统》-第3章7/98调度要解决的问题：WHAT：按什么原则分配CPU调度算法WHEN：何时分配CPU调度的时机HOW：如何分配CPU调度过程调度的概念与本质2020/1/16《计算机操作系统》-第3章8/98处理器调度的层次处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响处理机调度的三个层次：高级调度中级调度低级调度高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天中级调度涉及进程在内外存间的交换从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问低级调度也称微观调度从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效。2020/1/16《计算机操作系统》-第3章9/98高级调度-作业的概念与分类概念：作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。分类：根据需要处理工作的类型，分为计算型作业和I/O型作业。按照作业提交方式，分为批处理作业和终端型作业。一个系统能够同时接纳作业的个数称为系统的多道程序度。2020/1/16《计算机操作系统》-第3章10/98作业的状态：提交状态后备状态执行状态完成状态高级调度-作业的概念与分类作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得CPU，开始运行。从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程。系统接收输入的用户作业，并将其放入计算机磁盘。作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存。用户将作业提交给操作系统，等待输入程序和数据到磁盘。2020/1/16《计算机操作系统》-第3章11/98高级调度-概念与模型作业调度概念：按照操作系统预先规定的策略，从磁盘的作业后备队列中选择作业调入内存，为作业分配所需要的资源并建立与作业相对应的进程。当作业运行的准备工作完成后，作业调度启动作业运行。在作业运行结束后，作业调度归还并释放作业占用的资源，结束作业。模型：2020/1/16《计算机操作系统》-第3章12/98高级调度-策略与因素接纳多少个作业作业数目太多时，可能会影响到系统的服务质量;作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低接纳哪些作业先来先服务调度算法短作业优先调度算法基于作业优先级的调度算法响应比高者优先的调度算法2020/1/16《计算机操作系统》-第3章13/98高级调度-OS任务作业调度中操作系统需要完成如下主要工作：确定作业的数据结构确定作业的调度算法为作业分配资源回收作业资源操作系统为每个进入系统的作业分配一个与进程控制块（PCB）类似的作业控制块（JCB）JCB是作业的标志，OS根据JCB中的信息对作业进行调度和管理。作业运行需要各种资源，包括硬件资源和软件资源。硬件资源有内存、处理器和各种输入输出设备。软件资源有各种共享变量等。作业的资源分配策略主要考虑的是作业所包含的进程所需要的资源，在一般情况下，资源按照进程需求进行分配。资源分配中需要避免由进程之间的资源竞争而造成的死锁等现象。作业完成后，作业调度程序除了要输出相关的作业信息之外，还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控制块。在作业调度工作中，大多数工作由作业的调度程序完成。内存和输入输出设备的分配和释放不是由作业调度程序完成，而是由存储器管理和设备管理程序完成的。作业调度程序只是将作业对内存的要求和对设备的要求转交给相应的内存管理程序和设备管理程序，由内存管理程序和设备管理程序完成内存和设备的分配与回收。2020/1/16《计算机操作系统》-第3章14/98高级调度-作业状态转换作业调度将作业从后备状态转换到内存执行状态作业执行状态包含作业所对应进程的就绪、运行和阻塞状态2020/1/16《计算机操作系统》-第3章15/983.1处理器调度的层次内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念2020/1/16《计算机操作系统》-第3章16/98中级调度-概念与功能又称为中程调度，是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。多进程环境下，内存中存在多个进程，其中有些进程可能需要挂起，这些进程暂时不参与对处理器的竞争。为了充分利用内存资源，系统会采用进程对换的方法将进程换出到外存，将这些进程占用的内存空间释放，让内存能够接纳新的进程或使得内存中的进程能够更快推进。当被换出到外存中的进程挂起时间到时，又需要将这些进程换入到内存。中级调度是在换出内存的进程中确定需要进入内存的进程的一种调度操作。2020/1/16《计算机操作系统》-第3章17/983.1处理器调度的层次内容高级调度-作业调度中级调度低级调度-进程调度要点调度的本质进程调度的概念2020/1/16《计算机操作系统》-第3章18/98低级调度-概念与功能又称为进程调度、短程调度按照一定的调度算法从内存的就绪进程队列中选择进程，为进程分配处理器，避免进程对处理器竞争的方法。与作业调度和中级调度比较，进程调度发生的频率最高，作业调度发生的频率最低，中级调度主要用于内存管理，特别是虚拟存储器管理。2020/1/16《计算机操作系统》-第3章19/983.1.2进程调度模型只有进程调度的调度队列模型就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完低级调度-模型2020/1/16《计算机操作系统》-第3章20/983.1.2进程调度模型具有高、低两级调度的调度队列模型低级调度-模型2020/1/16《计算机操作系统》-第3章21/98具有三级调度时的调度队列模型3.1.2进程调度模型低级调度-模型2020/1/16《计算机操作系统》-第3章22/98低级调度-原因与机制引起进程调度的主要原因如下：处理器执行的进程完成任务，处理器空闲处理器执行的进程转入阻塞状态，此时处理器空闲处理器执行的进程被其它进程抢占处理器执行的进程被挂起机制：排队器分派器上下文切换机制2020/1/16《计算机操作系统》-第3章23/98低级调度-调度方式非抢占方式：简单，实时性差抢占方式时间片原则优先权原则短作业优先原则如果执行进程正好在执行一个没有资源的无限循环，则执行进程不会放弃处理器，所有的就绪进程会永久等待，系统进入了一种僵持的状态。指一个进程正在处理器中运行时，操作系统可以根据规定的抢占原则，将已经分配给进程的处理器从进程剥夺，并分配给其他的进程。在系统允许抢占调度，并满足抢占条件的情况下，系统才可以采用抢占调度方式。满足抢占条件的进程能够抢占当前正在执行进程的处理器。被抢占的进程状态从执行状态变为就绪状态，其进程控制块进入到进程就绪队列。思考：“抢占”可能带来的问题及原因？2020/1/16《计算机操作系统》-第3章24/98本章目录3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度2020/1/16《计算机操作系统》-第3章25/983.2评价调度算法的准则内容准则评价指标要点指标含义计算方式2020/1/16《计算机操作系统》-第3章26/98调度算法的评价准则基本原则：具有公平性资源利用率高（特别是CPU利用率）在交互式系统情况下要追求响应时间（越短越好）在批处理系统情况下要追求系统吞吐量面向系统的准则：系统吞吐量高；处理机利用率好；各类资源的平衡利用面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则2020/1/16《计算机操作系统》-第3章27/98处理器利用率CPUutilization响应时间responsetime周转时间turnaroundtime系统吞吐量throughput处理器利用率为CPU有效工作时间与CPU总的运行时间之比，即：CPU利用率=CPU有效工作时间/CPU总的运行时间CPU总的运行时间=CPU的有效工作时间+CPU的空闲时间响应时间是交互环境下用户从键盘提交第1个请求开始，到系统首次产生响应为止的时间，或者是屏幕上显示出结果为止的时间。响应时间=从终端键盘输入的请求信息传送到处理机的时间+处理机对请求信息的处理时间+生成的响应信息回送到终端显示器的时间周转时间指用户作业提交给操作系统开始到作业完成为止的时间。周转时间通常是评价批处理系统性能、选择作业调度方式与算法的重要准则之一。周转时间Ti=作业在后备队列中的等待调度时间+进程在就绪队列上等待调度的时间+进程在CPU上的运行时间+进程等待I/O或其他事件发生的时间作业的带权周转时间Tf=作业的周转时间Ti/系统为作业提供的服务时间TsinisiidTTnT11niiTnT11单位时间内处理的进程数目为CPU的工作成效，单位时间内完成的进程数目为系统的吞吐量。在选择处理器的调度算法时，用户希望CPU利用率和系统吞吐量越大越好，响应时间和周转时间越小越好。但是，通常情况下，系统希望的是能够合理利用处理器和各类资源，使作业的平均周转时间或带权周转时间小的调度算法。对于实时系统，作业调度的关键在于能否满足作业的实时要求，对周转时间等指标并不特别着重。调度算法的评价指标2020/1/16《计算机操作系统》-第3章28/98本章目录3.1处理器调度的层次3.2评价调度算法的准则3.3调度算法3.4线程调度3.5实时调度3.6多处理器调度3.7Windows2000/XP系统的处理器调度2020/1/16《计算机操作系统》-第3章29/983.3调度算法内容作业调度算法进程调度算法要点算法思想指标计算2020/1/16《计算机操作系统》-第3章30/983.3调度算法内容作业调度算法进程调度算法要点算法思想指标计算2020/1/16《计算机操作系统》-第3章31/98作业调度算法概念回顾作业调度是在资源满足的条件下，将处于后备状态的作业调入内存，同时生成与作业相对应的进程，并为这些进程提供所需要的资源。作业调度程序只保证被调度的作业有获得处理器的资格，而处理器的分配则需要进程调度才能