CSE 121 Spring 2003 Project 3

Due 7 June 2003

Overview

Problem Summary

For Project 3, you will extend the non-preemptive threads package of Project 2 to include priorities, preemptive scheduling, condition time-outs, and thread-safe user input from stdin. Generation of timer interrupts and exception handling will be discussed in section or in class. It is suggested that you experiment with each of these concepts prior to beginning the project.

You should write this project in C, and it should run as specified on ieng9. The latter is more of an issue than Project 2 because you will be using system calls of Unix that are not as well standardized as those that you used for Project 2.

Project 3 is due at the midnight of June 7, 2003.

Thread Priorities

Users can assign a priority to a thread from the range MinPriority (0) to MaxPriority (128). Your threads package may find it useful to use priorities outside of this range. The currently active thread should be the highest priority thread that is runnable (i.e. not blocked on a condition). Lower priority threads execute only when there are no higher priority threads ready to run. As soon as a higher priority thread is ready to execute, it preempts any lower priority thread that is currently running.

Time-outs

Your threads package will support timed conditions. For the most part, signals and conditions function the same as defined in Project 2. In Project 3, though, one will be able to set a timeout with a condition. A thread that waits on a condition for timeout milliseconds will become ready, just as if it had received a signal with a value of NULL. If the condition is signalled before that timeout, however, then the blocked thread will behave as specified in Project 2.

Pre-emptive Scheduling

In Project 2, a thread runs until it explicitly yields or waits on a condition. Thus, a thread that goes into an infinite loop will never yield the process to another thread.

In Project 3 you will preempt threads that run for too long without blocking or yielding. The interval between preemptions (called the quantum) set by a new function defined in thread.h.

The quantum will be changeable, but in your design document, you should recommend an appropriate value for the quantum. Be sure to defend why you recommended the value that you do.

Timers and Signals

Your threads package will need to set up a signal handler for timer signals sent to the process. Note, this signal handler can also help you with scheduling. We will use virtual time for the project instead of wall-clock time. Virtual time does not count CPU cycles spent on other processes, and so, is more suitable for this project. The Unix call setitimer() can be used to generate SIGVTALRM signals (i.e. virtual time signals). As covered in class, handlers using the Unix signal() system call. You will need to establish a signal handler for the SIGVTALRM signal. The handler you specify will be called when a (Unix timer) signal is received by the process. Your handler should save its context, decide which context to run next, and switch (maybe longjmp) to it. The use of all relevant Unix calls, as well as the saving and restoring of signal masks, will be covered in section or in class, but you can read about it yourself by looking at the man pages on setitimer and signal.

Do not confuse Unix signals with thread signals. Unix signals are sent via kill() or setitimer() and are handled by the handler you specify in signal(). Thread signals are implemented by your package and are sent using t_sig().

To drive the system, you will use setitimer to generate interrupts at a certain rate. The period between these interrupts is called the granularity of your thread package's clock. You will need to determine a reasonable granularity for the clock. Test your package at different granularities to determine this value. Explain in your documentation why you chose a particular granularity and be able to defend it.

Standard Headers

You will be provided with the same two standard header files, called /home/solaris/ieng9/cs121s/public/p2/{standard.h,thread.h}, which you should #include unchanged in your program. (Don't copy them into your directory, and don't hand them in.)

The following definitions have been added to the standard.h header file:

The second header file thread.h has been modified to update the interface to your threads package to reflect the new capabilities defined for project three, and to include further functionality.

Data Abstractions

The data abstractions defined for project two still pertain for this project. Modifications may be required to satisfy the specification for project two. Below are some questions worth thinking about:

System Commands

For project three you will need to become familiar with the system timer, signal (interrupt), and file control interfaces. You may need to use some of these system capabilities to implement time-slicing, condition time-outs, concurrency control (needed to satisfy safety properties), and non-blocking user input. It is suggested that you look at the man pages for the following systems calls: signal, setitimer (itimer), sigset_t, sigemptyset, sigaddset, sigprocmask, siglongjmp, sigsetjmp, and fcntl.

Some questions you may ask yourself include:

Needed Routines

At the minimum you must write the routines described below. Their type signatures are defined in thread.h. For those routines that were specified in Project 2, only the modifications to their implementation will be listed. These routines must still provide the basic functionality outlined in Project 2. Note, this project can be implemented elegantly if the threads functionality is reused for implementing itself. This was done in Project 2, for example, where we suggested that new threads can be created by a spawner thread created by t_start and activated by waiting on a condition signaled in t_fork. Describe in your documentation the degree to which you reuse thread code. 
Condition cond_create(void)
Boolean cond_is_empty(Condition cond)
void cond_destroy(Condition cond)
int cond_set_timeout(Condition cond, int msec)
Each condition can have a time-out quantum associated with it. Initially, when the condition is created it will not have a time-out value. cond_set_timeout can be used to set a time-out quantum for a condition, or to unset the time-out quantum (by specifying msec equal to zero). It will return the old time-out quantum that was previously set for that condition. If the time-out quantum is set, then when a thread blocks on that condition it will only block for the given quantum of time without being signaled. When the ticker of the blocked thread counts down to zero, the thread should be unblocked and moved to the ready queue with a signal value of NULL.

