曹永立，楊茂林，廖　勇

(電子科技大學(xué)信息與軟件工程學(xué)院　成都　610054)

基于MPCP協(xié)議的任務(wù)最壞阻塞時(shí)間分析

曹永立，楊茂林，廖勇

(電子科技大學(xué)信息與軟件工程學(xué)院成都610054)

多處理器天花板協(xié)議(MPCP)是經(jīng)典的基于掛起機(jī)制的實(shí)時(shí)鎖協(xié)議，被廣泛應(yīng)用于分組固定優(yōu)先級(P-FP)調(diào)度下的多核/多處理器實(shí)時(shí)系統(tǒng)中。然而針對P-FP+MPCP調(diào)度的任務(wù)最壞阻塞時(shí)間分析往往過于保守，影響系統(tǒng)的可調(diào)度性。因此，該文提出一種計(jì)算實(shí)時(shí)任務(wù)最壞阻塞時(shí)間的新方法。其中實(shí)時(shí)任務(wù)模擬為非臨界區(qū)與臨界區(qū)的交替序列。該方法通過分析任務(wù)多次請求某一共享資源所需的最短執(zhí)行時(shí)間，以及任務(wù)在任意時(shí)間內(nèi)累計(jì)執(zhí)行臨界區(qū)時(shí)間的上限，提高了已有分析方法的計(jì)算準(zhǔn)確性。可調(diào)度性實(shí)驗(yàn)表明，該方法優(yōu)于已有方法，提高了系統(tǒng)可調(diào)度性。

阻塞;多核;分組調(diào)度;實(shí)時(shí)鎖協(xié)議;實(shí)時(shí)系統(tǒng)

在實(shí)時(shí)系統(tǒng)中，任務(wù)互斥訪問關(guān)鍵數(shù)據(jù)結(jié)構(gòu)、I/O設(shè)備等共享資源時(shí)，需要采用實(shí)時(shí)鎖協(xié)議以避免死鎖、阻塞鏈，同時(shí)減小優(yōu)先級反轉(zhuǎn)所造成的調(diào)度損失。在基于共享內(nèi)存的多處理器實(shí)時(shí)系統(tǒng)中，文獻(xiàn)[1]提出了一種單處理器優(yōu)先級天花板協(xié)議(priority ceiling protocol,PCP)[2]的多處理器天花板協(xié)議(multiprocessor priority ceiling protocol,MPCP)。該協(xié)議適用于分組固定優(yōu)先級(partitioned fixedpriority,P-FP)[3-4]調(diào)度下的多核/多處理器實(shí)時(shí)系統(tǒng)。

為了確保實(shí)時(shí)任務(wù)在其截止時(shí)限內(nèi)完成，需要對任務(wù)的可調(diào)度性進(jìn)行定量分析。在基于P-FP+ MPCP的調(diào)度策略下，可調(diào)度性分析包含任務(wù)最壞阻塞時(shí)間分析。文獻(xiàn)[1]將任務(wù)阻塞分為本地局部資源阻塞、本地全局資源阻塞、遠(yuǎn)程低優(yōu)先級任務(wù)阻塞、遠(yuǎn)程高優(yōu)先級任務(wù)阻塞，以及間接阻塞，并通過計(jì)算各部分阻塞時(shí)間的累加和得到任務(wù)最壞阻塞時(shí)間。由于前兩個(gè)阻塞部分并非相互獨(dú)立，該方法存在重復(fù)計(jì)算問題。文獻(xiàn)[5]將任務(wù)描述為臨界區(qū)與非臨界區(qū)相間的模型，采用響應(yīng)時(shí)間分析法(response time analysis,RTA)[6-8]計(jì)算任務(wù)遠(yuǎn)程阻塞時(shí)間。該方法減小了文獻(xiàn)[1]中的重復(fù)計(jì)算問題，但沒有考慮相鄰臨界區(qū)間的間隔，因此所得的最壞阻塞時(shí)間仍較保守。文獻(xiàn)[3]利用任務(wù)中相鄰臨界區(qū)間的最短時(shí)間間隔，提出了新的任務(wù)最壞時(shí)間分析方法。該方法在相鄰臨界區(qū)最短時(shí)間間隔較大時(shí)可排除文獻(xiàn)[1]中的部分保守計(jì)算，相反則可能得到更壞的結(jié)果。文獻(xiàn)[9]改進(jìn)了文獻(xiàn)[5]中的計(jì)算方法，提高了任務(wù)最壞阻塞響應(yīng)時(shí)間計(jì)算的準(zhǔn)確性。為了進(jìn)一步提高任務(wù)阻塞時(shí)間分析的準(zhǔn)確性，本文結(jié)合文獻(xiàn)[5]的任務(wù)模型以及文獻(xiàn)[9]的RTA分析框架，提出了分析任務(wù)多次請求同一共享資源所需的最短執(zhí)行時(shí)間，以及任務(wù)在任意時(shí)間內(nèi)累計(jì)執(zhí)行臨界區(qū)上限的方法，并基于該分析方法提出一種新的任務(wù)最壞阻塞時(shí)間分析方法。該方法進(jìn)一步減小了分析所得的任務(wù)最壞阻塞時(shí)間，實(shí)驗(yàn)表明，該分析方法可提高實(shí)時(shí)任務(wù)集合的可調(diào)度性。

