Threads

We can think of processes as an abstraction that creates an idealized machine for running a program. In the early days of computing, these idealized machines were inspired by the actual machines of the day, which were uniprocessors (i.e., single core). So it made sense to have a single execution state per process.

Quickly enough, multi-processor machines arrived, but these were initially rare and expensive, and the idea that programmers might want the complexity that arises from multiple execution states per process was not immediately obvious. If programmers wanted multiple tasks to run concurrently, they could always create multiple processes, and various mechanisms were devised to let processes communicate and synchronize with each other.

But programming-language designers liked the idea of providing a more lightweight way to run multiple tasks concurrently within the same program (and thus within the same process). That goal led to the development of threads.

Green Threads

In the early days of threads, they were implemented entirely in user space, without any support from the operating system's kernel. User-space threads are sometimes called green threads (or virtual threads).

Here's some example code showing a simple implementation of user-space threads from within a program:

#include <stdio.h>
#include <stdlib.h>
#include <ucontext.h>
#include <signal.h>
#include <unistd.h>
#include <sys/time.h>

#define STACK_SIZE 16384 /* Stack size for each thread */

/* Contexts for main and two threads */
ucontext_t contexts[3];           /* 0: main, 1: thread 1, 2: thread 2 */
int current_thread = 1;           /* Tracks the current thread */
volatile int num_threads = 0;     /* Number of threads */

void
scheduler(int signum)
{
        if (num_threads < 2) {
                printf("Too few threads to schedule\n");
                return;
        }
        int prev_thread = current_thread;

        /* Toggle between thread 1 and thread 2 */
        current_thread = (current_thread == 1) ? 2 : 1;
        printf("-- Switching from thread %d to thread %d\n", prev_thread, 
                current_thread);

        /* Swap context to the next thread */
        swapcontext(&contexts[prev_thread], &contexts[current_thread]);
}

void
thread1(void)
{
        for (int i = 1; i <= 42; i++) {
                printf("Thread 1: %d\n", i);
                usleep(100000); /* Simulate work */
        }
        printf("Thread 1 exiting\n");
        --num_threads;
}

void
thread2(void)
{
        for (int i = 1; i <= 42; i++) {
                printf("Thread 2: %d\n", i);
                usleep(100000); /* Simulate work */
        }
        printf("Thread 2 exiting\n");
        --num_threads;
}

void
newthread(void (*entrypoint)(void), ucontext_t *contextptr)
{
        void *stack = malloc(STACK_SIZE);
        if (stack == NULL) {
                perror("malloc");
                exit(EXIT_FAILURE);
        }
        if (getcontext(contextptr) == -1) {
                perror("getcontext");
                exit(EXIT_FAILURE);
        }
        contextptr->uc_stack.ss_sp = stack;
        contextptr->uc_stack.ss_size = STACK_SIZE;
        contextptr->uc_link = &contexts[0]; /* Return to main if thread exits */
        makecontext(contextptr, entrypoint, 0);
        ++num_threads;
}

int
main(void)
{
        struct sigaction sa;

        newthread(thread1, &contexts[1]);
        newthread(thread2, &contexts[2]);

        /* Set up the SIGALRM signal handler */
        sa.sa_handler = scheduler;
        sigemptyset(&sa.sa_mask);
        sa.sa_flags = SA_RESTART; /* Restart interrupted system calls */
        if (sigaction(SIGALRM, &sa, NULL) == -1) {
                perror("sigaction");
                exit(EXIT_FAILURE);
        }

        /* Configure the timer to trigger SIGALRM every 0.5 seconds */
        ualarm(500000, 500000);

        /* Start the first thread */
        current_thread = 1;
        swapcontext(&contexts[0], &contexts[1]);

        /* If our scheduler wasn't running, we'd run the first thread all 
         * the way to completion and but since it is, both threads will run 
         * concurrently.  When one of them exits (we don't know which one will
         * exit first), we'll return here. */

        /* Finish the other thread thread */
        current_thread = (current_thread == 1) ? 2 : 1;
        swapcontext(&contexts[0], &contexts[current_thread]);

        printf("Main thread exiting\n");
        return 0;
}

• Try this code in Online GDB

This code uses

• makecontext, swapcontext, and getcontext (provided by the C library) to manipulate the execution context of the program. Importantly, these functions work just by saving and restoring the CPU registers, so they don't require any special support from the operating-system kernel itself.
• ualarm to set a timer that will interrupt the program and switch to a different thread by calling the scheduler function.
• thread1 and thread2 each count up to 42 before quitting.

