The Scheduling Subsystem For Realtime Java: Explained - Embedded.com

The Scheduling Subsystem For Realtime Java: Explained

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

The RTSJapproaches thesolution to the problem of writing real-time code from a differentdirection than other available software development platforms such as atypical RTOS (real-timeoperating system) applicationprogramming interface (API) .

RTSJ embraces the notion of real-time schedulingtheory as a fundamental principle for the development of programs whichhave temporal correctness requirements and as an environment whichenhances the ability of developers to write more portable real-timecode.

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

The RTSJ proposes a new system model for the development anddeployment of applications which have temporal correctnessrequirements. Understanding this system model is the first step towardunderstanding the scheduling framework in the RTSJ, hence, we'll firstspend some time on it before delving further.

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

The RTSJ abstracts the unit of schedulability in this way to allowthe application to imbue these schedulable objects with values thatcharacterize their expected behavior and determined requirements withrespect to time. But more importantly this abstraction allows more thanjust threads to come under the control of the scheduler, e.g., eventhandlers in the RTSJ no longer just execute whenever, they executeunder the control of the scheduler.

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

The feasibility set is an abstract set which simply holds the set ofthings which the scheduler manages. The set also embodies a feasibilityalgorithm, such as ratemonotonicassignment (RMA) or the deadlinemonotonic algorithm (DMA) .

Given the values of the characteristics given to the instances of Schedulable (from here on let'sshorten this to the informal, Schedulable or Schedulables) in the setthe feasibility algorithm can determine if all of the Schedulables willmeet their given deadlines. There are, of course, a lot of detailsabout how the feasibility algorithm actually can do such a thing andwe'll cover some of those later.

In the late 1990's it became apparent to a number of us in the fieldthat the problem of software development for real-time and embeddedsystems had gone beyond the simple and looked to be on a path ofexponentially increasing complexity, arising from increases in bothsize and required features.

Clearly, the state-of-the-art in software development for thesesystems needed a productivity/abstraction boost. At this time the Javaprogramming language and runtime crossed the threshold from aninteresting experiment to the defacto development platform for desktopand enterprise applications. The Java environment offered significantproductivity increases for development of large, complex, andnetwork-oriented software artifacts over other language choices.

Thus, a growing number of people began to consider the Java languageas a possible choice for large and complex software developmentprojects whose requirements included either embedded hardware targetplatforms and/or timeliness. Unfortunately, some fundamental featuresof the Java language precluded the predictable execution of applicationlogic.

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

We need not cover all here except to note that JSR-01 requirescompatibility with the existing Java Language Specification (JLS) asdefined by theJCP. The expert group always followedthe path of tightening existing semantics in the JLS as opposed torequiring new semantics not currently supported by the JLS. The RTSJredefined seven areas of the JLS:

1) Threads, Dispatching,and Scheduling
2) Memory Management / GarbageCollection
3) Synchronization and ResourceSharing
4) Asynchronous Event Handling
5) Asynchronous Transfer ofControl
6) Asynchronous ThreadTermination
7) Physical Memory Access

Of the seven only a portion of the first, scheduling, is the primaryfocus of this article. To fully understand the scheduling subsystemthough we'll also look briefly at the RTSJ system model and threadcontexts.

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

1) Allow the definition ofschedulable objects.
2) Manage the assignment ofexecution eligibility to schedulableobjects.
3) Perform feasibility analysisfor a set of schedulable objects.
4) Control the admission of new schedulable objects to the feasibilityset.
5) Manage the execution ofinstances of the AsyncEventHandler andRealtimeThread classes.
6) Assign releasecharacteristics to schedulable objects.
7) Assign execution eligibilityvalues to schedulable objects.
8) Manage the execution ofgroups of schedulable objects thatcollectively exhibit additional release characteristics.

System Model, Memory Model, andThreads
Arising out of the RTSJ guiding principles and observations of trendsin development of software artifacts for embedded and real-time systemsis the RTSJ System Model.

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

