Spinlock

from Wikipedia, the free encyclopedia

A spinlock (spin lock) is a mechanism for process synchronization . There is a lock ( lock ) for protecting a shared resource by competing processes or threads (see Critical section ) according to the principle of mutual exclusion ( mutex ).

implementation

The block is implemented by means of active waiting : 

 // Eintrittsprotokoll
 solange (Sperrvariable besitzt Wert 'gesperrt') { //   \
    tue nichts;                                    //   | Achtung! Hier:
 }                                                 //   | Atomares Vergleichen und Setzen
 setze Sperrvariable auf 'gesperrt'                //   /

 // Kritischer Abschnitt
 modifiziere Ressource

 // Austrittsprotokoll
 setze Sperrvariable auf 'frei'

At the beginning the lock variable has the value free . All processes run through the same protocol for entry into a critical section: If the lock variable is free , set it to locked , otherwise check this again (active waiting). The checking and setting is done atomically and is implemented differently depending on the processor architecture (see Fetch-and-add , Compare-and-swap or Test-and-set ).

The process that sets the lock tag to locked is called the "owner" of the lock tag.

advantages

The method avoids context changes , which are very time-consuming. If the waiting time for a lock to be released is on average shorter than a context change, then spinlocks are faster than alternative mutexes despite their additional runtime . This increases the effective parallelism in some cases considerably compared to thread-changing synchronization mechanisms and is therefore a frequently encountered procedure with heavily concurrent algorithms (e.g. in the Linux kernel ).

disadvantage

Active waiting requires runtime . A spinlock can slow program execution considerably if there are more threads than processor cores.

Depending on the scheduling method, the use of spinlocks can also lead to deadlocks . This results from the fact that a spinlock does not suspend the active thread, but rather actively waits for the lock variable ( i.e. remains running ) and thus hinders other threads that are ready to run . The following example illustrates the problem: In a single-processor system with two threads, a spinlock is successfully blocked by a thread L with low priority. Shortly afterwards (and before the release of the spin lock by thread L), a thread H with high priority becomes executable by an event and activated by the scheduler . Thread H now also tries to lock the spinlock and thus gets into active waiting. In the case of a scheduling method without time slicing , this results in a deadlock, since thread L cannot run again and can no longer release the spinlock. Using a synchronization mechanism with thread switching would have prevented the deadlock in this example.

literature

  • Sándor Juhász, Ákos Dudás, Tamás Schrádi: Cost of mutual exclusion with spin locks on multi-core CPUs . In: Proceedings of the 5th WSEAS congress on Applied Computing conference, and Proceedings of the 1st international conference on Biologically Inspired Computation (=  BICA'12 ). World Scientific and Engineering Academy and Society (WSEAS), Stevens Point WI 2012, ISBN 978-1-61804-089-3 , pp. 15-19 ( acm.org - Conference Paper).
  • Mordechai Ben-Ari: Principles of Concurrent and Distributed Programming: Algorithms and Models (=  Prentice-Hall International Series in Computer Science ). 2nd Edition. Addison-Wesley, 2005, ISBN 978-0-321-31283-9 .
  • James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986 . In: Distrib. Comput. tape 16 , no. 2-3 . Springer-Verlag, September 2003, ISSN  0178-2770 , p. 75-110 , doi : 10.1007 / s00446-003-0088-6 .
  • M. Raynal, D. Beeson: Algorithms for mutual exclusion . MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3 .

Individual evidence

  1. ↑ Lesson 1: Spin locks . Page maintained by Rob Landley, rob at landley dot net. August 12, 2013. Retrieved November 4, 2013.