[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Programming prioritisation




On Oct 2, 2012, at 2:13 AM, "Teig, Oyvind CCS" <Oyvind.Teig@xxxxxxxxxxxxxxxx> wrote:

On 1 Oct 2012, at 17:07, Larry Dickson wrote:
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.
 
So,
1.     are there absolutely no ALT implementations that are implemented with pseudorandom choice if more than one guard is (are?) ready?

I prefer, not pseudorandom choice, but a rotating priority, i.e. P1 = (1,2,3,…,n), P2=(2,3,…,n,1), P3=(3,…,n,1,2) and so forth up to Pn. The priorities rotate one step each time the ALT fires. This insures every channel gets top priority sometimes. I suspect it will be easier to prove things about this scheme than about pseudorandom schemes. It is certainly easy to program with an indexed jump table in some form.

2.     if the answer is “absolutely no” then why all this discussion about ALT and PRI ALT?
3.     please help, because I have not understood the real life difference under that circumstance!
4.     since the term “naturally prioritized” means PRI?

I'm talking about the standard way of implementing an ALT, e.g. in the Inmos Compiler Writers Guide, describing how the component Transputer assembly instructions work. The order of disabling establishes the priority. I believe everyone has to program it this way, including analogous constructions like C select.

Larry

 
Øyvind Teig
 
 
Fra: Mailing List Robot [mailto:sympa@kent.ac.uk] På vegne av Ian East
Sendt: 1. oktober 2012 19:22
Til: Larry Dickson
Kopi: Occam Family
Emne: 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
                                    P
                        event b then
                                    Q
                        
                        idle
                                    Z
 
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
Open Channel Publishing Ltd.
(Reg. in England, Company Number 6818450)