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

1、第一章操作系统概论1、有一台计算机，具有IMB内存，操作系统占用200KB ,每个用户进程各占 200KB。如果用户进程等待I/O的时间为80 % ,若增加1MB内存，则CPU的 利用率提高多少？答：设每个进程等待I/O的百分比为P ,则n个进程同时等待刀0的概率是 Pn ,当n个进程同时等待I/O期间CPU是空闲的，故CPU的利用率为Pn。 由题意可知，除去操作系统，内存还能容纳4个用户进程，山于每个用户进程 等待I/O的时间为80 % ,故：CPU 利用率=1- (80%) 4 =若再增加1MB内存，系统中可同时运行9个用户进程，此时：cPu利用率=1 - (1-80%)9 =故增加IMB

2、内存使CPU的利用率提高了 47 % :87 %/59 %=147 %147 %-100 % = 47 %2个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程 序A先开始做，程序B后开始运行。程序A的运行轨迹为：计算50ms、打印 100ms、再计算50ms、打印100ms ,结束。程序B的运行轨迹为：计算50ms、 输入80ms、再计算100ms ,结束。试说明(1 )两道程序运行时，CPU有无空 闲等待若有，在哪段时间内等待为什么会等待(2 )程序A、B有无等待CPU的 情况若有，指出发生等待的时刻。答：画出两道程序并发执行图如下:单位10 ms处理器|A汁H |R计建|i

3、iiA计篁 iiR计|辎入机ii:u蛤入i1 打印机iiA rren ji i1A打印|程序ALi打印i计垃|rren|程序B1计篁1i竝入总1rfrM|时( (B(ms)11I1 11|05010 0150180 200250300（1）两道程序运行期间，CPU存在空闲等待，时间为100至150ms之间（见图 中有色部分）（2）程序A无等待现象，但程序B有等待。程序B有等待时间段为180rns至 200ms间（见图中有色部分）3设有三道程序，按A、B、C优先次序运行，其内部计算和UO操作时间由图 给出。ABCCH=30msIC216*0msIC3j=20ms1IIi2=40msI1Iii=3

4、0ms1.IIi2=40ms11Cn=10ms1C23=10ms1C33=20ms试画出按多道运行的时间关系图（忽略调度执行时间）。完成三道程序共花多少 时间比单道运行节省了多少时间若处理器调度程序每次进行程序转换化时1ms , 试画出各程序状态转换的时间关系图。答：1）忽略调度执行时间，多道运行方式（抢占式）：时 037 810 12 13141719抢占式共用去190ms ,单道完成需要260ms ,节省70ms。CPU ,C11 ：C21 ： C13 C211C31：fc23 C33MIMx,上忽略调度执行时间，多道运行方式(非抢占式)：时间 037 9 1012 13 14 1618

5、单位 10用I/O112II |1122 |1132CPUC11C21fcUC3123| JC33非抢占式共用去180ms ,单道完成需要260ms ,节省80ms。2 )调度执行时间1ms ,多道运行方式(抢占式)：调度执行时间ITns ,多道运行方式(非抢占式)：4在单CPU和两台1/0( II , 12 )设备的多道程序设计环境下，同时投入三个 作业运行。它们的执行轨迹如下：Jobl : 12 ( 30ms )、CPU ( 10ms )、Il( 30ms )、CPU ( 10ms )、12 ( 20ms )Job2 : Il ( 20ms ) 、 CPU ( 20ms ) 、12 ( 4

6、0 ms )J0b3 : CPU ( 30ms ) 、 Il ( 20ms ) 、CPU ( 10ms ) 、Il (10ms )如果CPU、Il和12都能并行工作，优先级从高到低为Jobl、Job2和Job3 , 优先级高的作业可以抢占优先级低的作业的CPU ,但不抢占II和12 o试求：(1)每个作业从投入到完成分别所需的时间。(2 )从投入到完成CPU的利 用率。(3)12设备利用率。答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：，CPULJob31 Job2 | Jobl | Job21 Job3I1 Jobl I1 Job3 |11|Job21JoblJob31| J

7、ob3112|Jobl11Job21Jobli r|Jobl121 CPU L,IlCPUF12|Job21IICPU |-CPU112Job1CPUi1 CPU111i CPU i n|时间1i1IJF111 |(ms)0102030405060708090100no(1 ) Jobl从投入到运行完成需110ms , Job2从投入到运行完成需90ms , Job3 从投入到运行完成需110ms.CPU 空闲时间段为：60ms 至 70ms , 80ms 至 90ms , 100ms 至 110ms。所以 CPI； 利用率为(110-30) /10 =%。设备II空闲时间段为:20ms至40

8、ms , 90ms至100ms,故II的利用率为 (110-30)/110 = 72 . 7 %。设备12空闲时间段为：30ms至50ms,故12的利用率为(110-20) / 110=%。5在单CPU和两台1/0( II , 12 )设备的多道程序设计环境下，同时投入三个 作业运行。它们的执行轨迹如下：Jobl : 12 ( 30ms ) 、 CPU ( lOrns ) 、 Il ( 30ms ) 、 CPU ( 10ms )Job2 : Il ( 20ms ) 、 CPU ( 20ms ) 、 12 ( 40ms )Job3 : CPU ( 30ms ) 、 Il ( 20ms )如果CP

9、U、Il和12都能并行工作，优先级从高到低为Jobl、Job2和Job3 , 优先级高的作业可以抢占优先级低的作业的CPU。试求：(1 )每个作业从投入到完成分别所需的时间.(2 )每个作业投入到完成CPU的利用率。(3 ) I/O设备利用率。! Jobl |II答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)：CPU J0b3_ I Job2 I Job】Job2 I Jop3 111, Job2 |IJobl_I Job3 112JoblII域 2_IJobl |12 CPU IIII CPUJob2 | Il| CPU同 CPU 112_|时间 |1|$II _) _| _I

