陳澤瑋，楊茂林，雷 航，廖 勇，謝 瑋

(1.電子科技大學(xué) 信息與軟件工程學(xué)院, 成都 610054; 2.云南省電子工業(yè)研究所, 昆明 650031)

SET-MRTS：一種多處理器實(shí)時(shí)系統(tǒng)可調(diào)度性實(shí)驗(yàn)平臺

陳澤瑋1*，楊茂林1，雷 航1，廖 勇1，謝 瑋2

(1.電子科技大學(xué) 信息與軟件工程學(xué)院, 成都 610054; 2.云南省電子工業(yè)研究所, 昆明 650031)

(*通信作者電子郵箱chenzewei@hotmail.com)

近年來，隨著實(shí)時(shí)調(diào)度研究的快速發(fā)展，可調(diào)度性實(shí)驗(yàn)的復(fù)雜性隨之增加, 然而，由于缺乏標(biāo)準(zhǔn)化、模塊化的可調(diào)度性實(shí)驗(yàn)工具，研究者往往需要耗費(fèi)大量時(shí)間進(jìn)行實(shí)驗(yàn); 此外，由于實(shí)驗(yàn)源碼不能公開獲得，使得實(shí)驗(yàn)結(jié)果難以驗(yàn)證，實(shí)驗(yàn)代碼難以重用與擴(kuò)展。針對可調(diào)度性實(shí)驗(yàn)重復(fù)工作量大、難以驗(yàn)證的問題，提出一種可調(diào)度性實(shí)驗(yàn)基礎(chǔ)框架。該框架通過隨機(jī)分布產(chǎn)生任務(wù)系統(tǒng)集合，并測試其可調(diào)度性，基于該框架設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)新的可調(diào)度性實(shí)驗(yàn)開源平臺——SET-MRTS。該平臺采用模塊化架構(gòu)設(shè)計(jì)了任務(wù)模塊、處理器模塊、共享資源模塊、算法庫、配置解析模塊以及輸出模塊。實(shí)驗(yàn)結(jié)果表明，SET-MRTS支持單/多處理器實(shí)時(shí)調(diào)度算法和實(shí)時(shí)同步協(xié)議分析，能夠正確地進(jìn)行可調(diào)度性對比實(shí)驗(yàn)，輸出直觀的實(shí)驗(yàn)結(jié)果，并且支持算法庫的擴(kuò)充，與算法庫中已實(shí)現(xiàn)的算法進(jìn)行對比實(shí)驗(yàn)，具有良好的兼容性與可擴(kuò)展性。SET-MRTS是第一個(gè)支持完整實(shí)驗(yàn)流程，包括算法實(shí)現(xiàn)、參數(shù)配置、結(jié)果統(tǒng)計(jì)、圖表繪制等的可調(diào)度性實(shí)驗(yàn)開源平臺。

實(shí)時(shí)嵌入式系統(tǒng);多核系統(tǒng);實(shí)時(shí)調(diào)度;實(shí)時(shí)鎖協(xié)議;可調(diào)度性實(shí)驗(yàn);開源平臺

0 引言

實(shí)時(shí)系統(tǒng)廣泛應(yīng)用于航空航天、武器裝備、汽車電子、醫(yī)療電子、信息通信等安全關(guān)鍵系統(tǒng)[1]。隨著片上多核以及多處理器系統(tǒng)的大量產(chǎn)業(yè)應(yīng)用，多核/多處理器實(shí)時(shí)系統(tǒng)成為計(jì)算機(jī)系統(tǒng)研究領(lǐng)域的重要課題之一， 其中，實(shí)時(shí)調(diào)度(Scheduling)與資源同步(Synchronization)是確保系統(tǒng)實(shí)時(shí)性的核心與關(guān)鍵技術(shù)。圍繞多核/多處理器系統(tǒng)的實(shí)時(shí)調(diào)度算法與實(shí)時(shí)鎖協(xié)議(Locking Protocol)成為實(shí)時(shí)系統(tǒng)領(lǐng)域的研究熱點(diǎn)。近年來，學(xué)術(shù)界提出了大量實(shí)時(shí)調(diào)度算法、實(shí)時(shí)任務(wù)同步協(xié)議以及相應(yīng)的可調(diào)度性分析方法。如何將新算法與已有算法的可調(diào)度性能進(jìn)行快速而客觀的分析比較成為亟待解決的問題。

在實(shí)時(shí)系統(tǒng)研究領(lǐng)域，一些理論指標(biāo)如利用率界限(Utilization Bound)[2]和加速因子(Speedup Factor)[3]等常用于基于獨(dú)立任務(wù)模型(例如周期任務(wù)模型[2]和偶發(fā)任務(wù)模型[4])的調(diào)度算法性能評價(jià)， 然而，在基于非獨(dú)立任務(wù)模型的研究中，例如實(shí)時(shí)鎖協(xié)議[5-7]等領(lǐng)域，直接使用這些理論指標(biāo)進(jìn)行性能評價(jià)尚有一定困難。此外，這些理論指標(biāo)可能受限于實(shí)際系統(tǒng)中幾乎不會發(fā)生的極端情況，因而并不能全面反映具體算法在某些應(yīng)用場景中的性能。為了快速比較多個(gè)算法的相對性能，分析特定因素對算法性能的影響，算法研究中往往通過設(shè)計(jì)隨機(jī)實(shí)驗(yàn)觀測算法性能的變化趨勢。近年來，隨機(jī)實(shí)驗(yàn)方法已廣泛用于驗(yàn)證實(shí)時(shí)調(diào)度算法以及實(shí)時(shí)鎖協(xié)議的可調(diào)度性能。

