Scheduling a Real-Time Program

Some time ago I had the interesting task of working with the International Space Station’s Control and Data Handling group. That group was building the flight code for the Node Control Software. One of my contributions was the manual scheduling of the mission-critical real-time program. Specifically, I needed to allocate calls to the various components of the software at various points in the run time.

To accomplish this task, I needed to know the run-time characteristics of dozens of software components, and the effect on the system as software components were moved from one rate group to another. This juggling act isn’t unusual. Because the system was hand scheduled, and because I was the scheduler, knowing these characteristics was my task in a nutshell.

The difficulty this particular real-time system posed was the almost complete lack of developmental utilities. The system was supported by tools that were deficient in their ability to provide the run-time information needed to schedule, debug, and by modern standards, even write code. Debugging was often carried out through text output. The compiler’s debugger was itself a bit buggy.

Clearly, to schedule this system successfully, I needed a good way to obtain information from the system during run time. I needed a spy. I needed a fly on the wall. I needed a peephole.

So I devised a tattletale .

In this article, I present two solutions to problems that arose in conjunction with my task. The first solution is the means by which I got data out of the system—my tattletale. The second solution is the method by which I displayed the data.

The system in question
The space station Multiplexer-Demultiplexers (MDMs) were originally designed to interface with physical I/O. That is, each MDM consisted of:

• A 12MHz Intel 80386
• 2MB of RAM
• 2MB of EEPROM
• A single MIL-STD-1553 I/O channel to an upper layer controller
• Various low-level inputs and outputs, such as:
  • Relay drivers
  • Digital inputs and outputs
  • Analog inputs and outputs
  • Any other strange interface that a space station would need

For an MDM to have any chance of running space station control software, some features had to be added to the hardware. The largest new feature was the addition of four more MIL-STD-1553 channels of I/O. The upshot of the changes is simple. The MDMs, which had been adequately sized for the job intended, were now woefully underpowered. This meant that there would be few spare processor cycles, and that all of the tasks that were now on the processor would have to be scheduled carefully.

What did I need to know?
The software on the MDMs was to run in one of several rate groups. For the purposes of this article, I present only two of the rate groups: the 80Hz group of 12.5ms period, and the 10Hz group with a period of 100ms. The 12.5ms periods were called subframes, and eight of these subframes made up a 100ms frame. Within a subframe were 16 divisions which marked the transaction time slots for the MIL-STD-1553 buses. Figure 1 shows the frame and subframe timing relationship.

Frame and subframe timing relationship
To schedule a dozen or so user applications, I had to know how often each had to run, the constraints on the applications in terms of execution order, execution deadlines, availability of I/O, and a raft of other details.

When I took all of the requirements and constraints into account, I had to choose in which of the eight subframes different applications would run. Obviously, since each subframe lasted only 12.5ms, I could fill each subframe only to that point. ¹ If any application were still running at the end of the 12.5ms subframe, the subframe would overrun, which might cause the system to crash. Not surprisingly, astronauts do not wish to type Control-Alt-Delete very often on their life support system’s MDM—mainly because MDMs don’t have this feature.

What I really needed to know, as I tried out various scheduling options, was just how much time I was using, subframe by subframe, while the real-time system was in operation. This was problematic because the text output capability of the system was limited to about 1,200 bits per second (bps). I estimated that I needed at least 1,280bps. Uh-oh.

How did we plan to know what was going on?
I wanted to obtain, for each subframe, the amount of time the CPU used for execution of the application code. This information is often called CPU utilization .

I wanted to obtain this information in as transparent a manner as possible, of course. It wouldn’t do to interfere with the timing of the software, and thereby my own measurements. Clearly, I needed to get this data out of the MDM in some economical fashion that didn’t burden the machine, and didn’t use up all what little text output capability was available.

Making timing measurements in an operating processor without incurring any timing penalties is possible, though it naturally comes at a price—a $40,000 price, to be exact.

That expensive method is to use an in-circuit emulator (ICE). The ICE is hardware that uses a probe placed between the processor chip and the processor’s socket. The ICE uses fast circuits to monitor and modify the signals that pass between the motherboard and the CPU. In most cases, this can be done without any significant timing penalties whatsoever. (Well, you should get something for $40,000.)

Would you feel a bit nervous about this approach? You should. It requires that (a) the processor be opened up, (b) the CPU removed, (c) a bulky, delicate, cranky, and expensive probe be inserted, and (d) the whole thing protected from the night cleaning crew while you try to use it. ²

