典型题目讲解

09年考研操作系统试题

21.假设某计算机的存储系统由Cache和主存组成，某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是(D) A．5% B.9.5% C.50% D.95%

22.下列选项中，能引起外部中断的事件是(A)

A．键盘输入 B.除数为0 C.浮点运算下溢 D.访存缺页 23.单处理机系统中，可并行的是D

I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备 A．I、II和III B. I、II和IV C. I、III和IV D. II、III和IV 24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是 D A．时间片轮转调度算法 B.短进程优先调度算法 C.先来先服务调度算法 D.高响应比优先调度算法

25.某计算机系统中有8台打印机，有K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是 C A．2 B.3 C.4 D.5

26．分区分配内存管理方式的主要保护措施是 A

A．界地址保护 B.程序代码保护 C.数据保护 D.栈保护

27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是C A．2的8次方字节 B.2的16次方字节 C.2的24次方字节 D.2的32次方字节 28.下列文件物理结构中，适合随机访问且易于文件扩展的是B A．连续结构 B.索引结构

C.链式结构且磁盘块定长 D.链式结构且磁盘块变长

29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是A

A．110，170，180，195，68，45，35，12 B.110，68，45，35，12，170，180，195 C.110，170，180，195，12，35，45，68 D.12，35，45，68，110，170，180，195

30.文件系统中，文件访问控制信息存储的合理位置是A

A．文件控制块 B.文件分配表 C.用户口令表 D.系统注册表

31．设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是B A．0、1 B.1、1 C.1、2 D.2、1

32．程序员利用系统调用打开I/O设备时，通常使用的设备标识是A A．逻辑设备名 B.物理设备名 C.主设备号 D.从设备号

45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

1

信号量empty表示缓冲区中空闲单元，其初值应设置为N；oddfull表示缓冲区中装有奇数的单元，其初值应设置为0；evenfull表示缓冲区中装有偶数的单元，其初值也应设置为0。另外还需设置一个互斥信号量mutex以防止三个进程同时对缓冲区进行操作，其初值应设置为1。

P1进程可描述为： P1(){ int number; While(1){

Number=produce(); Wait(empty); Wait(mutex); Put();

If(number%2==0) signal(evenfull); else signal(oddfull); signal(mutex); } }

P2(){

While(1){

Wait(oddfull); Wait(mutex); getodd();

signal(empty); signal(mutex); countodd(); } }

P3(){

While(1){

Wait(evenfull); Wait(mutex); geteven(); signal(empty); signal(mutex); counteven(); } }

46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示。

页表内容 页号 页框（Page Frame）号 有效位（存在位） 0 1 2 101H — 254H 1 0 1 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为

2

2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2） 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。 （1）

①： 逻辑地址2362H——页号为2，页内地址为362H。

先访问TLB，时间为10ns，未命中；再去访问页表，时间为100ns，获得对应页在内存，其对应的物理块号254H，从而拼接成物理地址254362H，同时将第2页的信息装入TLB中；最后根据这个物理地址访问内存，时间为100ns。故，访问到虚地址对应单元的数据总共需要210ns.

②： 逻辑地址1565H——页号为1，页内地址为565H。

先访问TLB，时间为10ns，未命中；再去访问页表，时间为100ns；因对应页不在内存，将产生缺页中断，中断处理的时间为108ns（其中包括更新页表和TLB等），在中断处理时，因为内存已满，须淘汰一个内存页，LRU算法将选择淘汰第0页；接着重新执行指令，访问TLB（10ns）便可得到页对应的物理块号，拼接成物理地址，最后根据这个物理地址访问内存，时间为100ns。故，访问到该虚地址对应单元的数据总共需要：10+100+108+10+100=328ns.

③： 逻辑地址25a5H——页号为2，页内地址为5a5H。

先访问TLB，时间为10ns，命中(在①时已将该页信息装入TLB)，获得对应的物理块号254H，从而拼接成物理地址2545a5H；最后根据这个物理地址访问内存，时间为100ns。故，访问到虚地址对应单元的数据总共需要110ns.

（2） 逻辑地址1565H的页号为1，页内地址为565H。按照上述访问序列，在访问到该地址时，查页表时将发生缺页中断，中断处理时因内存已满，须淘汰一个内存页，由于第2页刚被访问过，不能被淘汰出去，所以LRU算法将选择淘汰第0页，也就是说，第1页将存放内存的第101H号页框中。因此逻辑地址1565H对应的物理地址为101565H.

第一章操作系统引论

1.1操作系统目标和作用

1、下列选择中，哪些不是操作系统关心的主要问题。（浙大2003） （1）管理计算机裸机；（2）设计提供用户与计算机硬件系统间的界面； （3）管理计算机系统资源；（4）高级程序设计语言的编译器。 2、说明操作系统与硬件、其他系统软件以及用户之间的关系。

提示：操作系统是覆盖在硬件上的第一层软件，他管理计算机的硬件和软件资源，并向用户提供良好的界面。操作系统与硬件紧密相关，它直接管理着硬件资源，为用户完成于硬件相关的操作，从而极大地方便了用户对硬件资源的使用，并提高资源的利用率。操作系统又是一种特殊的系统软件，其他的系统软件都运行在操作系统基础之上，

3

可获得操作系统提供的大量服务，即操作系统是其他系统软件与硬件的接口。而一般用户使用计算机除了需要操作系统支持外，还需要用到大量的其他系统软件和应用软件，使其工作更加方便和高效。它们之间的层次关系为：其他用户，应用程序，其他系统软件，操作系统，计算机硬件。

3、选择：从用户角度看，操作系统是（）。（选项：计算机资源的管理者；计算机工作流程的组织者；用户与计算机之间的接口；由按层次结构组成的软件模块的集合。）

1.2操作系统发展过程

1、引入多道程序技术的前提条件之一是系统具有（3）（西电00） （1）多个cpu；（2）多个终端；（3）中断功能；（4）分时功能

2、判断：所谓多道程序设计，即指每一时刻有若干个进程在执行。F（南京大学00） 3、判断：采用多道程序设计的系统中，系统的程序道数越多，系统效率越高。F （西电01）

4、判断：由于采用了分时技术，用户可以独占计算机的资源。F

5、分布式操作系统与网络操作系统本质上的不同之处在于（实现各计算机之间的通信；共享网络中的资源；满足较大规模的应用；系统中若干台计算机相互协同完成同一任务） 6、若程序A和B单独执行时分别用TA和TB，TA=1h，TB=1.5h，其中处理器工作时间分别为TA=18min，TB=27min。如果采用多道程序设计方法，让A，B并行工作，假定处理器利用率达到50%，另加15min系统开销，请问系统效率提高百分之几？ 提示：1-[(18+27)/50%+15]/2.5h

7、在操作系统中引入并发可以提高系统效率，若有两个程序A和B，A程序执行时所做的工作按次序需要用cpu：10s，设备1：5s，cpu：5s，设备2：10s，cpu10s；程序B执行时所做的工作按次序需要用设备1：10s，cpu：10s，设备2：5s，cpu：5s，设备2：10s。如果在顺序环境下执行两个程序，则cpu的利用率为（）；如果在并发环境下执行两个程序，则cpu的利用率为（）。 8、设某计算机系统有一个cpu、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到cpu运行，进程B后运行。进程A 的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms。进程B 的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可用甘特图）并说明：（1）运行过初中，cpu有无空闲等待？计算cpu利用率。（2）进程A和B运行过程中有无等待现象？

9、判断：多道程序设计是利用了CPU和通道的并行工作来提高系统利用率的。 10、判断：多道程序设计可以缩短系统中作业的执行时间。

11、判断：在一个兼顾分时操作系统和批处理系统中，通常把终端作业称为前台作业，而把批处理型作业称为后台作业。

12、判断：批处理系统不允许用户随时干预自己程序的运行。 13、判断：Windows操作系统完全继承了分时系统的特点。

4

14、( C)不是Unix系统的特色。

A.“交互的分时系统” B.“以全局变量为中心的模块结构” C.“模块之间调用关系简明” D.“可以分成内核和外壳”

15、实现多道程序系统的最主要硬件支持是什么？ 解 中断系统和通道技术。

(1) 很多进程的切换是由时钟中断引起的，尤其是分时系统。用户程序进行系统调用时通过软中断来实现，如TRAP。通道和外设的操作也要向操作系统发送中断。 (2) 在多道程序系统中，当CPU要求在主存和外设间传输数据时，通过发出I/O指令命令通道工作，通道独立地在内存和外设间进行数据传输，I/o操作完成后，通道以中断方式通知CPU，从而实现了CPU计算与I/O操作的并行。

