Real-Time Java for the Rest of Us

This chapter is from the book

Real-Time Java Programming: With Java RTS

Learn More Buy

This chapter is from the book

This chapter is from the book 

Real-Time Java Programming: With Java RTS

Learn More Buy

Real-Time Scheduling

A task by itself represents a useless body of instructions. For a task to be useful and meaningful, it must be processed, and it therefore must have scheduled execution time on a processor. The act of scheduling processor time to a task, or thread, and assigning it a free processor is often called dispatching. Real-time schedulers can schedule individual tasks for execution either offline (prior to the system entering its running state) or online (while the system is in an active, running state). Regardless of when it occurs, all scheduling work is done according to a predefined algorithm, or set of rules.

Scheduling Constraints

Many factors, or constraints, are taken into account when scheduling real-time tasks. Because each application—and hence each task—is different, these constraints may vary from system to system. However, they all generally fall into a subset of constraints that need to be considered. The first constraint is the amount of available resources; whether they’re tasks in a computer or construction workers on a job, having what you need to complete a task is important. The second constraint is task precedence; to avoid chaos, and to ensure proper system behavior, certain tasks may need to be executed before others. The third constraint is timing; each task has its own deadline, some tasks execute longer than others, some may execute on a steady period, and others may vary between release times.

Each constraint contains many of its own factors that need to be considered further when scheduling tasks. Let’s examine these constraints in more detail now, and how they may affect task scheduling.

Resources

Because we speak in terms of processors, tasks, and execution times, most people think of only the CPU as the main resource to be scheduled. This isn’t always the case. For example, recalling the highway analogy above, cars represented tasks, and the road represented the processor. More realistically, in a real-time network packet switching system, tasks represent data packets, and the processor represents an available communication line. Similarly, in a real-time file system, a task is a file, and the processor is an individual disk platter/head combination. However, regardless of the actual physical work being done (sending a packet, writing a file, or executing a thread), we will refer to all of them as simply a task. Further, regardless of the actual component doing the work (a network card/communication link, a disk controller, or a CPU), we will refer to all of them as simply a processor.

It’s easy to see how the availability of critical system resources, such as the processor, is important to a scheduling algorithm. After all, to execute a thread, there must be a CPU available to execute it. However, it goes beyond just the processor; other resources, such as shared objects that require synchronization across tasks, are to be considered. This may be something as abstract as a shared object in memory, or something more concrete such as a shared region of memory, or the system bus. Regardless, there is often a need to lock shared resources to avoid errors due to concurrent access. This effectively limits a resource to being updated atomically, by one task at a time. Since resource locking synchronizes access to a shared resource, one task may become blocked when attempting to access a resourced that is currently locked by another task.

In a real-time system, it’s important to ensure that high-priority, hard real-time tasks continue to make progress towards completion. Resource locking is commonly a problem since priority inversion can cause tasks to execute out of order. In many general-purpose operating systems, resource locking can lead to priority inversion, resulting in unbounded latency for critical tasks, and missed deadlines in a hard real-time system. For instance, in Figure 1-10, we see three tasks, T1, T2, and T3, each with decreasing priority, respectively.

Figure 1-10 Resource locking can lead to priority inversion. In a real-time system, this scenario must be controlled, or avoided.

In this scenario, task T3 is released shortly after the system starts. Although it’s the lowest-priority task in the system, it begins execution immediately because no other tasks have been released. Early in its execution, it acquires a lock on resource R1. At about time t + 1.5, task T1 is released and preempts the lower-priority task, T3. At time t + 3, task T2 is released but cannot execute because task T1 is still executing. At some point after t + 3, task T1 attempts to acquire a lock on R1, but blocks because it’s already locked. Because of this, T2 gains execution precedence over T1 even though it has a lower priority. When T2 completes, T3 continues again until it releases R1, at which point T1 is finally able to resume.

In a general-purpose computer system, this may be a common and acceptable situation. In a real-time system, however, this violates the principal of task priority execution, and must be avoided. The time frame from shortly after t + 3, to shortly after t + 5, represents unbounded latency that adds an unknown amount of delay to the critical task, T1. As a result, real-time systems must implement some form of priority inversion control, such as priority inheritance, to maintain forward progress of critical tasks. This will be discussed later in the chapter; for now, let’s continue our discussion on scheduling constraints.

