西电3版――操作系统习题答案

1、注意：1)“本章要点”部分，用红字标注的不是期末考试出题范围。2)“习题部分”用蓝字标注的是重点习题，期末考试50%的题目是这些习题的原题。红字标注的习题期末考试不考，仅供考研的同学参考。3）大部分习题答案只给出要点，同学们可以自行适当补充，但一定要简明扼要。4）如“本章要点”部分用红字标注的非考试内容，在“习题”部分有相关的重点习题，则对该部分内容只需做该习题即可。-第一章 本章概略叙述了操作系统的历史、功能、体系结构，属于常识性的知识。本章不指定要点，只需完成以下习题即可。 教材习题（P33）1. 设计现代OS的主要目标是什么?答：（P1-2）方便性，有效性，可扩充性和开放性. 2. OS

2、的作用可表现为哪几个方面?答：P2-3a. OS作为用户与计算机硬件系统之间的接口（用户观点）；b. OS作为计算机系统资源的管理者（设计者观点）；c. OS作为扩充机器.（虚拟机观点） 3为什么说OS实现了对计算机资源的抽象？ 答：P3。抽象，可以理解为“简单明了的通用性”。OS隐藏了多变的、琐碎硬件的细节，为用户提供了简单的、基本不随硬件变化而变化的操作方式。4. 试说明推动多道批处理系统形成和发展的主要动力是什么?答: P7-8。提高计算机CPU、内存资源利用率和系统吞吐量的需要。5. 何谓脱机I/O和联机I/O?答：P6。a. 脱机 (Off-Line) I/O是将用户程序和数据在一台

3、外围机的控制下进行I/O，I/O时可以不连接主机。b. 若这种I/O在主机控制下进行则称之为联机I/O。c. 教材第5章还介绍了一种假脱机技术-SPOOLING，是模拟脱机的虚拟设备技术，主要用于虚拟打印机。6. 试说明推动分时系统形成和发展的主要动力是什么?答：P9-P11。计算机最早主要用于科学计算，用于事务处理后（最早用于火车售票），用户需要人机交互和即时响应性，于是出现了分时系统。可以看到需求是技术的推动力。 7. 实现分时系统的关键问题是什么?应如何解决?答:P11-12。a. 关键问题：及时接收，及时处理;b. 对于及时接收，只需在系统中设置一多路卡，多路卡作用是使主机能同时接收用

4、户从各个终端上输入的数据；对于及时处理，应使所有的用户进程都进入内存，在一个的时间段内，能使每个就程都轮换运行一次. 8为什么要引入实时操作系统?答：P11-12。因为工业控制、国防、航空航天等很多领域存在实时信息处理领域的需要. 9 什么是硬实时和软实时任务？请举例说明。答：P12。硬实时对任务的截止时间有严格要求，超过截止时间任务即算失败，比如雷达、导弹控制系统。软实时对任务的截止时间要求较宽松，比如在线视频播放。一般来说，通用操作系统（Windows, linux,UNIT等）不支持硬实时，只支持软实时，有些嵌入式操作系统可以支持硬实时。10 在8位和16位（PC）微机中，占据统治地位的

5、是什么操作系统？答：CP/M, MS DOS等。这两种操作系统是单用户、单任务的，主要用来管理文件和磁盘，现已成历史。 11试列出Windows的5个主要版本，并分别说明较其前一版本有何改进。答：有兴趣的同学可以上网查。Windows有几个历程碑： Windows 3.X，非抢占式多任务,GUI，单用户。 Windows95/98，抢占式多任务,GUI，单用户。 Windows NT，是微软第一个服务器版OS，后来发展成Windows Server系列。 Windows XP，全面支持互联网、娱乐、单用户 。 12试从交互性、及时性、可靠性方面，将分时系统及实时系统进行比较。答：从对时间的要求

6、看，分时系统实际上也是个软实时系统（定时切换），所以在及时性、可靠性方面与软实时差不多，但及时性肯定不如硬实时，对可靠性的要求也不如硬实时高（但硬实时对可靠性要求太高，不易满足）。另外，一般来说，分时系统的交互性要好于实时系统，因为分时系统就是为了交互的需求而出现的。 13 OS具有哪几大特征?它的最基本特征是什么?答：P14-18。a. 并发(Concurrence),共享(Sharing),虚拟(Virtual),异步性(Asynchronism).b. 其中最基本特征是并发和共享. 14 处理机管理具有哪些功能?它们的主要任务是什么?15 内存管理有哪些主要功能?它们的主要任务是什么?1

