第一章 操作系统引论

第一章 操作系统引论

本章学习要点

【1】掌握操作系统的概念与作用 【2】掌握操作系统的基本类型与特点 【3】掌握操作系统的特征与功能 【4】掌握多道程序设计技术

本章学习难点

【1】多道程序设计技术 【2】操作系统的特征

一. 判断改错题（正确的打√，错误的打×并改正）

（1） 实时系统只能应用于生产控制系统，不能应用于信息处理系统。（ 错 ） （2） 并发含有“同时进行”的概念，是指两个或者是多个事件在同一时刻发生。

（ 错 ）

（3） 操作系统虚拟机在逻辑功能上与裸机一样，具有一个物理实体。（ 错 ） （4） 对用户而言，操作系统是一种人机交互的环境，对设计者而言，它是一种强功能

的系统资源管理程序。（ 对 ）

（5） 资源的共享是以程序的并行执行为条件的，没有程序的并行执行，就没有资源的

共享。（ 错 ）

（6） 计算机系统的资源包括程序和数据两大部分。（ 错 ）

（7） 若把计算机系统分为若干层次，则按由上而下顺序可分为应用系统与应用软件、

操作系统、其它系统软件和裸机。（ 错 ）

（8） 批处理控制程序解决了作业间的自动转换，减少了时间浪费，尤其是主机CPU

时间的浪费，如果一个用户的计算作业非常庞大,也不会独自一直占据CPU。（ 错 ）

二. 填空题

（1） 实时含有立即、及时之意，因而 响应时间 是实时系统最关键的因素。 （2） 操作系统的层次结构中，与 硬件紧密相关 或运行频率较高的模块都安排在

紧靠硬件的软件层中，这一部分通常称为 内核 ，它在执行基本操作时，往往是利用 原语 操作来实现，该操作具有原子性。

（3） UNIX是一个真正的 多 用户、 多 任务的 网络 操作系统。

（4） 如果一个操作系统兼有 批处理操作系统 、 分时操作系统

和 实时操作系统 三者或其中两者的功能，这样的操作系统称为通用操作系统。

（5） 实现多道程序设计必须妥善解决三个问题： 文件 、 作业 和系统资源

的管理和调度。

（6） 批处理系统的主要优点是 系统吞吐量大 ，资源利用率高，系统

1

第一章 操作系统引论

开销小，它的缺点在于作业处理的 平均周转时间较长 ，用户交互能力较弱。

（7） 操作系统是对计算机进行 控制，管理 的程序，是计算机和 用户 的接口。 （8） 提供网络通讯和网络资源共享功能的操作系统称为 网络 操作系统。 （9） 对系统总体设计目标来说，批处理系统注重提高计算机的效率，尽量增加系统的

吞吐量 ，分时系统应保证用户的 交互性 ，而实时系统在及时响应和处理的前提下，再考虑 与用户的交互性 。

（10） 在主机控制下进行的输入/输出操作称为 联机I/O 操作。

（11） 在计算机系统中， CPU 是整个系统硬件的核心和基础，而在计算机软件系

统中， 操作系统 具有同样的核心和基础作用。

三. 简答题

1. 简述操作系统在计算机系统中的位置。 答：操作系统OS是运行在计算机硬件系统上的最基本的系统软件。它在计算机系统中位于计算机裸机和计算机用户之间，为系统软件和用户应用软件提供了强大的支持

2. 简述操作系统的虚拟机的观点和资源管理的观点。

答：一种是虚拟机的观点——装有操作系统的计算机极大地扩展了原计算机的功能，给用户提供了一个友好的、易于操作的界面，对用户来说，好像是一个扩展了的机器，即一台虚拟机器。另一种是资源管理的观点，操作系统完成对处理机、存储器、I/O设备等硬件资源和文件等软件资源的管理

3. 什么是操作系统？它有什么基本特征？

答：操作系统是一组控制和管理计算机硬件和软件资源、合理组织计算机的工作流程，以及方便用户的程序的集合。操作系统的基本特征是：

并发——是指两个或多个事件在同一时间间隔内发生。宏观上是同时的，微观上是交替的。

共享——系统中的资源可供内存中多个并发执行的进程共同使用。根据资源的不同属性，可分为两种资源共享方式：互斥共享和同时访问。

虚拟——通过某种技术把一个物理实体变成若干个逻辑上的对应物，物理实体是实的，即实际存在，而后者是虚的，是用户的感觉。

异步性——在多道程序环境下，多个进程并发执行，但由于资源等因素的限制，内存中的每个进程何时执行，何时暂停，以怎样的速度向前推进，每道程序需多少时间才能完成，都是不可预知的，进程以异步的方式运行。但只要运行环境相同，作业经过多次运行，都会获得完全相同的结果。

2

第一章 操作系统引论

4. 多道程序设计时应注意什么问题？

答：处理机管理问题——多道程序之间如何分配CPU，使CPU既能满足各程序运行的需要，又能提高处理机的利用率。

内存管理问题——为每道程序分配必要的内存空间，并防止程序遭破坏。 I/O设备管理——分配为多道程序共享的I/O设备，方便用户使用，提高设备利用率。 文件管理问题——组织大量的程序和数据，便于用户使用，保证数据的安全和一致。 作业管理问题——对系统中各种类型的作业进行组织

四. 本章复习题

1. 实时操作系统必须在（ B ）内处理来自外部的事件。 A.一个机器周期 B.被控制对象规定的时间 C.周转时间 D.时间片 2. 操作系统中最基本的两个特征是（ B ）

A.并发和不确定性 B.并发和共享 C.共享和虚拟 D.虚拟和不确定性 3. 分时系统追求的目标是（ B ）

A.充分利用I/O设备 B.快速响应用户 C.提高系统吞吐量 D.充分利用内存 4. 批处理系统的主要缺点是（ D ）

A.系统吞吐量小 B.CPU利用率不高 C.资源利用率低 D.无交互能力 5. 在主机控制下进行的输入输出操作称为（ 联机 ）操作。

6. 如果操作系统具有很强的交互性，可同时供多个用户使用，系统响应比较及时，则

属于（ 分时操作系统 ）类型；如果系统可靠，响应及时但仅有简单交互能力则属于（ 实时操作系统 ）类型；如果操作系统在用户提交作业后不提供交互能力，它追求的是计算机资源的高利用率，大吞吐量和作业流程的自动化，则属于（ 批处理系统 ）类型。

7. 设内存中有三道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O

操作时间

程序 操作 A B C 计算 I/O 计算 30 60 20 40 30 40 10 10 20 3

第一章 操作系统引论

如表所示（单位：ms）。假设三道程序使用相同设备进行I/O操作，即程序以串行方式使用设备。试画出单道运行和多道运行的时间关系图（调度程序的时间忽略不计）。在两种情况下，完成三道程序各要花多少时间？

单道运行时间：(30+40+10)+(60+30+10)+(20+40+20)=260ms 多道运行时间：180 ms

8. 试比较分时系统和实时系统。

4

第二章 进程管理

第二章 进程管理

本章学习要点

【1】掌握进程的定义和特征

【2】掌握进程状态及其状态转换的原因 【3】熟练运用信号量解决进程同步问题 【4】掌握调度的类型与方式 【5】掌握常用的进程调度算法 【6】掌握死锁的相关知识 【7】理解银行家算法

本章学习重点和难点

【1】运用信号量解决进程同步问题 【2】进程调度算法 【2】银行家算法

一. 判断改错题（正确的打√，错误的打×并改正。） （1） 进程由程序和数据两部分组成。（ ） （2） 在生产者消费者进程中，V操作的次序无关紧要，而P操作次序不能颠倒。（ ） （3） 产生死锁的原因之一是对计算机操作不当，造成计算机死机。（ ） （4） 原语是指操作系统中的初始化程序。（ ）

（5） 若进程处于阻塞状态，当引起阻塞的条件被解除时，进程状态应变为运行状态。

( )

（6） 并发进程可以同时进入临界区，交替访问临界资源。( ) （7） 程序的封闭性是指该程序不允许某些进程调用。（ ）

（8） 消息通信因为它数据量较小，因而它是一种低级通信方式。（ ） （9） 单机系统最多允许两个进程处于运行状态。（ ）

（10） 死锁产生，必须要满足四个必要条件，所以，为避免死锁产生，主要注意如何不

让这四个必要条件成立，并打破循环等待资源的环路。（ ）

（11） 操作系统的进程管理是整个操作系统管理中的核心，它包含了进程的调度、协调

以及进程通信。（ ）

二. 填空题

（1） 操作系统中，进程是 、 和管理的最小独立单位，操作系

统的各种活动都与 有关。

（2） 消息传递系统属于 级通信方式，进程间的数据交换以 为单位。 （3） 一个进程可以由系统创建，或者由 用创建原语创建。被创建的进程开

始处于等待状态。在条件成熟时，采用 原语为它们分配除 以外的所有资源，并被排列到 队列中。

（4） 一次仅允许一个进程使用的资源称为 ，同时把访问该资源的那段程序

5

第二章 进程管理

代码称为 。

（5） 轮转法是按照 轮流地把处理器分配给就绪队列中的进程，该算法多用于

系统中，其难点在于 。

（6） 信号量的物理意义是当信号量大于零时表示 ；当信号量小

于零时，其绝对值为 。

（7） 死锁的检测可以通过 图，利用 定理来实现。

（8） 进程运行过程中，因为 、等待I/O操作等事件发生时，通过

原语将它撤下，排入 队列，并引起新的 。

（9） 有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，

则信号量值的变化范围是 。

（10） 对单处理机系统，处于 状态的进程只能有1个，处于就绪状态的进程

可以有多个，它们仅未获得 控制权，按某种方式排成一队列，此队列称为 队列，操作系统必须按照一定的 ，每次从队列中选择一个进程投入运行，这个选择过程称为 。

三. 简答题

①. 处理机管理的主要任务是什么？具有哪些主要功能？ 答：

②. 程序的顺序执行和并发执行有何不同？ 答：

③. 简述进程的定义，进程的基本状态以及进程状态转换的典型原因。 答：

6

第二章 进程管理

④. 简述进程与程序的区别。 答：

⑤. 进程的实体是什么？ 答：

⑥. 简述进程控制块的主要内容。 答：

⑦. 简述进程通信的概念，最基本的通信原语有那些？ 答：

