第3章 处理机调度4.ppt

1、第3章 处理机调度,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,处理机调度,处理机调度是操作系统的重要功能之一，其调度策略决定了操作系统的类型，其算法优劣直接影响整个系统的性能。调度问题是操作系统设计的一个中心问题。 调度就是选出待分配的作业或进程。处理机调度的目的就是分配处理机。 除了挑选合适的进程投入运行以外，调度程序还要关注CPU的利用效率。,在不同的操作系统中所采用的调度方式并不完全相同。有的系统中采用一级调度、二级调度或三级调度，且调度的算法也可以完全不同。 三级调

2、度模型：作业从进入系统到最后完成，可以经历三级调度：高级调度、中级调度和低级调度。,调度级别, 高级调度,高级调度：又称作业调度。 主要功能：根据一定的算法，从输入的一批作业中选出若干个作业，分配必要的资源，如内存、外设等。为其建立相应的用户作业进程和为其服务的系统进程（如I/O进程），最后把它们的程序和数据调入内存，等待进程调度程序对其进行调度，并在作业完成后作善后处理工作。, 中级调度,为了使内存同时存放的进程数目不至于太多，有时需将某些进程从内存中移到外存上，以减少多道程序的数目。引入中级调度的目的是提高内存的利用率和系统吞吐量。实际上是内存管理中的对换功能。, 低级调度,低级调度：又称

3、进程调度。 主要功能：根据一定的算法将CPU分配给就绪队列中的一个进程。 执行进程调度的程序称为进程调度程序，由它实现CPU在进程间的切换。进程调度程序运行频率很高，在分时系统中往往经过几十毫秒就要运行一次。 进程调度是操作系统中最基本的一种调度。在一般类型的操作系统中都必须有进程调度，且调度策略的优劣直接影响整个系统的性能。,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.2 作业调度,3.2.1 作业状态 3.2.2 作业调度,3.2.1 作业状态（4种）,提交状态：用户

4、向系统提交一个作业时，该作业所处的状况。 后备状态：用户作业经过输入设备送入输出井（磁盘）中存放，等待进入内存时所处的状况。此时，该作业的数据已转换成为机器可读的内部形式，并且作业请求资源等信息也交给了操作系统。,执行状态：作业分配到所需要的资源，被调入内存，其进程经调度在处理机上执行相应的程序时所处的状况。此时该作业真正处于活动状态。 完成状态：作业完成了计算任务，结果由打印机输出，最后由系统收回分配给它的全部资源，准备退出系统时的作业状况。,作业的流程,3.2.2 作业调度,作业控制块（Job Control Block ，JCB ）：在多道批处理系统中通常有上百个作业被收容在输入井（磁盘

5、）中，为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的JCB的组成内容有所区别。,作业控制块的主要内容,JCB是作业在系统中存在的唯一标志。作业进入系统时由SPOOLing系统为每个作业建立一个JCB；当作业退出系统时，则它的JCB也一起被撤消。 在磁盘输入井中的所有后备作业按作业类型（CPU型、I/O型等）组成不同的后备作业队列。由作业调度程序从中挑选作业，随后放入内存，予以运行。 作业调度主要用于批处理系统。,2. 作业调度的主要任务：完成作业从后备状态到执行状态和从执行状态到完成状态的转换。 作业调度的主要功能： 记录系统中各个作业的情

6、况; 按照某种调度算法从后备作业队列中挑选作业; 为选中的作业分配内存和外设等资源; 为选中的作业建立相应的进程; 作业结束后进行善后处理工作。,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.3 进程调度,3.3.1 进程调度的功能和时机 3.3.2 两级调度模型 3.3.3 三级调度模型,3.3.1 进程调度的功能和时机,进程调度为低级调度，完成进程状态从就绪态到运行态的转化。进程调度程序完成一台物理CPU转变为多台虚拟（或逻辑）CPU的工作。 进程调度程序是操作系统的真

7、正核心，它直接负责CPU的分配。系统中所有进程都是在CPU上运行的，进程调度程序就是它们的切换开关。,1. 进程调度的主要功能,保存现场：当前运行的进程调用进程调度程序时, 即表示该进程要求放弃CPU。这时，进程调度程序把它的现场信息, 如程序计数器及通用寄存器的内容等保留在该进程PCB的现场信息区中； 挑选进程：根据一定的调度算法, 从就绪队列中选出一个进程, 并将其状态置为运行态, 准备分配CPU； 恢复现场：为选中的进程恢复现场信息, 并将CPU控制权交给该进程, 从而接着上次间断的地方继续运行。,2. 进程调度的时机,任务完成：正在运行的进程完成任务后, 主动释放对CPU的控制； 等待