10、(ms)01020304050607080 9Q(1 ) Jobl从投入到运行完成需80ms , Job2从投入到运行完成需90ms , Job3 从投入到运行完成需90ms o(2 ) CPU空闲时间段为：60ms至70ms , 80ms至90ms。所以CPU利用率为 (90-20 ) / 90 =%。(3 )设备II空闲时间段为：20ms至40ms ,故II的利用率为(90-20) / 90 = 77. 78 %。设备12空闲时间段为：30ms至50ms ,故12的利用率为(90-20 ) / 90= %。6若内存中有3道程序A、B、C ,它们按A、B、C优先次序运行。各程序 的计算轨迹为

11、：A :计算(20 )、1/0( 30 )、计算(10 )B :计算(40 )、1/0( 20 )、计算(10 )c :计算(10 )、1/0 ( 30 )、计算(20 )如果三道程序都使用相同设备进行I/O (即程序用串行方式使用设备，调度开销 忽略不计)。试分别画出单道和多道运行的时间关系图。两种情况下，CPU的平 均利用率各为多少？答：分别画出单道和多道运行的时间图(1)单道运行时间关系图I CPUI/O| A1J111_1:5111|CPU i A ji *iiiiii?_iUisj4:JI1111ii时间iii i i: :; :1 1 1 ! 1 1 1 1 (ms)02040 5

12、0 6080100120140160180 i 处单道总运行时间为190ms o CPU利用率为(190-80 ) /190二%单道运行时间关系图I/O1- A1LBIcCPUiiii1 A |B1 A1 0 1 c 1U L.时间J,L:iiiiiiiii!1 1 1(ms)02040 50 6080100120140多道总运行时间为140ms o CPU利用率为(140-30 ) / 140二%7若内存中有3道程序A、B、C ,优先级从高到低为A、B和C ,它们单独 运行时的CPU和I/O占用时间为:程序程序A：60203010402020 (ms)1/02CPUI/OlCPUI/Ol C

13、PUI/Ol程序B；3040703030 (ms)I/OlCPUI/O2CPUI/O2程序C：40603070 (ms)CPUI/OlCPUI/O2如果三道程序同时并发执行，调度开销忽略不讣，但优先级高的程序可中断优先 级低的程序，优先级与I/O设备无关。试画出多道运行的时间关系图，并问最 早与最迟结束的程序是哪个每道程序执行到结束分别用了多少时间计算三个程 序全部运算结束时的CPU利用率？ 答：画出三个作业并发执行的时间图:I B| c |A | c |CPU101|C 1B 1BL A 1BI c Ll AtJ|C1 A_11 A I102 1A1 1B_j1B .11C1|cpu| 10

14、1|A1102RU | 10! |p 1IV 1B1101 |cpu11wmi1 PU 1102 |Ccpu1011F卬u1021时间L_ _L1 11|(ms) 匸1 1 1 0306090120150180210240270300330(1)最早结束的程序为B ,最后结束的程序为C o(2 )程疗;A为250ms 程丿了: B为220ms。程序C为310ms。(3 ) CPU 利用率为(310 -120 ) / 310 = %有两个程序，A程序按顺序使用：(CPU) 10秒、(设备屮)5秒.(CPU) 5秒、 (设备乙)10秒、(CPU) 10秒。B程序按顺序使用：(设备甲)10秒、(CP

15、U)10秒、(设备乙)5秒、(CPU)5秒.(设备乙)10秒。在顺序环境下先执行 A ,再执行B ,求出总的CPU利用率为多少？答：程序A执行了 40秒，其中CPU用了 25秒。程序B执行了 40秒，其中 CPU用了 15秒。两个程序共用了 80秒，CPU化40秒。故CPU利用率为40/80 =50 %。9、在某计算机系统中，时钟中断处理程序每次执行的时间为2ms (包括进程切 换开销)。若时钟中断频率为60HZ ,试问CPU用于时钟中断处理的时间比率为 多少答：因时钟中断频率为60HZ ,所以，时钟周期为：1 / 60s二50/3ms。在每个时钟周期 中，CPU花2ms执行中断任务。所以，C

