短作业优先（Shortest Job First, SJF）

短作业优先（Shortest Job First, SJF）调度算法是一种以进程执行时间为依据的调度策略，以下是关于它的详细介绍：

算法原理

• 非抢占式短作业优先：调度程序每次从就绪队列中选择预计执行时间最短的进程分配CPU，一旦进程获得CPU，就会一直执行直到完成，期间不会被其他进程中断。
• 抢占式短作业优先（最短剩余时间优先）：每当有新进程到达时，调度器会比较新进程的执行时间与当前进程的剩余执行时间，如果新进程的执行时间更短，则会抢占当前进程的CPU。

算法示例

假设有四个进程P1、P2、P3、P4，预计执行时间分别为6、8、7、3个时间单位，它们都在时间点0进入系统。

• 非抢占式SJF：调度顺序为P4→P1→P3→P2，平均等待时间为(0 + 3 + 9 + 16) / 4 = 7个时间单位。
• 抢占式SJF（SRTF）：时间0到1，P1开始执行，剩余时间为5；时间1到3，P2到达，P1继续执行；时间3，P4到达，P1被抢占，P4开始执行；时间6到7，P1继续执行，剩余时间变为4；时间7到10，P3到达并执行，剩余时间为4；之后继续进行剩余进程的调度。

算法优缺点

• 优点
  • 减少平均等待时间：优先执行短任务，使较短的进程能快速完成，从而降低整体的等待时间，提高系统吞吐量。
  • 提高系统响应速度：对于短任务可以尽快完成，尤其是抢占式SJF，能更好地降低平均等待时间，提高系统的响应能力。
• 缺点
  • 长任务可能被长期推迟：如果有源源不断的新短任务进入就绪队列，长任务可能会长时间得不到执行，甚至可能导致饥饿。
  • 无法处理突发事件：非抢占式SJF一旦分配CPU，不会有中断机制处理紧急任务。
  • 需要事先知道进程的执行时间：实际中较难准确预知进程的执行时间，这可能导致该算法不一定能真正做到短作业优先调度。

适用场景

• 非抢占式SJF：适用于那些需要减少调度开销、不要求高实时性的场景，比如批处理系统。
• 抢占式SJF：适合对响应时间要求较高的系统，比如交互式系统和某些实时操作系统。