Implementing Kernel Threads in xv6

Hi there! Welcome to this guide on integrating kernel threads into xv6. Designed for those with a foundational understanding of operating systems, this article aims to bridge theory and practical application. If you’re unfamiliar with xv6, be prepared for a challenge, but also an enriching learning experience. Think About It: What makes operating system development, especially concepts like concurrency, inherently complex?

As its creators put it, xv6 is “a simple, Unix-like teaching operating system,” created in the summer of 2006 at MIT.

In this article, we will methodically guide you through the implementation of concurrency within xv6, allowing the system to manage multiple tasks simultaneously. While concurrency will improve task management within the system, we’ll save the complexities of parallel processing for a future discussion.

What is a thread in theory?

Imagine a lightweight process, that’s the essence of a thread. Unlike their more heavyweight counterparts, traditional processes, threads within the same process collaborate by sharing vital resources like heap memory and file descriptors. However, each thread carves out its own independent stack, a dedicated space to manage its unique execution flow and keep track of its function calls.

How does a thread switch occur?

This sequence diagram illustrates the process of context switching between two threads

Thread switching is facilitated through a process known as context switching. During a context switch, the CPU’s current state, including all the registers (such as the Program Counter, which indicates the next instruction to execute), is saved. The system then loads a new set of register values corresponding to a different thread, effectively switching the execution context. This clever swap allows the CPU to jump between running different threads or processes seamlessly.

Where does xv6 save registers?

Within the architecture of xv6, two pivotal data structures orchestrate the management of the CPU’s registers: the context and the trapframe.

Kernel-Level Context (context struct)

This set of registers is used for context switching between processes within the kernel. Whenever the scheduler decides to switch the running process, it’s usually due to an interrupt — commonly a timer interrupt in xv6’s Round Robin scheduler. This transitions user-mode to kernel-mode, where the system then yields to activate the scheduler and select another process to run.

In this flow, the current process is halted in the kernel. To resume it, execution continues from the saved kernel context, eventually calling usertrapret to return to user-mode. Similarly, the newly selected process follows this same flow, resuming execution in the kernel and then transitioning back to user-mode via usertrapret to continue its user-level code execution.

Switching process context in kernel mode is done by an assembly function named swtch in kernel/swtch.S, which stores the current CPU’s registers in cpu->context and restores the process context in the CPU. The kernel can return to the scheduler by restoring cpu->context again.

User-Kernel Transitions (trapframe struct)

Whenever a process transitions from user-mode to kernel-mode, the assembly function uservec in kernel/trampoline.S is invoked, storing the process's registers in the trapframe.

When the process needs to return to user-mode from kernel-mode, usertrapret is called, which then invokes userret in assembly to restore the registers from the trapframe into the CPU.

Thus, the trapframe always contains the register states from user-mode operations, while the context struct stores the kernel-mode register states for that process.

Note that: It’s important to understand that in xv6, the kernel primarily manages a single kernel-level context per process. When the scheduler switches between threads within the same process (as implemented in this article), it largely manipulates the user-level state (saved in the trapframe) and the thread-specific stack. More sophisticated operating systems often employ a finer-grained approach where the kernel maintains a separate kernel-level context for each individual thread. This allows for more efficient scheduling and can be crucial for leveraging true parallelism on multi-core processors, as each thread can be independently scheduled onto a different CPU core. We will likely explore this distinction further in future discussions on parallelism.

Low-Level Architecture of Context Switching

Context switching is truly the lowest level of code in software. It’s so foundational that parts of the OS must be written in assembly language, dealing directly with CPU registers. This low-level operation is exemplified by files like swtch.S and trampoline.S in xv6, both following the principle of storing and restoring registers to switch between processes or threads.

The swtch function in kernel/swtch.S uses the following signature:

void swtch(struct context *old, struct context *new);

Assembly Code:

swtch:
    sd ra, 0(a0)
    sd sp, 8(a0)
    sd s0, 16(a0)
    ...
    ld ra, 0(a1)
    ld sp, 8(a1)
    ld s0, 16(a1)
    ...
    ret

