调度
调度是为同时需要资源的多方，分配所需资源的方法。 凡有稀缺资源(“排队”)之处，皆有调度。
调度的资源
- 处理机（CPU） 从就绪队列中挑选下一个占用CPU运行的进程
- 临界区 信号量V操作后，从等待队列挑选一个进程唤醒
- 内存 从外存的挂起队列挑选一个进程激活
- I/O设备 决定I/O设备处理等待队列中的哪个I/O请求
调度的时机
- 进程从运行态切换到等待态(非抢占调度) I/O操作、wait操作、sleep……
- 进程退出(非抢占调度) return、exit、出错……
- 进程时间片完(抢占调度) 高优先级进程抢夺 时钟中断
- 进程从等待到就绪、新建(抢占调度) I/O中断、fork
调度算法
目标和相关定义 
- 运行时间:占用cpu运行的时间
周转时间=等待时间+运行时间周转时间 = 等待时间 + 运行时间周转时间=等待时间+运行时间
响应时间在等待时间里面
带权（归一化）周转时间𝑾=Tt/Ts，其中Tt𝑾 = T_t/T_s，其中T_tW=Tt/Ts，其中Tt 是进程的周转时间，TsT_sTs 是该进程接受服务的时间（即运行时间）
先来先服务,排队算法
FCFS (Fisrt Come Fisrt Serve) 或 FIFO (First In First Out)
- 缺点:周转时间长
I/O型进程必须等待计算型进程用完CPU，将导致 设备使用率低，对短作业不公平
最短作业优先
SJF(Shortest Job First) 或 Shortest Process Next- 
在目前的假设条件下，可以证明，SJF调度算法的平均 T周转时间是**最优（optimal）**的
- 缺点:作业可能在任何时刻到达,周转时间也会变长
最短剩余时间优先
SRT(Shortest Remaining Time)或STCF(Shortest Time-to-Complete First-
新来作业产生中断，重新调度 
缺点
- 可能产生饥饿(starvation) 在上面的例子中，从10时刻起，如果源源���断有短进程到来，则作业A始终得不到执行
- SJF也可能饥饿，比如0时刻到来10和100作业，之后不断有10作业到来
- 由于允许抢占，SRT比SJF更容易饥饿
- 对长作业不公平
- 算法的实现更困难，开销更大
- 必须支持中断处理（抢占）
- 需要计算“已运行的时间”
- 每次中断都要调度
轮转（轮询）调度算法
响应时间比上面三种都要好
RR（ Round Robin ），又称时间片调度 
- 每运行一个时间片（time slice, scheduling quantum，时钟周期的倍数）产生时钟中断，并重新调度
- 公平，长短作业都能兼顾，不会饥饿
- 调度时算法简单（可仅用FCFS）
时间片大小的选取 
缺点
- T周转T_{周转}T周转是各种调度算法中较差的，甚至可能还不如FCFS
高响应比优先
短作业尽快响应，长作业也能照顾到，平均周转作业时代的一个折中方案
响应比（Response Ratio） 𝑹𝒓𝑹_𝒓Rr𝑹𝒓=(等待时间+运行时间)/运行时间𝑹_𝒓 = (等待时间 + 运行时间)/运行时间Rr=(等待时间+运行时间)/运行时间=周转时间/运行时间 = 周转时间/运行时间=周转时间/运行时间当等待时间同样长，短作业的响应比高，优先执行
一般来说，没有抢占，即等待时间 == 响应时间
随等待时间的增加，响应比会上升，从而照顾到长作业 
终极解决方案-MLFQ
多级队列(静态优先级)调度：
多级=多个队列，各有不同的优先级（Priority） 
具体怎样实现是机制(mechanism ，战术)，如：
- 应该定多少个优先级？
- 每级队列使用什么调度算法（FCFS、RR）？
- 每级队列应该分多大的时间片？
- 当用完时间片，降多少级？
- 满足什么条件提升优先级？提升多少？
- 上述内容用什么方式实现？（查表、数学公式……）
规则
- if Priority(A)>Priority(B)，运行Ａ（不运行B），大于小于号要具体确定
- if Priority(A)=Priority(B)，以RR方式运行A和B
- 新来的作业的优先级定为最高
- 如果一个作业（在一定时间S内累计）用完了它的时间片，则降低其优先级
- 如果作业在时间片前释放CPU，则保持不变
- 一定时间S后，将所有作业提升为最高优先级
缺点：
- 对未知进程难以确定优先级；
- 饥饿；
- 误判：假如一个进程刚开始是计算型的，但随着时间变化为交互式的，却因为降级而永远不能被平等对待
- 博弈问题：吃透了规则的计算型进程，对普通计算型进程不公平
公平共享调度
- 优先级调度的目标：优化周转时间、响应时间、资源利用率
- 公平调度的目标：让每个任务都能获得一定份额的系统资源
Lottery调度（摆烂调度）
- 为每个进程提供至少一张彩票
- 更重要的进程获得较多彩票
- 每次调度时，随机选取一张，握有该票的进程运行
- 可在需要时将彩票交给合作进程
调度算法总结
