《操作系统原理》离线作业答案

《操作系统原理》

计算机专业课程系列——

《操作系统》作业集

第一章参考答案

一、单项选择题

1、（A2, B4, C3），2、(A6, B1, C4)，3、D，4、C，5、C，6，A 二、填空题：

1、（处理机管理、存储器管理、设备管理、文件管理、用户接口），2、通用操作系统，3、（CPU，I/O），4、（分时操作系统，实时操作系统，批处理操作系统），5、（实时性、 可靠性），6、（吞吐量，资源利用率 、周转时间。），7、（用户，系统，用户），8、（交互性），9、（及时性，可靠性），10、(多道程序设计)，11、（系统调用），12、(原语操作)，13、（命令图形，系统调用），14、（处理机时间），15、，16、（系统调用） 三、判断题：

1、（错 ），2、（错），3、（错），4、（错），5、（错），6、（错），7、（错），8、（错） 四、名词解释： 1.操作系统

答：是一组控制和管理计算机系统中的各种软硬件资源，合理地组织计算机系统的工作流程，方便用户使用的程序的集合。 2.虚拟机

答：虚拟机是指“虚拟”的计算机，是由软件模拟实现出来的计算机，实际上它是将本地主机上的硬盘和内存划分出一部分或几部分，虚拟成一台或多台子机。这些虚拟出的新计算机拥有独立的硬盘、软驱、光驱和操作系统，可以像使用普通计算机一样使用它们，如同时运行多个不同的操作系统等，对真实的计算机不会产生任何的影响。 3.分时系统

答：分时是指多个用户分享使用同一台计算机。多个程序分时共享硬件和软件资源。分时系统的特点：人机交互性好。在调试和运行程序时由用户自己操作。享主机：多个用户同时使用。用户独立性：对每个用户而言好象独占主机。

- 1 -

《操作系统原理》

4.实时系统

答：用于工业过程控制、军事实时控制、金融等领域，包括实时控制、实时信息处理 要求：响应时间短，在一定范围之内；系统可靠性高 5.多道程序设计

答：在内存中同时存放多道用户作业,使它们都处于执行的开始点和结束点之间。 6.系统调用

答：操作系统提供服务的接口之一 7.特权指令

答：只能由操作系统使用的指令 8.中断响应

答：中断响应是当中央处理机发现已有中断请求时，中止，保存现行程序执行，并自动引出中断处理程序的过程。 五、简答题：

1、答:为使程序能并发执行,系统必须为每个程序建立进程,进程是系统中能独立运行并作为资源分配的基本单位,它是一个活动的实体.多个进程之间可以并发执行和交换信息,有效改善了系统的资源利用率和吞吐率.但是进程的引入增加了OS的复杂性,OS必须具备控制和管理各种并发活动的能力. 为使并发进程能共享系统资源,OS必须针对不同属性的资源提供不同的共享方式,即互斥共享和同时共享.另外,还要实现互斥访问方式中进程间的同步

2、答:覆盖了软件的机器叫作虚机器.

使用了虚机器的概念后,可以使用户在使用计算机时不涉及硬件细节,为用户使用计算机提供了方便.另外,OS使用虚机器概念来设计,每当在计算机系统上覆盖了一层软件后,系统功能便增强一级. OS本身包含若干层,所以当在裸机上覆盖OS后,便获得了一台功能显著增强、使用极为方便的虚拟机.

3、答：存储管理。在多道程序设计环境下，在主存中的几道程序共享同一主存，硬件必须提供必要的手段，防止各道程序相互侵犯，同时要保证程序在主存中能随机移动。 处理机管理和调度。由于多道作业共享CPU，所以需对CPU进行管理，合理调度，以提高其利用率。

资源的管理和分配。对系统中的资源进行合理有效的管理，以利于多道程序共享。 4、答：单道批处理的特点：自动性、顺序性、单道性。

- 2 -

《操作系统原理》

多道批处理的特点：多道性、无序性、调度性。 分时系统的特点：多路性、独立性、及时性、交互性。 实时系统的特点：多路性、独立性、及时性、交互性、可靠性。 5、答：提高了CPU的利用率。 提高了内存和I/O设备的利用率。 增加了系统的吞吐量。

第二章参考答案

一、单项选择题：

1、D，2、C，3、C，4、C，5、D，6、C，7、B，8、（A1，B2），9、（A4，B2，C4，D6，E2），10、（A2，B6，C5，D4，E6），11、D 二、多项选择题：

1、（A，C，D，E），2、（D，E） 三、填空题：

1、（执行，就绪，阻塞，重新调度），2、（同步，互斥，互斥），3、（可用资源的数目，因请求该资源而被阻塞的进程数目），4、（用户，系统，用户），5、（申请资源，释放资源，等待此资源的进程数，可用资源数），6、（多道程序设计，进程控制块），7、进程控制块，8、（作业控制块），9、（管程），10、（共享变量），11、N，12、（发送，接收），13、（初始化标识符信息，初始化处理机状态信息，初始化处理机控制信息），14、（减少并发执行时所需付出的时空开销，提高程序执行的并发度），15、（可分割性，失去封闭性，不可再现性），16、（互斥资源，互斥，进入区，退出区） 四、判断

1、（对），2、（对），3、（错），4、（错），5、（ 对），6、（错），7、（错），8、（错），9、（错），10、（错），11、（错），12、（错），13、（对） 五、名词解释 1.进程

答：进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。 2.线程

答：调度的基本单位，共享进程的资源

- 3 -

《操作系统原理》

3.临界资源

答：一次只允许一个进程使用到资源。 4.临界区

答：在进程中涉及到共享变量的程序段叫临界区。 5.进程同步

答：进程的同步：指系统中一些进程需要相互合作，共同完成一项任务。 6.进程互斥

答：由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程竞争使用这些资源，进程的这种关系为进程的互斥。 7.进程状态

进程生命周期所处的状态 六、简答题

2、答：（1）为支持多进程的并发执行，OS必须为每个进程建立一个PCB，来记录OS所需的、用于描述进程、及控制进程运行所需的全部信息。

（2）支持进程状态的转换，在三种进程的基本状态中，系统至少应当提供进程创建原语、进程撤消原语、阻塞原语和唤醒原语；在五进程状态中，还应当增加挂起原语和激活原语。 （3）执行创建原语：创建一个进程，它的PCB状态为就绪状态。 执行撤消原语：撤消一个进程，它的PCB及资源被回收。 执行阻塞原语：调用该原语的进程的PCB的状态变为阻塞状态 执行唤醒原语：被唤醒进程的PCB中的状态变为就绪状态

执行挂起原语：被挂起进程的状态从执行——静止就绪、或活 动阻塞——静止阻塞，或活动就绪——静止就绪

执行激活原语：被激活的进程的状态从静止就绪——活动就绪，或从静止阻塞——活动阻塞

3、答：在交换信息量方面：利用P、V操作原语可以实现进程的互斥和同步，但只能交换少量的信息，缺乏传输消息的能力；而高级通信不仅可以实现进程的互斥和同步，且能交换大量的消息，是理想的进程通信工具。

通信对用户透明方面：用P、V操作原语通信时必须在用户程序中增加P、V编程，而且若编程不当，还会出现死锁；而高级通信机制对用户则是透明的。

- 4 -

《操作系统原理》

4、答：现代计算机系统中程序并发执行和资源共享的需要，使得系统的工作情况变得非常复杂，而程序作为机器指令集合，这一静态概念已经不能如实反映程序并发执行过程的动态性，因此，引入进程的概念来描述程序的动态执行过程。这对于我们理解、描述和设计操作系统具有重要意义。

进程定义为程序在并发环境中的执行过程，它与程序是完全不同的概念。主要区别是：

（1）程序是静态概念，是永久性软件资源；而进程是动态概念，是动态生亡的暂存性资源。

（2）进程是一个能独立运行的单位，能与其他进程并发执行，系统是以进程为单位分配CPU的；而程序则不能作为一个能独立运行单位。

（3）程序和进程没有一一对应关系。一个程序在工作时可以由多个进程工作，一个进程在工作时至少对应有一个程序。

（4）各个进程在并发执行时会产生制约关系，使各自推进的速度不可预测；而程序作为静态概念，不存在这种异步特征。

进程和程序关系类似生活中的炒菜与菜谱。菜谱相同，而各人炒出来的菜的味道却差别很大。原因是菜谱基本上是一种静态描述，它不可能把所有执行的动态过程中，涉及的时空、环境等因素一一用指令描述清楚。

