基于系統實(shí)時(shí)事件驅動(dòng)和時(shí)間驅動(dòng)相結合的調度方法

　引言

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

　　1 問(wèn)題提出

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

圖1 虛擬化操作系統

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

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

　　2 解決方法

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

　　2.1 調度原則

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

圖2 調度原則

　　2.2 實(shí)時(shí)性分析

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

圖3 中斷實(shí)時(shí)響應分析

　　虛擬操作系統應用中常會(huì )有以下3類(lèi)事件的實(shí)時(shí)響應需要考慮：

　　0類(lèi)事件--底層硬件中斷需要得到上層某個(gè)Domain的快速響應處理；

　　1類(lèi)事件--Domain（GuestOS）之間的通信事件需要被另一個(gè)Doamin快速處理；

　　2 類(lèi)事件--Domain（GuetOS）中的任務(wù)空閑時(shí)，主動(dòng)放棄CPU，通知Domain調度器使其他Domain（GuestOS）得到運行機會(huì )。

　　這些事件的實(shí)時(shí)性響應時(shí)間分析和中斷響應類(lèi)似。

　　在本方法中，如圖4所示，上述的3類(lèi)事件都以設置觸發(fā)事件的形式驅動(dòng)Domain調度器，Domain調度器可以根據這些事件組合、當前的GuestOS狀態(tài)組合、當前的Domain調度狀態(tài)來(lái)產(chǎn)生調度決策。

　　2.3 方法實(shí)施

　　2.3.1 事件定義

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

　　2.3.2 狀態(tài)定義

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

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

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

圖4 基于事件驅動(dòng)的實(shí)時(shí)調度方法

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

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

表3 調度查詢(xún)表

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

　　2.3.3 事件置位與清除規則

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

　　事件置位和清除規則時(shí)序如圖5所示。圖5表示了3種類(lèi)型的調度觸發(fā)事件的設置和清除時(shí)機，以及事件驅動(dòng)策略和時(shí)間片驅動(dòng)策略的切換時(shí)機，其中S_timer的關(guān)閉/打開(kāi)分別表示開(kāi)始事件驅動(dòng)調度/開(kāi)始時(shí)間片驅動(dòng)調度。圖中有5種事件置位/清除操作，其中虛線(xiàn)箭頭表示的5種操作是在GuestOS中進(jìn)行的，需要采用超級調用（hypercall）實(shí)現，其中的硬件中斷事件置位操作（實(shí)線(xiàn)箭頭）是在虛擬化操作系統特權空間中進(jìn)行的，可以直接操作。

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

　　當調度觸發(fā)事件到來(lái)時(shí)，首先設置事件標識位，然后去檢查各類(lèi)事件組中的標識位。如果有更高優(yōu)先級的事件存在，返回；如果沒(méi)有，再檢查自己是否是第一個(gè)觸發(fā)事件。如果是，關(guān)閉時(shí)間片驅動(dòng)調度策略，開(kāi)始事件驅動(dòng)調度策略 （關(guān)閉S_timer），然后去查詢(xún)事件驅動(dòng)調度表，對比當前Domain判斷是否需要產(chǎn)生調度。

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

圖5 事件置位和清除規則時(shí)序圖

　　3 測試結果與分析

　　3.1 測試結果

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

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

　?、?GuestOS系統運行性能的平均加速比為：threadx 1.82，Linux 1.94.

　?、?中斷響應加速比為：?jiǎn)蝹€(gè)GuestOS運行時(shí)為8474，兩個(gè)GuestOS同時(shí)運行時(shí)為15.6015.且響應時(shí)間平穩，有良好的可預測性。

　?、?GuestOS之間的數據通信速度加速比為12.51，且速率穩定。

　　3.2 測試分析

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