操作系统硕士研究生入学考试模拟试题参考答案（电子）

答：(1)LRU淘汰最近最少使用的页面，方法之一是可在页表项中为每页增加一个计数器，每当页面被访问时，页对应的页表项中的计数器加1，当发生缺页中断淘汰计数器值最小的那一只，同时将所有计数器清0。(2) 系统发生“抖动”时应采用增加工作集的方法，可把缺页进程锁住不让其换出，而调入的页总是占据那些暂时不执行进程所占用的内存页面，从而扩大缺页进程的工作集。

23. 简述LRU、NRU和LFU这3种页面置换算法的思想，并各给出一种可能的实现方案。

(中科大1998)

答：LRU算法利用“最近的过去”作为“最近的将来”的一种近似，选择最近最久未使用过的页面予以淘汰。实现方法：为每个页表的每个页面保留一个访问字段，用来记录该页面自上次被访问以来所经历的时间T，当需要淘汰一个页面时，总是选择现有页面面中T值最大的页面淘汰。

NRU算法总是选择在最近一个时期内未被访问过的页面予以淘汰。实现方法：为页表的每个页面保留一个访问位，当某页被访问时其访问位置1，系统周期性地对所有访问位清0。当需要淘汰一个页面时，总是从访问位为0的页面中选择一个予以淘汰。

LFU算法总是选择在最近时期使用最少的页面予以淘汰。实现方法：为每个页面增设一个访问计数器，每当页面被访问时其访问计数器加1。当需要淘汰一个页面时，总是淘汰计数器值最小的页面，同时，所有计数器清0。

24. 解决大作业和小内存矛盾有哪些途径?简述其实现思想。(上交大1997)

答：覆盖技术：由用户把一个程序划分为若干个功能相对独立的程序段，并根据程序的逻辑结构让不会同时执行的程序段共享同一块内存区(称覆盖区)。程序执行中再依需要把程序段调入覆盖区，由此达到小内存运行大作业的目的。 虚存技术：操作系统把主存与辅存统一管理和使用，自动实现部分装入和部分对换功能，即用户大作业在执行时，—部分用户信息放在主存，而其他部分信息放在辅存，当访问信息不在主存时，由系统将其从辅存调入主存。由此，能达到小内存运行大作业的目的，而且可以还可以在小内存中运行多道大作业。

25. 为什么要在设备管理中引入缓冲技术?操作系统如何实现缓冲技术?(国防科大2001) 答：(1)调节CPU和I/O设备之间速度不匹配的矛盾 例如，如果不设缓冲，则程序输出时由于打印机速度跟不上而使CPU停下来等待，而在CPU计算时，打印机又因无数据输出而闲置。有了缓冲区，则程序可把输出数据预先输到缓冲区后继续运行，而打印机可从缓冲区取数慢慢打印，从而，CPU和I/O设备之间速度不匹配的矛盾得到缓和。

(2)实现I/O设备之间的并行操作 类似地，可以开出多缓冲，每个对应于一个设备，实现I/O设备和I/O设备之间的并行操作

(3)减少内外(I/O)交换次数 开设缓冲区后可以实现成组和分解操作，既减少了内外(I/O)交换次数，又充分利用了外存空间。同时，减少内外(I/O)交换次数，也减少了CPU处理I/O中断的次数，提高了系统效率。

缓冲区是临界资源，OS要管理缓冲区的申请、释放和互斥问题。例如，可设缓冲池，并分成空闲缓冲区、输入缓冲区、输出缓冲区。当输入设备需要输入数据时，从空闲缓冲队列取一个空缓冲区，待装满数据后，将其插入输入队列。当CPU处理输入数据时，就从输入队列取下一个数据缓冲区进行处理，处理完该缓冲区数据后将其插入空闲缓冲区队列。当CPU进行数据输出时，也作类似处理。

17

26. 什么是DMA方式?它与中断方式的主要区别是什么?()

答：DMA又称直接内存存取方式，其特点是外设在硬件支持下直接与内存交换成批数据而不需CPU干预。DMA方式下，地址总线、数据总线及相关控制信号线均与CPU共用。平时被CPU管理使用，当DMA时，乐用偷窃总线控制权的办法，CPU管理的总线由DMA控制器接管，并由DMA控制器控制外设与内存间成批交换数据。每当DMA传送的数据完成后发出一个中断，由CPU响应中断并回收控制权。

