Hybrid Implementations / Scheduler Activations

Hybrid Implementations / Scheduler Activations

Hybrid Implementations

Different ways have been considered to try to unite the benefits of user-level threads with kernel-level threads. One way is use kernel-level threads and then multiplex user-level threads onto some or all of the kernel threads, as shown in the following figure. When this approach is used, the programmer can decide how many kernel threads to use and how many user-level threads to multiplex on each one. This model gives the ultimate in flexibility.

Multiplexing user-level threads onto kernel-level threads

With this approach, the kernel is aware of only the kernel-level threads and schedules those. Some of those threads may have various user-level threads multiplexed on top of them. These user-level threads are created, destroyed, and scheduled just like user-level threads in a process that runs on an operating system without multithreading capability. In this model, each kernel-level thread has some set of user-level threads that take turns using it.

Scheduler Activations

As kernel threads are better than user-level threads in some key ways, they are also unquestionably slower. As a result, researchers have looked for ways to improve the situation without giving up their good features. Below we will explain one such approach devised by Anderson et al. (1992), called scheduler activations. Related work is discussed by Edler et al. (1988) and Scott et al. (1990).

The objectives of the scheduler activation work are to imitate the functionality of kernel threads, but with the better performance and greater flexibility generally linked with threads packages implemented in user space. Particularly, user threads should not have to make special nonblocking system calls or check in advance if it is safe to make certain system calls. However, when a thread blocks on a system call or on a page fault, it should be possible to run other threads within the same process, if any are ready.

Efficiency is achieved by avoiding unnecessary transitions between user and kernel space. If a thread blocks waiting for another thread to do something, for instance, there is no reason to involve the kernel, therefore saving the overhead of the kernel-user transition. The user-space run-time system can block the synchronizing thread and schedule a new one by itself.

When scheduler activations are used, the kernel allocates a certain number of virtual processors to each process and lets the (user-space) run-time system assign threads to processors. This mechanism can also be used on a multiprocessor where the virtual processors may be real CPUs. The number of virtual processors assigned to a process is at first one, but the process can ask for more and can also return processors it no longer requires. The kernel can also take back virtual processors already assigned in order to allocate them to more needy, processes.

The central idea that makes this scheme work is that when the kernel knows that a thread has blocked (e.g., by its having executed a blocking system call or caused a page fault), the kernel notifies the process run-time system, passing as parameters on the stack the  number of the thread in question and a description of the event that happened. The notification happens by having the kernel activate the run-time system at a known starting address, almost similar to a signal in UNIX. This mechanism is called an upcall.

Once activated like this, the run-time system can reschedule its threads, usually by marking the current thread as blocked and taking one more thread from the ready list, setting up its registers, and restarting it. Later, when the kernel learns that the original thread can run again (e.g., the pipe it was trying to read from now contains data, or the page it faulted over has been brought in from disk), it makes one more upcall to the run-time system to inform it of this event. The run-time system, at its own discretion, can either restart the blocked thread instantly or put it on the ready list to be run later.

When a hardware interrupt happens while a user thread is running, the interrupted CPU switches into kernel mode. If the interrupt is caused by an event not of interest to the interrupted process, such as completion of another process I/O, when the interrupt handler has finished, it puts the interrupted thread back in the state it was in before the interrupt. If, however, the process is interested in the interrupt, such as the arrival of a page required by one of the process threads, the interrupted thread is not restarted. Instead, the interrupted thread is suspended, and the run-time system is started on that virtual CPU, with the state of the interrupted thread on the stack. It is then up to the run-time system to decide which thread to schedule on that CPU: the interrupted one, the newly ready one, or some third choice.

An objection to scheduler activations is the basic reliance on upcalls, a thought that violates the structure inherent in any layered system. Generally, layer n offers certain services that layer n + 1 can call on, but layer n may not call procedures in layer n + 1. Upcalls do not follow this basic principle.


kernel threads, multithreading, system call, kernel mode