一種虛擬化操作系統(tǒng)基于事件驅動的實時調度方法※

黨茂昌

（中興通訊股份有限公司 上海研發(fā)中心 軟件平臺架構部，上海 201203）

黨茂昌（系統(tǒng)架構師），主要研究領域為嵌入式系統(tǒng)、操作系統(tǒng)、無線通信技術、虛擬化技術、圖形系統(tǒng)等，主要從事手機硬件／軟件系統(tǒng)架構設計、BSP開發(fā)等工作。

引 言

目前，虛擬化操作系統(tǒng)（hypervisor）廣泛應用于服務器、PC機等，這些應用領域對實時性要求較低。隨著一些嵌入式實時應用領域的發(fā)展，比如下一代手機對安全性、應用聚合和云計算等方面的需求，需要采用虛擬化操作系統(tǒng)。傳統(tǒng)的虛擬化操作系統(tǒng)很難滿足這些應用領域的實時性要求。經過大量的測試與分析，發(fā)現(xiàn)虛擬化操作系統(tǒng)實時性差的主要源頭之一是調度算法實時性不佳。有必要對虛擬化操作系統(tǒng)的調度方法進行實時性改造，使之可以應用于實時性要求較高的場合。本文提出了一種基于系統(tǒng)事件驅動和時間驅動相結合的實時調度方法，經實踐表明，該方法有效地解決了虛擬化操作系統(tǒng)在嵌入式系統(tǒng)應用中帶來的實時性問題。

1 問題提出

基于虛擬化操作系統(tǒng)（hypervisor），可以實現(xiàn)單CPU上多個操作系統(tǒng)（GuestOS）在相互隔離的內存域（Domain）中同時運行。如圖1所示，箭頭表示調度。其中的系統(tǒng)調度采用二級調度策略，虛擬化操作系統(tǒng)對GuestOS（Domain）進行第一級調度，GuestOS對自身的任務進行第二級調度，系統(tǒng)的實時性響應很難保證。

對于第一級調度（Domain調度），傳統(tǒng)的調度策略都是基于時間片的調度方法（SEDF、BVT、ARR、Credit等），通常應用于實時性要求較低的場合（網絡服務器等），對于實時性要求較高的場合（手機等），調度的實時性就很難滿足系統(tǒng)要求。具體表現(xiàn)為：CPU利用率低、中斷響應緩慢、GuestOS之間數(shù)據(jù)通信速率不足等。為了改進這些性能，必須設計一種新的滿足實時性應用場合的調度方法。根據(jù)實際測試和分析，發(fā)現(xiàn)實時性響應差的主要瓶頸在于GuestOS不能夠得到及時的調度。

本文的方法主要對第一級調度策略進行改造，即改造虛擬化操作系統(tǒng)對GuestOS（Domain）的調度方法。

圖1 虛擬化操作系統(tǒng)

2 解決方法

本文的方法采用系統(tǒng)實時事件驅動Domain調度器的策略。當系統(tǒng)中有需要實時響應的緊急或重要事件發(fā)生時，這些事件有機會驅動Domain調度器產生調度行為，使之（緊急或重要事件）得到快速處理。當沒有緊急或重要事件發(fā)生時，Domain調度器采用基于時間片（權重）的調度算法。

2.1 調度原則

圖2表示了調度原則。圖2中，系統(tǒng)硬件中斷、GuestOS事件發(fā)送、Guest Idle之類的緊急或重要事件發(fā)生時，有機會通過強原則去驅動Domain調度器，切換Domain使之得到快速處理。當系統(tǒng)中沒有緊急或重要事件發(fā)生時，Domain調度器通過弱原則進行調度（時間片等）。

圖2 調度原則

2.2 實時性分析

以中斷處理為例分析中斷響應時間，如圖3所示。從圖3中可以看到，原調度策略的中斷響應時間包含：“等待Domain調度時間片結束”＋ “Doamin切換”。新的調度策略，僅包含“Doamin切換”時間。可見，采用新的策略，中斷的實時性響應得到了提高。

圖3 中斷實時響應分析

虛擬操作系統(tǒng)應用中常會有以下3類事件的實時響應需要考慮：

0類事件——底層硬件中斷需要得到上層某個Domain的快速響應處理；

1類事件——Domain（GuestOS）之間的通信事件需要被另一個Doamin快速處理；

2類事件——Domain（GuetOS）中的任務空閑時，主動放棄CPU，通知Domain調度器使其他Domain（GuestOS）得到運行機會。

這些事件的實時性響應時間分析和中斷響應類似。

在本方法中，如圖4所示，上述的3類事件都以設置觸發(fā)事件的形式驅動Domain調度器，Domain調度器可以

根據(jù)這些事件組合、當前的GuestOS狀態(tài)組合、當前的Domain調度狀態(tài)來產生調度決策。

2.3 方法實施

2.3.1 事件定義

本方法具體實現(xiàn)時，根據(jù)實時系統(tǒng)的具體應用情況，首先定義出緊急／重要事件（需要引發(fā)調度才能滿足實時響應要求的事件），并按照2.2節(jié)所述的3類實時事件劃分，對其分類并設計優(yōu)先級排序。0類事件優(yōu)先級最高，1類事件優(yōu)先級居中，2類事件優(yōu)先級最低，每類事件自身也按照優(yōu)先級排序。

2.3.2 狀態(tài)定義

