调度算法-Read.ppt

第三章处理机调度与死锁
处理机调度的基本概念
调度算法
上节回顾
处理机调度概念:高级、中级、低级
高级调度:作业为对象,从外存到内存,进程创建操作
中级调度:进程为对象,外存与内存互换,挂起与唤醒操作
低级调度:进程为对象,CPU调度,进程执行操作
两种低级调度方式:抢占与非抢占
概念:周转时间、带权周转时间
周转时间= 完成时间-到达时间= 等待时间+ 运行时间
带权周转时间= 周转时间/ 运行时间
调度算法:先来先服务FCFS、短作业优先SJF
高优先权优先调度算法
1. 优先权调度算法的类型
非抢占式优先权算法
在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成; 或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中。
2) 抢占式优先权调度算法
在这种方式下,系统把处理机分配给优先权最高的进程,在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程的执行,重新将处理机分配给新到的优先权最高的进程。每当出现一个新的就绪进程i时,就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj,原进程Pj便继续执行;但如果是Pi>Pj, 则立即停止Pj的执行,做进程切换,使i进程投入执行。
显然,这种抢占式的优先权调度算法,能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中。
2. 优先权的类型
1) 静态优先权
静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~7或0~255中的某一整数, 又把该整数称为优先数。只是具体用法各异:有的系统用“0”表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反。
确定进程优先权的依据有如下三个方面:
进程类型。
(2) 进程对资源的需求。
(3) 用户要求。
2) 动态优先权
动态优先权是指,在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高。若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程,将因其动态优先权变得最高而优先获得处理机,此即FCFS算法。若所有的就绪进程具有各不相同的优先权初值,那么,对于优先权初值低的进程,在等待了足够的时间后,其优先权便可能升为最高,从而可以获得处理机。当采用抢占式优先权调度算法时,如果再规定当前进程的优先权以速率b下降,则可防止一个长作业长期地垄断处理机。
3. 高响应比优先调度算法
优先权的变化规律可描述为:
由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP。据此,又可表示为:
(1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业。
(2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务。
(3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机。