处理机调度与死锁-(3).ppt

《处理机调度与死锁-(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除开始本章学习目标处理机调度的基本概念处理机调度算法实时调度和多处理机调度死锁问题及解决对策返回本章首页3.1处理机调度的基本概念3.1.1高级、中级和低级调度3.1.2调度队列模型3.1.3选择调度方式和算法的准则返回本章首页3.1.1调度的类型一、调度的职能(1)记录系统中所有进程的有关情况(2)确定分配处理机的原则(3)

2、分配处理机给进程(4)从进程收回处理机返回本节目录二、高级、中级和低级调度1.高级调度——作业调度(1)接纳多少作业(2)接纳哪些作业——取决于调度算法返回本节目录2.低级调度——进程调度(1)非抢占方式——CPU不能被动剥夺引起调度的因素：*进程执行完毕，或发生某事件进程不能继续运行*进程因I/O请求而停止*进程通信或同步过程中执行了某种原语返回本节目录(2)抢占方式(PreemptiveMode)抢占的原则：*优先权原则*短作业优先原则*时间片原则返回本节目录3.中级调度——对换暂时不能运行

3、的进程中级调度的任务是挂起暂时不能运行的进程，以提高内存的利用率和系统的吞吐量。返回本节目录3.1.2调度队列模型一、仅有进程调度的调度队列模型返回本节目录二、具有高级和低级调度的调度队列模型1.调度队列模型2.与进程调度队列模型的区别(1)就绪队列的形式*优先权队列*无序链表(2)设置多个阻塞队列三、同时具有三级调度的调度队列模型3.1.3选择调度方式和算法的准则一、面向用户的准则1.周转时间短作业周转时间=外存等待时间+就绪队列等待时间+CPU执行时间+I/O操作时间平均周转时间=平均带权周

4、转时间2.响应时间快——提交请求开始到首次响应止3.截止时间的保证——任务必须开始执行的最迟时间4.优先权准则——紧急任务优先执行返回本节目录二、面向系统的准则1.系统吞吐率高——单位时间内完成的作业多2.处理机利用高——40%~90%3.各类资源平衡利用3.2调度算法3.2.1先来先服务和短作业优先调度算法3.2.2优先权调度算法3.2.3基于时间片的调度算法下一页3.2.1先来先服务和短作业优先调度算法一、先来先服务调度算法——FCFS按照进程进入就绪队列的先后顺序调度进程，到达得越早，其优

5、先数越高。未遇到其他情况时，获得处理机的进程就一直运行下去。二、(运行时间)短作业优先调度算法1.基本原理2.算法的缺点(1)对长作业不利(2)未考虑作业的紧迫性(3)时间是估计的，不一定真的最短3.2.2优先权调度算法一、优先权调度算法的类型1.非抢占式优先权算法最高优先级的就绪进程获得处理机之后，就一直运行下去(除非因自身的原因被阻塞，如要求I/O操作)，直至运行结束。2.抢占式优先权算法就绪队列中优先级高的进程可以随时取代正在运行的进程，投入运行。二、优先权的类型1.静态优先权——进程创建

6、时确定(1)进程的类型(I/O进程、对换进程等)(2)进程的资源需求(内存、执行时间等)(3)用户要求(紧迫程度、支付费用等)2.动态优先权——进程创建时确定三、高响应比优先调度算法1.优先权的定义2.响应比3.算法特点(1)对短作业有利(2)服务时间相同，等待时间越长，优先权越高(3)随着时间增加，长作业得到照顾3.2.3基于时间片的调度算法一、时间片轮转法所有就绪进程按先后次序排队，处理机总是优先分配给就绪队列中的第一个进程，并分配它一个固定的时间片（如100毫秒）。时间片时间到，同时未遇到

7、任何阻塞时，进程就回到就绪队列的尾部。二、多级反馈队列调度算法根据进程的优先级设置多个就绪队列，第一个队列的优先级最高，队列之间的优先级依次降低。高优先级队列中的进程执行时间片短当一个进程进入内存时，首先把它放到第一个队列的末尾，按FCFS原则等待调度。若在时间片内未执行完，将被放到第二个队列的末尾；然后依次类推仅当前面的队列为空时，才调度后面队列中的进程。三、多级反馈队列调度算法的性能1.终端型作业此类作业较短，只要在第一队列的时间片内完成，即可获得较好的满意度2.短批处理作业用较短的时间即可

8、完成3.长批处理作业将依次在不同的队列中运行，不必担心长期得不到处理3.3实时调度3.3.1实现实时调度的基本条件3.3.2实时调度算法的分类3.3.3常用的几种实时调度算法3.3.1实现实时调度的基本条件一、提供必要的调度信息1.就绪时间2.开始截止时间和完成截止时间3.处理时间4.资源要求5.优先级二、系统的处理能力强二、系统的处理能力强1.单机系统m个周期性任务，Pi为周期时间，Ci为执行时间2.多处理机系统(处理机数为N)三、采用抢占式调度机制四、具有快速切换机制1.对外部中断的快速响应