操作系统习题课.ppt

《操作系统习题课.ppt》由会员分享，可在线阅读，更多相关《操作系统习题课.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统习题课操作系统习题课操作系统习题课操作系统习题课Part 1conceptiona)Operating system,batch system,Time-sharing system b)process,file,system call,threadc)JVM(JAVA virtual machine),LWP(light weigh process),PCB,deadlock,d)Critical Section,IPC,Part 2 课后习题讲解课后习题讲解调度算法简介调度算法简介a)FCFS按照作业到达后备作业队列的先后次按照作业到达后备作业队列的先后次序来选择作业。序来选择作业

2、。b)SJF根据每个作业下次要运行的根据每个作业下次要运行的CPU脉冲长脉冲长度，调度最短的作业度，调度最短的作业c)Priority按照进程的优先权高低来调度，使按照进程的优先权高低来调度，使高优先权进程得到优先处理高优先权进程得到优先处理d)RR算法总是选择就绪队列中第一个进程，允算法总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间许其占有处理机一个时间片的时间,以先来以先来先服务的原则进行调度先服务的原则进行调度6.3 考虑下面进程集，进程占用考虑下面进程集，进程占用的的CPU区间长度以毫秒来计算：区间长度以毫秒来计算：Process Burst Time Priority

3、 P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2 假设在时刻假设在时刻0 0进程以进程以P1,P2,P3,P4,P5P1,P2,P3,P4,P5的顺的顺序到达。序到达。a.画出画出4个个Gantt图分别演示用图分别演示用FCFJ、SJF、非抢占优先级（数字小代表优先、非抢占优先级（数字小代表优先级高）和级高）和RR（时间片（时间片=1）算法调度时进）算法调度时进程的执行过程。程的执行过程。b.在在a a里每个进程在每种调度算法里每个进程在每种调度算法下的周转时间是多少？下的周转时间是多少？周转时间周转时间 ：从提交到运行结束的全部时：从提交到运行结束的全部时间间 FCF

4、S RR SJF Priority P1 10 19 19 16P2 11 2 1 1P3 13 7 4 18P4 14 4 2 19P5 19 14 9 6c.c.在在a a里每个进程在每种调度里每个进程在每种调度算法下的等待时间是多少算法下的等待时间是多少？等待时间等待时间 ：进程在就绪队列中等待调度：进程在就绪队列中等待调度的时间总和。的时间总和。周转时间周转时间=等待时间等待时间+运行时间运行时间 FCFS RR SJF PriorityP1 0 9 9 6P2 10 1 0 0P3 11 5 2 16P4 13 3 1 18P5 14 9 4 1d.哪一种调度算法的平均等待时哪一种调

5、度算法的平均等待时间对所有进程而言最小？间对所有进程而言最小？平均等待时间就是将每个算法的所有等待平均等待时间就是将每个算法的所有等待时间相加后求平均。时间相加后求平均。在这道题中就是短作业优先。在这道题中就是短作业优先。6.4 假设下列进程在所指定的时刻假设下列进程在所指定的时刻到达等待执行。每个进程将运行所到达等待执行。每个进程将运行所列出的时间量长度。采用非抢占式列出的时间量长度。采用非抢占式调度算法。调度算法。Process Arrival Time Burst Time P1 0.0 8 P2 0.4 4 P3 1.0 1a.当使用当使用FCFS调度算法时，这些调度算法时，这些进程的

6、平均周转时间是多少？进程的平均周转时间是多少？解答：解答：FCFS P1 8 P2 11.6 P3 12平均周转时间平均周转时间=（8+11.6+12）/3=10.53b.使用使用SJF的平均周转时间。的平均周转时间。解答：解答：SJF P1 8 P2 12.6 P3 8 平均周转时间平均周转时间=（8+12.6+8）/3=9.53C.SJF被认为可以提高性能，但是注意在被认为可以提高性能，但是注意在时刻时刻0选择运行进程选择运行进程P1是因为无法知道两个是因为无法知道两个更短的进程很快会到来。更短的进程很快会到来。计算一下如果第一个时间单元计算一下如果第一个时间单元CPU置为置为空闲，然后使

7、用空闲，然后使用SJF，计算平均周转时间，计算平均周转时间？解答：解答：一个时间单元以后一个时间单元以后P1,P2,P3全全部到达。这是执行的顺序就是部到达。这是执行的顺序就是P3,P2,P1 平均周转时间为平均周转时间为6.86 这个算法是预知调度。注意进程这个算法是预知调度。注意进程P1和和P2在等待，所以他们的等待时间可能会在等待，所以他们的等待时间可能会增加增加。6.8 下列算法之间的联系下列算法之间的联系a.Priority and SJF 最短的作业有最高的优先级。最短的作业有最高的优先级。c.Priority and FCFS FCFS将最高的优先级给了先达到的作将最高的优先级给