7、6 设备管理有哪些主要功能?其主要任务是什么?17 文件管理有哪些主要功能?其主要任务是什么?这4道题虽然不是重点，但同学们还应该做一下，对操作系统“四大子系统”的功能有个整体的了解。 18 是什么原因使（多道）操作系统具有异步性特征?答: P17-18，及P36-37都解答了这个问题。这个问题较重要，说明了单道程序和多道程序运行的差别。a. 多道程序执行结果可能是不确定的（比如说对共享变量的访问）,即程序是不可再现的。解决这个问题主要靠进程的互斥。b. 多道程序环境下，虽然任一个程序都有确定的运行顺序（有明确的前驱-后继），但多个程序间的执行顺序以及完成每道程序所需的时间都是不确定的，这取决

8、于CPU的调度策略、进程间的同步关系（比如生产者消费者问题）等因素，这些因素在单道程序环境下都不存在。解决这个问题主要靠进程同步。 19-24题：这几道题的答案都在1.5小节“OS结构设计”。这一小节讲了操作系统宏观的体系结构，这些知识也适合于一般的复杂软件。但教材的叙述有明显的问题：没有把操作系统的“内核”结构，与操作系统的“整体（内核+外围）”分开讲。操作系统的“内核”结构只有两种：微内核与结构化分层结构。面向对象、客户服务器模式等不适合于OS内核。补充习题1 从程序员的角度，了解高级语言库（函数库、类库）、系统调用库(system call)、系统服务(system service)、O

9、S核心之间的关系。答：这个问题是比较重要的，我在课堂上反复讲过。1) 现代的通用操作系统，一般是不允许程序员接近其核心的。程序员怎样使用OS的功能呢?2) 核心提供一组系统服务(system service)，系统服务工作在系统态，一些指令时受保护的（特权指令），不允许程序员直接使用。3) OS提供一组系统调用库(system call)，一般是C语言函数的形式，比如WIN32 API。程序员可以通过调用这些库函数，这些库函数再调用系统服务(system service)，把结果返回给程序员。需要注意的是:系统调用库工作在用户态，系统服务工作在内核态，两者调用返回时，OS要进行状态切换。4)

10、系统调用库(system call)是程序员所能直接访问的OS最底层了，大多数程序员是通过高级语言库（函数库、类库）去间接使用系统调用库的，这样更简单一些，但很显然效率不够好。5）系统调用库的使用相当繁杂，因此程序员可以使用C/C+、JAVA等高级语言里函数库、类库中的一部分函数或类（主要是与I/O有关的函数或类）调用操作系统的功能，当程序员调用这些函数或类后，系统（高级语言运行环境或操作系统）将其转换为系统调用系统服务，一层层的调用OS内核功能，然后再一层层返回。2 从用户角度，了解用户命令、系统服务(system service)、OS核心之间的关系。答：用户命令可分为字符命令和GUI命令

11、2种，无论发出何种命令，都被OS外围的一个“命令解释程序（比如Windows的 ，UNIT/LINUX的SHELL）程序”截获，变换成相应的系统服务(system service)去调用OS的核心，然后返回。用户命令是不能直接调用OS核心的。3怎样看待操作系统的开销？答：OS为了管理硬件等资源，必需付出必要的“管理成本”开销，比如进程调度。有时用纯软件方案“成本”太高，不得不加硬件，比如分页内存、虚拟内存、一些CACHE技术等等。当软件和硬件“成本”都太高时，不得不放弃一些好的方法，比如银行家算法。操作系统内核程序本身也是进程，本身就是开销。4 有人说某操作系统是多用户多

12、任务的，这是什么意思？答：多用户代表多个用户可同时登录使用，分时系统（UNIX）就是典型的多用户操作系统。多任务是多道程序（或多进程）并发的。5 Windows有一个终端仿真程序，可以将本机仿真成主机终端登录远程主机，这个程序的名字叫什么？答：telnet6有人说设计PC机的单用户操作系统，CPU的利用率不重要，怎么理解此观点？答：多道程序设计可提高CPU的利用率，但在PC机中操作系统中，提高CPU利用率只是手段而不是目地，单用户操作系统CPU调度的主要的目地是方便用户同时运行多个任务，及快速响应用户请求。7 为什么通用操作系统一般不支持硬实时？答：通用操作系统支持的应用种类太多，内部构造太复

13、杂。比如CPU调度，要考虑公平性因素，为各类进程服务，很难以最优先的次序满足硬实时要求。在中断响应机制、进程上下文切换等操作中，时间开销也是无法准确预测的，不能满足硬实时要求。通用操作系统一般为分层设计，这降低了效率，也不能满足硬实时要求。第二章 要点这一章和第3章是本课程最重要的两章。2.1 进程的基本概念 本小节重点内容是进程的概念、进程的三种状态及转换（围绕P38图2-5理解）、进程控制块FCB的概念及作用、进程就绪队列和阻塞（等待）队列的概念。其它内容作一般性的了解即可。2.2 进程控制掌握原语的概念。其它内容作一般性的了解即可。2.3 进程同步这一小节是至关重要的，也是相当难的。（1

14、）P47-50，临界资源问题、临界区的概念、同步机制应遵循的规则。 （2）P50，整型信号量原语的含义，及其缺点。（3）P51，记录型信号量原语的含义，特点，及其优点（与整形信号量对比）。（4）P52-53 AND型信号量和信号量集，一般性了解。（5）P53 2.3.3 信号量的应用，一般性了解。（6）P55 管程，一般性了解。2.4 经典进程的同步问题 熟练掌握用记录型信号量解生产者消费者、哲学家进餐、读者-写者问题。其它解法（AND信号量、信号量集、管程等）可以不看。 2.5 进程通信：一般性了解。2.6 线程 概念性的掌握什么是线程、线程与进程主要的异同、线程的状态、内核线程、用户线程。

15、对于软件班和数学班的同学，上述概念将结合实验考核，二学历班的同学无此要求。教材习题1 什么是前驱图？为什么要引入前驱图？答：P35。前驱图是一个有向无循环图，用于描述进程之间执行的前后关系。引入前驱图可以比较直观的描述多道程序进程之间的不确定（异步）关系。2 试画出下面四条语句的前驱图： S1: a=x+y; S2: b=z+1; S3: c=a-b; S4: w=c+1 答：参考P36图2-4。根据变量赋值的顺序，有 (S1 , S2)-S3-S43. 程序并发执行为什么会产生间断性特征?答：P36。因为程序在并发执行过程中存在相互制约性（同步要求），另外进程时而要求使用CPU、时而I/O也

16、会造成进程间断。 4. 程序并发执行为何会失去封闭性和可再现性?答：P37。多个进程共享系统中的各种共享资源（可以表示为共享变量或共享内存），一方面资源状态可由多个进程来改变，另一方面处置不当可能引起共享变量出错（需要互斥来解决），即存在资源共享性使程序失去封闭性；而失去了封闭性导致程序失去可再现性。 5. 在操作系统中为什么要引入进程概念?它会产生什么样的影响?a.为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以描述，而引入了进程概念。b.影响：OS通过管理进程，使程序的并发执行得以实行. 6. 试从动态性，并发性和独立性上比较进程和程序?a 动态性是进程最基本的特性，程序是静

17、态实体；b 并发性是进程的重要特征，程序是不能并发执行的.c 独立性是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位.而对于未建立任何进程的程序，都不能作为一个独立的单位参加运行. 7. 试说明PCB的作用?为什么说PCB是进程存在的唯一标志?答：P41a. PCB是进程实体的一部分（进程实体包括PCB、程序代码、数据），是操作系统中最重要的记录型数据结构，PCB中记录了操作系统所需的用于描述进程情况及控制进程运行所需的全部信息.b在进程的整个生命周期中，系统总是通过其PCB对进程进行控制，系统是根据进程的PCB而感知到该进程的存在的，所以说，PCB是进程

18、存在的唯一标志. 8试说明进程在三个状态之间转换的典型原因答：结合P38图2.5说明。主要原因是请求I/O和I/O完成、CPU调度。9. 为什么要引入挂起状态?该状态具有哪些性质?答：P39。挂起是进程在就绪队列上等待，进程挂起时不接受CPU调度。a. 引入挂起状态是由于5种需要: 终端用户的需要，父进程的需要，操作系统的需要，对换的需要和负荷调节的需要.b. 处于挂起状态的进程虽在就绪队列中，但不能接收处理机调度。 10 在进行进程切换时，所要保存的处理机状态信息主要有哪些?答：P42第一段。 11 试说明引起进程创建的主要事件.12 试说明引起进程撤消的主要事件.答：P44-45。13 在

19、创建一个进程时，需完成的主要工作是什么?答:P44操作系统发现请求创建新进程事件后；1)申请空白PCB；2)为新进程分配资源；3)初始化进程控制块；4)将新进程插入就绪队列. 14 在撤消一个进程时，需完成的主要工作是什么?答：P45 “2进程的终止过程”15 试说明引起进程阻塞或被唤醒的主要事件是什么?答：P4616 进程在运行过程中存在哪两种形式的制约?试举例说明之答：P48第1-2段。1)直接制约：进程共享独占式资源的互斥制约（比如互斥使用打印机）；2)间接制约：进程之间存在合作关系带来的同步制约（比如生产者消费者问题）3)互斥也可以看作是一种特殊的同步。补充习题：什么是临界资源和临界区

