keeping simple

Category: operating systems

  • parallel processing and bash reduce

    It’s sad that after all this time, one can look at any random article on parallel programming and find some variation of:

    for i = 1 ... n
      create thread i
             do something
end for

    as if that was the only way to express parallel computation. This is such an awkward way of looking at problems.  I think many problems come from the sloppy “non-determinism” of the operating systems and multi-core machines.  One of the few  interesting ideas seen in the last 20 years on parallel processing is the Google map-reduce scheme ( . But what I find impressive is bashreduce. This is really a clever trick and a great validation of the UNIX toolset design (as if it needed another validation).

  • RTOS design and embedded system development

    Real-time operating systems are either a solved problem or a backwater of engineering design. Threads, semaphores, mutexes, some basic I/O, priority scheduling all of this has been more or less standardized in the  POSIX 1003.13 smaller profiles (51,52) for many years. The basic programming model has not changed in years. Even FSM’s original RTOS and QNX, the two most unusual RTOS’s, are pretty similar from a programming point of view except for the split between real-time and non-real-time in our old product.  My suspicion is that the programming model provided by these RTOS designs can be replaced by something better mostly because I think synchronization is a painful and error prone exercise that only gets worse as systems become more complicated. On the other hand, although many of our customers really loved it, and I think it was a huge advantage, the split mode approach in the old RTLinux* was a difficult learning experience for a lot of people.

    Consider a simple design:

    1. Task A: collect data from an Analog/Digital converter, sampling at rate 1/t seconds and filling a small buffer (1/t)*n seconds.
    2. Task B:  Aggregate A data and produce 3 streams of processed data that are functions of the input data and some settings.
    3. Task C:  produce control data from the processed data at an output rate of 1/t2 seconds
    4. Task D: provide a secure internet port which will process requests to interrogate data, to setup data push at some rate maximum 1/t3 pushes per second and update the settings with worst case delay from arrival of input packet to reset of 1/t4 seconds.
    5. Task E: operate a touch screen display that has some of the same functionality as task D

    That seems like it should be straightforward, but it’s not: it’s a one year project that has a 70% chance of failing. Making sure shared data is efficiently and correctly shared, validating that the scheduling and timing is ok, and optimizing for hardware limits and power are all hard.  And that seems wrong because there is nothing in such a project that has not been done thousands of times before.  As the electric power industry stumbles into modern software based control,  the slow development times and poor reliability of products developed under this model is a serious problem.

    * NOTE: RTLinux is a trademark of WindRiver Systems.

    [note: edited to remove garbage characters]

     

  • chrome OS

    SAN FRANCISCO — In a direct challenge to Microsoft, Google announced late Tuesday that it is developing an operating system for PCs based on its Chrome Web browser.

    The move sharpens the already intense competition between Google and Microsoft, whose Windows operating system controls the basic functions of the vast majority of personal computers. NYT

    Google sez

    Speed, simplicity and security are the key aspects of Google Chrome OS. We’re designing the OS to be fast and lightweight, to start up and get you onto the web in a few seconds. The user interface is minimal to stay out of your way, and most of the user experience takes place on the web. And as we did for the Google Chrome browser, we are going back to the basics and completely redesigning the underlying security architecture of the OS so that users don’t have to deal with viruses, malware and security updates. It should just work.

    Google Chrome OS will run on both x86 as well as ARM chips and we are working with multiple OEMs to bring a number of netbooks to market next year. The software architecture is simple — Google Chrome running within a new windowing system on top of a Linux kernel. For application developers, the web is the platform. All web-based applications will automatically work and new applications can be written using your favorite web technologies. And of course, these apps will run not only on Google Chrome OS, but on any standards-based browser on Windows, Mac and Linux thereby giving developers the largest user base of any platform. Press release

    Looks like the revenge of Plan9 is on.

  • State machine functions and recursive composition

    My graduate school research was motivated by a difficulty we have doing real creative engineering in operating systems that may seem ridiculous to people who don’t work in the field. The problem is that we can’t describe the problem. What an operating system does is complicated beyond the expressive capability of the mathematics we have at hand so we end up with vague gesturing, making applications work, and commitments to support existing APIs which are themselves mostly defined by what existing implementations do.  One result is that there are embarrassing errors in nearly every commercial OS. Another result is that OS development has stagnated. Compare to databases where at least the relational algebra idea has allowed researchers to think about what the damn thing is supposed to do at some reasonable level of abstraction.  Formal methods research has produced nearly nothing of use to engineers – the only useful parts have been the automated validation programs and those have advanced mostly because of the increasing power of the machines used to run the validation algorithms. All this by way of introducing another attempt to clarify the primitive recursive basis of compositional state machine theory.

    Download here. (updated to improve fonts!)

    Applications paper on the unfortunately acronymed Proportional Integral Derivative controllers on the way.

  • Wind River sold to Intel: more reaction

    And like Intel, I would argue that mobile software companies are instrumental in making silicon solutions pervasive, because they tick two major check boxes: reference design and support.

    The hidden asset of mobile software companies
    Mobile embedded software companies (e.g. Myriad, Access, Aplix, NXP software, Azingo) have a unique understanding of products as a hardware/software system. They understand how silicon can be leveraged, encapsulated and productised to fast-track device delivery. Beyond specific IP, these companies have the capability to build the very first product that will feature a new chipset. This is the reference design check box.

    A reference design is not a half-baked breadboard; it is a scale 1:1 device, ready to ship.

    The absence of such capability has drained Texas Instrument, once the mobile silicon leader. Alternatively, true reference design has been instrumental in the success of Qualcomm and Mediatek.(cite)

    Also see previous note

  • Wind River purchased by Intel

    If anything, Wind River’s inability to breakout, despite a once Microsoft-like position of dominance, is a by-product of their failure to meaningfully go “up the stack” and away from their historical focus on the silicon layer as a primary differentiation point.

    In other words, if Wind River had enabled the next generation of Cisco and Apple killers by providing more differentiated OEM-in-a-Box offerings, ala what Google is now trying to do with Android, they would not be staring at a $900M market cap and relatively flat revenues, margins and stock price.

    Well, that’s an argument. Embedded is a tough beat, but Wind did not exactly set the world on fire developing new concepts and software. Intel’s history in software is not glorious either – so it’s going to be an interesting challenge for the new entity.

  • Suns tracking SGI

    IBM dropped its offer to acquire Sun for $7billion. Sun has now a series of projects for which it has large costs, but no clear method of making money. What did Sun gain from open sourcing Solaris, from giving away Java, from embracing Linux, and so on? Irving Wladawsky-Berger (whose blog is worth reading) or whoever it was at IBM, figured out a strategy for making money by using Open Source software to lower the customer cost of things IBM customers needed, but IBM could not profitably sell at a competitive price.  The Oracle people did the same. Sun seems to have understood it was possible to make money with “free software”, but not how to build that into their strategy. The successful free software plan reduces vendor development costs and price to customer of stuff the vendors competitors sell that usually comes with or enables use of  the vendors key products. But Solaris was a Sun key product so it basically used free software to damage its own business. And it lost track of the purpose of Java. Sun Java now serves as the entry product for customers who will pay IBM and others when they become addicted to it. And OpenOffice just looks like an attempt to stick it to MicroSoft.

    And dithering on processor roadmap is silly. I saw a talk from a SPARC designer and asked why they had to dedicate so much silicon to some obsolete memory management nonsense. The answer, decoded, was that the Solaris team was too busy working on x86 to make even minimal changes for SPARC. If you are going to do something like that, you should probably drop the entire product.

    Anyways, Sun appears to be following Digital Equipment Corporation and SGI down the track. Storied companies with brilliant engineers and technology, lead by people who don’t have much sense of how to make money with it all.

  • Program structure and threads

    Threads were initially used for telephony systems where each request to connect could be given to a new thread to manage. The simplification was, in theory, dramatic. The programmer could just write the code for handling a single line, and the OS and network code would multiplex operation over 100,000 calls. The programmer does not have to worry about what operations block and delay time since each particular call could operate sequentially as fast as possible.

    Imagine writing this same code using some sort of request queue. The only way to do it would be to make extensive use of asynchronous I/O, something that was uncommon when threads became popular: back before the world wide web and event driven systems became ubiquitous.  In fact, any multi-threading design seems convertible into a single threaded design via use of asynchronous events and asynchronous I/O. But these methods are not noticeably easier than threads.

    Edited and simplified 2/17/2016

     

     

     

  • Fault tolerant patent application for virtual machine

    [0018]For incoming network packets, the following is done during the logging mode. When a packet is received, an event-request is posted for the VMM, at Block 210. When the VMM processes the event, it stops the VM, synchronizes the guest VCPU state, and then calls into the device emulator (i.e., device emulation software event handler), at Block 220. The device emulator logs an event at Block 230. Then, the device emulator receives the packets, and logs their contents, at Block 240. The last packet logged is marked so that during replay the device emulator can know when the last packet for this event occurs in the log.

    [0019]During replay the following occurs: When an I/O event is encountered in the log, the device emulator (i.e., device emulation software event handler) is called by the VMM. The device emulator reads all packets that were logged, and copies them into the memory of the VM. In this way, the receive queue of packets is updated at the exact same point in the instruction execution sequence during logging and replay.

    United States Patent Application 20090007111
    Kind Code A1
    Nelson; Michael ;   et al. January 1, 2009

    LOGGING AND REPLAYING INPUT/OUTPUT EVENTS FOR A VIRTUAL MACHINE

    VMWARE application.

  • fault tolerant patent

    So I don’t understand the novelty in the methods here over the Glazer patent.

    The replica supervisors provide interfaces to the replicas that are the same as the interface provided by the operating system. Thus, when one of the replicas makes a call to the operating system, the corresponding replica supervisor is invoked and the supervisor ensures that the effect of the intercepted call is the same regardless of whether the primary or backup performs the operation. When the primary supervisor intercepts a call by the primary replica, the primary supervisor makes the call to the operating system on behalf of the replica and then delivers the results of the operating system call (the “values returned by the operating system”) to the primary replica. In other words, the primary supervisor causes a transformation in the state of the primary replica that is equivalent to the transformation the operating system would have caused if the call had not been intercepted.

    The primary supervisor also sends a message to the backup replica. The message contains the values returned by the operating system. When the backup supervisor intercepts a call to the operating system by the backup replica, the backup supervisor does not call the operating system on behalf of the backup replica. Instead, the backup supervisor uses the values sent by the primary supervisor, as a result of the corresponding call by the primary replica, to transform the state of the backup replica. Thus, the replica supervisors ensure that the primary and backup replicas undergo equivalent transformations of their application state as a result of corresponding calls to the operating system.

    Inventors: Bressoud; Thomas C. (Northborough, MA), Ahern; John E. (Sudbury, MA), Birman; Kenneth P. (Ithaca, NY), Cooper; Robert C. B. (Wellesley, MA), Glade; Bradford B. (Harvard, MA), Schneider; Fred B. (Ithaca, NY), Service; John D. (Chelmsford, MA)
    Assignee: Stratus Computer, Inc. (Marlboro, MA)
    Appl. No.: 08/565,145
    Filed: December 1, 1995

    Compare to

    More specifically, the invention contemplates a parallel computer system having at least a first and a second primary task performing means and a first and a second secondary (backup) task performing means. The task performing means are interconnected by a message bus means. In such a system, there is contemplated the method of sending messages among the task performing means. In particular, the invention contemplates sending messages from the first primary task performing means to the second primary task performing means which operates on the messages in accordance with the task associated with such means. The second primary task performing means operates on the received messages by initially storing a received message in a queue and thereafter reading the message from the queue for processing. In addition, this second primary task performing means accumulates a count of the messages it reads from the queue. At the same time, or immediately thereafter, the primary task performing means sends the same messages to the second secondary task performing means which stores these messages in a message queue associated therewith. The messages stored in the queue of the second secondary task performing means are only processed if there is a failure of the second primary task performing means.