039 - Adding real-time processes to on/when programming?

This note will try to discuss if it is possible (or reasonable) to add safe real-time processes to systems like the nRFGo Studio by Nordic Semiconductor [1], or to the Echelon Lon-controller, programmed in Neuron C [2]?

(After having almost finished this note, it has swollen to show how a channel based system could be written, more generally.)

Neuron C is used in Neuron Chips and Smart Transceivers, where Network variables are fundamental to Neuron C and LONWORKS applications. The nRFgo SDK is a Software Development Kit for Nordic nRF24L Series 2.4GHz RF System-on-Chips (SoCs).

Both have event-driven (on/when) architecture. Add "safe processes" to already well tuned software and hardware architectures, what do I mean?

Should you follow this note as it develops, please warn me if I say something wrong. To say it shortly, I would know my mantra (write a CSP channel based process scheduler in C) quite well. Many blog notes, publications and invited lectures revolve around that theme. But nRFGo and Neuron C I have never had any experience with. I simply rememeber long ago (about 1995) when some collegues did use the Neuron C. I see it's still alive. And the nRFGo seems to have been written just up the hill from where I live, so I got curious.

I don't know if an nRFGo or Neuron C programmer would ever want or need a process term. Since it would be the first I would personally look for, I would even before that have a look at what's already there. I have programmed so much microcontrollers that I would know what an interrupt is there for. An interrupt function, is a sort of "process", since there is microcode (or whatever) to handle how it is able to set other functions aside, and later on return to the interrupted function the morning after. Only, the interrupted code slept without knowing it.

And I remember around the year 2000, when I was on a committee called RTJWG [3] (now defunct), how so much of the discussions was about how to connect asynchronous I/O to the Java language. I had programmed the transputer for almost ten years at the time, and it and the occam language didn't even have a separate interrupt term. All was processes. So, I really didn't understand why they were discussing this so much then. I also remember a programmer I worked with back in the early eighties who got that part almost all wrong, and a collegue had to spend a year dismantling and collecting the assembly code back again. The part of the product that had a run time scheduler (a separate board and processor with code also written in assembly) worked from day one (in the asyncronous I/O and process term context). We got it all working according to specs before some Swedish nuclear power stations had to rely on the system.

Here comes on or when programming, to deliver a framework to connect interrupts (or all internal events) to non-interrupt code. Or to decouple the two. It might not be a good idea to do an FFT in the interrupt, it may be better to just pass over the data and let some other code do it later on. The sooner the better, probably - but not in the interrupt. The interrupt would have some hard real-time schedule to it, like get it over in 20 us, because there are other interrupts, you know.

In nRFGo there already is an on (like on_pipe_updated or on_transaction_finished) and a subscriber term, and there is a dispatcher for handling of events and communication between different modules. I will later try to figure out what a module is, and what a transaction is. The nRFGo uses the Keil compiler, probably wrapped up by some tools that they developed in Qt. I think their Help tells me this. So, they seem to have a C compiler there. Even if their tool also builds code by the set-up config, the user has C available. After ARM bought Keil, the ARM suite was moved over to the Keil IDE. But Nordic lists the Keil C51 C compiler, so the core must be C51 based.

In Neuron C there is a when, and events are used in when-clauses to enable the execution of a when-task, using a special syntax. A when statement can contain more than one when clause.

I think these two mechanism basically do the same: deliver a framework to connect asynchronous I/O to the rest of the code.

Scheduler and dispatcher

nRFGo contains a dispatcher, and Neuron C a scheduler. The Wikipedia article says that a scheduler typically decides which process is running, while the dispatcher makes it running [4]. This note will not be precise about this, as it is rather difficult to distinguish in a microcontroller. nFRGo and Neuron C will do about the same, with different wording - even if Neuron C's scheduler also have preemption mode.

Towards a process model

The modules or tasks mentioned are meant to be independent subscribers to defined services. In a way they are a means to order the asynchronous I/O.

However they don't seem to be processes as I would think of them. I will try to explain.

They are closely connected to the hardware in the processors. None of the code would be portable. I remember when we wanted to port some embedded code that implemented a software UART from an AVR to and ARM, I wrote an interpreter below the hardcoded use of registers in the AVR. So, on the ARM, the interpreter picked up bytes at named memory locations and wrote back. And the oversampling represented in the UART and its use of timers, input capture and output compare registers etc. was handled with a single timer interrupt on the ARM. We didn't change a line of code on the AVR, and the ARM addition was a layer below. This layer handled two usch UARTS, one more than was available in the AVR.

The more some code handles particular hw in the processor, the less it is portable. The sw described in this note connects to that hw alone. Nothing else, as far as I can see.

There are no independent processes or tasks that may talk with each other, and have a life of their own. And since these are not defined, there is no communication or synchronization model either.

One of the Lon chips "also supply one binary semaphore to support synchronized access to shared resources between the application and the ISR processor". This is interesting, and probably very useful. But it does not add the process model I am looking for.

The process model

