Project 1: User-level Threads Package
Due: Thursday, January 27th 11:59pm
Overview
In Unix, the standard unit of multitasking is the process: a single thread of control in its own address space. A Unix process is a fairly heavy-weight object; to switch from one process to another can require the system to shuffle a large amount of information around. In some applications, it is more useful to have the unit of multitasking be a more light-weight object. This can be achieved by having several threads of control running within one address space: all of them share the same global variables, open files, etc.
Your assignment is to implement a simple version of this capability. The threads will communicate by waiting on conditions and signalling on these conditions. When a thread is signalled, it is passed a value which may contain some data.
All the files that you'll be given for this class can be obtained here.
This file contains two header files, thread.h and standard.h, which define the data types you must use and the functions you must implement.
All About Threads
Threads allow multiple execution paths to exist in a single address space. Although your threads share a single address space, they have separate stacks and register states. We call this private information the context of a thread.
In order for threads to be useful, it is necessary to be able to switch from one thread context to another; i.e. when a thread yields or blocks on a condition, another thread should start running. We will use the C functions setjmp and longjmp for this purpose.
Briefly, setjmp saves the current context (stack and registers) of a C program in a jmp_buf type. longjmp takes a jmpbuf argument and restores the context. So when a thread yields or blocks, it will save its context via setjmp, and then a scheduler can start a new thread via longjmp. For more information on setjmp and longjmp, consult the Unix man pages.
Conditions
You will implement a generalization of pure conditions, which have some properties of both pure conditions and semaphores. You should call this type Condition in your project. There are two basic operations associated with conditions:
- A thread can wait on a condition. If there are no queued signals on that condition (see below), then the thread blocks until the condition is signaled by a later thread. If there is at least one queued signal for that condition, then the thread is returned one signal value, and continues execution.
- A thread can signal a condition. If there are threads waiting on the condition, only one of the blocked threads is woken up ("unblocked") by the signal. If there are no waiting threads, the signal might be thrown away, or queued for the next thread that waits on this condition. (You will implement both behaviors.)
Every signal has associated with it a parameter, of type any_ptr, that will be passed to the thread woken up by the signal. Signal parameters have a variety of uses depending on the application program. They can be useful for testing your threads package, too. If you don't care about the parameter for a particular signal, just send NULL.
Standard Headers
You are provided with two standard header files, called standard.h and thread.h, which you should include unchanged in your program. The first header file provides the following definitions:
- any_ptr: This type is useful for managing objects whose type you don't want to declare. Any kind of pointer; for example, (char *), (int *), etc., can be cast to an any_ptr, and vice versa.
- Boolean: This type can have two values, TRUE (1) and FALSE (0).
- ThreadFunc: A pointer to a void function, that takes one argument of type any_ptr. You will use this type to hold the initial routine a thread enters when it is created.
The second header file provides the definitions for your threads package, described below.
Needed Data Abstractions
- A queue manager. This should be able to maintain a queue of arbitrary objects. You should be able to create a new queue, destroy a queue, insert a value at the end of a queue, return the first object from a queue, and determine (nondestructively) whether or not a queue contains any elements. The implementation of such a queue will be discussed in section.
- Some structure to hold information about a thread. This will probably contain at least a jmp_buf holding the thread context. It might contain other fields as well.
- A type, Condition, implementing a condition variable. The type signature for this is in thread.h, and must be a pointer to a struct containing (at least) two queues: a queue of threads that are blocked awaiting signals, and a queue of signals that are awaiting threads to receive them.
- A global "ready queue" which contains pointers to the contexts of all threads which are ready (i.e. not blocked on any condition and not running.)
Thread Package API
In order to clearly define the scope of this project and to make testing your code easier we are giving you an API (basically a set of procedures) that you must implement. The following is a list of all the procedures and a description of what they do.
void t_start(ThreadFunc f, any_ptr v)
You have to bootstrap the system before you can start creating threads. Normally, t_fork is called by one thread to create another thread. Initially, however, there are no threads; t_start is responsible for creating the first thread. The first thread may be one that is responsible for creating other threads, and can be created in a special manner (whatever your particular setup requires).
t_start should start all threads which your system requires internally, and should then start a thread executing the user's routine f with parameter v.
t_start does not return until all the user's threads have exited or blocked (if all are blocked, the system is deadlocked). It should set up a jmp_buf which will be longjmp'd to when deadlock is detected, or when the last thread exits. In addition, it should be possible for the main program to call t_start repeatedly.
Condition cond_create()
This routine returns a newly allocated condition, with two queues allocated for blocked threads and pending signals.
Boolean cond_is_empty(Condition cond)
Given a condition, this routine returns FALSE if some thread is blocked awaiting a signal on that condition, and TRUE if no thread is blocked on that condition.
void cond_destroy(Condition cond)
This routine destroys the condition, freeing up any memory allocated for it and its parts. After this function, cond is no longer a valid condition.
void t_yield()
This routine places the current thread on the ready queue, allowing another thread to run. It has no effect if there are no other threads on the ready queue.
any_ptr t_wait(Condition cond)
The calling thread blocks, waiting for some other thread to signal the condition (using t_sig below). Note that the context switches without t_wait returning. When this thread wakes up, t_wait returns the value that the signalling thread passed to the t_sig call (see below). If several threads wait on the same condition, they are woken up, one per signal, in FIFO order. If there are pending unreceived signals on the condition, the thread will not block, but will take the oldest unreceived signal ( i.e. , FIFO order again). The chronology of a call is:
- Check the pending signal queue.
- If it is not empty, dequeue the first value and return it. Nothing more needs to be done.
- If it is empty, the thread must wait to be signalled:
- Check the ready threads queue.
- If it is empty, the system has deadlocked, and the program should exit.
- If it is not empty, this thread must block itself and start up the first thread on the ready queue:
- Update the context part of your thread information structure (using setjmp), and add the thread structure to the condition's blocked queue.
- Dequeue the first thread from the runnable queue and longjmp to its context. This will cause it to resume execution where it was suspended.
- Eventually the blocked thread will receive a signal and be rescheduled to run. When this happens, it must find out the value of the signal that awoke it and return this value.
void t_sig(Condition cond, any_ptr val, Boolean queue_signal)
A condition cond has been signalled. val is an optional parameter that will be passed to the thread awoken by the condition. If a thread is currently blocked on the condition, it should be woken up and made ready to run. This process will be inside t_wait, and so that function will return val.
If no thread is blocked on the condition, what action is taken will depend on the queue_signal parameter. If queue_signal is TRUE, the signal info (including at least the parameter val) gets added to a ``pending signals'' queue of the condition, with the assumption that some future thread will block on the condition. If queue_signal is FALSE, the signal and parameter val are simply discarded. The former behavior resembles that of a semaphore, while the latter emulates a pure condition.
void t_fork(ThreadFunc f, any_ptr v)
This routine performs a "fork": it splits one thread into two. The first one continues as though the call did nothing; the second one begins executing routine f with parameter v.
Note: In the following we use the convention that stacks grow down; i.e., the place where stack expansion takes place is the bottom of the stack.
The new thread must have some stack space allocated for it. There are several ways to do this. One way that is in some senses cleaner than most others involves having a special "spawner" thread that is signalled by the t_fork routine. This thread lives below all allocated stack space that is in use by other threads, and is generally waiting on a special internal condition. When it is signalled, it performs the following sequence of operations:
- Allocate some space for the new thread's context.
- From the value of the signal that awoke it (the return value from t_wait), get the routine and parameter for the new thread.
- Call setjmp (this will be where the new thread begins executing).
- Append this new context to the runnable threads queue.
- Call the spawn routine recursively, via some intermediate routine with a large amount of locals (a large local array will do). This causes a block of stack space to be allocated. This space will be the stack for the new thread; as the new thread's stack grows down, it will not run into any other thread's stack (unless it overflows the space allocated for it; you should make this space large enough that this will not be a problem for the code that you write; 10000 bytes is usually far more than enough).
This recursive call must never return. If it does, it will suddenly be executing with its stack pointer in the same area as the new thread's stack pointer; this will cause nothing but grief.
Once the spawn routine has successfully recursed, it again waits on the spawn condition, waiting for another thread to fork.
The context created by the setjmp call above, that was originally placed on the runnable threads queue, will eventually start running. When it does, it should call the user's routine, with the supplied argument.

