多處理器下的硬實時操作系統研究

實現遷移

當非RT0任務調用了函數artis_request_for_migration()時，它不能直接把自己插入到其他處理器的運行隊列當中，因為這樣就會造成多處理器在同一時間運行同一任務的情況，所以在ARTiS系統中，是通過與當前處理器上的下一個任務來插入遷移任務的，總的來說可以分為三步：首先，遷移進程會調用artis_request_for_migration()，設置遷移標志，并將自身的親和CPU設置為本地CPU，然后使自身再次進入可搶占狀態，調用調度函數。然后，新調度的任務將執行函數artis_complete_megration()，該函數將調用函數 finish_task_swith()完成調度，選擇一個非實時處理器把遷移任務插入到其上的RT-FIFO隊列，并通過產生一個進程間的中斷信號來強制目標處理器產生一輪新的調度。最后，目標處理器上的調度程序將通過調用函數artis_fetch_migration()從RT-FIFOs隊列中取出遷移任務。

2.2 負載平衡機制

在ARTiS系統中，當涉及對稱處理器之間的負載平衡時，直接沿用原有的負載平衡機制。而對于不對稱處理器上的負載平衡，則通過修改原linux的負載平衡機制來實現。由于非實時任務從實時處理器到非實時處理器的遷移是強制的。所以不存在負載平衡的問題，所以這里只考慮如何將非實時處理器上的非實時任務遷移至實時處理器。可以從兩個方面進行分析：一個是確定遷移的目標處理器，一個是確定要遷移的任務。

確定遷移的目標處理器

CPU的負載指的就是該CPU運行隊列的長度（在該CPU上等待運行的程序個數），Pairing policy首先計算各個CPU運行隊列的長度，然后把負載最重的CPU上的任務分配到負載較輕的CPU上。當各個CPU處理的都是非實時的任務時，該策略則運作的很好，因為非實時的任務將平分CPU的時間，但是在有實時任務的情況下，由于實時任務具有絕對的優先級，它將獨占CPU，所以不能再簡單的只用運行隊列的長度來衡量負載的大小。

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

確定遷移的任務

當確定了遷移的處理器之后，接下來要確定的就是要遷移的任務。選擇的標準就是盡量選擇那些可以在實時處理器上可以較長保持可搶占狀態的非RT0任務，如果一個非RT0任務遷移的頻率過高，那么就會造成非RT0任務在實時處理器與非實時處理器之間推來推去，即所謂的乒乓效應。這樣不僅沒有達到負載平衡的目標，反而降低了改任務執行的效率。

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