七、计算题 1

顾客: P(mutex); rc:=rc+1; if rc=1 then v(wakeup); Else p(wait); V(mutex); Cut hair 理发师: P(wakeup); Repeat Cut hair; P(mutex); rc:=rc-1; If rc<>0 then v(wait); V(mutex); Until rc=0;

- 5 -

《操作系统原理》

2、答：Var full-in,empty-in,mutex-in,full-out,empty-out,mutex-out : semaphore:= 0,M,1,0,N,1; buffer-in: array[0,M-1] of item; buffer-out: array[0,N-1] of item; in1,out1,in2,out2: integer :=0,0,0,0 Begin parbegin

process IN:begin

repeat

input an item nextin; wait(empty-in); wait(mutex-in); buffer-in(in1):=nextin; in1 :=(in1+1) mod M; signal (mutex-in); signal (full-in); until false; end

compute:begin

repeat

wait(full-in); wait(mutex-in); nextc:=buffer-in(out1); out1 :=(out1 + 1) mod M; signal (mutex-in); signal (empty-in); wait(mutex-out); wait(empty-out); buffer-out(in2):=nextc;

- 6 -

《操作系统原理》

in2 :=(in2+1) mod N; signal (mutex-out); signal (full-out); until false; end

process out:begin repeat

wait(full-out); wait(mutex-out);

nexto:=buffer-out(out2); out2 :=(out2 + 1) mod N; signal (mutex-out); signal (empty-out); output the item in nexto; until false; end 3、

- 7 -

《操作系统原理》

READ ： While wc = 1 do skip; ------若有写进程请求，则后续读不响应 P(mutex); Rc:=rc + 1; If rc = 1 then P(wr); -----若是第一个读进程，则要看有无写进程 V(mutex); READING P(mutex); Rc := rc -1; If rc = 0 then V(wr); -------若所有读进程都执行完，可以让其它进程读写 V(mutex); 。 WRITE Wc := 1; P(wr); WRITING; Wc := 0; V(wr); a 4、答：设:mutex:=1;sa=M-1;sb=N-1;

A Repeat P(sa); P(mutex); Put A v(mutex); V(sb) Until false B Repeat P(sb); P(mutex); Put b V(mutex); V(sa) Until false 第三章参考答案

一、单项选择题：

1、C，2、C，3、B，4、（A1,B2,C5,D4,E3,F6），5、（A2,B1,C3,D2），6、D，7、A，8、B 二、多项选择题

1、（C，D），2、(B，D，E，F) 三、填空题：

- 8 -

《操作系统原理》

1、（死锁的避免，死锁的预防，死锁的解除），2、（动态），3、（互斥条件，不剥夺条件，请求和保持条件，环路等待条件），4、（短作业优先），5、2?m?M-1，6、（破坏产生死锁的四个必要条件之一），7、（FCFS），8、（可剥夺式基于优先级的调度算法），9、（提高系统效率，吞吐量高，及时得到计算结果，周转时间短） 四、判断题：

1、（错），2、（错），3、（错），4、（错），5、（错），6、（错），7、（错），8、（错），9、（错），10、（错），11、（对），12、（对），13、（错） 五、名词解释： 1.抢占式进程调度

答：进程调度的职责（任务）是控制协调进程对CPU的竞争，即按选定的调度算法从就绪队列中选择一个进程，让它占用CPU（即把CPU的使用权交给被选中的进程）。 抢占式进程调度是系统可强行剥夺正在运行进程的CPU 2.可再入程序

可再入程序（两个及两个以上进程共用一个程序）：可被多个进程同时调用的程序。具有下列特征：它是纯代码的，即在执行过程中自身不会改变，调用它的进程应该提供数据区（工作区）。 3.死锁

答：多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们将无法再向前推进。 4.死锁避免

答：系统中对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源；如果分配后系统可能发生死锁，则不予分配，否则予以分配。 是一种保证系统不进入死锁状态的动态策略， 该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。 5.死锁预防

答：在系统设计时确定资源分配算法，限制进程对资源的申请，从而保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 六、简答题：

- 9 -

《操作系统原理》

1、答：抢占式是指当一进程正在CPU上运行时，若有优先权更高的进程进入就绪队列，则要中止现运行进程的运行，将CPU分配给优先级更高的进程。而非抢占式则是指当一进程正在CPU上运行时，若有优先权更高的进程进入就绪队列，现行进程继续运行直到完成或出现某些情况才让出CPU。

FCFS属于非抢占式；HPF属于抢占式。

2、答：银行家算法是一种避免死锁的策略。该策略是在实施资源分配之前先计算实施该分配后是否存在一种顺序，使得所有的进程都能执行结束，即是否处于安全状态。若是，则分配，否则不分配。

该算法在实际系统中很难使用。因为算法需已知进程申请资源的最大数目、系统中进程数目要固定，这在现实中很难做到。

3、答： 因为7个进程共享系统中8个相同的资源，且每个进程最多需2个资源，所以最坏情况是每个进程都已占有一个资源，还再需用一个资源，这时，系统中还有一个资源可用，可以把这个资源分配给其中的一个进程，就满足了它的全部需求，使其运行结束，释放其所占有的资源供其他进程使用。所以系统不会出现死锁。

4、答：用Maxi,Needi,Allocationi分别表示第I个进程对该类资源的最大需求量、还需要量、已分配到的量，则有：Needi﹥ 0 （对所有I），∑Maxi﹤M+N

若系统已因竞争该类资源而进入死锁，则意味着已有一个以上的进程因申请不到该资源而阻塞，而M个资源肯定已经全部分配出去了，即：∑Allocationi= M， 因此有

∑Needi =∑Maxi - ∑Allocationi ﹤M+N-M，即∑Needi﹤N ，这样，至少必存在一个进程，其Needi≤0，这与题目已知条件“每个进程都需要该类资源”矛盾。所以系统不可能因竞争该类资源而死锁。

5、答：死锁的防止是系统预先确定一些资源分配策略，进程按规定申请资源，系统按预先规定的策略进行分配，从而防止死锁的发生。

而死锁的避免是当进程提出资源申请时系统测试资源分配，仅当能确保系统安全时才把资源分配给进程，使系统一直处于安全状态之中，从而避免死锁。 七、计算题： 1、答：

作业 进程名 A B C D E 平均 算法

- 10 -

《操作系统原理》

运行时间 优先级 优先级高 完成时间 等待时间 周转时间 完成时间 2 1 30 28 30 2 0 2 30 28 30 4 2 28 24 28 12 8 12 18 14 18 6 3 24 18 24 20 14 20 6 0 6 8 4 18 10 18 26 18 26 14 6 14 10 5 10 0 10 30 20 30 28 18 28 —— 16 22 —— 12 18 —— 13．2 19．2 时间片（2分） 等待时间 周转时间 FCFS,顺序为 C,D,B,E,A 完成时间 等待时间 周转时间

2、答：（1）利用安全性算法对上述状态进行分析，找到了一个安全序列（P0，P3，P4，P1，P2），故该状态是安全的。分析如下表所示。

进程 P0 P3 P4 P1 P2 work 1622 1654 1686 169 10 269 10 Need 0012 0652 0656 1650 2356 Allocation 0032 0032 0014 1000 1354 Work+allocation finish 1654 1686 169 10 269 10 39 14 14 TRUE TRUE TRUE TRUE TRUE (2)P2 发出请求Request（1，2，2，2）后，系统按银行家算法进行检查：

Request（1，2，2，2）<= Need2(2,3,5,6), 且Request（1，2，2，2）<=Available(1,6,2,2) 系统假定可为P2分配资源,并修改Available、Allocation2和Need2如下： Available=（0，4，0，0） Allocation2=（2，5，7，6） Need2=（1，1，3，4）

接下来进行安全性检查：此时对所有的进程，条件Needi <= Available(0,4,0,0)都不成立,故系统进入不安全状态.因此,不能给P2分配资源.

(3)系统立即满足进程P2的请求(1,2,2,2)后,并没有马上进入死锁状态.因为此时上述进程

- 11 -

《操作系统原理》

并没有申请新的资源，只有当上述进程提出新的资源请求并导致所有没执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。

3、答：（1）T0时刻是安全状态。其中一个安全序列为：P5，P1，P2，P3，P4 （2）Request[2]=(0,3,4), 但Available=(2,3,3) 不能满足P2的请求。P2阻塞。