Precedence

In many systems, real-time systems included, tasks cannot be scheduled in arbitrary order. There is often a precedence of events that govern which threads must be scheduled first. Typically, the threads themselves imply the ordering through resource sharing, or some form of communication, such as a locking mechanism. One example is a system where a task T1 must wait for another task T2 to release a lock on an object before it can begin execution. This act of task synchronization must be performed at the OS kernel level so as to notify the scheduler of the task precedence that exists.

In the example above the scheduler will block task T1, and will allow task T2 to execute. When task T2 completes its processing and releases its lock on the synchronized object that the two tasks share, the scheduler can dispatch task T1. The task precedence dictated by the synchronization in this example must be obeyed even if there are other processors in the system that are ready to execute waiting tasks. Therefore, in this example, regardless of the number of available processors, task T1 will always wait for task T2 to complete and hence release task T1 to begin.

Notation: T2 < T1, or T2 → T1 for immediate task precedence

Task precedence can get complex, as a system with multiple tasks (each with its own dependencies) must be scheduled according to the precedence rules. Real-time system designers must understand task precedence fully before a system begins execution to ensure that real-time deadlines can be met. To do this, precedence relationships can be predetermined and represented by a graph, such as the one shown in Figure 1-11.

Figure 1-11 A directed acyclic graph helps to summarize task dependencies in a system.

In this diagram, each node on the graph represents a task. The nodes at the top must execute and complete first before threads below them can execute. These rules are repeated at each level of the graph. For instance, the scheduler for the tasks represented in Figure 1-11 will begin by dispatching task T2 to execute first. Once T2 is complete, task T1 will execute, while tasks T3 and T4 are blocked. Once T1 completes, tasks T3 and T4 will be eligible to be dispatched. If there is more than one processor ready, both tasks T3 and T4 can be scheduled to run simultaneously—this graph does not indicate precedence between them.

Timing

Real-time tasks are labeled as such because they have time-related constraints, usually to do with a deadline for processing. As a result, schedulers are concerned with many time-related parameters to ensure that a task can complete on or before its deadline. For instance, schedulers need to consider the following, per task:

• Deadline: of course, understanding the task’s deadline (relative or absolute) and its value is critical to determining if it can be scheduled feasibly.
• Period: many real-time tasks need to execute at regular time intervals. Others do not, and instead respond to events as they happen. The scheduler must distinguish each task’s type (periodic, aperiodic, and sporadic), along with the timing characteristics that might apply. We’ll discuss periodic tasks in the next section.
• Release Time: important information when scheduling periodic tasks, to determine if a set of tasks can be scheduled feasibly.
• The Variation in Releases Times: tasks vary slightly from period to period as to when they will actually be eligible for execution.
• Start Time: some tasks will not be able to execute as soon as they are released (due to locks, higher-priority tasks running, and so on).
• Execution Time: task cost functions need to know the best- and worst-case execution times for a task.

Other parameters are calculated as a result of scheduling a given set of tasks, such as:

• Lateness: the difference between a task’s actual completion time, and its deadline.
• Tardiness: the amount of time a task executes after its deadline. This is not always equal to the lateness value, as a task may have been preempted by another task, which caused it to miss its deadline.
• Laxity: the amount of time after its release time that a task can be delayed without missing its deadline.
• Slack Time: same as laxity (above). However, this term is sometimes used to describe the amount of time a task can be preempted during its execution and still meet its deadline.

Scheduling Algorithms

The three constraint sets above are directly used in scheduling algorithms to determine a feasible schedule for a set of real-time tasks. Feeding into the algorithm as parameters are the set of tasks, T, to be scheduled; the set of processors, P, available to execute them; and the set of resources, R, available for all tasks in the system.

Scheduling algorithms differ in their criterion in determining when, and for how long, a task can execute on a processor. Real-time scheduling algorithms exist to ensure that regardless of system load—or the amount of threads eligible to be dispatched—the time-critical tasks of the system get ample processing time, at the right time, to meet their deadlines. Let’s examine some of the high-level characteristics of real-time schedulers.

Preemptive Versus Non-Preemptive Scheduling

