From: cjmchale@dsg.cs.tcd.ie (Ciaran McHale)
Subject: Re: OO Concurrency Control (Was: OO Concurrency)
Organization: DSG, Dept. of Computer Science, Trinity College Dublin
Date: Thu, 15 Oct 1992 15:55:10 GMT

In <1992Oct15.092419.1617@news.unige.ch> oscar@cui.unige.ch
(Oscar Nierstrasz) writes:
>In article 239@dsg.cs.tcd.ie, cjmchale@dsg.cs.tcd.ie (Ciaran McHale) writes:
>>[apparent paradox of simultanuously wanting synchronisation to be
>>(i) an implementation issue and (ii) part of the type specification]
>
>Actually, it's not such a paradox -- what needs to be stated clearly is
>the client/server contract that the object conforms to.  This may include
>some liveness and safety properties wrt synchronization.  Beyond that,
>the implementor should have complete freedom to choose any synchronization
>strategy that satisfies the contract.  If the "contract" is nothing more
>than a set of operations, that suggests that all requests will eventually be
>serviced.  In the case of a "container" object, the contract should state
>that the number of gets must be no more than the number of puts.  Then
>stacks and queues and other of your favourite containers (concurrent or
>sequential) may choose any synchronization scheme as long as the contract is
>satisfied.  A container that blocks "puts" when it becomes full would
>not satisfy the contract, so the contract would have to be weakened in
>such a case.

Interesting. I had not considered it in that light. The above suggests
two categories of synchronisation contracts:

	/1/ A set of operations, upon which all requests will eventually
	    be serviced.
	/2/ A "container" object which has restrictions on the ordering
	    of requests.

Oscar, were you offering these contract types purely as hypothetical
examples, or do you see these as actual classifications?

The reason I ask this question is that some researchers are wondering
how useful it would be to have hierarchies of synchronisation policies,
and how one would define sub-type relationships for such policies. I'll
give some examples to illustrate this, but first I will define the
terminology I will be using in the examples.


----start of terminology discussion----
I will express synchronisation constraints as "guards"---conditions
which must become true before an operation is allowed to execute. For
example:

	Foo: some-condition;
	Bar: another-condition;

The above guards state that an invocation of operation Foo will be
blocked until "some-conditon" becomes true. Similarly, an invocation of
Bar will be blocked until "another-condition" becomes true.

I presume that the system will automatically maintain the following
synchronisation counters:

	req(Op)		--- count of the number of requests which have
			    been made on Op
	start(Op)	--- count of the number of requests which have
			    _started_ executing Op.
	term(Op)	--- count of the number of requests which have
			    _terminated_ execution of Op.

From these, we have the following additional counters/macros:

	wait(Op) = req(Op) - start(Op)
	exec(Op) = start(Op) - term(Op)

I will also use a shorthand notation:

	exec(Op1, Op2,... OpN) = exec(Op1) + exec(Op2) + ... + exec(OpN)

(At the moment there are no standard names for synchronisation counters.
For example, both Guide and DRAGOON use different names for their
counters. The above discussion simply explains the names of the counters
which I will be using. If the reader is lost at this stage then I
suggest reading a paper on Guide or DRAGOON, or the Scheduling Predicates
paper I mentioned in my previous posting.)
----end of terminology discussion----

The basic readers/writer policy can be expressed as:

	Read: exec(Write) = 0
	Write: exec(Read, Write) = 0;

Readers priority can be expressed as:

	Read: exec(Write) = 0
	Write: exec(Read, Write) = 0 and wait(Read) = 0;

Noting the similarity between these two policies, we might say that the
readers priority is a "sub-policy" of the basic readers/writer policy.
We can see this clearly if we rewrite the above examples as:

	sync_policy Readers_Writer is
		Read: exec(Write) = 0;
		Write: exec(Read, Write) = 0;
	end;

	sync_policy Readers_Priority INHERIT Reader_Writer is
		// Read's guard is inherited by default
		Write: INHERIT and wait(Read) = 0;
	end;

[Note: I'm using the keyword "sync_policy" to refer to a synchronisation
policy in a way analogous to the keywords "type" or "class" are used in
(sequential) OO programming. DRAGOON's "behavioural" classes are similar
in concept to my "sync_policy" classes.]

We can also define Mutual_Exclusion as a "sub-policy" of Readers_Writer
as follows:

	sync_policy Mutual_Exclusion INHERIT Reader_Writer is
		Read: INHERIT and exec(Read) = 0;
		// Write's guard is inherited
	end;

Now, the following example is relevant to what Oscar said...

	sync_policy Alternation INHERIT Mutual_Exclusion is
		Write: INHERIT and start(Write) = term(Read);
		Read: INHERIT and term(Write) > start(Read);
	end;

This definition contains some redundancy but I don't think that is
relevant. What _is_ relevant is that I've defined the Alternation
policy as a sub-policy of Mutual_Exclusion. Let's draw the inheritance
hierarchy:

                            Readers_Writer
                                /   \
                               /     \
                              /       \
                             /         \
                Mutual_Exclusion   Readers_Priority
                      |
                      |
                      |
                 Alternation

An interesting question is this---is the above hierarchy compatible with
the two categories of synchronisation contracts which I saw in Oscar's
posting? To refresh your memory, the two categories are:

	/1/ A set of operations, upon which all requests will eventually
	    be serviced.
	/2/ A "container" object which has restrictions on the ordering
	    of requests.

If the "two categories" concept is valid then I would have thought that
they would have formed separate hierarchies of synchronisation policies,
which is clearly not the case here since Alternation (definitely of
category /2/) is a sub-policy of Mutual_Exclusion (of category /1/).

Of course, it could be that the categories are valid but that the
concept of hierarchies of synchronisation policies is not.

Or perhaps category /2/ is a "sub-category" of category /1/, which is
reflected in the above hierarchy by Alternation (of category /2/) being
a sub-policy of Mutual_Exclusion (of category /1/).

A last possibility is that Oscar offered those categories purely as
hypothetical examples rather arguing for them as actual
classifications. In which case, the questions I raise in this posting
are probably moot :-)

Comments, anyone?

>Ideally, contracts should be part of the type system and should be
>type-checkable.  This implies, in turn, that you shouldn't try to
>specify too much, or you will be unable to verify the contracts
>statically.  (It is not clear where the boundary lies between checking
>of type safety and program verification -- in concurrent systems, type
>checking should include some limited dynamic analysis, it seems, to
>deal with these issues.)

Agreed.


Ciaran.
-- 
---- Ciaran McHale (cjmchale@dsg.cs.tcd.ie)
\bi/ Department of Computer Science, Trinity College, Dublin 2, Ireland.
 \/  Telephone: +353-1-7021539 FAX: +353-1-6772204
Newsgroups: comp.object