Embedded Systems Programming Course

Operating Systems

Introduction

A wide variety of operating systems are available for embedded systems. Generally the processor used in the design will dictate what operating systems are available. Of course, advanced embedded designers are also free to develop their own operating systems, leaving out any features they do not need. This is commonly done when the design requires a bare minimum of RAM, ROM and external interfaces.

The most widely used operating systems in the embedded market normally include a common set of features, of which process and task scheduling, is probably the most important to most developers. Another very important feature of embedded operating systems is whether the OS is real-time or not. A real-time operating system basically is guaranteed to service interrupt requests from external devices in a predictable and consistent manner. In other words, the response time for interrupts in a real-time operating system is measurable and repeatable. An operating system that is not real-time does not have a predictable response to service requests. In some applications, this can mean the difference between a working, reliable system or one that sometimes works okay, other times does not.

Currently, the most popular embedded systems operating systems are probably QNX from QNX, Tornado and VxWorks from WindRiver, the TRON family of operating systems from the Sakamura Laboratory in the University of Japan, Lynx from LynuxWorks, OS-9 from Microware and uC/OS-II from Micrium, Inc. This is by no means an exhaustive listing.

There are literally hundreds of different commercial or free real-time and embedded operating systems on the market. One was even developed locally in Huntsville as an open source real-time operating system call RTEMS. You can download it by visiting On-Line Applications Research's website. They encourage interested people to improve the system by adding new features, which can then be included in later releases. For a more comprehensive list of embedded operating systems on the market, see one of the following web sites:

The capabilities and features provided by each varies widely, but most offer a fairly common set of features such as: a kernel that may support a large number of different processors, device drivers for various chipsets and plug-in boards, process and task management along with process/task scheduling services, basic input/output functions and much more. Some include video graphics capabilities complete with mouse support and window managers, for those systems that have this kind of hardware. Nearly all of them will come bundled with various tools such as text editors, compilers and/or assemblers, debugging tools and quite possibly even simulators that allow you develop and test software without needing the hardware at all. Prices range from no cost up to thousands of dollars depending on the quality of tools included.

Linux is quickly becoming a favorite amongst embedded systems developers. It has the unique attributes of not only being available for no cost, but also of supporting a wider array of devices and processors than most other embedded systems. In addition, the Linux kernel can be reduced to a very small size and stored on a ROM chip of less than 512KB if needed. Or if the system has the need for expanded features, it is easy to add additional device drivers or software of almost any imaginable type, generally at no cost.