16、PU用于时钟中断处理的时间比率为：2(50/3)=6/50 =12%。第二章处理器管理设调度次序为：J2、JI、J3。则T2二b+ (b+a ) +(b+a + c)=3b + 2a + c 1.下列指令中哪些只能在核心态运行？(1)读时钟日期；(2)访管指令；(3)设时钟日期；(4)加载PSW; (5)置特殊 寄存器：(6)改变存储器映象图；(7)启动I/O指令。答：(3 ) , ( 4 ) , ( 5 ) , ( 6 ) , ( 7 ).2假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这 种算法对“I/O繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。答：因为

17、I/O繁忙型作业忙于I/O,所以它CPU用得少，按调度策略能优先执行。 同样原因一个进程等待CPU足够久时，山于它是“最近使用处理器较少的进程”, 就能被优先调度，故不会饥饿。3并发进程之间有什么样的相互制约关系下列日常生活中的活动是属哪种制约 关系：(1)踢足球，(2)吃自助餐，(3)图书馆借书，(4)电视机生产流水线工 序。答：并发进程之间的基本相互制约关系有互斥和同步两种。其中(1)、(3)为 互斥问题.(2)、(4)为同步问题。4在按动态优先数调度进程的系统中，每个进程的优先数需定时重新讣算。在处 理器不断地在进程之间交替的情况下，重新计算进程优先数的时间从何而来？答：许多操作系统重新

18、计算进程的优先数在时钟中断处理例程中进行，山于中断 是随机碰到哪个进程，就插入哪个进程中运行处理程序，并把处理时间记在这个 进程的账上。若后备作业队列中等待运行的同时有三个作业JI、J2、J3 ,已知它们各自 的运行时间为a、b、c,且满足a b 0可见，采用短作业优先算法调度才能获得最小平均作业周转时间。6、若有一组作业J1 ,，Jn ,其执行时间依次为S1 ,，Sn。如果这些 作业同时到试找出一种作业调度算法到达系统，并在一台单CPU处理器上按单 道方式执行。使得平均作业周转时间最短。答：首先，对n个作业按执行时间从小到大重新进行排序，则对n个作业：J1 ，Jn,创门的运行时间满足：S1W

19、S2 WWS (n-1 ) W Sn 。那 么有：T=S| +( Si +S2 + (S| + S? + S3)十+(S| 扌 S2 + S3+ SB )/n=n X S+( n-lX S；+ (n-3)X S十十 S；/n=(SS2-T 3) SVQVT 4 = Q=S 5= Q 接近于 0峯 l Q= CPU 利用率=T/ (T+S)2)QTCPU利用率QS CPU 利用率=Q/ (Q+S)4)Q=SCPU 利用率=50%5)Q-0 CPU 利用率一09有5个待运行的作业，各自预计运行时间分别是：9、6、3、5和x ,采 用哪种运行次序使得平均响应时间最短？ 答：按照最短作业优先的算法可以

20、使平均响应时间最短。x取值不定，按照以下 情况讨论：1)xW3次序为x. 3, 5, 6, 92)3xW5次序为：3. x, 5, 6, 93)5xW6次序为彳3. 5, j 6.94）6次序为m 3w 5 6,X10有5个批处理作业A到E均己到达计算中心，其运行时间分别2 .4.6. 8和10分钟：各自的优先级分跳狠掀完为、飞、飞、氏积5、这里5为最 高级。对于1）时间片轮转算法、2）优先数法、3）短作业优先算法、4）先来 先服务调度算法（按到达次序C、D、B、E、A）,在忽略进程切换时间的前 提下，计算出平均作业周转时间。（对1）每个作业获得相同的2分钟长的时间 片；对2）到4）采用单道运

21、行，直到结束。）答：（1 ） FCFS调度算法执行次序执行时间等待时间周转时间带杈周转时间c6061D86141.75B414184.5E1018282.8A2283015作业平均周转时间T=(6+14+18+25+30)/5= 19.2作业平均带权周转时间W=(l+L75+4.5+2.8+15)/5=5.01（2）优先级调度算法执疗次序执行时间等待时间周转时间带权周转时间E100101D810182.25C618244B424287A2283015作业平均周转时间T=(10+l 8+24+28+30)/5=22作业平均带权周转时间W(l +2.25+4+7+15)/5-5.85(3)时间片轮