16、填空：在一台主机上同时连接多台终端，多个用户可以通过终端同时交互使用计算机资源，这种系统称为（）操作系统；允许多个用户将多个作业提交给计算机集中处理的操作系统称为（）；计算机系统能及时处理过程控制数据并作出响应的操作系统称为（）。 17、分时系统的一个重要性能是响应时间，下述（）因素与改善响应时间有关： 选项：CPU速度快；时间片；轮转调度法；优先数+非抢占式调度算法；进程数目增加。

18、衡量整个计算机性能的指标有（）：用户接口；资源利用率；系统中进程数量；吞吐量；周转时间。

19、判断：单用户系统中，任何时刻，只能有一个用户进程。

20、填空：操作系统的主要性能参数有（系统资源利用率、系统吞吐量）

21、下列作业类型中，适合在分时系统中运行的有_____、______；适合在批处理系统中运行的有_____、______。（选项：学习编程；数据统计；发送电子邮件；整理硬盘） 22、判断：linux是与Unix兼容的操作系统，它不仅仅是只能运行在PC机上。

1.3操作系统的基本特性

1、判断：并发是并行的不同表述，其原理相同。（清华1998） 2、并发性的概念是（）。（北京理工01） 3、在单处理机系统中实现并发技术后，判断：

（1）各进程在某一时刻并行运行，cpu与外设间并行工作； （2）各进程在一个时间段内并行运行，cpu与外设间串行工作；

（3）各进程在一个时间段内并行运行，cpu与外设间并行工作。（四川大学01） 2、填空：现代操作系统的两个最基本的特征是（）、（）。（川大2005）

1.4操作系统的主要功能

1、在用户程序中要将一个字符送到显示器上显示，使用操作系统提供的（）接口：（系统调用；函数；原语；子程序）

5

2、系统调用的作用是什么？请给出实现系统调用的步骤。

3、用户程序向系统提出使用外设的请求方式是（）：作业申请；原语；系统调用；I/O指令。

4、判断：系统调用与用户程序之间的调用不同之处是处理机状态的改变。 5、判断：命令解释程序是操作系统的一个程序，它必须在核心态下运行。

6、用户进程通过系统调用fork创建一个新进程，在执行系统调用前，用户进程运行在（）；在执行fork过程中，用户进程运行在（）。（选项：系统态；用户态；系统态或用户态；内部态）

6、判断：系统调用命令就是访管指令，它的功能是由硬件直接提供的。 7、比较一般的过程调用和系统调用：

答：（1）运行在不同的系统状态：一般过程调用，其调用程序和被调用程序都运行在相同的状态：系统态或用户态。而系统调用的调用过程运行在用户态，被调用过程运行在系统态。（2）通过软中断进入：一般过程调用不涉及系统状态状态转换，可直接由调用过程转向被调用过程；而系统调用通常是通过软中断机制，先由用户态转换为系统态，经核心分析后，再转向相应的系统调用处理子程序。（3）返回问题：一般过程调用在被调用过程执行完后将返回到调用过程继续运行。但对于采用抢占式调度的系统中，当从系统调用返回时，有可能会重新调度。

第二章 进程管理

2.1 进程的基本概念

1、进程申请打印输出完成向系统发出中断后，进程的状态变化为（）。（南京邮电01） 2、判断：当一个进程从等待态变为就绪态，则一定有一个进程从就绪态变成运行态。 3、如果一个单处理机系统中有N个进程，

? 运行进程最多几个，最少几个？ ? 就绪进程最多几个，最少几个？ ? 等待进程最多几个，最少几个？

解答： 运行进程最多1个，最少0个；

就绪进程最多N-1个，最少0个； 等待进程最多N个，最少0个；

4、判断：在一个N个进程的单处理机系统中，有可能出现N个进程都被阻塞的情况。 5、补充内容：

特权指令

指具有特殊权限的指令。这类指令只用于操作系统或其他系统软件，一般不直接提供给用户使用。 在多用户、多任务的计算机系统中特权指令必不可少。它主要用于系统资源的分配和管理，包括改变系统工作方式，检测用户的访问权限，修改虚拟存储器管理的段表、页表，完成任务的创建和切换等。 常见的特权指令有以下几种:

6

（1）有关对I/O设备使用的指令 如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。

（2）有关访问程序状态的指令 如对程序状态字（PSW）的存取指令等。 （3）存取特殊寄存器指令 如存取中断寄存器、时钟寄存器、设置中断屏蔽、关中断、置基址寄存器等指令。 （4）其他指令：清内存，停机

6、关于进程状态，判断：

（1）进程一旦形成，首先进入的是运行状态。 （2）一个进程必须经过进程的三个基本状态才能结束。 （3）进程可能同时处于某几种基本状态中。

（4）分时系统中，一个正在运行的进程的时间片到，该进程将转入就绪状态。

7、只能在管态下执行的指令有（从内存中取数指令；把运算结果写内存指令；算术运算指令；I/O指令；读时钟指令；置时钟指令、寄存器清零指令；屏蔽所有中断；改变存储器映像图；改变磁盘空间分配位图；） 8、在一个分时系统中，用户提交了一个作业，作业内容包括：请求内存缓冲区；计算并将结果存于内存缓冲区；请求打印机；将缓冲区中的内容在打印机上输出；释放打印机；释放内存；结束。

讨论进程可能的状态变化。

9、判断：在单CPU的系统中，任何时刻都有一个进程处于运行状态。 10、判断：进程申请CPU得不到满足时，其状态变为阻塞态。 11、能从1种状态转变为3种状态的是（）：就绪；阻塞；完成；执行 12、判断：进程在运行中，可以自行修改自己的PCB。

13、判断：当进程申请CPU得不到满足时，它将处于阻塞状态。

14、判断：当进程由执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中。 15、操作系统通过PCB来控制和管理进程，用户进程可从PCB中读出与本身运行状态相关的信息。

16、若一个进程实体由PCB、正文段、数据段和堆栈段组成，请指出下列C语言程序中的内容位于哪一段中：外部变量、局部变量、函数调用实参传递值、用molloc（）要求动态分配的存储器、常数值。

（局部变量：堆栈段；静态局部变量：数据段；外部变量：数据段；函数调用参数：堆栈段；malloc分到的存储区：数据段）

17、unix为什么要把PCB分为进程表项（Proc区）和U区？

提示：因为进程表项中的内容对核心来说必须总是可存取的，而U区中的域只能由正在运行的进程来存取。只有当创建一个进程时，核心才为其分配U区空间，那些不与任何进程相联系的进程表项是不需要U区的。

18、以unix为例，说明Operating System Function Execute Within User Process 的实现模型。

7

提示：unix存在两类进程：系统进程和用户进程。前者在核心态下执行os代码，后者在用户态下执行用户程序。当用户进程因中断或系统调用进入内核态，此时发生了模式切换，但没有发生进程上下文切换。这时，系统进程开始执行，而这两个进程（用户/系统进程）使用同一个PCB，实质是一个进程，仅执行的程序不同，映射的物理地址空间不同，使用的堆栈不同。

19、进程和程序直接可以形成一对一、一对多、多对一、多对多的关系，请分别举例说明在什么情况下会形成这样的关系？

提示：进程与程序一对多：一个进程中执行多个程序；多对一：分时系统中的编译程序为多个终端用户的源程序进行编译；多对多：

20、UNIX系统中进程由三部分组成：进程控制块，正文段和数据段。这意味着一个程序的正文与数据可以是分开的，这种分开的目的是为了( ABC ) A.可共享正文 B.可共享数据

C.可重入 D.方便编程 E.以上全部

21、对于运行于unix系统的以下程序，其执行后 的输出结果是（） Void main() { }

22、在分时系统中，导致进程创建的典型事件是（2）（选项：用户注册；用户登录；用户记账）；在批处理系统中，导致进程创建的典型事件是（2）（选项：作业录入；作业调度；进程调度）；由系统专门为允许中的应用进程创建新进程的事件是（）（选项：分配资源；进行通信；共享资源）；（）（选项：分配PCB；分配内存；分配CPU；分配外设；插入就绪队列）不是创建进程所必需的步骤。

23、系统有n（n＞2）个进程，且当前不再执行进程调度程序，判断下述情况十分可能发生： （1）有一个运行进程，没有就绪进程，n-1个阻塞进程。 （2）有一个运行进程，有一个就绪进程，n-2个阻塞进程。 （3）有一个运行进程，n-1个就绪进程，没有阻塞进程。 （4）没有运行进程，有2个就绪进程，n-2个阻塞进程。

24、判断：在单处理机上，进程就绪队列和阻塞队列都只能由一个。 25、判断以下关于unix进程组成的说法：

