青岛理工大学操作系统作业答案(共12页).doc

《青岛理工大学操作系统作业答案(共12页).doc》由会员分享，可在线阅读，更多相关《青岛理工大学操作系统作业答案(共12页).doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第1章 作业综合题1、设内存中有三道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O操作时间如表所示（单位：ms）。三道程序的操作时间 程序操作ABC计算306020I/O403040计算101020假设三道程序使用相同设备I/O操作，即程序是以串行方式使用设备，调度程序的执行时间忽略不计，试计算出在单道和多道两种情况下，完成这三道程序各要花多少时间？要求画出多道运行的时序图。（假定在多道方式下采用的是基于优先级的非抢占调度程序）解：采用单道方式运行这三道程序，运行次序为A、B、C，故总的运行时间为：(30+40+10)+(60+30+10)+(20

2、+40+20)=260ms 采用多道方式运行这三道程序，A、B、C这三道进程的运行存在并行，故总的运行时间如图所示为180ms第二章1、如图所示，有一计算进程和一打印进程，它们共享一个单缓冲区，计算进程不断地计算出结果并将它放入单缓冲区中，打印进程则负责从单缓冲区中取出每一个结果进行打印。请用信号量来实现它们的同步关系。答：方法一：从临界资源的角度来思考：本题中有两类临界资源：第一类是计算进程争用的空闲缓冲区，初始状态下有一个空闲缓冲可供使用，设置信号量empty，初值为1；第二类是打印进程争用的已放入缓冲区中的打印结果，初始状态下缓冲区中无结果可打印，设置信号量full，初值为0。var f

3、ull, empty: semaphore:=0,1;begin parbegin cp:begin repeat computer next number; wait(empty); add the number to buffer; signal(full); until false end pp:begin repeat wait(full); take a number from buffer; signal(empty); print the number; until false end parendend2、试用信号量解决读者写者问题，使得写者与读者优先级根据到达顺序确定（读写平

4、等）。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者1）典型错误代码讲解：不增加任何信号量Var rmutex, wmutex:semaphore=1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if Readcount=0 then wait(wmutex); Readcount =

5、 Readcount+1; signal(rmutex); perform read operation; wait(rmutex); Readcount= Readcount-1; if Readcount=0 then signal(wmutex); signal(rmutex); until false; end writer:begin repeat if readcount0 then wait(rumtex); wait(wmutex); perform write operation; signal(rmutex); signal(wmutex); until false; en

6、d parend end到达序列：R1, R2, W1, R3, R4, W2进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者R2到达rmutex=0rmutex=1Readcount=2执行/就绪W1到达rmutex=0阻塞1阻塞Readcount0R3到达阻塞1阻塞rmutex=0R4到达阻塞2阻塞rmutex=0W2到达阻塞3阻塞rmutex=0R1离开阻塞4阻塞rmutex=0R2离开阻塞5阻塞rmutex=0产生死锁2）解决方案 var S, rmutex, wmu

7、tex: semaphore:=1, 1,1; readcount: integer:= 0;reader: begin repeat wait(S); wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until fals

8、e end writer: begin repeat wait(S); wait(wmutex); perform write operation; signal(wmutex); signal(S); until false end到达序列：R1, R2, W1, R3, R4, W2进程行为S=1rmutex=1wmutex=1readcount=0备注R1到达S=0S=1rmutex=0rmutex=1wmutex=0readcount=1第一个读者执行/就绪R2到达S=0S=1rmutex=0rmutex=1readcount=2执行/就绪W1到达S=0阻塞1第一个写者R3到达阻塞1R

9、4到达阻塞2W2到达阻塞3R1离开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤醒W1W1被唤醒wmutex=0执行/就绪W1离开S=1wmutex=1负责唤醒R33、请给出一个写者优先的“读者写者”问题的算法描述。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试列出类似如下测试结果进程行为rmutex=1wmutex=1Readcount=0状态备注R1到达rmutex=0rmutex=1wmutex=0Readcount=1执行/就绪第1位读者答：为使写者优先，可在原来的读优先算

