You are to implement GTThreads -- a preemptive user-level thread package with an API similar to Pthreads. You are to demonstrate your library by further implementing a solution to the classic Dining Philosophers problem.
First you must implement the core of the thread library as well as
a thread scheduler. The scheduler must be a preemptive
round robin scheduler. Each thread is assigned a time slice(its quantum)
for which it is allowed to run. A thread is preempted if it used up
its quantum. Preemption can be achieved by using an alarm signal as
a timer. You may use the system's virtual time instead of wall-clock
time, see setitimer(2).
The preemption period in microseconds should be specified
in a function, i.e., gtthread_init(period). Any program using your
GTThreads package must call the function first.
The GTThreads API should look something like this:
int gtthread_create(gtthread_t * thread,
void * (*start_routine)(void *),
void * arg);
int gtthread_join(gtthread_t thread, void **status);
void gtthread_exit(void * retval);
void gtthread_yield(void);
gtthread_t gtthread_self(void);
int gtthread_equal(gtthread_t t1, gtthread_t t2);
int gtthread_cancel(gtthread_t thread);
Next, you have to implement a mutex synchronization primitive to enable safe concurrent manipulation of shared data. The API for the mutex primitive again follows closely Pthread's:
int gtthread_mutex_init(gtthread_mutex_t * mutex);
int gtthread_mutex_lock(gtthread_mutex_t * mutex);
int gtthread_mutex_unlock(gtthread_mutex_t * mutex);
Finally, you have to implement a solution to the classic Dining Philosophers problem using your implementation of GTThreads. The problem statement is as follows:
Five philosophers are sitting at a round table doing their two favorite things: eating and thinking. Each philosopher has their own bowl of rice, but unfortunately there are only five chopsticks for the entire table. The chopsticks are spaced equally around the table, one between each pair of neighboring rice bowls. Whenever a philosopher wants to eat, they must acquire a chopstick from the both the left and the right; if one of the two chopsticks is already in use, then the philosopher must wait hungrily until it is released. Whenever a philosopher wants to stop eating and think for a while, they must release any chopsticks they hold and put them back on the table.
In your implementation, each philosopher should have a thread which alternates between eating and thinking, spending a random amount of time in each mode. Chopsticks are a shared resource and each must be protected by a mutex. Each thread should print out status information, such as "Philosopher #1 is hungry", "Philosopher #1 tries to acquire left chopstick", "Philosopher #1 releases right chopstick", etc.
VERY IMPORTANT: Your algorithm should not have deadlocks regardless of the scheduling period used by your thread system and the order that threads run.
main(), counts as a thread just like any other. You can
get the gtthread_t for it with gtthread_self(), and it
can call or be the argument of any of the thread functions. If the
main thread gtthread_exit's, then the program should keep
going; if it return's from main() then it is
fine to exit the whole program.
Preemption can be achieved by using an alarm signal as a timer. You may use the system's virtual time instead of wall-clock time, see setitimer(2). Virtual time does not count CPU cycles spent on other processes and increments only when the process is running. The unix call setitimer() can be used to generate SIGVTALRM signals. You will need to establish a signal handler for the SIGVTALRM signal. Test your package with different scheduling periods to determine an appropriate value.
Two sets of calls for context switching are sigsetjmp/siglongjmp and
makecontext/getcontext/setcontext/swapcontext. We
suggest that you use sigsetjmp/siglongjmp since the makecontext etc. may be unsafe
in signals.
sigsetjmp() saves the current state
in a buffer and siglongjmp( ) then restores the state
that are stored in the buffer. When creating a thread,
first allocate memory to store the thread state. Then execute the sigsetjmp( ), and modify the program counter(PC) and
stack pointer(SP) to the values for the thread which is to be started.
If you choose to use the makecontext/setcontext/getcontext/swapcontext,
please report potential signal-safe problems of your scheduler if there's any.
Note that of these functions do not act like normal C functions; in fact,
that's the point of them. Manual pages for these Unix standard library routines are available on CoC Unix systems.
We also suggest that you familiarize yourself with the manual pages for
the Pthreads API functions corresponding to the ones you are asked to
implement. Manual pages for those are also available on CoC Unix systems.
Simply substitute the "gtthread_" prefix with a "pthread_" prefix, e.g.
"gtthread_create" becomes "pthread_create".
Work incrementally! First try to implement thread switching before moving on to the nice library interface.
README file including: