Novos FCFS

Novos FCFS: First Come, First Served Scheduling Environment

Many applications are decomposed into a set of independent tasks that, taken as a whole, meet the application’s requirements. Each task gains control of the CPU in some defined order in response to system dynamics. This is the essence of multitasking. The Novos FCFS Environment implements a multitasking policy called “First Come, First Served” scheduling. In it, all tasks scheduled by the FCFS policy run in the Background and, except for the Idle Task, have a single, fixed priority.

The FCFS multitasking model is a form of Cooperative Task Scheduling because each of the Background tasks maintains control of the CPU only for as long as is necessary for it to do whatever portion of its work is required at that time. When it has done that work, it voluntarily gives up CPU control so that other tasks can have their turn. This “cooperation” with the other tasks ensures the work of the application gets done in a timely and orderly manner.

Background tasks (BG tasks) in the Novos FCFS Environment that are eligible to run are put in a FIFO queue from which the Task Scheduler pulls the BG task at the front of the queue and gives it control of the CPU. When the BG task finishes its work, it yields CPU control and goes to the tail of the queue to run again when it again reaches the head of the queue. After the task yields, the Scheduler selects the next task from the head of the queue and gives it control of the processor. And the process repeats.

A BG task can yield control voluntarily and can also block further execution to wait until some event occurs. Such capability requires that each BG task have an associated stack on which to save the task’s local variables and context when the task is not in control of the CPU as the result of yielding control, waiting for an event or preemption by a Foreground task.

The Novos FCFS Environment also supports pre-emptive scheduling of Foreground tasks (FG tasks), which operate at higher priorities than the FCFS scheduled BG tasks. Any FG task can pre-empt a BG task but a BG task cannot pre-empt another BG task because all BG tasks, except the Idle Task, have the same priority level.

The mixed capability of the Novos FCFS Environment provides a very clean, provable operating environment that covers a broad spectrum of applications, including some that are mission critical.


Why Use the Novos FCFS Environment?

The Novos FCFS Environment is useful for embedded applications that have soft real-time control requirements. It has been the experience of many embedded developers over many years that a cooperatively scheduled, multitasking environment is one of the easiest to control and use. Interference from other BG tasks is eliminated, which simplifies debugging and testing.

And if there is also a requirement for deterministic, hard real-time operations in the application, the Novos FCFS Environment includes Foreground tasks (FG tasks). When FG tasks are used in conjunction with Rate Monotonic Analysis, the Foreground entities in the Novos FCFS Environment can yield hard real-time performance with provable schedulability. You can use the FG tasks to meet the application’s real-time requirements and use the BG tasks for the soft real-time jobs.

The Novos FCFS 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
  • Pre-emptive scheduling of all Foreground execution entities
  • Passing data between the execution entities, including interrupt service routines
  • Handling time-based operation
  • Requiring only one stack for all Foreground entities
  • Requiring each BG task to have its own stack
  • Providing two types of exclusive access management

If you are thinking about building such an operating environment yourself, you owe it to yourself to consider using the Novos FCFS Environment. It will definitely reduce your overall costs because the Novos FCFS Environment source code is FREE. You will also reduce your project risk, shorten the application development schedule and help make a more maintainable product.

And the Novos FCFS Environment is fully documented. We offer two volumes of documentation on the Novos FCFS Environment that are separately available for a small charge. A User Guide explains the Novos FCFS Environment design, its classes and how to use it. A Services Reference Guide gives a complete description of each Novos FCFS Environment API. Get the code and the docs and see how all of it can help on your next application.

Servicing Interrupts

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 FCFS Environment is especially well suited to the job of servicing them rapidly and predictably.

The Novos FCFS 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 FCFS 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.

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 FCFS Environment supports two means to synchronize with events. The first is the classical method that uses a semaphore associated with the event. A Background task waits (pends) for the event and another entity, in the Foreground or Background, posts a signal that the event has occurred, allowing the waiting Background task to resume its operation when it next gets CPU control. It is a proven and effective technique but in a cooperative scheduling environment, it can lead to unwanted timing issues, the so-called “Convoy Effect”.

The other means of event synchronization in the Novos FCFS Environment uses 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 FCFS Environment even for real-time applications.

Using EARs for rapid response to events is also a way of mitigating the Convoy Effect often found in cooperative multitasking environments. Instead of having to wait for a task to get to the head of the queue 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 improved.

Novos FCFS Entities and Service Classes

The Novos FCFS Environment supports 76 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. A DIH can invoke Novos FCFS services that pass data between the DIH and other entities whether in the Foreground or the Background. Events caused by those services can schedule Event Action Routines.

An Event Action Routine (EAR) is a micro-task that executes when a Novos FCFS 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 FCFS services available to any FG task.

Background Tasks (BG tasks) are independent execution entities that run in the Background. Each BG task has a priority and a stack for local variables as well as for context saving. 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. All BG tasks in the Novos FCFS Environment (except the Idle Task) have the same, fixed priority. BG tasks gain CPU control in the order they are made ready or become unblocked as a result of some event. Once in control of the CPU, a BG task maintains that control until it voluntarily gives it to another BG task.

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 FCFS 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.