The Real-Time Specification for Java (RTSJ), also known by it's Java Specification Request1 number (JSR-01), was formalized in June of 2000. Since then a number of commercial implementations have become available.

The RTSJ approaches the solution to the problem of writing real-time code from a different direction than other available software development platforms such as a typical RTOS (real-time operating system) application programming interface (API).

RTSJ embraces the notion of real-time scheduling theory as a fundamental principle for the development of programs which have temporal correctness requirements and as an environment which enhances the ability of developers to write more portable real-time code.

This article will explain the scheduling subsystem, or framework, in RTSJ 1.0.1(b) and some new features scheduled for RTSJ 1.1 and show how to use the features in programs.

The RTSJ proposes a new system model for the development and deployment of applications which have temporal correctness requirements. Understanding this system model is the first step toward understanding the scheduling framework in the RTSJ, hence, we'll first spend some time on it before delving further.

The second fundamental construct we need to understand is that the RTSJ abstracts the unit of schedulability above that with which we are most all familiar, i.e., the thread. In the RTSJ things that are scheduled are instances of the Java interface, Schedulable.

The RTSJ abstracts the unit of schedulability in this way to allow the application to imbue these schedulable objects with values that characterize their expected behavior and determined requirements with respect to time. But more importantly this abstraction allows more than just threads to come under the control of the scheduler, e.g., event handlers in the RTSJ no longer just execute whenever, they execute under the control of the scheduler.

Thus in the RTSJ event handlers are a schedulable entity rather than, as in a typical RTOS, an unschedulable entity. Once an application creates its initial set of instances of Schedulable with the appropriate characteristics the application may put those into what we call the 'feasibility' set.

The feasibility set is an abstract set which simply holds the set of things which the scheduler manages. The set also embodies a feasibility algorithm, such as rate monotonic assignment (RMA) or the deadline monotonic algorithm (DMA).

Given the values of the characteristics given to the instances of Schedulable (from here on let's shorten this to the informal, Schedulable or Schedulables) in the set the feasibility algorithm can determine if all of the Schedulables will meet their given deadlines. There are, of course, a lot of details about how the feasibility algorithm actually can do such a thing and we'll cover some of those later.

In the late 1990's it became apparent to a number of us in the field that the problem of software development for real-time and embedded systems had gone beyond the simple and looked to be on a path of exponentially increasing complexity, arising from increases in both size and required features.

Clearly, the state-of-the-art in software development for these systems needed a productivity/abstraction boost. At this time the Java programming language and runtime crossed the threshold from an interesting experiment to the defacto development platform for desktop and enterprise applications. The Java environment offered significant productivity increases for development of large, complex, and network-oriented software artifacts over other language choices.

Thus, a growing number of people began to consider the Java language as a possible choice for large and complex software development projects whose requirements included either embedded hardware target platforms and/or timeliness. Unfortunately, some fundamental features of the Java language precluded the predictable execution of application logic.

Some historical backround
In 1998 a number of us began to build momentum for a formal way in which the Java language could be extended to support such applications. The Java Community Process (JCP) was created by Sun Microsystems and Java Specification Request 01 was started in early 1999. The JSR-01 expert group identified and followed a number of fundamental principles2.

We need not cover all here except to note that JSR-01 requires compatibility with the existing Java Language Specification (JLS) as defined by the JCP. The expert group always followed the path of tightening existing semantics in the JLS as opposed to requiring new semantics not currently supported by the JLS. The RTSJ redefined seven areas of the JLS:

1) Threads, Dispatching, and Scheduling
2) Memory Management / Garbage Collection
3) Synchronization and Resource Sharing
4) Asynchronous Event Handling
5) Asynchronous Transfer of Control
6) Asynchronous Thread Termination
7) Physical Memory Access

Of the seven only a portion of the first, scheduling, is the primary focus of this article. To fully understand the scheduling subsystem though we'll also look briefly at the RTSJ system model and thread contexts.

