多處理器下的硬實(shí)時(shí)操作系統(tǒng)研究

實(shí)現(xiàn)遷移

當(dāng)非RT0任務(wù)調(diào)用了函數(shù)artis_request_for_migration()時(shí)，它不能直接把自己插入到其他處理器的運(yùn)行隊(duì)列當(dāng)中，因?yàn)檫@樣就會(huì)造成多處理器在同一時(shí)間運(yùn)行同一任務(wù)的情況，所以在ARTiS系統(tǒng)中，是通過(guò)與當(dāng)前處理器上的下一個(gè)任務(wù)來(lái)插入遷移任務(wù)的，總的來(lái)說(shuō)可以分為三步：首先，遷移進(jìn)程會(huì)調(diào)用artis_request_for_migration()，設(shè)置遷移標(biāo)志，并將自身的親和CPU設(shè)置為本地CPU，然后使自身再次進(jìn)入可搶占狀態(tài)，調(diào)用調(diào)度函數(shù)。然后，新調(diào)度的任務(wù)將執(zhí)行函數(shù)artis_complete_megration()，該函數(shù)將調(diào)用函數(shù) finish_task_swith()完成調(diào)度，選擇一個(gè)非實(shí)時(shí)處理器把遷移任務(wù)插入到其上的RT-FIFO隊(duì)列，并通過(guò)產(chǎn)生一個(gè)進(jìn)程間的中斷信號(hào)來(lái)強(qiáng)制目標(biāo)處理器產(chǎn)生一輪新的調(diào)度。最后，目標(biāo)處理器上的調(diào)度程序?qū)⑼ㄟ^(guò)調(diào)用函數(shù)artis_fetch_migration()從RT-FIFOs隊(duì)列中取出遷移任務(wù)。

2.2 負(fù)載平衡機(jī)制

在ARTiS系統(tǒng)中，當(dāng)涉及對(duì)稱處理器之間的負(fù)載平衡時(shí)，直接沿用原有的負(fù)載平衡機(jī)制。而對(duì)于不對(duì)稱處理器上的負(fù)載平衡，則通過(guò)修改原linux的負(fù)載平衡機(jī)制來(lái)實(shí)現(xiàn)。由于非實(shí)時(shí)任務(wù)從實(shí)時(shí)處理器到非實(shí)時(shí)處理器的遷移是強(qiáng)制的。所以不存在負(fù)載平衡的問(wèn)題，所以這里只考慮如何將非實(shí)時(shí)處理器上的非實(shí)時(shí)任務(wù)遷移至實(shí)時(shí)處理器。可以從兩個(gè)方面進(jìn)行分析：一個(gè)是確定遷移的目標(biāo)處理器，一個(gè)是確定要遷移的任務(wù)。

確定遷移的目標(biāo)處理器

CPU的負(fù)載指的就是該CPU運(yùn)行隊(duì)列的長(zhǎng)度（在該CPU上等待運(yùn)行的程序個(gè)數(shù)），Pairing policy首先計(jì)算各個(gè)CPU運(yùn)行隊(duì)列的長(zhǎng)度，然后把負(fù)載最重的CPU上的任務(wù)分配到負(fù)載較輕的CPU上。當(dāng)各個(gè)CPU處理的都是非實(shí)時(shí)的任務(wù)時(shí)，該策略則運(yùn)作的很好，因?yàn)榉菍?shí)時(shí)的任務(wù)將平分CPU的時(shí)間，但是在有實(shí)時(shí)任務(wù)的情況下，由于實(shí)時(shí)任務(wù)具有絕對(duì)的優(yōu)先級(jí)，它將獨(dú)占CPU，所以不能再簡(jiǎn)單的只用運(yùn)行隊(duì)列的長(zhǎng)度來(lái)衡量負(fù)載的大小。

