nerd1951.com

I’ve been reading about one of my favorite subjects lately: object oriented operating systems. It seems any operating systems research includes a discussion of micro-kernels vs. monolithic kernels. Micro kernels include the minimal functionality required to manage the processor and memory, functions such as thread management. The Linux Kernel is a monolithic kernel, including the file system and Internet Protocol stack and a host of other services in the kernel.

I’m firmly in the micro kernel camp but I think this is a reflection of my embedded systems background. If the file system, IP stack and other services are provided as user processes, it is much easier to tailor an OS kernel for your embedded system. But this flexibility comes at a price. Micro kernels have traditionally had performance problems. When the file system or the IP stack is a user process there is the additional overhead of making system calls for thread management. A file system or IP stack in a monolithic kernel has access to special kernel facilities for thread management without the context switching overhead of the user’s systems calls.

What does all this have to do with Lock Free Data Structures? Many systems calls are made to serialize access to shared data. Lock Free Data Structures use an atomic machine instruction to guarantee atomic operations on data structures. If we can use Lock Free Data Structures rather than thread services such as Mutexes then we might have the best of both OS approaches; the flexibility of the micro kernel with the performance of the monolithic kernel.

I don’t know if this will work out. I’m still researching Lock Free Data Structure and I want to implement something to play with but this is what excites me lately. I must lead a pretty dull life.

I’ve been too busy to blog lately.  I’m finishing my paper for the Embedded Systems Conference and I had to make a quick trip out of town over the weekend.  Meanwhile, on my day job, my project has hit a snag just when I thought everything was nearly working, as embedded systems projects seem to like to do.

I’ve added a new page; Reading. It’s a list of links to papers on the web I’ve read and found interesting.  Someone else out there might find some of this stuff interesting.  There are three papers on Lock Free Data Structures.  These are data structures that are designed so that data can be shared among different threads or even different processors without incurring the costs of using an operating system locking mechanism. 

I’ve been using a limited lock free - wait free queue for years, between two threads or two processors and never realized there was a name for what I was doing.  I found a paper; Specifying Concurrent Programming Modules by Leslie Lamport, that proves that this type of queue is safe and correct given atomic updates of array indexes and limiting the queue to one reader and one writer.  In my implementation I emulate atomic index updates by copying the index to a local variable, making changes to the local then copying it back to the global index.  In some cases I’ve had turn off all compiler optimizations to insure that the local copy is not optimized out of existance but it would be even safer to code this part in assembly language.  I’ll post an implementation of this queue when I have the time.

On the ZigBee front there are a couple of good articles on Embedded Systems Design’s website. Picking the right 802.15.4/ZigBee wireless connection for your embedded design: Part 1: Matching Zigbee protocols to the application and Part 2: Power consumption and cost issues

I started playing with Atmel’s AVR Butterfly development board today. I received it for entering a design contest sponsored by Atmel and Circuit Cellar.

The Butterfly is literally smaller than a business card, runs off a watch battery, and includes an LCD, a joystick and a small speaker. The board comes with demo software loaded. The software is menu driven. Using the joystick and the display you use the menu to display the time, temperature or battery voltage, or play a couple of tunes or a few other sound effects.

Development software comes with the board and it is easy to load your own applications via the board’s serial port.  The AVR Butterfly board, coupled with one of MaxStream’s ZigBee RF modules (see Home Area Network) would make a perfect prototype for a wireless remote control for some mad-scientist/evil-genius project…… ah…… or…… a light dimmer….. no, really just a light dimmer.

Embedded Linux is getting a lot of exposure these days, in the trade press, books websites.  You can easily find all the reasons why Linux is the best RTOS solution.  Personally, I don’t think so. 

Don’t get me wrong.  I love Linux.  I develop a lot of code under Linux using the Eclipse IDE.  I prototype and unit test code under Linux.  I use Linux as an X-Term, a firewall, a local DNS server and a file server. Many, if not most web servers are running Linux.  At home and in the office, I have both a Windows box and a Linux box on my desk.

But there are legal, economic and technical reasons why I don’t believe the Embedded Linux is the right RTOS answer for most embedded products.

