README

# What Linux platform do I use.           
I am using ubuntu/trusty64 (Official Ubuntu Server 14.04 LTS builds) created by vagrant.

# How the preemptive scheduler is implemented.
* The context switch is implemented using basically three things. First one is the SIGVTALRM alarm signal. Every thread has some time do its work. Once the time is used up, an alarm signal will be delivered by kernel and we make syscalls to switch to another thread. The user level context switching is done by ucontext_t struct and system calls like setcontext, getcontext, swapcontext and makecontext. The last one is a global ready queue keeping track of all the runnable threads. When a thread is running, we dequeue that thread from the ready queue. When the thread is interrupted by the preemptive scheduler, we enqueue that thread to the back of the ready queue. So it is a round-robin preemptive scheduler.
 
* getcontext is used whenever a new thread is created. We use getcontext to save the stack frame, register values and program counter associated with the current thread. Then we use makecontext to install their start_routine, such that when we do context swtiching later using setcontext or swapcontext, the program can jump into the start_routine and continue executing.

* swapcontext is used in context switching done by the signal handler. It saves the context for current thread and switch to and run the start_routine of the next thread. setcontext is only used when a thread has exited or is cancelled. In this case, we do not need to save the current context and can directly execute the next thread in the queue.

# How to compile the library and run my program
To compile, run
```
mkdir include && mkdir lib
cd src && make
```
It will simply put the header files (gtthread.h steque.h) into include folder and library file (libgtthread.a) into lib folder. 

# How I prevent deadlocks in my dining philosopher solution.
I use a simple strategy to prevent deadlocks. Every philosopher has an index and every chopstick also has an index. For instance, the index of left chopstick is (phil_id + 4) % 5, and the index of the right chopstick is phil_id. We can just let every philosopher pick up the chopstick with the smaller index. In this way, the deadlock situation where every philopher picks up the chopstick on the same side will never happends, since exact one philosopher will not pick any chopstick in this case.

# Thoughts on the project
* In order to get the return value of a thread's start_routine, I use a wrapper function. The wrapper function will call the start_routine provided by the user, get back the return value and call pthread_exit with that return value.

* Another issue we have is to distinguish between joining a thread that has exited, joining a cancelled thread and joining a thread that is never created. In order to do this, I use a zombie_queue to keep track of all the threads that have terminated.
 
# Things that work well
* The *context syscalls work pretty well in this project and it definitely saves a lot of time since we do not need to manually link the new thread to their corresponding start_routine.

* The queue based lock works better than spin lock. I try both methods. The spin lock does not provide fairness between thread. Hence when I use my gtthread for dining philophoser problem, a large amount of meals will be eaten by 1 philosopher. On the other hand, queue lock improve this situation a lot, even though it is not as good as pthread lock.

# Things that don't work well
* I first developed this project on my local OSX machine. But it will not work because the *context syscalls are deprecated on OSX yosemite. So I switch to Ubuntu 64 bit OS.