调度算法

高级调度-作业调度--功能是用某种调度算法决定就绪队列中那几个作业调入内存

中级调度-内存调度--功能是将外存中的程序块调入内存，并加入就绪队列

低级调度-进程调度--功能是用算法决定哪个进程获得处理机

阅读本文应了解的知识：

• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间/运行时间
• 等待时间 = 周转时间 – 运行时间
• 响应比=（等待时间+要求服务时间）/ 要求服务时间

FCFS-先来先服务

• 算法思想： 公平
• 规则：按照作业/进程到达顺序进行服务
• 作业调度：考虑哪个作业先到到后备队列
• 进程调度：考虑哪个进程先到达就绪队列
• 是否抢占式：非抢占式
• 优点：简单容易实现，公平
• 缺点：不利于短作业，对长作业有利
• 是否导致饥饿：不会
• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间/运行时间
• 等待时间 = 周转时间 – 运行时间

J1->J2->J3->J4

SJF-短作业优先(SPF短进程优先)

• 算法思想： 追求平均等待时间，平均周转时间，平均带权周转时间最短
• 规则：服务时间最短的优先得到服务
• 作业调度：SJF短作业优先
• 进程调度：SPF短进程优先
• 是否抢占式：SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法
• 优点：“最短的”平均等待时间、平均周转时间(前提是所有进程同时可运行或者说所有进程几乎都同时到达)因为最短剩余时间优先算法得到的平均等待
  时间、平均周转时间还要更少
• 缺点：不利于长作业，对短作业有利，由此可能产生饥饿现象
• 是否导致饥饿：会，当短作业不断到来会导致长作业长时间得不到服务
• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间/运行时间
• 等待时间 = 周转时间 – 运行时间

J1->J3->J4->J2

证明：如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。

 设有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

时间片轮转--适合多用户分时系统。

平均分配给每个进程相同的时间片，当时间片到或进程阻塞和主动结束，会将CPU交给下一个进程

时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级调度

算法分为抢占式和非抢占式

• 非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度
• 而抢占式调度每有一个新的就绪队列，便进行优先权比较，

优先级分为分静态优先级和动态优先级

• 静态优先级，创建时确认，无法修改
• 动态优先级，会随着时间的增加而提升优先级，

多级反馈队列调度--整合包

多级--分为多个队列

反馈--会进行对比

过程

新来的进入第一队列末尾，按先来先服务等待调度，如果第一时间片结束但没运行完，则进入第二队列

特点

• 多队列，1-n
• 优先级递减
• 时间片递增