操作系统课后重点习题整理

操作系统课后重点习题整理

第一章

1.17Definetheessentialpropertiesofthefollowingtypesofoperating

systems:列出卜列操作系统的基本特点：

a.Batch批处理

b.Interactive交互式

c.Timesharing分时

d.Realtime实时

e.Network网络

g.Distributed分布式

f.并行式h.集群式i.手持式

Answer:作业chi-第四题

（第六版答案）

a.Batch

相似需求的J2b分批、成组的在计算机上执行，Job由操作员或自动Job程序装置装

载；可以通过采用buffering,off-lineoperation,spooling,multiprogramming等

技术使CPU和I/O不停忙来提高性能

批处理适合于需要极少用户交互的Jobo

b.Interactive

由许多短交易组成，下一次交易的结果可能不可预知

需要响应时间短

c.Timesharing

使用CPU调度和多道程序提供对系统的经济交互式使用，CPU快速地在用户之间切换一

般从终端读取控制，输出立即打印到屏幕

d.Realtime

在专门系统中使用，从传感器读取信息，必须在规定时间内作出响应以确保正确的执行

e.Network

在通用os上添加

联网、通信功能

远程过程调用

文件共享

f.Distributed

具有联网、通信功能

提供远程过程调用

提供多处理机的统一调度调度

统i的存储管理

分布式文件系统

第二章

第六版2.3Whatarethedifferencesbetweenatrapandaninterrupt?Whatis

theuseofeachfunction?

答:作业ch2-第二题

（第六版答案）Aninterrupt是硬件产生的系统内的流的改变

Atrap是软件产生的“中断”。

interrupt可以被I/O用来产生完成的信号，从而避免CPU对设备的轮询

Atrap可以用来调用OS的例程或者捕获算术错误第七版2.3讨论向操作系统传递参数

的三个主要的方法。

1.通过寄存器来传递参数

2.寄存器传递参数块的首地址

3.参数通过程序存放或压进堆栈中，并通过操作系统弹出堆栈。

第三章

第七版3.1论述短期，中期和长期调度之间的区别.

a.短期调度:在内存作业中选择就绪执行的作业,并为他们分配CPU,

b.中期调度:作为一种中等程度的调度程序，尤其被用于分时系统，•个交换方案的实

施，将部分运行程序移出内存，之后，从中断处继续执行。

c.长期调度（作业调度程序）：确定哪些作'也调入内存以执行.

它们主要的不同之处是它们的执行的频率。短期调度必须经常调用一个新进程，由于在

系统中，长期调度处理移动的作业时，并不频繁被调用，可能在进程离开系统时才被唤

起。

第七版3.2问：描述一下内核在两个进程间进行上下文功换的动作.

答：总的来说，操作系统必须保存正在运行的进程的状态，恢复进程的状态。保存进程

的状态主要包括CPU寄存器的值以及内存分配，上下文切换还必须执行一些确切体系结构

的操作，包括刷新数据和指令缓存。

（书中答案）进程关联是由进程的PCB来表示的，它包括CPU寄存器的值和内存管理信

息等。当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调

度要执行的新进程的已保存的关联状态。

第五章

第七版5.4Considerthefollowingsetofprocesses,withthelengthofthe

CPU-bursttimegiveninmilliseconds:（考虑下列进程集,进程占用的CPU区间长度

以毫秒来计算：）

错误！未指定书签。

TheprocessesareassumedtohavearrivedintheorderPl,P2,P3,P4,P5,

allattime0.（假设在时刻0以进程Pl,P2,P3,P4,P5的顺序到达。）

a.DrawfourGanttchartsillustratingtheexecutionoftheseprocesses

usingFCFS,SJF,anonpreemptivepriority（asmallerprioritynumberimpliesa

higherpriority）,andRR（quantum=1）scheduling.（画出4个Gantt图分别演示用

FCFS、SJF、非抢占优先级（数字小代表优先级高）和RR（时间片=1）算法调度时进程的

执行过程。）

b.Whatistheturnaroundtimeofeachprocessforeachofthescheduling

algorithmsinparta?（在a里每个进程在每种调度算法下的周转时间是多少？）

c.Whatisthewaitingtimeofeachprocessforeachofthescheduling

algorithmsinparta?(在a里每个进程在每种调度算法下的等待时间是多少？)

d.Whichoftheschedulesinpartaresultsintheminimalaveragewaiting

time(overallprocesses)?(在a里哪一种调度算法的平均等待时间对所有进程而言最

小？)答：作业ch6-第三题

第六章

第六版6.4Supposethatthefollowingprocessesarriveforexecutionatthe

timesindicated.Eachprocesswillrunthelistedamountoftime.Inanswering

thequestions,usenonpreemptiveschedulingandbasealldecisionsonthe

informationyouhaveatthetimethedecisionmustbemade.

ProcessArri\Timo

Pl0.08

Pl0.44

1.01

p3

a.WhatistheaverageturnaroundtimefortheseprocesseswiththeFCFS

schedulingalgorithm?

b.WhatistheaverageturnaroundtimefortheseprocesseswiththeSJF

schedulingalgorithm?

c.TheSJFalgorithmissupposedtoimproveperformance,butnoticethatwe

chosetorunprocessPlattime0becausewedidnotknowthattwoshorter

processeswouldarrivesoon.Computewhattheaverageturnaroundtimewillbe

iftheCPUisleftidleforthefirst1unitandthenSJFschedulingisused.

RememberthatprocessesPlandP2arewaitingduringthisidletime,sotheir

waitingtimemayincrease.Thisalgorithmcouldbeknownasfuture-knowledge

scheduling.

答：

a.((8-0)+(12-0.4)+(13-1.0))/3=10.53;

b.((8-0)+(13-0.4)+(9-l.0))/3=9.53;

c.((14-0)+(6-0.4)+(2-l.0))/3=6.87;

第六版（理发师）第4题:

TheSleeping-BarberProblem.Abarbershopconsistsofawaitingroomwithn

chairsandthebarberroomcontainingthebarberchair.Ifthereareno

customerstobeserved,thebarbergoestosleep.Ifacustomerentersthe

barbershopandallchairsareoccupied,thenthecustomerleavestheshop.If

thebarberisbusybutchairsareavailable,thenthecustomersitsinoneof

thefreechairs.Ifthebarberisasleep,thecustomerwakesupthebarber.

Writeaprogramtocoordinatethebarberandthecustomers.

答：作业ch7-第四题

理发师和顾客同步，理发师必须由顾客唤醒，理发师给一个顾客理发完，要让理发完的

顾客退出，让等待顾客进入，顾客互斥的占用n个位置

〃共享变量

semaphoreScuthair,Snumchair;//Scuthair制约理发师，Snumchair制约顾客

Scuthair=O;Snumchair=O;

barber:

do{

wait(Scuthair)；〃检查是否有顾客，无就睡眠

给某个顾客理发

signa](Snumchair);〃让理发完的顾客退出1,让等待的一个顾客进入

}while(1);

Customeri:

wait(Snumchair);〃申请占用椅子signal(Scuthair);〃给理发师发一个信号

坐在椅子上等着理发〃共享变量

semaphoreScuthair,Mutexchair;//Scuthair给理发师，Mutexchair制约顾客对椅

子的互斥占领

intnumber=0;〃顾客的共享变量，记录已经有的顾客数

Scuthair=O;Mutexchair=1;

Customeri:

wait(Mutexchair);〃申请对共享变量number的操作(申请占用椅子)if(number==

n-l){signal(Mutexchair);exit;}

number=number+1;

signal(Scuthair)；〃给理发师发一个信号

signal(Mutexchair);

等待理发,，

理发完毕,，

wait(Mutexchair)；〃申请对共享变量number的操作

number=number-1;

signal(Mutexchair);

离开理发店

barber:

do{

wait(Scuthair);〃检查是否有顾客，无，就睡眠

给某个顾客理发

}while(1);

