计算机操作系统 课后答案(刘循 朱敏 文艺 著) 人民邮电出版社.pdf

练习答案 练习 1 1.1-1.10 题解见书 1.11有一台输入设备和一台输出设备的计算机系统上，运行有两道程序。两道 程序投入运行情况如下： 程序 1 先开始运行，其运行轨迹为：计算 50ms、输出 100ms、计算 50ms、 输出 100ms，结束； 程序 2 后开始运行，其运行轨迹为：计算 50ms、输入 100ms、计算 100ms、 结束。 1. 忽略调度时间， 指出两道程序运行时， cpu 是否有空闲？在哪部分空闲？ 2. 有无等待 cpu 的情况？如果有，发生在哪部分？ 题解: 由题画出 cpu 利用图如下： 由图可知，1.cpu 有空闲，在 100ms150ms 时间段是空闲的。 2.程序 1 无等待时间， 而程序 2 在一开始的 0ms50ms 时间段会等待。 1.12在计算机系统上运行三道程序，运行次序为程序 1、程序 2、程序 3。 程序 1 的运行轨迹为：计算 20ms、输入 40ms、计算 10ms。 程序 2 的运行轨迹为：计算 40ms、输入 30ms、计算 10ms。 程序 3 的运行轨迹为：计算 60ms、输入 30ms、计算 20ms。 忽略调度时间，画出三道程序运行的时间关系图；完成三道程序共花多少时间？ 与单道程序比较，节省了多少时间？ 解答：三道程序运行，完成三道程序共花 170ms。与单道程序（260ms）比较， 节省了 90ms。 （始终按照 1-2-3 的次序，即程序 1程序 2程序 3程序 1程序 2（在程 序 3 运行前会停 10ms 等待输入完成）程序 3。 （如果不是按照程序 1、2、3 的次序完成则会有多种情况。 ） 1.13在计算机系统上有两台输入/输出设备，运行两道程序。 程序 1 的运行轨迹为： 计算 10ms、 输入5ms、 计算5ms、 输出10ms、 计算10ms。 程序 2 的运行轨迹为： 输入 10ms、 计算10ms、 输出5ms、 计算5ms、 输出10ms。 在顺序环境下，先执行程序 1，再执行程序 2，求总的 cpu 利用率为多少？ 题解：由题画出 cpu 利用图如下： 由图可知，在总共 80ms 的时间里，cpu 空闲时间为 40ms，即： cpu 利用率=40ms/80ms*100%=50% 1.14一个计算机系统有足够的内存空间存放 3 道程序， 这些程序有一半的时间 在空闲等待 i/o 操作。问多大比例的 cpu 时间被浪费掉了。 题解：由题画图如下： 因为每个程序有一半的时间在等待 i/o 操作，所以在并发状态下，程序 1、程序 2、程序 3 所占时间比依次减半（如上图） ，所以浪费的时间比例为 1/8。 练习 2 2.1-2.17 题解见书 218 某系统中进程状态变化如图 2.22 所示，当对系统中的进程进行观察时， 发现某一进程产生的一次状态变化会引起另一进程发生状态变化。 （1） 在什么情况下， 一个进程的状态变化 3 能够立即引起另一进程的状态变化1？ （2） 在什么情况下， 一个进程的状态变化 2 能够立即引起另一进程的状态变化1？ （3）进程的状态变化 3 是否可能引起另一进程的状态变化 2？进程的状态变化 3 是否可能引起另一进程的状态变化 1？ 解答： （1）当就绪队列中还存在其它进程的情况下，一个进程的状态变化 3 能够立即 引起另一进程的状态变化 2。 （2）当就绪队列中还存在其它进程的情况下，一个进程从运行状态变化到就绪 状态后，另一个就绪进程能够从就绪状态变为运行状态。 （3）不可能，可能。 219 分别写出相应的程序来描述图 2.23 中的前趋图。 解答 s1 s2 s3 s4 s5 s6 s7 程序：s1:a:=x+1 s2:b:=a+2 s3:c:=a+3 s4:d:=b+4 s5:e:=b+c s6:f:=e+5 s7:g=e+6 s1 s2 s3 s4 s5 s6 s7 程序：s1:a:=x+1 s2:b:=a+2 s3:c:=a+3 s4:d:=b+4 s5:e:=b+c s6:f:=d+e s7:g:=c+e 2.20假设在一个系统中，新进程以每分钟 8 个进程的速率到达，每个进程请 求服务的平均时间为 6s，估计在一个单处理器系统中 cpu 忙的时间比率。 如果新进程以每分钟 10 个进程的速率到达，每个进程请求服务的平均时间 也为 6s，估计在一个单处理器系统中 cpu 忙的时间比率。 如果新进程创建以每分钟超过 10 个进程的速率到达， 每个进程请求服务的 平均时间为 6s，估计在一个单处理器系统中 cpu 忙得时间比率，并解释此时的 情况。 解答： 因为新进程每分钟 8 个进程的速率到达，每个进程之间达到的时间间隔为 7.5s。由于每个进程占用 6s 的 cpu 时间。所以，1 分钟之内 cpu 的空间时间为 8*1.5s=12s。cpu 的利用率为 48/60=0.8，即 80%。 因为新进程每分钟 10 个进程的速率到达，每个进程之间达到的时间间隔为 6s。由于每个进程占用 6s 的 cpu 时间。所以，1 分钟之内 cpu 的空间时间为 0s。 cpu 的利用率为 100%。 如果新进程创建以每分钟超过 10 个进程的速率到达，每个进程请求服务的 平均时间为 6s，则请求服务时间会大于 1 分钟，cpu 一直会处于繁忙，所以 cpu 忙的时间比率同样为 100%。 2.21一个系统中有 4 个进程， 进程 p1 要求 20s 后运行， 经过 40s 后再次运行 ； 进程 p2 要求 25s 后运行；进程 p3 要求 35s 后运行，经过 35s 后再次运行；进程 p4 要求 60s 后运行。进程在阻塞队列等待被唤醒后运行，试创建进程的唤醒队 列。 解答：进程的唤醒队列为 p1p2p3p4p1p3 注意：“经过 40s 后再次运行”表示第 1 次运行完成后再过 40s。 2.22如果线程是在用户空间线程库中实现，解释为什么当进程中的一个线程 阻塞时，进程内的所有其它线程都会阻塞？如果线程是在内核空间中实现,而进 程内的一个线程阻塞不会引起进程内的其他线程被阻塞，为什么？ 解答： 用户级线程由用户空间运行的用户级线程库实现。 当一个应用程序提交给操 作系统后，操作系统首先为该应用程序建立一个内核管理进程，然后用户级线程 库为该进程创建一个或多个用户级线程，但内核并不知道用户空间线程的活动， 内核只是以进程为单位， 实现进程状态的转换， 因此当进程中的一个线程阻塞时 ， 进程内的所有其它线程都会阻塞。 如果线程是在内核空间中实现的，这些内核级线程都由内核创建和控制管 理，内核为整个进程及进程中的所有线程维护现场信息，内核的调度是在线程的 基础上进行的，因而进程的一个线程阻塞不会引起进程内的其他线程被阻塞。 练习 3 3.1-3.12 题解见书 3.13 证明作业调度算法中短作业优先调度算法具有最小平均等待时间。 证明:假设在作业队列中等待运行的作业有 n 道,分别为 n0，n1，n2，nn-1， 它们的运行时间分别为 t0，t1，tn-1，且满足 t0t10 说明任何一种作业调度顺序的作业的平均等待时间都大于按照短作业优先的作 业的平均等待时间。 3.14 假设在一个处理器上执行 5 个作业，作业到达的次序和需要执行的时间分 别为：j0（75ms） 、j1（15ms） 、j2（5ms） 、j3（15ms） 、j4（45ms） ， 假定系统中使用 fcfs 调度算法，作业 j3 的周转时间是多少？作业的平均等 待时间是多少？ 答： 3.15 在单道批处理系统中，三个作业的提交时间分别为：10：00、10：10、10： 20，需要执行时间分别为：2 小时、1 小时、0.5 小时，分别按照短作业优先调 度算法和高响应比优先调度算法进行调度，比较哪一种调度算法更好？ 解： (1) 不抢占： 执行顺序为 a，c，b 平均周转时间： （120+130+200）/3=150（min） 平均带劝周转时间： （120/120+130/30+200/60）/3 =26/9 抢占： a（10：10） ，b（10：20） ，c(10:50),b(11:40),a(13:30) 平均周转时间： （210+90+30）/3=110（min） 平均带劝周转时间： （210/120+90/60+30/30）/3 =510/360=17/12 (2) 响应比高者优先调度算法不会抢占，因此，只存在这样一种情况： 执行顺序为 a，c，b 平均周转时间： （120+130+200）/3=150（min） 平均带劝周转时间： （120/120+130/30+200/60）/3 =26/9 所以，如果要比较哪一种算法好自然针对不抢占的情况。根据比较结果， 它们的平均周转时间和平均带权周转相同， 这主要是该应用正好发生了这样凑巧 周转时间(ms)等待时间（ms） j0750 j19075 j29590 j311095 j4155110 平均等待时间（ms）74 的情况。 3.16 假设在具有一个处理器的系统上执行下面的作业，假如采用抢占式短作业 优先调度算法，作业需要处理时间 t 和到达时间 a 分别如下：那么： 作业 1 的周转时间是多少？作业的平均等待时间是多少？ 答： 1。执行顺序为：0（10） ，2（30） ，1（65） ，3（90） ，0（130） ，4（170） 作业 0 的周转时间为：130， 作业 1 的周转时间为：55，作业 1 的周转时间为：55， 作业 2 的周转时间为：20， 作业 3 的周转时间为：35 作业 4 的周转时间为：65 平均周转时间=305/5=61 作业 0 的等待时间为：130-50=80， 作业 1 的等待时间为：55-35=20， 作业 2 的等待时间为：10-10=0， 作业 3的等待时间为： ，35-25=10 作业 4的等待时间为： ，65-40=25 3.17 假如在具有一个处理器系统中，采用优先级高者优先的进程调度算法，优 先数小代表优先级高，进程达到顺序 i 和需要处理时间 t、优先数分别如下： （1）没有优先级抢占情况下，写出进程的执行先后序列，进程 2 的周转时间是 多少？进程的平均等待时间是多少？ （3）有优先级抢占情况下，写出进程的执行先后序列，进程 2 的周转时间是多 少？进程的平均等待时间是多少？ 答： （1）无抢占： 执行顺序为：1（15） ，4（60） ，0（135） ，2（140） ，3（155） 进程 0 的周转时间为：135 it到达时间 a 0500 13510 22010 32555 44095 it优先级 0753 1151 254 3155 4452 进程 1 的周转时间为：15 进程 2 的周转时间为：140进程 2 的周转时间为：140 进程 3 的周转时间为：155 进程 4 的周转时间为：60 进程的平均等待时间=（ （135-75）+（15-15）+（140-5）+（155-15）+（60-45） /5 = 70 （2）有抢占： 优先级抢占同上一样。 318 假如在具有一个处理器的系统中，采用时间片轮转调度算法，时间片大小 为 10。进程需要处理时间 t 和到达时间 a 分别如下： 写出进程的执行序列，进程 3 的周转时间是多少？进程的平均等待时间是多 少？ 答： 进程的执行序列为：0，1，2，0，1，2，0，1，3，4，0，1，3，4，0，4 进程 0 的周转时间t0= 140 进程 1 的周转时间t1= 105 进程 2 的周转时间t1= 50 进程 3 的周转时间t1= 40进程 3 的周转时间t1= 40 进程 4 的周转时间t1= 75 进程的平均等待时间为： （ （140-50）+（105-35）+（50-20）+（40-15）+（75-40） /5=50 3.19 在时间片轮转调度算法中，有 n 个进程共享 cpu。 （1）如果进程切换的时间不可忽略，每次进程切换用去时间为 s 秒，在保 证每个进程至少每 t 秒内能够在 cpu 上轮回一次的前提下，确定时间片大小 q 使得进程切换所造成的负载最小。 (2) 如果 n=100，t=1，s=0.001，那么 q 的大小应该是多少？ 答： （1）时间片大小 q =（t-ns）/n （2）q=（1-100*0.001）/100 = 0.009 3.20 有一个四道作业的操作系统，若在一段时间内先后到达 6 个作业，它们的 提交时间和估计运行时间由下表给出： 作业提交时间估计运行时间（分钟） it到达时间 a 0500 13510 22010 31580 44085 18：0060 28：2035 38：2520 48：3025 58：355 68：4010 系统采用短作业优先调度算法，作业被调度进入系统后中途不得退出。但作 业运行时可被更短的作业抢占。分别给出 6 个作业的执行时间序列，作业的 周转时间， 平均周转时间。 答： 作业的执行顺序为：1（8：20） ，2（8：25） ，3（8：45） ，5（8：50） ，6 （9：00） ，4（9：25） ，2（9：55） ，1（10：35） 作业 1 的周转时间 = 155 min 作业 2 的周转时间 = 95 min 作业 3 的周转时间 = 20 min 作业 4 的周转时间 = 55 min 作业 5 的周转时间 = 15 min 作业 6 的周转时间 = 20 min 作业的平均周转时间为：360/6=60作业的平均周转时间为：360/6=60 3.21 在一个实时系统中有 4 个周期性事件，周期分别为 50、100、150、200ms。 假设其处理时间分别需要 30、25、20 和 xms，则该系统可调度允许的 x 值最大 为多少？ 解: 30/50 + 25/100 +20/150+x/200 =1 x = 10/3 3.22 某系统的进程状态变化如图 3.23 所示，该系统的进程调度为非抢占方式， 根据该状态图叙述系统的调度策略、调度效果。 图 3.23 状态变化图 阻塞 运行低优先级就绪 首先选择 100ms 高优先级就绪 其次选择 100ms 答：首先采用优先权高者优先调度算法，然后采用时间片为 100ms的调度算法。 该调度算法如果调度效果考虑更周到的话， 应该让阻塞队列上的进程唤醒后 进入低优先级就绪队列，这样能够保证优先级高的进程及时调度，优先级低的进 程能够合理的得到调度。 第 4 章 4.1-4.12 题解见书 4.13如果有n个进程共享一个互斥段 （1）如果每次只允许一个进程进入互斥段。 （2）如果每次最多允许m个进程同时进入互斥段（m10) （2）v(s);（5）x- - ; （3）y=x- 2;（6）else p(s); x- -; 分别说明（1）、（2）、（3）、（4）、（5）、（6）语句之后的 x、y 值为多少？ 答： （1）x=11,y=2(2) x=11,y=2(3) x=11,y=9 (4)x=11,y=9(5) x=10,y=9(6) x=10,y=8 4.18三个进程：输入、计算、输出。它们通过两个缓冲区传递数据，如图 4.11 所示。 每个缓冲区一次只能放入一条数据。写出用信号量进行同步。 解：var empty1,full1,empty2,full2:semaphore:=1,0,1,0; begin parbegin i:begin repeat wait(empty1); put to buffer1; signal(full1); until false; end; p:begin repeat wait(full1); get from buffer1; signal(empty1); wait(empty2); put to buffer2; signal(full2); until false; end; o:begin repeat wait(full2) get from buffer2; signal(empty2); until false; end; parend; end; 练习 5 5.1 什么是死锁？引起死锁的原因和必要条件是什么？ 死锁是指多个进程因为竞争资源造成的一种僵局。 原因：并发进程对临界资源的竞争和并发进程推进顺序不当。 必要条件：互斥条件，占有并请求条件，不剥夺条件，环路等待条件。 5.2 比较解决死锁的方法中， 那种方法最容易实现？那种方法使得资源的利用率 最高？ 解决死锁的方法：预防死锁，避免死锁，检测死锁，解除死锁。 预防死锁是通过设计协同资源管理程序，在进程运行期间，柏怀死锁产生 的四个条件之中的任何一个，是指不成立。是最容易实现的方法。 解除死锁是在发现死锁后，解除死锁，释放资源。是资源利用率最高的方 法。 5.3 预防死锁的方法有哪些？ 破坏互斥条件，破坏占有并请求，阻止环路等待，允许剥夺 5.4-5.7 题解见书 5.8 系统中有 3 个进程共享 4 个资源，每个进程每次只能申请或释放一个资源， 每个进程最多需要 2 个资源，给进程是否会发生死锁，为什么？ 解: 不会发生死锁。3 个进程共享 4 个资源，每个进程最多需要 2 个资源。 总有一 个进程的请求会满足，运行并释放资源。不会形成环路等待。 5.9 系统中有 20 个进程，每个进程最多使用 3 个资源，每个进程逐个申请并竞 争使用 60 个同类资源。一旦某进程获得所需要的资源，完成后立即释放全部资 源。系统是否会发生死锁？为什么？ 系统不会发生死锁。以最坏的情况来考虑，20 个进程都需要使用 3 个资 源。 当前， 每个进程都持有2个 资 源 。（20*2=40）.都在申请第 3个资源 （60-40=20） 对于剩余的 20 个资源，每个进程多会得到一个资源。不会形成环路等待。 5.10一台计算机有 8 台打印机，被n个进程竞争使用，每个进程最多需 要 3 台。 请问n为多少时，系统没有死锁的危险，说明原因。 解: n=3 时，没有死锁的危险。 对于 n 个进程，都持有 2 台打印机时，申请第 3 台打印机，只要有一台 的多余的打印机能被申请到，则系统就没有死锁的危险。即 n*2+1=8，得 n=3。 5.11考虑图 5.9 所示的资源分配图，哪个进程会发生死锁？ 解答:考虑图 5.9 所示的资源分配图，哪个进程会发生死锁？ 进程 p3,p4 会发生死锁。 对于进程 p1,p2，进程的推进不需要等待其他进程的完成。 进程 p3,p4。p3 要等 p4 完成并释放资源后方能推进。而 p4 要等到 p3 完成后才 能。结果是 p3,p4 都不能完成。形成死锁。 5.12假定有 3 个人排队等候上电梯。当电梯门打开的时候，3 个人都朝门口 冲去，但是门不够大，他们 3 人不能同时进门。描述解决这种死锁的方法，可以 让 3 个人都上电梯。说明你的解决方案清除了哪个死锁的必要条件。 解答: 让 3 个人轮流进电梯。 破坏了死锁发生的 4 个必要条件中的“不剥夺条件”。 5.13假定一个系统具有四个系统类型，c=3，7，2，3，最大资源需求数表 如图 5.10 所示。资源分配器根据图 5.11 中的表来分配资源，这个状态 安全吗？ 为什么？ 图5.10图5.11 解答: 这个状态安全。存在安全执行序列p4,p0,p1,p3,p2； 练习 6 6.1-6.8 题解见书 6.9如果一个分页系统能够向用户提供的逻辑地址最大为 16 页，页面大 小为 2k，内存总共有 8 个存储块。请问逻辑地址应该为多少位？内 存空间为多大？ 解：逻辑地址应该为 4+11=15（位） 内存空间为 8*2k =16k 6.10如果一个分页系统的页表存放在内存。 （1）若对内存的一次存取需要 1.2s，请问一次页面访问的存取需 要花多少时间？ （2）若系统配置了联想寄存器，对快表的命中率为 70%，假如查询 联想寄存器的时间忽略不计，请问实现一次页面访问的存取 时间是多少？ 解： （1）访问一次页面的存取需要花费的时间为 2*1.2s=2.4s （2）实现一次页面访问的存取时间=0.3*2.4s+0.7*1.2s=1.56s 6.11如果一个分页系统逻辑地址长度为 16 位，页面大小为 4kb，第 0、1、2 页对应 10、12、14 号物理块， 请问逻辑地址为 2f6ah 对应的物理地址为多少？ 解：逻辑地址为 2f6ah 对应的二进制码为：0010 1111 0110 1010，页号为：2， 页内偏移为 f6ah。 查询页表 2 号页面对应 12号块， 所以， 物理地址为1100 1111 0110 1010， 最终物理地址为：cf6ah 6.12如果内存中有 4 个空闲块，每个空闲块的大小为 10mb。有 10 个请求，每 次请求 1mb 的内存大小， 对于下面列出的内存分配方法中的每一种， 确定所有 10 个请求都被满足之后剩余空闲块的大小。 （a）首次适应算法 （b）循环首次适应算法 （c）最佳适应算法 （d）最坏适应算法 解： （a）首次适应算法：块 1 用完，块 2，3，4 剩余 10mb。 （b）循环首次适应算法：块 1，2 余 7mb，块 3.4 余 8mb。 （c）最佳适应算法：块 1 用完，块 2，3，4 余 10mb。 （d）最坏适应算法：块 1，2 余 7mb，块 3，4 余 8mb。 6.13如果一个系统的段表为： 求下列逻辑地址相应的物理地址。如果越界请指明。 0,380、1,20、1,24、2,200、3,500、4,120。 解：0,380表示为 0 段，段内偏移为 380，物理地址为 580； 1,20表示为 1 段，段内偏移为 20，物理地址为 920； 1,24表示为 1 段，段内偏移为 24，物理地址为 924； 2,200表示为 2 段，段内偏移为 200，已经越界； 3,500表示为 3 段，段内偏移为 500，物理地址为 1700； 4,120表示为 4 段，段内偏移为 120，已经越界。 练习 7 7.1-7.4 题解见书 7.5在分页虚拟存储器管理中，如果已知时间利用率为：cpu20%、分页 磁盘 92%、外设 50%，请问采取哪些措施可以改善 cpu 的利用率？ 解：增大分页磁盘空间。 7.6一个 32 位地址的计算机系统使用二级页表，虚拟地址为 9 位顶级页 表，11 位二级页表和偏移。请问：页面长度为多少？虚拟地址空间 有多少个页面？ 解：页面占用的位数=32-9-11=12 位，页面长度为 4k。虚拟地址空间有 1m 个页 面。 7.7如果分页虚拟存储系统向用户提供的逻辑地址空间最大为 16 页，每 页 2kb，内存总共有 8 个存储块，请问逻辑地址至少应为多少位？内 存空间多大？ 解：解：逻辑地址应该为 4+11=15（位） 内存空间为 8*2k =16k 7.8在一个请求分页的虚拟存储器管理中，一个程序的运行页面走向为： 1、2、3、4、2、3、5、6、3、1、4、6、7、5、2、4、1、3、2 段号始址段长 0200510 190030 210080 31200500 4180080 如果为程序分配页框为 3 个、4 个，请分别用 fifo、opt 和 lru 算法求 出缺页中断次数和缺页率。 解：页框为 3： fifo 缺页中断次数为 14；缺页率为 14/19。 opt 缺页中断次数为 8；缺页率为 8/19。 lru 缺页中断次数为 13；缺页率为 13/19。 页框为 4： fifo 缺页中断次数为 7；缺页率为 7/19。 opt 缺页中断次数为 5；缺页率为 5/19。 lru 缺页中断次数为 10；缺页率为 10/19。 练习 8练习 8 8.1-8.8 题解见书 练习 9 9.1-9.8 题解见书 9.9若采用字长为 16 位的位示图管理磁盘空间， 某操作系统的磁盘文件空间共 有 500 块，问位示图需要多少个字？第i列第j行对应的块号为多少？ 解答：500/16 取整为 32。 块号=16*i+j 9.10一个链接文件由 5 个逻辑记录组成， 每个逻辑记录的大小与磁盘块大小都 为 512 字节，一次存放在 25，70，98，83，60 号磁盘上。若要存取文件的第 1 769 逻辑字节处的信息，问需要访问哪个磁盘块？ 解答:1769 位于第 3 个逻辑记录(从 0 开始)。所以,需要访问第 83 号磁盘块。 9.11在 unix 操作系统中，如果一个盘块的大小为 1kb，每个盘块号占用 4 个 字节，即每块可放 256 个地址，如果进程要访问偏移为 143140 处的数 据，问需要几次寻址？ 解答：unix 操作系统中前面 0-9 个块为直接寻址，后面分别为 1 次间接寻址，2 次间接寻址，3 次间接寻址。 由于 1 个盘块为 1kb 大小，可寻址范围为 10kb，即 10*1024=10，240。显 然，143140 已经超过了直接寻址。 1 次间接寻址范围为 256*1024=262144，所以，143140 就在 1 次间接寻 址中。 故需要通过 1 次间接寻址。 9.12从磁盘高速缓存读取数据需要 1ms，从磁盘读取数据需要 40ms，如果命中 率为 50%，计算出读取数据的平均时间。 解答：1*