linux在多核處理器上的負載均衡原理
linux在多核處理器上的負載均衡原理
CPU作為電腦的核心組成部份，它的好壞直接影響到電腦的性能。下面是學習啦小編帶來的關于linux在多核處理器上的負載均衡原理的內容，歡迎閱讀!
linux在多核處理器上的負載均衡原理：
現在互聯網公司使用的都是多CPU(多核)的服務器了，Linux操作系統會自動把任務分配到不同的處理器上，并盡可能的保持負載均衡。那Linux內核是怎么做到讓各個CPU的壓力均勻的呢?
做一個負載均衡機制，重點在于：
1. 何時檢查并調整負載情況?
2. 如何調整負載?
先看第一個問題。
如果讓我這樣的庸俗程序員來設計，我第一個想到的就是每隔一段時間檢查一次負載是否均衡，不均則調整之，這肯定不是最高效的辦法，但肯定是實現上最簡單的。實際上，2.6.20版linux kernel的確使用軟中斷來定時調整多CPU上的壓力(調用函數run_rebalance_domains)，每秒1次。
但每秒一次還是不能滿足要求，對很多應用來說，1秒太長了，一秒鐘內如果發生負載失衡對很多web應用都是不能接受的，何況其他實時應用。最好kernel能夠緊跟進程的變化來調整。
那么，好，我們在進程創建和進程exit的時候檢查并調整負載呢?可以，但是不完整，一個進程創建以后如果頻繁的睡眠、醒來、睡眠、醒來，它這樣折騰對CPU的負載是有影響的，你就不管它了嗎?說到底，我們其實關注的是進程是否在使用CPU，而不是它是否誕生了。所以，我們應該在進程睡眠和醒來這兩個時間點檢查CPU們的負載。
再看第二個問題，怎么調整負載呢?從最繁忙的那個CPU上挪一個進程到最閑的那個CPU上，如果負載還不均衡，就再挪一個進程，如果還不均衡，繼續挪....這也是個最笨的方法，但它卻真的是linux CPU負載均衡的核心，不過實際的算法在此基礎上有很多細化。對于Intel的CPU，壓縮在同一個chip上的多核是共享同一個L2的(如下圖，里面的一個Processor其實就是一個chip)，如果任務能盡可能的分配在同一個chip上，L2 cache就可以繼續使用，這對運行速度是有幫助的。所以除非“很不均衡”，否則盡量不要把一個chip上的任務挪到其他chip上。
于是，為了應對這種CPU core之間的異質性——在不同的core之間遷移任務，代價不同——Linux kernel引入了sched_domain和sched_group的概念。sched_domain和sched_group的具體原理，可參考劉勃的文章和英文資料。
【代碼剖析】
SMP負載均衡檢查或調整在兩個內核函數里發生：
1. schedule()。當進程調用了sleep、usleep、poll、epoll、pause時，也就是調用了可能睡去的操作時都會轉為內核代碼里對schedule()函數的調用。
2. try_to_wake_up() 。說白了就是進程剛才睡了，現在要醒來，那醒來以后跑在哪個CPU上呢?這個選擇CPU的過程，也就是負載均衡的過程。
我們先看schedule()的代碼，我們忽略函數前面那些和負載均衡無關的代碼(本文代碼以內核2.6.20版為準)：
[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 }
每個CPU都有一個運行隊列即這里的 rq，運行隊列里放著該CPU要運行的進程，如果運行隊列里沒有進程了，就說明當前CPU沒有可調度的任務了，那就要調用idle_balance從其它CPU上“平衡”一些(就是挪一些)進程到當前rq里。
再看 idle_balance()的實現：
[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對應的domain(2816行)，并調用load_balance_newidle，我們繼續：
[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);
原來就是我們上面說的“笨辦法”，針對當前CPU所屬的每個domain(從子到父)，找到該 sched_domain里最忙的sched_group(2752行)，再從該group里找出最忙的運行隊列(2759行)，最后從該“最忙”運行隊列里挑出幾個進程到當前CPU的運行隊列里。move_tasks函數到底挪多少進程到當前CPU是由第4和第5個參數決定的，第4個參數是指最多挪多少個進程，第5個參數是指最多挪多少“壓力”。有了這兩個參數限制，就不會挪過頭了(即把太多進程挪到當前CPU，造成新的不均衡)。
舉個例子，假如有一臺8核的機器，兩個CPU插槽，也就是兩個chip，每個chip上4個核，再假設現在core 4最忙，core 0第二忙，如圖：
按照 劉勃的文章里的提法，首先是core domain，即Processor 0屬于domain 1，Processor 1屬于domain 2，其中domain 1包含4個sched_group，每個group對應一個core，如下圖(group未畫出)：
假如現在是 Core 3 在執行idle_balance，則先在domain 1里找最忙的group，找到第二忙的group是core 0(core 4不在domain 1里，所以不會找到它)，再從core 0里找最忙的runqueue(運行隊列)，core 0就一個運行隊列，所以直接就是它對應的runqueue了，然后從該runqueue里挪出幾個任務到Core 3，這一層domain的均衡做完了。
接著是domain 1的父domain，即 cpu_domain，下圖的domain 0：
這個domain 0包含了兩個group，每個group對應一個chip，即每個group對應了4個core。
在domain 0找最繁忙的group，顯然會找到Processor1 對應的group(因為core 4超忙)，那么繼續在Processor 1里找最忙的runqueue，于是找到core 4，最后從core 4的runqueue里挑出幾個任務挪到core 3,。
這樣，整個系統8個核都基本平衡了。
也許有人要問，為什么是從子domain到父domain這樣遍歷，而不是倒過來，從父到子遍歷呢?這是因為子domain通常都是在一個chip上，任務的很多數據在共享的L2 cache上，為了不讓其失效，有必要盡量讓任務保持在一個chip上。
也許還有人要問：如果core 3本來就是最忙的core，它如果運行idle_balance，會發生什么?答案是什么也不會發生。因為在find_busiest_group函數里，如果發現最忙的是“本CPU”，那么就直接返回NULL，也就不再做任何事。
那core 3豈不永遠是最忙的了?呵呵，大家忘了，系統里總有閑的CPU(哪怕是相對比較閑)，它總會執行schedule()，就算它從不調用sleep從不睡眠，時鐘中斷也會迫使其進程切換，進而調用schedule，進而將繁忙CPU的任務攬一部分到自己身上。這樣，誰最閑，誰早晚會從忙人身上攬活兒過來，所以忙人不會永遠最忙，閑人也不會永遠最閑，所以就平等，就均衡了。
再看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有什么區別?變量this_cpu是實際運行這個函數的處理器(“目標處理器”)，而變量cpu是進程p在睡眠之前運行的處理器??為了方便我們暫且稱之為“源處理器”。當然，這兩個處理器也可能是同一個，比如進程p在處理器A上運行，然后睡眠，而運行try_to_wake_up的也是處理器A，其實這樣就最好了，進程p在處理器A里cache的數據都不用動，直接讓A運行p就行了??這就是1428行的邏輯。
如果this_cpu和cpu不是同一個處理器，那么代碼繼續：
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 }
計算出“目標處理器”和“源處理器”各自的負載( 1453行和1454行)，再計算“目標處理器”上的每任務平均負載 tl_per_task，最后進行判斷：如果“目標處理器”的負載小于“源處理器”的負載且兩處理器負載相加都比 tl_per_task小的話，喚醒的進程轉為“目標處理器”執行。還有一種情況就是1474行的判斷，如果“目標處理器”的負載加上被喚醒的進程的負載后，還比“源處理器”的負載(乘以imbalance后)的小的話，也要把喚醒的進程轉為“目標處理器”執行。如果兩個因素都不滿足，那還是由p進程原來呆的那個CPU(即”源處理器“)繼續來處理吧。
有點兒繞，是吧?其實代碼雖繞，用意是簡單的：
1472行-1473行其實是這樣一個用意：如果“目標處理器”的負載很小，小得即使把壓力全給到“源處理器”上去也不會超過“源處理器”上的平均任務負載，那么這“目標處理器”的負載是真的很小，值得把p進程挪過來。
1474行的用意則是：如果我們真的把p進程挪到“目標處理器”以后，“目標處理器”的壓力也不比“源處理器”大多少，所以，還是值得一挪。
說來說去，還是那個笨原則：把任務從最忙的CPU那兒轉到很閑的CPU這兒。
我們已經看過了睡眠和醒來時的內核函數，那么軟中斷里的 run_rebalance_domains又干了些什么呢?其實也很簡單，它調用了load_balance函數，而這個函數和load_balance_newidle實現上基本一樣，就不累述了。
看了linux在多核處理器上的負載均衡原理文章內容的人還看：
5.CPU怎么查看