Software Engineering

Our expertise brings needed skills to your project

Linux Event Loop with Cyclic Executive

Simple Real-Time Scheduler for Embedded Linux

So, you’re developing a real-time application which runs under Linux
  • You’ve got some periodic (for example, timer) signals to handle
  • And some aperiodic tasks (perhaps handling TCP/IP packets or other I/O)
  • And some regularly scheduled tasks to perform (such as motor control, UI)
Here is a simple design which cleanly handles all those soft real-time requirements:
  1. Set-up a periodic timer to expire at the shortest periodic task rate
  2. Write and Register a signal handler for the timer
  3. Open files corresponding to the aperiodic events
  4. Within an infinite loop, use pselect() to block until the periodic timer expires or an aperiodic event occurs:
    1. If a file became “Ready …” – handle the data / request / etc.
    2. If the timer signaled – run the periodic / regularly scheduled tasks as needed

Overview

We’ll discuss each of these steps in detail below. The basic design pattern is an infinite event loop, sometimes called a “Super Loop”. By using a periodic timer to generate a signal we incorporate a Cyclic Executive within the event loop. The timer expiration becomes an event to be processed. This event triggers the execution of all the periodic tasks: those that must run at a predefined rate.

In contrast to this periodic event, many important events, such as Input/Output (I/O), are unpredictable – they do not occur on any defined schedule. When they do appear, they must be processed right away. We capture these events as changes in the state of their associated file descriptor.

“Everything is a file” is a general philosophy of Linux. Or more accurately, “Everything is a file descriptor”. TCP and UDP sockets, pipes, serial comm ports and other devices, shared memory, even information on system processes are all referenced via the Linux file system. Open one of these files and you can read / write to that entity – for example, receive data from a serial port or write data to a TCP connection.

We access these elements through their associated file descriptors. For example: when a file descriptor for a serial I/O device becomes “Ready to Read”, it indicates data has been received and our program can go get it. Or, when a file descriptor for a TCP/IP client socket becomes “Ready to Write”, it indicates our connection request to a server was accepted (or rejected).

Our event loop will run as soon as any of the files we specify become ready to read, or ready to write (or either). It will also run when the periodic timer signal is raised. When it runs, we simply determine which event (or events) occurred and handle them. Then we return to the top of our event loop and block (sleep) until the next event occurs.

Linux Event Loop with Cyclic Executive
Figure 1 - Linux Event Loop with Time-Triggered Cyclic Executive

Periodic Timer – Setting up the Cyclic   Executive

The periodic timer is the heart of the Cyclic Executive. If there are any tasks to perform on a regular basis, and this is almost always the case, it’s required. Examples:

  • Handling user input
  • Updating the user interface
  • Controlling motors or other actuators
  • Monitoring temperature, pressure or other sensors

All of these are typically done at some fixed interval, requiring periodic scheduling.

The timer’s duration is set to expire at the fastest periodic rate required for any of the tasks. For example, consider the following tasks:

  • Every 20ms: update a motor control output
  • Every 40ms: check the status of an active communications port
  • Every 100ms: update the user interface

Since the periods are all multiples of the shortest task (20ms), we can use a single timer. We simply count the number of 20ms invocations to determine when to run the 40ms and 100ms tasks: every 2x or every 5x, respectively. If you need to run a task at a rate which is not a multiple of the fastest task, say, every 33ms, set-up an additional periodic timer at that rate.

Write the Signal Handler

The first step is to write the code which will be called when the program receives the “Periodic Timer Expired” signal. It should look something like this:

#include // gOverrun_cnt_20ms tracks the number of 20ms timer expirations between signal handler invocations

static volatile sig_atomic_t  gOverrun_cnt_20ms = 0;

// gCnt_20ms_isr tracks the number of invocations between event loop processing runs

volatile sig_atomic_t   gCnt_20ms_isr = 0;

// gProcess_20ms_task flag indicates handle 20ms processing

volatile sig_atomic_t   gProcess_20ms_task = FALSE;

// This is the actual signal handler function

void handler_20ms_periodic_timer(int sig, siginfo_t *siginfo, void *context) {

int i;

gCnt_20ms_isr++;  // Increment the 20ms signal handled counter

gOverrun_cnt_20ms = siginfo->si_overrun; // Save overrun count

gProcess_20ms_task = TRUE;  // flag the 20ms processing to run

}

Notes on the Signal Handler

  • sig_atomic_t is an integer type which is guaranteed to be read / written as an atomic entity even in the presence of asynchronous interrupts or signals. Although we’re using the C increment “++” operator here, which performs a read/modify/write, since the only function which also references these variables ( main()) will be blocked while this signal handler is running, it’s safe.
  • gProcess_20ms_task is a global flag which will be checked within our event loop to determine if it’s time to run the 20ms task. Of course, this could (and probably should) be encapsulated in get / set functions, but to keep from cluttering the main design points we’ll just use globals here.
  • gCnt_20ms_isr and gOverrun_cnt_20ms are two variables we can check in our main() routine to see if things are running as expected. If gCnt_20ms_isr > 1, it tells us we didn’t run the 20ms task processing before a 2nd timer signal was received.

On the other hand, gOverrun_cnt_20ms tells us how many timer signals were generated before our signal handler finally ran. This indicates it was blocked – probably by some process external to our application, but possibly by an error within our program.

Register the Signal Handler

The next step is to register the signal handler for the periodic timer. This informs the Linux kernel what function to call when the signal is delivered to our process.

#include

struct sigaction sig_act;

char buf[255] = {0};   // buffer used for error messages

// Use the sa_sigaction field, not the handler field

sig_act.sa_sigaction = &handler_20ms_periodic_timer;

//tell sigaction() to use the sa_sigaction field, not sa_handler

sig_act.sa_flags = SA_SIGINFO;

sigemptyset(&sig_act.sa_mask); // Don’t block additional signals when running handler

if (sigaction(SIGRTMIN, &handler_20ms_periodic_timer, NULL) < 0) { // Register it!

// Display some diagnostic info on stderr if sigaction() doesn’t succeed

snprintf(buf, sizeof(buf), “problem registering handler … %s–>%s:%d “, __FILE__, __FUNCTION__, __LINE__);

perror(buf);

psignal(SIGRTMIN, buf);

}

Notes on registering the signal handler

  • SIGRTMIN is a macro for the real-time signal number which will be associated with this handler. This value is adjusted by the Linux operating system and can vary. Therefore, always use the macro, not a hard-coded number. Additional signals use notation SIGRTMIN+n.
  • Registering the signal handler is typically done in the program’s start-up initialization code.

Create and Initialize the Timer

Next, we create the periodic timer. Before doing so, it’s a good idea to block the timer signal, so we don’t get a signal before we’re ready.

sigset_t mask;      //define a signal mask

sigemptyset(&mask); //signal mask must be cleared first …

sigaddset(&mask, SIGRTMIN); // … then add our signal to the mask

sigprocmask(SIG_BLOCK, &mask, NULL); // and add it to the process’s signal mask

Next, create the timer. This involves setting up a few variables and calling the timer_create() function.

timer_t timer_20ms;

struct sigevent sig_event;

sig_event.sigev_notify = SIGEV_SIGNAL; //generate a signal when timer expires

sig_event.sigev_signo = SIGRTMIN;     // use this signal number

sig_event.sigev_value.sival_ptr = &timer_20ms; // pass this timer id to sig handler

timer_create(CLOCK_MONOTONIC_RAW, &sig_event, &timer_20ms); // Create the timer

Now we can start the timer. Calling timer_settime() with a non-zero value in itimer_spec.it_value  arms (starts) the timer. When the timer expires, if itimer_spec.it_interval is non-zero, the timer is reloaded with that value, which re-arms it.  We’ll set an initial timeout in 20ms, with an interval of 20ms.

struct itimerspec itimer_spec;

itimer_spec.it_value.tv_sec = 0;

itimer_spec.it_value.tv_nsec = TWENTY_MS_IN_NS;

itimer_spec.it_interval.tv_sec = 0;

itimer_spec.it_interval.tv_nsec = TWENTY_MS_IN_NS;

timer_settime(timer_20ms, 0, &itimer_spec, NULL) != 0)

Lastly, unblock the timer and we’re set to go!

sigemptyset(&mask); //signal mask must be cleared first …

sigaddset(&mask, SIGRTMIN);  // then add our signal

sigprocmask(SIG_UNBLOCK, &mask, NULL); // and remove it from the process’s signal mask

Notes on creating the timer

  • CLOCK_MONOTONIC_RAW is the type of clock we’ll use for this timer – it’s unaffected by the Network Time Protocol (NTP) or the incremental adjustments performed by adjtime(). If your Linux kernel is earlier than 2.6.32, you’ll have to use CLOCK_MONOTONIC. Realize it will jitter slightly as NTP, if used, maintains synchronization with the network’s time server. Don’t use CLOCK_REALTIME – it will jump forwards and backwards as the host system enters and leaves daylight-savings time, or if the time is manually adjusted.
  • TWENTY_MS_IN_NS is a macro defined as 20,000,000 – the number of nanoseconds in 20 milliseconds.
  • The signal mask is the set of signals whose delivery is currently blocked. Sigprocmask() is “unspecified” in a multi-threaded process, since each thread has its own signal mask and there is no single process signal mask. Use pthread_sigmask() in multi-threaded processes.

Set-up the infinite event loop

Before we enter the event loop for good, get the current signal mask with the unblocked timer interrupt; we’ll need it for the upcoming pselect() call:

sigset_t signal_mask;      //define a signal mask

sigprocmask(0, NULL, &signal_mask); // get current signal mask (timer is unblocked)

The infinite event loop is simple. If you want a way to exit the loop, put it in the loop condition:

while (some_condition_to_exit_the_process == FALSE) {

We’ll use pselect() to put the process to sleep until an event occurs:

  • either a specified file descriptor becomes ready
  • or the timer signal is raised

To avoid a race condition, we have to block the periodic timer signal and check it’s flag before calling pselect().

sigset_t mask;      //define a signal mask

sigemptyset(&mask);        //signal mask must be cleared first …

sigaddset(&mask, SIGRTMIN); // … then add our signal to the mask

sigprocmask(SIG_BLOCK, &mask, NULL); // and add it to the process’s signal mask

If the periodic timer signal has fired, do the 20ms Task processing now.

if ( gProcess_20ms_task == TRUE ) {

gProcess_20ms_task = FALSE;   // reset the global variable

do_20ms_task();

}

Specify the aperiodic events

Linux maps sockets, pipes, serial I/O and other hardware devices, shared memory, etc. to files. Our program detects events generated from these sources by changes in their read, write, or error statuses. We access these elements through their associated file descriptors.

To handle aperiodic events of interest we set-up file descriptor sets for pselect() to wait on. There are three sets: read, write, and error. pselect() will block until:

  1. any file descriptor in the read set is ready to read
  2. any file descriptor in the write set is ready to write
  3. any file descriptor in the error set has an error condition pending
  4. a specified timeout occurs
  5. a specified signal occurs (our SIGRTMIN timer signal, for this example)

We will only use the a., b., and e.  conditions for our Scheduler.

Set-up the file sets to include all the file descriptors we’re currently waiting to become ready to read, or ready to write:

FD_ZERO(&read_fdset); // initialize descriptor set to the NULL set

FD_SET(serial_io_fd, &read_fdset); // add the serial I/O file descriptor to the read set

FD_SET(named_pipe_fd, &read_fdset); // add the named pipe file descriptor to the read set

FD_ZERO(&write_fdset); // initialize descriptor set to the NULL set

FD_SET(TCP_client_fd, &write_fdset); // add the TCP Client descriptor to the write set

We also need to know the maximum file descriptor number of any file which pselect() is waiting on. If this never changes and is known at compile time – use it! Otherwise, you’ll need to search through all the file descriptors you’re waiting on to find the one with the highest number.

Finally … call pselect(). It will block until one of our specified file descriptors becomes ready to read, or ready to write, or our timer signal was received (and handled).

return_status = pselect( max_fd_number+1, &read_fdset, &write_fdset, NULL, NULL, &signal_mask);  // Note: use current signal mask with the timer signal unblocked

Handle the events as they occur

When pselect() returns, if return_status is > 0, it indicates the number of file descriptors which are ready. Check each file descriptor, and if it’s ready – process data as needed:

if (FD_ISSET(serial_io_fd , &read_fdset) {

// process incoming serial data

}

if (FD_ISSET(TCP_client_fd , &write_fdset) {

// check socket status and handle connection acceptation / rejection

}

// and so on for every file descriptor you’re handling …

When pselect() returns with return_status = -1, it indicates an error. Check the errno value, if it’s EINTR, then pselect() was interrupted by a signal – presumably our timer signal! Check the global variable and handle the periodic task processing. This is the Time-triggered Super Loop Cyclic Executive.

if ((return_status == -1) && (errno == EINTR)) { // we caught a signal

if ( gProcess_20ms_task == TRUE ) {  // the 20ms timer signal handler ran

// Check loop delays due to blocking within main loop itself

if ( gCnt_20ms_isr > 1 ) { // was loop processing hung up?

fprintf(stderr, “\n>>> missed %d 20ms loop executions! <<<\n“, cnt_20ms_isr-1);

}

gCnt_20ms_isr = 0;

gProcess_20ms_task = FALSE;   // reset the global variable

counter_40ms_task++;   // Increment the 40ms task execution counter

counter_100ms_task++;   // Increment the 100ms task execution counter

// perform required processing

do_20ms_task();

if (counter_40ms_task == 2) { // 2 x 20ms = 40ms

check_active_comm_port_status();

// … and any other tasks to run every 40ms

counter_40ms_task = 0;

}

if (counter_100ms_task == 5) { // 5 x 20ms = 100ms

update_user_interface();

// … and any other tasks to run every 100ms

counter_100ms_task = 0;

}

// and so on for other periodic tasks …

} // end: 20ms timer signal handler ran

// Check loop delays due to blocked signal

if ( gOverrun_cnt_20ms > 0 ) { //was timer signal blocked?

fprintf(stderr, “\n>>> missed %d 20ms signals! <<<\n“, get_overrun_cnt_20ms());

}

} // end: we caught a signal

} // end while – infinite loop

Notes on handling the events

  • FD_ZERO, FD_SET, and FD_ISSET are all macros designed to simply handle the file descriptor sets used with pselect().
  • All the periodic tasks are handled here: 20ms, 40ms, and 100ms tasks. Some periodic tasks may be used exclusively by one of the file descriptor handling tasks. For example, a communication channel may want to disconnect after several seconds of inactivity and attempt to reconnect. In this case, it’s better to define a specific counter and status flag in the timer signal handler that can later be checked by the file descriptor handling task.

Application and Performance

We used this design to develop a “Slew-to-Cue” system. Oversimplifying a bit, the system receives the location of a drone and automatically moves, or slews, a gun to point at it. This involved interfacing to:

  • Remote Operated Gun Mount
  • Military Radar
  • Command and Control (C2) System
  • Daylight and Infrared Camera

The Radar detects moving objects. These objects are displayed on the C2 system; they become potential targets. Then an Operator selects one of these, the drone target, to send to our Slew-to-Cue system. Our device processes all this information and commands the Gun Mount and the Camera to point at the drone’s position in the sky. This involves some sophisticated mathematics to compensate for parallax and pitch and roll errors, as well as convert latitude, longitude and elevation from the Radar to an azimuth, elevation and range which the Gun Mount uses.

We implemented our system on an ARM-based Single-Board-Computer (SBC) from Technologics Systems (model TS-7250-V2) running Debian Linux. The design uses a single process with SCHED_NORMAL policy to handle all the time-sensitive tasks.  Why handle everything in a single process?

  1. Simpler design and coding – no need for Inter-Process Communication (IPC) such as shared memory, semaphores, mutexes, pipes or message queues.
  2. Much simpler debugging and testing – it’s easy to step through a single process and see what’s going on.

Our system processed the following continuous communication loads simultaneously:

In / OutData Size (bytes)DescriptionComm ChannelFrequency
Receive1904Radar Tracks dataTCP/IP 133ms
Receive41Target Geo-Location dataTCP/IP 233ms
Receive25Platform PositionTCP/IP 233ms
Receive9Camera PositionTCP/IP 233ms
Receive56Gun Mount Status/Position ReportRS422 Serial port20ms
Send56Gun Mount Control/Slew CommandsRS422 Serial port20ms

Table 1 – Real-time Tasks

In addition, many other messages were received / sent as needed to acknowledge commands, request and get status, etc. User Interface I/O was handled as needed, every 100ms.

Some of the performance measurements were qualitative. For example, how closely did the Gun Mount and Camera track the moving target: was it centered in the middle of their respective display screens? This would be a problem if we were unable to process the incoming data streams quickly and effectively. The system performed admirably in all these qualitative aspects.

One real-time requirement could be measured quantitatively. Whenever we received a Gun Mount Status/Position Report, the system must:

  1. process the data
  2. compute the new parameters
  3. send the Gun Mount Control/Slew Commands within 5ms
Gun Mount Serial Communications
Figure 2 – Gun Mount Serial Communications

In Figure 2, the top trace shows the serial message being received by the hardware. The second trace (from the top) shows a “blip” each time our serial interface handler runs. The OS or serial driver buffers several bytes before it indicates data is ready to be read. The “Ready to Read” status change awakens our process from sleep and it handles whatever data has been transmitted. When all 56 bytes of the message have been received, we process the entire message and prepare the Gun Mount Control/Slew Commands message and send it to the serial port interface. At this point, the message is in the hands of the operating system. The bottom trace shows the serial port transmit line actively sending the data 460 µs later. This shows we should have no difficulty in meeting our real-time requirements: we’ve responded in < 2ms, well within the 5ms requirement.

Another Timing Requirement

A second real-time requirement can also be measured quantitively: the 20ms task, and all other processing, must always finish within 20ms – before the next 20ms task is ready to run. We instrumented the code and used a high-resolution system timer to measure how much time our process is “sleeping”, waiting for something to do. Since we wake the process up every 20ms, we measured sleep time during every 20ms loop. On average, our process is sleeping 19.4 ms out of every 20ms. This means its only using 3% of the available processor power, or through-put, when the system is idling: just receiving Gun Mount Status/Position Reports and sending the Gun Mount Control/Slew Commands every 20ms. We pushed the system hard by:
  • sending Radar data for many potential targets simultaneously
  • sending the 3 messages from the C2 system: Target Geo-Location, Platform Position and Camera Position
  • continuously slewing the Gun Mount to follow the target identified by the C2 system
Even then the worst-case sleep time was 12.57 ms, showing we used less than 38% of the processor through-put during our busiest 20ms loop. Although this is not a thorough Worst-Case-Execution-Time analysis, these measurements are sufficient for our soft real-time system and provide great confidence that we’ll never miss a 20ms deadline.  Indeed, since the software logs a message if this ever occurs, and it hasn’t, we’re confident it never will.

Conclusion

This simple design pattern, implemented in a single Linux process, proved itself to be very robust:
  1. Use a timer to trigger the periodic tasks
  2. Open files corresponding to the aperiodic events
  3. Within an infinite loop:
    1. Use pselect() to block until the periodic timer signals or an aperiodic event occurs
    2. Handle the events and run the periodic tasks as needed
The design pattern is easy to understand and easy to extend for other tasks and events, whether they occur on a regular schedule (periodic) or randomly (aperiodic).