04 处理机管理19064

《04 处理机管理19064》由会员分享，可在线阅读，更多相关《04 处理机管理19064（56页珍藏版）》请在金锄头文库上搜索。

1、4 处理机调度,4.1 分级调度4.2 作业调度4.3 进程调度4.4 调度算法4.5 算法评价4.6 实时系统调度方法本章小结习题,CPU是计算机系统中一个十分重要的资源。在早期的计算机系统中，对它的管理是十分简单的。随着多道程序设计技术和各种不同类型的操作系统的出现，各种不同的CPU管理方法得到启用。不同的CPU管理方法将为用户提供不同性能的操作系统。 例如：在多道批处理系统中，为了提高处理机的效率和增加作业吞吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合理。这样，就能使系统中的各种资源可充分利用。但由于是批处理，在用户看来，这是一台没有交互、速度较慢的处理机。在分时系统中，在调

2、度作业执行时要首先考虑每个用户作业得到处理机的均等性。这样，系统资源的利用率就不如批处理系统。在实时系统中，首先考虑的是处理机的响应时间。由此可以看到，根据操作系统的要求不同，处理机管理的策略是不同的。,4 处理机调度,4 处理机调度,衡量调度策略的最常用的几个指标是：周转时间、吞吐率、响应时间以及设备利用率等。 周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。 吞吐率是指在给定的时间内，一个计算机系统所完成的总工作量。 响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。 设备利用率主要指输入输出设备的使用情况。 本章将以CP

3、U 管理为核心，讨论管理、控制用户进程执行的方法。,4.1.1 作业的状态及其转换 一个作业从用户提交开始到真正占有处理机而被执行，则要由系统经过多级调度才能实现。 如图4.1 所示，一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等4个状态。,4.1 分级调度,图4.1 作业的状态及其转换,4.1 分级调度,另外，由于处于执行状态下的作业一般包含有多个进程，而在单机系统中，每一时刻只能有一个进程占有处理机。那么，其他进程就只能处于准备抢占处理机的就绪状态或等待得到某种新资源的等待状态。 为了提高资源的利用率，在有些操作系统中把一部分在内存中处于就绪状态或等待状

4、态而在短时期内又得不到执行的进程、作业换出内存，以让其他作业的进程竞争处理机。 这样，在外存中，除了处于后备状态的作业外，还存在有处于就绪状态而等待得到内存的作业。这就需要有一定的方法和策略为这部分作业分配空间。,4.1 分级调度,一般来说，处理机调度可以分为4级：(1) 作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。(2) 交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交

5、换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。,4.1 分级调度,(3) 进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。(4) 线程调度。,4.1 分级调度,在多道批处理系统中，存在着作业调度和进程调度。但是，在分时系统和实时系统中，一般不存在作业调度，而只有进程调度、交换调度和线程调度。 这是因为在分时系统和实时系统中，为了缩短响应时间或为了满足用户需求

6、的截止时间，作业不是建立在外存，而是直接建立在内存中。在这些系统中，一旦用户和系统的交互开始，用户马上要进行控制。因而，这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。,4.1 分级调度,4.1.3 作业与进程的关系 作业可被看作是用户向计算机提交任务的任务实体，例如一次计算、一个控制过程等。反过来，进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。显然，计算机要完成一个任务实体，必须要有一个以上的执行实体。也就是说，一个作业总是由一个以上的多个进程组成的。 那么，作业怎样分解为进程呢？首先，系

7、统必须为一个作业创建一个根进程。然后，在执行作业控制语句时，根据任务要求，系统或根进程为其创建相应的子进程，然后，为各子进程分配资源和调度各子进程执行以完成作业要求的任务。,4.1 分级调度,无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。 本节介绍进程调度的功能、进程调度发生的时机以及由进程调度引起的进程上下文切换等。,4.3 进程调度,4.3.1 进程调度的功能 进程调度的具体功能可总结如下：(1) 记录系统中所有

8、进程的执行情况 作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的 PCB 表中。并且，进程管理模式根据各进程的状态特征和资源需求，将各进程的 PCB 表排成相应的队列并进行动态队列转接。 进程调度模块通过 PCB 变化来掌握系统中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。,4.3 进程调度,(2) 选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。 根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法和多级反馈轮转