8、资源：由于等待某些资源或事件, 正在运行的进程不得不放弃CPU; 运行到时：在分时系统中, 当前进程使用完规定的时间片时, 时钟中断使该进程让出CPU; 发现标志：核心处理完中断或陷入事件后, 发现系统中“重新调度”标志被置上, 表明有比当前用户进程更适宜运行的进程, 则执行进程调度。,二、进程的状态和组成,3.3.2 两级调度模型,作业调度和进程调度是CPU主要的两级调度，它们的区别如下: 级别不同。作业调度是宏观调度，为进程活动做准备,进程调度是微观调度，使进程真正活动起来； 执行频率不同。作业调度次数少,进程调度频率高； 有的系统不设作业调度, 但进程调度必不可少。,二级调度简化队列图,

9、本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.4 调度性能的评价,3.4.1 调度策略的选择 3.4.2 性能评价准则,3.4.1 确定调度策略时应考虑的主要因素,设计目标。所用算法应保证实现系统的设计目标。 目标不同， 系统设计要求不同。 批处理系统: 提高资源利用率和增加系统的平均吞吐量； 分时系统: 保证对用户的均衡响应时间; 实时系统: 实现对事件的及时可靠的处理; 网络系统: 用户和程序能方便、有效地利用网络中的分布式资源。,公平性。对所有作业或进程应公平对待，使

10、每个进程能公平地共享CPU。 均衡性。均衡使用资源，尽量使系统中各种资源同时得到利用，提高资源的利用率。 统筹兼顾。兼顾响应时间和资源利用率。对分时系统，应在很短的时间响应用户需求。 优先级。基于相对优先级，但避免无限延期。随着等待时间的延长，低优先级进程的优先级应得到提升。 开销。系统开销不应太大。,3.4.2 性能评价准则,CPU利用率： 实际系统中，CPU利用率一般从40%(轻负荷系统)至90%(重负荷系统)。通常在一定的I/O等待时间的百分比下，运行程序道数越多，CPU空闲时间的百分比越低。 吞吐量：单位时间内CPU完成作业的数量。,3. 周转时间,周转时间：从作业提交到作业完成的时间

11、间隔。用于作业等待进入内存， 进程在就绪队列中等待， 进程在CPU上执行和完成I/O操作所花费时间的总和。 Ti = tci tsi 其中： tsi表示作业的提交时间，亦即作业到达 系统的时间； tci表示作业的完成时刻。 平均周转时间: n个作业的平均周转时间T为:,带权周转时间：为周转时间T和实际运行时间R之比。能合理的反映长短作业的差别。 W = T / R 平均带权周转时间：,4. 就绪等待时间：CPU的调度算法并不真正影响作业执行或I/O操作的时间数量。各种CPU调度算法仅影响作业(进程)在就绪队列中所花费的时间数量。 5. 响应时间：从提交第一个请求到产生第一个请求的回应所用的时间

12、。为刚开始响应的时间，而不是用于输出响应的时间。,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.5 常见调度算法,3.5.1 先来先服务法（FCFS） 3.5.2 时间片轮转法（RR） 3.5.3 优先级法 3.5.4 其它调度算法简介,3.5.1 先来先服务法（FCFS）,实现思想：每次调度都选择队头的作业或进程； 有利于长作业（进程），不利于短作业（进程）； 有利于CPU繁忙型作业（需大量CPU时间进行计算的作业），不利于I/O繁忙型作业（需频繁请求I/O的作业）； 算

13、法简单，实现容易，但效率低。,例如：设有三个作业，编号为1，2，3。各作业分别对应一个进程。各作业依次到达，相差一个时间单位，3个进程分别需要运行24、3和3个时间单位。 图示三个作业的执行顺序； 算出各作业的周转时间和带权周转时间。,复习：,周转时间：从作业提交到作业完成的时间间隔。 Ti = tci tsi 平均周转时间: n个作业的平均周转时间T为: 带权周转时间：为周转时间T和运行时间R之比。 W = T / R 平均带权周转时间：,图示三个作业的执行顺序： 算出各作业的周转时间和带权周转时间：,3.5.2 时间片轮转法（RR）,主要用于分时系统中的进程调度。 实现思想： 系统把所有就

