You are to implement GTThreads -- a non-preemptive user-level thread package with an API similar to Pthreads. You are to demonstrate your library by applying it to solve a simple producer-consumer problem, and then use it to build a combining tree.
First you must implement the core of the thread library as well as a thread scheduler. The schedular may be a simple round-robin scheduler, though interested students are encouraged to explore more complex designs.
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);
Then, you have to test your implementation of GTThreads on a producer–consumer problem. The problem statement is as follows:
You have two temperature sensors, which are producing readings at random intervals of time. The readings are written to single global queue. There is a client thread which is waiting on the producers to fill data in the queue so it can read from it. You have to implement each sensor as a thread, and the client as a thread. The client must read from the queue when there is data and sleep if it is empty. The producer threads have to lock the queue before they fill it with data.
Once you have successfully implemented the above problem, you build a combining tree using your library. The problem statement is as follows.
When multiple threads are running in a system, and the system makes the threads wait at a certain point in the processing till all the concerned threads have reached that point is called Barrier Synchronization. The point at which the threads are made to stop and wait is called the “Barrier”. The program moves on if and only if all the threads reach the barrier. In a combining tree, we use multiple barriers to synchronise our processing.
In your program, there will be seven different threads and each thread will sleep for a random amount of seconds and simulate processing for a random interval of time. At Barrier 1, we will synchronise three threads. Each thread will have been deemed to arrive at the barrier if they have completed 1000 processing cycles. At Barrier 2, we will synchronise the remaining 4 threads at 1500 processing cycles. Finally all the seven threads should synchronise at Barrier 3, with each thread having completed 3000 processing cycles.
NOTE : You can change the barrier limit for the number of processing cycles, as long as you can show you are synchronising at the barrier. A simple way to show that a thread has reached the barrier is by putting out a puts statement.
VERY IMPORTANT: Your algorithm should not have deadlocks regardless
of the specifics of your thread system. You should not rely on the order that
threads run or on the lack of preemption; an evil TA may well test with a
different thread library or may add extra calls the gtthread_yield().
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. We suggest that you use the getcontext(), setcontext(), makecontext(),
and swapcontext()
Unix standard library routines to help you with your implementation. Manual
pages for them are available on CoC Unix systems. Note that of these functions
do not act like normal C functions; in fact, that's the point of them. When you
call swapcontext(),
your thread stops and another one wakes up; if you are looking at the code,
then the line of code following a swapcontext() does not execute until
some other thread swaps back to you.
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 with the getcontext(),
etc., functions, before moving on to the nice library interface.
Use at least 100kb for thread stacks, if you call any of the printf()
family of functions; 10kb has been observed to overrun, at least when using GNU
libc.
Note that this project is about cooperative threading only. You do not need
to worry about automatic thread switching based on time passing by; in fact,
the standard setcontext,
etc., functions do not support this.
General submission instructions are on the main course web page. Your submission should include:
README
file including: