aTonyXiao

User-level-Thread

 
  • May 05, 2017

Project 2 : User-level-Thread report

ECS 150: Project #2 - User-level thread libraray

In this report, we are going to explain how we implemented each phase and summarize our high-level design of the structure of the shell in the end. This report also includes an appendix of the important bugs we fixed.

The problems we encountered:

Queue implementation

At first, one of us used array to implement the Queue, which acuqires a fixed size. Then we go through the instructions and found out we don’t have fixed size, thus we decide to use Linked list to implement the Queue. In order to implement the function of Queue in O(1) time. We had the ptr which indicate the head and another ptr which point to tail so the enqueue() dequeue() can be easily done in O(1). For the destroy(), we just remove the head and tail reference, then it was destroyed in O(1). iter() function is pretty tricky, we implement it as itered over the queue and pass each element in that func.

Thread API

At first, we have a pretty good understanding about how tcb contains so the progresses of uthread_create(), uthread_self() and the basic struct implementation are quite smooth, we add more element in the struct as we moved on the different phases. However the retval of uthread_join() took us some time to understand it, then we know it is just for us to catch the return value which works as garbage collection.

Preemption

For this phase, we implement a preempt test which will alternatively print out thread1 and thread2, Those threads are in an infinity loop which will trigger the time_handler to make them yield for each other. The total number of time of print was controlled by another while loop. The problem we faced is we couldn’t use iffor the condition check but while works. Later on we found out there is a race condition due to the optimization. The given Makefile use -O2 for optimization, which will remove the if condition in our test file. This is a feature in C. If we change it to -O0which stands for no optimization, if works same as while. The race condition due to optimization also mentioned in the lecture on May 5th.

Key points needed to state:

phase1:

The key for this part is to understand how queue works and how to use linked list in queue. This part was learned in ECS60.

  1. We create a linked_list stuct object,
  2. For enqueue, create a new node contain the data and append it to the tail.
  3. For dequeue, assign next with data, assign prev with queue->head, assign queue->head with next and length--.
  4. For the destroy(), we just remove the head and tail reference, then it was destroyed in O(1).
  5. iter() function is pretty tricky, we implement it as itered over the queue and pass each element in that func.

phase2:

The key for this part is to understand how thread works.

  1. Only for the first time callcreate(), We initilaize the thread tcb within the uthread_create and create two threads named currentT(main thread) and runningT when there is originally 0 thread exists. for later call We just initialize runningT when there are threads already exits. Then enqueue the threads. Call context_int function to initilize context, stack.
  2. For uthread_exit, we dequeue the runningT and catch a return value and store it in our date structure, and DONT forget to call context_switch in the end!
  3. uthread_yield is a little bit tricky, we have to use another thread object to temporarly hold the currentT, change the state of runningT, dequeue the runningT and enqueue the currentT(main thread), pass the tmp object we created to context_swtich.
  • Remark, it is cardinal to manully yield the thread before we do the preemption since if we didn’t do that, it will keep consuming resources.

phase3:

The key for this part is to know the gathering thread(the thread calling join_thread) will not complete join untill the target thread is dead.

  1. We have to check the target thread is dead or not by checking the exited and check for zombie state.
  2. If the target is dead, then we free the space of target and collect it retval.
  3. If target thread is still active, we have to block the gathering thread and run the target thread.
  • join is kind of similar to waitpid(), it collect the zombie thread and release the space.
  • also need change yield() to ignore the blocked thread.
  • unblock it when the target thread is done.

phase4:

The key for this part is to understand how contains and how that work: study how sigaction and how sigemptyset works.

  1. Using sigemptyset to initializes the signal set given by set to empty, with all signals excluded from the set. from manpage
  2. Set timer by using setitimer(), which arm/disarmed the timer.
  3. When we call preempt_disable, we assign sigact.sa_handler with SIG_IGN to go to the ignore mode
  4. When we call preempt_enable, we assign the sa_handler with timer_handler function we implement.
  • The time handler will trigger for a hundred times per second, which will cause the current running thread to yield(). The hardest part for phase4 is to determine where should enable and where should disable. We don’t want to be disrupted when we creating, yielding, exiting, so we disable them at the beginning of the function and enable at the end.
  • we spent few days to figure out the race condition due to optimization, the difference between while and if in assembly level. if sometimes will be automatically removed during the C optimazation.
Search