（3） Request[4]=(2,0,1) ，Available=(2,3,3)， Need[4]=(2,2,1),Max[4]=(4,2,5) 满足Request[4]< Need[4],

且Request[4]< Available，再进行安全性检查，见下页表。存在一个安全序列，可以为P4实施资源分配。

安全性检查

进程 Work Max Allocation Need Work+ Allocation P4 0,3,2 4,2,5 4,0,5 0,2,0 4,3,7 P2 4,3,7 5,3,6 4,0,2 1,3,4 8,3,9 P3 8,3,9 4,0,11 4,0,5 0,0,6 12,3,14 P5 12,3,14 4,2,4 3,1,4 1,1,0 15,4,18 P1 15,4,18 5,5,9 2,1,2 3,4,7 17,5,20

5、解:

10:00 A作业到达,进程调度程序调度A运行

10:20 B作业到达,作业调入内存,抢占进程A的处理机,A回到就绪队列,A还需运行20分钟 10:30 C作业到达,在后备队列中等待

10:50时,B运行30分钟后结束运行,D作业到达,后备队列中有C,D两个作业等待调度,根据短作业优先原则,D调入内存.内存中,A在就绪队列上已等待了30分钟,A的优先级高于D,A

- 12 -

《操作系统原理》

运行,D就绪.此时C在后备队列中已等待了20分钟并继续等待.

11:10,A运行结束,C装入内存,C的优先权高于D,C运行,D继续等待,此时D已等待了20分钟.

12:00,C运行结束,D运行 12:00 D运行结束

作业名 进入内存时间 结束时间

A 10:00 11:10 B 10:20 10:50 C 11:10 12:00 D 10:50 12:20 各作业的周转时间为: A:70 B:30 C:90 D:90

平均周转时间为(70+30+90+90)/4=70

第四章参考答案

一、 单项选择题：

1、D，2、B，3、D，4、B，5、B，6、C，7、D，8、A，9、D，10、B，11、A，12、A，13、B，14、C，15、C，16、D，17、A，18、B 二、多项选择题： 三、填空题：

1、(内存，外存)，2、（存储分配、地址重定位、存储保护、存储扩充），3、(字节，物理地址，逻辑地址)，4、(逻辑地址，物理地址，静态重定位，动态重定位)，5、(动态重定位，一，两，局部性，快表 )，6、(物理，固定，系统，逻辑，不固定，用户)，7、(越界保护，存取权限)，8、(计算机的地址结构)，9、(基址寄存器，限长寄存器)，10、（越界），11、(最差)，12、（提高查找速度），13、(最佳)，14、(管态)，15、（缺页）(操作保护) （越界保

- 13 -

《操作系统原理》

护），16、（低地址）（高地址），17、（段表）（缺段中断）（地址变换 ），18、（虚拟 ），19、. (按小到大)，20、(被中断的)，21、（页面置换调度），22、(局部性)，23、（块号*块长+页内地址），24、（静态重定位），25、。（页号，页内地址），26、（抖动）

四、判断题：

1、错，2、错，3、错，4、错，5、错，6、错，7、错，8，对、9、错，10、错，11、对，12、对，13、对，14、错，15、对，16、错 五、名词解释： 1.段式管理

答：段式存储管理支持用户的分段观点，以段为单位进行存储空间的分配。按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。 对换(SWAPPING) 2.页式管理

答：页式管理把内存分成大小相等的许多区域，每个区称为“块”（内存块），程序中的逻辑地址也进行分页，页的大小与块的大小一致。以块为物理单位进行内存空间分配，即把作业信息按页存放到块中。

进行存储空间分配时，根据作业的长度可确定它的页面数，一个作业有多少页，那么在把它装入内存时就给它分配多少块内存空间。这些内存块可以是不相邻的。 3.页面调度

答：当内存中无空闲块时，为了装入一个页面而必须按某种算法从已在内存的页中选择一页，将它暂时调出内存，让出内存空间，用来存放所需装入的页面，这个工作称为“页面调度”。 4.快表

答：为了提高存取速度，通常都设置一个小容量高速缓冲存储器。查找速度极快，但造价很高。利用高速缓冲存储器存放页表的一部分，把存放在高速缓冲存储器中的部分页表称“快表”。快表中登记了页表中的一部分页号与内存块号的对应关系。根据程序执行局部性

- 14 -

《操作系统原理》

的特点，在一段时间内总是经常访问结页，若所这些页登记在快表中，则可快速查找并提高指令执行速度。 5.虚存

答：虚拟存储器实际上是为扩大内存容量而采用的一种设计技巧。把作业信息保留在磁盘上，当作业请求装入时，只将其中一部分行装入内存，作业执行中若要访问的信息不在内存中，则再设法把这些信息装入内存。

虚拟存储器的容量是由计算机的地址结构决定的。 6.抖动

答：刚被调出的页面又立即要用，因而又要把它装入，而装入不久又被选中调出，调出不久又被装入，如此反复，使调度非常频繁。这种现象称为“抖动”或称“颠簸”。一个好的调度算法应减少和避免抖动现象。 7.逻辑空间

答：为了方便用户，每个用户可认为自己作业的程序和数据存放在一组“0”地址开始的连续空间中。用户程序中使用的地址称为“逻辑地址”，由逻辑地址对应的存储空间称“逻辑地址空间”。 8.物理空间

答：内存以字节（每个字节为8个二进制位）为单位编址，每个字节都有一个地址与其对应。假定内存的容量为n，则该内存就有n个字节的存储空间，其地址编号为0，1，2?，n－1。这些地址称为内存的“物理地址”（绝对地址），由物理地址构成的内存空间称“物理地址空间”。 9.覆盖

答：覆盖是指一个作业的若干程序段（或数据段）间，或者几个作业的某些程序段间共享某主存空间。覆盖技术通常与单用户连续分配、固定分区和可变分区等存储管理技术配合使用。它不但用于用户作业的运行中，而且还常用于操作系统本身的运行中。 10.内零头

答：若存储单元长度为N,该块存储的作业长度为M，则剩下的长度为(N-M)的空间称为该单元的内部碎片。 11.外零头

答：若存储单元长度为N，在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的作业,则称该块为外零头。

- 15 -

《操作系统原理》

12.请求页式管理

答：基于页式管理的虚拟存储技术。首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入内存，作业执行时若所访问的页面已在内存中，则进行地址转换，得到欲访问的内存绝对地址，若欲访问的页面不在内存中，则产生一个“缺页中断”，由操作系统把当前所需的页面装入内存中。

为此，在装入作业时，就应在该作业的页表中指出哪些页已在内存，哪些页还没有装入内存。

13.请求段式管理

答：段式虚拟存储管理仍以段式存储管理为基础，为用户提供比内存实际容量大的虚拟空间。段式虚拟存储管理在段表中增设段是否在内存的标志以及各段在磁盘上的位置，已在内存的段要指出该段在内存中的起始地址和占用内存区长度。

作业执行中访问某段时，由硬件的地址转换机构查段表，若该段在内存，则立即把逻辑地址转换成绝对地址。若该段不在内存中，则形成“缺断中断”，由操作系统处理这个中断。处理的办法是：

（1）查内存分配表，找出一个足够大的连续区以容纳该分段，如果找不到足够大的连续区则检查空闲区的总和，若空闲区总和能满足该段要求，那么进行适当移动将分散的空闲区集中；若空闲区总和不能满足该段要求，可把内存中的一段或几段调出，然后把当前要访问的段装入内存。

（2）段被移动、调出和装入后都要对段表中的相应表目作修改。

（3）新的段被装入后应让作业重新地被中断的指令，这时就能找到要访问的段，可以继续执行下去。 14.地址变换

答：将逻辑地址转换为物理地址的过程。 六、简答题：

1、答：通过硬件支持和软件算法提供的可以比实际主存容量大得多的存储器是虚拟存储器。虚拟存储技术是实现内存扩充的主要手段。扩充内存的目的是为了增强系统的处理能力和方便用户。

2、答：固定式分区是在系统生成时将主存划分为若干个分区，每个分区的大小可以不等，但分区容量和分区数目固定不变。

可变式分区是动态划分存储器分区的方法，它是在作业装入内存时才建立的分区，并且要

- 16 -

《操作系统原理》

使分区的容量正好适应作业的大小。在作业进入系统前，根据作业的大小来申请所需的存储容量，然后由系统实施分配。

