操作系统高校考研题汇总

操作系统考研试题分析

1.操作系统课程特点............................................................................................................. 2 2.题型分析： ......................................................................................................................... 3 3.试题分析.............................................................................................................................. 5 3.1基本概念 ...................................................................................................................... 5 3.2逻辑结构 ...................................................................................................................... 7 3.3用户界面与OS实例 .................................................................................................. 9 3.4进程的描述与控制 ................................................................................................... 10 3.5同步、互斥与通信 ................................................................................................... 12 3.6算法设计题 ................................................................................................................ 17 3.7进程通信 .................................................................................................................... 25 3.8进程调度 .................................................................................................................... 27 3.9死 锁 ........................................................................................................................... 28 3.10作业调度 .................................................................................................................. 35 3.11存储管理 .................................................................................................................. 37 3.12设备管理 .................................................................................................................. 44 3.13文件系统 .................................................................................................................. 46 3.14 UNIX系统分析 ....................................................................................................... 48

试题分析-1

操作系统考研试题分析

1.操作系统课程特点

和其他基础课程比较起来，操作系统原理这门课程有着十分显著的特点。 （1）内容十分广泛和庞杂

操作系统是随着计算机技术的发展和计算机应用的日益普及而逐渐发展和完善起来的。它经历了手工操作阶段、批处理（早期）和执行系统阶段、批处理操作系统阶段、分时操作系统阶段以及在此基础上形成的个人计算机操作系统、网络操作系统、分布式操作系统的共同发展阶段。对操作系统理论的研究也是随着操作系统实践的发展而不断深入的。早期计算机系统中各部分的界限并不十分严格，因而操作系统涉及的内容十分广泛，包含了硬件、编译、数据结构等内容，直到今天，我们仍然可以从操作系统原理各类教材的内容组织中看到这种包容的痕迹。如中断机构是典型的计算机组成原理研究的对象，也是多数操作系统原理课程所必须讲述的内容；存储管理中空闲块管理既是操作系统研究的课题，也是数据结构课程的重要内容之一，等等。另一方面，操作系统管理着计算机系统的全部软、硬件资源，而这些资源本身种类繁多，特性千差万别，操作系统要管理这些资源，就不得不适应这些资源的差异，从而增加自己的复杂性。此外，操作系统的实例类型极为丰富，作为一门实践性很强的课程来说，又必须注意理论与实际的结合，应该了解各种操作系统的实例，跟踪当代的研究成果，以便增加感性认识，更深刻地理解操作系统。这也给操作系统原理课程的组织和学习增加了难度。

（2）知识点难度跨度大

操作系统课程中各知识点的难度跨度相对而言是比较大的。既有操作系统界面这种常见的内容，也有进程管理这类比较抽象、难度较大的内容。在操作系统实例方面，一般读者可能对DOS、Windows比较熟悉，而对UNIX/Linux、OS/2接触较少，感到不易把握。难度跨度大，就给读者在学习中迅速转换角色造成了困难，造成有的章节一读就懂，一学就会，有的章节虽已苦读多遍，却仍不得要领。

（3）既呆板又灵活

在操作系统课程中，有许多知识点是必须记忆的，表现出来就是概念多。另一方面，在整个操作系统课程中很难找到一根主线，或者说找到一个一成不变的可以套用到任何环境中去的原理、方法、策略。实际上，在不同的环境下，评价操作系统设计策略的优劣与否的标准是不同的，举例说，实时系统要求很高的可靠性和响应及时性，但从批处理系统的要求来看，实时系统简直是在浪费资源。银行家算法和LRU算法都是理想的，但几乎都不能运用于实际中去。这就是操作系统的灵活性，它要求读者在学习每一部分内容时，不仅要记住给出的结论，还要认真思考所讨论问题的由来、环境、意义、理论依据和应用背景，并结合实例操作系统加深理解，做到举一反三。

那么，应该如何学好操作系统原理这门课程呢？我们建议读者要根据这门课程的特点，有针对性地加强训练。要结合教材讲授的操作系统实例和实验课，深刻领会设计思想。UNIX在进程管理、存储管理和文件系统方面都体现了很好的设计思想，值得认真研究。

试题分析-2

操作系统考研试题分析

2.题型分析：

从历年各校研究生入学考试试题来看，主要题型有以下几种： （1）名词解释

主要考查考生对操作系统的基本概念的记忆程度，要求表述准确、完整。这类题型难度系数较低，如果考生用心准备，是可以争取到全分的。操作系统的概念较多，但在名词解释题型中通常只考查最基本的概念，如操作系统、微内核、并行、顺序进程与并发进程、中断响应、中断源、系统调用、时钟、原语、特权指令、作业控制语言（JCL）（引论）；进程、线程、进程控制块（PCB）、临界区、抢占式进程调度、剥夺式抢占、死锁、作业说明书（进程管理）；可再入程序、地址映射、地址重定位、虚存、动态重定位、联想存储器、程序局部性、工作集（存储管理）；虚设备、通道、SPOOLING、缓冲（设备管理）；索引文件、磁盘调度算法、文件系统（文件系统），等等。一般名词解释的分值都在每题2分以上，所以值得重视。需要提醒考生的是，要防止考查偏题，即平时没有接触过的概念。这就要求考生对报考学校的历史性考题作一些分析研究。

（2）填空题

也是考查基本概念的主要题型，考查范围比名词解释广，但不要求考生对每个概念的表述作完整记忆，考生只需对概念的主要内容领会即可，因而单题难度略小一些。

（3）判断改错题

在考查考生对基本概念记忆的基础上，进一步考查考生对相似概念的辨异能力。这类题型比名词解释和填空题略难，要求考生准确理解概念背后的含义。

（4）选择题

考查范围主要是基本概念，也包括简单计算、基础知识、基本原理的考查，但是增添了迷惑性，增大了难度。解题方法一是熟记基本概念，采用直选法。二是采用排除法，即将不正确或看起来不熟悉的选项排除出去，剩下的备选项即为答案。除了常见的单项选择与多项选择外，有的学校会在操作系统实例的主要特点这个知识点上考选择题，要求将给定的操作系统类型与其最主要的特点联系起来。对熟悉操作系统产品的考生来说，应该难度不大。

（5）简答题

简答题主要考查考生对基本原理的理解，难度跨度比较大。既可以考基本概念题，如要求比较分时系统与实时系统的区别，也可以考难度较大的设计题。如东南大学2000年试题：

假如你是某操作系统的设计者，承担慢速字符设备管理任务。该操作系统要求用户使用慢速字符设备和使用普通文件一样方便快捷。请问你在设计中至少要解决哪些问题?

这类题综合性强，无参照，难度大，甚至很难给出标准答案。考生要在平时加强基本功的训练，可以有意识地阅读一些技术文章，扩大知识面。

（6）作图题

作图题是操作系统课程中比较独特的题型。主要考查范围是进程状态变迁、存储分配、给定PV操作算法要求画出前趋图以及画出文件系统的目录结构等。解这类题要注意作图美观、标记清楚，不遗漏标识符。

（7）算法题

试题分析-3

操作系统考研试题分析

主要有算法设计和算法分析题，偶尔会出现算法填空题。主要考查范围是进程的同步与互斥、死锁等内容。这部分内容我们在进程管理一章作了较详细的讲述。

（8）计算题

主要考查范围是资源利用率计算（进程管理）、周转时间计算（作业调度）、缺页次数（率）计算（存储管理）、访盘次数计算（文件系统）等。本书围绕这些内容也选编了大量例题和习题，供读者参考。

（9）证明题

操作系统课程实践性强，理论证明不是其重点。但少数学校也有考查证明题的传统。因此，我们在本书中选编了少量证明题，供读者参考。对报考这些学校的考生来说，应该熟记这些考题，因为基本原理的证明是很难做到花样翻新的，换言之，如果要考，则原题再现的可能性比较大。

试题分析-4

操作系统考研试题分析

3.试题分析

3.1基本概念

●什么是操作系统？它有什么基本特征？（哈工大2000年试题） 【解答】

操作系统：操作系统是计算机系统中的一个系统软件。它是一些程序模块的集合，这些程序模块管理和控制计算机中的硬件和软件资源，合理地组织计算机工作流程，以便有效地利用这些资源为用户提供一个功能强、使用方便的工作环境，从而在用户及计算机之间起到接口的作用。

操作系统的基本特征是并行性、共享性、不确定性。

●判断：操作系统程序都是在核心态下才能运行。（大连理工大学2000年试题） 【分析】

操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户的程序的集合。操作系统提供的服务，一部分必须在核心态下才能运行，如进程调度、目录服务等。还有一些功能，如DOS下的外部命令，则可以由用户调用，运行在用户态下。

【解答】 错误。

●批处理系统的主要缺点是：（清华大学1996年试题） A．CPU利用率低。 B．不能并发执行。 C．缺少交互性。 D．以上都不是。 【解答】 选择C。

●填空：多道运行的特征之一是宏观上并行，它的含义是（ ）。（华中科技大学2000年试题） 【分析】

多道运行的特征是多道性、宏观上并行、微观上串行。多道性是指计算机主存中同时存放几道相互独立的程序。宏观上并行是指同时进入系统的几道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕。微观上串行是指主存中的多道程序轮流或分时地占有处理机交替执行。

【解答】

并发程序都已经开始执行，但都未结束。

●判断：在分时系统中，响应时间≈时间片×用户数，因此为改善响应时间，常用的原则是使时间片越小越好。（东南大学1996年试题）

【分析】

试题分析-5

操作系统考研试题分析

时间片越小，进程切换所用的开销就相对越大。因此时间片不是越小越好，一般使用户键入的常用命令能在一个时间片内处理完毕即可。

【解答】 错误。

●实时系统应具备的两个基本特性是（ ）和（ ）。（北京理工大学2000年试题） 【分析】

实时系统是顺应实时控制和实时信息处理的需要而产生的。所谓\实时\是表示\及时\、\即时\，而实时系统是指系统能及时（或即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时系统的应用领域决定了它的特性是：①具有实时时钟管理功能；②能进行过载保护；③高可靠性。

【解答】 及时性高可靠性

●实时信息处理是实时应用的一种，例如（ ）和（ ）都是实时信息处理的例子。（华中科技大学2000年试题）

【解答】

飞机订票系统、图书资料查询系统

●现代操作系统的基本功能是管理计算机系统的硬件、软件资源，这些管理工作分为A管理、B管理、C管理、D管理、E和通信事务管理。（东南大学2000年试题）

【解答】

A．处理机 B．存储器管理 C．设备 D．文件 E．作业 【扩展】

选择：操作系统的（ ）管理部分负责对进程调度。

A．主存储器 B．控制器 C．运算器 D．处理机这里要防止把处理机与系统结构中所说的处理机的组成混淆起来。选择D。

●为了支持多道程序运行，存储管理必须要实现的主要功能有（ ）、（ ）和主存扩充。（华中科技大学1997年试题）

【分析】

在多道程序运行环境下，程序员无法预知存储管理模块将把他们的程序分配到主存的什么地方，而且程序员也希望摆脱存储地址、存储空间大小等细节问题。因此存储管理模块应该提供地址重定位能力。另外，由于主存中可同时存放多道程序，为了防止程序间相互干扰，存储管理模块必须提供存储保护手段。

