Threads cannot be implemented as a library

ABSTRACT

In many environments, multi-threaded code is written in a language that was originally designed without thread support (e.g. C), to which a library of threading primitives was subsequently added. There appears to be a general understanding that this is not the right approach. We provide specific arguments that a pure library approach, in which the compiler is designed independently of threading issues, cannot guarantee correctness of the resulting code.We first review why the approach almost works, and then examine some of the surprising behavior it may entail. We further illustrate that there are very simple cases in which a pure library-based approach seems incapable of expressing an efficient parallel algorithm.Our discussion takes place in the context of C with Pthreads, since it is commonly used, reasonably well specified, and does not attempt to ensure type-safety, which would entail even stronger constraints. The issues we raise are not specific to that context.

REFERENCES

• 1: A. Alexandrescu, H.-J. Boehm, K. Henney, B. Hutchings, D. Lea, and B. Pugh. Memory model for multithreaded C++: Issues. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1777.pdf.
• 2: A. Alexandrescu, H.-J. Boehm, K. Henney, D. Lea, and B. Pugh. Memory model for multithreaded C++. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2004/n1680.pdf.
• 3: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
• 4: Alessio Bechini , Pierfrancesco Foglia , Cosimo Antonio Prete, Fine-grain design space exploration for a cartographic SoC multiprocessor, ACM SIGARCH Computer Architecture News, v.31 n.1, March 2003 [doi>10.1145/773365.773375]
• 5: Brian N. Bershad , David D. Redell , John R. Ellis, Fast mutual exclusion for uniprocessors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.223-233, October 12-15, 1992, Boston, Massachusetts, United States
• 6: H.-J. Boehm. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/.
• 7: Hans-J. Boehm, An almost non-blocking stack, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011774]
• 8: P. A. Buhr. Are safe concurrency libraries possible. Communications of the ACM, 38(2):117--120, February 1995.
• 9: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden
• 10: John Lu , Keith D. Cooper, Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.308-319, June 16-18, 1997, Las Vegas, Nevada, United States
• 11: Ericsson Computer Science Laboratory. Open source Erlang. http://www.erlang.org.
• 12: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 13: Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993 [doi>10.1145/161468.161469]
• 14: Maurice Herlihy , Victor Luchangco , Mark Moir, Obstruction-Free Synchronization: Double-Ended Queues as an Example, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.522, May 19-22, 2003
• 15: HP Technical Brief. Memory ordering optimization considerations. http://h21007.www2.hp.com/dspp/files/unprotected/ddk/Optmiztn.pdf.
• 16: IEEE and The Open Group. IEEE Standard 1003.1-2001. IEEE, 2001.
• 17: JSR 133 Expert Group. Jsr-133: Java memory model and thread specification. http://www.cs.umd.edu~pugh/java/memoryModel/jsr133.pdf, August 2004.
• 18: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 19: L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computing, C-28(9):690--691, 1979.
• 20: D. Lea. Concurrency jsr-166 interest site. http://gee.cs.oswego.edu/dl/concurrency-interest.
• 21: D. Lea. The JSR-133 cookbook for compiler writers. http://gee.cs.oswego.edu/dl/jmm/cookbook.html.
• 22: Raymond Lo , Fred Chow , Robert Kennedy , Shin-Ming Liu , Peng Tu, Register promotion by sparse partial redundancy elimination of loads and stores, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.26-37, June 17-19, 1998, Montreal, Quebec, Canada
• 23: Jeremy Manson , William Pugh , Sarita V. Adve, The Java memory model, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.378-391, January 12-14, 2005, Long Beach, California, USA
• 24: Maged M. Michael, Scalable lock-free dynamic memory allocation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 25: B. Pugh. The "double-checked locking is broken" declaration. http://www.cs.umd.edu~pugh/java/memoryModel/DoubleCheckedLocking.html.
• 26: B. Pugh. The java memory model. http://www.cs.umd.edu/~pugh/java/memoryModel/.
• 27: W. Pugh. The java memory model is fatally flawed. Concurrency - Practice and Experience, 12(6):445--455, 2000.
• 28: John H. Reppy, CML: A higher concurrent language, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.293-305, June 24-28, 1991, Toronto, Ontario, Canada
• 29: Jack L. Rosenfeld, A case study in programming for parallel-processors, Communications of the ACM, v.12 n.12, p.645-655, Dec. 1969 [doi>10.1145/363626.363628]
• 30: V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
• 31: A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.15-25, June 17-19, 1998, Montreal, Quebec, Canada
• 32: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]
• 33: A. Terekhov and D. Butenhof. The austin common standards revision group: Enhancement request 9 (austin/107): Clarification of "memory location". http://www.opengroup.org/austin/docs/austin_107.txt, May 2002.
• 34: The MPI Forum. The message passing interface (MPI) standard. http://www-unix.mcs.anl.gov/mpi/.
• 35: R. Treiber. Systems programming: Coping with parallelism. Technical Report RJ5118, IBM Almaden Research Center, 1986.
• 36: Youfeng Wu , James R. Larus, Static branch frequency and program profile analysis, Proceedings of the 27th annual international symposium on Microarchitecture, p.1-11, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192725]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages, Performance

Keywords:
data race, optimization, pthreads, register promotion, threads