操作系统第三章课件-002

第三章

处理机调度和死锁

处理机调度的层次处理机调度系统中有多道程序和多个进程时，系统按某种算法，动态地把处理机分配个某个就绪队列中的进程的过程调度的三个层次高级调度中级调度低级调度高级调度

又称作业调度、长程调度、接纳调度作业和作业步作业job包含程序、数据和作业说明书系统根据作业说明书对程序的运行进行控制作业步jobstep：作业的加工处理步骤一个作业包含托干个作业步。如编译、连接、运行等作业调度作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。作业调度功能记录已进入系统的各作业的情况（JCB，JobControlBlock）；按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；为被选中的作业创建进程，并且为其申请系统资源；作业加束后作善后处理工作。作业控制快JCB

为管理和调度作业，为每个作业设置的控制块是存放作业控制和管理信息的数据结构高级调度特性接纳作业数内存驻留数太多，周转时间T长太少，

系统效率低接纳策略决定接纳哪些作业即采用何种调度算法FCFS、短作业优先等低级调度又称进程调度，短程调度调度对象是进程主要是由分派程序（Dispatcher）分配处理机进程调度功能保护现场入就绪队列算法实现处理机分派恢复现场进程调度的三个基本机制排队器负责将就绪进程某种策略排队分派程序按照进程调度策略，从就绪进程中取出进程，进行上下文切换，分配处理机给进程上下文切换机制当调度新的进程执行时，保存当前执行进程的上下文，装入即将运行进程的上下文调度分派结构pcb1schedulersuspwakeupreceive…pcb2pcb3pcb4…dispatchercpuReady-qpcb5pcb2schedulersuspwakeupreceive…pcb5pcb3pcb4…dispatchercpuReady-qpcb1进程调度方式非抢占方式一旦处理机分配后，直到进程完成或自愿放弃处理机 简单，实时性差(如win31)抢占方式时间片原则优先权原则短作业优先原则中级调度又称中程调度为提高系统吞吐量和内存利用率引入进程的内/外存对换功能换出时，进程为挂起或就绪驻外状态由中程调度决定调度哪些就绪进程入内存调度队列模型仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现调度队列模型具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度具有三级调度就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业选择调度方式和算法的准则面向用户的准则面向系统的准则面向用户的准则

周转时间短，常用于批处理系统作业从提交―>完成的时间.分为：驻外存等待调度时间驻内存等待调度时间执行时间阻塞时间平均周转时间Tii进程的周转时间平均带权周转时间Ts系统的服务时间面向用户的准则响应时间快（交互性作业）键盘提交请求到首次响应时间输入传送时间处理时间响应传送时间截止时间的保证（实时系统）优先权准则即需要抢占调度面向系统的准则吞吐量高对于批处理：单位时间完成作业数处理机利用率好特别于大中型多用户系统各类资源的平衡利用内存、外存、I/O设备等调度算法是一个资源分配问题根据系统的资源分配策略所规定资源分配算法典型算法先来先服务短作业优先高优先权优先调度时间片轮转调度先来先服务FCFS简单，有利于长作业即CPU繁忙性作业注意作业C的带权周转时间进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99短作业优先调度算法短作业进程优先SJ(P)F提高了平均周转时间和平均带权周转时间，从而提高了系统吞吐量对长作业不利，有可能得不到服务不易确定作业完成时间FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1高优先权优先调度算法优先权调度算法类型非抢占式优先权算法当前运行进程不可被抢占当要调度新的进程时按优先权调度抢占式优先权算法，实时性更好如果出现优先权更高的进程，则中止当前进程，并将处理机分配给优先权高的进程优先权类型静态优先权进程优先权在整个运行期不变确定优先权依据进程类型、进程对资源的需求、用户需求。简单，但低优先权作业可能长期不被调度动态优先权如：优先权随执行时间而下降，随等待时间而升高可用响应比Rp作为优先权Rp=（等待时间＋服务时间）/服务时间即：Rp=（tw+ts）/ts优点：长短兼顾缺点：需计算Rp高响应比优先算法响应比Rp=（tw+ts）/ts短作业Rp大ts（要求服务时间）相同的进程间相当于FCFS。长作业等待一段时间仍能得到服务。基于时间片的轮转调度算法多运用于分时系统中两种策略时间片轮转多级反馈队列调度时间片轮转

系统根据按时间片轮流调度进程时间片大小的确定太大：退化为FCFS太小：系统开销过大系统对进程的响应时间T=nq；q为时间片,n为就绪队列中进程的数目；系统的处理能力应保证一个时间片处理完常用命令多级反馈队列调度设置多个就绪队列，为每个队列设定不同的优先级第一个队列优先级最高，其他依次递减优先级越高的队列、每个时间片越短第i+1个队列的时间片长是第i个队列的2倍新进程进入内存后，首先加入第一队列队尾，按FCFS等待调度第一轮结束后，若进程未结束，则加入第二队列，依此类推仅当第一队列空闲时，才会调度第二队列进程运行，依此类推就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1<S2<S3多级队列反馈调度算法