9、法等。这些选择策略决定了调度算法的性能。(3) 进行进程上下文切换 一个进程的上下文（context）包括进程的状态、有关变量和数据结构的值、硬件寄存器的值和PCB以及有关程序等。一个进程的执行是在进程的上下文中执行。,4.3 进程调度,4.3.2 进程调度的时机 进程调度发生在什么时机呢？这与引起进程调度的原因以及进程调度的方式有关。 引起进程调度的原因有以下几类：(1) 正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。(2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。(3) 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激

10、活了等待资源的进程队列。(4) 执行中进程提出IO请求后被阻塞。(5) 在分时系统中时间片已经用完。,4.3 进程调度,(6) 在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。 以上都是在CPU执行不可剥夺方式下所引起进程调度的原因。在CPU执行方式是可剥夺时，还有：(7) 就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。 所谓可剥夺方式，即就绪队列中一旦有优先级高于当前执行进程优先级的进程存在时，便立即发生进程调度，转让处理机。,4.3 进程调度,4.3.3 进程上下文切换 进程上下文由正文段、数据段、硬件寄

11、存器的内容以及有关数据结构等组成。 硬件寄存器主要包括存放 CPU 将要执行的下条指令虚拟地址的程序计数器 PC，指出机器与进程相关联的硬件状态的处理机状态寄存器 PSW，存放过程调用（或系统调用）时所传递参数的通用寄存器 R 以及堆栈指针寄存器 S 等。 数据结构则包括 PCB 等在内的所有与执行该进程有关的管理和控制用表格、数组、链等。 在发生进程调度时，系统要做进程上下文切换。,4.3 进程调度,进程上下文切换一般有以下4个步骤：决定是否做上下文切换以及是否允许做上下文切换。 保存当前执行进程的上下文。 使用 4.5 节中所述进程调度算法，选择一个处于就绪状态进程。(4) 恢复或装配所选

12、进程的上下文，将 CPU 控制权交给所选进程。,4.3 进程调度,4.3.4 进程调度性能评价 进程调度虽然是系统内部的低级调度，但进程调度的优劣直接影响作业调度的性能。 反映作业调度优劣的周转时间只在某种程度上反映了进程调度的性能，例如，其执行时间部分中实际上包含有进程等待（包括就绪状态时的等待）时间，而进程等待时间的多少是要依靠进程调度策略和等待事件何时发生来决定的。 进程调度性能是操作系统设计的一个重要指标。,4.3 进程调度,进程调度性能的衡量方法可分为定性和定量两种。 定性衡量方面，首先是调度的可靠性。另外，简洁性也是衡量进程调度的一个重要指标。 定量评价包括CPU的利用率评价、进程

13、在就绪队列中的等待时间与执行时间之比等。 实际上，由于进程进入就绪队列的随机模型很难确定，而且进程上下文切换等也将影响进程的执行效率，从而对进程调度进行解析是很困难的。 一般情况下，大多利用模拟或测试系统响应时间的方法来评价进程调度的性能。,4.3 进程调度,本节讨论各种常用的进程调度算法和作业调度算法。1. 先来先服务（FCFS）调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。在没有特殊理由要优先调度某类作业或进程时，从处理的角度来看，FCFS 方式是一种最合适的方法，无论是追加还是取出一个队列元素在操作上

14、都是最简单的。 直观看，该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中等待时间长短来决定它们是否优先享受服务。不过对于那些执行时间较短的作业或进程来说，如果它们在某些执行时间很长的作业或进程之后到达，则它们将等待很长时间。,4.4 调度算法,1. 先来先服务（FCFS）调度算法 在实际操作系统中，尽管很少单独使用 FCFS 算法，但和其他一些算法配合起来，FCFS 算法还是使用得相当多的。 例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的 FCFS 方式。,4.4 调度算法,2. 轮转法（round robin） 将CPU的处理时间分成固定大小的时间片。如果一个进

15、程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的 CPU 而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程或作业。,4.4 调度算法,显然，轮转法只能用来调度分配那些可以抢占的资源。将它们随时剥夺再分配给别的进程。CPU 是可抢占资源的一种。但如打印机等资源是不可抢占的。 由于作业调度是对除了 CPU 之外的所有系统硬件资源的分配，其中包含有不可抢占资源，所以作业调度不使用轮转法。,4.4 调度算法,图4.4 轮转法调度,2. 轮转法（round robin）,2. 轮转法（round robin） 在轮转法中，时

16、间片长度的选取非常重要。时间片长度的选择会直接影响系统开销和响应时间。 时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加重系统开销。 时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。 时间片长度的选择是根据系统对响应时间的要求 R和就绪队列中所允许的最大进程数 Nmax 确定的。它可表示为：q = R / Nmax,4.4 调度算法,通常，系统开销也是处理机执行时间的一部分。CPU的整个执行时间等于各进程执行时间加上系统开销。在进程执行时间大幅度减少的情况下，如果系统开销也随之减少的话，系统的响应时间有可能更好一点。 例如，响应时间R 为10s, Nmax 为10，则 Q=1s,如果系统大部分时候都只有最多3个进程，并且每个进程都能在3s内完成，这时候由于进程切换而引起的系统开销是没必要的。 一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次 q 值，作为新一轮调度的时间片。这种方法得到的时间片随就绪队列中的进程数变化。,