Why programs fail and get hacked

“People’s distrust of the high-pressure engines was confirmed when the boiler of a stationary engine exploded at Greenwich on 8 September 1803. It was the usual tale; the boy who had been trained to work the engine went off to catch eels and a labourer stopped the engine without releasing the safety valve.” Richard Hills, Power from Steam, Cambridge 1989.

I posted this to Risks digest in 1995. Software is still in the pre-safety equipment steam boiler stage.

Priority Inheritance: Hack or Error

The subject of priority inheritance has come up again on the Linux kernel mailing list and Torvalds correctly notes

“Friends don’t let friends use priority inheritance”. Just don’t do it. If you really need it, your system is broken anyway.

“Priority inheritance” is similar to “soft real-time” in that both are efforts to avoid building software to specification. I put together a detailed critique in “Against Priority Inheritance”. There are two basic problems with priority inheritance (1) the algorithms are inefficient, complex, and inherently buggy and (2) any claimed benefits can be obtained in a more durable and efficient manner via good design.

The RTLinux core does not support priority inheritance for a simple reason: priority inheritance is incompatible with reliable real-time system design. Priority inheritance is neither efficient nor reliable. Implementations are either incomplete (and unreliable) or surprisingly complex and intrusive.

Doug Locke’s response to “Against Priority Inheritance” seems to me to have to evade the issue in the standard way: read his response and see for yourself. It’s not enough to say “yes, of course you need a proper implementation” since one of the points of the paper is that proper implementations are fragile, expensive, and unreliable.

Update: If you want technical details on the can-o-worms PI opens – read the great description by Bryan Crantril at Sun.

Comparing VXworks to RTLinux

A couple of years ago, one of our salesmen asked us to comment on a comparison between VxWorks and RTLinux performance that had a prospective customer worried. When we tracked down the article, we were dumbfounded that it was being taken seriously. The article was a student paper from a mid-level class in Networks with some obvious limitations that I’m sure are known to the author. (I am very thankful my undergraduate student papers were written before the Internet so they don’t show up years later.) The paper compares the old RTLinuxFree 3.1 to VxWorks. Here are some curiosities.

  • The author writes:
    “We configured both RTOSes to use round-robin scheduling policy to determine context switch time.” That’s impressive given that RTLinuxFree 3 did not ever support round-robin scheduling.
  • Measurements show RTLinux with better priority inheritance performance! RTLinux has never implemented priority inheritance for reasons described in my paper Priority Inheritance: Hack or Error.
  • There is a comparison of interrupt latency on an MPC8260 that is dubious: we measured RTLinux 3.x with about 1/10 of the latency he shows.
  • He compares the performance of a message receive call, despite the absence of such a call from RTLinux 3.1.
  • and so on …

The paper is available on a server in Korea and it shows up near the top of searches. There is a reason we don’t do that comparison (VxWorks license), but there is no good reason that project teams seriously considering options can’t do the comparison for themselves.

Tags: , .

Proving Operating Systems Correct:#8

One of the longstanding problems with operating systems is that there is no way to validate their correctness in the same way that engineers can calculate the ability of a beam to carry a weight or a wire to carry a current. Well, the problem is worse than that, because we don’t even have a precise way of stating exactly what we want the OS to do. We have APIs, a good thing, but suppose that you want to show that an implementation of pthread_create is correct. The first question is correct according to what specification and then you start trying to figure out a precise way to state the requirements implied by the man page. Not easy. At least for me. This paper is a start.