基于FPGA的實時操作系統調度器硬件化設計與實現

關 沫，張曉宇

(沈陽工業大學 信息科學與工程學院，遼寧 沈陽 110870)

0 引言

面對嵌入式系統功能需求的復雜化和多樣性，目前在復雜任務中多核系統已基本取代單核系統。隨著異構多核系統的快速發展，其以芯片高利用率、低功耗、高并行化應用程序等諸多優勢已成為處理器體系結構發展的一個重要方向[1]。但是多核處理器在體系結構和系統管理上有不同于單核處理器的固有特性，在多核平臺上高效地設計和部署軟件實時操作系統仍然面臨著一些挑戰。一般多核系統運行模式主要有三種：Asymmetric Multi-Processing(AMP)、Symmetric Multi-Processing(SMP)和Bound Multi-Processing(BMP)。SMP運行模式的實時操作系統無法部署在異構多核系統中，在該運行模式下的實時系統的實例存在于RAM中，并依附于同構處理器進行調度，管理所有可運行系統實例的處理器內核，而對于異構的處理器系統實例只存在于一種架構的處理器中而無法管理所有架構[2-3]。AMP運行模式可使多個系統實例存在于不同處理器系統中，但不能將多核系統統一管理起來。BMP運行模式允許共享同一個數據集的應用獨立地運行在同一個內核上，但鎖定于一個內核的應用無法利用其他內核，即使其他內核處于空閑狀態，造成系統浪費。

在系統的實時性方面，對于基于軟件實現的多核實時操作系統的任務調度產生的Non-deterministic Polynomial(NP)難題[4]，單純依靠改進算法已不能使實時性得到更大的提高，僅依靠提升處理器的性能產生的效果也十分有限。要實現調度算法并行的物理操作，在現有的計算機處理器中很難達到，必須借助外部輔助設備進行[5]。而硬件電路獨立于處理器運行，不占用處理器的處理時間，所節省的時間可用于執行任務程序，所以基于硬件實現的操作系統可以使其實時性和可靠性顯著提高[6]。

本文工作是基于目前Field Programmable Gate Array(FPGA)具有功能強大、設計靈活、易于維護和升級等特點[7]，使用FPGA進行實時操作系統內核調度器的搭建，硬件化系統內核的任務調度算法，并設計了一種新的運行模式VMP，使系統不再是一段處理器的可執行程序，系統實例運行在處理器之外，不再依附與處理器本身進行調度，從而實現對所有異構處理器系統的管理。

1 硬件實時操作系統運行模式設計

硬件實時操作系統與軟件實時操作系統雖然在設計與搭建上不太相同，但其主要功能基本一致。任務調度算法是軟件實時操作系統的核心也是硬件操作系統的核心器件[8]。硬件系統調度器使用的調度算法與一般軟件系統一樣均為搶占式加輪詢式。對于異構處理器的任務調度，本文設計一種新的運行模式VMP，該運行模式將SMP與BMP兩種運行模式相結合，使之可以動態地相互轉化或共存在一個系統之中，在SMP運行模式下可保證系統的整體運算能力，在BMP運行模式下可降低CACHE沖突。

在VMP運行模式下需將可執行任務進行分組，然后指定內核執行的任務分組形成可執行任務集合，每個內核的調度任務都將在任務集合中選取。在運行時可動態改變任務分組及集合內分組。圖1所示有7個任務需在3種不同架構的處理器中運行，其中任務0、1為DSP任務，任務2為X86任務，任務3、4、5、6為ARM任務。圖1中DSP和X86處理器運行在BMP運行模式下即所有任務固定在特定的處理器下，ARM處理器運行在SMP運行模式下。如果改變ARM的執行任務分組則其變為BMP運行模式，即SMP與BMP運行模式可以進行相互轉化。這樣VMP既保證了系統的實時性，又提高了系統的整體運算效率。

