Build a Super Simple Tasker

Almost all embedded systems are event-driven; most of the time they wait for some event such as a time tick, a button press, a mouse click, or the arrival of a data packet. After recognizing the event, the systems react by performing the appropriate computation. This reaction might include manipulating the hardware or generating secondary, “soft” events that trigger other internal software components. Once the event-handling action is complete, such reactive systems enter a dormant state in anticipation of the next event.1

Ironically, most real-time kernels or RTOSes for embedded systems force programmers to model these simple, discrete event reactions using tasks structured as continuous endless loops. To us this seems a serious mismatch–a disparity that’s responsible for much of the familiar complexity of the traditional real-time kernels.

In this article we’ll show how matching the discrete event nature typical of most embedded systems with a simple run-to-completion (RTC) kernel or “tasker” can produce a cleaner, smaller, faster, and more natural execution environment. In fact, we’ll show you how (if you model a task as a discrete, run-to-completion action) you can create a prioritized, fully preemptive, deterministic real-time kernel, which we call Super Simple Tasker (SST), with only a few dozen lines of portable C code.2

Such a real-time kernel is not new; similar kernels are widely used in the industry. Even so, simple RTC schedulers are seldom described in the trade press. We hope that this article provides a convenient reference for those interested in such a lightweight scheduler. But more importantly, we hope to explain why a simple RTC kernel like SST is a perfect match for execution systems built around state machines including those based on advanced UML statecharts. Because state machines universally assume RTC execution semantics, it seems only natural that they should be coupled with a scheduler that expects and exploits the RTC execution model.

We begin with a description of how SST works and explain why it needs only a single stack for all tasks and interrupts. We then contrast this approach with the traditional real-time kernels, which gives us an opportunity to re-examine some basic real-time concepts. Next, we describe a minimal SST implementation in portable ANSI C and back it up with an executable example that you can run on any x86-based PC. We conclude with references to an industrial-strength single-stack kernel combined with an open-source state machine-based framework, which together provide a deterministic execution environment for UML state machines. We’ll assume that you’re familiar with basic real-time concepts, such as interrupt processing, context switches, mutual exclusion and blocking, event queues, and finite state machines.

Links: http://embedded.com/columns/technicalinsights/190302110

Intertask communication and synchronization

Most operating systems, including RTOSs, offer a variety of mechanisms for communication and synchronization between tasks. These mechanisms are necessary in a preemptive environment of many tasks, because without them the tasks might well communicate corrupted information or otherwise interfere with each other.

For instance, a task might be preempted when it is in the middle of updating a table of data. If a second task that preempts it reads from that table, it will read a combination of some areas of newly-updated data plus some areas of data that have not yet been updated. [New Yorkers would call this a "mish-mash."] These updated and old data areas together may be incorrect in combination, or may not even make sense. An example is a data table containing temperature measurements that begins with the contents “10 C.” A task begins updating this table with the new value “99 F”, writing into the table character-by-character. If that task is preempted in the middle of the update, a second task that preempts it could possibly read a value like “90 C” or “99 C.” or “99 F”, depending on precisely when the preemption took place. The partially updated values are clearly incorrect, and are caused by delicate timing coincidences that are very hard to debug or reproduce consistently.

An RTOS’s mechanisms for communication and synchronization between tasks are provided to avoid these kinds of errors. Most RTOSs provide several mechanisms, with each mechanism optimized for reliably passing a different kind of information from task to task.

Probably the most popular kind of communication between tasks in embedded systems is the passing of data from one task to another. Most RTOSs offer a message passing mechanism for doing this, as seen in Figure 5. Each message can contain an array or buffer of data.

If messages can be sent more quickly than they can be handled, the RTOS will provide message queues for holding the messages until they can be processed. This is shown in Figure6.

Another kind of communication between tasks in embedded systems is the passing of what might be called “synchronization information” from one task to another. “Synchronization information” is like a command, where some commands could be positive, and some negative. For example, a negative command to a task would be something like “Please don’t print right now, because my task is using the printer.” Or more generally, “I want to lock the . . . for my own use only.” A positive command would be something like “I’ve detected a cardiac emergency, and I want you to help me handle it.” Or more generally, “Please join me in handling . . .”

Most RTOSs offer a semaphore or mutex mechanism for handling negative synchronization (sometimes called “mutual exclusion”). These mechanisms allow tasks to lock certain embedded system resources for their use only, and subsequently to unlock the resource when they’re done.

For positive synchronization, different RTOSs offer different mechanisms. Some RTOSs offer event-flags, while others offer signals. And yet others rely on message passing for positive synchronization as well as data passing duties.

Operating System

An operating system (OS) is the software that manages the sharing of the resources of a computer. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the system. At the foundation of all system software, an operating system performs basic tasks such as controlling and allocating memory, prioritizing system requests, controlling input and output devices, facilitating networking and managing file systems. Most operating systems come with an application that provides a user interface for managing the operating system, such as a command line interpreter or graphical user interface. The operating system forms a platform for other system software and for application software. Linux and Mac OS (or any other BSD-derivative) are popular UNIX-like operating systems. Windows takes a different approach to operating systems, derived upon a historic single-user model.

Links:

http://en.wikipedia.org/wiki/Operating_system

http://computer.howstuffworks.com/operating-system.htm

http://www.top500.org/lists/2005/11/charts/Operating_System