Figure: Stack configurations around a t_fork
The above figure shows how the stack is changed by the execution of a t_fork. Initially, there is some amount of stack in use by active threads. The spawner's stack space is below all other threads' stack space. When the spawner receives a signal, it first does a setjmp to its current position; this is where the new thread's stack pointer will begin. It then copies itself down the stack, through a recursive call (explained below), and blocks on its condition again. Note that its old stack area is now the property of the new thread; it may never return from the recursive call because this would cause it to try to use its old stack area, causing a conflict. The new thread's stack pointer is now where the spawner's stack pointer used to be; the spawner's old locals can now be used by the new thread (since, until it calls the user's code, it is still executing in the spawn routine).
The stack space should be allocated by using indirect recursion: the routine where the spawner normally waits for a signal should call another routine, which has a large local array, which calls the first routine again. The reason for this is that the stack pointer is at the bottom of the local space, and so the top of the next routine's locals will be just below this. If this next routine is the spawn routine again, some of its locals (the ones at the top of its area) may be overwritten by the new thread. Interposing a separate routine which does nothing but allocate stack space solves this problem.
Note that, as you have multiple threads active, you have multiple stack areas. Your thread switching routines will be jumping back and forth between them using longjmp.
- Caveat
- The way that a thread exits is by returning from the routine where it began executing: that is, the routine passed to the call to t_fork that created it. Your code must anticipate threads exiting this way and handle them correctly. You may want to have the thread queue itself on some condition that will never be signalled, or have it simply overwrite its own context with that of another runnable thread.
Grading
In order to verify the correctness of your threads implementation we will run a series of tests against your source code. The tests will use your thread API to perform a set of various operations. These tests will include but are not limited to:
Thread package initialization (t_start)
Creation of new threads (t_fork)
Synchronization and communication between threads using conditions.
Proper thread stack space allocation
Deadlock detection
We will run these tests by compiling the source code you turn in with a main() function that we implement.
Turn In
You will turn in your projects using the turnin command. In order to do this you must first tar your project files and then submit the tar file.
Example:
% tar cvf project1.tar [files]
% turnin -c cs121w -p project1 project1.tar