Threads cannot be implemented as a library

From AcaWiki
Jump to: navigation, search

Citation: Hans-J. Boehm (2005/06) Threads cannot be implemented as a library. ACM SIGPLAN Notices (RSS)
DOI (original publisher): 10.1145/1064978.1065042
Semantic Scholar (metadata): 10.1145/1064978.1065042
Sci-Hub (fulltext): 10.1145/1064978.1065042
Internet Archive Scholar (search for fulltext): Threads cannot be implemented as a library
Download: https://dl.acm.org/doi/10.1145/1064978.1065042
Tagged: Computer Science (RSS) parallel systems (RSS)

Summary

Placeholder

Theoretical and Practical Relevance

Every major programming language now handles threads in the language specification, rather than leaving it up to the libraries.


Problem

  • We need threads because:
    • Applications need concurrency (e.g. servers)
    • Exploit multiprocessor systems

Status quo: threads provided by libraries

  • Threads in C/C++ are defined as a library, pthreads.
  • Thread operations affect memory synchronization.
  • Compilers have to pretend thread operations read/write all of memory, in order to maintain correctness.

Problems with status quo

  • "The Pthreads specification prohibits races, i.e. accesses to a shared variable while another thread is modifying it... Whether or not a race exists depends on the semantics of the programming language, which in turn requires that we have a properly defined memory model. Thus this definition is circular."
  • The library breaks important compiler optimizations:
    • Compiler optimizations may transform code that writes 4 bytes to addr to code that writes to addr, addr+4, addr+8, and addr+16 in one instruction. Whether this optimization is valid depends on what the concurrent thread is doing, which exists outside of the language
    • Register promotion causes repeated accesses to the same memory location to access a register instead. This is only valid if no other thread accesses that variable.

The better way

  • Compilers must be aware of the existence of threads to correctly compile code.
  • Threads must be defined in the language specification.
  • Some programs have "benign" data races. The algorithm has races, but is correct as long as one of the competing writes wins.
    • There is no way to take advantage of these algorithms in a language with race-free semantics.

Elsewhere

Retrieved from "https://acawiki.org/index.php?title=Threads_cannot_be_implemented_as_a_library&oldid=11947"