Fair and Starvation-Free Spinlock for Real-Time AUTOSAR systems: M-HLP
Pages 436 - 445
Abstract
We present in this paper, a fair and starvation-free spin-lock protocol for partitioned fixed priority (P-FP) preemptive multi-core real-time operating systems (mRTOS). We discuss some strongly related works in this regard and highlight the drawbacks with respect to the AUTOSAR standards. We then proceed to define a system model and develop a mathematical framework to calculate an upper bound on the blocking time a task incurs under our protocol. We also discuss how our protocol was implemented in a state-of-the-art AUTOSAR-compliant mRTOS. Finally, through experimental evaluation, we show that our protocol performs better than the existing spinlock protocol of the mRTOS.
References
[1]
AUTOSAR Specification of Operating System. https://bit.ly/3kFJ4SC. Accessed January 2023.
[2]
A. Wieder and B. B. Brandenburg. 2013. On Spin Locks in AUTOSAR: Blocking Analysis of FIFO, Unordered, and Priority-Ordered Spinlocks. RTSS '13.
[3]
Wieder, A. "Blocking analysis of spin locks under partitioned fixed-priority scheduling." Ph.D. dissertation, Saarland University, 2018.
[4]
Brandenburg, B & Anderson, J & Baruah, S & Härtig, H & Prins, J & Donelson, F & Paul, S & Mckenney, E. (2012). B. B. BRANDENBURG: Scheduling and Locking in Multiprocessor Real-Time Operating Systems.
[5]
R. Rajkumar, "Real-time synchronization protocols for shared memory multiprocessors," ICDCS, Paris, France, 1990
[6]
K. Lakshmanan, D. de Niz and R. Rajkumar, "Coordinated Task Scheduling, Allocation and Synchronization on Multiprocessors," RTSS'09.
[7]
S. Afshar, M. Behnam, R. J. Bril and T. Nolte, "Flexible spin-lock model for resource sharing in multiprocessor real-time systems," SIES'14.
[8]
David P. Reed & Rajendra K. Kanodia. 1979. Synchronization with eventcounts and sequencers. Commun. ACM, Feb. 1979.
[9]
J. Mellor-Crummey & M. Scott, "Algorithms for scalable synchronization on shared-memory multiprocessors," ACM Trans. Comp. Sys '91.
[10]
M. Coutinho, J. Rufino and C. Almeida, "Response Time Analysis of Asynchronous Periodic and Sporadic Tasks Sheduled by a Fixed Priority Preemptive Algorithm," ECRTS'08.
[11]
J. Lehoczky, L. Sha and Y. Ding, "The rate monotonic scheduling algorithm: exact characterization and average case behavior," RTSS'89.
[12]
L. Sha, R. Rajkumar & J. P. Lehoczky, "Priority inheritance protocols: an approach to real-time synchronization," in IEEE Trans on Computers '90.
[13]
J. Peleska et al. A Real-world Benchmark Model for Testing Concurrent Real-time Systems in the Automotive Domain. ICTSS'11.
[14]
Leonidas I. Kontothanassis, Robert W. Wisniewski, and Michael L. Scott. Scheduler-conscious synchronization. ACM Trans. Comput. Syst. 1997.
[15]
M. Alfranseder, M. Deubzer, B. Justus, J. Mottok and C. Siemers, "An efficient spin-lock based multi-core resource sharing protocol," IPCCC'14.
[16]
A. Block, H. Leontyev, B. B. Brandenburg, and J. H. Anderson, "A Flexible Real-Time Locking Protocol for Multiprocessors," RTCSA'12.
[17]
Baker, T. A stack-based resource allocation policy for realtime processes. RTSS'91.
[18]
P. Gai, G. Lipari, and M. Di Natale. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. RTSS'01.
[19]
D. Griffin, I. Bate & R. I. Davis, "Generating Utilization Vectors for the Systematic Evaluation of Schedulability Tests," RTSS'20.
[20]
TC38x 32-Bit Single-Chip Microcontroller. Infineon Technologies AG. https://shorturl.at/hiDEJ. Accessed March 2023.
[21]
D. Griffin, I. Bate, and R. I. Davis. Dirichlet-Rescale (DRS) algorithm software
[22]
Davis, Robert & Griffin, David & Bate, Iain. A Framework for Multi-core Schedulability Analysis Accounting for Resource Stress and Sensitivity. Real-Time Syst'22.
[23]
Emberson, P. & Stafford, R. & Davis, R.I. (2010). Techniques For The Synthesis Of Multiprocessor Tasksets. WATERS'10.
[24]
Min-Allah, N., Khan, S.U., Ghani, N. et al. A comparative study of rate monotonic schedulability tests. J Supercomput '12.
Index Terms
- Fair and Starvation-Free Spinlock for Real-Time AUTOSAR systems: M-HLP
Recommendations
The lock holder and the lock waiter pre-emption problems: nip them in the bud using informed spinlocks (I-Spinlock)
EuroSys '17: Proceedings of the Twelfth European Conference on Computer SystemsIn native Linux systems, spinlock's implementation relies on the assumption that both the lock holder thread and lock waiter threads cannot be preempted. However, in a virtualized environment, these threads are scheduled on top of virtual CPUs (vCPU) ...
On Spin Locks in AUTOSAR: Blocking Analysis of FIFO, Unordered, and Priority-Ordered Spin Locks
RTSS '13: Proceedings of the 2013 IEEE 34th Real-Time Systems SymposiumMotivated by the widespread use of spin locks in embedded multiprocessor real-time systems, the worst-case blocking in spin locks is analyzed using mixed-integer linear programming. Four queue orders and two preemption models are studied: (i) FIFO-...
Starvation-Free Monitors
Theoretical Aspects of Computing – ICTAC 2019AbstractMonitors are a synchronization construct which allows to keep a thread waiting until a specific resource for that thread is available. One potential problem with these constructs is starvation; a situation where a thread, competing for a resource, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2024
1898 pages
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 May 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SAC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 100Total Downloads
- Downloads (Last 12 months)100
- Downloads (Last 6 weeks)60
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in