22、转法作业执行时间竿待时间周转时带权周转时间A2021 1B48123C614203.33D&18263.25E1020303作业平均周转时间T=(2+12+20+26+30)/5=18作业平均带权周转时闾W=(l+3+3.33+3.25+3)/$=2.71按次序ABCDEBCDECDEDEE轮转执行。(4 ) SJF调度算法作业执行时间尊持时伺周转时间带权周转时间Ai2021B4261.5C66122D812202.5E1020303作业平均周转时间T=(2+6+12+20+30)/5=14作业平均带权周转时间W=(H 1.5+2+2.5+3/5=211、有5个批处理作业A到E均已到达计算中心

23、，其运行时间分别10、6、2、4和8分钟：各自的优先级分别被规定为3、5、2、1和4 ,这里5为 最高级。若不考虑系统切换开销，计算出平均作业周转时间。(l)FCFs (按A、B、C、D、E) ; (2)优先级调度算法，(3)时间片轮转法(每个作业获得相 同的2分钟长的时间片)。答：(1 ) FCFS调度算法执行次序执行时何等待时间周转时间带权周转时间A100101B610162.66C216189D418225.5E&22303.75作业平均周转时间1=(10+16+18+22+30)/5=192作业平均带权周转时间W=( 1十2.6倂9 十 5.5+3.75/5M .38(2)优先级调度算

24、法执行次序执行时间等待时间周转时间带权周转时间B6061E86141.75A1014242.4C2242613D426307.5作业平均周转时间T=(6+ 】4 十24+26十 30)/5=20作业平均带权周转时间W=(l+1.75+2.4+13+7.5)/55.13(3)时间片轮转法按次ABCDEABDEABEAEA轮转执行。作业执行时间等待时间周转时间=带权周转时间:A102030999B616223C2463 .66D412163E8202843. 5作业平均周转时间T = ( 30 + 22 + 6 + 16 + 28 ) / 5二 作业平均带权周转时间呂二(3 + + 3 +4 +

25、) / 5 =12 (1)假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输 出为主，你将怎样赋予它们占有处理器的优先级为什么？(2)假定一个处理器正在执行三道作业，一道以计算为主，第二道以输入输出为 主，第三道为计算与输入输出均匀。应该如何赋予它们占有处理器的优先级使得 系统效率较高？答：处理器调度算法会考虑以下因素：作业响应时间要求；让CPU尽量和外围 设备并行工作；限制一个计算进程长时间霸占处理器。因而，(1 ) F0为主作 业优先级高。(2 )输入输出为主作业优先级最高，输入输出均匀的作业其次， 而计算为主作业的优先级最低。13请你设讣一种先进的讣算机体系结构，它使用硕件而

26、不是中断来完成进程切 换，则CPU需要哪些信息请描述用硬件完成进程切换的工作过程。答：该计算机有一个专用硬件寄存器，它始终存放指向当前运行进程的PCB的 指针。当系统中发生了一个事件，如F0结束事件，CPU便可把运行进程的上下 文保存到专用硬件寄存器指针指向的PCB中保护起来，然后，CPU转向中断向 量表，找到设备中断处理程序入口，让专用硬件寄存器指针指向(设备)中断服 务例程，于是，便可启动中断服务例程工作。14设讣一条机器指令和一种与信号量机制不同的算法，使得并发进程对共享变 量的使用不会出现与时间有关的错误。解：(1 )设计机器指令。设计一条如下的”测试、比较和交换”三地址指令，提供了一

27、种硬件互斥解决方 案：$R3B2D2TC&SR1该指令的功能如下:1 ) C为一个共享变量，由地址2、即变址(B2 ) + D2给出,(2 ) (R1 )与(C )比较，(3 )如果(R1 )二(C )则(R3) -C ,并置条件码为00， 如果(Rl ) H (c )则(C )-Rl ,并置条件码为01 ” .(2)编写进程访问共享变量的程序。对每个访问共享变量c的进程，编写访问共享变量的程序段为：)陆界区程序说明(C ) fR1 ;共享变量C的值保护到RI中。loop2 : ( R1 ) R3 ;R1的值传送到R3中,进程修改共享变量时，先对R3操 作(不是直接操作C )。Add /dec

28、rease R3 ;R3加1 /减1 ,进程归还/申请由共拿变量C代表的TC & S ;共享资源(假定每次一个)。R( condition = 01 )执行”测试、比较和交换”指令。loop2 ;条件码=01 ,转向循环loop2 ；否则离开临界区。（3 ）程序执行说明。此解与互斥使用共享变量的思路绝然不同，并发运行的进程可不互斥地访问它们 的共享变量。此方案认为造成共享变量C值错误的原因在于：一个进程（P1 ） 在改变C值的过程中，另一个进程伊2 ）插进来也改变了 C的值，而本进程（P1） 却不知道，造成了 c值结果不正确。如果有办法使本进程口 1 ）能知道C值是 否改变，改变的话在继承改变

29、了的C值的基础上，再作自己的改变操作，则就 不会导致共享变量C值的错误。为此，本解决方案中，当一个进程1）准备改变 C值时，先把C的值保护在R1中，然后，通过R3来改变共享变量C的值。当 要把新的值（即R3内的值）送C之前，先要判断一下在本进程（P1 ）工作期 间是否有别的进程口 2 ）插进来也改变了 C的值（并发进程Pl、P2的执行完 全会造成这种情况）,方法是：将扭1）中被保护的C的原来值，与C的当前 值比较，若相等，说明C值未被改变过，则将本进程（P1 ）修改过的新值送C （即 （R3 ） C ）；若不相等，说明C值在工作期间被改变过，则应该继承C的 新值（即（C ） -R1 ）并且返回

