操作系统第二章应用题参考答案2021

（（4版）CH2应用题参考答案PAGEPAGE10第二章 应用题参考答案布置作业第二章5,8,10,12,17,20,27,28,305J1J2a、b、ca<b<c，试证明采用短作业优先算法调度能获得最小平均作业周转时间。答：采用短作业优先算法调度时，三个作业的总周转时间为：T1=a+(a+b)+(a+b+c)=3a+2b+c ①若不按短作业优先算法调度，不失一般性，设调度次序为：J2、J1、J3。则三个作业的总周转时间为：T2=b+(b+a)+(b+a+c)=3b+2a+c ②令②-①式得到：T2-T1=b-a>0可见，采用短作业优先算法调度才能获得最小平均作业周转时间。8 4(第一个答案是按照非抢占式优先级调度计算的，如果有同学按照抢占式优先级调度计算也算正确)作业名进入后备队列时间执行时间优先级JOB18:0060分1JOB28:3050分2JOB38:4030分4JOB48:5010分3试填充下表。作业名进入后备队列时间执行时间开始执行时间结束执行时间周转时间带权周转时间平均周转时间T=带权平均周转时间W=解:【按照非抢占式优先级调度】作业名进入后备队列时间执行时间开始执行时间结束执行时间周转时间带权周转时间JOB18:0060分8:009:006060/60JOB38:4030分9:009:305050/30JOB48:5010分9:309:405050/10JOB28:3050分9:4010:30120120/50平均周转时间T=(60+50+50+120)/4=70带权平均周转时间W=(1+5/3+5+12/5)/4=2.52【按照抢占式优先级调度】8:00~8:30JOB1,30分钟8:30~8:40JOB2,40分钟8:40~9:10JOB3,0分钟9:10~9:20JOB4,0分钟9:20~10:00执行JOB2,0分钟10:00~10:30执行JOB1,0分钟作业名进入后备队列时间执行时间开始执行时间结束执行时间周转时间带权周转时间JOB18:0060分8:0010:30150150/60JOB28:3050分8:3010:009090/50JOB38:4030分8:409:103030/30JOB48:5010分9:109:203030/10平均周转时间T=(150+90+30+30)/4=75带权平均周转时间W=(150/60+90/50+30/30+30/10)/4=2.07510 5635答：按照最短作业优先的算法可以使平均响应时间最短。X取值不定，按照以下情况讨论：1）x≤3次序为：x，3，5，6，92）3<x≤5次序为：3，x，5，6，93）5<x≤6次序为：3，5，x，6，94）6<x≤9次序为：3，5，6，x，95）9<x 125AE10、6、2、4835215（1）FCFS(A、B、C、D、E)；(2)优先级调度算法；(3)时间片轮转法(2分钟长的时间片)。答：(1)FCFS调度算法执行次序执行时间等待时间周转时间带权周转时间ABCDE100101610162.66216189418225.5822303.75作业平均周转时间T=(10+16+18+22+30)/5=19.2作业平均带权周转时间W=(1+2.66+9+5.5+3.75)/5=4.38(2)优先级调度算法执行次序执行时间等待时间周转时间带权周转时间BEACD606186141.751014242.42242613426307.5作业平均周转时间T=(6+14+24+26+30)/5=20作业平均带权周转时间W=(1+1.75+2.4+13+7.5)/5=5.13(3)时间片轮转法按次序ABCDEABDEABEAEA轮转执行。作业执行时间等待时间周转时间带权周转时间ABCDE1020303616223.662463412164820283.5作业平均周转时间T=(30+22+6+16+28)/5=20.4作业平均带权周转时间W=(3+3.66+3+4+3.5)/5=3.4317 如果在限制为两道的多道程序系统中，有四个作业进入系统的时间、估计运行SJFSRTF作业进入系统时间（分）开始运行时间结束运行时间周转时间JOB110：0030JOB210：0520JOB310：105JOB410：2010平均周转时间T=平均带权周转时间W=解：作业进入系统时间（分）开始运行时间结束运行时间周转时间JOB110：003010：0011：0565JOB210：052010：0510：2520JOB310：10510：2510：3020JOB410：201010：3010：4020平均周转时间T=31.25平均带权周转时间W=2.29说明：10：00时，J0B1进入系统，系统中只有一道作业，故JOB1被调入主存并启动执行。10：05时，JOB2到达，系统最多允许两个作业同时进入主存，所以JOB2也被调入主存。此时，主存中有两个作业，哪一个在处理器上执行？题目规定，当一新作业投入运行后，可按照SRTF进程调度算法执行，根据这一原则，由于J0B2运行时间（20分钟）JOB1少（10：05时，JOB125分钟），所以进JOB2J0B1在就绪队列中等待。10：10时，JOB3到达系统，由于主存中已经有两个作业，所以，JOB3不能马上进入主存；同样原理，10：20JOB4也不能进入主存。10：25时，JOB2运行结束，退出系统，此时主存中剩下JOB1、而输入井中JOB3JOB4，由于作业调度算法遵循SJF原则，因此作业调度程序选JOB3进入主存。通过比较主存就绪队列中进程JOB1JOB3的运行时间，得知JOB3运行时JOB3JOB3退出系统后，JOB4。JOB4运行结束后，JOBI才能继续运行。20 6作业提交时间估计运行时间(分钟)18：006028：203538：252048：302558：35568：4010系统采用剩余SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短作业抢占。(1)分别给出6个作业的执行时间序列、即开始执行时间、作业完成时间、作业周转时间。(2)计算平均作业周转时间。答：作业号时间需运行时间开始运行时间被抢占还需运行时间时间周转时间J18:00608:004010:35155J28:20358:20309:5595J38:25208:258:4520J48:30259:00259:2555J58:3558:458:5015J6说明:8:40108:509:0020J2J1；J3J2。J4SJFJ4不能被运行，J35分钟。4根据进程调度可抢占原则，J3J5、J6J5可进入主存。J5J6J6最短，故它第三个完成。然后是:J4、J2J1(7)T=(155+95+20+55+15+20)/6=60CPU就绪队列CPU就绪队列CPUCPU就绪队列CPUCPU就绪队列CPU后备队列CPU后备队列CPUJ1J2J3J4J5J6100K21台。采用可变I/O作业号进入输入井时间运行时间主存需求量磁带需求打印机需求18:0025分钟15K1128:2010分钟30K0138:2020分钟60K1048:3020分钟20K1058:3515分钟10K11作业调度采用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)平均作业周转时间=44分钟。(5))最大作业周转时间为55分钟。分析：本题综合测试了作业调度、进程调度、及对外设的竞争、主存的竞争。8:00作业1到达，占有资源并调入主存运行。8:202323资源1CPU时间。8:30作业1在8:30结束，释放磁带与打印机。但作业2仍不能执行，因不能移动而没有30KB的空闲区，继续等待。作业4在8:30到达，并进入主存执行，与作业3分享CPU。8:35作业5到达，因分不到磁带机/打印机，只能在后备队列等待。9:00作业3运行结束，释放磁带机。此时作业2的主存及打印机均可满足，投入运行。作业5到达时间晚，只能等待。9:10作业4运行结束，作业5因分不到打印机，只能在后备队列继续等待。9:15作业2运行结束，作业5投入运行。9:30作业全部执行结束。015K

