How is preemptive scheduling implemented for user-level threads in Linux?

Question

With user-level threads there are N user-level threads running on top of a single kernel thread. This is in contrast to pthreads where only one user thread runs on a kernel thread.

The N user-level threads are preemptively scheduled on the single kernel thread. But what are the details of how that is done.

I heard something that suggested that the threading library sets things up so that a signal is sent by the kernel and that is the mechanism to yank execution from an individual user-level thread to a signal handler that can then do the preemptive scheduling.

But what are the details of how state such as registers and thread structs are saved and/or mutated to make this all work? Is there maybe a very simple of user-level threads that is useful for learning the details?

Answer 1

To get the details right, use the source! But this is what I remember from when I read it...

There are two ways user-level threads can be scheduled: voluntarily and preemptively.

• Voluntary scheduling: threads must call a function periodically to pass the use of the CPU to another thread. This function is called yield() or schedule() or something like that.
• Preemptive scheduling: the library forcefully removes the CPU from one thread and passes it to another. This is usually done with timer signals, such as SIGALARM (see man ualarm for the details).

About how to do the real switch, if your OS is friendly and provides the necessary functions, that is easy. In Linux you have the makecontext() / swapcontext() functions that make swapping from one task to another easy. Again, see the man pages for details.

Unfortunately, these functions are removed from POSIX, so other UNIX may not have them. If that's the case, there are other tricks that can be done. The most popular was the one calling sigaltstack() to set up an alternate stack for managing the signals, then kill() itself to get to the alternate stack, and longjmp() from the signal function to the actual user-mode-thread you want to run. Clever, uh?

As a side note, in Windows user-mode threads are called fibers and are fully supported also (see the docs of CreateFiber()).

The last resort is using assembler, that can be made to work almost everywhere, but it is totally system specific. The steps to create a UMT would be:

• Allocate a stack.
• Allocate and initialize a UMT context: a struct to hold the value of the relevant CPU registers.

And to switch from one UMT to another:

• Save the current context.
• Switch the stack.
• Restore the next context in the CPU and jump to the next instruction.

These steps are relatively easy to do in assembler, but quite impossible in plain C without support from any of the tricks cited above.