可重定位式分区分配即浮动分区分配，是解决碎片问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续的区域，而把“碎片”集中成一个较大的空白区。这个移动过程称为紧凑或靠拢。

3、答：分区存储管理不需要过多的硬件支持，只需界地址寄存器，用于实现地址变换和存储保护。对各分区的保护措施通常采用的方法有三种：界地址寄存器法、基址—限长寄存器法和锁匙相配法。

4、答：页表的主要作用是提供动态地址变换所需的数据。设置一个页表要考虑的因素主要有：页面大小的选取、页表中包含的信息、页表存放和位置（是否有快表）等。 5、答：引入段式存储管理的原因主要有两方面：从系统角度看，其他的各种存储管理方案为用户提供的是一个线性地址空间，这对于模块化程序和变化的数据结构的处理以及程序和数据的共享都带来不便；从用户角度看，也希望作业信息按自身的逻辑关系分成若干自然段。

段式存储管理方案的主要优点是：（1）彻底消除了碎片；（2）提供了大量的虚存；（3）允许动态增加段的长度；（4）便于作业中各模块的动态装入和连接；（5）可以实现程序和数据的共享；（6）便于实现存储保护。

段式存储管理方案的主要缺点：（1）进行地址变换和实际靠拢操作需花费CPU时间；（2）为管理各分段要建立若干表格，占用空间；（3）在辅存上管理可变长度的段比较困难；（4）也存在系统抖动现象。

6、答：请求分页、分段和段页式存储管理方案提供了虚拟存储器。

7、答：实现虚拟存储器的关键技术的两个：请求调页（段）技术；淘汰页（段）技术。 8、答：多次性是指可以把一个作业分多次装入内存，每次装入当前运行需要使用的部分。 交换性是指作业在运行过程中，可以当前暂不用的部分换出内存，若以后需时再换入内存。 离散性是指一个作业可以存放在内存不连续的多个区域中。

9、答：存储保护的主要任务是确保每道程序都只能在自己的存储区域内访问，这就要求对每一次访问的地址进行越界检查。如果越界检查完全由软件实现，则会降低程序的执行速度，越界检查通常由硬件实现。当然对发现越界后的处理需与软件配合来完成。所以存储保护功能是由硬件和软件协同来完成的。

10、答：以进程为单位进行对换时，并非每次都将整个进程换出。原因如下：

- 17 -

《操作系统原理》

从结构上看，进程是由程序段、数据段和进程控制块（PCB）三部分组成的。通常，PCB都常驻内存而不被换出。

如果程序段或数据段正被若干个进程共享，也不能被换出。 11、答：内存利用率不高主要表现在以下几方面：

内存中存在着大量的、分散的、难以利用的碎片；暂时或长期不能运行的程序和数据占据了大量的内存空间；当作业较大时内存只能装入少量的作业，当它们被阻塞时将使CPU空闲，从而也降低了内存的利用率；内存中存在着重复的拷贝。 针对上述问题，可采用下列方法来提高内存利用率：

改连续分配方式为离散分配方式，以减少内存的碎片；增加对换机制，将那些暂时不用的程序和数据从内存换到外存；采用虚拟存储管理技术，使更多的作业能装入内存，使CPU更加忙碌；引入动态装入和链接机制，尽量避免装入本次运行中不用的程序；引入存储器共享机制，允许一个正文段或数据段被若干个进程共享，以减少内存中的重复拷贝。 12、答：页式存储管理中设置的页表指出了逻辑地址中的页号与所占的主存块号的对应关系。页式存储管理在用动态重定位方式装入作业时，要利用页表做地址转换工作。快表是存放在高速缓存中的部分页表。由于采用页表做地址转换，读写内存数据时CPU要访问两次主存。有了快表，有时只要访问一次高速缓存以及一次主存即可，这样就提高了查找的速度和指令执行的效率。

13、答：假设作业执行中访问页面的总次数为A，其中有F次访问的页面尚未装入主存，故产生F次缺页中断。于是定义f=F/A，f称为缺页中断率。

影响缺页中断率的因素有：1）分配给作业的主存块数；2）页面的大小；3）程序编制方法；4）页面调度算法。

14、答：缺页中断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、CPU现场等步骤。但缺页中断又是一种特殊的中断，它与一般中断的主要区别是:

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

一条指令在执行期间可能产生多次缺页中断。例如，对于一条读取数据的多字节指令，指令本身跨越两个页面，假定指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。

- 18 -

《操作系统原理》

15、答:内零头:若存储单元长度为N,该块存储的作业长度为M,则剩下的长度为(N-M)的空间称为该单元的内部碎片;若存储单元长度为N,在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的作业,则称该块为外零头.

在固定式分区分配中两种零头均会存在,因为空间划分是固定的,无论作业长短,存储单元均不会随之变化,若作业短而存储块长则产生内零头,若作业长而存储块短则产生外零头. 在可变式分区分配中只有外零头而无内零头,因为空间划分是依作业长度进行的,是要多少给多少,但剩下的部分太短而无法再分则成为外零头

页式虚存中会存在内零头而无外零头,因为存储空间与作业均分为等长单元,所以不存在无法分配的单元,但作业长度并不刚好为页面大小的整数倍,因此在 最后一页会有剩余空间,即为内零头

段式虚存中会存在外零头而无内零头,因段式的空间划分类似于可边分区分配,根据段长分配,要多少给多少,但会剩余小空间无法分配,则为外零头。

16、答：段式存储管理与页式存储管理的区别是：页式存储管理提供连续的逻辑地址，由系统进行分页；而短式存储管理中作业的分段由用户决定，每段独立编程，因此段间的逻辑地址是不连续的。

七、计算题：

1、答：用最先适应算法，这五个作业无法全部一次装入主存。因为J1（13K）和J2（36K）能够装入前两个空闲区（45K，40K），J3（108K）无法装入第三个空闲区（15K），所以J3（108K）和J4（43K）分别装入第四个（200K）和第五个空闲区（150K），而J5（195K）就无法装入主存了。

用最优适应算法能使主存的利用率最高。此时，五个作业能够依次全部装入主存。 2、解：若快表的命中率为85%，则有效存取时间为（1-85%）×1+1=1.15 若快表的命中率为50%，则有效存取时间为（1-50%）×1+1=1.5

3、答：1）由于共有4个页面，所以逻辑页号需要2位二进制数表示，每页1024个字节需要10位二进制数表示，所以，逻辑地址需要12位二进制数表示。

2）因为主存有64个物理块，需要6位二进制数来表示，块的大小与页的大小相等，所以块内地址也需要10位二进制数，所以，绝对地址需要用16位二进制数表示。 4、答：因为每页有512个字节，所以主存块中每块也有512个字节。则主存中各块的起始地址=块号*块长，它们分别如下。

- 19 -

《操作系统原理》

0块：0000 1块：0512 2块：1024 3块：1536 4块：2048 5块：2560 6块：3072 7块：3584 （a）0，200的绝对地址为：2048+200=2248 （b）1，185的绝对地址为：3072+185=3257 （c）越界 （d）越界

5、分析：由于每个主存块可以存放128个数组元素，只有一个内存块可以用来存放数组信息，数组中的元素按行编址。

对于第一个程序，数组访问顺序是：A[1,1],A[2,1],A[3,1], ??,A[128,1] A[1,2],A[2,2],A[3,2], ??,A[128,2] ???.

若采用LRU页面调度算法时，两个程序各会产生多少次缺页中断？

分析：由于每个主存块可以存放128个数组元素，只有一个内存块可以用来存放数组信息，数组中的元素按行编址。

对于第一个程序，数组访问顺序是：A[1,1],A[2,1],A[3,1], ??,A[128,1] A[1,2],A[2,2],A[3,2], ??,A[128,2] ???. A[1,128],A[2,128],A[3,128], ??,A[128,128]

显然，数组的存放顺序（按行）与访问顺序（按列）不一致，每访问一个数组元素遇到一次缺页中断。如果采用LRU算法，会产生128×128次缺页中断

对于第二个程序，数组访问顺序为：A[1,1],A[1,2],A[1,3], ??,A[1,128] A[2,1],A[2,2],A[2,3], ??,A[2,128] ???.

A[128,1],A[128,2],A[128,3], ??,A[128,128] 显然，数组的存放顺序（按行）与访问顺序（按行）一致，每访问一行数组元素遇到一次缺页中断。如果采用LRU算法，会产生128次缺页中断