（1）进程由进程控制块、正文段、数据段三部分组成； （2）进程控制块包括基本控制块和扩充控制块，常驻内存； （3）正文段是指可供多个进程共享的程序；

（4）数据段分为用户栈区、用户数据区和系统工作区。 提示：

8

printf(“hello1”); Fork(); printf(“hello2”);

Proc结构或称进程表项进程控制块User结构Unix进程正文段：可共享程序段用户栈区数据段用户数据区：非共享程序段和用户工作数据系统工作区：包括核心栈和user结构 26、下列内容中属于进程上下文的是：（）（选项：用户打开文件表；PCB；中断向量；核心栈）

27、根据Bernstein条件，则如下4条语句中： S1：a=x+y; S2: b=z+1; S3:c=a-b; S4:w=c+1;

S1和S2能否并发执行？S3和S4呢？ 28、某系统的进程状态变迁如图所示：（1）说明一个进程发生变迁1、3和5的原因；（2）当发生一个变迁时可能引起另一个变迁的发生，则这两个变迁称为因果变迁。下述因果变迁是否会发生？如果有可能的话，会在什么情况下发生？3→5；3→2；2→1；4→1；4→5. （3）根据此状态变迁图说明该系统的调度策略和调度效果。

运行2低优先就绪135阻塞4高优先就绪首次选择100ms，以后选择500ms 2.2 进程控制：

1、下列程序执行时，系统的输出可能是什么？ {

a=55;

9

}

pid=fork(); if (pid==0){ } Else { }

sleep(7);

Printf(“a=%d\\n”,a); Wait(0);

Printf(“parent child exited\\n”); sleep(5); a=99; sleep(5);

printf(“child leaving\\n”); exit(0);

2.3进程同步：

Int I;

(for i=1;i<=10;i++) Total=total+1;

1、临界资源：P1、P2两个进程执行代码相同，共享total变量：

问：最后total可能的最小值、最大值（2，20） 2、判断：临界区就是临界资源所在的区域。

3、所谓临界区是指（一个缓冲区、一段数据区、同步机制、一段程序）（南京理工01） 4、判断：对临界资源应采用互斥的方式来实现共享。（北京理工02）

5、下面活动分别属于进程的哪种制约关系？（1、几个同学去图书馆借书；几个同学在打篮球；流水生产线上的各道工序；对一个产品的生产和消费；）（北京理工96） 6、填空：若信号量 初值为3，当前值为-3，则表示有（）个进程在该信号量上等待？ 7、下面是两个并发执行的进程，他们能正确运行吗？若不能请修改。（北航02） Parbegin

Int x; P1 {

int y,z;

10

P2: { }

}

X=1;y=0;

If x>=1 then y=y+1; Z=y;

x=0;t=0;

If x<=1 then t=t+2; U=t;

8、双进程临界区问题的算法，其中布尔型数组blicked[2]初始值为{false，false}，整型turn初始值为0，id代表进程编号（0，1），请说明正确否？（违反忙则等待原则） Do{

blocked[id]=true; While(turn!=id) { }

编号为id的进程的临界区 Blocked[id]=false;

编号为id的进程的非临界区 }while（true）；

9、在具有N个进程的系统中，允许M个进程（N≥M≥1）同时进入它们的临界区，其信号量S的值的变化范围是（），处于等待状态的进程数最多是（）个。 10、判断以下解决双进程临界区问题的算法是否正确： Process Pi(i=0,1):

Do{

Flag[i]=true; While(flag[1-i]);

critical section flag[i]=false;

While(blocked[1-id]); Turn=id;

remainder section

}while(1);

11

11、用V操作唤醒一个等待进程时，被唤醒进程的状态变为（）。（选项：运行；等待；就绪；完成）

12、若有3个进程共享一个互斥段，每次最多允许两个进程进入互斥段，则信号量的变化范围是（）。 13、关于进程同步与互斥的说法，判断：

（1）进程的同步与互斥都涉及到并发进程访问共享资源的问题。 （2）进程的同步是进程互斥的一种特殊情况。

（3）进程的互斥是进程同步的特例，互斥进程是竞争共享资源的使用，而同步进程之间必然存在依赖关系。

（4）进程互斥和进程同步有时候也称为进程同步。 14、判断：临界区是不可中断的程序。

15、判断：如果在加锁法实现互斥时，将未进入临界区的进程排队等待，从而让其有被再调度 的机会，加锁法和P、V原语实现互斥时其效果是相同的。

16、由于并发进程执行的随机性，一个进程对另一个进程的影响是不可预测的，甚至造成结果的不正确，下面对造成不正确的因素的描述正确的是：（）（选项：与时间有关；与进程占用的处理机有关；只与执行速度有关；只与外界的影响有关）

17、有两个优先级相同的进程A、B如下，令信号量S1和S2的初值均为0，已知Z=3，则A、B并发运行结束后X、Y、Z的值分别是：

A Y=2; Y=Y+3; V(S1); Z=Y+0; P(S2); Z=Y+Z; B X=2; X=X+3; P(S1); X=X+Y; V(S2); Y=Y+Z; 18、信号量是一个整型变量，可在其上做加1或减1的操作。

2.4 经典进程同步问题

1、一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中，超市的工作人员也用三轮车从仓库中取货去出售。假设共有3辆三轮车，仓库中只能容纳10辆三轮车的货物，且每次从汽车上取货只能共给一辆三轮车，仓库也只能容纳一辆三轮车进入。用信号量实现向仓库中送货及从仓库中取货的同步算法。 2、有一个仓库，可以存放A、B两种产品，但要求：

① 每次只能存入一种产品（A或B）； ② A产品数量－B产品数量

其中M、N是正整数，使用P、V操作描述产品A与产品B的入库过程。

12

3、一组生产者进程和一组消费者进程共享10个缓冲区，每个缓冲区可以存放一个整数；生产者进程每次一次性向3个缓冲区写入3个整数，消费者进程每次从缓冲区取出一个整数。用信号量实现进程的同步关系。 4、写者优先的读者写者问题：

wmutex:semaphore=1 //读者与写者之间、写者与写者之间互斥使用共享数据

S：semaphore=1 //当至少有一个写者准备访问共享数据时，它可使后续的读者等待

写完成

S2：semaphor＝1 //阻塞第二个以后的等待读者

readcount,writecount: semaphore = 0,0; //当前读者数量、写者数量 mutex1 :semaphore = 1 //多个读者互斥使用readcount mutex2 :semaphore = 1 //多个写者互斥使用writecount Cobegin:

Reader: begin Repeat Wait（S2）； wait(S);

wait(mutex1)

if readcount=0 then wait(wmutex); readcount++; signal (mutex1); signal(S); signal（S2）； reading… wait(mutex1); readcount--;

if readcount=0 then signal(wmutex); signal(mutex1); until false; begin; writer: begin repeat;

wait(mutex2);

if writecount=0 then wait(S); writecount++;

signal （mutex2）; wait(wmutex); writing…

signal(wmutex); wait(mutex2); writecount--;

if writecount=0 then signal(S);

signal （mutex2）; until false; end;

13

coend;

5、有座可双向通行的单车道桥，最大载重负荷为4辆汽车。请给出任一辆车通过该桥的管理算法。

6、设公共汽车上，司机和售票员的活动分别是：

司机的活动：启动车辆； 正常行车； 到站停车； 售票员的活动：

关车门； 售票； 开车门；

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。

设两个信号量S和C，初值为S＝0；C＝0；

司机： L1： 正常行车 售票员： L2： 售票

到站停车 P（S） V（S） 开车门 P（C） 关车门 启动开车 V（C） GO TO L1 GO TO L2

7、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。 S, S1, S2 :semaphore=1,0,0; Cobegin:

Process Father:

Begin:

L1: P(S);

Put Apple; V(S1)； GO TO L1； End； Process Mother:

Begin:

L2: P(S);

Put Orange; V(S2)； GO TO L2； End； Process Son:

Begin:

14

L3: P(S2);

Get Orange; V(S)；

GO TO L1； End；

Process Daughter:

Begin:

L4: P(S1); Get Apple; V(S)；

GO TO L4； End； CoEnd;

8、进程A1、A2、……An1通过m个缓冲区向进程B1、B2……Bn2不断地发送消息。发送和接收工作遵循如下规则：

（1） 每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度； （2） 对每一个消息，B1，B2，…，Bn都必须接收一次，读入各自的数据区内； （3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。

解答：本题是生产者——消费者问题的一个变形，一组生产者A1，A2，…….An1和一组消费者B1，B2，……Bn2公用m个缓冲区，每个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。 Mutex,empty[n2],full[n2]:semaphore; Mutex=1; //多进程互斥使用缓冲区

empty[0,1,……n2]={m,m,……m}; full[0,1,…..n2]={0,0,……0}; int I; Cobegin:

Process Ai Begin: Loop:

Int I;

For ( I=0; I

将消息放入缓冲区； v(Mutex);

for( I=0; I

Process Bi Begin:

15

6、段式存储管理中分段是由用户决定的，因此（）

（1）段内的地址和段间的地址都是连续的。（2）段内的地址是连续的，而段间的地址是不连续的。（3）段内的地址是不连续的，而段间的地址是连续的。（1）段内的地址和段间的地址都是不连续的。

4.6虚拟存储器基本概念

1、简述“虚拟”在操作系统中的应用。

提示：虚拟存储管理、虚拟设备、分时系统中的cpu等。

2、判断：虚拟存储器的大小等于或小于内存和外存的容量之和。（西电） 3、判断：虚拟存储器的大小可比主存容量大，也可比主存容量小。（电子科大） 4、判断：cpu的地址空间决定了计算机的最大存储容量 5、交换扩充了主存，因此，交换也实现了虚拟存储器，对吗？

6、总体上说，按需调页是个很好的虚拟内存管理策略。但是有些情况并不适合，判断：（堆栈；线性搜索；矢量运算；二分法搜索（浙大06） 提示：按需调页适合运行的程序师具有局部性现象的程序，即最好是对数据进行顺序访问的程序。矢量运算就是数组运算，数组存放是连续的，所以数组运算就是临近的数据的运算，满足局部性。二分法搜索先找中间的那个元素，如果没有找到，就再找前面数过去的1/4位置或倒数1/4的位置，再这样找下去，显然每次搜寻的元素都不是相邻的，所以不满足局部性。

7、判断：请求页式存储管理系统中，若把页面的大小增加一倍，则缺页中断次数也减少一半。

8、在虚拟分页存储管理中，（）没有优先考虑最近使用过的页面。（选项：最优页面替换算法；第二次机会算法；LRU算法；时钟页面替换算法；NFU算法；最近未使用页面算法）一台小型计算机有4个页框（页0-页3）。在第一个时钟周期时R位是0111（页0是0，其他是1）。在随后的时钟周期中这个值是1011，1010，1101，0010，1010，1100，0001。如果使用带有8位计数器的老化算法，最后一个周期后页2的计数器值是（）。 9、在一个32位计算机的虚拟页式存储管理系统中，怎样解决页表非常庞大的问题？请给出具体解决方案（假设页面大小为4K，用户空间为2GB，每个内存块用4字节表示）

10、测得某个采用按需调页策略的系统部分状态数据为：CPU利用率20%，对换空间的磁盘利用率98%，其他设备的利用率5%，由此断定系统出现异常。此种情况下（）能提高利用率（安装一个更快的硬盘；通过扩大硬盘容量增加对换空间；增加运行进程数；加内存条来增加物理内存容量；更换速度更快的CPU；采用更快的I/O设备。） （浙大98）

11、在请求分页系统中，地址变换过程可能会因为（）、（）、（）等原因而产生中断。 12、在请求分页管理系统中，需要哪些数据结构？（页表、块位图） 13、某请求页式系统，允许用户空间为32个页面（每页1KB），主存为16KB，若一个用户程序有10页长，某时刻该进程的页表如下所示： 虚页号 0

物理块号 8 26

是否在TLB中 是 1 2 3 4 5 6 其他 7 4 10 5 3 2 无效 是 否 否 否 是 是 问：（1）计算虚地址0AC5H、1AC5H对应的物理地址。 （2）页表存放在主存中，对主存的一次存取需要1.5ns，对TLB表的查找时间忽略为0，试问这两次访问共耗费多少时间？（浙大04）

14、已知某系统页面长为4KB，页表项4B，采用多层分页策略映射64位虚拟地址空间，若限定最高层页表占1页，问需要采用几层分页策略？

提示；由于每层页表的大小都不超过一页，所以每层的页号不超过10位。10*n+12>=64,所以采用6层。 15、一台机器有48位虚地址和32位物理地址，页面是8K，问在页表中需要多少个页表项？一个倒置的页表需要多少页表项呢？

16、一个程序要把100×100的数组的初值置为“0”，现在假定有两个内存块可以用来存放数组信息，每个内存块可以存放200个数组元素，数组中的元素按行编址。两个内存块的初始状态都为空，若程序编写如下： （1）int A [100,100]; For i=1 to 100 For j=1 to 100 A[i,j]=0; （1）int A [100,100]; For j=1 to 100 For i=1 to 100 A[i,j]=0; 当采用LRU页面置换算法时，（1）和（2）两个程序各会产生多少次缺页？

17、在请求页式存储管理系统中，页的大小为128字节。有一个64*64的整型数组，系统按行存储，每个整数占用两个字节。若系统为它分配一个贮存块存放数据，且程序已经驻留内存。试问实现为该数组清零操作时，可能产生多少次缺页中断。程序的代码编写如下： int A [64,64]; int i，j；

For （i=0； i<64;i++） For （j=0； j<64;j++） A[i,j]=0;

18、某页式虚存系统中，假定访问内存的时间是10ms，平均缺页中断处理时间是25ms，平均缺页中断率为5％。计算在该虚存系统中，平均有效访问时间是多少？

19、某操作系统的存储管理采用页式管理系统，系统的物理地址空间大小为32M，页的大小

27

是4K，假定某进程的大小为32页，问： （1）写出逻辑地址格式；

（2）如果不考虑权限位，该进程的页表有多少项？每项至少多少位？

20、已知某系统页长4KB，页表项4B，采用多层分页策略映射64位虚址空间。若限定最高层页表占1页，问它可以采用几层分页策略？ 21、一台计算机上的一条指令执行平均需要k纳秒，其上的某个操作系统处理一次页故障需要n纳秒，如果计算机上的程序执行平均m条指令发生一次缺页，问实际的指令执行时间为多少？

提示：=(m*k+n)/m

22、在分页系统中，其页表存放在内存中。

（1）如果对内存的一次存取需要100微秒，则实现一次页面访问至少需要的存取时间是多少？

（2）若系统有快表，快表的命中率为80％，当页表项在快表中时，其查询快表的时间为20微秒，问此时的存取时间是多少？

23、有一页式系统，其页表存放在主存中。

（1）如果对主存的一次存取需要1.5微秒，试问实现一次页面访问的存取时间是多少？ （2）如果系统增加快表，平均命中率为85％，若忽略快表查找时间，问此时的存取时间为多少？

24、在页式虚拟存储管理系统中，假定驻留集为M个页帧（初始所有页帧均为空），在长为P的引用串中具有N个不同页号（N>M），对于FIFO何LRU两种页面替换算法，试求出页故障的上限和下限，说明理由。

25、假定某一页式虚拟存储器，内存的平均访问时间为1微秒，辅存的平均访问时间为10毫秒，问如果希望虚拟存储器的平均访问时间仅比内存的增加10％，则需要页面失效率是多少？

26、一个计算机有cache，有一个用作虚拟内存的磁盘。若从cache中读取一个字所用的时间为Ans，从内存中将一个字读入cache的时间为Bns，从磁盘中将一个字调入内存的时间为Cns。若在cache中读取一个字的命中率是（n-1）/n，在内存中读取一个字的命中率是(m-1)/m,则平均访问时间是多少？

27、内存的利用率不高主要表现为哪几种形式？可以通过哪些途径来提高内存的利用率？ 28、人们观察到在两次页故障之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，页故障的平均间隔也加倍。假设一条普通指令需要1μs，但若发生了页面故障就需要2001μs。一个程序运行了60s，期间发生了1500次页面故障，如果该页面的可用内存时原来的2倍，这个程序运行需要多少时间：

提示：处理页面故障的时间=2001-1=2000μs，该程序共有指令数=（60s-1500*2000μs）/μs=57000000条，增加内存后，该页面故障次数为1500/2次，页面故障处理时间为

28

=750*2000μs=1500000μs，则该程序运行时间为=1500000μs+57000000μs=58.5s。

29、假定占有M块（初始为空）的进程有一个页访问串，这个页访问串的长度为p，其中涉及到q个不同的页号，对于任何页面置换算法，问：（1）缺页中断次数的下届和上届分别是多少？

30、覆盖技术与虚拟存储技术有何本质不同？交换技术与虚拟存储有何不同？

提示：覆盖技术中，覆盖段由用户设计，用户自身对内存的划分要参与操作；虚拟存储技术是由系统提供逻辑空间给用户使用，而用户并不真正了解内存的情况，物理空间的划分和管理由系统完成；交换技术是讲内存中暂时没有运行的进程调出内存，但并没有提供大于实际内存空间的逻辑空间给用户使用，该技术并不是直接面向用户的；虚拟技术可以调出正在运行的进程的内容，它是提供更大的逻辑空间供用户使用，是直接面向用户的。

31、某计算机系统执行一条指令需10ns，一次缺页需额外的20ms，如果每1000000条指令发生一次缺页，则指令平均执行时间为多少？ 32、在某页式虚存管理系统中，假定访问内存的时间是10ms，平均缺页中断处理时间为25ms，平均缺页中断率为5%。试计算在该虚存系统中，平均有效访问时间是多少？

33、请求分页系统必须至少具有三种硬件支持（一定量内存和较大量外存、地址转换机构、缺页中断机构）。

34、实现虚拟存储器的关键技术是（请求调入技术和置换技术）。 35、unix为实现请求分页管理，使用了哪些数据结构？ 答：（1）页表：（2）磁盘块描述表：记录虚页号对应的盘块号。（3）页框数据表：用于描述每个页框。（4）对换使用表：描述对换设备上的每一页的使用情况。

36、虚拟存储系统的基础是程序的局部性理论，此理论的基本含义是（选项:程序执行时对主存的访问是不均匀的；代码的顺序执行；变量的连续访问）；局部性有两种形式：时间局限性和（选项：指令局部性；数据局部性；空间局部性）。它们的意义分别为（选项：最近被访问的单元，很可能在不久的将来还要被访问；最近被访问的单元，很可能它附近的单元也即将被访问；结构化程序设计，很少出现转移语句；程序中循环语句的执行一般时间很长）。根据局部性理论，Denning提出了（选项：Cache结构的思想；工作集理论；LRU算法；） 37、作业在执行中发生缺页中断，经操作系统处理后，应让其执行（）指令。

选择：被中断的前一条；被中断的那一条；被中断的后一条；启动时的第一条。 38、什么是Belady现象？

答：Belady现象是指在使用FIFO置换算法转换时，在进程或作业没有得到它所要求的全部页面的情况下，有时会出现的分配给它的页面数越多，缺页次数反而也越多的现象。 39、名词解释：抖动，工作集。

答：在虚拟存储系统中，由于大量页面的换入换出操作导致CPU利用率急剧下降的现象。工作集是在某段时间间隔里，进程实际要访问的页面的集合。

40、在某页式虚存系统中，假定访问内存的时间是10ns，平均缺页中断处理时间为25ms，平均缺页中断率为5%，试计算在该虚存系统中，平均有效访问时间是多少？ =25ms*5%+10ns*（1-5%）

40、unix系统中的存储管理时采用（A3）方式；对换空间采用（B2）管理方式。 A：（1）请求分页；（2）动态分段；（3）段页式且支持请求调页；（4）段页式且支持请求调段。 B：（1）固定分区；（2）动态分区；（3）分页；（4）分段

29

41、下面的程序设计技术和数据结构，对于请求分页的环境而言，（3，5，6）是好的，（2，7）是坏的。 （1）栈；（2）hash表；（3）顺序检索；（4）二分查找；（5）纯代码；（6）向量操作；（7）间接寻址

42、假定某一页式虚拟存储器，内存的平均访问时间为1μs，辅存的平均访问时间为10ms，试问如果希望虚拟存储器的平均访问时间仅比内存的增加10%，则需要页面失效率是多少？ 答：设页面失效率为f，则虚拟存储器的平均访问时间为： （1-f）*1μs+f*10ms=1+9999*f（μs），据题意，1.10＞1+9999*f，所以，f＜0.00001

43、虚拟存储管理利用了交换区、内存已经Cache。假设从Cache读取一个字节数据需Ans；如果该数据不在Cache，却在内存，则从内存读至Cache需Bns，然后还需从Cache得到；如果该数据既不在Cache，又不在内存，则从交换区读入内存需Cns，然后还需传至Cache，才能读取。已知Cache的命中率为n，内存的命中率为m，求平均访问时间。

44、现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串：1，2，3，4，5，3，4，1，6，7，8，9，5，4，5，4，2.分别采用FIFO,LRU,OPT页面替换算法，各将产生多少次缺页中断？

第五章 设备管理

5.1 I/O系统

1、判断：（1）共享设备必须是可寻址的和可随机访问的设备。

（2）字符设备的基本特征是可寻址到字节，即能指定输入的源地址和输出的目标地址；

（3）共享设备是指同一时间内运行的多个进程能同时访问的设备； （4）在分配共享设备和独占设备时都可能引起死锁； （5）通道是处理输入、输出的软件；

（6）所有外围设备的启动工作都由系统统一来做； （7）来自通道的I/O中断由设备管理负责处理； （8）编制好的通道程序是存放在主存储器中的。

（9）只有引入通道后，cpu计算与I/O操作才能并行执行。

（9）设备控制器是可编址设备，当用于控制多台设备时，则具有多地址（对） （10）处理器与外围设备的并行工作能力是由（）提供的：硬件；系统软件；应用软件；支援软件。

（11）存储型设备可以作为主存储器的扩充，信息传输单位为块。

（12）按设备的使用特性，可将计算机设备分为存储型设备和输入输出设备。 （13）输入输出型设备负责主存储器与外围设备间的信息传输，信息传输单位是字符。 （14）存储型设备一般属于共享设备，而输入输出型设备则属于独占设备。 （15）独占设备一般不宜采用静态分配策略。

30

（16）作业指定独占设备的方式包括直接指定设备绝对号和指定设备类与相对号两种。 （17）指定绝对设备号的方式使设备分配的适应性好、灵活性强，用户程序中经常使用。 （18）在unix系统中，标准输入和标准输出都是终端设备，即键盘和显示器。 （19）在unix系统中，使用“＞”或“》”可以使输出重定向，“＜”可以使输入重定向。

（20）在unix系统中，管道pipe是连接在进程间的可共享文件。

（21）在unix系统中，Shell文件相当于MS-DOS的批处理文件，直接执行即可。 2、填空：通道技术的引入，实现了（处理器与设备的）并行、（设备与设备的）并行、（进程与进程的）并行。

3、把设备作为特殊文件处理，系统可以不必提供设备驱动程序。 4、下面关于设备属性的论述中正确的是（2）

（1）字符设备的一个基本特性是可寻址的，即能指定输入时的源地址和输出时的目标地址；（2）共享设备必须是可寻址的和可随机访问的设备；（3）共享设备是指在同一时刻内，允许多个进程同时访问的设备；（4）在分配共享设备和独占设备时，都可能引起死锁。

5、以下关于外部设备的说法，错误的是（4）

（1）外部设备分为存储型和I/O型两种。（2）存储型设备可以作为内存的扩充，信息传送单位为块。（3）I/O型设备负责内存与外设之间的信息传递，信息传输的单位是字符。（4）存储型设备一般属于共享设备，而I/O型设备则属于独占设备。 6、下面关于设备管理的论述中正确的是（1，2，3）

（1）所以外设的启动工作都是由系统统一来做。（2）来自通道的I/O中断事件由设备管理负责处理。（3）编制好的通道程序存放在内存中。（4）由用户给出的设备编号是设备的绝对号。

7、计算机系统启动设备是按（3）来启动的。

（1）设备名；（2）设备相对号；（3）设备绝对号；（4）设备地址

5.2 I/O控制

1、I/O控制发展的主要推动因素是什么？

答：（1）力图减少CPU对I/O操作的干预，把CPU从繁重的I/O控制中解脱出来，以充分发挥CPU数据处理的能力；（2）缓和CPU的高速性和I/O设备的低速性之间速度不匹配的矛盾，以提高CPU的利用率和系统吞吐量；（3）提高CPU和I/O设备的并行程度，使他们处于忙碌状态。

5.3缓冲管理

1 高速缓存和缓冲区的区别：

两者都是介于一个高速设备和一个低速设备之间的，但是它们之间有着很大的区别：（1）两者存放的数据不同。高速缓存上放的是低速设备上某些数据的一个拷贝，即高速缓存上有的数据低速设备上一定有；而缓冲区则是放置低速设备传递给高速设备的数据，然后再从缓冲区送到高速设备，而在低速设备上不一定有备份；（2）两者的目的不同：高速缓存是为了

31

存放低速设备上经常要被访问的数据，如果不能命中，高速设备仍然要访问低速设备；而缓冲区是为了缓和高速设备与低速设备间速度不匹配的矛盾而设置的，高速设备和低速设备间通信每次都要经过缓冲区，高速设备不会直接去访问低速设备。 2、判断：换冲技术是借用外存储器的一部分区域作为缓冲池。 3、在缓冲区实现机制中，为什么要将缓冲区的头部和缓冲体分开？

提示：（1）使系统更加安全，不会产生越界访问；（2）可以提高访问效率，比如将头部放入cache，可以减少缓冲区查找时间。

4、在某系统中，从磁盘将一块数据输入到缓冲区需要花费的时间为T，cpu对一块数据进行处理的时间为C，将缓冲区的数据传送到用户区所花的时间为M，那么单缓冲和双缓冲情况下，系统处理大量数据是，一块数据的处理时间为多少？ 5、UNIX中是如何进行块设备缓冲区管理的？

6、判断：缓冲技术是以空间换取时间，而且只能在设备使用不均衡时起到平滑作用（对） 7、在多用户系统中，实现减排驱动程序需要字符缓冲技术，请给出两种实现字符缓冲的方法。

8、若数据输入一缓冲区的设计tio始终大于对该数据的处理时间tc或者反之。试问，对上述两种情况各应采取哪种缓冲区较为合适？

答：若tio大于tc，采用单缓冲；反之，应采用循环缓冲或者缓冲池。 9、unix如何管理缓冲区？

答：unix分别为字符设备和块设备设置了缓冲区。（1）字符设备缓冲区管理：系统设置了一组字符缓冲区，供各种字符设备使用。其中，每个缓冲区的大小为70字节，包括4项：第一个字符位置，最后一个字符位置，指向下一个缓冲区的指针，余下的64个字节存放数据。所有空闲缓冲区链接成一个队列。缓冲区的分配和释放均可在链首处进行。（2）块设备缓冲区管理：类似缓冲池管理。每个缓冲区分成两部分：用于存放管理控制信息的缓冲首部和存放数据的缓冲区，两者一一对应，但物理上不相连，而是独立存储，只是在缓冲首部中用一个指针指向对应的缓冲区。缓冲首部还包括设备号和块号，以分别指出对应的文件系统和磁盘上的数据块。为了对缓冲区进行管理，系统设置一个双向链接的空闲链表，系统初启时，将所有的缓冲区首部链入空闲链表中。为了加速对缓冲区的查找，系统把所有缓冲区按设备号及块号所计算的散列值组织成多个散列队列，每个散列队列仍是一个双向链表。由于每一个缓冲区都在一个散列队列中，而空闲缓冲区又应链入空闲缓冲区队列，因此一个空闲缓冲区可同时链入两个队列中，从而使对一空闲缓冲区的查找可通过两种方式进行：A 若要获取任意一个空闲缓冲区，从空闲链首摘下一个即可；B 若要寻找一特定的空闲缓冲区，则搜索散列队列更方便。

10、假定吧磁盘上一个数据块中信息输入到一单缓冲区的时间T为100μs，将缓冲区中数据传送到用户区的时间M为50μs，而CPU对这一块数据进行计算的时间C为50μs，这样系统对每一块数据的处理时间为（150μs），如果将单缓冲改为双缓冲，则系统对每一块数据的处理时间为（100μs）。

5.4 I/O软件的设计目标

补充内容：中断处理：

32

（1）中断的概念：所谓中断是指CPU对系统发生的某个事件做出的一种反应，它使CPU暂停正在执行的程序，保留现场后自动执行相应的处理程序，处理该事件后，再返回断点继续执行被“打断”的程序。

引起中断的事件称为中断源。中断源向CPU提出的处理请求称为中断请求，发生中断时，被打断的程序的暂停点称为断点。 （2）中断类型：

1）按功能划分：（1）机器故障中断，如机器校验错、电源故障、主存出错；（2）I/O中断，如打印机输出结束中断、磁盘传输出错中断；（3）外中断，如计时部件发生的计时中断；（4）程序性中断，如非法操作码、算术溢出、除数为0，地址越界等；（5）访管中断，如分配内存，分配外设进行I/O操作。 2）按中断事件来源划分：

目前，很多小型机系统和微型机系统都采用这种分类方式。①中断：它是由CPU以外的事件引起的，如I/O中断、时钟中断、控制台中断等。利用中断实现设备与CPU的通信。中断是异步的，因为从逻辑上讲，中断的产生与当前正在执行的进程无关。②异常：它是来自CPU内部的事件或程序执行中的事件引起的过程。如CPU本身故障、通路校验错、主存奇偶错、非法操作码、地址越界、页面失效、调试指令、算术操作溢出、程序故障、访管指令等引起的事件。异常是同步的，又分为出错、陷入和可编程异常。出错和陷入之间最重要的区别是处理完异常事件返回时，出错事件会重新执行导致异常的那条指令，如缺页故障；而陷入事件不会重新执行那条指令它主要用于程序调试。可编程异常是由于用户在C程序中使用了系统调用而引发的过程。异常是不能被屏蔽的，一旦出现应立即响应并加以处理。

（3）中断处理过程：

①中断响应（硬件即中断装置操作）：中断处理是由软硬件结合实现的。发生中断时，CPU暂停执行当前的程序，转去处理中断。这个由硬件对中断请求作出反应的过程，称为中断响应。通常，CPU执行完一条指令后，立即检查有无中断请求（A 判别自愿性中断，只要检查操作码是否为访管指令；B 判别强迫性中断，则要检查中断寄存器内容。若为0，则无中断；若非0，则表示有中断事件发生。）。若有，而且“中断允许”触发器为1（表示CPU可以响应中断请求），则立即做出响应。一般来说，中断响应顺序执行下述三步动作： 1）暂停当前程序的执行；

2）保存原程序的断点信息（主要是PC计数器的值和程序状态字的内容）；

每个程序都有一个程序状态字（PSW）来反映本状态的执行状态，如基本状态（下一条指令的地址、条件码、管态/目态、计算/等待等）、中断码和中断屏蔽位等内容。处理器设有一个“程序状态字寄存器”用来存放当前运行程序的PSW。程序状态字可分为当前PSW（当前正在占用处理器的进程的PSW）、旧PSW（保存的被中断进程的PSW）和新PSW（中断处理程序的PSW）。

当出现中断事件后，把被中断进程的PSW保存为旧PSW，即完成断点信息保护。

33

3）转到相应的中断处理程序：CPU接到中断后，就从中断控制器中得到中断号，使用中断号查询中断向量表（里面存放了中断处理程序的入口地址和中断处理时的程序状态字PSW），然后转入中断处理程序。

中断装置通过“交换PSW”过程完成此项任务，即把出现的中断事件存放到当前PSW中断码位置，然后把该当前PSW保存为旧PSW，再把操作系统中断处理程序的新PSW送到程序状态字寄存器中，成为当前的PSW.

②中断处理：

中断响应后就由软件（中断处理程序）进行相应处理。操作系统的中断处理程序对中断事件进行处理时，大致要做三方面的工作： 1）保护被中断进程的现场信息： 把中断时的通用寄存器，控制寄存器内容及旧PSW保存到被中断进程的进程控制块中或内存中一个专门设置的中断现场保护栈中。 2）分析中断原因：

根据旧PSW的中断码可知发生该中断的具体原因。 3）处理发生的中断事件

核心调用中断处理程序，对中断进行具体处理。例如，调用终端中断处理程序ttyintr，判断终端输入输出是否正常完成。如果正常完成，则驱动程序便可做结束处理；如果还有数据要传送，则继续进行传送；如果是异常结束，则根据异常原因作相应处理。

4）恢复现场：

相应中断处理程序执行以后，要退出中断。

A 选取可以立即执行的进程。通常，退出中断后，应恢复到原来被中断的进程断点继续执行。如果原来被中断的进程是在核心态下工作，则不进行进程切换，因为进程在核心态下运行的是操作系统程序，涉及整个系统资源的管理，需要优先执行。如果原来被中断进程是用户态进程，且此时系统中存在比它优先级更高的进程，则重新进行调度。

B 恢复工作现场：把先前保存在中断现场区中的信箱（如PC、PSW，各通用寄存器中的信息等）取出复原。从时间顺序上讲，先恢复环境信息（各通用寄存器内容），再恢复控制信息（PC、PSW）。通常，使用一条不可中断的特权指令来复原控制信息。 （3） 中断优先级和中断屏蔽

1） 中断优先级 是硬件设计时确定的。中断装置按预定的顺序来响应同时出现的中断事件，这个预定的顺序称为“中断优先级”。中断优先级是按中断事件的重要性和紧迫程度来确定的 ，是由硬件设计时固定下来的。一般情况下，优先级的高低顺序依次为： 硬件故障中断 、 自愿中断 、 程序性中断 ， 外部中断和输入输出中断 . 2）中断的嵌套处理

3）中断屏蔽的作用。中断优先级只是规定了中断装置响应同时出现的中断的次序，当中断装置响应了某个中断后中断处理程序在进行处理时，中断装置也可能去响应另一个中断事件。因此会出现优先级低的中断事件的处理打断优先级高的中断事件的处理，使得中断事件的处理顺序与响应顺序不一致，而且会形成多重嵌套处理，使多现场保护、程序返回等工作变的复杂。

中断屏蔽技术就是为了解决上述问题而提出的在一个中断处理没有结束之前不响应其他中断事件，或者只响应比当前级别高的中断事件。于是，当中断装置检查到有中断事件后，便去查看PSW中中断屏蔽标志，如果没有屏蔽就响应该中断；否则，暂时不响应该中断，待屏蔽标志消除后再响应。自愿中断是不能屏蔽的。

4）中断禁止：是指在可引起中断的事件发生时系统部接收该中断信号，因而就不可能

34

提出中断请求而导致中断，就是不让某些事件产生中断。它常用在执行某些特殊工作的条件下，如求余运算，算术运算中强制忽略某些中断，如定点溢出等。在中断禁止的情况下，CPU正常运行，根本不理睬所发生的那些事件。

从概念上讲，中断屏蔽和中断禁止是不同的。前者表示硬件接受了中断，但系统暂时不响应，要延迟一段时间，待中断开放后，被屏蔽的中断就能被响应并得到处理。而后者，硬件不准许事件提出中断请求，从而使中断被禁止。

1、I/O软件通常设为四个层次：用户空间I/O软件、设备独立性软件、设备驱动程序和中断处理程序，问以下各项工作是在哪个层次上完成的？ （1）用户进程请求打印一个输出文件；

（2）将一维磁盘块号转换为三维物理地址（柱面、磁道和扇区） （3）获得设备驱动程序的入口地址； （4）将终端输入的字符转换为ASCII码； （5）设备驱动进程被唤醒； （6）向设备寄存器写命令；

（7）检查用户是否有权使用设备；

（8）将二进制整数转化成ASCII码以便打印。（用户层） （9）维护一个最近使用块的缓存。

2、当中断发生后，进入终端处理的程序属于（用户程序；可能是用户程序，也可能是os程序；os程序；） 3、判断：在中断处理过程中，必须屏蔽中断（错）

4、由系统通过逻辑设备表实现逻辑设备到物理设备的映射。当更换物理设备时，用户的程序不用改，仅修改逻辑设备表。

5、计算机中断系统中，断点、恢复点与PC寄存器之间的关系是什么？中断源有哪些基本类型？

提示：引起中断的事件称为中断源，中断源通常由硬件发现。中断处理程序是由操作系统处理的，属于操作系统的组成部分。

6、计算机系统中判别是否有中断事件发生应是在( B ) A.进程切换时 B.执行完一条指令后

C.执行P操作后 D.由用户态转入核心态时

7、中断装置的职能主要有三点： 1)检查是否有中断事件发生。 2)若有中断发生，保护好被中断进程的断点及现场信息，以便进程在适当时候能恢复驼行。 3)启动操作系统的中断处理程序。