第七章

第七版7.5Inarealcomputersystem,neithertheresourcesavailablenorthe

demandsofprocessesforresourcesareconsistentoverlongperiods(months).

Resourcesbreakorarereplaced,newprocessescomeandgo,newresourcesare

boughtandaddedtothesystem.IfdeadlockiscontrolledbythebankerJs

algorithm,whichofthefollowingchangescanbemadesafely(without

introducingthepossibilityofdeadlock),andunderwhatcircumstances?一个

真实的计算机系统中，无论是可用的资源还是进程命令对资源的要求都会持续很长•段时

间(儿个月)。资源损坏或被替换，新的进程进入和离开系统，新的资源会被购买和添加

到系统中。如果用银行家算法控制死锁，下面哪些变化是安全的(不会导致可能的死

锁)，并且在什么情况下发生？)

a.IncreaseAvailable（newresourcesadded）增加可用资源（新的资源被添加到系

统）b.DecreaseAvailable（resourcepermanentlyremovedfromsystem）减少可用

资源（资

源被从系统中永久性地移出）

c.IncreaseMaxforoneprocess（theprocessneedsmoreresourcesthan

allowed,

itmaywantmore）增加一个进程的Max（进程需要更多的资源，超过所允许给予的资

源）d.DecreaseMaxforoneprocess（theprocessdecidesitdoesnotneed

thatmany

resources）减少一个进程的Max（进程不再需要那么多资源）

e.Increasethenumberofprocesses增加进程的数量

f.Decreasethenumberofprocesses减少进程的数量答：作业ch8-第二题

第七版7.7Considerasystemconsistingofmresourcesofthesametype,

beingsharedbynprocesses.Resourcescanberequestedandreleasedby

processesonlyoneatatime.Showthatthesystemisdeadlock-freeifthe

followingtwoconditionshold:（假设一个系统有m个资源被n个进程共享，进程每次

只请求和释放•个资源。证明只要系统符合下面两个条件，就不会发生死锁）

a.Themaximumneedofeachprocessisbetween1andmresources（每个进程需

要资源的最大值在1到m之间）

b.Thesumofallmaximumneedsislessthanm+n（所有进程需要资源的最大值

的和小于m+n）

答：作业ch8-第三题

使用Section7.6.2的术语,可以有：

a.n

ilMaxi<m+n

b.Maxi1foralli

Proof:Needi=Maxi—Allocation!

Ifthereexistsadeadlockstatethen:

c.n

ilAllocationi二m

Usea.toget:

Usec.toget:Needi+Allocationi=Maxi<m+nNeedi+m<m+n

n

iIRewritetoget:Needi

这意味着存在一个Pi的进程，其Needi=0.如果Maxi>=l,那么Pi进程至少有一个资源

可以释放。从而系统就不会进入死锁状态。

第七版7.11

AllocationMrt.vAvailable

ABCDABCDABCD

p0

p001200121520

110001750

p2

13542356

p3

P06320652

400140656

Considerthefollowingsnapshotofasystem:

Answerthefollowingquestionsusingthebanker'salgorithm:(使用银行家算

法回答下面的问题)

a.WhatisthecontentofthematrixNeed?(Need矩阵的内容是怎样的？)b.Is

thesysteminasafestate?(系统是否处于安全状态？)

c.IfarequestfromprocessPlarrivesfor(0,4,2,0),cantherequestbe

grantedimmediately?(如果从进程Pl发出•个请求(0420),这个请求能否被满

足？)答：作业ch8-第四题a.Need矩阵的内容是P0(0000)P1(0750)P2

(1002)P3(0020)P4(0640)o

b.系统处于安全状态，因为Available矩阵等于(1520),进程P0和P3都可以运

行，当进程P3运行完时，它释放它的资源，而允许其它进程运行。

c.可以被满足，满足以后，Available矩阵等于(1100),当以次序P0,P2,P3,

Pl,P4运行时候，可以完成运行。

第八章

