Article

LFTHREADS: a lock-free thread library

Authors:

Anders Gidenstam,

Marina PapatriantafilouAuthors Info & Claims

OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

Pages 217 - 231

Published: 17 December 2007 Publication History

Abstract

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 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 LFTHREADS 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 LFTHREADS is achieved by a new method, which we call responsibility hand-off (RHO), that does not need any special kernel support.

References

[1]

Anderson, T., Bershad, B., Lazowska, E., Levy, H.: Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. In: ACM Trans. on Computer Systems, pp. 53-79. ACM Press, New York (1992).

Digital Library

[2]

Feeley, M.J., Chase, J.S., Lazowska, E.D.: User-level threads and interprocess communication. Technical Report TR-93-02-03, University of Washington, Department of Computer Science and Engineering (1993).

[3]

Franke, H., Russell, R., Kirkwood, M.: Fuss, futexes and furwocks: Fast userlevel locking in linux. In: Proc. of the Ottawa Linux Symp, pp. 479-494 (2002).

[4]

Multithreading in the solaris operating environment. Technical report, Sun Microsystems.

[5]

Kontothanassis, L.I., Wisniewski, R.W., Scott, M.L.: Scheduler-conscious synchronization. ACM Trans. Computer Systems 15(1), 3-40 (1997).

Digital Library

[6]

Holman, P., Anderson, J.H.: Locking under pfair scheduling. ACM Trans. Computer Systems 24(2), 140-174 (2006).

Digital Library

[7]

Devi, U.C., Leontyev, H., Anderson, J.H.: Efficient synchronization under global edf scheduling on multiprocessors. In: Proc. of the 18th Euromicro Conf. on Real-Time Systems, pp. 75-84. IEEE Computer Society, Los Alamitos (2006).

Digital Library

[8]

Blumofe, R.D., Leiserson, C.E.: Scheduling multithreaded computations by work stealing, In: Proc. of the 35th Annual Symp. on Foundations of Computer Science (FOCS), 356-368 ( 1994).

Digital Library

[9]

Oguma, H., Nakayama, Y.: A scheduling mechanism for lock-free operation of a lightweight process library for SMP computers. In: Proc. of the 8th Int. Conf. on Parallel and Distributed Systems (ICPADS), 235-242 ( 2001).

Digital Library

[10]

Zahorjan, J., Lazowska, E.D., Eager, D.L.: The effect of scheduling discipline on spin overhead in shared memory parallel processors. IEEE Trans. on Parallel and Distributed Systems 2(2), 180-198 (1991).

Digital Library

[11]

Zuberi, K.M., Shin, K.G.: An efficient semaphore implementation scheme for small-memory embedded systems. In: Proc. of the 3rd IEEE Real-Time Technology and Applications Symp (RTAS), IEEE, pp. 25-37. IEEE Computer Society Press, Los Alamitos (1997).

Digital Library

[12]

Anderson, J.H., Kim, Y.J., Herman, T.: Shared-memory mutual exclusion: major research trends since 1986. Distributed Computing 16(2-3), 75-110 (2003).

Digital Library

[13]

Massalin, H., Pu, C.: A lock-free multiprocessor OS kernel. Technical Report CUCS-005-91 (1991).

[14]

Massalin, H.: Synthesis: An Efficient Implementation of Fundamental Operating System Services. PhD thesis, Columbia University (1992).

Digital Library

[15]

Greenwald, M., Cheriton, D.R.: The synergy between non-blocking synchronization and operating system structure. In: Operating Systems Design and Implementation, 123-136, (1996).

Digital Library

[16]

Greenwald, M.B.: Non-blocking synchronization and system design. PhD thesis, Stanford University (1999).

Digital Library

[17]

Valois, J.D.: Lock-free linked lists using compare-and-swap. In: Proc. of the 14th ACM Symp. on Principles of Distributed Computing (PODC), ACM, pp. 214-222. ACM Press, New York (1995).

Digital Library

[18]

Michael, M.M., Scott, M.L.: Correction of a memory management method for lock-free data structures. Technical Report TR599, University of Rochester, Computer Science Department (1995).

Digital Library

[19]

Michael, M.: Scalable lock-free dynamic memory allocation. In: Proc. of SIGPLAN 2004 Conf. on Programming Languages Design and Implementation, ACM Press, ACM SIGPLAN Notices (2004).

Digital Library

[20]

Gidenstam, A., Papatriantafilou, M., Sundell, H., Tsigas, P.: Practical and efficient lock-free garbage collection based on reference counting. In: Proc. of the 8th Int. Symp. on Parallel Architectures, Algorithms, and Networks (I-SPAN), pp. 202-207. IEEE Computer Society Press, Los Alamitos (2005).

Digital Library

[21]

Gidenstam, A., Papatriantafilou, M., Tsigas, P.: Allocating memory in a lock-free manner. In: Proc. of the 13th Annual European Symp. on Algorithms (ESA), pp. 242-329. Springer, Heidelberg (2005).

Digital Library

[22]

Herlihy, M., Luchangco, V., Martin, P., Moir, M.: Nonblocking memory management support for dynamic-sized data structures. ACM Trans. on Computer Systems 23(2), 146-196 (2005).

Digital Library

[23]

