1、 练习 11.1-1.10 题解见书1.11 有一台输入设备和一台输出设备的计算机系统上，运行有两道程序。两道程序投入运行情况如下：程序 1 先开始运行，其运行轨迹为：计算 50ms、输出 100ms、计算50ms、输出 100ms，结束；程序 2 后开始运行，其运行轨迹为：计算 50ms、输入 100ms、计算100ms、结束。1. 忽略调度时间，指出两道程序运行时，CPU 是否有空闲？在哪部分空闲？指出程序 1 和程序 2. 有无等待 CPU 的情况？如果有，发生在哪部分？题解:由题画出 CPU 利用图如下：由图可知，1.CPU 有空闲，在 100ms150ms 时间段是空闲的。2.程序
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 的次序，即程
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，
4、即：CPU 利用率=40ms/80ms*100%=50%1.14 一个计算机系统有足够的内存空间存放 3 道程序，这些程序有一半的时间在空闲等待 I/O 操作。问多大比例的 CPU 时间被浪费掉了。题解：由题画图如下：因为每个程序有一半的时间在等待 I/O 操作，所以在并发状态下，程序 1、程序 2、程序 3 所占时间比依次减半（如上图） ，所以浪费的时间比例为 1/8。练习 2218 某系统中进程状态变化如图 2.22 所示，当对系统中的进程进行观察时，发现某一进程产生的一次状态变化会引起另一进程发生状态变化。（1）在什么情况下，一个进程的状态变化 3 能够立即引起另一进程的状态变化1？（2
5、）在什么情况下，一个进程的状态变化 2 能够立即引起另一进程的状态变化1？（3）进程的状态变化 3 是否可能引起另一进程的状态变化 2？进程的状态变化3 是否可能引起另一进程的状态变化 1？解答：（1）当就绪队列中还存在其它进程的情况下，一个进程的状态变化 3 能够立即引起另一进程的状态变化 2。（2）当就绪队列中还存在其它进程的情况下，一个进程从运行状态变化到就绪状态后，另一个就绪进程能够从就绪状态变为运行状态。（3）不可能，可能。219 分别写出相应的程序来描述图 2.23 中的前趋图。解答S1S2S3S4S5S6S7程序：S1:a:=x+1S2:b:=a+2S3:c:=a+3S4:d:=
6、b+4S5:e:=b+cS6:f:=e+5S7:g=e+6S1S2S3S4S5S6S7程序：S1:a:=x+1S2:b:=a+2S3:c:=a+3S4:d:=b+4S5:e:=b+cS6:f:=d+eS7:g:=c+e2.20 假设在一个系统中，新进程以每分钟 8 个进程的速率到达，每个进程请求服务的平均时间为 6s，估计在一个单处理器系统中 CPU 忙的时间比率。如果新进程以每分钟 10 个进程的速率到达，每个进程请求服务的平均时间也为 6s，估计在一个单处理器系统中 CPU 忙的时间比率。如果新进程创建以每分钟超过 10 个进程的速率到达，每个进程请求服务的平均时间为 6s，估计在一个单处
7、理器系统中 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
8、分钟，CPU 一直会处于繁忙，所以 CPU 忙的时间比率同样为 100%。2.21 一个系统中有 4 个进程，进程 P1 要求 20s 后运行，经过 40s 后再次运行；进程 P2 要求 25s 后运行；进程 P3 要求 35s 后运行，经过 35s 后再次运行；进程 P4 要求 60s 后运行。进程在阻塞队列等待被唤醒后运行，试创建进程的唤醒队列。解答：进程的唤醒队列为 P1P2P3P4P1P3注意：“经过 40s 后再次运行”表示第 1 次运行完成后再过 40s。2.22 如果线程是在用户空间线程库中实现，解释为什么当进程中的一个线程阻塞时，进程内的所有其它线程都会阻塞？如果线程是在内核空
9、间中实现,而进程内的一个线程阻塞不会引起进程内的其他线程被阻塞，为什么？解答：用户级线程由用户空间运行的用户级线程库实现。当一个应用程序提交给操作系统后，操作系统首先为该应用程序建立一个内核管理进程，然后用户级线程库为该进程创建一个或多个用户级线程，但内核并不知道用户空间线程的活动，内核只是以进程为单位，实现进程状态的转换，因此当进程中的一个线程阻塞时，进程内的所有其它线程都会阻塞。如果线程是在内核空间中实现的，这些内核级线程都由内核创建和控制管理，内核为整个进程及进程中的所有线程维护现场信息，内核的调度是在线程的基础上进行的，因而进程的一个线程阻塞不会引起进程内的其他线程被阻塞。练习 33.
10、13 证明作业调度算法中短作业优先调度算法具有最小平均等待时间。证明:假设在作业队列中等待运行的作业有 N 道,分别为 N0，N1，N2，Nn-1，它们的运行时间分别为 t0，t1，tn-1，且满足 t00说明任何一种作业调度顺序的作业的平均等待时间都大于按照短作业优先的作业的平均等待时间。3.14 假设在一个处理器上执行 5 个作业，作业到达的次序和需要执行的时间分别为：J0（75ms） 、J1（15ms） 、J2（5ms） 、J3（15ms） 、J4（45ms） ，假定系统中使用 FCFS 调度算法，作业 J3 的周转时间是多少？作业的平均等待时间是多少？答：周转时间(ms) 等待时间（m
11、s）J0 75 0J1 90 75J2 95 90J3 110 95J4 155 110平均等待时间（ms） 743.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:
12、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所以，如果要比较哪一种算法好自然针对不抢占的情况。根据比较结果，它们的平均周转时间和平均带权周转相同，这主要是该应用正好发生了这样凑巧的情况。3.16 假设在具有一个处理器的系统上执行下面的作业
13、，假如采用抢占式短作业优先调度算法，作业需要处理时间 T 和到达时间 A 分别如下：那么：I T 到达时间 A0 50 01 35 102 20 103 25 554 40 95作业 1 的周转时间是多少？作业的平均等待时间是多少？答：1。执行顺序为：0（10） ，2（30） ，1（65） ，3（90） ，0（130） ，4（170）作业 0 的周转时间为：130，作业 1 的周转时间为：55，作业 2 的周转时间为：20，作业 3 的周转时间为：35作业 4 的周转时间为：65平均周转时间=305/5=61作业 0 的等待时间为：130-50=80，作业 1 的等待时间为：55-35=20，
14、作业 2 的等待时间为：10-10=0，作业 3 的等待时间为：，35-25=10作业 4 的等待时间为：，65-40=253.17 假如在具有一个处理器系统中，采用优先级高者优先的进程调度算法，优先数小代表优先级高，进程达到顺序 I 和需要处理时间 T、优先数分别如下：I T 优先级0 75 31 15 12 5 43 15 54 45 2（1）没有优先级抢占情况下，写出进程的执行先后序列，进程 2 的周转时间是多少？进程的平均等待时间是多少？（3）有优先级抢占情况下，写出进程的执行先后序列，进程 2 的周转时间是多少？进程的平均等待时间是多少？答：（1）无抢占：执行顺序为：1（15） ，4
15、（60） ，0（135） ，2（140） ，3（155）进程 0 的周转时间为：135进程 1 的周转时间为：15进程 2 的周转时间为：140进程 3 的周转时间为：155进程 4 的周转时间为：60进程的平均等待时间=（135-75）+（15-15）+（140-5）+（155-15）+（60-45） ）/5 = 70（2）有抢占：优先级抢占同上一样。318 假如在具有一个处理器的系统中，采用时间片轮转调度算法，时间片大小为 10。进程需要处理时间 T 和到达时间 A 分别如下：I T 到达时间 A0 50 01 35 102 20 103 15 804 40 85写出进程的执行序列，进程
16、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进程 4 的周转时间 T1= 75进程的平均等待时间为：（140-50）+（105-35）+（50-20）+（40-15）+（75-40） ）/5=503.18 在时间片轮转调度算法中，有 n 个进程共享 CPU。（1）如果进程切换的时间不可忽略，每次进程切换用去时间为 s 秒，在保证每个进程至少每 t 秒内能够在 CPU 上
17、轮回一次的前提下，确定时间片大小 q 使得进程切换所造成的负载最小。(2) 如果 n=100，t=1，s=0.001，那么 q 的大小应该是多少？答：（1）时间片大小 q =（t-ns）/n（2）q=（1-100*0.001）/100 = 0.0093.19 有一个四道作业的操作系统，若在一段时间内先后到达 6 个作业，它们的提交时间和估计运行时间由下表给出：作业 提交时间 估计运行时间（分钟）1 8：00 602 8：20 353 8：25 204 8：30 255 8：35 56 8：40 10系统采用短作业优先调度算法，作业被调度进入系统后中途不得退出。但作业运行时可被更短的作业抢占。分
18、别给出 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=603.20 在一个实时系统中有 4 个周期性事件，周期分别为50、100、150、200ms。假设其处理
19、时间分别需要 30、25、20 和 xms，则该系统可调度允许的 x 值最大为多少？解:30/50 + 25/100 +150/20 +200/x =1X = 10/33.21 某系统的进程状态变化如图 3.23 所示，该系统的进程调度为非抢占方式，根据该状态图叙述系统的调度策略、调度效果。图 3.23 状态变化图阻塞运行低优先级就绪首先选择 100ms高优先级就绪其次选择 100msy 答：首先采用优先权高者优先调度算法，然后采用时间片为 100ms 的调度算法。该调度算法如果调度效果考虑更周到的话，应该让阻塞队列上的进程唤醒后进入低优先级就绪队列，这样能够保证优先级高的进程及时调度，优先级
20、低的进程能够合理的得到调度。第 4 章4.13 如果有 n 个进程共享一个互斥段（1）如果每次只允许一个进程进入互斥段。（2）如果每次最多允许 m 个进程同时进入互斥段（ mn） 。问采用的信号量初值是否相同？信号量值的变化范围如何？答：所采用互斥信号量的初值不同。（1）互斥信号量初值为 1，变化范围为-n+1，1。当没有进程进入互斥段时，信号量值为 1；当有 1 个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为 0；当有 1 个进程进入互斥段，有 1 个进程等待进入互斥段时，信号量值为-1；最多可有 n-1 个进程等待进入互斥段，故此时信号量的值为-（n-1） 。（2）互斥信号量初
21、值为 m，变化范围为m-n，m。当没有进程进入互斥段时，信号量值为 m；当有 1 个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为 m-1；当有 m 个进程进入互斥段，但没有进程等待进入互斥段时，信号量值为 0；当有 m 个进程进入互斥段，有 1 个进程等待进入互斥段时，信号量值为-1；最多可有 n-m 个进程等待进入互斥段，故此时信号量的值为-（n-m） 。4.14 在两条双向道路的交叉路口，没有行人通过，只有汽车通过。交通情况如 下：（1）任何给定的时刻只能有一辆车过马路；（2）当一辆车到达交叉路口并且另一条街道上没有车来到的时候，应该允许此车通过；（3）当两个方向上都有车到达的时候，它们应该轮流通过，以防止在其中一个方向上的无限期延迟。 用信号量操作实现道路交通问题。解：semphore S1=0,S2=0;/有无车到达，为 0 时无到达semphore M1=1,M2=0;/路中被占P1:if(车到达)v(S1);while(!S1);if(!S2)过一辆车；
