CPU的调度和schedule()（哈工大李志军）

CPU调度策略

CPU调度即在就绪队列中，通过调度选择下一个执行的任务。

调度算法：

• 尽快结束任务：周转时间（从任务进入到任务结束）短
• 用户操作尽快响应：响应时间（从操作发生到响应）短
• 系统内耗时间少：吞吐量（完成的任务量）

如何做到合理？

• 吞吐量与响应时间的矛盾：
  

• 前台任务和后台任务的关注点不同：

  前台任务关注响应时间，后台任务关注周转时间。

• IO约束型任务和CPU约束型任务：
  

• IO约束型任务： CPU区间长度较短，调用IO频率较大。多是前台任务。

• CPU约束型任务： CPU区间长度较长，调用CPU频率高。多是后台任务。

周转时间=作业完成时刻—作业到达时刻；
带权周转时间=周转时间/服务时间；
平均周转时间=作业周转总时间/作业个数；
平均带权周转时间=带权周转总时间/作业个数；

---

First Come, First Served(FCFS)，先来先服务

缩短周转时间：短作业优先（SJF）

短作业优先的调度平均周转时间最短。
证明：
平均周转时间：
$p_1+(p_1+p_2)+(p_1+p_2+p_3)+....+(p_1+p_2+...+p_n)$p1​+(p1​+p2​)+(p1​+p2​+p3​)+....+(p1​+p2​+...+pn​)
合并之后：
$= np_1+(n-1)p_2+....+p_i = \sum(n+1+i)p_i$=np1​+(n−1)p2​+....+pi​=∑(n+1+i)pi​
任取两个任务 $p_j < p_k,(j<k)$pj​<pk​,(j<k)
平均周转时间：
$= np_1+(n-1)p_2+....+(n+1-j)p_j+.....+(n+1-k)p_k+...+p_i$=np1​+(n−1)p2​+....+(n+1−j)pj​+.....+(n+1−k)pk​+...+pi​
交换 $p_j,p_k$pj​,pk​：
$= np_1+(n-1)p_2+....+(n+1-j)p_k+.....+(n+1-k)p_j+...+p_i$=np1​+(n−1)p2​+....+(n+1−j)pk​+.....+(n+1−k)pj​+...+pi​
由 $p_j < p_k$pj​<pk​
$(n+1-j)p_j+(n+1-k)p_k < (n+1-j)p_k+(n+1-k)p_j$(n+1−j)pj​+(n+1−k)pk​<(n+1−j)pk​+(n+1−k)pj​
所以短作业优先可以保证平均周转时间最短。

缩短响应时间：时间片轮转

设定时间片的大小，将时间片分配到每个任务，依次执行直至全部执行完毕。

调度算法的选择：

后台任务得不到运行->尝试后台任务优先级动态升高 -> 前台响应时间拉长 -> 尝试前后台任务使用时间片 -> 退化到仅时间片轮转 -> 时间片轮转的弊端 …

一个实际的 schedule() 函数

• while循环找出PCB数组(task[])中counter最大的就绪态的进程，设为next。
• if(counter != 0) 直接切换到next进程
• else if(counter == 0) 进入for循环，将 PCB数组中所有进程counter = counter / 2 + priority ：
  • 此时如果就绪态的进程，执行前counter应为0
  • 如果是阻塞态的进程(如 IO), 执行后counter 应比就绪态的counter大，使其执行时间更长，优先级更高，此处实现了优先级的动态调整。

counter第一个作用：时间片

counter第二个作用：优先级

counter总结

因为时间片轮转短作业的任务也会先执行完，所以轮转起来也近似了SJF调度。