20、?a. 一次仅允许一个进程使用的资源成为临界资源，这种资源可以用共享变量代表，这种资源必须是互斥使用的。b. 在每个进程中，访问临界资源的那段程序称为临界区。 17. 为什么进程在进入临界区之前，应先执行进入区代码，在退出临界区后又执行退出区代码?答：P50。为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为进入区代码；在退出临界区后，必须执行退出区代码，用于恢复未被访问标志。使用信号量，则进入区代码为P（S）

21、，“退出区”代码为V（S），S初值为1 18 同步机构应遵循哪些基本准则?为什么?答：P50a. 空闲让进.b. 忙则等待.c. 有限等待.d. 让权等待. 上述准则适合于进程的同步和互斥。记录型信号量实现了上述原则。19 试从物理概念上说明记录型信号量wait和 signal答：P51。Wait操作又叫P操作，signal操作又叫V操作。20. 你认为整型信号量机制和记录型信号量机制，是否完全遵循了同步机构的四条准则?答：P50-51。a. 在整型信号量机制中，未遵循让权等待的准则，存在“忙等”现象。b. 记录型信号量机制完全遵循了同步机构的四条准则。 21 如何利用信号量机制来实现多个进程

22、对临界资源的互斥访问？并举例说明之。答：P50的伪代码 Repeat Entry sectionCritical section /对共享资源（临界资源）的访问Exit section Remainder section /不访问共享资源的其他代码 Until false说明了多个进程对临界资源的互斥访问的解决思路，具体的，可设一记录型信号量S，初值为1，用P(S)替代Entry section，V（S）替代Exit section 在教材生产者消费者和读者写者的例子中都能看到上述用法。22 试写出相应的程序来描述图2-17所示的前驱图（图略）答：参考P54-55“2利用信号量实现前驱关系”（

23、考研的同学应把这部分内容看一下）。这也是信号量对进程同步的一种用法，信号量初值为0。23. 在生产者消费者问题中，如果缺少了signal(full)或signal(empty),对执行结果会有何影响?答：缓冲区满后，生产者进程被阻塞（进入关于信号量empty的等待队列），由于消费者取走产品后不执行signal(empty), 被阻塞的生产者进程继续被阻塞，即便缓冲区有空位也不能生产。缓冲区空后，消费者进程被阻塞（进入关于信号量full的等待队列），由于生产者生产后不执行signal(full), 被阻塞的消费者进程继续被阻塞，即便缓冲区有产品也不能消费。 24. 在生产者消费者问题中，如果将两

24、个wait操作即wait(full)和wait(mutex)互换位置；或者是将signal(mutex)与signal(full)互换位置结果会如何?答：首先，教材P58是生产者消费者问题的最佳解，它支持多个生产者进程和多个消费者进程并发，而不仅仅是一个生产者进程和一个消费者进程并发。（1）如果将（消费者的）两个wait操作即wait(full)和wait(mutex)互换位置，后果是：a.影响了多个消费者的并发性，当一个消费者进行了wait(mutex)，其它消费者因得不到mutex被阻塞，即便缓冲区有多个产品也不允许取。形象的说，教材的解法允许多个消费者同时逛商店，但拿产品时一个一个消费者

25、拿；而颠倒wait(full)和wait(mutex)顺序后，商店一次只能允许一个顾客进入，等顾客拿完产品出门后，另一位顾客才能进去。b. 可能造成死锁。假如某消费者执行wait(mutex)后没被阻塞，但接着执行wait(full)后被阻塞了, 要等待生产者的signal (full)才能解除阻塞，而生产者可能因消费者提前使mutex=0而被阻塞，无法执行signal (full)，这样就造成死锁。c 可能还有其它后果。（2）将（生产者的）signal(mutex)与signal(full)互换位置，似乎不会影响并发性，也不会造死锁，个人认为这也是一种正确的写法。 这道题我给出的答案仅供参考

26、。25. 我们为某临界区设置一把锁W，当W=1时，表示关锁；W=0时，表示锁已打开.试写出开锁原语和关锁原语，并利用它们去实现互斥. 答: 先看教材P50的伪代码 Repeat Entry sectionCritical section Exit section Remainder section Until false说明了多个进程对临界资源的互斥访问的解决思路，在前面的第21题中，讨论了可设一记录型信号量S，初值为1，用P(S)替代Entry section，V（S）替代Exit section。 还有一种办法是教材P75介绍的“互斥锁”，其思路很简单：将Critical section想

27、象成只允许一个进程进入的小黑屋，小黑外有一把锁，当进程发现锁是开着的，可以进入小黑屋，然后关上锁不让其它进程进入，出来时把锁打开给其它进程进入的机会。 锁可以看作是（小黑屋外的）共享变量W，对W有两个操作：unlock(W) ，lock(W)，这两个操作必须也是原子操作，其理由与信号量必须是原子操作一样。开锁原语: unlock(W)W=0;关锁原语: lock(W) if(W=1) do no_op; W=1;利用开关锁原语实现互斥，用lock(W);替代Entry section，unlock(W)替代Exit section即可。var W:=0;process : repeatlock

