負(fù)載均衡
? ? ? ? 我們先前提到過(guò)遣总，schedule()和運(yùn)行隊(duì)列等等都是針對(duì)于單個(gè)處理器而言的睬罗。那么，是否存在某種機(jī)制來(lái)解決多處理器系統(tǒng)中負(fù)載不均的狀況呢旭斥？想象某個(gè)擁有五個(gè)處理器的系統(tǒng)容达，Acpu上處理5個(gè)進(jìn)程，而B(niǎo)cpu僅僅處理1個(gè)垂券，毋庸置疑地浪費(fèi)了Bcpu中大量的計(jì)算資源花盐，卻又使得Acpu苦不堪言，導(dǎo)致整個(gè)系統(tǒng)的性能下降菇爪。所以?xún)?nèi)核提供了負(fù)載均衡器(load balancer)解決該難題算芯。在<kernel/sched.c>中能看到相關(guān)代碼。
? ? ? ? 負(fù)載均衡器的核心函數(shù)是load_balance()凳宙，該函數(shù)可以通過(guò)兩種渠道被調(diào)用熙揍。一種是在schedule()中，當(dāng)schedule()檢測(cè)到當(dāng)前CPU運(yùn)行隊(duì)列中的進(jìn)程數(shù)為零時(shí)氏涩，負(fù)載均衡函數(shù)被調(diào)用诈嘿。還有一種是因?yàn)槎〞r(shí)器而被調(diào)用——比如每過(guò)一毫秒且CPU相對(duì)空閑的時(shí)候堪旧，以及類(lèi)似的時(shí)候。在load_balance()運(yùn)行時(shí)奖亚，將會(huì)給當(dāng)前運(yùn)行隊(duì)列上鎖淳梦，以及確保中斷禁用，防止并發(fā)地訪(fǎng)問(wèn)運(yùn)行隊(duì)列昔字。
? ? ? ? 兩種方式的調(diào)用結(jié)果存在差異爆袍。schedule()的調(diào)用里，工作十分簡(jiǎn)單——因?yàn)楫?dāng)前隊(duì)列是空的作郭。所以我們只需要尋找到某個(gè)不為空的核陨囊，將其進(jìn)程拉過(guò)來(lái)即可。在定時(shí)器的調(diào)用里夹攒，我們需要解決任何運(yùn)行隊(duì)列中的不平衡蜘醋。
? ? ? ? 接下來(lái)是load_balance()的執(zhí)行步驟。
? ? ? ? 1.調(diào)用find_busiest_queue()尋找最繁忙的運(yùn)行隊(duì)列咏尝。如果最繁忙的隊(duì)列中進(jìn)程的數(shù)目至少比當(dāng)前運(yùn)行隊(duì)列中多25%压语，則程序繼續(xù)，否則返回编检。
? ? ? ? 2.尋找其試圖遷移的優(yōu)先隊(duì)列胎食，一般來(lái)說(shuō)推薦過(guò)氣隊(duì)列，因?yàn)檫^(guò)氣隊(duì)列中的進(jìn)程已經(jīng)有一段時(shí)間沒(méi)有運(yùn)行了允懂，也更有可能不在當(dāng)前CPU的CACHE中厕怜。如果過(guò)氣隊(duì)列為空，那么搜尋活動(dòng)隊(duì)列蕾总。
? ? ? ? 3.搜尋選定隊(duì)列中的最高優(yōu)先級(jí)進(jìn)程的列表粥航。這些進(jìn)程更重要因此更迫切地需要運(yùn)行。當(dāng)然之間有一些小插曲生百，詳細(xì)看下面的代碼:
? ? ? ? 在這里稍微提一下已經(jīng)多次出現(xiàn)的list_entry()函數(shù)躁锡，這實(shí)際上是一個(gè)雙向鏈表相關(guān)的函數(shù)。在Linux內(nèi)核中置侍，提供了一個(gè)用來(lái)創(chuàng)建雙向循環(huán)鏈表的結(jié)構(gòu) list_head映之。雖然Linux內(nèi)核是用C語(yǔ)言寫(xiě)的，但是list_head的引入蜡坊，使得內(nèi)核數(shù)據(jù)結(jié)構(gòu)也可以擁有面向?qū)ο蟮奶匦愿苁洌ㄟ^(guò)使用操作list_head 的通用接口很容易實(shí)現(xiàn)代碼的重用，有點(diǎn)類(lèi)似于C++的繼承機(jī)制秕衙。詳情見(jiàn)Linux 內(nèi)核list_head 學(xué)習(xí)（一）蠢甲。
? ? ? ? 4.每個(gè)給定優(yōu)先級(jí)列表中的任務(wù)都被分析，以此來(lái)尋找適當(dāng)?shù)娜蝿?wù)進(jìn)行遷移据忘○信＃“適當(dāng)”指的（1）是不在當(dāng)前CPU的CACHE中搞糕。（2）不被禁止遷移。（3）不是當(dāng)前運(yùn)行的任務(wù)曼追。這一步驟通過(guò)調(diào)用can_migrate_task()來(lái)實(shí)現(xiàn):
? ? ? ? 5.如果不平衡情況依舊存在窍仰，則跳轉(zhuǎn)繼續(xù)處理。否則退出函數(shù)礼殊。
進(jìn)程搶占和上下文切換
? ? ? ? 上下文切換是指從當(dāng)前運(yùn)行進(jìn)程切換到其他可執(zhí)行進(jìn)程驹吮。通過(guò)定義在<kernel/sched.c>的context_switch()來(lái)實(shí)現(xiàn)。當(dāng)某個(gè)新的進(jìn)程被選擇而即將被運(yùn)行時(shí)晶伦，該函數(shù)被schedule()調(diào)用碟狞。該函數(shù)執(zhí)行了以下兩個(gè)基本工作:
? ? ? ? 1.調(diào)用<asm/mmu_context.h>中定義的switch_mm()函數(shù)，切換虛擬內(nèi)存映射婚陪。
? ? ? ? 2.調(diào)用<asm/system.h>定義的switch_to()函數(shù)族沃。保存當(dāng)前進(jìn)程的上下文，并進(jìn)行上下文切換泌参。
? ? ? ? 進(jìn)程上下文脆淹，就是進(jìn)程執(zhí)行時(shí)的環(huán)境。具體來(lái)說(shuō)就是各個(gè)變量和數(shù)據(jù)及舍，包括所有的寄存器變量未辆、進(jìn)程打開(kāi)的文件窟绷、內(nèi)存信息等锯玛。
? ? ? ? （1）用戶(hù)級(jí)上下文: 正文、數(shù)據(jù)兼蜈、用戶(hù)堆棧以及共享存儲(chǔ)區(qū)攘残；
? ? ? ? （2）寄存器上下文: 通用寄存器、程序寄存器(IP)为狸、處理器狀態(tài)寄存器(EFLAGS)歼郭、棧指針(ESP)；
? ? ? ? （3）系統(tǒng)級(jí)上下文: 進(jìn)程控制塊task_struct辐棒、內(nèi)存管理信息(mm_struct病曾、vm_area_struct、pgd漾根、pte)泰涂、內(nèi)核棧。
? ? ? 當(dāng)發(fā)生進(jìn)程調(diào)度時(shí)辐怕，進(jìn)行進(jìn)程切換就是上下文切換(context switch).操作系統(tǒng)必須對(duì)上面提到的全部信息進(jìn)行切換逼蒙，新調(diào)度的進(jìn)程才能運(yùn)行。而系統(tǒng)調(diào)用進(jìn)行的模式切換(mode switch)寄疏。模式切換與進(jìn)程切換比較起來(lái)是牢，容易很多僵井，而且節(jié)省時(shí)間，因?yàn)槟Ｊ角袚Q最主要的任務(wù)只是切換進(jìn)程寄存器上下文的切換驳棱。詳情查看用戶(hù)空間與內(nèi)核空間批什，進(jìn)程上下文與中斷上下文[總結(jié)]一文。
? ? ? ? 回歸主題蹈胡，那么對(duì)于內(nèi)核來(lái)說(shuō)渊季。內(nèi)核必須知道什么時(shí)候該執(zhí)行schedule()。如果只在代碼顯示地調(diào)用時(shí)調(diào)用罚渐，那么用戶(hù)空間的程序就會(huì)無(wú)休無(wú)止地運(yùn)行下去却汉。所以，內(nèi)核提供了nead_resched(該標(biāo)志似乎存儲(chǔ)在thread_info結(jié)構(gòu)的flags里,其對(duì)應(yīng)與flags取值為TIF_NEED_RESCHED)標(biāo)志來(lái)表示是否需要執(zhí)行調(diào)度荷并。如果要設(shè)定這個(gè)標(biāo)志合砂，就要調(diào)用scheduler_tick()，而調(diào)用只會(huì)發(fā)生在（1）當(dāng)一個(gè)進(jìn)程耗盡其時(shí)間片源织。（2）在try_to_wake_up()函數(shù)里——當(dāng)一個(gè)比當(dāng)前進(jìn)程優(yōu)先級(jí)更高的任務(wù)被喚醒時(shí)翩伪。
? ? ? ? 以下介紹三個(gè)用于nead_resched的函數(shù):
? ? ? ? 1.set_tsk_need_resched()
? ? ? ? 2.clear_tsk_need_resched()
? ? ? ? 3.need_resched()
? ? ? ? 除上述，當(dāng)從用戶(hù)空間返回谈息，或者是從中斷函數(shù)中返回的時(shí)候缘屹，nead_resched就會(huì)被檢查。該標(biāo)志存儲(chǔ)在每個(gè)進(jìn)程的thread_info結(jié)構(gòu)中的flags成員里侠仇。如果flags的值為TIF_NEED_RESCHED時(shí)轻姿，就等價(jià)于nead_resched被置位。
?
用戶(hù)搶占
? ? ? ? 用戶(hù)級(jí)的進(jìn)程搶占發(fā)生在內(nèi)核將要返回用戶(hù)空間時(shí)逻炊，并且nead_resched被設(shè)置時(shí)互亮。? ?
? ? ? ? 總而言之，用戶(hù)級(jí)進(jìn)程搶占可能發(fā)生在：
? ? ? ? ? ? 1.從系統(tǒng)調(diào)用返回用戶(hù)空間時(shí)余素。
? ? ? ? ? ? 2.從中斷處理函數(shù)返回用戶(hù)空間時(shí)豹休。
內(nèi)核搶占
? ? ? ? Linux和其他大多數(shù)的Unix系統(tǒng)以及其他派別的系統(tǒng)不同，Linux是一個(gè)完全可搶占的(先發(fā)制人的)操作系統(tǒng)桨吊。在不是完全可搶占的系統(tǒng)中威根，內(nèi)核代碼會(huì)持續(xù)執(zhí)行直到全部完成。也就是說(shuō)视乐，調(diào)度進(jìn)程沒(méi)有能力去打斷一個(gè)正在內(nèi)核中運(yùn)行的任務(wù)洛搀。內(nèi)核進(jìn)程是合作地進(jìn)行(平均分配時(shí)間？)炊林，而不是引入搶占機(jī)制的姥卢。內(nèi)核代碼會(huì)運(yùn)行直到它完成并返回到用戶(hù)空間，或者是顯式地阻塞。但是独榴，我們的Linux系統(tǒng)是完全可搶占的：一個(gè)進(jìn)程可能在任何時(shí)間點(diǎn)被搶占僧叉，只要任務(wù)處在安全的可切換的狀態(tài)。
? ? ? ? 什么時(shí)候適合重新安排呢棺榔？當(dāng)內(nèi)核任務(wù)不占用“鎖”時(shí)瓶堕，內(nèi)核就具備搶占其的能力。也就是說(shuō)症歇，如果一個(gè)內(nèi)核進(jìn)程不擁有鎖郎笆，那么該進(jìn)程就是可重入的，并且是可被搶占的忘晤。
? ? ? ? 與用戶(hù)級(jí)搶占不同宛蚓，內(nèi)核級(jí)別的搶占引入了新的標(biāo)志，就是thread_info結(jié)構(gòu)中的preempt_count成員设塔。其初始值為0凄吏，當(dāng)進(jìn)程每每獲得鎖時(shí)就增加1，每每釋放鎖時(shí)就減1闰蛔。所以當(dāng)該值為0時(shí)痕钢，內(nèi)核是可搶占的。下面討論從中斷里返回的情況:如果返回的是內(nèi)核空間序六，內(nèi)核會(huì)檢查當(dāng)前的進(jìn)程的preempt_count和nead_resched的值任连。如果都滿(mǎn)足需求——這意味著某任務(wù)繼續(xù)調(diào)度，并且當(dāng)前進(jìn)程處在安全(可以重新調(diào)度)的狀態(tài)例诀，就會(huì)調(diào)用schedule()随抠。如果不滿(mǎn)足上述條件。中斷程序結(jié)束后余佃，將會(huì)常規(guī)地返回被中斷處繼續(xù)執(zhí)行暮刃。當(dāng)前內(nèi)核進(jìn)程釋放完所有鎖時(shí)跨算，也會(huì)檢查nead_resched是否被設(shè)置爆土。
? ? ? ? 總而言之，內(nèi)核級(jí)搶占可能發(fā)生在：
? ? ? ? 1.當(dāng)中斷進(jìn)程返回到內(nèi)核空間時(shí)诸蚕。
? ? ? ? 2.當(dāng)內(nèi)核程序再次變得可搶占時(shí)步势。
? ? ? ? 3.內(nèi)核態(tài)運(yùn)行的任務(wù)顯示調(diào)用schedule()時(shí)。
? ? ? ? 4.內(nèi)核態(tài)進(jìn)程阻塞時(shí)背犯。（是任務(wù)代碼的自我實(shí)現(xiàn)嗎坏瘩？還是某種機(jī)制檢測(cè)到該任務(wù)阻塞后啟動(dòng)調(diào)度進(jìn)程？）
實(shí)時(shí)
? ? ? ? Linux提供了兩種實(shí)時(shí)調(diào)度算法SCHED_FIFO和SCHED_RR漠魏。前者就是簡(jiǎn)單地先到先執(zhí)行原則倔矾，在該調(diào)度算法中不存在時(shí)間片的說(shuō)法，當(dāng)這樣的任務(wù)變?yōu)榭蛇\(yùn)行狀態(tài)，會(huì)一直運(yùn)行直到它阻塞或者是顯式地放棄cpu哪自。并且用SCHED_FIFO的進(jìn)程總比SCHED_NORMAL的優(yōu)先調(diào)度丰包。采用SCHED_FIFO算法的進(jìn)程只能被同為SCHED_FIFO的或者是SCHED_RR的進(jìn)程搶占。兩個(gè)以上的具有相同優(yōu)先級(jí)的FIFO類(lèi)進(jìn)程才用輪流執(zhí)行的方式壤巷。如果一個(gè)SCHED_FIFO的進(jìn)程執(zhí)行邑彪，那么所有優(yōu)先級(jí)低于它的進(jìn)程無(wú)法翻身，直到該進(jìn)程結(jié)束胧华。
? ? ? SCHED_RR與SCHED_FIFO的區(qū)別在于寄症，使用該算法的進(jìn)程擁有時(shí)間片。進(jìn)程們只能在耗盡自己預(yù)定義的時(shí)間片前運(yùn)行矩动。同一優(yōu)先級(jí)的進(jìn)程輪流執(zhí)行有巧。因此在SCHED_RR中時(shí)間片僅對(duì)相同優(yōu)先級(jí)的進(jìn)程有意義。一個(gè)較低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)不可能搶占一個(gè)SCHED_RR的進(jìn)程悲没，盡管這個(gè)進(jìn)程耗盡了自己的時(shí)間片（但未結(jié)束）剪决。
? ? ? ? SCHED_NORMAL就是我們先前討論的一般進(jìn)程調(diào)度方法。
? ? ? ? 我們用實(shí)時(shí)優(yōu)先級(jí)表示實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)檀训。正如先前提到柑潦，其值為[0，99（MAX_RT_PRIO－1）]峻凫。而我們知道常規(guī)的進(jìn)程優(yōu)先級(jí)是[-20渗鬼，19]。后來(lái)為了體系里表示的簡(jiǎn)單荧琼，我們將Nice的值映射到了[MAX_RT_PRIO譬胎，MAX_RT_PRIO＋40]。
