《操作系统》复习大纲及习题

1、计算机操作系统复习要点及习题第一章 操作系统概述1、操作系统的定义及特征2、操作系统分类：批处理、分时、实时；三种系统的特点；3、理解并发与并行第二章 进程管理1、进程的概念2、进程的结构、三种基本状态及状态之间的转换和转换条件3、进程与程序的联系与差别4、进程的并发执行使进程失去顺序性，可能产生与时间有关的错误。5、共享变量、临界区、临界资源的概念6、进程互斥的概念7、重点：信号量机制定义整形变量如S表示信号量，S的初值、S>0表示有S个资源可用、S<0则| S |表示S等待队列中的进程个数、S=0表示无资源可用的含义。P(S)、V(S)操作的含义。使用信号量机制实现进程互斥、同

2、步问题。P(S) 表示申请一个资源、V(S) 表示释放一个资源。P.V操作必须成对出现，有一个P操作就一定有一个V操作。当为互斥操作时，它们同处于同一进程；当为同步操作时，则不在同一进程中出现。8、生产者-消费者问题第三章处理机调度与死锁1、重点：处理机调度算法（必须有完整的计算过程，只有结果无过程不能给满分）（1）、先到先服务算法（FIFO）（2）、短作业优先算法（SJF）给定一作业，假定它们同时到达，并且在一台处理机上按单道方式执行，则短作业优先调度算法平均周转时间为最短。（3）、高响应比优先调度算法（4）、最高优先数算法（5）、循环轮转/时间片轮转算法(RR)2、死锁的概念一组进程中的每

3、一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。3、死锁四个必要条件：资源独占、保持申请、不可剥夺、循环等待4、死锁四种处理方法：死锁预防、死锁避免、死锁检测、死锁恢复5、死锁预防的两种方法：预先分配策略、有序分配策略6、死锁避免：进程提出资源请求，系统在分配之前进行安全性检测，若使进程进入不安全状态，则拒绝分配。重点：银行家算法（必须有完整的计算过程，只有结果无过程不能给满分）6、死锁恢复四种方式：重新启动、终止进程、剥夺资源、进程回退第四章内存管理1、分区分配策略最先适应算法、最佳适应算法、最坏适应算法。2、分页式存储管理方式：作业（逻辑

4、地址）分页、内存（物理地址）分块，一页大小等于一块。页表由系统设置，常驻内存，用页表实现从页号到物理块号的地址映射。重点：分页式存储管理地址映射过程。将逻辑地址转换为（页号，页内地址）两部分，然后根据页号查页表，将实际的物理块号和页内地址拼接成实际的物理地址。3、分段式存储管理方式：用户作业（逻辑地址）分段。系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段。4、段页式存储管理的基本思想：用分段方法来分配和管理虚存，分页方法来分配和管理实存，在段页式管理系统中，每一段不再占有连续的实存空间，而被划分成若干个页面。第五章虚拟存储虚拟存储系统基于程序运行的局部性原理，

5、借助于外存空间，从而允许一个进程在其运行过程中部分地装 内存的技术。重点:OPT算法、FIFO算法、LRU算法（必须有完整的计算过程，只有结果无过程不能给满分） 1.采用段式存储管理的系统中,若地址用24位表示,其中8位表示段号,则允许每段的最大长度是（ ）。 A.2 B.2 C.2 D.2分析：段长度为除了表示段号之外的长度：2=22.在操作系统中，对信号量S的signal（P）原语操作定义中，使进程进入相应阻塞队列等待的条件是 （ ） A. S>0 B. S=0 C. S<0 D. S>=0分析：信号量S=0，说明系统资源刚好够用，不会阻塞进程，信号量S<0,阻塞进

6、程，其绝对值是等待的进程数量，信号量S>0,表示可用的资源数量3.系统中有4个并发进程，都需要某类资源3个。试问该类资源最少为（ ）个时，不会因竞争该资源而发生死锁。 A. 9B. 10C. 11D. 12【分析】：设资源最少为X个，则需满足4*（3-1）+1 >=X,这个公式表明，这4个进程至少有一个有3个资源，就不会发送死锁, X<=9.4.有三个进程P1,P2,P3共享同一个程序段，而每次最多允许两个进程进入该程序段，则信号量S的初值为（ ）。 A. 0 B. 1 C. 2 D. 3【分析】：S的初值即为资源的个数。最多允许两个进程进入该程序段，说明对应的资源只能有两个

