The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion OO Concurrency

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Oct 8 1992, 7:45 am
Newsgroups: comp.object, comp.lang.smalltalk, comp.lang.eiffel
From: cjmch...@dsg.cs.tcd.ie (Ciaran McHale)
Date: Thu, 8 Oct 1992 13:52:01 GMT
Local: Thurs, Oct 8 1992 9:52 am
Subject: Re: OO Concurrency
In <1992Oct7.144936.1...@bony1.bony.com> rich...@bony1.bony.com

(Richard Bielak) writes:
>cjmch...@dsg.cs.tcd.ie (Ciaran McHale) writes:
>>Richard writes:
>>>Ciaran writes:
>>>>[can pre-/post-conditions be evaluated safely in the face of concurrent
>>>>executions?]
>>>You can divide features of a class into "querries" and "commands".
>>>Querries only read the object's attributes and return some value.
>>>Commands modify the object.

>>Indeed, that is one way to handle it. But it has some limitations:

>>        o The readers/writer (queries/commands as you call them) policy
>>          may be artifically constraining the potential for
>          concurrency.

>Since objects contain data and concurrent objects contain data shared
>by many threads, so the concurrency *must* be constrained.

I didn't express myself clearly in my previous posting. I'll try again.
Consider the following class:

Class Foo
"declare instance variables"

A(...)
{
something := x;
}

B(...)
{
y := ...;
}
end Foo;

Basically, B is a writer on one part of the object (the variable "y")
and A is an reader on a _different_ part of the object (the variable
"x"). So, if concurreny is allowed, the synchronisation constraints on
A and B might state that:

1. B cannot execute if B is already executing (i.e., mutex with
respect to itself)
2. There is no restriction on invocations of A.

Notice that the potential concurrency is greater than than allowed by
labeling everything as either a "(whole object) reader" or "(whole
object) writer". By recognising that some operations only read/write
sub-parts of an object, while other operations read/write other
sub-parts we can have more potential for concurrency.

Now let us consider how certain pre-conditions may restrict the
potential concurrency of the object. In particular, consider the
following which attaches a precondion on A.

Class Bar
"declare instance variables"

A(...)
precondition: y > 10;
{
something := x;
}

B(...)
{
y := ...;
}
end Bar;

A's precondition reads the value of "y", which is updated in B. Thus,
the synchronisation constraints on the object might be:

1. as stated previously.
2. as stated previously.
3. A's precondition may not be evaluated while B is executing
(and visa versa).

Because there is a strong link between the evaluation of A's
precondition and the execution of A, it is tempting to lump them
together; doing so allows us to simplify the above synchronisation
constraints into:

1. B cannot execute if A or B is executing.
2. A cannot execute if B is executing.

While this is certainly a possible solution, it is constricting the
potential concurrency of the object (as can be seen if you compare these
synchronisation constraints to the original ones I specified).

That's what I tried (but failed:-) to say in my previous posting.

I agree with Richard that:

>Since objects contain data and concurrent objects contain data shared
>by many threads, so the concurrency *must* be constrained.

However, unfortunately, pre-/post-conditions seem to reduce the
potential for concurrency within an object. This is _not_ to say that
pre-/post-conditions are a bad idea; only that more work needs to be
done to integrate them with synchronisation mechanisms.

BTW, Maurice Herlihy holds a rather different opinion on concurrency
control (reference at end of this posting).

>>        o Most likely it would be the programmer's responsibility to
>>          take the pre-/post-conditions into account when writing the
>>          synchronisation code for the object. I think this gives
>>          programmers more than enough rope to hang themselves with.

>keyword be needed for routines that are "writers" (commands).

What I meant by that comment is that programmers know they have to look
at the code bodies of operations when they are deciding on a
synchronisation policy for the object, but they may fail to _also_ take
pre-/post-conditions into account when doing this. I think this issue
is independant of whether one expresses synchronisation constraints in
terms of guards, path expressions or keywords such as

@article{Misc-11,
author =      "Maurice Herlihy",
title =      "{A Methodology for Implementing Highly Concurrent Data
Structures}",
journal =      "SIGPLAN Notices",
year =      "1990",
volume =      "25",
number =      "3",
pages =      "197--206",
month =      mar,
note =      "Special Issue: Second ACM SIGPLAN Synmposium on
Principles \& Practice of Parallel Programming
(PPOPP)",
abstract =      "A {\em concurrent object\/} is a data structure shared
by concurrent processes. Conventional techniques for
implementing concurrent objects typically rely on
{\em critical sections\/}: ensuring that only one
process at a time can operate on the object.
Nevertheless, critical sections are poorly suited for
asynchronous systems: If one process is halted or
delayed in a critical section, other, non-faulty
processes will be unable to progress. By contrast, a
concurrent object implementation is
{\em non-blocking\/} is it always guarantees that some
process will complete an operation in a finite number
of steps, and it is wait-free if it guarantees that
{\em each\/} process will complete an operation in a
finite number of steps. This paper proposes a new
methodology for constructing non-blocking and wait-free
implementations of concurrent objects. The object's
representation and operations are written as stylised
sequential programs, with no explicit synchronisation.
Each sequential operation will is automatically
transformed into a non-blocking or wait-free operation
using novel synchronisation and memory management
algorithms. These algorithms are presented for a
multiple instruction/multiple data (MIMD) architecture
in which $n$ processes communicate by applying
{\em read}, {\em write}, and {\em compare\&swap\/}
operations to a shared memory.",
annote =      "I can't seem to grasp all of this paper. However, what
I do understand is that this is important research.
Hopefully in a few years the ideas in this paper will
have matured a bit more and will be more accessable."

}

Ciaran.
--
Ciaran McHale                                                             ----
Department of Computer Science, Trinity College, Dublin 2, Ireland.       \bi/
Telephone: +353-1-7021539 FAX: +353-1-772204 email: cjmch...@dsg.cs.tcd.ie \/