操作系统_第3章辅导与自测(8页).doc

《操作系统_第3章辅导与自测(8页).doc》由会员分享，可在线阅读，更多相关《操作系统_第3章辅导与自测(8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-第3章 处理机调度 辅导与自测3.1 本章知识点调度是操作系统的基本功能，几乎所有的计算机资源在使用之前都要经过调度。CPU作为计算机最主要的资源，处理机调度的目的就是分配CPU。CPU是操作系统中最核心的调度，其调度策略决定了操作系统的类型，其调度算法优劣直接影响整个系统的性能。所以，调度问题是操作系统设计的一个中心问题。本章的主要知识点为：（1）调度级别一般来说，作业从进入系统到最后完成，可能要经历三级调度：高级调度、中级调度和低级调度，这是按调度层次进行分类的。其中，高级调度又称为作业调度，低级调度又称为进程调度。作业调度是在输入的一批作业中选择有权竞争CPU的作业。资源的分配策略（特

2、别是内存管理）对作业调度有很大影响。为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。进程调度是从就绪进程队列中选择一个进程，并把CPU分配给它。进程调度是这三级调度中是必不可少的。这三级调度中，要重点理解作业调度和进程调度形成的两级调度模型，如下图所示。通过理解这个图，理解作业的4种状态：提交、后备、执行和完成，作业调度的功能，进程调度的功能，进程调度的时机，以及这两级调度如何协调工作完成了处理机调度。（2）常用调度算法针对不同的系统目标，会采取不同的调度策略。确定调度策略是件复杂的工作，往往要兼顾多种因素的影响。CP

3、U利用率、吞吐量、周转时间、就绪等待时间和响应时间等是通常评价系统性能时都要考虑的几个指标。教材中主要介绍了3种调度算法，分别是先来先服务法、时间片轮转法和优先级法。先来先服务法（FCFS）是最简单的调度算法，它的实现思想就是“排队买票”的办法。按作业（或进程）到来的先后次序进行调度，即先来的先得到执行。时间片轮转法（RR）的设计实现思想是系统把所有就绪进程按先入先出的原则排成一个队列。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。当进程用完分给它的时间片后，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首

4、进程。轮转法适用于分时系统。其主要问题是时间片如何选择：时间片太长了，就成为FCFS调度；时间片太短了，频繁调度，开销太大。优先级调度算法的实现思想：是从就绪队列中选出优先级最高的进程，把CPU分给它使用。又分为非抢占式优先级法和抢占式优先级法。前者是：当前占用CPU的进程一直运行下去，直到完成任务或者因等待某事件而主动让出CPU时，系统才让另一个优先级高的进程占用CPU。后者是：当前进程在运行过程中，一旦有另一个优先级更高的进程出现在就绪队列中，进程调度程序就停止当前进程的运行，强行将CPU分给那个进程。其它常用的调度算法还有：短作业优先法、最短剩余时间优先法、多级队列法、多级反馈队列法。（

5、3）中断处理并发是现代计算机系统的重要特性，它允许多个进程同时在系统中活动。而实施并发的基础是由硬件和软件结合而成的中断机制。中断是现代计算机系统中的重要概念之一，它是指CPU对系统发生的某个事件做出的处理过程。按功能划分，中断一般分为I/O中断、机器故障中断、外部中断、程序性中断、访管中断。在中断响应和处理过程中，硬件对中断请求做出响应：中止当前程序的执行，保存断点信息，转到相应的处理程序。软件对中断进行相应的处理：保存现场，分析原因，处理中断，中断返回。各中断处理程序是操作系统的重要组成部分。对中断的处理是在核心态下进行的。Linux系统提供给用户的最重要的系统程序是shell命令语言解释

6、程序。其基本功能是解释并执行用户输入的各种命令，实现用户与Linux核心的接口。shell解释程序的工作过程基本上是读入命令行、分析命令行和构成命令树，创建子进程来执行命令树等步骤。（4）Linux系统的进程调度Linux系统的进程调度机制主要涉及调度方式、调度策略、调度时机和调度算法。Linux系统对进程采用两级调度：中级调度（对换进程，解决内存分配）和低级调度（解决CPU分配）。进程调度基本上采用抢占式优先级算法。而针对不同类型的进程又采用相应的调度策略。本章还介绍了Linux系统中常用的调度命令，如nohup、at、batch、jobs、fg、bg。 3.2典型例题解析【例1】为了使系统

7、中各部分资源得到均衡使用，就必须选择对资源需求不同的作业进行合理搭配，这项工作是由（ ）完成的。 A作业调度 B中级调度 C进程调度 D内存调度答案 A分析 首先，要了解操作系统处理机调度的级别，即作业从进入系统到最后完成，至少要经历两级调度：高级调度和低级调度。为了使内存中同时存放的进程数目不至于太多，有时需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。各个级别调度的含义，所解决的问题，即功能是什么。只有清晰地掌握了这些基本概念，才能做好选择。本题说的是作业的合理搭配以达到系统资源的均衡利用，显然是作业调度的工作。而中级调度解决的是内存分配问题，进程调度解决的是哪

8、一个就绪进程占有CPU的问题。因此答案选A。【例2】作业调度程序从处于（ ）状态的队列中选取适当的作业调入主存运行。A执行 B提交 C完成 D后备答案 D分析 解答此题需要了解作业的状态以及转换。一个作业从进入系统到运行结束要经历四种状态：提交状态、后备状态、执行状态和完成状态。（1）提交状态：用户的一个作业提交给系统时所处的状态，如用户通过键盘向机器输入作业。处于提交状态的作业，其信息正在进入系统。（2）后备状态：用户作业经输入设备（如读卡机）输入进外存（磁盘）中存放，等待进入内存时所处的状态。此时，系统将为该作业建立一个作业控制块JCB，并把作业插入到后备作业队列中等待调度运行。（3）执行

9、状态：作业调度程序按照一定的作业调度算法从后备作业队列中选中一个作业，为它分配必要的资源，建立一组相应的进程后，这个作业就由后备状态转变为执行状态。需要指出的是，处于执行状态的作业在系统中并不一定真正占有处理机，作业能否真正在处理机上运行由进程调度来控制。（4）完成状态：作业完成了处理任务，输出结果形成报告，系统将作业控制块JCB从当前作业队列中删除，并回收分配给作业的全部资源，准备退出系统时的作业状态。四种作业状态的转换见下图： 进程调度 作业调度 作业调度提交后备完成运行就绪阻塞参考上图，有这样一个判断题：作业调度程序选中一个作业后，与该作业相关的进程即占有CPU运行。答案是错误的，因为执

10、行状态的作业能否真正在CPU上运行由进程调度来控制，这时候的进程至少有三种基本状态，不能保证一定是占有CPU的运行状态。【例3】在批处理系统中，周转时间是（ ）。 A作业运行时间 B作业等待时间和运行时间之和 C作业的相对等待时间 D作业被调度进入主存到运行完毕的时间答案 B分析 作业的周转时间作业完成时间作业提交时间。周转时间是用于作业等待进入内存、进程在就绪队列中等待、进程在CPU上运行和完成I/O操作所花费时间的总和。因此，周转时间是作业等待时间和运行时间之和。答案D是不对的，因为作业提交后进入作业后备状态，此时作业是在外存，这个时间也要计入作业的周转时间。【例4】在作业调度中，若采用优

11、先级调度算法，为了尽可能使CPU和外部设备并行工作，有如下三个作业：J1以计算为主，J2以输入输出为主，J3计算和输入输出兼顾，则它们的优先级从高到低的排列顺序是（ ）。AJ1，J2，J3 BJ2，J3，J1 CJ3，J2，J1 DJ2，J1，J3答案 C分析 本试题将作业分为：I/O繁忙的作业、CPU繁忙的作业、I/O与CPU均衡的作业三种类型，由系统或操作员根据作业类型指定优先级。为了尽可能使CPU和外部设备并行工作，那么I/O繁忙的作业和CPU繁忙的作业都不能指定为最高的优先级，因为这两类作业都无法均衡地使用资源（CPU或者I/O设备）。对于这两类作业，应指定I/O繁忙的作业优先级高于C

12、PU繁忙的作业，这样做可以提高CPU的利用率，增加系统的吞吐量。因此，这三类作业优先级从高到低的排列顺序是：I/O与CPU均衡的作业、I/O繁忙的作业、CPU繁忙的作业。【例5】下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号提交时间运行时间1230.00.41.08.04.01.0分析 解此题关键是要清楚系统中各道作业随时间的推进情况。我们用一个作业执行时间图来表示作业的执行情况，帮助我们理解此题。采用先来先服务调度策略，其作业执行时间图如下： 作业作业3作业2作业1

13、0 0.4 1.0 8.0 12.0 13.0 时间 作业提交时间 各作业陆续完成时间采用短作业优先调度策略，其作业执行时间图如下： 作业作业3作业2作业1 0 0.4 1.0 8.0 9.0 13.0 时间 作业提交时间 各作业陆续完成时间 另外，作业i的周转时间Ti作业完成时间作业提交时间 系统中n个作业的平均周转时间，其中Ti为作业i的周转时间。解：采用先来先服务调度策略，则调度次序为l、2、3。作业号提交时间 运行时间 开始时间 完成时间周转时间1 0.08.00.08.0 8.02 0.44.08.0 12.0 11.63 1.01.0 12.0 13.0 12.0平均周转时间T（8

14、11.612）/310.53采用短作业优先调度策略，则调度次序为l、3、2。作业号提交时间运行时间开始时间完成时间周转时间1 0.0 8.0 0.0 8.0 8.03 1.0 1.08.09.08.02 0.4 4.0 9.0 13.0 12.6平均周转时间T（8812.6）/39.53【例6】今有三个批处理作业。第一个作业10:00到达，需要执行2小时；第二个作业在10:10到达，需要执行1小时；第三个作业在10:25到达，需要执行25分钟。分别采取如下两种作业调度算法：调度算法1：作业号到达时间开始执行时间执行结束时间12310:0010:1010:2510:0012:0013:0012:

15、0013:0013:25调度算法2：作业号到达时间开始执行时间执行结束时间12310:0010:1010:2511:5010:5010:2513:5011:5010;50 （1）计算各调度算法下的作业平均周转时间。 （2）调度算法1是什么作业调度算法？分析 作业的周转时间作业完成时间作业提交时间。 以调度算法1的作业2为例，其周转时间=作业完成时间13:00作业提交时间10:10，得到结果为2小时50分钟，转换为小时为2.83小时。转换的目的是为了方便计算平均周转时间。解：（1）采用调度算法1时： 作业1的周转时间为2小时；作业2的周转时间为2.83小时；作业3的周转时间为3小时；平均周转时间

16、为：（22.833）32.61小时。 采用调度算法2时： 作业1的周转时间为3.83小时；作业2的周转时间为1.67小时；作业3的周转时间为0.42小时；平均周转时间为：（3.83l.670.42）3l.97小时。（2）调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。【例7】一个进程在执行过程中可以被中断事件打断，当相应的中断处理完成后，就一定恢复该进程被中断时的现场，使它继续执行。（ ） 答案 （）分析 中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，如被中断进程的优先级最高，则返回断点继续

17、执行被“打断”的程序。本题开头的叙述是正确的，即“一个进程在执行过程中可以被中断事件打断”，但是后面说“一定恢复该进程被中断时的现场”，以及“继续执行”就不正确了，因此，系统中进程的并发执行情况非常复杂，中断后的进程能否继续执行，要看那时的具体情况，可能会继续执行，也可能处于就绪队列中无法立即继续执行。【例8】在UNIX/Linux系统中，执行到trap指令时，CPU的状态就从核心态变为用户态。（ ） 答案 （）分析 为了对操作系统程序（特别是其内核部分）进行保护，防止受到用户程序的损坏，系统提供了不同的处理机执行状态，通常分为核心态和用户态两种。当操作系统程序执行时，处理机处于核心态，它有较

18、高的特权，可以执行一切指令（包括一般用户程序中不能使用的特权指令）。用户程序在用户态下执行。它的权限较低，只能执行指令集中的非特权指令。用户程序要想得到操作系统的服务，必须使用系统调用。在UNIX/Linux系统中，系统调用像C语言的普通函数调用那样出现在程序中。但是，一般的函数调用序列并不能把进程的运行模式从用户态变为核心态，而系统调用却可以做到这一点，即从用户空间转入系统空间。trap指令是实现系统调用的汇编代码，trap指令有这样一种性质：当CPU执行到trap指令时，CPU的状态就从用户态变为核心态。本题正好说反了，因此是错误的。【例9】UNIX/Linux系统中的shell是负责（

19、）的模块。A解释并执行来自终端的命令 B解释并执行来自终端的内部命令C解释并执行来自终端的外部命令 D进行系统调用答案 A分析 shell命令语言解释程序是UNIX/Linux系统提供给用户的最重要的系统程序。它不属于内核部分，而是在核心之外以用户态方式运行。其基本功能是解释并执行用户输入的各种命令，实现用户与Linux核心的接口。shell命令分为内部命令和外部命令两种，内部命令是最简单最常用的命令，在shell启动时进入内存，Linux外部命令是一个独立的可执行程序。3.3练习题一、选择题（选择一个正确答案的代码填入括号中）1. 作业生存期共经历4个状态，它们是提交、后备、（ ）和完成。

20、A等待 B就绪 C开始 D执行2. 作业调度是（ ）。A从输入井中选取作业进入主存 B从读卡机选取作业进入输入井C从主存中选取作业进程占有CPU D从等待设备的队列中选取一个作业进程3. 在操作系统中，JCB是指（ ）。A文件控制块 B进程控制块 C作业控制块 D程序控制块4. 作业调度选择一个作业装入主存后，该作业能否占用处理器必须由（ ）来决定。A设备管理 B作业控制 C进程调度 D驱动调度5. 进程调度根据一定的调度算法，从（ ）队列中挑选出合适的进程。A阻塞 B就绪 C运行 D等待6. 在操作系统中，作业处于（ ）时，已处于进程的管理之下。A后备状态 B阻塞状态 C执行状态 D完成状态

21、7. 作业调度的关键在于（ ）。A选择恰当的进程管理程序 B选择恰当的作业调度算法C用户作业准备充分 D有一个较好的操作环境8. 从系统的角度出发，希望批处理控制方式下进入输入井的作业（ ）尽可能小。 A等待装入主存时间 B周转时间C执行时间 D平均周转时间9. 设某作业进入输入井的时间为S，开始运行的时间为R，得到计算结果的时间为E，则该作业的周转时间T为（ ）。AT=ES BT=E(S+R) CT=(S+R)+ E DT=ER10. 现有3个作业同时到达，每个作业的计算时间都是1小时，它们在一台CPU上按单道方式运行，则平均周转时间为（ ）。A1小时 B2小时C3小时 D6小时11. 按照

22、作业到达的先后次序调度作业，排队等待时间最长的作业被优先调度，这是指（ ）调度算法。A先来先服务法 B短作业优先法C时间片轮转法 D优先级法12. 为了使计算机在运行过程中能及时处理内部和外部发生的各种突发性事件，现代操作系统采用了（ ）机制。A查询 B中断 C调度 D进程13. 在操作系统中，引起中断的事件称为（ ）。A中断源 B中断请求C断点 D系统调用14. 当硬件中断装置发现有事件发生，就会中断正在占用CPU的程序执行，让操作系统的（ ）占用CPU。A系统调用程序 B中断处理程序C作业管理程序 D文件管理程序15. 下列中断类型中，属于自愿性中断事件的是（ ）。A硬件故障中断 B程序中

23、断C访管中断 D外部中断16. 下列中断中，可能要人工介入的中断是（ ）。A程序中断 B时钟中断C输入输出中断 D硬件故障中断17. 系统调用的目的是（ ）。A请求系统服务 B终止系统服务C申请系统资源 D释放系统资源18. 用户要在程序一级获得系统帮助，必须通过（ ）。A进程调度 B作业调度 C键盘命令 D系统调用19. 系统调用是由操作系统提供的内部调用，它（ ）。A直接通过键盘交互方式使用 B只能通过用户程序间接使用C是命令接口中的命令 D与系统的命令一样20. CPU状态分为核心态和用户态，从用户态转换到核心态的途径是（ ）。A运行进程修改程序状态字 B中断屏蔽C系统调用 D进程调度程

24、序二、判断题（正确的划，错误的划。）1. 处理机调度可分为三级：高级、中级和低级。在所有的系统中，都必须具备这三级调度。（ ）2. 作业调度选中一个作业后，与该作业相关的进程即占有CPU运行。（ ）3. 吞吐量是指单位时间内CPU完成作业的数量。（ ）4. 确定作业调度算法时应主要系统资源的均衡使用，使I/O繁忙作业和CPU繁忙作业搭配运行。（ ）5. 平均周转时间和周转时间与选用的调度算法有关。（ ）6. 通常，为了提高效率，赋予需要大量计算的作业较高优先级，赋予需要大量输入/输出的作业较低的优先级。（ ）7. 优先级作业调度算法是指为系统中的每一个作业确定一个优先级，进行作业调度时总是优先

25、选择优先级高的作业进入主存运行。（ ）8. 计算机对中断的处理是在用户态下进行的。（ ）9. 中断处理一般分为中断响应和中断处理两个步骤，前者由软件实施，后者由硬件实施。（ ）10. 系统调用的调用过程是通过用户程序，运行在用户态，而被调用的过程是运行在核心态下。（ ）三、简答题四、应用题请同学们解答参考教材104页的课后习题。请大家自己完成参考答案：一、DACCB CBDAB ABABC DADBC二、3，4，5，7，10是正确的。1. （）。处理机的三级调度中只有进程调度是必不可少的。2. （）。作业调度选中的作业能否占有CPU由进程调度决定，不一定即可执行。6. （）。正好说反了，应赋予需要大量计算的作业较低优先级，赋予需要大量输入/输出的作业较高的优先级。8. （）。计算机对中断的处理是在核心态下进行的。9. （）。中断响应由硬件实施，中断处理由软件实施。三和四、见本章教材习题解答。-第 8 页-