In an earlier article we looked at the design and implementation of a time-triggered scheduler, but we didn’t consider the implications of actually using it. This can take some getting used to if you have never used such a system before. Imagine that we wanted to create a simple traffic light system… in a more traditional event-triggered design, it might look something like this:

In a typical RTOS, calling the Delay function will cause the task to become blocked for the given duration (it is often hard to tell from the documentation if the delay is up to or at least the value — I have seen both). Blocking a task involves removing it from the list of tasks that the scheduler can execute (the ready list) and using a context switch to resume another task instead. Obviously this functionality is not available in our simple scheduler, as we do not have the ability to save and restore contexts (which generally requires platform-specific assembly code).

If we cannot block tasks, actually implementing a delay will involve spinning — sitting in an empty loop for the specified amount of time. This prevents any other task from running for that time, which in this example is up to 15 seconds! Obviously with other tasks in the system, this would not be acceptable — between the delays and the infinite loop they would never get to run. One alternative is to use a Finite State Machine (FSM).

Switch-Based Finite State Machines

In C, state machines are often implemented with a switch statement. We just store the current state in a variable and switch on it every time the task function is called, updating the state variable whenever the state must change. In practice, this means setting the task period to something sensible and using a counter to determine if it is time to change state, which can be implemented as follows:

The code above is quite simple and a switch statement works well for an FSM with few states, but even in this case — with all the states filled in — it is quite excessive when compared to the original blocking version. A common way to reduce the amount of code we need to write is to use a table-based implementation.

Table-Based Finite State Machines

The state machine shown above is mostly concerned with data — the actual functionality of the state is carried out by the call to Set_Lights on each transition; this is the same for every state, so all we really need to concern ourselves with is the nature of the states themselves. For each state, we need to know:

1. which state it transitions to; and
2. how long it remains in the state.

This information can be wrapped up in a structure and stored in an array, indexed by the enumeration that we defined earlier:

With the above table in hand, writing the actual task function is now a trivial exercise:

That is much less code than the switch example for a data-driven and time-triggered state machine, but this only works here because we have the Set_Lights function that takes the current state as a parameter. How might this work if we had to use, say, a separate function for each light (Set_Red_Light, Set_Amber_Light and Set_Green_Light)?

In the RTOS example at the beginning of this article, it would be easy — I can just call the functions as needed. For the switch-based state machine it is equally easy, but still results in a lot of excess boilerplate for state transitions and the switch itself. Can it be done with a table-based approach? I can think of at least two ways, off the top of my head:

1. We can add the data for individual lights to the state table and use it to call all three of the light-setting functions.
2. We can include a function pointer in the state table and call it to carry out the state’s operation.

The first method is less work, but also less interesting. The second method is far more generic — you could write any time-triggered state machine with just a function pointer, an index to the next state and a time value in the structure. That means that both the structure and the state changing code could be reused as necessary… in fact, you don’t even need the next state information if the function can return it:

You might be wondering why I bothered with all the assertions this time, when I left them out of the previous examples. The answer is simply that this is a generic function that may be reused months or years down the line — it’s helpful both to check the parameters for correctness and as informal documentation of the function’s preconditions.

I also made the first parameter const, which is always useful but which I rarely bother with in examples like this. I did it this time because the array that we pass in will probably be declared as static const and I wanted to avoid casting that ‘const-ness’ away… your compiler will almost certainly issue a warning if this is left out anyway.

As a side note: declaring an array as static const is the best way to ensure that the compiler and linker place it in a read-only memory section, which is very helpful in embedded systems where it will be placed into flash memory and kept out of our more limited (and therefore precious) RAM.

Using the generic state machine code is now quite simple:

This allows us to easily split up our state transition code into separate functions, with just the state table and a simple three line function as overhead. The design is as capable as the switch-based approach, but without the messy boilerplate code that can easily get mixed in with the actual state operations. Of course, we still haven’t reached the level of simplicity shown in the RTOS example — I know of at least one method of achieving such simplicity without platform-specific context switching, but this article is already too long, so I’ll leave it for another time.