隨機(jī)實(shí)驗(yàn)通常包括隨機(jī)參數(shù)產(chǎn)生、算法邏輯實(shí)現(xiàn)、重復(fù)實(shí)驗(yàn)、數(shù)據(jù)結(jié)果統(tǒng)計(jì)以及圖表繪制等。由于目前尚沒有完整的模塊化和標(biāo)準(zhǔn)化實(shí)驗(yàn)工具，當(dāng)研究者提出新的算法時(shí)通常需要耗費(fèi)大量時(shí)間重復(fù)以上過程。為了進(jìn)行充分的橫向比較，實(shí)驗(yàn)中還需要實(shí)現(xiàn)已有的相關(guān)算法，從而進(jìn)一步增加了實(shí)驗(yàn)用時(shí)。此外，大量文獻(xiàn)中所發(fā)表的實(shí)驗(yàn)結(jié)果均來自于作者個(gè)人或其研究小組的獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)源碼通常不能公開獲取，因此難以對實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證。另一方面，現(xiàn)有的部分實(shí)驗(yàn)源碼[8-10]往往僅包含針對特定系統(tǒng)模型的隨機(jī)數(shù)產(chǎn)生方法，以及針對具體算法的邏輯實(shí)現(xiàn)。由于系統(tǒng)模型的兼容性以及調(diào)用不同算法的差異性等問題，具體實(shí)驗(yàn)中往往難以直接重用或擴(kuò)展現(xiàn)有代碼。