To understand scheduling algorithms, we need to agree upon some basic concepts. For instance, most operating systems allow a task to be assigned a priority. Higher-priority tasks, when ready to execute, will be given precedence over lower-priority tasks. An algorithm is said to be preemptive if a running task can be interrupted by another, higher priority task. However, there are scheduling algorithms in the real-time world that are non-preemptive [Liu00]. In this case, once a thread executes, it continues to do so until it completes its task.

Some algorithms allow a mixture of preemptive and non-preemptive tasks with classes of thread priorities, and specific support for real-time tasks. On a multi-processor system, this hybrid approach works well, since relatively long-running non-preemptive tasks do not prevent the system from performing other tasks, as long as there are more processors available than real-time tasks. The advantage to the real-time programmer is increased control over system behavior, which results in a more deterministic system overall.

Context Switching

In addition to the added determinism it provides, another reason to choose a non-preemptive scheduler is to avoid unforeseen context switches, which occur when one thread preempts another thread that’s already running. The operating system must expend processor time executing code that saves the state of the already running thread, and then resets internal data structures and processor registers to begin execution of the preempting thread so that it can begin execution. This entire preemption process is summarized as dispatching, as mentioned earlier in this chapter. The time it takes a particular system to perform this preemption task is called dispatch latency, and can interfere with a system’s ability to respond to an event by its deadline.

As a system becomes increasingly busy, with more threads competing for processing time, a considerable percentage of time can be spent dispatching threads, resulting in an additive effect in terms of dispatch latency. A system that spends more time dispatching threads than actually performing real work is said to be thrashing. Real-time systems must guarantee that even under high system load, thrashing due to context switches will not occur, or that it at least won’t interfere with the high-priority threads performing real-time processing in the system. OS kernels with hybrid preemption/non-preemption support are useful in these cases, allowing real-time processing to be guaranteed on a general-purpose system.

Dynamic and Static Scheduling

One way to control context switching while still allowing preemption is through static scheduling. For instance, in a dynamically scheduled system, tasks are dispatched on the fly as the system is running, based upon parameters that may change over time (such as task priority). All decisions as to which task to schedule at each point in time are made while the system is running, and are based on the system state at certain checkpoints. This is a common scheduling algorithm used in many popular operating systems.

With static scheduling, however, the execution eligibility of a task never changes once it’s assigned. The important scheduling parameters for each task, such as the priority, are determined when those tasks first enter the system based upon the state of the system and its current set of tasks. For instance, a static scheduling algorithm may assign a priority to a new task based on its period (defined below) relative to the periods of the other tasks in the system. In this way, a static scheduling algorithm can be used either offline or online (while the system is running).

Task Migration

Another important parameter to real-time task scheduling is the ability of a task to be executed by different processors in a multiprocessor system. For instance, in some systems, once a task begins execution on a particular processor, it cannot migrate to another processor even if it’s preempted, and another processor is idle. In this type of system, task migration is not allowed.

However, many systems do allow tasks to migrate between available processors as tasks are preempted, and different processors become available. This type of system supports dynamic task migration, as there are no restrictions placed on tasks in relation to processors. Of course, there are systems that fall in between, which support restricted task migration. One example is a system with many processors, where certain tasks are restricted to a subset of total processors within the system. The remaining processors may be dedicated to a task, or small set of tasks, for example. Another example might be that on multiprocessor/multi-board systems, the OS might limit task migration to CPUs on the same board to take advantage of locality of reference.

An example of a common real-time operating system that supports restricted task migration is Solaris. Solaris allows you to define individual processor sets, assign physical processors (or processor cores) to the defined sets, and then dedicate a processor set to a particular application. That processor set will then execute only the threads (tasks) within that application, and no others. The tasks will be able to migrate across the physical processors within the set, but not the others.

Periodic, Aperiodic, and Sporadic Tasks

Earlier in this chapter, we discussed relative and absolute deadlines, and compared the differences using some examples. A task that is released at a regular time interval is often called a periodic task. An aperiodic task has no known period; external events are generated asynchronously at unknown, often random, time intervals. To be precise, with an aperiodic task, the time interval between releases varies, but is always greater than or equal to zero:

In comparison, for a periodic task, the length of the time interval between any two adjacent releases is always constant:

Whether a thread is periodic or aperiodic can make a difference to the scheduler, as one is to do work on a known time interval, and the other is released when an event notification arrives—such as a network message—at unknown points in time. It’s obvious that if all threads in a system were periodic, it would be easier to work out a schedule than if all threads were aperiodic.

A system with multiple aperiodic threads must be carefully planned and measured as unforeseen events, and combinations of events, can occur at any time. This situation may seem orthogonal to the real-time requirement of predictability, but with careful consideration of thread priorities, it’s mathematically possible to schedule such a system. Later in this chapter, we’ll examine how the most common scheduling algorithms handle aperiodic tasks through what’s called a sporadic server.

A common example of a sporadic task in a hard real-time system is the autopilot control in an airplane’s flight control system. The human pilot may switch the autopilot on, and subsequently off, at specific points in time during a flight. It’s impossible to determine precisely when these points in time may occur, but when they do, the system must respond within a deadline. It would certainly be considered an error condition if, when the pilot switched off the autopilot, that the system took an unduly large amount of time to give the human pilot control of the aircraft.

A sporadic task is one where the length of the time interval between two adjacent releases is always greater than or equal to a constant (which itself is non-zero):

Execution Cost Functions

When scheduling real-time tasks, it’s necessary to have a mathematical basis upon which to make scheduling decisions. To do this, we need to take into account the following calculations of task execution cost:

• Total completion time, t_c = max(f_i) – min(a_i)

  This cost function calculates the overall completion time for a set of tasks by subtracting the time the last task finished from the time the first task started; note that these can be different tasks.

  

  This function returns the value 1, indicating true, if the task’s finish time exceeds its absolute deadline, or if the task’s completion time exceeds its relative deadline, depending upon the type of deadline the task has.

  

  This function calculates the total number of tasks that miss their deadline in a given real-time system with n tasks. Note: To simplify the equations and the discussion going forward, let’s define a task’s deadline, d_i, where d_i equals its absolute deadline d_i when a task has an absolute deadline, or d_i = a_i + D_i when a task has a relative deadline.

  Maximum lateness, L_max = max(f_i – d_i): this function calculates the task with the maximum lateness (missed its deadline by the greatest amount of time) using d_i as we’ve just defined it. Note that this value can be negative (when all tasks finish before their deadlines), or positive.

  

  This function calculates the average response time for a given real-time system by dividing the sum of all task completion times by the total number of tasks in the system.

Classification of Real-Time Schedulers

Let’s look now at the common types of schedulers used in real-time systems. We’ve already explored some features of scheduling algorithms in general, such as preemption, static and dynamic scheduling, and support for aperiodic and periodic tasks. Real-time systems go further in breaking down task scheduling

For instance, real-time schedulers can be broken down into two overall categories:

• Guarantee-Based: these algorithms are often static, often non-preemptive, and rigid to ensure that all tasks can complete their work by their given deadline. In dynamic systems, conservative measurements are typically used to ensure that the arrival of new tasks will not cause any existing tasks to miss their deadlines as a result. Often, these algorithms will err on the side of not allowing a new task to start if there is a chance it can disrupt the system. This is done to avoid a domino effect, where the introduction of a new task causes all existing tasks to miss their deadlines. This pessimistic approach can sometimes mean that tasks may be blocked from starting that would not have caused a problem in reality.
• Best-Effort Based: these algorithms are dynamic, more optimistic, and less conservative, when it comes to new task arrival. These schedulers are typically used in systems with soft real-time constraints, such that a missed deadline due to new task arrival is generally tolerable. They are classified a “best-effort” because these schedulers almost always allow new tasks into the system, and will do their best to ensure that all tasks complete their processing on or close to their deadlines. This results in a very responsive, efficient, real-time system that is best suited for soft real-time tasks where hard guarantees are not needed.

Within both classifications, the different algorithms must be one of the following to be considered as real-time:

• Feasible: sometimes called an heuristic algorithm, this scheduler searches for a feasible schedule whereby all tasks complete their work at or before their respective deadlines. A feasible schedule still guarantees the real-time behavior of the system. A schedule is deemed infeasible if one or more tasks within a real-time system miss a deadline.
• Optimal: an optimal scheduling algorithm is one that will always find a feasible schedule (all tasks complete on or before their deadlines) if one exists. An optimal algorithm may not always produce the best schedule, but it will always produce a schedule that meets every task’s deadline if one is possible.

