基于改進RMS算法的多核嵌入式系統(tǒng)總線周期調(diào)度表優(yōu)化設(shè)計

于海心，王晶，李曉鋒

(北京控制工程研究所，北京 100000)

高效、可靠的信息收集是遠程指揮控制決策系統(tǒng)三大基本要素之一。如何實現(xiàn)高速有效可靠的信息采集一直是制約遠程控制系統(tǒng)高效指揮的一個瓶頸。嵌入式系統(tǒng)是一種實時性系統(tǒng)，對于這類系統(tǒng)而言,系統(tǒng)的正確性包括邏輯計算結(jié)果以及結(jié)果產(chǎn)生的時間，即必須在規(guī)定的時間范圍內(nèi)正確地響應(yīng)系統(tǒng)輸入。隨著技術(shù)進步以及應(yīng)用需求的提升，嵌入式系統(tǒng)的結(jié)構(gòu)和功能日益復(fù)雜，系統(tǒng)的集成度逐步提高，該現(xiàn)象直接導(dǎo)致嵌入式系統(tǒng)面臨實時性約束和高集成度設(shè)計需求的雙重壓力，而多核處理器的出現(xiàn)使得上述矛盾的解決成為可能。盡管多核處理器可以解決時間約束和高集成度之間的矛盾，并為實時系統(tǒng)帶來諸多改變和進步，但是多核體系結(jié)構(gòu)因其固有屬性，導(dǎo)致在設(shè)計和部署實時系統(tǒng)時會面臨一些挑戰(zhàn)，目前在實時系統(tǒng)中并未有效地發(fā)揮多核平臺的高性能優(yōu)勢[1]。總線周期調(diào)度表是指一個周期內(nèi)所有可能傳輸?shù)目偩€命令集。一個優(yōu)質(zhì)的總線周期調(diào)度表可以使總線負載達到平衡，提高總線的利用率和數(shù)據(jù)傳輸?shù)膶崟r性。對于一般的現(xiàn)場總線,常見的周期調(diào)度表的構(gòu)建算法主要包括單處理器中的靜態(tài)單調(diào)速率算法(RMS)、動態(tài)最小截止期優(yōu)先算法(EDF)和最短空閑時間優(yōu)先算法(LLF)。隨著多核處理器在高可靠控制領(lǐng)域的應(yīng)用逐步廣泛，傳統(tǒng)的現(xiàn)場總線周期表構(gòu)建算法已經(jīng)不足以構(gòu)建一個面向多核嵌入式系統(tǒng)的高效率且負載均衡的總線周期表。為提高總線周期表的效率，越來越多的科研工作者在該方面進行了優(yōu)化和改進，文獻[2]采用差分進化算法，文獻[3]采用模擬退火算法，文獻[4]采用粒子群優(yōu)化算法，文獻[5]采用Pareto蟻群優(yōu)化算法對現(xiàn)場總線的調(diào)度表進行優(yōu)化設(shè)計，文獻[6-8]對資源調(diào)度算法的優(yōu)化評價問題進行研究，而對于多核體系結(jié)構(gòu)的資源分配和調(diào)度問題，文獻[9-11]均進行了研究和探討，上述各類方法均在其特定系統(tǒng)模型中取得了某一特性的最優(yōu)。針對某高可靠性同構(gòu)多核嵌入式系統(tǒng)總線周期表的優(yōu)化設(shè)計問題，筆者分析了其任務(wù)特性，給出了該系統(tǒng)的周期調(diào)度模型，并提出了一種改進RMS算法。該算法應(yīng)用于具有多核嵌入式系統(tǒng)的航天控制系統(tǒng)中，該系統(tǒng)能夠為遠程指揮決策系統(tǒng)提供空天資源的信息支持。

1 多核嵌入式系統(tǒng)概述

1.1 系統(tǒng)結(jié)構(gòu)

多核嵌入式系統(tǒng)根據(jù)處理器核的封裝類型不同可以分為同構(gòu)多核系統(tǒng)和異構(gòu)多核系統(tǒng)。同構(gòu)多核指處理器芯片中內(nèi)部所有核結(jié)構(gòu)相同且各個核具有相同地位，支持相同的指令集；異構(gòu)多核指處理器芯片中采用多種功能不同的核，處理不同功能且根據(jù)需要可能會支持不同的指令集。筆者重點研究同構(gòu)多核處理器的總線周期調(diào)度表問題，討論一種多核嵌入式系統(tǒng)，各個處理器為相同結(jié)構(gòu)，彼此獨立，通過共享二級內(nèi)存彼此完成計算同步及信息交互，每個控制器獨立控制一條總線，如圖1所示。該結(jié)構(gòu)可以增加系統(tǒng)的總線數(shù)據(jù)輸入與輸出能力，可以增加嵌入式系統(tǒng)的集成規(guī)模，同時各核之間耦合度不高，可以通過對總線上數(shù)據(jù)源的備份設(shè)計提高系統(tǒng)的穩(wěn)定性和可靠性。