The function saves the current registers into struct context *old, and restores registers from struct context *new, essentially starting execution of the new process exactly where it last stopped, without losing the old process's state. This mirrors a similar logic in user-mode transitions.

Assembly code wasn’t that terrifying, right? :D

Managing Thread Stacks

Why Separate Stacks?

Each thread requires its own stack to manage function calls, store local variables, and keep track of return addresses. Sharing a stack among threads would lead to data corruption and unpredictable behavior, as threads could overwrite each other’s data.

Stack Allocation:

The stack is used to store data in user-mode, so the address of the stack is pointed to by trapframe->sp, and it must be a valid user-mode address for the process. An effective method is to create an array with the desired size for the thread's stack. When allocating the thread, you pass the pointer of the last element in the array to trapframe->sp, ensuring the stack starts at the correct address.

Stack Overflow:

There’s always a risk of stack overflow, which occurs when a thread exceeds its allocated stack space. This can lead to program crashes or erratic behavior. Although implementing mitigation strategies might be beyond this article’s scope, it’s important to be aware of this risk.

How does xv6 handle processes?

In this article, we will adopt the straightforward method xv6 uses for managing processes to handle threads as well. In xv6, processes are given a preset space: the system initializes 64 processes (denoted by NPROC) at kernel startup. These processes are stored in an array, initially marked as unused. When the system needs to run a new process, it simply finds an unused entry in this array and allocates it for the new process.

In a similar fashion, we will define NTHREAD, analogous to NPROC, to establish the maximum number of threads each process can support. We will create an array of size NTHREAD to manage these threads. However, memory allocation for a thread's trapframe and stack will occur dynamically only when a new thread is created.

This approach allows us to manage multiple threads per process, maintaining the simplicity of xv6’s existing architecture while enhancing its capability to handle concurrent tasks.

Note that: The fixed-size thread array (NTHREAD = 32) simplifies implementation but limits scalability. If a process requires more threads than allowed, this design becomes restrictive. Exploring dynamic allocation or using alternative data structures like linked lists could provide more flexibility, accommodating a greater number of threads per process.

#define NPROC        64  // maximum number of processes
#define NTHREAD      32  // maximum number of threads in each process

This sequence diagram illustrates the flow of creating processes and threads in xv6.

Modifying the Process Structure for Thread Management

Based on the diagram, we need to modify the struct proc in xv6 to accommodate threads. By integrating threads into the process structure, we enhance the system's ability to manage and schedule threads effectively. Here’s how we modify the struct procin the kernel/proc.h file:

struct proc {
    int pid;                        // Process ID
    ...
    struct thread threads[NTHREAD]; // All threads in process
    struct thread *current_thread;  // Pointer to the current running thread
};

Process States in xv6:

Before defining our struct thread, we need to establish an enumeration for the states a thread can have, similar to process states.

• UNUSED: Available for allocation as a new process.
• RUNNABLE: Waiting for the scheduler to assign CPU resources.
• RUNNING: Currently executing.
• SLEEPING: Paused and waiting for an interrupt.

For threads, we’ll map these states accordingly:

• THREAD_UNUSED: Available for allocation as a new thread within a process.
• THREAD_RUNNABLE: Waiting for the scheduler to assign CPU resources.
• THREAD_RUNNING: Currently executing.
• THREAD_JOINED: Waiting for another thread to complete (it’s not crucial in the initial steps).

These states will guide the management and scheduling of threads, aligning with how processes are handled.

enum threadstate {
    THREAD_UNUSED,
    THREAD_RUNNABLE,
    THREAD_RUNNING,
    THREAD_JOINED,
};

Thread structure

Now, let’s define our struct thread. Each thread needs several key components:

• Trapframe: Essential for context switching, allowing each thread to save and restore its state.
• Thread ID: A unique identifier for each thread, similar to a process ID.
• State: To track the current status of the thread.

Here’s a basic outline of how the struct thread look:

struct thread {
    enum threadstate state;
    struct trapframe *trapframe;
    uint id;
    uint join; // later
};

Implementing the Thread System Call

