CS6420 - Programming Assignment 2

Overview

For this assignment, you are to implement a user level threads package we'll call GTHREADS. GTHREADS should provide pre-emptive multitasking, and should also provide a mutex locking facility. I will specify the exact API you need to provide (details below), a skeleton gthreads.c, a Makefile, and several test cases.

When I first started on this assignment, I thought it would be very challenging. I had done a similar assignment previously using SUNOS and found it quite difficult. The good news is that SOLARIS provides a much better API for getting this job done, so the project is not quite as difficult as I first thought. Since that's the case, I specified a couple of extra things you need to do, just to make it interesting.

Which system to use

In order to keep some consistency in what all of us are doing, we should all develop this program on a SUN Sparc Solaris system. There are several Solaris machines generally available, notably elvis.cc.gatech.edu and asperta.cc.gatech.edu. You can log into any system on the CoC network, and then telnet to elvis by entering "telnet elvis" (from a unix system), or using the telnet window on WindowsNT and opening a connection to "elvis". Elvis has 4 CPU's and lots of memory, so it should not be a bottleneck for us getting our work done.

Coding the Program

First, get a copy of the Makefile, testgt.c, gthreads.h, and gthreads.c. To get a copy of these links, DO NOT cut and paste (this will give a Makefile that does not work). Instead, use the right mouse button and select "Save Link As..". The version of testgt.c as of this writing is complete, but we may discover errors or improvements as we go along. Watch the newsgroup for information about updated code. Do not edit gthreads.h, testgt.c, or the Makefile. Simply fill in code for all of the subroutines in gthreads.c to implement the specifications above.

Specifications

First, any program using your gthreads package must call "GThread_init", specifying the pre-emption interval in microseconds. If 0 is specified, this means to NOT do pre-empting, but instead revert to only context switching on a yield.

Threads are creating using the GThread_create function. The three parameters specified there should be self explanatory. There should be no pre-set limit in your gthreads regarding how many threads can be created, so don't pre-allocate some fixed amount of space for handling threads. Also, "create" does NOT schedule the thread immediately! It just creates it, and it is scheduled later when a thread is being pre-empted or the current thread is yielding.

Threads may call "GThread_yield" to voluntarily give up the CPU to another thread. The code for yield should just select another ready thread and transfer control to that thread at the last point in it's execution path.

Threads MUST call GThread_exit before terminating. This actually makes our job a bit easier, since you don't have to worry about what to do if a thread's "StartFunc" just exits (which pthreads allows).

You should maintain a count of active threads, and return that count in response to a "GThread_count" call. The testgt.c program will use this extensively to know when all threads have completed.

One other important point. The main program is also a thread, and should be scheduled just like all the other threads. In other words, I expect the main program of testgt.c to be pre-empted just like any other thread, and it may also call GThread_yield to yield.

GTMutex_create is called to initialize a mutex to the default "unlocked" value. GT_MUTEX is defined as a void* in gthreads.h, but of course you will make a structure of you own choosing to use for mutexes, and do a type cast to the right type.

GTMutex_lock, GTMutex_unlock and GTMutex_islocked should be self-explanatory. However, to make it more interesting, we specify the following two requirements. DO NOT SPIN waiting for a lock to free up. Instead, if a thread asks for a lock that is not available, de-schedule that thread, making a note of the mutex that it is waiting on. When the mutex is freed, re-schedule that thread (you can either schedule it immediately, or note that it is a candidate for later scheduling). Second, we will require that only the thread that locked a mutex can unlock it. In other words, if any thread other than the one that locked a mutex tries to unlock it, do not unlock it and return GT_FAILED instead.

For each mutex, keep track of the successful and unsuccessful lock attempts. testgt.c will use these values to insure things are working right.

Some Hints

To get the pre-emptive multitasking, you will need to ask the operating system for a periodic "Alarm Clock" signal, which you can then use to select another thread for execution. You do this by using the "signal" and "ualarm" unix calls. To manage the context of your threads, use the Solaris "getcontext", "setcontext", "makecontext", and "swapcontext" calls. Each of these manage a structure of type "ucontext_t", defined in "ucontext.h". Be sure to give each thread a private stack! It cannot possibly work if you don't do this.

To implement the Mutex, use the Sparc "swap" instuction. It's easy to include a small piece of assembly language code in your C program using the "asm" macro.

Compiling and linking your program

Use the Makefile I provided. This is what we will be using to compile and test your implementation.

Testing Your Program

We will test your program simply by running the test cases I provided in testgt.c. There are four test cases. You run each one individually by running "testgt 1", "testgt 2", etc. Each test case reports the success or failure of the test on stdout.

Grading Criteria

Test 1, GThread_yield testing 30%
Test 2, Pre-emptive Multitasking testing 30%
Test 3, Proper operation and scheduling of Mutexes 20%
Test 4, Proper ownership tracking of Mutexes 10%
Quality of Code (Neatness, commenting, etc) 10%

Turning In Your Program

Email your "gtelnet.c" program (not as an attachment, but just as the body of the message) to rly@cc. One way to do this is (on unix):

mail rly@cc < gthreads.c

Contact Information:

riley@cc.gatech.edu
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280

Last Modified: Jul. 6, 1998