Nevertheless, an ICE is so powerful a tool that in early development stages, particularly when the hardware and software are first introduced to each other, it can be well worth the cost and trouble, if not an absolute lifesaver. We had a few ICE boxes, but they were antiques, modified for the MDMs, and not much fun to use. They didn’t understand our linker’s symbol table, so we were forced to shout at the boxes in hexadecimal. To be honest, only the more hardware-oriented developers really wanted anything to do with these machines, and even then, it wasn’t fun.

The alternative to an ICE is to use software techniques. The MDM software already incorporated a set of timers and utility calls that allowed me to make the basic measurements subframe by subframe. I determined, using the ICE for a sanity check, that my “intrusion” into the timing of the system was under 0.25ms for an entire 100ms frame. I judged this to be acceptable.

I set up some calls to the system timers. I stored my timing information in a small array that consisted of a set of 16-bit integers, representing the number of milliseconds used in each of the eight subframes. That wasn’t so hard.

The hard part was to come. How, in a system devoid of ordinary I/O, would I get these eight words out of the box every 100ms?

Sneaking the data out the side door
You’ll recall that I mentioned that the MDMs now had a total of five MIL-STD-1553 buses. MIL-STD-1553 buses are quite interesting—I’ve published an article on their simulation—but I’ll cut to the chase. ³

A MIL-STD-1553 bus is an elaborate command-and-response implementation of time domain multiplexed communication. This means that it is rather like a conveyor belt, moving packets of a small maximum size at a fixed rate to predetermined destinations. MIL-STD-1553 buses are neither fast (less than 750kbits per second) nor versatile, but they are robust, hence well-suited to command and control applications. They are found primarily on military and mission-critical systems.

On a MIL-STD-1553 bus, a central bus controller (BC) repeatedly issues a command and possibly a data packet to one of 32 remote terminals (RTs). The RT responds immediately with a status response, and possibly a data response. Data packets are limited to 32 words of 16 bits each.

Each RT is further subdivided into 32 subaddresses, so that the BC may address one of 32 subaddresses on one of 32 RTs during each command and response transaction. ⁴

Most of the applications on the MDM were concerned with moving data on and off these buses. Consequently, the buses were pretty tightly filled. However, a few holes were left, if you knew where to look.

I knew where to look, because I’d written one of the first working prototypes of the code that handled the five MIL-STD-1553 buses.

I “appropriated” a particular RT’s address and one of its subaddresses. I knew that this particular RT address would not be used by any other device on the bus. This particular RT was polled (you guessed it) every 100ms. My eight timing numbers for the previous frame fit in the poll quite nicely, taking only half the data packet.

In short, I collected the timing for each of eight subframes in a buffer. When the frame was over, I passed the eight 16-bit words directly to the memory locations due to be sent out over the MIL-STD-1553 bus. Whoosh! Data away!

That was my tattletale. A constant whispering stream of information on the 80Hz and 10Hz rate groups. Low overhead in the code, and the use of unused bandwidth on the bus.

Catching (and cache-ing) the data
Okay, the data were streaming out of the box in real time. What to do with it all?

Well, it turns out that to see anything on a MIL-STD-1553 bus, you need a MIL-STD-1553 bus analyzer. These are always expensive, ⁵ and often miserably difficult to use. However, we were lucky to have at our disposal SBS PASS-1000 analyzers, which are well designed and a pleasure to use. ⁶ These analyzers could capture my data and display it in a reasonably understandable format. That’s exactly what I did at first.

As I began to use the data on the CPU utilization of the subframes, I became more dependent on the information. As good as the PASS-1000 was, I still had to reserve it, set it up, and consult its screen, or look at the history trace of my data.

After discussing this with my associates, someone pointed out that an RT interface card was available for a few of our Unix boxes. We began to use this card to capture the timing data emitted by the MDM. This approach worked pretty well because I could capture seconds and minutes of run time, instead of just a few samples from the PASS-1000 display screen.

The only drawback was that the data were presented in eight columns, with as many rows as I might care to capture, one row per 100ms frame. This layout wasn’t too bad, but I realized that a better way to display and interpret the data existed.

Making the data make sense
Columns of data extending for hundreds of rows aren’t usually easy to interpret, but the array form of the data suggested Matlab to me. It might as well have suggested a new 1999 Lexus, since I had neither a Lexus nor Matlab at my disposal. (We didn’t have a decent compiler, to my mind.) My next thought was my 1984 Jeep Cherokee—that is to say, Excel. And indeed, like my Cherokee, Excel fit the bill.

On the Unix machine I’d captured my timing data as a large text file. I transferred the text file to an Excel spreadsheet. Table 1 displays a typical 1s run.

The rows of the table represent a single frame of 100ms. Within the row, the frame is broken into the CPU execution times of each of its eight subframes. The columns therefore present the time history of a particular subframe.

