OSI Lab2: User-level Threading

In this lab, you will implement a user-level threading package. This means you will write code that operates entirely in user space, without relying on kernel-level thread management. Your implementation will handle tasks such as creating, destroying, and scheduling threads. The threading package will be non-preemptive, meaning only one thread runs at a time, and threads voluntarily yield control to allow others to execute.

Section 0: Fetch lab2 from upstream repo

You should have requested access to and joined the upstream repo (git@github.com:NEU-CS6640-labs/egos-upstream) as part of Lab 1. If you have not yet contacted us, please do so. If you have already sent an email but did not receive an invitation to the upstream repo from GitHub, first check your spam folder. If the invitation is not there, reach out to us via the staff mailing list.

We pushed the lab2 to a remote branch upstream/lab2. Note that upstream points to the git@github.com:NEU-CS6640-labs/egos-upstream. Next, you will fetch the branch and create a lab2 branch on your local repo (i.e., your private GitHub repo origin, pointing to git@github.com:NEU-CS6640-labs/egos-<YOUR_ID>).

Here is a visualization of how the repos are organized: lab repo architecture

Here are steps to fetch lab2:

set remote repo upstream
```
 $ git remote set-url upstream git@github.com:NEU-CS6640-labs/egos-upstream.git
```
If you get error: No such remote 'upstream', run git remote add upstream git@github.com:NEU-CS6640-labs/egos-upstream.git instead.

fetch lab2 branch

$ git fetch upstream lab2

<you should see:>
...
 * [new branch]      lab2       -> upstream/lab2

create a local lab2 branch

$ git checkout --no-track -b lab2 upstream/lab2
<you should see:>
Switched to a new branch 'lab2'

confirm you’re on local branch lab2

$ git status
<you should see:>
On branch lab2
nothing to commit, working tree clean

push branch lab2 to remote repo origin
```
$ git push -u origin lab2
```
In the following, you should work on this lab2 branch, and push to the origin’s lab2 branch to submit your work. OSI staff will grade your origin:lab2 branch, so if you have any updates you want to keep from Lab1, you should manually merge them into the lab2 branch.

Section 1: User-level threading design

HOWTO: Start by thoroughly reading all the instructions to gain a basic understanding of the tasks required for the lab, rather than jumping directly into coding. Also, we expect you to revisit the instructions during the lab whenever you meet challenges.

Preview

The core of implementing your user-level threading is the following four functions in apps/user/ult.c:

// initialize the threading package
void thread_init();

// create a new thread with a given stack size
void thread_create(void (*f)(void *arg), void *arg,
                       unsigned int stack_size);

// yield to another thread (if any)
void thread_yield();

// exit the current thread
void thread_exit();

There will be detailed descriptions of their expected functionalities and suggestions of how you should implement them. But, before that, you need to understand and decide the overall design of the threading package.

In this lab, you should limit your code and modifications within the two files, apps/user/ult.c and library/queue.h.

Thread control block

A thread is a basic unit of execution: it occupies the CPU and runs its own functions until it invokes thread_yield(). Each thread is associated with a thread control block (TCB), a data structure used to manage and store information about individual threads.

In Lab 2, the TCB is defined as struct thread in apps/user/ult.c. You will determine what information to store in the thread control block. Typically, it includes the following:

thread id: A unique identifier for the thread.
status: The current execution state of the thread.
function pointer: The entry point or “main” function of the thread.
function arguments: The arguments for the thread’s “main” function.
stack pointer: The address of the top of the thread’s execution stack.
program counter (*): The address of the next instruction to execute.
registers (*): General-purpose registers storing data used by the thread.

Our skeleton code for context switching will handle storing the starred items above (i.e., the program counter and registers), so you don’t need to manage them manually. You will later see how the registers are stored in detail.

Exercise 1 Design your thread control block

Complete the definition of struct thread in apps/user/ult.c
Implement a way to generate unique thread ids.
Design the possible thread states (e.g., ready, running, terminated).
The function pointer and its argument will be sent by thread_create(). See its function signature to ensure the type of the function pointer and its argument.
Define the stack pointer as type void *.
Consider adding additional meta-data for debugging or thread management purposes.

Some notes:

You will likely revisit and update your thread control block, as you may need more information during your implementation.
It might make your life easier to write a helper function to initialize thread control blocks, so you don’t forget to initialize (later added) attributes.
You will allocate memory for each thread using malloc. Tracking this allocated memory within the thread control block will simplify thread destruction, as you will need to free the allocated memory.