The process model I would suggest to add is "standard" CSP type processes with safe buffered channels. I have used much of my professional life with this model, starting with the occam language. I have also published a lot about this. Blog note 034 has something about buffered channels. Add this paper (it's also [5]), and you'd have a good starting point. I will not re-refer to these papers. There will also be rationale for this type of programming in those references.

It starts to dawn on me how difficult this note could become, or has become. I had not thought that I should include the code to anything like BufChanSched (buffered channel based process scheduler), you must do it yourself. But maybe my writings could be of some inspiration.

In my experience this model is useful both for typical data-flow dominated systems (like regulating systems and more process-oriented designs) as well as control dominated systems (like drivers or protocols). And then, most systems I have seen are a mix of both styles.

The process model by how to make it

Still, here are some points (which basically says a lot about the process model):

1. A process is a C function. Start all process names with P_.
2. Make a list of pointers to those functions.
3. No static variables in the functions.
4. No reference to external variables except the channels it uses.
5. A channel sends data and is basically blocking. The second on the channel (sender or receiver) continues to run, while the first becomes ready.
6. A channel sends signals (with no data) asynchronously (never blocks).
7. A buffered channel never blocks, but always returns an ok/full bool. When it's full the scheduler uses a channel ready signal channel to tell that the channel again may be sent to
8. A channel input may define three types of timers: ALTTIMER, EGGTIMER and REPTIMER.
9. If you need to pass parameters to a function, there is no way to do it in C. Since it's going to be called by its pointer when it's scheduled, adding parameters may be done with some kind of table. But this is most often not needed for a small scheduler in C. Since there is no language support, it's possible to get around it.
10. ...
11. You need a standard scheduler in C, that keeps a list of the entry points to all processes. The entry points are assigned once only.
12. A process has initialization code, and a "while (true)" loop.
13. It has a "proctor table" described in the reference above, that by a simple, hidden goto gets the process to any rescheduling point. See here.
14. A process has only one reason to be scheduled.
15. A process may send on a channel, but there is no output guard.
16. A process may receive on a single channel.
17. A process may wait on a list of channels in an ALT. Each component may have a boolean guard to that it's easy to switch this on and off in the process. If false that component is skipped. When one component of the ALT has become activated (is that the word?), then the ALT is torn down, so that all the other entries's "first" state is nulled.
18. You could start "individs" of each process, but then you would have to parameterise the channels.
19. Each process has a struct of local variables which is allocated on the heap by a malloc in the initialisation part. Call this the "context". This is never freed, so it's easy to know if you have overflowed.
20. ...
21. A simple return from the process code gets you down to the scheduler. Therefore, no blocking calls are allowed from any subroutine level.
22. When the scheduler finds no cause to schedule a channel or there is no channel waited for, there is a system fault. You probably have a deadlock.
23. To avoid deadlock, use a deadlock free pattern, like knock-come from blog note 009.
24. No external functions may call any function in a process file (except the scheduler).
25. The process context is local to a process, and not seen elsewhere. Only parts of it are exposed to the channel (place and sizeof).
26. Two processes may call a common function, since this scheduler is not preemptive. But do it seldom, and in no case let that function have any side effects. This means that it cannot alter common state (like registers or static etc.). The exception is all channel handling, ie. all scheduler functions. Of course it has system side effects, but not application side effects.
27. Channel size is dynamic, but the sender and receiver must agree. So a common protocol definition header file must be made. A protocol is a collection of structs with tags and data.
28. With this system communication and synchronization is the same. If you use buffering, it may become the same.
29. Channel names are handled by en enum, values from 0 to n. Channels may have to be initialized. I do it in a separate function, that would init all.
30. ...
31. Coding the ALT is the most complex, because you may need a bitset (any primitive word size or array), used by each ALT to represent the ALT set. An ALT is "built" or "tore down". You need it so that the first that arrives on the channel, only refers to that bitset to tear down, with no knowledge of the other components.
32. If you need "fair ALT", then you could bundle the ALT set in an array, and start the ALT with an index which is one more than the one just "taken". The index needs to wrap around in modulo n
33. If you need processes to have priority, think twice (priority inversion etc.).
34. If you have thought twice, make one ready queue for each priority.
35. But maybe you would rather think of channels as the means to supply priority. Should they instead be prioritized? But do think twice on this too.
36. If you do need priority, play on team with the interrupt functions. The chip designers would have thought out a scheme for you.
37. Use macros to make it code better readable and hide parameters that don't need to be seen. But be aware of limitations, like Neuron C does not support #if or #elif. The synchronization points described in [5] uses labels thas absolutely should be invisible.
38. ...

These points are well documented in the literature. But a list like the above may still be ok.

So what about nRFGo and Neuron C?

The challenge is to add a small and safe run-time system with light-weight processes to these already small systems. A hypothetical BufChanSched would probably just add a few kB of code, and around 10 bytes per blocking (zero-buffered) channel. Process overhead is also small in code and RAM. And scheduling and rescheduling is light weight, smaller than interrupt context switching.

Maybe it would be nice to have processes available also for the application code in a radio chip like nRF24LE1 or the networking Neuron chip?

Perhaps someone could make an open source project for a pluggable channel based scheduler? With it, the (right) process model comes creeping all by itself..

..provided you also have a glimpse at where it came from: occam and occam-π. And assure your boss (and/or better half) that it's not going to be a waste of knowledge, as these days you'll even make a sneek peek into some of Go.

References

[1] - http://www.nordicsemi.com/eng/Products/2.4GHz-RF/nRFgo-SDK. Is there a public manual like the Neuron C manual? So I have guessed my way.. However, there is a little used public talk forum, see http://www.nrftalk.net

[2] - http://www.echelon.com/support/documentation/manuals/devtools/default.htm (Search for "Neuron C")

[3] - Real Time Java Working group, J Consortium (Java Consortium) - (NIST), backed by HP, Microsoft, Newmonics. All remains of this seem lost. Of course, the Sun based initiative JSR-1 won (http://en.wikipedia.org/wiki/Real_time_Java)

[4] - http://en.wikipedia.org/wiki/Scheduling_(computing) dispatcher / scheduler

[5] - "New ALT for Application Timers and Synchronisation Point Scheduling" by Vannebo and Teig. See http://www.teigfam.net/oyvind/pub/pub_details.html#NewALT

.