1.2 系統(tǒng)任務(wù)分析

針對多核處理器調(diào)度策略，主流分為全局方案和規(guī)劃方案兩種。全局調(diào)度策略是指相同的實時任務(wù)每次出現(xiàn)均不在同一處理器上執(zhí)行，且該調(diào)度策略對處理器的同步要求較高，因此所有的處理器上只能使用一種調(diào)度算法，這種方案的優(yōu)勢在于多處理器系統(tǒng)可以統(tǒng)一協(xié)調(diào)分配資源，資源的使用效率較高。與全局調(diào)度策略不同，在規(guī)劃調(diào)度策略中一個實時任務(wù)每次出現(xiàn)都在同一個處理器上執(zhí)行，如圖2所示，全部任務(wù)由任務(wù)分配算法預(yù)先劃分到處理器，在這個策略下每一個處理器都可以運行不同的調(diào)度算法。規(guī)劃策略的優(yōu)勢在于將多處理器的調(diào)度開銷集中在處理器任務(wù)分配中，而這個分配僅執(zhí)行1次且發(fā)生在第1次執(zhí)行前，這樣降低了調(diào)度策略的復(fù)雜性。

通過對圖1所示系統(tǒng)進行分析可知，該系統(tǒng)各處理器獨立控制一條總線，而每條總線的負載不相同，即每個處理器所處理的總線任務(wù)不相同。因此，該種類型多核系統(tǒng)在各總線負載不相同的前提下，更適合使用規(guī)劃調(diào)度策略。在該系統(tǒng)執(zhí)行任務(wù)的過程中，對于單處理器而言，由于總線上負載運行狀態(tài)可能發(fā)生變更，如負載通信故障等，會導(dǎo)致每周期執(zhí)行任務(wù)發(fā)生改變，針對此類多核系統(tǒng)僅采用靜態(tài)調(diào)度策略是不滿足系統(tǒng)的要求的，還需考慮因總線負載動態(tài)均衡的問題。

1.3 系統(tǒng)周期調(diào)度模型

分析如圖1所示系統(tǒng)P的周期調(diào)度模型。該實時系統(tǒng)P包含有m個同構(gòu)處理器，P={p1，p2，…，pm}，假定每個處理器pi所處理的總線任務(wù)集ti不同，且各處理器的總線任務(wù)間不存在任何共享資源和依賴關(guān)系。系統(tǒng)P的總線任務(wù)集合Ta={t1，t2，…,tm}，各單核處理器pi的任務(wù)集ti可以用三元組來描述：

ti=(Ei，Di，Ti)，

(1)

式中：Ei表示任務(wù)ti最長完成時間；Di表示任務(wù)ti的相對截止期；Ti表示任務(wù)ti的周期。

本文僅考慮任務(wù)周期和相對截止期相等并且任務(wù)執(zhí)行時間小于等于周期的情況，則：

Di=Ti， 0≤Ei≤Ti.

(2)

各處理器pi任務(wù)集ti的資源使用效率為

ui=Ei/Ti.

(3)

對于多核系統(tǒng)P的總線資源使用效率用U表示，用來衡量系統(tǒng)P各總線周期表的資源調(diào)度效率：

(4)

則系統(tǒng)P的總線資源使用負載平衡度為

(5)

該指標可以用來衡量系統(tǒng)P的總線負載均衡。

2 改進RMS算法

2.1 RMS算法概述

單調(diào)速率調(diào)度(Rate Monotonic Schedule，RMS)算法是最優(yōu)的靜態(tài)優(yōu)先級調(diào)度算法，采用非搶占的靜態(tài)優(yōu)先級的策略調(diào)度周期性任務(wù)。該策略的原理是更頻繁地使用處理器資源的任務(wù)應(yīng)該獲得更高的優(yōu)先級，因此周期越短優(yōu)先級越高，周期越長優(yōu)先級越低。RMS算法的假設(shè)理論前提：各個任務(wù)之間沒有資源共享，沒有忙等，沒有互斥，也沒有信號量；每個任務(wù)的最后期限是周期性的；優(yōu)先級分配的原則是，周期越短的任務(wù)優(yōu)先級越高。

