操作系统第三章作业讲解.pdf

《操作系统第三章作业讲解.pdf》由会员分享，可在线阅读，更多相关《操作系统第三章作业讲解.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 作业讲解作业讲解1 1、有、有 5 5 个作业进入就绪队列等待运行，预计它们的运行时间分别为个作业进入就绪队列等待运行，预计它们的运行时间分别为9 9、6 6、3 3、5 5 与与 X X，它们以什么样的调，它们以什么样的调度顺序运行时会取得最小的响应时间？（答案与度顺序运行时会取得最小的响应时间？（答案与 X X 值有关）值有关）答：短作业优先调度算法是使响应时间最小的调度算法：0 X 3时，调度顺序为： X、3、5、6、93 X 5时，调度顺序为： 3、X、5、6、95 X 6时，调度顺序为： 3、5、X、6、96 9 时，调度顺序为： 3、5、6、9、X2 2、假设一个系统

2、中有、假设一个系统中有 4 4 个进程，它们的到达时间和服务时间如表所示，忽略个进程，它们的到达时间和服务时间如表所示，忽略 I/OI/O 以及其他开销时间，若以及其他开销时间，若分别按先来先服务（分别按先来先服务（FCFSFCFS） 、非抢占及抢占的短进程优先（、非抢占及抢占的短进程优先（SPFSPF） 、高响应比优先（、高响应比优先（HRRNHRRN） 、时间片轮转、时间片轮转（RRRR，时间片，时间片=1=1） 、多级反馈队列调度算法（、多级反馈队列调度算法（FBFB，第，第 i i 级队列的时间片级队列的时间片=2=2i-1i-1）进行）进行 CPUCPU 调度，请给出各调度，请给出各

3、进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。进程进程到达时间到达时间服务时间服务时间A A0 05 5B B1 12 2C C3 39 9D D6 67 7算法时间完成时间周转时间带权周转时间进程A551551771.455112122.413132.6B763763321763431.5652.5CD10.251.979.751.8359.251.43510.251.9712.752.113.252.365162313171.442.4323142082.221.1423142082.221.

4、14162313171.442.43232220162.222.29232120152.222.14平均时间FCFS完成时间SPF（非抢占）周转时间带权周转时间SPF（抢占）完成时间周转时间带权周转时间完成时间周转时间带权周转时间完成时间周转时间带权周转时间完成时间周转时间带权周转时间HRRNRR（q=1）FB（q=2i-1）3 3、若有、若有 4 4 个周期性任务，任务个周期性任务，任务 A A 要求每要求每 30ms30ms 执行一次，执行时间为执行一次，执行时间为 15ms15ms；任务；任务 B B 要求每要求每 50ms50ms 执行一执行一次，次，执行时间为执行时间为 5ms5ms

5、；任务任务 C C 要求每要求每 50ms50ms 执行一次，执行一次，执行时间为执行时间为 15ms15ms；任务任务 D D 要求每要求每 100ms100ms 执行一次，执行一次，执行时间为执行时间为 10ms10ms，应如何按最低松弛度优先算法对它们进行，应如何按最低松弛度优先算法对它们进行 CPUCPU 调试？调试？ （要求画出（要求画出 0-150ms0-150ms 时段的调时段的调度时序图，并列出每次切换时每个任务的松弛度）度时序图，并列出每次切换时每个任务的松弛度）答：对于上面的 4 个周期性任务，利用最低松弛度优先算法进行调度的情况如图所示：0 010102020303040

6、4050506060707080809090100100110110120120130130140140150150A1,B1B3,C3A6,B4B2,C2A3A2A5A4D2C1,D1C4到达时间必须完成时间A1A2A4A5,B3A3B2,C2B1,C1D1C3140140 1451450 015153030 3535656580809090 95951101101251255050松弛度D1=10B2=45A5=10A2=15A4=10D2=55A1=15B2=15C2=35B3=20B1=15B1=45D1=40D2=65D1=60C1=35B3=35A3=10B3=5D1=90A2=1