多核硬件調度器的調度規則如下：每個核心總是執行未被其他核心占用的優先級最高，且在最新一次輪詢中未被執行過的任務。為了保證系統的實時性，當有突發任務(任務恢復，新任務創建)時，將替換核心中運行時間最長且優先級最低的任務。為了降低系統的功耗，核心如果沒有可運行任務則關閉該核心，直到有可調用的任務或任務關閉處理器核心。

2 硬件實時操作系統調度器設計

根據實時操作系統硬件調度器性質及調度規則可將調度器分為6個基本模塊電路，分別為任務狀態電路、分組電路、事件管理電路、任務輪詢電路、任務選擇電路及地址映射電路。圖2是以4核處理器為例的硬件調度器示意圖。

圖1 任務調度示意圖

圖2 硬件調度器示意圖

2.1 任務狀態電路

任務是否可運行由任務狀態決定，而任務狀態則由硬件系統內核調度器中任務狀態標志決定。每個任務都有一個任務狀態，并由任務狀態電路提供。在硬件操作系統中由于存儲空間固定，因此任務的數量固定。每個任務有兩種狀態屬性，如圖3所示，屬性1為任務是否存在，屬性2為任務是否掛起，M、N為優先級數和同優先級任務數，組成M×N位任務編碼。

圖3 任務狀態轉換圖

由這兩種屬性可以組合出3種狀態：睡眠態任務(未使用{運行掛起})、就緒態任務(使用運行)、掛起態任務(使用掛起)。任務的屬性狀態標志在寄存器組中由兩個寄存器保存。寄存器組的輸出相當于軟件操作系統里任務就緒表的標志位。每個寄存器組中有2個狀態寄存器，第一個寄存器為0表示任務未載入，為1表示任務已載入。第二個寄存器為0表示任務掛起，為1表示任務運行。輸入創建、刪除、恢復、掛起任務編碼可改變任務狀態。

2.2 任務輪詢電路

對于一個可同優先級輪詢的硬件調度器，不僅要有任務狀態這個條件，還要有一個標志，即任務輪詢標志。在任務輪詢電路中用寄存器組成的一維向量表示。在軟件操作系統里，任務輪詢基本使用循環鏈表。而在硬件系統中則無法使用鏈表，需要一種模擬循環鏈表的電路完成操作。圖4是使用一維向量表示在最新的一輪調度中還剩下可調度的任務編碼。

圖4 輪詢電路示意圖

輪詢電路規則是進行一次調度時，本次輪詢輸出的可用任務編碼等于就緒態任務編碼按位與當前一維向量。一維向量值則是上一個狀態值按位與當前調度的任務編碼的按位取反，且當無可用任務編碼輸出且有就緒任務編碼輸入時，將一維向量值重新置為1。

按照以上規則可以保證在一次輪詢中每一個就緒態任務都會被調度并支持同優先級任意數量的長度擴展。

2.3 任務選擇電路

當前調度的任務編碼是本次輪詢輸出的可用任務編碼經過任務選擇電路的輸出編碼。任務選擇電路的功能有兩個，一是將輸入的睡眠態任務編碼進行選擇輸出創建任務編碼，二是通過輸入的次輪詢所輸出的可用任務編碼及突發任務編碼進行任務調度。無論是創建還是調度都需要對輸入任務編碼進行選擇。選擇規則總是從最低位起第一個可用任務開始選擇。

為了增加系統的擴展性，加入了控制信號，表1為選擇電路真值表，PRD為控制信號輸入，OQ為控制信號輸出，任務編碼輸入輸出長度可隨配置變化。表1所示為3編碼輸入選擇器。

表1 選擇電路真值表

當創建任務時將選擇電路并聯，每個選擇電路的任務輸入寬度為同優先級任務數，選擇電路個數為優先級數，睡眠態任務編碼為任務輸入，要創建優先級為所有PRD端口的輸入。在創建任務時只需輸入要創建的優先級就可得到相應的任務輸出。對于多核系統只需將輸入的睡眠態任務編碼去除掉，當前選擇任務編碼輸出作為下一個核心的選擇電路的任務編碼輸入。以此類推可完成任意數量核心的任務創建。將每一個核心的任務編碼輸出作為任務狀態電路的創建任務編碼輸入。

