Extra Credit Homework 1: User Level Threads
This assignment will teach you to build a minimal scheduler and a threading system. You can do this assignment on any Linux system, you do not need xv6. Submit your programs and the shell through Gradescope (see instructions at the bottom of this page).
NOTE: YOU CANNOT PUBLICLY RELEASE SOLUTIONS TO THIS HOMEWORK. It's ok to show your work to your future employer as a private Git repo, however any public release is prohibited.
This assignment introduces you to the notion of threads, context switching and scheduling.
Before starting to work on your thread implementation, you should understand what threads are. Here is a good link that introduces POSIX threads that you have to develop (you don't have to read all of it, just get the basic idea of what threads are and how they work): https://computing.llnl.gov/tutorials/pthreads/. If you feel like it you can also read a couple of chapters from the OSTEP book: Concurrency: An Introduction and Interlude: Thread API
The take-away idea for threads: threads are very much like processes (they can run in parallel on different physical CPUs), but they share the same address space (the address space of the process that created them). Hence all threads of the same process can read and update the all variables in that address space to communicate and collaborate on computing a complex result in parallel.
While threads share the same address space they each need their own stack as they might execute entirely different code in the program (call different functions with different arguments --- all this information has to be preserved for each thread individually, hence they need different stacks.
Now it's time to take a look at the implementation of user-level threads we will be working with. Download all the files in the src folder and and look over them (you can use Makefile to build them).
Our implementation uses one POSIX thread of the Linux system instead of a CPU (but it's not hard to extend it to a multi-threaded implementation on top of POSIX threads, i.e., just invoke the schedule function in multiple threads and run our threads similar to how xv6 does it on multiple CPUs). We do not support preemptive scheduling, i.e., there is no timer interrupt or a signal delivered, threads explicitly yield to each other. The <threads.c file provides a simple implementation for user-level threads. Specifically, you can create a new thread with the u_thread_create() function. The u_thread_create() has the following signature (it's very similar to the thread creation function in the POSIX standard.
int u_thread_create(void (*fn)(void *), void *arg);The u_thread_create() call creates a new user thread that runs inside the same process (in contrast to the kernel thread implementation, the u_thread_create() doesn't invoke a single system call, but instead just executes the function that is passed as an argument (fn) on the already allocated stack (stack). The function pointed by the fn pointer takes a void pointer as an argument (it's passed inside u_thread_create() as arg. The new user thread runs until it explicitly yields execution back to the parent with the u_yield() call. The u_yield() call doesn't do a single system call, but saves execution of the thread on the stack and switches back to the parent process (i.e., it continues execution at the line immediately following the u_thread_create() invocation. You can then create and run multiple user threads like this:
#includeThe program above will produce:#include #include "threads.h" void do_work(void *arg) { int i; for (i = 0; i < 2; i++) { printf("I'm in %s\n", (char *)arg); u_yield(); } }; int main(int argc, char *argv[]) { char a1[] = "Thread 1"; char a2[] = "Thread 2"; u_thread_create(do_work, (void*)a1); u_thread_create(do_work, (void*)a2); u_sched(); printf("Threads finished\n"); return 0; }
I'm in Thread 1 I'm in Thread 2 I'm in Thread 1 I'm in Thread 2 Threads finished
Part 1: Add scheduling
Now you have to change the scheduling logic to the system above. Specifically, you should change the u_sched() function in the threads.c file that will schedule your threads in a fair manner, i.e., even if one thread yields twice as often as another, both threads should get the same fraction of the CPU time, i.e., 50%. In other words if you have two work functions and one spins for 1,000,000 times adding an integer in each iteration of a loop, and then prints something on the screen, and then yields, and another work function that does the same but spins 2,000,000 times before printing and yielding, you should see 2x more prints from the first function on the screen -- it's fair, since the first function runs for only half the time of the second one, and deserves to be scheduled twice as often to get a fair fraction of the CPU time. The u_sched() function should implement the scheduling logic, i.e., track time, context switch to the next thread that ran the least, etc. It exits only when all thread finish. You can keep the track of time with the __rdtsc() function (see example in threads.c).Part 2: Implement Join
You should implement the int u_thread_join(void) that waits for a child thread. It returns the process id of waited-for child or -1 if none. Note you should keep track of parent-child relationship, so parents can wait on children, and well, also make sure threads can create children recursively. Note that my implementation does not deallocate resources on exit, yours should (we will test on creating more than MAX_THREADS threads, and will test recursive thread creation and join).Submit your work
Submit your solution through Gradescope Gradescope CS143A Operating Systems. Please zip all of your files and submit them. The structure of the zip file should be the following:
/ - threads.c - threads.h - Makefile