First, the legal issues.  Linux is licensed under the Free Software Foundation’s GPL which is designed to keep open source software open.  If you modify the kernel then you have to make the modifications’ source code public.  If you add a device driver, chances are this will be considered a kernel modification.  This is how Linksys got in trouble with their WRT54G router.  They were forced to release the source code much to the delight of their competition and hackers everywhere.  Under some interpretations of the GPL you can get into trouble for just linking to the GNU standard c library.  If you go the embedded Linux route, you might want to put an intellectual property lawyer on your development team.

Next the economic issues.  The old saying goes: “There’s no such thing as a free lunch.”  And using free software isn’t free.  You still need support.  Either you are going to pay someone for that support or do your support in-house.  In-house support means that at least one of your software engineers is going to be the Linux guru.  The time spent supporting Linux is time not being spent developing feature code for your target market.  You are diluting your added value to the end customer.  The other economic hit is that Linux is a bigger resource hog than other RTOSs.  This means more memory, faster processors, more heat and power.  All this adds cost to your product making the price higher or the margins lower.

Finally there are the technical issues.  In the final analysis, Linux is not a hard real time operating system.  The newer Linux kernels have improved a lot and you can hit your timing requirements most of the time.  If you are developing a hard real time system most of the time probably isn’t good enough.  Linux is also large and complex.  Being large and complex means more room for bugs and unexpected behavior.  It depends on the application and I don’t mind having Linux in my wireless router but I wouldn’t want it used in the flight controls of an aircraft that I’m flying in or have Linux as the OS in some medical equipment.

I believe that the excitement over Embedded Linux is stimulated by the reaction to the absurd per-seat and license pricing for VxBorg and the like.  I believe there is a market opportunity for an RTOS somewhere between the monopolistic pricing of the large embedded tool and RTOS vendors and the free lunch mentality of the Embedded Linux enthusiasts.  Only time will tell.

From here in the embedded systems trenches, my view is that most embedded systems software is still written in C and embedded software design, when it is done at all, is ad-hoc at best.  My rather pessimistic view is not just based on my own experience but also based on interviewing dozens of applicants for embedded programming jobs.  I believe that this is a crisis as our society becomes more and more dependant on technology and it is the big dirty secret of our industry.

There are a number of reasons why we are in this state today, some economic, some technical.  Ten years ago I worked for a company that had a concise repeatable process for embedded software design based on structured analysis and design and incorporating a CASE tool.  Then we caught object fever and jumped on the band-wagon.  I must admit that I became an object/C++ zealot myself and was partly responsible for this change.  The problem was that we never really had the time to learn how to do it well and during the transition the rest of our software processes fell apart.  I believe this happened at a number of companies at that time.

Then there were the go-go nineties when we were all in a rush to bring new products to market as quickly as possible at any cost, using any shortcut.  Many mid-level software engineers began their careers during the rush and never really learned design.  School projects just aren’t large or complex enough to teach good design skills.  The widespread embracing of agile methods is nothing more than an excuse for short-cutting the design process in many cases.   As one new embedded systems programmer put it in a review on Amazon.com:

One problem I have found in embedded area is that almost everybody uses procedural language to code i.e. C but nobody trains you (atleast no body does in Computer Engineering/Computer science undergrad) how to design large scale software in C. You read books about C and advanced C but how do you actually go about designing an embedded system from scratch. You go to the bookstores and everywhere you find “Object Oriented Analysis and Design”.

What about Object Oriented design?  Many of the shops where I’ve worked have paid it lip service.  We talk about use-cases when we mean requirements.  We throw a few class diagrams into a design document then implement the design in C, a procedural language.  The most commonly used object oriented CASE tool in use is Visio (hint – it’s just a drawing tool).  When C++ is used in embedded systems it is at best object based programming.  Classes are used for encapsulation but there is rarely any polymorphism, inheritance, or composition.

What is the solution?  I still believe that Object Oriented design and programming is the best solution for complex software systems but I’m a pragmatist.  When I was younger I was an Object zealot and a C++ bigot but twenty five years of experience has made me pragmatic if nothing else.  I think that it is time to seriously consider resurrecting Structured Analysis and Design.  What do you think?