Re: Programming prioritisation

On Oct 1, 2012, at 8:24 AM, Ian East <ian.east@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

Hi Larry

The semantics of PRI PAR, PRI ALT and my when (intended to reflect prioritised vectored interrupts (PVI)) are quite different.

As I understand them, PVI is the same as PRI PAR, except that the waiting interrupts do not round-robin, but when they can run, the highest-priority one always goes first. As I understand it, once the ISR is entered, it runs to completion, even if a higher-priority interrupt becomes pending, unless an STI is specifically programmed in the ISR.

This can actually be implemented by a PRI ALT within a single high-priority process that implements all the ISRs.

I almost always prefer the round-robin (even going to the extent of re-prioritizing the interrupts after each ISR fires) because of the danger of starvation. ISRs should be quick, setting bits and counters, and any long-winded response should be in interruptible processes which can be activated in occam by the ISR code. If quick ISRs in a round robin do not produce good enough response, it's usually a sign that your chip is underpowered for the events it is handling. An exception could be if individual serial bytes drive an interrupt.

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.

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.

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.

The test of a language is whether there are simple, transparent solutions to simple problems. I still want a 'when' construct, in lieu of PVI.

I'm of the opinion that shared variables have their rôle to play, and that we should find a way to understand them better in order to use them safely. (UCS does address them, but I have yet to find the time to pursue this further.

Ian
PS In the description of 'when' below, P, Q, … would each run to termination, following their guard event.

Therefore there is no pre-emption, so it seems to be perfectly modeled by a PRI ALT.

Larry

I should add that the same difficulty in both interpreting and implementing 'fairness' exists as with ALT (selection/choice).