This discussion is archived
3 Replies Latest reply: Jan 7, 2010 3:43 PM by 807557 RSS

Scheduling in Real-Time Java

807557 Newbie
Currently Being Moderated
Hello,

I have some questions concerning how scheduling in fact is intended to be performed in a RTSJ based Real-Time Java System.

As far as I understood, RTSJ requires pre-emptive priority-based dispatching of Schedulable objects.
This means that the execution eligibility of a schedulable entity is mainly its priority.
That causality is reflected within the specification with the (one-and-only specified) PriorityScheduler, which is the base scheduler for actual Real-Time Java applications.
Furthermore, there is a notion of extensibility of that PriorityScheduler described by RTSJ,
in order to provide further scheduling mechanims and feasibility analysis algorithms (please correct me if there are any wrong assumptions).

This is the point, where everything becomes really weird to me ...

As far as I could investigate, in most RTSJ implementations based on a POSIX compliant system underneath (like Java RTS does on RTLinux or Solaris)
each (Realtime)JavaThread is mapped 1-to-1 to a light-weight process on the operating system level (e.g. a pthread).
So far, we have no "green threads" within the JVM, but real LWPs scheduled by the OS.
The difference between "normal" and "real-time" threads lies in the scheduling policy used for that mapping.
While normal Java threads probably map to SCHED_RR or SCHED_OTHER, real-time threads are scheduled by the OS via the SCHED_FIFO policy in order to achieve a better real-time predictability.
However, the OS's scheduling mechanisms automatically make decisions about the right positioning of a LWP within an appropriate run-queue, due to thread's preemption, blocking or release (even dynamic priority changes) activities and its scheduling policy.
That's exactly why I ask myself, what is the need of a Scheduler representation within a JVM?
Furthermore, how a Scheduler extension is able to incorporate with the threading model and the underlying scheduling mechanisms of the OS?

One point could be a situation where a real-time JVM runs directly on top of the bare hardware and has to perform scheduling decisions on its own.
The Scheduler API could then be understood as an extension mechanism of a kind of JVM-intern scheduler (e.g. the PriorityScheduler), thereby allowing scheduling decisions to be made even in user defined Scheduler implementations.

A similar use case for an OS-based scenario could be if a JVM is intended to pass scheduling/threading routines of the underlying OS (eg. a part of the POSIX API)
up to the Java application level in order to provide the opportunity for a kind of application defined scheduling (like e.g. in the MaRTE OS).

Unfortunatelly, after introspecting the RTSJ API, both conclusions seem to me to be wrong.
So far, Java RTS seems not to provide any mechanism for reaction on scheduling events/decisions, neither intra-JVM nor from an underlying OS outside of the JVM.
Furthermore, there is no notion for incorporation with the base PriorityScheduler for making extended scheduling decisions.

I hope this post could bring me more light into the scheduling idea behind Real-Time Java systems as intnded by the RTSJ.

Sincerely,

