操作系统第三章调度与死锁.ppt
《操作系统第三章调度与死锁.ppt》由会员分享,可在线阅读,更多相关《操作系统第三章调度与死锁.ppt(35页珍藏版)》请在三一办公上搜索。
1、第三章,调度与死锁,进程调度的核心是调度算法。,进程调度是实现多道程序系统的关键,直接影响到操作系统的性能,是本章讨论的主要问题。,3.1 调度的基本概念(一),作业从进入系统到完成,可能要经历三级调度过程:,一、调度的类型和模型,1、高级调度 又称为作业调度,它决定将哪些在外存上处于后备状态的作业调入主机内存,准备执行。因此,有时把它称为接纳调度。2、低级调度 又称为进程调度,它决定就绪队列中哪个进程将获得处理机,并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为分派程序。3、中级调度 中级调度的主要作用是在内存和外存之间进行进程交换,以解决内存紧张的问题。如它将内存中处于等待状态
2、的某些进程调至外存对换区,以腾出内存空间,而将外存对换区上已具备运行条件的进程重新调入内存,准备运行。故又称为交换调度。,阻塞状态,就绪状态,执行,状态,调度,I/O请求,进程,释放,时间片到,后备作业队列,3.1 调度的基本概念(二),CPU,就绪队列,内存,外存,阻塞队列,作业调度,等待事件,中级调度,即交换调度,交换文件,就绪队列,阻塞队列,三级调度的模型,3.1 调度的基本概念(三),作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有CPU并执行。作业调度是进程调度的基础,作业被调入内存后,是以进程的形式执行的。在一个OS中进程调度与作业调度的算法是一致的。,?问题?
3、,1。进程调度与 作业调度之间(功能、调度算法)有 何区别和联系?,2。三级调度中,最核心的是那一级调度?为什么?,?,?,?,各级调度间的关系,3.1 调度的基本概念(四),作业步 将一个作业划分为若干个顺序处理的步骤,作 业步相互独立又相互关联。,作业 是用户请求计算机系统执行的一次独立的上机任 务,是能够共享公共资源区域的一族有关进程(家族)。从静态观点看,作业由 控制命令系列、程序集、数据 集三部分构成。,补充:关于作业的概念,作业控制块 JCB(Job Control Block)用于描述作业。定义为记录类型(作业名、优先级、建立时间、状态外 存地址、大小等)。,作业状态 作业在其生
4、命期中,共有四种状态:,关于作业的状态,作业状态 作业在其生命期中,共有四种状态:进入、后备、运行、完成,提交,作业调度,完成,问题:引起进程调度的原因有哪些?,3.1 调度的基本概念(五),非抢占式(非剥夺式)进程 一旦被调度,就一直占有CPU,直到完成或因发生某事件而被阻塞(I/O请求)。抢占式(剥夺式)进程未执行完,可由调度程序剥夺其CPU,另分配给别的进程。抢占的原因有:优先级、时间片、短进程等。,在OS中,进程调度的方式分为两类。,二、进程调度的方式,3.1 调度的基本概念(六),记录系统中所有进程的执行情况 确定分配处理机的原则(调度算法)分配处理机给进程 回收处理机、进行进程上下
5、文切换,三、进程调度的功能,显然,进程调度的核心问题是调度算法。,3.1 调度的基本概念(七),1。周转时间短 周转时间TT(Tumaround Time)对作业从作业提交到完成。对进程第一次进入就绪队列到运行结束。平均周转时间ATT(Average Tumaround Time)ATT=Ti 带权平均 W=其中:Ti 各进程的TT Tri 实际执行时间,2.响应时间快 响应时间RT(Response Time)输入键盘命令到屏幕显示结果。,四.调度算法准则 调度算法应该尽可能提高资源利用率,减少CPU空闲时间,公平服务。可从以下方面考虑:,3.2 调度算法(一),先来先服务(FCFS)算法
6、最短CPU运行期优先(SCBF)算法 最高优先权(HPF)算法 时间片轮转(RR)算法 多级反馈队列算法,思考题 1、各种调度算法的特点、性能如何?适宜于 哪类 OS?2。最高优先权算法中,动态优先权有何实际意义?,常用调度算法,3.2 调度算法(二),一.、先来先服务(FCFS)算法,FCFS(First Come First Server)法,又称为先进先出(FIFO)算法,就绪进程按照进入的先后次序排列,调度程序总是选择队首的进程执行。,这是一种非剥夺式的调度算法,简单、易实现。对短进程易出现等待时间长,服务质量差。该算法有利于CPU繁忙型的进程,不利于I/O繁忙型的进 程。,该算法只能
7、用于辅助算法。,3.2 调度算法(二),二、最短CPU运行期优先(SCBF)算法,该算法优于FCFS,但长进程等待时间长,估算误差较大。,SCBF(Shortest CPU Burst First),即调度程序总是选择CPU运行时间最短的进程执行。,3.2 调度算法(三),三、最高优先权(HPF)算法,调度程序每次都将CPU分配给就绪队列中具有最高优先级(Highest Priority)的进程。该算法的核心是优先级的确定。调度方式分为剥夺式和非剥夺式。,静态优先级 在创建进程时根据进程的特性或者用户要求赋予,在进程的整个生命期中不能改变。简单、易实现,但是调度性能不高,优先级低的进程可能长期
8、等待。,动态优先级 在创建进程时为进程赋予一个基本优先级,在进程的执行过程中可随进程的特性动态改变。引起优先级改变的原因:进程等待CPU时间长短,执行所需CPU时间长短等。,分两类优先级:,3.2 调度算法(四),三、最高优先权(HPF)算法,确定进程优先级的一般原则:1.进程的类型 例如:系统进程高于用户进程;前台进程高于后台进程;实时进程高于一般进程。2.对资源的需求量及类型 占用CPU时间少的,使用内存资源少的进程优先级高。3.按作业到达系统的时间顺序 4.按用户类型和要求,3.2 调度算法(五),四、时间片轮转(RR)算法,该算法主要用于分时系统,按照公平服务的原则,为进程分配CPU时
9、间片。是一种剥夺式的算法。轮转法的关键是时间片的选取:时间片太大,则轮转法蜕化为FCFS法。时间片太小,则增加CPU的额外开销。影响时间片设置的主要因素:系统响应时间R、就绪进程数N、计算机处理能力等。时间片长度:q=R/N max,3.2 调度算法(六),五、高响应比优先调度算法(HRN),HRN(Highest Response ratio Next)算法将短进程优先与动态优先级相结合。所谓高响应是指进程获得调度的响应,即优先数R。R=(W+T)/T=1+W/T T 估计进程执行的时间。W 进程等待的时间。随着进程等待时间的增加,优先权动态增加。对等待相同时间的短进程比长进程优先权增加得多
10、。长进程随着等待时间增加也会被调度。,3.2 调度算法(七),六、多级队列调度,根据作业性质不同分为若干个就绪队列,如:系统进程队列,交互进程队列,批处理队列等。对各队列采用不同的调度算法。,3.2 调度算法(八),亦称多级反馈轮转法(Round Robin with Multiple Feedback)实现基本思想:1。按优先级分别设置N个就绪队列,优先级愈高的队列分配 的时间片愈小。2。系统总是先调度当前优先级最高的队列中的进程,只有当 最高优先级队列为空时,才去调度低一优先级队列中的进 程。3。进程被调度后,若未执行完时间片到,则优先级降低,进 程排入相应优先级队列的队尾。4。同一优先级
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 第三 调度 死锁
链接地址:https://www.31ppt.com/p-6164590.html