In this article we discussed a few different approaches to implementing time delays without blocking; next time, I will be looking at how to handle tasks with long execution times that hog the CPU.

Last time, I looked at some of the simplest alternatives to using a Real-Time Operating System. The problem is, as soon as you need both accurate timing and prioritised tasks, you are out of luck — a foreground/background system would need a separate interrupt source per task priority, which can bring its own problems to the table:

In order to meet our requirements and avoid these issues, we really need a scheduler… luckily, they aren’t too hard to write. The simplest of all schedulers is the Time-Triggered Co-operative (TTC) scheduler, in which tasks are released by a single timer interrupt (hitting the green ‘sweet spot’ on the above graph). This differs from foreground/background scheduling in that tasks are actually executed from the main function and not from the interrupt handler itself.

Time-Triggered Systems

Before delving into the scheduler implementation, it’s probably worth taking a short detour through time-triggered systems. If you’re not familiar with them, they are a subset of the more widely used event-driven programming technique. The difference is that the only ‘events’ we are allowed to use are those whose timing is known in advance. This typically means just having one timer interrupt as the event source — which, as some will already have guessed — often leads to a technique known as polling.

Polling has a poor reputation in most software development circles, and for good reason. As soon as you start polling on more than a few frequent (but aperiodic) events, the time taken to continually check for the event can be costly in terms of processor utilisation. Then there’s the problem of long tasks, which — in a co-operatively scheduled system — can delay polling activities and potentially cause events to be missed.

Despite these issues, the idea of knowing exactly what your system is doing at any given instant is very compelling. So, in this article we will look at building a co-operative scheduler and in future articles we will look at ways of coping with the shortcomings of this approach. Perhaps in time I might even get as far as writing about pre-emptive schedulers!

The Anatomy of a Task

For systems written in C, a task is usually represented as a function. The average RTOS will not allow the task function to return, instead forcing us to wrap the code in an infinite loop. Having the task perform operations periodically — as in a time-triggered system — is done by calling blocking functions provided by the RTOS, similar to the following:

Notice how similar this is to the super loop example from last time? It suffers from many of the same problems too, but we won’t get into that now. Instead, let’s look at a roughly equivalent task for a time-triggered, co-operative scheduler:

Notice that the function is allowed to return, and that we specify a period and delay for the task. The scheduler will be responsible for calling the task function at the appropriate times — we do not control this inside the task itself. Note also that the task function is called directly without context switching, and so does not require a stack of its own.

The scheduler implementation will need a data structure to store this information; to keep things simple, we can use the following:

The above structure is effectively minimal for a time-triggered scheduler, containing just the function pointer and timing data needed to call the task at the appropriate times. Note that the implementation is easiest if the period and delay are in units of ‘ticks’, which correspond to a (single) periodically repeating timer interrupt.

Implementing a Simple Scheduler

Time is obviously going to be the most important factor in a time-triggered system. To build the scheduler, we will need — as a minimum — the ability to configure a hardware timer such that it generates an interrupt at the desired frequency. This is platform dependent and I will not go into detail here — see the datasheet or user manuals for your architecture for more information.

In the terminology introduced last time, all tasks in our co-operative scheduler are going to be ‘background’ tasks. In other words, the interrupt handler is not responsible for actually running tasks; instead it will just keep track of time for us:

It’s that simple — all the real work will be done outside of the ISR, in a dispatcher that can be called over and over again from the main function. All we really need to do is wait until the elapsed_ticks variable is greater than zero, then decrement the delay of every task and execute any that reach zero. The task’s delay variable can then be reloaded with the period.

Note that the elapsed_ticks variable must be made volatile, as it is accessed both inside and outside of an ISR. This is not to ensure atomic access — which is good, because it doesn’t — but instead prevents some potentially harmful compiler optimisations (however unlikely). We must take further steps to ensure atomic access, and in this case I have opted for a heavy handed application of disabled interrupts:

Reading the above code, you might notice that the first call to the dispatcher will (probably) jump past the outer loop and exit almost immediately. This is not a disaster — if the function is called repeatedly as intended then it will still operate correctly — but it is not ideal.

Initialisation and Usage

We can improve efficiency by making use of the microcontroller’s idle mode:

Line 13 effectively puts the microcontroller to sleep until the next interrupt occurs; once again, this function is highly architecture-dependent and you will have to write it yourself. The trouble with using idle mode is what happens when an interrupt occurs immediately before this line is reached — the elapsed_ticks variable will still be incremented, but the dispatcher will not run until the following tick (i.e. one tick will be ‘missed’).

We can assume that the timer interrupt will not fire between lines 9 and 13 above, but there is still the possibility of this happening between the end of Dispatch_Tasks and entering idle mode. Actually, there is another problem with this code — the dispatcher decrements the delay before testing it and we are setting the initial delay to zero, so how do we avoid underflow (or subtraction overflow if you prefer)?

That’s it for the implementation… let’s take a look at how it works with the two-task example from last time:

So, we now have access to priorities — based on the order of the task array — as well as a simple way of getting accurate timing. Next time, we’ll look at some of the problems inherent in both co-operative and time-triggered schedulers and some ways of working around them.

As microcontrollers increase in speed and capacity, it’s becoming much more tempting to simply fit a full Real-Time Operating System (RTOS) into a design, without considering other options. This is a shame, because over time a number of alternatives have been developed that can be simple and effective. In this series, I will be discussing some of these, starting with the very simplest — the super loop.

Super Loops

Without an operating system to fall back on, the application is responsible for executing any tasks that must run. The easiest way to do this is just to keep calling task functions repeatedly in an infinite (super) loop:

Note that we need an infinite loop in the main function because there is no OS to return to.

The solution above has the advantage of utter simplicity; it will run the two tasks, one after the other, as fast as they can be run. The disadvantages are that there will be no pre-emption and no accuracy to the timing of the tasks.

Timing can be an important issue for many tasks, such as debouncing a button press, sampling data from an ADC, or executing a control algorithm. These tasks are usually required to run with a fixed period, which we might be able to accomplish in a super loop. Suppose we want to run the tasks above every ten milliseconds, with five milliseconds between them:

This might work as described, but only if the two tasks are extremely short. The problem here is the delay can only begin after the associated task has finished. If the tasks each had a constant Worst-Case Execution Time (WCET), then we could simply reduce the delay values appropriately, but this is exceptionally rare and not very practical (any change to the tasks or optimisation settings could invalidate the delay). The problem is shown here, where we assume that both tasks take around two milliseconds to complete:

Clearly we don’t want the task’s period to be tied to its execution time. If the problem is that the delay only starts after the task finishes, can we find a way to start it before the task runs? A sandwich delay does precisely that.

Sandwich Delays

The goal of a sandwich delay is to achieve a delay that is constant from the beginning of the task. The delay function used previously started a timer and looped until the desired time had passed; this time, we can simply try starting the timer before the task runs:

It should be obvious where the name comes from — the task is sandwiched by the two delay calls. The timing behaviour is also greatly improved, now providing the ten millisecond periods that we were looking for:

We have the periodic behaviour that we were looking for, but what about the lack of pre-emption? I will address this point at length later in the series, but for now consider what happens if some of our tasks are very long and others are very frequent. In the example above, what if we also needed a task run every millisecond at a higher priority (e.g. to acquire a sample from an ADC)?

A simple sandwich delay cannot provide this behaviour. In fact, we have no support for higher priorities at all; this is where foreground/background scheduling comes into play.

Foreground/Background Scheduling

Foreground/background scheduling is simply the practice of using interrupt handlers to carry out the most important work in your system. Tasks run from the super loop in the main function become the background tasks, while the interrupt handlers become the foreground (higher priority) tasks:

In the above example, we still have both of our tasks — which now run in the ‘background’. In the foreground we have added a new task that retrieves a sample from an ADC, which should run every millisecond. Because the new task is actually triggered directly in an interrupt handler, it has the ability to pre-empt any background task:

So now we have two priorities and some pre-emption going on. It’s possible to have more than two priorities if you have other interrupts and associated handlers; many systems can do nesting and prioritisation of interrupt handlers. That doesn’t make it a good idea! Having many different interrupt sources just doesn’t scale well — in my experience, predictability drops off rapidly with each additional source beyond the basic system tick timer.

What we really want is a way to get prioritisation and accurate timing for background tasks as well, ideally without sacrificing predictability, simplicity, performance or memory usage in the process. We can do this — easily — with a simple scheduler, which is the topic of the next article in this series.

Time. Quality. Features. It’s usually described as a triangle, which somehow represents the state of your product or your feature. I believe the idea is that in a perfect and unattainable world, this triangle is perfect, equilateral, and seemingly at rest. There is balance among the time you have to release, the quality you are seeking to attain, and the features you want to ship.

In reality, this triangle is never at rest. It’s constantly shifting and, well, I don’t think it’s actually a triangle. It’s just a mental model that gives you just enough ammunition to lie.

The whole article is worth reading — I like the concept of “Bits”, “Features” and “Truth” as roles for certain people on the team. It seems more approachable than the traditional engineering manager, product manager and program manager titles.

“I’m the Bits” does sound wrong, though.

Most projects have some kind of standard source code template which has the copyright and license text and placeholders for things like a description. All I have to say is: You don’t need a template. Stop using it.

He’s referring to things like this, found at the top of most source-code files:

Actually, that one’s fairly trivial — see the actual post for a much worse example. His post actually seems to be about file-level comments, rather than comment templates, but it’s still worth a read.

As a distributed version control system, Mercurial allows us to push and pull changes between any two repositories in an ad hoc manner. In reality, most projects can benefit from a central server (even if it’s just a repository on the lead developer’s machine) — somewhere accessible to keep an authoritative copy of the project.

In this article, I’ll look at one way to work with a remote central repository in order to share code with other developers.

Last time, Joe managed to create and merge branches for both his cutting-edge development and the bug fixes he made to the released software. But what about his colleague, Dan? He’s going to need a copy of Joe’s changes and he’s going to need to share some changes of his own. As mentioned in the introduction, Joe can use the push command to send his changes to a remote repository… except we don’t have one yet.

To create a new repository, Joe can use the init command with a parameter indicating the working directory (or none for the current directory). To add files to a new repository, Joe will add them to the working directory and then use the add command to tell the repository about their existence (without parameters, this will add all files in the working directory and recurse through all subdirectories). This can all be done on a remote server over SSH.

Mercurial can push from one local repository to another, or to a remote repository through SSH, HTTP or even to a shared drive. It even comes with a built-in standalone web-server for ad hoc sharing. Whichever method is used, the push command will allow Joe to add his changes from last time into the repository on the central server. Dan can get a copy of the repository on his computer by cloning the server’s copy.

Now they both have up-to-date copies of the repository, Joe and Dan can start making changes simultaneously. If Joe finishes first and pushes his changes, what will happen when Dan tries to do the same? Simply put, he won’t be able to. Mercurial will complain that the push will create multiple heads — which would effectively be two anonymous branches.

On encountering this error, Dan can pull Joe’s changes into his own repository, creating the multiple heads there instead. Dan could follow the steps from last time and merge the heads before committing and pushing the merge changeset. From what I can tell, this is usually the recommended approach in Mercurial; I don’t like it because it results in littering the central repository’s history with useless commit messages from merge operations.

The alternative approach, which is often used in that other version control system, is to rebase the local changes on top of the ones we have just pulled in. This is actually a multi-step process that first copies the changesets from one head onto the other (this actually works by merging), then deletes the old changesets (indeed, the entire anonymous branch):

Generally, this approach goes against the Mercurial philosophy that the history should be immutable (to avoid losing data), but it is just so much cleaner than the alternative of having merge-commits all over the place. If every developer follows this workflow, then the only time we will see merges should be when working with named release branches, which is useful.