在ARTiS系統(tǒng)中，在原有的策略上，添加了一個(gè)由實(shí)時(shí)任務(wù)的運(yùn)行時(shí)間構(gòu)成的負(fù)載參數(shù)，這時(shí)將通過(guò)公式L× 1/1?RT (L表示某個(gè)CPU上非實(shí)時(shí)任務(wù)的個(gè)數(shù)，RT表示實(shí)時(shí)任務(wù)需要占用CPU的時(shí)間)計(jì)算各個(gè)處理器上的負(fù)載。例如：假設(shè)在雙CPU的情況下有6個(gè)任務(wù)（包括實(shí)時(shí)任務(wù)），實(shí)時(shí)任務(wù)需占用CPU時(shí)間的3/4的，對(duì)于通常的分派策略，一個(gè)處理器分三個(gè)任務(wù)，那么在一個(gè)處理器上，每個(gè)非實(shí)時(shí)任務(wù)將占用1/3的CPU 時(shí)間，而在另一個(gè)處理器上，非實(shí)時(shí)任務(wù)占用的時(shí)間只有1/8，顯然分配很不均等。在ARTiS中，它首先會(huì)統(tǒng)計(jì)每個(gè)處理器上的非實(shí)時(shí)任務(wù)的個(gè)數(shù)，并利用公式L× 1/1?RT計(jì)算出每個(gè)處理器的負(fù)載，然后選擇負(fù)載較輕的處理器作為目標(biāo)處理器，這時(shí)每個(gè)非實(shí)時(shí)任務(wù)將都會(huì)占有1/4的處理器時(shí)間，達(dá)到了負(fù)載均衡的目的。參照下圖：

確定遷移的任務(wù)

當(dāng)確定了遷移的處理器之后，接下來(lái)要確定的就是要遷移的任務(wù)。選擇的標(biāo)準(zhǔn)就是盡量選擇那些可以在實(shí)時(shí)處理器上可以較長(zhǎng)保持可搶占狀態(tài)的非RT0任務(wù)，如果一個(gè)非RT0任務(wù)遷移的頻率過(guò)高，那么就會(huì)造成非RT0任務(wù)在實(shí)時(shí)處理器與非實(shí)時(shí)處理器之間推來(lái)推去，即所謂的乒乓效應(yīng)。這樣不僅沒(méi)有達(dá)到負(fù)載平衡的目標(biāo)，反而降低了改任務(wù)執(zhí)行的效率。

為了避免乒乓效應(yīng)，ARTiS采用統(tǒng)計(jì)的方式來(lái)預(yù)估一個(gè)任務(wù)可能的遷移頻率（在任務(wù)屬性中添加兩個(gè)變量，分別用來(lái)保存遷移請(qǐng)求的時(shí)間間隔平均值和上一次遷移發(fā)生的時(shí)間），并通過(guò)該預(yù)估的頻率與當(dāng)前遷移任務(wù)發(fā)生的時(shí)機(jī)相比較，由此來(lái)決定當(dāng)前的任務(wù)是否可以遷移。對(duì)于一個(gè)請(qǐng)求遷移的任務(wù)，由于它的請(qǐng)求點(diǎn)有可能發(fā)生在預(yù)估請(qǐng)求之前，也有可能發(fā)生在預(yù)估請(qǐng)求之后，所以分兩種情況：當(dāng)請(qǐng)求點(diǎn)發(fā)生在預(yù)估點(diǎn)之前時(shí)（如圖2中的第五個(gè)遷移點(diǎn)所示），如果它離預(yù)估的遷移點(diǎn)很近，那么說(shuō)明它馬上又要遷移了，所以應(yīng)當(dāng)被阻止，而如果離預(yù)估點(diǎn)較遠(yuǎn)的話（如圖2中的第4個(gè)遷移點(diǎn)）。同樣對(duì)于請(qǐng)求點(diǎn)發(fā)生在預(yù)估點(diǎn)之后的遷移請(qǐng)求，如果離預(yù)估點(diǎn)很近的話（如圖2中的第一個(gè)遷移點(diǎn)），那么認(rèn)為它剛剛發(fā)生過(guò)遷移，所以不允許短時(shí)間內(nèi)再次遷移，所以也會(huì)被阻止，而與之較遠(yuǎn)的（3）、（4）遷移點(diǎn)則可進(jìn)行遷移。由此可見(jiàn)，在設(shè)計(jì)的同時(shí)設(shè)定的偏差范圍將直接影響ARTiS的性能，所以應(yīng)當(dāng)通過(guò)多次的試驗(yàn)來(lái)選取一個(gè)合適的偏差。