第2章处理机管理PPT课件

1、LOGO1第2章 处理机管理学习要点： 进程的概念 进程的组成与管理 处理机的调度算法 处理机的二级调度与作业管理LOGO2处理机管理第二章正文2.1 进程 2.1.1多道程序设计多道程序设计程序A程序B程序C0469141820232630423542334程序A程序B程序C0469131822121517(a) 单道程序设计环境(b) 多道程序设计环境时间时间打印机输出CPU执行图例：.单道程序设计环境特点单道程序设计环境特点1.资源的独占性资源的独占性.执行的顺序性执行的顺序性结果的再现性结果的再现性多道程序设计环境特点多道程序设计环境特点2.执行的并发性执行的并发性.相互的制约性相互的

2、制约性状态的多变性状态的多变性LOGO3处理机管理第二章正文2.1 进程用户程序用户程序监督程序监督程序磁盘操作磁盘操作磁带操作磁带操作磁盘操作磁盘操作磁带操作磁带操作用户程序用户程序A用户程序用户程序B监督程序监督程序请求带输入启动磁带机结束中断请求盘输入启动磁盘中断处理结束中断中断处理CPU运行设备运行t两道作业运行情况两道作业运行情况请求盘输入启动盘调度B请求带输入结束中断中断处理调度A中断处理调度B结束中断CPU运行设备运行单道作业运行情况单道作业运行情况结束中断LOGO4处理机管理第二章正文2.1 进程. 用户进程用户进程：可以并发执行的用户程序段，它们是操作系统的服务对象，是系统资

3、源的实际享用者。 系统进程系统进程：操作系统中用于管理系统资源的那些并发程序，它们向用户提供系统服务，分配系统的资源。 2.1.2进程的定义进程的定义1.应该从应该从3个方面来描述进程个方面来描述进程.进程是程序的一次运行活动；进程的运行活动是建立在某个数据集合之上；进程要在获得资源的基础上从事自己的运行活动。2.3.进程定义进程定义 所谓“进程进程”，是指一个程序在给定数据集合上的一次执行过程，是系统进是指一个程序在给定数据集合上的一次执行过程，是系统进行资源分配和运行调度的独立单位行资源分配和运行调度的独立单位。进程的分类进程的分类.LOGO5处理机管理第二章正文2.1 进程 系统进程直接

4、管理软、硬件资源的活动；用户进程不得插手资源管理，在需要使用某资源时，须向系统提出申请，由系统统一调度与分配。 系统进程间的相互关系由操作系统负责协调；用户进程间的相互关系由用户自己(在程序中)安排，操作系统向用户提供一定的协调手段(以命令的形式)。 4. 系统进程与用户进程的区别系统进程与用户进程的区别. 系统进程使用资源的级别，高于用户进程。 LOGO6处理机管理第二章正文2.1 进程 进程间会相互制约进程间会相互制约。进程是系统中资源分配和运行调度的单位，因此在对资源共享和竞争中，必然会相互制约，影响着各自向前推进的速度。 进程之间具有并发性进程之间具有并发性。系统中多个进程对应的多个程

5、序同时在系统中运行，轮流占用CPU和各种资源。 每个进程都有自己的生命期每个进程都有自己的生命期。一个进程创建后，系统就感知到它的存在；撤消后，系统就无法再感知到它。于是，从创建到撤消，这个时间段就是一个进程的“生生命期命期”。 不同进程可以执行同一个程序不同进程可以执行同一个程序。从进程定义知，区分进程的条件一是所执行的程序，二是数据集合。因此，即使多个进程执行同一个程序，只要它们运行在不同的数据集合上，那么它们就是不同的进程。 “进程进程”是一个动态的概念是一个动态的概念。进程强调的是程序的一次“执行”过程，因此它是一个动态的概念；程序是一组有序指令的集合，在多道程序设计环境下，它不涉及“

6、执行”，因此是一个静态的概念。 2.1.3进程的特征进程的特征1.2.进程与程序的关系进程与程序的关系进程与程序的区别进程与程序的区别 进程是程序的一次执行过程，程序是进程赖以存在的基础。这就是说，进程与程序之间有一种必然的联系。但进程又不等同于程序，它们是两个完全不同的概念。 .LOGO7处理机管理第二章正文2.1 进程2.进程的特征进程的特征l 动态性 进程是对应程序的执行 进程是动态产生，动态消亡的，有生命周期l 并发性 多个进程同时运行l 独立性 进程是资源分配的一个独立单位l 制约性 指进程在执行过程中可能与其它进程产生直接或间接的关系LOGO8处理机管理第二章正文2.1 进程 在输