8、引起I/O中断的事件有（1，2）。（选项：数据传送完毕；设备出错；设备正在处理数据；指令错；缺页；访存越界）

9、如果有多个中断同时发生，系统将根据中断优先级响应优先级最高的中断请求。若要调整中断事件的响应次序，可以利用（）。（选项：中断禁止；中断嵌套；中断响应；中断屏蔽） 10、当用户程序执行访管指令时，中断装置将使CPU（）：维持在用户态；维持在核心态；从核心态转换到用户态；从用户态转换到核心态。

35

11、中断处理程序占用处理器时，要从（）取出信息，才能分析中断发生的原因：当前PSW；新PSW；旧PSW；当前指令的操作码。

12、缺页中断属于（程序性中断），CTRl+C中断属于（外部中断）。 13、判断：中断时用户程序转换到操作系统程序的驱动源。

14、判断：采用DMA方式控制数据I/O操作要比通道 传输速度慢一些。

15、下面的事件（）不是引起中断的事件。（选项：掉电；打印完毕；程序出错；除0出错）

5.5设备分配

1、常用的I/O调度算法有哪些？试说明I/O调度中为什么不能采用时间片轮转法。 提示：原因如下：（1）独占设备的固有属性决定了不能采取时间片轮转法；（2）I/O设备的速度比cpu慢，I/O设备间来回切换的开销很大，采用时间片轮转法会导致大量的时间浪费在设备的启动和切换上；（3）由于各种I/O设备的数据传输速率相差较大，时间片的大小不好确定。