Thread context switch

Each thread has its own execution context. A thread context refers to the state of a thread at a particular moment in time, including all the information necessary for your threading package to resume the thread’s execution. In egos-2k+, a thread context contains general registers, the stack, and pc (program counter, the address of the next instruction to run).

Next, we describe how egos-2k+’s context switch works in user-space:

(a) a helper function, ctx_switch()

A thread context switch stops the current running thread and switches to the next thread to run. For example, context-switching from thread t1 to t2 involves:

save registers and program counter of t1
switch the stack from t1 to t2
restore registers of t2
jump to where t2 stopped last time
t2 starts to run

The above steps will be handled by a helper function we provide, named ctx_switch:

void ctx_switch(void** old_sp, void* new_sp);

ctx_switch() pushes the registers (of the current thread) on stack and then saves the current stack pointer in *old_sp. It then sets the stack pointer to new_sp and pops the registers previously pushed. You can find ctx_switch’s implementation in grass/context.S.

(b) another helper function, ctx_start()

The above ctx_switch() switches between two runnable threads, but how to create a thread’s context in the first place? To assist context creations, we provide ctx_start:

void ctx_start(void** old_sp, void* new_sp);

Different from ctx_switch(), ctx_start() does not restore registers of a running thread (because there is none); instead, it invokes ctx_entry(), a function you will implement.

Exercise 2 Understand ctx_start()/ctx_switch()

Read the code of ctx_switch() and ctx_start() in grass/context.S.
Use “RISC-V registers” on the reference page for understanding RISC-V registers.
Use “RISC-V instruction listings” on the reference page for understanding instructions.
You will use ctx_start() to create a brand new thread with an empty stack, and use ctx_switch() to switch between existing threads.

Design wrap-up and scheduling threads

A brief summary

Here is a summary of how a thread runs: when creating a thread, allocate a thread control block (struct thread) and a stack, both using malloc(). The thread control block should store the thread’s information, such as its running state and stack pointer. Use ctx_start() to run the newly created thread for the first time. When switching to another thread, update the thread control blocks for both the current and the next thread, and then use ctx_switch() to switch their contexts. When a thread exits, ensure the threading package never resumes execution of the exited thread, and free all memory allocated for it.

Scheduling threads

Your threading package should use a simple FIFO algorithm to schedule threads: all runnable threads should be placed in a queue, and each time a thread gives up control of the CPU, the thread at the head of the queue should run next. To implement this, you need a queue:

Exercise 3 Implement queue

Implement enqueue() and dequeue() in library/queue.h
We provide some skeleton code for one possible way to implement queue. Feel free to discard it entirely and use your own design.

Some notes:

You should test your queue thoroughly. If there is a bug in your queue implementation, it will be extremely difficult to debug your user-level threading.
Your queue implementation will be used in the future labs.
Besides the runnable thread queue, you may also need another queue for the “terminated threads”. Things will be clearer when you implement thread_exit().

Section 2: Implementing core functions

In this section, you will implement the four threading interfaces:

thread_init()
thread_create()
thread_exit()
thread_yield()

and their corresponding helper functions.

Thread package initialization and thread creation

thread_init() initializes all data structures in the threading package. As a side effect, a data structure representing the current thread is created.
thread_create(void (*f)(void *arg), void *arg, unsigned int stack_size) creates a new thread. The thread executes the function f with a single argument arg. If f returns, the thread should be cleaned up as if the thread has invoked thread_exit(). When calling thread_create(), your code may yield the CPU to the new thread.
For example, thread_create(consumer, "consumer 1", 16 * 1024) should create a new thread with a 16KB stack. This thread will invoke consumer("consumer 1").

Exercise 4 Implement thread_init, thread_create, and ctx_entry