I normally collected 100 to 200 seconds of data, which resulted in tables with 1,000 to 2,000 rows. The software’s largest period was 10s, but there were variations between the 10s periods as well.

You can see that my sample tabular data isn’t very interesting, except that it indicates that the timing is below the 8,000µs requirement. ⁷ Other features of the data, if they exist, are lost in the rows and columns.

I wanted a better way to look at the data. I made some graphs of the CPU execution times vs. real time, and immediately saw that the data was periodic. Of course I had known all along that this had to be true, but the graphs underscored it.

Once I realized that the data was periodic, the solution to the data display problem came to me clearly. I needed a graph which worked well with periodic data.

One such graph is called a radar plot . Mine is shown in Figure 2 . On the radar plot you can see various interesting features that are otherwise lost in the data:

• The timing is largest in subframes 3 and 5. There was a good reason for this, and it confirmed my intuition about something happening on one of the buses
• The subframes have some execution “jitter” from frame to frame. I investigated these jitters, and found (mostly) good reasons for them
• Subframe 4 had considerable jitter. Investigation revealed a program fault

I believe the nicest thing about the radar plot is that it’s a good graphical representation of the tabular data. Repetitive features are overlaid, but differences are visible. Several features are obvious at a glance, and it gives a good feel for the execution behavior of the system.

No, they don’t use this method, but you may
That I obtained my data using a specialized bus isn’t really all that important. Most systems will not have MIL-STD-1553 buses, but will have other communication channels. To get the information you need, you may have to investigate the channels that are available, and find some spare bandwidth to “borrow.”

What is important is selecting the presentation method for your data. This selection can be crucial to making the data useful. I stumbled upon a very good method for displaying execution data, and I hope that it’s one that’s useful sometime to you in your work.

I wish I could claim that our client recognized my effort as an important and technically astute innovation from my company, but I can’t. Regrettably, when I was moved from the scheduling task to a new task, my tattletale was abandoned. And shortly after that, the small amount of code that I introduced into the run time for the tattletale was removed.

I’m not surprised that my tattletale wasn’t used by the people who took the scheduling task over from me. At that point the scheduling was almost completed, and only fine-tuning remained. However, I would have left the tattletale code in the flight code. It didn’t use a significant amount of system resources, and certainly didn’t use any part of the MIL-STD-1553 bus that was needed elsewhere. The tattletale could have whispered on and on, until some time that it might have been needed. But from a program management perspective, such code could not be permitted to remain in flight code controlled by formal specifications and subject to rigorous verification.

I thought I’d share this technique with you, since it required little in the way of system resources, very little effort to set up, and provided insight into the timing operation of the 80Hz and 10Hz rate groups. The data presentation method, while not rocket science, can be quite useful.

Bob Lacovara holds a Master’s degree in electrical engineering and a PhD in computer science. He has designed embedded systems and related hardware since 1974, first as a consultant, then as the owner of a small business. He currently works at Draper Laboratory on control interactions between components of the International Space Station.

Endnotes

1. In reality, a requirement allocated only 65% of the 12.5ms period for use by all the 80Hz tasks in a particular subframe.
2. We used sawhorses, signs, crime-scene tape, and flags to try to keep people away from the jury-rig.
3. Lacovara, R. C., “Application of a New Simulation Tool to a Command and Control Subsystem of Space Station Freedom,” Proceedings of the 1993 Summer Computer Simulation Conference , Boston, MA.
4. The process is certainly a little more complex than this, so my apologies to the MIL-STD-1553 experts who might be reading this article.
5. Were you surprised?
6. Honest. The PASS-1000 is a first-rate analyzer: easy to use, powerful, and versatile. To my mind, they are the first choice in MIL-STD-1553 analyzers.
7. The actual requirement was that no subframe was used beyond 65% of 12.5ms, or 8,125µs. I used 8,000µs as a round number, and considered the “leftover” 125µs as mine to play with as I chose. I didn’t tell my managers about this.

Table 1 Execution time raw data, in microseconds, for subframes 1 through 8 SF 1 SF 2 SF 3 SF 4 SF 5 SF 6 SF 7 SF 8 4322 6214 7633 3396 7580 5478 5248 2874 4412 6214 7632 3396 7579 5478 5910 2874 4003 6214 7635 3122 7582 5479 5248 2874 4322 6214 7635 3396 7582 5479 5910 2874 4412 6214 7635 1423 7582 5478 5248 2874 4003 6214 7633 3396 7580 5478 5910 2874 4322 6214 7632 3396 7579 5478 5248 2874 4412 6214 7635 3122 7582 5479 5910 2874 4003 6214 7635 3396 7582 5479 5248 2874 4322 6214 7635 1423 7582 5478 5910 2874