解：采用LRU算法时，程序（1）会产生128×128次缺页中断，程序（2）会产生128次缺页中断。

6、解：（1）作业的虚存地址空间为：2=1MB （2）系统的页面大小为：2=2KB

- 20 -

11

20

《操作系统原理》

（3）逻辑地址5000分解成页号P和页内地址W为：P=2，W=904，其对应的物理地址为 5×2KB+904=10KB+904=11144

分析：逻辑地址结构为20位，而页内地址占11位，页号占9位，所以作业的虚存地址空间为2=1MB，系统的页面大小为2=2KB。把逻辑地址5000分解为页号和页内地址：5000 mod 2K, 得到页号为2，页内偏移为904，查页表，页号2 对应的物理块号为5，从而可以求出对应的物理地址。 7、 作业名 进入“输入井”时间 A B C D 8:30 8:40 8:50 9:00 40 30 50 20 40K 120K 180K 80K 8:30 8:40 10:00 9:10 8:30 9:10 10:00 9:40 9:10 9:40 10:50 10:00 40 60 120 60 需计算时间（分钟） 主存要求 装入主存时间 开始执行时间 执行结束时间 周转时间（分钟） 20

11

（1）按上述要求填充表中的空白处

(2)计算四个作业的平均周转时间(40+60+120+60)/4=70

8、答：FIFO： 是否缺页 内存中包含的页面 8 8 8 8 0 0 0 2 2 3 4 0 2 3 4 5 2 3 4 5 0 3 4 3 5 5 0 0 2 2 3 8 0 2 8 0 2 3 0 4 0 5 3 4 0 4 3 2 3 0 2 8 0 * * * * * * * * * * 产生10次缺页中断 LRU： 8 0 2 3 0 4 0 5 3 4 0 4 3 2 3 0 2 8 0 - 21 -

《操作系统原理》

是否缺页 内存中包含的页面 * * * * * * * * 8 8 8 8 0 0 0 2 2 3 4 0 2 3 4 0 5 3 4 0 2 3 8 0 2 3 产生8次缺页中断

9、答：1）采用“先来先服务算法”：

作业名 装入主存的时间 A B D C E 8:06 8:18 9:00 9:14 9:14 8:06 8:46 9:14 9:39 10:01 8:46 9:14 9:39 10:01 10:11 开始执行时间 执行结束时间 周转时间（分钟） 40 56 39 91 61 所以，作业的执行顺序为A、B、D、C、E。作业的平均周转时间为：（40+56+39+91+61）/5=57.4分钟。 采用“短作业优先算法”：

作业名 装入主存的时间 A B D E C 8:06 8:18 9:00 9:14 9:14 8:06 8:46 9:14 9:39 9:49 8:46 9:14 9:39 9:49 10:11 开始执行时间 执行结束时间 周转时间（分钟） 40 56 39 39 101 所以，作业的执行顺序为A、B、D、E、C。作业的平均周转时间为：（40+56+39+39+101）/5=55分钟。

先来先服务算法具有一定的公平性，容易实现。但当计算时间长的作业先进入“输入井”而

- 22 -

《操作系统原理》

被选中执行时，就可能使计算时间短的作业长时间等待，从而使计算时间短的作业周转时间变长，因此平均周转时间也变长，降低了系统的吞吐能力。

采用短作业优先算法，能使平均周转时间最短。由于系统可以不断接受新作业进入输入井，如果新进入的作业估计的计算时间比较短，则会使进入输入井时间较早但计算时间长的作业等待时间过长，会令用户不满。由于该算法是以用户估计的计算时间为标准，所以要避免用户为了使自己的作业优先被处理而故意将计算时间估计得短一些。

第五章参考答案

一、单项选择题：

1、C，2、C，3、A，4、C，5、D，6、B，7、A，8、A，9、C，10、A，11、B，12、A，13、C，14、A，15、B，16、C，17、D，18、D，19、A，20、A 二、填空题：

1、(存储设备) (输入/输出设备)，2、(内存地址) (暂存数据)，3、（I/O设备）(三) (一)，4、（通道结构，通道，并行工作）

，5、(高的利用率) (死锁问题)，6、(CPU，(输入输出的处理机)，外设或外存)，)，7、(恢复点)，8、(顺序存取) (顺序存取)，9、(系统设备表) (设备控制表),(控制器控制表),(通道控制表)，10、（输入井和输出井） 三、判断题：

1、对，2、错，3、对，4、错，5、错，6、对，7、对，8、错 四、名词解释： 虚设备技术

答：虚拟设备：用共享设备来模拟独占设备的工作，把独占设备改造成可共享的，以提高设备的利用率，这种模拟的独占设备称为虚拟设备。 通道

答：又称输入输出处理机，完成内存与外设之间的传送信息。只要CPU启动了通道，通道就按指定的要求独立完成输入输出操作，而CPU可以做与输入输出操作无关的其他工作，从而使计算机系统获得了CPU与外设之间并行工作的能力。 缓冲技术

答：缓冲技术可提高外设利用率，尽可能使外设处于忙状态。目的是匹配CPU或用户应用

- 23 -

《操作系统原理》

进程与外设的不同处理速度，减少对CPU的中断次数，提高CPU和I/O设备之间以及各个I/O设备之间的处理并行性。因此，缓冲区所在的位置：内存，控制器或外设。 磁盘调度

答：为了提高系统效率，降低若干个访问者执行输入输出操作的总时间（平均服务时间），增加单位时间内的输入输出操作次数，应根据移动臂的当前位置使寻找时间和延迟时间尽可能小的那个访问者优先得到服务。

磁盘调度：系统采用一定的调度策略来决定各个等待访问磁盘者的执行次序，这一工作称为磁盘的“磁盘调度”，采用的调度策略称为“磁盘调度算法”。 设备驱动程序

答：驱动程序是I/O处理功能的低级系统例程。

它具有如下特征：（1）中转数据和控制：不是数据和控制的源端和目的端（应用程序和设备）,（2）与硬件特性密切相关：通常由硬件厂商提供，（3）向上屏蔽设备细节：不同类型设备通常其设备驱动程序接口不同，同类设备的接口相同。因此，同类设备的不同型号，只要更换设备驱动程序则可由OS使用。 设备管理

答：设备管理提供设备使用的用户接口：命令接口和编程接口。设备的符号标识；设备分配和释放：使用设备前，需要分配设备和相应的通道、控制器；设备的访问和控制：包括并发访问和差错处理；I/O缓冲和调度：目标是提高I/O访问效率。 设备分配

答：由于外设资源的有限，需解决进程间的外设共享问题，以提高外设资源的利用率。设备分配是对进程使用外设过程的管理。设备分配的原则是合理使用外设(公平和避免死锁)，提高设备使用率。 设备无关性

答：用户编制程序时不必指定特定的设备，在程序中使用“设备类、相对号”定义的逻辑设备。程序执行时系统根据用户指定的逻辑设备转换成与其对应的具体物理设备，并启动该物理设备工作。于是，用户编制程序时使用的设备与实际使用哪台设备无关，这种特性称为“设备的独立性”。 五、简答题：

1、答：设备管理的设计目标是：

A，方便性：向用户提供方便的设备使用接口；

- 24 -

《操作系统原理》

B，并行性：设备传输与CPU重叠，各设备之间并行工作； C，均衡性：既要使设备忙碌，又要避免忙闲不均； D，独立性：又称与设备无关性，它是隐蔽设备的物理特性。

设备管理的基本功能是：动态地掌握并记录设备的状态；按照设备的类型和系统中所采用的分配算法，决定把某一个设备分配给要求该设备的进程；完成实际的I/O操作。为完成上述功能，设备管理软件应包括I/O交通管制程序、I/O调度程序（即设备分配程序）、I/O设备处理程序。

2、答：常见的I/O控制方式有程序直接控制方式、中断控制方式、直接内存访问方式（DMA）和通道控制方式。

程序直接控制方式管理简单、价格低廉，但要使主机等待I/O设备，且设备与CPU、设备与设备只能串行工作。中断控制方式在某种程度上使CPU摆脱了等待I/O设备的空转现象，主机和外设可以并行工作，提高了主机的利用率，但由于中断次数多，每次中断都要作现场保护和恢复工作，系统开销较大，仍要占用较多的CPU时间，而且快速的I/O设备要求中断响应要足够快，否则会造成数据丢失。

DMA方式和通道方式都较好地解决了上述问题，从而大减少了CPU的负担。DMA方式与通道控制方式相比，在灵活性和功能方面仍存在一定的局限性，DMA方式要求CPU执行设备驱动程序启动设备，给出存放数据的起始地址以及操作方式和传送字节长度等，而且一个DMA控制器只能控制一个设备。

3、答：设备分配策略与下列因素有关：

A，I/O设备的因有属性：对于独占设备、共享设备、虚拟设备等通常采用相应的分配算法； B，设备分配算法：常见的有先来先服务算法、优先级高者优先算法； C，设备分配的安全性：避免死锁的产生；

D，设备独立性：是指应用程序使用的逻辑设备独立于系统实际配置的物理设备

4、答：实现虚拟设备必须要有一定的硬件和软件条件为基础。硬件方面需大容量的磁盘、中断机构和通道装置，具有CPU与通道并行工作的能力；软件方面应采用多道程序设计技术。

5、答：引入设备独立性可使应用程序独立于具体的物理设备。此时用户用逻辑设备名来申请使用某类物理设备。当系统中有多台该类设备时，系统可将其中的任何一台分配给请求进程，而不必局限于某一台指定的设备。这样可显著地改善资源的利用率及可适应性。独

- 25 -

《操作系统原理》

立性还可使用户程序独立于设备的类型。如进行输出时，既可用显示终端，也可用打印机，有了这种适应性就可以很方便地进行输入输出重定向。

为了实现设备独立性，在应用程序中应使用逻辑设备名来请示使用某类设备；而系统中必须设置一张逻辑设备表LUT用来进行逻辑设备到物理设备的映射，其中每个表目中包括逻辑设备名、物理设备名、设备驱动程序的入口地址三项；当应用程序用逻辑设备名I/O设备时，系统必须为它分配相应的物理设备，并在LUT表中建立一个表目，以后进程利用该逻辑设备名请求I/O操作时，便可从LUT中得到物理设备名和驱动程序入口地址。 6、答：在利用SPOOLING技术共享打印机时，对所有提出输出请求的用户进程，系统接受它们的请求时，并不真正把打印机分配给它们，而是为每个进程做两件事情（1）由输出进程在输出井中为它申请一空闲缓冲区，并将要打印的数据送入其中；（2）输出进程再为用户进程申请一张空白的用户打印请求表，将将用户的打印请求填入表中，再将该表挂到打印队列上。至此，用户进程觉得它的打印过程已经完成，而不必等待真正的慢速的打印过程的完成。当打印机空闲时，输出进程将从请求队列队首取出一张打印请求表，根据表中的要求将要打印的数据从输出井传送到内存输出缓冲区，再由打印机进行打印。打印完成后，再处理打印队列中的下一个请求表，直到打印队列空。

次序 1 2 3 4 5 6 7 8 9 10 11 12 FCFS 143 86 147 91 17794 150 102 175130 SSTF SCAN 143 147 150 175 177 130 102 94 91 86 CSCAN 143 147 150 175 177 86 91 94 102 130 143 147 150102130 94 91 86 175 177 六、计算题：

1、解：各种调度算法的寻道次序如表所示： 计算可得各算法的磁头移动次数如下。

- 26 -

《操作系统原理》

(1)FCFS：565 (2)SSTF：162 (3)SCAN：125 (4)CSCAN：169

2、分析：解题方法为先计算出每种算法的柱面移动总量，因为每个柱面移动需要6ms，所以寻道时间=柱面移动总量×6ms

解：（1）先来先服务算法调度顺序为：10，22，20，2，40，6，38，

柱面移动总量为(20-10)+(22-10)+(22-20)+(20-2)+(40-2)+(40-6)+(38-6)=146， 寻道时间为146×6ms=876ms

(2) 下一个最邻近柱面即最短寻道优先，调度顺序为20，22，10，6，2，38，40 柱面移动总量为60，寻道时间为60×6ms=360ms (3) 电梯算法调度顺序为:20,22,38,40,10,6,2 柱面移动总量为58，寻道时间为58×6ms=348ms

3、分析：由于磁带的物理块长为B，所以一个长度为L字节的文件存放到磁带上需要L/B（向上取整数）个磁带块。由于启动一次磁带机可交换8个块的信息，所以读/写这个文件共需执行 [L/B]/8 次I/O操作。为满足读/写该文件的需要，应设置的内存缓冲区至少应能放下8个块的信息，故至少需8B个字节。

答：（1）存放该文件需L/B（向上取整数）个磁带块。 （2）读/写这个文件共需执行 [L/B]/8 次I/O操作。 （3）应设置的内存缓冲区至少需8B个字节。

4、分析：本题中，作业的调度不仅与作业到达时间有关，而且与系统中的资源分配情况有关。内存分配采用可变式式分区管理，要求先分配地址低端且不能移动已存放在内存中的作业，即将内存空间按用户要求动态地划分成若干个分区，每次分配内存空间时总是从某个满足空间要求的空闲分区中划分出与作业大小相同的一部分。静态分配指的是作业得到了所有申请的外设后才能进入主存运行

8：00时，作业1到达，此时内存和外设均处于空闲状态，且作业1申请的设备台数与内存均可满足。

8：20时，作业2到达，由于作业2申请的打印机当前正被作业1使用，因此作业2只能等待。与此同时，作业3也已到达，它只申请1台磁带机和60K内存空间，系统能满足它的

- 27 -

《操作系统原理》

要求，因此作业3进入内存运行。此时作业1已运行了20分钟，它还需要运行5分钟，但这时内存中已有两道作业，因此它们要平分CPU时间，既作业1至少还要运行10分钟才能运行完毕。

8：30时，作业1运行完毕，释放了它所占用的磁带机和打印机，也释放了它所占用的内存空间。此时系统中有1台磁带机和1台打印机空闲，还有一个大小为15K和一个大小为25K的空闲分区。与此同时，作业4到达，它与正在等待的作业2一起竞争内存和外设。因作业2要求的内存空间量无法满足，因此作业2只好继续等待。作业4只申请20K内存空间并只要1台磁带机，它的申请可以满足。此时，作业3已运行了5分钟，还需要15分钟，内存中有两道作业。

8：35时，作业到达，这时没有空闲磁带机，作业5等待

9：00时，作业3运行完毕，释放了它所占用的1台磁带机和内存空间。此时系统中有1台磁带机和1台打印机，还有一个大小为75K和一个大小为5K的空闲分区。因作业2先于作业5到达，且作业2的申请资源能够得到满足，所以作业2被调入内存，而作业5继续等待。

9：10时，作业4运行完毕，释放了它所占用的磁带机和内存空间。此时，系统中有2台磁带机空闲，还有一个大小为70K的空闲分区。但因作业5申请1台打印机，它只好继续等待。

9：15时，作业2运行完毕，释放了它所占有的打印机和内存空间。作业5进入内存运行，它独自使用CPU，15分钟后，运行完毕。 由上述分析可知：

(1) 作业调度选中作业的次序是1，3，4，2，5 (2) 作业1的周转时间是8：30-8：00=30分钟 作业2的周转时间是9：15-8：20=55分钟 作业3的周转时间是9：00-8：20=40分钟 作业4的周转时间是9：10-8：30=40分钟 作业5的周转时间是9：30-8：35=55分钟 (3) 作业全部执行结束的时间是9：30 5、答：根据题目给出的已知条件可得： 磁盘转速：6000转/60000ms=0。1转/ ms; 转一段需时间：（1/9）/0。1=10/9 ms;

- 28 -

《操作系统原理》

读完后需处理时间为2。5 ms；最后一段不需处理时间；

假定读文件从A段开始，首先计算出读A，B所需的时间，其他依次类推。A段被读出后，磁盘继续转动，因此当A处理完后，磁头并未定位在B段的起始点，需将磁盘转到B段的起始点开始读起；B段读完后，出现同样情况，再将磁盘转至C段起始点，开始读起， D，E，F，G，H，I 段同样处理。

读A段需时间10/9ms，处理A的2。5 ms时间内磁盘转过段数为2。5/（10/9）=2。25段，即当A处理完后，磁头定位在D段1/4位置处，若要顺次读取B段，还需转（6+3/4）段，所需时间为（10/9）*（6+3/4）ms=7。5ms ，此为定位B段起始点所花费的时间，同理，定位其他段起始时间一样，共计8*7。5=60ms;加上读出各段所花费时间为（10/9+2。5）*8+10/9=30ms;则60+30=90