Each thread requires specific parameters for its creation to ensure it functions correctly. Here are the necessary parameters:

1. Pointer to the Function: This is the function that the thread will execute.
2. Argument for the Function: Input for the function that the thread starts.
3. Stack Address: The memory address for the thread’s stack.
4. Return Value: The thread system call returns the thread ID if successful, indicating a new thread was created. If unsuccessful, it returns 0.

Given these requirements, the signature of our thread system call will be as follows. Add this to user/user.h to define the interface:

int thread(void *start_thread, int *stack_address, void *arg);

This signature sets up the necessary infrastructure for creating threads, ensuring that the function, arguments, and stack are correctly specified and managed.

Now that we have laid the groundwork, it’s time to implement the thread system call and the allocthread() function. For those familiar with xv6, adding a new system call should be a familiar process. Here’s how you can add the thread system call:

// syscall.h
// Add the following line to define the new system call number
#define SYS_thread 22

// syscall.c
// Declare the system call function
extern uint64 sys_thread(void);

// Add the system call to the syscalls array
static uint64 (*syscalls[])(void) = {
    ...
    [SYS_thread] sys_thread,
};

// usys.pl
// Add the following entry to ensure the thread 
// system call can be accessed by user space programs
entry("thread");

// sysproc.c
// Define the function stub for the system call:
uint64
sys_thread(void)
{
    uint64 start_thread, stack_address, arg;
    argaddr(0, &start_thread);
    argaddr(1, &stack_address);
    argaddr(2, &arg);
    struct thread *t = allocthread(start_thread, stack_address, arg);
    return t ? t->id : 0;
}

Initializing Multi-Threading for Processes

When allocthread() is called for the first time in a process, we need to enable multi-threading for that process. The main thread, which previously ran the entire process, will now be managed as part of the thread array. The first entry in our threads array is reserved for this main thread. Here’s how we can initialize and enable multi-threading:

// sets a thread's state to unused and frees its resources.
void freethread(struct thread *t) {
    t->state = THREAD_UNUSED;
    if(t->trapframe)
        kfree((void*)t->trapframe);
    t->trapframe = 0;
    t->id = 0;
    t->join = 0; // later
}

// initializes threading for a process, setting up the main thread 
// and preparing the threads array for future threads.
struct thread* initthread(struct proc *p) {
    if (!p->current_thread) {
        for (int i = 0; i < NTHREAD; ++i) {
            p->threads[i].trapframe = 0;
            freethread(&p->threads[i]);
        }

        // initialize main thread
        struct thread *t = &p->threads[0];
        t->id = p->pid;
        if((t->trapframe = (struct trapframe*)kalloc()) == 0){
            freethread(t);
            return 0;
        }
        t->state = THREAD_RUNNING;
        p->current_thread = t;
    }
    return p->current_thread;
}

// frees current running thread and schedules another thread to run.
// kills the process if no more thread can schedule.
void exitthread() {
    struct proc *p = myproc();
    freethread(p->current_thread);
    if (!thread_schd(p)) {
        setkilled(p);
    }
}

To optimize resource allocation, we need to ensure that all threads are freed when a process is deallocated. This involves modifying the freeproc function. Additionally, to properly initialize threading, we should set the default value of current_thread to NULL in procinit(), where the procs array is initialized in kernel/proc.c :

void procinit(void) {
  struct proc *p;
  ...
  for(p = proc; p < &proc[NPROC]; p++) {
      ...
      p->state = UNUSED;
      p->current_thread = 0;
  }
}

static void freeproc(struct proc *p) {
  ...
  p->state = UNUSED;
  p->current_thread = 0;
  for (int i = 0; i < NTHREAD; ++i) {
      freethread(&p->threads[i]);
  }
}

Implementing allocthread

To allocate a new thread, we must first initialize multi-threading for the process using initthread. Next, we find an unused thread slot and initialize its trapframe. Here's a breakdown of the key registers involved:

1. Program Counter (epc): Points to the start function for the thread.
2. Return Address (ra): This register stores the address to return to after function execution. (We will use this later)
3. Stack Pointer (sp): Points to the thread’s stack address.
4. First Arg (a0): Holds the first argument for the start function.

