From: cjmchale@dsg.cs.tcd.ie (Ciaran McHale)
Subject: Re: OO Concurrency
Organization: DSG, Dept. of Computer Science, Trinity College Dublin
Date: Thu, 8 Oct 1992 13:52:01 GMT

In <1992Oct7.144936.1652@bony1.bony.com> richieb@bony1.bony.com
(Richard Bielak) writes:
>cjmchale@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.
>
>By default all routines could be "readers" (querries). Additional
>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
"reader"/"writer".



@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: cjmchale@dsg.cs.tcd.ie \/
Newsgroups: comp.object