将上述情况改进，在2。5ms 时间内磁盘转过2。5/（10/9）=2。25段，让A，B两段相隔3段，则在A段处理完后，只需经过3/4段便可定位B 段，故定位B段所花费时间为（10/9）*（3/4）=5/6ms，定位时间总计为8*5/6=20/3ms;加上读各段花费的时间30ms， 故总时间为36。7。

第六章参考答案

一、单项选择题：

1、A，2、A，3、B，4、B，5、B，6、D，7、B，8、A，9、A，10、D，11、D，12、B，13、C，14、C，15、C，16、A,B，17、C 二、多项选择题： 1、( A，D，F，G，H) 三、填空题：

1、无结构的流式文件，有结构的记录文件，记录，2、顺序存取法，直接存取法，3、绝对路径，相对路径，根目录，前目录，4、空闲文件目录，空闲链表，位示图，5、防止未经核准的用户进入系统，为用户分配文件访问权，为保护系统的各级目录，控制用户对文件的访问，6、首块地址和文件长度，7、普通文件，目录文件，特殊文件，8、文件保密，9、顺序存取，随机存取，10、文件的保密，11、文件备份，文件转储，12、顺序存取，13、索引，数据，14、文件的存储地址，15、增量转储，16、文件名，文件在磁盘上的存放地址，17、索引表，首地址

- 29 -

《操作系统原理》

四、判断题：

1、错，2、错，3、错，4、对，5、对，6、错，7、错，8、对，9、错，10、对，11、对，12、错，13、错，14、错，15、对 五、名词解释： 1.文件

答：逻辑上具有完整意义的信息集合。 2.文件系统

答：是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。 3.文件目录

答：把所有的目录项有机地组织在一起，就构成了文件目录。 4.目录文件

答：由文件目录组成的文件。系统中有许多的文件目录（或子目录），文件目录需要长期保存，为了对文件目录进行管理，通常把文件目录也作为文件保存在外存中。 5.值班目录

答：把当前正在使用文件的文件目录存放在内存中，称为值班目录。为了提高文件检索速度，文件系统向用户提供了一个当前正在使用的目录，称为当前目录。 6.文件保密

答：防止未经文件拥有者授权而窃取文件。 7.文件保护

答：防止文件被破坏。 8.目录项

答：目录项记录了系统为管理文件所需的有关信息。包括文件名、存储介质上的位置，以及如何和管理文件等信息。（文件控制块） 9.顺序存取

答：对文件中的信息按顺序依次进行读写的存取方式； 10.随机存取

答：可以按任意次序随机地读写文件中的信息。 11.绝对路径名

答：指出了从根目录开始跟随的一条指向指定文件的路径；

- 30 -

《操作系统原理》

12相对路径名

答：指出了从当前目录出发到指定文件的路径。 六、简答题：

1、答：把一些外部设备也看成文件，用户就可以用统一的观点去看待和处理驻留在各种存储媒体上的信息而无需去考虑保存文件的设备差异，从而为用户带来很大的方便。 2、答：文件目录是文件系统的关键数据结构，用来组织文件以及对文件进行检索。 文件目录中包含若干个目录项，在文件目录表中的每个目录项是一个文件控制块。一个文件控制块包含以下住处文件的标识信息、文件的结构信息、文件存取控制信息、文件的管理信息。

常用的目录结构形式有三种：单级的文件目录、二级目录、多级树型目录结构。 3、答：文件的存取方式主要有顺序存取法和随机存取法。确定文件的存取方式取决于两方面的因素：与怎样使用文件有关、与存储介质的特性有关。

4、答：文件的保护是指防止文件被破坏。文件的保密是指防止未经文件拥有者许可，任何用户不得访问该文件。

5、答：原因为：用户进程存取一个文件时，系统首先要检索目录结构，按名查找该文件控制块。打开文件的基本思想是：按指定文件名检索目录结构，把找到的文件控制块读入并保存到内存中，此后每次存取该文件时，就无需再执行按名查找过程，可以直接在内存中找到它的文件控制块，从而加快了存取速度。文件打开后，可以对该文件进行读写、存取。当一个文件不再被存取时，需关闭该文件，释放占用的活动文件控制块和系统打开文件表的资源，并将文件控制块的内容复制到存储设备上。这样做，一方面提高了资源利用率，另一方面保证了数据安全（对于延迟写系统） 七、计算题：

1、答: 在引入索引结点前， 每个目录项中存放的是对应文件的FCB，故256个目录项共需占用256*64/512=32个盘块， 因此，在该目录中检索到一个文件平均启动磁盘次数为(1+32)/2= 16.5次

引入索引结点后，每个FCB只需存放文件名和索引结点的编号，则256个目录项共需占用256*(8+2)/512 = 5 个盘块，因此找到匹配的目录项平均需要启动(1+5)/2，即3次磁盘;得到索引结点编号后，还需启动磁盘将文件的索结点读入内存，故平均需启动磁盘 4 次. 2、答：（1）位示图需要[500/32]=16个字

（2）第i 字第j 位对应的块号是32×i + j 。

- 31 -

《操作系统原理》

3、答：（1）为有效利用磁盘空间，可以将两个逻辑记录作为一组，存放在一个物理块中，块中余下的12个字节可以用来保存链接指针。

（2）包含第1452个字符的逻辑记录位置为：逻辑记录号=int (1452，250)=5 ; 位移量=mod( 1452， 250) = 202 ， 从该文件的目录中取出文件的首地址，即存放第0个逻辑记录的物理块号，顺着链接指针即可找到第5个逻辑记录。 4、解：因为 1569=512*3+33

所以要访问字节的逻辑记录号为3，对应的物理磁盘号为80。故应访问第80号磁盘块。 5、解：（1）因磁带记录密度为每英寸800字符，则一个逻辑记录占据的磁带长度为： 160/800=0。2英寸，1500个逻辑记录要占据的磁带长度为（0。2+0。6）*1500=1200英寸。 磁带利用率为： 0。2/（0。2+0。6）=25%

（2）要使磁带利用率不少于50%，则一组逻辑记录中的记录数为x 0.2x/(0.2x+0.6)>=50% X>=3

所以一组中的逻辑记录数至少为3

模拟试题（一）参考答案

一、线程 2. 并发 3. 临界区 4. 虚拟存储器 5. 设备独立性 二、1，文件管理2，装入时，运行时

3，逻辑设备，物理设备 4， CPU I/O设备 5，进程同步 6，CPU时间，磁盘空间 三、简答题

1，模块结构：提高了OS的正确性、可理解性和可维护性；增强了OS的可适应性，可依需要进行裁剪；加速了开发过程。其难点存在于模块的划分、接口的定义。

层次结构：基本原则为每一层都只使用其底层提供的功能和服务，并对上层提供服务，这样可使系统的调试和验证都很容易。其设计遵循自底向上的原则。其难点在于层次的划分和层次顺序的确定。如MS DOS，分为BIOS、DOS核心和命令处理程序这样几层。 微内核结构：微内核指经过精心设计的、能实现OS核心功能的小型内核，运行在核心态，常驻内存。它包括进程管理、存储管理、进程通信、低级I/O，而其他的功能则以服务的形式提供。WIN NT 就是以微内核为核心、以C/S为基础的OS。微内核结构减小了OS的复杂

- 32 -

《操作系统原理》

性，增强了可维护性和可扩展性。

2，实时时钟管理：提供系统日期和时间、定时和延时等时钟管理功能；过载保护：缓冲区排队，丢弃某些任务，动态调整任务周期；高度可靠性和安全性：容错能力（如故障自动复位）；基于优先级的抢占式CPU调度。 3，当前系统处于安全状态。

如果系统中的可利用资源Available为（0，6，2），系统不安全，因为找不到一个安全序列，使5个进程全部执行结束。

4，LRU：最近最久未使用置换算法，即选择最近最久未使用的页面来淘汰。该算法需要较多的硬件支持，所以较难实现。一个近似算法为CLOCK算法，为每页设置一个“引用位”，当页表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页。

5，打印机虽然是独享设备，但是通过SPOOLing技术，可以将它改造为一台可供多个用户共享的设备。当用户进程请求打印输出时，SPOOLing系统并不是真正把打印机分配给该用户进程，而由输出进程为他在输出井中申请一个存储空间，并将要打印的数据以文件的形式存放于此。各进程的输出文件形成一个输出队列，由输出SPOOLing系统控制这台打印机进程，依次将队列中的输出文件打印出来。所以利用SPOOLing技术可以提高I/O的速度，将独占设备改造为共享设备，实现虚拟打印机的功能。

