作系统结构课后习题参考答案

第三章操作系统结构

3.1操作系统关于进程管理的五个主要活动是什么？

答：（1）创建和删除用户进程和系统进程；

（2）暂停和重启进程；

（3）提供进程同步机制；

（4）提供进程通信机制；

（5）提供死锁处理机制。

3.2操作系统关于内存管理的三个主要活动是什么？

答：（1）记录内存的哪部分正在被使用及被谁使用；

（2）当内存空间可用时.，决定哪些进程可以装入内存；

（3）根据需要分配和释放内存空间。

3.3操作系统关于二级存储管理的三个主要活动是什么？

答：（1）空闲空间管理；

（2）存储空间分配；

（3）硬盘调度。

3.4操作系统关于文件管理的五个主要活动是什么？

答：（1）创建和删除文件；

（2）创建和删除目录：

（3）提供操作文件和目录的原语；

（4）将文件映射到二级存储器（辅存）上；

（5）在稳定（非易失的）存储媒介上备份文件。

3.5命令解释器的用途是什么？为什么它经常与内核是分开的？

答：（1）命令解释器的用途：从用户或命令文件读入命令并执行它，通常将其变成一个或多个系

统调用它们。

（2）它通常不是内核的一部分，因为命令解释是会改变的，不是固定的。

3.7系统调用的用途是什么？

答：（1）系统调用提供了进程与操作系统之间的接口，即允许用户级进程要求操作系统的服务。

3.10系统程序的用途是什么？

答：（1）系统程序可以被认为是有用的系统调用的捆绑。它们给用户提供了基本功能以使用户不

需要写自己的程序来解决共同的问题。

第四章进程

4.2论述短期、中期和长期调度之间的区别。

答：（1）短期调度：从就绪可执行的进程中选择进程，并为其中之一分配CPU。

（2）中期调度：特别用于分时系统中作为中等程度调度程序。能将进程移出内存（并移出对

CPU的激烈竞争），因此降低多道程序设计的程度。之后进程能被重新调入内存，并从中断处继

续执行。

（3）长期调度：从缓冲池中选择进程，并将它们装入内存以执行。

它们的主要区别是执行的频率。短期调度程序必须频繁地为CPU选择新进程执行；长期调度

程序执行并不频繁，用于控制多道程序设计的程度，即内存中的进程数量；中期调度程序介于两

者之间。

4.4描述一下内核在两个进程间进行上下文切换的动作。

答：通常，操作系统必须保存正在运行的进程的关联状态并装入经调度要执行的新进程的已保存

的关联状态。保存的状态通常包括除了内存分配之外的所有CPU寄存器的值。上下文切换还执行

许多体系结构的具体操作，包括包括冲厕数据和指令缓存。

4.6第4.4节中的正确的生产者-消费者算法在任一时刻只允许装满n-1个缓冲区。修改这个算法

让它能够充分利用所有的缓冲区。

答：参照P142第七章进程同步。

第五章线程

5.3用户级线程与内核级线程的两个不同点是什么？在什么情况下一种类型比另一种类型更好？

答：(1)用户级线程对内核来说是未知的，而内核线程对内核是已知的；

(2)用户级线程山线程库调度管理，而内核级线程所有线程管理山核心完成。

(3)内核线程不需要与进程关联即以线程为基础进行调度，而每个用户线程必须从属于一个

进程。

5.4描述一下内核采取行动进行内核级线程上下文切换的过程。

答：内核线程之间的上下文切换通常需要保存被转出线程的CPU寄存器的值和恢复被调度要执行

的新线程的CPU寄存器的值。

第六章CPU调度

6.3答:

FCFS

SJF

非抢占Priority

1,21>4P1Pl

P1P3PsP3PlPsPlP5PlP5

0123456789101112131419

(2)每个进程在每种调度算法卜的周转时间为:

法FCFSSJF非抢占PriorityRR

进程

Pl10191619

11112

P2

P3134187

P4142194

Ps199614

(3)每个进程在每种调度算法卜的等待时间为:

法FCFSSJF非抢占PriorityRR