⑧. 简述读者——写者问题的思想。 答：

⑨. 什么是原语？ 答：

7

第二章 进程管理

⑩. 简述引起进程调度的原因。 答：

?. 进程调度有何功能？有哪些常用的调度算法？ 答：

?. 什么叫安全状态？常用什么方法保持系统处于安全状态？ 答：

?. 进程之间存在哪几种相互制约关系？各是什么原因引起的？下列活动分别属

于哪种制约？①若干同学去图书馆借书②两队举行篮球比赛③流水线生产的各道工序④商品生产和社会消费。

答：

?. 系统中有3个进程，4个相同类型的资源，每个进程最多需要2个资源，该系

统是否会发生死锁？为什么？

答：

8

第二章 进程管理

?. 资源分配图如图所示，系统是否处于死锁状态？

P0 P1 ? ?

r1 r2 r3 r4 ? ? ? ?

P2 P3

答：

?. 简述解决死锁的途径。

?. 简述死锁定理。 答：

四. 综合应用题

?. 请用信号量实现4*100接力赛的同步过程 答：

? P4 9

第二章 进程管理

有一发送者进程和一接收者进程，其流程如下。s是用于实现进程同步的信号量，m是用于实现进程互斥的信号量。试完成流程图。假定缓冲区有无限多个，s和m的初值为多少？ 发送者 接收者 申请缓冲区 C 把信息写入缓冲区 D A 从消息链首取一个缓冲区 将缓冲区放到消息链尾 V(m) B 从缓冲区取出消息 V(s) 释放缓冲区 答：

?. 桌上有一只盘子，最多允许存放两只水果，每次只能放入或取出一个水果。爸

爸专向盘中放苹果，妈妈专向盘中放桔子，两个儿子专等吃盘中的苹果，两个女儿专等吃盘中的桔子。试用PV操作实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。

答：

?. 在公共汽车上，司机和售票员的活动分别是 司机：启动车辆；正常行车；到站停车； 售票员：关车门；售票；开车门；

在汽车不断到站、停车、行驶过程中，这两个活动存在着同步关系，试用信号量和P、V操作实现它们的同步。 答：

10

第二章 进程管理

21. 某寺庙，有小、老和尚若干，有一水缸，由小和尚提水入缸供老和尚引用。水

缸可容12桶水,水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为4个。每次入、取缸水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。

答：

22. 设系统中有五个进程、3种资源，总数分别为A 17，B 5，C 20，T0时刻系

统状态如下。 P1 P2 P3 P4 P5 最大资源需求 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 A 2 4 4 2 3 已分配资源 B 1 0 0 0 1 C 2 2 5 4 4 A 2 剩余资源数 B 3 C 3 11

第二章 进程管理

i. ii. iii.

15 2 17 完成剩余资源数的计算： T0时刻是否安全？

若P2请求资源（0，3，4），系统如何处理？

答：

23. P1，P2，P3，P4四个进程同时依次进入就绪队列，它们所需要的处理器时间和

优先数如下，若不计调度等所消耗的时间，请回答： 进程 处理器时间（秒） 优先数 P1 20 2 P2 15 3 P3 10 5 P4 12 3

①分别写出采用先来先服务和非抢占式的优先数调度算法时进程执行的次序。 ②分别计算每个进程在就绪队列中的等待时间和平均等待时间。 答：

24. 系统中有四道作业，分别用先来先服务、短作业优先调度方法和最高响应比优

先法调度，完成表格的计算，并计算平均带权周转时间。 单位：小时

作业 提交时间 1 2 3 1：00 1：10 2：00 运行时间 2 6 2 12

第二章 进程管理

4 2：00 1

五. 本章复习题

25. 简要分析“高响应比优先调度”算法。 26. 简述作业调度和进程调度的区别与联系。

27. 打印机和磁盘都是共享资源，当多个作业共享时有什么不同？ 28. 为什么说多级反馈队列调度算法能较好地满足各类用户的需要？ 29. 举例描述资源分配图。

30. 简述选择作业调度算法的原则。

31. 某招待所有100个床位，住宿者入住要先登记，离去时要撤消登记。请用PV

操作给出住宿登记及撤消登记过程的算法描述。 32. 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主

存的缓冲区1，每执行一次只能读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次只能复制一个记录；PC将缓冲区2的内容打印出来，每执行一次只能打印一个记录。缓冲区的大小等于一个记录大小。试用PV操作来保证文件的正确打印。

33. 有A，B，C，D四人，A不断地向篮中放红球，B不断地向篮中放绿球，C不断

地从篮中取红球，D不断地从篮中取绿球。规定篮中最多放M只球，并且每次只能存放或取用一只，取球和放球不能同时进行。现设四个信号量S1，S2，S3和S4，用于解决同步与互斥。

34. 说明S1，S2，S3和S4四个信号量的含义和初值。 35. 完成下面的P、V操作流程。

A B C D

↓ ↓ ↓ ↓ ① ② ⑤ ⑦ ↓ ↓ ↓ ↓ P（S2） ③ P（S2） P（S2） ↓ ↓ ↓ ↓ 向篮中放红球 向篮中放绿球 从篮中取红球 从篮中取绿球

13

第二章 进程管理

↓ ↓ ↓ ↓ V（S2） V（S2） ⑥ V（S2） ↓ ↓ ↓ ↓ V（S3） ④ V（S1） ⑧ ↓ ↓ ↓ ↓

36. 在某一自动测量系统中要完成采样、转换和显示等任务。采样过程把从传感器

上得到的整型微电压值存入一个缓冲区，转换过程把微电压值从缓冲区中取出，计算成度量值后再存入该缓冲区，显示过程把缓冲区中的度量值取出并显示。用PV操作实现三个过程的同步问题，说明信号量SS，SC，SD的作用。完成程序的填充，使其能正确执行。

Begin

Buffer:integer; SS,SC,SD:semaphore; SS:=1;SC:=0; SD:=0; Cobegin

PROCESS sample Begin

L1:get a sample; ; buffer:=sample; ; goto L1 end;

PROCESS conver Begin

L2: ;

Take a sample from buffer;

Convert the sample to a value; Buffer:=value; ; goto L2 end;

PROCESS display

Begin

L3: ;

Take a value from buffer; ;

display the value; goto L3 end; coend;

14

第二章 进程管理

end;

37. 试用PV操作描述协调一个理发师和多个顾客之间的同步问题：某个理发店有

一间N个椅子的理发厅。当没有顾客时，理发师去睡觉。当有顾客进来时，如果理发师正在睡觉，这个顾客会叫醒他。

38. 某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零

件，装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上，F1存放零件A ，F2存放零件B，F1和F2的容量均为可以存放10个零件。装配工人每次从货架上取一个A零件和一个B零件组装成产品。请用PV操作正确管理。

39. 哲学家甲请哲学家乙、丙和丁到某处讨论问题，约定全体到齐后开始讨论，在

讨论的间隙四位哲学家进餐，每人进餐都需使用刀、叉各一把，餐桌的布置如图，请用信号量及P、V操作说明这四位哲学家的同步、互斥过程。

丁

叉2 刀1 ①. b 丙 甲 b ? 刀2 叉1

乙

40. 在一间酒吧有三个音乐爱好者队列，第一队的爱好者只有随身听，第二队只有

音乐磁带，第三队只有电池。而要听音乐就必须三种物品齐全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种。全部买卖就这样进行下去。试用PV操作正确解决这一买卖。

41. 某数据库有一个写进程，N个读进程，它们之间读写操作的互斥要求是：

i. 写进程正在写该数据库时，不能有其他进程读该数据库。 ii. 读进程之间不互斥，可以同时读该数据库。

iii. 如果有若干进程正在读该数据库，一个写进程正等待写，则随后欲读的进

程也不能读该数据库，需等待写进程先写。

请用信号量及PV操作描述进程互斥及工作过程。

42. 若有10个同类资源供三个进程共享，下表列出了这三个进程目前已占资源和

最大需求量的情况，现在这三个进程P1，P2，P3又分别申请1个，2个，1个资源，请问：

① 能否先满足进程P2的要求？为什么？ ② 如何为这三个进程分配资源比较合适？

15

第二章 进程管理

进程 P1 P2 P3

已占资源数

3 3 2

最大需求数

7 8 3

43. 假设在单道批处理系统的后备状态中有四道作业，将按照“最高响应比优先法”

调度运行，试计算各时刻的响应比，并完成下表的计算。（单位：小时）

作业 提交时间 运行时间 开始时刻 完成时刻 周转时间 1 2 3 4 8:00 8:50 9:00 9:50 2 0.5 0.1 0.2 平均周转时间= 平均带权周转时间= 16

第三章 存储管理

第三章 存储管理

本章学习要点

【1】掌握存储管理的相关概念

【2】掌握操作系统的分区存储管理方法 【3】熟悉分页和分段存储管理方法 【4】熟悉虚拟存储管理方法

本章学习难点

【1】分页与分段地址映射 【2】虚拟存储管理

44. 判断改错题（正确的打√，错误的打×并改正。）

45. 进行程序的相对地址到物理地址的转换，就是地址重定位。（ ） 46. 在分页管理中所产生的内存碎片，最多小于帧的大小。（ ）

47. 段页式存储管理是通过请求调入和替换功能，对内外存进行统一管理，为用户

提供了比实际内存容量大得多的物理存储空间。（ ）

48. 请求页式存贮管理中，若一个作业要求的全部存贮需求不能满足，该作业只能

等待。 ( )

49. 碎片的总容量如果超过某个作业申请的容量，就可以将其分配给该作业。

（ ）

50. 最佳适应法将能满足作业需求量的最小空闲区分配给作业。( )

51. 相对于简单分页管理来说，请求页式管理是“用时间换取了空间”，这是该种

管理方式的一个缺点。（ ）

52. 段式管理便于处理动态变化的数据结构，便于动态链接，便于分段共享。（ ） 53. 请求分页管理过程中，作业地址空间同样受到内存容量大小的限制。（ ） 54. 分区管理取消了存储分配连续性要求，使一个作业的地址空间在内存中可以是

若干个不一定连续的区域。（ ）

55. 静态分配是指在目标程序运行之前完成的存储分配。例如分区管理和分页管

理。（ ）

56. 分页管理中，作业地址空间是一维的，页的长度是等长的。（ ）

57. 填空题

