This entry is part 3 of 3 in the series RTOS Alternatives.
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | typedef enum { LIGHT_RED, LIGHT_RED_AMBER, LIGHT_GREEN, LIGHT_AMBER } traffic_light_state; // Event triggered RTOS version. void Traffic_Light_Controller(void *parameters) { while (1) { Set_Lights(LIGHT_RED); Delay(15000); // wait 15 seconds Set_Lights(LIGHT_RED_AMBER); Delay(2000); // wait 2 seconds Set_Lights(LIGHT_GREEN); Delay(15000); Set_Lights(LIGHT_AMBER); Delay(2000); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // Called once per second by the scheduler. void Traffic_Light_Update(void) { // Initial values that immediately change to LIGHT_RED. static traffic_light_state current_state = LIGHT_AMBER; static int32_t time_left = 1; if (--time_left > 0) { return; // Not ready for a state change yet. } switch (current_state) { case LIGHT_RED : current_state = LIGHT_RED_AMBER; time_left = 2; break; // And so on for the other states... } Set_Lights(current_state); } |
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:
- which state it transitions to; and
- 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:
1 2 3 4 5 6 7 8 9 10 11 | typedef struct { traffic_light_state next_state; int32_t state_time; } traffic_light_type; static const traffic_light_type state_table[] = { { .next_state = LIGHT_RED_AMBER, .state_time = 15 }, { .next_state = LIGHT_GREEN, .state_time = 2 }, { .next_state = LIGHT_AMBER, .state_time = 15 }, { .next_state = LIGHT_RED, .state_time = 2 } }; |
With the above table in hand, writing the actual task function is now a trivial exercise:
1 2 3 4 5 6 7 8 9 10 11 12 | // Called once per second by the scheduler. void Traffic_Light_Update(void) { // Initial values that immediately change to LIGHT_RED. static traffic_light_state current_state = LIGHT_AMBER; static int32_t time_left = 1; if (--time_left <= 0) { current_state = state_table[current_state].next_state; time_left = state_table[current_state].state_time; Set_Lights(current_state); } } |
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:
- We can add the data for individual lights to the state table and use it to call all three of the light-setting functions.
- 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | typedef struct { uint32_t (*transition)(void); int32_t time; } state_type; // Call this periodically to execute a state machine. void State_Update(const state_type *states, int32_t *current_time, uint32_t *current_state) { assert(states != NULL); assert(current_time != NULL); assert(current_state != NULL); if (--*current_time <= 0) { *current_time = states[*current_state].time; *current_state = states[*current_state].transition(); } } |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | uint32_t Enter_Red_State(void) { Set_Red_Light(TRUE); Set_Amber_Light(FALSE); Set_Green_Light(FALSE); // Return the next state to transition to. return LIGHT_RED_AMBER; } static const state_type state_table[] = { { .transition = Enter_Red_State, .time = 15 }, // ... the other states go here. }; void Traffic_Light_Update(void) { // Initial values that immediately change to LIGHT_RED. static traffic_light_state current_state = LIGHT_AMBER; static int32_t time_left = 1; State_Update(state_table, ¤t_time, ¤t_state); } |
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.
Tags: C++, Embedded Systems, RTOS, Software