To achieve a feasible schedule for tasks in a hard real-time system, there are three common approaches often used. These are:

• Clock-Driven: sometimes called time-driven, this approach schedules task execution based on known time qualities of each task in the system before the system starts. Typically, all decisions are made offline, and scheduling activities are performed during well-known points in time while the system is running. The result is a guaranteed real-time schedule with predictable execution, where the scheduler operates with very little overhead. The time-based quality(s) used to make scheduling decisions vary among the different clock-driven algorithms often used.
• Weighted Round-Robin: similar to round-robin schedulers used in time-sharing systems, this approach applies a different weight value to each task in the system based upon some criterion. Tasks with higher weight are given more execution time, or higher priority, resulting in their ability to complete their work sooner. This approach is only suitable in certain types of systems (such as those with very little interdependency amongst the individual tasks in the system).
• Priority-Driven: sometimes called event-driven, scheduling decisions are made when important system events occur (such as the release of a task, the availability of a resource, an IO event, and so on) with the intent to keep resources as busy as possible. With this approach, tasks are given a priority, placed in priority-ordered queues when released, and are then dispatched at the earliest point in time that a processor is free. No task is unduly delayed when an idle processor exists (a trait that can be a liability in some cases). Algorithms within this scheduling class are further sub-classed as fixed-priority (where task priorities and execution orders remain constant during system execution), and dynamic-priority (where tasks’ priorities can change, and all scheduling is done online while the system is running).

There are many different real-time scheduling algorithms in existence, each of which works best with certain types of systems. For instance, some schedulers analyze tasks offline, before the system begins to execute. This type of system requires all tasks be known before execution, and that no new tasks be introduced while the system is in a time-critical mode.

Other schedulers work while a system is online, and must contain additional logic to ensure that as new tasks enter the system, a new feasible schedule can be generated. In either offline or online scenarios, some schedulers work only with fixed-priority tasks, while others allow tasks’ priorities to change while the system is running.

The dynamic-priority, online schedulers tend to be the most complex and least predictable, while static-priority schedulers tend to be best for hard real-time systems. Let’s look at some common algorithms that fall into these categories, and examine their characteristics:

• First-Come-First-Served (FIFO): sometimes referred to as a first-in-first-out (FIFO) schedule, this is a dynamic-priority algorithm that schedules tasks based on their release times (execution eligibility).
• Earliest-Deadline-First Scheduler (EDF): in this dynamic preemptive scheduler, at any instant the executing task is the task with the closest deadline.
• Shortest-Execution-Time-First Scheduler (SETF): in this non-preemptive scheduler, the task with the smallest execution time is scheduled first.
• Least-Slack-Time Scheduler (LST): tasks are given higher priority based on their slack time. In this dynamic-priority algorithm, task slack time is calculated as the task’s deadline minus the current point in time minus the time required to complete processing. The task with the smallest slack time is given highest priority. Slack times—and hence priorities—are recalculated at certain points in time, and tasks are subsequently rescheduled.
• Latest-Release Time-First Scheduler (LRT): sometimes called reverse-EDF, tasks are scheduled backward, in the sense that release times are treated as deadlines, and deadlines are treated as release times. The scheduler works backwards in time and assigns tasks to processors based on their deadlines, working back to the start of execution. Think of it as reading from right to left. This scheduler performs all scheduling offline, before the system begins to execute.
• Rate-Monotonic Scheduler (RM): the inverse of a task’s period is called its rate. Used in systems with periodic tasks and static priorities, this fixed-priority preemptive algorithm assigns higher priorities to tasks with shorter periods (higher rates).
• Deadline-Monotonic Scheduler (DM): in this static, fixed-priority preemptive scheduler, the task with the shortest relative deadline is scheduled first. In a real-time system, when each task’s relative deadline equals its period, the RM and DM schedulers generate the same schedule.

In some systems, such as those that run both real-time and general-purpose applications together, a scheduling algorithm is used in conjunction with a partitioning scheme to achieve optimal system behavior. With this approach, tasks are partitioned, or grouped, based upon certain criteria. The partitioning scheme can be either fixed, or adaptive:

• Fixed-Partition Scheduling: this is a dynamic, preemptive, scheduler that assigns time budgets, in terms of total processing time allowed, to different groups of tasks called partitions. Each partition, as a whole, is bounded not to exceed its total budget of processor time (i.e., 10% of the CPU).
• Adaptive-Partition Scheduling: this is a dynamic, preemptive, scheduler where a percentage of the processor time (and sometimes system resources) are reserved for a particular group of tasks (partition). When the system reaches 100% utilization, hard limits are imposed on the non-real-time partition in order to meet the needs of the real-time tasks. When the system is less than 100% utilized, however, active partitions will be allowed to borrow from the budget reserved for other, non-active, partitions.

The intent of the Java Real-Time System is to hide this complexity from you. However, to truly appreciate its implementation, and to understand why your Java applications behave as they do within it, you should at least have a cursory understanding of the theory behind its implementation.

Both the RTSJ and Sun’s Java RTS are meant to provide real-time behavior to Java applications even on general-purpose hardware with a real-time OS. However, this is a deviation from what has been classically accepted as a real-time system. In the past, you had to write code in a language designed for real-time applications and use dedicated, special-purpose hardware to run them on. Again, to gain a true appreciation of the real-time space, and the problems that Java RTS had to overcome, let’s take a brief look at some common real-time languages and operating systems.

Multi-Core Processors and Scheduling

For the most part, modern operating systems treat individual processor cores as individual processors themselves. This is an accurate representation, as each core is a complete processor in its own right, capable of acting like an independent processor—albeit sometimes with a shared on-chip cache. Therefore, it’s not required for the OS to treat individual cores any differently than individual processors.

However, some OS kernels do take special care in scheduling threads on separate cores as opposed to separate physical processors. Solaris 10, for instance, will schedule eligible threads to distribute them across physical processors first, then across the cores of individual processors [McDougall07]. For instance, on a system with two dual-core processors, Solaris will dispatch the first thread on core 1 of processor 1, and the second thread on core 1 of processor 2 (see Figure 1-12).

Figure 1-12 The Solaris kernel attempts to balance threads across CPUs to help with heat dissipation.

Threads 3 and 4 will be dispatched to core 2 of processor 1, and core 2 of processor 2, respectively. In this case, even though thread 2 could have been scheduled on core 1 of processor 1, this would upset the balance. The intent is to distribute running threads across physical processors and their cores evenly. For instance, on a system with four quad-core processors, with sixteen dispatched and running threads, the thread-to-processor/core distribution should look as shown in Figure 1-13.

Figure 1-13 Solaris kernel threads spread equally across all available cores. From this point onward, additional threads will be scheduled on the next available (free) core.

This distribution of threads over available cores has little bearing on our real-time discussion, although it’s important to know that it does occur.

Real-Time Operating Systems

To meet the needs of the most demanding real-time systems, specialized operating systems are available. Besides having the required features to support predictable task execution for time-critical applications, the real-time OS will also have its own real-time constraints. For example, core scheduling and other OS-specific functionality must behave in predictable, measurable, ways, with high efficiency and low latency. In other words, the OS and its scheduling activities must never contribute to unbounded task latency, or be unpredictable in any sense.

A real-time OS has thread schedulers built-in that support real-time systems. Most often, these operating systems allow programmers to control the computer hardware at the lowest level, including processor interrupts, physical memory access, and low-level input/output (I/O) processing. This is done so that the real-time application developer can remove as much of the non-deterministic behavior and end-to-end latency found in general-purpose operating systems.

Many real-time operating systems target embedded systems with dedicated functionality and limited hardware resources. This means that these systems are not meant to be general-purpose systems, and using a real-time OS proves to be a valuable tool in these cases. However, as mentioned before in this chapter, with the continuing advances in hardware capabilities at lower cost, the need for specialized hardware and operating systems has diminished significantly. A dedicated real-time OS comes at a high cost relative to the general-purpose operating systems available today. Many argue that the state of the industry has reached a point that this extra cost is no longer justified. However, recall that while adding additional, more powerful, hardware can help improve raw performance and throughput, it almost never makes an unpredictable system behave predictably.