7、入/输出操作完成后，会使某个进程的状态由阻塞变为就绪。这属于由于外界环境的变化而引起的状态变化。 一个处于运行状态的进程，比如会由于提出输入/输出请求而使自己的状态变成为阻塞。这属于进程自身推进过程中引起的状态变化。 就绪状态就绪状态：已具备运行所需的一切条件，只是由于别的进程占用处理机而暂时无法运行。 运行状态运行状态：获得CPU的进程处于此状态，其对应的程序正在处理机上运行着。 阻塞状态阻塞状态：进程为了等待某种外部事件的发生（如等待输入/输出操作的完成，等待另一个进程发来消息），暂时无法运行。阻塞状态也称等待状态或挂起状态。 2.1.4进程的状态及状态变迁进程的状态及状态变迁1. 进程的

8、三种基本状态进程的三种基本状态2. 进程状态的变迁进程状态的变迁运行状态阻塞状态就绪状态调度该进程时间片用完某事件发生等待某事件发生. 一个进程的状态，可随自身的推进和外界环境的变化而变化，从一种状态变迁到另一种状态。进程状态变迁图中，箭头表示状态变迁的方向，文字是引起这种状态变迁的原因。.LOGO9处理机管理第二章正文2.2 进程控制块进程控制块进程控制块 2.2.1进程的三个组成部分进程的三个组成部分.程序程序数据集合数据集合PCB程序数据集合 为管理和控制进程，系统在创建一个进程时，都为其开辟一个专用的存储区，随时记录它在系统中的动态特性；当一个进程被撤消时，系统收回分配给它的存储区。把

9、这一存储区称作为该进程的“进程控制块PCB” 。 2.2 进程控制块进程控制块n 进程的组成：程序进程的组成：程序+ +数据数据+PCB+PCB程序段：描述进程所要完成的功能数据段：程序在执行时必不可少的工作区和操作对象进程控制块PCB (执行上下文)控制进程所需的数据(进程属性)，包括:进程标识符信息处理器状态信息进程控制信息LOGO10处理机管理第二章正文2.2 进程控制块 现场信息现场信息：进程暂时让出处理机时，须把当前各种现场信息保存在PCB的固定单元里。这样，当进程再次获得处理机时，就可以把这些信息置入处理机的相应寄存器中，恢复到被中断时的原有状态，保证进程正常执行。 标识信息标识信

10、息：代表了一个进程的身份，是系统内部区分不同进程的依据 。o2.2.2 进程控制块的内容进程控制块的内容.进程名进程状态程序存放位置数据存放位置通用寄存器内容控制寄存器内容断点地址进程优先数队列指针标识信息说明信息现场信息管理信息说明信息说明信息：随时反映进程的情况 。 管理信息管理信息：系统通过这些信息管理、调度进程，使它们有条不紊地工作。LOGO11处理机管理第二章正文2.2 进程控制块 就绪队列就绪队列：系统中所有处于就绪状态的进程的PCB排成一队，称其为“就绪队列”。一般地，就绪队列里会有多个进程的PCB排在里面，它们形成处理机分配的侯选对象。 阻塞队列阻塞队列：所有处于阻塞状态的进程

11、的PCB，应该根据阻塞的原因进行排队，每一个都称为一个“阻塞队列”。 2.2.3进程控制块队列进程控制块队列PCB1PCB2PCB5PCB10PCB3PCB7PCB6PCB8PCB9PCB4-1-1-1运行队列头指针就绪队列头指针阻塞队列1头指针阻塞队列2头指针运行队列：就绪队列：阻塞队列1：阻塞队列2：. 运行队列运行队列：处于运行状态的PCB构成运行队列。在单CPU系统，任何时刻系统里都只有一个进程处于运行状态，因此运行队列里只能有一个PCB 。.LOGO12处理机管理第二章正文2.3进程的调度与管理 进程调度程序：-操作系统中决定把cpu分配给哪个进程使用的程序-从就绪队列中选择一个进程

