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

Re: Programming prioritisation




On Oct 4, 2012, at 8:23 AM, "Eric Verhulst \(OLS\)" <eric.verhulst@xxxxxxxxxxxxxxxxxxxxxx> wrote:

In OpenComRTOS the equivalent of PRI PAR and PRI ALT come together. In my view, they can't be decoupled.
 
1. Tasks get a priority (at compile time). System wide attribute, so independently on which node they have been mapped. On each node, scheduling is in order of priority and preemptive.
 
2. They synchronise and exchange data using "hubs" (the equivalent of channels). The hub can be an any node as well. The hub allows N-to-N semantics (synchronisaton)
 
3. Assume we have senders en receivers synchronising in a hub. (using blocking semantics)
 
4. Depending on who comes first, either there will be receivers waiting, either there will be senders waiting. It doesn't matter on which node the tasks are mapped. The system layer handles this communication transparently.
 
5. The insertion in the waiting list(s) is in order of priority. So these lists are resorted at any insertion.
 
6. When there is a synchronisation, the highest priority waiter (top of the list) is rescheduled first. The service request returns with RC_OK.

OK, that is like a PRI ALT with priority determined by sender's task priority. Now I understand Oyvind's objection number 2: it would be indeterminate if that task had unknown priority. (That can be solved by fiat.) This is only one of the ways a PRI ALT can be programmed.

But the whole controversy is of small import in the real world, because cases mostly break two ways:

(a) If there's enough responsiveness, ALTs tend to have to wait. That almost always means the ready timing leader wins (the only exception being interrupt during the process queue rotation), and the priority does not matter.

(b) If ALTs don't wait, it's usually because the ALTing process or other multitaskers are wallowing in their response to previous stimuli while queues of screaming senders are lining up. Your hardware is underpowered, and if more than one of these screamers has a real-time response requirement, you are doomed, and once again the priority does not matter.

Larry

 
7. RC_Fail is possible with non-blocking semantics. (no matching request was waiting => return immediately, to be avoided as risk of busy polling)
 
8. RC_TO is possible if the time-out expires before the synchronisation happens.
 
This makes it also clear, that while the highest priority tasks synchronise first, one should still not assume a specific order at runtime. The order on the waiting lists depends on runtime parameters not under control of the waiting tasks. One only knows that when synchronisation happens, the highest priority tasks will be rescheduled first. Evidently, you can influence this by selecting the hubs used by the tasks.
 
 
Eric
 
From: Mailing List Robot [mailto:sympa@kent.ac.uk] On Behalf Of Larry Dickson
Sent: Thursday, October 04, 2012 4:54 PM
To: Teig, Oyvind CCS
Cc: Ian East; occam-com@xxxxxxxxxx
Subject: Re: Programming prioritisation
 
All,
 
I find this thread surprising. PRI ALT arises naturally because that is by far the easiest way to program an ALT. The order of disabling determines the priority. This seems to hold for other languages' approximations to ALT (i.e. select) and as far as I can see must hold for everyone. Fair ALTs can only be built on top of this natural PRI ALT by randomizing or rotating the order.
 
Does anyone know any other way of doing it?
 
PRI PAR, on the other hand, is harder to program than plain PAR.
 
Larry
 
On Oct 4, 2012, at 2:04 AM, "Teig, Oyvind CCS" <Oyvind.Teig@xxxxxxxxxxxxxxxx> wrote:


Ian
 
Thanks!
 
| where he rejects prioritised choice (PRI ALT) because it presents problems "when the priority orders of different parallel processes cannot be resolved".
 
1.     But if these priority orders are known and may be resolved, then PRI ALT may be useul? (I think so!)
2.     So, does a too encapsulated or out of scope PRI PAR rule out PRI ALT because the components in the ALT have UNKNOWN PAR?
3.     But then, how can PRI PAR be out of scope for a component? Hmm..
 
Øyvind
 
Fra: Ian East [mailto:ian.east@openchannelpublishing.com] 
Sendt: 4. oktober 2012 10:51
Til: Teig, Oyvind CCS
Kopi: occam-com@xxxxxxxxxx
Emne: Re: SV: Programming prioritisation
 
Hi Øyvind
 
I certainly referred to Bill Roscoe's second book on CSP, which he describes as part sequel, part successor, to his original Theory and Practice of Concurrency :
 
            Roscoe, A. W. :  2010, Understanding Concurrent Systems, Springer ISBN 978-1-84882-257-3
 
I mentioned the one section on priority in the book (#20.2 Priority, pp. 486-496 (though there is a brief mention earlier in the context of timed systems), where he rejects prioritised choice (PRI ALT) because it presents problems "when the priority orders of different parallel processes cannot be resolved".
 
I managed a brief chat with Gavin Lowe, whose thesis concerned prioritisation, and suggested I really ought perhaps to read his thesis first.  He recommended instead starting with his more recent papers, as they were more up-to-date.
 
From these contributions, this discussion (thread), and my own thoughts, I think there are two clear conclusions thus far :
            1          in the presence of many low-cost processors ('cores'), we can usually forget prioritisation in practice
            2          where a programming language does incorporate prioritisation, it is better to prioritise events (and their response), in which case
                        there must be an opportunity to declare a partial order over the events concerned over the scope affected.
 
I remain concerned that the first approach may sometimes result in a more complicated communication pattern which may be more difficult to program (or, conversely, invite more error).
 
I have yet to fully understand the consensus (if there is one) in the CSP community over programming prioritisation.
 
Ian
 
 
On 4 Oct 2012, at 08:13, Teig, Oyvind CCS wrote:



UK mainlanders and others.
I wonder where this thread started? At CPA-2012 I think it was said that in Bill Roscoe’s “latest book” he shows that PRI ALT is
… not wanted? ... not needed? … plain wrong? … ok, provided?
I do see that Roscoe has published quite a lot even this year http://www.cs.ox.ac.uk/people/publications/personal/Bill.Roscoe.html. (Or was it Steve Schneider, but on Amazon I see nothing very new from him). I have seen one of these names in a mail comment lately, but I can’t find it! Anyway, I’d appreciate more precise statements:
1.      What was the source of this?
2.      And a brief explanation of what was stated, and the context?
I did start a little blog note yesterday, it’s somewhat off-topic to the core of this discussion, but I would like to put in a little about the (pros and) cons of PRI ALT. See http://www.teigfam.net/oyvind/home/047-priority-select-in-go/ (I’d like comments, but it’s very crude at the moment, my suggestion is probably wild or wrong, but there is a point, at least to trash, there). If I do quote this thread, how should I do it?
Med vennlig hilsen / sincerely
Øyvind Teig
 
Ian East
Open Channel Publishing Ltd.
(Reg. in England, Company Number 6818450)