28、(W);critical sectionunlock(W);remainder sectionuntil false; 锁比信号量简单，但只能用于进程互斥，不能用于同步。 26试修改下面生产者消费者问题解法中的错误答：按P58的正确解法修改即可。 27 试利用记录型信号量写出一个不会出现死锁的哲学家进餐问题的算法.答：先看P62哲学家进餐问题的解及可能出现死锁的原因（出现了循环等待）。根据P105死锁的四个必要条件，只要破除其中一个必要条件即可。下面的解的思路是：偶数哲学家现拿左面的筷子，后拿右面的，奇数哲学家正相反，这样就破除了循环等待，使死锁不可能发生。设初始值为1的信号量cI表示I号筷子

29、被拿(I=1,2,3,4,.,2n),其中n为自然数.Beginif I mod 2=1 then /如为奇数哲学家 P(cI);P(cI-1 mod 5);Eat;V(cI-1 mod 5);V(cI);else /如为偶数哲学家P(cI-1 mod 5);P(cI);Eat;V(cI);V(cI-1 mod 5);End 28 在测量控制系统中的数据采集任务，把所采集的数据送一单缓冲区；计算任务从该单缓冲中取出数据进行计算.试写出利用信号量机制实现两者共享单缓冲的同步算法.答：解法与生产者消费者问题一样。这个题目的用意在于给出生产者消费者问题的一个实际应用-多进程的单缓冲通信。生产者消费者

30、是非常重要、有广泛实际价值的问题。29画图说明管程由哪几部分组成?为什么要引入条件变量?答：见P56图2-13管程由三部分组成:局部于管程的共享变量说明；对该数据结构进行操作的一组过程；对局部于管程的数据设置初始值的语句.因为调用wait原语后，使进程等待的原因有多种，为了区别它们，引入了条件变量.30 如何利用管程解决生产者消费者问题？答：见P60。考研的同学无需看这道题，只需会使用记录型信号量解进程同步问题即可，管程、信号量集、AND信号量只需从概念上了解一下即可，无需做大题。31 什么是AND型信号量？。32 什么是信号量集？。答：考研的同学只需从概念上了解一下即可，无需做大题33试比较

31、进程间的低级通信工具与高级通信工具.答：P65。信号量是低级的进程通信工具，优点是速度快（教材认为效率低是片面的），缺点是难以使用，通信对用户不透明（所有的操作都必须由程序员来实现）,而且必须借助共享内存才能通信。而高级通信工具则可弥补这些缺陷，用户可直接利用操作系统所提供的一组高级通信命令，高效地传送大量的数据。34当前有那几种高级通信机制？答：P65-66a. 共享存储器系统通信方式（低级）;b. 消息传递系统通信方式（高级）;c. 管道通信方式（高级）. d. RPC(远程过程调用)，教材没有介绍。RPC允许一台机器远程呼叫另一台机器上的过程（或函数），这是网络时代最常见的高级通信机制，

32、JAVA的RMI, RMI-IIOP 微软的COM+RPC .net remoting，以及CORBA, web Service等分布式通信（和组件）技术都是从RPC发展起来的。35 消息队列通信机制有哪几方面功能？答：P69-71。主要有消息缓冲区、发送原语、接受原语。36 为什么要在OS中引入线程？答：这道题比较重要，参见P72。因为进程既是资源分配的基本单位、又是CPU调度的基本单位，负担沉重，引入线程后，线程变成了CPU调度的基本单位，线程创建、切换、撤销的开销较小，有利于提高系统性能。37 试说明线程有哪些属性？答：P73-74“3线程的属性”38试从调度性，并发性，拥有资源及系统开

33、销几个方面，对进程和线程进行比较.答：P72“2线程与进程的比较”a. 在引入线程的OS中，把线程作为调度和分派的基本单位，而把进程作为资源拥有的基本单位；b. 在引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，亦可并发执行，因而使OS具有更好的并发性；c. 进程始终是拥有资源的一个独立单位，线程自己不拥有系统资源，但它可以访问其隶属进程的资源；d. 在创建，撤消和切换进程方面，进程的开销远远大于线程的开销. 39 为了在多线程OS中实现进程之间的同步与通信，通常提供了哪几种同步机制？答：P75。互斥锁、条件变量、信号量。对于用户级线程还可以提供管程机制。实际上线程

