NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/programm/3347

Text File | 1992-12-22 | 4.3 KB | 84 lines

Newsgroups: comp.programming
Path: sparky!uunet!spool.mu.edu!agate!linus!linus.mitre.org!boole.mitre.org!crawford
From: [e-mail] (Randy Crawford)
Subject: Re: reentrant code
Message-ID: <[e-mail]>
Sender: [e-mail] (News Service)
Nntp-Posting-Host: boole.mitre.org
Organization: The MITRE Corporation, McLean, VA
References: <[e-mail]> <[e-mail]>
Date: Tue, 22 Dec 1992 05:04:26 GMT
Lines: 71

In article <[e-mail]> [e-mail] (Peter Westlake) writes:
>Randy Crawford ([e-mail]) wrote:
>:
>: In article <[e-mail]>, [e-mail] (Michael J. Grier) writes:
>: >
>: > In article <[e-mail]>, [e-mail] (Randy Crawford) writes:
>: > |(Unattributed) wrote:
>: > |>
>: > |>>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.
>
>This sounds more like recursion than concurrency.  Yes, there are several
>activations of the access function on the stack at the same time, but this
>does not constitute concurrency any more in this case (passing in functions
>to be called back) than it does when recursing by less devious means.

In only one sense could my definition be interpreted as recursion.  Given two
tasks, A and B, after A begins execution and then stops, and B begins, B must
eventually end before A does.  If A were to complete before B, you wouldn't
have true recursion, since recursion is necessarily nested such that the parent
task will always complete no earlier than the child.  After all, if A were
defined recursively using B, A could not be computed until after B was
computed and the result used to compute A.

Of course, if the two tasks _were_ recursive and shared a common resource,
you'd have a unresolvable deadlock problem -- task B must wait for parent A to
complete because B cannot use the shared resource until parent A finishes
using it, but A cannot continue execution until after B completes and produces
the recursive result needed by A.  This is a really good example of bad design.

As Mr. Grier put it:
> 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.

Here, reentrancy is necessary only if there are one or more data shared among
these search callbacks to which they might write asynchronously, interfering
with each other's state.  In that case, I still see this as a concurrency
problem (and certainly a reentrancy problem too).

To better define my terms, I think that reentrancy exists to serve concurrency,
and as such, you cannot have reentrancy without concurrency, but you can have
concurrency without reentrancy when no shared data is vulnerable.

To pick a nit.

(BTW.  I agree with the earlier poster who suggested that I was confusing
context switching with sticky bits and memory swapping.  I meant to describe
it as `context' swapping in working set terms, not in terms of active memory
or the physical movement of memory.  Obviously, modern Unixen do not use the
sticky bit for such things.)
--

| Randy Crawford        [e-mail]        The MITRE Corporation
|                                                 7525 Colshire Dr., MS Z421
| N=1 -> P=NP           703 883-7940              McLean, VA  22102