Go vs Ada

[Archos]

Today Ada is used in industries like avionics, space, railroad,
military, automotive or medical devices but it's possible that Go can
have space here too.

Does Go could be used instead of Ada to build highly reliable, secure
and safe applications?

[Florian Weimer]

* Archos:

For Ada applications in this areas, it's typical to use a subset which
does not support heap allocation (to meet hard real time targets and
avoid fragmentation issues) and guarantees an upper bound on stack
usage (no recursion, no stack allocation of arrays, etc.). There are
tools (such as SPARK) which can ensure that no run-time panics occur.
This is really a different world.

There are Ada users which use it for business applications. Go might
be a serious contender in this area, but these systems are generally
really, really large and are not terribly likely candidates for
porting.

The Ada and Go memory models are extremely similar. One day, GNAT
might offer the Go garbage collector as an option.

[Thomas Bushnell, BSG]

There is a story that in the Falklands War there was a bug in a gunnery targeting program used by some of the British ships. The gunnery officer on one of the small ships affected knew his ballistics in and out, but computer programming he had only because of his brief few-month course. He was able to find the error in the Ada program, repair it, and fix the targeting problem. Things like this were part of the design goals of Ada; the reason it is so verbose is not only because it borrows from Pascal and Modula, but also because it was crucial that people who had had a brief course could remember what the syntax meant. Using lots and lots of English instead of symbols is key there.

I doubt Go has that as a design goal, to say the least. ;)

Thomas

[Øyvind Teig]

A rather new subset of Ada is the "The Ada Ravenscar Profile": http://en.wikipedia.org/wiki/Ravenscar_profile where we read that "The Ravenscar profile is a subset of the Ada tasking features designed for safety-critical hard real-time computing." 

Among one of its no-nos, Ravenscar prohibits use of rendezvous, one implementation of a CSP-type communication between Ada tasks. The reason is that tasks are fifo queued on the entry queue. This makes is difficult to do required timing analysis.

I have just learned (in a thread I started here) that Go also has queueing of its channels - another CSP-type implementation.

Unlike the the original CSP-based language occam, where there is no queue on a channel.

If this is so, then how would Go avoid having a "Go SomeSmallVillageInEngland" safety critical subset? I fear it may halt.

But then, this may have been "as designed" by the Go designers. Queueing on channels certainly is _one_ way to do things. Could anybody tell why there was a need in Go for queues?