One new use for this is the so-called network appliance market. Companies like NIC and now selling computers priced as low as $200 or less, that boot from a CD-ROM and can attached to a standard network, or dial up an ISP, and lets users browse the web, check e-mail, or run web-based applications. Any company that wants to market these new appliances will have to at least consider using Linux as the embedded operating system with it unique combination of powerful software and low costs. (Well maybe Microsoft won't consider running Linux as its operating system, but pretty much everybody else probably will.)

Since operating systems vary so widely and there are so many different ones to choose from, we will restrict ourselves to examining only a couple of them. You will of course have to make a final decision about which operating system you would like to run on your embedded designs for yourself. Remember, you can always create your own operating system, but generally this will only be realistic for very small projects, or on projects that you anticipate will sell by the thousands or millions. Building your own robust, high-performance, feature-rich operating system, even for a small embedded system is a daunting task. Unless absolutely necessary, I highly recommend trying to use an existing, well established, and thoroughly debugged operating system.


Tasks

Many embedded systems have multiple responsibilities and therefore must perform multiple tasks, apparently simultaneously. As an example, a home automation/security system may have to monitor window and door security switches, a smoke detector, turn on and off house lights at the appropriate times, detect rain conditions and turn on sprinklers, and much more. While the system is busy turning on lights, it absolutely must be able to still monitor the smoke alarm. If a break-in is detected, the system will probably call the police to notify them of a burglary in progress. While the system is busy dialing the police, it should still continue to check the smoke detector at regular intervals. This is called multi-tasking and embedded systems have several ways in which this can be accomplished.

The first, and simplest, method is by using what is called round robin processing. In this setup, a main loop just checks the state of the system, one after the other, in a loop. This works well for simple designs, but does have a few problems. First, is that important tasks are not given any extra priority and must wait for slower tasks to be completed before the high priority task get a chance to run. Many times, interrupts can be used to overcome this problem, but that can introduce its own set of problems. Let's look at an example.

////////////////////////////////////////////////////////////////////////
//
// RoundRobin1.c
//
// An example of round-robin processing.
//
// Emulates a simple home monitoring system.  Checks the state of the
// two input switches.  If the first is pressed, the system reacts as
// if a burglary is in progress and calls a function that would dial
// the police.  If the second switch is pressed, simulates the action
// taken for a smoke detector by calling the fire department.
//
// Revision History
//
// 5/31/2001 - RLP - Initial version
//
///////////////////////////////////////////////////////////////////////

#define LOOPCOUNT 1000

call_police()
{
  int i, j;

  printf( "Calling police...");
  WrPortI( PADR, NULL, 0x02);

  for( i = 0; i < LOOPCOUNT; i++ )
  {
    for( j = 0; j < LOOPCOUNT; j++ )
    {
      // This loop does nothing.  Simulates the time it takes to
      // call the police and notify them of a break-in.
    }
  }
  WrPortI( PADR, NULL, 0xff);
  printf( "done.\n" );
}

call_fire_department()
{
  int i, j;

  printf( "Calling fire department...");
  WrPortI( PADR, NULL, 0x01);

  for( i = 0; i < LOOPCOUNT; i++ )
  {
    for( j = 0; j < LOOPCOUNT; j++ )
    {
      // This loop does nothing.  Simulates the time it takes to
      // call the police and notify them of a break-in.
    }
  }

  WrPortI( PADR, NULL, 0xff);
  printf( "done.\n" );
}

int check_breakin()
{
  int val;

  val = RdPortI( PBDR );

  if( val & 0x04 )
    return 0;
  else
    return 1;
}

int check_fire()
{
  int val;

  val = RdPortI( PBDR );

  if( val & 0x08 )
    return 0;
  else
    return 1;
}

main()
{
  int alarm;

  // Switch Parallel Port A to output mode so we can light the LEDs
  WrPortI(SPCR, &SPCRShadow, 0x84);
  WrPortI(PADR, &PADRShadow, 0xff);

  while( TRUE )
  {
    if( check_breakin() )
      call_police();

    if( check_fire() )
      call_fire_department();
  }
}

In this short example, a round-robin system is used to first check for a break-in, then next for a fire. If either is detected, the appropriate function is called to dial the police or the fire department. Since there is no modem attached to the Rabbit prototype board, I've made the system turn on an LED and print a message to the debugging console, for testing purposes.

The only real problem with this system is that while it is busy dialing the modem, say the police, then it will never have a chance to check for a fire. This is because the call_police() function does not return until it is completed. One could argue that if either the police or fire department is called, there is no need to call the other. Remember though, this is just an example and instead of calling the fire department, perhaps the system should activate a sprinkler system and call the fire department. It would not be good to tie the system up completely while a lengthy task is being performed.

One solution is to use an interrupt that can sense the state of the switches as they are pressed, instead of polling the switches in a loop as we have done here. Another option is to create two separate tasks in the program, one that monitors for fires, while the other watches for break-ins. Each method is workable, but can introduce additional problems. The biggest problem is how to share resources, hardware and data, between the two tasks. In our example, the modem is used to both dial the police and to dial the fire department. Obviously a modem cannot do both simultaneously; therefore some way of sharing the device must be found.

The most commonly used way of sharing either data or resources between two different tasks is the semaphore. A semaphore is always in one of two states, either held or not held. Sometimes this is referred to as locked or unlocked. The act of locking the semaphore gives you exclusive rights to use the resource or data the semaphore is protecting. If one task has acquired the semaphore, all other tasks must wait until it is released before they can continue. In essence, the task that has acquired the semaphore has locked out all other tasks.

There are several terms that are sometimes used for semaphores, but most operating systems refer to them as either semaphores or mutexes. Technically, there are only two types, called counting semaphores and binary exclusive semaphores. A counting semaphore allows several locks to be placed on the semaphore, up to a pre-defined limit. A binary exclusive semaphore only allows a single lock to be acquired.

Counting semaphores are useful for limited the number of tasks that are running at the same time. Consider a web server that starts up a new task to handle every request from the client. If the client requests are spaced out over time, this is a very good way to achieve concurrency and makes the overall response of the system faster. Unfortunately, if many requests come into the web server at almost the same time, a large number of tasks may be launched. In this case, it may be good to limit the total number of tasks that can be active at the same time. A counting semaphore can provide an easy solution to this. Since there is a limit on the number of times the semaphore can be locked, it can be used to limit the total number of tasks that be spawned. Until one of the locks is released, presumably by one of the tasks completing, additional tasks will be unable to obtain a lock on the semaphore. The popular Apache web server software uses this technique. If it allowed an unlimited number of tasks to run, it is possible that the computer could be overloaded and spends all of its time switching between tasks, without getting any real work accomplished.

A binary semaphore, or mutex, only allows one tasks to acquire the lock. This is most commonly used to prevent two tasks from modifying data at the same time. Even if one task is only reading the data, a mutex is useful, since it prevents reading and using data that is in the middle of a change.

You should be aware of a couple of potential problems when using semaphores and mutexes. The biggest possibility for error is a condition known as a deadlock. Imagine for a second we have two processes running called Task1 and Task2. Also imagine that we have two mutexes protecting data, named MutexA and MutexB. If both tasks need to acquire locks on both mutexes, there is a possibility of a deadlock occurring. If Task1 first acquires MutexA, then MutexB, while Task2 acquires MutexB first, then MutexA, at some point in time a deadlock will happen. The problem occurs if Task1 locks MutexA, then before it can lock MutexB, a task switch occurs that allows Task2 to start running again. Now, Task2 can acquire a lock on MutexB, followed by an attempt to lock MutexA. Of course MutexA was locked by Task1, so Task2 is forced to wait for MutexA to be released by Task1. The operating system will put Task2 to sleep, pending the release of the mutex. This will probably allow Task1 to resuming running. Its next step is to acquire the lock for MutexB, which of course was just locked by Task2. Since Task1 cannot acquire the lock, it too is put to sleep until MutexB is released. Task2 is waiting for MutexA to be released, while Task1 is waiting for MutexB to be released. Since both tasks are now sleeping, waiting on the other, neither task will ever run again.

This kind of problem may escape even the most rigorous testing in the laboratory, only to start making the system crash or lock up, in some cases years after shipping the final product. The only way to be sure this kind of situation never occurs, is to never use mutexes or semaphores at all. Of course, that is not very realistic, so the next best thing is make sure all tasks acquire locks in the same sequence to prevent a deadlock.

Other problems with semaphores and mutexes are usually related to either completely forgetting to acquire a lock before modifying data, or forgetting to release a lock when it is no longer needed. Both of these problems are generally fairly easy to find, but careful attention to detail during your initial programming effort can save you a lot of wasted time and much frustration.

Another way to protect data is simply to disable processor interrupts while modifying the data. This works well in many cases, but does have an effect on the overall response of the system. While interrupts are disabled, the CPU is prevented from handling interrupt requests from the hardware. If the interrupts are disabled too long, it may mean losing serial port characters, missing timer ticks, etc? In some cases the data can be modified quickly enough that disabling interrupts is the best way to go. Locking and unlocking semaphores may require many thousands of CPU cycles, while disabling and enabling interrupts is generally accomplished in just a few CPU cycles.


Interprocess Communication and Control

When multiple tasks are running, very often some kind of communications between processes is needed. While it is certainly possible to setup your own data structures for this, there is still one problem that must be overcome. While you are modifying the data structures, the changes you make must be performed atomically. This means that the critical steps needed to change the data cannot be interrupted to prevent data corruption. In order to simplify your life as a programmer, most operating systems provide one or more ways for tasks to communication with each other.

The first interprocess communications method is called a mailbox. Just like an e-mail server, which has a mailbox that can hold messages exchanged between two people, an operating system mailbox holds messages exchanged between two tasks. Many different capabilities exist on mailboxes. Some systems only allow one task to write the mailbox, as the other reads from it, while others allow two-way communications. Some mailboxes can only hold a single message, while other may allow many messages to be stored in the mailbox. In any event, when reading from or writing to the mailbox itself, the operating system will ensure that the operation is done atomically, often times by temporarily disabling interrupts.

A queue is very similar to a mailbox, except queues generally can hold multiple messages. Very often queues can also sort their messages based on a priority level automatically. This causes more urgent messages to be retrieved before lower priority messages. Windows uses queues quite heavily for passing messages between tasks, especially between the operating system itself and the running application. It does not really have much of a concept on priority levels, but it does assume the WM_PAINT message (this message triggers a screen refresh) is the lowest priority message. As a result, Windows always scans the queue of all applications and inserts all other messages ahead of the WM_PAINT message, if it found in the queue. The idea is that those other messages may change the way the screen needs to be drawn, so why not process the WM_PAINT message as a last resort always. In many cases, the operating system may allow you to define your own priority levels.

Finally, a pipe is a way for one process to send large amounts of data to another running task or process. Basically one task can write to the pipe, while another task can read from it. Pipes are generally best thought of as a serial stream of data like a garden hose, where whatever is pushed into the input side, will eventually be extracted from the output side when it is read.