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

(word完整版)操作系统第五版费祥林_课后习题答案解析参考第一章 操作系统概论1、有一台计算机，具有IMB 内存，操作系统占用200KB ，每个用户进程各占200KB 。如果用户进程等待I/O 的时间为80 % ,若增加1MB 内存，则CPU 的利用率提高多少？答：设每个进程等待I/O 的百分比为P ，则n 个进程同时等待刀O 的概率是Pn ，当n 个进程同时等待I/O 期间CPU 是空闲的,故CPU 的利用率为1-Pn。由题意可知，除去操作系统，内存还能容纳4 个用户进程，由于每个用户进程等待I/O的时间为80 ， 故:CPU利用率l-（80)4 = 0.59 若再增加1MB 内存,系统中可同时运行9 个用户进程，此时：cPu 利用率l（1-80）9 = 0。87 故增加IMB 内存使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 的情况?若有，指出发生等待的时刻.答：画出两道程序并发执行图如下：（1）两道程序运行期间，CPU存在空闲等待，时间为100 至150ms 之间（见图中有色部分）(2)程序A 无等待现象,但程序B 有等待。程序B 有等待时间段为180rns 至200ms 间(见图中有色部分)3 设有三道程序，按A 、B 、C优先次序运行,其内部计算和UO操作时间由图给出。 试画出按多道运行的时间关系图（忽略调度执行时间）。完成三道程序共花多少时间？比单道运行节省了多少时间？若处理器调度程序每次进行程序转换化时lms ， 试画出各程序状态转换的时间关系图。答:1 ）忽略调度执行时间，多道运行方式（抢占式）：?抢占式共用去190ms ，单道完成需要260ms ，节省70ms 。忽略调度执行时间，多道运行方式（非抢占式）: 非抢占式共用去180ms ，单道完成需要260ms ，节省80ms 。2 ）调度执行时间1ms ， 多道运行方式（抢占式）: 调度执行时间ITns ，多道运行方式（非抢占式): 4在单CPU 和两台 I/O（ I1 ， 12 ）设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下：Jobl : I2 （ 30ms ）、CPU ( 10ms ）、I1 （ 30ms ）、CPU （ 10ms ）、I2 ( 20ms ) Job2 ： I1 （ 20ms ）、CPU （ 20ms ）、I2 ( 40 ms ) JOb3 : CPU （ 30ms )、I1 ( 20ms ）、CPU ( 10ms ）、I1 （ 10ms ） 如果CPU 、I1 和I2 都能并行工作，优先级从高到低为Jobl 、Job2 和Job3 ,优先级高的作业可以抢占优先级低的作业的CPU ，但不抢占I1和I2 。试求：（ l )每个作业从投入到完成分别所需的时间。（2 )从投入到完成CPU 的利用率.（3 )I2设备利用率。答：画出三个作业并行工作图如下(图中着色部分为作业等待时间）: ,( 1 ) Job1 从投入到运行完成需110ms ， Job2 从投入到运行完成需90ms ， Job3 从投入到运行完成需110ms. CPU 空闲时间段为：60ms 至70ms ， 80ms 至90ms ， 100ms 至110ms 。所以CPU 利用率为（11030）/10 = 72.7 。设备I1 空闲时间段为：20ms 至40ms ， 90ms 至100ms,故I1的利用率为 (11030）/l10 = 72 。 7 %。 设备I2 空闲时间段为:30ms 至50ms，故I2的利用率为（11020） / 110 = 81.8 。 5 在单CPU 和两台I/O（ I1 , 12 ）设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨迹如下:Jobl : I2 （ 30ms )、CPU （ 10rns )、I1 （ 30ms ）、CPU （ 10ms ) Job2 : I1 （ 20ms ）、CPU ( 20ms ）、I2 ( 40ms ) Job3 ： CPU ( 30ms ）、I1 ( 20ms ) 如果CPU 、I1和I2 都能并行工作，优先级从高到低为Job1 、Job2和Job3 ，优先级高的作业可以抢占优先级低的作业的CPU 。 试求：（ l ）每个作业从投入到完成分别所需的时间 ( 2 ）每个作业投入到完成CPU 的利用率。 （3 ）I/0设备利用率. 答:画出三个作业并行工作图如下（图中着色部分为作业等待时间）: （ 1 ) Job1从投入到运行完成需80ms , Job2 从投入到运行完成需90ms , Job3 从投入到运行完成需90ms 。( 2 ） CPU 空闲时间段为：60ms 至70ms , 80ms 至90ms 。所以CPU利用率为（ 90-20 ) / 90 = 77.78 。（ 3 ）设备I1 空闲时间段为：20ms 至40ms ，故I1 的利用率为（9020 ) / 90 = 77 . 78 。设备I2 空闲时间段为：30ms 至50ms ，故I2 的利用率为（9020 ) / 90=77。78 。6 若内存中有3 道程序A 、B 、C ，它们按A 、B 、C 优先次序运行.各程序的计算轨迹为：A ：计算（20 ）、I/O( 30 ）、计算（10 ） B ：计算（40 ）、I/O( 20 ）、计算（10 ) c ：计算（10 )、I/O （ 30 )、计算（20 ) 如果三道程序都使用相同设备进行I/O（即程序用串行方式使用设备，调度开销忽略不计）。试分别画出单道和多道运行的时间关系图。两种情况下，CPU 的平均利用率各为多少？答：分别画出单道和多道运行的时间图( 1 )单道运行时间关系图 单道总运行时间为190ms 。CPU 利用率为（19080 ）/190 = 57.9 % 单道运行时间关系图 多道总运行时间为140ms 。CPU 利用率为(140-30 ） / 140 = 78.6 7 若内存中有3 道程序A 、B 、C ，优先级从高到低为A 、B 和C ,它们单独运行时的CPU 和I/O 占用时间为：如果三道程序同时并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先级与I/O 设备无关。试画出多道运行的时间关系图，并问最早与最迟结束的程序是哪个？每道程序执行到结束分别用了多少时间？计算三个程序全部运算结束时的CPU 利用率?答：画出三个作业并发执行的时间图： （ l ）最早结束的程序为B ，最后结束的程序为C 。 ( 2 ）程序A 为250ms 。程序B 为220ms 。程序C 为310ms . ( 3 ) CPU 利用率为（310 -120 ) / 310 = 61.3 % 有两个程序，A 程序按顺序使用：（ CPU)10 秒、(设备甲）5 秒、（CPU）5 秒、（设备乙）10 秒、（CPU)10 秒。B程序按顺序使用：(设备甲）10 秒、（CPU)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 ，所以，时钟周期为：l / 60s = 50/3ms 。在每个时钟周期中，CPU 花2ms 执行中断任务。所以,CPU 用于时钟中断处理的时间比率为：2(50/3）=6/50 = 12.第二章 处理器管理1。下列指令中哪些只能在核心态运行?(l）读时钟日期;（2）访管指令；(3）设时钟日期；（4）加载PSW； （5）置特殊寄存器：(6）改变存储器映象图；(7）启动I/O指令.答：（ 3 ） ， ( 4 ） , （ 5 ) , ( 6 ） ， （ 7 ） .2 假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O 繁重型作业有利，但并不是永远不受理“处理器繁重”型作业。答：因为I/O繁忙型作业忙于I/O，所以它CPU 用得少,按调度策略能优先执行.同样原因一个进程等待CPU 足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。3 并发进程之间有什么样的相互制约关系？下列日常生活中的活动是属哪种制约关系:(1)踢足球，（2）吃自助餐，（3）图书馆借书，(4）电视机生产流水线工序。答:并发进程之间的基本相互制约关系有互斥和同步两种.其中（1）、（3)为互斥问题(2)、(4）为同步问题。4 在按动态优先数调度进程的系统中,每个进程的优先数需定时重新计算.在处理器不断地在进程之间交替的情况下，重新计算进程优先数的时间从何而来？答：许多操作系统重新计算进程的优先数在时钟中断处理例程中进行,由于中断是随机碰到哪个进程,就插入哪个进程中运行处理程序,并把处理时间记在这个进程的账上。5 若后备作业队列中等待运行的同时有三个作业J1 、J2、J3 ，已知它们各自的运行时间为a 、b 、c，且满足a b c，试证明采用短作业优先算法调度能获得最小平均作业周转时间。答：采用短作业优先算法调度时，三个作业的总周转时间为：Tl = = a + （ a +b ) + ( a + b + c ) = 3a + 2b + c 若不按短作业优先算法调度，不失一般性，设调度次序为：J2 、J1 、J3 。则三个作业的总周转时间为：T2=b(ba ) （ba + c ) = 3b + 2a + c 令- 式得到：T2 - Tl = b- a 0 可见，采用短作业优先算法调度才能获得最小平均作业周转时间。 6、若有一组作业J1 ， ，Jn ，其执行时间依次为S1 ， , Sn .如果这些作业同时到试找出一种作业调度算法到达系统,并在一台单CPU 处理器上按单道方式执行。使得平均作业周转时间最短。答：首先，对n 个作业按执行时间从小到大重新进行排序，则对n 个作业:J1 ， ，Jn ， 创门的运行时间满足：S1S2 S (n-l ) Sn 。那么有：由于任何调度方式下,S1 + S2 + S3Sn为一个确定的数，而当S1 S2 S( n 1 ） Sn 时才有：0*S1+1*S2+2*S3+(n1）Sn的值最大，也就是说，此时T 值最小。所以，按短作业优先调度算法调度时，使得平均作业周转时间最短。7、 假定执行表中所列作业，作业号即为到达顺序，依次在时刻0 按次序1 、2 、3 、4 、5 进入单处理器系统.（1）分别用先来先服务调度算法、时间片轮转算法、短作业优先算法及非强占优先权调度算法算出各作业的执行先后次序（注意优先权高的数值小)； （2）计算每种情况下作业的平均周转时间和平均带权周转时间。 （ 1 ）采用FCFS 算法调度作业，运作情况： （ 2 ）采用双算法调度作业，若令时间片长l ，各作业执行情况为:1 、2 、3 、4 、5 、l 、3 、5 、1 、5 、1 、5 、1 、5 、1 、l 、l 、1 、1 . ( 3 ）采用SJF 算法调度作业，运作情况： ( 4 ）采用非剥夺优先权算法调度作业,运作情况：8 对某系统进行监测后表明平均每个进程在I/O 阻塞之前的运行时间为T 。一次进程切换的系统开销时间为S 。若采用时间片长度为Q 的时间片轮转法，对下列各种情况算出CPU 利用率。9 有5 个待运行的作业,各自预计运行时间分别是：9 、6 、3 、5 和x ，采用哪种运行次序使得平均响应时间最短?答：按照最短作业优先的算法可以使平均响应时间最短.x 取值不定,按照以下情况讨论：10.有5 个批处理作业A 到E 均己到达计算中心,其运行时间分别2 、4 、6 、8 和10 分钟:各自的优先级分跳狠掀完为、飞、飞、氏积5 、这里5 为最高级.对于1） 时间片轮转算法、2)优先数法、3）短作业优先算法、4）先来先服务调度算法(按到达次序C 、D 、B 、E 、A) ，在忽略进程切换时间的前提下，计算出平均作业周转时间。（对l）每个作业获得相同的2 分钟长的时间片；对2)到4）采用单道运行，直到结束。）答：（ l ) FCFS 调度算法 （ 2 )优先级调度算法( 3 ）时间片轮转法按次序ABCDEBCDECDEDEE 轮转执行。( 4 ) SJF调度算法 11、 有5 个批处理作业A 到E 均已到达计算中心，其运行时间分别10 、6 、2 、4 和8 分钟；各自的优先级分别被规定为3 、5 、2 、1 和4 ,这里5 为最高级.若不考虑系统切换开销，计算出平均作业周转时间。（1) FCFs （按A 、B 、C 、D 、E ) ； (2） 优先级调度算法，（3)时间片轮转法（每个作业获得相同的2 分钟长的时间片）。答：( 1 ） FCFS 调度算法 （ 2 ）优先级调度算法( 3 ）时间片轮转法 按次序ABCDEABDEABEAEA 轮转执行。 作业 执行时间 等待时间 周转时间 带权周转时间 ABCDE 10 6 2 48 20l64 l220 302261628 33 .6634 3. 5 作业平均周转时间作业平均带权周转时间 T = ( 30 + 22 + 6 + 16 + 28 ） / 5 = 20。4W = ( 3 + 3.66 + 3 +4 + 3.5 ） / 5 = 3.43 12 (l)假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输出为主,你将怎样赋予它们占有处理器的优先级？为什么?（2)假定一个处理器正在执行三道作业,一道以计算为主，第二道以输入输出为主，第三道为计算与输入输出均匀。应该如何赋予它们占有处理器的优先级使得系统效率较高？答:处理器调度算法会考虑以下因素：作业响应时间要求；让CPU 尽量和外围设备并行工作；限制一个计算进程长时间霸占处理器。因而，（ 1 ) FO 为主作业优先级高。（2 ） 输入输出为主作业优先级最高，输入输出均匀的作业其次,而计算为主作业的优先级最低。 13 请你设计一种先进的计算机体系结构,它使用硬件而不是中断来完成进程切换，则CPU 需要哪些信息？请描述用硬件完成进程切换的工作过程. 答：该计算机有一个专用硬件寄存器，它始终存放指向当前运行进程的PCB 的指针。当系统中发生了一个事件,如FO 结束事件，CPU 便可把运行进程的上下文保存到专用硬件寄存器指针指向的PCB 中保护起来，然后,CPU 转向中断向量表，找到设备中断处理程序入口,让专用硬件寄存器指针指向（设备)中断服务例程，于是，便可启动中断服务例程工作。 14 设计一条机器指令和一种与信号量机制不同的算法，使得并发进程对共享变量的使用不会出现与时间有关的错误。解：（ l ）设计机器指令。设计一条如下的测试、比较和交换”三地址指令,提供了一种硬件互斥解决方案： TC&S R1R3B2D2该指令的功能如下：l ) C 为一个共享变量，由地址2 、即变址（B2 ） + D2 给出， (2 ）（Rl )与（C )比较， （3 ）如果（Rl ) = （ C )则(R3）C ，并置条件码为00” , 如果(R1 )(c ）则（C )Rl ，并置条件码为”01 . （ 2 ）编写进程访问共享变量的程序.对每个访问共享变量C 的进程,编写访问共享变量的程序段为: 陆界区程序 说明 ( C ）Rl ；loop2 ： （ R1 ) R3 ; Add /decrease R3 ;TC & S ；R( condition = 01 ) loop2 ; 共享变量C 的值保护到RI 中。 Rl 的值传送到R3 中，进程修改共享变量时,先对R3 操作（不是直接操作C ）。 R3 加1 减1 ，进程归还申请由共享变量C 代表的共享资源(假定每次一个）。 执行”测试、比较和交换”指令。 条件码01 ，转向循环loop2 ；否则离开临界区。 （ 3 ）程序执行说明。此解与互斥使用共享变量的思路绝然不同，并发运行的进程可不互斥地访问它们的共享变量。此方案认为造成共享变量C 值错误的原因在于：一个进程（Pl ）在改变C 值的过程中，另一个进程伊2 ）插进来也改变了C 的值，而本进程（Pl）却不知道，造成了c 值结果不正确。如果有办法使本进程口1 ）能知道C 值是否改变，改变的话在继承改变了的C 值的基础上，再作自己的改变操作，则就不会导致共享变量C 值的错误。为此，本解决方案中，当一个进程l）准备改变C 值时，先把C 的值保护在Rl 中，然后，通过R3 来改变共享变量C 的值.当要把新的值（即R3 内的值）送C之前，先要判断一下在本进程（P1 ）工作期间是否有别的进程口2 ）插进来也改变了C 的值（并发进程P1 、P2 的执行完全会造成这种情况），方法是：将扭1 )中被保护的C 的原来值，与C 的当前值比较，若相等，说明C 值未被改变过，则将本进程(Pl ）修改过的新值送C (即（R3 ） 一C ) ；若不相等,说明C 值在工作期间被改变过，则应该继承C 的新值（即（C )一Rl ）并且返回到loop2 处重新对C值计数，以此保证C值的最终结果的正确性。这里提及进程工作期间”指的是一个进程从开始至结束对共享变量C 值的操作的这段时间，也就是执行进程, I 晦界区”这段程序的时间.此外，在进程进入临界区之前，应等待直到C 为非。（即有资源可用）为止。( 4 ）举例。假定系统中有静态分配资源磁带机共3 台，被N 个进程共享，由共享变量C 来代表可用磁带机台数,其初值为3 。现有并发进程P1 和P2 均申请使用磁带机，执行临界区程序。进程Pl 执行临界区程序( C ）R1 ;因（C)=3 ，故（R1) = 3 。 loop2: ( Rl ）R3 因(R1 ） = 3 ，故（R3 )当前也3 . decrease R3 ：申请使用磁带机，做减1 操作，故(R3 )=2. TC & S 执行”测试、比较和交换，, TC & S 指令。如果R1=（C ）则（R3 )C,即(C）=2 ,并置条件码为”00 , 跳出临界区程序，去使用磁带机。如果（Rl ） （C) ，例如，( C )=2 ,说明进程P2 抢先申请了磁带机，所以，C 与保护在R1 中的值不一样了（C 的值必 小于Rl 的值）,应以C 的当前值为准，执行（C ） Rl ( R1 此时变为2 ) ，并置条件码为”01 ，转向foopZ 。于是伍1 ） = 2 , 跟着(R3 卜2 。接着卿）减1 后应l 了。再执行TC S 时，由于伍1 卜（C ) = 2 ，会使C 变为1 。 r ( conditio 二01 ） loop2 ； 巧单道批处理系统中，下列三个作业采用先来先服务调度算法和最高响应比优先算法进行调度，哪一种算法性能较好？请完成下表： 作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 12310 : 0010 ： 1010 : 252 : 001 : 000 ： 25平均作业周转时间=平均作业带权周转时间W =答: 可见HRRF 比FIFO 要好 16 若有如表所示四个作业进入系统，分别计算在FCFS 、S 开和HRR 卫算法下的平均周转时间与带权平均周转时间.（时间以十进制表示） 答： 17 Kleinrock 提出一种动态优先权算法：进程在就绪队列等待时，其优先权以速率a变化；当进程在处理器上运行，时其优先权以速率p 变化。给参数a，b 赋以不同值可得到不同算法.（l )若abc是什么算法？（ 2 ）若abc是什么算法 答：（ l ）是先进先出算法。因为在就绪队列中的进程比在CPU 上运行的进程的优先数提高得快，故进程切换时,先进入就绪队列的进程优先权就越高.( 2 ）是后进先出算法.因为在就绪队列中的进程比在CPU 上运行的进程的优先权下降得快,故后进入就绪队列的进程此先进入的进程的优先权高。 18 有一个四道作业的操作系统，若在一段时间内先后到达6 个作业，它们的提交和估计运行时间由下表给出： 系统采用SJF 调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作业抢占。（l ）分别给出6 个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。（2 )计算平均作业周转时间.答 说明:( 1 ） J2 到达时抢占J1 ; J3 到达时抢占J2 。 （ 2 ）但J4 到达时，因不满足SJF ，故J4 不能被运行，J3 继续执行5 分钟。 ( 3 ）由于是4 道的作业系统,故后面作业不能进入主存而在后备队列等待，直到有作业结束。 ( 4 ）根据进程调度可抢占原则,J3 第一个做完。而这时J5 、J6 均己进入后备队列，而J5 可进入主存。 ( 5 )因J5 最短，故它第二个完成。这时J6 方可进入主存。因J6 最短，故它第三个完成。 ( 6 ）然后是：J4 、J2和J1 ( 7 ） T =( 155 + 95 + 20 + 55 + 15 + 20 ) / 6 = 60 19、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。（ 1 ）列出所有作业进入内存时间及结束时间.（ 2 ）计算平均周转时间.答：每个作业运行将经过两个阶段：作业调度(SJF 算法）和进程调度(优先数抢占式).另外，批处理最多容纳2 道作业，更多的作业将在后备队列等待。（ l ） 10 : 00 ，作业A 到达并投入运行。 （ 3 ) 10 ： 2O ，作业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 的优先级高于作业D , 故作业C 投入运行。 （ 7 ) 12 ： 00 ，作业c 运行结束，作业D 投入运行。 （ 8 ） 12 : 20 ，作业D 运行结束。 各作业周转时间为：作业A 70 ，作业B 30 ,作业C 90 ，作业D 90 。平均作业周转时间为70 分钟。 20 、某多道程序设计系统供用户使用的主存为100K ，磁带机2 台，打印机1 台。采用可变分区内存管理，采用静态方式分配外围设备,忽略用户作业FO 时间.现有作业序列如下： 作业调度采用FCFS 策略，优先分配主存低地址区且不准移动已在主存的作业,在主存中的各作业平分CPU 时间现求：( l ）作业被调度的先后次序？（ 2 ）全部作业运行结束的时间？( 3 ）作业平均周转时间为多少?( 4 ）最大作业周转时间为多少？ 答:( l ）作业调度选择的作业次序为：作业1 、作业3 、作业4 、作业2 和作业5 . ( 2 )全部作业运行结束的时间9 ： 30 。 ( 3 ）周转时间:作业1 为30 分钟、作业2 为55 分钟、作业3 为40 分钟、作业4 为40 分钟和作业5 为55 分钟。 （ 4 ）平均作业周转时间44 分钟. ( 5 )最大作业周转时间为55 分钟。 分析:本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争.8 ： oo 作业1 到达，占有资源并调入主存运行。 8 ： 20 作业2 和3 同时到达，但作业2 因分不到打印机，只能在后备队列等待.作业3 资源满足,可进主存运行，并与作业1 平分CPU 时间。 8 : 30 作业1 在8 : 30 结束，释放磁带与打印机.但作业2 仍不能执行，因不能移动而没有30KB 的空闲区，继续等待.作业4 在8 ： 30 到达，并进入主存执行，与作业3 分享CPU8 : 35 作业5 到达，因分不到磁带/打印机，只能在后备队列等待。 9 ： 00 作业3 运行结束，释放磁带机。此时作业2 的主存及打印机均可满足,投入运行。作业5 到达时间晚，只能等待. 9 ： 10 作业4 运行结束，作业5 因分不到打印机，只能在后备队列继续等待. 9:15巧作业2 运行结束，作业5 投入运行。 9 : 30 作业全部执行结束。 21、某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K ，磁带机5 台。采用静态方式分配外围设备,且不能移动在主存中的作业，忽略用户作业I/O时间.现有作业序列如下：现求：( l ） FIFO 算法选中作业执行的次序及作业平均周转时间？（ 2 ） SJF 算法选中作业执行的次序及作业平均周转时间？（进程调度也采用FCFS ) 答：( 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 。( 3 ） 9 : 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待.( 4 ） 9 ： 05 作业D 到达，磁带机不够，进后备作业队列等待。后备作业队列有C 、D 。（ 5 ) 9 : 10 作业A 运行结束,归还资源磁带，但注意主存不能移动（即不能紧缩）。作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了，。也由于主存不够进入后备作业队列。此时作业D 因资源满足（主存磁带均满足），进主存就绪队列等待。后备作业队列还有C 、E 。（ 6 ) 9 : 35 作业B 运行结束，作业D 投入运行。这时作业C 因资源满足而调入主存进就绪队列等CPU .而作业E 因磁带机不够继续在后备作业队列等待。( 7 ) 9 : 55 作业D 运行结束,作业C 投入运行。这时作业E 因资源满足而调入主存进就绪队列等CPU 。( 8 ) 10 : 30 作业C 运行结束，、作业E 投入运行。( 9 ） 10 : 40 作业E 运行结束。2 短作业优先算法。说明：（ 1 ) 8 ： 30 作业A 到达并投入运行。注意它所占用的资源。 （ 2 ) 8 ： 50 作业B 到达，资源满足进主存就绪队列等CPU 。 （ 3 ) 9 ： 00 作业C 到达，主存和磁带机均不够，进后备作业队列等待。 ( 4 ） 9 : 05 作业D 到达,磁带机不够,进后备作业队列等待。后备作业队列有C 、D 。 ( 5 ) 9 : 10 作业A 运行结束，归还资源磁带，但注意主存不能移动（即不能紧缩）.作业B 投入运行。作业C 仍因主存不够而等在后备队列。这时作业E 也到达了,虽然该作业最短，也由于主存不够进入后备作业队列此时作业D 因资源满足（主存磁带均满脚，进主存就绪队列等待。后备作业队列还有C 、E 。 （ 6 ） 9 : 35 作业B 运行结束，作业D 投入运行.这时作业C 和E 资源均满足，但按SJF 应把作业E 调入主存进就绪队列等CPU 。而作业C 因磁带机不够继续在后备作业队列等待. ( 7 ） 9 : 55 作业D 运行结束，作业C 调入主存进就绪队列等CPU .（ 8 ） 10 ： 05 作业E 运行结束，作业C 投入运行 ( 9 ) 10 ： 40 作业C 运行结束.上题中，若允许移动己在主存中的作业，其他条件不变，现求：( l ) FIFO 算法选中作业执行的次序及作业平均周转时间？（ 2 ） SJF 算法选中作业执行的次序及作业平均周转时间?答：FIFO 算法选中作业执行的次序为：SJF 算法选中作业执行的次序为：（l ) A 、B 、D 、E 和C.作业平均周转时间为58 分钟。( 2 ） A 、B 、E 、D 和C.作业平均周转时间为56 分钟.与上题类同,详细说明略. 23、设计一个进程定时唤醒队列和定时唤醒处理程序：（ l ）说明一个等待唤醒进程入队v 的过程。（2 ）说明时钟中断时，定时唤醒处理程序的处理过程。（3 )现有进程P1 要求20 秒后运行，经过40 秒后再次运行；PZ 要求25 秒后运行；P3 要求35 秒后运行，经过35 秒后再次运行；P4 要求60 秒后运行。试建立相应的进程定时唤醒队列。答：组织如下的定时唤醒队列 .（ l ）当一个需定时唤醒的进程要入队时，根据它要唤醒的时间，被扦入队列的适当位置,注意，唤醒时间按增量方式存放。（ 2 ）每当时钟中断时，时钟中断例程判别把队列中的第一个进程的时间量减1 ，直到该值为时唤醒进程工作。同时队列中下一个进程成为队列头。24、一个实时系统有4 个周期性事件，周期分别为50 、100 、300 和250ms 。若假设其处理分别需要35 、20 、10 和X ms,则该系统可调度允许的X值最大为多少?实时任务可调度应满足： 35 / 50 +20/100 + 10/300 +X/250l X250(l-28/30) = 2500.067 = 16.75ms第三章 同步、通讯与死锁1、 有三个并发进程:R 负责从输入设备读入信息块，M 负责对信息块加工处理；P 负责打印输出信息块。今提供； l ）一个缓冲区，可放置K 个信息块； 2 ）二个缓冲区，每个可放置K 个信息块; 试用信号量和P 、V 操作写出三个进程正确工作的流程。答：1 ） var B ： array 0 , k1 of item ; sread ： semaPhore : = k ； smanage ： semaPhore : = 0 ； swrite ： semaphore ： = 0 ； rptr ： integer : = O ； mptr ： integer : = O ； wptr ：integer ： = 0 ； x : itemcobegin process reader ; process manager ; process writer ; begin begin begin LI ： read a message intox ； L2 : P （ smanage ) ； L3 : P （ swnte ) ；P （ sread ） ； x：=Bmptr； x:=Bswrite；Brptr:=x； mptr：=（mptr+1) mod k； wptr：=(wptr+1） mod k;Rptr：=(rptr+1) mod k; manage the message in x; V(sread)；V（smanage）; Bmptr：=x; print the message in x；Goto L1; V（swrite）； goto L3；End; goto L2； end；End;coend2 ) var A , B ：array 0 , k l of item ; sPut1 ： semaphore:=k； SPut2： semaPhore:=k； sget1 : semaPhore : = 0 ; sget2 : semaphore : = 0 ; put1 ：integer ：=O ； put2:integer ： = 0 ； get1 ：integer ：=O ； get2 : integer ： = O ; cobegin process reader ; processn manager; process Writer ； begin begin begin Ll : read a message into x ; L2 ： P ( sgetl ） ； L3 ： P （ sgetZ ) ； P （ SPut1 ） ； x : = A get1 ； x ： = B get2; A put1:=x ; get1 ：(get1+1 ） mod k ； get2:=（get2 + l ） mod k ;Put1：=(put1+1） mod k; V(sput1); V(sput2）;V(sget1)； manage the message into x; print the message in x；Goto L1； P（sput2); goto L3;Put2：=（put2+1） mod k;V(sget2）；Goto L2；End;Coend2 设有n 个进程共享一个互斥段，如果：( 1 )每次只允许一个进程进入互斥段；（ 2 ）每次最多允许m 个进程（m 簇n ）同时进入互斥段。试问：所采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用的互斥信号量初值不同。1 ）互斥信号量初值为1 ，变化范围为nl ， 1 。当没有进程进入互斥段时，信号量值为1 ；当有1 个进程进入互斥段但没有进程等待进入互斥段时，信号量值为O ；当有1 个进程进入互斥段且有一个进程等待进入