【解答】

存储无关性、存储保护

●选择：衡量整个计算机性能指标的参数有：（北京理工大学1999年试题）

A．用户接口。 B．资源利用率。 C．作业步的多少。 D．吞吐量。 E．周转时间。

试题分析-6

操作系统考研试题分析

【分析】

操作系统的性能与计算机系统工作的优劣有着密切的联系。评价操作系统的性能指标一般有： 系统的可靠性；系统的吞吐率（量），是指系统在单位时间内所处理的信息量，以每小时或每天所处理的各类作业的数量来度量；系统响应时间，是指用户从提交作业到得到计算结果这段时间，又称周转时间；系统资源利用率，指系统中各个部件、各种设备的使用程度。它用在给定时间内，某一设备实际使用时间所占的比例来度量；可移植性。

【解答】选择B、D、E。 【扩展】

判断：资源的利用率高和系统的工作效率高是一回事（）。（东南大学试题） 解答：系统的工作效率，也就是吞吐率。从上述分析可知，此题应判错误。

3.2逻辑结构

●判断：数据库管理程序需要调用操作系统程序，操作系统程序的实现也需要数据库系统的支持。（）（大连理工大学2000年试题）

【分析】

从操作系统虚拟机的结构来看，最核心层是裸机，紧挨着的一层是操作系统，这一层把应用程序和裸机隔离开来，使得应用程序看起来似乎运行在一个虚拟机器上。题中说法没有正确反映应用程序与操作系统的关系。

【解答】 错误。

●简答：操作系统有哪几种结构设计方法？简述其中之一的特点。（武汉大学2000年试题） 【解答】

操作系统有无结构、层次结构和客户/服务器模型等3种结构设计方法。

现今大多数操作系统采用的是层次结构。层次结构是结构设计方法的一种，使用这种方法进行设计时，可以形成正确、结构清晰的软件系统，从而达到可靠、可适应、可移植的设计目标。在层次式结构下，操作系统的各模块应处于什么位置、各模块之间的关系十分清晰。

●一个分层结构操作系统由裸机，用户，CPU调度和P、V操作，文件管理，作业管理，内存管理，设备管理，命令管理等部分组成。试按层次结构的原则从内到外将各部分重新排列。（中国科学院计算技术研究所1997年试题）

【解答】

按层次结构的原则从内到外依次为：裸机，CPU调度和P、V操作，内存管理，作业管理，设备管理，文件管理，命令管理，用户。

试题分析-7

操作系统考研试题分析

●在计算机系统中，为什么要区分管态与目态？操作系统为什么能为用户程序提供各种服务？（西安电子科技大学1999年试题）

【解答】

操作系统是计算机系统中最重要的系统软件，为了能正确地进行管理和控制，其本身是不能被破坏的。因此，系统采用了区分处理机状态的办法，为操作系统程序建立一个保护环境。这样，用户程序只能在管态下运行，只能执行非特权指令，只能访问自己的存储区，从而保护了操作系统程序的正常运行。

操作系统虚拟机为用户提供了一个协助解决问题的装置。操作系统为用户提供两种类型的用户界面，其一是命令接口，包括键盘命令、作业控制语言、图形化用户界面等；其二是系统调用，又称程序接口。通过这两种界面，操作系统把它的全部操作命令的集合呈现给用户（或用户程序），从而实现了为用户服务。

●判断：用户程序通常可以直接访问系统缓冲区中的数据。（ ）（大连理工大学2000年试题） 【分析】

由前面叙述可知，用户程序工作在目态下，只能直接访问自己的存储区，访问系统缓冲区必须通过操作系统的服务。

【解答】 错误。

●选择：你认为下列哪几种指令应该在核心状态下执行。（（上海交通大学1999年试题,10分） 1．屏蔽所有中断；2．读时钟周期；3．设置时钟日期；4．改变存储映像图；5．存取某地址单元的内容；6．停机。

【解答】

1、2、4、6必须在核心状态下执行。

●简答：试说明中断在进程控制中的推动作用。（南开大学2000年试题）（8分） 【解答】

中断是实现操作系统功能的基础，是构成多道程序运行环境的根本措施，是进程控制中的推动力量。例如，外设完成中断或请求使用外设的访管中断的出现，将导致I/O管理进程投入运行；申请或释放主存而发出的访管中断，将导致在主存中创建一个进程而且开始运行；时钟中断或I/O完成中断，可导致处理机调度工作的执行；操作员从键盘发出终止执行的命令，可以终止当前进程的运行。所以，中断是进程运行的引导，是它们被激活的驱动源。

●选择：中断发生时，由硬件保护并更新程序指令计数器PC，而不是由软件完成，主要是为了（ ）（华中科技大学1998年试题）

A．提高处理速度。 B．使中断程序易于编制。 C．节省内存。 D．能进入中断处理程序并能正确返回。

【分析】

一次中断过程分为中断进入（由硬件负责）和中断处理过程（由软件负责）。在中断进入过程中，首先保存PC、PS值，然后从中断向量地址中得到PC、PS值放入寄存器。软件的中断处理过程是，先保存

试题分析-8

操作系统考研试题分析

现场信息和参数传递，再执行中断处理程序，最后恢复和退出中断。简要地说，一次中断，两次保护现场。分步保护现场的原因是，进入软件的中断处理后，PC、PS寄存器里被填上了新内容，因此，PC、PS的保护只能由硬件完成。

【解答】 答案是D。 【扩展】

中断响应的实质是什么？

从上述分析可知，中断响应的实质是交换指令执行地址和处理器状态信息。

●填空：中断优先级是由硬件规定的，若要调整中断的响应次序，可通过_______。(北京大学1997年试题)

【分析】

中断优先级是由硬件规定的，其次序是不能由软件更改的。要调整中断的响应次序，只能通过中断屏蔽。

【解答】 中断屏蔽

3.3用户界面与OS实例

●在答卷上用连线把下面左右两列词连起来形成最恰当的5对。（东南大学2000年试题） 左列： 右列： （1）Linux （1）面向对象 （2）UNIX （2）网络操作系统 （3）Windows NT （3）微内核 （4）Mach 3.0 （4）自由软件 （5）OS/2 （5）C语言

【分析】

UNIX的核心代码大部分是用C语言写的。Windows NT是当然的网络操作系统。Linux是UNIX的一种，具体讲Linux是一套兼容于System V以及BSD UNIX的操作系统，也是遵循POSIX规范的一个操作系统。Linux于1991年4月由芬兰人Linus Benedict Torvalds在赫尔辛基大学独立开发，并由此开创了自由软件的先河。当UNIX日渐庞大复杂而难以掌握时，人们提出了Microkernel的概念，就是把Kernel去芜存菁，仅留下重要的部分，以此减低Kernel的复杂度。Mach就是在Carnegie-Mellon（卡耐基－梅隆CMU）大学诞生的一个Microkernel（微核心）操作系统（1980年）。Mach最普遍的版本是Mach 2.5。它是许多商业UNIX如DEC OSF/1、NextStep的基础。Mach 3.0才是真正纯粹的完全Microkernel化版本。

OS/2采用32位抢先多任务体系结构，采用客户机－服务器策略，在对等层环境既是一个客户机又是一个服务器。OS/2可以同时运行Windows 3.1、DOS和OS/2的应用软件。

OS/2的图形用户界面称为WorkPlace Shell。它使用面向对象的标记和拖放界面（在这一点上，Windows

试题分析-9

操作系统考研试题分析

NT也是）。用户可以对工具和文件夹进行个人化以简化对重要信息的访问。

【解答】 连线见下图：

3.4进程的描述与控制

●什么是进程控制块？试从进程管理、进程通信、中断处理、文件管理、存储管理、设备管理的角度设计进程控制块应包含的项目。（北京大学1999年试题）

【分析】

北京大学1990年、1992年、1995年、1997年都以名词解释的形式考查了PCB这一知识点。1999年再次考查这一知识点，并提高了考试要求，即要求理解PCB结构中各分量的含义。

熟记我们在前面列出的进程控制原语的形式描述有助于加深对这个题的理解。 【解答】

进程控制块（PCB）是为描述进程的运动变化过程而采用的一个与进程相联系的数据结构，用于记录系统管理进程所需的信息，描述进程的瞬间特征。它是进程的唯一实体，操作系统通过PCB而感知进程的存在。

为了完成进程管理、进程通信、中断处理、文件管理、存储管理、设备管理等各项任务，进程PCB结构必须如下项目：

①进程的标识符name：每个进程都必须有唯一的标识符，可以用字符或编号表示。在创建一个进程时，由创建者给出进程的标识，唯一地标识进程，与其他进程区别。

②进程当前运行状态status：说明本进程目前处于何种状态（运行、就绪、等待），作为进程调度时分配处理机的主要依据。

③当前队列指针next：登记了处于同一状态的下一个PCB的地址，以此将处于同一状态的所有进程链接起来。比如在一个就绪队列中，当前活动进程阻塞，则需要根据当前队列指针调度下一个就绪进程进入运行。

④总链指针all_q_next：将所有的进程链接起来，进程PCB中的该项内容总是指向总链中的下一个PCB地址。这在有的场合是很方便的，比如当创建一个进程时，需要判断创建者给出的标识符名是否唯一，此时沿总链往下查找就比较方便。

⑤程序开始地址start_addr：进程开始的地址。当一个进程被调度进入运行时，需要从此处获得进程开始地址。

试题分析-10

操作系统考研试题分析

⑥CPU现场保护区cpustatus：通常保护的信息有工作寄存器、指令计数器以及程序状态字等，供进程调度时使用。当一个进程由运行转入其他状态时，需要把这些信息保存起来。当一个进程投入运行时，又需要把这些内容写入相应的寄存器。同时进行中断处理也需要保存CPU现场。

⑦通信信息communication information：是指每个进程在运行过程中与别的进程进行通信时所记录的有关信息。

⑧家庭联系process family：有的系统允许一个进程创建自己的子进程，这样，会组成一个进程家庭。在pcb中必须指明本进程与家庭的联系，如它的子进程和父进程的标识符。

⑨占有资源清单own_resource，用于设备管理。

⑩进程优先级priority，在中断处理、进程调度过程中都需要比较进程之间的优先级。

上述项目是一般PCB结构应包含最基本内容。不同的操作系统所使用的PCB结构是不同的。在UNIX系统中，为完成存储管理、文件管理，还在PCB结构中设有i结点指针、主存地址、当前中断保护区内r0等内容。

●判断：进程是基于多道程序技术而提出来的。其最基本的特性是并发性和动态性；进程的执行也即在各种基本状态之间多次转换的过程。但只有处于就绪、阻塞、执行这3种状态的进程位于内存。（中科院软件所2000年试题）

【解答】

错误。①去掉并发性；②进程在新、死状态上只经过一次；③进程都在内存中。

●一个单CPU的操作系统共有n个进程，不考虑进程状态过渡的情况：（北京大学1995年试题） ①给出运行进程的个数。 ②给出就绪进程的个数。 ③给出等待进程的个数。 【分析】

