關(guān) 沫，張曉宇

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

0 引言

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

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

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

1 硬件實時操作系統(tǒng)運行模式設(shè)計

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

在VMP運行模式下需將可執(zhí)行任務(wù)進行分組，然后指定內(nèi)核執(zhí)行的任務(wù)分組形成可執(zhí)行任務(wù)集合，每個內(nèi)核的調(diào)度任務(wù)都將在任務(wù)集合中選取。在運行時可動態(tài)改變?nèi)蝿?wù)分組及集合內(nèi)分組。圖1所示有7個任務(wù)需在3種不同架構(gòu)的處理器中運行，其中任務(wù)0、1為DSP任務(wù)，任務(wù)2為X86任務(wù)，任務(wù)3、4、5、6為ARM任務(wù)。圖1中DSP和X86處理器運行在BMP運行模式下即所有任務(wù)固定在特定的處理器下，ARM處理器運行在SMP運行模式下。如果改變ARM的執(zhí)行任務(wù)分組則其變?yōu)锽MP運行模式，即SMP與BMP運行模式可以進行相互轉(zhuǎn)化。這樣VMP既保證了系統(tǒng)的實時性，又提高了系統(tǒng)的整體運算效率。

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

2 硬件實時操作系統(tǒng)調(diào)度器設(shè)計

根據(jù)實時操作系統(tǒng)硬件調(diào)度器性質(zhì)及調(diào)度規(guī)則可將調(diào)度器分為6個基本模塊電路，分別為任務(wù)狀態(tài)電路、分組電路、事件管理電路、任務(wù)輪詢電路、任務(wù)選擇電路及地址映射電路。圖2是以4核處理器為例的硬件調(diào)度器示意圖。

圖1 任務(wù)調(diào)度示意圖

圖2 硬件調(diào)度器示意圖

2.1 任務(wù)狀態(tài)電路

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

圖3 任務(wù)狀態(tài)轉(zhuǎn)換圖

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

2.2 任務(wù)輪詢電路

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

圖4 輪詢電路示意圖

輪詢電路規(guī)則是進行一次調(diào)度時，本次輪詢輸出的可用任務(wù)編碼等于就緒態(tài)任務(wù)編碼按位與當(dāng)前一維向量。一維向量值則是上一個狀態(tài)值按位與當(dāng)前調(diào)度的任務(wù)編碼的按位取反，且當(dāng)無可用任務(wù)編碼輸出且有就緒任務(wù)編碼輸入時，將一維向量值重新置為1。

按照以上規(guī)則可以保證在一次輪詢中每一個就緒態(tài)任務(wù)都會被調(diào)度并支持同優(yōu)先級任意數(shù)量的長度擴展。

2.3 任務(wù)選擇電路

當(dāng)前調(diào)度的任務(wù)編碼是本次輪詢輸出的可用任務(wù)編碼經(jīng)過任務(wù)選擇電路的輸出編碼。任務(wù)選擇電路的功能有兩個，一是將輸入的睡眠態(tài)任務(wù)編碼進行選擇輸出創(chuàng)建任務(wù)編碼，二是通過輸入的次輪詢所輸出的可用任務(wù)編碼及突發(fā)任務(wù)編碼進行任務(wù)調(diào)度。無論是創(chuàng)建還是調(diào)度都需要對輸入任務(wù)編碼進行選擇。選擇規(guī)則總是從最低位起第一個可用任務(wù)開始選擇。

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

表1 選擇電路真值表

當(dāng)創(chuàng)建任務(wù)時將選擇電路并聯(lián)，每個選擇電路的任務(wù)輸入寬度為同優(yōu)先級任務(wù)數(shù)，選擇電路個數(shù)為優(yōu)先級數(shù)，睡眠態(tài)任務(wù)編碼為任務(wù)輸入，要創(chuàng)建優(yōu)先級為所有PRD端口的輸入。在創(chuàng)建任務(wù)時只需輸入要創(chuàng)建的優(yōu)先級就可得到相應(yīng)的任務(wù)輸出。對于多核系統(tǒng)只需將輸入的睡眠態(tài)任務(wù)編碼去除掉，當(dāng)前選擇任務(wù)編碼輸出作為下一個核心的選擇電路的任務(wù)編碼輸入。以此類推可完成任意數(shù)量核心的任務(wù)創(chuàng)建。將每一個核心的任務(wù)編碼輸出作為任務(wù)狀態(tài)電路的創(chuàng)建任務(wù)編碼輸入。

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

圖5 調(diào)度電路示意圖

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

在多核系統(tǒng)中，將前一個內(nèi)核的任務(wù)輸入編碼去掉前一個內(nèi)核的當(dāng)前調(diào)度編碼作為本內(nèi)核的任務(wù)編碼輸入，以此類推可完成多核任務(wù)調(diào)度電路的搭建。

2.4 任務(wù)分組電路

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

圖6 任務(wù)分組電路示意圖

2.5 事件管理電路

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

2.6 地址映射電路

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

在任務(wù)創(chuàng)建時輸入任務(wù)數(shù)據(jù)和任務(wù)號，這時任務(wù)數(shù)據(jù)存入上方任務(wù)信息RAM中，與任務(wù)號對應(yīng)的任務(wù)編碼存入下方任務(wù)編碼RAM中。任務(wù)切換時輸入調(diào)度任務(wù)輸出，也就是切換任務(wù)中的當(dāng)前切換任務(wù)編碼，輸出切換任務(wù)對應(yīng)的任務(wù)信息。在進行任務(wù)狀態(tài)操作時，通過輸入對應(yīng)的任務(wù)號及相應(yīng)操作的控制碼，可將任務(wù)編碼送入對應(yīng)的任務(wù)編碼總線完成操作。