进程

Pl0969

10001

p2

P3112165

P4131183

14419

P5

(4)由上可知，SJF算法的平均等待时间最小。

6.4答:

a.10.53((8+11.6+12)/3)

b.9.53((8+8+12.6)/3)

c.6.86((1+5.6+14)/3)

第七章进程同步

7.1术语忙等的含义是什么？操作系统里其他种类的等待有哪些？忙等能否完全避免？为什么？

答：忙等的含义是当一个进程位于其临界区内时，任何试图进入其临界区的进程都必须在其进入

代码中连续地循环。

操作系统里其他种类的等待有：等待1/0,等待信号被释放等等。

忙等可以通过使用同步原语，如：互斥锁、信号量或条件变量。

7.2解释自旋锁对单处理器系统不合适而对多处理器系统合适？

答：在单处理系统中，因为只有唯一的一个CPU,因此在一个进程等待外部事件时造成CPU资

源的浪费。而在多处理系统中，由于自旋锁的优点是在进程必须等待一个锁时无需上下文切换，

因此当锁只保留较短时间时，就非常有用。

7.8理发店问题。

参考解答：使用三个信号量：customers,用来记录等候理发的顾客数（不包括正在理发的顾客）；

barbers,记录正在等候顾客的理发师数，为0或1；mutex用于互斥。另外还需要一个变量waiting,

也用于记录等候的顾客数，实际上是customers的•个副本。之所以使用waiting是因为无法读取

信号量的当前值。

在该解法中，进入理发店的顾客必须先检查等候的顾客数量，如果顾客数量少于椅子数，他

就留下来等，否则就离开。

理发师进程结构为：

do{

wait(customers);如果等待的顾客数为0则进入睡眠状态

wait(mutex);获得对waiting的访问权

waitint=waiting-l;将等待的顾客数减1

signal(barbers);一个理发师现在一经做好理发的准备

signal(mutex);释放waiting的访问权

cut_hair();理发（临界区以外）

}while(l);

顾客进程结构为：

wait(mutex);进入临界区