单处理机在任一时刻只能处理一道程序，在不考虑状态过渡的情况下，任一进程只有3种状态，即运行、就绪和等待。但此时该系统其他条件未知（如资源分配情况），故无法确定就绪进程和等待进程的数目。

【解答】 ①1。 ②不一定。 ③不一定。

●填空：为了实现进程由等待状态转换成就绪状态的状态变化，操作系统应提供_______原语。（华中科技大学2001年试题）

【解答】 唤醒原语。

●什么是线程？试说明线程与进程的关系。（南京大学2000年试题） 【解答】

试题分析-11

操作系统考研试题分析

在引入线程的OS中，线程是进程中的一个实体，是被系统调度和分派的基本单位。

进程与线程既区别、又联系。进程是任务调度的单位，也是系统资源的分配单位；而线程是进程中的一条执行路径，当系统支持多线程处理时，线程是任务调度的单位，但不是系统资源的分配单位。每个进程至少有一个执行线程。

3.5同步、互斥与通信

●何谓临界区？下面给出的实现两个进程互斥的算法是安全的吗？为什么？（中国科学技术大学1998年试题）

#define TRUE;#define FALSE; int flag[2];

flag[0] = flag[1] = FALSE; enter-crtsec(i)int i;{ WHILE(flag[1-i]); flag[i] = TRUE;} leave-crtsec(i)int i;{ flag[i] = FALSE;} process i: /* i = 0 OR i = 1 */ ...

enter-crtsec（i）; /*进入临界区*/ IN CRTICAL SECTION Leave-crtsec（i）; /*离开临界区*/ ...

【解答】

一次仅允许一个进程使用的资源称为临界资源，在进程中对于临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自独立的速度向前推进。但由于它们共享某些临界资源，而产生了临界区问题。对于具有临界区问题的共行进程，它们之间必须互斥，以保证不会同时进入临界区。

这种算法是不安全的。因为，在进入临界区的操作enter-crtsec( )不是一个原子操作，如果两个进程同时执行完其循环（此前两个flag均为False），则这两个进程可以同时进入临界区。

●举例说明P、V操作为什么要求设计成原语（即对同一信号量上的操作必须互斥）。（北京大学1993年试题）

【分析】

这是一个概念题，要求考生对P、V操作有较深刻的理解。 【解答】

P操作的流程如下所示。

试题分析-12

操作系统考研试题分析

PROCEDURE P(S)BEGIN lock out interrupts; S := S-1; IF S < 0 THEN BEGIN

status(q) := blockeda; insert(Q，q); unlock interrupts; scheduler; END;

ELSE unlock interruptsEND;

设信号量S的初值为1，当一个P操作执行完\后，S的值为0，该P操作不应被阻塞。但若P操作不是一个原语，也就是说在一个P操作执行的过程中可以有另一个P操作同时在执行，假如第2个P操作在第1个P操作执行判断语句\前也执行了\操作，则这时的S值为-1。这时第一个P操作将会被阻塞。这样的P操作不符合P操作的语义。

同样地，对于V操作，其流程为： PROCEDURE V(S)BEGIN lock out interrupts; S := S + 1; IF S <= 0 THEN BEGIN remove(Q，R); status(R):= readya; insert(RL，R);

length(RL):= length(RL)+ 1; END;

unlock interrupts;END;

设信号量S的初值为-1，当一个V操作执行完\后，S的值为0，该V操作应该唤醒一个被P操作阻塞的进程。但若V操作不是一个原语，也就是说在一个V操作执行的过程中可以有另一个V操作同时在执行。假如第2个V操作在第1个V操作执行判断语句\前也执行了\操作，则这时的S值为1。这时第1个V操作将不再去唤醒被阻塞的进程。这样的V操作不符合V操作的语义。

同样地，当P操作的执行过程中插入了V操作，也会出现不符合原语语义的情况。例如，在P操作执行完\后，S的值为-1，经判断，该进程应该被阻塞。但若在进行判断后阻塞进程前执行完另外一个V操作，则该V操作并没有可以唤醒的被阻塞的进程。而当V操作执行完后继续执行P操作时，该P操作仍将阻塞该进程，这一进程将不被唤醒。

对于V操作的执行过程中插入了P操作，也会出现不符合原语语义的情况。例如，在V操作执行完\后，S的值为1，该进程无需唤醒其他进程。但若在进行判断前执行了一个P操作，则在后续操作中需要唤醒一个阻塞进程。

【扩展】

试题分析-13

操作系统考研试题分析

类似这一类有关概念的讨论，首先需要明确概念的定义，然后再进行讨论。在讨论的过程中，对可能发生的情况应分类讨论。论述要清楚。

●一个系统有多个进程（＞5）共同存在并同时工作，但只有5台磁带机。每个进程最多可以申请一台磁带机工作。编制了下列程序来管理磁带机：（北京大学1993年试题）

申请：

PROCEDURE get_tape(VAR x: integer); VAR i: integer;

tape_units: shared integer; wait_tape: shared boolean;

tape: shared ARRAY[0..4] OF integer; BEGIN wait_tape := true; P(S);

WHILE (wait_tape = true) DO BEGIN

IF tape_units > 0 THEN BEGIN

tape_units := tape_units-1; i := 0;

WHILE (i<=4) DO BEGIN

IF tape[i] = 0 THEN BEGIN x := i; tape[i] := 1; exit END; i := i + 1; END;

wait_tape := false; END; END; V(S); END;释放：

PROCEDURE release_tape(x: integer); VAR tape_units: shared integer; tape: shared ARRAY[0..4] OF integer; BEGIN

试题分析-14

操作系统考研试题分析

P(S);

tape_units := tape_units + 1; tape[x] := 0; V(S); END;

说明：

shared表示该变量为多个进程共享。 S为信号量，初值为1。 其他变量初值为： tape[i] = 0 （0≤i≤4） tape_units = 5 wait_tape = false 问：

①上述程序的问题在什么地方？ ②改正它。

【分析】本题考查了临界资源的属性。临界资源可以为多个进程共享、访问，必须是全部变量。 【解答】 程序的问题有：

（1）所有的共享变量应是全局变量，而非局部变量。 （2）wait_tape也应互斥共享，但在题中并未实现这一点。 改后的程序如下： BEGIN

Var tape_units:shared integer; tape: shared ARRAY[0..4] OF integer; wait_tape:shared integer; S: integer;

PROCEDURE get_tape(var x:integer); BEGIN var i: integer; P(S);

wait_tape:= true;

WHILE(wait_tape = true) DO

试题分析-15

操作系统考研试题分析

BEGIN

IF tape_units > 0 THEN

BEGIN

tape_units := tape_units - 1; i = 0;

WHILE(i <= 4) DO BEGIN x := i; tape[i] := 1; exit END; i := i + 1; END;

wait_tape := false; END; END; V(S); END;

PROCEDURE release_tape(x:integer); BEGIN P(S);

tape_units := tape_units + 1; tape[x] := 0; V(S); End;

试题分析-16

操作系统考研试题分析

3.6算法设计题

●进程A和B利用公共缓冲池交换数据。设缓冲池有N个缓冲块，进程A每次生成一个数据块存入一空缓冲区，进程B每次从缓冲池中取出一个满的缓冲块。试用信号量及P、V操作实现进程A和B的同步。（中山大学1996年试题）

【分析】

本题是标准的生产者－消费者问题。与上题相比，使用了多缓冲区，需要增加一个信号量。另外，环形缓冲池和环形队列管理也是考点之一。

【解答】

Var mutex，empty，full:semaphore:1，n，0; buffer : ARRAY[0..n-1] of item; in， out :integer:= 0，0; BEGIN COBEGIN: A: BEGIN L1: …

produce a date block; … P(empty); P(mutex); Buffer[in] := nextp; in : = (in + 1) mod n V(mutex); V(full); GOTO L1; END; B: BEGIN L2: P(full); P(mutex);

Nextpc := Buffer[out]; out : = (out + 1) mod n V(mutex); V(empty);

consume the item in nextc

试题分析-17

操作系统考研试题分析

GOTO L2; END;

GOTO L2; END; 【扩展】

此题应注意以下几点：

（1）在所有的程序中P(mutex)和V(mutex)应成对出现。

（2）对资源信号量empty和full的P、V操作也必须成对出现，但它们是处于不同的程序中，正是这一点保证了互斥共享。

（3）在每个程序中的P操作顺序不能颠倒，应先执行对资源信号量的操作，再执行对互斥信号量的操作，否则可能引起进程死锁。

●设有一个具有N个信息元素的环形缓冲区，A进程顺序地把信息写入缓冲区，B进程依次地从缓冲区读出信息。回答下列问题：（中国科学院软件研究所1996年试题）

①叙述A、B两进程的相互制约关系；②判别下列用P、V操作表示的同步算法是否正确？如不正确，试说明理由，并修改成正确算法。

VAR buffer: ARRAY 0..N-1 OF T; in，out: 0..N-1;VAR S1，S2: Semaphore; S1 := 0; S2 := N;in := out := 0; PROCEDURE A: BEGIN REPEAT 生产数据m; P(S2); Buffer(in) := m; in := (in + 1) MOD N; V(S1); forever END;

PROCEDURE B: BEGIN REPEAT V(S2); m := buffer(out); 消费m;

out := (out + 1) MOD N; P(S1); forever END;

试题分析-18

操作系统考研试题分析

【分析】

本题是一个标准的生产者--消费者问题。题中所给的算法与标准算法不同，但考生不能因此就说这个算法不正确。考生须仔细分析试题中所给出的算法。

在本题中，进程B在使用缓冲区前（读缓冲区）无需进行任何P操作，即进程B不会因任何原因被阻塞。这与题目中的控制要求不相符。因此这个算法实现是错误的。此外，对缓冲区的访问也没有用互斥信号量进行控制。

【解答】

①A和B两进程的相互制约关系如下：

当缓冲区满时，A进程不可以写，必须等待；当缓冲区空时，B进程不可以读，必须等待。 ②该算法有错，它对读进程进入临界区未加限制。当缓冲区为空时，也可以进入临界区读信息。当存在多个读进程和多个写进程时，还需要引入一个信号量S0以防止同时读或同时写。

改进后的算法如下：

VAR buffer: ARRAY 0..N-1 OF T;

in，out: 0..N-1;VAR S0，S1，S2: Semaphore; S0 := 1; S1 := 0; S2 := N;in := out := 0; PROCEDURE A: BEGIN REPEAT 生产数据m; P(S2); P(S0); Buffer(in) := m; in := (in + 1) MOD N; V(S0); V(S1); forever END;

PROCEDURE B: BEGIN REPEAT P(S1); P(S0); m := buffer(out); out := (out + 1) MOD N; V(S0); V(S2); 消费m; forever

试题分析-19

操作系统考研试题分析

END;

【扩展】

本题是一类判别错误和改错题。这类题目一般是用来检查考生对一些典型算法的掌握程度的。在本题中，是考查考生对生产者－消费者问题的掌握。解答这类问题时，首先需要对标准算法熟练掌握，其次，还需对算法的变化做到心中有数。不要把正确的变化列为出错点。例如本例中，如果题目中的算法给出的V操作顺序与标准算法不同，考生则不能认为其解答是错误的。因为在控制算法中，V操作的顺序不会影响算法的正确性。