58. 源程序经过 产生相对目标程序，运行时，必须经过 将相对

目标程序装入内存，并实现相对地址到 的转换。

59. 分页管理的主要任务之一是实现 到 的内存地址映像。

60. 固定式和可变式分区的存储管理中，寻找空闲区一般采用： 、 和

等分配算法。

61. 分页管理中，每存取一个数据，要访问两次内存，第一次访问内存中

的 ，得到数据的 。第二次根据所得内容，从内存中取

17

第三章 存储管理

出 。

62. 在分段管理中，系统为每个运行的作业建立一个 ，其内容主要

包括 、 、 和状态标志。

63. 内存扩充的概念有两种，一种是在物理上进行扩充，为系统增配更多的存储芯

片，以扩大 ；另一种是利用目前机器中实际内存空间，借助软件技术，实现内存扩充，称为 ，主要技术有 和 两种。

64. 当程序经过 以后，形成了一种由机器指令组成的集合，被称

为 。它的指令顺序都是以0作为一个参考地址，这种地址被称为 ，地址的集合被称为 。

65. 在虚拟段式存储管理中，若逻辑地址的段内地址大于段表中该段的段长，则发

生 。

66. 在分段管理的地址变换过程中，若执行某条指令，首先要找到该作业段表

的 ，然后根据逻辑地址中的段号去查找 ，得到该段的 ， 其值与段内位移量 ，得到 。

67. 简答题

68. 简述存储管理主要解决的问题。 答：

69. 简述可变式分区管理的分配策略。 答：

70. 为什么要重定位？何谓静态重定位和动态重定位？ 答：

18

第三章 存储管理

71. 各种存储管理方式对作业地址空间连续性有何要求？ 答：

72. 页和段有什么不同？ 答：

73. 常用的页面调度算法有哪几种？ 答：

74. 在请求分页系统中，页表包含的内容有哪些？分别有何作用？ 答：

75. 虚拟存储也是一种内存扩充技术，它与覆盖、交换技术技术有何不同？答：

19

第三章 存储管理

76. 简述虚拟存储器的特征。 答：

77. 请求页式管理常用的替换策略有哪些？ 答：

78. 简述段页式管理方式的优点。 答：

79. 应用题

80. 已知主存容量为512KB，假定操作系统代码占低地址部分的64KB，存储分配时

从空闲区的高址处分割一块作为分配区。现有作业序列：作业1 要求100KB，作业2 要求56KB，作业3 要求80KB ，作业1 完成，作业2 完成，作业4 要求100KB，作业5 要求60KB，试画出作业1、2完成后内存的分布情况，并按首次适应法和最佳适应法分别画出此时空闲队列及作业4、5进入系统后的内存分布。（注意表明各部分的大小和起始位置） 答：

20

第三章 存储管理

81. 在请求分页系统中，采用LRU页面置换算法时，假设一个作业的页面走向为4，

3，2，1，4，3，5，1，3，2，1，5，当分配给该作业的物理块数分别为3和4时，试描述访问过程中发生缺页的情况，并计算缺页中断率，比较所得结果。

82. 本章复习题

a) 段式和页式存储管理的地址结构相似，它们有什么实质性差异？

b) 对访问串1，2，3，4，1，2，5，1，2，3，4，5，试描述在驻留集大小分别为

3，4时，使用FIFO和LRU替换算法的过程，并计算缺页率。

83. 某虚拟存储器的用户空间共32个页面，每页1KB，主存16KB。假定某时刻系

统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址093C转换为物理地址。

21

第三章 存储管理

84. 假定存储器中有地址由低到高的三块空闲块，大小依次为350字节、250字节

和500字节，请构造一串内存请求序列，对该请求首次适应算法能满足，而最佳适应算法则不能。并描述最佳适应算法的内存分配过程。

85. 在页式存储管理中，某作业J的逻辑地址空间为4页，每页2048字节，已知

该作业的页表如下，试借助地址变换图（要求画出地址变换图）求出逻辑地址4865所对应的物理地址。

页号 物理块号

0 2 1 4

2 6

3 8

86. 在某多道程序系统中，供用户使用的内存空间有100K，磁带机2台，打印机1

台。系统采用可变式分区分配管理内存，对磁带机和打印机采用静态分配方式，并设输入/输出操作的时间忽略不计。现有一作业序列如下： 作业号 到达时间 1 2 3 4 5 8:00 8:20 8:20 8:30 8:35 要求计算时间(分钟) 25 10 20 20 15 要求内存量 15K 30K 60K 20K 10K 申请磁带申请打印机数（台） 机数（台） 1 1 1 1 1 1 1 采用先来先服务的调度算法，优先分配内存的低地址区域且不准移动内存中的作

业，在内存中的作业平分CPU时间，试问： a) 作业调度选中作业的次序是什么？ b) 计算各作业的周转时间。

22

第四章 设备管理

第四章 设备管理

本章学习要点

【1】掌握与设备管理相关的概念 【2】掌握I/O控制方式 【3】理解缓冲、中断与通道技术

【4】掌握SPOOLing的功能与实现原理

本章学习难点

【1】缓冲、中断与通道技术 【2】SPOOLing技术

87. 判断改错题（正确的打√，错误的打×并改正。）

88. 虚拟设备是指被多个用户或进程交替使用的设备，宏观上好象多个用户同时在

使用。( ）

89. 采用Spooling技术，就可使独占设备增加，使用户同时面对独立的同类设备。

（ ）

90. 通道技术本质上是从软件上解决操作系统对输入输出操作的控制问题。（ ） 91. 逻辑设备是物理设备属性的表示，用来指定某一具体设备。（ ）

92. 从设备的资源属性分类，可把设备分为独占设备、共享设备和虚拟设备。

（ ）

93. 操作系统设备管理模块的主要任务是如何有效地分配和使用设备，如何协调处

理机与设备操作的时间差异，提高系统总体性能。（ ）

94. 系统与设备间的协调主要是速度上的协调，要解决快速处理器与慢速的I/O设

备间的操作匹配矛盾，只有通过建立硬件缓冲区的方法。（ ）

95. 用户在使用I/O设备时，通常采用物理设备名，指明具体的设备。（ ） 96. 缓冲是一种暂存技术，它利用外存的一部分，在数据传送过程中进行暂时的存

放。（ ）

97. 填空题

98. 设备分配的具体实现是由操作系统中的 负责对提出设备请求的

分配设备，这种分配还应包括分配 ，如控制器等，以保证分配的完整性。

99. 通常的I/O操作通过两种指令实现控制，一种是由操作系统发出的 ，

另一种是由 提供的。

100.在微机中，常把I/O中断处理程序以 的方式作为操作系统设备管

理和控制的依据，用户采用一种通用的 来使用这些设备。 101.从计算机设备的数据组织方式分类，设备可以分为块设备和_____________，

23

第四章 设备管理

而按设备的共享属性分类，可以分为 、共享设备和 。 102.在设备分配算法的实现中，同样要考虑 问题，防止在多个进程进行

设备请求时，因相互等待对方释放所占设备而陷入 。

103.引入缓冲技术，有效地改善了系统CPU与I/O设备之间 不匹配的情

况，也减少了I/O设备对CPU的 ，简化了中断机制，节省了系统开销。

104.设备管理中采用的数据结构有 、 、 和

四种。

105.CPU对外围设备的控制方式主要由四种： 方式、 方式、

方式和通道方式。

106.简答题

107.设备管理的目标是什么？ 答：

108.简述设备管理的主要功能。 答：

109.什么是缓冲？引入缓冲有什么好处？ 答：

110.简述通道和缓冲的概念。 答：

24

第四章 设备管理

111.打印机和磁盘都是共享资源，当多个作业共享时有什么不同？ 答：

112.什么是设备的独立性？ 答：

113.有哪几种I/O控制方式，分别适用于何种场合？

114.试比较I/O控制方式中的中断控制方式和DMA方式。 答：

115.I/O设备与CPU之间有何主要矛盾？如何解决？ 答：

116.在设备管理中，瓶颈问题产生的原因是什么？如何解决？ 答：

117.简述设备分配过程。

25

第四章 设备管理 第五章 文件管理

第五章 文件管理

本章学习要点

【1】掌握操作系统文件管理的相关概念

【2】掌握文件的逻辑结构、物理结构和存取方法 【3】理解文件目录及目录结构 【4】掌握磁盘调度算法

【5】理解外存空间的管理方法

本章学习难点

【1】UNIX系统的成组链接法

118.判断改错题（正确的打√，错误的打×并改正。）

119.文件的存取方法仅依赖于文件的物理结构，而与存放文件的存储特性无关。

（ ）

120.文件系统中每个文件的系统标识符可以有多个。( ) 121.数据库文件是一种无结构的字符流式文件。（ ）

122.采取顺序文件结构，连续存取一批相邻的记录时，存取速度很慢。（ ） 123.多级目录结构中，重名问题得到了解决，同一目录中文件或目录重名是允许的。

（ ）

124.通过对用户分类和限定各类用户对目录和文件的访问权限来保护系统中目录

和文件的安全，这种文件安全管理方式指的是系统级安全管理。（ ） 125.索引文件是一种对文件存储进行连续分配的方式，文件系统为每个文件另建一

张指示逻辑记录和物理块之间的对应关系的表，即索引表，文件本身和索引表组成的文件即是索引文件。（ ）

126.编译程序是用户用以编译程序的应用工具，因此，它是用户文件。（ ） 127.索引表的建立会占用额外的存储空间和访问时间。（ ）

128.填空题

129.链接文件可以分布在存储设备中各个存储部位，它可以解决存储器的

问题，有利于文件扩充。

130.确定磁盘上一个块所在的位置必须给出三个参数： 、

和 。

131.对索引文件的存取首先查找 ，然后根据 的地址存取相应

的物理块。

132.文件的逻辑结构分为 和 两种。 133.UNIX和DOS操作系统都把设备作为一种 ， 向它 操作完成输出

功能。

26

第四章 设备管理 第五章 文件管理

134.简答题

135.文件系统主要解决哪些问题？

136.简述文件的概念和特征。 答：

137.简述文件目录的概念及其在文件系统中的作用。 答：

138.磁盘访问时间由哪几部分组成？试说明各组成部分的含义。

139.本章复习题

a) 简述文件的逻辑结构与文件的物理结构的概念。 b) 简述文件的三大基本特征。 c) 试解释位示图的概念。