This model supports the execution of non-, soft-, and hard real-timelogic within the same application, on the same Java VirtualMachine (JVM ), and onthe same computing machine. These three execution contexts aresupported by three different thread types:

java.lang.Thread(JLT) : Used for backward compatibilityand all logic which does not require timeliness. Pre-existing Javaapplications 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 hasmaximum latency requirements which are larger than the maximuminterference of the garbagecollector(GC) . For RTSJ implementations which include a real-time garbagecollector (RTGC) logic within this context uses the RTGC for automaticmemory management, i.e., reclamation of invisible objects. Logicexecuting in this context must follow the assignment rules (see memorymodel later).

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

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

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

[The lifetime of an object,obliquely, refers to the mechanism by which the assertion: “theapplication logic will never use a particular object again” can bemade. E.g., the lifetime of an object controlled by a manual memorymanagement mechanism is from the point in time the application createsit until the application logic forcibly terminates it, e.g., with acall 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 anobject can no longer be referenced by application logic. If noreference to an object exists in application logic then the applicationcan no longer 'see' that object and the GC can collect it.)

Objects allocated in IMnever die. They can be referenced by all logic at any time withoutconcern. Objects allocated in an SM area live until no thread isexecuting in the static/dynamic programmatic scope into which the SMhad been assigned. Of course, this last statement requires a bit moreexplanation.

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

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

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

Schedulable, Scheduler, andParameter Objects
The Java language includes a concept known as an interface. Aninterface is a classlike definition but includes only methodsignatures. Class definitions are allowed to Implement an interface.

A Class definition which implements an interfaces must include allof the method signatures in the interface with a complete code body foreach. The fundamental unit of schedulability in the RTSJ is an instanceof the interface Schedulable. All RTSJ implementations will include four class definitions whichimplement 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 isrepresented by the abstract class, Scheduler .Application logic interacts with the scheduler via methods on one ofthe concrete subclasses of Scheduler ,e.g., PriorityScheduler . Thepriority scheduler is required in all implementations, however,particular applications may include additional schedulers.

When the application code creates instances of Schedulable , via the constructorsof one of the four Schedulables given above, the schedulable can begiven a set of characteristics which both define and mandate certainbehavior.

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