多级队列反馈调度算法特点长、短作业兼顾，有较好的响应时间短作业一次完成；中型作业周转时间不长；大型作业不会长期不处理实时调度实现实时调度的基本条件提供必要的调度信息就绪时间、开始/完成截止时间、处理时间、资源要求、优先级；系统处理能力强满足限制条件m:周期性实时任务Ci:处理时间Pi:周期时间N:处理器数目实现实时调度的基本条件采用抢占调度方式剥夺方式非剥夺方式实现简单一般实时任务较小，以及时放弃CPU具有快速切换机制具有快速响应外部中断能力。快速任务分派实时调度算法的分类非抢占式调度算法时间片轮转 秒级非抢占优先权（协同） 秒~毫秒级抢占式调度算法时钟中断抢占优先权 毫秒级基于抢占点抢占立即抢占

毫秒~微秒级只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完成b非抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度抢占时刻（其它中断）b立即抢占优先权调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间调度时间常用的几种实时调度算法最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式最早截止时间优先EDF例134213421234t开始截止时间任务到达任务执行EDF算法用于非抢占调度方式最低松弛度优先LLF算法松弛度若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90主要用于可抢占的调度方式中例：A的执行周期为20ms,执行时间10msB的执行周期为50ms,执行时间25msA1A2A3A4A5A6A7A8B1B2B3020406080100120140160t图3－11A/B任务每次必须完成的时间最低松弛度优先LLF算法A1(10)A2(10)A3(10)A4(10)t01020304050607080t1=0B1(20)B1(5)B2(15)B2(10)t1t2t3t4t5t6t7t8进程死锁系统中的进程无法进一步推进产生死锁的原因和必要条件产生死锁的原因竞争资源引起死锁进程推进顺序不当引起死锁竞争资源引起死锁可剥夺（CPU、内存，）和非剥夺性（打印机，磁带机）资源竞争非剥夺性资源——可造成死锁竞争临时性资源由一个进程产生，被另一个进程使用一段时间后便无用的资源。p1p2R1R2进程推进顺序不当引起死锁213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)4产生死锁的必要条件互斥条件（资源的临界性）请求和保持条件不剥夺条件环路等待处理死锁的基本方法预防破坏4个条件之一有效，使资源利用率低避免防止进入不安全态。检测检测到死锁再清除。解除与“检测”配套。死锁预防互斥条件是资源固有属性，不能避免。摒弃请求和保持条件全分配，全释放（AND）缺点：延迟进程运行、资源严重浪费摒弃“不剥夺”条件增加系统开销，且进程前段工作可能失效摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行缺点：原序号已排定，新增资源不便；用户不自由；资源与进程使用顺序不同造成浪费系统的安全状态在“避免死锁”方法中的判断条件安全状态按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。能找到安全序列的状态为安全状态。系统的安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2p1p3上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P393安全——不安全的转换银行家算法死锁避免算法算法思想系统分配资源前进行安全性检查此次分配后，仍然可以找到一个安全的推进序列，则可以完成分配银行家算法（cont.）数据结构available[j]系统现有Rj类资源max[i,j]进程i需要Rj的最大数alloc[i,j]进程i已分配的Rj资源数need[i,j]进程i需要Rj类资源即：need[i,j]=max[i,j]－alloc[i,j]Requesti[] 进程i请求资源数Worki[j]进程j执行完后系统可用资源数finish[i]布尔量，进程i能顺利完成为真避免死锁-银行家算法银行家算法Requesti[j]<=need[i,j]errorRequesti[j]<=availiable[j]blockYNYN银行家算法Available[j]=available-requesti[j]Allocation[i,j]=allocation[i,j]+requesti[j]Need[i,j]=need[i,j]-requesti[j]安全性检查安全性算法(1)设置向量Work[]和Finish[] Work[j]:=available Finish[i]:=true(2)从进程集合中找到一个能满足下述条件的进程Finish[i]=falseNeed[i,j]<=work[j](3)找到,进程i可执行完 work[j]:=work[j]+allocation[i,j] finish[i]:=true goto(2)(4)检查所有进程的finish[]=true?,是则系统处于安全状态,否则为不安全状态实例MaxABCAllocationABCNeedABCAvailableABCp0753010743332(230)p1322200(302)122(020)p2902302600p3222211011p4433002431T0时刻的资源分配表，P1请求1,0,2实例WorkABCNeedABCAllocABCWork+allocABCFinishp1332122200532truep3532011211743truep4743431002745truep27456003021047truep010477430101057trueT0时刻的安全序列实例WorkABCNeedABCAllocABCWork+allocABCFinishp1230020302532truep3532011211743truep4743431002745truep0745743010755truep27556003021057true