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

操作系统课后重点习题整理第一章1.17 D e f i n e th e e s s e n ti a l p r o p e r ti e s o f th e f o l l o w i n g typ e s o f o p e r a ti n gs ys te m s:列出卜列操作系统的基本特点：a.B a tc h 批处理b.In te r a c ti v e 交互式c.T i m e s h a r i n g 分时d.R e a l ti m e 实时e.N e tw o r k 网络g.D i s tr i b u te d 分布式f.并行式h.集群式i.手持式An s w e r:作 业 c h i-第四题（第六版答案）a.B a tc h相似需求的J 2 b 分批、成组的在计算机上执行，J o b 由操作员或自动J o b 程序装置装载；可以通过采用 b u f f e r i n g,o f f-l i n e o p e r a ti o n,s p o o l i n g,m u l ti p r o g r a m m i n g 等技术使C P U 和 I/O 不停忙来提高性能批处理适合于需要极少用户交互的J o b ob.In te r a c ti v e由许多短交易组成，下一次交易的结果可能不可预知需要响应时间短c.T i m e s h a r i n g使用C P U 调度和多道程序提供对系统的经济交互式使用，C P U 快速地在用户之间切换一般从终端读取控制，输出立即打印到屏幕d.R e a l ti m e在专门系统中使用，从传感器读取信息，必须在规定时间内作出响应以确保正确的执行e.N e tw o r k在通用os上添加联网、通信功能远程过程调用文件共享f.D i s tr i b u te d具有联网、通信功能提供远程过程调用提供多处理机的统一调度调度统i的存储管理分布式文件系统第二章第六版 2.3 Wh a t a r e th e d i f f e r e n c e s b e tw e e n a tr a p a n d a n i n te r r u p t?Wh a t i sth e u s e o f e a c h f u n c ti o n?答:作业c h 2-第二题（第六版答案）An i n te r r u p t是硬件产生的系统内的流的改变A tr a p 是软件产生的“中断”。i n te r r u p t可以被I/O 用来产生完成的信号，从而避免C P U 对设备的轮询A tr a p 可以用来调用O S 的例程或者捕获算术错误第七版2.3 讨论向操作系统传递参数的三个主要的方法。1 .通过寄存器来传递参数2 .寄存器传递参数块的首地址3 .参数通过程序存放或压进堆栈中，并通过操作系统弹出堆栈。第三章第七版3.1论述短期，中期和长期调度之间的区别.a.短期调度:在内存作业中选择就绪执行的作业,并为他们分配CPU,b.中期调度:作为一种中等程度的调度程序，尤其被用于分时系统，个交换方案的实施，将部分运行程序移出内存，之后，从中断处继续执行。c.长期调度（作业调度程序）：确定哪些作 也调入内存以执行.它们主要的不同之处是它们的执行的频率。短期调度必须经常调用一个新进程，由于在系统中，长期调度处理移动的作业时，并不频繁被调用，可能在进程离开系统时才被唤起。第七版3.2问：描述一下内核在两个进程间进行上下文功换的动作.答：总的来说，操作系统必须保存正在运行的进程的状态，恢复进程的状态。保存进程的状态主要包括CPU寄存器的值以及内存分配，上下文切换还必须执行一些确切体系结构的操作，包括刷新数据和指令缓存。（书中答案）进程关联是由进程的PCB来表示的，它包括CPU寄存器的值和内存管理信息等。当发生上下文切换时，内核会将旧进程的关联状态保存在其PCB中，然后装入经调度要执行的新进程的已保存的关联状态。第五章第七版 5.4 Consider the following set of processes,with the length of theCPU-burst time given in milliseconds:（考虑下列进程集,进程占用的CPU区间长度以毫秒来计算：）错误！未指定书签。The processes are assumed to have arrived in the order P l,P 2,P 3,P 4,P 5,all at time 0.（假设在时刻0以进程Pl,P2,P3,P4,P5的顺序到达。）a.Draw four Gantt charts illustrating the execution of these processesusing FCFS,SJF,a nonpreemptive priority（a smaller priority number implies ahigher priority）,and RR（quantum=1）scheduling.（画出 4 个 Gantt 图分别演示用FCFS、SJF、非抢占优先级（数字小代表优先级高）和RR（时间片=1）算法调度时进程的执行过程。）b.What is the turnaround time of each process for each of the schedulingalgorithms in part a?（在a里每个进程在每种调度算法下的周转时间是多少？）c.W h a t i s t h e w a i t i n g t i m e o f e a c h p r o c e s s f o r e a c h o f t h e s c h e d u li n ga lg o r i t h m s i n p a r t a?(在a里每个进程在每种调度算法下的等待时间是多少？)d.W h i c h o f t h e s c h e d u le s i n p a r t a r e s u lt s i n t h e m i n i m a l a v e r a g e w a i t i n gt i m e (o v e r a ll p r o c e s s e s)?(在a里哪一种调度算法的平均等待时间对所有进程而言最小？)答：作业c h 6-第三题第六章第六版 6.4 S u ppo s e t h a t t h e f o l l o w i n g pr o c e s s e s a r r i v e f o r e x e c u t i o n a t t h et i m e s i n d i c a t e d.Ea c h pr o c e s s w i l l r u n t h e l i s t e d a m o u n t o f t i m e.I n a n s w e r i n gt h e qu e s t i o n s,u s e n o n pr e e m pt i v e s c h e d u l i n g a n d b a s e a l l d e c i s i o n s o n t h ei n f o r m a t i o n y o u h a v e a t t h e t i m e t h e d e c i s i o n m u s t b e m a d e.ProcessArriTimoPl0.08Pl0.44p31.01a.W h a t i s t h e a v e r a g e t u r n a r o u n d t i m e f o r t h e s e pr o c e s s e s w i t h t h e FC FSs c h e d u l i n g a l g o r i t h m?b.W h a t i s t h e a v e r a g e t u r n a r o u n d t i m e f o r t h e s e pr o c e s s e s w i t h t h e S J Fs c h e d u l i n g a l g o r i t h m?c.T h e S J F a l g o r i t h m i s s u ppo s e d t o i m pr o v e pe r f o r m a n c e,b u t n o t i c e t h a t w ec h o s e t o r u n pr o c e s s P l a t t i m e 0 b e c a u s e w e d i d n o t k n o w t h a t t w o s h o r t e rpr o c e s s e s w o u l d a r r i v e s o o n.C o m pu t e w h a t t h e a v e r a g e t u r n a r o u n d t i m e w i l l b ei f t h e C P U i s l e f t i d l e f o r t h e f i r s t 1 u n i t a n d t h e n S J F s c h e d u l i n g i s u s e d.R e m e m b e r t h a t pr o c e s s e s P l a n d P 2 a r e w a i t i n g d u r i n g t h i s i d l e t i m e,s o t h e i rw a i t i n g t i m e m a y i n c r e a s e.T h i s a l g o r i t h m c o u l d b e k n o w n a s f u t u r e-k n o w l e d g es c h e d u l i n g.答：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题:T h e S l e e pi n g-B a r b e r P r o b l e m.A b a r b e r s h o p c o n s i s t s o f a w a i t i n g r o o m w i t h nc h a i r s a n d t h e b a r b e r r o o m c o n t a i n i n g t h e b a r b e r c h a i r.I f t h e r e a r e n oc u s t o m e r s t o b e s e r v e d,t h e b a r b e r g o e s t o s l e e p.I f a c u s t o m e r e n t e r s t h eb a r b e r s h o p a n d a l l c h a i r s a r e o c c u pi e d,t h e n t h e c u s t o m e r l e a v e s t h e s h o p.I ft h e b a r b e r i s b u s y b u t c h a i r s a r e a v a i l a b l e,t h e n t h e c u s t o m e r s i t s i n o n e o ft h e f r e e c h a i r s.I f t h e b a r b e r i s a s l e e p,t h e c u s t o m e r w a k e s u p t h e b a r b e r.W r i t e a pr o g r a m t o c o o r d i n a t e t h e b a r b e r a n d t h e c u s t o m e r s.答：作 业 c h 7-第四题理发师和顾客同步，理发师必须由顾客唤醒，理发师给一个顾客理发完，要让理发完的顾客退出，让等待顾客进入，顾客互斥的占用n个位置共享变量s e m a ph o r e S c u t h a i r,S n u m c h a i r;/S c u t h a i r 制约理发师，S n u m c h a i r 制约顾客S c u t h a i r=O;S n u m c h a i r=O;b a r b e r:d o w a i t (S c u t h a i r)；检查是否有顾客，无就睡眠给某个顾客理发s i g n a (S n u m c h a i r);让理发完的顾客退出 1,让等待的一个顾客进入 w h i l e (1);C u s t o m e r i:w a i t (S n u m c h a i r);申请占用椅子s i g n a l (S c u t h a i r);给理发师发一个信号坐在椅子上等着理发共享变量s e m a ph o r e S c u t h a i r,M u t e x c h a i r;/S c u t h a i r 给理发师，M u t e x c h a i r 制约顾客对椅子的互斥占领i n t n u m b e r =0;顾客的共享变量，记录已经有的顾客数S c u t h a i r=O;M u t e x c h a i r =1;C u s t o m e r i:w a i t (M u t e x c h a i r);申请对共享变量n u m b e r 的 操 作(申 请 占 用 椅 子)i f (n u m b e r=n-l)s i g n a l(M u t e x c h a i r);e x i t;n u m b e r =n u m b e r +1;s i g n a l (S c u t h a i r)；给理发师发一个信号s i g n a l(M u t e x c h a i r);等待理发,，理发完毕,，w a i t (M u t e x c h a i r)；申请对共享变量n u m b e r 的操作n u m b e r =n u m b e r -1;s i g n a l(M u t e x c h a i r);离开理发店b a r b e r:d o w a i t (S c u t h a i r);检查是否有顾客，无，就睡眠给某个顾客理发 w h i l e (1);第七章第七版 7.5 I n a r e a l c o m pu t e r s y s t e m,n e i t h e r t h e r e s o u r c e s a v a i l a b l e n o r t h ed e m a n d s o f pr o c e s s e s f o r r e s o u r c e s a r e c o n s i s t e n t o v e r l o n g pe r i o d s (m o n t h s).R e s o u r c e s b r e a k o r a r e r e pl a c e d,n e w pr o c e s s e s c o m e a n d g o,n e w r e s o u r c e s a r eb o u g h t a n d a d d e d t o t h e s y s t e m.I f d e a d l o c k i s c o n t r o l l e d b y t h e b a n k e rJ sa l g o r i t h m,w h i c h o f t h e f o l l o w i n g c h a n g e s c a n b e m a d e s a f e l y (w i t h o u ti n t r o d u c i n g t h e po s s i b i l i t y o f d e a d l o c k),a n d u n d e r w h a t c i r c u m s t a n c e s?一个真实的计算机系统中，无论是可用的资源还是进程命令对资源的要求都会持续很长段时间(儿 个 月)。资源损坏或被替换，新的进程进入和离开系统，新的资源会被购买和添加到系统中。如果用银行家算法控制死锁，下面哪些变化是安全的(不会导致可能的死锁)，并且在什么情况下发生？)a.I n c r e a s e A v a i l a b l e （n e w r e s o u r c e s a d d e d）增加可用资源（新的资源被添加到系统）b.D e c r e a s e A v a i l a b l e （r e s o u r c e pe r m a n e n t l y r e m o v e d f r o m s y s t e m）减少可用资 源（资源被从系统中永久性地移出）c.I n c r e a s e M a x f o r o n e pr o c e s s （t h e pr o c e s s n e e d s m o r e r e s o u r c e s t h a na l l o w e d,i t m a y w a n t m o r e）增加一个进程的M a x （进程需要更多的资源，超过所允许给予的资源）d.D e c r e a s e M a x f o r o n e pr o c e s s （t h e pr o c e s s d e c i d e s i t d o e s n o t n e e dt h a t m a n yr e s o u r c e s）减少一个进程的M a x （进程不再需要那么多资源）e.I n c r e a s e t h e n u m b e r o f pr o c e s s e s 增加进程的数量f.D e c r e a s e t h e n u m b e r o f pr o c e s s e s 减少进程的数量答：作 业 c h 8-第二题第七版 7.7 C o n s i d e r a s y s t e m c o n s i s t i n g o f m r e s o u r c e s o f t h e s a m e t y pe,b e i n g s h a r e d b y n pr o c e s s e s.R e s o u r c e s c a n b e r e qu e s t e d a n d r e l e a s e d b ypr o c e s s e s o n l y o n e a t a t i m e.S h o w t h a t t h e s y s t e m i s d e a d l o c k-f r e e i f t h ef o l l o w i n g t w o c o n d i t i o n s h o l d:（假设一个系统有m个资源被n个进程共享，进程每次只 请 求 和 释 放 个资源。证明只要系统符合下面两个条件，就不会发生死锁）a.Th e m a xi m u m n eed o f ea c h p r o c es s i s bet ween 1 a n d m r es o u r c es （每个进程需要资源的最大值在1 到 m之间）b.Th e s u m o f a l l m a xi m u m n eed s i s l es s t h a n m +n （所有进程需要资源的最大值的和小于m+n）答：作 业 c h 8-第三题使 用 Sec t i o n 7.6.2 的术语,可以有：a.ni l Ma xi m+nb.Ma xi 1 f o r a l l iPr o o f:Need i =Ma xi A l l o c a t i o n!If t h er e exi s t s a d ea d l o c k s t a t e t h en:c.ni l A l l o c a t i o n i 二 mUs e a.t o g et:Us e c.t o g et:Need i+A l l o c a t i o n i =Ma xi m +n Need i+m =l,那么Pi 进程至少有一个资源可以释放。从而系统就不会进入死锁状态。第七版7.1101234ppppPAllocationMrt.vAvailableA B C DA B C DA B C D001200 12152010001750135423560632065200140 6 5 6Co n s i d er t h e f o l l o wi n g s n a p s h o t o f a s ys t em:A n s wer t h e f o l l o wi n g q u es t i o n s u s i n g t h e ba n k er s a l g o r i t h m:(使用银行家算法回答下面的问题)a.W h a t i s t h e c o n t en t o f t h e m a t r i x Need?(Need 矩阵的内容是怎样的？)b.Ist h e s ys t em i n a s a f e s t a t e?(系统是否处于安全状态？)c.If a r eq u es t f r o m p r o c es s Pl a r r i ves f o r (0,4,2,0),c a n t h e r eq u es t beg r a n t ed i m m ed i a t el y?(如果从进程P l 发 出 个 请 求(0 4 2 0),这个请求能否被满足？)答：作 业 c h 8-第四题a.Need 矩阵的内容是P0 (0 0 0 0)P1(0 7 5 0)P2(1 0 0 2)P3 (0 0 2 0)P4 (0 6 4 0)ob.系统处于安全状态，因为A va i l a bl e矩 阵 等 于(1 5 2 0),进 程 P0 和 P3 都可以运行，当进程P3 运行完时，它释放它的资源，而允许其它进程运行。c.可以被满足，满足以后，A va i l a bl e矩 阵 等 于(1 1 0 0),当以次序P0,P2,P3,Pl ,P4 运行时候，可以完成运行。第八章第七版&3 G i ven m em o r y p a r t i t i o n s o f 10 0 K,5 0 0 K,20 0 K,3 0 0 K,a n d 6 0 0 K (i no r d er),h o w wo u l d ea c h o f t h e Fi r s t-f i t,B es t-f i t,a n d W o r s t-f i t a l g o r i t h m sp l a c e p r o c es s es o f 212K,4 17 K,112K,a n d 4 26 K (i n o r d er)?W h i c h a l g o r i t h mm a k es t h e m o s t ef f i c i en t u s e o f m em o r y?(按顺序给出5个部分的内存，分别是10 0 K B,5 0 0 K B,20 0 K B,3 0 0 K B 和 6 0 0 K B,用 f i r s t-f i t,bes t-f i t 和 wo r s t-f i t 算法,能够怎样按顺序分配进程212K B,4 17 K B,112K B,4 26 K B 和 4 26 K B?哪个算法充分利用了内存空间？)答：作业c h 9-第二题(1)f i r s t-f i t,bes t-f i t 和 wo r s t-f i t 算法分配进程如下：Fi r s t-f i t:212K i s p u t i n 5 0 0 K p a r t i t i o n4 17 K i s p u t i n 6 0 0 K p a r t i t i o n112K i s p u t i n 28 8 K p a r t i t i o n (n ew p a r t i t i o n 28 8 K =5 0 0 K 212K)4 26 K m u s t wa i tB es t-f i t:212K i s p u t i n 3 0 0 K p a r t i t i o n4 17 K i s p u t i n 5 0 0 K p a r t i t i o n112K i s p u t i n 20 0 K p a r t i t i o n4 26 K i s p u t i n 6 0 0 K p a r t i t i o nW o r s t-f i t:212K i s p u t i n 6 0 0 K p a r t i t i o n4 17 K i s p u t i n 5 0 0 K p a r t i t i o n112K i s p u t i n 3 8 8 K p a r t i t i o n4 26 K m u s t wa i t（2）B es t-f i t 算法充分利用了内存空间。第七版&12 Co n s i d er t h e f o l l o wi n g s eg m en t t a bl e:SegmentBaseLength02196001230014290100313275804195296W h a t a r e t h e p h ys i c a l a d d r es s es f o r t h e f o l l o wi n g l o g i c a l a d d r es s es?a.0,4 3 0b.1,10c.2,5 0 0d.3,4 0 0e.4,112答：作 业 c h 9-第四题a.4 3 0 6 0 0,219+4 3 0 =6 4 9 ；b.10 10 0,i l l eg a l ；d.4 0 0 9 6,i l l eg a l第九章9.13 个页面置换算法应使发生页错误的次数最小化。怎样才能通过将使用频率高的页平均分配到整个内存而不只是竞争少数几个页帧页来达到这种最小化。可以对每个页帧设置一个计数器来记录与此帧相关的页数。那么当置换一个页时，就可以查找计数器值最小的页帧A n s wer:a.定义一个页面置换算法解决问题:【计数器初始值一0；II.计数器值增加一一 每当新的一页与此帧相关联；i n.计数器值减少每当与此帧相关联的一个页不再需要；i v.怎样选择要被置换的页找到带有最小计数器值的帧。使用先进先出算法解除其关系b.1 4 个页错误C.1 1 个页错误9.1 5 颠簸的原因是什么？系统怎样检测颠簸？一旦系统检测到颠簸，系统怎样做来消除这个问题？A nswer:分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。该系统可通过对比多道程序的程度来估计C P U 利用率的程度，以此来检测颠簸。降低多道程序的程度可以消除颠簸。第十章第六版 1 0.1 1 C onsider the following page reference string:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.H ow many page faults would occur for the following replacement algorithms,assumingone,two,three,four,five,six,or seven frames?Remember all framesare initially empty,so your first unique pages will all cost one fault each.L RU replacementF I F O replacementO ptimal replacementAnswer:Number of framesLRUFIFOOptimal12020202181815315161141014858107671077777第十二章1 2.1 C onsider a file currently consisting of 1 0 0 blocks.A ssume that thefile control block(and the index block,in the case of indexed allocation)isalready in memory.C alculate howmany disk I/O operations are required for contiguous,linked,and indexed(single-level)allocation strategies,if,for one block,the following conditions hold.I nthe contiguousallocation case,assume that there is no room to grow in thebeginning,but there is room to grow in the end.A ssume that the blockinformation to be added is stored in memory.T he block is added at the beginning.b.T he block is added in the middle.c.T he block is added at the end.d.T he block is removed from the beginning.T he block is removed from the middle.ContiguousLinkedIndexeda.20111b.101521c.131d.19810e.98520f.01000f.The block is removed from the end.12.2 Suppose that a disk drive has 5000 cylinders,numbered 0 to 4999.Thedrive is currentlyserving a request at cylinder 143,and the previous request was at cylinder125.The queueof pending requests,in FIFO order,is86,1470,913,1774,948,1509,1022,1750,130Starting from the current head position,what is the total distance(incylinders)thatthe disk arm moves to satisfy all the pending requests,for each of thefollowing diskschedulingalgorithms?（假设一个错哦盘驱动器有5000个柱面，从 0 到 4999,驱动器正在为柱面143的一个请求提供服务，目前面的一个服务请求是在柱面125.按 FIFO顺序，即将到来的请求队列是86,1470,913,1774,948,1509,1022,1750,130从现在磁头位置开始，按照下面的磁盘调度算法，要满足队列中即将到来的请求要求磁头总的移动距离（按柱面数计）是多少？）a.FCFSb.SSTFc.SCANd.LOOKe.C-SCANa.FCFS 的调度是 143,86,1470,913,1774,948,1509,1022,1750,130.总寻求距离是7081.b.SSTF 的调度是 143,130,86,913,948,1022,1470,1509,1750,1774.总寻求距离是1745.c.SCAN 的调度是 143,913,948,1022,1470,1509,1750,1774,4999,130,86.总寻求距离是9769.d.LOOK 的调度是 143,913,948,1022,1470,1509,1750,1774,130,86.总寻求距离是3319.e.C-SCAN 的调度是 143,913,948,1022,1470,1509,1750,1774,4999,86,130.总寻求距离是9813.f.C-LOOK 的调度是 143,913,948,1022,1470,1509,1750,1774,86,130.总寻求距离是3363.