Electronic Design

EiED Online>> Single-Stack RTOS

Single-stack operating systems are small and fast but most programmers are unfamiliar with them. They must be matched to the desired application. See how they work and where to use them.

Most embedded developers are familiar with interrupt driven, multitasking operating systems that provide a stack area for each task but I think most developers will be unaware of single-stack operating systems. A single-stack operating system typically uses less memory and it is well suited for microcontrollers that implement their stack in hardware.

Single-stack operating systems are not for all applications, especially where tasks are relatively independent and potentially complex such as a web server. Single-stack operating systems do fit well in control and digital signal processing applications where tasks are well defined and often where timing is critical. This may seem a bit confusing, as single-stack operating systems are non-preemptive. But time critical does not necessary mean minimum latency, especially when interrupt handlers can provide low-latency response time.

Although less common, commercial versions of single-stack operating systems are available. Quadros RTXCss is one product that employs a single-stack architecture. It can use the same operating system support as Quadros' other RTOS implementations. This includes features such as intertask communication and synchronization, memory management, and other kernel oriented functions.

The Quadros RTXCdm operating system mixes single-stack and multiple-stack operating systems. In this case, one of the stacks is reserved for the single-stack operating system tasks. As it turns out, the single-stack operating system is the highest priority thread in the multiple-stack environment. This approach is not a requirement when mixing a single-stack operating system with a multiple-stack operating system but it is the case with the Quadros product. In fact, it is architecturally possible to have single-stack tasks grouped by stacks where each of these threads manages a set of tasks. Of course, the operating system must take this into account when implementing kernel services.

OSEK/VDX is an open system definition for automotive electronics. It includes a single-stack definition as one of its many specifications. There are a number of commercial OSEK operating systems available.

Why Use A Single-Stack RTOS?
Low RAM requirements often make a single-stack RTOS the right choice. The primary memory savings is in stack memory usage. Applications will still need to allocate memory for buffers and other structures. The use of a single-stack RTOS will not change these requirements. On the other hand, an application's stack must support interrupt routines as well as the maximum amount of stack space required by an application. In a single-stack RTOS, the task that will use the largest stack sets the amount of memory.

Low ROM requirements can be an issue with respect to the operating system footprint. A single-stack implementation can be smaller because synchronization issues are simpler. A multiple-stack operating system must make sure task switches occur properly, including proper support for task synchronization primitives that often require disabling interrupts for a small period of time.

Low overhead and low interrupt latency for operating system services is one benefit of using single-stack operating systems again because of the simple implementation of task synchronization primitives. Interrupts typically are not disabled at any time because a task switch only occurs under very specific conditions that cannot conflict with synchronization primitive changes.

Time critical, deterministic system design is possible with a single-stack approach, although one must keep its limitations in mind. Because of how the tasks operate, it is usually possible to determine the maximum amount of time that a task will be active. Likewise, it is possible to determine the maximum number of tasks that will be runnable at one time and thereby determine the maximum cycle time for the system. A single-stack operating system can be used as long as the application can handle this cycle time. This often requires interrupt latency critical functions to be handled in interrupt routines instead of enabling a high-priority task to do the work.

Hardware stack support almost demands some form of single-stack support because it is not possible to switch between stacks. Some small systems implement a software stack but this type of interpretation incurs both register and execution overhead. Hardware stacks tend to be found in 8-bit and some 16-bit microcontrollers.

Conceptually simple, static systems lend themselves to single-stack operating systems. These often occur in embedded applications. Multiple-stack systems provide a better environment where tasks can be added arbitrarily to a system.

Simple schedulers are common in single-stack operating systems. It is also relatively easy to implement different schedulers without having to contend with major operating system redesign. Multiple-stack operating systems schedulers tend to be much more difficult to implement and qualify.

On the other hand, single-stack operating systems are obviously not suitable for a number of applications. Otherwise their use would be more common. Tasks can have priorities in a single operating system but they only control when a task is runnable. Enabling a higher priority task does not allow the higher priority task to run until the current task finishes its work. In some environments, this may not be desirable.

How A Single-Stack Operating System Works
Programmers that have dealt with embedded microcontrollers without an operating system have probably implemented their own simple single-stack operating system. It could look as simple as the following code:

	void main () \{
		for (;;) \{
			try () \{
			task1();
				task2();
				task3();
			\}
catch ( exception e )
\{\}
		\}
	\}

The stack usage includes the minimal operating system support and each task/function uses the stack as necessary and returns upon completion (Fig. 1). Of course, this assumes that all tasks run each cycle. A more dynamic implementation such as the following employs a scheduler that allows tasks to wait on semaphores or other interprocess communication primitives.

void main () \{
		for (;;) \{
			try () \{
			scheduler();
			\}
catch ( exception e )
\{\}
		\}
	\}

This approach allows a more arbitrary execution graph (Fig. 2). There are a variety of simple ways to implement a scheduler. The scheduler does not have to worry about being interrupted by another task and execution is simply a matter of calling the appropriate function. This might be accomplished via a table or list of function pointers. Some very basic 8-bit microcontrollers may not be able to do this. In the latter case, a scheduler could use a task dispatch function such as the following:

void dispatch (int n) \{
		switch (n) \{
		case 1: task1();break;
		case 2: task2();break;
		case 3: task3();break;
	\}
	\}

Of course, the task functions must be predefined. However, this is a minor issue for an embedded system where tasks are rarely downloaded for execution.

Programming Differences
Programmers will notice a couple of differences when dealing with a single-stack operating system. Task creation is different. Sometimes it requires defining a dispatch function or table and there is obviously no stack allocation required. Also, more complex tasks are typically implemented using a state machine approach. Remember, you cannot simply wait on a semaphore and continue executing after the wait function returns as in a multiple-stack operating system. Instead, a state will typically perform some operations, call an operating system primitive to setup the task to be restarted when an event occurs, and then return. Alternatively, the task may perform part of its function, change its state, and then return, allowing other tasks to run. The task steps through each state as it gets another turn at the processor, such as in the following example:

void task1() \{
		static int state = 0 ;
		switch (state) \{
		case 0: state0();state=1;break;
		case 1: state1();state=2;break;
		case 2: state2();state=3;break;
		case 3: state3();state=0;break;
	\}
	\}

The next time you consider a system design, look at single-stack operating systems. It takes a slightly different mind set to utilize but the pay off can be considerable. It may also allow a simpler processor to handle an application.

Although not always the best solution, single-stack operating systems are sometimes the right choice. Single-stack operating systems have found a home in a wide variety of applications from digital signal processing to robotics.

Related Links
Quadros
www.quadros.com

OSEK/VDX
www.osek-vdx.org

TAGS: Automotive
Hide comments

Comments

  • Allowed HTML tags: <em> <strong> <blockquote> <br> <p>

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
Publish