Queuing spin lock algorithms to support timing predictability

Author

Craig, Travis S.

Author_Institution

Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA

fYear

1993

fDate

1-3 Dec 1993

Firstpage

148

Lastpage

157

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Real-Time Systems Symposium, 1993., Proceedings.

Conference_Location

Raleigh Durham, NC

Print_ISBN

0-8186-4480-X

Type

conf

DOI

10.1109/REAL.1993.393505

Filename

393505