8、了先达到的作业。业。d.RR and SJF（特别注意）（特别注意）没有关系没有关系8.9 N个进程共享个进程共享M个同类资源，个同类资源，若每个进程都需要该类资源，而且若每个进程都需要该类资源，而且各进程对该类资源的最大需求之和各进程对该类资源的最大需求之和小于小于M+N。请说明该系统不会因为。请说明该系统不会因为竞争该资源而死锁。竞争该资源而死锁。死锁死锁Deadlock：计算机系统中多道程：计算机系统中多道程序并发执行时，两个或两个以上的进程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进现象（僵局）

9、，如无外力作用，这些进程将永远不能再向前推进。程将永远不能再向前推进。用用Maxi,Needi,Allocationi分别表示第分别表示第I个进程对该类资源的最大需求量、还个进程对该类资源的最大需求量、还需要量、已分配到的量，则有：需要量、已分配到的量，则有：Needi 0（对所有（对所有I），），Maxi M+N 若系统已因竞争该类资源而进入死锁，则意若系统已因竞争该类资源而进入死锁，则意味着已有一个以上的进程因申请不到该资源味着已有一个以上的进程因申请不到该资源而阻塞，而而阻塞，而M个资源肯定已经全部分配出去个资源肯定已经全部分配出去了，即：了，即：Allocationi=M，因此有因此有

10、 Needi=Maxi-Allocationi M+N-M，即，即 Needi N，这样，至少必存在一个进程，其这样，至少必存在一个进程，其Needi0，这说明此时至少有一个进程已经获得了所，这说明此时至少有一个进程已经获得了所需的全部资源，那么它就能执行完成并释放需的全部资源，那么它就能执行完成并释放它所占有的资源，这与前面的假设（已发生它所占有的资源，这与前面的假设（已发生死锁）矛盾。所以系统不可能因为竞争该类死锁）矛盾。所以系统不可能因为竞争该类资源而死锁。资源而死锁。Part 3 exercise 练习题分为两个部分一部分为进程练习题分为两个部分一部分为进程管理另一部分为作业管理管理另

11、一部分为作业管理1、如何理解进程的顺序性与并发、如何理解进程的顺序性与并发性？性？1、顺序性、顺序性 顺序性包括两层含义：（顺序性包括两层含义：（1）内部顺序性，对于一个进程）内部顺序性，对于一个进程来说，它的所有指令是按序执行的；（来说，它的所有指令是按序执行的；（2）外部顺序）外部顺序性，对于多个进程来说，所有进程是依次执行的。性，对于多个进程来说，所有进程是依次执行的。例如，假如有例如，假如有P1和和P2两个进程，其活动分别为：两个进程，其活动分别为：P1活动：活动：A1 A2 A3 A4 P2活动：活动：B1 B2 B3 B4 顺序执行时，有如下两种情形：顺序执行时，有如下两种情形：情

12、形情形1：A1 A2 A3 A4 B1 B2 B3 B4 情形情形2：B1 B2 B3 B4 A1 A2 A3 A4 2、并发性、并发性 并发性包括如下两层含义：（并发性包括如下两层含义：（1）内部顺序性，对于一个）内部顺序性，对于一个进程来说，它的所有指令是按序执行的；（进程来说，它的所有指令是按序执行的；（2）外部）外部并发性，对于多个进程来说，所有进程是交叉执行的。并发性，对于多个进程来说，所有进程是交叉执行的。例如，对于上面例如，对于上面P1和和P2两个进程来说，并发执行有许多两个进程来说，并发执行有许多情形，如：情形，如：情形情形1：A1 B1 B2 A2 A3 B3 A4 B4 情

13、形情形2：B1 B2 A1 A2 A3 B3 B4 A4 并发进程在其执行过程中，出现哪种交叉情形是不可预并发进程在其执行过程中，出现哪种交叉情形是不可预知的，这就是并发进程的不确定性，操作系统应当保知的，这就是并发进程的不确定性，操作系统应当保证：无论出现何种交叉情形，每个进程运行的结果都证：无论出现何种交叉情形，每个进程运行的结果都应当是唯一的，正确的。应当是唯一的，正确的。2、什么是进程的同步与互斥、什么是进程的同步与互斥？答：进程的同步与互斥是指进程在推进时的相互答：进程的同步与互斥是指进程在推进时的相互制约关系。在多道程序系统中，由于进程合作制约关系。在多道程序系统中，由于进程合作与

