We have been working closely with CEVA, Inc. to support their versatile CEVA-X family of low power, high performance DSP cores using the CEVA-Toolbox™ suite of development tools. CEVA holds 90% of the market for DSP cores and boasts adoption by many leading SoC developers. Today we announced our support for CEVA-X1622, CEVA-X1641 and CEVA-X1643 DSP cores. Read more about RTXC/CEVA integration here. ...
RTOS Explained: Understanding Event Flags
To fully understand event flags it will be helpful to read the previous blog entry on semaphores since both semaphores and event flags are techniques used by RTOSes for synchronizing tasks. Semaphores and event flags must have the inherent capability to capture and retain information about an event’s occurrence since the system may be otherwise occupied when the event happened. Event flags are bits and the usual way of handling them is to group them into larger data elements. Different efficiencies can be obtained with different sizes, so it is not uncommon to see one RTOS that uses an event flag grouping of a byte and others that use a short or a word. Whatever the grouping, it is usually called an event group. The application developer assigns the association of flags in the group to their related events. At time of initialization, the common procedure is to set all flags in an event group to a value, indicating that the associated events have not occurred. From there on, the content of the event group at any given moment is a joint effort between the tasks that use it and the operating system. The system may set a flag to indicate the event’s occurrence but it is usually the responsibility of the task to cause the flag to be reset. This shared responsibility exposes the vulnerability of event flags – if the task doesn’t reset the flag before the next event arrives, an event can be lost, which can have varying degrees of consequence. While there is that glaring vulnerability, event flags still have some very attractive features. For one, it is very simple to perform logical testing of the flags. A task can test on a certain configuration of flags in an event group and wait if that condition is not met. Testing on the logical OR condition of a set of event flags allows a task to wait until any one of the events occurs and to identify which one simply and easily. In the same way a task can wait for a logical AND condition in which all of the event in a set must occur before the waiting task can proceed. Event flags can be designed so that they are reset upon a trigger or left intact so that the testing task can determine which one of them happened. This is most likely to be the case when using a set of event flags in a logical OR manner. When the testing task has made its determination as to which event triggered the task’s release, it must issue a request to reset them in order to prepare for the next occurrences. When the event flags are used in a logical AND condition, the task does not get triggered until all of the events in the set have occurred, leaving no question about which events happened. In this condition, resetting of the event flags can be managed by the system to reset on triggering, which is much less likely to run into the race condition one can easily encounter if the task resets the event flags in an Or condition. So within the boundaries of response time for the various events and their frequency of occurrence, event flags can be a very useful object for managing events and synchronizing with them. While event flags are easy to use, one downside to their use is that it can be difficult to process an event deterministically. For system designs where the event groups are available to all tasks, it is possible (and quite likely) that a single event group may hold event flags that are tested by multiple tasks. Such usage demands that each task have a unique testing trigger set up for that event group. When any one of the events in the group occurs, the set of triggering conditions must be examined to see if any of the triggers have occurred. It might be a bounded operation dependent on the number of triggering conditions in action, but it is not deterministic. Event flag objects can be included in an RTOS with a minor increase in code footprint. For that reason alone, they are worthwhile to include provided that the vulnerability to event loss is not a concern. ...
RTOS Explained: Understanding Semaphores
A fundamental requirement of a competent multitasking system is a flexible means to detect occurrence of an event and then to synchronize a task with that event (external or internal; synchronous or asynchronous). The requirement is usually met by either semaphores or event flags. Whichever object type is used (and some RTOSes support both) their purposes are identical: synchronize a task as near as possible to the actual time of the event’s occurrence. Semaphores and event flags must have the inherent capability to capture and retain information about an event’s occurrence since the system may be otherwise occupied when the event happened. This is known as event memory. The methodology for this event memory constitutes the primary difference between semaphores and event flags. The term “semaphore” is derived from the nautical use of signaling flags to spell out messages in which the message’s characters are based on the position of the two flags, the semaphores. Except for the concept of signaling, the analogy ends there. In the world of computing, there are many variations to how semaphores are designed and operate, especially in conjunction with real-time operating systems. The most commonly used semaphore model is one that has a counter and a set of tasks that are waiting on the associated event. This is the counting semaphore model and it is found in most commercial RTOS products today. The count element of the semaphore serves as the event memory. In its basic implementation, the semaphore’s count increments each time its associated event occurs and decrements it each time a task tests it when its count is greater than zero. A count greater than 0, means events have happened for which tasks have not yet tested. A count of 0 means that no events have occurred since the last time the semaphore was tested. The set of waiter tasks is a record of those tasks that are waiting for the event to occur before proceeding further. Of course, it is not necessary to wait on an event if it has not occurred at the time of the test. It is certainly possible for a task to poll a semaphore and to continue processing depending on whether the associated event has or has not happened. That’s not usually what is considered good design, so let’s put it aside and focus on how the semaphore would normally be used. When the counting semaphore is initialized, its count element and the set of waiting tasks are cleared to null states. If a task tests the semaphore associated with an event and it has not yet occurred, its count isn’t changed but the task becomes blocked and is added to the set of waiters. When the event eventually occurs, the semaphore’s count is incremented by 1. And if it has waiters, one or more of them can be resumed, depending on the design of the system. But regardless of the manner in which the system releases waiter tasks, the semaphore’s count would be reduced by 1. In the RTXC Quadros kernel, the application developer may choose to have waiting tasks released from the semaphore’s set of waiting tasks in priority order or all at once. If, on the other hand, the event occurs before a task has come around to testing for it, the count element is incremented by one, setting the semaphore’s event memory. When the next test of the semaphore occurs, the operating system reduces the semaphore’s count by 1 and allows the testing task to continue without loss of CPU control. A semaphore may be organized in various ways and takes various amounts of RAM, depending on that organization. Some counting semaphores can be organized as a single byte, others can require many more. Regardless of the organization, the counting semaphores’ can accurately maintain the count of multiple occurrences of the associated event without losing even one. This is one of the reasons the RTXC Quadros kernel uses counting semaphores as the primary mechanism for synchronizing tasks with those events. Variations on this basic semaphore permit multiple semaphores to be signaled when one event occurs. Likewise, one task can synchronize with any one of a set of events to occur by waiting on their respective semaphores, producing a logical OR condition. There are other types of semaphore testing options. One is to have the testing task blocked for a certain number of ticks (instead of an indeterminate wait). In RTXC Quadros kernel, it is permissible to set a semaphore’s count to a negative value in order to have tasks wait for multiple occurrences of the associated event before being triggered. The RTXC Quadros RTOS also allows semaphores to be associated with events in other classes. For instance, a semaphore can be associated with an alarm’s expiration or an empty queue receiving an entry. This provides additional synchronizing flexibility that allows disparate objects to be logically combined so that the developer can trigger a task to start at some determined period when any one of them occurs. ...
RTOS Explained: Understanding Priority Inversion
A fundamental maxim in a real-time system is that the highest priority task that is ready to run must be given control of the processor. If this does not happen deadlines can be missed and the system can become unstable or worse. Priority inversion simply means that the priority you established for a task in your system is turned upside down by the unintended result of how priorities are managed and how system resources are assigned. It is an artifact of the resource sharing systems that are fundamental to RTOS operation. Mutex (and/or Semaphore) objects are used to ensure that the various tasks can have exclusive access to system resources when they need them. Consider Task C that is writing to RAM. To protect against memory corruption which could occur if another higher priority task (Task A) preempts Task C and writes to the same block, Task C uses a Mutex to lock access to the RAM until the write is completed. However, Task A interrupts Task C before the operation can be completed and yet Task A needs to access the file system to complete its work. The result is a priority inversion. Task C must finish its work so that Task A can get access, but Task A has blocked Task C because Task A has a higher priority. Embedded gridlock! This scenario can be termed “bounded inversion.” A variation of this is termed “unbounded inversion.” Task C has locked the RAM with a Mutex and is then preempted by Task B which is attempting to perform an unrelated, but higher priority operation. Highest priority Task A then preempts Task B but relinquishes control (blocks) since it cannot access the resource because of the Mutex claimed by task C. Task B then resumes operation and maintains control of the processor for as long as it needs it. Task A (the highest priority task) is unable to run during this unbounded period. The simple solution is to let Task C finish what it was doing, uninterrupted, and then release the Mutex on the file system so that Task A can do what it needs to do. But the operating system objects are doing exactly what they were programmed to do and, without special logic to deal with these situations, the scheduler must honor the relative priorities of Tasks A, B and C and the inherent rules of the operating system. So how does the developer avoid these situations or once in them, how does the system get out of the situation? A great deal of study has gone into this subject and space does not allow a detailed review of the research. Instead, let’s consider the two most common ways that RTOSes deal with priority inversion and how each approach affects the conditions of bounded or unbounded inversion. Both of these techniques are valid and both have their pros and cons. Priority Inheritance Protocol – Change the priority of Task C to the same as Task A. Task A has to wait for Task C to complete, but the assumption is that at the higher priority, Task C can get more cycles that are not pre-empted and can thus complete its critical region more quickly in real-time. When Task C completes its critical region, it returns to its original priority and ownership of the shared resource’s Mutex is then assigned to the waiting Task A. Priority Ceiling Protocol – This method is also called Instant Inheritance Protocol. If there is a set of n tasks that use a shared resource, a Mutex is assigned to the shared resource and given a priority that is at least as high as, if not higher than, the highest priority of the n tasks in the set. When any task attempts to acquire ownership of the shared resource’s Mutex, it will be granted and its priority instantly changed to the priority of the Mutex. This action prevents any possibility of preemption by another member of the set of the shared resource’s users because all other tasks in the set are, by definition, at a lower priority than that of the current owner. Thus, there can be no tasks that are waiting to get ownership of the Mutex because they cannot get scheduled. This method effectively prevents the possibility of a priority inversion. Notice that this method also effectively deals with unbounded inversion issue because no other task (such as Task B) that has a priority between that of the lowest priority task in the set and the highest priority members of the set can get scheduled. When the owner task completes its critical region, the Mutex is released and the task returned to its original priority. The Priority Ceiling Protocol used by other RTOSes avoids the potential problem of dealing with unbounded inversions but, since all tasks that use the same resource are permanently given the same high priority, even if they are not essential tasks, this may starve other, more important tasks. The RTXC Quadros RTOS uses Priority Inheritance Protocol. It addresses bounded inversions and avoids the potential problem of Priority Ceiling Protocol that can starve tasks which are not part of the set. ...
RTOS Explained: Understanding Critical Regions
Critical Regions and the Effect on RTOS Responsiveness A key design concern for any RTOS is that of its responsiveness to interrupts. Because an interrupt can occur at any time, the RTOS must be prepared to recognize the interrupt as quickly as possible and then accommodate the interrupt service routine (ISR) that handles it. The issue becomes one of managing the internal data structures of the kernel in such a way that regardless of what is executing at the time of the interrupt, none of those data structures get corrupted. The time-honored way of preventing data corruption in an RTOS is to make use of one or more critical regions in places where an interruption of processing flow within a kernel service and possible reentrancy might lead to damage. The critical region can assume several forms but it is primarily a section of code that executes with interrupts disabled. The critical region starts by disabling interrupts and ends by enabling them. In between, the code can execute without fear of interruption and hence, corruption. There are various ways to disable and enable interrupts, especially those processors that have multiple levels, making critical regions a bit more complex. But for now, let’s just keep it simple for the sake of clarity. Because critical regions disable interrupts, system responsiveness is greatly affected by the duration of the critical region (if any) that is in effect at the time an interrupt occurs. Simply put, the shorter the critical region, the better the system’s responsiveness. If a task is interrupted in the middle of a kernel service it has invoked, there is a good chance that the kernel’s data structures are in a state of flux at the time of the interrupt. Without the kernel executing the code that keeps the data structure pristine, the interrupt and its ISR could invoke a kernel service that totally corrupts the data structure, leading to les than desirable results for both the task and the ISR. Obviously, such situations must be avoided. Thus, when designing an RTOS one has to make a fundamental decision as to how kernel services are to be treated at the interrupt level. There are basically two choices and both are legitimate. Allow ISRs to make kernel service requests just like a task with the exception that an ISR cannot block, (i.e., wait for a service to reach completion such as waiting to get data from an empty queue). ISRs can only issue kernel service requests from a limited set of services that restricts what the ISR can do/change in the system. The first choice naturally leads to a reentrant kernel and great flexibility because tasks and ISRs are treated the same, with that one exception about waiting. That flexibility comes at a price of designing kernel services that require lengthy critical regions in order to protect the underlying data structures in the kernel. An ISR must not be allowed to corrupt an internal data structure in use by a task at the time of the interrupt. Thus, any and all parts of the kernel service code that would be vulnerable to the ISR must be protected by one or more critical regions. Hence, the critical region may be rather large, leading to reduced interrupt responsiveness. So there is a trade-off: Great coding flexibility for reduced responsiveness. The second design choice limits the capability of the kernel services that may be invoked from an ISR. By making such a restriction, the kernel designer can precisely determine how a task’s use of a service and its underlying data structures would be vulnerable to an ISR. There are still critical regions to consider but the design generally results in fewer and smaller critical regions, making this choice more responsive to interrupts. The trade-off for this concept then is: Reduced flexibility for improved responsiveness. While both of these choices are legitimate, the RTXC Quadros RTOS uses the second choice in the belief that responsiveness is preferable to ISR coding flexibility, provided that there is a reasonable set of kernel services available to the ISR designer. And, of course, RTXC Quadros RTOS does provide such a set of kernel services using the same form as services available to tasks but with name space separation. Task services have a prefix of KS_ while the services available to ISRs have a prefix of IS_. Given these two choices and how they can affect an RTOS design, it should be pointed out that it is also possible to create an RTOS design that reduces the number of critical regions in the entire kernel to only a few, perhaps two or three. The resulting design, while atypical, can mitigate the undesirable elements of the two choices just described yielding an RTOS that is highly responsive to interrupts and has high ISR coding flexibility through a common set of kernel services for tasks and ISRs. ...
RTOS Explained: Understanding Counters and Alarms
One of the valuable feature of a real-time operating system is the ability to count and then to take action at certain defined values of an associated counter. Most RTOSes count only a single independent variable, time, denominated in the unit of time each tick represents. But the RTXC Quadros RTOS provides a more flexible approach to counting because time is not the only independent variable one is likely to encounter in a real-time system. The RTXC Quadros RTOS certainly accommodates time, represented by periodic events, but it can also handle aperiodic events that represent independent variables such as angular rotation or flow. Why is this important? Imagine having to keep track of rotational speed of an automobile’s engine or the volume of fluid flowing through a positive displacement meter with only time as your independent variable. All sorts of transformations would be required, each with its own built-in errors. But if there were a tick representing increments of angular displacement, measuring angular velocity or RPMs on an engine is significantly easier. Likewise, if each tick from a PD meter represented some known volume, flow rate and volume become very straightforward and more accurate. To allow more degrees of design freedom to system developers, the RTXC Quadros RTOS uses a hierarchy of classes to count and keep track of ticks. At the highest level in the hierarchy, there is an Event Source, representing some base count frequency. One or more Counters can be associated with the parent Event Source. The user defines the units of the Counter and the number of Event Source ticks that represent one Counter tick. In this way, it is easy to divide down a higher frequency into a lower one. Using time as an example, an Event Source might provide a fixed rate of 1000 ticks per second (1 kHz), which would allow a counter representing 1 millisecond if each Event Source tick was treated as a Counter tick. And if another Counter associated with that same Event Source used 1000 Event Source ticks as one Counter tick, its units would be denominated in seconds (1 Hz). Thus, if a Counter is incremented at a regular rate, then it can represent time. Normally, the units are milliseconds but others are possible. And the Counter doesn’t have to start at zero. A task can set up a Counter to begin counting from a specified base value, making a time base such as Base Universal Time very simple to achieve. Many applications need to know the number of ticks that occurred between two events. Two kernel calls are required: the first to establish the starting value and the second to get the number of ticks (from whatever counter) that have elapsed between two events, returning the difference in number of ticks from the initial event. Some RTOSes must continually poll their counters to check the value. The RTXC Quadros uses an Alarm class for generalized counting management as the third member of the counting hierarchy. This solution allows any Counter to be the parent of an Alarm with its units denominated in the units of the parent Counter. Thus, both periodic and aperiodic alarming is possible. If you need an alarm every 0.5 litres of volume flowing through a given meter without regard to instantaneous flow rate, having an alarm to tell you when it occurs is a real improvement over some traditional RTOS capabilities. The concept of alarming, however, is rather simple. An Alarm is defined to occur at a particular value of an associated Counter. When the counter reaches the value that matches the expiration point of the alarm, an action can take place, such as resuming a task that was waiting for the alarm to expire. There are two basic types of Alarm objects in the RTXC Quadros RTOS: One-shot Alarm: An Alarm that is defined for one and only pone point of expiry, upon which the alarm becomes inactive and can only be re-armed by explicit action via a kernel service before it can be used again. Cyclic Alarm: An Alarm having an initial period and a recycle period. The first point of expiration is at the end of the initial period, after which the Alarm is automatically reset to the recycle period for each expiration thereafter until the Alarm is cancelled. At the expiration of an alarm, whether one-shot or cyclic, it is possible to synchronize that event by resuming a task waiting for that event, signaling a semaphore, etc. The expiration of an alarm can also cause a RTXC Thread to be scheduled directly or indirectly. Through these synchronization mechanisms, it is not necessary to spend non-productive processor cycles polling the alarm to see if it has expired. As a result, a deterministic response to an alarm expiration is possible. No special CPU resources are required for alarms or their associated counters. In fact, it is possible to define an internal event as the system tick event. The counting hierarchy does not distinguish between an event tick from an internal or an external source. Obviously, most applications make use of some sort of periodic interrupt for the system time tick. It is up to the user to define the source of such a tick. ...
RTOS Explained: Understanding Kernel Services
Kernel services (sometimes referred to as systems calls or functions) are used to cause the kernel to operate on the data of the kernel objects to achieve the desired behavior of the application code. Knowledge of how these data structures work is fundamental to building real-time application systems around the RTXC Quadros RTOS product. To function consistently and predictably a real-time operating system must be based on a set of rules. These rules permit software processes to operate and gain access to system resources in an orderly manner. Kernel services embody and enforce these rules to ensure the necessary order in the application processes that use them. Time is the most difficult and unforgiving resource managed by the kernel. Kernel services must be designed and coded to require minimal execution time yet remain predictable. Execution speed of the kernel services determines the responsiveness of the system to changes in the physical process. Here are just a few examples of RTXC Quadros kernel services: KS_TestSemaT Test a semaphore and wait for a specified number of ticks on a specified counter if the semaphore is not DONE. KS_YieldTask Yield to the next ready task of the same priority. KS_OpenQueue Allocate and name a dynamic queue. KS_ReceiveMsgT Receive a message from a mailbox. If the mailbox is empty, wait a specified number of ticks for a message. KS_AllocBlkW Allocate a block of memory. If the partition is empty, wait for an available block. KS_UseMutx Look up a dynamic mutex by name and mark it for use. XX_AllocSysRAM Allocate a block of system RAM. A rich set of kernel services means less code for you to write. In the case of the RTXC Quadros RTOS you have access to more than 330 services. And, like the 88 keys on a piano that provide a seemingly infinite variety of music, you can use these kernel services in an almost infinite number of combinations to meet the specific need of your embedded applications. In the RTXC Quadros RTOS User Manual each kernel service is described in detail with example code. ...
RTOS Explained: Preemptive Scheduling
The RTXC Quadros multistack RTOS supports three scheduling methods that may be used in whatever combination the developer requires. Preemptive Round Robin Time-Sliced Today we will discuss the topic of preemptive scheduling. To achieve efficient CPU utilization a multitasking RTOS uses an orderly transfer of control from one code entity to another. To accomplish this the RTOS must monitor system resources and the execution state of each code entity, and it must ensure that each entity receives control of the CPU in a timely manner. The key word here is timely. A real-time system that does not perform a required operation at the correct time has failed. That failure can have consequences that range from benign to catastrophic. Response time for a request for kernel services and the execution time of these services must be fast and predictable. With such an RTOS, application program code can be designed to ensure that all needs are detected and processed. Real-time applications usually consist of several tasks (also can be called processes or threads) that require control of system resources at varying times due to external or internal events. Each task must compete with all other task for control of system resources such as memory, execution time, or peripheral devices. The developer uses the scheduling models in the RTOS to manage this “competition” between these tasks. Program code can be compute-bound (heavily dependent on CPU resources) or I/O-bound (heavily dependent on access to external devices). Program code that is I/O bound or compute bound cannot be allowed to monopolize a system resource if a more important task requires the same resource. There must be a way of interrupting the operation of the lesser task and granting the resource to the more important one. One method for achieving this is to assign a priority to each task. The kernel then uses this priority to determine a task’s place within the sequence of execution of other tasks. In a prioritized system the highest priority task that is ready is given control of the processor. Tasks of lower priority must wait and, even when running, may have their execution preempted by a task of higher priority. When a task completes its operation or blocks (waits for something to happen before it can continue) it releases the CPU. The scheduler in the RTOS then looks for the next highest priority code entity that is ready to run and assigns it control of the CPU. In this preemptive scheduling model a task must be in one of four states: Running – the task is in control of the CPU Ready – the task is not blocked and is ready to receive control of the CPU when the scheduling policy indicates it is the highest priority task in the system that is not blocked Inactive – the task is blocked and requires initialization in order to become ready. Blocked – the task is waiting for something to happen or for a resource to become available. Preemptive Scheduling in Summary Each Task has a priority relative to all other tasks The most critical Task is assigned the highest priority The highest priority Task that is ready to run gets control of the processor A Task runs until it yields, terminates, or blocks Each Task has its own memory stack Before a Task can run it must load its context from its memory stack (this can take many cycles) If a Task is preempted it must save its current state/context; this context is restored when the Task is given control of the processor Further reading Read our previous blog post on Run-to-Completion Threads Download the whitepaper: 10 Questions to Ask Your RTOS Vendor Visit the RTXC Quadros RTOS information page ...
RTOS Explained: Run-to-Completion (RTC) Threads
Introduction to RTXC Threads The RTXC Quadros RTOS offers two different execution entities: Tasks and Threads. You may be familiar with various terms like process or task or thread, depending on your OS experience. In RTXC Quadros Tasks and Threads have very specific functionality. Whether you use Threads or Tasks (or both) depends on the requirements of your application and on the particular RTXC Quadros configuration you are using. Tasks are RTXC program code that performs a defined function or set of functions. In the RTXC Quadros world each task has a priority and its own stack for saving context when preempted or rescheduled. Tasks can block or wait on events. Each task is independent of other tasks but can establish relationships with other tasks in many forms, including data structures, input, output, or other constructs. Threads are lightweight tasks which are designed to run to completion unless preempted by an ISR or a Thread at a higher priority level. The run-to-completion model allows all Threads in an application use a single stack. If preempted they save their context to the common stack. The single stack means that Threads cannot block or wait on events however Threads can be initiated by events. A Thread has no context upon entry and must perform any required data initialization upon entry. When its operations are complete, the thread returns to the RTXC/ss scheduler without context. Threads have an inherent priority above that of tasks. Thus, the lowest priority Thread is of greater importance than the highest priority Task. Thread Usage Threads are ideal for applications with event driven, hard real-time requirements. Because RTXC Threads fit very nicely into fixed priority scheduling methods, thread priorities can be determined using Rate Monotonic Analysis (RMA) to ensure schedulability of the real-time tasks to meet their deadlines. Being lightweight tasks, Threads are adept at handling processing associated with a high frequency of interrupts. They can be scheduled and complete their operating more quickly and with less system overhead. Threads are also ideal for event-driven execution using Finite State Machines (FSM) or Hierarchical State Machines (HSM). The advantage for state machine implementations is that our implementation of Threads supports the Run-To-Completion execution model inherent in state machine design: the system must complete the processing of an event before it can start processing the next event. Thread Scheduling and Preemption Depending on how you set up your system you can operate RTXC/ss as a Cooperative Executive or as a Prioritized, Preemptive Executive. Cooperative Scheduler: If you implement only a single priority level within RTXC/ss then Threads will run to completion once they are launched. However, during their operation they may be interrupted. You can establish a priority for Threads within a level but this only determines the order in which they will be scheduled. A running Thread cannot be preempted by another Thread in the same level. Prioritized, Preemptive Scheduler: If you implement multiple priority levels within RTXC/ss then a ready Thread in a higher priority level will preempt the Current Thread. In this case the context of the Current Thread is saved in the common stack to be resumed after all ready Threads in higher levels of priority have run. For more information on any of these topics request our user manuals or contact your local sales representative. ...