操作系统第五版费祥林-课后习题答案解析参考.doc

第一章 操作系统概论1、有一台计算机,具有IMB 内存,操作系统占用0B ，每个用户进程各占20KB 。如果用户进程等待I/ 得时间为80 % ,若增加MB内存，则CPU 得利用率提高多少?答：设每个进程等待I/O 得百分比为P ,则n 个进程同时等待刀O 得概率就是n ,当 个进程同时等待I/O 期间PU 就是空闲得,故PU 得利用率为1Pn。由题意可知，除去操作系统,内存还能容纳 个用户进程,由于每个用户进程等待I得时间为0% , 故:CPU利用率=l-(8）4 = 0、59 若再增加1 内存，系统中可同时运行9 个用户进程,此时:cu利用率=l-（8） = 0、87故增加MB 内存使CP 得利用率提高了47 ： 7 /59 =147 % 47 %-100 % = 47 %2一个计算机系统，有一台输入机与一台打印机,现有两道程序投入运行，且程序A 先开始做,程序B 后开始运行.程序A 得运行轨迹为:计算50ms 、打印100s 、再计算0ms 、打印00 ,结束。程序B 得运行轨迹为：计算50m 、输入8ms 、再计算1m ,结束。试说明(1 )两道程序运行时,有无空闲等待？若有,在哪段时间内等待？为什么会等待?（ 2 ）程序 、B 有无等待CP 得情况？若有，指出发生等待得时刻。答:画出两道程序并发执行图如下:(1）两道程序运行期间,CPU存在空闲等待，时间为00至10m 之间(见图中有色部分)（2)程序A 无等待现象，但程序B 有等待。程序B有等待时间段为180至00s间(见图中有色部分）3 设有三道程序，按A、B、C优先次序运行，其内部计算与U操作时间由图给出. 试画出按多道运行得时间关系图(忽略调度执行时间）。完成三道程序共花多少时间?比单道运行节省了多少时间？若处理器调度程序每次进行程序转换化时l , 试画出各程序状态转换得时间关系图。答：1 ）忽略调度执行时间，多道运行方式（抢占式）：？抢占式共用去9s ,单道完成需要20ms ，节省70ms 。忽略调度执行时间，多道运行方式（非抢占式)： 非抢占式共用去80 ，单道完成需要26m，节省80m。2 ）调度执行时间1ms ，多道运行方式（抢占式）： 调度执行时间Tn,多道运行方式（非抢占式）: 4在单CPU 与两台 I/O（I1 ， 12）设备得多道程序设计环境下，同时投入三个作业运行。它们得执行轨迹如下:Jl ： I2 （ 30m)、CPU （ ）、1( 30ms )、CPU( 10ms ）、I2( 20 ) b2 ：1 ( 20ms）、CPU （20ms)、I ( 0 m）JOb3: CPU( 30ms ）、（ 20m ）、CU （ 0ms )、I1( 10ms ） 如果CPU、I 与I2都能并行工作,优先级从高到低为ol 、Jo 与J3,优先级高得作业可以抢占优先级低得作业得CPU,但不抢占I1与I。试求:( l）每个作业从投入到完成分别所需得时间。(2 ）从投入到完成P得利用率。(3 )I设备利用率。答：画出三个作业并行工作图如下（图中着色部分为作业等待时间): ,（ 1)Jb1 从投入到运行完成需110ms ， Job2 从投入到运行完成需9s ， ob3 从投入到运行完成需11ms、 CPU 空闲时间段为：ms 至7ms , 0ms至0ms , 1ms至ms .所以U 利用率为(11030）/1 72、7 .设备I1空闲时间段为：2m至40ms，90m至100ms，故I1得利用率为 （1103)l10 72 、 7 。 设备I2 空闲时间段为：30ms 至50ms,故得利用率为(11020）/ 10 81、8 。 5 在单CPU 与两台/O（ I1 ， 1 )设备得多道程序设计环境下，同时投入三个作业运行.它们得执行轨迹如下:Jl： I （ 30s )、CPU（ 0rns )、I1 （30ms ）、CP （0ms ）Jb2 : I1 (20ms )、PU （ 20m)、I( 40m ） Jb : CPU ( 0ms ）、I (20ms )如果CU 、I1与都能并行工作,优先级从高到低为Jb1 、Job2与Job3 ,优先级高得作业可以抢占优先级低得作业得CU.试求：( ）每个作业从投入到完成分别所需得时间 (）每个作业投入到完成P 得利用率。 (3 ）I/0设备利用率. 答：画出三个作业并行工作图如下（图中着色部分为作业等待时间）: （1) Job1从投入到运行完成需80m ， Jo2 从投入到运行完成需9 , ob3 从投入到运行完成需90ms 。( 2 ) CP 空闲时间段为：60ms 至70ms ，80ms至9ms。所以CPU利用率为（ 9020） / 90 =77、78 。（）设备I 空闲时间段为：20ms 至ms ，故I1 得利用率为（902） 9 =77 、 8 。设备I2 空闲时间段为：30m 至50ms ，故I2 得利用率为（90- ) / 907、78 。6 若内存中有3 道程序 、B、，它们按 、B 、C 优先次序运行。各程序得计算轨迹为：计算（20 ）、I/O( 30 )、计算（10)：计算（0 ）、I/O( 20 )、计算（0 ) c :计算（10 )、I/ (30 )、计算(20 ) 如果三道程序都使用相同设备进行IO（即程序用串行方式使用设备，调度开销忽略不计)。试分别画出单道与多道运行得时间关系图.两种情况下，PU 得平均利用率各为多少？答：分别画出单道与多道运行得时间图( 1 ）单道运行时间关系图 单道总运行时间为0m 。U 利用率为(1080 ）/190= 57、9 单道运行时间关系图多道总运行时间为40m 。C利用率为（1030 ） / 140 =8、 7若内存中有3 道程序 、B 、 ，优先级从高到低为A、B与C ，它们单独运行时得CP与/O 占用时间为:如果三道程序同时并发执行，调度开销忽略不计，但优先级高得程序可中断优先级低得程序，优先级与/O 设备无关。试画出多道运行得时间关系图,并问最早与最迟结束得程序就是哪个？每道程序执行到结束分别用了多少时间？计算三个程序全部运算结束时得CU 利用率？答:画出三个作业并发执行得时间图： ( l ）最早结束得程序为B ,最后结束得程序为C .（ 2）程序 为25s .程序B 为220m 。程序 为10ms。 （ 3 ) CP利用率为（310 0 ) 0 = 1、3 有两个程序， 程序按顺序使用:( CPU）10秒、（设备甲）5 秒、（CPU)5秒、（设备乙）10 秒、(CP)10 秒。B程序按顺序使用：(设备甲）10 秒、(CU)10 秒、(设备乙）5 秒、（ CPU）5 秒、（设备乙）10 秒。在顺序环境下先执行A ,再执行B ，求出总得C 利用率为多少?答：程序A 执行了40 秒，其中PU 用了25 秒。程序B 执行了40秒,其中CP 用了15秒.两个程序共用了80秒,PU 化 40 秒.故CPU利用率为40/8 =5 。、在某计算机系统中,时钟中断处理程序每次执行得时间为2s（包括进程切换开销)。若时钟中断频率为60,试问C用于时钟中断处理得时间比率为多少？答：因时钟中断频率为6HZ ,所以,时钟周期为:l/ s = 503ms.在每个时钟周期中,CPU 花2s 执行中断任务。所以,CPU用于时钟中断处理得时间比率为：（50/3)=6/50 = %.第二章 处理器管理1、下列指令中哪些只能在核心态运行？（l)读时钟日期;(2）访管指令；(3）设时钟日期；(4)加载SW; （5)置特殊寄存器:（)改变存储器映象图;(7）启动IO指令.答:( 3 ） ，(4 ) ， （ 5) ， （6 ） ， （ 7 ) 、2 假设有一种低级调度算法就是让“最近使用处理器较少得进程”运行,试解释这种算法对“IO 繁重”型作业有利,但并不就是永远不受理“处理器繁重”型作业.答:因为I繁忙型作业忙于IO，所以它CPU 用得少,按调度策略能优先执行。同样原因一个进程等待CPU 足够久时,由于它就是“最近使用处理器较少得进程,就能被优先调度，故不会饥饿。并发进程之间有什么样得相互制约关系?下列日常生活中得活动就是属哪种制约关系：（1）踢足球，（2)吃自助餐，(3）图书馆借书,（）电视机生产流水线工序.答:并发进程之间得基本相互制约关系有互斥与同步两种。其中(1)、(3)为互斥问题.（）、（4）为同步问题。 在按动态优先数调度进程得系统中，每个进程得优先数需定时重新计算。在处理器不断地在进程之间交替得情况下,重新计算进程优先数得时间从何而来？答：许多操作系统重新计算进程得优先数在时钟中断处理例程中进行，由于中断就是随机碰到哪个进程，就插入哪个进程中运行处理程序,并把处理时间记在这个进程得账上.5 若后备作业队列中等待运行得同时有三个作业J1、J、3 ,已知它们各自得运行时间为a 、b 、c,且满足 bc就是什么算法？（ ）若abc就是什么算法答:（）就是先进先出算法。因为在就绪队列中得进程比在CPU 上运行得进程得优先数提高得快,故进程切换时,先进入就绪队列得进程优先权就越高。( ）就是后进先出算法.因为在就绪队列中得进程比在CPU 上运行得进程得优先权下降得快,故后进入就绪队列得进程此先进入得进程得优先权高。 18 有一个四道作业得操作系统，若在一段时间内先后到达6个作业，它们得提交与估计运行时间由下表给出： 系统采用SF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占.(l)分别给出6 个作业得执行时间序列、即开始执行时间、作业完成时间、作业周转时间。（)计算平均作业周转时间。答 说明:（ ) J2 到达时抢占J1 ；J3到达时抢占2 。 ( 2)但J4 到达时,因不满足JF ,故J4 不能被运行,J继续执行5分钟。 （ ）由于就是 道得作业系统，故后面作业不能进入主存而在后备队列等待，直到有作业结束. ( 4 )根据进程调度可抢占原则，J3 第一个做完。而这时J5 、6 均己进入后备队列，而J可进入主存。 ( 5）因 最短,故它第二个完成。这时6 方可进入主存.因6 最短,故它第三个完成。 ( 6)然后就是：J 、J2与J1( 7)T =( 155 + 5 20+ 55 + 15 2 ) /6 = 0 9、有一个具有两道作业得批处理系统，作业调度采用短作业优先得调度算法,进程调度采用以优先数为基础得抢占式调度算法，在下表所示得作业序列,作业优先数即为进程优先数，优先数越小优先级越高。（ 1 ）列出所有作业进入内存时间及结束时间。（2 ）计算平均周转时间。答：每个作业运行将经过两个阶段：作业调度（JF算法）与进程调度（优先数抢占式)。另外，批处理最多容纳2 道作业，更多得作业将在后备队列等待。（ ）10 : 0 ,作业 到达并投入运行。 ( 3 )0 ： 2 ，作业B 到达且优先权高于作业A ,故作业B 投入运行而作业 在就绪队列等待。 ( 4 ） 0： ,作业 到达,因内存中已有两道作业,故作业C 进入作业后备队列等待。（5 ) 1 : 50 ，作业B运行结束，作业D 到达，按SJF 短作业优先算法,作业D 被装入内存进入就绪队列。而由于作业A 得优先级高于作业D ，故作业投入运行 ( 6 ) 11: 10 ，作业A 运行结束,作业C 被调入内存，具作业c 得优先级高于作业D ,故作业C 投入运行。 （ 7 ） 1 : 0，作业c 运行结束，作业D 投入运行. ( )12 ： 0 ，作业D 运行结束。 各作业周转时间为:作业A 7，作业B 30，作业C 90，作业D 0。平均作业周转时间为0 分钟.20、某多道程序设计系统供用户使用得主存为100K ，磁带机2 台，打印机1 台。采用可变分区内存管理,采用静态方式分配外围设备,忽略用户作业O 时间。现有作业序列如下： 作业调度采用FS 策略,优先分配主存低地址区且不准移动已在主存得作业,在主存中得各作业平分CPU 时间.现求：（ )作业被调度得先后次序？（ 2 ）全部作业运行结束得时间？（ 3 ）作业平均周转时间为多少?(4 ）最大作业周转时间为多少? 答：（l ）作业调度选择得作业次序为:作业1 、作业 、作业 、作业2 与作业5、 （ ）全部作业运行结束得时间: 3 . （ 3 ）周转时间:作业1为30 分钟、作业2 为 分钟、作业3 为40 分钟、作业4 为0 分钟与作业5 为5 分钟。( 4)平均作业周转时间=44 分钟。 （ 5 ）最大作业周转时间为5 分钟. 分析：本题综合测试了作业调度、进程调度、及对外设得竞争、主存得竞争。 : oo 作业1 到达，占有资源并调入主存运行。8 ： 20 作业与3 同时到达,但作业2因分不到打印机，只能在后备队列等待.作业3 资源满足，可进主存运行，并与作业 平分CPU时间。8 : 30 作业1 在 : 30结束,释放磁带与打印机。但作业 仍不能执行，因不能移动而没有30KB 得空闲区，继续等待.作业4 在8 ： 30 到达，并进入主存执行,与作业3 分享CPU8: 3 作业5 到达,因分不到磁带打印机,只能在后备队列等待。 9:0 作业3 运行结束,释放磁带机。此时作业 得主存及打印机均可满足，投入运行.作业5到达时间晚，只能等待. ： 1 作业4运行结束,作业5 因分不到打印机,只能在后备队列继续等待。 9：15巧作业2 运行结束,作业5 投入运行. 9 : 30作业全部执行结束。1、某多道程序设计系统采用可变分区内存管理,供用户使用得主存为20 ,磁带机5 台。采用静态方式分配外围设备，且不能移动在主存中得作业,忽略用户作业I/O时间.现有作业序列如下：现求:( l ) FF 算法选中作业执行得次序及作业平均周转时间？( 2 ) SJF 算法选中作业执行得次序及作业平均周转时间？（进程调度也采用S ) 答:( 1 ） FO算法选中作业执行得次序为：A 、D、C 与 作业平均周转时间为63分钟 (2 ）SJF算法选中作业执行得次序为：、B 、D 、E与C 。作业平均周转时间为58分钟 详细说明：1.先来先服务算法。说明：（ ）8 ： 30 作业A到达并投入运行。注意它所占用得资源。( 2） 8: 50 作业 到达,资源满足进主存就绪队列等Cu 。（ 3 ） 9 ： 00 作业C 到达,主存与磁带机均不够，进后备作业队列等待。( 4 )9 : 05 作业 到达,磁带机不够,进后备作业队列等待。后备作业队列有 、D 。（ ） 9 :1作业A 运行结束,归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业 仍因主存不够而等在后备队列。这时作业E 也到达了，。也由于主存不够进入后备作业队列。此时作业D 因资源满足(主存磁带均满足）,进主存就绪队列等待。后备作业队列还有C 、。( 6 ) 9： 35 作业 运行结束,作业D 投入运行。这时作业C 因资源满足而调入主存进就绪队列等CPU.而作业E 因磁带机不够继续在后备作业队列等待。( ) :55作业D 运行结束,作业C投入运行。这时作业 因资源满足而调入主存进就绪队列等CP 。（ 8 ) 0：30作业C运行结束,、作业E 投入运行。( ） 1 :40 作业E运行结束.2。短作业优先算法。说明：（ 1) 8 ：0 作业 到达并投入运行。注意它所占用得资源。 (2 ）8 : 5 作业B到达,资源满足进主存就绪队列等CPU 。 （ ) ： 00 作业C 到达，主存与磁带机均不够，进后备作业队列等待。 （ 4) 9 :05 作业D 到达,磁带机不够,进后备作业队列等待。后备作业队列有、 、 （ 5 ) 9 ： 10 作业A运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩)。作业 投入运行。作业C 仍因主存不够而等在后备队列.这时作业 也到达了，虽然该作业最短,也由于主存不够进入后备作业队列此时作业D 因资源满足(主存磁带均满脚,进主存就绪队列等待。后备作业队列还有C 、。（6) 9 ： 35作业B 运行结束,作业D投入运行。这时作业与 资源均满足,但按SJF 应把作业 调入主存进就绪队列等CPU .而作业 因磁带机不够继续在后备作业队列等待。 （ 7 ) :55 作业D 运行结束,作业C 调入主存进就绪队列等CPU、( 8 ） 10 : 5 作业E 运行结束,作业C 投入运行（9 ） 10 :40 作业C 运行结束.上题中，若允许移动己在主存中得作业，其她条件不变，现求：（ l ）FIO算法选中作业执行得次序及作业平均周转时间?（ 2) SF 算法选中作业执行得次序及作业平均周转时间?答：FIF 算法选中作业执行得次序为:JF 算法选中作业执行得次序为：(l ） A 、B 、与.作业平均周转时间为58 分钟。（2 ） 、B 、E 、D与C。作业平均周转时间为56 分钟。与上题类同，详细说明略。 3、设计一个进程定时唤醒队列与定时唤醒处理程序:（ ）说明一个等待唤醒进程入队v 得过程。(2 )说明时钟中断时，定时唤醒处理程序得处理过程。（3 ）现有进程P1 要求20 秒后运行,经过40 秒后再次运行；P 要求25秒后运行；3 要求35秒后运行，经过35秒后再次运行;4要求60秒后运行。试建立相应得进程定时唤醒队列。答:组织如下得定时唤醒队列 。( l）当一个需定时唤醒得进程要入队时，根据它要唤醒得时间,被扦入队列得适当位置,注意，唤醒时间按增量方式存放。( ）每当时钟中断时，时钟中断例程判别把队列中得第一个进程得时间量减 ，直到该值为时唤醒进程工作。同时队列中下一个进程成为队列头。2、一个实时系统有 个周期性事件,周期分别为50 、100 、300 与25m .若假设其处理分别需要35 、20 、10 与Xms，则该系统可调度允许得X值最大为多少?实时任务可调度应满足: 35 /5 0/100 1/30X/50l X250(l28/）=20、06 6、75m第三章 同步、通讯与死锁、 有三个并发进程：R 负责从输入设备读入信息块，M 负责对信息块加工处理;P 负责打印输出信息块。今提供; ）一个缓冲区,可放置K个信息块；2 ）二个缓冲区，每个可放置K 个信息块； 试用信号量与、V 操作写出三个进程正确工作得流程。答：1 )a : array 0 , k-1 of item；sead: maPoe : = k ;smage ： semahre ： 0 ； srite : sepre: 0 ； rpt :iner : ; t ： ineger: =O ； wpr ：inege: =0 ；x ：itemcobg processreader; procs anager； roces wrir ； beggin gn LI ： reda mssageito ; 2 : ( smae ); L3 : (wnte ） ；P （ sra ） ;x:=ptr； x：=Bswrite；Brptr:=; mp：=(mtr+1）md k; wpr：=(t+） mod k；tr:=（ptr+1） modk; anag themessge i x; V（re);V（sange）；p：=x； prit he messan x；Goo L；V（swri); oo L3；Ed; goL; end；End；coen2） va , B :aray 0 ，k ftem ； 1 ： smaphore：k; Put: semaPhor：=k; gt1 ： semPoe : = ； get： semaphore ： 0 ； put1 :nteger ：=O ; put2：ntge : = ； et1 :iteger := ; gt ： nteger : = O;oin rcss eae; penmaagr； poesWrer ； bgi egin beg l: ed a messageinto x ； L ：P （sgel ）；L3： （ sge) ； ( SPut1 ) ； : = A get1； x : = get2; A t：= ;et1 :（get1+1) mok ； get2:=(gt+ l ） md k；t1:=(ut1+） mo k; V（sput1);（spu)；V（set1）;maah esgeto x; it hemesage n ;oo L1； P（sput); otoL3;Pt：=（pu2+1）mok；V（sget2)；Goto 2；En;Coend2设有n个进程共享一个互斥段，如果：（ 1 )每次只允许一个进程进入互斥段；（ ）每次最多允许m 个进程（m 簇n)同时进入互斥段。试问：所采用得信号量初值就是否相同？信号量值得变化范围如何？答:所采用得互斥信号量初值不同。 ）互斥信号量初值为1 ,变化范围为n , 1 。当没有进程进入互斥段时，信号量值为 ;当有1 个进程进入互斥段但没有进程等待进入互斥段时，信号量值为O ；当有1个进程进入互斥段且有一个进程等待进入互斥段时,信号量值为1;最多可能有n1 个进程等待进入互斥段，故此时信号量得值应为(n 1 ）也就就是-n 。 2 ）互斥信号量初值为 ,变化范围为n+m , 。当没有进程进入互斥段时,信号量值为m ；当有1个进程进入互斥段但没有进程等待进入互斥段时,信号量值