Regardless, there are instances, such as with embedded systems, where a real-time OS continues to be the only option. While this book does not go into detail regarding real-time operating systems, it’s important to know that they do exist and serve a specialized purpose. Real-time applications typically require the same set of services from the OS—such as disk IO, networking support, a file system, user IO, and so on—as general purpose applications do. However, the real-time application requires its OS to make guarantees that are both measurable and predictable.

RT-POSIX Operating System Extensions

With the intent to unify the real-time application and OS space, the Real-Time Portable Operating System based-on Unix (RT-POSIX 1003.1b) standard was created. POSIX is a standard that has been very successful and widely adopted in a wide-range of OS implementations, for both mission-critical and general-purpose computing. RT-POSIX defines an extension to it that addresses the needs of hard and soft real-time systems.

The standard defines a minimum set of features that a compliant OS must implement. Additional features can be implemented, provided that they do not conflict with or hereby negate the required features. For example, RT-POSIX-compliant operating systems must have the following traits:

• Preemption: true task preemption must be supported using task priority rules that are strictly obeyed.
• Priority Inversion Control: although it cannot guard well against deadlocks, priority inheritance ensures that lower-priority threads will never be able to block higher-priority threads due to classic priority inversion.
• Periodic, Aperiodic, and Sporadic Threads: the POSIX standard requires only processes be implemented. For real-time applications, threads of different priority may need to run to perform a task. For this reason, the RT-POSIX standard requires the OS be able to schedule tasks down to the thread level, and that applications be able to create and destroy those threads. Underlying OS threads must be able to support the various types of task release events common to real-time applications. For instance, a thread should be able to specify its period and then rely on the OS to wake it up at precise time boundaries that match that period. Simply performing a call to “sleep” from within the task’s code (as is done in a non-real-time OS) is not sufficient.
• High-Resolution Timers: such timers should be made available to real-time applications, as well as the real-time OS itself so that it can dispatch threads with as little latency and jitter as possible. For example, an OS scheduler with a 10-millisecond tick size will, at best, experience up to 10 milliseconds latency during thread dispatch processing. In general, the larger the tick count, the higher the max latency and jitter values will grow. Both are qualities to be avoided in real-time systems. The RT-POSIX standard states that up to 32 timers per process must be supported, and that timer overruns (when a timer goes beyond its chosen duration) be recorded.
• Schedulers: the kernel needs to support both deadline-monotonic and rate-monotonic deadline scheduling in order to support the common real-time scheduling algorithms such as weighted round-robin, fixed-priority, and earliest-deadline-first scheduling. The type of scheduler used can be defined down to the thread level, where two threads of the same process may be scheduled differently.
• Scheduled Interrupt Handling: the ability to create a preemptable task that processes low lever device interrupts. This is sometimes called a software interrupt. In contrast, a general-purpose OS typically handles these events completely itself, making the data or status available through some other means.
• Synchronous and Asynchronous IO: synchronous IO operations provide real-time tasks more control over IO-related tasks, such as file and network operations. Asynchronous IO allows the system to progress task execution while IO is occurring, or waiting to occur. For instance, a task that reads a network packet can process the packet’s payload even while it waits for the next packet to arrive.
• Inter-Task Communication: to facilitate predictable, low-latency, communication between tasks, queues should be provided at the OS level. This also ensures fast, consistent, and measurable performance, with support for message prioritization. These queues are sometimes made available to tasks both local to the system, and remote. Regardless, message delivery must be prioritized, and at least eight prioritized signals are supported per process.
• Priority Inheritance: to guard against deadline misses due to priority inversion (where a lower-priority task’s priority is raised above that of a higher-priority task) priority inheritance needs to be implemented at the kernel level, or at least emulated.
• Resource Quotas: the ability to monitor and control the usage of system resources such as memory and processor time to ensure the system behaves in a predictable way even when under heavy load.
• Memory Sharing: shared memory (between processes) and memory-mapped files must be supported.
• Memory Locking: applications must be able to control the memory residency of their code sections through functions that will either lock all of its code, or only the portions specified.
• Real-Time File System: file systems that ensure files are made up of contiguous disk blocks, pre-allocate files of fixed size to be used on-demand while the system is running, and offer sequential access, provide the most predictable behavior and timing characteristics.
• Synchronization: OS primitives that support efficient resource sharing between tasks with priority inheritance, and ceiling priority (both of which are protocols to control or avoid thread priority inversion).