Thursday, May 28, 2009

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


Thursday, May 14, 2009

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.

Search

BlogListing