总论:所有的程序都是CPU和I/O等待交替执行
CPU调度器的操作时机
调用CPU调度器的时机,通常发生在
某一进程从执行状态转化为等待状态
某一进程从执行状态转化为就绪状态
某一进程从等待状态转为就绪状态
某一进程终止
注意,调度时机不限于此4种情况,有非抢占式调度,和抢占式调度
CPU调度器
决定了将CPU分配给谁
后续操作就是, CPU分配器将CPU控制权交给该进程,操作内容通常包括
上下文切换
从内核态转移至用户态
跳转至用户程序中PC寄存器所指示的位置
分配延迟
CPU分配暂停前一进程,启动后一进程所经历的时间
CPU调度追求的指标
线程调度算法
1.First-Come,First-Served(FCFS)
2.Shortest-Job-First(SJF)调度算法
算法要求:
进入就绪队列的进程预告需要多长CPU时间才能完成本次执行
算法思想:
选取就绪队列中,需要CPU时间最短的进程
3.Highest response Ratio Next
从甘特图中可以得到这个结果.以上几个算法不好实现或者效果不太好
4.优先权法(Priority Scheduling)
每个进程都有一个优先数,通常是整型数,选取就绪队列中,优先权最高的进程
当优先权定义为进程"需要的CPU时间"时,SJF算法就是有优先权法
5.轮转法(Round Robin,RR)
每个就绪进程获得一小段CPU时间(时间片,time quantum),通常10ms-100ms
时间片用完,这个进程被迫交出CPU,重新挂回到就绪队列
当然,进程在时间片用毕之前其Burst Cycle结束,也主动交出CPU
假设n个就绪进程,时间片q,每个就绪进程得到1/n的CPU时间.任何就绪进程最 多等待(n-1)q单位时间.
多层队列
把就绪队列拆分成几个队列
列入:
要求交互的进程,在前台队列
可以批处理的进程,在后台队列每个队列有其自己的调度算法
前台就绪队列 -- RR
后台就绪队列--FCFS
设计多层队列
就绪队列进入就绪队列时,决定去哪儿?
CPU怎么在队列间分配?
固定优先权法.列如,先前台队列,再后台队列
时间片办法.列如,80%的CPU时间给前台队列,20%的CPU时间给后台进 程
多层反馈队列示例
三层队列
Q0 - 用RR算法,时间片8ms
Q1 - 用RR算法,时间片16ms
Q2 - 用FCFS算法
多层反馈队列示例
调度场景
一个就绪进程进入Q0层.当它分配到CPU,可执行8ms.如果它8s后没有执行完毕,则迁移至Q1层.否则,它离开就绪队列,该干嘛干嘛.
在Q1层,当它分配到CPU,可执行16ms.如果16ms后没有执行完毕,则迁移至Q2层.否则离开就绪队列,该干嘛干嘛.
设计多层反馈队列
队列个数
每层队列它自己的调度算法
一个算法,将就绪进程升级至高层次队列
一个算法,将就绪进程降级至低层次队列
一个算法,决定当一个就绪进程进入就绪队列时,去那层
实时调度
硬实时系统 - 调度机制能够确保一个关键任务在给定的时间点前完成(必须的)
软实时计算 - 调度机制尽量给与关键任务最高优先级,尽量在预定时间点钱完 成 (尽量完成)