Re: Teaching Concurrency

[firth@sei.cmu.edu (Robert Firth)]

In article <10330@june.cs.washington.edu> pattis@cs.washington.edu (Richard Pattis) writes:

>OK, so this begs the question: what is the "smallest" assignment that can
>use concurrency fruitfully. I would like to teach a bit about tasking in
>one of my classes, but I don't want students to get "wrong" ideas from the
>example I use.  Anyone out there have such an assignment? Is there some prime
>example out there of a good use of multi-tasking that is amenable to
>classroom instruction?

In the hope that it helps, I'll describe briefly the exercises i used
to teach concurrency as part of a real-time systems design course.
These are the one-page programs; the next step up was device drivers,
a simple message switch, &c.  A warning upfront: the tasking features
of Ada are inadequate to solve some of these exercises.

(1) delay.  the program contains one task, which simply prints
    "I'm still here" every five seconds.  explains: task structure,
    task creation and termination, delay.

(2) interleaf.  the program consists of six tasks, which do this

	print "." every second
	print "5" every five seconds
	print "6" every six seconds
	print "7" every five seconds
	print "8" every six seconds
	print a newline every 30 seconds

    explains: several tasks; reentrant use of task code (by middle 4),
    interleaving of task output; control of interleaving by priority.

(3) veryslowsort.  the program reads a list of integers and creates
    one task per integer, whose priority is given by the integer and
    whose sole action is to print the integer.  the integers are
    therefore output in task priority order, ie they are sorted.

    illustrates: dynamic task creation and priority assignment, use
    of task parameters.

(4) chain gang.  the program creates a reasonably large number of
    identical tasks (eg 100), each with a parameter that identifies
    itself.  Each task waits for a message from (task-1), prints
    "This is (task) and I have the message", and passes the message
    to (task+1).  Except that the last task sends the message to
    a master task.  The master creates the tasks, sends a message to
    the first, and waits for it to go all around the chain.

    illustrates: array of tasks, message passing, task parameters
    and dynamic task names, task blocking on message read.

(5) sampler.  one task computes the value of pi by an excruciatingly
    slowly converging series; the other task samples the computed
    value every couple of seconds or so. illustrates: simple shared
    variable, preemption of low-priority task.

(6) quantum mouse.  The program reads in a small maze, with an entry
    point and an exit point.  it creates a mouse (a task) at the
    entry point.  the task traverses the maze, creating a copy of
    itself at every branch point.  the traversal lays a trail through
    the maze, consisting of the letters ABCDE... in order, ie letter
    'J' is placed in a cell first reached by a mouse (any mouse) 10
    steps from the entry.  A mouse that can move only to a marked cell
    dies.  When the last mouse dies, the maze is printed out; every
    cell is marked with its minimum distance from the entry.

    illustrates: shared data, dynamic task replication with state
    inheritance, wait for termination of task set.

(Incidentally, the tasking features used in these exercises were
 contained in a set of subroutines described in a six-page handout and
 implemented on a bare machine in less than 200 lines of code.)