Novos RRS: Round Robin Scheduling Environment
The Novos RRS Environment employs a multitasking model for Background tasks (BG tasks) as well as Foreground tasks (FG tasks). All BG tasks in the Novos RRS Environment share the same priority, executing is what is called “Round Robin” fashion.
The Round Robin multitasking model is a form of Cooperative Task Scheduling but unlike FCFS scheduling, a BG task maintains control of the CPU only for a limited amount of time. Every BG task in the Robin has a time quantum property that defines how long it can maintain CPU control. When that time quantum expires, the Novos RRS Task Scheduler forces the task to give up CPU control so that the next eligible task can have its turn. This enforced “cooperation” with the other tasks ensures the work of the application gets done in a timely and orderly manner.
Background tasks in the Novos RRS Environment that are eligible to run are found in a FIFO queue (the Robin) from which the Task Scheduler pulls the BG task at the front of the queue and gives it control of the CPU whilst simultaneously starting its time quantum timer. When the time quantum expires, the Scheduler forces the BG task to yield CPU control and then moves it to the tail of the queue to run when it again reaches the head of the queue. The Scheduler then selects the next task from the head of the queue and gives it control of the processor. And the process repeats. Only when there are no BG tasks in the Robin does control pass to the Idle Task, which does not have an execution time quantum.
In addition to the time quantum property, each BG task has a stack on which it maintains local variables and on which the Novos RRS Environment will save the BG task’s context when it is not in control of the CPU.
With proper selection of time quanta, the Novos RRS Environment allows for a democratic sharing of the CPU in the Background while still permitting hard real-time operations in the Foreground. A BG task can be pre-empted by an FG task but not by another BG task because all BG tasks, except the Idle Task, run at a single priority level. Through the combination of the set of FG tasks, multiple BG tasks and the Idle Task, it is possible to produce a broad range of applications.
Why Use the Novos RRS Environment?
The Novos RRS Environment consists of two modes of operation to provide an efficient framework for embedded system implementation. In the Background, the Novos RRS Environment is useful for applications that have soft real-time control requirements because it avoids the long task/short response issue found in cooperative FCFS scheduling.
It has been the experience of many embedded developers over many years that a multitasking environment using Round Robin scheduling is very easy to control and use. Interference from other BG tasks is eliminated, which simplifies debugging and testing. With the right time quanta for the various BG tasks, the result is an excellent, provable execution environment for an embedded system.
The Novos RRS Environment is also fully documented. We offer two separately available volumes of documentation for the Novos RRS Environment for a small charge. A User Guide explains the Novos RRS Environment design, its classes and how to use it. A Services Reference Guide gives a complete description of each Novos RRS Environment API. Get the code and the docs and see how all of it can help on your next application.
The Novos RRS Environment makes it easy to get the job done quickly and efficiently by:
- Providing a standard model for interrupt servicing that simplifies device driver design
- Recognizing and synchronizing application code with external or internal events
- Multitasking of Background tasks using Round Robin scheduling
- Requiring each BG task to have its own stack and time quantum
- Pre-emptive scheduling of all Foreground execution entities
- Requiring only one stack for all Foreground entities
- Passing data between the execution entities, including interrupt service routines
- Handling time-based operations
- Providing two types of exclusive access management
If you are thinking about a new application that could use Round Robin scheduling, you owe it to yourself to consider using the Novos RRS Environment. The price is right – It’s FREE – and it will reduce your project risk, shorten the application development schedule and help make a more maintainable product.
The Novos RRS Environment is also fully documented. We offer two separately available volumes of documentation for the Novos RRS Environment for a small charge. A System Reference Guide explains the Novos RRS Environment design, its classes and how to use it. A Services Reference Guide gives a complete description of each Novos RRS Environment API. Get the code and the docs and see how all of it can help on your next application.
Most embedded applications need to service peripheral devices from time to time. Polling the devices is one way but a costly one in terms of cycles, power and performance. Interrupts are usually a better solution and the Novos RRS Environment is especially well suited to the job of servicing them rapidly and predictably.
The Novos RRS Environment uses two-level interrupt service model that is common to all Novos operating environments, providing a robust design and ease of handling interrupts. The highest level services the immediate needs of the interrupting device and schedules the second level handler, the Deferred Interrupt Handler (DIH). As a high priority Foreground execution entity, the DIH has full access to the Novos RRS API set, allowing it to communicate with other DIHs as well as FG tasks or the Idle Task about the device’s input or output data.
Synchronizing with Events
It is a common requirement in almost all embedded systems that the various execution entities know when an event takes place in order to synchronize with it. Timely response to events is often part of the application’s requirements. And if there is a real-time requirement, it is a necessity.
The Novos RRS Environment supports two ways to achieve event synchronization. One is the classical method using a semaphore associated with the event in which a Background task waits (pends) for the event to occur and another entity signals (posts) the event’s occurrence. Although it is well-proven and effective, this classical technique in a cooperative scheduling environment can lead to unwanted timing issues, the so-called “Convoy Effect”.
The second choice the Novos RRS Environment gives you is to use Event Action Routines (EARs) for specific types of class-related events. By employing EARs, it is easy to respond to such events in a timely manner, further enhancing the capability of the Novos RRS Environment even for real-time applications.
Using EARs for rapid response to events is also a way of mitigating the Convoy Effect that can occur with cooperative multitasking. Instead of having to wait for a task to get to the head of the queue (the Robin) and gain CPU control before responding to an event, an associated EAR can deal with the event when it occurs. The time criticality of the task’s response to the event is thereby greatly reduced.
Novos RRS Classes of Services
The Novos RRS Environment supports 78 services distributed amongst ten classes, which include:
A Deferred Interrupt Handler (DIH) is a Foreground execution entity that runs as the result of an interrupt. It allows an interrupt service routine to connect with other execution entities in the application through the use of Novos RRS services in order to pass data between the device and those entities. A DIH can invoke a Novos RRS service that causes an event that schedules an Event Action Routine.
An Event Action Routine (EAR) is a micro-task that executes when a Novos RRS service invoked from any execution entity detects an event for which there is an associated EAR. The scheduled EAR always runs as a Foreground entity, meaning that it will pre-empt any Background or Foreground task operation. The association between an object, the event conditions and an Event Action Routine is user-defined. An EAR can invoke all services available to any Foreground execution entity.
Foreground Tasks (FG tasks) execute at priorities below that of an Event Action Routine but above that of the Background tasks. FG tasks are interruptible as well as pre-emptible by Event Action Routines and higher priority FG tasks. They can also schedule other FG tasks and may invoke Novos RRS services available to any FG task.
Background Tasks (BG tasks) are independent execution entities that run in the Background. Each BG task (except the Idle Task) has the same fixed priority as well as a stack for local variables and for saving and restoring the CPU context when it is not in control of the CPU. The stack enables it to block, suspend or otherwise pause in its execution path in order to synchronize its execution with events outside its scope. Each BG task in the Novos RRS Environment (except the Idle Task) has a defined, task-specific time quantum that limits the duration of its CPU control in any given execution cycle. BG tasks gain CPU control with respect to their order in the Robin queue. Once in control of the CPU, a BG task maintains that control until it voluntarily gives it to another BG task or is forced to yield because its time quantum expires.
The Alarm and Counter classes provide services to handle time-based operations in all execution entities, including the Idle Task. A single system time-base can support any number of application-defined alarms, which can be either one-shot or cyclic in nature. BG tasks can block while waiting for alarms to expire. FG tasks cannot wait.
The Event Group class services provide execution entities ways to use groups of bit-level flags to set and detect one or more events in a simple and efficient way with AND/OR Boolean logic. One or more BG tasks can set up task-specific test conditions on an event group and wait with or without a timeout until its test flags match those of the event group. FG tasks can set and test the flags in an event group but they cannot block if the test does not produce a match.
The Queue class provides services to move data to/from the execution entities, including the Idle Task, DIH, EAR and FG task entities. Support exists for both First-In-First-Out (FIFO) and Last-In-First-Out (LIFO) queueing. Except for the Idle Task, blocking with or without timeouts while waiting to put data into or get data from a queue is permitted for BG tasks. FG tasks cannot block during queue operations.
The Semaphore class supports a full counting model that permits any execution entity to post a signal and/or detect the occurrence of a related event. Except for the Idle Task, BG tasks can wait for an entity to post a signal to a semaphore with or without a timeout. Posting a signal can result in one or all tasks waiting for the event to receive notice of its occurrence. The degenerate case of the counting semaphore model is the binary semaphore, which is also supported for simple exclusive access to resources.
The Memory Pool class allows RAM to be divided into pools of user-defined, fixed size blocks that all execution entities can allocate, use and release. Contiguous and non-contiguous RAM blocks are permissible, allowing a versatile means to manage a precious resource. If a RAM block is unavailable, a BG task can wait with or without a timeout for one to be freed to the memory pool, or under certain conditions, to allocate the block from available RAM.
The Mutex class provides a more complex exclusive access management method as compared to that offered by the Semaphore class. Once acquired, a Novos RRS mutex has a defined owner and only that owner can release it. Waiting with or without a timeout to acquire a mutex is supported. There is no priority inversion support because all BG tasks have the same priority.