在使用RMS調(diào)度算法生成總線周期表進行總線消息調(diào)度時，總線消息不能被搶占，一旦發(fā)生消息資源被搶占，則會破壞消息數(shù)據(jù)的完整性，導(dǎo)致數(shù)據(jù)污染，進而導(dǎo)致系統(tǒng)處理錯誤。筆者將討論使用RMS調(diào)度算法進行1553B總線任務(wù)的可調(diào)度性分析，如無特殊說明文中所指的現(xiàn)場總線為1553B總線。

2.2 RMS算法可調(diào)度性分析

算法的可調(diào)度性分析是指在給定的任務(wù)模型中，算法能否在規(guī)定時間內(nèi)完成現(xiàn)有的任務(wù)。文獻[6]給出了調(diào)度性判定的定義，“檢查一個任務(wù)集Ta在指定算法中是否可調(diào)度”，“如果任務(wù)集中每個作業(yè)執(zhí)行完成時都不會錯過截止期，則稱這個任務(wù)集在指定算法下是可調(diào)度的”，文獻[6]中也給出了該定義的證明過程。

總線傳輸消息任務(wù)包括周期消息和隨機消息。周期消息是指總線上以固定的順序、周期和相位出現(xiàn)的消息，而隨機消息是事件觸發(fā)，不以固定時間出現(xiàn)的消息。對周期消息的調(diào)度是一種周期任務(wù)的調(diào)度，消息發(fā)生的周期是固定的，被調(diào)度的時間是明確的，多條消息不可同時占用總線和處理器的資源。對于單處理器來講，使用RMS算法對總線周期任務(wù)的調(diào)度不存在問題，所有的總線周期任務(wù)均能在最壞截止期之前完成。針對圖1中所述系統(tǒng)P，假定處理器pi管理的總線Bi上存在周期任務(wù)t1、t2，其中任務(wù)周期T1=αT2，其中α為整數(shù)且α≥1。假設(shè)在總線Bi上僅存在上述兩個任務(wù)，則對于總線Bi來講，T2為最小周期采用Δ來表示，T1為最大周期，T1=kΔ，k>1且k∈N。對于系統(tǒng)P，為保證所有處理器pi同步，則在所有的總線Bi上σ是相同的。對于在所有的總線Bi上所有周期任務(wù)均能在T1前完成。在實時嵌入式系統(tǒng)中，對于總線上的隨機消息而言，其周期未知，發(fā)生時間不明確，但是對其響應(yīng)時間卻有著明確的要求。因此，僅采用RMS算法對其在系統(tǒng)P中進行調(diào)度是不可行的。筆者針對這個問題以及系統(tǒng)P的多核體系結(jié)構(gòu)，對RMS算法進行了改進，使其能夠完成多核系統(tǒng)P的總線所有類型消息的任務(wù)調(diào)度。

2.3 改進RMS算法及可調(diào)度性分析

針對圖1所示多核結(jié)構(gòu)系統(tǒng)P，每個處理器pi在系統(tǒng)運行時單獨控制一條總線Bi且各總線任務(wù)間無資源共享問題。在系統(tǒng)P進行總線任務(wù)調(diào)度時，為保證系統(tǒng)運行正確，各處理器采集的負載數(shù)據(jù)時序正確，各總線任務(wù)的最小周期σ必須保持一致，如圖3所示。各總線的任務(wù)周期不同，但系統(tǒng)P的所有總線任務(wù)存在一個最小周期σ，其他任務(wù)的周期Ti是整數(shù)倍數(shù)。

在系統(tǒng)P中，除周期任務(wù)外還存在非周期任務(wù)，即隨機任務(wù)。對于隨機任務(wù)的調(diào)度，存在兩種處理思路，一種是建立基于馬爾可夫鏈的消息隊列，隨時刷新總線調(diào)度周期表；一種是將非周期消息周期化。第1種思路的優(yōu)勢在于總線調(diào)度表靈活，資源使用率高，缺點在于調(diào)度算法復(fù)雜，占用處理器資源，不斷進行總線調(diào)度表的生成，這對于實時性很強的嵌入式系統(tǒng)來講，過于浪費處理器資源。筆者采用第2種思路建立對RMS算法進行改進?？偩€進行周期消息傳輸時存在資源占用期和資源閑置期，在每個周期消息之間存在一個寂靜期。在寂靜期內(nèi)總線上無消息傳送，采用RMS算法生成的總線調(diào)度策略，寂靜期內(nèi)無法進行消息傳輸。改進RMS算法的核心思想是利用這段寂靜期，將這段時間作為隨機消息的時間窗口。當一個隨機消息到來，該算法會在隨機消息要求響應(yīng)時間給這個消息選擇一個最優(yōu)時間窗口，讓該消息在最壞截止期之前完成傳輸。