基于以上背景，本文針對實(shí)時(shí)系統(tǒng)可調(diào)度性實(shí)驗(yàn)提出一種隨機(jī)實(shí)驗(yàn)框架，并基于該框架開發(fā)了可調(diào)度性實(shí)驗(yàn)開源平臺SET-MRTS(Schedulability Experiment Toolkit for Multiprocessor Real-Time Systems)(https://github.com/ChenZewei/SET-MRTS)。開源平臺基于C++語言開發(fā)，包含了進(jìn)行可調(diào)度性實(shí)驗(yàn)所需的完整工具，包括系統(tǒng)參數(shù)產(chǎn)生模塊、算法庫、實(shí)驗(yàn)配置模塊、數(shù)據(jù)統(tǒng)計(jì)模塊以及圖表繪制模塊。其中，系統(tǒng)參數(shù)模塊提供了靈活豐富的系統(tǒng)參數(shù)，包括任務(wù)參數(shù)、處理器參數(shù)、共享資源參數(shù)等。用戶可以基于這些參數(shù)實(shí)現(xiàn)各種算法并將新算法添加到算法庫。算法庫中的所有算法均可以重用。隨機(jī)實(shí)驗(yàn)中，用戶只需根據(jù)實(shí)驗(yàn)需求，在配置模塊中對實(shí)驗(yàn)參數(shù)進(jìn)行簡單配置，同時(shí)選取所需比較的算法。SET-MRTS將根據(jù)配置信息進(jìn)行重復(fù)實(shí)驗(yàn)，統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果并自動繪圖。SET-MRTS是第一個(gè)具備完整可調(diào)度性實(shí)驗(yàn)工具鏈的開源平臺。

1 實(shí)時(shí)調(diào)度領(lǐng)域相關(guān)研究

1.1 相關(guān)工作

可調(diào)度性實(shí)驗(yàn)廣泛用于實(shí)時(shí)調(diào)度算法分析與比較。文獻(xiàn)[11]針對單處理器系統(tǒng)可調(diào)度性實(shí)驗(yàn)，提出了UUnifast算法用以隨機(jī)產(chǎn)生均勻分布的任務(wù)資源利用率(Utilization)。文獻(xiàn)[12]針對多處理器系統(tǒng)，研究了任務(wù)資源利用率的產(chǎn)生方法，提出了UUnifast-Discard算法。在可調(diào)度性實(shí)驗(yàn)平臺方面，國內(nèi)尚沒有開源實(shí)驗(yàn)平臺，國際上也僅有少數(shù)研究團(tuán)隊(duì)發(fā)布了可調(diào)度性實(shí)驗(yàn)所需的部分工具。

馬克斯普朗克軟件系統(tǒng)研究所(Max Planck Institute for Software System)開發(fā)的SchedCAT[8]是目前維護(hù)較活躍的多處理器可調(diào)度性實(shí)驗(yàn)開源工具。SchedCAT最初用于多處理器實(shí)時(shí)鎖協(xié)議分析[5]，是目前最完善的實(shí)時(shí)鎖協(xié)議分析工具； 然而，SchedCAT僅包含系統(tǒng)參數(shù)產(chǎn)生模塊和算法庫，用戶必須獨(dú)立設(shè)計(jì)實(shí)驗(yàn)流程并完成數(shù)據(jù)統(tǒng)計(jì)和繪圖。ReTis實(shí)驗(yàn)室的開源工具Algorithms[9]是針對單處理器實(shí)時(shí)調(diào)度算法的算法庫。該工具僅包含UUnifast算法以及實(shí)現(xiàn)單處理器可調(diào)度性分析的Matlab函數(shù)，而缺乏支持完整隨機(jī)實(shí)驗(yàn)所需的其他模塊。意大利系統(tǒng)分析與計(jì)算機(jī)科學(xué)研究所(IASI)發(fā)布的多處理器可調(diào)度性判定工具C++ Exact Multiprocessor Feasibility/Schedulability Tools[10],但僅用于判斷某個(gè)給定任務(wù)系統(tǒng)的可調(diào)度性，尚不支持批量化隨機(jī)實(shí)驗(yàn)。此外，一些研究團(tuán)隊(duì)發(fā)布了實(shí)時(shí)調(diào)度仿真開源工具，如YAO-SIM[13]、RTSIM[14]、PartiCor[15]、TrueTime[16]等。然而，調(diào)度仿真僅能夠作為系統(tǒng)不可調(diào)度的充分條件，不能直接用于評價(jià)可調(diào)度性分析方法的性能。本文推出的開源工具平臺SET-MRTS包含了可調(diào)度性實(shí)驗(yàn)所需的完整模塊且易于擴(kuò)展，可直接用于可調(diào)度性實(shí)驗(yàn)。

1.2 可調(diào)度性判定

常用的可調(diào)度性分析方法包括響應(yīng)時(shí)間分析法(Response-Time Analysis, RTA)和資源利用率界限判定法。

1.2.1 基于響應(yīng)時(shí)間分析的判定

定義1 任務(wù)τi的第j個(gè)任務(wù)實(shí)例記為Ji, j。令Ji, j的釋放時(shí)間為ri, j，完成時(shí)間為fi, j，則響應(yīng)時(shí)間Ri, j為：

Ri, j=fi, j-ri, j

(1)

任務(wù)τi的最壞響應(yīng)時(shí)間(Worst-Case Response Time, WCRT)Ri為τi的所有任務(wù)實(shí)例的響應(yīng)時(shí)間的最大值，即：

(2)

根據(jù)經(jīng)典RTA分析框架[17]，Ri可進(jìn)一步表示為：

Ri=Ci+Bi+Ii

(3)

其中:Ci為τi的最壞執(zhí)行時(shí)間(Worst-Case Execution Time，WCET)，Bi為τi的最壞阻塞時(shí)間(Worst-Case Blocking Time, WCBT)，Ii為τi的最大搶占延遲(Interference)。Ri的具體計(jì)算方法由具體調(diào)度算法、鎖協(xié)議以及可調(diào)度性分析方法決定。

若計(jì)算法所得的Ri不大于τi的相對截止時(shí)間，則稱該任務(wù)可調(diào)度。若任務(wù)系統(tǒng)中所有任務(wù)均可調(diào)度，則稱該任務(wù)集合可調(diào)度。

1.2.2 資源利用率界限判定法

資源利用率界限判定法常用于隱式截止時(shí)間(Implicit Deadline)周期任務(wù)系統(tǒng)。令τi的最壞執(zhí)行時(shí)間為Ci，相對截止時(shí)間為Di，周期為Ti。τi的相鄰兩個(gè)任務(wù)實(shí)例的時(shí)間間隔為Ti，且Ti=Di。任務(wù)τi以及任務(wù)系統(tǒng)的資源利用率定義如下。

定義2 任務(wù)τi的資源利用率ui如式(4)所示，任務(wù)系統(tǒng)Γ的資源利用率U如式(5)所示:

(4)

(5)

一個(gè)調(diào)度算法A的資源利用率界限為UA，則可確保任意資源利用率小于等于UA的任務(wù)系統(tǒng)在算法A中可調(diào)度。例如，在單處理器系統(tǒng)中最早截止時(shí)間優(yōu)先(Earliest Deadline First， EDF)算法的利用率界限為1，則對于任意資源利用率不大于1的隱式截止時(shí)間周期任務(wù)系統(tǒng)，EDF算法能夠確保該任務(wù)系統(tǒng)可調(diào)度。

2 平臺設(shè)計(jì)與實(shí)現(xiàn)

2.1 平臺設(shè)計(jì)需求

SET-MRTS的設(shè)計(jì)目的是提供一個(gè)功能完善、兼容性強(qiáng)、易于擴(kuò)展的可調(diào)度性實(shí)驗(yàn)平臺，用戶無需二次開發(fā)便可使用該平臺進(jìn)行可調(diào)度性實(shí)驗(yàn)。當(dāng)需要對算法庫中尚未建立的算法或分析方法(如新提出的方法)進(jìn)行實(shí)驗(yàn)時(shí)，開發(fā)者僅需實(shí)現(xiàn)該方法即可與算法庫中所有方法進(jìn)行比較。

2.2 平臺模塊設(shè)計(jì)

為了實(shí)現(xiàn)上述設(shè)計(jì)需求，采取了高內(nèi)聚、低耦合的模塊化設(shè)計(jì)方法。SET-MRTS主要包括任務(wù)模塊、處理器模塊、共享資源模塊、配置解析模塊以及輸出模塊。其中，任務(wù)模塊、處理器模塊與共享資源模塊之間具有關(guān)聯(lián)關(guān)系。例如，在分組調(diào)度(Partitioned Scheduling)算法可調(diào)度性實(shí)驗(yàn)中，處理器模塊中需要維護(hù)分配到各處理器上的任務(wù)信息；而在實(shí)時(shí)鎖協(xié)議可調(diào)度性實(shí)驗(yàn)中，任務(wù)模塊也需要維護(hù)每個(gè)任務(wù)所訪問的共享資源信息。此外，各子模塊間還存在聚合或組合的關(guān)系。平臺的結(jié)構(gòu)圖(類圖)如圖1所示(空心菱形為聚合關(guān)系，實(shí)心菱形為組合關(guān)系，箭頭為關(guān)聯(lián)關(guān)系)。

任務(wù)模塊是SET-MRTS中的重要模塊，由任務(wù)類、任務(wù)集合類以及共享資源請求類所構(gòu)成。其中，任務(wù)類(Task)描述了可調(diào)度性分析方法中所使用的所有隨機(jī)任務(wù)參數(shù)，包括了任務(wù)的最壞執(zhí)行時(shí)間(WCET)、相對截止時(shí)間(Deadline)、周期(Period)和共享資源請求(Request)等主要屬性。新的任務(wù)將被加入任務(wù)集合中，組成一個(gè)任務(wù)系統(tǒng)。通過任務(wù)集合類(TaskSet)可以獲得系統(tǒng)資源利用率(get_utilization_sum)、最大任務(wù)資源利用率(get_utilization_max)等，并且可以根據(jù)某一屬性對任務(wù)進(jìn)行排序(sort_by_xxx)，使任務(wù)系統(tǒng)能夠靈活地調(diào)整，為各種可調(diào)度性分析方法的實(shí)現(xiàn)提供了方便。此外，每個(gè)任務(wù)還通過共享資源請求類來表示對共享資源的訪問。

圖1 SET-MRTS的類圖Fig. 1 Class diagram of SET-MRTS

處理器模塊則包括通過處理器類和處理器集合類。處理器類用于描述實(shí)驗(yàn)所使用的處理器模型，包括各處理器的執(zhí)行速率(Speedfactor)以及處理器系統(tǒng)的規(guī)模(核心數(shù)量，core_num)等。處理器集合(ProcessorSet)類則用于表示處理器平臺的組成。雖然SET-MRTS現(xiàn)在主要用于同構(gòu)多處理器下可調(diào)度性分析方法的測試，但也為異構(gòu)多核/多處理器平臺與可并行任務(wù)模型下的實(shí)時(shí)任務(wù)調(diào)度分析提供了基礎(chǔ)。

共享資源模塊主要用于實(shí)時(shí)調(diào)度領(lǐng)域中的實(shí)時(shí)鎖協(xié)議分析，如多處理器優(yōu)先級天花板協(xié)議(Multiprocessor Priority Ceiling Protocol, MPCP)[18]、分布式優(yōu)先級天花板協(xié)議(Distributed Priority Ceiling Protocol, DPCP)[19]和多處理器堆資源協(xié)議(Multiprocessor Stack Resource Protocol, MSRP)[20]等。該模塊由共享資源類與共享資源集合類所組成，其中共享資源類對共享資源進(jìn)行了抽象描述，包括了共享資源號、共享資源的全局性(global_resource)以及訪問該共享資源的任務(wù)隊(duì)列(TaskQueue)等。共享資源類通過共享資源集合類(ResourceSet)進(jìn)行封裝。通過該模塊可以描述整個(gè)系統(tǒng)的共享資源，并且與各個(gè)任務(wù)建立訪問關(guān)系，從而實(shí)現(xiàn)共享資源的優(yōu)先級天花板(Priority Ceiling)查詢以及任務(wù)的阻塞時(shí)間分析。

以上3個(gè)模塊是SET-MRTS的核心組成部分，也是可調(diào)度性分析所依賴的基本結(jié)構(gòu)。通過對這些模塊進(jìn)行操作，能夠規(guī)范實(shí)驗(yàn)流程，確保實(shí)驗(yàn)平臺可調(diào)度性分析方法的兼容性與可擴(kuò)展性。

此外，隨機(jī)實(shí)驗(yàn)參數(shù)設(shè)置也是實(shí)驗(yàn)流程的重要環(huán)節(jié)。SET-MRTS采用配置文件的方式實(shí)現(xiàn)實(shí)驗(yàn)參數(shù)的輸入。參數(shù)配置模塊通過實(shí)現(xiàn)一個(gè)解析類對使用XML格式的配置文件進(jìn)行解析，并存放在指定的參數(shù)結(jié)構(gòu)中。如圖1的配置模塊中，XML類通過get_integers函數(shù)來提取配置文件中指定元素的整型參數(shù)集合。用戶僅需要對配置文件進(jìn)行配置即可進(jìn)行實(shí)驗(yàn)。通過參數(shù)配置模塊能夠有效提高參數(shù)輸入的效率。隨著SET-MRTS的不斷拓展與更新，會有更多的參數(shù)需要輸入，配置模塊能夠保證參數(shù)的拓展不影響平臺的兼容性。

目前已知的其他開源平臺僅提供實(shí)驗(yàn)結(jié)果的在線輸出，或通過文本格式保存實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果，用戶需要對該結(jié)果進(jìn)行整理，才能夠得到更加直觀的實(shí)驗(yàn)結(jié)果。SET-MRTS的輸出模塊不僅能夠在實(shí)驗(yàn)結(jié)束后以文本格式保存實(shí)驗(yàn)結(jié)果(通過Output類)，還能夠根據(jù)配置生成對應(yīng)的折線圖(通過Chart類)，并保存為位圖或矢量圖，從而為研究者提供更直觀的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果。

2.3 實(shí)驗(yàn)流程

2.3.1 實(shí)驗(yàn)流程

實(shí)驗(yàn)中，SET-MRTS通過參數(shù)輸入模塊建立實(shí)驗(yàn)場景，然后根據(jù)可調(diào)度性分析方法圍繞任務(wù)模塊、處理器模塊以及共享資源模塊進(jìn)行相應(yīng)操作，并輸出實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果。實(shí)驗(yàn)開始時(shí)，通過XML類提取配置文件中的參數(shù)并保存于Param類的實(shí)例中，并以此參數(shù)建立實(shí)驗(yàn)場景，例如處理器種類與數(shù)量、生成共享資源實(shí)例以及產(chǎn)生任務(wù)系統(tǒng)等。接著，測試所選可調(diào)度性分析方法在以上實(shí)驗(yàn)場景中的可調(diào)度率，并進(jìn)行重復(fù)實(shí)驗(yàn)。最后，統(tǒng)計(jì)各算法的性能指標(biāo)(如可調(diào)度率)并通過輸出模塊輸出實(shí)驗(yàn)結(jié)果。整體實(shí)驗(yàn)流程如圖2所示。

圖2 實(shí)驗(yàn)流程Fig. 2 Flow chart of experiments

2.3.2 參數(shù)配置

SET-MRTS使用XML結(jié)構(gòu)化語言描述實(shí)驗(yàn)參數(shù)，并通過配置文件進(jìn)行參數(shù)配置。用戶可以配置隨機(jī)實(shí)驗(yàn)參數(shù)的產(chǎn)生規(guī)則，如任務(wù)資源利用率均值、任務(wù)系統(tǒng)資源利用率取值范圍，以及任務(wù)集合資源利用率取值的步長等。配置文件支持整型、浮點(diǎn)型、字符型參數(shù)的輸入，并支持多組數(shù)據(jù)的組合輸入。實(shí)驗(yàn)參數(shù)配置示例如下所示：

//實(shí)驗(yàn)中任務(wù)系統(tǒng)資源利用率增長的步長

//任務(wù)系統(tǒng)資源利用率范圍 …

2.3.3 任務(wù)系統(tǒng)產(chǎn)生

SET-MRTS使用隨機(jī)分布產(chǎn)生任務(wù)的屬性。根據(jù)配置文件中設(shè)置的參數(shù)產(chǎn)生范圍，使用基于均勻分布和指數(shù)分布等隨機(jī)數(shù)產(chǎn)生方法隨機(jī)產(chǎn)生任務(wù)周期、任務(wù)最壞執(zhí)行時(shí)間、任務(wù)截止時(shí)間、任務(wù)資源利用率等參數(shù)； 同時(shí)，記錄每個(gè)任務(wù)集合的任務(wù)數(shù)、任務(wù)系統(tǒng)資源利用率等參數(shù)。該流程偽代碼如下：

uniform_gen(int min, int max) //產(chǎn)生在min和max之間的均勻分布隨機(jī)數(shù) exponential _gen(int lambda) //以lambda為率參數(shù)產(chǎn)生指數(shù)分布隨機(jī)數(shù) while(current_utilization < utilization_bound) { period=uniform_gen(u_min, u_max); deadline=uniform_gen(d_min, d_max) * period; utilization=exponential_gen(lambda); if(current_utilization+utilization>utilization_bound); { utilization=utilization_bound-current_utilization; } wcet=period * utilization; taskset.add_task(wcet, deadline, period); }

2.3.4 共享資源訪問

共享資源是實(shí)時(shí)鎖協(xié)議分析中的重要結(jié)構(gòu)。任務(wù)所需要訪問的共享資源集合、任務(wù)訪問每個(gè)共享資源的最大次數(shù)以及最長訪問時(shí)間是計(jì)算任務(wù)阻塞時(shí)間的主要依據(jù)。SET-MRTS采用訪問概率來決定任務(wù)對共享資源的請求，該流程的偽代碼如下：

calculate_total_len()

//用于計(jì)算訪問總時(shí)長 add_request()

//用于將共享資源訪問申請?zhí)砑又寥蝿?wù) add_task()

//用于將該任務(wù)添加到共享資源訪問隊(duì)列 probability(double P)

//以概率P為真 foreach(resource in resource_set) { if(probability(request_prob)) { request_num=uniform_gen(1, num_max); max_len=uniform_gen(len_min, len_max); total_len=calculate_total_len(); task.add_request(request_num, max_len, total_len); resource_set.add_task(&task); } }

任務(wù)創(chuàng)建時(shí)將遍歷共享資源集合，根據(jù)配置文件中設(shè)置的共享資源訪問概率隨機(jī)確定是否訪問某個(gè)共享資源，并通過隨機(jī)分布函數(shù)產(chǎn)生其他屬性。

2.4 平臺擴(kuò)展性

SET-MRTS具有良好的兼容性與可擴(kuò)展性。實(shí)驗(yàn)平臺能夠方便地實(shí)現(xiàn)新的可調(diào)度性分析方法并能夠與已實(shí)現(xiàn)的方法進(jìn)行比較。分析者只需要按照各模塊的格式實(shí)現(xiàn)新的算法并添加到算法庫中，便能夠通過配置文件隨意選擇算法庫中的算法進(jìn)行實(shí)驗(yàn)比較。在實(shí)驗(yàn)平臺的設(shè)計(jì)和實(shí)現(xiàn)中，采取了模塊化的方法來設(shè)計(jì)和實(shí)現(xiàn)平臺的任務(wù)、處理器和共享資源模塊。各模間通過清晰的接口連接，從而方便設(shè)計(jì)者實(shí)現(xiàn)新的算法。隨著本平臺功能的擴(kuò)充，將支持更多的可調(diào)度性分析方法。

3 實(shí)驗(yàn)與分析

以下通過兩個(gè)簡單的實(shí)驗(yàn)來驗(yàn)證SET-MRTS的功能。實(shí)驗(yàn)一針對獨(dú)立任務(wù)模型，不包含實(shí)時(shí)鎖協(xié)議的分析，因此沒有配置共享資源參數(shù)。實(shí)驗(yàn)二則分別對基于自旋鎖和信號量機(jī)制的實(shí)時(shí)鎖協(xié)議進(jìn)行分析。實(shí)驗(yàn)二中測試了共享資源訪問概率對可調(diào)度率的影響。兩個(gè)實(shí)驗(yàn)均采用了同構(gòu)多處理器模型，所有處理器的執(zhí)行速度均相同。

3.1 實(shí)驗(yàn)配置

表1列出了實(shí)驗(yàn)一所使用的主要參數(shù)。

表1 獨(dú)立任務(wù)模型主要參數(shù)Tab. 1 Primary parameters for independent task model

3.2 實(shí)驗(yàn)結(jié)果與分析

以經(jīng)典可調(diào)度性分析方法為例進(jìn)行可調(diào)度性實(shí)驗(yàn)，由實(shí)驗(yàn)平臺所導(dǎo)出的折線圖結(jié)果如圖3所示。

圖3 可調(diào)度性分析方法的實(shí)驗(yàn)結(jié)果對比Fig. 3 Result comparison of some schedulability analysis methods

實(shí)驗(yàn)一的結(jié)果如圖3所示，展示了獨(dú)立任務(wù)模型中多種分析方法的可調(diào)度率(Ratio)隨系統(tǒng)資源利用率(TaskSet Utilization)的變化趨勢。其中，RTA-GFP表示基于全局固定優(yōu)先級調(diào)度的響應(yīng)時(shí)間分析，其后綴則表示分析方法的不同版本，[native]為文獻(xiàn)[21]的響應(yīng)時(shí)間分析方法，[bc]則是Bertogna和Cirinei提出的改進(jìn)方法[22]，[gn]則是由Guan等所提出的分析方法[23]。WF-DM和WF-EDF表示分組調(diào)度中采用Worst-Fit(WF)算法進(jìn)行任務(wù)分配的可調(diào)度率。其中，DM和EDF分別表示采用單調(diào)截止時(shí)間(Deadline-Monotonic)算法[24]以及最早截止時(shí)間優(yōu)先(Earliest Dealine First, EDF)[2]算法進(jìn)行任務(wù)調(diào)度。圖3所示的各算法可調(diào)度率變化趨勢與相應(yīng)理論分析的結(jié)論一致。

實(shí)驗(yàn)二對多處理器環(huán)境下基于自旋鎖機(jī)制[20]和信號量機(jī)制[25-26]的實(shí)時(shí)鎖協(xié)議作對比實(shí)驗(yàn)，圖例中[spin]為使用自旋鎖機(jī)制的可調(diào)度性測試，[semaphore]則使用了信號量機(jī)制，并使用無共享資源的可調(diào)度性測試[normal]作為最優(yōu)參照組。實(shí)驗(yàn)中所使用的參數(shù)配置與表1保持一致,而對于產(chǎn)生共享資源的主要參數(shù)配置則如表2所示，實(shí)驗(yàn)結(jié)果如圖4所示。

表2 共享資源模型主要參數(shù)Tab. 2 Primary parameters for shared resource model

圖4 包含鎖協(xié)議的分組調(diào)度分析方法對比Fig. 4 Result comparison of some partitioned scheduling analysis methods using locking protocol

4 結(jié)語

本文針對實(shí)時(shí)系統(tǒng)設(shè)計(jì)中的可調(diào)度性分析技術(shù)，提出了一種可調(diào)度性實(shí)驗(yàn)框架，并基于該框架設(shè)計(jì)實(shí)現(xiàn)了一個(gè)新的可調(diào)度性實(shí)驗(yàn)開源平臺SET-MRTS。該平臺基于模塊化設(shè)計(jì)原則，提供了可調(diào)度性實(shí)驗(yàn)所需的完整功能模塊。SET-MRTS是第一個(gè)提供從算法實(shí)施、參數(shù)配置、隨機(jī)實(shí)驗(yàn)、結(jié)果統(tǒng)計(jì)到自動繪圖全過程支持的可調(diào)度性實(shí)驗(yàn)開源平臺。對圖模型分析的支持和異構(gòu)多處理器平臺的可調(diào)度性分析是SET-MRTS下一步的工作重點(diǎn)。

References)