●今有3个并发进程R、M和P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成\，\；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用P、V操作为同步机制写出它们能正确并发执行的程序。（南京大学1997年试题）

【分析】

此题是3个进程之间的同步问题。显然R与M、R与P、P与M之间均应有一缓冲区指针。与之对应有3个信号量。

【解答】

Var full，changed，empty，mutex:integer; Var fullP，changedP，emptyP:integer; Var ch:char ;

Var charray ARRAY[0..n] of char; fullP:= 0; emptyP:= 0; changedP:= 0; full := 0; empty := n; changed := 0; mutex := 0; R: BEGIN getchar(ch); P(Empty); P(mutex); charray[fullP] :=ch; fullP := (fullP + 1) mod n; V(mutex);

V(changed); END;

试题分析-20

操作系统考研试题分析

M: BEGIN P(changed); P(mutex);

ch := charray[changedP]; if ch = ' ' then ch = ',';

changedP := (changedP + 1) mod n; V(full); V(changed); END; P: BEGIN P(full); P(mutex);

ch := charray[emptyP]; putchar(ch);

emptyP := (emptyP + 1) mod n; V(mutex); V(empty); END;

【扩展】

本题在进程同步之外，还考查了考生基本编程能力及环形队列操作。考生应该注意这个信号。尽管P、V操作本身已有一定难度，但仍然存在结合其他知识点命题，以进一步增加难度的可能。

我们可以列举一些知识点综合的方向。比如说，在读者－写者问题中，可以结合UNIX文件系统附带考查文件打开、关闭等操作；可以把P、V操作和实际的资源管理问题结合起来，等等。

●多个进程共享一个文件，其中只读文件的称之为读者，其余只写文件的称为写者。读者可以同时读，但是写者只能独立地写。（中科院软件所1995年试题）

①说明进程间的相互制约关系，应设哪些信号量？ ②用P、V操作写出其同步算法。

③修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者都必须等待，而无论是否有读者在读文件。

【分析】

本题要求写出的算法与前面的题目略有不同。这里的两类进程（读者和写者进程）的控制是不相同的。对于写者进程，只能独占文件，即当有写者进程时不能有其他进程运行；对于读者进程，可以与其他的读者进程共享文件，即当有读者进程的，只允许其他的读者进程运行，而不允许写者进程运行。此外，当全部正在运行的读者进程运行完毕后，才允许其他的写者进程进入。

为了达到这一控制效果，我们引入了一个变量rc，用于记录当前正在运行的读者进程数。每个读者进

试题分析-21

操作系统考研试题分析

程进入系统后须对rc值加1。当rc值由0变为1时，说明是第一个读者进程进入，因此需要该读者进程对控制写者进程的信号量进行P操作，以便与写者进程互斥运行；当rc值由非0值增加时，说明不是第一个读者进程，此时控制写者进程的信号量已经过P操作控制禁止写者进程进入，因此不需要再次对该信号量进行P操作。

当读者进程退出时，须对rc做减1操作。如发现减1后rc值变为0，说明是最后一个读者进程退出，因此需要该读者进程对控制写者进程的信号量进行V操作，以便使写者进程能够进入。

【解答】

①进程间的相互制约关系有三类。一是读者之间允许同时读；二是读者与写者之间须互斥进行；三是写者之间须互斥写。

②进程间的控制算法如下所示。 BEGIN

integer mutex1，mutex2，rc;

mutex1 := 1; mutex2 := 1; rc := 0;

COBEGIN reader: BEGIN P(mutex1); rc := rc + 1;

IF rc = 1 THEN P(mutex2); V(mutex1); Reading the file; P(mutex1); rc := rc-1;

IF rc = 0 THEN V(mutex2); V(mutex1); END; writer: BEGIN P(mutex2); Writeing the file; V(mutex2); END; COENDEND;

③为了提高写者的优先级，我们增加一个信号量w，用以在写进程到达时封锁后续的读者进程。相应的控制算法如下：

BEGIN

试题分析-22

操作系统考研试题分析

integer mutex1，mutex2，rc，w;

mutex1 := 1; mutex2 := 1; rc := 0; w := 1;

COBEGIN reader: BEGIN P(w); P(mutex1); rc := rc + 1;

IF rc = 1 THEN P(mutex2); V(mutex1); V(w);

Reading the FILE; P(mutex1); rc := rc-1;

IF rc = 0 THEN V(mutex2); V(mutex1); END; writer: BEGIN P(w); P(mutex2); Writeing the FILE; V(mutex2); V(w); END; COENDEND;

【扩展】

对于可由一类进程多次访问，而不同类的进程必须互斥访问的资源的控制，是进程控制中常见的一类问题。本题是这类问题中的一个典型，它给出了对于这类资源的控制方法，即采用一个资源计数变量rc进行控制。把对于该资源的访问控制变成对变量rc的访问。这时，资源计数变量rc是一个临界资源，需要用信号量对其进行访问控制。

●有桥如图所示。（北京大学1992年试题）

试题分析-23

操作系统考研试题分析

车流如箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通行（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上堵塞。

【分析】

由于桥上不允许两车相会，故桥应被互斥访问，而同一方向上允许多辆车依次通过，即临界区允许多个实例访问。用一个信号量来互斥访问临界区。由于不能允许某一方向的车完全\控制\桥，应保证最多某一方向上连续通过一定数量的车后，必须让另一方向上的车通过。用另两个信号量来实现这一点。

【解答】 BEGIN

Var integer mutex ，availn ，avails; availn = m; avails = m; mutex = 0; COBEGIN South:BEGIN L1: P(avails); P(mutex); Cross the bridge; V(mutex); V(availn); END; North: BEGIN L1: P(availn); P(mutex); Cross the bridge; V(mutex); V(avails); END; COEND; END;

试题分析-24

操作系统考研试题分析

【扩展】

在解此类题目时，首先应分析清楚此题的临界区是什么，题目对临界区的共享的约束条件是什么，再分析应设几个信号量，各信号量的作用是什么。当所有问题都分析清楚之后再做题。另外当遇到实际问题时，根据实际情况，注意分析是否应补充约束条件。在实际考试中最好把所有分析过程、补充的约束条件写出，一方面帮助解题，一方面帮助老师阅卷。

3.7进程通信

●图所示的是高级通信原语SEND和RECEIVE不完整的框图。请填充适当的P、V操作，并说明所用信号量的意义和初值。（中国科学院软件研究所1994年试题）

【分析】

本题是一个生产者－消费者问题，与标准的生产者－消费者问题的不同之处在于本题的消息缓冲区的个数是无限制的，因此，不需要生产者－消费者问题解答中的信号量avail。在框图中所给出的信号量就是控制消息个数的信号量full。为了正确地控制程序流程，我们还要加入对应于生产者－消费者问题中的信号量mutex，以控制对消息链的互斥访问。

【解答】

框图中所缺的步骤如下： ① P(S1) ② V(S1) ③ P(S2) ④ P(S1) ⑤ V(S1)

其中，S1是用于控制互斥访问消息链的互斥信号量，其初值为1；S2是用于记录消息个数的同步信

试题分析-25

操作系统考研试题分析

号量，其初值为0。

●消息缓冲通信技术是一种高级通信机制，由Hansen首先提出。（北京大学1997年试题） ① 试叙述高级通信机制与低级通信机制P、V原语操作的主要区别。 ② 请给出消息缓冲机制（有界缓冲）的基本原理。

③ 消息缓冲通信机制（有界缓冲）中提供发送原语Send（receiver，a），调用参数a表示发送消息的内存区首地址，试设计相应的数据结构，并用P、V原语操作实现Send原语。

【解答】

① P、V操作是一种低级通信机制，它们作为同步工具用在进程同步和互斥上是非常有效的，但是作为通信工具，则不够理想。而高级通信机制是指用户可直接利用操作系统所提供的一组通信命令，高效传送大量数据的一种通信方式。二者的主要区别如下：

P、V操作效率较低。 通信对用户不透明。

② 消息缓冲通信机制，首先由美国的Hansan提出，并在RC4000上实现。在这种通信机制中，发送进程利用Send原语，将消息直接发送给接收进程。接收进程利用Receive原语接受消息。该机制主要利用的数据结构是消息缓冲区。

发送进程在利用发送原语发送消息前，在自己的内存空间里设置一发送区，把待发送的正文、发送进程标志符、消息长度等信息填入，然后调用发送原语，把消息发送给目标进程。发送原语首先根据发送区中设置的长度来申请一个缓冲区i，接着把发送区中的正文信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列上，应先获得接收进程的内部标志符。由于该队列属于临界资源，应执行同步操作。

接收进程调用接收原语receive()，从自己的消息缓冲队列中，摘下第一个消息缓冲区i，并将其中的消息正文拷贝到指定的消息接收区内。

③ 消息缓冲区可描述为： type message buffer = record sender; 发送者进程标志符 size; 消息长度 text; 消息正文

next; 指向下一个消息缓冲区的指针 end; 发送原语：

PROCEDURE send(receive，a) //接收进程标志receive， 发送区a BEGIN getbuf(a.size，i); i.sender := a.sender; i.size := a.size; i.text := a.text; i.next := 0;

getid(PCB.set，receive.j);

试题分析-26

操作系统考研试题分析

P(j.mutex); insert(j.mq，i); V(j.mutex); V(j.sm); END; 接收原语：

PROCEDURE receive(b) //发送区b BEGIN j:= internal name; P(j.sm); P(j.mutex); remove(j.mq，i); V(j.mutex); b.sender: = i.sender; b.size:= i.size; b.text:=i.text; END;

3.8进程调度

●设某系统进程的状态除了最基本的三种状态外，还增加了创建状态、延迟状态和完成状态。试画出系统的进程状态变迁图，并标明状态变迁可能的原因。（华中科技大学2001年试题）

【解答】

进程状态变迁图及可能的原因如图所示：

试题分析-27

操作系统考研试题分析

3.9死 锁

●用信号量及P、V操作解生产者-消费者问题，并改动操作使之产生死锁。（南开大学1995年试题） 【分析】

本题是关于P、V操作及生产者－消费者问题的一个基本问题。在这里主要考查考生对生产者－消费者问题的理解和对死锁问题的理解。

【解答】

生产者-消费者问题的流程如下： BEGIN integer mutex, avail, full; mutex := 1; avail := n; full := 0;

COBEGIN producer: BEGIN L1: produce next product; P(avail); P(mutex); add TO buffer; V(full); V(mutex); goto L1; END;

consumer: BEGIN L2: P(full); P(mutex); take from buffer; V(avail); V(mutex); consume product; goto L2; END; COEND END;

要使该操作产生死锁，只需改动P操作的顺序。能产生死锁的操作流程如下：

BEGIN integer mutex, avail, full;

试题分析-28

操作系统考研试题分析

mutex := 1; avail := n; full := 0; COBEGIN producer: BEGIN L1: produce next product; P(mutex); P(avail); add TO buffer; V(full); V(mutex); goto L1; END;