與創建任務類似，任務調度也是通過選擇電路進行調度輸出，將創建任務時并聯的選擇電路改為串聯，并將任務編碼輸入由睡眠態任務編碼改為編碼總線上從低到高的突發任務編碼、本次輪詢輸出的可用任務編碼及下次輪詢輸出的可用任務編碼。圖5所示為一個優先級的調度電路，其數量與優先級數相同。在多優先級中，將PRD與OQ串聯起來形如調度控制->(0優先級)PRD、(0優先級)OQ->(1優先級)PRD、(1優先級)OQ->(2優先級)PRD等，以此類推。

圖5 調度電路示意圖

從圖5串行鏈接可知，最先調度的為0優先級任務。在同優先級中最先調度突發任務，未有突發任務則調度本輪詢可用任務，未有可用任務則調度次輪詢可用任務，在多核調度中，可能出現本輪可調度任務數少于請求調度的核心數，這時會從次輪詢中提前調度任務作為本輪詢的補充。如果在次輪詢可用任務中未有可用調度任務，則進行下一優先級搜索。即從優先級最高的開始調度，如果0優先級未有可調度任務，其后從1優先級開始調度，以此類推。如果所有優先級未有可用任務調度則關閉處理器內核，等待可用任務。

在多核系統中，將前一個內核的任務輸入編碼去掉前一個內核的當前調度編碼作為本內核的任務編碼輸入，以此類推可完成多核任務調度電路的搭建。

2.4 任務分組電路

任務分組功能則是通過分組電路中由寄存器組成的二維向量實現，如圖6所示。在任務分組向量中，由0與1標記分組且分別互斥。通過任務狀態控制該行任務分組向量的輸出。通過任務分組功能將任務分組信息進行保存，選擇哪些分組的選擇信息則是保存在選擇電路中。通過選擇信息將每個選擇分組的一維向量分別按位與調度電路的輸入，保證輸入的任務都是本處理器下調度的任務，則可實現任務分組功能。

圖6 任務分組電路示意圖

2.5 事件管理電路

為保證系統實時性，必須對一些系統事件進行及時處理[9]。事件是所有可改變任務狀態的操作，包括任務的創建、刪除、掛起、恢復和改變內核可調度任務集合的操作(如改變任務分組信息和選擇信息)。系統會對改變任務狀態的任務通過事件管理電路通知任務選擇電路進行優先調度。對所有內核進行搜索，優先切換空閑狀態下的內核，其次為運行優先級最低且運行時間最長的內核，以此保障系統的實時性。

2.6 地址映射電路

在軟件實時系統中切換任務需要這個任務的TCB任務控制塊，以得到各種信息。而在硬件調度中任務信息存儲在地址映射電路中。由于切換任務編碼總線中的任務信息只有任務編碼，需要將任務編碼轉換為任務信息，以任務編碼為數據地址通過由寄存器組成的多個RAM輸出任務信息，如圖7所示。

在任務創建時輸入任務數據和任務號，這時任務數據存入上方任務信息RAM中，與任務號對應的任務編碼存入下方任務編碼RAM中。任務切換時輸入調度任務輸出，也就是切換任務中的當前切換任務編碼，輸出切換任務對應的任務信息。在進行任務狀態操作時，通過輸入對應的任務號及相應操作的控制碼，可將任務編碼送入對應的任務編碼總線完成操作。

(1)創建任務