34、的同步机制与进程的同步机制几乎相同。40 用于实现线程同步的私有信号量和公有信号量有何区别？答：参见P76。私有信号量只归一个进程所有，可被该进程所属的线程共享，OS可能不知道私有信号量的存在。公有信号量正相反。41 什么是用户级线程和内核级线程?.答：P77。内核级线程是依赖于OS内核的，它存在于用户进程和系统进程中，它们的创建，撤消和切换都由OS内核实现；用户级线程仅存在于用户级中，它们的创建，撤消和切换不利用系统调用来实现，因而与内核无关，内核并不知道用户级线程的存在。JAVA线程是用户级的。42 试说明用户级线程的实现方式43 试说明内核支持级线程的实现方式 答：P78-81。考研的同

35、学只需了解P80 图2-16，用户线程与OS内核间一对一、多对一、多对多的映射即可。第三章 要点这一章和第2章是本课程最重要的两章。3.1小节概念上了解什么是高级调度、中级调度、低级调度。熟知P87介绍的抢占式和非抢占式调度。 3.2 小节 熟知P88图3.1调度队列模型。3.3 小节 熟悉本小节介绍的各种调度算法及其优劣。3.4 小节 知道什么是实时调度，实现实时调度的基本条件。其它内容可以不看。 3.5 小节 了解死锁产生的原因（P103-105）。 特别熟悉产生死锁的四个必要条件（P105） 了解处理死锁的基本方法（P105-106）3.6 小节 了解预防死锁的几种办法（P106-107

36、） 熟悉系统安全状态（107-108）、银行家算法（P109-111），知道怎样使用银行家算法的思路，手工找出是否存在安全序列。考研的同学最好能编程实现它。 3.7小节 了解P112资源分配图的约简、了解P113的死锁定理。本章习题1. 高级调度与低级调度的主要任务是什么?为什么要引入中级调度?a 作业调度又称宏观调度或高级调度，其主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存，输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利.b. 进程调度（又称CPU调度、微观调度、低级调度），其主要任务是按照某种策略和方法选取一个处于就绪状态

37、的进程，将处理机分配给它。C 为了提高内存利用率和系统吞吐量，引入了中级调度. 2 何为作业？作业步和作业流？答：P84-85。在个人电脑上很少用到“作业”这个概念，但Windows操作系统有一种批处理文件，其后缀为.bat，相当于教材提到的“作业说明书”， 批处理文件可以顺序的执行一系列程序。3 在什么情况下需要用到作业控制块JCB？其中包含了那些内容？答：P85。4 在作业调度中如何决定接纳多少个作业和接纳哪些作业？ 答：P85。5 试说明低级调度的主要功能？答：P86。缩略成百字左右的答案即可。6 在抢占式调度中，抢占的主要原则是什么？答：P87的三条原则。7. 选择调度方式和调度算法时

38、，应遵循的准则是什么?答：P90-91a 面向用户的准则：周转时间短，响应时间快，截止时间的保证，以及优先权准则.B 面向系统的准则：系统吞吐量高，处理机利用率好，各类资源的平衡利用. 8 在批处理系统、分时系统、实时系统中，各采用哪几种调度算法？答：批处理系统适合采用动态优先权的抢占式或非抢占式算法。分时系统本身就是抢占式的（时间片一到即切换进程），结合动态优先权就更好了。这道题需要对3.3小节的各种算法有深入了解。比如：1) 什么是抢占式或非强占式？2) 什么是动态优先级和静态优先级？3) 短作业优先算法是否含有优先级？是否是抢占式的？4) 分时系统是否抢占式？5) 哪些算法会造成进程饥饿

39、？为什么？6) 带优先级（静态或动态）的算法一定是抢占式的吗？本题对实时调度算法不做要求。9 何为静态和动态优先级？确定静态优先级的依据是什么？答：P93。“2优先权的类型”。10 试比较FCFS和SPF两种算法答：简单的说，FCFS公平，无进程饥饿，但调度性能不好。SPF正相反。11 时间片轮转法中，应如何确定时间片的大小？答：P95。12 试举一个例子说明通常的优先级调度算法不适合于实时系统？答：优先级调度算法即可以是抢占式的，也可以是非抢占式的。实时系统的进程调度是很复杂的，比如进程A需要10ms内完成，当进行到5 ms，来了一个优先级更高的需要2 ms内完成的进程B，如B抢占A，则B完

40、成后A无法按时完成；如B不抢占A，则A完成后B无法按时完成。13. 为什么说多级反馈队列能较好地满足各种用户的需要?答：P9714 为什么在实时系统中，要求系统（尤其是CPU）有较强的处理能力？答:P98“2系统处理能力强”。实际上有些实时系统CPU处理能力并不强，比如一些嵌入式实时系统，这就要求系统尽量少做一些并发计算任务，留出足够冗余处理实时任务。15 按调度方式可将实时调度算法分为哪几种？答：P99-10016 什么是最早截止时间优先调度算法，请举例说明之17 什么是最低松弛度优先调度算法，请举例说明之答：P100-102。考研的同学概念上了解一下即可。 最早截止时间优先调度算法：任务要

