一 概述
说到linux 的内核调度算法，首先想到的是2.4内核的时间片轮转加简单的优先级策略，相对比较简单。在2.4的内核中分为实时进程和普通进程，实时进程采用SCHED_FIFO 和 SCHED_RR，FIFO是先进先出，而RR（Round Robin)采用轮转策略。如果是普通进程SCHED_NORMAL，在父进程创建子进程是coutner值减半，防止fork子进程获得多执行权限。对于睡眠进程，如果counter值没用完，则会获得更高优先级，这样保证交互进程得到快速响应。
从2.6开始引入了O(1)的红黑树算法，还是这三种算法SCHED_FIFO、SCHED_RR和SCHED_NORMAL。相对2.4主要是进行在进程优先级计算和pick next上进行了优化。后面CFS公平调度算法的引入，奠定了后面kernel调度的主基调。CFS从RSDL/SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再企图区分交互式进程，它将所有的进程都统一对待。2.6.23中，CFS实现了两个调度算法，CFS算法模块和实时调度模块。对应实时进程，将使用实时调度模块。对应普通进程则使用CFS算法。
CFS 支持三种调度测率，分别是：
SCHED_NORMAL (traditionally called SCHED_OTHER): 普通task
SCHED_BATCH: Does not preempt nearly as often as regular tasks would, thereby allowing tasks to run longer and make better use of caches but at the cost of interactivity. This is well suited for batch jobs.
SCHED_IDLE: This is even weaker than nice 19, but its not a true idle timer scheduler in order to avoid to get into priority inversion problems which would deadlock the machine.
SCHED_FIFO/_RR are implemented in sched/rt.c and are as specified by POSIX.
由于linux开始都是运行在桌面或者服务器的SMP架构，对于功耗和负载的关系没有考虑太多，比如他会将4个task平均分配到4个核上。但是对于移动端的设备，这种情况显得明显不足。对于Mobile设备，如果有4个task在不影响交互的情况下，最好是都运行在一个核上，其他三个CPU core可以关掉，这样不影响交互，电量的消耗最少，提高了设备的待机时间。
因此移动设备为了进行功耗和性能任务调度需要进行特殊设计。
二 移动设备调度算法
刚开始手机还没有大小核结构，从双核到4核都是同构CPU，调度算法主要以拔插CPU核(CPU hotpulug)和CPU的频率调节(DVFS)为主。通过拔插CPU核和调节频率适应不同人物负载。
后面发展到ARM CPU大小核的引入，对于任务繁重的情况启动大核，实现大马拉大车，轻负载用小核，小马拉小车。
对于大小核簇的调度有两种方法一种是高通的HMP调度，一种是linaro的EAS（Energy Aware Scheduling）
1） HMP（Heterogeneous mobile processing）
他的原理主要是将大小核分为大核调度域和小核调度域。不需要考虑两个域之间的负载均衡问题。主要检测当前CPU的负载，如果判断任务重那么就迁移到大核簇，反之迁移到小核簇。负载计算方法如下：
max_possible_capacity = 1024 * (fmax * / min_max_freq) *
(efficiency / min_possible_efficiency)
In the example HMP system quoted in Sec 2.3, "least" performing CPU is A53 and
thus min_max_freq = 1GHz and min_possible_efficiency = 1024.
Capacity of A57 = 1024 * (2GHz / 1GHz) * (2048 / 1024) = 4096
Capacity of A53 = 1024 * (1GHz / 1GHz) * (1024 / 1024) = 1024
Capacity of A57 when constrained to run at maximum frequency of 500MHz can be
calculated as:
Capacity of A57 = 1024 * (500MHz / 1GHz) * (2048 / 1024) = 1024
2） EAS(Energy Aware Scheduling）
EAS=DVFS+cpuidle+CFS,EAS将进程/程序/应用分为四个cgroup，即 top-app, system-background, foreground, and background,将要处理的任务放入其中一个类别中，然后为该类别提供CPU power，并将工作委派给不同的CPU核心。top-app是完成的最高优先级，其次是forground，background和system-background gorup. backgound group与system-background group具有相同的优先级，但system-background group通常也可以访问更多的核心.，EAS将选择处于最浅空闲状态的核心，从而最大限度地减少唤醒设备所需的能量.如果不需要，它不会唤醒big cluster。
对于CPU负载的跟踪，EAS有两种算法：
一种 PELT(Per-Entity Load Tracking)
一种是 WALT（Window-Assisted Load Tracking）
HMP相对于EAP，HMP的优点是性能表现比较明显，而EAS/PELT在功耗上更胜一筹。而EAS/WALT则是在性能和功耗上的最优选择。
