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

RE: Programming prioritisation

No, this is where scheduleability analysis comes (giving you the system wide priorities). You analyse the application and determine if you can make it run on the given hardware.

If not, you have to change either the application, either the hardware. Both have boundaries.

Application: if you simplify it too much, you will likely no longer meet requirements.

Hardware: even using very fast or more hardware might not help (Amdahl's law, power constraints) or worst the application is no longer economically viable.


Priority based preemptive scheduling is one of the ways, if not the only one, to be able to use the minimal hardware (cost, power, ...) and still meet the application requirements when the application has multiple functions to execute in a real-time manner. As said before, responsiveness in real-time is related to keeping the external hardware happy and not missing data (often samples). Meeting all deadlines is achieved by assigning the right priorities at compile time. Both aspects are related but not necessarily.

Using more hardware than needed can most often only be justified if the risk associated with eventually missing the real-time requirements is economically worse. E.g. when the airplane crashes.




From: Larry Dickson [mailto:tjoccam@xxxxxxxxxxx]
Sent: Thursday, October 04, 2012 5:50 PM
To: Eric Verhulst (OLS)
Cc: 'Teig, Oyvind CCS'; 'Ian East'; occam-com@xxxxxxxxxx
Subject: 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.




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.





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




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.




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





| 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..




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.





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)