A thread library provides programmers with an API for creating and managing threads. Support for threads must be provided either at the user level or by the kernel.
Kernel level threads are supported and managed directly by the operating system.
User level threads are supported above the kernel in user space and are managed without kernel support.
In general, user-level threads can be implemented using one of four models.
All models maps user-level threads to kernel-level threads. A kernel thread is similar to a process in a non-threaded (single-threaded) system. The kernel thread is the unit of execution that is scheduled by the kernel to execute on the CPU. The term virtual processor is often used instead of kernel thread.
In the many-to-one model all user level threads execute on the same kernel thread. The process can only run one user-level thread at a time because there is only one kernel-level thread associated with the process.
The kernel has no knowledge of user-level threads. From its perspective, a process is an opaque black box that occasionally makes system calls.
In the one-to-one model every user-level thread execute on a separate kernel-level thread.
In this model the kernel must provide a system call for creating a new kernel thread.
In the many-to-many model the process is allocated m number of kernel-level threads to execute n number of user-level thread.
The two-level model is similar to the many-to-many model but also allows for certain user-level threads to be bound to a single kernel-level thread.
In both the many-to-many model and the two-level model there must be some way for the kernel to communicate with the user level thread manager to maintain an appropriate number of kernel threads allocated to the process. This mechanism is called scheduler activations.
The kernel provides the application with a set of kernel threads (virtual processors), and then the application has complete control over what threads to run on each of the kernel threads (virtual processors). The number of kernel threads (virtual processors) in the set is controlled by the kernel, in response to the competing demands of different processes in the system.1
The kernel notify the user-level thread manager of important kernel events using upcalls from the kernel to the user-level thread manager. Examples of such events includes a thread making a blocking system call and the kernel allocating a new kernel thread to the process.1
Let’s study an example of how scheduler activations can be used. The kernel has allocated one kernel thread (1) to a process with three user-level threads (2). The three user level threads take turn executing on the single kernel-level thread.
The executing thread makes a blocking system call (3) and the the kernel blocks the calling user-level thread and the kernel-level thread used to execute the user-level thread (4). Scheduler activation: the kernel decides to allocate a new kernel-level thread to the process (5). Upcall: the kernel notifies the user-level thread manager which user-level thread that is now blocked and that a new kernel-level thread is available (6). The user-level thread manager move the other threads to the new kernel thread and resumes one of the ready threads (7).
While one user-level thread is blocked (8) the other threads can take turn executing on the new kernel thread (9).
Scheduling of the usea-level threads among the available kernel-level threads is done by a thread scheduler implemented in user space. There are two main methods: cooperative and preemptive thread scheduling.
The cooperative model is similar to multiprogramming where a process executes on the CPU until making a I/O request. Cooperative user-level threads execute on the assigned kernel-level thread until they voluntarily give back the kernel thread to the thread manager.
In the cooperative model, threads yield to each other, either explicitly (e.g., by
yield() provided by the user-level thread library) or implicitly (e.g., requesting a
lock held by another thread). In the below figure a many-to-one system with
cooperative user-level threads is shown.
The preemptive model is similar to multitasking (aka time sharing). Multitasking is a logical extension of multiprogramming where a timer is set to cause an interrupt at a regular time interval and the running process is replaced if the job requests I/O or if the job is interrupted by the timer. This way, the running job is given a time slice of execution than cannot be exceeded.
In the preemptive model, a timer is used to cause execution flow to jump to a central dispatcher thread, which chooses the next thread to run. In the below figure a many-to-one system with preemptive user-level threads is shown.
A hybrid model between cooperative and preemptive scheduling is also possible
where a running thread may
yield() or preempted by a timer.