Vladimir
  • 1. Re: Scheduling in Real-Time Java
    807557 Newbie
    Currently Being Moderated
    I'll try to summarize the idea here.

    Scheduler represents a specific scheduling policy. It defines the semantics of the scheduling policy, the interaction with release characteristics and things like admission-control/feasibility. The default (and only) defined Scheduler is the PriorityScheduler which represents the common priority-preemptive, run-to-block, scheduling policy available on most real-time operating systems. This corresponds to the POSIX SCHED_FIFO policy.

    The intent is that an RTSJ implementation (not an RTSJ user) can define additional scheduling abstractions and policies. For example, an implementation might provide an extension to PriorityScheduler that implements SCHED_RR (ie it adds time-slicing). Or an implementation might add a dynamic scheduler such as Earliest Deadline First, or Least-Laxity-First, or one of numerous dynamic schedulers. However the RTSJ is missing many details such as how multiple schedulers would interact.

    The expectation is not that arbitrary schedulers can be added to arbitrary implementations of the RTSJ. An implementation that uses the native OS scheduler - ie by 1-1 mapping of Java threads to native threads - can't easily support a scheduler not supported by the OS. Conversely a VM might not use the OS and might take full control of all scheduling decisions for Java threads.

    Hope this clarifies things somewhat.

    David Holmes
    RTSJ Technical Interpretation Committee and JSR-282 Expert Group member
  • 2. Re: Scheduling in Real-Time Java
    807557 Newbie
    Currently Being Moderated
    Thank you very much for your answer.

    >
    The expectation is not that arbitrary schedulers can be added to arbitrary implementations of the RTSJ. An implementation that uses the native OS scheduler - ie by 1-1 mapping of Java threads to native threads - can't easily support a scheduler not supported by the OS. Conversely a VM might not use the OS and might take full control of all scheduling decisions for Java threads.
    >

    That means, that a scheduling policy different to PriorityScheduler can only be assigned to a Schedulable object if it is supported by the OS and the JVM?
    It also seems that at the current state of the art the PriorityScheduler representative within the JVM is intended only for manipulating a feasibility set of Schedulable objects (supporting online feasibility analysis)?
    However, since user-defined scheduling is not intended by the specification, applications have to rely on the feasibility analysis based on the underlying/supported scheduling mechanisms.
    Thus, in the current Java RTS implementation this would be the "default" feasibility mechanism based on the PriorityScheduler.
    Unfortunatelly I can not figure out the need of maintaining a feasibility set, since feasibility, as specified for the PriorityScheduler, is a simple asumption that we have "an adequatly fast machine to handle the periodic and sporadic load"?
    I actually assumed that feasibility analysis performs real cost budgeting taking into account deadlines and so on, but it seems to be specified simply to make a negative statement always when aperiodic tasks are involved ?

    In "Getting More Flexible Scheduling in the RTSJ" Wellings and Zerzelidis propose some (more or less) "minor" extensions to the RTSJ API in order to enable hierarchical scheduling within the fixed priority framework.
    In fact, they suggest a two-level scheduling scheme with the PriorityScheduler at the top level, assuming that "any scheduling policy can be supported by manipulating priorities".
    The main idea is to encapsulate blocking statements within the JVM and the Runtime Library (causing a potential context switch) with callbacks to an application level scheduler.
    That scheduler in turn performs scheduling decisions by adjusting the priorities of schedulables according to a certain policy.

    Since Andy Wellings is a member of the RTSJ Technical Interpretation Committee, is there any attempt to evolve the specification in a similar direction as described above, in order to support more flexible scheduling mechanisms and feasibility analysis?

    Sincerely,

    Vladimir
  • 3. Re: Scheduling in Real-Time Java
    807557 Newbie
    Currently Being Moderated
    Vladimir.Nikolov wrote:
    That means, that a scheduling policy different to PriorityScheduler can only be assigned to a Schedulable object if it is supported by the OS and the JVM?
    Well it has to be supported by that implementation of the RTSJ. Howe that is done - ie whether it requires OS support - depends on that VM, the OS and the actual scheduling policy.
    It also seems that at the current state of the art the PriorityScheduler representative within the JVM is intended only for manipulating a feasibility set of Schedulable objects (supporting online feasibility analysis)?
    However, since user-defined scheduling is not intended by the specification, applications have to rely on the feasibility analysis based on the underlying/supported scheduling mechanisms.
    Thus, in the current Java RTS implementation this would be the "default" feasibility mechanism based on the PriorityScheduler.
    Unfortunatelly I can not figure out the need of maintaining a feasibility set, since feasibility, as specified for the PriorityScheduler, is a simple asumption that we have "an adequatly fast machine to handle the periodic and sporadic load"?
    I actually assumed that feasibility analysis performs real cost budgeting taking into account deadlines and so on, but it seems to be specified simply to make a negative statement always when aperiodic tasks are involved ?
    The RTSJ scheduling framework provides support for feasibility analysis by defining the admission control methods eg setXXXIfFeasible. However the RTSJ does not, and can not, mandate any non-trivial feasibility algorithm because in simple terms no such general algorithms exist. There are some static feasibility tests in the literature and you could apply those offline to your application (assuming you can find the values of all the "magic" numbers in such formulae - which is generally not the case). At present the RTSJ doesn't support even these simple feasibility tests because blocking-time is not recorded in the release parameters - something being addressed in RTSJ 1.1. In any case unless there is a pluggable framework for feasibility tests it would be a waste of time for VMs to implement them given they can (more) easily be done offline using other tools.

    Only dynamic admission control is really of interest and as far as I am aware no such general dynamic admission control policies exist (anything you find in the literature is very context specific). So it is left up to an implementation as to whether they try and define dynamic admission control algorithms - and so far none have because they don't have one.

    In "Getting More Flexible Scheduling in the RTSJ" Wellings and Zerzelidis propose some (more or less) "minor" extensions to the RTSJ API in order to enable hierarchical scheduling within the fixed priority framework.
    Since Andy Wellings is a member of the RTSJ Technical Interpretation Committee, is there any attempt to evolve the specification in a similar direction as described above, in order to support more flexible scheduling mechanisms and feasibility analysis?
    If there is ever a RTSJ 2.0 then more sophisticated scheduling support is one of the items on the wishlist. But there's no guarantee there ever will be a RTSJ 2.0

    David Holmes