调度算法
高级调度-作业调度--功能是用某种调度算法决定就绪队列中那几个作业调入内存
中级调度-内存调度--功能是将外存中的程序块调入内存，并加入就绪队列
低级调度-进程调度--功能是用算法决定哪个进程获得处理机
阅读本文应了解的知识：
- 周转时间 = 完成时间 - 到达时间
- 带权周转时间 = 周转时间/运行时间
- 等待时间 = 周转时间 – 运行时间
- 响应比=（等待时间+要求服务时间）/ 要求服务时间
FCFS-先来先服务
- 算法思想： 公平
- 规则：按照作业/进程到达顺序进行服务
- 作业调度：考虑哪个作业先到到后备队列
- 进程调度：考虑哪个进程先到达就绪队列
- 是否抢占式：非抢占式
- 优点：简单容易实现，公平
- 缺点：不利于短作业，对长作业有利
- 是否导致饥饿：不会
- 周转时间 = 完成时间 - 到达时间
- 带权周转时间 = 周转时间/运行时间
- 等待时间 = 周转时间 – 运行时间
J1->J2->J3->J4
作业 |
到达时间 |
所需服务时间 |
开始执行时间 |
完成时间 |
周转时间 |
带权周转时间 |
J1 |
0 |
20 |
0 |
20 |
20 |
1 |
J2 |
5 |
15 |
20 |
35 |
30 |
2 |
J3 |
10 |
5 |
35 |
40 |
30 |
6 |
J4 |
15 |
10 |
40 |
50 |
35 |
3.5 |
SJF-短作业优先(SPF短进程优先)
- 算法思想： 追求平均等待时间，平均周转时间，平均带权周转时间最短
- 规则：服务时间最短的优先得到服务
- 作业调度：SJF短作业优先
- 进程调度：SPF短进程优先
- 是否抢占式：SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法
- 优点：“最短的”平均等待时间、平均周转时间(前提是所有进程同时可运行或者说所有进程几乎都同时到达)因为最短剩余时间优先算法得到的平均等待
时间、平均周转时间还要更少 - 缺点：不利于长作业，对短作业有利，由此可能产生饥饿现象
- 是否导致饥饿：会，当短作业不断到来会导致长作业长时间得不到服务
- 周转时间 = 完成时间 - 到达时间
- 带权周转时间 = 周转时间/运行时间
- 等待时间 = 周转时间 – 运行时间
J1->J3->J4->J2
作业 |
到达时间 |
所需服务时间 |
开始执行时间 |
完成时间 |
周转时间 |
带权周转时间 |
J1 |
0 |
20 |
0 |
20 |
20 |
1 |
J2 |
5 |
15 |
35 |
50 |
45 |
3 |
J3 |
10 |
5 |
20 |
25 |
15 |
3 |
J4 |
15 |
10 |
25 |
35 |
20 |
2 |
证明：如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。
设有n个作业j1,j2,j3,...,jn，其运行时间分别为t1,t2,t3,...,tn。不妨假设t1<=t2<=t3<=...<=tn，则短作业优先的作业调度算法的平均周转时间为：
T=(t1+(t1+t2)+(t1+t2+t3)+....(t1+t2+t3+...+tn))/n
=(n*t1+(n-1)*t2+...+tn)/n
考虑其他不同调度算法，设在此调度算法下的作业调度次序为ji1,ji2,...jin,其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，则类似上面可以得出：
T1=((n*ti1+(n-1)*ti2+...+tin)/n)
根据不等式结论：如果有a1<=a2<=...<=an 且b1<=b2<=...<=bn，则
a1bn+a2bn-1+...+anb1<=a1bi1+a2bi2+...+anbn<=a1b1+a2b2+...+anbn
其中（i1,i2,...,in）是（1,2,3,...,n）的一个排列，不难得出T<=T1。
HRRN-高相应比优先
- 算法思想： 要综合考虑作业/进程的等待时间和要求服务时间
- 规则：每次调度都计算各个作业/进程的响应比，选最高的进行服务
- 是否抢占式：非抢占式
- 优缺点：
等待时间相同时，要求服务时间短的优先（SJF 的优点）
要求服务时间相同时，等待时间长的优先（FCFS 的优点）
对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题 - 是否导致饥饿：不会
- 周转时间 = 完成时间 - 到达时间
- 带权周转时间 = 周转时间/运行时间
- 等待时间 = 周转时间 – 运行时间
- 响应比=（等待时间+要求服务时间）/ 要求服务时间=(开始时间-到达时间+服务)/服务
- 开始时间指本次调度的作业的开始时间，即上一个完成的进程的完成时间
响应比计算：
0时刻：只有J1到达就绪队列，J1上处理机
7时刻（J1完成）：就绪队列中有 J2 (响应比=(20-5+15)/15=2)、 J3((20-10+5)/5=3)、 J4((20-15+10)/10=1.5)，
8时刻（J3完成）： J2((25-5+15)/15=2.3)、 J4((25-15+10)/10=2)
12时刻（J2完成）：就绪队列中只剩下 J4
作业 |
到达时间 |
所需服务时间 |
开始执行时间 |
完成时间 |
周转时间 |
带权周转时间 |
J1 |
0 |
20 |
0 |
20 |
20 |
1 |
J2 |
5 |
15 |
25 |
40 |
35 |
2.3 |
J3 |
10 |
5 |
20 |
25 |
15 |
3 |
J4 |
15 |
10 |
40 |
50 |
35 |
3.5 |
时间片轮转--适合多用户分时系统。
平均分配给每个进程相同的时间片，当时间片到或进程阻塞和主动结束，会将CPU交给下一个进程
时间片设为 20ms~50ms 通常是一个比较合理的折中值。
最高优先级调度
算法分为抢占式和非抢占式
- 非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度
- 而抢占式调度每有一个新的就绪队列，便进行优先权比较，
优先级分为分静态优先级和动态优先级
- 静态优先级，创建时确认，无法修改
- 动态优先级，会随着时间的增加而提升优先级，
多级反馈队列调度--整合包
多级--分为多个队列
反馈--会进行对比
过程
新来的进入第一队列末尾，按先来先服务等待调度，如果第一时间片结束但没运行完，则进入第二队列
特点
- 多队列，1-n
- 优先级递减
- 时间片递增