對于處理器Pi管理的總線Bi上存在的隨機任務(wù)ti，也可采用三元組方法來表示，ti=(Ei，Di，Ti)，與周期任務(wù)不同的是Ti表示該任務(wù)的最大響應(yīng)時間，即任務(wù)ti必須在Ti時間內(nèi)開始執(zhí)行?？偩€使用率U和負載均衡度σ2的計算方法與周期任務(wù)相同。

假定，系統(tǒng)P中處理器pi管理的總線Bi上存在周期消息t1、t2，隨機消息t3需要進行資源調(diào)度。其中，t1、t2消息已知發(fā)送周期，t3僅在事件X發(fā)生時才發(fā)送，且其最壞執(zhí)行時間E3和任務(wù)執(zhí)行時間D3已知。改進算法對上述消息的調(diào)度表設(shè)計如圖4所示。改進算法通過分析周期消息t1、t2的調(diào)度周期，找出其可調(diào)度隨機消息的時間發(fā)送窗口W1，W2，W3，并根據(jù)隨機消息t3的資源占用情況，在下一個最小周期T2中選擇合適的時間窗口對t3進行調(diào)度，將時間窗口W2作為隨機消息t3的保留時間窗口。該時間窗口在總線的最大周期中至少出現(xiàn)一次，因此當t3的響應(yīng)時間滿足T2≤T3≤T1時，且存在窗口Wi>t3時，該算法能夠保證所有任務(wù)在最壞截止期內(nèi)完成。

3 仿真實驗與分析

為驗證改進RMS算法對多核嵌入式系統(tǒng)的總線周期調(diào)度表優(yōu)化效果，與RMS調(diào)度算法進行比較。假定針對系統(tǒng)P，一組待調(diào)度總線消息如表1所示。

表1 待通信總線數(shù)據(jù)

將表1所列總線消息，采用改進RMS算法進行調(diào)度。生成圖1中系統(tǒng)P的各總線B1～B4的總調(diào)度任務(wù)集TA={Ta1，Ta2，Ta3，Ta4}。各總線周期調(diào)度表如表2所示，可以看出改進后的RMS算法在將隨機任務(wù)的資源開銷考慮進去，隨機任務(wù)增加在總線的資源調(diào)度表中，增加了系統(tǒng)的資源使用率。隨機任務(wù)出現(xiàn)越多，系統(tǒng)的資源使用率越高。

表2 總線任務(wù)周期調(diào)度表

與RMS調(diào)度算法比較結(jié)果如表3所示，可以看出該算法可以提高總線負載均衡度、提高總線傳輸效率，同時能夠適用于多核嵌入式系統(tǒng)。

表3 改進的RMS算法與RMS算法比較

4 結(jié)束語

為提高遠程指揮控制決策系統(tǒng)的信息采集效率和可靠性，提出了一種改進RMS算法。筆者給出了一種多核處理器的體系結(jié)構(gòu)，在該系統(tǒng)中各處理器單獨管理一條總線，處理器間通過二次共享緩存進行信息交互。在總線周期表設(shè)計中采集改進RMS算法為非周期任務(wù)設(shè)計時間窗口，有效避免了總線上存在非周期消息時出現(xiàn)總線飽和或者堵塞的現(xiàn)象。該方法通過排隊論對非周期消息進行建模，將非周期消息周期化并利用改進RMS 調(diào)度算法對其進行合理調(diào)度。算法的實現(xiàn)條件為隨機消息的響應(yīng)時間，即消息觸發(fā)事件到消息執(zhí)行時間大于系統(tǒng)最小周期且小于系統(tǒng)最大周期，同時總線表中存在大于隨機消息的最壞截止期的時間窗口。在實現(xiàn)周期消息和非周期消息混合傳輸?shù)那闆r下，保證了非周期消息的實時性，實現(xiàn)了數(shù)據(jù)在總線上的實時、可靠的傳輸。