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.
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 ieng9; 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.
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.
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:
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:
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.
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.)
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.
The files you turn in 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.
We will not accept late projects.