12、并把cpu分配给它使用 进程调度算法：-进程调度程序采用的调度方法LOGO13处理机管理第二章正文2.3进程的调度与管理处理机调度的三个层次处理机调度的三个层次 高级调度高级调度1. 当系统决定接纳一个作业时，就要为它开辟一个作业控制块（ JCB），以便随时记录作业的信息。 . 被系统接纳的作业，在没有投入运行前是以“后备作业后备作业”的形式存放在辅存里。所有后备作业的JCB链接在一起，形成“后备作业队列”。这些作业没有资格参与对处理机的竞争，但系统从它们的里面去挑选参与CPU竞争的作业。. 高级调度决定哪个后备作业可进入系统去接受处理，它控制着多道程序设计环境的“度”：进到系统的作业多，资源

13、的利用率提高了，但每个作业获得处理结果的时间可能会长；进到系统的作业少，每个作业很快就得到自己的处理结果，但资源的利用率可能会下降。 (（作业从外存到内存作业从外存到内存）)低级调度低级调度2. 低级调度真正决定CPU下一次执行哪一个进程，它将按照一定的算法，从就绪队列里挑选出可运行的进程投入运行。低级调度的各种算法，是我们讨论的主要目标。低级调度也被称为“进程调度” 。（进程获得进程获得cpu）LOGO14处理机管理第二章正文2.3进程的调度与管理中级调度中级调度 3. 中级调度是介于高级调度和低级调度之间的一种调度，如果系统为进程设置有“挂起”状态，那么就会涉及到中级调度。也就是说，中级调