7、。5.设与某资源关联的信号量(K)初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M、N分别是（ ）。 A 0、1 B1、0 C1、2 D2、0【分析】：信号量(K)初值为3，当前值为1，说明已经有两个资源被占用，还剩余一个资源（M=1）。资源还有剩余，M>0,说明没有任何资源在等待（N=0）。6.当采用分页式虚拟存储管理时，如果在作业执行过程中需访问的页面不在主存储器中，则硬件将发出一个_缺页_中断。7.在缺页处理过程中，操作系统执行的操作可能是（ ）。 修改页表 磁盘IO 分配页框A仅、 B仅 C仅 D 、和 8.某系统正在执行三个进程P1、P2和P3，各

8、进程的计算(CPU)时间和IO时间比例如下表所示。进程计算时间IO时间Pl9010P25050P31585为提高系统资源利用率，合理的进程优先级设置应为（ ）。 AP1>P2>P3 BP3>P2>P1 CP2>P1=P3 DP1>P2=P3【分析】：为了合理设置优先级，应该将进程的CPU时间和I/O时间综合考虑，对于CPU占据时间（即计算时间）较少的进程，应该给予更高的优先级。大题说明1. 关于PV操作的大题可以参考一下：哥哥弟弟取钱和爸爸妈妈弟弟姐姐取放苹果和橘子的案例2. 银行家算法的例题（类似必考）3. LUR,FIFO和OPT页面调度必考其它说明关注

9、课件上的例题（特别是考研题，部分题目是原题）操作系统最重要的两个目标是（）A.开放性和有效性B可扩充性和方便性C.有效性和方便性D.方便性和开放性答案：C批处理系统的主要优点是解决了作业间的自动转换问题，提高了CPU的利用率，所以系统吞吐量大，资源利用率高主要缺点就是交互性差，一旦作业提交，其中间过程就很难控制。批处理系统的主要缺点是：（清华大学1996年试题）ACPU利用率低。 B不能并发执行。C缺少交互性。 D以上都不是。【解答】选择C。一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚到达5ms，它们的计算和I/O操作顺序如下：P1：计算60ms，I/O 80ms，计算20msP2

10、：计算120ms，I/O 40ms，计算40ms若不考虑调度和切换时间，则完成两个作业所需要的最短时间是（ ）A. 240ms B. 260msC. 340ms D. 360ms多道批处理系统的特征：(1)多道性：内存中有多道程序，可并发执行(2)无序性：完成时间与进入内存先后无关(3)调度性：作业从提交到完成经两次调度作业调度：外存->内存（选多个）进程调度：分配处理机（选1个）填空题：1.多道运行的特征之一就是宏观并行，它的含义是（ ）（2000年，华中科技大学）2.多道程序设计的特点是多道、（ ）和（ ）（2000年西安电子科技大学）答案：1.计算机内存中同时存放几道相互独立的程序

11、 2. 宏观上并行，微观上串行多道程序优点：(1)资源利用率高(2)系统吞吐量大原因(1)资源忙 (2)完成或运行不下去时才切换缺点： (1)无交互能力-修改和调试极不方便 (2)作业平均周转时间较长分时操作系统（Time Sharing Operating System）是一种联机的多用户交互式的操作系统。一般采用时间片轮转的方式，使一台计算机为多个终端服务。对每个用户能保证足够快的响应时间，并提供交互会话能力。 。共享：是指系统中的资源可供内存中多个并发执行的进程共同使用。互斥共享方式同时访问方式互斥共享方式互斥就是排他性临界资源（独占资源）：在一段时间内只允许一个进程访问的资源（如打印机

12、等硬件；栈、变量、表格等）同时访问方式宏观上在一段时间内允许多个进程“同时”访问某些资源微观上“轮流”（交替访问）处理机、内存、磁盘、可重入代码在程序中在试图读取某个磁盘上的第100个逻辑块，使用操作系统提供的（ ）接口A. 系统调用 B.图形用户接口C. 原语 D.键盘命令为什么要区分处理机的态?答：操作系统是计算机系统的最重要的系统软件，为了能正确的进行管理和控制，其本身是不能被破坏的。为此系统应能建立一个保护环境，采用的办法就是分处理机的状态。在计算机系统中，为什么要区分管态与目态？（西安电子科技大学1999年试题）【解答】操作系统是计算机系统中最重要的系统软件，为了能正确地进行管理和控

13、制，其本身是不能被破坏的。因此，系统采用了区分处理机状态的办法，为操作系统程序建立一个保护环境。这样，用户程序只能在管态下运行，只能执行非特权指令，只能访问自己的存储区，从而保护了操作系统程序的正常运行。下列选项中，会导致用户进程从用户态切换到内核态的操作是（ ）.整数除以零 .sin()函数调用 . read()系统调用仅 、 仅、 仅 、 、 、操作系统定义：一个特殊的程序设计目标：方便+有效利用计算机资源3个作用：接口+资源管理者+计算资源的抽象3种基本类型：多道+分时+实时操作系统的4个特征：并发+共享+虚拟+异步程序顺序执行的特顺序性封闭性可再现性给程序的编制、调试带来很大方便缺点是

