linux在多核處理器上的負(fù)載均衡原理
linux在多核處理器上的負(fù)載均衡原理
CPU作為電腦的核心組成部份，它的好壞直接影響到電腦的性能。下面是學(xué)習(xí)啦小編帶來的關(guān)于linux在多核處理器上的負(fù)載均衡原理的內(nèi)容，歡迎閱讀!
linux在多核處理器上的負(fù)載均衡原理：
現(xiàn)在互聯(lián)網(wǎng)公司使用的都是多CPU(多核)的服務(wù)器了，Linux操作系統(tǒng)會(huì)自動(dòng)把任務(wù)分配到不同的處理器上，并盡可能的保持負(fù)載均衡。那Linux內(nèi)核是怎么做到讓各個(gè)CPU的壓力均勻的呢?
做一個(gè)負(fù)載均衡機(jī)制，重點(diǎn)在于：
1. 何時(shí)檢查并調(diào)整負(fù)載情況?
2. 如何調(diào)整負(fù)載?
先看第一個(gè)問題。
如果讓我這樣的庸俗程序員來設(shè)計(jì)，我第一個(gè)想到的就是每隔一段時(shí)間檢查一次負(fù)載是否均衡，不均則調(diào)整之，這肯定不是最高效的辦法，但肯定是實(shí)現(xiàn)上最簡單的。實(shí)際上，2.6.20版linux kernel的確使用軟中斷來定時(shí)調(diào)整多CPU上的壓力(調(diào)用函數(shù)run_rebalance_domains)，每秒1次。
但每秒一次還是不能滿足要求，對(duì)很多應(yīng)用來說，1秒太長了，一秒鐘內(nèi)如果發(fā)生負(fù)載失衡對(duì)很多web應(yīng)用都是不能接受的，何況其他實(shí)時(shí)應(yīng)用。最好kernel能夠緊跟進(jìn)程的變化來調(diào)整。
那么，好，我們在進(jìn)程創(chuàng)建和進(jìn)程exit的時(shí)候檢查并調(diào)整負(fù)載呢?可以，但是不完整，一個(gè)進(jìn)程創(chuàng)建以后如果頻繁的睡眠、醒來、睡眠、醒來，它這樣折騰對(duì)CPU的負(fù)載是有影響的，你就不管它了嗎?說到底，我們其實(shí)關(guān)注的是進(jìn)程是否在使用CPU，而不是它是否誕生了。所以，我們應(yīng)該在進(jìn)程睡眠和醒來這兩個(gè)時(shí)間點(diǎn)檢查CPU們的負(fù)載。
再看第二個(gè)問題，怎么調(diào)整負(fù)載呢?從最繁忙的那個(gè)CPU上挪一個(gè)進(jìn)程到最閑的那個(gè)CPU上，如果負(fù)載還不均衡，就再挪一個(gè)進(jìn)程，如果還不均衡，繼續(xù)挪....這也是個(gè)最笨的方法，但它卻真的是linux CPU負(fù)載均衡的核心，不過實(shí)際的算法在此基礎(chǔ)上有很多細(xì)化。對(duì)于Intel的CPU，壓縮在同一個(gè)chip上的多核是共享同一個(gè)L2的(如下圖，里面的一個(gè)Processor其實(shí)就是一個(gè)chip)，如果任務(wù)能盡可能的分配在同一個(gè)chip上，L2 cache就可以繼續(xù)使用，這對(duì)運(yùn)行速度是有幫助的。所以除非“很不均衡”，否則盡量不要把一個(gè)chip上的任務(wù)挪到其他chip上。
于是，為了應(yīng)對(duì)這種CPU core之間的異質(zhì)性——在不同的core之間遷移任務(wù)，代價(jià)不同——Linux kernel引入了sched_domain和sched_group的概念。sched_domain和sched_group的具體原理，可參考劉勃的文章和英文資料。
【代碼剖析】
SMP負(fù)載均衡檢查或調(diào)整在兩個(gè)內(nèi)核函數(shù)里發(fā)生：
1. schedule()。當(dāng)進(jìn)程調(diào)用了sleep、usleep、poll、epoll、pause時(shí)，也就是調(diào)用了可能睡去的操作時(shí)都會(huì)轉(zhuǎn)為內(nèi)核代碼里對(duì)schedule()函數(shù)的調(diào)用。
2. try_to_wake_up() 。說白了就是進(jìn)程剛才睡了，現(xiàn)在要醒來，那醒來以后跑在哪個(gè)CPU上呢?這個(gè)選擇CPU的過程，也就是負(fù)載均衡的過程。
我們先看schedule()的代碼，我們忽略函數(shù)前面那些和負(fù)載均衡無關(guān)的代碼(本文代碼以內(nèi)核2.6.20版為準(zhǔn))：
[kernel/sched.c --> schedule() ]
3489 cpu = smp_processor_id();
3490 if (unlikely(!rq->nr_running)) {
3491 idle_balance(cpu, rq);
3492 if (!rq->nr_running) {
3493 next = rq->idle;
3494 rq->expired_timestamp = 0;
3495 wake_sleeping_dependent(cpu);
3496 goto switch_tasks;
3497 }
3498 }
每個(gè)CPU都有一個(gè)運(yùn)行隊(duì)列即這里的 rq，運(yùn)行隊(duì)列里放著該CPU要運(yùn)行的進(jìn)程，如果運(yùn)行隊(duì)列里沒有進(jìn)程了，就說明當(dāng)前CPU沒有可調(diào)度的任務(wù)了，那就要調(diào)用idle_balance從其它CPU上“平衡”一些(就是挪一些)進(jìn)程到當(dāng)前rq里。
再看 idle_balance()的實(shí)現(xiàn)：
[kernel/sched.c --> idle_balance()]
2806 /*
2807 * idle_balance is called by schedule() if this_cpu is about to become
2808 * idle. Attempts to pull tasks from other CPUs.
2809 */
2810 static void idle_balance(int this_cpu, struct rq *this_rq)
2811 {
2812 struct sched_domain *sd;
2813 int pulled_task = 0;
2814 unsigned long next_balance = jiffies + 60 * HZ;
2815
2816 for_each_domain(this_cpu, sd) {
2817 unsigned long interval;
2818
2819 if (!(sd->flags & SD_LOAD_BALANCE))
2820 continue;
2821
2822 if (sd->flags & SD_BALANCE_NEWIDLE)
2823 /* If we've pulled tasks over stop searching: */
2824 pulled_task = load_balance_newidle(this_cpu,
2825 this_rq, sd);
2826
2827 interval = msecs_to_jiffies(sd->balance_interval);
2828 if (time_after(next_balance, sd->last_balance + interval))
2829 next_balance = sd->last_balance + interval;
2830 if (pulled_task)
2831 break;
2832 }
2833 if (!pulled_task)
2834 /*
2835 * We are going idle. next_balance may be set based on
2836 * a busy processor. So reset next_balance.
2837 */
2838 this_rq->next_balance = next_balance;
2839 }
從子 sched_domain到父sched_domain遍歷該CPU對(duì)應(yīng)的domain(2816行)，并調(diào)用load_balance_newidle，我們繼續(xù)：
[kernel/sched.c --> load_balance_newidle()]
2730 static int
2731 load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
2732 {
2733 struct sched_group *group;
2734 struct rq *busiest = NULL;
2735 unsigned long imbalance;
2736 int nr_moved = 0;
2737 int sd_idle = 0;
2738 cpumask_t cpus = CPU_MASK_ALL;
2739
2740 /*
2741 * When power savings policy is enabled for the parent domain, idle
2742 * sibling can pick up load irrespective of busy siblings. In this case,
2743 * let the state of idle sibling percolate up as IDLE, instead of
2744 * portraying it as NOT_IDLE.
2745 */
2746 if (sd->flags & SD_SHARE_CPUPOWER &&
2747 !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
2748 sd_idle = 1;
2749
2750 schedstat_inc(sd, lb_cnt[NEWLY_IDLE]);
2751 redo:
2752 group = find_busiest_group(sd, this_cpu, &imbalance, NEWLY_IDLE,
2753 &sd_idle, &cpus, NULL);
2754 if (!group) {
2755 schedstat_inc(sd, lb_nobusyg[NEWLY_IDLE]);
2756 goto out_balanced;
2757 }
2758
2759 busiest = find_busiest_queue(group, NEWLY_IDLE, imbalance,
2760 &cpus);
2761 if (!busiest) {
2762 schedstat_inc(sd, lb_nobusyq[NEWLY_IDLE]);
2763 goto out_balanced;
2764 }
2765
2766 BUG_ON(busiest == this_rq);
2767
2768 schedstat_add(sd, lb_imbalance[NEWLY_IDLE], imbalance);
2769
2770 nr_moved = 0;
2771 if (busiest->nr_running > 1) {
2772 /* Attempt to move tasks */
2773 double_lock_balance(this_rq, busiest);
2774 nr_moved = move_tasks(this_rq, this_cpu, busiest,
2775 minus_1_or_zero(busiest->nr_running),
2776 imbalance, sd, NEWLY_IDLE, NULL);
原來就是我們上面說的“笨辦法”，針對(duì)當(dāng)前CPU所屬的每個(gè)domain(從子到父)，找到該 sched_domain里最忙的sched_group(2752行)，再從該group里找出最忙的運(yùn)行隊(duì)列(2759行)，最后從該“最忙”運(yùn)行隊(duì)列里挑出幾個(gè)進(jìn)程到當(dāng)前CPU的運(yùn)行隊(duì)列里。move_tasks函數(shù)到底挪多少進(jìn)程到當(dāng)前CPU是由第4和第5個(gè)參數(shù)決定的，第4個(gè)參數(shù)是指最多挪多少個(gè)進(jìn)程，第5個(gè)參數(shù)是指最多挪多少“壓力”。有了這兩個(gè)參數(shù)限制，就不會(huì)挪過頭了(即把太多進(jìn)程挪到當(dāng)前CPU，造成新的不均衡)。
舉個(gè)例子，假如有一臺(tái)8核的機(jī)器，兩個(gè)CPU插槽，也就是兩個(gè)chip，每個(gè)chip上4個(gè)核，再假設(shè)現(xiàn)在core 4最忙，core 0第二忙，如圖：
按照 劉勃的文章里的提法，首先是core domain，即Processor 0屬于domain 1，Processor 1屬于domain 2，其中domain 1包含4個(gè)sched_group，每個(gè)group對(duì)應(yīng)一個(gè)core，如下圖(group未畫出)：
假如現(xiàn)在是 Core 3 在執(zhí)行idle_balance，則先在domain 1里找最忙的group，找到第二忙的group是core 0(core 4不在domain 1里，所以不會(huì)找到它)，再從core 0里找最忙的runqueue(運(yùn)行隊(duì)列)，core 0就一個(gè)運(yùn)行隊(duì)列，所以直接就是它對(duì)應(yīng)的runqueue了，然后從該runqueue里挪出幾個(gè)任務(wù)到Core 3，這一層domain的均衡做完了。
接著是domain 1的父domain，即 cpu_domain，下圖的domain 0：
這個(gè)domain 0包含了兩個(gè)group，每個(gè)group對(duì)應(yīng)一個(gè)chip，即每個(gè)group對(duì)應(yīng)了4個(gè)core。
在domain 0找最繁忙的group，顯然會(huì)找到Processor1 對(duì)應(yīng)的group(因?yàn)閏ore 4超忙)，那么繼續(xù)在Processor 1里找最忙的runqueue，于是找到core 4，最后從core 4的runqueue里挑出幾個(gè)任務(wù)挪到core 3,。
這樣，整個(gè)系統(tǒng)8個(gè)核都基本平衡了。
也許有人要問，為什么是從子domain到父domain這樣遍歷，而不是倒過來，從父到子遍歷呢?這是因?yàn)樽觗omain通常都是在一個(gè)chip上，任務(wù)的很多數(shù)據(jù)在共享的L2 cache上，為了不讓其失效，有必要盡量讓任務(wù)保持在一個(gè)chip上。
也許還有人要問：如果core 3本來就是最忙的core，它如果運(yùn)行idle_balance，會(huì)發(fā)生什么?答案是什么也不會(huì)發(fā)生。因?yàn)樵趂ind_busiest_group函數(shù)里，如果發(fā)現(xiàn)最忙的是“本CPU”，那么就直接返回NULL，也就不再做任何事。
那core 3豈不永遠(yuǎn)是最忙的了?呵呵，大家忘了，系統(tǒng)里總有閑的CPU(哪怕是相對(duì)比較閑)，它總會(huì)執(zhí)行schedule()，就算它從不調(diào)用sleep從不睡眠，時(shí)鐘中斷也會(huì)迫使其進(jìn)程切換，進(jìn)而調(diào)用schedule，進(jìn)而將繁忙CPU的任務(wù)攬一部分到自己身上。這樣，誰最閑，誰早晚會(huì)從忙人身上攬活兒過來，所以忙人不會(huì)永遠(yuǎn)最忙，閑人也不會(huì)永遠(yuǎn)最閑，所以就平等，就均衡了。
再看try_to_wake_up()：
[kernel/sched.c --> try_to_wake_up()]
1398 static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
1399 {
......
1417
1418 cpu = task_cpu(p);
1419 this_cpu = smp_processor_id();
1420
1421 #ifdef CONFIG_SMP
1422 if (unlikely(task_running(rq, p)))
1423 goto out_activate;
1424
1425 new_cpu = cpu;
1426
1427 schedstat_inc(rq, ttwu_cnt);
1428 if (cpu == this_cpu) {
1429 schedstat_inc(rq, ttwu_local);
1430 goto out_set_cpu;
1431 }
變量this_cpu和變量cpu有什么區(qū)別?變量this_cpu是實(shí)際運(yùn)行這個(gè)函數(shù)的處理器(“目標(biāo)處理器”)，而變量cpu是進(jìn)程p在睡眠之前運(yùn)行的處理器??為了方便我們暫且稱之為“源處理器”。當(dāng)然，這兩個(gè)處理器也可能是同一個(gè)，比如進(jìn)程p在處理器A上運(yùn)行，然后睡眠，而運(yùn)行try_to_wake_up的也是處理器A，其實(shí)這樣就最好了，進(jìn)程p在處理器A里cache的數(shù)據(jù)都不用動(dòng)，直接讓A運(yùn)行p就行了??這就是1428行的邏輯。
如果this_cpu和cpu不是同一個(gè)處理器，那么代碼繼續(xù)：
1447 if (this_sd) {
1448 int idx = this_sd->wake_idx;
1449 unsigned int imbalance;
1450
1451 imbalance = 100 + (this_sd->imbalance_pct - 100) / 2;
1452
1453 load = source_load(cpu, idx);
1454 this_load = target_load(this_cpu, idx);
1455
1456 new_cpu = this_cpu; /* Wake to this CPU if we can */
1457
1458 if (this_sd->flags & SD_WAKE_AFFINE) {
1459 unsigned long tl = this_load;
1460 unsigned long tl_per_task;
1461
1462 tl_per_task = cpu_avg_load_per_task(this_cpu);
1463
1464 /*
1465 * If sync wakeup then subtract the (maximum possible)
1466 * effect of the currently running task from the load
1467 * of the current CPU:
1468 */
1469 if (sync)
1470 tl -= current->load_weight;
1471
1472 if ((tl <= load &&
1473 tl + target_load(cpu, idx) <= tl_per_task) ||
1474 100*(tl + p->load_weight) <= imbalance*load) {
1475 /*
1476 * This domain has SD_WAKE_AFFINE and
1477 * p is cache cold in this domain, and
1478 * there is no bad imbalance.
1479 */
1480 schedstat_inc(this_sd, ttwu_move_affine);
1481 goto out_set_cpu;
1482 }
1483 }
計(jì)算出“目標(biāo)處理器”和“源處理器”各自的負(fù)載( 1453行和1454行)，再計(jì)算“目標(biāo)處理器”上的每任務(wù)平均負(fù)載 tl_per_task，最后進(jìn)行判斷：如果“目標(biāo)處理器”的負(fù)載小于“源處理器”的負(fù)載且兩處理器負(fù)載相加都比 tl_per_task小的話，喚醒的進(jìn)程轉(zhuǎn)為“目標(biāo)處理器”執(zhí)行。還有一種情況就是1474行的判斷，如果“目標(biāo)處理器”的負(fù)載加上被喚醒的進(jìn)程的負(fù)載后，還比“源處理器”的負(fù)載(乘以imbalance后)的小的話，也要把喚醒的進(jìn)程轉(zhuǎn)為“目標(biāo)處理器”執(zhí)行。如果兩個(gè)因素都不滿足，那還是由p進(jìn)程原來呆的那個(gè)CPU(即”源處理器“)繼續(xù)來處理吧。
有點(diǎn)兒繞，是吧?其實(shí)代碼雖繞，用意是簡單的：
1472行-1473行其實(shí)是這樣一個(gè)用意：如果“目標(biāo)處理器”的負(fù)載很小，小得即使把壓力全給到“源處理器”上去也不會(huì)超過“源處理器”上的平均任務(wù)負(fù)載，那么這“目標(biāo)處理器”的負(fù)載是真的很小，值得把p進(jìn)程挪過來。
1474行的用意則是：如果我們真的把p進(jìn)程挪到“目標(biāo)處理器”以后，“目標(biāo)處理器”的壓力也不比“源處理器”大多少，所以，還是值得一挪。
說來說去，還是那個(gè)笨原則：把任務(wù)從最忙的CPU那兒轉(zhuǎn)到很閑的CPU這兒。
我們已經(jīng)看過了睡眠和醒來時(shí)的內(nèi)核函數(shù)，那么軟中斷里的 run_rebalance_domains又干了些什么呢?其實(shí)也很簡單，它調(diào)用了load_balance函數(shù)，而這個(gè)函數(shù)和load_balance_newidle實(shí)現(xiàn)上基本一樣，就不累述了。
看了linux在多核處理器上的負(fù)載均衡原理文章內(nèi)容的人還看：
5.CPU怎么查看