第七版&3Givenmemorypartitionsof100K,500K,200K,300K,and600K(in

order),howwouldeachoftheFirst-fit,Best-fit,andWorst-fitalgorithms

placeprocessesof212K,417K,112K,and426K(inorder)?Whichalgorithm

makesthemostefficientuseofmemory?(按顺序给出5个部分的内存，分别是

100KB,500KB,200KB,300KB和600KB,用first-fit,best-fit和worst-fit算法,能够怎

样按顺序分配进程212KB,417KB,112KB,426KB和426KB?哪个算法充分利用了内存空

间？)

答：作业ch9-第二题

(1)first-fit,best-fit和worst-fit算法分配进程如下：

First-fit:

212Kisputin500Kpartition

417Kisputin600Kpartition

112Kisputin288Kpartition(newpartition288K=500K—212K)

426Kmustwait

Best-fit:

212Kisputin300Kpartition

417Kisputin500Kpartition

112Kisputin200Kpartition

426Kisputin600Kpartition

Worst-fit:

212Kisputin600Kpartition

417Kisputin500Kpartition

112Kisputin388Kpartition

426Kmustwait

（2）Best-fit算法充分利用了内存空间。

第七版&12Considerthefollowingsegmenttable:

SegmentBaseLength

0219600

1230014

290100

31327580

4195296

Whatarethephysicaladdressesforthefollowinglogicaladdresses?

a.0,430

b.1,10

c.2,500

d.3,400

e.4,112

答：作业ch9-第四题

a.430<600,219+430=649；

b.10<14,2300+10=2310；

c.500>100,illegal；

d.400<580,1327+400=1727；

e.112>96,illegal

第九章

9.13•个页面置换算法应使发生页错误的次数最小化。怎样才能通过将使用频率高的

页平均分配到整个内存而不只是竞争少数几个页帧页来达到这种最小化。可以对每个页帧

设置一个计数器来记录与此帧相关的页数。那么当置换一个页时，就可以查找计数器值最

小的页帧

Answer:

a.定义一个页面置换算法解决问题:

【•计数器初始值一0；

II.计数器值增加一一^每当新的一页与此帧相关联；

in.计数器值减少——每当与此帧相关联的一个页不再需要；

iv.怎样选择要被置换的页——找到带有最小计数器值的帧。使用先进先出算法解

除其关系

b.14个页错误

C.11个页错误

9.15颠簸的原因是什么？系统怎样检测颠簸？一旦系统检测到颠簸，系统怎样做来消

除这个问题？

Answer:

分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。该系统可通

过对比多道程序的程度来估计CPU利用率的程度，以此来检测颠簸。降低多道程序的程度

可以消除颠簸。

第十章

第六版10.11Considerthefollowingpagereferencestring:

1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.

Howmanypagefaultswouldoccurforthefollowingreplacementalgorithms,

assumingone,two,three,four,five,six,orsevenframes?Rememberallframes

areinitiallyempty,soyourfirstuniquepageswillallcostonefaulteach.

LRUreplacement

FIFOreplacement

Optimalreplacement

Answer:

NumberofframesLRUFIFOOptimal

1202020

2181815

3151611

410148

58107

67107

7777

第十二章

12.1Considerafilecurrentlyconsistingof100blocks.Assumethatthe

filecontrolblock(andtheindexblock,inthecaseofindexedallocation)is

alreadyinmemory.Calculatehow

manydiskI/Ooperationsarerequiredforcontiguous,linked,andindexed

(single-level)

allocationstrategies,if,foroneblock,thefollowingconditionshold.In

thecontiguousallocationcase,assumethatthereisnoroomtogrowinthe

beginning,butthereisroomtogrowintheend.Assumethattheblock

informationtobeaddedisstoredinmemory.

Theblockisaddedatthebeginning.

b.Theblockisaddedinthemiddle.

c.Theblockisaddedattheend.

d.Theblockisremovedfromthebeginning.

Theblockisremovedfromthemiddle.

ContiguousLinkedIndexed

a.20111

b.101521

c.131

d.19810

e.9852