LFthreads : A Lock-Free Thread Library
LFthreads is a thread library entirely based on lock-free methods, i.e. no spin-locks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lock-freedom is highly desirable in multiprocessors/multicores due
- PDF / 361,159 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 46 Downloads / 208 Views
2
Algorithms and Complexity, Max-Planck-Institut f¨ur Informatik, 66123 Saarbrcken, Germany [email protected] Computer Science and Engineering, Chalmers University of Technology, SE-412 96 G¨oteborg, Sweden [email protected]
Abstract. LF THREADS is a thread library entirely based on lock-free methods, i.e. no spin-locks or similar synchronization mechanisms are employed in the implementation of the multithreading. Since lock-freedom is highly desirable in multiprocessors/multicores due to its advantages in parallelism, fault-tolerance, convoy-avoidance and more, there is an increased demand in lock-free methods in parallel applications, hence also in multiprocessor/multicore system services. This is why a lock-free multithreading library is important. To the best of our knowledge LF THREADS is the first thread library that provides a lock-free implementation of blocking synchronization primitives for application threads. Lock-free implementation of objects with blocking semantics may sound like a contradicting goal. However, such objects have benefits: e.g. library operations that block and unblock threads on the same synchronization object can make progress in parallel while maintaining the desired thread-level semantics and without having to wait for any “slow” operations among them. Besides, as no spin-locks or similar synchronization mechanisms are employed, processors are always able to do useful work. As a consequence, applications, too, can enjoy enhanced parallelism and fault-tolerance. The synchronization in LF THREADS is achieved by a new method, which we call responsibility hand-off (RHO), that does not need any special kernel support. Keywords: lock-free, multithreading, multiprocessors, multicores, synchronization, shared memory.
1 Introduction Multiprogramming and threading allow the processor(s) to be shared efficiently by several sequential threads of control. This paper studies synchronization algorithms for realizing standard thread-library operations and objects (create, exit, yield and mutexes) based entirely on lock-free methods. Lock-freedom implies that no spin-locks or similar locking synchronization is used in the implementation of the operations/objects and guarantees that in a set of concurrent operations at least one of them makes progress when there is interference and thus operations eventually completes. The rationale in LF THREADS is that processors should always be able to do useful work when there are runnable threads available, regardless of what other processors do; E. Tovar, P. Tsigas, and H. Fouchal (Eds.): OPODIS 2007, LNCS 4878, pp. 217–231, 2007. c Springer-Verlag Berlin Heidelberg 2007
218
A. Gidenstam and M. Papatriantafilou
i.e. despite other processors simultaneously accessing shared objects related with the implementation of the LF THREADS-library operations and/or suffering stop failures or delays (e.g. from I/O or page-fault interrupts). Even a lock-free thread library needs to provide blocking synchronization objects, e.g. for mutual exclusion in