7、0A4=15B1=30C3=25D2=60B2=30D1=50B2=5C1=20D2=80D1=25D1=75D1B2A4A3C2A1C1B1A2A5B3D2C3任务执行110110125125140140 1451451551550 015153030 35355050656580809090 95954 4、3 3 个进程共享个进程共享 4 4 个同类型的资源，每个进程最大需要个同类型的资源，每个进程最大需要 2 2 个资源，请问该系统是否会因为竞争该资源而个资源，请问该系统是否会因为竞争该资源而死锁？死锁？答：答：该系统不会因为竞争该类资源而死锁。因为，必有一个进程可获得2 个资源故能顺

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

9、出现下面的资源分配情况：ProcessProcessP0P1P2P3P4AllocationAllocation00321000135401320014NeedNeed00121650235605520658AvailableAvailable1522试问：1）该状态是否安全（要求列出安全性算法检查表）？2）若进程 P2 提出请求 Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？3）如果系统立即满足P2 的上述请求，请问，系统是否立即进入死锁状态，请说明原因？答：1）利用安全性算法对上面的状态进行分析，找到了一个安全序列P0、P3、P1、P2、P4，

10、故系统是安全的。资源情况进程WorkABCDNeedABCDAllocationABCDWork+AllocationABCDFinishP0P3P1P2P415221554168626863913100012055216502356065800320132100013540014155416862686391310391414TrueTrueTrueTrueTrue2）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)系统先假

11、定可为 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不能满足任何进程的请求，故系统进入不安全状态。此时当进程 P2 提出请求 Request(1,2,2,2)后，系统不能将资源分配给它。3）系统立即满足进程P2 的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并因得不到

12、资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。7 7、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系统会发生死锁吗？统会发生死锁吗？进程P1P2P3P4当前分配数R12310R20131R30001待分配的请求R11000R21001R30010R10可用资源R20R30P1P1P2P2P3P3P4P4R1R1R2R2R3R3P1P1P2P2P3P3P4P4P2P2只有分配边，没有请求只有分

13、配边，没有请求边，所以首先可以将边，所以首先可以将P2P2所有所有的边化简的边化简R1R1R2R2R3R3P1P1P2P2P3P3P4P4P2P2释放资源后，释放资源后，P1P1与与P4P4都可都可以获得资源，运行结束。所以获得资源，运行结束。所以选择以选择P1P1化简化简R1R1R2R2R3R3P1P1P2P2P3P3P4P4P4P4可以获得资源，运行结束。可以获得资源，运行结束。R1R1R2R2R3R3P1P1P2P2P3P3P4P4所有结点都成为孤立结点，所以所有结点都成为孤立结点，所以图是可以完全化简的，不会发生图是可以完全化简的，不会发生死锁死锁R1R1R2R2R3R3存在两种化简序

14、列 1）p2-p1-p4-p3；2）p2-p4-p1-p38 8、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，而不是存在的资源数）而不是存在的资源数） 。进程P1P2当前分配数R111最大分配数R132P3P43297答：如果R1 有一个资源可用，能保证P2 运行完。然后P2 释放它现在使用的资源，使得R1 类型的资源 2个可用，这将允许 P1 执行完。P1 释放它使用的资源后，R1 类型的资源数增加为 3 个可用。只有 3个 R1 类型的资源，如果P3、P4

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

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

17、的轮转算法、抢占式优先权调度算法、多级反馈队列调度算法实时系统可采用的进程调度算法有：非抢占式优先权调度算法、抢占式优先权调度算法、最早截止时间优先算法、最低松弛度优先算法（后两种都属于高优先权优先的实时调度算法）5 5、在银行家算法中，若出现下面的资源分配情况：、在银行家算法中，若出现下面的资源分配情况：ProcessProcessP0P1P2P3P4AllocationAllocation00321000135400320014NeedNeed00121650235606520656AvailableAvailable1622试问：1）该状态是否安全？2）若进程 P2 提出请求 Reque

18、st(1,2,2,2)后，系统能否将资源分配给它？3）如果系统立即满足P2 的上述请求，请问，系统是否立即进入死锁状态？答：1）利用安全性算法对上面的状态进行分析，找到了一个安全序列P0、P3、P4、P1、P2，故系统是安全的。资源情况进程P0P3P4P1P2WorkABCD1622165416861691026910NeedABCD00120652065616502356AllocationABCD00320032001410001354Work+AllocationABCD165416861691026910391414FinishTrueTrueTrueTrueTrue2）P2 发出请求

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