CS6640 Lab2: User-level Threading

In this lab, you will implement a threading package that runs on user-level; meaning, it is not kernel but user-level code (which you will write) to manage threads. That includes creating, destroying, and scheduling threads. The threading package is non-preemptive: only one thread can run at a time and threads voluntarily release control to other threads.

Fetch lab2 from upstream repo

You should have received an email from GitHub (in your email registered at GitHub) to invite you joining NEU-CS6640-labs/egos-upstream. Please accept the invitation. If you don’t receive the email, first check your spam folder and then let us know via 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.git. 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>.git).

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. CS6640 staff will grade your origin:lab2 branch, so if you have any updates you want to keep from Lab1, you should merge/rebase to the lab2 branch.

Section 1: User-level threading design

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, app/user/ult.c and app/user/queue.h.

Thread control block

A thread is a running unit: it occupied the CPU and runs its own functions until it invokes thread_yield(). Each thread has a thread control block, which is a data structure used to manage and store information about individual threads. In lab2, this is defined as struct thread in app/user/ult.c. You will need to decide what information stored in the thread control block. Usually, it will at least contain:

thread id: a unique identifier of a thread
status: the thread’s current execution state
a function pointer: the “main” function of a thread
function arguments: argument(s) of the thread’s “main” function
stack pointer: the top of the thread’s execution stack
program counter (*): the address of the next instruction to be executed
registers (*): general-purpose registers that store data used by the thread

Our skeleton code (context switch) will help you store the stared items above (i.e., program counter and registers), so you don’t have to worry about them. You will see how the registers are stored later.

Exercise 1 Design your thread control block

Fill in the struct thread in app/user/ult.c
You will need to implement a way to generate unique thread ids.
You will need to design what status a thread can have (like 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.
Stack pointer is of type void *.
You may want to fill in more meta-data for debugging or thread management purpose.

Some notes:

You will likely come back 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 malloc some memory for each thread. Tracking allocated memory in the thread control block will make destroying threads easier, when you 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 brief summary of how a thread runs: when creating a thread, you will want to allocate (malloc) a thread control block (struct thread), as well as a stack (also allocated by malloc()). The thread control block should keep track of this thread’s information like the running state and the stack pointer. You also want to use ctx_start() to run the newly created thread for the first time. When switching to another thread, you will update the thread control blocks of the current and the next threads, and then use ctx_switch() to actual switch their contexts. When a thread exits, you want to make sure the threading package never returns to it, and free all the allocated memory for the thread.

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 do this, you need a queue:

Exercise 3 Implement queue

Implement enqueue() and dequeue() in apps/user/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.
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 the 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 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 directly.
For example, thread_create(consumer, "consumer 1", 16 * 1024) should create a new thread with a stack of 16 KB. This thread invokes 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: stack grows downwards, so be careful with what address will be assigned to 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() means that the thread is done 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() and terminate the current thread.
thread_yield() means that the current thread voluntarily wants to yield the CPU to another runnable thread. If there is no other runnable thread, thread yield is a no-op and returns immediately to the current thread. The threading package obtains “control” only when the current thread invokes one of the API functions. There is no “main loop”, so all thread scheduling decisions have to be made when the threading package obtains 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 your 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 ~/cs6640/egos/slack/lab2.txt.
- Make sure that your code build with no warnings.

Push your code to GitHub:

 $ cd ~/cs6640/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 CS6640 staff. A large part of the lab instructions is also borrowed from his project description.