然后，根據(jù)系統(tǒng)設計和運行情況列出Domain狀態(tài)組合、GuestOS狀態(tài)組合，如表1、表2所列。最后，根據(jù)系統(tǒng)運行要求，設計出驅動事件調度查詢表，如表3所列。

表1給出了GuestOS運行狀態(tài)組合，表示每個guestOS中的任務運行情況。每個GuestOS可以處于Run或Idle兩個狀態(tài)，多個GuestOS的狀態(tài)組合起來（本文用2個GuestOS說明），就可以制作出GuestOS的狀態(tài)組合表。

表1 GuestOS狀態(tài)組合

圖4 基于事件驅動的實時調度方法

表2 Domain狀態(tài)組合

表2表示了Domain狀態(tài)組合。表示Domain調度器的調度情況，每個Domain可以處于Run或Ready兩個狀態(tài)，多個Domain的狀態(tài)組合起來（本文采用2個Domain），就可以制作出Doamin的狀態(tài)組合表。

表3 調度查詢表

表3是調度查詢表。調度觸發(fā)事件可以通過它查詢到下一個需要被調度運行的GuestOS。它是一個二維的數(shù)組，其中列的維度由調度觸發(fā)事件表示，優(yōu)先級從高向低排列，另一個行的維度由GuestOS狀態(tài)組合表示，包含表1的所有GuestOS狀態(tài)組合。通過這兩個維度的輸入，可以查詢到預期的需要被調度的GuestOS（Domain），作為調度器下一次調度決策的輸入。

2.3.3 事件置位與清除規(guī)則

2.2節(jié)圖4中表示了調度事件置位和清除規(guī)則，說明了3種類型的調度觸發(fā)事件是如何設置和清除的。

事件置位和清除規(guī)則時序如圖5所示。

圖5表示了3種類型的調度觸發(fā)事件的設置和清除時機，以及事件驅動策略和時間片驅動策略的切換時機，其中S＿timer的關閉／打開分別表示開始事件驅動調度／開始時間片驅動調度。圖中有5種事件置位／清除操作，其中虛線箭頭表示的5種操作是在GuestOS中進行的，需要采用超級調用（hypercall）實現(xiàn)，其中的硬件中斷事件置位操作（實線箭頭）是在虛擬化操作系統(tǒng)特權空間中進行的，可以直接操作。

2.3.4 事件優(yōu)先級處理策略

當調度觸發(fā)事件到來時，首先設置事件標識位，然后去檢查各類事件組中的標識位。如果有更高優(yōu)先級的事件存在，返回；如果沒有，再檢查自己是否是第一個觸發(fā)事件。如果是，關閉時間片驅動調度策略，開始事件驅動調度策略 （關閉S＿timer），然后去查詢事件驅動調度表，對比當前Domain判斷是否需要產生調度。

當調度觸發(fā)事件響應處理完成后，需要調用hypercall清除，清除該事件的標識位后，要先去檢查一下是否有比自己優(yōu)先級低的事件存在。如果有，就去處理它，查詢事件驅動調度表，判斷是否需要產生新的調度；如果沒有比自己優(yōu)先級低的事件的存在，表示事件組中沒有其他事件存在了，啟動事件片調度策略，結束事件驅動調度策略（打開S＿timer）。

3 測試結果與分析

3.1 測試結果

硬件測試環(huán)境：ARM926EJ－S、主頻226MHz、64MB SDRAM、I／D Cache 16KB／16KB enable、MMU enable。軟件平臺：自研虛擬化操作系統(tǒng)（基于Xen）、Threadx、Linux（參考圖1）。測試軟件采用LMBench，以及根據(jù)實際應用場景設計的大量測試用例。

對本文提出的調度方法和常用的BVT調度算法進行對比測試，測試結果表明系統(tǒng)的實時性響應和系統(tǒng)的運行性能都有較大幅度的提升。根據(jù)對大量測試數(shù)據(jù)的統(tǒng)計，得到以下3個結果：

①GuestOS系統(tǒng)運行性能的平均加速比為：threadx 1.82，Linux 1.94。

②中斷響應加速比為：單個GuestOS運行時為8.474，兩個GuestOS同時運行時為15.6015。且響應時間平穩(wěn)，有良好的可預測性。

圖5 事件置位和清除規(guī)則時序圖

③GuestOS之間的數(shù)據(jù)通信速度加速比為12.51，且速率穩(wěn)定。

3.2 測試分析

經過實踐應用表明，本文提出的方法有效地解決了虛擬化操作系統(tǒng)傳統(tǒng)調度方法帶來的CPU利用率低、中斷響應緩慢、操作系統(tǒng)（GuestOS）之間數(shù)據(jù)通信速度慢等問題。

編者注：本文為期刊縮略版，全文見本刊網站www.mesnet.com.cn。

［1］M Joseph，P Pandya.Finding Response Times in a real－Time System［J］.The Computer Journal，1986（5）.

［2］C Liu，J Layland.Scheduling Algorithms for Multiprogramming in a Hard－Real－Time Environment［J］.Journal of theACM，1973（1）.

［3］Marco Spuri.Analysis of Deadline Scheduled Real－Time Systems［J］.Journal of the ACM，1996（1）.

［4］B Sprunt，L Sha，J Lehoczky.Aperiodic Task Scheduling for Hard－Real－Time Systems［J］.Real Time systems，1989（1）：27－60.

［5］秦嘯，韓宗芬，龐麗萍.基于異構分布式系統(tǒng)的實時容錯調度算法 ［J］.計算機學報，2002（1）.