[1] DAVIS R I, BURNS A. A survey of hard real-time scheduling for multiprocessor systems[J]. ACM Computing Surveys, 2011, 43(4):88-87.

[2] LIU C L, LAYLAND J W. Scheduling algorithms for multiprogramming in a hard-real-time environment[J]. Journal of the ACM, 1973, 20(1): 46-61.

[3] KALYANASUNDARAM B, PRUHS K. Speed is as powerful as clairvoyance[J]. Journal of the ACM, 2000, 47(4):617-643.

[4] LEUNG Y T. A new algorithm for scheduling periodic, real-time tasks[J]. Algorithmica, 1989, 4(1):209-219.

[5] BRANDENBURG B B. Improved analysis and evaluation of real-time semaphore protocols for P-FP scheduling[C]// Proceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Sysmposium. Piscataway, NJ: IEEE, 2013: 141-152.

[6] YANG M, WIEDER A, BRANDENBURG B B. Global real-time semaphore protocols: a survey, unified analysis, and comparison[C]// Proceedings of the 2015 IEEE Real-time Systems Symposium. Piscataway, NJ: IEEE, 2015:1-12.

[7] YANG M L, LEI H, LIAO Y, et al. Improved blocking time analysis and evaluation for the multiprocessor priority ceiling protocol[J]. Journal of Computer Science and Technology, 2014, 29(6):1003-1013.

[8] SchedCAT: Schedulability test collection and toolkit[EB/OL]. [2016-08-10].http://www.mpi-sws.org/～bbb/projects/schedcat.

[9] Algorithms: Matlab functions for real-time analysis[EB/OL]. [2016-08-10].http://retis.sssup.it/?q=algorithms.

[10] BONIFACI V, MARCHETTI-SPACCAMELA A. Feasibility analysis of sporadic real-time multiprocessor task systems[J]. Algorithmica, 2010, 63(4):763-780.

[11] BIMI E, BUTTAZZO G C. Measuring the performance of schedulability tests[J]. Real-Time Systems, 2005, 30(1):129-154.

[12] DAVIS R I, BURNS A. Improved priority assignment for global fixed priority preemptive scheduling in multiprocessor real-time systems[J]. Real-Time Systems, 2011, 47(1): 1-40.

[13] YAO-SIM: Yet Another Operating System sIMulator[EB/OL]. [2016-08-10].http://yaosim.sssup.it.

[14] RTSIM: Real-time system simulator[EB/OL]. [2016-08-10].http://rtsim.sssup.it.

[15] PartiCore: Partitioning tool for multi-core reservations[EB/OL]. [2016-08-10].http://particore.sssup.it.

[16] TrueTime: Simulation of networked and embedded control systems [EB/OL]. [2016-08-10].http://www.control.lth.se/attic/truetime.

[17] AUDESLY N, BURNS A, RICHARDSON M, et al. Applying new scheduling theory to static priority pre-emptive scheduling[J]. Software Engineering Journal, 1993, 8(5):284-292.

[18] RAJKUMAR R, SHA L, LEHOCZKY J P. Real-time synchronization protocols for multiprocessors[C]// Proceedings of the 1988 Real-Time Systems Symposium. Piscataway, NJ: IEEE, 1988:259-269.

[19] RAJKUMAR R. Real-time synchronization protocols for shared memory multiprocessors[C]// Proceedings of the 10th International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE, 1990:116-123.

[20] GAI P, LIPARI G, NATALE M D. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip[C]// Proceedings of the 22nd Real-Time Systems Symposium. Washington, DC: IEEE Computer Society, 2001:73-83.

[21] JONSSON J. Some insights on fixed-priority preemptive non-partitioned multiprocessor scheduling[EB/OL].[2016-05-20]. https://users.soe.ucsc.edu/～sbrandt/rtss2000/proceedings/14.pdf.

[22] BERTOGNA M, CIRINEI M. Response-time analysis for globally scheduled symmetric multiprocessor platforms[C]// Proceedings of the 28th IEEE International Real-Time Systems Symposium. Washington, DC: IEEE Computer Society, 2007:149-160.