10、法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成。初值为0的整型变量writecount用来对写者进行计数；初值为1 的互斥信号量mutex用来实现多个写者对writecount的互斥访问。读者与写者进程算法描述如下： var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1; writecount, readcount: integer:=0,0;reader: begin repeat wait(S); wait(rmutex); if readcount=0 then wait(wmute

11、x); readcount:=readcount+1; signal(rmutex); signal(S); perform read operation; wait(rmutex); readcount:=readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false end writer: begin repeat wait(mutex); if writecount=0 then wait(S); writecount:=writecount+1; signal(mutex); wait(wmute

12、x); perform write operation; signal(wmutex); wait(mutex); writecount:=writecount-1; if writecount=0 then signal(S); signal(mutex); until false end到达序列：R1, R2, W1, R3, R4, W2进程行为S=1mutex=1rmutex=1wmutex=1writecount=0readcount=0备注R1到达S=0S=1rmutex=0rmutex=1wmutex=0readcount=1第一个读者执行/就绪R2到达S=0S=1rmutex=

13、0rmutex=1readcount=2执行/就绪W1到达S=0mutex=0mutex=1阻塞1writecount=1第一个写者R3到达阻塞1R4到达阻塞2W2到达mutex=0mutex=1阻塞2writecount=2R1离开rmutex=0rmutex=1readcount=1R2离开rmutex=0rmutex=1wmutex=1readcount=0负责唤醒W1W1被唤醒wmutex=0执行/就绪W1离开mutex=0mutex=1wmutex=1writecount=1负责唤醒W23、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别

14、按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（MFQ，第i级队列的时间片=2i-1）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，填入下表中（抢占式算法要求画出调度时序图，HRRN算法要求列出调度时的响应比）。30”进程到达时间服务时间A05B12C39D67算法时间进程平均时间ABCDFCFS完成时间周转时间带权周转时间SPF（非抢占）完成时间周转时间带权周转时间SPF（抢占）完成时间周转时间带权周转时间RR（q=1）完成时间周转时间带权周转时间M

15、FQ（q=2i-1）完成时间周转时间带权周转时间作业号到达时间运行时间开始时间完成时间周转时间带权周转时间调度依据平均周转时间为：平均带权周转时间为：算法时间进程平均时间ABCDFCFS完成时间周转时间带权周转时间55176316131.4423172.4310.251.97SPF（非抢占）完成时间周转时间带权周转时间55176323202.221481.149.751.835SPF（抢占）完成时间周转时间带权周转时间771.432123202.221481.149.251.435RR（q=1）完成时间周转时间带权周转时间12122.4431.523202.2222162.2912.752.1

16、MFQ（q=2i-1）完成时间周转时间带权周转时间13132.6652.523202.2221152.1413.252.365作业号到达时间运行时间开始时间完成时间周转时间带权周转时间调度依据A050551就绪队列中只有AB125763RPB=3RPC=11/9=1.22C39716131.44RPC=15/9=1.67RPD=10/7=1.43D671623172.43就绪队列中只有D平均周转时间为：10.25平均带权周转时间为：1.974、在一个软实时系统中有四个周期性任务，任务A、B、C、D分别要求每50ms、100ms、200ms、250ms执行一次，假定A、B、C、D的执行时间分别为

17、35ms、20ms、10ms与x ms，那么要使得这个实时系统为可调度的，x的最大值为多少？（要求列出计算公式）10”答：实时系统可调度的条件为： ，其中Ci 表示处理时间，Pi表示周期时间根据题目所列条件，必须满足35/50 + 20/100 + 10/200 + x/250=1，所以x的最大值为12.5ms5、什么是最低松弛度优先调度算法？它采用何种调度方式？抢占时机是什么？10”答：LLF算法根据实时任务的松弛度（松弛度 = 必须完成的时间 其本身的运行时间 - 当前时间）来确定任务的优先级，即任务的松弛度愈低，其优先级愈高。在实现该算法时，要求系统中有一个按松弛度排序的实时任务就绪队列

