Some images of FrizzleBot. You'll notice I've hooked up the new battery pack and an ultrasonic range sensor on the front More details soon.

FrizzleBot

Here is a video of FrizzleBot roaming around my kitchen and hallway. The frame rate is not so great due to interference and roommates leeching the bandwidth on my network. However, it should at least give you a sense of how the interface works.

FrizzleBot

Quick update: I ran an experiment tonight and was able to send FrizzleBot on a mission from the living room of my apartment to the kitchen and back. No big problems, except there was a bluetooth connection reset at one point, but the connection was quickly restored, and disaster was averted. Otherwise, the experiment was a success.

FrizzleBot

I'm starting this log later than I should have,

but after some success, I've decided it is crucial

to start documenting my experiences with FrizzleBot.

Let's start from the beginning.

Early February this year I finally received the

package containing the pieces to a kit I ordered from

Bizoner.com. It includes a 4-wheel chasis with 4

servo motors (one for each wheel). Also included 

was an Arduino Duemilanove microcontroller board,

a motor shield and an I/O expansion shield from 

DFRduino. Other hardware included 4 wheels, panels,

standoffs, screws for mounting, a 9v battery

connector, a 4xAA battery pack as an additional

external power source, and some other miscellaneous

equipment for mounting. The kit came almost completely

disassembled, but the motor controller board and 

servos in the chasis were already wired. There were

also a couple of APC220 wireless serial chips, but

it turns out that I never used them for programming

the Arduino (more details on this later).

First, I tried assembling the pieces without disconnecting

the wiring or opening up the chasis. Once assembled,

I began experimenting with programming the Arduino using

the very simple Arduino IDE over a wired USB connection

to my laptop. Programming the microcontroller worked

without much trouble, but when I sent signals to the motors,

the wheels would move in opposite directions on the same side.

For example, sending a PWM signal to the left motors (they are

wired in tandem on each side) would cause one of the left 

wheels to move forward and the other to move backward. No matter

how I wired the motors to the board, I could not get both wheels

on one side to move in the same direction. Clearly this 

behavior could never be useful, so I was stuck.

Eventually, I decided to open up the chasis and look at how

the motors were wired together on each side. It turns out that

they came mis-wired, and I after I rewired them, the motors

would cooperate. This was the first roadblock I was able to

circumvent. I began experimenting with driving the motors, first

by writing a series of simple Arduino sketches, which worked easily

except for some difficulty figuring out what pins on the Arduino 

with which I needed to interact.

My goal was to eventually be able to control the motors from my

Verizon Samsung Galaxy S3 smart phone, which I had been hacking

on for a few months prior. I had been flashing custom ROMs and 

building my own kernels for a while.

Aside: I once flashed a ROM on my phone using a utility called Odin

which overwrote some partition, causing my phone to be unable to 

connect to the Verizon services. I couldn't use 4g, make calls, 

or send text messages. Even if I flashed the stock ROM I couldn't

get it to function properly, so first I went to a Verizon store in 

Boston. They tried resetting and flashing the device with their

equipment, but still the same problem persisted. That was December 

2012, and I went home to Texas to visit my family for Christmas. 

When I was there I went to another Verizon store, and they couldn't 

fix it either. I had them send me a new phone, and so far I haven't 

bricked this one.

My phone is now running Cyanogenmod 10.1 MR1, Android Jellybean 4.2.1,

