EROS retrospective -- threading

[shapj@us.ibm.com]

One problem in EROS is multithreading. There are two issues, one technical
and the other social.

The social issue is that people have a very hard time "getting it" about
how multithreading is done in this kind of system. Perhaps the solution is
an example library. Would anybody care to write one that illustrates the
use of a redirector domain?

The technical issue is more serious. Oran Krieger has pointed out a fatal
flaw in the redirector design: in a multiprocessor, an invocation of the
redirector necessarily involves either a rescheduling of the redirector on
the calling processor or a cross-processor transfer. The redirector then
does the same thing in dispatching some particular thread.  Even on
small-scale multiprocessors the cost of the L2 cache line transfers can be
considerable. On larger-scale multiprocessors, where memory access times
are non-uniform, it's deadly.

On this list, we have discussed two designs for moving thread dispatch into
the kernel:

1. A kernel implemented redirector using a tree of nodes.

Think of this as a tree of nodes whose leaves are start capabilities. The
tree is traversed by the kernel and a start key to an available process is
chosen via some kernel-implemented strategy.

Can anybody propose a design by which the tree can be pre-traversed to
generate a more efficient dispatching structure?  For example, can we
usefully implemented some cache of multithread dispatch queues that is
loaded the first time the tree is examined and is subsequently efficient?

Also, the depth bound on the tree would appear to want to be a function of
the number of processors. This introduces an architectural dependency. Can
anyone suggest a reasonable bound?

2. A revision to the meaning of "available", in which every process has a
dedicated capability slot indicating the process (usually itself) whose
invocations it answers.  This introduces a possible exhaustion of the
number of multithread dispatch queues and a need to keep track of those
available processes that are not listening for themselves in much the way
that running processes must be tracked now.  It is, however, easier for the
programmer to comprehend.

The need for in-kernel redirection implies the need for in-kernel semaphore
support. The logic for this is likewise based on cross-processor
communication arguments.


Jonathan S. Shapiro, Ph. D.
Research Staff Member
IBM T.J. Watson Research Center
Email: shapj@us.ibm.com
Phone: +1 914 784 7085  (Tieline: 863)
Fax: +1 914 784 6576