We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 29 Issue 6
November  2014
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Mao-Lin Yang, Hang Lei, Yong Liao, Furkan Rabee. Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol[J]. Journal of Computer Science and Technology, 2014, 29(6): 1003-1013. DOI: 10.1007/s11390-014-1485-y
Citation: Mao-Lin Yang, Hang Lei, Yong Liao, Furkan Rabee. Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol[J]. Journal of Computer Science and Technology, 2014, 29(6): 1003-1013. DOI: 10.1007/s11390-014-1485-y
shu

Improved Blocking Time Analysis and Evaluation for the Multiprocessor Priority Ceiling Protocol

  • 1 School of Information and Software Engineering, University of Electronic Science and Technology of China Chengdu 611731, China;
    2 School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731 China

Funds: This work was supported by the National Natural Science Foundation of China under Grant No. 61103041, the National High Technology Research and Development 863 Program of China under Grant No. 2012AA010904, the Fundamental Research Funds for the Central Universities of China under Grant No. ZYGX2012J070, the Huawei Technology Foundation under Grant No. IRP-2012-02-07, and the Excellent Ph.D. Student Academic Support Program of UESTC under Grant No. YBXSZC20131028.
More Information
  • Author Bio:

    Mao-Lin Yang is a Ph.D. candidate in the School of Information and Software Engineering from the University of Electronic Science and Technology of China (UESTC), Chengdu. He received his B.S. degree in light chemical engineering from Tianjin University of Science and Technology in 2009, and M.S. degree in software engineering from Zhejiang University in 2011. His research interests include real-time scheduling algorithms, real-time locking protocols, and real-time operating systems. He is a student member of IEEE.

  • Received Date: September 07, 2013
  • Revised Date: July 08, 2014
  • Published Date: November 04, 2014
    Abstract
  • The Multiprocessor Priority Ceiling Protocol (MPCP) is a classic suspension-based real-time locking protocol for partitioned fixed-priority (P-FP) scheduling. However, existing blocking time analysis is pessimistic under the P-FP + MPCP scheduling, which negatively impacts the schedulability for real-time tasks. In this paper, we model each task as an alternating sequence of normal and critical sections, and use both the best-case execution time (BCET) and the worst-case execution time (WCET) to describe the execution requirement for each section. Based on this model, a novel analysis is proposed to bound shared resource requests. This analysis uses BCET to derive the lower bound on the inter-arrival time for shared resource requests, and uses WCET to obtain the upper bound on the execution time of a task on critical sections during an arbitrary time interval of △t. Based on this analysis, improved blocking analysis and its associated worst-case response time (WCRT) analysis are proposed for P-FP + MPCP scheduling. Schedulability experiments indicate that the proposed method outperforms the existing methods and improves the schedulability significantly.
    • FullText(HTML)
    • References (15)
  • [1]
    Gracioli G, Fröhlich A, Pellizzoni R, Fischmeister S. Implementation and evaluation of global and partitioned scheduling in a real-time OS. Real-Time Syst., 2013, 49(6): 669-714.
    [2]
    Brandenburg B. Scheduling and locking in multiprocessor real-time operating systems [Ph.D. Thesis]. The University of North Carolina at Chapel Hill, 2011.
    [3]
    Brandenburg B, Calandrino J, Block A, Leontyev H, Anderson J. Real-time synchronization on multiprocessor: To block or not to block, to suspend or spin? In Proc. the 14th IEEE Real-Time Embedded Tec. App. Symp., April 2008, pp.342353.
    [4]
    Ras J, Cheng A. An evaluation of the dynamic and static multiprocessor priority ceiling protocol and the multiprocessor stack resource policy in an SMP systems. In Proc. the 15th IEEE RTAS, April 2009, pp.13-22.
    [5]
    Rajkumar R. Real-time synchronization protocols for shared memory multiprocessors. In Proc. the 10th Int. Conf. Dist. Computing Syst., May 28-Jun. 1, 1990, pp.116-123.
    [6]
    Block A, Leontyev H, Brandenburg B, Anderson J. A flexible real-time locking protocol for multiprocessors. In Proc. the 13th IEEE RTCSA, August 2007, pp.47-56.
    [7]
    Brandenburg B, Anderson J. Optimality results for multiprocessor real-time locking. In Proc. the 31st IEEE RealTime Syst. Symp., Nov. 30-Dec. 3, 2010, pp.49-60.
    [8]
    Sha L, Rajkumar R, Lehoczky J. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Computers, 1990, 39(9): 1175-1185.
    [9]
    Lakshmanan K, De Niz D, Rajkumar R. Coordinated task scheduling, allocation and synchronization on multiprocessors. In Proc. the 30th IEEE Real-Time Syst. Symp., Dec. 2009, pp.469-478.
    [10]
    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 Syst., 2009, 42(1/2/3): 63-119.
    [11]
    Bertogna M, Baruah S. Limited preemption EDF scheduling of sporadic task systems. IEEE Trans. Industrial Informatics, 2010, 6(4): 579-591.
    [12]
    Schliecker S, Negrean M, Ernst R. Response time analysis on multicore ECUs with shared resources. IEEE Trans. Industrial Informatics, 2009, 5(4): 402-413.
    [13]
    Brandenburg B. Improved analysis and evaluation of real-time semaphore protocols for P-FP scheduling. In Proc. the 19th IEEE RTAS, April 2013, pp.141-152.
    [14]
    Ridouard F, Richard P, Cottet F. Negative results for scheduling independent hard real-time tasks with self-suspensions. In Proc. the 25th IEEE Real-Time Syst. Symp., December 2004, pp.47-56.
    [15]
    Liu C, Layland J. Scheduling algorithms for multiprogramming in a hard real-time environment. J. ACM, 1973, 20(1): 46-61.
    • Relative Articles

  • Related Articles

    [1]Xiao-Tong Cui, Kai-Jie Wu, Tong-Quan Wei, Edwin Hsing-Mean Sha. Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults[J]. Journal of Computer Science and Technology, 2016, 31(2): 267-283. DOI: 10.1007/s11390-016-1626-6
    [2]Jason Cong, Henry Duwe, Rakesh Kumar, Sen Li. Better-Than-Worst-Case Design：Progress and Opportunities[J]. Journal of Computer Science and Technology, 2014, 29(4): 656-663. DOI: 10.1007/s11390-014-1457-2
    [3]Pin-Yan Lu, Chang-Yuan Yu. Worst-Case Nash Equilibria in Restricted Routing[J]. Journal of Computer Science and Technology, 2012, 27(4): 710-717. DOI: 10.1007/s11390-012-1257-5
    [4]Xiao-Dong Wang, Ying-Jie Wu. An Improved HEAPSORT Algorithm with n log n - 0.788928n Comparisons in the Worst Case[J]. Journal of Computer Science and Technology, 2007, 22(6): 898-903.
    [5]Sheng-En Li, Shan Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time[J]. Journal of Computer Science and Technology, 2005, 20(3): 367-372.
    [6]JIANG Tao, LI Ming, Paul M.B. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5): 402-408.
    [7]SHI Weisong, HU weiwu, TANG Zhimin. Where Does the Time Go in Software DSMs?—Experiences with JIAJIA[J]. Journal of Computer Science and Technology, 1999, 14(3): 193-205.
    [8]Li Weihua, Yuan Youguang. Error Recovery in a Real-Time Multiprocessor System[J]. Journal of Computer Science and Technology, 1992, 7(1): 83-87.
    [9]Zhang Bo, Zhang Ling. An Algorithm for Finding D-Time Table[J]. Journal of Computer Science and Technology, 1992, 7(1): 62-67.
    [10]Zhang Zhongyun, Zhu Mingfa, Li Jie. Partitioning of Independent Tasks for Minimizing Completion Time and Total Waiting Time[J]. Journal of Computer Science and Technology, 1991, 6(3): 276-281.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (34) PDF downloads (2295) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return