d) 外存管理的主要功能是什么？

e) 若某磁盘共有200个柱面，其编号为0~199，假使已完成第68号柱面的访问请

求，正在访问96号柱面的请求者服务，还有若干个请求者在等待服务，依次要访问的柱面号为：175，52，157，36，159，106，108，72

f) 分别用先来先服务调度算法、电梯调度算法来确定实际服务的次序。 g) 分别计算两种算法的移动臂移动的距离。 h) 一磁盘文件卷的总容量为512块（每块512字节），块号从0#~511#。假定0#~7#，

500#~511#用于初始引导程序。按UNIX操作系统中的成组链接法，100块一组，

27

第四章 设备管理

将余下的块分组，写出各组的块号范围及块数，并说明此方法的优点。

28

附录一 自测题

i) 第1章 操作系统概论

(1) 试说明什么是操作系统，它具有什么特征？其最基本特征是什么？

操作系统就是一组管理与控制计算机软硬件资源并对各项任务进行合理化调度，且附加了各种便于用户操作的工具的软件层次。

现代操作系统都具有并发、共享、虚拟和异步特性，其中并发性是操作系统的最基本特征，也是最重要的特征，其它三个特性均基于并发性而存在。

(2) 设计现代操作系统的主要目标是什么？

现代操作系统的设计目标是有效性、方便性、开放性、可扩展性等特性。其中有效性指的是OS应能有效地提高系统资源利用率和系统吞吐量。方便性指的是配置了OS后的计算机应该更容易使用。这两个性质是操作系统最重要的设计目标。开放性指的是OS应遵循世界标准规范，如开放系统互连OSI国际标准。可扩展性指的是OS应提供良好的系统结构，使得新设备、新功能和新模块能方便地加载到当前系统中，同时也要提供修改老模块的可。

(3) 试说明客户机/服务器结构的操作系统为什么获得广泛应用。

客户机/服务器结构的操作系统具有不同于传统集中式OS的一系列独特优点，使得其在网络时代大为流行。主要原因有以下几点：

140. 该系统的数据可以进行分布式处理和存储。客户机本身均具有一定的处理能

力，部分数据处理和存储工作可由本地客户机完成，减少了服务器机的任务量。 141. 对于重要数据，可以将其放在受到严密保护的服务器所在的局域网内集中管

理，以便保证数据安全。

142. C/S结构有较好的灵活性和可扩充性，客户机/服务器机类型可选范围很大。 143. 易于修改用户程序。对客户机的修改和增删很方便，甚至可以由用户自行进行。

(4) 处理机管理有哪些主要功能？请简要描述。

处理机的管理功能主要体现在创建、撤销进程，并按照一定的算法为其分配所需资源，同时还要管理和控制各用户的多个进程协调运行，确保各个进程可以正确的通信。在多道程序OS中，这些管理功能最终通过对进程的控制和管理来实现，而在具有线程机制的OS中，这些功能的实现还依赖于对线程的管理和控制。 (5) 存储器管理有哪些主要功能？请简要描述。

操作系统所管理的存储器包括内存、外存等，因此存储器管理的主要任务就是将各种存储器件统一管理，保证多道程序的良好运行环境，同时还要兼顾内存利用率、逻辑上扩充内存的需求以及用户的感受，提供优良的控制、存取功能，为用户提供操控存储器的手段。

为实现上述要求，存储器管理应具有内存分配、内存回收、内存保护、地址映射和虚拟内存等功能。

29

附录一 自测题

(6) 文件管理有哪些主要功能？请简要描述。

其主要功能就是管理外存上的静态文件，提供存取、共享和保护文件的手段，以方便用户使用，同时禁止无权限用户对他人资源的误访问或有权限用户对资源的误操作。文件管理机制还要能有效管理外存空闲区域，根据文件的大小为其分配和回收空闲区。为了满足用户对响应时间的要求，文件管理机制还应实现目录管理，以便快速地定位文件。文件管理机制能有效保护文件安全，提高资源利用率，为用户提供快速检索和使用文件的手段，是OS不可或缺的组成部分。

(7) 设备管理有哪些主要功能？请简要描述。

设备管理的主要作用是使用统一的方式控制、管理和访问种类繁多的外围设备。设备管理功能主要体现在：接收、分析和处理用户提出的I/O请求，为用户分配所需I/O设备，同时还要做到尽量提高CPU和I/O设备利用率、I/O处理效率，为用户提供操控I/O设备的便捷界面和手段。根据设备管理模块的功能要求，可以将其功能分为设备分配、缓冲管理、设备处理、虚拟设备等。

(8) 操作系统具有哪些接口？这些接口的作用是什么？

操作系统为用户提供的接口有图形接口、命令接口和程序接口几种形式。

操作系统包括三种类型的用户接口：命令接口（具体又可分为联机命令接口与脱机命令接口）、程序接口及图形化用户接口。其中，命令接口和图形化用户接口支持用户直接通过终端来使用计算机系统，而程序接口则提供给用户在编制程序时使用。

a) 第2章 进程管理

(1) 什么是进程？为什么要在操作系统中引入进程？

进程是可并发执行且具有独立功能的程序在一个数据集合上的运行过程，它是操作系统进行资源分配和调度的基本单位。“进程”概念是人们为了使程序能够并发执行，并且能对并发的程序加以描述和控制而引入的。

(2) 试从并发性、独立性、动态性上比较程序和进程的不同。

144. 并发性是进程的重要特征，同时也是OS 的重要特征。引入进程的目的正是

为了使其程序能和其它进程的程序并发执行，而程序是不能并发执行的。 145. 独立性是指进程实体是一个能独立运行的基本单位，同时也是系统中独立获

得资源和独立调度的基本单位。而对于未建立任何进程的程序，都不能作为一个独立的单位参加运行。

146. 动态性是进程最基本的特性，可表现为由创建而产生，由调度而执行，因得

不到资源而暂停执行，以及由撤销而消亡，因而进程有一定的生命期；而程序只是一组有序指令的集合，是静态实体。

30

附录一 自测题

(3) 进程有哪些基本状态？这些状态具有什么特征？

进程的三种基本状态分别是：就绪状态、运行状态、阻塞状态。

147. 就绪状态：进程已获取到除CPU之外的所有必要资源，只要再得到CPU，就

可以马上投入运行。

148. 运行状态：处于就绪状态的进程被调度程序选中后将得到CPU控制权，此时

该进程就可以使用处理器进行数据运算和处理。 149. 阻塞状态：当一个进程正在等待某个事件的发生(如等待I/O的完成)而暂停执

行，这时，即使分配有CPU时间，它也无法执行。

(4) 说明进程基本状态的转换关系及引起这些状态间转换的典型原因。

处于就绪状态的进程，在调度程序为之分配了处理器之后，就可以投入运行。同时，进程的状态也由就绪状态转变为运行状态；在采用时间片机制的操作系统中，分配给当前进程的时间片用完之后，它会暂停执行，其状态也由运行状态转换到就绪状态；如果由于某事件发生(比如进程需要访问某I/O设备，而该设备正在被别的进程访问)而使进程运行受阻，不能再继续向下执行时，它的状态会由运行状态转变为阻塞状态；当进程期望的某事件发生时(比如需要访问的I/O设备已可用)，进程将从阻塞状态转变为就绪状态。

(5) 试说明引起进程创建的典型事件。

引起进程创建的典型事件有：用户登录、作业调度、提供服务、应用请求。

(6) 什么是PCB？它具有什么作用？为什么说PCB是进程存在的唯一标识？

进程控制块(Process Control Block，PCB)是操作系统为了管理进程而设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程。

它的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能和其它进程并发执行的进程.

因为系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。进程与PCB是一一对应的。

(7) 试说明进程创建的过程。

创建进程的操作必须调用创建原语来实现。创建原语首先为新进程申请获得惟一的数字标示符，并从PCB集合中获取一个空白PCB；为新进程的程序和数据以及用户栈分配必要的内存空间；然后对PCB进程初始化；最后将新进程插入就绪队列中，等待被调度执行。

(8) 试说明进程撤销的过程。

系统调用进程终止原语来终止进程。首先根据被终止进程的标示符，从PCB集合中查找到该进程的PCB，从中读出该进程的状态，终止该进程的执行，如果该进程还有子孙进程，应该将它的所有子孙进程终止，防止它们成为不可控进程；然后回收进程所拥有的资源；最后将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其它程序来搜

31

附录一 自测题

集信息。

(9) 什么是线程？请比较它与进程的异同。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。线程基本上不拥有资源，只需要一些必不可少的资源(如程序计数器、一组寄存器和栈)。

进程和线程的差异：

150. 在传统的OS中，进程是拥有资源和独立调度分派的基本单位，在加入线程的

OS中，线程是代替进程成为独立调度和分派的基本单位，进程则仍是拥有资源的基本单位。

151. 并发粒度不同。除了不同进程的线程之外，同一个进程里的不同线程之间也可

以并发执行，所以线程拥有更好的并发性。

152. 拥有资源数量不同。进程是拥有资源的基本单位，线程除了一些在运行过程中

必不可少的资源外，基本上不拥有系统资源，它可以访问自己所在的进程的资源。

153. 管理开销不同。创建、撤销进程时系统都要为之分配和回收资源，所以进程切

换用的时间开销相对要多于线程。进程间通信很麻烦，而同一进程的线程则通过共享进程的资源很方便地通信和同步，同步开销小得多。

进程和线程有着很多相似的地方：都可以并发执行；都有就绪、执行、阻塞这些基本状态，也都可以在这些基本状态之间转换状态；从创建到撤销都有一定的生命周期；都需要同步工具。

(10) 处理器调度的层次有哪些？各层次的主要工作是什么？

处理器调度的层次分为三级调度：高级调度、中级调度和低级调度。

154. 高级调度：它需要做出两个决定，一个是要从驻留在外存后备队列中调入多

少个作业，二是要调入哪几个作业；然后为被选中的作业创建进程，并分配必要的系统资源，如内存、外设等，然后把新创建的进程放入就绪队列中，等待被调度执行。

155. 中级调度：中级调度主要涉及进程在内存和外存之间的交换。当系统中的内

