操作系统第3章 处理机调度与死锁习题

第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除第三章处理机调度与死锁第三章习题课一、选择题(1)在三种基本类型的操作系统中，都设置了______，在批处理系统中还应设置______，在分时系统中除了______，通常还设置了______。A.剥夺调度B.作业调度C.进程调度D.中级调度CBCD第三章处理机调度与死锁第三章习题课一、选择题(2)我们如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用______；为照顾紧急作业的用户，应采用______；为能实现人机交互作用采用______；而能使短作业、长作业及交互作业用户都比较满意时，应采用______。A.FCFS调度算法B.短作业优先调度算法C.时间片轮转法D.多级反馈队列调度算法E.基于优先权调度算法BECD第三章处理机调度与死锁第三章习题课一、选择题(3)产生死锁的基本原因是_______和_______，产生死锁的四个必要条件是互斥条件，_______，不剥夺条件和_______。①A.资源分配不当B.竞争资源C.作业调度不当D.资源的独占性②A.进程推进顺序不当B.进程调度不当C.系统中进程太多D.CPU运行不快③A.请求和阻塞条件B.请求和释放条件C.请求和保持条件D.释放和阻塞条件④A.线性增长条件B.环路等待条件C.无序释放条件D.有序请求条件①②③④BACB第三章处理机调度与死锁第三章习题课一、选择题(4)实际操作系统，要兼顾资源的使用效率和安全可靠，对资源的分配策略，往往采用______策略。A.预防死锁B.避免死锁C.检测死锁D.三者的混合(5)在下列死锁的解决办法中，属于预防死锁策略的是____。A.银行家算法B.资源有序分配法C.死锁检测法D.资源分配图化简法DB第三章处理机调度与死锁第三章习题课二、填空题(1)资源的一次分配法和有序分配法分别破坏了产生死锁的必要条件中的______________和______________，它们属于__________，而银行家算法属于__________。(2)作业调度是从_____________中选出一____作业，为它们分配______，并为它们创建______。请求和保持条件环路等待条件预防死锁避免死锁后备作业队列批资源进程第三章处理机调度与死锁第三章习题课二、填空题(3)最有利于提高系统吞吐量的作业调度算法是__________；能对紧急作业进行及时处理的调度算法是______________；能较好的满足短作业用户要求，又能适当的照顾长作业，以及照顾作业到达次序的调度算法是__________________。(4)在高响应比优先的调度算法中，当各个作业的等待时间相同时，________将得到优先调度；当各个作业要求的运行时间相同时，________________将得到优先调度。短作业优先算法高优先权优先算法高响应比优先算法短作业最先到达者等待时间最长者第三章处理机调度与死锁第三章习题课三、应用题1.设有三道作业，它们的提交时间和运行时间如下表：作业号提交时刻(时)运行时间(小时)110.002210.101310.250.25求：试给出下面两种调度算法下，作业的执行顺序、平均周转时间和平均带权周转时间。(1)先来先服务FCFS调度算法(2)短作业优先SJF调度算法第三章处理机调度与死锁第三章习题课5.32.63平均12313.2513.000.2510.2532.92.9013.0012.00110.1021212.0010.00210.001带权周转时间周转时间完成时刻开始时刻运行时间提交时刻作业号(1)先来先服务FCFS调度算法第三章处理机调度与死锁第三章习题课4.052.38平均8212.2512.000.2510.2533.153.1513.2512.25110.1021212.0010.00210.001带权周转时间周转时间完成时刻开始时刻运行时间提交时刻作业号(2)短作业优先SJF调度算法第三章处理机调度与死锁第三章习题课三、应用题2.设有四道作业，它们的提交时间和运行时间如下表：作业号提交时刻(时)运行时间(小时)18:002.028:500.539:000.149:500.2求：试给出下面三种调度算法下，作业的执行顺序、平均周转时间和平均带权周转时间。(1)先来先服务FCFS调度算法(2)短作业优先SJF调度算法(3)高响应比优先调度算法第三章处理机调度与死锁第三章习题课(1)先来先服务FCFS调度算法6.291.6474.835810:4810:360.29:50416.009610:3610:300.19:0033.3410010:3010:000.58:5021.0012010:008:002.08:001带权周转时间周转时间完成时间开始时间运行时间提交时间作业号第三章处理机调度与死锁第三章习题课(2)短作业优先SJF调度算法4.571.382.342810:1810:060.29:50411.006610:0610:000.19:0033.9311810:4810:180.58:5021.0012010:008:002.08:001带权周转时间周转时间完成时间开始时间运行时间提交时间作业号第三章处理机调度与死锁第三章习题课(3)高响应比优先调度算法5.091.3754.835810:4810:360.29:50411.006610:0610:000.19:0033.5310610:3610:060.58:5021.0012010:008:002.08:001带权周转时间周转时间完成时间开始时间运行时间提交时间作业号2:(70+30)/0.5=2003:(60+6)/0.1=6604:(10+12)/0.2=1102:(76+30)/0.5=2124:(16+12)/0.2=140第三章处理机调度与死锁第三章习题课三、应用题3.假设某系统中有3种资源(R1,R2,R3)，在某时刻系统中共有4个进程，进程(P1,P2,P3,P4)的最大资源需求数向量和此时已分配的资源数向量分别为：进程最大资源需求当前已分配到资源P1(3,2,2)(1,0,0)P2(6,1,3)(5,1,1)P3(3,1,4)(2,1,1)P4(4,2,2)(0,0,2)第三章处理机调度与死锁第三章习题课三、应用题系统中当前可用资源向量为(1,1,2)，问：(1)计算还需要资源数组；(2)系统此时是否安全？(4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNeedAllocationMax第三章处理机调度与死锁第三章习题课truetruetruetrueFinish(1,0,0)(0,0,2)(2,1,1)(5,1,1)Allocation(8,3,6)(8,3,4)(6,2,3)(1,1,2)Work(9,3,6)(2,2,2)P1(8,3,6)(4,2,0)P4(8,3,4)(1,0,3)P3(6,2,3)(1,0,2)P2Work+AllocationNeed三、应用题系统中当前可用资源向量为(1,1,2)，问：(1)计算还需要资源数组；(2)系统此时是否安全？第三章处理机调度与死锁(4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNeedAllocationMax第三章习题课(3)如果进程P2发出资源请求向量(1,0,1)，系统能否将资源分配给它？①Request2(1,0,1)≤Need2(1,0,2)②Request2(1,0,1)≤Available2(1,1,2)(6,1,2)(0,1,1)(0,0,1)第三章处理机调度与死锁第三章习题课truetruetruetrueFinish(1,0,0)(0,0,2)(2,1,1)(6,1,2)Allocation(8,3,6)(8,3,4)(6,2,3)(0,1,1)Work(9,3,6)(2,2,2)P1(8,3,6)(4,2,0)P4(8,3,4)(1,0,3)P3(6,2,3)(0,0,1)P2Work+AllocationNeed三、应用题④再利用安全性算法检查此时系统是否安全。存在一个安全序列：P2,P3,P4,P1第三章处理机调度与死锁(4,2,0)(0,0,2)(4,2,2)P4(1,0,3)(2,1,1)(3,1,4)P3(1,0,2)(5,1,1)(6,1,3)P2(1,1,2)(2,2,2)(1,0,0)(3,2,2)P1AvailableNeedAllocationMax第三章习题课(4)如果进程P1发出资源请求向量(1,0,1)，系统能否将资源分配给它？①Request1(1,0,1)≤Need1(2,2,2)②Request1(1,0,1)≤Available1(1,1,2)(2,0,1)(0,1,1)(1,2,1)不安全状态第三章处理机调度与死锁第三章习题课三、应用题4.假设某系统中有4种资源，在某时刻系统中共有5个进程，进程(P0,P1,P2,P3,P4)的最大资源需求数向量和此时已分配的资源数向量分别为：进程最大资源需求当前已分配到资源P0(0,0,1,2)(0,0,1,2)P1(2,7,5,0)(2,0,0,0)P2(6,6,5,6)(0,0,3,4)P3(4,3,5,6)(2,3,5,4)P4(0,6,5,2)(0,3,3,2)第三章处理机调度与死锁第三章习题课三、应用题系统中当前可用资源向量为(2,1,0,0)，问：(1)计算进程还需要请求的资源向量；(2)系统当前是处于安全状态么？(2,1,0,0)Available(0,3,2,0)(2,0,0,2)(6,6,2,2)(0,7,5,0)(0,0,0,0)Need(0,3,3,2)(0,6,5,2)P4(2,3,5,4)(4,3,5,6)P3(0,0,3,4)(6,6,5,6)P2(2,0,0,0)(2,7,5,0)P1(0,0,1,2)(0,0,1,2)P0AllocationMax第三章处理机调度与死锁第三章习题课三、应用题系统中当前可用资源向量为(2,1,0,0)，问：(1)计算进程还需要请求的资源向量；(2)系统当前是处于安全状态么？truetruetruetruetrueFinish(0,0,3,4)(2,0,0,0)(0,3,3,2)(2,3,5,4)(0,0,1,2)Allocation(6,7,9,8)(4,7,9,8)(4,4,6,6)(2,1,1,2)(2,1,0,0)Work(6,7,12,12)(6,6,2,2)P2(6,7,9,8)(0,7,5,0)P1(4,7,9,8)(0,3,2,0)P4(4,4,6,6)(2,0,0,2)P3(2,1,1,2)(0,0,0,0)P0Work+AllocationNeed第三章处理机调度与死锁第三章习题课(3)当进程P2申请(0,1,0,0)时，系统能立即满足么？①Request2(0,1,0,0)≤Need2(6,6,2,2)②Request2(0,1,0,0)≤Available2(2,1,0,0)(2,1,0,0)Available(0,3,2,0)(2,0,0,2)(6,6,2,2)(0,7,5,0)(0,0,0,0)Need(0,3,3,2)(0,6,5,2)P4(2,3,5,4)(4,3,5,6)P3(0,0,3,4)(6,6,5,6)P2(2,0,0,0)(2,7,5,0)P1(0,0,1,2)(0,0,1,2)P0AllocationMax(0,1,3,4)(2,0,0,0)(6,