调度算法的指标：

CPU利用率：指CPU忙碌的时间占总时间的比例

系统吞吐量：单位时间完成的作业量  总完成了作业 / 总共花了时间

周转时间：指从作业被提交给系统开始，到完成的时间间隔

 

 调度算法

---

1. 批处理系统  --图

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-serverd（FCFS）

按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长

 

1.2 短作业优先 shortest job first（SJF） 非抢占式

按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

 

1.3 最短剩余时间优先 shortest remaining time next（SRTN）抢占式

按估计剩余时间最短的顺序进行调度。
 

 

1 .4 高响应比优先（HRRN，Highest Response Ratio Next） 非抢占式

FCFS算法是在每次调度选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，故对短作业不友好

SJF算法是选择一个执行时间最短的作业为其服务。没有考虑作业的等待时间，所以对长作业不友好，甚至会造成饥饿问题

高响应比考虑到了等待时间和运行时间

高响应比优先算法在每次调度时先计算各个作业（进程）的响应比最高的为其服务

响应比 = （等待时间 + 要求服务时间 ） /  要求服务时间

2. 交互式系统 --图

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转 抢占式

将所有就绪进程按FSFC的原子排成一个队列，每次调度，把CPU时间片分配给队首进程，当时间片用完，由计时器发出时钟中断，剥夺处理机，将进程重新放入就绪队列队尾排队，同时将CPU分配给队首的进程

时间片轮转的算法时间效率和时间片大小有关：

• 如果时间片太大，进程都可以在一个时间片内完成，时间片轮转调度算法退化为FSFC，实时性得不到保证
• 如果时间片太小，会导致进程切换频繁。进程切换都要保存进程的信息并载入新进程的信息

2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。（动态优先级）

非抢占式：

 

抢占式：

 2.3 多级反馈队列

FSFC考虑到等待时间，公平。SJF考虑到运行时间，时间片轮转可以让每个进程都得到及时响应，优先级调度算法可以灵活处理紧急任务。而多级反馈队列就对上面进行折中权衡

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。