一 概述
說到linux 的內(nèi)核調(diào)度算法，首先想到的是2.4內(nèi)核的時間片輪轉(zhuǎn)加簡單的優(yōu)先級策略酿愧，相對比較簡單沥潭。在2.4的內(nèi)核中分為實(shí)時進(jìn)程和普通進(jìn)程，實(shí)時進(jìn)程采用SCHED_FIFO 和 SCHED_RR嬉挡，F(xiàn)IFO是先進(jìn)先出钝鸽，而RR（Round Robin)采用輪轉(zhuǎn)策略。如果是普通進(jìn)程SCHED_NORMAL庞钢，在父進(jìn)程創(chuàng)建子進(jìn)程是coutner值減半拔恰，防止fork子進(jìn)程獲得多執(zhí)行權(quán)限。對于睡眠進(jìn)程基括，如果counter值沒用完颜懊，則會獲得更高優(yōu)先級，這樣保證交互進(jìn)程得到快速響應(yīng)风皿。
從2.6開始引入了O(1)的紅黑樹算法河爹，還是這三種算法SCHED_FIFO、SCHED_RR和SCHED_NORMAL桐款。相對2.4主要是進(jìn)行在進(jìn)程優(yōu)先級計算和pick next上進(jìn)行了優(yōu)化咸这。后面CFS公平調(diào)度算法的引入，奠定了后面kernel調(diào)度的主基調(diào)魔眨。CFS從RSDL/SD中吸取了完全公平的思想媳维，不再跟蹤進(jìn)程的睡眠時間，也不再企圖區(qū)分交互式進(jìn)程遏暴，它將所有的進(jìn)程都統(tǒng)一對待侄刽。2.6.23中，CFS實(shí)現(xiàn)了兩個調(diào)度算法朋凉，CFS算法模塊和實(shí)時調(diào)度模塊州丹。對應(yīng)實(shí)時進(jìn)程，將使用實(shí)時調(diào)度模塊侥啤。對應(yīng)普通進(jìn)程則使用CFS算法当叭。
CFS 支持三種調(diào)度測率，分別是：
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開始都是運(yùn)行在桌面或者服務(wù)器的SMP架構(gòu)盖灸，對于功耗和負(fù)載的關(guān)系沒有考慮太多蚁鳖，比如他會將4個task平均分配到4個核上。但是對于移動端的設(shè)備赁炎，這種情況顯得明顯不足醉箕。對于Mobile設(shè)備，如果有4個task在不影響交互的情況下徙垫，最好是都運(yùn)行在一個核上讥裤，其他三個CPU core可以關(guān)掉，這樣不影響交互姻报，電量的消耗最少己英，提高了設(shè)備的待機(jī)時間。
因此移動設(shè)備為了進(jìn)行功耗和性能任務(wù)調(diào)度需要進(jìn)行特殊設(shè)計吴旋。
二 移動設(shè)備調(diào)度算法
剛開始手機(jī)還沒有大小核結(jié)構(gòu)损肛，從雙核到4核都是同構(gòu)CPU，調(diào)度算法主要以拔插CPU核(CPU hotpulug)和CPU的頻率調(diào)節(jié)(DVFS)為主荣瑟。通過拔插CPU核和調(diào)節(jié)頻率適應(yīng)不同人物負(fù)載治拿。
后面發(fā)展到ARM CPU大小核的引入，對于任務(wù)繁重的情況啟動大核笆焰，實(shí)現(xiàn)大馬拉大車劫谅，輕負(fù)載用小核，小馬拉小車嚷掠。
對于大小核簇的調(diào)度有兩種方法一種是高通的HMP調(diào)度捏检，一種是linaro的EAS（Energy Aware Scheduling）
1） HMP（Heterogeneous mobile processing）
他的原理主要是將大小核分為大核調(diào)度域和小核調(diào)度域。不需要考慮兩個域之間的負(fù)載均衡問題不皆。主要檢測當(dāng)前CPU的負(fù)載未檩，如果判斷任務(wù)重那么就遷移到大核簇，反之遷移到小核簇粟焊。負(fù)載計算方法如下：
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將進(jìn)程/程序/應(yīng)用分為四個cgroup冤狡，即 top-app, system-background, foreground, and background,將要處理的任務(wù)放入其中一個類別中，然后為該類別提供CPU power项棠，并將工作委派給不同的CPU核心悲雳。top-app是完成的最高優(yōu)先級，其次是forground香追，background和system-background gorup. backgound group與system-background group具有相同的優(yōu)先級合瓢，但system-background group通常也可以訪問更多的核心.，EAS將選擇處于最淺空閑狀態(tài)的核心透典，從而最大限度地減少喚醒設(shè)備所需的能量.如果不需要晴楔，它不會喚醒big cluster顿苇。
對于CPU負(fù)載的跟蹤，EAS有兩種算法：
一種 PELT(Per-Entity Load Tracking)
一種是 WALT（Window-Assisted Load Tracking）
HMP相對于EAP税弃，HMP的優(yōu)點(diǎn)是性能表現(xiàn)比較明顯纪岁，而EAS/PELT在功耗上更勝一籌。而EAS/WALT則是在性能和功耗上的最優(yōu)選擇则果。