If cond_set_timeout is called when there are blocked threads on the condition, then these threads will time out based on the new quantum. For example, suppose a thread t waits on a condition with a time-out of 100 msec. After 40 msec, the time-out associated with the condition is set to 200 msec. Then, t will time out after 200 more msec have elapsed - that is, 240 msec after it initially executed t_wait. 

void t_start(ThreadFunc f, any_ptr v, Priority p)
void t_fork(ThreadFunc f, any_ptr v, Priority p)
As in Project 2, you must bootstrap the system. This requires initializing all internal threads, conditions, attributes, etc. that your package requires. In addition, t_start is responsible for creating the first thread. Al thread starts executing the user's routine f with parameter v at priority level p.

Each thread, including the initial thread, is assigned a priority. You will need to keep track of this priority for the life of the thread. This priority will be used for scheduling. The currently-running thread must be the ready thread with the highest priority. If a signal is sent to a condition upon which more than one thread is blocked, then the thread with the highest priority is the one that is unblocked. And, if Thread A signals an empty condition with a value x, after which Thread B with a higher priority signals the condition with a value y, then a thread that subsequently executes t_wait will obtain the value y. Like in Project 2, the priority with respect to blocking and signalling on conditions should be FIFO for threads with the same priority.

The stack space of a thread that has terminated (i.e., returned from the specified function) is expected to be recycled in this project. This can be accomplished in many ways. For example, the finished thread can block on a "dead-thread" condition. Then, t_fork can signal this condition instead of the spawner condition. Doing so will require some modification to spawner.

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. 

long t_set_quantum(long msec)
This routine is used to set the quantum of time that threads are allowed to execute. Once a thread has continuously run for this quantum of time it should check the ready queue to determine if another thread is available to run. If there is another thread with the same priority, then the current thread should pre-empt and allow this other thread to run. (Why do you only need to check for threads with the same priority?)

A quantum of zero indicates no preemption. The initial value of the quantum should be zero.

 int getline (char *buffer, int n) This routine reads up to n characters from standard in (file descriptor 1), placing them into array buffer. This function returns when n characters have been entererd, a \n is entered, or a ^D is entered. It returns 0 if ^D is entered, 1 otherwise. Priority t_priority() This routine returns the current priority of the thread. Priority t_set_priority(Priority p) This routine is used to set, or reset, the priority of a thread. It returns the old priority value. Note, when a thread priority is reset, it may be immediately preempted. void t_yield() This routine places the current thread on the ready queue, possibly allowing another thread to run. It has no effect if there are no other threads on the ready queue. Note, your scheduler must take into account thread priorities when selecting the next thread to execute. any_ptr t_wait(Condition cond) The calling thread blocks, waiting for some other thread to signal the condition (using t_sig below). If several threads wait on the same condition, they should be woken up, one per signal, in priority order. If there are pending unreceived signals on the condition, the thread will not block, but will take the highest priority signal (where the priority of a signal is equal to the priority of the thread that placed the signal on the queue via t_sig). 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 there are threads currently blocked on the condition, the highest priority thread should be woken up and made ready to run. This process will be inside t_wait, and so that function will return val.

As in Project 2, 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. Signals should be queued in priority order. If queue_signal is FALSE, the signal and parameter val are simply discarded.

Testing

We will link a couple of test programs to your module(s) to test the required operations defined for project three. 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 modules will include main(). We will make them available for public use within two weeks. When you hand in your program, your makefile should compile all of the test cases. (See ``Handing In'', below.)

Documentation

You should hand in a Design Document with your project. This document should provide an overview of your program's organization and design. It should serve as a rough ``road-map'' of your program that an outsider might read before tackling the code. You should list and briefly describe the major functions, sketch out a typical execution path, and explain any major design decisions or unusual algorithms. A rehash of this handout is not acceptable documentation. Look through the project description though, in it you may find many questions and other suggestions which would fit nicely into your documentation.

You may also turn in other documents with your project if you feel they will help to explain your project better (e.g. a "known bug" list if there are several known bugs, or a "README" file

Handing In

Your project must be compiled into a library by your makefile. A threads library can be created by adding these lines to your makefile (be sure to include any needed object files, including the queue implementation, in the library). For example: 
libthreads.a: file1.o file2.o
   ar crv libthreads.a file1.o file2.o
   ranlib libthreads.a
This library can then be compiled with other .o files. For example: 
file: file_x.o file_y.o libthreads.a
   gcc -o file file_x.o file_y.o libthreads.a
The completed project must be submitted via turnin. It should include all required files needed to grade your project. For example, you will need to include all of your .h and .c files, your makefile, your document, your threads library, plus others necessary files. Do not include the standard.h, thread.h, and test files which we have provided you. You must make the appropriate links to the /home/solaris/ieng9/cs121s/public/p2 directory in your make file.

The tar file should include a make file (titled makefile) set up such that the command `` make'' will create all three test executables {mintest; testthread; rtest} that we have specified for you to run. Your executables will be the combination of your .c files and our test modules (we provide the main()).

Last revised on 15 May 2003 by ryhuang.