41、求的截止时间越早，其优先级就越高。最低松弛度优先调度算法：任务的紧急程度越高，其优先级就越高。18 何谓死锁?产生死锁的原因和必要条件是什么?答：死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进;产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；产生必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件。这四个必要条件必须同时满足，才有死锁的可能。 19 在解决死锁问题的几个方法中，哪种方法最容易实现?哪种方法使资源的利用率最高?a 解决死锁可归纳为四种方法: 预防死锁，避免死锁，检测死锁和解除死锁；b 其中，预防死锁的“摈弃环路”是最容

42、易实现的，系统开销也小；见P107。c 避免死锁（银行家算法）使资源的利用率最高（应该是系统开销最大）。 20 请详细说明可通过哪些途径预防死锁?答:P107a. 摈弃请求和保持条件,就是如果系统有足够的资源，便一次性地把进程所需的所有资源分配给它；b. 摈弃不剥夺条件，就是已经保持了资源的进程，当它提出新的资源请求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请；c. 摈弃环路等待条件，就是将所有资源按类型排序标号，所有进程对资源的请求必须严格按序号递增的次序提出. 21在教材银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Reques

43、t0(0,1,0),问系统可否将资源分配给它?答：可以。可以找到一个安全序列P1,P4,P3,P2,P0,或P1,P4,P3,P0,P2 。22 在银行家算法中，若出现下列的资源分配情况：试问：AllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6(1)该状态是否安全?(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？【注】期末考试不会出这道题的原题，但很可能出一比这道题简单的相同类型题目答：这是

44、5个进程，对4种资源的分配。Allocation是各进程已获得的资源，Need是尚缺的资源，Available是系统剩余的资源。银行家算法分为两部分：第一部分是资源预分配算法（P109“2银行家算法”），即对某进程的一个资源请求，先进行模拟分配，然后运行银行家算法的第二部分，找出是否存在安全序列。第二部分是安全性算法（P109“3安全性算法”）,找出当前系统状态是否有安全序列。(1)该状态是否安全? 只需运行银行家算法的第二部分即可。我的解法看上去与教材不一样，实际是一样的。Available（1622）P0 Need(0012)，分配/去配后：AllocationNeedAvailableP

45、01 6 5 4P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6Available（1 6 5 4）=P3 Need(0652)，分配/去配后：AllocationNeedAvailableP01 9 8 6P11 0 0 01 7 5 0P21 3 5 42 3 5 6P3P40 0 1 40 6 5 6Available（1 9 8 6）P1 Need(1750)，分配/去配后：AllocationNeedAvailableP02 9 8 6P1P21 3 5 42 3 5 6P3P40 0 1 40 6 5

46、6Available（2 9 8 6）P2 Need(2356)，分配/去配后：AllocationNeedAvailableP03 12 13 10P1P2P3P40 0 1 40 6 5 6Available（3 12 13 10）P4 Need(0656)，分配/去配后：AllocationNeedAvailableP03 12 14 14P1P2P3P4 最后得出安全序列为P0,P3,P1,P2,P4(应该还有其他安全序列)(2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？AllocationNeedAvailableP00 0 3 20 0 1 21

47、 6 2 2P11 0 0 01 7 5 0P21 3 5 4 2 3 5 6 P30 3 3 20 6 5 2P40 0 1 40 6 5 6首先要运行银行家算法的第一部分，进行预分配（模拟分配）。预分配后系统状态如下：AllocationNeedAvailableP00 0 3 20 0 1 20 4 0 0P11 0 0 01 7 5 0P23 5 7 6 1 1 3 4 P30 3 3 20 6 5 2P40 0 1 40 6 5 6然后运行银行家算法的第二部分，找安全序列。很显然，Available（0400）不能满足任何一个进程的Need，不存在安全状态。所以，P2提出的请求Req

48、uest(1,2,2,2)现在不能分配，要等待一段时间后，系统状态发生变化后，再提请求，再进行银行家算法的预分配和查找安全序列。补充习题1 （该题对考研的同学很重要，要求你能画出与题目答案相似的图表）某就绪队列中已有以下进程等待调度：Process CPU阵发期 优先级（数越小优先级越高）P1 24 3 P2 3 2 P3 3 1（1）在不考虑这些进程到达就绪队列时间先后的前提下（假定它们同时到达），分别画出及计算： 短作业优先算法、循环轮转算法（时间片为4）、静态优先数算法的甘特图及平均等待时间。注：周转时间=进程在就绪队列中的时间+CPU阵发期 CPU阵发期=进程占用CPU的时间等待时间=

49、周转时间-CPU阵发期甘特图是一种常用图表，横轴是时间，纵轴是任务（2）上述三种算法，哪种算法实用性最差？简单说明理由。（3）上述三种算法，哪些算法肯定是抢占式的？哪些算法既可以是抢占式的也可以是非抢占式的？答：（1）短作业优先算法P2P3P10 3 6 30 Waiting time for P1 = 6; P2 = 0; P3 = 3Average waiting time: (6 + 0 + 3)/3 = 3循环轮转算法（时间片为4）P1P2P3P1P1P1P1P10 4 7 10 14 18 22 26 30 The waiting time is : P1=30-24=6; P2=7

50、-3=4; P3=10-3=7The average waiting time is (6+4+7)/3=5.66静态优先数算法P3P2P1 0 3 6 Waiting time for P1 = 6; P2 = 3; P3 =0Average waiting time: (6 + 3 + 0)/3 = 3（2）短作业优先算法实用性最差，因为实际中很难知道进程的CPU阵发时间。（3）循环轮转算法肯定是抢占式的，其它两种算法既可以是抢占式的也可以是非抢占式的。补充习题2. 何谓银行家算法的保守性? 举例说明之。答：银行家算法的保守性是指银行家算法基于死锁的必要条件而非充分条件，如不存在安全序列也

51、不一定死锁。它只给出了进程需要资源的最大量，而所需资源的具体申请和释放顺序仍是未知的，因而银行家只能往最坏处设想。补充习题3（仅供考研同学参考）.1）假设有3个进程竞争同类资源，如果每个进程最大需要2个该类资源，则至少需要提供该类资源_ 个，才能保证不会发生死锁。 A. 3B. 4C. 5D. 62）系统中有4个并发进程，如果每个进程最大需要3个该类资源。试问该类资源最少为 个时，不会因竞争该资源而发生死锁。A. 9B. 10C. 11D. 12答:N个进程共享M个同类资源，如果每个进程最多申请X个资源（1XM)，则 N*（X-1)+1=M时不会死锁。此时肯定存在安全序列第四章 存储器管理 要