Below we quote directly from RTSJ 1.0.1(b) the requirements of the scheduling subsystem of the RTSJ:

1) Allow the definition of schedulable objects.
2) Manage the assignment of execution eligibility to schedulable objects.
3) Perform feasibility analysis for a set of schedulable objects.
4) Control the admission of new schedulable objects to the feasibility set.
5) Manage the execution of instances of the AsyncEventHandler and RealtimeThread classes.
6) Assign release characteristics to schedulable objects.
7) Assign execution eligibility values to schedulable objects.
8) Manage the execution of groups of schedulable objects that collectively exhibit additional release characteristics.

System Model, Memory Model, and Threads
Arising out of the RTSJ guiding principles and observations of trends in development of software artifacts for embedded and real-time systems is the RTSJ System Model.

(The terms soft and hard real-time are used in their formal sense. First, consider logic which has a temporal correctness condition, e.g., a deadline. When referring to logic which has a hard real-time requirement we will mean that the requirement is that the logic must never complete after the given deadline but if it does the system is considered to be in an abnormal mode. When referring to logic which has a soft real-time requirement we will mean that the logic is allowed to complete after the given deadline in explicitly defined ways.)

This model supports the execution of non-, soft-, and hard real-time logic within the same application, on the same Java Virtual Machine (JVM), and on the same computing machine. These three execution contexts are supported by three different thread types:

java.lang.Thread(JLT): Used for backward compatibility and all logic which does not require timeliness. Pre-existing Java applications will execute unmodified on an RT-JVM in this context.

javax.realtime.RealtimeThread(RTT): Used for logic which has soft real-time requirements or logic which has maximum latency requirements which are larger than the maximum interference of the garbage collector (GC). For RTSJ implementations which include a real-time garbage collector (RTGC) logic within this context uses the RTGC for automatic memory management, i.e., reclamation of invisible objects. Logic executing in this context must follow the assignment rules (see memory model later).

javax.realtime.NoHeapRealtimeThread(NHRT): Used for logic which has hard real-time requirements. Logic executed in this context must also follow the assignment rules and in addition is not allowed to manipulate (including even read) a reference to an object which had been allocated on the regular Java heap.

The RTSJ introduces, to Java applications, the notion of allocating objects in areas of memory other than the regular Java heap (Heap from now on). Two new memory areas are defined, Immortal Memory (IM), and Scoped Memory (SM).

The lifetime, when objects are considered live or dead, of objects allocated in these memory areas is managed by mechanisms different that that used for the Heap.

[The lifetime of an object, obliquely, refers to the mechanism by which the assertion: "the application logic will never use a particular object again" can be made. E.g., the lifetime of an object controlled by a manual memory management mechanism is from the point in time the application creates it until the application logic forcibly terminates it, e.g., with a call to a deallocation function such as free().]

Typical garbage collected language runtimes, such as regular Java, use visibility (the existence of a reference) to determine when an object can no longer be referenced by application logic. If no reference to an object exists in application logic then the application can no longer 'see' that object and the GC can collect it.)

Objects allocated in IM never die. They can be referenced by all logic at any time without concern. Objects allocated in an SM area live until no thread is executing in the static/dynamic programmatic scope into which the SM had been assigned. Of course, this last statement requires a bit more explanation.

The RTSJ also introduces the idea of a current memory area (CMA). All executing logic, at any particular point in time, has associated with it a memory area, one of: the Heap, the Immortal Memory Area, or a Scoped Memory Area.

An object created as the result of the execution of new is allocated in the CMA at the time new is executed. When an application starts the CMA is the Heap, as it is for any regular Java program. Application logic may change its CMA in various ways, all of which require more detail then we can get into in this class.

For now we'll just give a couple of ground rules for using these different memory areas. NHRTs must at all times have as their CMA either the IM area or an SM area. RTTs may have all three types of memory areas as their CMA, whereas JLTs may have only the Heap or the IM as their CMA.