四，1，Mutex1 = 1,mutex2 = 1,empty = 10,full = 0, count =3,其中Mutex1,mutex2为互斥信号量,分别实现对汽车和仓库的互斥使用, empty, full, count为资源信号量, empty和full分别表示仓库为空、满，count表示可用的三轮车的数目。

向仓库放货物： 从仓库取货物： Repeat

P(empty); P(count);

P(mutex1);

把货物从汽车搬到三轮车上; V(mutex1);

- 33 -

Repeat

P(full); P(count); P(mutex2);

把仓库中的货物放入三轮车; V(mutex2); V(empty); V(count); Until false

《操作系统原理》

P(mutex2);

把三轮车上的货物放入仓库; V(mutex2);

V(count); V(full); Until false;

2，FAT中有多少项：500KB / 2.5B = 200K, 即磁盘有200K块,故磁盘大小为200MB. 目录中的文件数为32KB / 16B = 2K 数据区200MB

模拟试题（二）参考答案

一、名词解释（每小题2分，共10分）

1.多个相关进程在执行次序上地协调，这些进程相互合作，在一些关键点上可能需要互相等待或互通消息。

2．在内存中同时存放多道用户作业，使它们都处于执行的开始点和结束点之间。 3．允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。 4．将作业地址空间中使用的逻辑地址转换为存储空间中的物理地址的过程。 5．将空闲分区按地址递增的次序排列，在进行内存分配时，从空闲分区表首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，按照作业大小，从该分区中划出一块内存空间分配给请求者。 二、填空（每空1分，共24分）

1.程序的动态并发执行，进程控制块。

2．死锁预防，互斥使用条件， SPOOLing技术；不可剥夺条件、请求和保持条件、循环等待条件。 3．通用操作系统。 4． CPU，I/O。

5．吞吐量，资源利用率，周转时间。

6．先来先服务、短作业优先、基于优先级的调度、时间片轮转法。

- 34 -

《操作系统原理》

7．独占设备、共享设备、虚拟设备。 8．系统调用。

9．磁盘，请求调入和置换功能。 三、选择题（每小题1分，共6分） 1． C 2． B 3． D 4． C 5． D6． B 四、判断题（每小题1分，共5分） 1． F2． F3． F4． F5． T 五、简答题（每题4分，共20分）

1．答：设备管理的主要任务是：按照用户的要求控制I/O设备工作；按照一定的算法把I/O设备分配给对该设备提出请求的进程；充分有效地使用I/O设备，提高设备的并行操作程度。因此设备管理应具备：设备分配、设备控制和其它功能。

2.答：进程有三种基本状态，即（1）执行状态、（2）就绪状态、（3）阻塞状态。中断引起进程由（1）状态转换为（2）状态；处理机调度引起进程由（2）状态转换为（1）状态；等待资源和事件引起进程由（1）状态转换为（3）状态；事件发生或资源等到引起进程由（3）状态转换为（2）状态。

3.答：操作系统一方面能向用户提供接口，方便用户使用计算机；另一方面它能管理计算机软硬件资源，以便和李充分地利用它们。从资源管理的角度讲，操作系统具有作业管理、进程管理、存储管理、设备管理和文件管理的功能。

4.答：在交换信息量方面：利用P、V操作原语可以实现进程的互斥和同步，但只能交换少量的信息，缺乏传输消息的能力；而高级通信不仅可以实现进程的互斥和同步，且能交换大量的消息，是理想的进程通信工具。

通信对用户透明方面：用P、V操作原语通信时必须在用户程序中增加P、V编程，而且若编程不当，还会出现死锁；而高级通信机制对用户则是透明的。

5.答：文件的结构就是文件的组织形式，从用户观点出发所看到的文件的组织形式称为文件逻辑结构；从实现观点出发，文件在外存上的存放组织形式称为文件的物理结构。文件的逻辑结构分为有结构的记录式文件和无结构的流式文件。文件的物理结构主要有顺序结构，链接结构和索引结构。

六、答：设置信号量s12，s13，s14，s24，s25，s35，s46，s56,初值为0

S1:s1,v(s12),v(s13),v(s14); S2:p(s12),s2,v(s24),v(s25);

- 35 -

《操作系统原理》

S3:p(s13),s3,v(s35); S4:p(s14),p(s24),s4,v(s46); S5:p(s25),p(s35),s5,v(s56); S6:p(s46),p(s56),s6.

七、答：（1）先来先服务算法，磁头移动序列为：

20?10?22?20?2?40?6?38，

共移动（10＋12＋2＋18＋38＋34＋32）＝146道，寻道时间为146×6＝876毫秒。 （2）下一个最邻近算法，磁头移动序列为：

20?22?10?6?2?38?40，

共移动（2＋12＋6＋4＋36＋4）＝64道，寻道时间为64×6＝384毫秒。 （3）电梯算法，磁头移动序列为：

20?22?38?40?10?6?2，

共移动（2＋16＋2＋30＋4＋4）＝58，寻道时间为58×6＝348毫秒。

八、答：各进程运行序列为：0 P1 1 P2 5 P4 10 P1 17 P3 26

其中，P1的等待时间为9，周转时间为17； P2的等待时间为0，周转时间为4； P3的等待时间为15，周转时间为24； P4的等待时间为2，周转时间为7；

则平均等待时间为（9＋15＋2）/4＝6.5，平均周转时间为（17＋4＋24＋7）/＝13 九、答：need如图红色部分所示。

讲资源先分给P1, 释放资源后available（5，3，2），再给P3，释放资源后available（7，4，3），给P4,P2,P0,所以安全序列为P1,P3,P4,P2,P0.

十、答：进程体共分为320/32＝10页，每页32字需要5位表示页内偏移地址。

逻辑地址101（八进制）＝001000001，则偏移地址为00001，逻辑页号为010，在联想存储器中找到对应的物理块号f3.

逻辑地址204（八进制）＝010000100，则偏移地址为00100，逻辑页号为100，联想存储器没有对应的页号，但在页表中对应的物理块号f3.

逻辑地址576（八进制）=101111110,则偏移地址为11110，逻辑地址页号1011，超出了范围，所以越界中断。

- 36 -

《操作系统原理》

S3:p(s13),s3,v(s35); S4:p(s14),p(s24),s4,v(s46); S5:p(s25),p(s35),s5,v(s56); S6:p(s46),p(s56),s6.

七、答：（1）先来先服务算法，磁头移动序列为：

20?10?22?20?2?40?6?38，

共移动（10＋12＋2＋18＋38＋34＋32）＝146道，寻道时间为146×6＝876毫秒。 （2）下一个最邻近算法，磁头移动序列为：

20?22?10?6?2?38?40，

共移动（2＋12＋6＋4＋36＋4）＝64道，寻道时间为64×6＝384毫秒。 （3）电梯算法，磁头移动序列为：

20?22?38?40?10?6?2，

共移动（2＋16＋2＋30＋4＋4）＝58，寻道时间为58×6＝348毫秒。

八、答：各进程运行序列为：0 P1 1 P2 5 P4 10 P1 17 P3 26

其中，P1的等待时间为9，周转时间为17； P2的等待时间为0，周转时间为4； P3的等待时间为15，周转时间为24； P4的等待时间为2，周转时间为7；

则平均等待时间为（9＋15＋2）/4＝6.5，平均周转时间为（17＋4＋24＋7）/＝13 九、答：need如图红色部分所示。

讲资源先分给P1, 释放资源后available（5，3，2），再给P3，释放资源后available（7，4，3），给P4,P2,P0,所以安全序列为P1,P3,P4,P2,P0.

十、答：进程体共分为320/32＝10页，每页32字需要5位表示页内偏移地址。

逻辑地址101（八进制）＝001000001，则偏移地址为00001，逻辑页号为010，在联想存储器中找到对应的物理块号f3.

逻辑地址204（八进制）＝010000100，则偏移地址为00100，逻辑页号为100，联想存储器没有对应的页号，但在页表中对应的物理块号f3.

逻辑地址576（八进制）=101111110,则偏移地址为11110，逻辑地址页号1011，超出了范围，所以越界中断。

- 36 -

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