Overview

• Problem Summary
• Context Switching
• Conditions
• Standard Headers
• Needed Data Abstractions
• Needed Routines
• Thread Exiting
• Testing
• Documentation
• Turning In
• Grading

Problem Summary

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. 

Context Switching

One needs a way 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.

The manual page for setjmp and longjmp are on sdcc7; please look there for details. 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. Read on for further details. 

Conditions

1. 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.

 
2. 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

• 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.

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.
• 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.)

Needed Routines

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:

1. Allocate some space for the new thread's context.
2. From the value of the signal that awoke it (the return value from t_wait), get the routine and parameter for the new thread.
3. Call setjmp (this will be where the new thread begins executing).
4. Append this new context to the runnable threads queue.
5. 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.

Thread Exiting

Testing

The test module, which includes main(), will be available for public use in two weeks. When you hand in your program, your makefile will link your modules with our test module to create an executable. (See Turning In.) 

Documentation

Spend some time thinking how to structure this document. Think of the design document as being the paper that you'd want someone to read who is familiar with thread.h but not with your implementation. This is the place to describe any assumptions that you made (and, why you made them) and the ramifications of those assumptions. If you think that it would describe your package well, you might sketch out a typical execution path. This is also the place to mention any known bugs.

Note that the proper use of English and a coherent writing style is important in writing this document. 

Turning In

The tar file should include a make file (titled makefile) set up such that the command `` make'' will create an executable file thread that we can run. Your executable will be the combination of your .c files and our test module (we provide the main()). Again, our test module will be available in two weeks; watch discus.ucsd.edu for details.

Grading

• Documentation 25%, described above.
• Correctness 40%: whether your program successfully does what was stated in the assignment handout and your problem specification. Bugs or logic errors found by our testing programs, or by code inspection, will lower this grade.
• Readability 20%: the degree to which your program can be read and understood by another. Good commenting is one factor, especially at the top of modules and functions. However, also remember that too many comments (e.g. one for every line!) can severely crowd a program. The code should go a long way in explaining itself: via intelligent function and variable naming, modular design, and intuitive rather than hacked-up algorithms.
• Elegance 15%: the quality of your programming solutions. This can mean good, tight algorithms; function re-use; economic utilization of memory; and enhanced performance through optimization. Note that none of these should be pursued in a way that greatly sacrifices readability. You won't lose many points here as long as you are not overly wasteful or sloppy in your code.