[23] GUAN N, STIGGE M, YI W, et al. New response time bounds for fixed priority multiprocessor scheduling[C]// Proceedings of the 30th IEEE Real-Time Systems Symposium. Piscataway, NJ: IEEE, 2009: 387-397.

[24] ABDELZAHER T F, SHARMA V, LU C. A utilization bound for aperiodic tasks and priority driven scheduling[J]. IEEE Transactions on Computers, 2004, 53(3):334-350.

[25] CHEN J, NELISSEN G, HUANG W, et al. Many suspensions, many problems: a review of self-suspending tasks in real-time systems[EB/OL].[2016-08-05].http://ls12-www.cs.tu-dortmund.de/daes/media/documents/publications/downloads/2016-chen-techreport-854.pdf.

[26] LAKSHMANAN K, NIZ D, RAJKUMAR R. Coordinated task scheduling, allocation and synchronization on multiprocessors[C]// Proceedings of the 2009 30th IEEE Real-Time Systems Symposium. Washington, DC: IEEE Computer Society, 2009: 469-478.

This work is partially supported by the National Key Technology Research and Development Program of China (2012BAH44F02).

CHEN Zewei, born in 1991, Ph. D. candidate. His research interests include real-time scheduling, embedded system.

YANG Maolin, born in 1987, Ph. D. candidate. His research interests include real-time scheduling, real-time locking protocol, embedded system.