14、绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。当进程用完分给它的时间片后，系统计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复，如同轮流坐庄。,例如：设4个进程A、B、C和D依次进入就绪队列（同时到达），四个进程分别需要运行12、5、3和6个时间单位。 图示RR法时间片q=1和q=4时进程运行情况； 算出各进程的周转时间和带权周转时间。,时间片轮转法(q=1),26,时间片轮转法(q=

15、4),26,时间片轮转法的性能,时间片的大小对轮转法的性能影响很大。 时间片的长短由下列因素决定： 系统响应时间：在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求； 就绪队列进程的数目：当系统要求响应时间一定时，时间片的大小反比于就绪队列中的进程数； 进程的转换时间：若进程的转换时间为t，时间片为q，为保证系统开销不大于某个标准，应使比值t/q不大于某一数值，如1/10； CPU运行指令速度：CPU运行速度快，时间片可短些。反之，则应取长些。,3.5.3 优先级法,实现思想：从就绪队列中选出优先级最高的进程，把CPU分给它使用。 两种处理方式： 非抢占式优先级法：当前占用CPU的进

16、程一直运行下去，直到完成任务或因等待某事件发生而主动让出CPU时，系统才让另一个优先级高的进程占用CPU。 抢占式优先级法： 当前进程在运行过程中，一旦有另一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程的运行，强行将CPU分给那个进程。,进程优先级可由系统内部定义或外部指定: 内部优先级：利用某些可度量的量来定义一个进程的优先级, 如，进程类型, 进程对资源的需求(时间限度,需要内存大小,打开文件的数目,I/O平均工作时间与CPU平均工作时间的比值等), 用它们来计算优先级。 外部优先级：按操作系统以外的标准设置, 如，外单位人员租用计算中心大型计算机所付款的类型和总数, 使

17、用计算机的部门以及其它的外部因素。,静态优先级和动态优先级: 优先数： 标识优先级的整数， 在Unix/Linux系统中，优先数越小， 优先级越高。 静态优先级：在创建进程时确定，且在进程的整个运行期间保持不变。优点是易于实现，系统开销小；缺点是会出现“饥饿”现象。 动态优先级：随着进程推进优先级不断改变，如，使得系统中等待CPU很长时间的进程逐渐提升其优先级，避免发生“饥饿”现象。,例如：假定在单CPU条件下有下列要执行的作业： 各作业依次到达，相差一个时间单位。 用执行时间图描述非抢占优先级调度算法执行这些作业的情况； 算出各作业的周转时间和带权周转时间。,用执行时间图描述非抢占优先级调度

18、算法执行这些作业的情况,算出各作业的周转时间和带权周转时间,3.5.4 其它调度算法简介,短作业优先法(SJF)：主要用于作业调度。 基本思想: 从后备作业队列中选取运行时间最短的作业放入内存。采用非抢占策略，系统选中某个短作业后投入运行，直到该作业完成并退出系统。 特点: 能有效地降低作业的平均等待时间和提高系统吞吐量，但对长作业很不利，且不能保证紧迫性作业会被及时处理。,最短剩余时间优先（SRTF） 采用抢占式策略。当新进程加入就绪队列时，若其需要的运行时间比当前运行进程所需的剩余时间还短，则强行夺取运行进程的CPU控制权，新进程调度运行。 特点：总能保证新的短作业一进入系统就得到执行，但

19、该算法需要增加系统开销，如保存进程断点现场，统计进程剩余时间等。,多级队列法 根据作业的某些特性，如占用内存大小和作业类型等，永久性的将各个作业分别链入不同的队列，每个队列有自己的调度算法。 如，把前台作业(交互型作业)队列和后台作业各设一个队列， 前台作业可用轮转法调度，后台作业可用FCFS调度。 此外，各队列间也要进行调度，通常采用固定优先级的抢占式调度。,多级反馈队列,系统中设置多个就绪队列, 每个队列对应一个优先级，第一个队列的优先级最高，其余逐级降低； 各就绪队列中进程的运行时间片不同，高优先级队列时间片小，低优先级队列时间片大； 新进程进入系统后，先放入第一队列的末尾，各队列按FC

