操作系统第三章作业讲解

1、.第三章 作业讲解1、有5个作业进入就绪队列等待运行，预计它们的运行时间分别为9、6、3、5与X，它们以什么样的调度顺序运行时会取得最小的响应时间？（答案与X值有关）答：短作业优先调度算法是使响应时间最小的调度算法：0 < X 3时，调度顺序为： X、3、5、6、93 < X 5时，调度顺序为： 3、X、5、6、95 < X 6时，调度顺序为： 3、5、X、6、96 < X 9时，调度顺序为： 3、5、6、X、9X > 9时，调度顺序为： 3、5、6、9、X2、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按先来先服

2、务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（FB，第i级队列的时间片=2i-1）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。进程到达时间服务时间A05B12C39D67算法时间进程平均时间ABCDFCFS完成时间周转时间带权周转时间55176316131.4423172.4310.251.97SPF（非抢占）完成时间周转时间带权周转时间55176323202.221481.149.751.835SPF（抢占）完成时间周转时间带权周转时间771.432123

3、202.221481.149.251.435HRRN完成时间周转时间带权周转时间55176316131.4423172.4310.251.97RR（q=1）完成时间周转时间带权周转时间12122.4431.523202.2222162.2912.752.1FB（q=2i-1）完成时间周转时间带权周转时间13132.6652.523202.2221152.1413.252.3653、若有4个周期性任务，任务A要求每30ms执行一次，执行时间为15ms；任务B要求每50ms执行一次，执行时间为5ms；任务C要求每50ms执行一次，执行时间为15ms；任务D要求每100ms执行一次，执行时间为10m

4、s，应如何按最低松弛度优先算法对它们进行CPU调试？ （要求画出0-150ms时段的调度时序图，并列出每次切换时每个任务的松弛度）答：对于上面的4个周期性任务，利用最低松弛度优先算法进行调度的情况如图所示：1301401501201100908070604030201010050B2,C2A6,B4C4A5A4A3A2A1,B1C1,D1B3,C3D2到达时间必须完成时间A5,B3C3A4A3A2A1B2,C2D1B1,C180651401451251109095503530150松弛度D2=55A5=10B3=20D2=65A4=10D1=10B2=15B2=45C2=35D1=40A2=1

5、5B1=15D1=60A1=15B1=45C1=35D1=90B3=5D2=60B3=35C3=25D2=80A4=15B2=5A3=10B2=30D1=25A2=10D1=50B1=30C1=20D1=75D1B3A3C2D2A5C3A4B2A2B1C1A1任务执行806515514011014512595503530150904、3个进程共享4个同类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争该资源而死锁？答：该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得2个资源故能顺利完成，并释放出其所占用的2个资源给其他进程使用，使它们也顺利完成。5、不安全状态是否必然导致

6、系统进入死锁状态？举例说明。答：不安全状态不一定导致进入死锁状态。因为，安全性检查中使用的向量Max是进程执行前提供的，而在实际运行过程中，一进程需要的最大资源量可能小于Max，如一进程对应的程序中有一段进行错误处理的代码，其中需要n个A种资源，若该进程在运行过程中没有碰到相应的错误，而不需要调用该段错误处理代码，则它实际上将完全不会请求这n个A种资源。6、在银行家算法中，若出现下面的资源分配情况：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

7、 2P40 0 1 40 6 5 8试问：1）该状态是否安全（要求列出安全性算法检查表）？ 2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？ 3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态，请说明原因？答：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

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 14TrueTrueTrueTrueTrue2）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，Allocati

9、on2和Need2向量： Available=（0，3，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）进行安全性检查：此时对所有的进程，条件Needi<=Available(0,3,0,0)都不成立，即Available不能满足任何进程的请求，故系统进入不安全状态。此时当进程P2提出请求Request(1,2,2,2)后，系统不能将资源分配给它。3）系统立即满足进程P2的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不

10、到资源而阻塞时，系统才进入死锁状态。7、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系统会发生死锁吗？进程当前分配数待分配的请求可用资源R1R2R3R1R2R3R1R2R3P1P2P3P4231001310001100010010010000存在两种化简序列1）p2-p1-p4-p3；2）p2-p4-p1-p38、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，而不是存在的资源数）。进程当前分配数最大分配数R1R1P1P2P3P411323297答：如果R1有一个资源可用，能保证P2运行完。然后P2释放它现在使用

11、的资源，使得R1类型的资源2个可用，这将允许P1执行完。P1释放它使用的资源后，R1类型的资源数增加为3个可用。只有3个R1类型的资源，如果P3、P4请求分配最大数目的资源，P3与P4就仍然处于死锁状态。如果一开始就有3个R1类型资源，而不是1个，P4就可以获得5个R1的可用资源并运行完。再加上P4原来占用的2个R1资源，就可以让P3运行。所以使该状态安全的所需可用资源的最小个数为3。9、在时间片轮转法中，应如何确定时间片的大小？答：时间片长度可按如下方法确定：1）系统对相应时间的要求；2）就绪进程的数目：数目越多，时间片越小（当响应时间一定时）；3）系统的处理能力：应当使用户输入通常在一个时

12、间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长；10、在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法能使资源利用率最高？答：解决死锁问题可归纳为三种方法：预防死锁、避免死锁、检测死锁和解除死锁。其中预防死锁最容易实现的；避免死锁使资源的利用率最高。课本上习题8、在批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？答：批处理系统可采用的进程调度算法有：高优先权优先调度算法、多级反馈队列调度算法、FCFS、SJF 分时系统可采用的进程调度算法有：基于时间片的轮转算法、抢占式优先权调度算法、多级反馈队列调度算法实时系统可采用的进程调度算法有：非抢占式优

13、先权调度算法、抢占式优先权调度算法、最早截止时间优先算法、最低松弛度优先算法（后两种都属于高优先权优先的实时调度算法）5、在银行家算法中，若出现下面的资源分配情况：ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 0 3 20 6 5 2P40 0 1 40 6 5 6试问：1）该状态是否安全？ 2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？ 3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态？答：1）利用安全性算法

14、对上面的状态进行分析，找到了一个安全序列P0、P3、P4、P1、P2，故系统是安全的。资源情况进程WorkA B C DNeedA B C DAllocationA B C DWork+AllocationA B C DFinishP0P3P4P1P21 6 2 21 6 5 41 6 8 61 6 9 102 6 9 100 0 1 20 6 5 20 6 5 61 6 5 02 3 5 60 0 3 20 0 3 20 0 1 41 0 0 0 1 3 5 41 6 5 41 6 8 61 6 9 102 6 9 103 9 14 14TrueTrueTrueTrueTrue2）P2发出请求向量Request(1,2,2,2)后，系统按银行家算法进行检查：Request2(1,2,2,2)<=Need2(2,3,5,6)Request2(1,2,2,2)<=Available(1,6,2,2)系统先假定可为P2分配资源，并修改Available，Allocation2和Need2向量： Available=（0，4，0，0） Allocation2=(2,5,7,6) Need2=（1，1，3，4）进行安全性检查：此时对所有的进程