多核调度算法 - 加速因子 - 本质理解

前言：标准速度平台下（处理器速度为1），仅满足条件 LOAD() <= m，dens_max <= 1 就能成功调度的算法，被称为最优调度算法。这个确实如此，从 LOAD()的定义可以得出来（见P99）。

---

FBB-FFD多核分区调度算法，书上P113页，

可调度条件 (公式1)：

而：

LOAD()很难算（从LOAD定义可知），因此上式一般不会用于可调度测试。存在的意义就是为了计算接下来 FBB-FFD 的加速因子。

 

 

如何理解这个推导呢，如下：

设处理器临界速度为x，那么在x速度或者小于这个速度时，任务集的LOAD() <= m*x 且 dens_max <= x的前提下，这个任务集就总是可调度的了（这是因为总能推出上面那个(公式1)，这就表明总能调度了），这个已经就是最优调度算法了呀（见前言）。我们如果把速度大于x，我们会发现，就推不出上面(公式1)了，

因此揭露出一个规律：处理器速度越小，且满足LOAD() <= m*x 且 dens_max <= x的前提下，实际上越能成功调度。而处理器速度大了，LOAD()和dens_max 也能变得更大，所以导致了更难调度。

当我们提速1/x倍后，即使新的处理器速度为x'，现在标准速度1就是那时候的x了，而那时候的x是可以服从前面的推导的，即LOAD() <= m 且 dens_max <= 1，就一定可以调度的。

举个例：现在处理器为标准速度1，两个核，则计算得出能自由调度的临界速度为

x = 2/(4*2-1)=0.3，也就是 LOAD() <= 0.6 且 dens_max <= 0.3，的任务集都能调度，而不用做什么 LOAD() <= 1/3*xx的判断了。

换句话说，如果0.3是我们的标准速度，那么另一块处理器的速度为1（这里就是提速了3.3倍，但是用户不知道），这块新处理器就实现了 LOAD() 自由，它只要小于0.3即可。

再换句话说，如果1是标准速度（相当于上面的0.3），那么另一块处理器的速度为3.3，这块新处理器就实现了 LOAD() 自由，它只要小于1即可，即 LOAD() <= m 且 dens_max <= 1，就一定可以调度的，这不就是实现了最优调度算法嘛。因此，关键在于这里要提速的倍数，这个就是加速因子。加速因子越小，说明代价越小，说明这个调度算法越优秀。

因此加速因子定义：达到最优调度算法（在标准处理器速度为1）的LOAD()上界，该调度算法需要多少倍的处理器速度。也就是达到最优调度算法在标准处理器速度为1的调度效果，那么该调度算法需要在多少倍速度的处理器上才能实现。这里的多少倍，就是加速因子。

就像单核EDF周期任务调度，U<=1即可，周期任务的U就是等于LOAD()的，因此EDF不就是最优调度嘛。而RM利用率上界0.69，说明不是最优，因为最优的LOAD()上界是1，因此RM调度在速度为1.4（就是1/0.69）的处理器上，就有U<=1即一定可调度该任务集了。