CSE 121 Spring 2003 Project 2

Due 12 May 2003


Overview


Problem Summary

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. 


Context Switching

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.

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. 


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:
  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.  
  3. 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.)

  4. 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 /home/solaris/ieng9/cs121s/public/p2/{standard.h,thread.h}, which you should #include unchanged in your program. The first header file provides the following definitions: The second header file provides the definitions for your threads package, described below. 

Needed Data Abstractions


Needed Routines

At the minimum you must write the routines described below. Their type signatures are defined in thread.h.

Thread Exiting

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. 

Testing

We will link a test program to your module(s) to test the required operations. That is why we have provided you with the definitions in thread.h: by including this header file, we will be able to test your package.

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

You should hand in a Design Document with your project. There is no official minimum or maximum size, but I am expecting something around three to five pages long.

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

You will turn in the project using turnin. The due date is 11:59 PM on Monday, 12 May 2003.

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.