CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 3 of 7 · 3 min read

User threads in code

In plain words: The C library has functions that save and restore a processor state without the kernel choosing anything: getcontext, makecontext and swapcontext. They are enough to build a tiny user-level thread system. Here two tasks take turns three times, with a one-line round-robin scheduler (Level 3) in main:

#include <stdio.h>
#include <ucontext.h>
#include <stdlib.h>

static ucontext_t main_ctx, ctx[2];

static void task(int id) {
    for (int step = 1; step <= 3; step++) {
        printf("user thread %d, step %d\n", id, step);
        swapcontext(&ctx[id], &main_ctx);      /* yield: give the processor back */
    }
}
int main(void) {
    for (int i = 0; i < 2; i++) {
        getcontext(&ctx[i]);
        ctx[i].uc_stack.ss_sp = malloc(64 * 1024);
        ctx[i].uc_stack.ss_size = 64 * 1024;
        ctx[i].uc_link = &main_ctx;
        makecontext(&ctx[i], (void (*)(void))task, 1, i);
    }
    for (int round = 0; round < 3; round++)
        for (int i = 0; i < 2; i++)
            swapcontext(&main_ctx, &ctx[i]);
    printf("all done\n");
    return 0;
}
user thread 0, step 1
user thread 1, step 1
user thread 0, step 2
user thread 1, step 2
user thread 0, step 3
user thread 1, step 3
all done

Each task has its own stack (the malloced 64 KB) and its own saved registers, which is what the definition of a thread asks for (page 1). The tasks alternate only because each one calls swapcontext to hand control back. This is cooperative scheduling: a task keeps the processor until it chooses to give it up. No timer interrupt takes it away.

Switching this way is quick, since there is no change of mode and no change of address space. A test that switched a million times and divided by the count gave about 240 ns per switch (three runs: 242, 238 and 255 ns). Part of that time is not the switch itself: strace showed that the library call swapcontext also made one system call, rt_sigprocmask, per switch, to save the signal mask. A pure user-level library avoids this and can switch in a few tens of nanoseconds.

The weakness appears when a task has to wait. Suppose both tasks call sleep(1):

two user-level tasks, each sleep(1): 2.0 s
two kernel threads, each sleep(1):   1.0 s

The user-level tasks took 2 seconds. sleep is a system call, and the kernel only sees one process, so it put the whole process to sleep, and the second task could not start until the first task's sleep had ended. The same program with two pthread threads took 1 second, because the kernel saw two threads and let both sleep at the same time. This is the central problem of user-level threads: one blocking system call blocks all of them, and a program using them cannot use more than one processor at a time, since the kernel schedules only one line of execution.

Common mistake

Assuming that more threads always means more parallelism. User-level threads inside one process only ever use one processor at a time, and a single blocking call stops all of them.

Check yourself: 1. What does swapcontext do? 2. Why did the two user-level tasks take 2 seconds? 3. Why is the user-level switch cheaper than a process switch?