Concurrency
As of summer 2000, we are pursuing two interrelated approaches to concurrency.
The high-level approach asks what are good interfaces
for front-end runtimes that want to support concurrency?
The low-level approach asks what are the
well-understood mechanisms that might be used to implement concurrency?
Our list of problems that have to be solved
relates more to the high-level approach; the point of view is mostly,
but not entirely, that of the front end.
We've also made a
very preliminary attempt at a high-level
interface,
a.k.a. ``Simon's Aunt Sally.''
These proposals may not hold up under scrutiny, but they
provide a useful point of departure.
From the low-level point of view, Norman, Christian, and some students spent
Spring 2000 studying existing techniques used to implement
concurrency.
You can read Norman's summary of the
experience and also check out the syllabus for the seminar.
The short version is that although it's not the whole story,
we have identified at least
three mechanisms: stack management, context switching, and
synchronization.
You can find more details in our submission to PLDI'01.
- We have identified many alternatives for stack management.
The approach that currently seems most promising is to move
control of the call stack from the back end to the front end.
We have a preliminary note about moving
in that direction.
Russ Cox developed some related ideas a bit further in his
student project on managing stacks.
If we carry this line of work to its logical conclusion, we may decide
that the call stack is a front-end data structure that the
back end just borrows from time to time.
- Context switching is our most fully developed area so far.
Shawn Hsiao and Olushola Olateju did some useful preliminary work in
their student project, entitled
Context Switching and Scheduling
in C--.
Starting with their ideas, and also those of Mitch Wand, Carl
Bruggeman, Oscar Waddell, and Kent Dybvig, we have
a fairly well developed proposal for context switching,
based on call/1cc.
- Thanks to work by Kate Ahn, Michael Bernstein, David Dyer, and
Hong Zhang, as well as advice from Martin Rinard, we expect C-- to
provide two mechanisms for synchronization.
On machines that can implement it efficiently and atomically, we may
provide a weak form of compare and swap.
On other machines, we anticipate providing test and set.
Contact: C-- Webmaster.
URL: http://www.cminusminus.org/.
Last edited: Mon 05 Feb 2007 14:02 EST.