30、到loop2处重新对C值计数，以此保证C值的 最终结果的正确性。这里提及”进程工作期间”指的是一个进程从开始至结束对 共享变量C值的操作的这段时间，也就是执行进程，I晦界区”这段程序的 时间。此外，在进程进入临界区之前，应等待直到C为非。（即有资源可用） 为止。（4 ）举例。假定系统中有静态分配资源磁带机共3台，被N个进程共享，由共享变量C来 代表可用磁带机台数，其初值为3。现有并发进程P1和P2均申请使用磁带机, 执行临界区程序。进程P1执行临界区程序（C ） f R1 ；因（C） =3 ,故（R1） = 3。loop2: （ Rl ） -R3 因（R1 ） = 3，故（R3 ）当前也=3。

31、decrease R3 :申请使用磁带机，做减1操作，故（R3 ）二2.TC & S执行”测试、比较和交换，TC & S指令。如果R1二（C ）则（R3 ） -C,即（C）二2 ,并置条件码为” 00,跳出临界区 程序，去使用磁带机。如果（Rl） H （C）,例如，（C ）二2，说明进程P2抢先申请了磁带机，所以, C与保护在R1中的值不一样了（C的值必小于R1的值）,应以C的当前值为准，执行（C ） Rl （ R1此时变为2 ）, 并置条件码为” 01 ,转向foopZ o于是伍1 ）二2 ,跟着（R3卜2。接着 卿）减1后应=1 了。再执行TC & S时，由于伍1卜（C ）二2 ,会使C变

32、 为1。r （ conditio 二 01 ） loop2 ;巧单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先 算法进行调度，哪一种算法性能较好请完成下表：作业提交时间运行时间开始时间完成时间周转时 间带权周 转时间12310 : 0010 : 1010 : 252 : 001 : 000 : 25平均作业周转时间二平均作业带权周转时间W二答:FIFO开始完成周转带权周作业捉交时间运行时间时间时间时间转时间110 :002 : 0010:0012:002120/120210 : 101 : 0012:0013:002:50170/60310 : 250 : 2513:00

33、13:253180/25平均祜业周转时间=2.61平均作业帝权周转时间W=3.68HRRF开始完成周转带权周作业提交时间运行时间时间时间时间转跡间110 : 002 : 0010:0012:002120/120210 : 101 ：0012;2513:253:15195/60310 : 250 ：2$12：0012:2$2120/25平均作业周转时间=2.41平均作业帶权周转时间W=3.02可见HRRF比FIFO要好16若有如表所示四个作业进入系统，分别计算在FCFS、S开和HRR卫算法下 的平均周转时间与带权平均周转时间。（时间以十进制表示）作业提交时何（时）怙计运行时间（小时）18.002

34、.002& 500.5039.000.1049.500.20答:FCFSSJFHRRF作业开始 时间完成时间周转 时间1开始 时同完成 时何周转 时间开始 时间完成时何周转时间1&0010.002.008.0010.002.008.0010.002.00210.0010.5010010.5010.8023010.1010.602.10310.5010.601.6010.00LG.101J0101.55* 1.625转时间帝权平均W-6.875W-5.15W-S.67S岡转时间17 Kleinrock提出一种动态优先权算法：进程在就绪队列等待时，其优先权以 速率a变化；当进程在处理器上运行，时其

35、优先权以速率p变化。给参数a, b赋 以不同值可得到不同算法。（1）若abc是什么算法（2 ）若abc是什 么算法答：（1）是先进先出算法。因为在就绪队列中的进程比在CPU上运行的进程 的优先数提高得快，故进程切换时，先进入就绪队列的进程优先权就越高。（2 ）是后进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优 先权下降得快，故后进入就绪队列的进程此先进入的进程的优先权高。18有一个四道作业的操作系统，若在一段时间内先后到达6个作业，它们的提 交和估计运行时间山下表给出：作业提交时何估计运行时间（分钟）i8： 006028： 203538： 252048： 302558： 3556

36、& 4010系统釆用SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时 可被更短作业抢占。（1 ）分别给出6个作业的执行时间序列、即开始执行时 间、作业完成时间、作业周转时间。（2 ）计算平均作业周转时间。答作业提交需运行开始运行被抢占还完成周转号时间时间时河需运行时间时廊时间J18:00608:004010:35155J28:20358:20309:5595J38:25208:258:4520J48:30259:00259:2555J58:3558:458:5015J68:40108:509:0020能绻队列说明:(1 ) J2到达时抢占JI ; J3到达时抢占J2 o(2 )但