(I have discussed some of this in a blog at http://oyvteig.blogspot.no/2011/12/035-channels-and-rendezvous-vs-safety.html)

kl. 17:56:24 UTC+2 søndag 24. juni 2012 skrev Thomas Bushnell, BSG følgende:

[Jay Weisskopf]

Proving determinism is an important part of getting software certified for things like avionics. Features like garbage collection essentially make Go a nonstarter for these types of applications.

[Rob 'Commander' Pike]

Go has both synchronous occam-style channels and queuing (we call them
buffered) channels. Synchronous channels have cleaner concurrent
semantics; buffered channels can have performance or other advantages
in some cases. It's up to you.

Neither style of channel is a argument against using Ada for your problem.

-rob

[Ian Lance Taylor]

Øyvind Teig <oyvin...@teigfam.net> writes:

> A rather new subset of Ada is the "The Ada Ravenscar Profile":
> http://en.wikipedia.org/wiki/Ravenscar_profile where we read that "The
> Ravenscar profile is a subset of the Ada tasking features designed for
> safety-critical hard real-time computing."
>
> Among one of its no-nos, Ravenscar prohibits use of rendezvous, one
> implementation of a CSP-type communication between Ada tasks. The reason is
> that tasks are fifo queued on the entry queue. This makes is difficult to
> do required timing analysis.
>
> I have just learned (in a thread I started here) that Go also has queueing
> of its channels - another CSP-type implementation.
>
> Unlike the the original CSP-based language occam, where there is no queue
> on a channel.
>
> If this is so, then how would Go avoid having a "Go
> SomeSmallVillageInEngland" safety critical subset? I fear it may halt.
>
> But then, this may have been "as designed" by the Go designers. Queueing on
> channels certainly is _one_ way to do things. Could anybody tell why there
> was a need in Go for queues?

I'm not exactly sure what you are asking. Go can have a queue of
goroutines waiting for a channel to become ready, and it is indeed a
FIFO queue. That seems like the natural way to handle channel
communications. You will have to expand on what the problem with it is.

Ian

[Øyvind Teig]

I will try to elaborate a little on this in the next comment (below).

[Øyvind Teig]

I am trying to get a grasp on this myself! I have programmed so much occam over the years that I was surprised when I rediscovered that it was possible to queue tasks, and that Ada in fact queued tasks on the entries. My "little green" Ada book by Burns from the eighties was clear on this. And now I learn that this is also so for Go.

 

A buffered channel has an associated message queue, but it does not need to have any associated process queue in each channel. In occam all channels are unidirectional one-to-one (since many-to-one are arranged as an array of one-to-one channels), and it does not allow output in ALT/select. So, when the only possible first process arrives on the channel, this is noted "in the channel" and not in any ready queue, and the process is descheduled and essentially forgotten. When the second comes on the channel, data is moved across and the first process is moved into the scheduler's ready queue. There may be one queue for each priority. But there is no process queue for each channel. The channel drives scheduling.

Observe that any CSP-type ALT/select scheduling will only take one cause, not several as in the Posix "select".

 

Now, if there is a many-to-one relationship in a single channel (and not an array of channels as in occam) (like I believe is so for Ada, Go and the JCSP library), when the first comes on the sender side, the scheme above would go. Store it in the channel and forget. But the second (an third etc..) on the sender side we need to deschedule but not forget. So, there has to be a queue in each channel listing which process that gets to send.

 

I am not sure how difficult it is to do required timing analysis in the second solution. That queue looks to me rather clean(?) But it has problems:

 

How should a receiver be able to "close the door" to the others during a session with one of them, if all the others are queued up? There has to be some kind of mask or filter for the channel scheduler to set those aside, so I guess it's possible. Basically a channel does not say "I want to listen to anyone who's at the sender side". It would say (occam) that it wants to communicate "on this channel", even on "myChan[i]". Hoare, in his original paper (1978 I think) made channel communication go between named processes, but later (1985, after the occam design that he also was involved with) made communication on named channels. A server in this case does not have to only engage in stateless communication with clients, since it is able to let a session go on with one, and shut the others out. This is a very powerful paradigm.

 

As a consequence we also have the problem of "fairness". Who controls fairness? In occam, the server could do it, by f.ex listen on the next indexed channel in an array of channels (modulo dimension of array), when one was finished with one. If this was not fair enough (to the clients), then it was up to the server to code it differently. With a queue with processes on the channel, the scheduler has to decide about fairness, or just don't care. Anyway, this important trait seems to be out of my hand, as aprogrammer?

 

Then there is buffering. If we have a buffered channel, there is no need for a process queue because there is no blocking - until the channel gets full, when the discussion above is again relevant. A buffered channel has the same problem with the queue, since there is no way to reason about how often the channel gets full. Never, some times, often? Safety critical system analysts will only accept good answers to this.

Then there is preemptive scheduling or not. The transputer (an occam virtual machine, so to say) scheduler let the channel do the scheduling, always. Everthing was connected to a channel: its four i/o links, its interrupt pin and even timers. The Ada Ravescar profile removes quite some nice things about Ada, but requires preemptive scheduling. But it also states that "However a similar profile could be defined that specified non-preemptive execution". I understand the latter, but not the first..

Now I haven't really touched Go much here. Will my ponderings also go for Go, or are there important differences or nuances? Since Go channels are based on CSP I assume that much of this is relevant? Are there any errors in my reasoning?

Øyvind Teig

Trondheim, Norway

kl. 07:06:21 UTC+2 mandag 25. juni 2012 skrev Ian Lance Taylor følgende:

kl. 07:06:21 UTC+2 mandag 25. juni 2012 skrev Ian Lance Taylor følgende:

[Ian Lance Taylor]

Øyvind Teig <oyvin...@teigfam.net> writes:

> Now, if there is a many-to-one relationship in a single channel (and not an
> array of channels as in occam) (like I believe is so for Ada, Go and the
> JCSP library), when the first comes on the sender side, the scheme above
> would go. Store it in the channel and forget. But the second (an third
> etc..) on the sender side we need to deschedule but not forget. So, there
> has to be a queue in each channel listing which process that gets to send.

I would describe Go channels as many-to-many. A channel can have many
goroutines queued to send, and the same channel could later have many
goroutines queued to receive.

> I am not sure how difficult it is to do required timing analysis in the
> second solution. That queue looks to me rather clean(?) But it has problems:

I don't know what you mean by "required timing analysis."

> How should a receiver be able to "close the door" to the others during a
> session with one of them, if all the others are queued up? There has to be
> some kind of mask or filter for the channel scheduler to set those aside,
> so I guess it's possible. Basically a channel does not say "I want to

> listen to *anyone* who's at the sender side". It would say (occam) that it

> wants to communicate "on this channel", even on "myChan[i]". Hoare, in his
> original paper (1978 I think) made channel communication go between named
> processes, but later (1985, after the occam design that he also was
> involved with) made communication on named channels. A server in this case
> does not have to only engage in stateless communication with clients, since
> it is able to let a session go on with one, and shut the others out. This
> is a very powerful paradigm.

In Go a receiver on a channel can not take control of the channel to
prevent other goroutines from receiving values on it. If you need to do
something like that in Go, you just create a new channel for the
specific communication.

> As a consequence we also have the problem of "fairness". Who controls

> fairness? In occam, the server could do it, by f.ex listen on the *next*indexed channel in an array of channels (modulo dimension of array), when

> one was finished with one. If this was not fair enough (to the clients),
> then it was up to the server to code it differently. With a queue with

> processes on the channel, the *scheduler* has to decide about fairness, or

> just don't care. Anyway, this important trait seems to be out of my hand,
> as aprogrammer?

In Go a goroutine dealing with multiple channels will use a select
statement, and select will choose among the channels pseudo-randomly.
That is where the Go runtime provides "fairness."

> Then there is preemptive scheduling or not. The transputer (an occam
> virtual machine, so to say) scheduler let the channel do the scheduling,
> always. Everthing was connected to a channel: its four i/o links, its
> interrupt pin and even timers. The Ada Ravescar profile removes quite some
> nice things about Ada, but requires preemptive scheduling. But it also
> states that "However a similar profile could be defined that specified
> non-preemptive execution". I understand the latter, but not the first..

The current Go scheduler is not preemptive, but channel I/O is not the
only place where goroutines can be scheduled. They can also be
scheduled at most system calls--i.e., most file or network I/O.

> Now I haven't really touched Go much here. Will my ponderings also go for
> Go, or are there important differences or nuances? Since Go channels are
> based on CSP I assume that much of this is relevant? Are there any errors
> in my reasoning?

Go channels are based on CSP, but they are not the same as CSP, or
Occam.

Ian

[Max]

Proving determinism is an important part of getting software certified for things like avionics. Features like garbage collection essentially make Go a nonstarter for these types of applications.

There is or was real-time java. Mars Rover "Spirit" used real time java software.

There is real time GC

Real time does not mean fast but predictable.

http://www.velocityreviews.com/forums/t130449-mars-rover-controlled-by-java.html 

There was also hardware java processor with hardware memory management with zero time delay for garbage collection.

[Paul Borman]

A realtime system does not require all software to be realtime.  As you indicated, realtime means determinism.  That you can guarantee an event will be processed in a given interval of time from when the event fired (not when you noticed it).  There can be non-realtime software on the device as long as the realtime events take priority and the maximum length of time it takes for the non-realtime task to be interrupted is accounted for.  Generally speaking, any possibility of general memory allocation or garbage collection in a code path would make that particular path non-realtime.  Realtime code pre-allocates memory before it enters realtime mode.

The article is no longer on CNET so I can't see where they said Java was used, but I can assure you 100% that the OS on the Spirit was an older version of VxWorks (they decide the software platform pretty much at the beginning of the project and don't do upgrades).  The realtime code was almost certainly written in C, though compiled with a C++ compiler.  I can believe there was java code there, but I do not believe it was handling the realtime events.

