keeping simple

Category: academics

  • RTLinux early paper from 20 years ago

    An early RTLinux paper with Michael Barabanov.
    real_time_1996

    Only 20 years later, the idea is now not too scary.

     

    Real-Time Linux
    Michael Barabanov Victor Yodaiken March 3, 1996

    1 Introduction

    If you wanted to control a camera or a robot or a scientific instrument from a PC, it would be natural to think of using Linux so that you could take advantage of the development environment, X-windows, and all the networking support. But, Linux cannot reliably run these kinds of hard real-time applications. A simple experiment will illustrate the problem. Take a speaker and hook it up to one of the pins from the parallel port. Then run a program that toggles the pin. If your program is the only one running, the speaker will produce a nice somewhat steady tone. Not completely steady, but not bad. When Linux updates the file system every couple of seconds, you might notice a small change in tone. If you move the mouse over a couple of windows the tone becomes irregular. If you start netscape in one of the windows, you will hear intervals of silence as your program waits for higher priority processes to run.

    The problem is that Linux, like most general purpose operating systems, is designed to optimize average performance and to try to give every process a fair share of compute time. This is great for general purpose computing, but for real-time programming precise timing and predictable performance is more important than average performance. For example, if a camera fills a buffer every millisecond, then a momentary delay in the process reading that buffer may cause data loss. If a stepper motor in a lithography machine must be turned on and off in precise intervals in order to minimize vibration and to move a wafer into position at the correct time a momentary delay may cause an unrecoverable failure. And consider what might happen if the task that causes an emergency shutdown of a chemistry experiment must wait to run until Netscape redraws the window. It turns out that redesigning Linux to provide guaranteed performance would take an enormous amount of work. And taking on such a job would defeat our original purpose. Instead of having an off the shelf general purpose OS, we would have a custom made special purpose OS that would not be riding the wave of the main Linux development effort. So what we did was slip a small, simple, real-time operating system underneath Linux. Linux becomes a task that runs
    only when there is no real-time task to run and we pre-empt Linux whenever a real-time task needs the processor. The changes needed in Linux itself are pretty minimal. Linux is mostly unaware of the real-time operating system as it goes about its business of running processes, catching interrupts, and controlling devices. But real-time tasks can run to a quite high level of precision. In our test P120 system, we can schedule tasks to run within a precision of about 20 microseconds.

    And more ….

  • ultrafinitism

    I have seen some ultrafinitists go so far as to challenge the existence of 2100 as a natural number, in the sense of there being a series of “points” of that length. There is the obvious “draw the line” objection, asking where in 21, 22, 23, … , 2100 do we stop having “Platonistic reality”? Here this … is totally innocent, in that it can be easily be replaced by 100 items (names) separated by commas. I raised just this objection with the (extreme) ultrafinitist Yessenin-Volpin during a lecture of his. He asked me to be more specific. I then proceeded to start with 21 and asked him whether this is “real” or something to that effect. He virtually immediately said yes. Then I asked about 22, and he again said yes, but with a perceptible delay. Then 23, and yes, but with more delay. This continued for a couple of more times, till it was obvious how he was handling this objection. Sure, he was prepared to always answer yes, but he was going to take 2100 times as long to answer yes to 2100 then he would to answering 21. There is no way that I could get very far with this. Harvey M. Friedman “Philosophical Problems in Logic” (found in Wikipedia) 

     

     

  • RISC-V and Bloat

    Went to UT today to listen to David Patterson speak about the open RISC  instruction set architecture and processors he and his colleagues are developing.  As a software developer, hearing about free hardware makes me giddy with joy, perhaps with a bit too much of a “let’s see how you like it” edge. It’s interesting you can get current generation processors manufactured in small numbers for really modest amounts of money now.  Patterson correctly objects to the kitchen sink nature of Intel and ARM processors now but I suspect he will run into the traditional problem from David Parnas’s software jewels paper.

  • Einstein and Peer Review

    From Time. Although when I posted this on twitter, I got a good response.

    https://twitter.com/lsidir/status/573416554265763840

    In computer science, well …

  • Project Roseline

    Accurate and reliable knowledge of time is fundamental to cyber-physical systems for sensing, control, performance, and energy efficient integration of computing and communications. This simple statement underlies the RoseLine project.  Emerging CPS [Cyber Physical Systems – vy]  applications depend on precise knowledge of time to infer location and control communication.  There is a diversity of semantics used to describe time, and quality of time varies as we move up and down the system stack.  System designs tend to overcompensate for these uncertainties and the result is systems that may be over designed, in-efficient, and fragile.  The intellectual merit derives from the new  and fundamental concept of time and the holistic measure of quality of time (QoT) that captures metrics including resolution, accuracy, and stability.  

    The project will build a system stack that enables new ways for clock hardware, OS, network services, and applications to learn, maintain and exchange information about time, influence component behavior, and robustly adapt to dynamic QoT requirements, as well as to benign and adversarial changes in operating conditions.  Application areas that will benefit from Quality of Time will include: smart grad, networked and coordinated control of aerospace systems, underwater sensing, and industrial automation.  The broader impact of the proposal is due to the foundational nature of the work which builds a robust and tunable quality of time that can be applied across a broad spectrum of applications that pervade modern life. Roseline.

  • Why is computer science education so horrible

    This is a post about CS education. It is prompted by a seriesofposts by Mark Guzdial in which he criticizes the pervasive belief among CS educators that when it comes to programming, there’s not much an instructor can do: some students get it, others don’t; it’s all in genetics or other external factors that CS educators can’t influence (aka the Geek Gene Hypothesis). I am with Mark on this, but I feel a bit stronger about it than he does. I think that attitude is bullshit, and the studies supporting it are unsound by means of making conjectures ignoring an enormous number of confounding factors.  Cristina (Crista) Videira Lopes

    A lot of it is not even teaching method, it is  attitude.  When CS was “professionalized” in the 1970s, all the stupid gatekeeper ambitions and pointless competition from the traditional “hard sciences” and engineering were imported.  When I taught intro CS, I found that the most important part of my walljob was sustaining the morale of the students who came in without programming background (and many bad ideas).

    Harvey Mudd, as Vidiera points out, has actually tried to address these problems and

    Our instructors had private conversations with students who were using up a disproportionate amount of air time in class talking about arcane details and asked them to have those conversations with the instructors in private because other students found their level of knowledge intimidating. [US News]

    Not being as nice, smart, or hardworking as the people as Harvey Mudd, I used to just tell those students to shut up and learn something in my class. And I spent a lot of time telling other students not to worry, that the “experts” didn’t actually know anything near what they thought they did. The common attitude among CS teachers, who are generally former arcane-air-time students themselves, is quite different.

  • Fischer Lynch Patterson and timeouts

    There is a widely cited (over 1400 cites in CiteseerX ) result called the Fischer-Lynch-Patterson text_message_from_godot-469763theorem about consensus – a key issue in distributed databases or any system where data is either distributed or replicated or both.

    In this paper, we show the surprising result that no completely asynchronous
    consensus protocol can tolerate even a single unannounced process death.

    As far as I can tell the “surprising” result is that unbounded delays are not bounded. Without timeouts, we can not distinguish between a site B that will eventually send a message to site A and a site B that has failed (crashed) and will never send a message.

    We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated!
    Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message. We also assume that processes do not have access to synchronized clocks, so algorithms based on time-outs, for example, cannot be used. (In particular, the solutions in [6] are not applicable.) Finally, we do not postulate the ability to detect the death of a process, so it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly.

    The Wikipedia summary is similar:

    In a fully asynchronous system there is no consensus solution that can tolerate one or more crash failures even when only requiring the non triviality property.[11] This result is sometimes called the FLP impossibility proof. The authors Michael J. Fischer, Nancy Lynch, and Mike Paterson were awarded a Dijkstra Prize for this significant work. The FLP result does not state that consensus can never be reached: merely that under the model’s assumptions, no algorithm can always reach consensus in bounded time. In practice it is highly unlikely to occur.

    I don’t get what is “significant” about this. It’s just a tautology wrapped in a complex formalism. If there is no upper bound on how long it can take for a node to send a message, and the only information passed between nodes is via message, then there is no way for one node to tell the difference between a delayed response and a response that will never come because the corresponding node has failed.

     

  • the terrible effect of Krohn-Rhodes

    One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\)  to state machines, but it does it in a way that doesn’t get us very far in understanding the structure of state machines. The problem is that the “division” is too restrictive. In terms of state machines, KR requires us to turn \( M\) into \( M_1 \rightarrow M_2\) where the input of \(M_2\) depends only on the system input and the output of \(M_1\).  This is called a “loop free” decomposition and Hartmanis-Stearns worked on it before KR teased out the underlying math. You can build a ripple carry adder that way and it makes sense that the simple devices that concerned early CS researchers seemed amenable to such a decomposition, but a few steps down the path and we come to systems that do not want to be decomposed into loop-free series at all. Consider a queue – when a new element is inserted each element needs the output of its neighbor to the back to get its new value – very nicely loop free. But consider a stack. A push makes each element take an input from its neighbor to the right and a pop makes each element take an input from its neighbor to the left.

    \[ \langle x_1, x_2 … x_n \rangle \mapsto[push\ y]\mapsto \langle y, x_1 \dots x_{n-1}\rangle \]

    \[ \langle x_1, x_2 … x_n \rangle \mapsto[pop]\mapsto \langle x_2 \dots x_{n},null\rangle \]

    In fact the stack is serially loop free – it has a nice loop free ordering per operation – but Krohn-Rhodes doesn’t go there (you could get to loop free by adding a counter to each element).  Anyways, the result is a theory that bounces off the observed or designed structure of computational objects and, at least to me, that designed structure is the interesting structure.

     

     

     

  • The UNIX file system as a recursive function

    Ignoring “write” operations, for the moment, a file system is just an implementation, a concrete manifestation, of a map from file names to file contents. A UNIX style file system complicates the story because file names are “paths” through a somewhat compromised tree structure.  You could try to express the relationships between nodes in this tree and paths by brute force axioms. For example: if the path “p” can be resolved to a file, then every proper prefix of “p” resolves to a file that is a directory. But, at least to me, it’s more intuitively compelling to describe the map as a recursive function – capturing the structure algorithmically. In fact, the axiom approach gets pretty damn ugly when we add things like “mounted file systems”.

    Begin with a recursive definition of a path: EMPTY is a path and if p is a path and n is a local file identifier then the sequence obtained by appending  n to p (on the left) is a path.  And there are no other paths than the ones that can be built from a finite number of applications of this rule.  We can write “n/p” for the path obtained by appending n to p (appending on the left). Let’s require of course that the separator symbol “/” is not in any local file identifier. Other than that, there is no need to say anything at all about the set of file identifiers now – you can think of it as the set of strings that are “/” free if that helps, but they could be anything at all that is “/” free and can be connected into sequences. And  “/” is just the name we use for the separator, it can be anything at all too.

    UNIX style file systems are nearly always constructed on top of flat file systems. That is, we suppose we have a primitive set of “flat file names” of some sort and a map F that maps flat file names to the corresponding file contents.  Flat file names can be the same as local file identifier or different – it doesn’t matter. Right now we don’t have to say much about these flat file names at all but we have some demands on file contents. In particular, files need to be able to “encode”  lookup tables that relate local file identifiers to flat file names. Since we will require that a local file identifier appear at most once in such a table, we can think of the file contents as encoding a function- the “directory function”.  If “i” is a flat file name and F(i) is defined, we need to be able to associate F(i) with a type: plain or  directory (to start). Plain is just some data. If F(i) is defined and F(i) has type directory, there is some function d= D(F(i))  we can decode from F(i) so that for some finite set of local file identifiers, “d” maps those identifiers to flat file names.

    The idea is that we can start with some flat file name “i” and a path, say,  p=a/b/c and follow p from “i” as follows. First get i’=D(F(i))(a) if F(i) is a directory. Then get i”= D(F(i’))(b) and i”’= D(F(i”))(c) – assuming that the intermediate flat files are directories and they encode functions that map the flat file names “a”, “b” and “c”.  There’s some complexity because we’re not assured that everything will work out – we may only be able to follow a path partway before coming to a dead end.

    So define a function R to take a flat file function F, an initial flat file name “i” and a path p and produces either a terminal flat file name or FAIL if the path cannot be followed all the way.  First we do the easy case R(F,i,EMPTY)= i.  The recursive case is

    R(F,i,n/p)= R(F,D(F(i))(n),p) if F(i) is a directory and D(F(i))(n) is definedFAIL otherwise.

    Associate F with a special flat file “r” – the root file. Then we can define U(p) = F(R(F,r,p)) if R(F,r,p) is not FAIL and let U(p)= FAIL otherwise.

    And that’s it – except that now the flexible nature of the file system becomes clear. Let’s add a new file type “indirect” so that if F(i) is indirect, then we can extract a flat file map and a root flat file name from the contents. That is, if F(i) is an indirect file we can produce (F’,r’) = X(F(i)) where F’ is a flat file map and F'(r’) is a directory under F’.  Say “i” is a properly defined indirect file under F if and only if F(i) is indirect and for (F’,r)=X(F(i)) we have F'(r) as a directory. We can now redefine R as follows to switch flat file systems on an indirect file.

    R(F,i,n/p)= R(F,D(F(i))(n),p) if F(i) is a directory and D(F(i))(n) is definedR(F’,r,p) if F(i) is an indirect file and X(F(i))= (F’,r) and F'(r) is a directory

    FAIL otherwise.

    Note that the first definition of R is obviously primitive recursive – because we lose one element of the path sequence on each recursive step – but it’s not obvious that the version of R with indirect calls must terminate. The final condition on the indirect case assures us that at least every second step must remove one element from the path.

     

  • Dennis Ritchie

    Truly a brilliant engineer.

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