I有一台计算机，具有1MB内存，操作系统占用200KB：每个用户进程各占200KB。如果用户
答：设每个进程等待I/O的百分比为P,那么n个进程同时等待I/O的概率是P",当n个进程同时
等待I/O期间CPU是空闲的，故CPU的利用率为1-曰。由题意可知，除去操作系统，内存还
CPU利用率=1-(80%)4=0.59
假设再增加1MB内存，系统中可同时运行9个用户进程，此时：
CPU利用率=1-(80%)9=0.87
故增加1MB内存使CPU的利用率提高了47%：
87%4-59%=147%
147%-100%=47%
2一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A先开始做，
程序B后开始运行。程序A的运行轨迹为：计算50ms＞打印100ms、再计算50ms＞打印100ms,
结束。程序B的运行轨迹为：计算50ms、输入80ms、再计算100ms,结束。试说明(1)两道程
无等待CPU的情况？假设有，指出发生等待的时刻。
答：画出两道程序并发执行图如下：
IA计算B计算B计算
处理器
输入机B输入|
打印机A打印|A打印|
程序A1计笠打印|计苴打印|
程序B计第输入「计部|
050100150180200250300
局部)。
ABC
Cn=30msC2i=60msC3i=20ms
Ii2=40ms[22=30msh2=40ms
C)3=10msC23=10msC3j=2Oms
答：
I/O112122132
CPUC11C21Cl：1C21C31C23C33_
抢占式共用去190ms,单道完成需要260ms,节省7()ms°
CPUCllC21C13C3I(：23C33
非抢占式共用去180ms,单道完成需要260ms,节省80ms。
4在单CPU和两台1/0(11,12)设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨
迹如下：
Jobl：I2(30ms)>CPU(lOms)、Il(30ms)CPU(lOms)、I2(20ms)
Job2：Il(20ms)>CPU(20ms)、I2(40ms)
Job3：CPU(30ms)>Il(20ms)、CPU(lOms)、Il(10ms)
如果CPU、Il和12都能并行工作,优先级从高到低为Jobl、Job2和Job3,优先级高的作业可以抢
⑵从投入到完成CPU的利用率。(3)1/0设备利用率。
CPULJob3IJob2JoblIJob2IJob3|IJobl|IJob3|
11|_Job2JJobl|Job3||Job3
12|_Jobl1Job2IJobl
Jobl|_12CPU1IIICPUI-~l12
Job2II1CPU匚1CPU112_J
—
Job3|_CPUl-iCPUr1IIICPU|Il
(ms)
0102030405060708090100110
(1)Jobl从投入到运行完成需ll()ms,Job2从投入到运行完成需90ms,Job3从投入到运行完成需
1lOmso
(110-30)/110=72.7%o
5在单CPU和两台1/0(11,⑵设备的多道程序设计环境下，同时投入三个作业运行。它们的执行轨
Jobl：I2(30ms)>CPU(lOms)、Il(30ms)>CPU(lOms)
Job3：CPU(30ms)、Il(20ms)
如果CPU、Il和12都能开行工作，优先级从高到低为Jobl、Job2和Job3,优先级高的作业可以抢
完成CPU的利用率。(3)1/0设备利用率。
I/O
CPU
02040506080100120140
7假设内存中有3道程序A、B、C,优先级从高到低为A、B和C,它们单独运行时的CPU和
I/O占用曲1■间为：
程序A：60203010402020(ms)
I/O2CPUI/OICPUI/OICPUI/OI
程序B：304070303()(ms)
I/O1CPU1/02CPUI/O2
程序C：40603070(1ms)
CPUI/OlCPUI/O2
如果三道程序同时并发执行，调度开销忽略不计，但优先级高的程序可中断优先级低的程序，优先
CPU|C|B|A|B|CIf|IB|CIAICI
[01IB|1AlC1Al|A|
[02A||B||B||C
A|102Cpu|101|P||101|cpu|101|
u
B|1()1|cpu|巳11°2cpu|102|
C
101「CPU」102
0306090120150180210240270300330
（1）最早结束的程序为B,最后结束的程序为C。
（2）程序A为250mso程序B为220ms。程序C为310ms。
⑶CPU利用率为（310-120）/310=61.3%
8有两个程序，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化了4。秒。故CPU利用率为40/80=50%o
答：因时钟中断频率为60HZ,所以，时钟周期为：l/60s=50/3ms。在每个时钟周期中，CPU花2ms
CH2应用题参考答案
1以下指令中哪些只能在核心态运行？
（1）读时钟日期；（2）访管指令；（3）设时钟日期；（4）加载PSW；（5）置特殊存放器；（6）改
变存储器映象图；（7）启动I/O指令。
答：⑶，（4）,（5）,（6）,（7）。
2假设有一种低级调度算法是让“最近使用处理器较少的进程”运行，试解释这种算法对“I/O
繁重”型作业有利，但并不是永远不受理“处理器繁重”型作业。
答:因为I/O繁忙型作业忙于I/O,所以它CPU用得少，按调度策略能优先执行。同样原因一个进
程等待CPU足够久时，由于它是“最近使用处理器较少的进程”，就能被优先调度，故不会饥饿。
3并发进程之间有什么样的相互制约关系？以下口常生活中的活动是属哪种制约关系：（1）踢足
球，（2）吃自助餐，（3）图书馆借书，（4）电视机生产流水线工序。
答：并发进程之间的根本相互制约关系有互斥和同步两种。其中（I）、（3）为互斥问题。（2）、（4）为同
步问题。
4在按动态优先数调度进程的系统中，每个进程的优先数需定时重新计算。在处理器不断地在
答：许多操作系统重新计算进程的优先数在时钟中断处理例程中进行，由于中断是随机的，碰到哪
T1=a+（a+b）+（a+b+c）=3a+2b+c①
假设不按短作业优先算法调度：不失一般性，设调度次序为：J2.JL.J3。那么三个作业的总周转
T2=b+(b+a)+(b+a+c)=3b+2a+c②
令②-①式得到：
T2-Tl=b-a>0
并在一台单CPU处理器上按单道方式执行。试找出一种作业调度算法，使得平均作业周转时
间最短。
T=[Si+(Si+S2)+(Si+S2+S3)+…+(S]+S2+S3+,,,+Sn)J/n
=[nXSi'+(n-l)XS2'+(n-3)XS3']+-+S]]/n
，
=(S；+S2+Sj+…+Sn'MOXSr+lXS2+2XS；+-+(n-l)S']/n
由于任何调度方式下，S「-S2'+S；+…+S；为一个确定的数，而当Si'WS2'<…WS.DWS；时
才有：OXS/+1XS2'+2XS3'+…+(n-l)S；的值最大,也就是说，此时T值最小。所以,按短作
7假定执行表中所列作业，作业号即为到达顺序，依次在时刻0按次序1、2、3、4、5进入单
处理器系统。
算出各作业的执行先后次序(注意优先权高的数值小)；
1103
211
323
414
552
答:
(1)采用FCFS算法调度作业，运作情况:
11()001()1()1
211010111111
3211II13136.5
411313141414
55141419193.8
1、5、1、5、1、5、1、1、1、1、1。
110019191.9
210222
320773.5
410444
55014142.8
(3)采用SJF算法调度作业，运作情况:
2100111
4111222
3222442
5544991.8
1109919191.9
(4)采用非剥夺优先权算法调度作业，运作情况:
211011
525161.2
13106161.6
33216189
441181919
1)Q=82)Q>T3[S 1)Q=8CPU利用率=17(T+S) 2)Q>TCPU利用率=T/(T+S) 3)T>Q>SCPU利用率:Q/(Q+S) 4）Q=SCPU利用率=50% 5）Q-*0CPU利用率-*0 1）xW3次序为：x,3,5,6,9 2）3 3）5 4）6 5）9 先数法、3）短作业优先算法、4）先来先效劳调度算法（按到达次序C、D、B、E、A）,在忽 （DFCFS调度算法 C6061 D86141.75 B414184.5 E1018282.8 A2283015 ⑵优先级调度算法 E100101 D810182.25 C618244 B424287 按次序ABCDEBCDECDEDEE轮转执行。 A2021 B48123 C614203.33 D818263.25 E1020303 （4）SJF调度算法 B4261.5 C66122 D812202.5 的优先级分别被规定为3、5、2、1和4,这里5为最高级。假设不考虑系统切换开销，计算 A10010I B610162.66 C216189 D418225.5 E822303.75 B601 E861.75 A10142.4 C22413 D4267.5 按次序ABCDEABDEABEAEA轮转执行。 A1020303 B616223.66 C2463 D412164 E820283.5 12(1)假定一个处理器正在执行两道作业，一道以计算为主，另一道以输入输出为主，你将怎样 赋予它们占有处理器的优先级为什么？ (2)假定一个处理器正在执行三道作业，一道以计算为主，第二道以输入输出为主，第三道为 计算与输入输出均匀。应该如何赋予它们占有处理器的优先级使得系统效率较高？ 先级最高，输入输出均匀的作业其次，而计算为主作业的优先级最低。 13请你设计一种先进的计算机体系结构，它使用硬件而不是中断来完成进程切换，那么CPU需 要哪些信息？请描述用硬件完成进程切换的工作过程。 答：该计算机有一个专用硬件存放器，它始终存放指向当前运行进程的PCB的指针。当系统中发 生了一个事件，如I/O结束事件，CPU便可把运行进程的上下文保存到专用硬件存放器指针指向的 PCB中保护起来，然后，CPU转向中断向量表，找到设备中断处理程序入口，让专川硬件存放器 指针指向(设备)中断效劳例程，于是，便可启动中断效劳例程工作。 14单道批处理系统中，以下二个作业采用先米先效劳调度算法和最高响应比优先算法进行调度, 哪一种算法性能较好？请完成下表： 开始完成周转带权周 110：002：00 210：101：00 310：250：25 FIFO 110：002：0010:0012:002120/120 210：101：0012:0013:002:50145/60 310：250：2513:0013:253180/25 HRRF 210：101：0012:2513:253:15195/60 310：250：2512:0012:252120/25 可见HRRF比FIFO要好。 18.002.008.()0 28.500.5010.30 39.000.1010.00 49.500.2010.10 FCFSSJFHRRF 作业开始完成周转开始完成周转开始完成周转 18.0010.002.008.0010.002.008.0010.002.00 210.0010.502.0010.3010.802.3010.1010.602.10 310.5010.601.6010.0010.101.1010.0010.101.10 410.6010.801.3010.1010.300.8010.6010.801.30 平均周T=1.725T=1.55T=1.625 带权平均W=6.875W=5.15W=5.675 16Kleinrock提出一种动态优先权算法：进程在就绪队列等待时，其优先权以速率a变化；当进 程在处理器上运行，时其优先权以速率B变化。给参数。、B赋以不同值可得到不同算法。 （1）假设a>8>0是什么算法？（2）假设a<8<0是什么算法 （1）是先进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先数提 高得快，故进程切换时，先进入就绪队列的进程优先权就越高。 （2）是后进先出算法。因为在就绪队列中的进程比在CPU上运行的进程的优先权下 降得快，故后进入就绪队列的进程此先进入的进程的优先权高。 18：0060 28：2035 38：2520 48：3025 58：355 68：4010 系统采用SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被更短作 J18:00608:009:0060 J58:3559:009:0530 J68:40109:059:1535 J38:25209:159:3570 J48:30259:3510:0090 J28:203510:0010:35135 注意，JI被调度运行后，直到它执行结束，才会引出作业调度程序工作。所以，J2至J6 虽在J1执行期间进入，但未被调度，均在等待。当J1撤离后，作业调度程序工作，按SJF算 法，显然有执行次序：J5、J6、J3、J4、和J2。 18有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以 优先数为根底的抢占式调度算法，在下表所示的作业序列，作业优先数即为进程优先数，优 先数越小优先级越高。 A10：0040分5 B10：2030分3 C10：3050分4 D10：5020分6 每个作业运行将经过两个阶段：作业调度(SJF算法)和进程调度(优先数抢占式)。另外，批处理 最多容纳2道作业，更多的作业将在后备队列等待。 ABAcD 进程就绪队列人DD 作业后备队列c (1)10:00,作业A到达并投入运行。 (2)10:2(),作业B到达且优先权高于作业A,故作业B投入运行而作业A在就绪队列等待。 (3)10:30,作业C到达，因内存中已有两道作业，故作业C进入作业后备队列等待。 (4)10:50,作业B运行结束，作业D到达，按SJF短作业优先算法，作业D被装入内存进入就 绪队列。而由于作业A的优先级高于作业D,故作业A投入运行。 (5)11:10,作业A运行结束,作业C被调入内存,且作业C的优先级高于作业D,故作业C投 入运行。 (6)12:00,作业C运行结束，作业D投入运行。 (7)12:20,作业D运行结束。 A10:0011:10 B10:2010:50 C11:1012:00 D10:5012:20 为70分钟。 19某多道程序设计系统供用户使用的主存为100K,磁带机2台，打印机1台。采用可变分区内 18:0025分钟15K11 28:2010分钟30K01 38:2020分钟60K10 48:3020分钟20K10 58:3515分钟10K11 作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作 答：(1)作业调度选择的作业次序为：作业1、作业3、作业4、作业2和作业5。 业5为55分钟。 20某多道程序设计系统采用可变分区内存管理，供用户使用的主存为200K,磁带机5台。采用 列如下： A8:3040分钟30K3 B8:5025分钟120K1 C9:0035分钟100K2 D9:0520分钟20K3 E9:1010分钟60K1 CH3应用题参考答案 1有三个并发进程：R负责从输入设备读入信息块，M负责对信息块加工处理；P负责打印输出信息块。