consumer: BEGIN L2: P(mutex); P(full); take from buffer; V(avail); V(mutex); consume product; goto L2; END; COEND END;

在这个流程里，由于生产者和消费者在生产和消费之前都要对信号量mutex进行P操作，所以，会导致生产者进入临界区后（对mutex进行P操作后），因无缓冲区而被阻塞；消费者由于无法进入临界区，无法释放缓冲区，从而导致死锁。同样地，当消费者进入临界区后（对mutex进行P操作后），由于无产品可供使用被阻塞；而生产者由于无法进入临界区，无法生产产品，从而导致死锁。

【扩展】

产生死锁是在用信号量进行流程控制过程中常会遇到的一个问题。何时会发生死锁。如何避免死锁，是在考研中常考的问题。在本题中，要求用经典的生产者-消费者问题构造出死锁现象，是一种常见的题型。此外，还会有要求分析给定流程控制是否会产生死锁等类似的问题。

●用信号量及P、V操作解生产者-消费者问题，并改动操作使之产生死锁。（南开大学1995年试题） 【分析】

本题是关于P、V操作及生产者－消费者问题的一个基本问题。在这里主要考查考生对生产者－消费者问题的理解和对死锁问题的理解。

【解答】

试题分析-29

操作系统考研试题分析

生产者-消费者问题的流程如下： BEGIN integer mutex, avail, full; mutex := 1; avail := n; full := 0; COBEGIN producer: BEGIN L1: produce next product; P(avail); P(mutex); add TO buffer; V(full); V(mutex); goto L1; END;

consumer: BEGIN L2: P(full); P(mutex); take from buffer; V(avail); V(mutex); consume product; goto L2; END; COEND END;

要使该操作产生死锁，只需改动P操作的顺序。能产生死锁的操作流程如下：

BEGIN integer mutex, avail, full; mutex := 1; avail := n; full := 0; COBEGIN producer: BEGIN L1: produce next product; P(mutex); P(avail); add TO buffer; V(full);

试题分析-30

操作系统考研试题分析

V(mutex); goto L1; END;

consumer: BEGIN L2: P(mutex); P(full); take from buffer; V(avail); V(mutex); consume product; goto L2; END; COEND END;

在这个流程里，由于生产者和消费者在生产和消费之前都要对信号量mutex进行P操作，所以，会导致生产者进入临界区后（对mutex进行P操作后），因无缓冲区而被阻塞；消费者由于无法进入临界区，无法释放缓冲区，从而导致死锁。同样地，当消费者进入临界区后（对mutex进行P操作后），由于无产品可供使用被阻塞；而生产者由于无法进入临界区，无法生产产品，从而导致死锁。

【扩展】

产生死锁是在用信号量进行流程控制过程中常会遇到的一个问题。何时会发生死锁。如何避免死锁，是在考研中常考的问题。在本题中，要求用经典的生产者-消费者问题构造出死锁现象，是一种常见的题型。此外，还会有要求分析给定流程控制是否会产生死锁等类似的问题。

●分析下面信号量解决哲学家进餐问题的同步算法是否满足同步机制的准则。若不满足，说明为什么，并给出满足同步机制准则的同步算法。(中科院软件所1998年试题)

VAR fork: ARRAY[0..4] OF semaphore;

fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1; PARBEGIN

Pi: REPEAT /* 第i个哲学家的生活过程 */ Think FOR While; P(fork[i]);

P(FOR[(i+1) MOD 5]); Eat FOR WHILE; V(fork[i]);

V(fork[(i+1) MOD 5]); UNTIL false PAREND

试题分析-31

操作系统考研试题分析

【分析】

哲学家进餐问题是进程同步与互斥中的一个典型问题。本题要求分析算法是否满足同步机制的准则，即每次至多有一个进程进入临界区，进程应在有限时间内进入临界区，进程在临界区内停留有限时间。本题所给出的算法会在特定情况下产生死锁，因此无法满足同步机制的准则中的\有限等待\准则。为了解决这一问题，我们可以用额外的信号量来控制对临界资源的访问，避免死锁 。

【解答】

上述同步算法不满足同步机制的准则中的\有限等待\准则。当每个哲学家都只拿到一把叉子时，发生死锁。

一种改进的算法如下：

VAR fork: ARRAY[0..4] OF semaphore; VAR mutex: semaphore;

fork[0] := fork[1] := fork[2] := fork[3] := fork[4] := 1; mutex := 1;

PARBEGIN

Pi: REPEAT /* 第i个哲学家的生活过程 */ Think For While; P(mutex); P(fork[i]);

P(FOR[(i+1) MOD 5]); V(mutex); Eat FOR WHILE; V(fork[i]);

V(fork[(i+1) MOD 5]); UNTIL false PAREND

【扩展】

哲学家进餐问题是进程同步与互斥中的一个典型问题。对于这一问题，避免死锁有多种方式。本题给出的方法是对资源申请的过程进行限制，即要求一次申请完所有的资源，也就是在申请两个资源的过程中不被其他进程打断，且在系统满足该进程要求之前别的进程无法申请资源。这样，就可以避免死锁。

此外，我们还可以对申请资源（叉子）的进程（哲学家）进行限制，即要求相临的两个哲学家不能同时申请。这样，在进程（哲学家）申请资源（叉子）时就不会申请不到了。

●写出两种检测进程死锁的方法及相应的结论（或定理）。(南开大学1998年试题) 【分析】

本题是一个基本问题，对于进程死锁的检测在教科书中已有明确的方法，考生须掌握教科书中的方

试题分析-32

操作系统考研试题分析

法与结论，并给出一个清晰明确的解答。

【解答】

进程死锁的检测有多种方法，这里给出两种方法：利用化简进程－资源有向图的方式进行死锁的检测和采用矩阵表示法进行死锁的检测。

（1）利用化简进程－资源有向图的方式进行死锁的检测利用化简进程－资源有向图的方式，可以检测出系统的某一状态S是否处于死锁状态，其化简方式如下：

①从有向图中找到既不阻塞又非孤立的结点进程Pi。在顺利的情况下，Pi可以获得它所需要的资源不断向前推进，直至运行完毕。然后释放它所占有的全部资源而处于潜伏状态，这相当于在图上消去Pi所有的请求边和分配边，使之成为孤立结点。

②进程Pi所释放的资源可以唤醒某些因等待该资源而被阻塞的进程Pj，在顺利的情况下，Pj又可以获得它所需要的资源继续推进，直至进行完毕，然后释放它所占有的全部资源，而处于潜伏状态。这相当于在图上消去Pj所有的请求边和分配边，使之成为孤立结点。

③在实施了上述的一系列化简步骤后，若消去图中所有的边，则称该图是可完全化简的。 ④若有向图不能通过任何进程予以化简，则称该图是不可化简的。

有关文献已经证明：给定进程－资源图的所有化简顺序将导致相同的不可化简图。列锁定理给出结论，S为死锁状态的充分条件是：当且仅当S状态的资源－进程图是不可完全化简的。

采用这种方式，通过化简进程－资源图，就可以检测系统的某一状态是否处于死锁状态。 （2）采用矩阵表示法进行死锁的检测采用矩阵表示法进行死锁的检测，它是通过系统在某一状态的资源分配矩阵和在这一状态时的资源请求矩阵进程来判定系统是否处于死锁状态。 设系统中有n个进程P1，P2，P3，…，Pn和m种类型的资源R1，R2，R3，…，Rm，一个类型的资源数目分别为W1，W2，W3，…，Wm，可表示为资源数目向量W。在任一时刻t，资源分配矩阵可表示为：

其中，元素a(i, j)表示分配给进程Pi的资源Rj的数目。行向量Ai表示进程Pi所获得的全部资源。请求矩阵可表示为：

其中，元素b(i, j)表示进程Pi所请求的资源Rj的数目。行向量Bi表示进程Pi所请求的资源总数。又定义可用资源向量为：

V = (v1，v2，…，vm)其中，元素vj = Wj-∑aij

试题分析-33

操作系统考研试题分析

采用矩阵表示法时，检测死锁的算法可描述为： 把某时刻t的可用资源向量V(t)赋予资源数目向量W。 把不占用资源的行向量Ai = 0记入表L中。

对所有请求各种资源的数量均小于相应资源现有数目的第j行做如下处理：将其进程－资源有向图化简，释放出资源，使可用资源数目增加，此时第j行已不再占有资源，将其记入L表中。

最后，若不能把所有的行都记入L表中，则初始状态将发生死锁。 【扩展】

对于死锁的检测还有一些其他方法，如队列表示法等。在这里我们简要介绍队列表示法。 把分配给进程Pi的资源链接到Pi进程，由此可写出分配队列如下：

P1 → (R1, a11) → (R2, a12) → … → (Rm, a1m); P2 → (R1, a21) → (R2, a22) → … → (Rm, a2m);

…

Pn → (R1, an1) → (R2, an2) → … → (Rm, anm)。

此外，把请求资源Rj的进程链接在一起，如下：

R1 → (P1, b11) → (P2, b21) → … → (Pn, bn1); R2 → (P1, b12) → (P2, b22) → … → (Pn, bn2);

…

Rm → (P1, b1m) → (P2, b2m) → … → (Pn, bnm)

其中，aij和bij的含义和矩阵表示法相同。这里也可以引入Ai(t)来表示进程Pi的资源分配向量，Bi(t)为进程Pi的资源请求向量，而且可写出完全类似的死锁检测算法。

●某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见表2.2，此刻系统的可用资源向量为（2, 1, 2），问题：(中科院软件所1999年试题)

①将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；②如果此时P1和P2均发出资源请求向量Request(1, 0, 1)，为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因；③如果②中两个请求立刻得到满足后，系统此刻是否处于死锁状态？

【解答】

①系统资源总数向量为（9, 3, 6） 各进程对资源需求矩阵为：

试题分析-34

操作系统考研试题分析

②采用银行家算法进行计算分析可知：

系统可以满足P2进程对资源的请求，将资源分配给P2之后，至少可以找到一个安全的执行序列，如（P2, P1, P3, P4）使各进程正常运行终结。

系统不可以将资源分配给进程P1，虽然可利用资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各进程能够正常运行终结。所以进程P1应该进入阻塞状态。

③系统满足进程P1和P2的请求后，并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态。

3.10作业调度

●现有如下作业序列：作业1（提交时间8.00，运行时间1.00）；作业2（提交时间8.30，运行时间3.00）；作业3（提交时间9.00，运行时间0.10）；作业4（提交时间9.30，运行时间0.50）（单位：小时，以十进制计）。 试用先来先服务和短作业优先调度算法处理该作业序列，问哪种作业调度算法性能更好（要求给出计算的数据和必要的步骤）。(华中科技大学2001年试题)

【分析】

本题是作业调度算法应用的基本题目。解题时按照所采用的调度策略进行计算。注意各个作业之间的切换顺序，计算时要细心，以免出错。

【解答】

先来先服务调度算法：

