On the Design and Implementation of Real-Time Resource Access Protocols

• Lucas Matheus dos Santos UFSC
• Giovani Gracioli UFSC
• Tomasz Kloda Technical University of Munich
• Marcos Caccamo Technical University of Munich

Resumo

Real-time operating systems (RTOS) should support resource access protocols to bound the maximum delay incurred by priority inversions. The implementation of such protocols must be lightweight because its performance affects the system schedulability. In this paper, we present an object-oriented design of real-time resource access protocols for single- and multi-core systems aiming at reducing the run-time overhead and increasing code re-usability. We implement the proposed design in an RTOS and measure the memory footprint and run-time overhead of the implementation in a modern processor. By applying the obtained overhead into the schedulability analysis of six protocols for synthetically generated task sets, our results indicate that proper implementation of resource access protocols has a low impact on the schedulability of real-time tasks.

Palavras-chave: Real-time resource access protocols, real-time operating systems, priority ceiling protocol, priority inheritance protocol, stack resource policy

Referências

J. Liu Real-Time Systems Upper Saddle River NJ USA:Prentice Hall PTR 2000.

G. C. Buttazzo Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications Springer 2011.

M. Yang A. Wieder and B. Brandenburg "Global real-time semaphore protocols: A survey unified analysis and comparison" RTSS pp. 1-12 2015.

M. Jones What really happened on mars? Dec 1997.

L. Sha R. Rajkumar and J. P. Lehoczky "Priority inheritance protocols: an approach to real-time synchronization" IEEE Transactions on Computers vol. 39 no. 9 pp. 1175-1185 Sep 1990.

T. P. Baker "Stack-based scheduling for realtime processes" Real-Time Syst. vol. 3 no. 1 pp. 67-99 Apr. 1991.

R. Rajkumar "Real-time synchronization protocols for shared memory multiprocessors" 10th ICDCS pp. 116-123 May 1990.

P. Gai G. Lipari and M. Di "Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip" 22nd IEEE RTSS pp. 73-83 2001.

S. K. Dhall and C. L. Liu "On a real-time scheduling problem" Oper. Res. vol. 26 no. 1 pp. 127-140 Feb. 1978.

J. M. Lopez M. Garcia J. L. Diaz and D. F. Garcia "Worst-case utilization bound for edf scheduling on real-time multiprocessor systems" 12th ECRTS pp. 25-33 2000.

E. W. Dijkstra "Cooperating sequential processes" in Programming Languages: NATO Advanced Study Institute Academic Press pp. 43-112 1968.

EPOS Aug 2020 [online] Available: http://epos.lisha.ufsc.br.

G. Gracioli A. A. Fröhlich R. Pellizzoni and S. Fischmeister "Implementation and evaluation of global and partitioned scheduling in a real-time OS" Real-Time Systems vol. 49 no. 6 2013.

A. Biondi and B. B. Brandenburg "Lightweight real-time synchronization under p-edf on symmetric and asymmetric multiprocessors" Proc. of the ECRTS 2016 pp. 1-11 2016.

K. Lakshmanan D. d. Niz and R. Rajkumar "Coordinated task scheduling allocation and synchronization on multiprocessors" 2009 30th IEEE Real-Time Systems Symposium pp. 469-478 2009.

L. Liu and J. W. Layland "Scheduling algorithms for multiprogramming in a hard-real-time environment" J. ACM vol. 20 no. 1 pp. 46-61 1973.

Schedcat: Schedulability test collection and toolkit Aug 2020 [online] Available: http://www.mpi-sws.org/bbb/projects/schedcat.

Freertos Jul 2016 [online] Available: http://www.freertos.org/.

R. Inam J. Mäki-Turja M. Sjödin and M. Behnam "Hard real-time support for hierarchical scheduling in freertos" OSPERT pp. 51-60 2011.

B. B. Brandenburg and J. H. Anderson "An implementation of the pcp srp d-pcp m-pcp and fmlp real-time synchronization protocols in litmusrt" in 14th IEEE RTCSA USA pp. 185-194 2008.

J. Liedtke "On micro-kernel construction" 15th SOSP. ACM pp. 237-250 1995.

J.-H. Lee and H.-N. Kim "Implementing priority inheritance semaphore on uc/os real-time kernel" IEEE Workshop on Software Technologies for Future Embedded Systems 2003 pp. 83-86 May 2003.

Q. Wang J. Song and G. Parmer "Execution stack management for hard real-time computation in a component-based os" IEEE 32nd RTSS pp. 78-89 Nov 2011.

M. Caccamo G. Lipari and G. Buttazzo "Sharing resources among periodic and aperiodic tasks with dynamic deadlines" Proc. 20th IEEE RTSS pp. 284-293 1999.

A. Burns and A. J. Wellings "A schedulability compatible multiprocessor resource sharing protocol - mrsp" ECRTS pp. 282-291 July 2013.

A. Block H. Leontyev B. B. Brandenburg and J. H. Anderson "A flexible real-time locking protocol for multiprocessors" 13th IEEE RTCSA pp. 47-56 Aug 2007.

A. Easwaran and B. Andersson "Resource sharing in global fixed-priority preemptive multiprocessor scheduling" 30th RTSS pp. 377-386 2009.

R. Teixeira and G. Lima "Improved task packing for shared resources in multiprocessor real-time systems scheduled by run under sblp" 2019 IX Brazilian Symposium on Computing Systems Engineering (SBESC) pp. 1-8 2019.

P. Regnier G. Lima E. Massa G. Levin and S. Brandt "Run: Optimal multiprocessor real-time scheduling via reduction to uniprocessor" 2011 IEEE 32nd Real-Time Systems Symposium pp. 104-115 2011.

B. B. Brandenburg "Multiprocessor real-time locking protocols: A systematic review" CoRR vol. abs/1909.09600 2019.

J. Robb and B. B. Brandenburg "Nested but separate: Isolating unrelated critical sections in real-time nested locking" 32nd ECRTS pp. 6:1-6:23 2020.

C. E. Nemitz T. Amert and J. H. Anderson "Using Lock Servers to Scale Real-Time Locking Protocols: Chasing Ever-Increasing Core Counts" 30th ECRTS pp. 25:1-25:24 2018.