UW Logo

CS842: Advanced Topics in Language Design and Implementation

User-Level Threading: Revisited

University of Waterloo : Faculty of Mathematics : School of Computer Science


Current Term (Winter 2015)

General Information


Problem

The number of processors (cores) continues to increase. Programmers want the ability to choose the amount of concurrency that best fits a problem, while still achieving good performance. The mechanism to accomplish this goal is user-level threading, which can scale to 10,000-100,000 threads, and can work with threading models in any programming language. The primary benefit from large numbers of threads is over-partitioning into small work-units to facilitate load balancing by the runtime. The secondary benefit is simpler concurrent program-construction. After experimenting with the user-level M:N threading model 15 years ago, the UNIX community adopted the 1:1 threading model. Hence, instead of M user threads multiplexing across N OS kernel-threads (M>>N), each user-level thread is bound to one kernel thread. However, 1:1 threading systems are beginning to saturate with increased processors and struggle to support concurrency approaches with large numbers of threads.

As a result, the notion of user-level M:N threading is being revisited with the expectation of untapped performance potential from low-cost: thread creation/deletion, context switching, synchronization, mutual exclusion, and preemption. The results are reinvigorating program-language and OS interaction with respect to creating and managing large numbers of threads in an application. For example, the languages Erlang, Haskell, and the new Go language from Google adopt the M:N threading model, providing simple mechanisms to create, and manage large numbers of user-level threads. Unfortunately, the 1:1 threading-model at the kernel level significantly constrains the M:N threading-model through restrictions at the kernel/application boundary.

Course Objectives

The course objectives are to teach basic concurrency concepts, and then examine the abstract notion of threads in a programming language. The main approach is to reexamine the major problem areas of M:N threading, e.g., scheduling, blocking, garbage collection, and preemption, to see if new solutions can be engineered. Current M:N systems do not handle some of these problems, and hence are fragile or restrictive, or ignore them by adopting a closed environment (no outside interaction). While user-level threading has been worked on extensively, it still remains a challenging problem with many open issues. The course material is presented from the programming-language perspective without formalism.

Resources

  1. Course Newsgroup Piazza cs842
  2. μC++ Download (installation: sudo sh u++-6.1.0.sh) detailed instructions
  3. FAQ (Frequently Asked Questions)
  4. Code Examples (makefiles, C++, μC++, Java)
  5. C++ Coding Guidelines
  6. μC++ Annotated Reference Manual (postscript)
  7. μC++ Background
  8. CS246 Course Notes
  9. Research Papers
  10. Real Time
  11. Books
  12. GNU Make manual
  13. C++ Tutorial (postscript, workcode)
  14. C++ Standard Library
  15. GDB Tutorial for C, C++
  16. Emacs Tutorial (.emacs)
  17. MFCF Help Centre

Valid XHTML 1.0 Strict