1　任務(wù)模型

2　任務(wù)請求共享資源時(shí)間分析

令Ni,k表示請求資源的次數(shù)，τi,k,x表示第x次訪問的臨界區(qū)，Si,k,x表示與τi,k,x對應(yīng)的臨界區(qū)編號。如圖1所示，，在其第3個(gè)臨界區(qū)中第2個(gè)請求，因此。從ri,l到第x次請求的最短時(shí)間間隔可由式(1)計(jì)算如下：

圖1 任務(wù)模型示例，非臨界區(qū)段與臨界區(qū)段相互交錯(cuò)

表1 本文變量列表

圖2 從Ji,l第x次請求資源ρk開始，請求n次ρk所需時(shí)間示例

3　任務(wù)最壞阻塞時(shí)間分析

3.1遠(yuǎn)程阻塞時(shí)間

由于各全局資源的優(yōu)先級天花板可能不同，任務(wù)在臨界區(qū)內(nèi)仍可能被搶占。如圖3所示，由于，J2在ρk的臨界區(qū)內(nèi)被J1在t2時(shí)刻搶占，被J3在t3時(shí)刻搶占。根據(jù)文獻(xiàn)[9]，任務(wù)iτ在ρk的臨界區(qū)內(nèi)被其他任務(wù)搶占的最大時(shí)間為：

圖3 遠(yuǎn)程阻塞示例

3.2本地阻塞時(shí)間

在任務(wù)τi就緒前或被遠(yuǎn)程阻塞而掛起時(shí)，其本地低優(yōu)先級任務(wù)可能被調(diào)度執(zhí)行并請求共享資源。當(dāng)?shù)蛢?yōu)先級本地任務(wù)獲得并繼承相應(yīng)資源的優(yōu)先級天花板時(shí)，其有效優(yōu)先級將高于τi，從而發(fā)生優(yōu)先級翻轉(zhuǎn)，延遲τi的執(zhí)行。在實(shí)時(shí)系統(tǒng)中，這種由優(yōu)先級翻轉(zhuǎn)引起的任務(wù)延遲被視作任務(wù)阻塞[10]。如圖4所示，在J1掛起等待全局資源ρk期間，J2和J3相繼請求全局資源ρk并掛起等待。此后，當(dāng)J1執(zhí)行非臨界區(qū)時(shí)，J2和J3的共享資源請求相繼得到滿足，從而阻塞J1。

圖4 本地阻塞示例

令Ni,G為τi的全局臨界區(qū)數(shù)，則τi最多因遠(yuǎn)程阻塞而掛起Ni,G次。此外，由于在τi到達(dá)時(shí)低優(yōu)先級任務(wù)可能已經(jīng)獲得共享資源，因此τi最多可被每個(gè)低優(yōu)先級本地任務(wù)阻塞+ 1次。設(shè)τl為τi的本地低優(yōu)先級任務(wù)，τl只有執(zhí)行臨界區(qū)時(shí)才可能阻塞τi，而在τi就緒后，τl只有在τi掛起期間才有機(jī)會(huì)執(zhí)行其非臨界區(qū)，因此τl在τi就緒期間的執(zhí)行時(shí)間減去τi的遠(yuǎn)程阻塞時(shí)間即為τl對τi的本地阻塞時(shí)間。

設(shè)tx*為Ji,l開始執(zhí)行第個(gè)臨界區(qū)的時(shí)刻，tn*為該任務(wù)從tx*開始到τi第n次進(jìn)入臨界區(qū)的時(shí)刻。令，令表示τi從tx*起執(zhí)行的n個(gè)臨界區(qū)時(shí)間之和。其中，和的計(jì)算方法與定理1和推論2類似(推論1、2針對特定共享資源ρk的臨界區(qū)，而和針對連續(xù)臨界區(qū))。根據(jù)以上分析，。由于因此。從而，在τi的一次執(zhí)行中，其被本地任務(wù)阻塞的時(shí)間上限為：

由于在任務(wù)τi就緒前或被遠(yuǎn)程阻塞而掛起時(shí)，其所有本地低優(yōu)先級任務(wù)均可能先后被調(diào)度執(zhí)行并請求共享資源，因此τi的本地阻塞時(shí)間不大于所有本地低優(yōu)先級任務(wù)對請求造成的最大阻塞之和，即：

