A.3 Two-Level Scheduling on Digital Unix

Starting with Digital UNIX Version 4.0, DECthreads implements a new scheduling model, referred to as two-level scheduling. DECthreads schedules "user threads" onto kernel execution contexts (often known as "kernel threads", or "virtual processors"), just as Digital UNIX schedules processes onto the processors of a multiprocessing machine.

A user thread is executed on a kernel thread until it blocks or until it exhausts its timeslice quantum. Then, DECthreads schedules a new user thread to run. While DECthreads is scheduling user threads onto kernel threads, the Digital Unix kernel is independently scheduling those kernel threads to run on physical processors. The term "two-level" scheduling refers to this relationship.

This division allows most thread scheduling to take place completely in user mode, without the intervention of the kernel. Since a thread context switch does not involve any privileged information, it can be done much more efficiently in user mode.

The key to making the two-level scheduling model work is efficient two-way communication between DECthreads and the Digital UNIX kernel. When a thread blocks in the kernel, the DECthreads scheduler is notified so that it can schedule another thread to take advantage of the idle kernel thread. This mechanism is sometimes referred to as an "upcall", and is inspired by the original University of Washington research on Scheduler Activations (Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy; ACM Operating Systems Review Volume 25, Number 5 "Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, October 13-16, 1991").