18、。该算法主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它便立即抢占CPU，以保证按截止时间的要求完成任务。6、若有4个周期性任务，任务A要求每30ms执行一次，执行时间为15ms；任务B要求每50ms执行一次，执行时间为5ms；任务C要求每50ms执行一次，执行时间为15ms；任务D要求每100ms执行一次，执行时间为10ms，应如何按最低松弛度优先算法对它们进行CPU调试？ （要求画出0-150ms时段的调度时序图，并列出每次切换时每个任务的松弛度）20”对于上面的4个周期性任务，利用最低松弛度优先算法进行调度的情况如图所示：1301401501201100908070604030

19、201010050B2,C2A6,B4C4A5A4A3A2A1,B1C1,D1B3,C3D2到达时间必须完成时间A5,B3C3A4A3A2A1B2,C2D1B1,C180651401451251109095503530150松弛度D2=45A5=10B3=20D2=65A4=10D1=10B2=15B2=45C2=35D1=40A2=15B1=15D1=60A1=15B1=45C1=35D1=90B3=5D2=60B3=35C3=25D2=80A4=15B2=5A3=10B2=30D1=25A2=10D1=55B1=30C1=20D1=75D1B3A3C2D2A5C3A4B2A2B1C1A1任

20、务执行8065155140110145125955035301509010、在银行家算法中，若出现下面的资源分配情况： 30”ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 5 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 1 3 20 5 5 2P40 0 1 40 6 5 8试问：1）该状态是否安全（要求列出安全性算法检查表）？ 2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？ 3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态，

21、请说明原因？答：1）利用安全性算法对上面的状态进行分析，找到了一个安全序列P0、P3、P1、P2、P4，故系统是安全的。资源情况进程WorkA B C DNeedA B C DAllocationA B C DWork+AllocationA B C DFinishP0P3P1P2P41 5 2 21 5 5 41 6 8 62 6 8 63 9 13 100 0 1 20 5 5 21 6 5 02 3 5 60 6 5 80 0 3 20 1 3 21 0 0 01 3 5 4 0 0 1 41 5 5 41 6 8 62 6 8 63 9 13 103 9 14 14TrueTrueTr

22、ueTrueTrue2）P2发出请求向量Request(1,2,2,2)后，系统按银行家算法进行检查：Request2(1,2,2,2)=Need2(2,3,5,6)Request2(1,2,2,2)=Available(1,5,2,2)系统先假定可为P2分配资源，并修改Available，Allocation2和Need2向量： Available=（0，3，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）进行安全性检查：此时对所有的进程，条件Needi=Available(0,3,0,0)都不成立，即Available不能满足任何进程的请求，故系统进入不

23、安全状态。此时当进程P2提出请求Request(1,2,2,2)后，系统不能将资源分配给它。3）系统立即满足进程P2的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。11、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系统会发生死锁吗？20”进程当前分配数待分配的请求可用资源R1R2R3R1R2R3R1R2R3P1P2P3P4231001310001100010010010000存在两种

24、化简序列1）p2-p1-p4-p3；2）p2-p4-p1-p312、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，而不是存在的资源数）。10”进程当前分配数最大分配数R1R1P1P2P3P411323297答：如果R1有一个资源可用，能保证P2运行完。然后P2释放它现在使用的资源，使得R1类型的资源2个可用，这将允许P1执行完。P1释放它使用的资源后，R1类型的资源数增加为3个可用。只有3个R1类型的资源，如果P3、P4请求分配最大数目的资源，P3与P4就仍然处于死锁状态。如果一开始就有3个R1类型资源，而不是1个，P4就可以获得5个R1的可用资源并运行完。再加上P4原来占用的2个R1资源，就可以让P3运行。所以使该状态安全的所需可用资源的最小个数为3。专心-专注-专业