Here’s how the allocthread function is implemented:

struct thread* allocthread(uint64 start_thread, uint64 stack_address, uint64 arg) {
    struct proc *p = myproc();
    if (!initthread(p)) {
        return 0;
    }
    for (struct thread *t = p->threads; t < p->threads + NTHREAD; t++) {
        if (t->state == THREAD_UNUSED) {
            t->id = allocpid();
            if((t->trapframe = (struct trapframe*)kalloc()) == 0){
                freethread(t);
                break;
            }

            t->state = THREAD_RUNNABLE;
            // Initialize trapframe
            *t->trapframe = *p->current_thread->trapframe;
            t->trapframe->sp = stack_address;
            t->trapframe->a0 = arg;
            t->trapframe->epc = (uint64)start_thread;
            return t;
        }
    }
    return 0;
}

Updating the Scheduler for Thread Management

With thread creation in place, the next step is to update the xv6 scheduler to accommodate thread scheduling. Scheduling is an NP-hard problem with various algorithms available. However, xv6 chooses a simple round-robin approach due to its educational nature.

Round-Robin: xv6 employs a simple round-robin scheduling algorithm, where each process or thread is given an equal opportunity to run. Although xv6 doesn’t use time slices explicitly in the traditional sense, it relies on timer interrupts to switch processes, ensuring that CPU time is evenly distributed among runnable processes.

In implementing threads, we ensure the scheduler maintains implicit invariants, such as treating all runnable threads with equal priority. By cycling through threads systematically, xv6 guarantees that each runnable thread is given a chance to execute, ensuring basic fairness in CPU allocation.

Key Steps:

• Find Runnable Thread: The function cycles through threads starting from the current thread, ensuring fair scheduling.
• Set Trapframe: Updates the trapframe by saving the previous one and loading the target thread’s trapframe to execute, following context switch principles.

Here’s how we can implement this:

int thread_sched(struct proc *p) {
    if (!p->current_thread) {
        return 1;
    }
    if (p->current_thread->state == THREAD_RUNNING) {
        p->current_thread->state = THREAD_RUNNABLE;
    }

    struct thread *next = 0;
    struct thread *t = p->current_thread + 1;

    for (int i = 0; i < NTHREAD; i++, t++) {
        if (t >= p->threads + NTHREAD) {
            t = p->threads;
        }
        if (t->state == THREAD_RUNNABLE) {
            next = t;
            break;
        }
    }

    if (next == 0) {
        return 0;
    } else if (p->current_thread != next) {
        next->state = THREAD_RUNNING;
        struct thread *prev = p->current_thread;
        p->current_thread = next;
        if (prev->trapframe) {
            *prev->trapframe = *p->trapframe;
        }
        *p->trapframe = *next->trapframe;
    }
    return 1;
}