20、FS方式排队； 若某个进程在相应时间片内未完成工作，则将其转到下一级队列的末尾； 系统先执行第一队列中的进程, 第一队列为空后，才运行第二队列，以此类推，最后一个队列采用时间片轮转法进行调度。,多级反馈队列,特点: 算法复杂, 但性能较好, 如 Unix, Windows NT, OS/2系统等采用。,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.6 中断处理,3.6.1 中断概述 3.6.2 中断处理过程 3.6.3 中断优先级和多重中断 3.6.4 系统调用处理 3.6

21、.5 shell命令的一般执行过程,3.6.1 中断概述,操作系统实施并发的基础是由硬件和软件结合而成的中断机制。 中断的典型实例是I/O中断，由系统调用引发的事件称作陷入（Trap）。 中断的概念 中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，如被中断进程的优先级最高，则返回断点继续执行被“打断”的程序。,中断示意图,几个概念,中断源：引起中断的事件或发出中断请求的来源。 中断请求：中断源向CPU提出的处理请求。 断点：发生中断时，被打断程序的暂停点。 中断最初作为通道（或设备）与CPU之间进行通信的工具。后来

22、发展为： 系统其他部件也可以造成中断。如，程序执行时运算的溢出、取数时奇偶错、电源故障、时钟计数等。 访管指令（或系统调用）中断。用户程序以此得到系统的内部服务。,2. 中断的类型 按功能划分 机器故障中断：产生于硬件故障 I/O中断：产生于通道和各种外部设备 外部中断：产生于计算机系统外部装置 程序性中断：产生于指令或数据的错误使用 访管中断：产生于“访问管理程序”的执行,按产生中断的方式划分 强迫中断：预料之外的事件发生，如机器故障、I/O中断、外部中断、程序性中断。 自愿中断：程序中有意使用的访管指令或系统调用。 按中断事件来源划分 中断：由CPU以外的事件引起的。如I/O中断、时钟中断

23、、控制台中断等。 异常：来自CPU内部的事件或程序执行中的事件。如CPU故障、程序故障、访管指令等。,3.中断系统的作用,提高主机的利用率，使高速CPU与低速外部设备可以并行工作； 及时进行事故处理； 实现分时操作； 实现实时操作； 方便程序调试。,3.6.2 中断处理过程,硬件级的中断结构与过程,1.中断的硬件结构,2. 中断响应 由硬件对中断请求做出反应的过程，称为中断响应。 中断响应顺序执行以下动作： 中止当前程序的执行； 保存原程序的断点信息（主要是程序计数器PC和程序状态寄存器PS的内容）； 转到相应的处理程序。 通常CPU在执行完一条指令后，立即检查有无中断请求。如有，而且“中断允

24、许”触发器为1，则立即做出响应。,3. 中断处理 中断响应后，就由软件（中断处理程序）进行相应处理。 中断处理过程分为4个阶段： （1）保存被中断程序的现场； （2）分析中断原因； （3）转入相应处理程序进程处理 （4）恢复被中断程序现场（即中断返回）,中断处理的一般过程,3.6.3 中断优先级和多重中断,中断优先级 当系统中同时发生多个中断时，硬/软件按优先次序处理中断。采用中断屏蔽可以改变中断处理顺序。 与某种中断相关的优先权称为它的中断优先级。优先级高的中断优先响应，通过线路排队办法实现。 另外，级别高的中断一般有打破级别低的中断处理程序的权利。,2. 中断屏蔽 中断屏蔽：在提出中断请求

25、后，CPU不予响应的状态。 中断禁止：在可引起中断的事件发生时系统不接收该中断信号，因而就不可能提出中断请求而导致中断。即不让某些事件产生中断。 两者的区别： 中断屏蔽表明硬件接受了中断请求，但暂时不能响应，要等待中断开放即可得到响应； 中断禁止是硬件根本不允许提出中断请求。,中断屏蔽的作用： 延迟或禁止对某些中断的响应； 协调中断响应与中断处理的关系 ； 防止同类中断的相互干扰 。 中断屏蔽的方式： 屏蔽方式随机器而异，可以用于整级屏蔽，也可用于单个屏蔽。,3. 多重中断 处理多个中断的方法有顺序处理方式和嵌套处理方式。 顺序处理方式 当一个中断正被处理期间，屏蔽其他的中断；在该中断处理完后

