3.1 处理机调度的层次和调度算法的目标
一、处理机调度的层次(3)
1.高级调度 (作业调度、长程调度)
①用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后,再将新创建的进程排在就绪队列上,准备执行 。主要用于多道批处理系统。
②考虑两个问题:选择多少个作业进入内存,为之创建进程? 取决于多道程序的度; 选择哪些作业? 取决于高级调度算法 。
2.低级调度 (进程调度、短程调度)
①决定就绪队列中的哪个进程应获得处理机,然后再由分派程序把处理机分配给该进程的具体操作。运行频率最高。
②功能:保存处理机的现场信息;按某种算法选取进程; 把处理器分配给进程。
③非抢占/抢占方式
非抢占方式:一旦把处理机分配给某进程后,便让该进程一直执行,直至该进程完成或发生某事件而被阻塞时,才再把处理机分配给其他进程。
抢占方式:允许调度程序根据某种原则(优先权原则,短作业优先原则,时间片原则),去暂停某个正在执行的进程,将已分配给该进程的处理机重新分配给另一进程。
3.中级调度(中程调度)
①当内存空间非常紧张时,选择一个进程(阻塞或就绪状态)换出到外存,释放出内存空间给别的进程使用;当内存空间较充裕时,从外存选择一个挂起状态的进程调度到内存。
②提高内存利用率和系统吞吐量。实际上是存储器管理的对换功能。
③只有支持进程挂起的操作系统才具有中程调度功能。
二、处理机调度算法的目标及准则
1.面向用户的准则(4)
①周转时间短
周转时间:从作业被提交给系统开始,到作业完成为止的这段时间间隔
平均周转时间:
平均带权周转时间:
(Ti:周转时间 Tsi:服务时间)
②响应时间快 :从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的时间
③截止时间的保证:指某任务必须开始执行的最迟时间,或必须完成的最迟时间
④优先权准则 :基于优先权让某些紧急的作业能得到及时处理
2.面向系统的准则(3)
①系统吞吐量高。吞吐量是指在单位时间内,系统所完成的作业数。
②处理机利用率好
③各类资源的平衡利用
3.2 作业和作业调度
一、批处理系统中的作业
1.作业:包含程序,数据,作业说明书。在多道批处理系统中,作业是用户提交给系统的一项相对独立的工作。
2.作业控制块JCB
3.作业运行的三个阶段和三种状态
①收容阶段—后备状态
②运行阶段 – 运行状态
③完成阶段 – 完成状态
二、作业调度的主要任务
根据JCB信息,检查系统中的资源能否满足作业对资源的需求,按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为他们创建进程、分配必要资源,安排在就绪队列。
三、FCFS算法:有利于长作业(进程),而不利于短作业(进程)
四、SJF算法:对长作业不利;完全未考虑作业的紧迫程度;估计不准运行时间
五、优先级调度算法 :把具有最高优先级的作业调入内存之中。
六、高响应比优先调度算法
动态优先级:
3.3 进程调度
一、进程调度的任务:保存处理机现场,按照某种算法选取进程 ,把处理机分配给进程
二、进程调度的方式 (最高优先权优先(FPF)调度下细分)
1.非抢占方式
在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。
2.抢占方式
在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程的执行,重新将处理机分配给新到的优先权最高的进程。
“抢占”的原则: ①优先权原则;②短进程优先原则;③时间片原则
三、基于时间片的轮转调度算法
常用于分时系统及事务处理系统
四、优先级调度算法(抢占式/非抢占式)
五、多队列调度算法 具有较好的性能,能较好地满足各种类型用户的需要
1.置多个就绪队列,并为各个队列赋予不同的优先级。 第一个最高,以后依次降低
2.当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。
3.如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行。如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……。
4.仅当第1~i-1队列空闲时,调度程序才调度第i队列中的进程运行。
5.如果正在处理第i队列,又有新进程进入较高优先级的队列,则立即把正在处理的进程放回第i队末尾,将处理及分配给高优先级的进程。
3.4 实时调度
一、实现实时调度的基本条件
1.提供必要的信息 :就绪时间,开始和完成截止时间,处理时间,资源要求,优先级
2.系统处理能力强
3.采用抢占式调度机制 :硬实时任务
4.具有快速切换机制
二、实时调度算法分类
1.非抢占式轮转调度算法:
调度程序每次选择队列中的第一个任务投入运行。当该任务完成后,便把它挂在轮转队列的末尾,等待下次调度运行。
2.非抢占式优先调度算法:
如果在系统中存在着实时要求较为严格的任务,则可采用非抢占式优先调度算法,为这些任务赋予较高的优先级。当这些实时任务到达时,把它们安排在就绪队列的队首,等待当前任务自我终止或运行完成后,才能被调度执行。
3.基于时钟中断的抢占式优先权调度算法:
某实时任务到达后,如果该任务的优先级高于当前任务的优先级,这时并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务。
4.立即抢占的优先权调度算法:
一旦出现外部中断,只要当前任务未处于临界区,便能立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务。
三、最早截止时间优先EDF(Earliest Deadline First) 算法
该队列按各任务截止时间的早晚排序;具有最早截止时间的任务排在队列的最前面
1.用于非抢占调度的调度方式
2.抢占式调度方式用于周期实时任务
四、最低松弛度优先LLF(Least Laxity First)算法
松弛度=必须完成时间-本身的运行时间-当前时间
当有任务执行时,只有等待任务的松弛度值为0才会发生任务的调度,其他情况不发生调度。
任务执行结束后或无任务执行时,再比较等待任务的松弛度值,较小的先执行。
标签:算法,半期,处理机,队列,作业,调度,3.4,3.1,进程 From: https://www.cnblogs.com/05-ReFrain-19/p/17324112.html