14、资源共享，这种进程间的制约称为可能。我与资源共享，这种进程间的制约称为可能。我们把前者称为进程同步，后者称为进程互斥。们把前者称为进程同步，后者称为进程互斥。进程同步是进程间共同完成一项任务时直接进程同步是进程间共同完成一项任务时直接发生相互作用的关系。发生相互作用的关系。进程互斥是进程之间的间接制约关系。在多进程互斥是进程之间的间接制约关系。在多道系统中，每次只允许一个进程访问的资源称道系统中，每次只允许一个进程访问的资源称为临界资源，进程互斥就是保证每次只有一个为临界资源，进程互斥就是保证每次只有一个进程使用临界资源进程使用临界资源。5、某系统的进程状态转换图如下图、某系统的进程状态转换图

15、如下图所示，请回答所示，请回答 引起各种状态转换的典型事件有哪些？引起各种状态转换的典型事件有哪些？2143执行态就绪态等待态就绪状态：进程就绪状态：进程已分配到除已分配到除CPU以外的所有资源，以外的所有资源，获得获得CPU后立即后立即执行。执行。执行状态：进程执行状态：进程已经获得已经获得CPU，正在执行。正在执行。等待状态：正在等待状态：正在执行的进程由于执行的进程由于某事件而暂时无某事件而暂时无法执行，便放弃法执行，便放弃处理机而处于暂处理机而处于暂停状态。停状态。6、在下列的进程状态变换中，（、在下列的进程状态变换中，（C ）是不可能发生的。）是不可能发生的。A，执行，执行等待等待

16、B，执行，执行就绪就绪 C，等待，等待执行执行 D，等待，等待就绪就绪9、产生死锁的原因是（、产生死锁的原因是（C、D）A，资源共享，资源共享 B，并发执行的进程，并发执行的进程 数太多数太多C，系统资源不足，系统资源不足 D，进程推进顺序，进程推进顺序非法非法9、关于死锁的一些概念、关于死锁的一些概念a)产生死锁的原因：产生死锁的原因：（1）竞争资源竞争资源 当资源数目不足以满足进程的需要的当资源数目不足以满足进程的需要的时候，会引起进程对资源的竞争而产时候，会引起进程对资源的竞争而产生死锁。生死锁。（2）进程间推进顺序不当进程间推进顺序不当 进程在运行过程中，请求和释放资进程在运行过程中，

17、请求和释放资源的顺序不当同样也会产生死锁。源的顺序不当同样也会产生死锁。9、关于死锁的一些概念、关于死锁的一些概念b)死锁发生的四个必要条件死锁发生的四个必要条件（1）互斥条件：）互斥条件：只允许一个进程占用这个资源只允许一个进程占用这个资源（2）占有并等待：）占有并等待：至少持有一个资源并且等待获得至少持有一个资源并且等待获得额外的由其他进程所持有的资源额外的由其他进程所持有的资源（3）不剥夺条件：）不剥夺条件：一个资源只有当持有它的进程完一个资源只有当持有它的进程完成任务后，自由的释放成任务后，自由的释放（4）循环等待：）循环等待：等待资源的进程之间存在环等待资源的进程之间存在环 在这四个