void scheduler(void) {
  ...
      if(p->state == RUNNABLE) {
        if (thread_schd(p)) { // <- Add thread schedling layer
            p->state = RUNNING;
            c->proc = p;
            swtch(&c->context, &p->context);

            ...
        }
      ...
}

Exit Thread System Call

We’ve already implemented the freethread and exitthread functions, but it's valuable to add a system call to exit the current running thread from any point the user desires. This capability is useful for thread termination. Here’s how you can add it as a syscall:

uint64 exitthread(void *return_value);

// syscall.h
#define SYS_exitthread 23

// syscall.c
extern uint64 sys_exitthread(void);

static uint64 (*syscalls[])(void) = {
    ...
    [SYS_exitthread] sys_exitthread,
};

// usys.pl
entry("exitthread");

// sysproc.c
uint64
sys_exitthread(void)
{
    uint64 return_value;
    argaddr(0, &return_value); // unused for now
    exitthread();
    return 0;
}

This addition allows users to terminate threads gracefully from any point, providing greater control over thread lifecycle management.

Handling Thread Termination

After implementing allocthread , exitthreadand updating the scheduler, we need to handle thread termination. This involves freeing its resources, removing it from the scheduler, and selecting another thread to run if necessary. Thread termination can occur through two different paths: successful completion or thread failure.

Successful Thread Termination:

By exposing exitthread as a syscall, users can cleanly exit from a thread at any desired point, such as the end of a thread function. Here’s an example in a test program:

void *my_thread(void *arg) {
    // THREAD CODE...
    exitthread(return_value); // syscall to exit thread
}

int main() {
    thread(my_thread, STACK_ADDRESS, arg); // syscall to allocthread
}

User-Space Library Approach:

A more refined approach entails developing a straightforward user-space library akin to pthread, enveloping thread functions within a structured framework. This library effectively automates the management of a thread's lifecycle.

// User-space internal threads runner function
void __internal_thread_start(void (*start_function)()) {
    void *return_value = start_function(); // Start thread
    exitthread(return_value);              // Terminate thread (syscall)
}

// User-space function to allocate thread
void create_thread(void (*start_function)(), void *stack_address) {
    // syscall to allocthread
    thread(__internal_thread_start, stack_address, start_function);
}

Example in a Test Program using this user-space thread library:

void *my_thread() {
    // THREAD CODE...
    return value;
}

int main() {
    // Calls user-space thread library
    create_thread(my_thread, STACK_ADDRESS);
}

Note that: you can modify the thread library to accept two inputs for the thread start argument: a0 for the library's internal thread start function and a1 for the developer's argument in the my_thread function. I'm assuming you're familiar with the process and can figure it out on your own.

Thread Failure Termination

When dealing with thread failures, if the thread in question isn’t the main thread, we can simply exit that specific thread. However, in this implementation, if the main thread fails, we opt to terminate the entire process, including all threads.

Whenever a failure occurs, the system traps to the kernel and enters the usertrap function in kernel/trap.c. This function is invoked whenever a user program makes a syscall, a device interrupt occurs, or an exception arises in the user program.

Key Checks in usertrap:

1. System Call: r_scause() == 8 indicates a system call.
2. Device Interrupt: (which_dev = devintr()) != 0 signals a device interrupt, such as a timer.
3. Exceptions: Other conditions are checked for exceptions.
4. Thread Handling: If the failure is not related to the main thread, the thread can be exited gracefully. Otherwise, the entire process is terminated to manage the failure effectively.

Modifying usertrap:

We add a condition to handle thread-specific errors. This ensures that if the failure is not related to the main thread (which necessitates terminating the process), we handle it appropriately:

// trap.c
void usertrap(void) {
  ...
  } else if (p->current_thread && p->current_thread->id != p->pid) {
      printf("usertrap(): thread unexpected scause 0x%lx pid=%d tid=%d\n", r_scause(), p->pid, p->current_thread->id);
      printf("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
      exitthread();
  } else {
  ...
}

Handling Thread Termination Without User-Space Library or Exit System Call

So far, we’ve discussed that when a thread wants to finish successfully, an exitthread syscall or a user-space library is typically required. But consider this: Can we track thread completion without these tools?

Yes, we can! It’s important to note that what I’m about to suggest isn’t the conventional method an OS uses to detect thread completion. However, this new approach offers a creative way to trick the system into recognizing when a thread has finished, without the need for a user-space library to wrap around our threads. Just a bit of fun experimentation! :))

Take this as a bonus for educational purposes and a deeper understanding of OS interrupt handling. This exploration provides insight into the inner workings of operating systems, especially how they manage interrupts and process transitions.

Okay, let’s revisit this concept. As mentioned earlier, we’ll explore the Return Address (ra) register. In this ingenious method, we create a controlled exception deliberately!

Why and How?

We need to regain kernel control when a thread finishes. Instead of terminating a thread using a standard syscall, we can intentionally cause an exception that redirects control back to the kernel, specifically into the usertrap function.

Here’s the Trick:

The Return Address (ra) stores the return location post-execution. By setting ra to an illegal address, we ensure that once the thread function concludes, it attempts to return to this unauthorized address. This results in an exception, seamlessly transferring control back to the kernel. It's a simple, unconventional approach that cleverly avoids the need for a user-mode library.