This code is just a simple demonstration. We could write a more full-featured scheduler that can deal with more than two threads, and we could add synchronization primitives to allow threads to communicate and synchronize with each other. In fact, the code would look a lot like what you've already seen and implemented in OS/161.

For some time, these user-space threads were the only game in town, and even after alternatives arrived, they remained popular because they were lightweight and less prone to race conditions (precisely because nothing actually happens simultaneously).

This approach was used by

• C (via the cthreads library, which later inspired the pthreads library);
• Early versions of Java;
• Python (via the greenlet library);
• Early versions of Go (at least if you didn't adjust the MAXPROCS environment variable);

and many others.

Native Threads

Eventually (mostly in the 1990s), operating systems began to provide support for threads in the kernel itself. These threads are called native threads.

But because having multiple execution states per process was a significant change, and support needed to be added to preexisting operating systems, adding support for native threads required retrofitting this new functionality into existing operating systems, which meant that prior design decisions made in those OSs had to be revisited.

Things that Need to be Per-Thread

• CPU registers: Each thread needs its own execution state.
• Stack: Each thread needs its own stack (for local variables and function calls).
• Thread state: Each thread needs its own state (e.g., ready, running, waiting).

Things that Need to be Per-Process

• Process ID (PID): A unique identifier for the process as a whole.
• Memory for program code: The program code is shared among all threads in the process.
• Memory for program data: The program data is shared among all threads in the process.

Things that Unix Decided to Share

Many of the remaining things on our list are shared among all threads in a process in Unix-like operating systems, including

• File descriptors: All threads in a process share the same set of open files.
• User and Group ID: All threads in a process run with the same user and group permissions.
• Current working directory: All threads in a process share the same working directory.
• Root directory: All threads in a process share the same root directory.
• Signals waiting; signal mask.
• Time of next alarm signal.

Things that Unix Decided to Make Per-Thread

Unix-like operating systems also have some per-thread attributes, including

• Priority: Each thread has its own priority.
• CPU time used: Each thread has its own CPU time usage.
• Signal mask

int pid = fork();
if (pid == 0) {
    // Child process
} else {
    // Parent process
}

Honestly, there are no great options here. POSIX decided to duplicate only the calling thread, and to leave the other threads in the dark that the fork even happened.

Generally, it's considered a bad idea for a multithreaded program to call fork() while other threads are actively working. It's okay, however, if just after forking the child immediately calls exec() to replace its memory space with a new program. That is, after all, the most common use of fork().

Hybrid Approaches

There are also hybrid approaches that try to combine the best of both worlds. We could, for example, have a user-space thread library that uses native threads behind the scenes. Options for doing this vary:

Synchronization in User Space

One place where thread libraries try to be more efficient is in synchronization. For example, if a thread is waiting for a lock, it might busy-wait for a short while before giving up and going to sleep. This approach can be more efficient than making a system call to the kernel to put the thread to sleep and wake it up again.

N:M Threading

Another approach is to have an N:M threading model, where N user-space threads are mapped to M native (kernel-supported) threads. This approach can be more efficient than a 1:1 threading model, because the user-space threads can be scheduled by the user-space thread library, which can be more efficient than the kernel scheduler.

For example, if we have communication channels, and one thread wants to send a message to another thread and wait for the response, we can do that without involving the kernel at all, switching between the sender and receiver entirely in user space.

This is the approach used by the Go programming language, which has a user-space thread library that maps Go routines to native threads. The environment variable GOMAXPROCS can be used to control how many native threads are used.

A similar approach is used by Apple's Grand Central Dispatch (GCD) library, which is used in macOS and iOS, and also behind the scenes to support Swift's concurrency model.

The Windows Thread Pool API, which is used by the .NET framework and other Windows libraries, uses a similar approach.

Takeaways

• Threads are a way to run multiple tasks concurrently within the same program.
• User-space threads are lightweight and can be more efficient, but can't take advantage of multicore machines.
  • It's actually not that hard to write a simple user-space–thread library, as we saw in the example code. But writing a full-featured one is quite tricky.
• Native threads are heavier because every thread action is a system call, but they can take advantage of multicore machines.
• There are hybrid approaches that try to combine the best of both worlds.
• There are many design decisions to be made when adding threading support to an existing operating system, and no perfect answers.

(When logged in, completion status appears here.)