37、丁4到达时，因不满足SJF ,故J4不能被运行，J3继续执行5分钟。(3 )由于是4道的作业系统，故后面作业不能进入主存而在后备队列等待， 直到有作业结束。(4 )根据进程调度可抢占原则，J3第一个做完。而这时J3、J6均己进入后 备队列，而J5可进入主存。(5 )因J5最短，故它第二个完成。这时J6方可进入主存。因J6最短，故 它第三个完成。(6 )然后是：J4、J2和J119、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法， 进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业 优先数即为进程优先数，优先数越小优先级越高。A10： 0040分5B10：

38、2030分3C10： 3050分4D10： 5020分6(7 ) T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60&009:25J1故绪队列n后备认列J6;后各队列8:25 8:30 8:35 &40 5:45 8:50作业名到达时间估计运行时间优先数(1)列出所有作业进入内存时间及结束时间。(2 )计算平均周转时间。答：每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数 抢占式)。另外，批处理最多容纳2道作业，更多的作业将在后备队列等待。时间（分钟）10:0010;20 10;3010:5011;1012-0012） ）201CPUJ

39、 A11a11!B !A1 , i i11ci i i i iD :1进程就堵队列11L1!A!D1D1i1作业后备队列(1 ) 10 : 00 ,作业A到达并投入运行。(3 ) 10 : 20，作业B到达且优先权高于作业A ,故作业B投入运行而作业 A在就绪队列等待。(4 ) 10 : 30 ,作业C到达，因内存中已有两道作业，故作业C进入作业后 备队列等待。(5 ) 10 : 50 ,作业B运行结束，作业D到达，按SJF短作业优先算法，作 业D被装入内存进入就绪队列。而山于作业A的优先级高于作业D，故作业A投 入运行(6 ) 11 : 10，作业A运行结束，作业C被调入内存，具作业c的优先

40、级高 于作业D ,故作业C投入运行。(7 ) 12 : 00 ,作业c运行结束，作业D投入运行。(8 ) 12 : 20，作业D运行结束。作业号进入输入井时间8;00&208:208:308:35运行时间25分钟10分钟20分钟20分钟15分钟主存需求戳30302OK10K磴带需求1011打印机需求II00作业进入内存时间*运行结束时间A10:0011:10B10:2010;50C11:1012:00D10:5012:20各作业周转时间为：作业A 70 ,作业B 30 ,作业C 90 ,作业D 90 平均作 业周转时间为70分钟。20、某多道程序设计系统供用户使用的主存为100K，磁带机2台，

41、打印机1台。 采用可变分区内存管理，采用静态方式分配外围设备，忽略用户作业F0时间。 现有作业序列如下：作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业， 在主存中的各作业平分CPU时间.现求：(1 )作业被调度的先后次序(2 ) 全部作业运行结束的时间(3 )作业平均周转时间为多少(4 )最大作业周转时 间为多少答：(1 )作业调度选择的作业次序为：作业1、作业3、作业4、作业2和 作业5 .(2 )全部作业运行结束的时间9 : 30。(3 )周转时间：作业1为30分钟、作业2为55分钟、作业3为40分钟、 作业4为40分钟和作业5为55分钟。(4 )平均作业周转时间=

42、44分钟。()最大作业周转时间为55分钟。分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。8 : 00作业1到达，占有资源并调入主存运行。3455 58 : 20作业2和3同时到达，但作业2因分不到打印机，只能在后备队列等 待。作业3资源满足，可进主存运行，并与作业1平分CPU时间。8 : 30作业1在8 : 30结束，释放磁带与打印机。但作业2仍不能执行，因 不能移动而没有30KB的空闲区，继续等待。作业4在8 : 30到达，并进入主 存执行，与作业3分享CPU8 : 35作业5到达，因分不到磁带/打印机，只能在后备队列等待。9 : 00作业3运行结束，释放磁带机。此时作

43、业2的主存及打印机均可满足， 投入运行。作业5到达时间晚，只能等待。9 : 10作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。9： 13巧作业2运行结束，作业5投入运行。9 : 30作业全部执行结束。08:00I5K75KIOOK1&20创309:009; 109;1$21、某多道程序设讣系统采用可变分区内存管理，供用户使用的主存为200K , 磁带机5台。采用静态方式分配外圉设备，且不能移动在主存中的作业，忽略 用户作业I/O时间。现有作业序列如下：作业号进入输入井时间运行时间主存需求量磁带需求A8:3040分钟30K3B8:5025分钟120K1C9:0035分钟100K2

44、D9:0520分钟20K3E9:1010分钟60K1现求：（1 ） FIFO算法选中作业执行的次序及作业平均周转时间（2 ） SJF算 法选中作业执行的次序及作业平均周转时间（进程调度也采用FCFS ）作业作业1 3作业3、4J作业5I19 CPU!111作业1:作业21作业5打印机11J11J11111作业门作业4!1作业5111J1 r111腿帝机211I11作业3111111*CPUIldCPU11111作业】J111/2CPUCPU作业21/2CPU1/2CPU:作业3I1/2CPU1/2CPU作业4作业，1*11111111CPU_1111e1111111111119；;309; 1

