基础的进程调度策略

• 为了简化分析，我们对进程（工作）做出以下不现实的假设
  • 假设1：每个工作执行相同的时间
  • 假设2：所有的工作同时到达
  • 假设3：一旦开始，每个工作保持运行直到完成（非抢占式）
  • 假设4：所有的工作都只是占用CPU（即它们不执行IO操作）
  • 假设5：每个工作的运行时间是已知的
• 通过逐步放宽假设，我们可以逐渐得到贴合现实的情况

• 调度指标用于在相同的假设下比较不同的调度策略，如：
  • 周转时间
    • 周转时间 = 完成时间 - 到达时间
    • 周转时间适合度量后台进程
  • 响应时间
    • 响应时间 = 首次运行时间 - 到达时间
    • 响应时间适合度量前台进程

先进先出(FIFO)/先来先服务(FCFS)

• 工作负载
  • 放宽假设1：每个工作可以执行不同的时间
• 策略
  • 按照进程的启动时间构造队列，先启动的先运行，直到运行完毕后再启动下一个进程
• 结果
  • 在某些情况下（如1s->2s->3s），平均周转时间为2秒，还不错
  • 在某些情况下（如10s->1s->1s），平均周转时间为11秒，并不理想（这种情况被称为“护航效应(Convoy Effect)”，即你在食堂排队时发现前面的人满背包找自己的饭卡，你还不得不等他）

最短任务优先(SJF, Shortest Job First)

• 工作负载
  • 放宽假设1：每个工作可以执行不同的时间
  • 放宽假设2：工作现在可以随时到达
• 策略
  • 先运行最短的任务，然后运行次短的任务，以此类推
• 结果
  • 对于同时到达的3个进程（如1s->2s->12s），平均周转时间为5s，还不错
  • 对于不同时到达的3个进程（如进程A(100s)到达，10秒后进程B(10s)、进程C(10s)到达），因为SJF是非抢占的，B和C仍然需要被迫等到A完成后才能开始，这并不理想。为了解决这个问题，还需要进一步放宽假设条件

最短完成时间优先(STCF, Shortest Time-to-Completion First)/最短剩余时间优先(SRTF, Shortest Remain Time First)

• 工作负载
  • 放宽假设1：每个工作可以执行不同的时间
  • 放宽假设2：工作现在可以随时到达
  • 放宽假设3：工作开始后不需要一直运行直到完成，即调度程序可以抢占工作A，转而执行工作B，稍后再回来执行工作A（抢占式调度程序）
• 策略
  • 向SJF添加抢占机制：每当新工作进入系统时，它就会确定手头上的工作中谁的剩余时间最少，然后执行调度
• 结果
  • 对与2.b.iii.2)的例子：进程A(100s)到达，10秒后进程B(10s)、进程C(10s)到达，此时B和C到达后A进程会被抢占，转而执行B、C，然后才回到A

轮转(RR, Round-Robin)

• 工作负载
  • 放宽假设1：每个工作可以执行不同的时间
  • 放宽假设2：工作现在可以随时到达
  • 放宽假设3：工作开始后不需要一直运行直到完成，即调度程序可以抢占工作A，转而执行工作B，稍后再回来执行工作A（抢占式调度程序）
• 策略
  • 系统中存在有时间长度的时间片(Time Slice)，每个时间片的长度必须是时钟中断周期的倍数
  • 系统在一个时间片内运行一个工作，当切换到下一个时间片时，系统就会换一个工作运行，以此构成循环，使每个工作都以很短的周期循环运行
• 结果
  • 这样的方法带来的平均响应时间很短，不过平均周转周期则长的可怕
• 注意
  • 时间片长度不能设置得太短，因为上下文切换需要时间，过于频繁的上下文切换会影响整体性能。这里使用摊销技术(Amortization) 来让浪费的时间占比更小。

• 策略
  • 使用重叠(Overlap) 操作，由于IO操作不占用CPU，所以此时CPU可以给别的进程使用，达到进程并行的效果
  • 在当前进程A发出IO请求后，系统会调度去执行别的进程，直到进程A的IO完成后，A才会再回到就绪队列等待被调度

• 策略：……也许可以尝试从历史中学习？