4　可調(diào)度性實(shí)驗(yàn)

本節(jié)實(shí)驗(yàn)在Microsoft VS平臺上進(jìn)行，根據(jù)UUnifast-Discard算法[11]隨機(jī)產(chǎn)生任務(wù)集合。其中，任務(wù)周期在[200,1 000]內(nèi)服從均勻分布，ui在[0.05,0.2]內(nèi)隨機(jī)產(chǎn)生，Ci根據(jù)任務(wù)CPU利用率定義由ui與Ti決定。每個(gè)任務(wù)有x∈[1,10]個(gè)臨界區(qū)，各臨界區(qū)長度y∈[0.5,8]。系統(tǒng)中有q=20個(gè)共享資源，任務(wù)各臨界區(qū)訪問各共享資源的概率均等，且每個(gè)任務(wù)集合中最多有20個(gè)任務(wù)訪問同一個(gè)共享資源。

將以上所得任務(wù)集合按照Worst-Fit算法(以避免任務(wù)分配故障問題[12])進(jìn)行任務(wù)分配(本文模擬m=8核處理器)，并采用Raj[1]、KDR[5]、YLLH[9]，以及本文提出的方法(Proposed)計(jì)算任務(wù)最壞阻塞時(shí)間。根據(jù)各方法所得最壞阻塞時(shí)間，采用文獻(xiàn)[5]的RTA方法分析任務(wù)集合的可調(diào)度性。每次實(shí)驗(yàn)隨機(jī)產(chǎn)生h=5 000個(gè)任務(wù)集合，分別計(jì)算以上4種分析方法的可調(diào)度率α。其中，可調(diào)度率計(jì)算方法如下：設(shè)一次實(shí)驗(yàn)隨機(jī)產(chǎn)生c個(gè)任務(wù)集合，其中由分析方法A得出有g(shù)個(gè)任務(wù)集合可調(diào)度，則方法A的可調(diào)度率為α=g/ c 。由于以上各方法的所得的任務(wù)最壞阻塞時(shí)間不相同，而實(shí)驗(yàn)中采用了相同的可調(diào)度分析算法，因此，實(shí)驗(yàn)結(jié)果中各方法的可調(diào)度率反映了最壞阻塞時(shí)間的差異對的系統(tǒng)可調(diào)度性的影響。可調(diào)度率越高的方法，其分析所得的最壞阻塞時(shí)間越小。

圖5中，每個(gè)任務(wù)有4個(gè)臨界區(qū)，臨界區(qū)長度為1.5。該實(shí)驗(yàn)顯示，各方法的可調(diào)度率均隨系統(tǒng)利用率增加而下降，其中新方法的可調(diào)度率高于其余方法。新方法通過計(jì)算任務(wù)執(zhí)行多個(gè)臨界區(qū)所需的執(zhí)行時(shí)間下限以及在任意時(shí)間內(nèi)執(zhí)行臨界區(qū)的時(shí)間上限，將給定時(shí)間內(nèi)不可能發(fā)生的阻塞時(shí)間排除在分析所得的最壞阻塞時(shí)間以外。而其余方法對任務(wù)在某段具體時(shí)間內(nèi)是否會(huì)發(fā)生任務(wù)阻塞不敏感，使得分析結(jié)果較保守。

圖5 x = 4，y = 1.5時(shí)α與U的關(guān)系

圖6 x = 4，U = 4時(shí)α與y的關(guān)系

圖6中，系統(tǒng)利用率為4，每個(gè)任務(wù)有4個(gè)臨界區(qū)。由于任務(wù)阻塞時(shí)間隨臨界區(qū)長度增加而增加，各分析方法的可調(diào)度率均隨臨界區(qū)長度增加而下降。當(dāng)y≤3.5時(shí)Proposed的可調(diào)度率為1；而在y=3.5時(shí)，YLLH與KDR的可調(diào)度率分別約為0.62和0.03，Raj為0。當(dāng)y＞3.5時(shí)，Proposed的可調(diào)度率下降速度低于其余方法。圖7中，系統(tǒng)利用率為4.5，任務(wù)臨界區(qū)長度為1.5。隨任務(wù)的臨界區(qū)數(shù)增加，任務(wù)在最壞情況下被阻塞的次數(shù)隨之增加，從而降低了可調(diào)度率。其中，各方法的α值隨x的變化趨勢與圖6相似，Proposed的可調(diào)度率明顯高于其余方法。

圖7 y = 1.5，U = 4.5時(shí)α與x的關(guān)系

5　結(jié) 束 語