45、09:159:008:35时何（分）& 308:208:00答：(1 ) FIFO算法选中作业执行的次序为：A、B、D、C和E作业平均周 转时间为63分钟(2 ) SJF算法选中作业执行的次序为：A、B、D、E和C。作业平均周转 时间为58分钟详细说明：1.先来先服务算法。说明：(1)8:30作业A到达并投入运行。注意它所占用的资源。(2)8:50作业B到达，资源满足进主存就绪队列等CPu o(3)9:00作业C到达，主存和磁带机均不够，进后备作业队列等待。(4 ) 9 : 05作业D到达，磁带机不够，进后备作业队列等待。后备作业队列 有C、D。( 5 ) 9 : 10作业A运行结束，归还资源

46、磁带，但注意主存不能移 动(即不能紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。 这时作业E也到达了，。也由于主存不够进入后备作业队列。此时作业D因资 源满足(主存磁带均满足)，进主存就绪队列等待。后备作业队列还有C、E o(6 ) 9 : 35作业B运行结束，作业D投入运行。这时作业C因资源满足而 调入主存进就绪队列等CPU。而作业E因磁带机不够继续在后备作业队列等待。(7 ) 9 : 55作业D运行结束，作业C投入运行。这时作业E因资源满足而 调入主存进就绪队列等CPU o(8 ) 10 : 30作业C运行结束，、作业E投入运行。(9 ) 10 : 40作业E运行结束。作卯D0

47、77/07/作业c20120作业ci jo/ 180作砂E1X0丄作业E%2001 U v200/作业A030作业A030作业A0 20Dx,作业B作业BJO作业B200/150200/ISO2008*308:509g9:O59:10302oe0201202009:359:5510:30时间CPU出帶机I檢带机2啟帝机2此带机4磁带机5作业A作业B作业Q作业D作业E作业A作业A作业AiCPU9：109：209：30作业B9:409:50!作业D作业|D作业D作业b后备认列后缶就绪筹待10:00 10:10 10:20 10:；作业C作业C作业ECPU作业执行次序进输入井时间装入主存时间开始执行

48、时间执行结束时间周转时间作业A8:30&308:309:1040（ （分）作业B8:508:509:109:3545作业D9：059:109:359活550作业C9:009:359:5510:3090作业E9:109:5510:3010:4090作业A8:40850 9：00命业B作业C就绻貓IL后备队列作业平均周转时间(40+45+50+90+90)/5=63 分钟2 短作业优先算法。说明：(1)8:30作业A到达并投入运行。注意它所占用的资源。(2)8:50作业B到达，资源满足进主存就绪队列等CPU。(3)9:00作业C到达，主存和磁带机均不够，进后备作业队列等待。(4 ) 9 : 05作

49、业D到达，磁带机不够，进后备作业队列等待。后备作业队列 有C 、D(5 ) 9 : 10作业A运行结束，归还资源磁带，但注意主存不能移动(即不能 紧缩)。作业B投入运行。作业C仍因主存不够而等在后备队列。这时作业E也 到达了，虽然该作业最短，也山于主存不够进入后备作业队列此时作业D因 资源满足(主存磁带均满脚，进主存就绪队列等待。后备作业队列还有C、E。(6 ) 9 : 35作业B运行结束，作业D投入运行。这时作业C和E资源均满 足，但按SJF应把作业E调入主存进就绪队列等CPU o而作业C因磁带机不够 继续在后备作业队列等待。(7 ) 9 : 55作业D运行结束，作业C调入主存进就绪队列等C

50、PU(8 ) 10 : 05作业E运行结束，作业C投入运行.(9 ) 10 : 40作业C运行结束。作业A030作业B150200/40000$9:350/20作业E80作业C1 wV2009:5510:0510:40作业执行次序进输入井时间装入主存时同开始执行时间执行结束时间周转时何作业A8:308:308:309:1040（ （分）作业B8:508:509;】09:3545作业D9:059:109:359:5550作业E9:109:359:5510:0555作业C9:00:9:5510:0510:40100作业平均周转时间(4045+50+55+100)/5=58 分钟上题中，若允许移动己

51、在主存中的作业，其他条件不变，现求：（1 ） FIFO算 法选中作业执行的次序及作业平均周转时间（2 ） SJF算法选中作业执行的次序 及作业平均周转时间？第三章同步、通讯与死锁1、有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理; P负责打印输出信息块。今提供；1)一个缓冲区，可放置K个信息块；2)二个缓冲区，每个可放置K个信息块； 试用信号量和P、V操作写出三个进程正确工作的流程。答：1 ) var B : array 0 , kT _ of item ;sread : semaphore : = k ;smanage : semaphore ： = 0 ;swrite

