This program, 'Uthread Library', is a user-level thread library that provides a complete interface for applications to create and run independents threads concurrently.
The implementation of this program follows four distinct steps:
- Construct the underlying data structure queue to store threads.
- Create struct TCB and global variables to store information about each thread and the thread library as the whole.
- Construct library functions for this cooperative user-level thread library.
- Add preemption function to this library.
Note: Variables names are bold. Function names are italic.
Since the required running time is O(1), so we cannot array to implement the queue. In this case, our queue is implemented as a linked list, and has three members head, tail, and size. head and tail point to the first and the lastnode in the queue, and the size keeps track of the length of the queue.We also created a struct for each node in the queue, which has members value points to its own value and next points to the next node in the queue.
Functions queue_enqueue and queue_dequeue work properly by changing what the first node and the last node point to, and what head and tail point to. Function _queue_delete works properly by having two nodes prev and curr. Once curr reachs to node needs to be deleted, prev will point to the node curr point to. Function queue_iterate can be resistant to deleted data items during iteration by assigning the variable next with next node before calling func and increamenting by assigning curr to next after calling func.
The iterate function find_ready serves for this propose. For each thread in the queue, if its state is ready, the iteration will stop and store this thread. Otherwise, queue_dequeue and queue_enqueue will be called in order to move the current first thread to the last.
The iterate function find_TCB serves for this propose. For each thread in the queue, if its TID is the given one, stop the iteration. Otherwise, keep iterating.
The iterate function change_join serves for this propse. For each thread in the queue, if its TID is the given one, queue_enqueue and queue_delete will be called in order to move the current thread to the last and stop the iteration. Otherwise, keep iterating.
We create a struct named TCB for each thread. It contains information about one thread's state, context, TID, stack pointer, return value(retval), its joined thread's return value(joinretval), the TID of the thread it's joined(joinwhich), and the TID of the thread joined itself(joinby).
We have two queues named threadqueue and zombiequeue. While the prior one stores all the ready, running, and blocked threads, the later one stores all the threads that are exited and waiting for another thread to collect its return value. We have an array ctx to store the context of each suspended threads. We have two TCBs. One for the main thread, and one for the current thread. We have AllTID to keep track total number of threads created. We have an array activethreads, and activethreads[i] == 1 indicates the thread with TID of i either in the threadqueue or zombiequeue.
The thread library is initialized by creating threadqueue, zombiequeue and assigning the current thread to two global variables main thread and the current thread. Also, the main thread will be enqueued into threadqueue.
This part will be explained based on four possible states a thread can be. Namely running, ready, blocked, and zombie, and how a thread can transfer between each state.
A running thread will be the first thread in threadqueue. If it joins to another thread, if that thread is in threadqueue, its state will be changed to blocked, and the function queue_iterate will be called with iterate function find_ready as explained above to find the next ready thread in threadqueue. retval will be assigned with this thread's joinretval if it's not NULL. If that thread is in zombiequeue, retval will be assigned with that thread's retval if it's not NULL. Also the current thread will be remained in running state. If it calls uthread_yield, queue_dequeue and queue_enqueue will be called in order to move this thread to the last, and find_ready will again be used on threadqueue. If this thread finishs all of its code, uthread_exit will be called. If this thread's joinby is not 0 or its joined by main thread, which indicates it's currently being joined by another thread, then queue_iterate will be called with iterate function find_TCB by passing this thread's joinby as one of arguments to find matched TID. Then the found thread's joinretval will be assigned with retval. If this thread has not been joined, it will be enqueued into zombiethread. For all conditions, once a thread's state changed from running to something else, it will be dequeued out of threadqueue. (It can be enqueued right after, but dequeued first)
A ready thread will be a thread in threadqueue. It changes its state to running when it becomes the first thread in threadqueue.
A blocked thread will be a thread in threadqueue, and it's currently joining another thread. Once that thread finishes, queue_iterate will be called with iterate function change_join to move this blocked thread to the end of threadqueue and change the state to ready.
A zombie thread is in zombiethread, and it waits for a thread to collect its return value. Once its collected, free(this thread) can be called.
We have create two global struct itimerval timer, timer_restore and two global struct sigaction signal_handler and signal_handler_restore, and a global sigset_t signal_sets. timer is initialized with 10hz. signal_sets is initialized with handling SIGVTALRM only. signal_handler is initialized with signal_sets and a function leads to uthread_yield. Then we call sigaction and setitimer with aboe arguments can successfully set the alarm and receive signals. In stop function, 10hz will be replaced with 0 to disable the alarm. Timer and signal handler will be restored by assigning to timer_restore and signal_handler_restore. Disable and enable work by using function sigprocmask with the first argument SIG_UNBLOCK and SIG_BLOCK.
Since threads share heap and data, all instructions involved changed of global variables or malloced spaces would be considered as critical sections. Thus, arounded by preempt_disable and preempt_enable.
We have four tester files for phase 4. They all contain three threads with thread 1 creates therad 2, thread 2 creates thread 3, and there is an infinite loop in thread 2. In test_preempt.c, we test for preempt_start by passing preempt == 1 to uthread_start. And the output is thread 1 thread 3 with no thread 2, thus works. Then, in test_preempt_stop.c, we test for preempt_stop by calling preempt_stop after uthread_start. It turns out after print thread 1, the program stuck into infinite loop, thus works. Then, in in test_preempt_disable.c, we test for preempt_disable by calling preempt_disable before the infinite loop, and the result turns out after print thread 1, the program stuck into infinite loop, thus works. Finally, in test_preempt_enable.c, we test for preempt_enable by calling preempt_disable and preempt_enable before the infinite loop, and the output is thread 1 with thread 3, thus works.
Note: Macro names are bold.
Maximum number of threads can be created is defined in macro as USHRT_MAX. The state of a thread can be ready, running, or blocked, and is defined as 0, 1, and 2 in macro correspondingly. If a thread is not in threadqueue and zombiequeue, then this thread is inactive, has defined with value 0 in macro, and 1 with active.
- We can not handle the situation when thread 1 joins thread 2, thread 2 joins thread 3, and thread 3 joins thread 1.
- In our program, if the user calls uthread_start after calling uthread_stop, then our tid will not restart from 1. The main is still 0.
- Once a thread is being freed, its TID will not be reused. For example, if there are currently five threads besides the main thread, and the thread two is being freed, then the new thread will take TID of 6 not 2.