Project 1: GTThreads

Goal

You are to implement GTThreads -- a userlevel thread package. The goal of this project is to understand the performance of different scheduling algorithms. To do so you must implement a user level thread scheduler that can schedule multiple threads. The focus of this project is on scheduling algorithms and scheduling overheads and optimizations.

Step 1

To start with you must implement a thread library and a simple scheduler. The scheduler MUST be a preemptive scheduler. As a baseline implement a basic round robin scheduler (assuming no hardware knowledge). You must measure the performance of two pieces of code using atleast 5 different quantum values.

Step 2

In the second step you must implement different scheduling policies and compare their overheads using the same methods as Step 1. In this step you can assume that the library has knowledge of the underlying hardware. Compare the performance of each scheduling policy with the basic no-knowledge round robin scheduler. You must implement atleast the following scheduler policies

  1. A scheduler that schedules one thread per processor in the system (assume the library knows about the number of processors at complie time).
  2. A scheduler that schedules threads on basis of processor affinity.

Measure the performance impact of using different scheduling policies on different hardware. Measure on a multiple processor machine. Your schedulers must be fair and there must be no starvation.

 

Description

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);

Requirements Clarifications

Suggestions(updated)

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.

Submission

Good questions and answers to them