Go could be used in a similar way, for the non-realtime aspects.  This does leave out avionics and other certified sections.

    -Paul

[Paulo Pinto]

The Aonix Perc VM is used in real time systems like planes and radar
control systems,

http://www.atego.com/products/aonix-perc/

--
Paulo

On Jun 25, 5:32 pm, Max <max.seven....@gmail.com> wrote:
> > Proving determinism is an important part of getting software certified for
> > things like avionics. Features like garbage collection essentially make Go
> > a nonstarter for these types of applications.
>
> There is or was real-time java. Mars Rover "Spirit" used real time java
> software.
> There is real time GC
> Real time does not mean fast but predictable.
>

> http://www.velocityreviews.com/forums/t130449-mars-rover-controlled-b...

[Øyvind Teig]

kl. 16:44:12 UTC+2 mandag 25. juni 2012 skrev Ian Lance Taylor følgende:

Øyvind Teig writes:

> Now, if there is a many-to-one relationship in a single channel (and not an
> array of channels as in occam) (like I believe is so for Ada, Go and the
> JCSP library), when the first comes on the sender side, the scheme above
> would go. Store it in the channel and forget. But the second (an third
> etc..) on the sender side we need to deschedule but not forget. So, there
> has to be a queue in each channel listing which process that gets to send.

I would describe Go channels as many-to-many.  A channel can have many
 goroutines queued to send, and the same channel could later have many
 goroutines queued to receive. 

> I am not sure how difficult it is to do required timing analysis in the
> second solution. That queue looks to me rather clean(?) But it has problems:

I don't know what you mean by "required timing analysis."

The Ada Ravenscar profile is concerned about this, it seems like the only rationale for it. I just used their words. But  this is for hard real-time systems that is required not to miss a deadline.

> How should a receiver be able to "close the door" to the others during a
> session with one of them, if all the others are queued up? There has to be
> some kind of mask or filter for the channel scheduler to set those aside,
> so I guess it's possible. Basically a channel does not say "I want to
> listen to *anyone* who's at the sender side". It would say (occam) that it
> wants to communicate "on this channel", even on "myChan[i]". Hoare, in his
> original paper (1978 I think) made channel communication go between named
> processes, but later (1985, after the occam design that he also was
> involved with) made communication on named channels. A server in this case
> does not have to only engage in stateless communication with clients, since
> it is able to let a session go on with one, and shut the others out. This
> is a very powerful paradigm.

In Go a receiver on a channel can not take control of the channel to
prevent other goroutines from receiving values on it.  If you need to do
something like that in Go, you just create a new channel for the
specific communication. 

Too bad not to directly control a channel. But then, not so bad after all, with the alternative:

A collegue pointed the solution out to me today, as I then remembered having seen it in the JCSP library as well. There "sending channels over channels" is a point. So a client passes over the channels needed for the session. When the session is over, the server goes back and then listens on the original set of channels. This also "simulates" input guards. 

Channels over channels, or "mobile channels" is also covered in occam-π http://en.wikipedia.org/wiki/Occam-π

The XMOS XC language has a a "transaction" term. I have discussed this in a blog at http://oyvteig.blogspot.no/2012/04/045-nondeterministic-note-about.html.

> As a consequence we also have the problem of "fairness". Who controls
> fairness? In occam, the server could do it, by f.ex listen on the *next*indexed channel in an array of channels (modulo dimension of array), when
> one was finished with one. If this was not fair enough (to the clients),
> then it was up to the server to code it differently. With a queue with
> processes on the channel, the *scheduler* has to decide about fairness, or
> just don't care. Anyway, this important trait seems to be out of my hand,
> as aprogrammer?

In Go a goroutine dealing with multiple channels will use a select
statement, and select will choose among the channels pseudo-randomly.
That is where the Go runtime provides "fairness."

This is like the old occam ALT, whereas PRI ALT has priority. Then there is the iteration over channel indexes as well, where the starting index is the key point. Adding one (mod size) to the last used index usually is "rather fair". Of course, random needs not be fair, one client could be selected too often. But pseudo-random goes through all numbers once and only once per round. In Promela, when one analyzes a model with Spin, the nondeterministic operator :: is used for the evaluation, but when the code is run, pseudo-random is used. See Promela at Wikipedia.

> Then there is preemptive scheduling or not. The transputer (an occam
> virtual machine, so to say) scheduler let the channel do the scheduling,
> always. Everthing was connected to a channel: its four i/o links, its
> interrupt pin and even timers. The Ada Ravescar profile removes quite some
> nice things about Ada, but requires preemptive scheduling. But it also
> states that "However a similar profile could be defined that specified
> non-preemptive execution". I understand the latter, but not the first..

The current Go scheduler is not preemptive, but channel I/O is not the
only place where goroutines can be scheduled.  They can also be
scheduled at most system calls--i.e., most file or network I/O.

Interesting. I like it.

> Now I haven't really touched Go much here. Will my ponderings also go for
> Go, or are there important differences or nuances? Since Go channels are
> based on CSP I assume that much of this is relevant? Are there any errors
> in my reasoning?

Go channels are based on CSP, but they are not the same as CSP, or
Occam.

I like what I see. But at the moment I'd rather sit in a helicopter with legacy occam code than new Go. But with the knowledge this community can come up with, I feel that the future might come. I did look at Limbo in the nineties, but at that time they even used "chan of protocol" without refering to CSP. Now they state their CSP base, and the Go designers' solution does not seem to be a carbon copy of what I have seen earlier. Quite interesting!

Øyvind

Ian

[Øyvind Teig]

kl. 18:17:16 UTC+2 mandag 25. juni 2012 skrev Paul Borman følgende:

A realtime system does not require all software to be realtime.  As you indicated, realtime means determinism.  That you can guarantee an event will be processed in a given interval of time from when the event fired (not when you noticed it).  There can be non-realtime software on the device as long as the realtime events take priority and the maximum length of time it takes for the non-realtime task to be interrupted is accounted for.  Generally speaking, any possibility of general memory allocation or garbage collection in a code path would make that particular path non-realtime.  Realtime code pre-allocates memory before it enters realtime mode.

The article is no longer on CNET so I can't see where they said Java was used, but I can assure you 100% that the OS on the Spirit was an older version of VxWorks (they decide the software platform pretty much at the beginning of the project and don't do upgrades).  The realtime code was almost certainly written in C, though compiled with a C++ compiler.  I can believe there was java code there, but I do not believe it was handling the realtime events.

Go could be used in a similar way, for the non-realtime aspects.  This does leave out avionics and other certified sections.

 

I agree with the above. Standards like IEC 61508 would not be too concerned about language, but specific traits, and rate those to selected quality levels. This is not a go or not Go. 

- Øyvind

    -Paul

[Kyle Lemons]

On Mon, Jun 25, 2012 at 9:17 AM, Paul Borman <bor...@google.com> wrote:

A realtime system does not require all software to be realtime.  As you indicated, realtime means determinism.  That you can guarantee an event will be processed in a given interval of time from when the event fired (not when you noticed it).  There can be non-realtime software on the device as long as the realtime events take priority and the maximum length of time it takes for the non-realtime task to be interrupted is accounted for.  Generally speaking, any possibility of general memory allocation or garbage collection in a code path would make that particular path non-realtime.  Realtime code pre-allocates memory before it enters realtime mode.

The article is no longer on CNET so I can't see where they said Java was used, but I can assure you 100% that the OS on the Spirit was an older version of VxWorks (they decide the software platform pretty much at the beginning of the project and don't do upgrades).  The realtime code was almost certainly written in C, though compiled with a C++ compiler.  I can believe there was java code there, but I do not believe it was handling the realtime events.

To the best of my knowledge (from my brief time working on MSL), the rover control software on Spirit, Opportunity, and Curiosity (the MER and MSL missions) had no Java anywhere in it.  Some parts of the system on the Earth side were in various other languages including Python and Java, but I only saw them used in testing and UI.  As much as I love Go, I would not have ever suggested it as the language of choice for the control software. I think it would have been a great language for developing the flight software tests, though, and probably for many other non-hard-realtime pieces of the puzzle.

[Ian Lance Taylor]

Øyvind Teig <oyvin...@teigfam.net> writes:

>> I don't know what you mean by "required timing analysis."
>>
> The Ada Ravenscar profile is concerned about this, it seems like the only
> rationale for it. I just used their words. But this is for hard real-time
> systems that is required not to miss a deadline.

What is required for hard real-time system is deterministic, measurable,
behaviour. Go's channels provide that (the fact that select is
pseudo-random is unimportant here). It takes a deterministic amount of
time to pick where data sent on a channel goes; that time is not
dependent on the number of goroutines waiting for data. (A minor
exception, probably unimportant: the time it takes a close a channel
depends on the number of goroutines waiting to read from the channel, as
each of them must be notified.)

Where Go fails to be deterministic is in memory allocation and garbage
collection. Neither memory collection nor garbage collection take a
fixed, known, amount of time. The amount of time will vary based on how
much memory has been allocated.

Also Go's current map implementation is not deterministic, even beyond
the fact that it uses memory allocation internally.

Ian

[Max]

http://en.wikipedia.org/wiki/Deterministic_garbage_collector

http://en.wikipedia.org/wiki/Real_time_Java 

Mainstream Go will unlikely be real-time soon but it is possible to create real-time version of Go like real-time Java

[Rob 'Commander' Pike]

We don't go to Ravenscar.

-rob

[minux]

On Mon, Jun 25, 2012 at 11:32 PM, Max <max.se...@gmail.com> wrote:

There was also hardware java processor with hardware memory management with zero time delay for garbage collection.

interesting, any references for practical zero time delay hardware memory management (garbage collection) systems?

i knew some Java cpus, but do not know any hardware GCs so any references will be helpful.

[Max]

i knew some Java cpus, but do not know any hardware GCs so any references will be helpful.

I read article on ibm.com about startup designing Java CPU with zero delay garbage collection, (~5 years ago)

I googled but have not found it

Here is paid  link that refers to similar technology. 

"Active memory processor: a hardware garbage collector for real-time Java embedded devices"

http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1217230&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F7755%2F27366%2F01217230.pdf%3Farnumber%3D1217230 

[Jose Espinosa]

Max,

May be you are referring to this series of articles http://www.ibm.com/developerworks/java/library/j-rtj1/

Jose

[Max]

May be you are referring to this series of articles http://www.ibm.com/developerworks/java/library/j-rtj1/

No. Article was about some startup and processor they designed. They mentioned company name many times.

IBM servers could get some extension to use these processor with IBM version of java, etc