Contents
This page is in group Technology and is about a facet of multi-threaded concurrent programming where some seem to think that synchronous non-buffered channels and processes are incompatible with hard real-time systems and guaranteed deadlines.
Over a beer the other night, but oh so serious, I heard a computer scientist challenge C. Liu and J. Layland’s (1973) hard definition of a hard deadline [5]. Very interesting, and I look forwards to seeing it written down. But this short note certainly takes hard as hard.
1987 (Welch)
Peter Welch in 1987 showed that using processes, process priorities (the two priorities of the transputer) and pre-emption of low by high priority processes (which could happen only between instructions) then hard real-time systems with guaranteed deadlines could be implemented [1] . He showed that this could be implemented in a CSP based system (with synchronized channels) running on transputers (which were fancy, new and odd at the time).
2015 (Welch)
In CPA 2015 (28 years after) Peter Welch showed that “(a) pre-emptive scheduling is not required, (b) priority inheritance is a design error (dealt with by correct design, not the run-time system) and (c) the occam-pi/CCSP scheduler can be made to work even more efficiently for hard real-time systems than it presently does for soft real-time (e.g. complex system modelling)” [2]. No pre-emption in this case is cooperative scheduling. With the same conclusion: hard real-time is guaranteed.
He presented an “id process” as solving the problem better than the “auto-prompter” from the 1987 paper. He now also discusses the XMOS XCore, quoting from his 1987 paper: “Imagine each process running on its own silicon” – exactly as the XCores may do it now.
As mentioned there is no priority inheritance here. Peter Welch pointed out in a private mail to me that
my CPA 2015 fringe pointed out, as said in your blog, that priority inheritance is not needed with correct design and this is just as well … since the concept is incompatible with the CSP model, here processes do not sync with other processes but with events … if a hi-pri process waits on an event, no information is available about the other processes with that event in their alphabet … so they can’t be found to have their priorities raised.
Then I discovered, during Welch’s 2015 fringe lecture that if the “id process” solved it, then the XCHAN (below) also solves it. When I commented on this, Welch immediately acknowledged. As part of the reviewing process for CPA 2012 (where I had my XCHAN paper) Peter Welch had indeed modeled XCHAN and shown that it was provably implementable. He then replied that he hadn’t used XCHAN here because he considered the id process simpler to grasp. Do read [2], it’s very interesting read.
2012 XCHAN (Teig)
Ta assure deterministic timing one basically need to be able to handle a cause or event according to the timing requirement. So one needs priority. Process A has high and B low priority. When A is scheduled to run (by pre-emption or interrupt) it also needs to get rid of its data without further delay. When B is low pri there may be priority inversion.
However, if B runs on a separate core with shared data pre-emption is not needed, as shown in Welch’s papers.
New here is the fact that the XCHAN [4] will also do the trick, with A and B on separate cores with no pre-emption and no priority inheritance. When A attempts to send on xout it never waits. If data is not taken by B immediately it will not send any newly arrived data, but buffer it in buf. When B is ready the ready channel end of XCHAN will be signalled so that A must now send because B is expecting it. But this time it can send what it wants, also information about any overflow.
The top figure shows the internals of XCHAN and the below how it might be drawn in a diagram.
Both figures as vectorised PDF here.
This scheme is almost like one would do from any interrupt into any process: serve it immediately, set a global bit, check it regularly and call to fetch data in a critical region. Except that with channels and processes all of this is automated. Especially, there is no busy polling by the application, it just waits for the signal from the interrupt channel, most probably in an ALT or select selective choice.
XMOS xC guarantees
Here it’s guaranteed that a timing requirement from some event to some action always holds. This architecture has been designed with hard real-time in mind. The hardware, the language and the compiler together do it. And should a new programmer arrive that doesn’t know about a specified timeout and – after his modifications – a timeout isn’t any longer fulfilled, the compiler wont’ build binaries. See [3]. Do observe that it won’t analyse through process communications. See my blog note My XMOS notes.
CPA 2016 fringe
I did a fringe presentation at the CPA 2016 conference at the University of Copenhagen. There was a comment by Peter Welch after my presentation. See it there, at Messing Around with Timeouts. In Contracts?
References
A standard disclaimer: nobody pays me for this, and nobody is allowed to send me goods, and I don’t endorse any here. I do this because I learn from it – as I hope you might, too. I might have misunderstood something here; so you should always check the sources.
- Managing Hard Real-Time Demands on Transputers by Peter H. Welch. In: Traian Muntean, ed., Proceedings of OUG-7 Conference and International Workshop on Parallel Programming of Transputer Based Machines. pp. 182-196, LGI-IMAG, Grenoble, France: IOS Press, Netherlands. ISBN 90 5199 002 4. 1987. See http://www.cs.kent.ac.uk/pubs/1987/243/. Stay tuned for a url with the paper PDF
- Managing Hard Real Times (28 Years Later) by Peter H. Welch, School of Computing, University of Kent, UK. Peter Welch, fringe presentation at CPA 2015 in August 2015. See abstract, slides PDF or slides PPT.)
- XMOS Programming Guide
- XCHANs: Notes on a New Channel Type by Øyvind Teig at Communicating Process Architectures 2012, see http://www.teigfam.net/oyvind/pub/pub_details.html#XCHAN
- Scheduling Algorithms for Multiprogramming in a Hard Real-time Environment by C. Liu and J. Layland. Journal of the ACM, 20(1): 46–61, Jan. 1973. See http://www.cs.ru.nl/~hooman/DES/liu-layland.pdf