Andrew Birrell, An Introduction to Programming With Threads
	summary by: Jaroslav Delapedraja

	This document is a brief summary of Birrell's paper, focusing on the
items I was able to cover in class on Jan 28.
	Birrell's paper begins with a discussion of when threads are necessary
and useful (e.g., device drivers, GUI code).  He then describes the
thread library that he will base his discussion on.  The library is a
user-level thread package that contains the following synchronization
tools: mutex locks, monitors (wait, signal, and broadcast on condition
variables), and alerts.  Alerts are described as dangerous and difficult
to debug, because they act like GOTO statements and make it difficult to
verify the correctness of a piece of code by local inspection.  The bulk
of his paper (and this summary) consists of descriptions of how to use
mutexes and monitors, with advice on avoiding common pitfalls.

Using Mutexes
	This section begins with two simple but important pieces of advice. 
The first is that unprotected shared data is bound to cause problems. 
The second is a more general statement about programming methodology:
Birrell recommends that each mutex-guarded section of code be thought of
as being responsible for preserving an invariant on the data it
accesses.  This methodology forces the programmer to reason carefully
about concurrent code, and helps prevent errors before they appear. 
This advice about unprotected data and invariants seems trivial, but is
actually essential because it is so easy to ignore or overlook.
	Next Birrell discusses safe methods of cheating, to allow reading of
protected data without incurring the cost of acquiring a mutex.  The
most popular use of safe cheating involves initialization routines,
where an uninitialized value demands a costly operation, but an
initialized value allows a thread to skip some of its work.  In this
case code such as: if (!init) { lock m { if (!init) initialize(); }
allows faster access to the protected variable init,  under the
assumption that once it is set to true its value will never change
again.
	Birrell then discusses two problems that can arise when working with
mutexes:  deadlocks and priority inversions.  The deadlock problem can
be solved by imposing a partial ordering on the mutexes in a program,
and requiring all threads to lock mutexes in that order only.  Priority
inversions can be caused by mid-level priority threads hogging the CPU,
preventing lower priority threads from running and unlocking a mutex
that is needed by a (blocked) higher priority thread.  Birrell does not
discuss any solutions to this problem, since it is costly to solve. 
(Priority inheritance came up in class discussion)

Using Condition Variables
	Birrell's discussion at this point shifts its focus to the correctness
and performance problems that can arise with the use of condition
variables.  The first problem discussed is caused by the lack of
guarantees on the semantics of a WAIT call.  The wait routine (called
within a lock block) is supposed to unlock a mutex, wait for a condition
to become true, and then re-lock the mutex.  But various problems can
arise because the thread library does not guarantee that the re-locking
of a mutex will be carried out immediately after a thread is awoken from
its conditional wait (within the WAIT call).  So it is possible for
another thread to lock the mutex and invalidate the condition, before
the first thread to call WAIT has a chance to leave the WAIT statement. 
The simple solution is to place all calls to WAIT within a while loop,
to force a re-verification of the expected conditions after a call to
WAIT.  (e.g. lock m{ ... while (!cond) WAIT(m, cond); ...})
	Similar situations can arise that do not affect the correctness of a
program, but cause performance degradation due to spurious wake-ups and
unnecessary contention for mutexes.  For example a BROADCAST call can
create excessive contention for a given mutex.  Another example is when
a call to SIGNAL is placed within a lock block, so that the thread to be
awoken may wake up before the mutex it needs has been freed, causing it
to waste scheduler time by waking up and then blocking on the mutex. 
Most of these performance problems can be solved by careful use of
additional mutexes at finer and finer granularities.  But the increased
code complexity of these solutions makes them more costly than the
initial performance problem, so they are usually not worth the trouble.
	Finally, Birrell discusses the "nested monitor problem," concerning
deadlock with monitors.  The main cause of this type of problem involves
nested lock statements, such that deeply nested WAIT calls only unlock
the deepest level mutex, and matching SIGNALs cannot be executed because
the higher level mutexes are not available.  This type of problem can
easily creep up, and only programmer discipline can prevent it.

Using Threads
	Birrell discusses the concept of pipelining-a method of organizing a
process as a chain of producer/consumer threads to extract parallelism. 
At its best, pipelining can produce linear speedup and full utilization
of multiprocessors.  At its worst, it can statically limit the amount of
parallelism in a program, and it can be difficult for programmers to
balance work among various stages of a pipeline.
	Excessive threading can eventually degrade performance, as too much
time is wasted in scheduling and mutex conflict resolution.  Threads
should only be used to improve code structure or to handle slow devices
and user input.  The use of threads to solely improve performance should
be done carefully, to prevent system overloading.
	Once threads are introduced to a system, all code libraries, syscalls,
and kernel level routines must be made re-entrant, as they might now be
called concurrently by multiple threads.  Of course, operating systems
that provide kernel-level threads have already taken care of this task.

Additional Techniques and Conclusion
	up calls, version stamps: skipped in lecture
	work crews: this simple idea consists of maintaining a surplus pool of
idle threads, so that when new threads are needed one of these existing
worker threads can be activated without incurring the cost of thread
creation.
	Birrell concludes by saying that Multi-threaded programs must function
efficiently and correctly, and they must not deadlock.  He argues that
this ideal can become a reality, if programmers heed the lessons of his
experience and restrict themselves to careful, disciplined use of the
thread primitives as discussed above.