Implementing a User-Level Threads Package

Question

I have been tasked in a class to create a user level thread library in C. I was wondering if anyone could give me a list of things to read up on to accomplish this. I have a good idea as to where to start, but any resources on user level threads and some applicable aspects of the C language that might help would be extremely valuable.

I am very unclear as to how I would implement a scheduler for such. Assume that I have a pretty good understanding of the C language and some of its more helpful library functions.

Answer 1

You can look up Apple's open-source implementation. Note that the largest part of the code is actually assembly code, because it requires some specialized things that you can't do in C, like retrieving the stack frame's return address or jumping to an arbitrary address.

• ucontext.h;
• getcontext.S;
• _setcontext.S;
• More generally, stuff here.

Userland threads (also commonly called "fibers") generally employ a cooperative model; that is, threads execute until they decide they've had enough time, then yield to another thread. Using a priority queue, you can implement a scheduler that executes the task that has run for the shortest amount of time. (The scheduler keeps a track of the running tasks, and the running task yields back when it decides it's had enough. The scheduler updates the amount of time the task has run, then yields to the one that has had the least execution time.)

Answer 2

I’ve done this for a homework assignment without writing any assembler at all. The thread switch mechanism was setjmp/longjmp. What this involved was allocating memory for each thread’s stack, then very carefully massaging the values in the jmp_buff so execution jumps to the next thread’s stack.

See also Russ Cox’s pretty readable libtask.

Edit in response to OP’s comment: In deciding when to switch threads there are two main directions: preemptive & cooperative. In the preemptive model, you’ll have something like a timer signal that causes execution flow to jump to a central dispatcher thread, which chooses the next thread to run. In a cooperative model, threads “yield” to each other, either explicitly (e.g., by calling a yield() function you’ll provide) or implicitly (e.g., requesting a lock held by another thread).

Take a look at the API of libtask for an example of the cooperative model, particularly the description of the function taskyield(). That’s the explicit yield I mentioned. There are also the non-blocking I/O functions which include an implicit yield—the current “task” is put on hold until the I/O completes, but the other tasks get their chance to run.

Answer 3

A simple cooperative scheduler can be done in C using swapcontext, look at the example in the swapcontext man page here, this is its output:

$ ./a.out
main: swapcontext(&uctx_main, &uctx_func2)
func2: started
func2: swapcontext(&uctx_func2, &uctx_func1)
func1: started
func1: swapcontext(&uctx_func1, &uctx_func2)
func2: returning
func1: returning
main: exiting

So as you can see it is quite doable.

Note: if you swap the context inside a timer signal handler, then you have yourself a pre-emptive scheduler, but I'm not sure if it's safe or possible to do this.

Edit: I found this in the man page of sigaction which suggests that it's possible to switch the context inside a signal handler:

If SA_SIGINFO is specified in sa_flags, then sa_sigaction (instead of sa_handler) specifies the signal-handling function for signum. This function receives the signal number as its first argument, a pointer to a siginfo_t as its second argument and a pointer to a ucontext_t (cast to void *) as its third argument.