18、条件中，条件在这四个条件中，条件1是由设备的固有条件是由设备的固有条件所决定的，不仅不能改变，还应该加以保证。所决定的，不仅不能改变，还应该加以保证。9、关于死锁的一些概念、关于死锁的一些概念c)处理死锁的基本方法处理死锁的基本方法鸵鸟算法鸵鸟算法预防死锁预防死锁避免死锁避免死锁检测和解除死锁检测和解除死锁9、关于死锁的一些概念、关于死锁的一些概念d)预防死锁的方法预防死锁的方法 预防死锁是使必要条件中的预防死锁是使必要条件中的2，3，4不能成立。不能成立。摒弃摒弃“占有并等待占有并等待”(全给或者全全给或者全部不给）部不给）摒弃摒弃“不剥夺条件不剥夺条件”摒弃摒弃“循环等待循环等待”10，从

19、资源分配的角度看，从资源分配的角度看，P操操作意味着向系统申请资源作意味着向系统申请资源 ，V操作意味着释放资源。如果信号操作意味着释放资源。如果信号量的当前值为量的当前值为-6，则表示系统该则表示系统该信号量链表中有信号量链表中有6个等待该资源个等待该资源的进程被阻塞，的进程被阻塞，如果信号量的当如果信号量的当前值为前值为6，则表示该信号量所代则表示该信号量所代表的资源的可用数目是表的资源的可用数目是6。解释：解释：注意信号量负值和正值的含义。注意信号量负值和正值的含义。S.value的初值表示系统中某类资的初值表示系统中某类资源的数目。源的数目。S.value0表示该类资源已经分配表示该类

20、资源已经分配完毕，绝对值表述该信号量链表中已经完毕，绝对值表述该信号量链表中已经阻塞进程的数目。阻塞进程的数目。P、V操作的含义操作的含义P(S)value-;if(value 0)add this process to listblockV(S)value+;if(value=0)remove a process P from listwakeup(P);入口入口s.value=s.value-1s.value0调度进程入等待队列调度进程入等待队列转进程调度转进程调度入口入口s.value=s.value1s.value0唤醒等待队列中的一个进程唤醒等待队列中的一个进程返回或转进程调度返回或

21、转进程调度返回返回返回返回s.value0是是是是否否P原语操作功能流程图原语操作功能流程图V原语操作功能流程图原语操作功能流程图 三、在银行家算法中，若出现三、在银行家算法中，若出现下面的资源分配情况：下面的资源分配情况：Process Allocation Need Available P0003200121622 P110001650 P213542356 P30032 0652 P40014 0656 1622为资源为资源ABCD的的数目数目（1）、该状态是否安全？）、该状态是否安全？安全状态是指系统的一种状态，在安全状态是指系统的一种状态，在此状态下此状态下,系统能按某种顺序（例如系

22、统能按某种顺序（例如P P1 1、P P2 2P Pn n）来为各个进程分配其所需资）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（序地一个个地完成。这个序列（P P1 1、P P2 2.P Pn n）称为）称为安全序列。安全序列。若系统此状态不存在一个安全序列，若系统此状态不存在一个安全序列，则称系统处于则称系统处于不安全状态不安全状态。（1）安全性算法）安全性算法1.Let Work and Finish be vectors of length m and n,respectively.Initialize（让（让

23、Work和和Finish作为长度为作为长度为m和和n的向量）的向量）Work:=AvailableFinish i=false for i-1,3,n.2.Find an i such that both:（找到（找到i）(a)Finish i=false(b)Needi WorkIf no such i exists,go to step 4.3.Work:=Work+AllocationiFinishi:=truego to step 2.4.If Finish i=true for all i,then the system is in a safe state，otherwise in

24、 an unsafe state.返回题目（1）、该状态是否安全？）、该状态是否安全？答：（答：（1）利用安全性算法对上述状态进行分析，找到了一个安）利用安全性算法对上述状态进行分析，找到了一个安全序列（全序列（P0，P3，P4，P1，P2），故该状态是安全的。分析），故该状态是安全的。分析如下表所示如下表所示。processwork Need Allocation Work+allocationfinish P0 1622001200321654TRUEP31654065200321686TRUEP4168606560014169 10 TRUEP1169 10 16501000269 10

25、 TRUEP2269 10 2356135439,14，14TRUE（2）资源请求算法原理）资源请求算法原理 当用户申请一组资源的时候，系当用户申请一组资源的时候，系统必须确定这些资源的分配是否仍统必须确定这些资源的分配是否仍会使系统处于安全状态。会使系统处于安全状态。如果会，就可以分配资源；否如果会，就可以分配资源；否则，系统必须等待直到某个其他进则，系统必须等待直到某个其他进程释放足够的资源为止。程释放足够的资源为止。（2）资源请求算法）资源请求算法1.If Requesti Needi go to step 2.Otherwise,raise error condition,since

26、process has exceeded its maximum claim.2.If Requesti Available,go to step 3.Otherwise Pi must wait,since resources are not available.3.假定给假定给Pi 分配资源分配资源 Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi Requesti4.用安全算法进行检查用安全算法进行检查,看系统是否处于安全状态看系统是否处于安全状态If safe the resourc

27、es are allocated to Pi.If unsafe Pi must wait,and the old resource-allocation state is restored（2）若进程）若进程P2提出请求提出请求Request（1，2，2，2）后，系统能）后，系统能否将资源分配给它？否将资源分配给它？解：解：P2 发出请求发出请求Request（1，2，2，2）后，系统）后，系统按银行家算法进行检查：按银行家算法进行检查：Request（1，2，2，2）=Need2(2,3,5,6),且且Request（1，2，2，2）=Available(1,6,2,2)系统假定可为系统假

28、定可为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)都不成立都不成立,故系统进入故系统进入不安全状态不安全状态.因此因此,不能给不能给P2分配资源分配资源.返回题目（3）如果系统立即满足）如果系统立即满足P2的上述请求，的上述请求，请问，系统是否立即进入死锁状态？请问，系统是否立即进入死锁状态？解