011

0113作业3100K

100K

作业40

8:00

作业2作业2作业4100K

8:20

作业5作业5作业2100K

8:30作业59:00

9:10

9:1511、11、33、4作业2、4 作业251251453CPU1/2CPU等待1/2CPU1/2CPU1/2CPU1/2CPU等待CPUCPU1/2CPU11打印机12123455台。采用静态方式分配外围设备，且不能移动在主存中的作业，进程调度采用FCFS，I/O时间。现有作业序列如下：作业号进入输入井时间运行时间主存需求量磁带需求ABCDE8:308:509:009:059:1040分钟25分钟35分钟20分钟10分钟30K120K100K20K60K31231现求：(1)FIFO算法选中作业执行的次序及作业平均周转时间。(2)SJF算法选中作业执行的次序及作业平均周转时间。答：FIFO算法选中作业执行的次序为：BDCE63分钟。SJF算法选中作业执行的次序为：A、B、D、EC。作业平均周转时间为58分钟。详细说明：1.先来先服务算法。说明：8:30 A到达并投入运行。注意它所占用的资源。8:50 BCPU。9:00 C到达，主存和磁带机均不够，进后备作业队列等待。9:05 DC、D。9:10A(即不能紧缩)BCE也到达了，也由于主存不够D因资源满足(主存/磁带均满足)，进主存就绪队列等待。后C、E。(6)9:35 BDC因资源满足而调入主存进就CPUE因磁带机不够继续在后备作业队列等待。(7)9:55 DCE因资源满足而调入主存进就CPU。(8)10:30 CE投入运行。(9)10:40 E运行结束。030200