處理器發送任務創建命令，輸入創建任務信號，從睡眠態任務編碼中選出一個任務編碼，輸出到任務創建編碼總線上。同時輸入任務數據和任務號，任務數據可以是PCB在內存中的指針，或是線程的堆棧指針，或是任務輪詢時間片大小等，這時輸入任務數據存入任務信息RAM中，創建任務編碼存入任務編碼RAM中。創建任務編碼所對應的寄存器組的狀態，由睡眠態變為就緒態或掛起態，這取決于在創建任務時輸入的命令。在輸入創建任務信號的同時完成以上步驟，在時鐘上升沿輸入信號，在下降沿存儲數據。

(2)刪除任務

處理器發送任務刪除命令，輸入任務號，任務號為讀地址，存儲器輸出相應的任務編碼。輸入控制代碼，輸出到刪除任務編碼總線。任務狀態電路將對應的任務變為睡眠態。同時刪除分組電路里面的任務。在輸入刪除任務信號的同時完成以上步驟，在時鐘上升沿輸入信號，在下降沿存儲數據。

圖7 地址映射電路

(3)掛起與恢復任務

與刪除任務一樣，處理器發送掛起、恢復任務命令或外部電路發送掛起、恢復任務編碼。當為處理器命令時，輸入任務號，任務號為讀地址，存儲器輸出相應的任務編碼。輸入控制代碼，輸出到相應的編碼總線。如外部電路發送任務編碼則直接送到相應的任務編碼總線。任務狀態電路將對應的任務變為對應的狀態。在輸入掛起、恢復任務信號的同時以上步驟同步完成，在時鐘上升沿輸入信號，在下降沿存儲數據。

3 測試結果與分析

本文調度器電路的實現采用VHDL硬件描述語言，使用Altera公司的Quartus軟件進行開發，用ModelSim進行功能仿真。

為了方便仿真及查看測試結果，將調度器配置核心數為2，優先級為2，同優先級任務數為5，分組數為2。共創建5個任務分別為1～5號任務，均為0優先級任務。分為2組，1、2號任務為0組，3、4和5號任務為1組。分別對任務調度、掛起任務、恢復任務及改變分組的功能進行了仿真測試。

如圖8所示，CPU_CURTASK分別為CPU0和CPU1的調度任務的信息輸出，將任務信息存儲為任務號，RE_X為任務的切換信號，兩個內核的可執行任務集合分別指向0組和1組，從圖8可知調度器執行命令從時鐘上升沿開始到下一個上升沿結束，且都是半個時鐘完成調度。從調度輸出可看出系統運行模式為BMP運行模式。

圖8 任務調度測試

如圖9所示，在200 ns輸入任務掛起控制代碼110，輸入控制的5號任務。可見在半個時鐘之后掛起任務5，且切換到任務3，在以后的任務調度中未見任務5。

圖9 掛起任務測試

如圖10所示，在270 ns輸入任務恢復控制代碼111，輸入控制的5號任務。可見在半個時鐘之后恢復任務5，且切換到任務5，在以后的任務調度中可見任務5。

圖10 恢復任務測試

如圖11所示，在450 ns輸入改變分組命令，將兩個內核的任務集合同時指向0、1分組。可見在任務調度時兩個內核同時調度一個任務集合，運行模式改變為SMP運行模式。

圖11 改變分組測試

測試結果表明基于硬件的多核調度器可以在半個時鐘之后到一個時鐘之內完成每一個內核發出的各種任務控制命令，與軟件調度器相比極大地降低了系統任務調度的時間。

4 結論

本文使用VHDL語言設計了實時操作系統硬件多核調度器，基于FPGA完成了內核調度器的搭建。該調度器采用新的VMP運行模式，基于優先級使用搶占加輪詢的方式進行任務調度，可根據系統配置進行硬件裁剪。系統測試結果表明該調度器可在一個系統時鐘之內完成多核處理器發出的各種任務控制命令，實現了對異構多核處理器系統的統一調度和管理。同時調度器的硬件實現可以加快多核處理器系統任務調度的速度，降低處理器的系統開銷，使處理器的時間基本用來執行用戶任務，提高了處理器的利用率。