LEI Hang, born in 1960, Ph. D., professor. His research interests include embedded software, software trusted test.

LIAO Yong, born in 1976, Ph. D., associate professor. His research interests include embedded real-time system.

XIE Wei, born in 1971, M. S., senior engineer. His research interests include computer engineering and electronic technology.

SET-MRTS: Schedulability experiment toolkit for multiprocessor real-time systems

CHEN Zewei1*, YANG Maolin1, LEI Hang1, LIAO Yong1, XIE Wei2

(1.SchoolofInformationandSoftwareEngineering,UniversityofElectricityScienceandTechnologyofChina,ChengduSichuan610054,China;2.YunnanResearchInstituteofElecronicIndustry,KunmingYunnan650031,China)

In recent years, the complexity of conducting schedulability experiments increases with the rapid development of real-time scheduling research. In general, schedulability experiments are time-consuming in the absence of standardized and modularized experiment tools. Moreover, since the source codes are not publicly available, it is difficult to verify the reported results in the literature, and to reuse and extend the experiments. In order to reduce the repeative work and help the vertification, a basic schedulability experiment framework was proposed. This experiment framework generated task systems through random distribution, and then tested their schedulability, and based on the framework, a novel open-source schedulability platform called SET-MRTS (Schedulability Experiment Toolkit for Multiprocessor Real-Time Systems) was designed and realized. The platform adopted the modular architecture. SET-MRTS consisted of the task module, the processor module, the shared resource module, the algorithm library, the configuration module and the output module. The experimental results show that, SET-MRTS supports uni-and multi-processor real-time scheduling algorithms and synchronization protocol analyses, which can correctly perform the schedulability test and output intuitive experimental results, and support the expansion of the algorithm library. Compared with algorithms in the algorithms library implemented in the experiment, SET-MRTS has good compatibility and expansibility. SET-MRTS is the first open source platform to support a complete experimental process, including algorithmic implementation, parameter configuration, result statistics, charting, and so on.

real-time and embedded system; multicore system; real-time scheduling; real-time locking protocol; schedulability experiment; open-source platform

2016-11-10;

2016-12-09。 基金項(xiàng)目:國家科技支撐計(jì)劃項(xiàng)目(2012BAH44F02)。

陳澤瑋(1991—)，男，海南文昌人，博士研究生，主要研究方向：實(shí)時(shí)調(diào)度、嵌入式系統(tǒng)； 楊茂林(1987—)，男，四川宜賓人，博士研究生，主要研究方向：實(shí)時(shí)調(diào)度、實(shí)時(shí)鎖協(xié)議、嵌入式系統(tǒng)； 雷航(1960—)，男，四川自貢人，教授，博士，主要研究方向：嵌入式軟件、可信軟件測試； 廖勇(1976—)，男，四川自貢人，副教授，博士，主要研究方向：嵌入式實(shí)時(shí)系統(tǒng)； 謝瑋(1971—)，男，云南昆明人，高級工程師，碩士，主要研究方向：計(jì)算機(jī)及電子技術(shù)。

1001-9081(2017)05-1270-06

10.11772/j.issn.1001-9081.2017.05.1270

TP316.2

A