2、一个spooling系统由输入进程I、用户进程P、输出进程O、输入缓冲区、输出缓冲区组成。I通过输入缓冲区为P输入数据，P的处理结果通过输出缓冲区交给进程O输出。进程间数据交换以等长的数据块为单位。这些数据块均存储在同一磁盘上。因此，spooling系统的数据块通信原语始终保证满足：i+o<=max，（1），其中max为磁盘容量（以数据块为单位），i为磁盘上输入数据块总数，o为磁盘上输出数据块总数。请说明该系统在什么情况下死锁，并说明如何修正约束条件（1）防止死锁。

提示：当i=max时，o=0，若此时输入、输出缓冲区均放满数据，则I/P/O均阻塞，进入死锁状态；将（1）修改为：i+o<=max,且i<=max-1即可。

3、在spooling系统中，用户进程实际分配到的是（）：用户所要求的外设；一块内存区，及虚拟设备；共享设备的一部分存储区；虚拟设备的一部分空间；

4、（）是操作系统中采用的以空间换时间的计数。（Spooling技术；虚拟存储技术；覆盖与交换技术；通道技术）

5、有关设备的管理中，( ADE )是正确的。 A.“计算机系统为每台设备确定一个绝对号” B.“每台设备都应该有一个惟一的相对号”