8.00作业1到达，开始运行；8.30作业1运行0.30小时；作业2到达，等待调入系统；9.00作业1运行1.00小时，运行结束；作业2较作业3先到达，开始运行；作业3到达；9.30作业2运行0.30小时，继续运行；作业3等待调入系统；作业4到达，等待调入系统；12.00作业2运行3小时，运行结束；作业3先到达，开始运行；作业4等待调入系统；12.10作业3运行0.10小时，运行结束；作业4开始运行；12.60作业4运行0.50小时，运行结束。 该调度算法下：平均周转时间

带权平均周转时间

短作业优先算法的运行情况见表:

试题分析-35

操作系统考研试题分析

该调度算法下：平均周转时间 带权平均周转时间

由以上两种算法下得到的结果来看，短作业优先算法优于先来先服务算法。 简答题：

什么是高级调度、中级调度和低级调度？(北京大学1991年试题) 【分析】

\三级调度\之间有区别，但更有联系。举例来说，用户以作业的形式向操作系统提交任务，系统完成这一调度即为\高级调度\；作业进入系统，要建立相应的进程，参与CPU的竞争，才能被执行，这里又用到\进程调度\（关于\进程调度\，不光有用户进程，还有系统进程）；同时，为了提高系统吞吐量，又出现了\中级调度\的概念。因此，真正理解这三级调度，对于掌握作业管理、调度，是非常重要的。

【解答】

作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，将经历如下三级调度。 （1）高级调度。这又称为作业调度。用于决定把外存中处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。

（2）低级调度。这又称为进程调度。它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度可以采用抢占方式和非抢占方式。

（3）中级调度。中级调度的主要目的是为了提高内存的利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存，而将它们调度到外存上去等待。当内存有空闲时，又将外存上的具有运行条件的就绪进程重新调入内存。

●某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：(南京大学1999年试题)

J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms).

处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题： （1）分别计算作业J1、J2和J3从开始到完成所用的时间。 （2）3个作业全部完成时CPU的利用率。 （3）3个作业全部完成时外设IO1的利用率。 【分析】

试题分析-36

操作系统考研试题分析

如前说述，本题在多道系统中的三个进程不仅要竞争使用处理机，而且还要竞争使用外设，这使得进程之间的关系更加复杂。另一方面，本题为了突出进程对CPU和外设的使用，弱化了作业调度的处理，因此题目中已假设这三个进程都已经装入主存，从这一点看，又降低了本题的难度。分析过程如图4.2所示（图中水平箭头表示实际执行过程，水平虚线表示等待过程）。进程运行示意图：

【解答】

（1） 由上图可知：J1从开始到完成的时间是0～80msJ2从开始到完成的时间是0～90msJ3从开始到完成的时间是0～90ms

（2） 三个作业全部完成时CPU的利用率是：

（3） 三个作业全部完成时外设IO1的利用率是：

3.11存储管理

●判断正误：虚地址即程序执行时所要访问的内存地址。(清华大学1998年试题) 【分析】

本题考查程序执行过程中访问虚地址和实地址的区别。要认识到，在用户程序中访问的地址是虚地址（逻辑地址），而系统在具体执行指令，取数据时，要把虚地址转换为实际的实地址。

【解答】

这句话是错误的。在虚拟存储系统中虚地址是一种逻辑意义上的地址，而不是真正的物理地址。当用户实际需要使用该虚地址中的程序或数据时，操作系统将进行地址变换，去具体查找该地址中的程序或数据。但在具体查找之前，操作系统并不知道该虚地址中的程序或数据具体在快表、内存、外存中哪里。所以认为虚地址是内存地址是错误的看法。

试题分析-37

操作系统考研试题分析

●在存储管理中，覆盖和对换技术所要解决的是什么问题？各有什么特点？(中国科学技术大学1996年试题)

【解答】

覆盖技术和交换技术是在多道环境下用来扩充内存的两种方法。这两种技术都是用来解决内存容量不足及有效利用内存的问题的方法。覆盖技术主要用于早期的操作系统中。而交换技术在现代操作系统中仍有较强的生命力。

覆盖技术是基于这样的一种思想提出来的，即一个程序不需要把所有的指令和数据都装入内存。可以把程序划为若干功能上相对独立的程序段，让那些不会同时执行的程序段共享一块内存。这样使用户看起来好像内存扩大了，从而达到了内存扩充的目的。

对换是指先把内存中某部分的程序或数据写入外存，再从外存中调入指定的程序或数据到内存中来，并让其得到执行的一种内存扩充技术。

覆盖技术要求程序员提供一个清楚的覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。这对程序员的要求较高。因此覆盖技术大多用在像操作系统程序等设计人员清楚地了解虚空间和内部结构的程序中。

而交换技术并不要求程序员做特殊的工作。交换完全由操作系统进行，整个过程对进程是透明的。而且交换技术主要是在进程或作业之间进行，而覆盖则主要是在同一个作业或进程内进行。另外覆盖技术只能用于处理相互之间较为独立的程序段。

●交换扩充了主存，因此，交换也实现了虚拟存储器，对吗？(清华大学1995年试题) 【分析】

该命题前后两部分都不妥当。交换技术是实现虚拟存储器的重要手段，能够在逻辑上扩充内存容量，但并不能简单说交换扩充了主存，事实上，计算机硬件的主存空间大小是不变的。另外，虽然交换是实现虚存的重要技术，但不是唯一条件，读者要清楚这一点。

【解答】 这种说法不正确。

交换是指把内存中暂不能运行的进程或暂时不用的程序和数据换出到外存上，以释放出足够的内存空间，把已具备运行条件的进程或进程所需的程序（数据）换入内存。交换是提高内存利用率的有效措施。

虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统，是指具有请求调入功能和置换功能、能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储系统的实现，毫无例外的都是建立在离散分配存储管理方式的基础上的。

虽然交换能提高内存利用率，但仅使用交换技术，仍然无法实现仅把作业的一部分装入内存便可运行作业，故交换并不能实现虚拟存储器。

●分区式管理时，主要使用的有关数据结构有哪些？常用哪几种方法寻找和释放空闲区？这些方法各有何优缺点？(清华大学1998年试题)

【解答】

为了实现分区式管理，系统中必须配置相应的数据结构，用来记录内存的使用情况，为分配内存提供依据。常用的数据结构为：

试题分析-38

操作系统考研试题分析

（1）空闲分区表。该表用于为内存中每个尚未分配出去的分区设置一个表项，每个分区的表项包含分区序号、分区始址、分区大小等表项。

（2）空闲分区链。为实现对空闲分区的分配和连接，在每个分区的起始部分，设置一些用来控制分区分配的信息以及用于连接各分区的前向指针。在分区的尾部则设置一个后向指针，将所有的分区联结成一个双向链。

通常使用的分配算法及优缺点如下：

（1）首次适应算法。使用该算法进行内存分配时，从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。

该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。

（2）循环首次适应算法。该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至找到一个能满足要求的空闲分区，并从中划出一块来分给作业。该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。

（3）最佳适应算法。该算法总是把既能满足要求，又是最小的空闲分区分配给作业。

为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但事实上并不一定。因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。

（4）最差适应算法。最差适应算法中，该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。这种分配方法初看起来不太合理，但它也有很强的直观吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。

最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。

该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。

●采用可变分区方式管理主存时，引入移动技术有什么优点？在采用移动技术时应注意哪些问题？(南京大学1997年试题)

【分析】

在可变式分区管理中，一个重要的问题就是碎片问题。在整个系统运行一段时间后，可能会出现这样的情况：分布在主存各处的破碎空闲区占据了相当数量的空间，当一个作业申请一定数量的主存时，虽然此时空闲区的总和大于新作业所要的主存容量，但却没有单个的空闲区大到足够能装下这个作业。解决这个问题的办法就是采用移动（拼接）技术。移动技术涉及到移动的时机问题，这样系统的开销也不尽相同。

【解答】

试题分析-39

操作系统考研试题分析

在连续分配方式中，存在大量不能被利用的小分区。设想我们有4个不相邻接的小分区，其大小分别为10kB、20kB、15kB、25kB。此时如有一个作业为40kB，则虽然总的空闲存储空间是够的，但仍然无法装入作业。为了利用这些空间，可采取的一种方法是将内存中的作业进行移动，使所有的、分散的小分区拼接成一个大分区，从而可以将作业装入该大分区。这就是引入移动技术的优点。需要注意的问题是由于移动后用户程序在内存中的位置发生了变化，如不对用户程序和数据的地址进行修改，则程序将无法执行。为使之能执行，必须进行重定位。即在系统中增加一个重定位寄存器，用它来装入程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

●某个操作系统采用可变分区分配方法管理，用户区主存512kB，自由区由可用空区表管理。若分配时采用分配自由区的低地址部分的方案，假设初始时全为空。对于下述申请次序：(复旦大学1997年试题)

req(300kB), req(100kB), release(300kB), req(150kB), req(30kB), req(40kB), req(60kB)回答下列问题： （1）采用首次适应（FF），自由空区中有哪些空块（给出地址、大小）？ （2）若采用最佳适应（BF），回答（1）中的问题。 （3）如果再申请90kB，针对（1）和（2）各有什么结果？ 【分析】

本题与上面的例题是相同的类型，只要掌握各种分配策略，此类题目应属得分题。但在解题过程中注意计算的准确性，利用图示做参考不失为好办法。

【解答】

（1）采用首次适应算法，自由空区中有两块空块：（280－1kB，20kB），(400－1kB,112kB)。 （2）若采用最佳适应算法，自由区空中有两块空块：（100－1kB，200kB），（492－1kB,20kB）, （3）若再申请90kB，对（1）中的首次适应算法，第二块空块可以满足分配。对（2）中的最佳适应算法，第一块空块可以满足分配。

●判断：在请求分页系统中，为了实现请调一页的功能，在页表中必须增加二个数据项，它们是中断位I和访问位。(华中科技大学1995年试题 )

【分析】

请调系统中系统必须解决如下两个问题：（1）怎样发现所访问的页面在不在主存？（2）若要访问的页面不在主存时如何处理？

解决第一个问题就是如何请调一页，必须在每个页表表目中再增加两个数据项：中断位I和该页面在辅存的位置。若I=1，表示此页不在主存；若I=0，表示该页在主存。

解决第二个问题，就是要决定哪些页面可被淘汰掉，即置换算法问题。为了给置换页面提供依据，页表中还必须包含关于页面的使用情况的信息，因此，在页表中增加\引用位\和\改变位\。\引用位\是用来指示某页是否被访问过：为1表示已被访问过，为0表示未被访问过。\改变位\表示某页是否被修改过：为1表示已被修改过，为0表示未被修改过。

【解答】

错。应为中断位和辅存地址。 【扩展】

这一道判断题，看似简单，但它要求对请求调页管理系统所用到的数据结构非常清楚，对这些数据

试题分析-40

操作系统考研试题分析

结构的作用以及表示的含义准确掌握。实际上，这些数据结构都是在为了解决调页过程中出现的问题而提出的，正如在分析中提出的两个问题。所以在复习的时候，不仅要牢固掌握一般性的原理，还要深入背后研究它产生的背景，这样才能透彻理解。

只要掌握本题涉及的相关内容，就不难回答下面的题目：(华中科技大学2001年试题)填空：在请求分页系统中，引用位标识（ ），它的用途是（ ）。

解答：该页面最近是否被访问过；为置换页面提供依据。