There is one small problem here though: do not rebase changes that have already been pushed. If you do, you only delete the old changes locally and other repositories may end up having two copies of your changesets. This can get messy and should therefore be avoided — I recommend a simple “pull, rebase, push” workflow only for local changes to avoid this kind of mess. Note also that in Mercurial, rebasing is done by an extension that must be enabled before we can use it. See the documentation for details.

That’s it for this time. So far the workflow I’ve discussed is mainly suitable for small-scale projects; next time I’ll look at how we can scale things up to larger projects with more developers. Meanwhile, here’s a quick summary of the new Mercurial commands used in this article:

Programmers (especially those coming from C) can very quickly get up to speed in C++ and feel quite proficient. These programmers will tell you that they know C++. They are lying. As a programmer continues in C++, he goes through this valley of frustration where he fully comes to terms with the full complexity of the language.

Very true, and worth a look just for the diagram.

The Ogg container format is being promoted by the Xiph Foundation for use with its Vorbis and Theora codecs. Unfortunately, a number of technical shortcomings in the format render it ill-suited to most, if not all, use cases.

I have no idea how accurate the article is, but it was certainly refreshing.

As I discussed previously there are many possible workflows to use with Mercurial; I will only be looking at some very specific scenarios. For example, it’s often the case that we want to separate work being done on cutting edge development from bug-fixes that get applied to the latest stable release. This is often done with branching — you have a main development branch and a separate branch for every significant release.

As with everything else, there are many ways to branch in Mercurial. I’ll start in this article by looking specifically at the use of named branches.

Remember Joe from last time? Let’s take a closer look at his repository:

Joe has made and committed some changes to the local repository; on the right we can see his changesets, each representing a set of changes that were committed together. Changesets in Mercurial have two identifiers — the small number on the left is a local identifier that is only valid within the repository. On the right is a global identifier that may be used across different repositories.

The current state of the working directory can be thought of as a potential changeset. It doesn’t yet exist in the repository or have an identifier of its own, but it could if it were committed immediately.

Suppose Joe had released the version at changeset 0 as his first major release. If a user has a problem with this release, it’s useful to be able to get back to the exact version that they were using and fix the bug there. To do this, Joe can tag the exact version that he released and use a branch for any ongoing bug-fixes. First, he must update his working directory to the relevant version:

Tags are stored in a file inside the repository that is itself kept under version control, so using the tag command also results in a commit. By contrast, the branch command provides a branch name for the next commit, which is why Joe used it first — to put the tag on the release’s branch.

So if Joe had to make some bug-fixes to the released version at this point, he could update to the tagged revision, make his changes and commit them back to the repository:

Joe’s working directory is still based on the bug-fix to the first release. But this commit was built on top of the new branch, so what does Joe’s repository look like now? Something like this:

Now that Joe has a branch for the first release of his product, how can he get those bug fixes back into the development branch? The answer is merging, where one branch is merged into another. The main branch that we use for development is called default, so first Joe must update to it and then he simply merges in all changes from the stable branch:

If there are conflicts during the merge, then Joe will need to resolve them manually. Usually this is a simple task of editing the file to include only the desired changes, but a graphical diff tool can make this task even easier. Joe uses the resolve command (with the -m and -a options) to indicate to Mercurial that all the conflicts have been resolved successfully.

Finally, as the merge is itself a change, it must be committed to the repository. Joe’s repository will now look like this:

Using named branches and tags like this works very well for tracking and managing releases. I would strongly recommend using one named branch for each major stable release, then tagging at every minor release. It’s then trivial to use Mercurial’s update command to switch the working directory to the head of any given branch.

That’s it for now; next time I’ll be looking at how we can deal with remote repositories and how to avoid littering our history with merges. Here’s a quick summary of the new Mercurial commands used in this article:

When a threat from incoming fire is detected by the vehicle, the energy stored in the supercapacitor can be rapidly dumped onto the metal plating on the outside of the vehicle, producing a strong electromagnetic field.

Polarise the hull plating?