存使用情况紧张时，中级调度把内存中暂时不能运行的进程调到外存中等待，等内存有足够的空闲空间时，再由中级调度决定将外存上的某些具备了运行条件的就绪进程调入内存，把其状态修改为就绪状态并挂在就绪队列中，等待进程调度。

156. 低级调度：按照一定的算法从就绪队列中选择一个进程，然后将处理器分配

给它。执行低级调度功能的程序称作进程调度程序，由它实现处理器在进程间的切换。

(11) 在批处理系统、分时系统、实时系统中，应分别采用哪种作业(进程)调度算法？

批处理系统采用先来先服务调度算法；分时系统采用时间片轮转法；实时系统采用高响应比优先调度算法。

32

附录一 自测题

(12) 说明时间片轮转调度算法的基本思路。

在采用时间片轮转调度算法的系统中，将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程，当然，进程可以未使用完一个时间片，就让出CPU(如阻塞)。这样可以保证就绪队列中的所有进程都有机会获得处理器而运行的机会，可以提高进程并发性和响应时间特性，从而提高资源利用率。

(13) 在一个单道批处理系统中，一组作业的到达时间和运行时间如下表所示。试计算使用先来先服务、短作业优先、高响应比优先算法时的平均周转时间和平均带权周转时间。

作业 1 2 3 4 到达时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 解：

用T表示周转时间，用W表示带权周转时间 FCFS的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.0 9.5 9.7 结束时间 9.0 9.5 9.7 9.8 周转时间 1.0 1.0 0.7 0.7 带权周转时间 1.0 2.0 3.5 7.0 FCFS的T =（1.0+1.0+0.7+0.7）/ 4 = 0.85 W =（1.0+2.0+3.5+7.0）/ 4 =3.375 SJF的作业调度情况如下： 作业 1 2 3 4 提交时间 8.0 8.5 9.0 9.1 运行时间 1.0 0.5 0.2 0.1 开始时间 8.0 9.3 9.0 9.2 结束时间 9.0 9.8 9.2 9.3 周转时间 1.0 1.3 0.2 0.2 带权周转时间 1.0 2.6 1.0 2.0 SJF的T=（1.0+1.3+0.2+0.2）/ 4 = 0.675 W =（1.0+2.6+1.0+2.0）/ 4 = 1.65 高响应比优先的作业调度情况如下： 作业 1 2 3 提交时间 8.0 8.5 9.0 运行时间 1.0 0.5 0.2 开始时间 8.0 9.0 9.6 结束时间 9.0 9.5 9.8 周转时间 1.0 1.0 0.8 带权周转时间 1.0 2.0 4.0 33

附录一 自测题 4 9.1 0.1 9.5 9.6 0.5 5.0 高响应比算法的T=（1.0+1.0+0.8+0.5）/ 4 = 0.825 W =（1.0+2.0+4.0+5.0）/ 4 = 3.0

(14) 什么是进程同步？什么是进程互斥？

同步是进程间的直接制约关系，这种制约主要源于进程间的合作。进程同步的主要任务就是使并发执行的各进程之间能有效地共享资源和相互合作，从而在执行时间、次序上相互制约，按照一定的协议协调执行，使程序的执行具有可再现性。

进程互斥是进程间的间接制约关系，当多个进程需要使用相同的资源，而此类资源在任一时刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待，进程的运行具有时间次序的特征，谁先从系统获得共享资源，谁就先运行，这种对共享资源的排它性使用所造成的进程间的间接制约关系称为进程互斥。互斥是一种特殊的同步方式。

(15) 进程执行时为什么要设置进入区和退出区？

为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为“进入区”代码；在退出临界区后，必须执行“退出区”代码，用于恢复未被访问标志。

(16) 同步机构需要遵循的基本准则是什么？请简要说明。

同步机制都应遵循下面的4条准则：

157. 空闲让进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区

运行有限的时间。

158. 忙则等待。当有一个进程在临界区时，其它欲进入临界区的进程必须等待，以

保证进程互斥地访问临界资源。

159. 有限等待。对要求访问临界资源的进程，应保证进程能在有限时间内进入临界

区，以免陷入“饥饿”状态。

160. 让权等待。当进程不能进入临界区时，应立即放弃占用CPU，以使其它进程有

机会得到CPU的使用权，以免陷入“饥饿”状态。

(17) 在生产者-消费者问题中，若缺少了V(full)或V(empty)，对进程的执行有什么影响？

如果缺少了V(full)，那么表明从第一个生产者进程开始就没有对信号量full值改变，即使缓冲池存放的产品已满了，但full的值还是0，这样消费者进程在执行P(full)时会认为缓冲池是空的而取不到产品，那么消费者进程则会一直处于等待状态。

如果缺少了V(empty)，例如在生产者进程向n个缓冲区放满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品时empty并没有被改变，直到缓冲池中的产品都取走了，empty的值也一直是0，即使目前缓冲池有n个空缓冲区，生产者进程要想再往缓冲池中投放产品会因申请不到空缓冲区而被阻塞。

34

附录一 自测题

(18) 在生产者-消费者问题中，若将P(full)和P(empty)交换位置，或将V(full)或V(empty)交换位置，对进程执行有什么影响？

对full和empty信号量的P、V操作应分别出现在合作进程中，这样做的目的是能正确表征各进程对临界资源的使用情况，保证正确的进程通信联络。

(19) 利用信号量写出不会出现死锁的哲学家进餐问题的算法。

对哲学家按顺序从0到4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为（i+1）%5。

semaphore chopstick[5]={1};

//定义信号量数组chopstick[5]，由于侉子是临街资源（互斥），故设置初值均为1。 Pi(){

//i号哲学家的进程 do{

if(i<(i+1)%5) {

wait(chopstick[i]);

wait(chopstick[(i+1)%5]); } else {

wait(chopstick[(i+1)%5]); wait(chopstick[i]); } eat

signal(chopstick[i]);

signal(chopstick[(i+1)%5]); think }while(1); }

(20) 什么是死锁？产生死锁的原因和必要条件是什么？

所谓死锁是指在一个进程集合中的所有进程都在等待只能由该集合中的其它一个进程才能引发的事件而无限期地僵持下去的局面。

产生死锁的原因可以归结为两点：1）竞争资源， 2）各进程之间的推进顺序不当。 产生死锁的必要条件有四个：1）互斥条件， 2）不剥夺条件， 3）请求和保持条件， 4）环路条件。

(21) 死锁的预防策略有哪些？请简要说明。

死锁的预防策略有三，说明如下：

161. 摒弃请求和保持条件：为摒弃请求和保持条件，系统中需要使用静态资源分配

35

附录一 自测题

法，该方法规定每一个进程在开始运行前都必须一次性地申请其在整个运行过程中所需的全部资源。此时，若系统有足够的资源，就把进程需要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它，即使有部分资源处于空闲状态也不分配给该进程。这样，当一个进程申请某个资源时，它不能占有其它任何资源，在进程运行过程中也不会再提出资源请求。这种方法破坏了请求和保持条件，从而避免死锁的发生。

162. 摒弃不剥夺条件：要摒弃“不剥夺条件”，可以使用如下策略：进程在需要资

源时才提出请求，并且进程是逐个地申请所需资源，如果一个进程已经拥有了部分资源，然后又申请另一个资源而不可得时，其现有资源必须全部释放。在这种方法中，进程只能在获得其原有资源和所申请的新资源时才能继续执行。 163. 摒弃环路等待条件：为确保环路等待条件不成立，可以在系统中实行资源有序

分配策略，即系统中的所有资源按类型被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。

(22) 某系统中有A、B、C、D四类资源，且其总数量都是8个。某时刻系统中有5个进程，判断下列资源状态是否安全？若进程P2申请资源(1，1，1，1)，能否为其分配？

进程 P0 P1 P2 P3 P4 Need A B C D 0 0 4 3 2 6 3 0 3 2 1 5 4 0 2 0 0 5 5 4 Allocation A B C D 0 0 2 2 1 1 0 0 2 1 0 3 2 0 0 0 0 2 2 2 解：

该时刻的安全状态：

由于Available向量为（3，4，4，1），所以Work向量初始化为（3，4，4，1） 此时的Work小于任意的Need[i]向量，所以系统处于不安全状态

由于Request2(1,1,1,1)

Allocation A P0 0 P1 1 P2 3 P3 2 P4 0 B 0 1 2 0 2 C 2 0 1 0 2 D 2 0 4 0 2 Need A 0 2 2 4 0 B 0 6 1 0 5 C 4 3 0 2 5 D 3 0 4 0 4 Available A 2 B 3 C 3 D 0 该时刻的安全性检测：

此时Available向量为（2,3,3,0），所以Work向量初始化为（2,3,3,0），此时的Work小于任意的Need[i]向量，所以系统处于不安全状态，所以不可以为P2分配资源

36

附录一 自测题

(23) 三个进程P1、P2、P3都需要5个同类资源才能正常执行直到终止，且这些进程只有在需要设备时才申请，则该系统中不会发生死锁的最小资源数量是多少？请说明理由。

系统中不会发生死锁的最小资源数量是13，这样可以保证当每一个进程都占有4个资源的时候，有一个进程可以获得最后一个资源后被运行，运行完毕后释放资源，于是其余进程也能顺利运行完，所以不会死锁。

(24) 在解决死锁问题的几个方法中，哪种方法最易于实现，哪种方法使资源的利用率最高？

预防死锁这个方法实现简单，效果突出；避免死锁这种方法系统吞吐量和资源利用率较高。

(25) 考虑由n个进程共享的具有m个同类资源的系统，如果对于i=1,2,3,…,n,有Need[i]>0并且所有进程的最大需求量之和小于m+n，试证明系统不会产生死锁。

解：

本题中只有一种资源，不妨设Max[i]为第i个进程的资源总共需要量，Need[i]为第i个进程还需要的资源数量，Allocation[i]表示第i个进程已经分配到的资源数量，Available为系统剩余的资源数，其中i=1,2,3,…,n。

假设此系统可以发生死锁。 系统剩余的资源数量为Available（Available>=0），由假设，因为系统处于死锁状态，所以Available个资源无法分配出去，所以每个进程的Need[i]都大于Available， 即 Need[i]>=Available+1

所以 ∑Need[i]>=n*(Available+1)=n*Available+n, ① 已经分配出去的资源数为m – Available;

即 ∑Allocation[i]=m – Available ② 由①式和②式可以得到：