DMA中断方式的主要区别是：(1)中断方式在每个数据传送完成后中断CPU，而DMA是在所要求的一批数据全部传送完毕才中断CPU。(2) 中断方式的数据传送是在中断处理时由CPU控制完成，而DMA方式则是在DMA控制器控制下完成。

27. 文件系统必须完成哪些工作?(厦门大学1999) 答：(1)文件目录管理

(2)文件的组织 (3)文件的存取

(4)文件存储空间管理

(5)文件的共享、保护、保密 (6)提供各种文件操作

28. 文件存储器的管理与内存管理有何异同?(西北大学1998) 答：文件存储器的管理与内存管理异同点：

(1) 主要任务 内存管理的主要任务为多道程序设计提供支撑；文件存储管理的主要任

务为文件系统提供和管理文件空间。

(2) 基本功能 内存管理的基本功能为内存的分配、回收、共享、保护和扩充；文件存

储管理的基本功能包括文件存储空间的分配和回收。

(3) 分配方式 都可采用连续分配，但以离散分配方式为主。前者常用算法有：最先适

应、最佳适应和最坏适应算法等；两者采用离散分配方式时，采用机制和数据结构不尽相同，内存管理常采用页表、段表；而外存管理采用文件分配表、位示图等。 (4) 分配单位 内存以字节、页面(若干字节) 或段(若干字节)为分配单位，长度变化大；

外存都以盘块或簇(若干连续盘块)为分配单位，长度固定。

29. 现代操作系统一般都提供多进程(或称多任务)运行环境，回答下列问题：(华中科大2000)

(1) 为支持多进程并发运行，系统必须建立哪些关于进程的数据结构? (2) 为支持进程状态变迁，至少应提供哪些进程控制原语?

(3) 执行每一个进程控制原语时，进程状态发生什么变化?相应数据结构发生什么变化? 答：(1)系统为每个进程建立一个数据结构-----进程控制块PCB，用于进程的控制和管理。PCB中记录了有关进程的标识、调度信息、文件信息、存储信息、现埸信息、设备及各种资源信息，以便系统控制和管理进程。PCB是进程存在的唯一标志，也是系统掌握的进程的帷一资料结构。

(2)进程生命周期中，会经历多种状态。系统应具有创建、撤销进程、实现进程状态转换等功能，为此操作系统内核中提供一组进程控制原语，至少包括：创建进程、撤销进程、阻塞进程、唤醒进程、终止进程原语等。用户可通过系统调用接口耒使用它们。

(3) 创建进程、撤销进程、阻塞进程、唤醒进程、终止进程原语的功能简述略。

30.何谓临界资源?使用临界资源诸进程如何实现进程同步?(北京邮电大学2000)

18

答：一次仅允许一个进程使用的资源称临界资源，进程中对临界区访问的程序段称临界区或临界段。对临界资源的使用必须互斥，进程进入临界区必须满足临界区调度的基本原则，实现进程互斥的方法有专门硬件指令(如test and set或swap)、信号量与PV操作、管程等方法。

31.何谓管程?它由哪几部分组成?说明引入管程的必要性。(北京邮电大学2000) 答：管程是管理进程同步的一种同步机制，它保证进程互斥地访问共享变置(代表共享资源)，并提供了一个阻塞和唤醒进程的设施----条件变量。它有三部分组成：(1)局部于管程的数据结构----共享变量，该共享变量表示了共享资源的状态。(2)局部于管程对上述数据结构进行规定操作的若干过程。(3)数据结构的初始化操作。

在引入管程前，对临界区的访问都分散在各个进程中，不但加重用户编程负担，而且容易造成程序设计错误(如用户不正确使用PV操作)。管程把分散在各进程中的临界区集中起来加以控制和管理，每次仅允许一个进程进入管程内，既便于系统管理共享资源，又能保证进程间的互斥，还能方便地利用高级程序设计语言编写程序。

32.现有操作系统对进程的定义不尽相同，有的还引入了挂起状态。试简要分析挂起状态的意义。(浙江大学2000)

答：在一些操作系统中，为了更好地管理和调度进程，以适应系统的功能目标，提高系统的整体效率，引入了挂起状态：

(1) 系统出现故障或功能模块受到破坏，可暂时挂起系统进程，以便修复或消除故障

后再把进程转换到原来状态。

(2) 用户检查作业执行情况或中间结果，可请求系统挂起该作业进程。

(3) 系统负荷过重，如进程数量过多、资源相对不足，造成系统性能下降。此时，需

要挂起部分进程以调整系统负荷，待系统负荷较轻时再恢复这些进程运行。 (4) 在虚存管理系统中，需要区分进程是驻留在内存还是外存，可用挂起状态表示进

程驻留在外存。

33.从进程的定义可看出，它有哪几个基本特征? 进程是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，是操作系统进行资源分配和保护的基本单位。(哈工大2002)

答：它具有如下属性：

结构性：进程包含了数据集合和运行于其上的程序，为了描述和记录进程的动态变化过程使其能正确运行，还需配置一个进程控制块，所以，每个进程至少有三要素组成：程序块、数据块和进程控制块。

共享性：同一程序同时运行于不同数据集合上时，构成不同的进程。或者说，多个不同的进程可以共享相同的程序，所以，进程和程序不是一一对应的。

动态性：进程是程序在数据集合上的一次执行过程，是动态概念，同时，它还有生命周期，由创建而产生，由调度而执行，由撤销而消亡；而程序是一组有序指令序列，是静态概念，所以，程序作为一种系统资源是永久存在的。

独立性：进程既是系统中资源分配和保护的基本单位，也是系统调度的独立单位（单线程进程）。凡是未建立进程的程序，都不能作为独立单位参与运行。通常，每个进程都可以各自独立的速度在CPU上推进。

制约性：并发进程之间存在着制约关系，进程在进行的关键点上需要相互等待或互通消息，以保证程序执行的可再现性和计算结果的唯一性。

并发性：进程可以并发地执行，进程的执行是可以被打断的，或者说，进程执行完一条指令后在执行下一条指令前，可能被迫让出处理器，由其他若干

19

个进程执行若干条指令后才能再次获得处理器而执行。进程的并发性能改进资源利用率和提高系统效率。

34. 画出作业和进程状态转换图。(厦门大了2001) 答： 执行 作 作 作 运行 状态 业 业 业 输 后 完 入 备 成 预输入完成 作业调度 作业运行结束 状 状 状 缓输出 就绪 等待 (创建用户进程) (撤销用户进程) 态 态 态 进程调度 作业调度与低级调度关系及作业和进程状态转换 中级调度

35. 什么叫“可再入”程序?它有什么特性?(西安电子科大2000)

答：可被多个进程同时调用的程序称“可再入”程序。它必定是纯代码，即执行过程中自身不会改变，故调用它的进程应该提供数据与工作区。

36. 分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空

间)，会给页表设计带来什么样的新问题?请给出一种解决方案，分析它的优缺点。(中科大1996)

答：分页存储管理中，允许把进程的页面离散地存放在物理块中，为保证正确的地址转换，系统为进程建立了页表。进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中的物理块号。进程运行时，通过查找页表，就可找到页面在内存中的物理位置。所以，页表的功能是实现从页号到物理块号的地址映射。

当地址空间变大后，页表也变得很大，会占用相当多的内存空间。如对于32位地址空间，若规定页面大小兴4KB，则每个进程页表的页表项有1KB。若每个页表项占4B，故每个进程页表要占用4MB内存空间，且还要求是连续的，这显然不现实。为此，可如下来解决：(1)对页表所需空间也采用离散分配和存放。(2)只将当前使用的页表页调入内存，其余的和暂不用的页面一样存放在外存中，待需要时再调入。

具体做法是采用两级页表。在用户逻辑地址原耒划分的基础上，把页表部分再细分为 页目录表和页表页、即对页表也分页(称页表页)。每个页表页的大小与物理块大小相同，32位地址空间可划分成如图。

对投入运行的程序，将其页目录表调入内存，而页表页仅调入当前使用的。程序运行若找不到相应页表页，则产生—个缺页表页中断，请求系统将该页表页调入内存。

两级页表能适应大地址空间的需要，实现了虚拟存储系统，但增加了地址变换开销和系统管理上的复杂性。 目录位移 页表页位移 页内位移 逻辑地址 物理地址

页框号 页内位移 页目录表 页表页地址 页框号

控制寄存器

进程一级页表 (页目录表)

进程二级页表 (页表页)

20

二级页表地址转换过程