52、点4.1 存储器的层次结构理解P116图4-1的存储器层次结构，知道这种结构从经济上考虑，具有好的性能/价格比。 了解P117-118高速缓存CACHE和磁盘缓存，知道它们使用的淘汰算法与虚拟内存的页面置换算法是基本相同的。4.2 程序的装入和链接 这一小节的内容是一些重要的专业常识。应了解本小节介绍的各种装入和链接方法，要求结合Windows操作系统及C语言的实际去理解上述装入和链接方法（联系实际部分可上网查询）。4.3 连续分配方式 通用操作系统大都不用连续分配方式，有些嵌入式OS可能使用这种分配方式。 这一小节只需阅读P121-124即可。4.4 基本分页存储管理方式 这是本章最重要的一

53、小节，要求全读。重点理解页面、物理块、页表、页表的访存、物理地址、逻辑地址、快表（TLB）等概念及相互关系。4.5 基本分段存储管理方式 阅读4.5.1，知道为什么要分段。阅读4.5.2 知道分段的原理。考研的同学要知道段表、地址变换，知道分段和分页的主要区别。 阅读4.5.3 知道分段有利于信息共享，知道“纯代码”的概念。 阅读4.5.4 知道什么是段页式存储。 需要补充说明的是：教材说过，分段方便编程，主要是指方便汇编语言程序员，和设计高级语言编译器的程序员。对使用高级语言进行应用编程的程序员来说，段是透明的，一般不能用高级语言代码去操作段。4.6 虚拟存储器的基本概念 这一小节重点是局部

54、性原理。其它内容泛读即可。4.7 请求分页存储管理方式 掌握请求分页的页表、什么是缺页中断。其它内容泛读即可。 4.8 页面置换算法 熟练LRU算法，知道该算法同样也适合于在本章介绍的CPU CACHE、快表、磁盘缓存的置换。其它内容泛读即可。 4.9 请求分段存储管理 考研的同学也可以不看。本章最后提示：实际的通用操作系统，一般使用请求分页（4.7小节）+基本分段（4.5小节）相结合的存储管理方式。请求分页是离散分配（节约内存）且有虚拟内存（扩展性好），基本分段是连续分配（有P136介绍的几个优点，教材认为基本分段也是离散分配似有不妥）。本章习题1 为什么要配备层次式存储器答：不同视角有不同答案。可以从经济上考虑，这种内外搭配、快慢结合的存储体系有利于实现最佳性能价格比。2. 可采用哪几种方式将程序装入内存?它们分别适用于何种场合?答：【P118 4.2.1】对于高级语言程序，首先由编译程序将用