0作业A作业A150200

0作业A作业A作业B150200

0作业B作业A作业B作业A作业D作业B301502008:508:30 9:00,9:05 9:108:50020120200

0作业D作业D作业C120180200

0作业C作业作业C作业E180200

0作业E200作业E9:359:559:35

10:30

10:40作业A作业B作业D作业C作业E作业A作业B作业D作业C作业ECPU后就绪等待后备队列CPU备 就绪等待就绪等待后备队列待就绪等作业CCPU业B作CPUD作业作业APUD作业作业A作业ED作业作业A作业CCPU12345作业A作业B作业C作业D作业E作业执行次序进输入井时间装入主存时间开始执行时间执行结束时间周转时间作业A8:308:308:309:1040(分)作业B8:508:509:109:3545作业D9:059:109:359:5550作业C9:009:359:5510:3090作业E9:109:5510:3010:4090作业平均周转时间(40+45+50+90+90)/5=63分钟短作业优先算法。说明：8:30 A到达并投入运行。注意它所占用的资源。8:50 BCPU。9:00 C到达，主存和磁带机均不够，进后备作业队列等待。9:05 DC、D。9:10 A(即不能紧缩)BCED因资源满足(主存/磁带均满足)，进主存就C、E。(6)9:35 BDCESJF应把作业E调入主存进就绪队列等CPU。而作业C因磁带机不够继续在后备作业队列等待。(7)9:55 DCCPU。(8)10:05 EC投入运行。(9)10:40 C运行结束。030200

0作业A作业A150200

0作业A作业A作业B150200

0作业A作业B作业A作业B作业D作业B301502008:508:30 9:00,9:05 9:108:5002080200

0作业E作业作业E作业C180200

0作业C200作业C02080180200020801802009:35作业D作业E

10:05

10:40时间 8:30 8:40 8:509:009:10 9:20 9:30 9:40 9:50 10:00 10:1010:2010:3010:40CPU

作业A

作业B

作业D

作业E

作业C作业D作业D作业作业A作业C作业作业作业A作业C作业AD2DD作业作业A3D作业作业A作业业B作E作业C作业业B作E作业C5作业A

CPUA、B、D、E、C。CPUCPU队列CPU后备待就绪等作业B队列CPU后备待就绪等作业C备 就绪等待后等待CPU备 就绪等待后等待就绪等待后备队列作业D就绪等待后备队列cpucpu作业E作业执行次序进输入井时间装入主存时间开始执行时间执行结束时间周转时间作业A8:308:308:309:1040(分)作业B8:508:509:109:3545作业D9:059:109:359:5550作业E9:109:359:5510:0555作业C9:009:5510:0510