Schedulable, Scheduler, and Parameter Objects
The Java language includes a concept known as an interface. An interface is a classlike definition but includes only method signatures. Class definitions are allowed to Implement an interface.

A Class definition which implements an interfaces must include all of the method signatures in the interface with a complete code body for each. The fundamental unit of schedulability in the RTSJ is an instance of the interface Schedulable. All RTSJ implementations will include four class definitions which implement Schedulable: RTT, NHRT, AsyncEventHandler (AEH), and BoundAsyncEventHandler (BAEH).

All instances of the interface Schedulable are visible to and managed by the scheduler. The scheduler itself is represented by the abstract class, Scheduler. Application logic interacts with the scheduler via methods on one of the concrete subclasses of Scheduler, e.g., PriorityScheduler. The priority scheduler is required in all implementations, however, particular applications may include additional schedulers.

When the application code creates instances of Schedulable, via the constructors of one of the four Schedulables given above, the schedulable can be given a set of characteristics which both define and mandate certain behavior.

Release characteristics, embodied in an instance of the class ReleaseParameters, indicate to the runtime system whether the Schedulable is released periodically, sporadically, or aperiodically.

(Classic real-time scheduling theory defines three patterns of releases for tasks. A release is considered a point in time at which the said task becomes available for dispatch to the processor.

Let t_i be the time of the i^-th release of task T.

T is periodic if t_i+1-t_i=C₀, i=1...+,C₀>0
T is sporadic if t_i+1-t_i is more than or equal to C₁, i=1...+,C₁>0
T is aperiodic if t_i+1-t_i more than or equal to 0...+

Instances of ReleaseParameters also include the cost per release, start time, handlers for missed deadlines or cost overruns. The cost values is used by both the cost enforcement algorithms and feasibility tests, both explained in subsequent sections. (Cost is the time taken for one release of a task to execute to completion on a uniprocessor.)

Instances of ReleaseParameters also include the cost per release, start time, handlers for missed deadlines or cost overruns. The cost values is used by both the cost enforcement algorithms and feasibility tests, both explained in subsequent sections, later.

Traditional priority is the dispatch time metric used by the required priority scheduler. This scheduler as well as any other scheduling algorithms may define a subclass of SchedulingParameters to communicate to the scheduler any values associated with the scheduler necessary for the scheduling algorithm to do its job. The RTSJ defines PriorityParameters for the required priority scheduler which simply holds the priority of the Schedulable.

Cost Enforcement
Although optional in RTSJ implementations, cost enforcement is probably the single most important feature for portability and analysis in the scheduling subsystem. As mentioned above, cost, is a value given to the system via a ReleaseParameters object and is an estimate of how much processor time will be used by the Schedulable per release.

(When we were designing the RTSJ we didn't want to require features that would be very difficult to implement in typical real-time operating systems because that would reduce the likelihood that these vendors would commit to RTSJ implementations (all standards efforts are, after all, compromises). Cost enforcement is such a feature. It is difficult to implement. However, we at Sun feel that no RTSJ implementation is complete without it.)

Cost enforcement, when available, turns this informative exchange into a contract between the application and the system. The system will allow the Schedulable no more than cost time units of processor time per release. If the Schedulable attempts to use more than cost time units per a release then the system will de-schedule the Schedulable and not reschedule it until the start of the next release time (for periodics this is the start of the next period).

Without cost enforcement the validity of any installed feasibility test depends completely on the cooperation and correct behavior of application logic. If, by chance, underestimation, or whatever, application logic exceeds its given cost in any release the consequences can be dramatic and far reaching.

Essentially, any other time-critical piece logic in the system could miss its deadline through no action of its own. Looking at this another way, cost overruns cause non-local effects, something all software developers fear, and in our case these non-local effects can easily cause system failure.

We use system failure here to mean that a piece of application logic which has hard real-time requirements, i.e., it must meet every deadline, fails to complete its work before its deadline. Without cost enforcement the system is at the mercy of the application and the system can do nothing to prevent the failure. However, if cost is enforced or honored then the system, through a feasibility test, can determine if all tasks will meet their deadlines. The feasibility test is a component of the scheduler.

Feasibility
Feasibility (schedulability is a synonymous term) is how the real-time community describes a sequence of releases of a set of tasks that ensures that all releases of all tasks meet their deadlines. To further understand this concept we'll first need to define, precisely, the scheduling problem. First, let's define our system model.

Consider a set of tasks, T_i each represented by the tuple, (C_i ,I_i, D_i)where C_i is the cost per release, I_i is the interval between releases, and D_i is the deadline for task T_i.

Each task also has a set of release times, call them, R_tk which represents the k^th release of task T_i . The scheduling problem is finding a sequence of R_jk such that R_+1ki-R_ikI_i and the completion time of the release started at R_ik completes before R_ik+ D_i and uses no more than C_i time units of the processor.

In a system where i=1 this is pretty simple. It's easy to see that if C_iI_i and D_i:I_ii and R_i+1k-R_ikI_i, i=1. ..+ the system is feasible, i.e., all releases of the task will meet their deadlines.

However, as we start to look at systems with more than one task determining feasibility becomes more difficult. In the general case solving this problem is NP-Hard; no know algorithm can find the optimal solution in polynomial time. But, fortunately, there are some restrictions and assumptions about the system that can be made which allow a closed form computation to determine feasibility.

The most widely known feasibility test is named the rate monotonic priority assignment algorithm (RMA). There are many others, such as the deadline monotonic algorithm and earliest deadline first. We'll look at only RMA, and how an RMA scheduler would be implemented in the RTSJ, in this class.

The system model we'll use is a set of n tasks T_i, i=1. ..n represented by the tuple (C_i,P_i) where C_i is the cost per period and P_i is the period, and a set of system priorities, p_j, j=1. ..m,mn where the dispatch eligibility of a task with priority p_j is greater than that of a task with priority p_j+1. The deadline for each release in this model is considered to be the start of the next period .

First, put the task in the order of their increasing period, from  T_{i1, ...,}  T_ik, ... ,T_in where the period of T_ik is less than or equal to the period of T_ik+1. Now assign priority P_k to task T_ik. This assignment pattern is the assignment of decreasing priorities to tasks as their periods monotonically increase, hence the name.

It has been proven that if,

then all releases of all tasks will complete before the end of the period (deadline) in which they are released. We've shown only a simple system model. Please see the Liu and Layland paper at the end of this article for the full model with all restrictions and the proof. This formula is actually straightforward to understand, but, a couple of examples may help. Lets first consider a set of three tasks with costs and periods of:

We see that this simple task set is not feasible because 0.80.78 is false. Let's just change one of the periods a bit and see what happens. If the new set of costs and periods is:

And, the right hand side is still 0.78, then the task set is now feasible because 0.630.78 is true. If priorities are assigned to these three tasks such that the tasks had execution eligibility in the following order
T₃>T₁>T₁ then, because the feasibility formula computation returned true, we would be sure that all releases of all three tasks would always complete before the start of the next period (deadline).

Another interesting observation is that in the definition of the tasks above we did not indicate the units (milliseconds, microseconds, etc.) for the cost and period values. It doesn't matter as long as all are in the same units.

This leads us to the realization that feasibility is independent from the magnitude of the costs and periods of the tasks in the system The cost and periods could have represented days and, still, the first example would still not be feasible.

The RTSJ accommodates the notion of feasibility analysis through its abstract concept of the feasibility set. Here's the general idea. During the initialization phase of an application instances of Schedulable, RTTs, NHRTs, AHEs, and BAEHs are created.

During their creation they are given the appropriate release and scheduling characteristics. In turn each is, abstractly, added to the feasibility set. The method used to add them to the set will, typically, execute the feasibility (e.g., RMA) formula on all of the Schedulables in the set plus the new one being added. The result of the computation is then returned to the application as a boolean (true or false).

If the return value is true then the application can be certain that all of the releases of all of the Schedulables will meet their deadlines. Additionally, note, that the application need not know anything about the underlying idiosyncrasies of the particular RT-JVM or the underlying OS. The separation of concerns is a fundamental goal of the RTSJ. We believe that it is the province of the RTSJ implementers to understand such idiosyncrasies and incorporate them into the computation of feasibility.

Sporadic and Aperiodic Schedulables
We'll briefly discuss how the RTSJ accommodates Schedulables which have a release pattern that is either sporadic or aperiodic. Recall that a sporadic release pattern means the the interval between release is given as a minimum, i.e., two subsequent releases will never occur closer than I time units.

These are handled just as periodics with the minimum interarrival time used as the period. There is some over-provisioning because, by definition, the sporadic Schedulables will not all be released as often as their given minimum interarrival times, but, in case they are, there will be processor cycles available to ensure that they also all meet their deadlines.

Aperiodic Schedulables are much more problematic. Recall that the aperiodic release pattern means that two, or infinitely more, releases can occur with 0 time units between each release. Of course in practice this is impossible, but, the theory has to take care of this boundary case. In theory a single aperiodic requires infinite computing power.

Obviously something has to be done. We typically define a periodic task9 whose job is to execute all aperiodic tasks that arrive before its release time. (In the literature this task has been given the unfortunate name of, sporadic server. I say unfortunate because it can be a point of confusion for people new to real-time scheduling theory discussions.

It simply means that the task serves aperiodic tasks by executing them during its own execution for each release of itself. And, since it may not need to execute once every period (because no aperiodic task needs to be executed) it is properly classified as a sporadic release pattern.)

The RTSJ supports this theoretical notion through instances of ProcessingGroupParameters (PGP). These are parameter objects that have the same fields as a periodic parameters object but have a different meaning.

This meaning is: All aperiodic Schedulables with a reference to a single instance of PGP constitute a processing group. Also, PGPs can be added to the feasibility set as a Schedulable themselves. The PGP has a cost and a period and is handled by the feasibility analysis just like a periodic task.

Releases of these aperiodic Schedulables will be executed in each period of the PGP up to cost time units. PGPs therefore collect aperiodic Schedulables and execute them periodically in a way that can be understood by the feasibility analysis.

Conclusion
We've seen how the RTSJ first abstracts the unit of schedulability into a Java interface names Schedulable. All instances of Schedulable (such as RTTs, NHRTs, AEHs, and BAEHs) may participate in the feasibility analysis. Schedulables are created and given a set of characteristics which define and mandate their execution behavior with respect to time.

By relying on the RTSJ feasibility analysis an application can obtain some measure of portability among different hardware, OS, and RT-JVM platforms. However, the estimation of the cost value remains a difficult issue, not only for RTSJ application but for all real-time applications.

The scheduling subsystem of the RTSJ greatly insulates the application and application developer from the idiosyncrasies of the underlying RT-JVM, OS, and hardware. Applications need only create instances of Schedulable, give them appropriate characteristics, add them to the feasibility set, and react to the result of the feasibility analysis.

Greg Bollella is distinguished engineer and principle investigator for Real-Time Java at Sun Microsystems. He has been interested in algorithms and software architectures that support the deterministic execution of logic within general-purpose operating systems and virtual machines since 1992.

References:
1. For more information about the Java Community Process, the organization by which the community evolves the Java Platform, go to http://jcp.org.
2. Liu, C.L. and Layland J.W., "Scheduling Algorithms for Multiprogramming in a Hard Real- Time Environment", JACM, Vol.20(1), 1973, pp. 46-61

This article is excerpted from a paper of the same name presented at the Embedded Systems Conference Boston 2006 and is used with permission.For more information, please visit www.embedded.com/esc/boston/ Real Time Java Resources on Embedded.com