(1)創(chuàng)建任務(wù)

處理器發(fā)送任務(wù)創(chuàng)建命令，輸入創(chuàng)建任務(wù)信號，從睡眠態(tài)任務(wù)編碼中選出一個任務(wù)編碼，輸出到任務(wù)創(chuàng)建編碼總線上。同時輸入任務(wù)數(shù)據(jù)和任務(wù)號，任務(wù)數(shù)據(jù)可以是PCB在內(nèi)存中的指針，或是線程的堆棧指針，或是任務(wù)輪詢時間片大小等，這時輸入任務(wù)數(shù)據(jù)存入任務(wù)信息RAM中，創(chuàng)建任務(wù)編碼存入任務(wù)編碼RAM中。創(chuàng)建任務(wù)編碼所對應(yīng)的寄存器組的狀態(tài)，由睡眠態(tài)變?yōu)榫途w態(tài)或掛起態(tài)，這取決于在創(chuàng)建任務(wù)時輸入的命令。在輸入創(chuàng)建任務(wù)信號的同時完成以上步驟，在時鐘上升沿輸入信號，在下降沿存儲數(shù)據(jù)。

(2)刪除任務(wù)

處理器發(fā)送任務(wù)刪除命令，輸入任務(wù)號，任務(wù)號為讀地址，存儲器輸出相應(yīng)的任務(wù)編碼。輸入控制代碼，輸出到刪除任務(wù)編碼總線。任務(wù)狀態(tài)電路將對應(yīng)的任務(wù)變?yōu)樗邞B(tài)。同時刪除分組電路里面的任務(wù)。在輸入刪除任務(wù)信號的同時完成以上步驟，在時鐘上升沿輸入信號，在下降沿存儲數(shù)據(jù)。

圖7 地址映射電路

(3)掛起與恢復(fù)任務(wù)

與刪除任務(wù)一樣，處理器發(fā)送掛起、恢復(fù)任務(wù)命令或外部電路發(fā)送掛起、恢復(fù)任務(wù)編碼。當(dāng)為處理器命令時，輸入任務(wù)號，任務(wù)號為讀地址，存儲器輸出相應(yīng)的任務(wù)編碼。輸入控制代碼，輸出到相應(yīng)的編碼總線。如外部電路發(fā)送任務(wù)編碼則直接送到相應(yīng)的任務(wù)編碼總線。任務(wù)狀態(tài)電路將對應(yīng)的任務(wù)變?yōu)閷?yīng)的狀態(tài)。在輸入掛起、恢復(fù)任務(wù)信號的同時以上步驟同步完成，在時鐘上升沿輸入信號，在下降沿存儲數(shù)據(jù)。

3 測試結(jié)果與分析

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

為了方便仿真及查看測試結(jié)果，將調(diào)度器配置核心數(shù)為2，優(yōu)先級為2，同優(yōu)先級任務(wù)數(shù)為5，分組數(shù)為2。共創(chuàng)建5個任務(wù)分別為1～5號任務(wù)，均為0優(yōu)先級任務(wù)。分為2組，1、2號任務(wù)為0組，3、4和5號任務(wù)為1組。分別對任務(wù)調(diào)度、掛起任務(wù)、恢復(fù)任務(wù)及改變分組的功能進行了仿真測試。

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

圖8 任務(wù)調(diào)度測試

如圖9所示，在200 ns輸入任務(wù)掛起控制代碼110，輸入控制的5號任務(wù)?？梢娫诎雮€時鐘之后掛起任務(wù)5，且切換到任務(wù)3，在以后的任務(wù)調(diào)度中未見任務(wù)5。

圖9 掛起任務(wù)測試

如圖10所示，在270 ns輸入任務(wù)恢復(fù)控制代碼111，輸入控制的5號任務(wù)?？梢娫诎雮€時鐘之后恢復(fù)任務(wù)5，且切換到任務(wù)5，在以后的任務(wù)調(diào)度中可見任務(wù)5。

圖10 恢復(fù)任務(wù)測試

如圖11所示，在450 ns輸入改變分組命令，將兩個內(nèi)核的任務(wù)集合同時指向0、1分組?？梢娫谌蝿?wù)調(diào)度時兩個內(nèi)核同時調(diào)度一個任務(wù)集合，運行模式改變?yōu)镾MP運行模式。

圖11 改變分組測試

測試結(jié)果表明基于硬件的多核調(diào)度器可以在半個時鐘之后到一個時鐘之內(nèi)完成每一個內(nèi)核發(fā)出的各種任務(wù)控制命令，與軟件調(diào)度器相比極大地降低了系統(tǒng)任務(wù)調(diào)度的時間。

4 結(jié)論

本文使用VHDL語言設(shè)計了實時操作系統(tǒng)硬件多核調(diào)度器，基于FPGA完成了內(nèi)核調(diào)度器的搭建。該調(diào)度器采用新的VMP運行模式，基于優(yōu)先級使用搶占加輪詢的方式進行任務(wù)調(diào)度，可根據(jù)系統(tǒng)配置進行硬件裁剪。系統(tǒng)測試結(jié)果表明該調(diào)度器可在一個系統(tǒng)時鐘之內(nèi)完成多核處理器發(fā)出的各種任務(wù)控制命令，實現(xiàn)了對異構(gòu)多核處理器系統(tǒng)的統(tǒng)一調(diào)度和管理。同時調(diào)度器的硬件實現(xiàn)可以加快多核處理器系統(tǒng)任務(wù)調(diào)度的速度，降低處理器的系統(tǒng)開銷，使處理器的時間基本用來執(zhí)行用戶任務(wù)，提高了處理器的利用率。