26、，开放中断，由处理器查看有无尚未处理的中断。如果有，则依次处理。 缺点：没有考虑中断的相对优先级或时间的紧迫程度 。,嵌套处理方式 这种方式对每类中断赋予不同的优先级，允许高优先级中断打断低优先级中断的处理程序 。 缺点：给程序设计带来困难。,3.6.4 系统调用处理,1陷入事件的处理方式 在UNIX/Linux系统中，对异常的处理称作陷入。 引起陷入的事件可以分为两组：一组是自愿进入陷入，称作自陷，如使用系统调用、断点跟踪；另一组是由于程序运行过程中出现软、硬件故障或错误，如转换无效、访问违章、非法指令等，也称作捕俘。 陷入处理的基本过程与中断处理基本相同。,陷入处理子程序的处理方式： 请求

27、系统管理人员干预：核心态下的陷入 ； 按用户规定方式进行处理 ：用户态下的陷入； 用户栈自动扩充：用户栈满自动扩充； 系统调用处理。,2. 系统调用的处理方式 UNIX/Linux系统中，系统调用以C语言函数形式出现在程序中。 系统调用可以做到把进程的运行模式从用户态变为核心态，即从用户空间转入系统空间，而一般的函数调用序列无法做到。 系统调用是CPU主动、同步地进入系统空间的手段。因为系统调用是由用户预先安排在程序的确切位置上的。,trap指令的一般格式是： trap xx 参数1 参数2 其中，xx表示系统调用号。 当CPU执行到trap指令时，CPU的状态就从用户态变为核心态。 陷入总控

28、程序：处理所有的陷入事件的总服务程序，属于内核。,执行过程,首先，陷入总控程序将有关参数压入系统栈中，以备返回用户空间、恢复现场时使用。 然后，调用陷入处理程序trap。trap程序根据陷入事件的不同类型做不同的处理。对于非法指令、跟踪陷入、指令故障、算术陷入、访问违章、转换无效等事件，转入信号机构进行处理（见下一节）；对于系统调用事件，调用system_call（系统调用处理函数）进行处理。 系统调用处理函数根据trap指令后面的系统调用号去查系统调用入口表，然后转入各个具体的系统调用处理程序。,3. 系统调用实现过程示例,问题描述： 设用户进程A在运行中要向已打开的文件（用fd表示）写一批

29、数据，为此在用户C源程序中可用如下系统调用语句： rw=write (fd,buf,count)； 编译后形成的汇编指令形式如下： trap 4 参数1 参数2 参数3 k1： 其中，参数1，2，3分别对应该文件的文件描述字fd，用户信息所在内存始址buf，传送字节数count。,系统调用执行过程,3.6.5 shell命令的一般执行过程,Linux系统提供给用户的最重要的系统程序是shell命令语言解释程序。它不属于内核部分，而是在核心之外以用户态方式运行。 shell基本功能：解释并执行用户输入的各种命令，实现用户与Linux核心的接口。系统初启后，核心为每个终端用户建立一个进程去执行sh

30、ell解释程序。,shell命令执行过程：,读取用户由键盘输入的命令行 ； 分析命令，以命令名作为文件名，其他参数改造为系统调用execve( )内部处理所要求的形式； 终端进程调用fork( )建立一个子进程 ； 终端进程本身用系统调用wait4( )来等待子进程完成（如果是后台命令，则不等待）。当子进程运行时调用execve( )，子进程根据文件名（即命令名）到目录中查找有关文件（这是命令解释程序构成的文件），调入内存，执行这个程序（即执行这条命令）；, 如果命令末尾有&号（后台命令符号），则终端进程不用执行系统调用wait4( )，而是立即发提示符，让用户输入下一个命令，转步骤（1）。

31、如果命令末尾没有&号，则终端进程要一直等待，当子进程（即运行命令的进程）完成工作后要终止，向父进程（终端进程）报告，此时终端进程醒来，在做必要的判别等工作后，终端进程发提示符，让用户输入新的命令，重复上述处理过程。,shell命令基本执行过程,本章内容,3.1 调度级别 3.2 作业调度 3.3 进程调度 3.4 调度性能的评价 3.5 常用调度算法 3.6 中断处理 3.7 Linux系统中的进程调度,3.7 Linux系统中的进程调度,3.7.1 Linux进程调度 3.7.2 Linux常用调度命令,3.7.1 Linux进程调度,1调度方式 Linux系统的调度方式基本上采用“抢占式优先级”方式； Linux系统中的调度基本上继承了UNIX系统的以优先级为基础的调度。即核心为系统中每个进程计算出一个优先级，该优先级反映了一个进程获得CPU使用权的资格，即高优先级的进程优先得到运行。,2调度策略 Linux系统针对不同类别的进程