Title :
Queuing spin lock algorithms to support timing predictability
Author :
Craig, Travis S.
Author_Institution :
Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
Abstract :
We introduce practical new algorithms for FIFO and priority-ordered spin locks on shared-memory multiprocessors with an atomic swap instruction. Different versions of these queuing spin locks are designed for machines with coherent-cache and NUMA memory models. We discuss extensions to provide nested lock acquisition, conditional locking, timeout of lock requests, and preemption waiters. These locks support predictable timing in the lowest kernel and user levels of time-line-scheduled and priority-scheduled real-time systems
Keywords :
cache storage; operating systems (computers); parallel algorithms; processor scheduling; real-time systems; scheduling; shared memory systems; FIFO; NUMA memory models; atomic swap instruction; coherent-cache; conditional locking; kernel; lock requests; nested lock acquisition; predictable timing; preemption waiters; priority-ordered spin locks; priority-scheduled real-time systems; queuing spin lock algorithms; queuing spin locks; shared-memory multiprocessors; time-line-scheduled; timeout; timing predictability; user levels; Computer science; Control systems; Hardware; Kernel; Multiprocessor interconnection networks; Real time systems; Resource management; Spinning; Testing; Timing;
Conference_Titel :
Real-Time Systems Symposium, 1993., Proceedings.
Conference_Location :
Raleigh Durham, NC
Print_ISBN :
0-8186-4480-X
DOI :
10.1109/REAL.1993.393505