C.“申请设备时指定绝对号可提高设备的使用率”

D.“申请设备时指定设备相对号使设备分配的灵活性强” E.“启动设备时应指出设备的绝对号”

6、实现虚拟设备的硬件条件是什么?操作系统应设计哪些功能程序?

硬件条件是：配置大容量的磁盘，要有中断装置和通道， 操作系统应设计好“预输入”程序，“井管理”程序，“缓输出”程序。

7、什么是虚拟设备？为什么要引入虚拟设备？实现虚拟设备时所依赖的关键技术是什么？ 答：虚拟设备是指通过某种技术，把一个物理设备变成若干台逻辑设备。逻辑设备实际上并不存在，只是给用户的一种感觉。

引入虚拟设备的原因是为了克服独占设备所具有的速度较慢、资源的利用率较低的缺

36

点，以提高设备的利用率。

实现虚拟设备所依赖的关键技术是分时技术。即多个用户进程通过分时的方式使用同一台物理设备。宏观上，是若干进程在同时执行I/O操作，而微观上，则是一台物理设备分时地为每个进程服务。目前最广泛的虚拟设备技术是SPOOLing技术。

8、SPOOLing对一个批处理系统是必要的，为什么？对一个分时系统需要吗？在多道程序系统中，为什么要实行SPOOLing技术？

答：SPOOLing对一个批处理系统是必要的，原因是：SPOOLing能实现作业的预输入缓输出功能，从而可在系统提供的输入井中，形成作业的预备队列，为作业调度提供方便；另外，SPOOLing还能实现虚拟设备功能，支持多道作业对系统配置的少量设备的需求。分时和批处理都需要缓输出功能。在多道程序系统中，系统的共享设备数量有限，为避免竞争使用独占设备而死锁，利用SPOOLing技术把独占设备改造成共享设备，这样不但提高了独占设备的利用率，还提高了I/O的速度，从而提高了CPU与外设的并行度。

9、假设一个单处理机系统，以单道批处理方式处理一个作业流，作业流中有两道作业，其占用CPU计算时间、输入卡片数、打印输出行数如表所示：

作业号 A B 占用CPU计算时间（分） 输入卡片张数（张） 输出行数（行） 3 2 100 200 2000 600 其中，卡片输入机速度为1000张/min；打印机速度为1000行/min。试计算：

（1）不采用SPOOLing技术，计算这两道作业的总运行时间（从第一个作业输入开始，到

第二个作业输出完成为止）。 （2）如果采用SPOOLing技术，计算这两道作业的总运行时间。 答：（1）=（0.1+3+2）+（0.2+2+0.6）=7.9分 （2）=0.1+3+2+0.6=5.7分

5.6磁盘管理

1、一个快速磁盘转速为7200RPM，每磁道160个扇区，每扇区512字节，那么理想状态下，其数据传输速率为（）。 2、判断：优化在磁盘上文件物理块的分布可显著减少寻道时间，因此能有效地提高磁盘I/O的速度。

3、设L,M,N分别表示盘组的柱面数、盘面数、扇区数，B表示块号，则第i柱面、j磁头、k扇区所对应的块号B为：B=(i*M*N)+(j*N)+k