with a custom built Android Linux kernel from ktoonsez (https://github.com/ktoonsez), version 

3.0.62. I built the kernel myself from source. 

I wanted to get the phone to communicate with the Arduino on

the robot without a wired connection. The reason is that I wanted 

to easily attach/detach the phone to/from the robot without having 

to deal with wires, and I also thought it would be an interesting 

exercise.

There were two options for wireless communication: bluetooth and

wireless ethernet. After thinking about this and shopping around,

I realized that there was no reason to use wireless ethernet, for

two reasons: (1) my phone already has a wifi adapter, so if it is

able to communicate with the Arduino, there is no reason to duplicate

the functionality, and (2) bluetooth adapters are generally less

expensive. For these reasons, I chose bluetooth as the communication

bus between the phone and the Arduino.

The I/O expansion shield that came with the robot kit has an XBee

socket which supports the BluetoothBee chips. I ordered one of these

for around $25, hoping that I could figure out how to get it functioning

with my board and not waste my money. This was the next major hurdle, and

at first I had no idea what I was doing, or whether or not the bluetooth

device was even compatible with my hardware.

After reading countless blog posts and tutorials, I had an idea of how to

write Arduino sketches for controlling the bluetooth device. It seemed 

simple in theory, but in practice this has been the most time consuming part

of this project so far. None of my initial sketches succeeded in pairing the

BluetoothBee with my phone's bluetooth device. At first I thought I had a

defective BluetoothBee, but from experience I suspected that I had probably 

missed some important step. Finally, I discovered the correct TX/RX pins to

use and the proper sequence of AT commands to send to the bluetooth device to

configure and put it into slave pairing mode, with automatic reconnect enabled.

It is worth noting that initially I was using an application on the phone

called BlueTerm to test connections with the Arduino. One day I was

astonished to see the red and green blinking LEDs on the BlueToothBee,

signifying that I finally had correctly programmed it to enter pairing mode

and start listening for pairing and connection requests from remote devices.

I fired up BlueTerm on the phone, paired with the Arduino, and established my 

first bluetooth connection.

Now I could send data from the phone to the Arduino, which would allow me to

write a very simple command set that the Arduino program would translate to

PWM signals sent to the servo controller outputs. Although the basic operations

worked, it took some time to get a somewhat robust motor control program

running, without experiencing random bluetooth connection resets or power

resets due to driving the motors incorrectly. It took a lot of experimentation

to find the right bounds for speed and timing parameters. At this point it

is somewhat stable, but occasionally I still get random connection resets. To

get around this, for now, I've made sure to stop the motors on reset, and

the BluetoothBee is configured to quickly automatically reconnect. It turns

out that connecting an additional external power supply, separate from the

power to the Arduino Duelimanove board, reduces the frequency of resets to a

manageable level. Now, I usually connect a 9v battery to the Duelimanove, and

the 4xAA battery pack is wired into the motor controller shield. I went and

bought a bunch of rechargable lithium AA batteries, because I can test using 

only these (without the 9v) and it still gives enough power to the Duelimanove

as well as the servos (albeit with less juice than if both power sources are

plugged in).

The command set that the motor control program implements is very simple; each

command is a single character:

'w' - set mode to move forward

's' - set mode to move backward

'a' - set mode to turn left

'd' - set mode to turn right

' ' - set mode to stop (saves speed to be restored on next mode change)

'x' - increase speed (by a hardcoded increment, caps at a maximum speed)

'z' - reduce speed (if > 0)

The program will send back the current speed value when the speed is changed.

Debugging and testing the motor control program for the Arduino

was another time consuming task, and is still sort of in progress, but it works

well enough to go on to more interesting things. On the phone side, I had

been testing all of this with BlueTerm, but I wanted a custom Android

application that I could use to programmatically send control commands to the

Arduino. So, I downloaded the Android SDK and development toolkit,

installed Eclipse, and configured the Android plugins for the IDE.

I found an example project for Eclipse that implements a simple Bluethooth

chat terminal, designed to be used to communicate between two Android devices.

I started working from the example Java source as a basis for an application 

that would allow me to establish a bluetooth connection to the Arduino and 

send data over the connection from the phone. My motivation was to be able to

forward data coming into the phone over an ethernet socket (e.g. from my

laptop) to the phone's bluetooth connection with the Arduino, thus remotely

controlling the motors over wifi from a remote location. The reason I wanted

this functionality is that I wanted to create a sort of ground-based "drone,"

that I could control while watching a video feed from a remote machine with an

Internet connection. The phone itself would be mounted on the robot and video

data collected by one of the phone's cameras.

My first idea was to use VNC to remotely control the phone, so I could load up

the BlueTerm application and not have to write my own custom app. The problem

was that no matter what video server app I used on the phone, it would not

continue to stream video if another view was active. When I would load the 

BlueTerm app over VNC, it would always stop the video feed, so I could only

use one or the other, but not both simultaneously. I figured programming

bluetooth would be easier than writing my own video server, so I chose to

focus on a background Android service that would open a TCP port, and upon 

connection, would forward all data from that port over the bluetooth

connection with the Arduino.

All of this shouldn't have been too difficult, but I hadn't used Eclipse for

years and had no experience with the Android SDK. Most of my problems were

related to Eclipse conventions for projects and Android xml configurations, so

this was definitely a learning experience. Also, I rarely use Java since most

of my experience is in low-level C and assembly language programming. It took

me a while to get the hang of the development environment, but I just recently

got this TCP to bluetooth socket program working. Now, I can power on my 

Arduino, load up the Android app, establish the bluetooth connection, and

telnet to a TCP port on the phone from my laptop. I can type the characters

from the command set I mentioned above directly into the telnet terminal on

my laptop, and they are forwarded to the Arduino to drive the robot around.

Since the forwarding logic is contained in a service running in the

background, I can load up the video server application on my phone, and watch

the video feed on my laptop as I'm also remotely controlling the motors.

The only other thing to complete this experiment was to physically mount the

phone on the robot. The kit had some strange looking metal bracket pieces that

just happened to be the right size to hold my phone steady. I spaced them in

such a way (and bent the metal a little bit) that I can seat the phone between

them without having to use ties, tape, or bolts. The video server I'm using

allows me to control some things, such as turning the bright LED on and off in

case the environment is too dark to see anything in the video feed. I can

view the video and access these controls over an http connection to the phone

from my laptop, while I also have the telnet connection open to control the

motors.

Next, I will try to connect this sonic range sensor I bought to the Arduino,

and figure out how to integrate it into the Arduino program. Its function

will be a failsafe stop mechanism to keep the robot from crashing into things,

in case either the TCP or bluetooth connection is lost and for some reason the

motors keep going. If it works well, I'll probably buy a few more to mount

around the perimeter of the robot, to increase safety. I'm amazed I haven't 

completely destroyed the thing yet, but I'd like for it to stay in one piece.

Another task is to learn about the camera API on the android, and integrate

the current tcp-to-bluetooth forwarding app with my own video streamer. I'm

stil not happy with the performance of the video server app I'm currently

using, and it's not convenient to have to load multiple apps on the phone to

initialize the connections and video stream. I will probably also write a 

client application for the laptop so I don't have to load a web browser and a

telnet terminal. 

Paper Review - Binary Translation Using Peephole Superoptimizers

This post is a review of a paper that was published in the Operating Systems Design and Implementation conference (OSDI) 2008:

Binary Translation Using Peephole Superoptimizers
Sorav Bansal and Alex Aiken, Stanford University
URL: http://www.usenix.org/events/osdi08/tech/full_papers/bansal/bansal.pdf

This is one of my new favorite papers from OSDI. They propose a novel application of techniques found in superoptimizers: automatic learning of translation rules that can be used to construct binary translators. They provide a method of determining optimal register mappings between architectures, and implement their approach. They use the implementation to generate translation rules, thereby constructing a static binary translator. PowerPC is used as the source architecture, and the target instruction set is x86. Experimental results are shown, that measure the runtime of translated code, compared with the native execution. Micro-benchmarks (lmbench) and larger benchmarks (specint) are the experimental workloads.

The following are some rough notes that I made just after reading this paper. I'll try to tweak my original notes a little, so they seem more coherent to the reader:

One really interesting thing about this work is that they use qemu on a linux-x86 host to compare performance and results of instruction sequences executing on an emulated PowerPC platform. Although the paper didn't say much about how they actually ran their experiments, I assume that they batch two phases: 1) train with sequences found on the powerpc platform, and record all of the state change and performance results, 2) feed the results from (1) into the x86 half of their implementation, discovering the translation rules. They didn't say much about how certain information about the architectures is encoded, such as register layout, flags, but did mention how they handled the stack and heap. I'm assuming the architectural details and general info about the instruction set encoding could be represented in some high-level interpreted language or configuration file.

Their approach is computationally complex, so it takes about a week to get a good set of rules. One source for additional research would be to look into optimizations for the approach. Pruning the search tree of possible sequences and finding register mapping more efficiently are particular examples. However, once the translation rules are found, the binary translator can be used with minimal overhead (avg ~67% native in their case).

Interestingly, the translated code often performed better than the native on microbenchmarks. This, they mention, could be due the fact that code is fundamentally easier to optimize on a RISC architecture such as PowerPC. When that highly optimized code is then translated to x86, a CISC architecture, the translated code is better optimized than the native x86 instructions used in the benchmarks. One thing to note here is that it is very difficult to compare performance across different architectures, so in general, this is a touchy subject. However, the approach in this paper is using relative execution costs, to find the best possible translation sequence of instructions such that performance is optimized and correctness is ensured. Also, I'm assuming all comparisons are done between translated x86 code and native x86 code from the x86 versions of the benchmarks (with some unspecified level of optimization).

Experiments were only performed on a static translator, although they do explain that their method could be theoretically applied to a dynamic translator. They calculate the overhead that would result from dynamic translation, and try to compare, but I'm not quite sure their analysis is correct, have to check this. I think they are ignoring the fact that there will be repeated
invocations of the algorithm that determines the best register mapping, as the register mappings change with different sequences of instructions. It seems like a bad idea to keep changing the register mappings, because the memory layout of the translation cache and representation of the virtual cpu will change continuously. However from my experience implementing a dynamic translator, the translation overhead is typically very low compared to the overhead due to low instruction quality (execution time of the instructions from the cache). The only difference in my case was that my source and destination were the same architecture (roughly), so the translation module itself was very efficient, also since many of the instructions had identical translations (and it was a RISC architecture). The point here is, that I think it is an open problem whether or not a performant dynamic translator would result from this work, although I am optimistic.

What I mostly learned from this paper is the material on superoptimizers. It makes sense that this would be a natural application, and I think that it's a good overlap between OS and Programming Languages. Also, it was good to get a review on issues in binary translation, which I have a lot of knowledge of (certainly, from implementing a full-system dynamic binary translator from scratch!). The paper touched on a large numbers of the problems I had to deal with during implementation. They don't go into too much depth on any one of these, but it definitely jogged my memory and made me remember the additional things you have to worry about when the translator is dynamic.

Unfortunately, I don't think their contribution can be applied to writing a same-architecture translator that includes translation of kernel code (full-system), with much reduction on the engineering effort. This is because much of the engineering complexity in this case has to do with branch handling, spilling/filling registers, exception handling and redirection, emulating memory accesses to protected data or memory mapped I/O, emulation of interrupt logic and low-level devices (ie, timer, serial port), and synchonizing resources among emulated threads. Additionally, a translator that translates between the same source and target instruction sets trivializes many of the translation rules, because many non-priveleged instructions will have identical translations. But, for a basic survey of fundamental binary translation issues for mostly user-level code between different instruction sets, this is a good paper.

Programming the Garcia Robot

Over the past few years, I've received emails from various students at universities around the world, wanting to find out how to write software for their Garcia Robot. The product is made by Acroname, Inc. and comes with a wide variety of options. Most of what I focus on here is the software aspect of the system, which requires an embedded computing platform. Acroname ships the Garcia with a Stargate board, sold by Crossbow Solutions, equipped with a USB port, a PCMCIA slot for wireless networking, two serial ports for interfacing with sensors/actuators, and an ARMv5-based Intel XScale CPU.

Besides the main computer described above, the Garcia also includes a micro-controller board, called the Brainstem, that provides a serial interface for controlling 2 wheel motors and accessing data from infra-red sensors and the ledge detector. Knowing the various ways of interfacing with the Brainstem is key to being able to write complex programs to control every aspect of the robot's behavior.

The Stargate platform runs a provided distribution of Linux. It is therefore possible to develop applications using the system call APIs (ie, read()/write()) in order to receive and send data over a serial port to the Brainstem. This is a cumbersome but useful way to gain precise control over all of the operations of the Brainstem, but is usually only a good option if predictability is needed for timeliness experiments. Also, this method requires the developer to understand many details about the Brainstem architecture and configuration.

Included with the software is a cross-compiler toolchain. Various toolchains for ARM-based platforms can be downloaded from the web, but they all provide an assembler, compiler, linker and other tools for generating ARM binaries using an x86-based pc for the development environment. Once a program is compiled, it can be uploaded to the Stargate via a wireless network, and subsequently executed.

Brainstem Commands

A Brainstem command is a variable-length sequence of bytes, with the following format:


The module field specifies the address of one of the two available modules on the Brainstem: the GP and the MOTO. The MOTO controls the motors and some of the infra-red sensors, and the GP controls the rest of the sensors. Refer to manuals on Acroname's website for details on which module is associated with each of the sensors/actuators. By default, the module address of the GP is 2, and the MOTO is configured at address 4.

Following the module address, the second byte of the command specifies the length in bytes of the command packet, not including the first two bytes for the module and length. Next, the command field specifies one of the many possible commands to execute. Acroname maintains a list of these commands and their argument formats in their Brainstem reference. Each command has a different number of arguments with varying semantics, so following the command field there are zero or more argument bytes.

The following is an example of a command packet that tells the Brainstem to set the velocity of one of the motors to the value 10: 4 4 62 0 0 10. Here, the first byte of value 4 specifies that this packet is for the MOTO module. The third byte of value 62, specifies the command number that sets the motor velocity, and the following bytes are the command's arguments, which specify to set the motor with index 0 to a velocity of 10 units. The command and its arguments have a combined size of 4 bytes, thus 4 is specified as the length field in the second byte of the packet.

In many cases, after a command is sent to the Brainstem, a reply will be sent back through the serial port in the form a debug packet. For example, after informing the GP module to do an infra-red sensor reading, a debug packet containing the value read from the sensor can be obtained via a read() call on the serial port's file descriptor.

An Example Program

The code for a simple console program is listed below, as an example of how to send Brainstem commands over the Stargate's serial port. The code uses standard APIs and assumes that the serial port device file is located at /dev/cua0. This code is intended for illustrative purposes only, and may need to be tweaked for use in practice. The values for the command bytes are read from the standard input and sent in binary format using the write() system call on the file descriptor of the serial port.

#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>

#define MAX_COMMAND_BYTES 50
#define SERIAL_PORT "/dev/cua0"

main()
{
   int i;

   int fd;
   size_t bytes_written;
   char command_bytes[MAX_COMMAND_BYTES];

   // Open the serial port for writing
   fd = open(SERIAL_PORT, O_RDWR | O_SYNC);

   if(fd < 0)
   {
      printf("Failed to open serial port\n");
      exit(1);
   }

   while(1)
   {
      // Collect command byte values from user
      printf("Enter Command >> ");

      scanf("%d %d", &command_bytes[0], &command_bytes[1]);

      for(i = 0; i < command_bytes[1]; i++)

         scanf("%d", &command_bytes[i+2]);

      // Send command packet to serial port
      bytes_written = 0;

      do
      {
         bytes_written = write(fd, (void *)(command_bytes + bytes_written),
                               (size_t)(command_bytes[1] + 2) - bytes_written);

         if(bytes_written < 0)
         {
            printf("Error writing to serial port: %d\n", bytes_written);

            exit(1);
         }
      } while(bytes_written < (size_t)(command_bytes[1] + 2));

      printf("Sent command to module %d, length %d:", command_bytes[0],
             command_bytes[1]);

      for(i = 2; i < (command_bytes[1] + 2); i++)

         printf(" %d", command_bytes[i]);
      printf("\n");
   }
}

References

• Acroname, Inc.: http://www.acroname.com
• Crossbow Solutions XScale Platform: http://blog.xbow.com/xblog/stargate_xscale_platform/
  
• Stargate Resources: http://platformx.sourceforge.net/Links/resource.html
  

A Real-time Systems Tutorial

Real-time systems design is an increasingly important topic in systems research communities as well as the software industries. Real-time applications and their requirements can be found in almost every area of operating systems and networking research. An incomplete list of such domains includes distributed systems, embedded systems, network protocol processing, aircraft design, spacecraft design..., and the list goes on. This page is intended to give the reader a brief, however incomplete, introduction to the concept of real-time tasks and their implications in the design of operating systems.

Table of Contents:

1. Introduction

2. Table of contents


3. Real-time task models

4. Real-time scheduling

5. Hard vs. soft real-time

6. Real-time networking

7. A survey of real-time systems

8. Conclusion

Real-time Task Models

In order to understand the functions of a real-time system, it is necessary to develop models of real-time activities and study their characteristics.
In this section, two fundamental real-time task models are described: periodic and aperiodic real-time tasks.

Periodic Real-time Tasks

In general, a real-time task requires a specified amount of particular resources during specified periods of time. A periodic task is a task that requests resources at time values representing a periodic function. That is, there is a continuous and deterministic pattern of time intervals between requests of a resource. In addition to this requirement, a real-time periodic task must complete processing by a specified deadline relative to the time that it acquires the processor (or some other resource).



For simplicity, assume that a real-time task has a constant request period (ie, must begin execution on the processor every n milliseconds). We can characterize such tasks as a tuple of values, (C, T), where T denotes the request period, which corresponds to the amount of time between temporally adjacent requests, and C represents the service time, or the amount of time for which the task must execute (in total) before a deadline, which is typically assumed to occur at the start of the next request period.



For example, a robotics application may consist of a number of periodic real-time tasks, which perform activities such as sensor data collection or regular network transmissions. Suppose the robot runs a task that must collect infrared sensor data to determine if a barrier is nearby at regular time intervals. If the configuration of this task requires that every 5 milliseconds it must complete 2 milliseconds of collecting and processing the sensor data, then the task is a periodic real-time task, and can be characterized in this model as the tuple: (C=2ms, T=5ms).

Aperiodic Real-time Tasks

The aperiodic real-time task model involves real-time activities that request a resource during non-deterministic request periods. There may either be no bound or only a statistical bound on the arrival period of
individual requests (task instances). Each task instance is also associated with a specified deadline, which represents the time necessary for it to complete its execution.



Examples of aperiodic real-time tasks are found in event-driven real-time systems, such as ejection of a pilot seat when the command is given to the navigation system in a jet fighter. Many, less time-sensitive, applications also arise in distributed systems involving real-time streaming media (ie, end-host routing over a logical overlay).

Real-time Scheduling

One of the most important responsibilities of a real-time system is to schedule tasks according to their deadlines in order to guarantee that all real-time activities achieve the required service level. Many scheduling algorithms exist for a variety of task models, but fundamental to many of these are the earliest deadline first (EDF) and rate-monotonic (RM) scheduling policies. A schedule for a set of tasks is said to be feasible if a proof exists that every task instance in the set will complete processing by its associated deadline.
Also, a task set is schedulable if there exists a feasible schedule for the set. The utilization associated with a given task schedule and resource (ie, CPU) is the fraction of time that the resource is allocated over the time that the scheduler is active.

Earliest Deadline First

The EDF scheduling algorithm is a preemptive and dynamic priority scheduler that executes tasks in order of the time remaining before their corresponding deadlines. Tasks with the least time remaining before their deadline are executed before tasks with more remaining time. At each invocation of the scheduler, the remaining time is calculated for each waiting task, and the task with the least remaining time is dispatched. If a task set is schedulable, the EDF algorithm results in a schedule that achieves optimal resource utilization. However, EDF is shown to be unpredictable if the required utilization exceeds 100%, known as an overload condition. EDF is useful for scheduling aperiodic tasks, since the dynamic priorities of tasks do not depend on the determinism of request periods.

Rate Monotonic

Recall the parameterization of a real-time periodic task as a tuple (C, T). Under the static-priority rate monotonic scheduling algorithm, tasks are ordered according to the value of their request period, T. Tasks with shorter request periods are assigned higher priority than those with longer periods. Liu and Layland proved that a feasible schedule is found under rate monotonic scheduling if the total requested utilization is less than or equal to ln(2), which is approximately 69.3%.



RM scheduling is optimal with respect to maximum utilization over all static-priority schedulers. However, this scheduling policy only supports tasks that fit the periodic task model, since priorities depend upon request periods. Because the request times of aperiodic tasks are not always predictable, these tasks are not supported by the RM algorithm, but are instead typically scheduled using a dynamic priority scheduler such as EDF.

Hard vs. Soft Real-time

The issue of predictability is of key concern in real-time systems. In fact, the term "predictable" can often be found in the multitude of definitions of real-time in the literature. Both periodic and aperiodic tasks have strict timing requirements in the form of deadlines. That is, the scheduler must be able to guarantee that each task is allocated a resource by a particular point in time, based on the task's parameters. In order to accomplish this, every allocation of any resource to any task must incur a latency that is deterministic or that can at least be predicted within a statistical margin of error.




Hard real-time tasks are required to meet all deadlines for every instance, and for these activities the failure to meet even a single deadline is considered catastrophic. Examples are found in flight navigation, automobile, and spacecraft systems. In contrast, soft real-time tasks allow for a statistical bound on the number of deadlines missed, or on the allowable lateness of completing processing for an instance in relation to a deadline. Soft real-time applications include media streaming in distributed systems and non-mission-ciritical tasks in control systems.

Real-time Networking

The growth in number of real-time distributed applications has fueled interest in methods for providing predictable communication-related services. Consider a wireless sensor network designed to locate injured civilians in disaster areas, or a networked application that allows a surgeon to control medical instruments from a distance. Many researchers are developing real-time network protocols and operating system mechanisms to ensure predictability of data distribution for such applications.



The real-time transport protocol (RTP) is a protocol based on UDP and is typically used in video/audio streaming applications in which there is a high tolerance for packet loss and low tolerance for delay variation. RTP is used in both multicast and unicast scenarios along with RTCP for transmission of control messages that carry quality feedback data.




Even if real-time networking protocols are employed, predictable service may not be possible unless end-host operating systems are equipped with appropriate mechanisms for processing incoming/outgoing network packets. These services typically dispatch event handlers in interrupt context in order to respond to events on the network, such as a packet received or ready for transmission. Systems such as RTLinux and RTAI, when used in conjunction with extensions like RTNet, provide deterministic timing guarantees on network packet processing and thus allow for real-time communication assuming that the low level network protocols in use are sufficiently predictable.

A Survey of Real-time Systems

The following is a list of some well-known real-time systems and links to more information:



QNX Neutrino Realtime Operating System


VxWorks RTOS


RTLinuxPro
and RTLinuxFree at FSMLabs



RTAI - the RealTime Application Interface for Linux


Montavista Real-time Linux


Xenomai - Real-time framework for Linux


RTnet - Hard Real-Time Networking for Real-Time Linux

Conclusion

As real-time applications become ubiquitous in various areas of computing research, there is motivation to extend existing systems with the mechanisms and policies necessary for providing predictable service. Also, many new real-time task models are being investigated in order to devise suitable scheduling algorithms for these new applications. Computer scientists will continue to analyze these new methods and apply them in situations where predictability and timeliness is of key consideration. Real-time systems is a rich domain for further study and will most likely continue to thrive for years to come.