Re: Programming prioritisation

On 1 Oct 2012, at 17:07, Larry Dickson wrote:

PRI ALT is merely a 'choice' operator, i.e. a selection, with no pre-emption. If something more important demands a response once the choice is made then tough.
But you accept this, according to your PS at the end.

NO! In a 'when' construct, any running process is pre-empted by a higher priority one (higher up list), whenever it's guard becomes ready. When the higher pri one terminates then it will resume. Sorry if that was not clear.

It also presents problems when combined in parallel with others of its ilk, causing Bill Roscoe (Understanding Concurrent Systems (UCS), p.487) to abandon "prioritised choice".
That is a head-in-the-sand attitude, since all real implementations of ALT are naturally prioritized. There is a danger of starvation, yes, but you have to specifically program against that. Just running ALT, which legally can be implemented by what amounts to a PRI ALT and is therefore unfair in an uncontrolled way, does not solve any starvation problems.

The problem arises when you compose PRI constructions in parallel with conflicting priority, which might arise through the pattern of communication across a network of processes. For example:

PAR

PRI PAR
a! w
b! x

PRI ALT

b? y
... respond to b

a? z
... respond to a

which deadlocks. (Excuse the tabs. I too favour 2-space indents, but not with variable width font.)

Whatever approach we take, a 'global' prioritisation of events must be declared, with scope encompassing the entire system affected.

PRI PAR is closer to PVI but runs into considerable semantic difficulty :
– since, by definition, prioritised processes cannot run concurrently, time-slicing via a scheduler
is merely a convenience, obscuring the reality, especially when they communicate via rendezvous
– the construct reduces to become meaningless, should enough processors become available to run
every process independently (which may be acceptable in practice, but not in theory, since we'd like
the meaning of any program to remain the same, without regard to the platform on which it runs);
then again it may not be acceptable in practice.

Note that, as with PRI ALT, the problem of composition can be overcome with a declaration of prioritisation that has adequate scope.

What I seek, and what I think is required for simple, transparent programming of many behaviours must reflect multiple ways in which to interact with a single process, not dissimilar to multiple 'methods' with a single object. The simplest example I can come up with, which is trivial to implement on the humblest micro which supports PVI, is where a single event requires no response but must be counted, and where that count affects somehow the response to other events. This is pretty tricky to accomplish with PRI PAR, and has no use for PRI ALT.
A loop around a PRI ALT that embraces all the ISRs in one high-priority process would do what you want:

PRI PAR
-- All the ISRs are in one high-priority process
INT counter :
SEQ
counter := 0
WHILE TRUE
PRI ALT
counter.event ? signal
counter := counter + 1
event2 ? whatever
-- use counter
event3 ? whatever
-- use counter
low.priority.code(triggering.channels)

Each of the interrupt branches has some soft channel that it uses to trigger the low-priority code (i.e. main loop), and can transmit the counter as needed. Or the PRI ALT can be enclosed in a SEQ and a single triggering channel used, which amounts to an OR of all the interrupts. ALTs (PRI or otherwise) are very useful for broadcasting updates like this, a task NOT well adapted to the "each stimulus has its own thread" approach.

If starvation is a danger, three PRI ALTs can be branched to, based on what fired last, each giving a different priority sequence.

I agree it achieves something similar, but it still presumes concurrency with the lower priority process. Communication with that process will be both contrived and potentially messy. How will the low priority process learn the counter value? We're back to channels between processes of differing priority, which is precisely what I wish to avoid. Combined, these have much more in common with sequential behaviour than concurrent.

Also, what if one of the lower priority processes in the ALT took a long time to complete. We will miss 'ticks'. It's not the behaviour I wanted.

Your proposal is anyway far less transparent than :

when

event a then

event b then

…

idle

where 'idle' equates with a SKIP guard. And I prize transparency above all else. The meaning ascribed to priority here is (IMHO) crystal clear.

The relative 'weight' of P and Q are immaterial.

Again, I have not described 'when' very well here, for which I apologise. The idea is that each clause is recursive (remains available after the termination of its guarded process) until it either disables itself or is disabled by a peer. The complete construction terminates only once all its member clauses terminate.

Yes, this does mean shared variables, but 1) we restrict these to a single construct (which can have a danger sign painted on it) and 2) we alleviate the risk with the restriction that only a single 'owner' can assign them. As we know, people have been building such systems around PVI for a very long time, with nothing more than a little care. When it comes to formal correctness, it's my understanding that CSP has difficulty with prioritisation anyway.

And I'd still like to keep prioritisation in a single construct (and thus interpretation) only. You've combined the two.

I'm not saying that my proposal is any way ideal, but just that there is a problem here (which may indeed relate to the difficulty the CSP folk have in dealing with prioritisation). (Incidentally, Bill Roscoe in UCS proposes establishing prioritisation over a system, in the form of a partial order. I'm not sure what the implications are for programming but I think he is saying "program without prioritisation, then impose one", without embellishing the language in any other way, then explore its behaviour (with FDR). I'm still not sure what the implications for programming are.)

Ian

PS I shall have very little time from now for a few days, so may have to pass on further discussion, though I shall still read further posts. It's been fun, even if we've failed to convince each other!

Ian East

ian.east@xxxxxxxxxxxxxxxxxxxxxxxxx

Open Channel Publishing Ltd.

(Reg. in England, Company Number 6818450)