14、计算机系统效率不高。并发执行时的特征间断性“停停走走”失去封闭性原因：多个程序共享资源不可再现性采用并发程序设计的目的是：充分发挥硬件的并行性，消除处理器和I/O 设备的互等现象，提高系统效率。机器部件能并行工作仅仅有了提高效率的可能性，而机器部件并行工作的实现还需要软件技术去利用和发挥，这种软件技术就是并发程序设计。PCB中的信息进程标识符：唯一的标识一个进程 内部标识（OS）外部标识（由创建者提供，由字母数字组成）处理机状态：由CPU的各种寄存器中的内容组成。通用R指令计数器PC 程序状态字PSW用户栈指针进程调度信息：进程状态进程优先级其它信息等待事件（阻塞原因）进程控制信息：程序和数据

15、的地址同步和通信机制资源清单链接指针就绪态 得了除CPU以外的所有必要资源 （万事具备，只欠CPU）执行态已获得处理机，程序正在被执行 （进程的终极理想）阻塞态进程在执行过程中，因等待某事件发生而暂时无法继续执行的暂停状态 （所需资源不足，等待）如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？解答：在单处理机系统中，处于运行状态的进程最多为1个，最少为0个；处于就绪进程最多为N-1个，最少为0个；处于阻塞的进程最多为N个，最少为0个。现在的操作系统对进程的定义不尽相同，有的还引入挂起(suspend)状态。试简述挂起状态的意义（浙江大学

16、2000年 5分）参考答案：由于进程的不断创建，系统资源已不能满足进程运行的要求，就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，以达到起到平衡系统操作负荷的目的。 进程控制包括： 进程创建、 进程撤消、 进程阻塞、 进程唤醒。 这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用给用户提供进程控制的功能。教材上叫原语（一种特殊的系统调用）。 下列选项中，导致创建新进程的操作是（ ）：.用户登录.设备分配.启动程序运行：设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程阻塞与唤醒要匹配使用，以免造成“永久阻塞”进程互斥关

17、系是一种特殊的进程同步关系，即逐次使用互斥共享资源。一次仅允许一个进程使用的资源称为临界资源。临界资源：物理设备，如输入机、打印机、磁带机等都具有这种性质。 软件资源，如公用变量、数据、表格、队列等也都具有这一特点。临界区：在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称为临界区或临界段。进入临界区的准则:空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区。忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待。有限等待。对任何要求访问临界资源的进程，应保证在有限的时间内能进入自己的临

18、界区，以免陷入“死等”状态。让权等待。当进程不能进入自己的临界区，应立即放弃占用CPU，以使其他进程有机会得到CPU的使用权，以免陷入“忙等”。练习题：兄弟俩共用一个账户，哥每次限存或取10元，弟每次限取或取5元存钱与取钱的进程如左所示，由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在哥哥第三次存钱时，弟弟在取钱1.请问最后的帐号上amount可能有多少钱？2.如何用p，v原语实现两并发进程的互斥操作？ 信号量小结信号量必须置初值，且只能置一次初值。初值可为非负整数信号量分类： 互斥的信号量：它的P、V在同一个进程中 同步的信号量：它的P、V在不同的进程中信号量的物

19、理意义： S>0：S表示可用资源的个数 S=0：S表示无资源，无等待进程 S<0：|S|表示等待队列中进程的个数P和V的位置放置的小结：对于互斥资源：P、V操作在同一个进程中（强调的是自私）对于共享资源的同步： P、V操作在不同进程中（强调的是你中有我，我中有你的协作关系）P和V信号量的初始化：必须置一次初值，且只能置一次初值初值必须>=0,不能为负值第三章处理机调度与死锁1、重点：处理机调度算法（必须有完整的计算过程，只有结果无过程不能给满分）（1）、先到先服务算法（FIFO）（2）、短作业优先算法（SJF）给定一作业，假定它们同时到达，并且在一台处理机上按单道方式执行，则

20、短作业优先调度算法平均周转时间为最短。（3）、高响应比优先调度算法（4）、最高优先数算法（5）、循环轮转/时间片轮转算法(RR)2、死锁的概念一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。3、死锁四个必要条件：资源独占、保持申请、不可剥夺、循环等待4、死锁四种处理方法：死锁预防、死锁避免、死锁检测、死锁恢复5、死锁预防的两种方法：预先分配策略、有序分配策略6、死锁避免：进程提出资源请求，系统在分配之前进行安全性检测，若使进程进入不安全状态，则拒绝分配。重点：银行家算法（必须有完整的计算过程，只有结果无过程不能给满分）6、死锁恢

