User Level Threading Library

This library was just a fun way to learn about how threads were implemented using round robin I plan on improving this to utilize multilevel feedback queues (MLFQ) to improve scheduling.

Usage

#include "lib/uthread.h"

// To use multiple threads, create an array of threads
int *threads = new int[x] // x is the amount of threads we want

// CALL THIS FIRST
int uthread_init(int quantum_usecs); // Initializes the main thread TCB and enables user level interrupts for round robin
                            // quantum_usecs is the microseconds you want the threads to context switch
                            // Returns 0 on success, exits (-1) program if error happens

int uthread_create(void *(*start_routine)(void *), void *arg); // Creates a thread that runs a function
                                                            // that takes in an array of arguments
                                                            // Returns the thread id created

int uthread_once(uthread_once_t *once_control, void(*init_routine)(void)); // Executes the init_routine once for a set of threads

int uthread_join(int tid, void **retval); // Blocks for thread to finish and sets the return value

// e.g.
unsigned long *local_cnt;
// ...
uthread_join(thread, (void **)&local_cnt); // When it is finished joining, local_cnt will have your value

You can compile using "make", test it using "make test" and run it on our example Monte Carlo Pi estimation program, pi.cpp which can be compiled used "make pi"

TCB

TCB.h and TCB.cpp contains the underlying data structures used to implement the user level threads. It utilizes <ucontext.h> in order to store the thread context using makecontext() which saves the thread context and is used to set the entry point of the thread using a stub which allows us to manage the thread exiting.

uthread

uthread.cpp and uthread.h contains the algorithms used to apply the threads in a round robin (RR) manner. It holds the join and finished queues for each thread as well as the states of the thread and how the threads are managed by the main thread.

Control Flow and Logic

When the program starts and uthread_init() is called, it creates a main thread, sets up the interrupt timer, and sets up the join, finished, and ready queue for our threads.

uthread_create() then creates our thread to run our start routine.

While the program runs, when the main thread calls uthread_join() or the interrupt timer goes off, it will cause the running thread to yield and context switch by popping our ready queue. Our New Thread is now the running thread.

When our running thread New Thread finishes computing, it will set its return value in uthread_exit() and stub(). Then inside uthread_exit() it will block itself and move to the finished queue then yield back to another thread or the main thread.

When the main thread is back, it will finish uthread_join() by cleaning up the finished threads. Afterwards, it will re-enable interrupts.

What I've Learned

I've learned how threads are managed especially using the main thread. Since the threads created are used to deal with the computation of the start_routine, we need a main thread to deal with the joining and cleaning up of the thread after it finishes computation and reenters the stub. As well as scheduling using interrupts with signals.