Here’s how we can set ra in allocthread:

struct thread* allocthread(uint64 start_thread, uint64 stack_address, uint64 arg) {
    struct proc *p = myproc();
    if (!initthread(p)) {
        return 0;
    }
    for (struct thread *t = p->threads; t < p->threads + NTHREAD; t++) {
        if (t->state == THREAD_UNUSED) {
            t->id = allocpid();
            if((t->trapframe = (struct trapframe*)kalloc()) == 0){
                freethread(t);
                break;
            }
            t->state = THREAD_RUNNABLE;
            // Initialize trapframe
            *t->trapframe = *p->current_thread->trapframe;
            t->trapframe->sp = stack_address;
            t->trapframe->a0 = arg;
            t->trapframe->ra = -1;  // Illegal address for trap (non-standard termination)
            t->trapframe->epc = (uint64)start_thread;
            return t;
        }
    }
    return 0;
}

And here’s how we can modify usertrap:

// trap.c
void usertrap(void) {
  ...
  } else if (p->current_thread && p->current_thread->id != p->pid) {
      if (r_sepc() != r_stval() || r_scause() != 0xc) {
          printf("usertrap(): thread unexpected scause 0x%lx pid=%d tid=%d\n", r_scause(), p->pid, p->current_thread->id);
          printf("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
      } else {
          uint64 return_value = p->trapframe->a0;
          printf("usertrap(): thread %d finished with value %lu\n", p->current_thread->id, return_value);
      }
      exitthread();
  } else {
  ...
}

Explanation

Non-Main Thread Checks: In the usertrap function, if the current thread isn’t the main thread (i.e., it's distinct from the process itself), an unexpected trap can indicate two scenarios:

Successfully Completed Thread:

• If the program counter (sepc) points to the illegal address set during thread creation, this means the thread has finished executing.
• In this case, stval should match the epc, and scause should be 0xc, indicating an Instruction Page Fault. This signals that the thread has completed successfully.

Thread Failure:

• If an unexpected condition occurs, we log the error details.

After identifying a completed or failed thread, resources are freed using exitthread(). If no runnable threads remain, the process is terminated. Additionally, you can retrieve the thread’s return value from p->trapframe->a0 and pass it to exitthread, helping to manage thread completion data and coordinate subsequent tasks.

This flowchart illustrates the lifecycle of thread, from initialization to scheduling and trap handling.

Testing Thread Implementation with a User Program

To verify that our thread implementation works as expected, let’s create a simple user program that spawns three threads. Each thread will perform a counting task, iterating through a specific range of numbers:

• Thread 1 : Counts from 101 to 200.
• Thread 2 : Counts from 201 to 300.
• Thread 3 : Counts from 301 to 400.

Here’s the code for the user program:

// user/threadtest.c
void *my_thread(void *arg) {
    uint64 number = (uint64) arg;
    for (int i = 0; i < 100; ++i) {
        number++;
        printf("%lu\n", number);
    }
    return (void *) number;
}

int main(int argc, char *argv[]) {
    int sp1[STACK_SIZE], sp2[STACK_SIZE], sp3[STACK_SIZE];

    int ta = thread(my_thread, sp1 + STACK_SIZE, (void *) 100);
    printf("NEW THREAD CREATED %d\n", ta);

    int tb = thread(my_thread, sp2 + STACK_SIZE, (void *) 200);
    printf("NEW THREAD CREATED %d\n", tb);

    int tc = thread(my_thread, sp3 + STACK_SIZE, (void *) 300);
    printf("NEW THREAD CREATED %d\n", tc);

    while(1) {
        // Busy-wait loop, we will join on threads later
    }

    printf("DONE\n");
}

Expected vs. Actual Output

When running the test program, we expect an output similar to this:

NEW THREAD CREATED 3
101
102
...
NEW THREAD CREATED 4
201
202
...

However, you might encounter something unexpected:

NEW THREAD CREATED 3
101
102
...
NEW THREAD CREATED 4
3
4
...

What’s Happening?

This discrepancy arises because the argument isn’t passed correctly to the threads. Let’s break down why this occurs:

Consider this scenario: Thread A calls a system call (e.g., printing involves calling the write syscall for each character). During kernel execution, handling system calls might trigger a timer interrupt, leading to kerneltrap() in kernel/trap.c.

Here’s the issue:

1. Kerneltrap and Context Switch: In kerneltrap, the yield function is called, triggering the scheduler to select a new process or thread. A different thread may be chosen.
2. Return to System Call: After finishing kerneltrap, the system returns to handling the syscall. Since the process hasn’t changed, it attempts to update the syscall return value in the trapframe a0. This can lead to incorrect arguments if the thread context changed.
3. Process Context: “Since the process hasn’t changed” means we are switching back using the same context for every thread in each process. This context is used for context switching within the kernel. For more advanced handling of parallelism, introducing a new context for each thread would be necessary.

This sequence diagram illustrates the process when a timer interrupt occurs during a system call in xv6. Thread A initiates a system call, but during its execution, a timer interrupt triggers the kernel to enter kerneltrap. The scheduler is invoked and selects Thread B to run next. Upon resuming, the syscall attempts to update the return value in the trapframe, leading to an incorrect argument in Thread B due to not handling the context switch correctly.

To address this, the syscall function must consider both process and thread changes:

• If a new thread is running, the syscall return value should update a0 in the old thread's trapframe, without altering the new thread's trapframe.
• If the thread remains unchanged or there’s no multi-threading, the process trapframe should be updated as usual.

Additionally, there’s a simpler alternative: we could ignore thread scheduling when yield is called from kerneltrap. However, this approach isn't recommended.

Updated syscall function

Update syscall function kernel/syscall.c :

void syscall(void) {
    int num;
    struct proc *p = myproc();
    struct thread *oldt = p->current_thread;
    uint64 ret;

    num = p->trapframe->a7;
    if (num > 0 && num < NELEM(syscalls) && syscalls[num]) {
        ret = syscalls[num]();
    } else {
        printf("%d %s: unknown sys call %d\n", p->pid, p->name, num);
        ret = -1;
    }

    struct thread *newt = p->current_thread;
    if (oldt != newt) {
        if (!oldt)
            oldt = &p->threads[0];
        oldt->trapframe->a0 = ret;
    } 
    if (oldt == newt || p->current_thread == oldt) {
        p->trapframe->a0 = ret;
    }
}

This change ensures that the syscall return value is correctly assigned, preserving thread arguments and initial states across interrupts, leading to expected behavior.

Implementing the Join Functionality

The purpose of the join is to synchronize thread execution. Typically, when the main program exits, all threads terminate. In our test program, we used an infinite loop to let threads complete. With join, a thread can block its execution until the specified thread finishes, either by completing or failing.

To implement this, we introduce a join variable in the thread structure, initialized to 0, indicating no threads are being joined. When a thread A joins B, we set threadA.join = threadB.id and update threadA.state to THREAD_JOINED.

When threadB exits, we check the threads array and restore any threads that had joined threadB to a RUNNABLE state, clearing their join field.

The join system call allows one thread to wait for another. Think About It: What potential issues could arise if the joining thread never receives a signal that the other thread has finished?

Adding jointhread System Call

We add a new system call, jointhread, which takes an ID and returns 0 if joined successfully, or a negative value otherwise. We must ensure no circular joins occur, as they lead to deadlocks.

The jointhread system call returns 0 when joining is successful, meaning the current thread will wait until the specified thread completes. Negative error codes denote specific issues: -1 for deadlock detection, preventing circular waits; -2 for an invalid thread ID, indicating the specified thread doesn’t exist; and -3 if t multi-thread has not enabled, avoiding redundant operations.

// syscall.h
#define SYS_jointhread 24

// syscall.c
extern uint64 sys_jointhread(void);

static uint64 (*syscalls[])(void) = {
    ...
    [SYS_jointhread] sys_jointhread,
};

// usys.pl
entry("jointhread");

// sysproc.c
uint64
sys_jointhread(void)
{
    int join_id;
    argint(0, &join_id);
    return jointhread(join_id);
}

int
jointhread(uint join_id)
{
    struct proc *p = myproc();
    struct thread *t = p->current_thread;
    if (!t) {
        return -3;
    }

    int found = 0;
    uint current_id = join_id;
    while (current_id != 0) {
        if (current_id == t->id) {
            return -1; // deadlock
        }

        uint target_id = current_id;
        current_id = 0;
        for (int i = 0; i < NTHREAD; i++) {
            if (p->threads[i].id == target_id) {
                current_id = p->threads[i].join;
                found = 1;
                break;
            }
        }
    }

    if (!found) {
        return -2;
    } else {
        t->join = join_id;
        t->state = THREAD_JOINED;
        yield(); // schedule another thread to run
        return 0;
    }
}

void
exitthread()
{
    struct proc *p = myproc();
    uint id = p->current_thread->id;
    for (struct thread *t = p->threads; t < p->threads + NTHREAD; t++) {
        if (t->state == THREAD_JOINED && t->join == id) {
            t->join = 0;
            t->state = THREAD_RUNNABLE;
        }
    }

    freethread(p->current_thread);
    if (!thread_schd(p)) {
        setkilled(p);
    }
}

Key Considerations:

• Deadlock Prevention: Ensure no circular joins occur; a thread cannot join another if it creates a cycle.
• State Management: Update the state and join variables appropriately to restore thread execution only when the associated thread completes.
• Self-Join Prevention: This is inherently managed by deadlock prevention. If a thread attempts to join itself, it gets detected as a potential deadlock and is handled accordingly by returning -1 as an error code.
• Unexpected Thread Failure: Whenever a thread completes or fails, exitthread must be called to handle cleanup. Once executed, exitthread notifies all threads that are joined on the terminating thread, ensuring they are informed of the completion or failure and can proceed accordingly.

Updated User Program with Join

With the join functionality implemented, the user program can now manage thread execution more effectively, allowing each thread to complete before proceeding. Here’s the updated program:

void *my_thread(void *arg) {
    uint64 number = (uint64) arg;
    for (int i = 0; i < 100; ++i) {
        number++;
        printf("%lu\n", number);
    }
    return (void *) number;
}

int main(int argc, char *argv[]) {
    int sp1[STACK_SIZE], sp2[STACK_SIZE], sp3[STACK_SIZE];

    int ta = thread(my_thread, sp1 + STACK_SIZE, (void *) 100);
    printf("NEW THREAD CREATED %d\n", ta);

    int tb = thread(my_thread, sp2 + STACK_SIZE, (void *) 200);
    printf("NEW THREAD CREATED %d\n", tb);

    int tc = thread(my_thread, sp3 + STACK_SIZE, (void *) 300);
    printf("NEW THREAD CREATED %d\n", tc);

    jointhread(ta);
    jointhread(tb);
    jointhread(tc);

    printf("DONE\n");
}

Expected Output

NEW THREAD CREATED 3
101
102
...
NEW THREAD CREATED 4
201
202
...
NEW THREAD CREATED 5
301
302
...
184
185
...
399
400
DONE

Limitations of Current Implementation

While this article focuses on introducing concurrency through kernel threads in xv6, it’s important to understand the limitations related to true parallelism, particularly in the context of multi-core processors.

Single Context Per Process : In xv6, a single kernel-level context is maintained per process rather than per thread. This means that all threads within a process share the same execution context in the kernel, limiting the ability to independently schedule threads on different CPU cores. As a result, the current implementation does not fully leverage multi-core processors for parallel execution.

Conclusion

In this article, we’ve expanded xv6’s capabilities by integrating threading support, enabling the OS to handle concurrency. We explored thread creation, scheduling, and synchronization through the implementation of system calls like allocthread and jointhread. By addressing traps and ensuring proper resource management, we prevented deadlocks and ensured smooth execution.

This flowchart illustrates the comprehensive lifecycle of thread management in xv6

Looking Ahead

In future articles, we’ll explore topics like thread locks and how to implement parallelism for multi-core processors. These will make xv6 even more powerful.