if(waiting<CHAIRS){如果没有空闲的座椅，离开

waitint=waiting+1;将等待理发的顾客数加1

signal(customers);如果需要，唤醒理发师

signal(mutex);释放waiting的访问权

wait(barbers);如果空闲理发师为0则进入睡眠状态

get_hair();就座并接受理发服务

}else{

Signal(mutex);理发店已满；不等待

第八章死锁

8.1列出三个与计算机系统环境相关的死锁的例子。

答：(1)两辆汽车从相反方向通过一座单行的桥梁；

(2)一人想爬上梯子而另一人想从梯子上下来；

(3)两列火车企图在同一轨道上相向而行。

8.2死锁是否可能只涉及一个进程？为什么？

答：不可能。这违反了占有并等待条件。

8.9假设有一个系统有m个资源被n个进程共享，进程每次只请求和释放一个资源。证明只要系

统符合下面两个条件，就不会发生死锁：

a.每个进程需要资源的最大值在1到m之间。

b.所有进程需要资源的最大值的和小于m+n。

答：假设进程i需要的最大值为Max(i),已分配的资源实例数为Alloc(i),还需要资源数为Need(i)o

则〃芍<

a.・1IMm+n

b.Max,>1foralli

锁，则Al,..

c.》Allocationj=m

根据a可得:

£Necdj+£Allocationi=£Max,<ni+u

根据c可得:

£Need[+m<m+n

因此得到：

-NeediVn

可以得出至少存在一个进程Pi,其Need⑴=0,因为Max⑴21,因此该进程能正常运行结束并

释放一个资源，死锁也就不会发生。

8.13

答：(1)Need矩阵内容分别为：(0,0,0,0)；(0,7,5,0)；(1,0,0,2)；(0,0,2,0)；

(0,6,4,2)

(2)该系统处于安全状态。

(3)P1请求为(0,4,2,0),止匕时Available为(1,1,0,0),该请求能立刻被满足。

第九章内存管理

9.2说明内部碎片与外部碎片的区别。

答：内部碎片是指在一个分区或一个页内，但是没有被占有这个分区或页的进程使用的内存。即

分配给作业的存储空间中未被利用的部分，直到该作业完成并释放该分区或页时才能被使用。而

外部碎片是指系统中无法利用的小存储块，只要通过合理的移动使所有空闲空间合并成一整块便

可分配给作业。

9.3描述卜列分配算法：首次适应、最佳适应、最差适应

答：（1）首次适应：搜索空闲内存列表分配第一个足够大小要求的空闲分区。

（2）搜索整个内存列表分配最小的足够大小要求的空闲分区。

（3）最差适应：搜索整个内存列表分配最大的空闲分区。

9.5如果有内存划分100KB、500KB,200KB、300KB和600KB（按顺序），首次适应、最佳适

应与最差适应算法各自将怎样放置大小分别为212KB、417KB、112KB和426KB（按顺序）的进

程？哪一种算法的内存利用率最高？

答：（1）首次适应：212K放在500K分区（剩余288K）；417K放在600K分区；112K放在剩余

的288K分区；而426K进程必须等待。

（2）最佳适应：212K放在300K分区；417K放在500K分区；112K放在200K分区；426K

放在600K分区。

（3）最差适应：212K放在600K分区（剩余388K）；417K放在500K分区；112K放在剩

余388K分区；而426K进程必须等待。

从上可看出，最佳适应算法的内存利用率最高。

9.8假设一个有8个1024字页面的逻辑地址空间，映射到一个有32帧的物理内存。问：

a.逻辑地址多少位？

b.物理地址多少位？

答:逻辑地址13位；物理地址15位。

9.10假设一个将页表放在内存的分页系统。

a.如果一次内存访问用200ns,访问一页内存需要多少时间？

b.如果加入TLB,并且75%的页表引用发生在TLB,内存有效访问时间是多少？（假设在TLB

中寻找页表项占用零时间，如果页表项在其中）。

答：a.访问一页内存需要200ns+200ns=400ns。

b.有效内存访问时间：0.75x200+0.25x400=250nso

9.16答：

a.0430逻辑地址的物理地址是：219+430=649

b.110逻辑地址的物理地址是：2300+10=2310

c.2500逻辑地址的长度越界，产生中断

d.3400逻辑地址的物理地址是：1327+400=1727

e.4122逻辑地址的长度越界，产生中断

第十章虚拟内存

10.1在什么情况下出现页错误？描述一下发生页错误时操作系统做了哪些动作？

答：当进程试图访问那些尚未调入到内存的页时，对标记为无效的访问会产生页错误陷阱。

处理页错误的程序：

(1)操作系统检查进程的页表，以确定该引用是合法还是非法的地址访问；

(2)如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入；

(3)找到一个空闲帧；

(4)调度一个磁盘操作，以便将所需要的页调入刚分配的帧；

(5)当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中；

(6)重新开始因非法地址陷阱而中断的指令。

10.10

答：由题目所给条件可知，数组A有100x100=10000个整数，系统中共有2个内存页用于存放数

组信息，数组中的元素按行编址。

若每页存放200个整数，则一个内存页中可以存放2行数组元素，对于程序a,数组元素的

访问顺序为：

A[0][0],A[0][l],A[01[99]

A[l][0],A[l][l]....A[l][99]

A[99][0],A[99][l]....A[99][99]

显然程序a对数组A的访问顺序与存储顺序一致，也是按行进行的。因此程序a每访问2行

数组元素都会产生一次缺页中断，则访问整个数组会产生100/2=50次缺页中断。

对于程序b,数组元素的访问顺序为：

A[0][0],A[l][0]....A[99JIOJ

A[0][l],A[l][l],A[99][l]

Af0][99],A[l][99],A[99][99]

显然程序b对数组A的访问顺序与存储顺序不一致。因此程序b每访问2个元素将产生一次

缺页中断，则访问整个数组会产生10000/2=5000次缺页中断。

10.II

答:

最近最少使用FIFO页置换最优页置换

帧数^\

(LRU)

12