式中，i=0，1，?，L-1；j=0，1，?，M-1；k=0，1，?，N-1 同样，根据B可以计算磁盘位置： 柱面号i=int（B,M*N）

磁头号j=int（mod（B,M*N）,N） 扇区号k=mod（mod（B,M*N）,N）

4、假定磁盘的存取臂现在处于6＃柱面上，有如下表所示的六个请求等待访问磁盘，试列出最省时间的响应顺序。（答：6，2，1，4，3，5）

37

序号 1 2 3 4 5 6 柱面号 7 5 15 7 20 5 磁道号 6 5 20 4 9 15 扇区号 3 6 6 4 3 2

2、假定有4各记录A,B,C,D，顺序放在磁盘的某磁道上，该磁道划分为4块，每块存放一个记录。现在要顺序处理这些记录，如果磁盘的转速为20ms转一周，处理程序每读出一个记录后花5ms时间进行处理。问：处理完这4个记录需要多少时间？为了缩短处理时间应如何安排这些记录？并计算处理的总时间。

3、磁盘调度的相关问题：各种调度算法

4、在某系统中，数据从磁盘读入缓冲区，然后从缓冲区传人用户区，再在用户区中处理。假设该磁盘系统中文件在磁道上非连续存放，磁头从一个磁道移至另一个磁道需要时间t1，逻辑上相邻数据块的平均距离为d磁道，每块的旋转延迟时间及传输道缓冲区的传输时间分别为t2和t3。问读取N个数据块的磁盘访问时间一共是多少？另外，假设将缓冲区的数据传送到用户区所花费的时间为t4且t4远远小于读取一个数据块的磁盘访问时间，CPU对一块数据进行处理的时间为t5。问分别在单缓冲和双缓冲情况下，一块数据的总处理时间是多少？

8、假设一个磁盘组共100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。现有一个含有6400个逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从0开始，逻辑记录的编号也从0开始。文件信息从0柱面、0磁道、0扇区开始存放，试问：

（1）该文件的第3680个逻辑记录应该存放在什么位置？

（2）第78柱面的第6磁道的第6扇区中存放了该文件的第几个逻辑记录？

9、有10个记录在某磁盘的一个磁道上，假定这个磁道划分为10个扇区，每个扇区存放一个记录。现在要从磁道上顺序地将10个记录读出，如果磁盘转速为20ms转一周，处理程序每读出一个记录后花4ms进行处理。问处理完10个记录的总时间是多少？为缩短处理时间应如何安排这些记录？需要多少处理时间？

10、对于硬盘上存放的信息，物理上读写的最小单位是一个（）（选项：二进位；字节；物理块；逻辑记录）

11、一个软盘有40个柱面，寻道时移过每个柱面花费6ms，若不采取任何使文件的块尽量紧密存放的措施，则逻辑上相邻的块平均间隔13个柱面，如果采取一定的措施使得文件中相邻的块尽可能放在一起，则块间的平均间隔是2个柱面。假定读写时找到柱面后平均旋转时间为100ms，传输速率为每块25ms，则在此两种情况下传输一个100块的文件各需要多长时间？

12、下列磁盘电动算法中，（2，5）算法可能会随时改变移动臂的运动方向。 （1）电梯；（2）FCFS；（3）循环扫描；（4）最短寻道时间

13、有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s，磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道的第3扇区，并立即被系统响应，

38

假设磁头当时处于15磁道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多时时间？

答：寻道时间=（25-15）*10=100ms

延迟时间=（3-1）*0.25=0.5ms 传输时间=0.25ms

第六章 文件系统

1、文件系统的性能对整体系统的性能影响很大，请说明在实现文件系统时可以从哪些方面提高文件系统的性能。

提示：目录管理；文件使用方式：打开、关闭；文件保护（包括文件恢复、口令、密码、访问控制等）；提高磁盘读写速度的方法（磁盘高速缓存、提前读、延迟写、优化物理块分布、并行交叉存取等） 2、有关文件管理与设备管理的关系，判断：

（1）文件管理与设备管理时操作系统好 的两个完全独立的功能，二者不存在任何关系。 （2）设备管理与文件系统密切相关，文件系统是设备管理的基础，设备管理必须依赖文件管理才能最终完成相应的功能。

（3）文件系统为用户按名存取服务，实现逻辑文件与物理文件之间的映射，而文件信息的存取是设备管理部分完成的。

（4）设备管理时文件系统的基础，文件管理是设备管理的一部分。

3、可通过哪些途径改善文件系统的性能？

答：（1）改进文件的目录结构以及检索目录的方法，来减少对文件的查找时间；（2）选择好的文件存储结构，以提高对文件的访问速度；（3）通过采用磁盘高速缓存、优化物理块的分布、利用提前读、延迟写或虚拟盘等方法来提高磁盘I/O速度，以提高对数据的传送速度。

6.1文件和文件系统

1、使用文件时，通常要显示地进行OPEN、CLOSE操作。

（1）这样做的目的是什么？（2）能否取消？应如何做？（3）取消后有什么不利？ 提示：（3）取消open，则每次使用文件都要判断文件是否已经打开，增加系统开销；取消close，则文件打开后会一直驻留在内存直到进程或系统结束、浪费系统资源。 2、判断：打开文件的功能就是将文件复制到主存。 3、判断：特殊文件是指其用途是由用户特殊规定的文件。

4、打开一个UNIX系统的文件，需要几个数据结构？之间的联系如何？

提示：索引节点、内存索引节点表，系统打开文件表、用户打开文件表、每个open返回给进程一个文件描述符，它是用户打开文件表中的表项序号，它在用户打开文件表中对应的表项指向系统打开文件表中唯一的表项。一个被打开文件的所有实例所对应的表项指向内存索引节点表中的同一表项。

5、在文件系统中可命名的最小数据单位是（数据项），用户以（记录）为单位对文件进行后

39

存取、检索等，对文件存储空间的分配则以（文件）为单位。 选项：字符串；数据项；记录；文件；文件系统

6.2文件逻辑结构

1、假定磁带的记录密度为每英寸800个字符，每一个逻辑记录长为160个字符，块与块之间的间隙为0.6英寸，现有1000个逻辑记录需要存储到磁带上，问： （1）不采用成组操作时，磁带空间的利用率是多少？

（2）采用以5个逻辑记录为一组的成组操作时，磁带空间的利用率是多少？ （3）为了是磁带空间的利用率大于50％，采用记录成组的块因子至少是多少？

2、某用户文件共10个逻辑记录，每个逻辑记录的长度为480个字符，现把该文件存放到磁带上，若磁带的记录密度为800字符/英寸，块与块之间的间隙为0.6英寸，回答下列问题： (1)不采用记录成组操作时磁空间的利用率为__________。

(2)采用记录成组操作且块因子为5时，磁带空间的利用率为__________。 (3)当按上述方式把文件存放到磁带上后，用户要求每次读一个逻辑记录存放到他的工作区。 当对该记录处理后，又要求把下一个逻辑记录读入他的工作区，直至10个逻辑记录处理结束。系统应如何为用户服务?

提示：(1)利用率为50% (2)利用率为83%

(3)设置长度为2400字符的主存缓冲区；找到该文件的存放位置，启动磁带机读出第一块内容存入主存缓冲区；进行记录分解，按用户要求依次把主存缓冲区中的五个记录传送到用户工作区；启动磁带机读第二块内容存入主存缓冲区，把第6至10个逻辑记录按用户要求依次传送到用户工作区。 4、下列叙述中正确的是（3，4）。

（1）在磁带上的顺序文件中插入新的记录时，必须复制整个文件；（2）由于磁带的价格比磁盘便宜，用磁带实现索引文件更经济；（3）在磁带上的顺序文件的最后添加新纪录时，不必复制整个文件；（4）变更磁盘上的顺序文件的记录内容时，不一定要复制整个文件；（5）在磁盘上的顺序文件中插入新的记录时，必须复制整个文件

5、对记录式文件，操作系统为用户存取文件信息的最小单位是（）（选项：字符；数据项；记录；文件）

6.3外存分配方式

1、判断：同一文件在不同的存储介质上应该用相同的组织形式。

2、如果文件采用直接存取方法使用，且文件大小不固定，则应采用（）物理结构。（选项：直接；索引；随机；顺序）

1、如果一个文件存放在100个数据块中，文件控制块、索引块或索引信息等都驻留在内存。下面各种情况下，需要做几次磁盘I/O操作？

（1）连续分配，将最后一个数据块搬到文件头部（200次） （2）单级索引分配，将最后一个数据块搬到文件头部（0次） （3）隐式链接分配，将最后一个数据块搬到文件头部（0次）

40

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