You are to implement GTThreads -- a preemptive user-level thread package with an API similar to Pthreads (details below). 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, man setitimer(2) for details. 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.
Students are allowed to collaborate freely on this assignment in so far as discussion of concepts and techniques for solving development problems are concerned. Each student is expected to turn in code that he/she wrote him/herself, however. In addition, each student will individually give a demo to one of the TAs where he/she will demonstrate an understanding of how the code works and the concepts behind it. The demo will be given a fractional score ranging from 0.0 to 1.0, and the final score for the assignment will be the product of the code submission grade and the demo score. For example, a student that gets a 70% on the code submission but scores 0.9 on the demo will have a final grade of 63% for the project. A student who gets a 90% on the code submission but only a 0.5 on the demo will have a final grade of 45%.
The GTThreads API should contain the following functions. The library interface must match the one specified here exactly. If the signature is different, and as a result, your code is not compiled with test cases, you will get 0 credit.
void gtthread_init(long period);
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);
int gtthread_equal(gtthread_t t1, gtthread_t t2);
int gtthread_cancel(gtthread_t thread);
gtthread_t gtthread_self(void);Next, you have to implement a mutex synchronization primitive to enable safe concurrent manipulation of shared data. The API for the mutex primitive should be as follows:
int gtthread_mutex_init(gtthread_mutex_t *mutex); int gtthread_mutex_lock(gtthread_mutex_t *mutex); int gtthread_mutex_unlock(gtthread_mutex_t *mutex);
Each function in GTThreads is analagous to a PThreads function; simply
replace the gtthread_ at the beginning with pthread_.
There are two exceptions to this naming pattern:
gtthread_init(period) is a unique function to GTThreads, and
gtthread_yield() is analagous to the PThread function
sched_yield(). Be sure to 'man' the functions you are emulating so
you understand how they're supposed to behave. Consulting other PThreads
references will probably be helpful as well. Your GTThreads should behave
identically to PThreads, with the following exceptions:
gtthread_init(period) function must be called from the
main thread before any other GTThreads functions are called. It
allows the caller to specify the scheduling period (quantum in micro second),
and may also perform any other initialization you deem necessary.
gtthread_create(thread, start_routine, arg) function
does not have an attr parameter. All your threads should
behave as if they have default PThread attributes (i.e. as if you specified
NULL for attr).
gtthread_detach(thread) function. You
are not required to implement detached threads; all threads should be
joinable
gtthread_yield() function does not have to return an
error code; it may return void.
gtthread_cancel() function does not have to implement
deferred cancelation; all cancelled threads should be killed
immediately.
gtthread_mutex_init(mutex) function does not have an
attr parameter. All your mutexes should behave as if they have
default mutex attributes (i.e. as if you specified NULL for
attr).
gtthread_mutex_destroy(mutex),
gtthread_mutex_trylock(mutex), or a static initializer (e.g.
GTTHREAD_MUTEX_INITIALIZER).
main() ) is a thread exactly like any other. It should have a
gtthread_t, you should be able to get it by calling
gtthread_self() from the initial thread, and you should be
able to specify it as an argument to other GTThreads functions. The only
difference in the initial thread is how it behaves when you execute a
return instruction. You can find details on this difference in
the man page for pthread_create.
setitimer()
function can be used to generate SIGVTALRM signals at a
specified interval. You will need to establish a signal handler for the
signal (man signal(2) and signal(7) for more information on signals). Test
your package with different scheduling preiods to determine an appropriate
value.
sigsetjmp() / siglongjmp() functions, and the other is using
the makecontext() / getcontext() / setcontext() /
swapcontext() functions. Note that these functions do not act loke
normal C functions, which is in fact the point. Consult the man pages on
these functions for details.
sigsetjmp() function saves the current state
in a buffer and siglongjmp() restores the state that was
stored in the buffer. When creating a thread, first allocate memory to
store the thread state, then execute sigsetjmp() and
modify the program counter (PC) and stack pointer (SP) values in the
data structure to the values for the thread which is to be started. The
data structure is platform dependent, so you'll have to actually look
at the header file to see how to modify it.*context() functions are more
platform-independent, but may by unsafe in signals. If you choose this
approach, please report in your README any potential signal-safe issues
in your scheduler if there are any.Finally, you have to implement a solution to the classic Dining Philosophers problem using your implementation of GTThreads. The problem statement is as follows:
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.
Makefile should generate gtthread.a and
gtthread.h (gtthread.h may be made statically if you prefer.)
Both files must be in the directory
where Makefile is. If you are not familiar with Makefile, google it.
Here is one example of simple Makefile:
#### GTThread Library Makefile
CFLAGS = -Wall -pedantic
LFLAGS =
CC = gcc
RM = /bin/rm -rf
AR = ar rc
RANLIB = ranlib
LIBRARY = gtthread.a
LIB_SRC = gtthread.c gtthread_sched.c gtthread_mutex.c
LIB_OBJ = $(patsubst %.c,%.o,$(LIB_SRC))
# pattern rule for object files
%.o: %.c
$(CC) -c $(CFLAGS) $< -o $@
all: $(LIBRARY)
$(LIBRARY): $(LIB_OBJ)
$(AR) $(LIBRARY) $(LIB_OBJ)
$(RANLIB) $(LIBRARY)
clean:
$(RM) $(LIBRARY) $(LIB_OBJ)
.PHONY: depend
depend:
makedepend -Y -- $(CFLAGS) -- $(LIB_SRC) 2>/dev/null
We will go through 25 test cases to evaluate your library. Here is one example:
#include <stdio.h>
#include <stdlib.h>
#include "gtthread.h"
/* Tests creation.
Should print "Hello World!" */
void *thr1(void *in) {
printf("Hello World!\n");
fflush(stdout);
return NULL;
}
int main() {
gtthread_t t1;
gtthread_init(50000L);
gtthread_create( &t1, thr1, NULL);
while(1);
return EXIT_SUCCESS;
}
This code should be compiled with your library with something like following command:
Checks thread creation, arguments, return values for different functions, scheduling and preemption.
README file including: