From: crawford@boole.mitre.org (Randy Crawford)
Subject: Re: reentrant code
Originator: crawford@boole.mitre.org
Organization: The MITRE Corporation, McLean, VA
Date: Mon, 14 Dec 1992 16:01:10 GMT


In article <1992Dec13.221314.26971@nntpd.lkg.dec.com>, mjg@ktbush.ogo.dec.com (Michael J. Grier) writes:
> 
> In article <1992Dec13.051634.14815@linus.mitre.org>, crawford@boole.mitre.org (Randy Crawford) writes:
> |>
> |>>The problems of reentrancy are a bit different from concurrency. 
> |>
> |>True, but reentrancy is irrelevant unless concurrency in some form (like
> |>context switching) is involved.
> |>
> 
>    Untrue.  Consider a module which implements an abstraction of a queue
> or other searching structure, which provides a service for iteration on the
> data structure.  If you specify the service such that the caller provides
> a function to execute for each element in the structure, there is again
> a need for reentrancy controls of some fashion.

Only if one part of the search cannot continue to completion before another
part begins (or resumes).  This is still concurrency (or concurrent sub-
tasks) no matter how you look at it.  When you have communicating concurrent
threads/processes/tasks/contexts/callbacks, you have concurrency.

> 
>    The reentrancy controls may be as simple as documenting, "Do not attempt
> to modify the data structure from the callback function.  If you do, the
> world may come crashing down about your ears."
> 
>    On the other hand, you might try to do something more intelligent and/or
> pro-active in the area, either setting a "busy" flag for the data structure,
> and/or making a copy of the data before beginning the iteration process.
> This takes time and memory.  [I prefer to provide both sorts of interfaces -
> ones which are faster but have more operational constraints, and safer ones
> which cost more.]

Busy flags are unnecessary unless you have multiple concurrent (sub)tasks.
Why have a busy flag unless at least two entities need to know whether a
common resource is available?  This necessarily implies some form of resource 
sharing and therefore, concurrency.  Resource sharing isn't a problem if only
one agent at a time requests them.

When you reduce the dining philosopher problem to one live philosopher and
two dead ones, you no longer have any problem sharing resources -- and no
more concurrency.

> 
>    My point is that reentrancy isn't a Boolean valued quality of a particular
> service/procedure/function.  You may be reentrant from a signal point of
> view, but not from a multi-threaded point of view.  My first example does not
> use concurrency according to any definition with which I am familliar.

A `signal-reentrant' point of view is no different from a `multi-threaded' point 
of view in terms of resource use -- both are composed of multiple executing 
contexts which must share common resources, possibly at the same time.  In those 
terms, both are undoubtedly forms of concurrency.
-- 

| Randy Crawford        crawford@mitre.org        The MITRE Corporation
|                                                 7525 Colshire Dr., MS Z421
| N=1 -> P=NP           703 883-7940              McLean, VA  22102
Newsgroups: comp.programming