52、: semaphore : = 0 ;rptr : integer : = 0 ;mptr : integer : = 0 ;wptr : integer : = 0 ;x : itemcobeginprocess reader ; process manager ; process writer ;begin begin beginLI : read a message intox ; L2 : P ( smanage ) ; L3 : P ( swnte );P ( sread ) ; x:=Bmptr; x:=Bswrite:Brptr ：=x; mptr: = (mptr+l) mod

53、 k; wptr：二(wptr+1) mod k;Rptr: = (rptr+l) mod k; manage the message in x; V(sread):V(smanage); Bumptr:=x; print the message in x;Goto LI: V(swrite); goto L3;End; goto L2; end;End;coend2 ) var A , B :array 0 , k -1 Z of item ;sPutl : semaphore:=k;SPut2: semaphore:=k;sgetl : semaphore : = 0 ;sget2 : s

54、emaphore : = 0 ;putl : integer :二0 ;put2： integer : = 0 ;getl : integer :二0 ;get2 : integer : = 0 ;cobeginprocess reader ; processn manager; process Writer ;begin begin beginLI : read a message into x ; L2 : P ( sgetl ) : L3 : P ( sgetZ )P ( SPutl ) ; x :二 A getl ; x : = B get2;A putl:=x ; getl : (g

55、etl+1 ) mod k ; get2:= (get2 + 1 ) mod k ;Putl:=(putl+l) mod k; V(sputl): V(sput2);V(sgetl); manage the message into x; print the message in x;Goto LI: P (sput2); goto L3;Put2：=(put2+1) mod k;V(sget2);Goto L2;End;Coend2设有n个进程共享一个互斥段，如果：(1)每次只允许一个进程进入互斥段；(2 )每次最多允许m个进程(m簇n )同时进入互斥段。试问：所采用的信号量初值是否相同信号

56、量值的变化范围如何？答：所采用的互斥信号量初值不同。1)互斥信号量初值为1 ,变化范围为-n+l , 1 。当没有进程进入互斥段时，信号量值为1 :当有1个进程进入互斥段但没有进程 等待进入互斥段时，信号量值为0 :当有1个进程进入互斥段且有一个进程等待 进入互斥段时，信号量值为-1 ;最多可能有n-l个进程等待进入互斥段，故此 时信号量的值应为-(n - 1 )也就是-n+1 2 )互斥信号量初值为m ,变化范围为-n+m , m 。当没有进程进入互斥段时，信号量值为m :当有1个进程进入互斥段但没有进程 等待进入互斥段时，信号量值为m - 1 ：当有m个进程进入互斥段且没有一个进 程等待进

57、入互斥段时，信号量值为0 :当有m个进程进入互斥段且有一个进程等 待进入互斥段时，信号量值为一1 ;最多可能有n - m个进程等待进入互斥段， 故此时信号量的值应为- (n-m)也就是-n+m.3有两个优先级相同的进程Pl和P2,各自执行的操作如下，信号量S1和S2初值 均为0。试问Pl、P2并发执行后，x、y、z的值各为多少Pl: P2:Begin beginY:二1; x:二1;Y:=y+3; x:=x+5:V(S1); P(S1);Z:=Y+1; X:X+Y;P(s2); V(S2);Y：=z+y; z：=z+x;End end答：现对进程语句进行编号，以方便描述.Pl : P2 :be

58、gin beginy ： = 1 ； x ：=1 ;y :二y+3 ； x ： x+5 ;V(S1); P(S1);Z:Y+1 ； x ： X+Y :P(s2); V(S2);Y:=z+y; z： =Z+X；End end、和是不相交语句，可以任何次序交错执行，而结果是唯一的。接 着无论系统如何调度进程并发执行，当执行到语句 时，可以得到x二10 , y =4。按Bernstein条件，语句的执行结果不受语句的影响，故语句执行 后得到z二5。最后，语句和并发执行，这时得到了两种结果为：语句先执行：x =10 , y二9 , z二150语句先执行：x =10 , y =19 , z =15此外，

59、还有第三种情况，语句 被推迟，直至语句后再执行，于是依次执行以 下三个语句：z :二 y + 1 ;y : =Z 十 y ;这时Z的值只可能是y +1=5 ,故y二Z+Y二5 + 4二9,而x二10。第三种情况为：x二10 , Y二9 , Z = 5 o4有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个 表Lh包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座 位。试用：1 ）信号量和P、V操作；2 ）管程，来实现用户进程的同步算法。答：1）使用信号量和F、v操作：var name : array 1 lOOjof A ;A = record number

60、 : integer ;name： string ;endi； A T i n&me :null;)for i : = 1 to 100 do A i .number : mutex , seatcount : semaphore ;i : integer ； mutex :二 1 ; seatcount : cobeginprocess readeri ( var readename： string )(i=l , 2 )P ( seatcount )P (mutex ) for i ： = 1 to 100 do i+ if A i .name=null then A i .name： r