High-Performance User-Level Threading

本研究计划的目的是研究线程的抽象概念和它们在编程语言中的交互机制。目标是为程序员提供选择最适合问题的并发数量的能力，同时仍能获得良好的性能。实现这一目标的机制是用户级线程，它可以扩展到10,000-100,000个线程，并且可以使用任何编程语言中的线程模型。大量线程的主要好处是将其过度划分为小的工作单元，以促进运行时的负载平衡。第二个好处是使用线程对象更简单的并发程序构造，利用了面向对象编程中的普通对象构造。在15年前试验了用户级M:N线程模型之后，UNIX社区采用了1:1线程模型。因此，不是M个用户线程跨N个OS内核线程（M>>N）进行多路复用，而是每个用户级线程绑定到一个内核线程。但是，随着处理器的增加，1:1线程系统开始饱和，并且难以支持具有大量线程的并发方法。

The purpose of this research program is to examine the abstract notion of threads and the mechanisms for their interaction in a programming language. The goal is to provide programmers with the ability to choose the amount of concurrency that best fits the 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 using thread objects, leveraging normal object-construction in object-oriented programming. 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. The objective of this research program 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, e.g., as the kernel is unaware of user threads, conflicting interactions occur. The focus of this research program is leveraging existing mechanisms as much as possible to generate proof-of-concepts for user-level threading. The scientific approach is extending the runtime for C++ and Go (and possibly Java) to identify fundamental user-level threading problems and test different solutions. Next is building performance experiments to compare approaches. Finally, extensive analysis of the results is required to understand where time is being lost or gained. Success will be measured by demonstrating a significant performance gain in a few key areas using M:N threading versus 1:1 threading (e.g., thread-per-connection web-server). The primary novelty and expected significance of the work is in programming-language runtime-support with respect to high-performance scheduling using available OS mechanisms. The secondary significance is to work with OS researchers and hardware designers to explore a few approaches for high-performance interactions across the application/OS boundary. The results directly re-address the question of whether M:N threading is a viable direction for future programming-language and OS development. Answering this question is crucial to the development direction of both these areas over the next 5 years.