∑Need[i] + ∑Allocation[i]>=n*Available+n+ m – Available=（n-1）*Available+m+n ③

又因为n>=1，所以（n-1）>=0，又因为Available>=0， 所以（n-1）*Available>=0 ④ 由③式和④式可以得到

∑Need[i] + ∑Allocation[i]>=0+m+n=m+n ⑤ 根据题意知： ∑Max[i]

所以 ∑Max[i]= ∑Need[i] + ∑Allocation[i] ⑦ 由⑥式和⑦式得：∑Need[i] + ∑Allocation[i]

由假设推出的⑤式和由题意推出的⑧式相矛盾，所以假设是错误的，即系统不会产生死锁。

(26) 某车站售票厅，在任何时刻最多可以容纳 20 名购票者进入，当售票厅中少于20

37

附录一 自测题

名购票者时，厅外的购票者可立即进入，否则需要在外面等待。若把一个购票者看作一个进程，请回答以下问题：

① 用信号量管理这些并发进程时，应该怎样定义信号量，写出信号量的初值以及信号量的各取值的含义。

② 根据所定义的信号量，写出相应的程序来保证进程能够正确地并发执行。 ③ 如果购票者最多为n个人，试写出信号量取值的可能变化范围(最大值和最小值)。 解：

①定义信号量S,初值为20，当s > 0时，它表示可以继续进入购票厅的人数，当s = 0时表示厅内已有20人正在购票，当s < 0时| s |表示正等待进入的人数。

②semaphore S=20;

begin

parbegin

procedure:begin repeat wait(s);

Enter and buy ticket; signal(s); until false;

end

parend end

③最大值为20，最小值为20-n

(27) 在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区；计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两个任务共享单缓冲区的同步算法。

解：

semaphore mutex = 1;

semaphore full = 0; semaphore empty = 1; begin

parbegin

collect: begin

repeat ??

collect data in nextp; wait(empty); wait(mutex);

buffer:=nextp;

38

附录一 自测题

signal(mutex); signal(full); until false;

end

compute: begin

repeat ??

wait(full); wait(mutex);

nextc:=buffer; signal(mutex); signal(empty);

compute data in nextc;

until false;

end parend end

(28) 桌上有一空盘，允许存放一只水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等着吃盘中的桔子，女儿专等着吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用，请用信号量实现爸爸、儿子和女儿3个并发进程的同步。

解：

本题中应设置三个信号量S、So、Sa，信号量S表示盘中是否为空，其初值为1；So

表示盘中是否有桔子，其初值为0；Sa表示盘中是否有苹果，其初值为0。同步描述如下：

爸爸: P(S); 儿子：P(So); 女儿：P(Sa); 将水果放入盘中 从盘子中取出桔子 从盘子中取出苹果 if (放入的是桔子) v(So)； V（S）； V（S）； else v(Sa)； 吃桔子 吃苹果；

(29) 设系统中仅有一类数量为M的独占型资源，系统中有N个进程竞争该类资源，其中各进程对该类资源的最大需求量为W。当M、N、W分别取下列值时，试判断哪些情形可能会发生死锁，为什么？

(1)M=2，N=2，W=1； (2)M=3，N=2，W=2； (3)M=3，N=2，W=3； (4)M=5，N=3，W=2；

解：

164. 不会发生死锁。因为两个进程需要的最多资源量都是1个，而系统拥有的资源

量正好是2个，两个进程都能顺利运行完，所以不会死锁。

39

附录一 自测题

165. 不会发生死锁。因为2个进程需要的最多的资源量都是2个，而系统拥有的资

源量是3个，所以总会有1个进程得到2个资源后被运行，运行完毕后释放资源，于是另一个进程也能顺利运行完，所以不会死锁。

166. 会发生死锁。当一个进程占有1个资源，另一个进程占有2个资源时，2个进

程都要再申请资源，但是系统已经没有资源了，所以就发生死锁了。

167. 不会发生死锁。因为三个进程需要的资源最大数量都是2个，而系统有5个资

源，所以至少有2个进程可以拿到足够的资源运行，运行完后再释放资源，最后一个进程也能得到运行，所以不会死锁。

a) 第3章 存 储 管 理

(1) 存储管理的任务和功能是什么？

存储管理的主要任务是：

168. 支持多道程序的并发执行，使多道程序能共享存储资源，在互不干扰的环境中

并发执行。

169. 方便用户，使用户减少甚至摆脱对存储器的管理，使用户从存储器的分配、保

护和共享等繁琐事物中解脱出来。 170. 提高存储器的利用率和系统吞吐量。

171. 从逻辑上扩充内存空间，支持大程序能在小的内存空间运行或允许更多的进程

并发执行。

为了完成上述任务，现代操作系统的存储管理应具有以下功能：

172. 存储空间的分配和回收。

173. 地址转换，实现逻辑地址到物理地址的映射。 174. 主存空间的共享。 175. 主存空间的保护。 176. 主存储空间的扩充。

177. 对换，对换的主要任务是实现在内存和外存之间的全部或部分进程的对换，即

将内存中处于阻塞状态的进程调换到外存上，而将外存上处于就绪状态的进程换入内存。对换的目的主要是为了提高内存利用率，提高系统的吞吐量。

(2) 为什么要配置层次式存储器？

为了解决CPU和存储器之间速度上的不匹配，在现代计算机系统中，存储系统通常采用层次结构，存储层次可粗略分为三级：最高层为CPU寄存器，中间为主存，最底层是辅存。根据具体功能还可以细分为寄存器、高速缓存、主存储器、磁盘缓存、辅存储设备(固定磁盘、可移动存储介质)5层。一个文件的数据可能出现在存储系统的不同层次中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。大容量的辅存常常使用磁盘，磁盘数据经常备份在可移动磁盘或者光盘上，以防止硬盘故障时丢失数据。

40

附录一 自测题

(3) 什么是逻辑地址？什么是物理地址？为什么要进行二者的转换工作？

逻辑地址是应用程序中使用的访存地址，有时也称为相对地址，由逻辑地址构成的地址空间称为逻辑空间。每个应用程序的逻辑地址空间都是从零号地址码开始的。 物理地址是内存储器的实际存储单元地址，有时也称为绝对地址，由物理地址构成的地址空间称为物理空间。物理地址空间也是从零号地址码开始的。

在多道程序环境下，程序逻辑地址空间和内存物理地址空间是不一致的。用户程序的逻辑地址可以是一维线性或多维线性，而内存中的每一个存储单元都有相应的内存地址相对应，属于一维线性地址。在将用户程序部分或全部地装入内存空间时，要实现逻辑地址到物理地址的映射。

(4) 什么是内部碎片和外部碎片？。

在一个分区内部出现的碎片(即被浪费的空间)称作内部碎片，如固定分区法就会产生内部碎片；

在所有分区之外新增的碎片称作外部碎片，如在动态分区法实施过程中出现的越来越多的小空闲块就是外部碎片，由于它们太小，无法装入一个进程，因而被浪费掉。

(5) 什么是分页和分段存储技术，两者有何区别？

在分页系统中，系统会把用户程序的地址空间划分成若干个大小相等的区域，每个区域称作一个页面或页。每个页都有一个编号，叫做页号。页号一般从0开始，如0，1，2，?，等。类似地，也把内存空间划分成若干和页大小相同的物理块，这些物理块叫“帧”(frame)或内存块。同样，每个物理块也有一个编号，块号也是从0开始依次顺序排列。系统为进程分配内存时，以块为单位将进程中的若干页分别装入多个可以不相邻接的块中。

在分段存储管理方式中，程序按内容或过程(函数)关系划分为若干个段，每个段定义一组逻辑信息，都有自己的名字。一个用户作业所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位进行内存分配，然后通过地址映射机构把段式虚拟地址转换为实际的内存物理地址。

分段和分页有许多相似之处，比如，二者在内存中都采用离散分配方式，而不是整体连续分配方式，而且都要通过地址映射机构来实现地址转换。但二者在概念上却完全不同，具体表现在下述三个方面：

178. 页是信息的物理单位，而段是信息的逻辑单位。分页是为了实现离散分配，减

少内存碎片，提高内存利用率。或者说，分页是由于系统管理的需要，而不是用户的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。段的长度不是固定的，取决于用户所编写的程序。分段的目的是为了能更好地满足用户的需要，更方便用户编程，更好地实现信息共享和保护。

179. 页的大小由系统确定，由系统把逻辑地址划分为页号和页内地址两部分，整个

系统只能有一种大小的页面；而段的长度却不固定，它取决于用户的程序。通常由编译程序在对源码进行编译时，根据程序的性质来划分。

180. 分页的进程地址空间是一维的，即单一的线性空间；而分段的进程地址空间是

二维的，由段号和段内地址两部分组成。

41

附录一 自测题

(6) 什么是虚拟存储器？列举采用虚拟存储器的必要性和可能性。

虚拟存储器是指在具有层次结构存储器的计算机系统中，具有请求调入和交换功能，为用户提供一个比实际物理内存容量大得多的可寻址的一种存储器系统，它能从逻辑上对内存容量进行扩充。

采用虚拟存储器的必要性：传统存储管理方式要求将作业全部装入内存之后才能运行，这一特征导致大作业和多个作业要求运行时系统无法满足；另外，传统存储管理方式具有驻留性，即作业装入内存直到运行结束，便一直驻留在内存中。尽管进程在运行中会因I/O等原因而长期处于阻塞状态，或有的程序模块在运行过一次后就不再需要，但它们都仍将继续占用宝贵的内存资源。

采用虚拟存储器的可能性：根据程序的局部性定理，应用程序在执行之前，没有必要全部装入内存，而只需要将那些当前要运行的部分页或段先装入内存即可运行，其余部分可以仍然留在外存。程序在执行时，如果它所访问的页(段)已经调入内存，便可继续执行下去。但如果程序所要访问的页(段)不在内存中(称为缺页或缺段)，此时程序可以利用操作系统提供的请求调页(段)功能，将它们调入内存，以便程序能够继续执行下去。如果内存已满，无法装入新调入的页(段)，则必须利用一定的页(段)置换功能，将内存中暂时不用的页(段)换到外存中，以腾出足够的空间来存放新调入的页(段)，从而保证程序的顺利执行。这样，一个大的程序就可以在较小的内存空间中执行。从用户的角度来看，该系统所具有的内存容量比实际内存容量大了很多。但实际上，用户所看到的大容量存储器是不存在的，只是虚拟的，故把这样的存储器称为虚拟存储器。