implement thread_init()
remember to create a thread control block for the current thread (i.e., the main() thread).
implement thread_create()
thread_create() should allocate a stack and a thread structure.
It can then start the new thread immediately using ctx_start().
This will invoke ctx_entry(). However, before you do so, you should put the current thread on the runnable thread queue and regard the newly created thread as the current thread.
Hint: the stack grows downwards, so ensure you assign the correct address to the stack pointer; it is not the address returned by malloc().
implement ctx_entry()
you will invoke the thread’s “main” function: f(arg).
For now, if ctx_entry directly returns, you will get a kernel exception.
(Why? because return pops the current stack and tries to go back to previous stack frame, but the current thread—which you define—has no previous stack frame, as the code jumps to ctx_entry due to ctx_start which is not a normal function call.)
Instead, you should call thread_exit().
After implementing these functions, run your code:
$ make && make qemu
...
➜ /home/cs6640 % ult  // run "ult" in egos shell
you should pass test_create() and test_stack().
“pass” means you will see the expected strings on screen (details in the comments of ult.c). Now, your code likely exits or crashes in the end because you haven’t implemented all the pieces.

Thread exiting and yielding

thread_exit() indicates that the thread has finished executing. This function should never “return”. Instead, the thread should be cleaned up, and another runnable thread (if any) should resume execution. Note that any function may call thread_exit() to terminate the current thread.
thread_yield() indicates that the current thread voluntarily yield the CPU to another runnable thread. If no other runnable thread exists, thread_yield() becomes a no-op and immediately returns to the current thread. The threading package grains “control” only when the current thread invokes one of the API functions. There is no “main loop”, so all thread scheduling decisions must be made when the threading package gains control.

Exercise 5 Implement thread_exit and thread_yield

implement thread_exit()
There are some subtleties about cleanup. When a thread exits, it cannot clean up itself because that would destroy its stack and it would no longer be able to switch to the next runnable thread. So it should switch to the next runnable thread and let that thread clean up the exited thread.
In the cleanup, you need to free the allocated thread control block, thread stack, and any allocated thread metadata (if any).
If the main() thread reaches return 0, all of your threads will be terminated even if they are still runnable. This is part of the design of user-level threads: the OS doesn’t know that a process has divided itself into threads, so when the process’s main() returns, the process terminates. To avoid this, you should make sure your main thread calls thread_exit() before it reaches return 0 (we did this in our test cases).
implement thread_yield()
Your threading package should use a simple FIFO algorithm to schedule threads.
You will want to keep track of what the current thread is. Typically, you don’t want the currently running thread to also be on the runnable queue. The runnable queue consists of those threads that are runnable, but not currently running.
You should pass all our test cases now.

Finally, submit your work

Submitting consists of three steps:

Executing this checklist:
- Fill in ~/osi/egos/slack/lab2.txt.
- Make sure that your code build with no warnings.

Push your code to GitHub:

 $ cd ~/osi/egos/
 $ git commit -am 'submit lab2'
 $ git push origin lab2

 Counting objects: ...
  ....
  To github.com/NEU-CS6640-labs/egos-<YOUR_ID>.git
     c1c38e6..59c0c6e  lab2 -> lab2

Actually commit your lab (with timestamp and git commit id):
1. Get the git commit id of your work. A commit id is a 40-character hexadecimal string. You can obtain the commit id for the last commit by running the command git log -1 --format=oneline.
2. Submit a file named git.txt to Canvas. (there will be an assignment for this lab on Canvas.) The file git.txt contains two lines: the first line is your github repo url; the second line is the git commit id that you want us to grade. Here is an example:
```
 git@github.com:NEU-CS6640-labs/egos-<YOUR_ID>.git
 29dfdadeadbeefe33421f242b5dd8312732fd3c9
```
  Notice: the repo address must start with git@github.com:... (not https://...). You can get your repo address on GitHub repo page by clicking the green “Code” button, then choose “SSH”.
3. Note: You can submit as many times as you want; we will grade the last commit id submitted to Canvas. Also, you can submit any commit id in your pushed git history; again, we will grade the commit id submitted to Canvas.
  Notice: if you submit multiple times, the file name (git.txt) changes to git-N.txt where N is an integer and represents how many times you’ve submitted. We will grade the file with the largest N.

NOTE: Ground truth is what and when you submitted to Canvas.

A non-existent repo address or a non-existent commit id in Canvas means that you have not submitted the lab, regardless of what you have pushed to GitHub—we will not grade it. So, please double check your submitted repo and commit id!
The time of your submission for the purposes of tracking lateness is the timestamp on Canvas, not the timestamp on GitHub.

This completes the lab.

Acknowledgments

This lab is originally designed by Robbert van Renesse and is tailored by OSI staff. A large part of the lab instructions is also borrowed from his project description.