从这两道题目不难看出，该知识点是华工的常考之处，报该校的考生应引起重视。

●简述LRU、NRU和LFU这3种页面置换算法的思想，并各给出一种可能的实现方案。(中国科学技术大学1998年试题)

【解答】

LRU算法利用\最近的过去\作为\最近的将来\的近似，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面淘汰。

LFU算法选择在最近时期使用最少的页面作为淘汰页。采用该算法时，应为内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问该页时，将该页寄存器的最高位置1，再每隔一段时间右移一次。需要指出的是该算法并不能反映出页面的真正使用情况，因为在一定的时间间隔里，只用寄存器的1位来记录页面的使用情况，因此在一定的时间间隔里，访问1次和访问1000次是等效的。

NRU算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访问时，访问位置1。系统周期性地对所有的引用位清零。当需要淘汰一页时，从访问位为0的页中选一页即可。

●设正在处理器上执行的一个进程的页表见表5.1，表中的虚页号和物理块号是十进制数，起始页号（块号）均为0，所有的地址均是存储器字节地址，页的大小为1024B。(中国科学院计算技术研究所1999年试题)

（1）详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 （2）下列虚地址对应于什么物理地址：5499，2221。

【解答】

（1）当进行地址变换时，首先去检索快表，试图从中找出所要访问的页。如找到，便修改页表项中的访问位。对于写指令，还需将修改位置为\，然后利用页表项中给出的物理块号和页内地址，形成物理地址。

如在快表中未找到该页的页表项，则应到内存中去查找页表，在从找到的页表项中的状态位来了解

试题分析-41

操作系统考研试题分析

该页是否已调入内存。其结果可能是：

①该页已调入内存，此时应将该页的页表项写入快表，当快表已满时，应调出按一定算法确定的页的页表项，然后再写入该页的页表项。

②该页尚未调入内存，此时产生缺页中断，请求操作系统从外存中把该页调入内存。

（2）5499 = 1024 * 5 + 379，故虚地址5499所对应的虚页号为5，页内地址为379。由题中附表知虚页号5对应的物理块号为0，所以虚地址5499所对应的物理地址为379。

2221 = 1024 * 2 + 173，故虚地址2221所对应的虚页号为2，页内地址为173。由题中附表知虚页号2对应的物理块号为空，故虚页号2所对应的物理块不在内存中。所以无法知道虚地址2221所对应的物理地址。

●一台计算机有4个页框，装入时间、上次引用时间和它们的R（读）与M（修改）位见表5.2（时间单位：滴答），请问NRU、FIFO、LRU和第二次机会算法将替换哪一页？(上海交通大学1999年试题)

【分析】

在分别用不同的置换算法时，要考虑页表相关数据结构的取值，因此，要对页表中用到的数据结构以及这些数据结构各自的用途有清楚的认识。

【解答】

NRU算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。在题述条件下，只有第0页是最近一个时期内未被访问的页。故NRU算法将淘汰第0页。

FIFO算法在需要淘汰某一页时，淘汰最先进入内存的页。在题述条件下，第2页是最先进入内存的页。故FIFO算法将淘汰第2页。

LRU算法在需要淘汰某一页时，淘汰最近最久未使用的页面。在题述条件下，第1页是最近最久未使用的页面。故LRU算法将淘汰第1页。

第二次机会算法在需要淘汰某一页时，淘汰一个自上一次对它检查以来没有被访问过的页面。在题述条件下，第二次机会算法将淘汰第0页。

●比较段式管理和页式管理的特点。(清华大学1999年试题) 【解答】

与页式管理相比较，段式管理的特点分别如下：

与动态页式管理一样，段式管理也提供了内外存统一管理的虚存实现。与动态页式管理不同的是，段式虚存管理每次交换的是一段有意义的信息，而不是像页式管理那样只交换固定大小的页，从而需要多次缺页中断才能把所需信息调入内存。

段式虚存管理中，段长可根据需要动态增长。这对那些需要不断增加或吸收新数据的段来说，是非常有好处的。但段长的长度受内存可用区大小的限制，且允许段长可根据需要动态增长，给系统管理带来了一定的难度和开销。便于对有完整逻辑功能的信息段进行共享，便于实现动态链接。

试题分析-42

操作系统考研试题分析

段式虚存要求更多的硬件支持。这就提高了机器成本。且在碎片问题以及为消除碎片所进行的合并等问题上较页式虚存管理要差。

页式管理实现的是单一的连续地址空间，而段式管理实现的是二维地址空间。

另外，与页式管理管理相同，段式管理在选择淘汰算法时必须十分慎重，否则也可能产生抖动问题。

●比较分段式与分页式存储管理方式的主要差别。(中山大学1997年试题) 【解答】

与页式管理相比较，段式管理的优点如下：

与动态页式管理一样，段式管理也提供了内外存统一管理的虚存实现。与动态页式管理不同的是，段式虚存管理每次交换的是一段有意义的信息，而不是像页式管理那样只交换固定大小的页，从而需要多次缺页中断才能把所需信息调入内存。

在段式虚存管理中，段长可根据需要动态增长。这对那些需要不断增加或吸收新数据的段来说，是非常有好处的。

便于对有完整逻辑功能的信息段进行共享。便于实现动态链接。 不足之处如下：

段式虚存要求更多的硬件支持。这就增加了计算机成本。

在碎片问题以及为了消除碎片所进行的合并等问题上较页式虚存管理要差。 允许段长可根据需要动态增长，给系统管理带来了一定的难度和开销。 段长的长度受内存可用区大小的限制。

另外，与页式管理管理相同，段式管理在选择淘汰算法时必须十分慎重，否则也可能产生抖动问题。

●在虚拟段式存储系统中，引入了段的动态链接。(北京大学1997年试题) ①试说明为什么引入段的动态链接。 ②请给出动态链接的一种实现方法。 【解答】

①分区式管理和分页式管理的进程地址空间都是线性的，这要求对源程序进行编译链接时把源程序中的主程序、子程序按一维地址顺序排列起来。这使得不同作业或进程之间共享公用子程序或数据变得非常困难。而且，对于不同的用户或进程来说，它们访问这些公用子程序或数据的权限是不同的。因此，如果系统不把用户给定的程序名和数据块名与这些被共享程序和数据在某个进程中的虚页中对应起来，则不可能共享放在内存页面中的程序和数据。另外，由于在页式管理时，一个页面中可能装有两个不同子程序段的指令代码，因此，通过页面共享来达到共享一个逻辑上完整的子程序或数据块是不可能的。

再者，从链接的角度来看，分区管理和页式管理只能采用静态链接。但一个大的进程可能由数百个甚至上千个模块组成。对他们进行链接要大量的CPU时间，将它们读入内存需要大量的空间。而实际执行时可能只用到其中的一个子集。因此从时间和空间代价上来说，静态链接也是不合适的。

综上所述，我们引入了段的动态链接，其目的是为用户提供一个方便灵活的程序设计环境。 ②为了实现段的动态链接，需要在系统中配置多种硬件设备，以快速完成动态链接的功能。其所需的硬件支持包括段表机制，缺段中断机构以及地址变换机构。

段表机制。由于应用程序的许多段中，只有一部分装入内存，其余一些段仍在外存，故通过段表来指示这些段的状态。段表项中包括段名、段长、起始地址、存取方式、访问字段等项目。

试题分析-43

操作系统考研试题分析

缺段中断机构。当进程所要访问的段尚未调入内存时，便由缺段中断机构产生一个缺段中断信号，由操作系统将所需的段调入内存中。

地址变换机构。其所需的地址变换机构如图所示。

3.12设备管理

●名词解释：通道(西安交通大学1999年试题) 【解答】

通道是一种特殊的处理机，它具有执行I/O指令的能力，并通过执行通道（I/O）程序来控制I/O操作。通道的引入是为了建立独立的I/O操作。它不仅希望数据传送独立于CPU，而且希望I/O操作的组织、管理和结束等也尽量独立，以保证CPU有更多的时间去从事计算。根据信息交换的方式，可将通道分为3种类型：字节多路通道、数据选择通道和数组多路通道。

●设管理缓冲区的3个队列分别为空白缓冲队列em，输入缓冲队列in，以及输出缓冲队列out，过程add_buf（type，numb）和take_buf（type，numb）分别用来把缓冲区numb插入type队列和从type队列中取出缓冲区numb。试描述进程从任一缓冲队列中得到一个缓冲区的过程get_buf（type，numb）和释放一个缓冲区numb进入缓冲队列的过程put_buf（type，numb）。(清华大学1998年试题)

【分析】

缓冲区是由整个系统公用的共享资源，所有要输入、输出的进程都需要缓冲区的分配。因此，缓冲区属于临界资源。在多进程申请缓冲区时，就必然会出现临界资源的同步、互斥使用。本题考查的是缓冲队列，但实际上又考查了进程p.v操作。不过该题属于生产者－消费者问题，难度不大。

【解答】

设过程get_buf()和过程put_buf()的描述如下：

设互斥信号量S(type)，其初值为1。设描述资源数目的信号量RS(type)，其初值为n（n为type队列长度）。

PROCEDURE get_buf(type,number) BEGIN

试题分析-44

操作系统考研试题分析

P(RS(type)); P(S(type));

Pointer of buffer(number) = take_buf(type,number) V(S(type)); END;

PROCEDURE put_buf(type,number) BEGIN P(S(type));

add_buf (type,number) V(S(type)); V(RS(type)); END;

【扩展】

从这道题我们可以得到一些启示，在复习\操作系统\各个部分时，不能把注意力仅停留在局部，而要注意知识点之间的横向联系。具体来讲，本题表面是考查缓冲管理（因为把缓冲区作为临界资源）而背后真正要考查的是进程同步问题。这使我们回想起操作系统的本质目标：有效地管理资源和方便用户使用。要能从操作系统各个方面理解这一点，这对于学好操作系统很有帮助。

●设CPU和输入设备I、输出设备O并行执行，且输入设备I和输出设备O的启动受CPU指令的控制。另外，输出设备O的启动还受输出缓冲是否装满输出数据的限制。只有装满输出数据，输出设备才能被启动。试描述中断处理方式下的CPU动作过程。(清华大学1996年试题)

【解答】

CPU的动作过程为：

（1）当没有输入输出请求时，CPU正常工作，运行多个进程。

（2）当某进程需要数据时，CPU发出\命令启动外围设备准备数据，同时将控制状态寄存器中的中断允许位打开，以便在需要时，中断程序可以被执行。在进程发出指令启动设备后，该进程放弃处理机，等待输入完成。由进程调度程序调度其他就绪进程占据处理机。当输入完成后，I / O控制器通过中断请求线向CPU发出中断。CPU在收到中断信号之后，转向预先设计好的中断处理程序对数据传输工作进行相应的处理。中断结束后，CPU回到被中断的现场，继续执行被中断的进程。在以后的某个时刻，进程调度程序选中提出请求并得到数据的进程，该进程继续工作。