Sundell, H., Tsigas, P.: NOBLE: A non-blocking inter-process communication library. In: Sundell, H., Tsigas, P. (eds.) Proc. of the 6th Workshop on Languages, Compilers and Runtime Systems for Scalable Computers, Springer, Heidelberg (2002).

[24]

Marathe, V.J.I.W.N.S., Scott, M.L: Adaptive software transactional memory. In: Proc. of the 19th Int. Conf. on Distributed Systems (DISC), Springer, pp. 354-368. Springer, Heidelberg (2005).

Digital Library

[25]

Shavit, N., Touitou, D.: Software transactional memory. In: Proc. of the 14th ACM Symp. on Principles of Distributed Computing (PODC), pp. 204-213. ACM Press, New York (1995).

Digital Library

[26]

Jayanti, P.: A complete and constant time wait-free implementation of CAS from LL/SC and vice versa. In: Proc. of the 12th Int. Symp. on Distributed Computing (DISC), pp. 216-230. Springer, Heidelberg (1998).

Digital Library

[27]

Moir, M.: Practical implementations of non-blocking synchronization primitives. In: Proc. of the 16th annual ACM Symp. on Principles of Distributed Computing, pp. 219-228. ACM Press, New York (1997), citeseer.ist.psu.edu/moir97practical.html

Digital Library

[28]

Herlihy, M.: A methodology for implementing highly concurrent data objects. ACM Trans. on Programming Languages and Systems 15(5), 745-770 (1993).

Digital Library

[29]

Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. on Programming Languages and Systems 12(3), 463-492 (1990), http://www.acm.org/pubs/toc/Abstracts/0164-0925/78972.html

Digital Library

[30]

Sundell, H.: Efficient and Practical Non-Blocking Data Structures. PhD thesis, Chalmers University of Technology (2004).

[31]

Tsigas, P., Zhang, Y.: Evaluating the performance of non-blocking synchronisation on shared-memory multiprocessors. In: Proc. of the ACM SIGMETRICS 2001/Performance 2001, pp. 320-321. ACM Press, New York (2001).

Digital Library

[32]

Tsigas, P., Zhang, Y.: A simple, fast and scalable non-blocking concurrent fifo queue for shared memory multiprocessor systems. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architectures, pp. 134-143. ACM Press, New York (2001).

Digital Library

[33]

Gidenstam, A., Papatriantafilou, M.: LFthreads: A lock-free thread library. Technical Report MPI-I-2007-1-003, Max-Planck-Institut für Informatik, Algorithms and Complexity (2007).

Cited By

Nikolakopoulos YPapatriantafilou MBrauer PLundqvist MGulisano VTsigas P(2016)Highly Concurrent Stream Synchronization in Many-core Embedded SystemsProceedings of the Third ACM International Workshop on Many-core Embedded Systems10.1145/2934495.2934496(2-9)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2934495.2934496
Gidenstam APapatriantafilou M(2009)LFTHREADSACM SIGARCH Computer Architecture News10.1145/1556444.155645636:5(88-92)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1556444.1556456

Recommendations

LFthreads: A Lock-Free Thread Library
Principles of Distributed Systems
Abstract
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/...
Static analysis of atomicity for programs with non-blocking synchronization
PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming

In concurrent programming, non-blocking synchronization is very efficient but difficult to design correctly. This paper presents a static analysis to show that code blocks are atomic, i.e., that every execution of the program is equivalent to one in ...
(Dis)Advantages of Lock-free Synchronization Mechanisms for Multicore Embedded Systems
ICPP Workshops '19: Workshop Proceedings of the 48th International Conference on Parallel Processing

Embedded systems show a tendency of migrating to multicore processors. However, to fully use the potential of multicore processors, it is necessary to partition software into threads that execute concurrently and communicate using shared memory. In order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

December 2007

457 pages

ISBN:354077095X

Editors:
Eduardo Tovar
Polytechnic Institute of Porto, ISEP, Department of Computer Engineering, Porto, Portugal
,
Philippas Tsigas
Chalmers University of Technology, Department of Computer Science & Engineering, Göteborg, Sweden
,
Hacène Fouchal
GRIMAAG, Université des Antilles et de Guyane, Guadeloupe, France

Sponsors

UAG: Université des Antilles et de la Guyane
Architecture, Réseaux et systèmes, Parallélisme, GdR-CNRS
EPHE: l'Ecole Pratique des Hautes Etudes
INRIA: Institut Natl de Recherche en Info et en Automatique
LaISC: Laboratoire d'Informatique et des Systèmes ComplexesLaboratoire d'Informatique et des Systèmes Complexes

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 December 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
1
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikolakopoulos YPapatriantafilou MBrauer PLundqvist MGulisano VTsigas P(2016)Highly Concurrent Stream Synchronization in Many-core Embedded SystemsProceedings of the Third ACM International Workshop on Many-core Embedded Systems10.1145/2934495.2934496(2-9)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1145/2934495.2934496
Gidenstam APapatriantafilou M(2009)LFTHREADSACM SIGARCH Computer Architecture News10.1145/1556444.155645636:5(88-92)Online publication date: 20-Jun-2009
https://dl.acm.org/doi/10.1145/1556444.1556456

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents