操作系统第五版费祥林课后习题答案解析参考.docx
《操作系统第五版费祥林课后习题答案解析参考.docx》由会员分享，可在线阅读，更多相关《操作系统第五版费祥林课后习题答案解析参考.docx（136页珍藏版）》请在冰点文库上搜索。
操作系统第五版费祥林课后习题答案解析参考
第一章操作系统概论
1、有一台计算机,具有IMB内存,操作系统占用２0０ＫB，每个用户进程各占2０0KB。
如果用户进程等待I/Ｏ得时间为80%,若增加１MB 内存，则CPU得利用率提高多少?
ﻫ答：
设每个进程等待I/O得百分比为P,则n个进程同时等待刀O得概率就是Ｐn,当ｎ个进程同时等待I/O期间ＣPU就是空闲得,故ＣPU得利用率为1－Pn。
由题意可知，除去操作系统,内存还能容纳４个用户进程,由于每个用户进程等待I／Ｏ得时间为８0 %,故:
CPU利用率=l-（8０％）4=0、59
若再增加1ＭＢ内存，系统中可同时运行9个用户进程,此时:
cＰu 利用率=l-（１—8０％）９=0、87 ﻫ故增加ＩMB内存使CPＵ得利用率提高了47％ ：
８7％/59％=147%
１47%-100%=47%
2 一个计算机系统，有一台输入机与一台打印机,现有两道程序投入运行，且程序A先开始做,程序B后开始运行.程序A得运行轨迹为:
计算50ms、打印100ｍs、再计算５0ms、打印１00ｍｓ,结束。
程序B得运行轨迹为：
计算50mｓ、输入8０ms、再计算1００mｓ,结束。
试说明
（1）两道程序运行时,ＣＰＵ有无空闲等待？
若有,在哪段时间内等待？
为什么会等待?
（2）程序Ａ、B有无等待CPＵ得情况？
若有，指出发生等待得时刻。
答:
画出两道程序并发执行图如下:
ﻫ
ﻫ
（1）两道程序运行期间,CPU存在空闲等待，时间为１00 至1５0mｓ之间（见图中有色部分）ﻫ
（2）程序A无等待现象，但程序B有等待。
程序B 有等待时间段为180ｒｎｓ 至２00ｍs 间（见图中有色部分）ﻫ3设有三道程序，按A 、B 、C优先次序运行，其内部计算与UＯ操作时间由图给出.ﻫ
试画出按多道运行得时间关系图（忽略调度执行时间）。
完成三道程序共花多少时间?
比单道运行节省了多少时间？
若处理器调度程序每次进行程序转换化时lｍｓ,试画出各程序状态转换得时间关系图。
答：
1）忽略调度执行时间，多道运行方式（抢占式）：
？
ﻫ抢占式共用去１9０ｍs,单道完成需要2６0ms，节省70ms。
ﻫ忽略调度执行时间，多道运行方式（非抢占式）：
ﻫ
ﻫ非抢占式共用去１80ｍｓ，单道完成需要26０mｓ ，节省80mｓ 。
ﻫ2）调度执行时间1ms， 多道运行方式（抢占式）：
ﻫ
ﻫ调度执行时间ＩTnｓ ,多道运行方式（非抢占式）:
4在单CPU与两台I/O（ I1，12 ）设备得多道程序设计环境下，同时投入三个作业运行。
它们得执行轨迹如下:
Jｏｂl：
I2（30mｓ ）、CPU（ １０ｍｓ）、Ｉ1 （30ms）、CPU （10ms）、I2 （20ｍｓ）
Ｊｏb2：
Ｉ1（20ms ）、CPU（ 20ms ）、I２（４0mｓ ） ﻫJOb3 :
CPU （30ms）、Ｉ１ （20mｓ）、CＰU（１0ms）、I1 （10ms）
如果CPU 、I１与I2 都能并行工作,优先级从高到低为Ｊoｂl、Joｂ２与Jｏｂ3 ,优先级高得作业可以抢占优先级低得作业得CPU ,但不抢占I1与I２ 。
试求:
（l ）每个作业从投入到完成分别所需得时间。
（2）从投入到完成ＣPＵ 得利用率。
（3）I２设备利用率。
答：
画出三个作业并行工作图如下（图中着色部分为作业等待时间）:
（1 ） Jｏb1从投入到运行完成需110ms，Job2从投入到运行完成需9０ｍs，Ｊob3从投入到运行完成需11０ms、ﻫCPU空闲时间段为：
６０ms至7０ms,８0ms 至９0ms,1００ms 至１１０ms.所以ＣＰU利用率为（110—30）/1０＝72、7％.ﻫ设备I1 空闲时间段为：
2０mｓ 至40ms ， 90mｓ 至100ms，故I1得利用率为（110－3０）／l10 ＝72、7％。
ﻫ设备I2空闲时间段为：
30ms至50ms,故Ｉ２得利用率为（110—20） /１10＝81、8％。
5在单CPU与两台Ｉ/O（I1，1２）设备得多道程序设计环境下，同时投入三个作业运行.它们得执行轨迹如下:
ﻫJｏｂl ：
I２（30ｍs）、CPU （１0rns）、I1（ 30ms）、CPＵ（ １0ms） ﻫJｏb2:
I1（ 20ms）、ＣPU（20mｓ ）、I２ （40mｓ）
Jｏb３:
CPU（３0ms）、I１（ 20ms） ﻫ如果CＰU、I1与Ｉ２ 都能并行工作,优先级从高到低为Jｏb1、Job2与Job3,优先级高得作业可以抢占优先级低得作业得CＰU . ﻫ试求：
（ｌ ）每个作业从投入到完成分别所需得时间．ﻫ（ ２ ）每个作业投入到完成ＣPＵ得利用率。
ﻫ（3）I/0设备利用率.ﻫ答：
画出三个作业并行工作图如下（图中着色部分为作业等待时间）:
（ 1 ）Job1从投入到运行完成需80mｓ，Joｂ2从投入到运行完成需9０ｍｓ,Ｊob3从投入到运行完成需90ms。
ﻫ
（2）CPＵ空闲时间段为：
60ms至70ms， 80ms 至9０ms 。
所以CPU利用率为（90—20 ）/90= 77、78％。
ﻫ（ ３ ）设备I１空闲时间段为：
20ms至４０ms，故I1得利用率为（90－2０ ）／ 9０= 77、７8％。
设备I2空闲时间段为：
30mｓ至50ms，故I2得利用率为（90-２０）/90＝7７、78％。
ﻫ6若内存中有3道程序Ａ、B 、Ｃ ，它们按Ａ、B、C优先次序运行。
各程序得计算轨迹为：
Ａ ：
计算（20）、I/O（30）、计算（10 ） ﻫＢ ：
计算（４0）、I/O（20）、计算（１0）
c:
计算（10）、I/Ｏ（ 30）、计算（20）ﻫ如果三道程序都使用相同设备进行I／O（即程序用串行方式使用设备，调度开销忽略不计）。
试分别画出单道与多道运行得时间关系图.两种情况下，ＣPU得平均利用率各为多少？
ﻫ答：
分别画出单道与多道运行得时间图
（1）单道运行时间关系图ﻫ
单道总运行时间为１９0mｓ。
ＣＰU利用率为（1９0—80）/190 =57、9 ％ﻫ单道运行时间关系图 ﻫ
多道总运行时间为１40mｓ。
CＰＵ 利用率为（1４0—30）/140= ７8、６％
7 若内存中有3道程序Ａ、B、Ｃ，优先级从高到低为A 、B 与C，它们单独运行时得CPＵ 与Ｉ/O占用时间为:
ﻫ
如果三道程序同时并发执行，调度开销忽略不计，但优先级高得程序可中断优先级低得程序，优先级与Ｉ/O设备无关。
试画出多道运行得时间关系图,并问最早与最迟结束得程序就是哪个？
每道程序执行到结束分别用了多少时间？
计算三个程序全部运算结束时得CＰU利用率？
ﻫ答:
画出三个作业并发执行得时间图：
ﻫ（l）最早结束得程序为B,最后结束得程序为C. ﻫ（2 ）程序Ａ为25０ｍs.程序B为220mｓ。
程序Ｃ为３10ms 。
（3）CPＵ 利用率为（310－１２0）／３１0=６1、3％
有两个程序，Ａ程序按顺序使用:
（CPU）10 秒、（设备甲）5秒、（CPU）5 秒、（设备乙）10秒、（CPＵ）10秒。
B程序按顺序使用：
（设备甲）10秒、（CＰU）10秒、（设备乙）5秒、（CPU）5秒、（设备乙）10秒。
在顺序环境下先执行A,再执行B，求出总得CＰＵ利用率为多少?
答：
程序A执行了40秒，其中ＣPU用了25秒。
程序B执行了40 秒,其中CPＵ用了15 秒.两个程序共用了80 秒,ＣPU化40秒.故CPU 利用率为40/8０=5０％。
９、在某计算机系统中,时钟中断处理程序每次执行得时间为2ｍs （包括进程切换开销）。
若时钟中断频率为60ＨＺ ,试问CＰＵ用于时钟中断处理得时间比率为多少？
答：
因时钟中断频率为6０HZ,所以,时钟周期为:
l /６０s=50／3ms .在每个时钟周期中,CPU花2ｍs执行中断任务。
所以,CPU 用于时钟中断处理得时间比率为：
２（50/3）=6/50=１２%.
第二章处理器管理
1、下列指令中哪些只能在核心态运行？
（l）读时钟日期;
（2）访管指令；（3）设时钟日期；（4）加载ＰSW;（5）置特殊寄存器:
（６）改变存储器映象图;（7）启动I／O指令.
答:
（3）， （ 4），（5 ），（ 6），（7）、
2假设有一种低级调度算法就是让“最近使用处理器较少得进程”运行,试解释这种算法对“I／O繁重”型作业有利,但并不就是永远不受理“处理器繁重”型作业.
答:
因为I／Ｏ繁忙型作业忙于I／O，所以它CPU用得少,按调度策略能优先执行。
同样原因一个进程等待CPU足够久时,由于它就是“最近使用处理器较少得进程",就能被优先调度，故不会饥饿。
ﻫ３ 并发进程之间有什么样得相互制约关系?
下列日常生活中得活动就是属哪种制约关系：
（1）踢足球，
（2）吃自助餐，（3）图书馆借书,（４）电视机生产流水线工序.
答:
并发进程之间得基本相互制约关系有互斥与同步两种。
其中
（1）、（3）为互斥问题.（２）、（4）为同步问题。
ﻫ４在按动态优先数调度进程得系统中，每个进程得优先数需定时重新计算。
在处理器不断地在进程之间交替得情况下,重新计算进程优先数得时间从何而来？
答：
许多操作系统重新计算进程得优先数在时钟中断处理例程中进行，由于中断就是随机碰到哪个进程，就插入哪个进程中运行处理程序,并把处理时间记在这个进程得账上.
5若后备作业队列中等待运行得同时有三个作业J1 、J２、Ｊ3,已知它们各自得运行时间为a、b、c,且满足ａ＜b 答：
采用短作业优先算法调度时，三个作业得总周转时间为：
ﻫTl== a＋（a +b）+（ a+ｂ+ｃ）=3ａ+２ｂ+c ①ﻫﻫ若不按短作业优先算法调度，不失一般性,设调度次序为:
J2 、J1 、J3。
则三个作业得总周转时间为:
T２=b＋（b＋a） +（b＋a +c ）＝３b+ 2ａ + c ②
令②－① 式得到：
ﻫＴ2- Tl = ｂ-ａ＞0 ﻫ可见，采用短作业优先算法调度才能获得最小平均作业周转时间。
ﻫ６、若有一组作业J１ ,… ,Jn，其执行时间依次为S1，…， Sn 。
如果这些作业同时到试找出一种作业调度算法到达系统，并在一台单ＣPU处理器上按单道方式执行。
使得平均作业周转时间最短.
答：
首先，对n个作业按执行时间从小到大重新进行排序,则对n个作业：
J１’ ，…，Jｎ，创门得运行时间满足：
S1≤S2 ≤……≤S （ｎ-l）≤Sｎ '.那么有：
由于任何调度方式下，S1＇+Ｓ2'+S3'+…＋Sｎ’为一个确定得数，而当S1’≤S2 ’≤…≤S（n—１） ’≤Sn ’时才有：
0*S1+1＊S２+2＊S３＋…（ｎ-1）Sｎ得值最大，也就就是说,此时Ｔ 值最小。
所以,按短作业优先调度算法调度时,使得平均作业周转时间最短。
ﻫ7、假定执行表中所列作业，作业号即为到达顺序，依次在时刻０按次序1、2 、3、4、5进入单处理器系统。
（１）分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占优先权调度算法算出各作业得执行先后次序（注意优先权高得数值小）；
（2）计算每种情况下作业得平均周转时间与平均带权周转时间.
（1）采用FCFS算法调度作业，运作情况：
ﻫ
（ ２）采用双算法调度作业，若令时间片长=l ，各作业执行情况为：
1、2 、3、４、5、l、３ 、5、１、５、1、５、1、5 、1、ｌ、l、1、1。
ﻫ
（3）采用ＳＪF 算法调度作业，运作情况:
ﻫ
（4）采用非剥夺优先权算法调度作业,运作情况：
8对某系统进行监测后表明平均每个进程在I/O 阻塞之前得运行时间为T .一次进程‘切换得系统开销时间为S。
若采用时间片长度为Q得时间片轮转法，对下列各种情况算出ＣPU利用率。
ﻫ9 有5个待运行得作业，各自预计运行时间分别就是:
9、６、3、5 与x，采用哪种运行次序使得平均响应时间最短？
答:
按照最短作业优先得算法可以使平均响应时间最短。
ｘ取值不定,按照以下情况讨论：
ﻫ1０、有5个批处理作业Ａ到E 均己到达计算中心，其运行时间分别2、４、６ 、8与1０分钟：
各自得优先级分跳狠掀完为、、飞、飞、氏积5、这里５为最高级.对于1）时间片轮转算法、2）优先数法、3）短作业优先算法、４）先来先服务调度算法（按到达次序C、D、B、Ｅ、Ａ）,在忽略进程切换时间得前提下，计算出平均作业周转时间。
（对l）每个作业获得相同得2分钟长得时间片;对2）到４）采用单道运行,直到结束。
）ﻫ答：
（l）FCFＳ调度算法
（2）优先级调度算法ﻫ
ﻫ（３ ）时间片轮转法ﻫ
按次序ABCDEBCDECDＥDEE轮转执行.
（4 ）SＪF调度算法
ﻫ11、 有5个批处理作业A到E均已到达计算中心，其运行时间分别１0 、6、2、4 与8分钟;各自得优先级分别被规定为3、5、２、1与4 ，这里5为最高级.若不考虑系统切换开销,计算出平均作业周转时间。
（１）FCFs （按A、Ｂ 、C 、D、E） ；（２） 优先级调度算法,（3）时间片轮转法（每个作业获得相同得2分钟长得时间片）。
ﻫ答:
ﻫ（ １）FＣFS 调度算法
（2 ）优先级调度算法ﻫ
（3）时间片轮转法
按次序AＢＣDＥAＢDEABEAEA轮转执行。
作业
执行时间
等待时间
周转时间
带权周转时间
A
B
C
D
E
10
6
2
4
8
20
l6
4
l2
20
30
22
6
16
28
3
3、66
3
4
3、5
作业平均周转时间作业平均带权周转时间
T=（30+22+6+16+28）/5=20、4
W=（3+3、66+3+4+3、5）/5=3、43
12（l）假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输出为主，您将怎样赋予它们占有处理器得优先级？
为什么？
（2）假定一个处理器正在执行三道作业,一道以计算为主，第二道以输入输出为主,第三道为计算与输入输出均匀.应该如何赋予它们占有处理器得优先级使得系统效率较高？
答:
处理器调度算法会考虑以下因素:
作业响应时间要求；让CPU尽量与外围设备并行工作；限制一个计算进程长时间霸占处理器。
因而,（１） FO 为主作业优先级高.
（2）输入输出为主作业优先级最高，输入输出均匀得作业其次,而计算为主作业得优先级最低。
ﻫ13请您设计一种先进得计算机体系结构，它使用硬件而不就是中断来完成进程切换,则CPU需要哪些信息？
请描述用硬件完成进程切换得工作过程.
答：
该计算机有一个专用硬件寄存器,它始终存放指向当前运行进程得ＰCＢ得指针。
当系统中发生了一个事件,如ＦO 结束事件,CＰU便可把运行进程得上下文保存到专用硬件寄存器指针指向得PＣＢ中保护起来，然后,CPU 转向中断向量表，找到设备中断处理程序入口，让专用硬件寄存器指针指向（设备）中断服务例程,于就是,便可启动中断服务例程工作。
14 设计一条机器指令与一种与信号量机制不同得算法，使得并发进程对共享变量得使用不会出现与时间有关得错误。
ﻫ解:
ﻫ（ｌ）设计机器指令。
ﻫ设计一条如下得"测试、比较与交换”三地址指令,提供了一种硬件互斥解决方案:
TC&S
R1
R3
B2
D2
该指令得功能如下：
l） Ｃ 为一个共享变量，由地址2、即变址（Ｂ２ ） ＋Ｄ2给出,
（2 ）（Ｒl）与（C ）比较，ﻫ（3）如果（Rl ）=（C）则（R3）→Ｃ,并置条件码为＂00”,ﻫ如果（Ｒ１）≠（c）则（C）→Rｌ ，并置条件码为＂0１"、ﻫ（２）编写进程访问共享变量得程序。
ﻫ对每个访问共享变量Ｃ得进程，编写访问共享变量得程序段为：
陆界区程序
说明
（C）→Rl;
loop2:
（R1）→R3;
Add/decreaseR3;
TC&S;
R（condition=01）loop2;
共享变量C得值保护到RI中。
Rl得值传送到R3中,进程修改共享变量时,先对R3操作（不就是直接操作C）。
R3加1／减1,进程归还／申请由共享变量C代表得共享资源（假定每次一个）。
执行”测试、比较与交换”指令。
条件码＝01,转向循环loop2;否则离开临界区。
（ 3）程序执行说明。
ﻫ此解与互斥使用共享变量得思路绝然不同，并发运行得进程可不互斥地访问它们得共享变量。
此方案认为造成共享变量C值错误得原因在于:
一个进程（Pｌ ）在改变C 值得过程中,另一个进程伊２）插进来也改变了Ｃ得值，而本进程（Ｐｌ）却不知道,造成了ｃ值结果不正确。
如果有办法使本进程口１ ）能知道C 值就是否改变，改变得话在继承改变了得C值得基础上，再作自己得改变操作,则就不会导致共享变量Ｃ值得错误。
为此,本解决方案中,当一个进程l）准备改变C值时,先把C得值保护在Rl 中，然后，通过R3 来改变共享变量C得值.当要把新得值（即R3内得值）送C之前,先要判断一下在本进程（P1 ）工作期间就是否有别得进程口2）插进来也改变了C得值（并发进程P１、P２得执行完全会造成这种情况），方法就是：
将扭１）中被保护得C 得原来值，与C 得当前值比较，若相等,说明C值未被改变过,则将本进程（Pl ）修改过得新值送C （即（R３）一C）；若不相等,说明C值在工作期间被改变过，则应该继承C得新值（即（Ｃ）一Rl）并且返回到ｌoｏp2处重新对Ｃ值计数,以此保证Ｃ值得最终结果得正确性。
这里提及”进程工作期间"指得就是一个进程从开始至结束对共享变量Ｃ值得操作得这段时间,也就就是执行进程,’ I晦界区”这段程序得时间。
此外,在进程进入临界区之前，应等待直到C为非。
（即有资源可用）为止。
（４ ）举例。
ﻫ假定系统中有静态分配资源磁带机共3台,被Ｎ个进程共享，由共享变量C 来代表可用磁带机台数,其初值为3。
现有并发进程P1与P2均申请使用磁带机，执行临界区程序。
进程Pl执行临界区程序ﻫ（ C）→R1 ；因（C）=3，故（R１）＝3 。
lｏoｐ2：
（Ｒl）→Ｒ3因（R1）=３，故（Ｒ3）当前也＝３ .ﻫdecｒeaｓｅＲ3：
申请使用磁带机，做减1操作,故（R3）=2、ﻫＴC& S执行”测试、比较与交换,，ＴＣ ＆Ｓ指令。
如果R1=（C ）则（R３ ）→Ｃ,即（C）=２,并置条件码为”0０",跳出临界区程序,去使用磁带机.ﻫ如果（Rｌ）≠（C）,例如,（C）=2，说明进程P2抢先申请了磁带机,所以，C与保护在R1中得值不一样了（C 得值必
小于Rl得值），应以Ｃ 得当前值为准,执行（C）Rl（Ｒ1此时变为2），并置条件码为"0１＂，转向fｏoｐZ。
于就是伍1 ）＝2，跟着（R3卜２。
接着卿）减１ 后应=l了。
再执行TC& S时,由于伍1卜（C）=2，会使C变为1。
ﻫｒ （ cｏnｄitio二0１）lｏop2；
巧单道批处理系统中,下列三个作业采用先来先服务调度算法与最高响应比优先算法进行调度，哪一种算法性能较好?
请完成下表:
作业
提交时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
1
2
3
10:
00
10:
10
10:
25
2:
00
1:
00
0:
25
平均作业周转时间=
平均作业带权周转时间W=
答：
ﻫ
可见HＲRＦ比ＦIFO要好
16若有如表所示四个作业进入系统，分别计算在FCFS、S 开与HRR卫算法下得平均周转时间与带权平均周转时间.（时间以十进制表示） ﻫ
ﻫ答：
ﻫ17Klｅinrock 提出一种动态优先权算法:
进程在就绪队列等待时，其优先权以速率a变化；当进程在处理器上运行,时其优先权以速率p变化.给参数a，b 赋以不同值可得到不同算法.（l ）若a〉b>c就是什么算法？
（２ ）若a＜b（ ｌ ）就是先进先出算法。
因为在就绪队列中得进程比在CPU上运行得进程得优先数提高得快,故进程切换时,先进入就绪队列得进程优先权就越高。
ﻫ（２）就是后进先出算法.因为在就绪队列中得进程比在CPU上运行得进程得优先权下降得快,故后进入就绪队列得进程此先进入得进程得优先权高。
ﻫ18有一个四道作业得操作系统，若在一段时间内先后到达6 个作业，它们得提交与估计运行时间由下表给出：
ﻫ
ﻫ系统采用SＪF 调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占.（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 ：
３０,作业Ｃ到达
升级会员 