本文針對P-FP+MPCP調(diào)度，采用文獻(xiàn)[5]的任務(wù)模型，將任務(wù)模擬為非臨界區(qū)與臨界區(qū)的交替序列，并對任務(wù)訪問共享資源的時(shí)間關(guān)系進(jìn)行定量分析。通過分析得出任務(wù)在任意時(shí)間內(nèi)執(zhí)行臨界區(qū)段的時(shí)間之和，從而得出任意任務(wù)在給定時(shí)間內(nèi)對其他任務(wù)造成的最大阻塞。在此基礎(chǔ)上，結(jié)合文獻(xiàn)[9]的阻塞時(shí)間分析框架，提出一種新的任務(wù)最壞阻塞時(shí)間分析方法。可調(diào)度性實(shí)驗(yàn)結(jié)果顯示，新的分析方法明顯優(yōu)于已有方法，提高了系統(tǒng)的可調(diào)度性。

本文的研究工作得到華為基金(IRP- 2012-02-07)及開源項(xiàng)目www.aCoral.org的資助，在此表示感謝。

[1]RAJKUMAR R. Real-time synchronization protocols for shared memory multiprocessors[C]//IEEE International Conference on Distributed Computing Systems. Paris: IEEE,1990: 116-123.

[2]SHA L,RAJKUMAR R,LEHOCZKY J. Priority inheritance protocols: an approach to real-time synchronization[J]. IEEE Transactions on Computers,1990,39(9): 1175-1185.

[3]SCHLIECKER S,NEGREAN M,ERNST R. Response time analysis on multicore ECUs with shared resources[J]. IEEE Transactions on Industrial Informatics,2009,5(4): 402-413.

[4]BRANDENBURG B. Improved analysis and evaluation of real-time semaphore protocols for P-FP scheduling[C]// IEEE International Conference on Real-Time Embedded Technology and Application Symposium. Philadelphia: IEEE,2013: 141-152.

[5]LAKSHMANAN K,NIZ D,RAJKUMAR R. Coordinated task scheduling,allocation and synchronization on multiprocessors[C]//IEEE International Conference on Real-Time System Symposium. Washington D. C: IEEE,2009: 469-478.

[6]AUDSLEY N,BURNS A,RICHARDSON M,et al. Applying new scheduling theory to static priority preemptive scheduling[J]. Journal of Software Engineering,1993,8(5): 284-296.

[7]BINI E,BUTTAZZO G. Schedulability analysis of periodic fixed priority systems[J]. IEEE Transactions on Computers,2004,53(11): 1462-1473.

[8]BRIL R,LUKKIEN J,VERHAEGH W. Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption[J]. Real-Time Systems,2009,42(1-3): 63-119.

[9]YANG Mao-lin,LEI Hang,LIAO Yong. Synchronization analysis for hard real-time multicore systems[J]. Applied Mechanics and Materials,2012,241-244: 2246-2253.

[10]BRANDENBURG B,ANDERSON J. Optimality results for multi-processor real-time locking[C]//IEEE International Conference on Real-Time Systems Symposium. San Diego: IEEE,2010: 49-60.

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

[12]劉加海,楊茂林,雷航,等. 共享資源約束下多核實(shí)時(shí)任務(wù)分配算法研究[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版),2014,48(1): 113-117. LIU Jia-hai,YANG Mao-lin,LEI Hang,et al. A research for multicore real-time task allocation algorithms[J]. Journal of Zhejiang University(Engineering Science),2014,48(1): 113-117.

編輯蔣曉

Worst-Case Blocking Time Analysis for MPCP

CAO Yong-li,YANG Mao-lin,and LIAO Yong
(School of Information and Software Engineering,University of Electronic Science and Technology of ChinaChengdu610054)

Multiprocessor priority ceiling protocol (MPCP)is a classical suspension-based real-time locking protocol,wildly used in partitioned fixed-priority (P-FP)scheduled multiprocessor/multicore real-time systems. However,prior worst-case task blocking time (WCTBT)analysis is pessimistic,which negatively impacts the system schedulability. Therefore,a novel WCTBT analysis is proposed. In this analysis,a task is modeled to be an alternative sequence of normal and critical section segments. By analyzing the minimum execution time required for a task to request several shared resources,this method improves the accuracy of prior work and provides an upper bound on the cumulative execution time for a task to execute critical sections in any time interval. Schedulability experiments indicate that the proposed method outperforms the existing methods and improves the system schedulability significantly.

blocking;multicores;partitioned scheduling;real-time locking protocols;real-time systems

TP301.6

A

10.3969/j.issn.1001-0548.2016.06.022

2015 ? 03 ? 14；

2015 ? 12 ? 26

國家自然科學(xué)基金(61103041)；國家863重大項(xiàng)目(2012AA010904)；中央高?；究蒲袠I(yè)務(wù)費(fèi)(ZYGX2012J070)

曹永立(1992 ? )，男，主要從事信息工程方面的研究.