(Classic real-time scheduling theory defines three patterns ofreleases for tasks. A release is considered a point in time at whichthe 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 0 ,i=1…+,C 0 >0
T is sporadic if t i+1 -t i ismore than or equal to C 1 ,i=1…+,C 1 >0
T is aperiodic if t i+1 -t i morethan or equal to 0…+

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

Instances of ReleaseParameters also include the cost per release, start time, handlers for misseddeadlines or cost overruns. The cost values is used by both the costenforcement algorithms and feasibility tests, both explained insubsequent sections, later.

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

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

(When we were designing the RTSJwe didn't want to require features that would be very difficult toimplement in typical real-time operating systems because that wouldreduce the likelihood that these vendors would commit to RTSJimplementations (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 withoutit .)

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

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

Essentially, any other time-critical piece logic in the system couldmiss its deadline through no action of its own. Looking at this anotherway, cost overruns cause non-local effects, something all softwaredevelopers fear, and in our case these non-local effects can easilycause system failure.

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

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

Consider a set of tasks, Ti each represented by thetuple, (Ci ,Ii , Di )where Ci is the cost per release, Ii is the interval betweenreleases, and Di is the deadline for task Ti .

Each task also has a set of release times, call them, Rtk which represents the kth release of task Ti . Thescheduling problem is finding a sequence of Rjk such that R+1ki -Rik Ii and the completion time of the release started at Rik completes before Rik + Di and uses no more than Ci time units of the processor.

In a system where i=1 this is pretty simple. It's easy to seethat if Ci Ii and Di :Ii iand Ri+1k -Rik Ii , i=1. ..+ thesystem is feasible, i.e., all releases of the task will meet theirdeadlines.

However, as we start to look at systems with more than one taskdetermining feasibility becomes more difficult. In the general casesolving this problem is NP-Hard; no know algorithm can find the optimalsolution in polynomial time. But, fortunately, there are somerestrictions and assumptions about the system that can be made whichallow a closed form computation to determine feasibility.

The most widely known feasibility test is named the ratemonotonic 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 implementedin the RTSJ, in this class.

The system model we'll use is a set of n tasks Ti ,i=1. ..n represented by the tuple (Ci ,Pi ) where Ci is the cost per period and Pi is the period, and a set ofsystem priorities, pj , j=1. ..m,mn where the dispatcheligibility of a task with priority pj is greater than thatof a task with priority pj+1 . The deadline for eachrelease 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 Ti1, …,  Tik , … ,Tin where the period of Tik is less than or equal to the period of Tik+1 . Now assignpriority Pk to task Tik . This assignment patternis the assignment of decreasing priorities to tasks as their periodsmonotonically increase, hence the name.

It has been proven that if,

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

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

And, the right hand side is still 0.78, then the task set isnow feasible because 0.630.78 is true. If priorities are assigned tothese threetasks such that the tasks had execution eligibility in the followingorder
T3 >T1 >T1 then, because thefeasibility formula computation returned true, wewould be sure that all releases of all three tasks would alwayscomplete before the start of the next period (deadline).

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

This leads us to the realization that feasibility isindependent from the magnitude of the costs and periods of the tasks inthe 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 analysisthrough its abstract concept of the feasibility set. Here's the generalidea. During the initialization phase of an application instances ofSchedulable, RTTs, NHRTs, AHEs, and BAEHs are created.

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

If the return value is true then the application can be certainthat all of the releases of all of the Schedulables will meet theirdeadlines. Additionally, note, that the application need not knowanything about the underlying idiosyncrasies of the particular RT-JVMor the underlying OS. The separation of concerns is a fundamental goalof the RTSJ. We believe that it is the province of the RTSJimplementers to understand such idiosyncrasies and incorporate theminto the computation of feasibility.

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

These are handled just as periodics with the minimuminterarrival time used as the period. There is some over-provisioningbecause, by definition, the sporadic Schedulables will not all bereleased as often as their given minimum interarrival times, but, incase they are, there will be processor cycles available to ensure thatthey also all meet their deadlines.

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

Obviously something has to be done. We typically define aperiodic task9 whose job is to execute all aperiodic tasks that arrivebefore its release time. (In the literature this task has been giventhe unfortunate name of, sporadic server. I say unfortunate because itcan be a point of confusion for people new to real-time schedulingtheory discussions.

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

The RTSJ supports this theoretical notion through instances ofProcessingGroupParameters (PGP) .These are parameter objects that havethe same fields as a periodic parameters object but have a differentmeaning.

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

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

Conclusion
We've seen how the RTSJ first abstracts the unit ofschedulability into a Java interface names Schedulable. All instancesof Schedulable (such as RTTs,NHRTs, AEHs, and BAEHs) may participatein the feasibility analysis. Schedulables are created and given a setof characteristics which define and mandate their execution behaviorwith respect to time.

By relying on the RTSJ feasibility analysis an application canobtain some measure of portability among different hardware, OS, andRT-JVM platforms. However, the estimation of the cost value remains adifficult issue, not only for RTSJ application but for all real-timeapplications.

The scheduling subsystem of the RTSJ greatly insulates theapplication and application developer from the idiosyncrasies of theunderlying RT-JVM, OS, and hardware. Applications need only createinstances of Schedulable, give them appropriate characteristics, addthem to the feasibility set, and react to the result of the feasibilityanalysis.

GregBollella is distinguishedengineer and principleinvestigator for Real-Time Java at SunMicrosystems. He has beeninterested in algorithms and software architectures that support thedeterministic execution of logic within general-purpose operatingsystems and virtual machines since 1992.

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

This article is excerpted from apaper of the same namepresented at the Embedded Systems Conference Boston 2006 and is usedwith permission.For more information, please visit www.embedded.com/esc/boston/Real Time Java Resources on Embedded.com

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.