21、复四种方式：重新启动、终止进程、剥夺资源、进程回退非抢占方式：一旦进程获得处理机，则一直执行，直到该进程完成或被阻塞此方式下，可能引起进程调度的因素：（1）正在执行的进程执行完毕，或因发生某事件不能再继续执行（2）执行中的进程因提出I/O请求而暂停执行（3）在进程通信或同步过程中执行了某原语，P操作等优点：简单、系统开销小，适合大多数批处理系统缺点：无法满足紧急任务的需要，不适合实时系统抢占方式：允许调度程序根据某原则，暂停正在执行的进程，将处理机重新分配抢占原则：优先权原则 就绪的高优先权进程有权抢占低优先权进程的CPU短作业优先原则 就绪的短作业(进程)有权抢占长作业(进程)的CPU时间片

22、原则 一个时间片用完后，系统重新进行进程调度选择调度方式和算法的选择准则面向用户的准则（1）周转时间短评价批处理系统 周转时间：是指从作业被提交系统开始，到作业完成为止的这段时间间隔。 响应时间快评价分时系统 响应时间：从用户通过键盘提交一个请求开始直至系统首次产生响应为止。 包括三部分时间：1）从键盘输入的请求信息传送到处理机的时间2）处理时间3）响应信息回送终端的时间（3）截止时间保证评价实时系统 截止时间：任务必须开始执行的最迟时间，或必须完成的最迟时间。（4） 优先权准则三种系统中皆适用调度算法的目的所在是从就绪队列中选择最适宜的就绪进程来执行。通常采用平均周转时间和带权平均周转时间作

23、业的周转时间： ti = tci-tsi ti:作业周转时间 tci：作业完成时间 tsi: 作业提交时间周转时间包括等待时间和运行时间 设有4个作业同时到达，每个作业的执行时间均为2个小时，它们在一台处理机上按单道方式执行，则平均周转时间为（ ）A 1小时， B 5小时C 2.5小时 D 8小时答案B（平均作业周转时间=（2+（2+2）+ （2+2+2）+ （2+2+2+2）/4=5小时 t i r iw i = = = 1+ 等待+运行 运行等待 运行先来先服务:The process to be selected is the process which requests the pro

24、cessor first. 算法容易实现，效率不高，没考虑作业要求服务时间的长短，不利于短作业。FCFS非常“绅士”非强占调度方式Shortest-Job-First (SJF):短作业优先每次总是从就绪队列中选择一个运行时间最小的作业调入内存.该算法易于实现，效率不高，主要弱点是忽视了作业等待时间,会出现饥饿现象。某系统采用短作业优先的调度策略，现有作业序列：作业1（提交时间：8:00,运行时间1.50），作业2（提交时间：8:30,运行时间0.80）作业3（提交时间：9:00,运行时间0.10），作业4（提交时间：9:30,运行时间0.30），单位：小时，以十进制计。其平均带权周转时间为：

25、（ ）A 4.65 B 3.00C 5.52 D 12.23答案B填空题：在作业调度算法中，（ ）调度算法的调度性能要好些答案：短作业优先（SJF）FCFS：只考虑作业的等待时间(谁先来？)，而忽视了作业的运行时间，亏了短作业。SJF:只考虑了作业的运行时间（谁时短？），而忽视了作业的等待时间，亏了长作业。响应比高者优先调度算法：一种拆衷的算法高响应比优先调度算法(HRRN)为每个进程引入动态优先权，随着等待时间增加优先权提高。 等待时间 + 要求服务时间优先权 = - 要求服务时间 等待时间 + 要求服务时间 响应时间 响应比(Rp) = - = - 要求服务时间 要求服务时间性能评价：周转

26、时间 = 完成时间 到达时间带权周转时间 = 周转时间 / 服务（运行）时间存储保护区别：1、寄存器的设置不同；2、判别式中用的判别条件不同上下界寄存器保护法用的是物理地址基址、限长寄存器保护法用的是程序的逻辑地址判别式：下界寄存器 物理地址 上界寄存器例：有一程序装入内存的首地址是500，末地址是1400，访问内存的逻辑地址是500、345、1000。 限长寄存器：900=1400-500 1、 0 500 900 2、 0 345 900 3、 0 1000 900× 下界寄存器：500 上界寄存器：1400 逻辑地址装入内存的首地 物理地址 1、500500 1000 500 1000 1400 2、345500 845 500 845 1400 3、1000500 1500 500 1500 1400×某系统采用基址、限长寄存器防护方法显现存储保护，在这些方法中判断是否越界的判别式是：A 0被访问的物理地址<基址寄存器的内容B 0被访问的物理地址基址寄存器的内容C 0被访问的逻辑地址<限长寄存器的内容D 0被访问的逻辑地址限长寄存器的内容C在可变式分区