激励学习的一段说说我多想采来一缕阳光

第三章处理机调度和死锁处理机调度进程数目处理机数目动态分配由处理机调度程序完成作业提交处理机调度获得处理机,执行3.1处理机调度的基本概念3.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性1.接纳作业数（内存驻留数）太多―――周转时间T长太少―――系统效率低2.接纳策略：即采用何种调度算法：FCFS、短作业优先等处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。1.非抢占方式：简单，实时性差(如win31)2.抢占方式（1）优先权原则（2）短作业优先原则（3）时间片原则。3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的内--外存对换功能（换出时，进程为挂起或就绪驻外状态）运行频率：低中高。一、仅有进程调度的调度队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度等待事件事件出现3.1.2调度的队列模型进程完成3.1.2调度的队列模型二、具有高/低级调度的调度队列模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现阻塞队列等待事件2事件2出现作业调度后备队列N三、具有三级调度的调度队列模型就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业3.1.3选择调度方式和算法的若干准则一、面向用户的准则1．周转时间短（常用于批处理系统）概念：作业从提交――完成的时间.分为：（1）驻外等待调度时间（2）驻内等待调度时间（3）执行时间（4）阻塞时间一、面向用户的准则平均周转时间平均带权周转时间可见带权W越小越好,Ts为实际服务时间。3.1.3选择调度方式和算法的若干准则][11niiTnT][11nisiiTTnW一、面向用户的准则2．响应时间快：（对交互性作业）概念：键盘提交请求到首次响应的时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截止时间的保证（特别于实时系统）4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则二、面向系统的准则1．吞吐量高（特别于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）3．各类资源的平衡利用。3.1.3选择调度方式和算法的若干准则3.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优先调度算法1.先来先服务调度算法FCFS特点：简单，有利于长作业即CPU繁忙性作业进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.993.2.1先来先服务和短作业（进程）优先调度算法2.短作业进程优先调度算法：SJ(P)F选出估计运行时间最短的作业（进程）提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）对长作业不利，有可能得不到服务（饥饿）未考虑作业的紧迫性估计时间不易确定图3.4FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.10417231241418ABCDEFCFS041923184613ABCDESJF3.2.2高优先权优先调度算法1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。3.2.2高优先权优先调度算法(2)2．动态优先权：如：优先权随执行时间而下降，随等待时间而升高。响应比Rp=（等待时间＋服务时间）/服务时间作为优先权优点：长短兼顾缺点：需计算Rp3.高响应比优先算法：特点：响应比Rp=（tw+ts）/ts（1）短作业RP大。（2）ts（要求服务时间）相同的进程间相当于FCFS。（3）长作业等待一段时间仍能得到服务。3.2.3基于时间片的轮转调度算法1.时间片轮转时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）2.多级反馈队列调度1.多个就绪队列，不同优先级2.新进程首先进入第一队列尾，FCFS；时间片结束后未完成的进入第二队列尾…3.第一队列空闲时才调度第二队列，抢占式3.2.3基于时间片的轮转调度算法（2）特点：长、短作业兼顾，有较好的响应时间（1）短作业一次完成；（2）中型作业周转时间不长；（3）大型作业不会长期不处理。就绪队列1至CPUS1就绪队列2S2至CPU就绪队列3S3至CPU就绪队列nSn至CPU时间片：S1S2S3图3－5多级队列反馈调度算法3.3.1实现实时调度的基本条件1．提供必要的调度信息（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；2．系统处理能力强，满足：3.3实时调度NPCPCmiiimiii111Ci为处理时间，Pi为周期时间（基于周期性实时任务）3.采用抢占调度方式剥夺方式：一般都采用此非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。4.具有快速切换机制具有快速响应外部中断能力。快速任务分派能力3.3.1实现实时调度的基本条件3.3.2实时调度算法的分类1非抢占式调度算法时间片轮转秒级非抢占优先权（协同）秒~毫秒级2抢占式调度算法时钟中断抢占优先权毫秒级基于抢占点抢占立即抢占抢占优先权毫秒~微秒级只要不在临界区即抢占（中断引发）进程1进程2进程n实时进程调度时间实时进程要求调度调度实时进程运行a非抢占轮转调度当前进程实时进程实时进程要求调度当前进程运行完成b非抢占优先权调度调度时间当前进程实时进程实时进程要求调度抢占时刻（其它中断）d立即抢占优先权调度调度时间c基于时钟中断抢占的优先权抢占调度当前进程实时进程实时进程要求调度时钟中断到达时调度时间3.3.3常用的几种实时调度算法1.最早截止时间优先EDF（earliestdeadlinefirst)算法根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高就绪队列中按个任务截止时间的早晚排序可以是抢占式或非抢占式2最早截止时间优先EDF例1341234t开始截止时间任务到达任务执行EDF算法用于非抢占调度方式34212.最低松弛度优先LLF算法松弛度：根据任务的紧急（松弛）程度确定优先级，越紧急优先级越高松弛度=必须完成时间-本身运行时间-当前时间若A进程需在200ms时完成，其本身运行需要100ms，当前时刻是10ms，则A的松弛度为：200－100－10＝90按松弛度排序的实时任务就绪队列主要用于可抢占的调度方式中最低松弛度优先LLF算法(2)A1A2A3A4t01020304050607080B1B1B2B2t1t2t3t4t5t6t7t8A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t每20ms执行一次，执行时间10ms每50ms执行一次，执行时间25mst2--A2:20,B1:15t1--A1:10,B1:25t3--A2:0,B1:15t4--A3:10,B1:5t5—A3:5,B2:30t7—A4:0,B2:203.4多处理机系统中的调度1.紧密耦合MPS和松弛耦合MPS紧密耦合共享RAM和I/O高速总线和交叉开关连接松弛耦合独立RAM和I/O通道和通信线路连接2.对称多处理器系统和非对称多处理器系统处理器是否结构相同3.4.2进程分配方式1.对称SMP中进程分配方式静态分配：开销小，忙闲不均动态分配：可防止多个处理器忙闲不均，松散耦合的系统中会增加开销2.非对称SMP中进程分配方式进程调度在主处理器上执行有潜在的不可靠性3.4.3进程（线程）调度方式1.自调度各个处理机自行在就绪队列中取任务。特点；简单，分布式调度，调度算法可采用前述方法，多个CPU利用率都不错（不会闲）但：瓶颈问题，（单队列）低效性；（需拷贝现场）线程切换频繁（当线程合作时,各线程并行的条件不容易满足）3.4.3进程（线程）调度方式2.成组调度优点：（1）对相互合作的进（线）程成组调度，可以减小切换，减小系统开销。（2）每次分配一组CPU，减少了调度频率。分配时间（1）面向所有程序平均分配（2）面向所有线程平均分配：使处理机利用率更高。2.成组调度两种分配时间的方法应用程序A应用程序BCpu1线程1线程1Cpu2线程2空闲Cpu3线程3空闲Cpu4线程4空闲时间1/21/2浪费37.5%应用程序A应用程序BCpu1线程1线程1Cpu2线程2空闲Cpu3线程3空闲Cpu4线程4空闲时间4/51/5浪费15%3.专用处理机分配引入：多处理机系统，每个处理已不再属宝贵资源。特点：每个进（线）程专用处理机，使其切换小，提高效率。主要用于大型计算，实时系统3.4.3进程（线程）调度方式3.5产生死锁的原因和必要条件所谓死锁(deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处在这种僵持状态时，若无外力作用，它们都将无法再向前推进。3.5.1产生死锁的原因一、竞争资源引起死锁。1．可剥夺（CPU、内存）和非剥夺性（打印机，磁带机）资源2．竞争非剥夺性资源——可造成死锁3．竞争临时性资源——也可能引起死锁p1p2R1R2p1p3S3S1p2S23.5.1产生死锁的原因二、进程推进顺序不当引起死锁进程推进顺序合法进程推进顺序非法213DP2Req(R2)P2Req(R1)P1Req(R1)P1Req(R2)P2Rel(R2)P2Rel(R1)P1Rel(R1)P1Rel(R2)43.5.2产生死锁的必要条件1．互斥条件（资源的临界性）2．请求和保持条件3．不剥夺条件4．环路等待3.5.3处理死锁的基本方法1．预防；破坏4个条件之一：有效，使资源利用率低。2．避免：防止进入不安全态。3．检测：检测到死锁再清除。4．解除：与“检”配套。3.6死锁预防和避免3.6.1死锁预防一、互斥条件是资源固有属性，不能避免。二、摒弃请求和保持条件全分配，全释放（AND）缺点：（1）延迟进程运行（2）资源严重浪费三、摒弃“不剥夺”条件增加系统开销，且进程前段工作可能失效。3.6死锁预防和避免四、摒弃“环路”条件有序资源分配法：为资源编号，申请时需按编号进行。缺点：（1）新增资源不便（原序号已排定）（2）用户不自由（3）资源与进程使用顺序不同造成浪费3.6.2系统的安全状态在“避免死锁”方法中的判断条件1.安全状态按某种顺序并发进程都能达到获得最大资源的可顺序完成的序列为安全序列。能找到安全序列的状态为安全状态，否则为不安全状态。避免死锁：资源分配时，使系统不进入不安全状态3.6.2系统的安全状态（2）2.安全状态例进程最大需求已分配可用P11053P242P392安全序列：p2p1p33.6.2系统的安全状态（3）3.安全不安全的转换上例中，若P3再申请一台，则不安全进程最大需求已分配可用P11052P242P3933.6.3利用银行家算法避免死锁1．数据结构Ava