29、：系统立即满足进程解：系统立即满足进程P2的请求的请求(1,2,2,2)后后,并没有马上进入死锁状态并没有马上进入死锁状态.因为此时上述进程并没有申请新的资源，因为此时上述进程并没有申请新的资源，只是进入了不安全状态只是进入了不安全状态。只有当上述进。只有当上述进程提出新的资源请求并导致所有没执行程提出新的资源请求并导致所有没执行完的多个进程因得不到资源而阻塞时，完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。系统才进入死锁状态。四、设在公共汽车上，司机和售票员的四、设在公共汽车上，司机和售票员的活动分别如下：活动分别如下：司机的活动：启动车辆；正常行司机的活动：启动车辆；正常行车；到站

30、停车。车；到站停车。售票员的活动：关车门；售票；售票员的活动：关车门；售票；开车门。开车门。1、在汽车不停地到站、停车以及行驶、在汽车不停地到站、停车以及行驶的过程中，司机和售票员之间的活动有的过程中，司机和售票员之间的活动有什么同步关系？什么同步关系？（1）解答：）解答：首先分析两个进程之间的同步关系。首先分析两个进程之间的同步关系。汽车行驶过程中，司机活动与售票员活动之汽车行驶过程中，司机活动与售票员活动之间的同步关系为：间的同步关系为：售票员关车门后，向司机发开车信号，售票员关车门后，向司机发开车信号，司机接到开车信号后起动车辆，在汽车正常司机接到开车信号后起动车辆，在汽车正常行驶过程中

31、售票员售票，到站时司机停车，行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。售票员在车停后开车门让乘客下车。那么，定义两个信号量那么，定义两个信号量s1：表示是否：表示是否允许司机起动车辆，允许司机起动车辆，s2：表示是否允许售票：表示是否允许售票员开门。初值为员开门。初值为0。2、请将以下描述这两个活动的、请将以下描述这两个活动的PV操作补充完整：操作补充完整：driver()while(1)p(s1);启动车辆；启动车辆；正常行车；正常行车；到站停车；到站停车；conductor()while(1)关车门；关车门；售票；售票；p(s2);开车门；开车门；上下乘客；上下

32、乘客；Semaphore s1=0;Semaphore s2=0;main()cobegindriver();conductor();Coend;s1：表示是否允许司机起动车辆，：表示是否允许司机起动车辆，s2：表示是否允许售票员开门：表示是否允许售票员开门driver()while(1)p(s1);启动车辆；启动车辆；正常行车；正常行车；到站停车；到站停车；v(s2),；conductor()while(1)关车门；关车门；v（s1）；售票；售票；p(s2);开车门；开车门；上下乘客；上下乘客；Semaphore s1=0;Semaphore s2=0;main()cobegindriver

33、();conductor();Coend;六、有六、有 5 个个 批处理的作业（批处理的作业（A,B,C,D,E）几乎同时到）几乎同时到达一个计算中心，估计的运行时间分别为达一个计算中心，估计的运行时间分别为2，4，6，8，10分钟，它们的优先数分别为分钟，它们的优先数分别为1，2，3，4，5（1为最低优先级）。对下面的每种调度算法，分别计算为最低优先级）。对下面的每种调度算法，分别计算作业的周转时间和平均周转时间作业的周转时间和平均周转时间一个四道作业的操作系统中，设在一段时间内先后到达一个四道作业的操作系统中，设在一段时间内先后到达6个作业，它们的提交时间和运行时间见表个作业，它们的提交时

34、间和运行时间见表作业号作业号 提交时间提交时间 运行时间运行时间 JOB1JOB2JOB3JOB4JOB5JOB68:008:208:258:308:358:4060352025 510系统采用短作业优先的调度算法，作业被调度进入运行后不再系统采用短作业优先的调度算法，作业被调度进入运行后不再退出，但当一作业进入运行时，可以调整运行的优先次序。退出，但当一作业进入运行时，可以调整运行的优先次序。1 按照所选择的调度算法，请分别给出上述按照所选择的调度算法，请分别给出上述6个作业的执行时间次个作业的执行时间次序序2 计算在上述调度算法下作业的平均周转时间计算在上述调度算法下作业的平均周转时间作业作业202.117.54.232 实验资料