（3）当某进程需要输出数据时，CPU将数据拷贝到输出缓冲区，并判断输出缓冲是否装满输出数据，如不满，则等待其他进程的输出数据。否则CPU发出\命令启动外围设备，将输出缓冲区中的所有数据输出。同时将控制状态寄存器中的中断允许位打开，以便在需要时，中断程序可以被执行。在进程发出指令启动设备后，该进程可继续执行，也可放弃处理机，等待输出完成。由进程调度程序调度其他就绪进程占据处理机。当输出完成后， I / O控制器通过中断请求线向CPU发出中断。CPU在收到中断信号之后，转向预先设计好的中断处理程序对数据传输工作进行相应的处理。中断结束后，CPU回到被中断的现场，继续执行被中断的进程。

试题分析-45

操作系统考研试题分析

●当前磁盘读写位于柱面号20，此时有多个磁盘请求，以下列柱面号顺序送至磁盘驱动器：10、22、20、2、40、6、38。寻道（Track）时，移动一个柱面需6ms，按下列算法计算所需寻道时间（柱面移动顺序及所需时间，总寻道时间；忽略到达指定柱面后所需寻道时间）。(上海交通大学1999年试题)

① 先来先服务。 ② 下一个最邻近柱面。

③ 电梯算法（当前状态为向上）。 【解答】 先来先服务：

① 磁头移动顺序为：（20）→10→22→20→2→40→6→38 磁头移动总量是146柱面，总寻道时间是：146×6ms＝876ms.

② 下一个最邻近柱面：

磁头移动顺序为：（20）→20→22→10→6→2→38→40 磁头移动总量是60柱面，总寻道时间是：60×6ms＝360ms.

③ 电梯算法

磁头移动顺序为：（20）→20→22→38→40→10→6→2 磁头移动总量是58柱面， 总寻道时间是：58N×6ms＝348ms.

●简答题：何谓虚拟设备？请说明SPOOLING系统是如何实现虚拟设备的。(西安交通大学2000年试题8分)

【解答】

使用\虚拟技术\，在一类物理设备上模拟另一类物理设备的技术，将独占设备转化为共享设备，通常把用来代替独占设备的那部分外存空间称为虚拟设备。

SPOOLING系统中，作业执行前，操作系统已将作业通过独占设备预先输入到磁盘或磁鼓上一个特定的存储区域（称之为\输入井\）存放好，称为\预输入\，此后，作业执行使用数据时不用再启动独占设备读入，而把这一要求转换成从辅助存储器中读入。另一方面，作业执行中，也不必直接启动独占设备输出数据，而只要将作业输出数据写入磁盘或磁鼓中的特定存储区域（称之为\输出井\）存放，当作业执行完毕后，由操作系统通过相应的输出设备来组织信息输出，称为\缓输出\。这样做可以提高独占设备的利用率，缩短作业的执行时间。这样，由于一台设备可以和辅助存储器中的若干存储区域相对应，所以在形式上就好像把一台输入设备（或输出设备）变成了许多虚拟的输入设备（或输出设备），即把一台不能共享的输入设备（或输出设备）转换成了一台可共享的缓冲输入设备（或输出设备），使用户产生一个\错觉\，好像他们各自都有一台专用的字符设备，从而实现虚拟设备。

3.13文件系统

●试述成组链表法的基本原理。(复旦大学1999年试题) 【解答】

成组链表法首先把文件存储设备中的所有空闲块按50块划分为一组，组的划分按从后往前的顺序划

试题分析-46

操作系统考研试题分析

分，每组的第一块用来存放前一组中各块的块号和总块数。由于第一组的前面再也没有其他组存在，因此第一组的块数为49块。最后一组可能不足50块，而且由于该组后再也没有其他组，所以，该组的物理块号与总块数只能存放在管理文件存储设备用的文件资源表中。系统在初启时把文件资源表复制到内存，从而使文件资源表中存放有最后一组空闲块号和总块数的堆栈进入内存，空闲块的分配与回收可在内存中进行。

当申请者提出空闲块要求时，盘块分配过程是从栈顶取出一空闲块号，将其对应的盘块分配，然后栈顶指针下移一位，总空闲块数减1。若该盘块是栈底，则将该块中存放的下一组的块号和总块数读入内存，然后才将该盘块分配，并重置栈顶指针。

在系统回收空闲盘块时，栈顶指针加1，把回收的空闲块号填入栈顶位置，空闲块数加1。如果栈顶指针等于50，则表示改组已满，需把当前栈的50个块号与块数写入新回收的空闲块中，重置栈顶指针

●文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。(清华大学1999年试题)

【解答】

块长512字节，块号长3字节，所以一个索引块可以存放170个盘块号。

二级索引时，最多可包含的存放文件的盘块的盘块号总数N=170×170=28900个盘块。所以使用二级索引时，可寻址的文件的最大长度=28900×256B=7225kB=7.05MB。

三级索引时，最多可包含的存放文件的盘块的盘块号总数N=170×170×170=4913000个盘块。 所以使用三级索引时，可寻址的文件的最大长度=

4913000*256B=1228250kB=1199.46MB。

●在实现文件系统时，为加快文件目录的检索速度，可利用\文件控制块分解法\。假设目录文件存放在磁盘上，每个盘块512字节。文件控制块占64字节，其中文件名占8字节。通常将文件控制块分解成两部分，第1部分占10字节（包括文件名和文件内部号），第2部分占56字节（包括文件内部号和文件其他描述信息）。(北京大学1997年试题)

①假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。

②一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。

【分析】

利用\文件控制块分解法\加快文件目录的检索速度，其原理是减少因查找文件内部号而产生的访问磁盘次数。因为在进行查找文件内部号的过程中不再需要把文件控制块的所有内容都读入，所以在查找过程中所需读入的存储块减少（即减少了访问磁盘的次数）。但是，采用这种方法访问文件，当找到匹配的文件控制块后，还需要进行一次磁盘访问，才能读出全部的文件控制块信息。这就是为何采用这种方法在一定条件下并不能减少访问磁盘的次数的原因。

【解答】

试题分析-47

操作系统考研试题分析

①采用分解法前，查找该目录文件的某一个文件控制块的平均访问磁盘次数为：

64×(254/2)/512=16采用分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数为：10×(254/2)/512+1=4

②访问磁盘次数减少的条件为：m

●选择题。(浙江大学1999年试题)

文件系统中，设立打开文件（Open）系统功能调用的基本操作是（1），关闭文件（Close）系统功能调用的基本操作是（2）。

（1）A.把文件信息从辅存读到内存。

B.把文件的控制管理信息从辅存读到内存。

C.把文件的FAT表信息从辅存读到内存。 D.把磁盘的超级块从辅存读到内存。 （2）A.把文件的最新信息从内存写入磁盘。 B.把文件当前的控制管理信息从内存写入磁盘。 C.把位示图从内存写回磁盘。

D.把超级块的当前信息从内存写回磁盘。 【解答】（1）B （2）B

3.14 UNIX系统分析

●填空：(中科院计算所1999年试题)

①UNIX系统V中，系统向用户提供的用于创建新进程的系统调用是（ ）；用于建立无名管道的系统调用是（ ）；用于建立有名管道的系统调用是（ ）。

②UNIX系统V中，引起进程调度的原因有（ ）、（ ）、（ ）和（ ）等。 【分析】

要熟悉UNIX系统V的常用的系统调用，创建新进程的系统调用是fork；建立无名管道的系统调用是pipe，建立有名管道的系统调用是mknod。

【解答】

①fork、pipe、mknod。

②正在执行的进程时间片完；正在执行的进程执行了sleep系统调用；正在执行的进程执行了exit系统调用；在执行完系统调用而返回到用户态时，系统中已出现了更高优先级的进程在等待运行。

【扩展】

要明白无名管道和有名管道的区别与联系：

无名管道是一个临时文件，是利用系统调用pipe建立起来的无名文件（指无路径名）。只用该系统调用所返回的文件描述符来标识该文件，因而，只有调用pipe的进程及其子孙进程，才能识别此文件描述符，从而才能利用该文件（管道）进行通信。

有名管道是为了克服无名管道使用上的局限，以让更多的进程也能利用管道进行通信。有名管道是利用mknod系统调用建立的，是可以在文件系统中长期存在的、具有路径名的文件，因而其他进程可以知道它的存在，并能利用该路径名来访问该文件。对有名管道的访问方式像访问其他文件一样，都需先用

试题分析-48

操作系统考研试题分析

open系统调用去打开它。

不论是有名管道还是无名管道，对它们的读写方式是相同的。

在UNIX系统中的进程调度的原因除了解答中所说的4个外，还有下面这种情况：当核心完成中断处理，控制被返回到用户态而要执行原进程时，若有更高优先级的进程在等待运行，会引起进程上、下文的切换。

●您认为下列哪几种指令应该只在核心态下执行：(上海交通大学1999年试题) ①屏蔽所有中断。 ②读时钟日期。 ③设置时钟日期。 ④改变存储映像图。 ⑤存取某地址单元的内容。 ⑥停机。 【分析】

在UNIX系统中，执行状态分为两种：用户态执行，表示进程正处于用户状态之中；核心态执行，一个应用进程在执行系统调用后，或I/O中断后，或时钟中断后，进程便处于核心态执行。这两种状态的主要差别有：

（1）处于用户态执行时，进程所能访问的内存空间和对象受到限制；而处于核心态执行中的进程则能访问所有的内存空间和对象。

（2）进程在核心态运行时是不可被剥夺的；而用户态运行时是可被剥夺的。 【解答】 ①应该。 ②不应该。 ③应该。 ④应该。 ⑤不应该。 ⑥应该。

●设在UNIX中有一进程P，P中有一操作需要访问偏移量为14000处的数据；试问UNIX如何利用过程bmap实现地址变换？(中科院软件所2000年试题)

【解答】

1．核心将14000换为逻辑块号13及块内偏移量688； 2．判断，因10<13<266，故为一次间址； 3．从i.add(10)中取得盘块号，设为x； 4．调用bread过程读x盘块；

5．在一次间址中的文件逻辑块号为3（从0编）； 6．从中得实际块号，设为y； 7．则该块中的688Ｂ即为所求。

试题分析-49

操作系统考研试题分析

【扩展】 bmap算法如下： 输入：（1）索引结点 （2）字节偏移量 输出：（1）文件系统中的块号 （2）块中的字节偏移量 （3）块中I/O字节数 （4）提前读块号 {

由字节偏移量计算出在文件中的逻辑块号； 为I/O计算出块中的起始字节； //输出2 计算出拷贝给用户的字节数； //输出3 检查是否可用提前读并标记索引结点； //输出4 决定间接级；

while(没在所必须的间接级上) {

从文件中的逻辑块号计算索引结点中或间接块中的下标； 从索引结点或间接块上得到磁盘块号；

如果需要，应从先前的磁盘读释放缓冲区（算法brelse）； if(再也没有间接级了) return(块号)；

读间接磁盘块（算法bread）； 按照间接级调节文件中的逻辑块号； } }

●请为下列程序中标号处加上注释。（清华大学1994年试题，共12处） 程序A

#define MSGKEY 75 struct msgform { long mtype; char mtext[256]; } main() {

struct msgform msg; int msgqid, pid, *pint;

试题分析-50

本文来源：https://www.bwwdw.com/article/2pyr.html