Thread Models

¶ … Mx1, 1x1 and MxN, each having its own advantages and disadvantages. Although Mx1 is commonly acknowledge as an inferior model, there's plenty of debate about the merits of 1x1 versus MxN. Lately, the trend has been for several operating systems such as Solaris and Linux to move from a MxN model to the 1x1 model. This paper compares the pros and cons of each thread model and explores reasons behind the transition from the more scalable MxN to the simpler 1x1 model.

A thread is an independent flow of control within a process, composed of a context (a register set and a program counter) and a sequence of instructions that can execute independently of other sequences of instructions (Threads and the Java virtual machine). At application startup, all data is initialized. Each thread can access this global data and all user code as well as its own private storage, attributes and stack.

Sequences that are independent of each other can be completed simultaneously as opposed to waiting for each sequence of the process to complete. Reducing the wait cycles for independent steps to complete in parallel maximizes the throughput of the application. There are three types of thread models (Thread models). One model is called user threads or many to one (Mx1) threads. In this model, all program threads share the same process thread. The thread application programming interfaces enforce the scheduling policy and decide when a new thread runs.

The scheduling policy allows only one thread to be actively running in the process at a time. And, the operating system kernel is only aware of a single thread of control (task) in the process. A second thread model is called kernel threads or one to one (1x1) threads (Thread models). These threads are separate tasks associated with a process. The kernel thread model uses a pre-emptive scheduling policy in which the operating system decides which thread is eligible to share the processor.

In an 1x1 thread model, there is a one-to-one mapping between program threads and process threads. Some platforms support a combination of the Mx1 and 1x1 thread models (Thread models). This model is called a many to many (MxN) thread model and is a more complex implementation of kernel threads than the 1x1 model. Each process that has M. user threads shares N. kernel threads. The user threads are scheduled on top of the kernel threads. The system allocates resources only to the more "expensive" kernel threads.

Disadvantages of the Mx1 model far outweigh its benefits (Threads and the Java virtual machine). With Mx1 there is some concurrency because if one thread becomes blocked another thread will be scheduled to run. This thread model is lightweight because the kernel does not need to manage the required resources when creating, terminating and scheduling threads. However Mx1 has a critical limitation of not being able to take advantage of multiple CPU systems because a user thread is bound to the process.

As a result, the kernel views the application as single threaded. And, because user threads aren't visible to the kernel, it is impossible to get detailed thread specific diagnostic information such as per thread CPU utilization. In the 1x1 model, processes are containers for threads, which are the only scheduled entities (Threads and the Java virtual machine). This allows straightforward, true parallel execution and individual threads can run simultaneously on a multiple CPU system. In addition, profiling information can be obtained on a per-thread basis.

However, the 1x1 model requires a great deal of overhead to manage thread creation, scheduling and context switching in the kernel. Too many threads can also negatively impact overall system performance presenting scalability issues for large systems with many threads. This MxN has all the advantages of both Mx1 and 1x1, (true parallel execution, multiple CPU access, per thread profiling) with very few of the disadvantages (Threads and the Java virtual machine).

This algorithm is the most flexible and scalable, however, it is also the most complex and therefore more prone to problems (New generation POSIX threds). It requires two cooperating schedulers, one each in user and kernel space. Signal handling is difficult and much work has to be done in user space. It also great effort to prevent one blocked thread from blocking other threads running in the same process. Thus, the great debate over whether or not MxN is really superior to 1x1 has materialized.

The new POSIX Thread Library for Linux is based on a 1x1 model (Native POSIX Thread Library 0.1 released). Earlier designs had required a MxN implementation to support a scalable thread library. This was especially true for the IA-32 and x86-64 platforms since the application binary interface with respect to threads forced the use of segment registers and the only way to use those registers was with the Local Descriptor Table (LDT) data structure of the processor.

Now, the kernel limitations leading to the need for an MxN model have been eliminated. The 1x1 model offers advantages over its MxN predecessor such as the avoidance of two-level scheduling that allows the kernel to make all schedule decisions and direction interaction between kernel and user-level code. Likewise, the Solaris 8 OE introduced an alternate implementation based on the 1:1 model which leveraged the improvements in kernel threading.