(7) 一个计算机系统的虚拟存储器，其最大容量和实际容量分别由什么决定？

虚拟存储器的最大容量由主存和辅存的容量之和确定。

虚拟存储器的实际容量由指令中表示地址的字长决定，也就是计算机的地址结构决定的。

(8) 如果内存划分为100KB、500KB、200 KB、300 KB和600 KB(按顺序)，那么，首次适应、最佳适应和最差适应算法各自将如何放置大小分别为215 KB、414 KB、110 KB和430 KB(按顺序)的进程，哪一种算法的内存利用率高？

见下图，在首次适应和最差适应算法中，最后430KB没有空间分配。由图可知，最佳适应算法的内存利用率高。

42

附录一 自测题

(9) 某操作系统采用分区存储管理技术。操作系统占用了低地址端的100KB的空间，用户区从100KB处开始共占用512KB，初始时，用户区全部空闲，分配时截取空闲区的低地址部分作为一个分配区。在执行了如下的申请、释放操作序列后：

作业1申请300KB、作业2申请100KB、作业1释放300KB、作业3申请150KB、作业4申请50KB、作业5申请90KB。

① 分别画出采用首次适应算法、最佳适应算法进行内存分配后的内存分配图和空闲区队列；

② 若随后又申请80KB，针对上述两种情况会产生什么后果？

采用首次适应算法、最佳适应算法进行内存分配后的内存分配图和空闲区队列图如下所示。

若随后又申请80KB，只有采用首次适应算法的内存分配还有空间可以分配，分配图如下：

(10) 某虚拟内存的用户编程空间共32页，每页的大小为1 KB，内存为16 KB，假设某时刻系统为用户的第0、1、2、3页分配的物理块为5、10、4、7，而该用户作业的长度为6页，试将16进制的虚拟地址0A5C、093C、1A5C转换成物理地址。

181. 虚拟地址为0A5C,对应的二进制数为：0000 1010 0101 1100。其中，页内偏移

量占10位地址码，为25C。页号占6位地址码，为2号页。因第2页存储在4号块中，其基地址为：0001 0000 0000 0000，即十六进制的1000H。这样，其物理地址为十六进制的125C。

43

附录一 自测题

182. 虚拟地址为093C，对应的二进制数为：0000 1001 0011 1100。其中，页内偏移

量占10位地址码，为13C。页号占6位地址码，为2号页。因第2页存储在4号块中，其基地址为：0001 0000 0000 0000，即十六进制的1000H。这样，其物理地址为十六进制的113C。

183. 虚拟地址为1A5C，对应的二进制数为：0001 1010 0101 1100。页内偏移量占

10位地址码，为25C。页号占6位地址码，为6号页。因为该用户作业的长度为6页，最大的页号为5号。因为虚拟地址为1A5C对应的6号页超出了地址范围，所以属于越界。

(11) 试述缺页中断与一般中断的主要区别。

程序在执行时，当访问的页面不在内存时，便产生缺页中断，请求操作系统将所缺页调入内存。中断处理程序将把控制转向缺页中断子程序。然后系统执行此子程序，把所缺页面装入主存中。接着处理器将重新执行缺页时打断的指令。缺页中断是一种特殊的中断，也就是说，缺页中断同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤，但与一般的中断相比，它又具有以下不同点：

184. 一般中断是一条指令完成后中断，而缺页中断是在一条指令执行时中断。通常，

CPU都是在一条指令执行完之后，才检查是否有中断请求到达。如果有，便去响应中断，否则，继续执行下一条指令。然而，缺页中断则是在指令执行期间，发现所访问的指令或数据不在内存时所产生和处理的。

185. 一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些

地址在不同的页中。

(12) 什么是抖动？产生抖动的原因是什么？

抖动是由于内存空间竞争引起的。当需要将一个新页面调入内存时，因内存空间紧张，不得不将一个老页面置换出去，而刚刚置换出去的老页面可能又要被使用，因此需要重新将它调入。若一个进程频繁地进行页面调入调出，势必加大系统的开销，使系统运行效率降低。通常称这种现象为该进程发生了抖动。

产生抖动的原因主要有：系统内的进程数量太多，致使一个进程分得的存储块过少；系统采用的置换算法不够合理。

（13) 考虑下面存储访问序列，该程序的大小为460字(以下数字均为十进制数字)：

10、11、104、170、73、309、185、245、246、434、458、364

该页面的大小为100字，该程序的基本可用内存为200字，计算采用FIFO、LRU和OPT置换算法的缺页次数。

因为页面的大小为100字，该程序的基本可用内存为200字，即可用内存为2块。程序的存储访问序列可转换为如下页面访问序列：

1、1、2、2、1、4、2、3、3、5、5、4

采用FIFO、LRU和OPT置换算法的访问序列如下：

44

附录一 自测题

由图可知FIFO算法的缺页次数为6次，LRU的缺页次数为7次，OPT的缺页次数为5次。

a) 第4章 设 备 管 理

(1) 简单叙述设备管理的任务和功能。 设备管理的主要任务包括：

186. 响应用户进程提出的I/O请求，选择和分配I/O设备进行数据传输操作。 187. 控制I/O设备和CPU(或内存)之间进行数据交换，提高设备和设备之间、CPU

和设备之间以及进程和进程之间的并行操作度，提高CPU与I/O设备的利用率，提高I/O设备的速度。 188. 方便用户使用设备，为用户提供友好的透明接口，把用户和设备硬件特性分开，

使得用户在编写应用程序时不必涉及具体的设备，系统按照用户的要求控制设备工作。另外，这个接口还为新增加的用户设备提供一个和系统核心相连接的入口，以便用户开发新的设备管理程序。 为了完成上述任务，设备管理应具有下述功能：

189. 设备分配: 计算机系统中的设备不允许用户直接使用，而是由操作系统统一分

配和控制。设备分配的基本任务是根据用户进程的I/O请求及系统当前的I/O资源情况，按照某种设备分配算法为用户进程分配所需的设备。 190. 缓冲管理: 为缓和CPU和I/O设备间速度不匹配的矛盾，提高CPU与I/O设备

之间以及各设备之间的并行性，现代操作系统都引入了缓冲技术。

191. 设备驱动: 设备驱动是指对物理设备进行控制，实现真正的I/O操作。设备驱

动的基本任务是实现CPU与设备控制器之间的通信，即接收由CPU发来的I/O命令，如读/写命令，转换为具体要求后，传给设备控制器，启动设备去执行；同时也将由设备控制器发来的信号传送给CPU，如设备是否完好、是否准备就绪、I/O操作是否已完成等，并进行相应的处理。

45

附录一 自测题

(2) 简单比较一下各种I/O控制方式的优缺点。

I/O控制方式有四种，即程序直接控制方式、中断控制方式、DMA方式和通道控制方式。它们各自的优缺点叙述如下：

192. 程序直接控制方式。优点是控制简单，不需要很多硬件支持。但CPU和外设

之间只能串行工作，且CPU的大部分时间处于循环测试状态，这使得CPU的利用率大大降低；CPU在一段时间内只能和一台外设交换数据信息，从而不能实现设备之间的并行工作；由于程序直接控制方式依靠测试设备状态标志来控制数据传送，因此无法发现和处理因设备或其它硬件所产生的错误。所以，程序直接控制方式只适用于那些CPU执行速度较慢且外设较少的系统。

193. 中断控制方式。优点是能实现CPU与设备、设备与设备间的并行操作，CPU

的利用率较程序直接控制方式大大提高。但I/O控制器的数据缓冲寄存器通常较小，且数据缓冲寄存器装满数据后将会发出中断，因此一次数据传送过程中中断次数较多，耗去了大量CPU时间；如果系统中配置的外设数目较多，且都以中断方式进行控制，则将耗去大量CPU时间或因CPU来不及处理而造成数据丢失。

194. DMA方式。与中断方式相比，DMA方式的优点是在一批数据传送完成后中断

CPU，从而大大减少了CPU进行中断处理的次数，并且DMA方式下的数据传送是在DMA控制器控制下完成的，在数据传输过程中无需CPU干预。但DMA方式仍有一定的局限，如对外设的管理和某些操作仍由CPU控制，且多个DMA控制器的使用也不经济。

195. 通道控制方式。通道是一个专管输入/输出控制的处理机。在通道控制方式下，

CPU只需发出I/O指令，通道就能完成相应的I/O操作，并在操作结束时向CPU发出中断信号。由此可见，CPU仅在I/O操作开始和结束时花极短的时间处理与I/O操作有关的事宜，其余时间都与通道并行工作，此外一个通道还能控制多台外设。但是，通道价格较高，从经济的角度出发不宜过多使用。

(3) 为什么要引入缓冲技术，其基本实现思想是什么？

缓冲技术是用来在两种不同速度的设备之间传输信息时平滑传输过程的常用手段。在操作系统的设备管理中，引入缓冲技术的主要原因可归结为以下几点。

196. 缓解CPU和I/O设备间速度不匹配的矛盾。 197. 减少对CPU的中断频率。

198. 提高CPU和I/O设备之间的并行性。

缓冲技术的实现思想是在CPU和外设之间设立缓冲，用以暂存CPU和外设之间交换的数据，从而缓和CPU与外设速度不匹配所产生的矛盾。缓冲的实现方法有两种：一种实现方法是采用硬件缓冲器，但由于这种方法成本太高，除一些关键部位外，一般情况下不采用硬件缓冲器；另一种实现方法是在内存划出一块存储区，专门用来临时存放输入/输出数据，这个区域称为缓冲区。

(4) 什么是SPOOLing系统，如何利用SPOOLing系统实现打印机的虚拟分配？

SPOOLing是外围设备同时联机操作，又称为假脱机输入/输出操作。SPOOLing技

46

附录一 自测题

术可将一台物理I/O设备虚拟为多台逻辑I/O设备，从而允许多个用户共享一台物理I/O设备。

SPOOLing技术是对脱机输入、输出系统的模拟，因此，它必须建立在具有多道程序功能的操作系统上，而且还应该有高速随机外存的支持，这通常是采用磁盘存储技术。 SPOOLing系统通常由以下3部分组成：

199. 输入和输出井：这是在磁盘上开辟的两个大存储空间。输入井是模拟脱机输入

时的磁 盘设备，用于暂存I/O设备输入的数据；输出井是模拟脱机输出的磁盘，用于暂存用户程序的输出数据。

200. 输入缓冲区和输出缓冲区：为了缓和CPU和磁盘之间速度不匹配的矛盾，在

内存中开辟两个缓冲区：输入缓冲区和输出缓冲区。输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井；输出缓冲区则用于暂存从输出井送来的数据，以后再传送给输出设备。

201. 输入进程和输出进程：SPOOLing利用两个进程来模拟脱机I/O时的外围控制

机。其中，输入进程模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU需要输入数据时，直接从输入井中读到内存；输出进程模拟脱机输出时的外围控制机，把用户要求输出的数据，先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备上。

(5) 为什么要引入设备独立性，如何实现设备独立性？

设备独立性又称为设备无关性。它指的是应用程序在使用设备进行I/O时，使用的是逻辑设备，而系统在实际执行时使用的是物理设备，由操作系统负责逻辑设备与物理设备的映射。引入设备独立性可以使设备的分配具有极大的灵活性，并易于实现I/O重定向。

系统为每个进程设置一张逻辑设备表LUT。当某进程用逻辑名来请求设备时，系统查阅系统设备表SDT，为它分配相应的可用物理设备。系统将这种用户逻辑设备与系统物理设备的映射建立在该用户的LUT中，并将该物理设备的驱动程序入口地址填入LUT中。以后，该进程利用逻辑设备名请求I/O操作时，系统通过查找LUT即可找到物理设备及其驱动程序。

(6) 设备分配中会出现死锁吗，为什么？

设备分配中会出现死锁。因为在不安全分配方式中，进程在发出I/O请求后仍继续运行，需要时则可以发出第二个、第三个I/O请求等。仅当进程所请求的设备已被另一个进程占用时，请求进程才进入阻塞状态。这种分配方式的优点是，一个进程可同时使用多个设备，使进程推进迅速。其缺点是分配不安全，因为它可能具备“请求和保持”条件，从而可能造成死锁。因此，在设备分配时，还应对本次的设备分配是否会发生死锁进行安全性检查，仅当分配是安全的情况下才可以进行设备分配。

(7) 在某个系统的某个运行时刻，有如下表示的磁盘访问的请求序列，假设磁头当前在15柱面，磁臂方向为从小到大。

47

附录一 自测题

15、20、9、16、24、13、29

请给出最短查找时间优先算法和电梯调度算法的柱面移动数，并分析为何通常情况下，操作系统并不采用效率更高的最短查找时间优先算法。

202. 按照最短查找时间优先算法，柱面的访问次序是： 15、16、13、9、20、24、29

令磁臂移动方向从小到大为正向，从大到小的方向为反向，那么，最短查找时间优先算法的柱面移动次数为：1+|-3|+|-4|+11+4+5=28。

203. 按照电梯调度算法，柱面的访问次序是： 15、16、20、24、29、13、9

电梯调度算法的柱面移动数为：1+4+4+5+|-16|+|-4|=34。

其中，最短查找时间优先算法比电梯调度算法的柱面移动数少6。因此说前者的效率更高一些。但是，由于磁头在访问操作中，可能不断有新的柱面请求加入，使磁头忙于应付一些距离较近的柱面请求，冷落了对远距离柱面的响应。长此以往，将可能造成某些远距离柱面处于“饥饿”状态。这就是通常情况下操作系统并不采用最短查找时间优先算法的原因。

(8) 为什么要引入磁盘高速缓存？什么是磁盘高速缓存？

磁盘的I/O速度远低于内存的访问速度，通常要低4~6个数量级。因此，磁盘的I/O已成为计算机系统的性能瓶颈。为了提高磁盘I/O的速度，其中最主要的技术便是采用磁盘高速缓存。

磁盘高速缓存并非通常意义下的内存和CPU之间增设的一个小容量高速存储器，而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，这里的高速缓存是一组在逻辑上属于磁盘，而物理上驻留在内存中的盘块。高速缓存在内存中可分成两种形式。第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存，其大小是固定的，不会受应用程序多少的影响；第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘I/O共享。

a) 第5章 文件管理

(1) 什么是文件，它包含哪些内容及特点？

文件是计算机系统中信息存放的一种组织形式，是在逻辑上具有完整意义的信息集合，并且有一个名字以供标识。

文件包含的内容有：源程序、二进制代码、文本文件、数据、表格、声音和图像等。 文件的特点如下：

204. 文件具有保存性。它被存储在某种存储介质上，长期保存和多次使用。

205. 文件是按名存取的。每个文件具有唯一的标识名，通过标识名(文件名)来存取

文件中的信息，而不需了解文件在存储介质上的具体物理位置。

206. 文件的内容是一组信息的集合。信息可以是源程序、二进制代码、文本文件、

48

附录一 自测题

数据、表格、声音和图像等。

(2) 文件系统要解决哪些问题？

文件系统的主要目标是提高存储空间的利用率，它要解决的主要问题有：完成文件存储空间的管理，实现文件名到物理地址的转换，实现文件和目录的操作，提供文件共享能力和安全措施，提供友好的用户接口。文件系统向用户提供了有关文件和目录操作的各种功能接口和系统调用，如命令接口、程序接口和交互接口等。

(3) 什么是逻辑文件？什么是物理文件？

逻辑文件时从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构。

物理文件是指文件在外存上的存储组织形式。它与存储介质的存储性能有关。

(4) 文件的物理组织方式有哪些，各有什么优缺点？

文件的物理组织方式有连续文件结构、链接文件结构和随机文件结构。

207. 连续文件结构是由一组分配在磁盘连续区域的物理块组成的。文件中的每一个

记录有一个序号，序号为i+1的记录，其物理位置一定紧跟在i号记录之后。 208. 链接文件结构是按顺序由串联的块组成的，即文件的信息按存储介质的物理特

性存于若干块中，一块中可包含一个逻辑记录或多个逻辑记录，或者一个逻辑记录占有多个物理块。每个物理块的最末一个字(或第一个字)作为链接字，它指向后继块的物理地址。文件的最后一块的链接字为结束标记(例如“?”)，它表示文件至本块结束。

209. 随机文件结构是实现非连续分配的另一种方式。在随机文件结构中，文件的数

据记录存放在直接存取型存储设备上，数据记录的关键字和其地址之间建立某种对应关系，并利用这种关系进行存取。通常有三种形式的随机文件结构：直接地址结构、索引结构和散列结构。

连续文件的优点是不需要额外的空间开销，只要在目录中指出起始块号和文件长度，就可以对文件进行访问，且一次可以读出整个文件。对于固定不变且要长期使用的文件(比如系统文件)，这是一种较为节省的方法。其缺点是：

210. 不能动态增长。因为在它后面如果已经记录了别的文件，则这一文件增长就可

能破坏后边的文件。如果后移下一个文件，则系统开销太大，甚至不可能。 211. 一开始就提出文件长度要求，而要用户预先知道文件长度不是太容易。

212. 一次要求比较大的连续存储空间，不一定好找。因为，如果外存上只有许多小

的自由空间，虽然其总容量大于文件的要求，但由于不连续，因而这些空间可能被浪费。

链接文件可以克服连续文件的上述缺点，然而它也存在如下缺点：

213. 由于在处理文件的一部分时必须得顺序访问，因而访问速度较慢，时间上比较

浪费。

214. 对块链接而言，每个块中都要有链接字。所以，要占用一定的存储空间。 相比之下，随机文件是一种比较好的结构，便于直接存取。但问题是，对于索引文

49

附录一 自测题

件应考虑如何有效地存储和访问索引表，对于散列文件应寻找一个较好的散列算法和确定解决冲突的办法。

(5) 什么是文件目录，常用的文件目录结构有哪些，各有什么特点？

文件目录是文件控制块的有序集合，是文件系统中最基本的数据结构。通过它可以将文件名转换为文件在外存的物理位置。每一个文件控制块在文件目录中都有一个目录项，其中登记着文件的名字、外存地址、文件长度、逻辑结构、物理结构、访问权限、文件建立和修改时间等。

文件目录通常是放在磁盘上的。它的组织形式有3种：单级目录、二级目录和多级目录。其中用得最普遍的是多级目录。

215. 单级目录是最简单的目录结构。在整个文件系统中只建立一张目录表，每个文

件占一个目录项，目录项中包含文件名、文件扩展名、文件类型、文件长度、文件物理地址以及其它文件属性。

216. 为了克服单级目录存在的缺点，改变单级目录中文件的命名冲突，并提高对目

录文件的检索速度，可以为每一个用户建立一个单独的用户文件目录UFD(User File Directory)。这些文件目录具有相似的结构，它由用户所有文件的文件控制块组成。另为，系统再建立一个主文件目录MFD (Master File Directory)，在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针。

217. 在大型文件系统中，通常采用三级或三级以上的目录结构，以提高对目录的检

索速度和文件系统的性能。多极目录结构又称为树型目录结构。多级目录结构是一棵倒向的有根树，树根是根目录；从根向下，每一个树枝是一个子目录，而树叶则是文件。树形目录有许多优点：它较好地反映了现实世界中具有层次关系的数据集合和较确切地反映系统内部文件的分支结构，不同的文件可以重名，只要它们不位于同一子目录中即可，易于规定不同层次或子树中文件的不同存取权限，便于文件的保护、保密和共享等。

(6) 某操作系统的磁盘文件空间共有500块，若用字长为32位的位示图管理磁盘空间，试问：①位示图占用多少磁盘空间？②第i字第j位对应的磁盘块号是多少？

① 占用16个字的存储空间。 ② 32?i+j。

(7) 试说明对索引文件和索引顺序文件的检索方法。

索引文件中，每一个主文件的记录都要建立一条索引。这里，主文件的记录可以是变长的，键值可以是无序的。索引表是定长的和有序的，适合采用折半检索法进行检索。

索引顺序文件中，主文件中的记录分成若干组，每一组的第一条记录建立一条索引项。整个索引文件是按键值排序的，系统可采用折半检索法对文件进行快速检索。检索到记录所在的外存块后，读出该块，再进行顺序查找和比较，最后找到所需要的记录。

(8) 什么是索引文件？为什么要引入多级索引？

索引文件中每条主文件的记录都建立一个索引记录，因而需要为主文件建立索引

50