A Minimal User-Level Thread Package

Part of 22C:116, Advanced Operating Systems On-Line Collection
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

General

The machine-independent thread package described here is written in C and may be incorporated into C or C++ programs to allow use of non-preemptive multithreaded programming. This package was developed as a pedagogical example, and has been used for instructional purposes under a variety of UNIX (including Linux and MacOS X) and Windows implementations. It should also work under CodeWarrior 7.0 on MacOS 9; some 'improvement' put into MacOS 10.3 broke it.

The machine independence of this package has limits! It makes reasonable assumptions for 32-bit architectures, but not all machines are guaranteed to follow these assumptions. When compiling on modern 64-bit machines this package may work if you force the compiler to use 32-bit pointers. The code needs to be rewritten to use modern and more portable C programming conventions, but even this offers no guarantees.


User Interface

Setup

void thread_manager_init()
void thread_launch( int size, void (* proc)(int), int param )
void thread_manager_start()

Prior to using any thread management routines, the thread manager must be initialized by a call to thread_manager_init. This clears the ready list and also reverse engineers the context switching mechanism of the host machine.

A call to thread_launch() will add one new thread to the ready list. This thread will run in a stack of the given size and when it runs, it will call proc(param) exactly once prior to termination. The code of proc is referred to as the body of the thread.

As soon as an initial ready list has been created, thread_manager_start() may be called to begin the execution of the bodies of all of the threads in the ready list. This routine does not return until there are no ready threads, either because all threads have terminated or because there is a deadlock. The thread manager does not distinguish between these two situations!

Threads may perform any computation, call any procedures, or address any static variables in the program, so long as the dynamic storage requirement for automatic variables and procedure linkage does not overflow the stack of the calling thread. Threads may call thread_launch() to create other threads.

Within a Thread

void thread_relinquish()
void thread_free( void * ptr)
void thread_exit()

When a thread calls thread_relinquish(), its state is changed from running to ready, and then some running thread (usually some other thread) is selected and run.

The thread_free() routine is entirely compatable with the free() routine of standard C; it is included here because a call to free() does not always function correctly when called from within a thread. The problem is caused by error checking in free() that is incompatable with the thread package although quite reasonable in any other context.

When a thread is finished, its body may return or it may call thread_exit(); these are equivalent. In either case, that thread's stack is deallocated and some other thread is run. If no threads remain, the thread package terminates.

Utility Routines

void thread_startup_report()  -- a diagnostic tool
void thread_safety_check()    -- check for stack overflow

A call to thread_startup_report() will yield a report of the results of the thread manager's work reverse engineering the host context switching facilities. These are based on the standard C library routines setjmp() and longjmp(); as a result, they depend on both the host hardware and the compiler being used.

A call to thread_safety_check() will check to see that the current thread's stack is within the bounds established when it was launched. This is primarily intended as a debugging aid.

Synchronization

void thread_semaphore_init( struct semaphore * s, int v )
void thread_wait( struct thread_semaphore * s )
void thread_signal( struct thread_semaphore * s )

Thread semaphores may be allocated freely as components of user data structures and they may be initialized at any time prior to use with calls to thread_semaphore_init(). Once a semaphore is initialized, threads may perform the standard semaphore operations wait and signal using calls to thread_wait() and thread_signal(). Semaphores are inexpensive, occupying only three words of memory.


Deficiencies and Limitations

This thread manager has been successfully tested for the example demonstration application under HP-UX using the gcc (GNU C), the CC (HP's C++) and c89 (HP's ANSI C) compilers. It works correctly under MacOS X (Objective-C) versions prior to 10.3, and Linux (GNU C). The source code requires no changes for any of these machines, despite the fact that the stack grows up on some, down on others, and the fact that the size and structure of the thread context description varies from 24 bytes on the Intel 486 to 200 bytes on the HP PA RISC architecture and 768 bytes on the Power PC (Macintosh).

This thread manager has missing pieces! Specifically, it does not include preemptive scheduling nor does it include support for parallel execution on a real multiprocessor. These features were left out deliberately! This thread package is intended as the base for student assignments in an introductory operating system class with where the emphasis is on how processes are implemented on a uniprocessor. Another interesting extension, suggested by Bryan Christianson, is to add thread deletion, so that one thread may force the immediate termination of another.


Obtaining a Copy

The C source code, threads.c, for this thread package is available, along with a header file, threads.h, defining the interface to the package. Take a copy and play with it, but please keep the attributions of original authorship and add your attribution as a change notice in the program header!

An example demonstrating the use of this package is also available. A second example demonstrating the use of semaphores and producer-consumer synchronization is also available.

Warning: The source code for this package gets quite arcane! The mechanisms by which it manages to be machine independent are fascinating enough that they have, over the years, distracted many students from the assignments they were supposed to be doing with this package.