14、度与实施进程的内、外存交换有关(把进程在内存和外存间交换）把进程在内存和外存间交换） 。 CPU就绪队列低级调度释放中级调度就绪/挂起队列时间片到高级调度阻塞/挂起队列阻塞队列中级调度事件等待事件发生交互用户作业后备作业队列. 系统中出现过高并发度时，就应将内存中的某些进程暂时换出到外存；系统的并发度较低时，就应该将外存中的某些进程换入到内存。进程在内、外存间的换出和换入，就是中级调度承担的责任，通过这种交换，以求达到调节和平衡系统“并发度”的目的。 . 高级调度执行的频繁程度很低，它只是粗略地决定是否接受一个新进程以及接受哪一个；中级调度为了实施交换决策，执行的频率相对要频繁一些；低级调度要

15、精确地决定执行哪一个进程，因此执行的频度为最高。 LOGO15处理机管理第二章正文2.3进程的调度与管理进程调度的功能、时机和基本策略进程调度的功能、时机和基本策略 1. 进程调度程序的功能进程调度程序的功能 .保护现场 .挑选运行对象 .恢复现场 2. 发生进程调度的时机发生进程调度的时机 当某进程正常完成自己的运行或被终止时，为不让CPU空闲，必须实行调度，以便从就绪队列里挑选新的进程投入运行。 . 分时系统中，时钟中断处理程序发现分配给某个进程的时间片用完时，就强制它交出CPU，重新进行CPU调度。 .运行中的进程提出I/O请求，或要等待别的进程发来消息，于是自己被阻塞。 .执行操作系统

16、提供的某些系统调用命令，如wait()等。 . 某进程的状态从阻塞变为就绪时，要由调度程序决定让哪一个进程投入运行：是新就绪进程、是正在运行的进程继续运行、还是调度另一个进程运行。 3. 进程调度的基本策略进程调度的基本策略 非抢占式：在把CPU分配给某个进程后，就一直让它使用下去，直到进程完成自己的工作，或因要等待某事件的发生而交出CPU，否则不允许其他进程夺取CPU。 . 抢占式：在调度程序把CPU分配给某进程使用后，只要满足某条件，就允许立即把CPU从运行进程手中夺取过来，分配给满足条件的进程使用。 LOGO16处理机管理第二章正文2.3进程的调度与管理 进程调度方式（两种）就 绪R执行

17、E只有一个 进程进程调度PA 5PB 4PC 2就 绪队列非抢占方式抢占方式优先权高低PD 6PA 将 继续运行此 时PD 将 抢占 PA 的运行作业长短时间片LOGO17处理机管理第二章正文2.3进程的调度与管理进程调度相关概念相关概念： 周转时间:进程从创建到结束运行所经历的时间。 平均周转时间：N个进程周转时间的平均值。 等待时间：等待CPU的时间之和。 平均等待时间：N个进程的等待时间的平均值。LOGO18处理机管理第二章正文2.3进程的调度与管理 2.3.1进程调度算法进程调度算法1.先来先服务调度算法先来先服务调度算法ABCD调度就绪队列到达阻塞队列完成I/O完成阻塞CPUI/O

18、基本思想：调度时以到达就绪队列的先后次序选择占用处理机的进程。进程一旦占有处理机，就一直用下去，直至结束或因等待某事件而让出处理机。 优点:实现简单 缺点:使短进程等待长进程，重要或紧迫的进程等待不那么重要或紧迫的进程特点:属于非抢占式调度方式，看似公平，但对后进入的短进程、I/O型进程不公平LOGO19处理机管理第二章正文2.3进程的调度与管理【例1】假设就绪队列中从队首开始依次排列有四个进程 P1、P2、P3、P4（假设它们几乎在0时刻同时到达就绪队列），它们的预计执行时间分别为16、12、4、3，若采用FCFS调度： （1）试给出这些进程的运行进度表； （2）计算各进程的周转时间和等待时

19、间； （3）计算系统的平均周转时间和平均等待时间；LOGO20处理机管理第二章正文2.3进程的调度与管理解：（1）FCFS运行进度表：（2）进程进程到达时刻到达时刻 运行时间运行时间开始时刻开始时刻结束时刻结束时刻周转时间周转时间 等待时间等待时间P10 16016160P201216282816P30428323228P40332353532（3）平均周转时间=（16+28+32+35）/4=28 平均等待时间=（0+16+28+32）/4=19LOGO21处理机管理第二章正文2.3进程的调度与管理 分析分析：a. 对对短进程不公平短进程不公平。b. 当长进程排在就绪队列的前面时必将增加后当

20、长进程排在就绪队列的前面时必将增加后面许多小进程的等待时间，从而将面许多小进程的等待时间，从而将增加系统增加系统的平均周转时间。的平均周转时间。c.不利于不利于I/O型进程型进程，未有效利用系统资源，未有效利用系统资源d. 现已很少用作主要的调度（分现已很少用作主要的调度（分/实时系统中实时系统中不能用）不能用）,一般与其他调度算法混合使用。一般与其他调度算法混合使用。e.FCFS同时同时适合于三级调度适合于三级调度。 LOGO22处理机管理第二章正文2.3进程的调度与管理A2.时间片轮转调度算法时间片轮转调度算法 基本思想：系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是

21、按FCFS选择队首的进程执行，调度时为进程分配一个称为“时间片”的时间段，并规定其执行完一个时间片时，系统将它送至就绪队列的末尾，再把处理机分配给就绪队列的队首进程。这样，处于就绪队列中的进程，就可以依次轮流的获得一个时间片的处理时间，然后回到队列尾部，如此不断循环，直至完成为止。ABCD调度就绪队列到达阻塞队列完成I/O完成阻塞CPUI/O时间片到特点：属于抢占调度方式，分时系统的典型调度算法。（只用于进程调度）过长退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。时间片长度的确定时间片长度的确定LOGO2

22、3处理机管理第二章正文2.3进程的调度与管理分配给进程A的一个时间片q分配给进程B的一个时间片q分配给进程A的另一个时间片q时钟中断时钟中断时钟中断用户A一次交互结束 RR调度算法的关键是时间片设置的大小。若时间片q设置得小，那么长作业可能需要经若干个时间片才能完成一次交互活动，从而增加了系统在进程间切换时的开销；若时间片q设置得长，长到每个交互只需要一个时间片就能够完成时，那么RR就成FCFS了。所以，时间片的尺寸最好是略大于一次典型交互活动所需的时间。 LOGO24处理机管理第二章正文2.3进程的调度与管理 引例引例: :请同学们思考，假设火车站限每人每次请同学们思考，假设火车站限每人每次

23、只可买一张票，现有只可买一张票，现有4个人排队买票，要买的张个人排队买票，要买的张数依次是数依次是6、4、8、5，那么他们买票的过程是？，那么他们买票的过程是？ 分析分析：现将买一张票的时间看作一个时间片，现将买一张票的时间看作一个时间片，4个人买票的过程分别看作进程个人买票的过程分别看作进程1,2,3,4，那么它，那么它们就是采用时间片轮转算法的思想进行的。们就是采用时间片轮转算法的思想进行的。LOGO25处理机管理第二章正文2.3进程的调度与管理【例2】进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms，均在0时刻到达。到达的先后次序为ABCD。如果时间片分别

24、为1 ms和5ms，计算各个进程的周转时间和平均周转时间。 分析分析 在掌握了时间片轮转法概念的基础上，我们可以用一个执行时间图来形象地表示作进程的执行情况，帮助我们理解此题。具体如下： LOGO26处理机管理第二章正文2.3进程的调度与管理解：解：采用时间片轮转法进行调度，算法的性能指标如下：LOGO27处理机管理第二章正文2.3进程的调度与管理 五个作业AE的情况如右所示，对进程实施两次RR调度算法，时间片分别为1个CPU时间单位和4个CPU时间单位。求各进程的开始运行时间、完成时间、周转时间、平均周转时间。 思考：RRq=1完成时间周转时间RRq=4完成时间周转时间作业情况 时间片进程名

25、到达时间服务时间ABCDE平均01234 43524 1210181117 1291681311.647121418 461011149LOGO28处理机管理第二章正文2.3进程的调度与管理123456789 10 11 12 13 14 15 16 17 18ABCDEABCDE(a) q=1(b) q=4A0BCABCDE4 1 3 213 2124 1 3 241 32 5DE43524LOGO29处理机管理第二章正文2.3进程的调度与管理3. 优先数调度算法优先数调度算法 基本思想：为系统中的每个进程规定一个优先数，就绪队列中具有最高优先数的进程有优先获得处理机的权利；如果几个进程的优

26、先数相同，则对它们实行先来先服务的调度。 进程的PCB里，都会记录进程的优先级。优先级常用数字表示，比如07，或04095。不过，数字0到底表示最高还是最低，各个操作系统不尽相同。有的系统以数字越小表示优先级越高，有的则以数字越大表示优先级越高。本书规定数字越小优先级越高。 LOGO30处理机管理第二章正文2.3进程的调度与管理设置优先数的方法设置优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 存在的问题：不灵活 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变LOGO31处理机管理第二章正文2.3进程的调度

27、与管理 就绪队列里有如右所示五个进程P1P5 ，实施HPF调度算法，试计算平均等待时间。例例3 ：进程所需CPU时间P1P2P3P4P5101215优先级31452它们的调度顺序是：P2P5P1P3P4 。.解解： .相应的gantt图如下所示。P2P5P1P3P40161618 19LOGO32处理机管理第二章正文2.3进程的调度与管理确定进程优先级的因素 根据进程的类型。比如由于系统进程完成的任务是提供系统服务，分配系统资源，因此给予系统进程较高的优先级，不仅合乎情理，而且也能够提高系统的工作效率。 (1)(2) 根据进程执行任务的重要性。每个进程所完成的任务，其重要性和紧迫性肯定是不一样

28、的。比如，赋予报警进程高的优先级，一旦紧急事件发生时，让它立即抢占CPU投入运行，这是理所当然的事情。 (3) 根据进程程序的性质。一个“处理机限制”进程，由于需占用较长的运行时间，影响系统整体效率的发挥，因此只能给予较低的优先级；一个“I/O限制”进程，给予它较高的优先级后，就能充分发挥CPU和外部设备之间的并行工作能力。 (4) 根据对资源的要求。系统资源有处理机、内存储器、外部设备等。可按照一个进程所需资源的类型和数量，确定它的优先级。比如给予占用CPU时间短或内存容量少的进程以较高的优先级，这样可以提高系统的吞吐量。 (5) 根据用户的请求。系统可以根据用户的请求，给予它的作业及其相应

29、进程很高的优先级，作“加急”处理。 . 进程优先级的分类：所谓“静态”优先级，即指在进程的整个生命期内优先数保持不变；所谓“动态”优先级，是指在进程的整个生命期内可随时修正它的优先级别，以适应系统环境和条件的变化。 LOGO33处理机管理第二章正文2.3进程的调度与管理4. 多级队列调度算法多级队列调度算法调度就绪队列到达完成CPU阻塞、就绪时间片到调度完成CPU阻塞、就绪调度完成CPU阻塞、就绪时间片到时间片到级1(先来先服务)级2(先来先服务)级n(先来先服务)基本思想：系统中维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时间片。级 1就绪队列里进程的调度级别最高，可

30、获得的时间片最短；级 n就绪队列里进程的调度级别最低，但可以获得的时间片最长。创建新进程时，它的PCB将先进入级 1就绪队列的末尾。 LOGO34处理机管理第二章正文2.3进程的调度与管理 多级队列（MQ）调度算法，是把就绪进程按不同的性质组合成若干个就绪队列，每个队列实行不同的进程调度算法。 系统进程就绪队列实时进程就绪队列交互进程就绪队列批处理进程就绪队列优先级高低. 可按进程的类型组建各种就绪队列：系统进程就绪队列、实时进程就绪队列、交互进程就绪队列、批处理进程就绪队列等。每个队列都执行自己的调度算法。 . 两个队列间获得CPU的权利要有先后次序。比如，根据每个队列的优先级不同，越往上的

31、队列，获得CPU的优先级越高；越往下的队列，获得CPU的优先级越低。这样，只有在系统进程就绪队列和实时进程就绪队列为空的前提下，才能够去调度交互进程就绪队列里的进程；当一个批处理进程执行时，若有一个交互进程抵达了就绪队列，那么批处理进程就将被抢占，把CPU让给交互进程使用。LOGO35处理机管理第二章正文2.3进程的调度与管理 系统从第1个队列开始调度；只有在前i-1个队列都空时，才调度第i个队列里的进程。当更高级别的队列到达进程时，系统将立即转去运行级别高的那个进程。 系统设多个就绪队列，有自己的优先级，第1个队列的优先级最高，越往下队列的优先级依次降低。 多级反馈队列的做法(1)(2) 为

32、就绪队列分配不同时间片，在优先级高的队列里的进程，获得的CPU服务时间短；在优先级低的队列里的进程，获得的CPU服务时间长。 (3) n个队列都实施FCFS调度算法，最后一个队列也可实施RR调度算法。新进程抵达时，先进入第1个就绪队列。进程在某个队列里获得时间片后，若用完时间片前被阻塞，仍回原队列末尾排队；若耗尽时间片后仍未做完工作，则将其移入低一级就绪队列排队，直至队列n。 (4)LOGO36处理机管理第二章正文2.3进程的调度与管理功能：在等待的事件发生后，由唤醒进程原语把等待进程从相应的阻塞队列里解放出来，进入就绪队列，重新参与调度。 撤消进程原语撤消进程原语 功能：为新建进程申请进程控

33、制块PCB，将创建者提供的信息填入PCB，将新建进程设置为就绪状态，按照调度算法把PCB排入就绪队列中。 2.3.2 进程管理的基本原语进程管理的基本原语1. 原语定义原语定义操作系统提供若干基本操作，以便能创建、撤消、阻塞和唤醒进程。为了保证执行的正确，要求它们以一个整体出现，不可分割。即一旦启动了对应的程序，就要保证做完，中间不能插入其它程序的执行序列。具有这种特性的程序被称为“原语原语”。为保证原语操作的不可分割性，通常总是利用屏蔽中断的方法。 2.进程管理的基本原语进程管理的基本原语.创建进程原语创建进程原语阻塞进程原语阻塞进程原语唤醒进程原语唤醒进程原语 功能：收回该进程占用的资源，

34、将该进程的PCB从所在队列里摘下，把PCB所占用的存储区归还给系统。 功能：将被阻塞进程的现场信息保存到PCB中，状态改为阻塞； 将其PCB排到相应的阻塞队列中。若被阻塞的是自己，调用了该原语后，就重新分配处理机。 LOGO37处理机管理第二章正文2.3进程的调度与管理作业： 进程ABCDE，它们到达和服务时间如下表，忽略I/O及其他开销时间，分别使用FCFS，时间片轮转,请给出各进程的完成时间、周转时间、平均周转时间。进程到达时间服务时间A04B13C25D32E44LOGO38处理机管理第二章正文2.4 作业调度2.4.1 用户与操作系统的两种接口用户与操作系统的两种接口1. 两种接口两种

35、接口.程序接口 操作系统提供各种系统调用命令，以让用户在编程时获得所需的功能服务。这是系统在程序一级给予用户的支持。命令接口 操作系统提供各种操作命令，以便用户通过键盘控制程序的运行。这是系统在作业控制一级给予用户的支持。2. 若干概念若干概念.特权指令与非特权指令 把CPU的指令分为两类：一类是操作系统和用户都能使用的指令，称为“非特权指令”；一类是只能由操作系统使用的指令，称为“特权指令”。 管态与目态 这是CPU的两种工作状态：当其处于管态时，可执行包括特权指令在内的一切机器指令；当其处于目态时，只能执行非特权指令，禁止使用特权指令。 LOGO39处理机管理第二章正文2.4 作业调度 一

36、般的过程调用，调用者与被调用者都运行在相同的CPU状态；但发生系统调用时，发出调用命令的调用者运行在目态，而被调用的对象则运行在管态。 .系统调用命令系统调用命令 操作系统里预先编制了不同功能的子程序，用户可在自己的程序里调用它们，以求操作系统提供功能服务。这些子程序被称为“系统功能调用”程序，简称“系统调用系统调用”。 访管指令访管指令是一条非特权指令，功能是执行它就会产生一个软中断，促使中央处理机由目态转为管态，进入操作系统 。用户程序只有通过 访管指令，才能由目态转为管态、以达到调用系统调用命令的目的。 .访管指令3.系统调用与一般过程调用的区别系统调用与一般过程调用的区别. 一般的过程

37、调用，直接通过转移指令转向被调用的程序；但系统调用时，只能通过访管指令提供的统一的入口，由目态进入管态，然后转向相应的系统调用命令。 一般的过程调用，执行完后径直返回断点继续执行；但系统调用可能会招致进程状态的变化，从而引起系统重新分配处理机，因此系统调用处理结束后，不一定是返回调用者断点处继续执行。 4. 操作命令操作命令脱机命令接口和联机命令接口。LOGO40处理机管理第二章正文2.4 作业调度 C编译程序以该源程序做为输入进行编译，产生出以“.OBJ”为扩展名的目标程序； 用户经键盘在编辑程序支持下建立以“.C”为扩展名的源程序； 作业步作业步：为了获得结果，一个作业需要经过若干个加工步

38、骤。称每一个加工步骤为一个作业步。 作业作业：指用户要求计算机系统做的一个计算问题或一次事务处理的完整过程。 2.5.2 作业与作业管理作业与作业管理. 一个作业的各作业步之间是有联系的。通常，上一个作业步的输出是下一个作业步的输入。下一个作业步能否顺利执行，取决于上一个作业步的结果是否正确。 .典型的C语言作业处理过程 (1)(2)(3) 连接装配程序以目标程序、系统库函数、包含文件等为输入，产生一个以“.EXE”为扩展名的可执行文件。这个文件才是真正可以投入运行的程序。 LOGO41处理机管理第二章正文2.4 作业调度 作业控制块作业控制块：把一个作业提交给系统时，系统为它开辟一个专用的存

39、储区，随时记录作业的信息。该存储区称为作业的作业控制块JCB。 . 后备作业与后备作业队列后备作业与后备作业队列：被系统接纳的作业，在未投入运行前，称后备作业。它们存放在辅存，由JCB连接在一起，形成后备作业队列。后备作业队列里的作业，不参与对处理机的竞争，但系统从它们里面挑选对象去参与对处理机的竞争。 . 作业调度：作业调度：按某种规则从后备作业队列里挑选作业进入内存，参与对处理机的竞争，称为作业调度作业调度，它由作业调度程序作业调度程序完成。所 采用的规则，称作业调度算法作业调度算法。 用户名外设类型与需求数量作业提交时间作业运行时间（估计）作业控制块(JCB)指针其他作业类别内存需求量作

40、业名作业现行状态作业优先数作业控制块JCB内容 作业调度的主要任务是：按照某种调度算法，从后备作业中挑选一批合理搭配的作业进入运动状态；同时为选中的作业分配内存和外部设备资源，为其建立相关的进程，当作业执行结束进入完成状态时，做好释放资源等善后工作。.LOGO42处理机管理第二章正文2.4 作业调度. 作业的生命期作业的生命期：从作业提交给系统，到作业运行完毕被撤消，是一个作业的生命期。在这期间，作业随着自己的推进，及环境变化，状态也在不断变化。 作业的四个基本状态(1) 提交状态(2) 后备状态(3) 运行状态(4) 完成状态提交状态提交状态 作业从输入设备进入输入井及作业进入内存储器时。

41、后备状态后备状态 操作员把作业输入到直接存取的后援存取器后，为进入系统的作业建立作业控制块， 并把它加入到后备作业队列中，等候作业调度程序调度。这一过程也称为作业注册。 运行状态运行状态 作业被作业调度程序选中，且分配了必要的资源，建立一组相应的进程后，该作业就 进入了运行状态。它分为三种状态：即就绪状态、执行状态、阻塞状态。完成状态完成状态 当作业正常运行结束或因发生错误而终止时，作业进入完成阶段。LOGO43处理机管理第二章正文2.4 作业调度2.5.3 作业的调度算法作业的调度算法作业调度的目标：作业调度的目标：1、响应时间快速2、周转时间或带权周转时间短3、均衡的资源利用率；4、吞吐量

42、大；5、系统反应时间短。评价作业调度算法优劣的性能指标：评价作业调度算法优劣的性能指标：1、作业平均周转时间；2、作业平均带权周转时间主要作业调度算法有：主要作业调度算法有：1、先来先服务法；2、短作业优先算法；3、最高响应比优先算法；作业调度时机：作业调度时机：一般当输入井中有一道作业建立，或内存中的一道作业运动结束时，系统启动统调度工作。LOGO44处理机管理第二章正文2.4 作业调度 在批处理系统中，使用作业的“周转时间周转时间”来描述系统的吞吐能力。假定作业 i 提交给系统的时间为S i，其完成的时间为W i。那么该作业的周转时间Ti是：Ti = W i S i对于一批n个作业而言，它

43、们的“平均周转时间平均周转时间” T 应该是： T=( T1 + T2 + + Tn ) / n.带权周转时间带权周转时间：Wi=Ti/Tr 作业周转时间与作业执行时间之比。Ti：周转时间， Tr ：实际执行时间平均带权周转时间：W= Wi /n n为作业个数。LOGO45处理机管理第二章正文2.4 作业调度 由于是按照1、2、3的顺序同时提交给系统，可假定它们三个到达系统的时间都为0。作业1第1个被作业调度程序选中，投入运行。花24个CPU时间运行完毕。因此其周转时间是：T1=24-0=24；作业2在等待24个CPU时间后被调度并运行。它花费3个CPU时间运行完毕，因此周转时间是：T2=27

44、-0=27；不难算出作业3的周转时间是：T3=30-0=30。于是，这三个作业的平均周转时间为：T= (T1+T2+T3 ) / 3 = (24+27+30) / 3 = 81 / 3 = 27 有3个作业，所需CPU时间如右表所示。按1、2、3的顺序，同时提交给系统，采用先来先服务的作业调度算法。求每个作业的周转时间及它们的平均周转时间。1. 先来先服务作业调度算法先来先服务作业调度算法 基本思想：以作业进入后备作业队列的先后次序，作为作业调度程序挑选作业的依据。即哪个作业在后备作业队列里等待的时间最长，下次调度即是选中者，这当然是以其资源需求能够得到满足为前提的。例：例：作业所需CPU时间

45、1232433解：解：作业1作业2作业32433所谓“甘特图”，即是指能够反映作业调度顺序及占用CPU时间的一种进度图。 LOGO46处理机管理第二章正文2.4 作业调度 右示五个作业，采用FCFS 作业和进程调度算法，可供5个作业 使用的内存空间为100KB，需要时按 序分配。作业进入内存后，不许在内 存中移动。计算每个作业的周转时间和平均周转时间。（忽略系统调度时间，作业都没有输入/输出请求）例例 ：作业所需CPU时间1234510.110.310.510.610.7到达时间所需内存量0.70.50.40.40.215KB70KB50KB20KB10KB解解： .各作业的周转时间装入内存时间完成时间10.110.311.311.310.7开始运行时间周转时间10.811.311.912.311.50.71.01.41.70.810.110.811.511.911.3.作业运行时的内存分配情况作业1(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(a)到10.7时 内存情形空闲(15KB)作业2(70KB)作业5(10KB)空闲(5KB)(b)到10.8作业1 完成时内存情形作业3(50KB)作业4(20KB)作业5(10KB)空闲(5KB)(c) 到11.3作业2 完成时内存情形空闲(15KB) 这批作业的调度顺序是： 12534， 系