Google
 
21st Home / Contact Us /Archives

 

 

PERC up your Java

Dr. Kelvin Nilsen

President, NewMonics Inc.
P.O. Box 692, ISU Research Park
2501 N. Loop Dr., Suite 900 C
Ames, Iowa 50010-0692

Tel. 515-296-0897
kelvin@iastate.edu

According to Sun Microsystems [1], Jav"originated as part of a research project to develop advanced software for a wide variety of networked devices and embedded systems." The research project initially chose to use C++ for development. But subsequently, Sun's developers encountered so many difficulties with C++ that they decided it would be best to design an "entirely new language environment." As a general purpose programming language, Java has much to offer developers of embedded real-time systems.

However, there are a number of shortcomings in its design and in all current implementations that hinder its use for programming of industrial control and consumer electronics devices. NewMonics Inc., a startup based in Ames, Iowa, has undertaken to address these shortcomings by standardizing a real-time application programmer interface (API) and by creating a clean-room implementation of the Java virtual machine that it plans to market under the PERC product name. PERC distinguishes itself from traditional Java in several important ways:

    1. PERC provides control structures to allow programmers to specify atomic segments of code and to specify timed statements. An atomic statement is like a synchronized statement except it has the additional constraint that it always executes either to completion or not at all. A timed statement is a statement that is allowed to execute no more than a programmer-specified amount of time.

    2. The standard PERC API includes all of the functionality of Sun's Java, plus it includes the standard libraries required for reliable execution of real-time programs.

    3. The implementation of the PERC virtual machine includes support for accurate garbage collection. This eliminates the possibility that dead memory will be mistakenly treated as live objects because of conservative pointer scanning. Further, it makes possible the use of garbage collection algorithms that defragment the heap. These capabilities are essential for reliable embedded real-time applications.

    4. PERC's run-time system includes support for real-time garbage collection. In contrast with existing Java implementations, in which the garbage collector may interrupt application processing for unpredictably long times at arbitrary times, real-time garbage collectors can be configured so that the garbage collection effort is evenly distributed between a number of incremental garbage collection steps. Furthermore, real-time garbage collectors can guarantee to each application a predetermined quantity of live memory and an allocation rate measured in terms of bytes of allocated memory per unit time.

    5. PERC's real-time API includes library support for periodic execution of real-time tasks. When a real-time activity is introduced into the local execution environment, standard protocols allow the activity to measure its memory and CPU-time needs in this environment and to negotiate with the system executive to determine how much of its desired resource budget will be available.


NewMonics' current plans are to provide support for execution of arbitrary Java byte-code programs on PERC virtual machines. Further, NewMonics is also developing Java library support to allow PERC programs to execute on traditional Java virtual machines. However, because of weaknesses in existing Java virtual machine implementations, PERC library add-ons for traditional Java virtual machines can only approximate the benefits of the PERC API. For superior performance and reliability, PERC programs should be executed on PERC virtual machines.

Does Java Need Real-Time Capabilities?

Some Java proponents suggest that current Java performance is acceptable and that there is no reason to add real-time determinism because whatever performance problems might exist in the Java environment itself are hidden by inherent network delays. NewMonics views this attitude as short-sighted:

  • First, Java as a programming language is useful for much more than just Web-page programming.

  • Second, there are many circumstances in which network latencies can be minimized through careful partitioning of dedicated sub-networks and intranets.

  • Third, even in situations for which network latencies hinder real-time presentation of Web-page information, robust Java applets should be written so as to mask network latencies by remaining responsive to user interaction even though certain network data may be temporarily inaccessible.

Note that many of the most promising applications for which Java is supposedly positioned are inherently real-time. Included among these are video conferencing, voice processing, full-motion video and other multimedia, distributed virtual reality environments, distributed video games, and interactive television. The high-level benefits of the Java programming language would also benefit developers of more traditional embedded system applications such as medical instrumentation, engine diagnostic systems, flight simulators, in-vehicle navigation systems, factory floor automation, anti-missile defense systems, and air traffic control.

Given the need for real-time capabilities, it is important to understand how the existing Java falls short of delivering the necessary capabilities. The problems can be broadly categorized according to (1) the Java language itself, and (2) implementation of the Java virtual machine.

Shortcomings with the Java language

Developers of real-time applications need to be able to describe their resource requirements in standard notations so as to enable Java's translation and run-time support mechanisms to guarantee availability of the necessary resources. The two primary resources that must be so managed are time and memory.

Memory:

Each real-time activity can be characterized in terms of the total amount of dynamic memory that it needs to keep live at any instant in time and the rate at which dynamic memory must be allocated (and garbage collected) in order to support reliable execution of the activity.


Time:

Each real-time activity (e.g. video conference session) is comprised of potentially many real-time tasks. Each real-time task's CPU requirements are characterized in terms of a periodic execution requirement. Note that the amount of CPU time required by the task in each execution period depends on the capacity of the host CPU. With a very fast processor, the task's periodic execution time needs are much smaller than with a slow processor.

Current Java programmers ignore consideration of these resource management issues. In essence, the Java programming environment presents the illusion that memory is unbounded and the CPU is infinitely fast. Since this illusion is false, Java programs do not behave in time-predictable ways. For example, a request within one thread to sleep for 50 ms might actually result in the thread sleeping for over 300 ms. And a request to allocate memory for a new object might result in an OutOfMemoryError exception that ultimately kills the thread.

Shortcomings with Existing Java implementations

Besides the fact that current Java implementations lack the ability to support programmer-controlled resource management such as has been described above, many of the implementation techniques currently in use are incompatible with the need to provide real-time predictability. Some of the particular difficulties are mentioned below.

Dynamic Just-In-Time (JIT) Optimizations:

Though JIT optimizations for Java are just now becoming available, their use in the implementations of existing programming languages such as Smalltalk and Self is well understood. Since these optimizations are applied on-the-fly, in response to recent execution history feedback, the time required to execute particular code segments varies radically. A particular code segment may initially execute slowly in deterministic time.

After many executions, the JIT optimizer may decide the code segment is deserving of optimization. The next time this code is invoked, it requires considerably more execution time because part of the time is spent optimizing the code's performance. Following this invocation, subsequent invocations execute in fast deterministic time. JIT optimization techniques work well on average, but they complicate the analysis and control required to achieve predictable real-time behavior.

Garbage Collection Scheduling:

Sun's Java implementation treats garbage collection as a low-priority thread. If all of the executing Java threads are I/O bound, this works well in that the garbage collection thread makes sufficient forward progress to complete garbage collection during times that the Java execution environment would otherwise be idle. However, if there exists even a single high-priority compute-bound thread, then the garbage collection thread does not execute until some thread's attempt to allocate memory fails. This triggers on-demand garbage collection.

Note that once the garbage collector has been triggered in this way, all threads are forced to wait until garbage collection completes. Since the thread that triggers garbage collection may have been executing at a relatively low priority, this situation is described by real-time engineers as a form of priority inversion. The important point to consider is that even high-priority threads are forced to wait for this low priority thread's resource allocation request to be satisfied.

Garbage Collection Strategies:

A garbage collector has the responsibility of locating memory that is no longer in use and returning this memory to the free pool to make it available for future allocation requests. The garbage collector determines which memory is "no longer in use" by searching for segments of memory to which no existing in-use objects refer. Objects refer to each other by address.

Computer programmers describe locations that hold memory addresses as pointers. A live object is one that is reachable by following a chain of pointers between objects where the initial link of the chain is represented by a root pointer. Root pointers are, by definition, the starting point for any attempt to access memory-allocated objects. Objects that are not reachable according to this definition are said to be dead, and it is the garbage collector's responsibility to reclaim their memory.

The distinction between accurate and conservative garbage collectors is the mechanism used by the garbage collector to distinguish pointers from non-pointers. An accurate garbage collector distinguishes based on the programming language's type system. A conservative garbage collector simply treats any memory location that holds a value that could be interpreted as a legal memory address as a pointer. There are two significant problems with conservative garbage collection in embedded systems environments:

  • First, dead memory may be treated as live if integer or floating point values happen to resemble legal addresses. This results in unwanted retention of dead memory.

  • Second, because the garbage collector is generally not sure whether a particular value is a pointer or non-pointer, it is not able to relocate live objects in order to defragment the free pool. The result is that a conservative garbage collector is not able to offer reliability guarantees regarding availability of free memory.


Unfortunately, all of the existing Java implementations that we are aware of use at least partially conservative garbage collection techniques.

What is PERC?

PERC stands for Portable Executive for Reliable Control. PERC is both a standard programming language notation and a virtual machine definition. As a language, PERC is identical to Java except that it supports two control structures that are not a part of the official Java definition. The relationships between PERC and Java are characterized in Figure 1.



FIGURE 1. Relationships between PERC and Java


PERC can be translated directly to annotated Java byte codes using NewMonics' Percolator(TM) product. Or it can be converted to traditional Java by a hypothetical PERC-to-Java preprocessor (p2jpp) following the conventions outlined in reference [2]. The advantage of using Percolator is that it translates the PERC code into byte codes that are annotated using special attribute definitions to enable efficient and reliable compliance with real-time constraints.

Traditional Java virtual machines do not understand these attributes. And without these attributes, compliance with programmer-specified real-time requirements can only be approximated. Note that either virtual machine can execute byte codes generated by either translator.

Atomic Statements

One of the two PERC syntactic extensions is a control structure that allows programmers to specify that certain code segments are to be executed either in their entirety or not at all.


Timed Statements

The other special PERC syntax is a control structure that allows programmers to specify a maximum amount of time for execution of particular code segments.

The following PERC code demonstrates both atomic and timed statements:

x = computeApproximation();
i = 0;
timed (10 ms) {

    for ( ; ; ) {

      z = refineApproximation(x);

      atomic {

        x = z;

        i++;

      }

    }

}


In this code, an initial approximation is computed first. This approximation is then refined as many times as is possible without exceeding the 10 ms time limit. Upon termination of the timed statement, the variable i represents the number of times the approximation was refined. Knowing how much work can be accomplished in a 10 ms time period may allow this application to dynamically adjust its future service quality.

PERC Libraries

PERC provides a standard set of libraries to enable programmers to describe their real-time needs to the run-time environment. A draft description of these libraries is available as reference [2]. This article provides only a high-level overview of the PERC API.

Real-Time Activities

The RealTime package defines a RealTime.Activity class. PERC programmers extend this class to create their own real-time activities. Each real-time activity consists of an arbitrary number of real-time tasks, a configure method, and a negotiate method.


Real-Time Tasks

PERC supports a number of different kinds of real-time tasks. Most tasks are characterized in terms of their desired execution frequency and their periodic CPU-time requirements. Periodic tasks are automatically executed in each period. CPU time is reserved for periodic execution of Sporadic tasks, but the tasks are only invoked if certain conditions are satisfied at the time the task would normally be triggered. Spontaneous tasks are not necessarily periodic. In response to particular conditions, a Spontaneous task may be triggered for execution if sufficient time and memory resources exist.

Periodic, Sporadic, and Spontaneous tasks are executed to completion each time they are triggered. In PERC, these kinds of tasks are comprised of essential startup and finalization code and an optional work component. The run-time system makes sure that each task has sufficient time to execute its essential components and provides a configurable amount of additional CPU time for execution of the task's optional components. A fourth type of real-time task is identified by the Ongoing label. Unlike the other three kinds of real-time tasks, Ongoing tasks are suspended and resumed rather than being killed and restarted at the end of each execution period.

Garbage collection is an example of an Ongoing real-time task. Activity Configuration When a real-time activity is first introduced to the run-time system for execution, it undergoes a configuration process: the run-time system invokes the activity's configure method. In response, the activity determines the total amount of memory and the rate at which memory must be garbage collected in order to reliably execute the activity.

Additionally, the activity determines the number of tasks that need to be executed and specifies an execution frequency, a minimum CPU-time allotment, and a preferred CPU-time allotment for each task. The RealTime package provides services to assist in the analysis of the activity's memory and CPU-time needs. Once its resource needs have been determined, the configure method returns a representation of its needs to the run-time environment.

Resource Negotiation

The PERC run-time environment examines the resource needs of the newly configured activity in the context of all of the other real-time activities that are currently executing. If it has sufficient resources to satisfy the activity's requirements, it proposes a resource budget by invoking the activity's negotiate method. Since the run-time environment may propose a budget that is less than what the activity described as its preferred allocation but more than its minimal allocation, the activity may either accept or reject the proposed budget. If the activity accepts the budget, the run-time system arranges to begin its execution. Otherwise, the routine that attempted to introduce this new activity into the system workload is notified that there were not sufficient resources to accept responsibility for execution of the new activity.

In some cases, the run-time system may find it desirable to modify the resource budgets of executing activities as part of the negotiation process. Individually, the run-time system proposes revised budgets for each activity by invoking the corresponding negotiate method. Activities that are already running have no obligation to accept smaller budgets. However, it is in their best interest to do so. If they refuse to consider alternative budgets, the system "user" may decide to simply close them down in order to make their resources available to other activities.

Mixing PERC with Java

The principal benefit of PERC extensions is to allow application developers to reliably negotiate and manage their use of time and memory resources. The PERC extensions are adequate to allow even developers of non-real-time activities to participate in resource negotiation. Developers of a word processor application might, for example, specify that their application requires a total of 1 MByte of dynamic memory and anywhere from 0 to 10 seconds of execution time in every 10-second period. Developers of robust "Jav" software would be wise to consider using the PERC configuration and negotiation interfaces. Nevertheless, Java developers need not honor the PERC interface.

In an environment that includes the execution of PERC applications in combination with traditional Java applications, the PERC programs are provided with whatever resources they were budgeted as part of the negotiation process and the Java applications are simply provided with whatever resources are left over.

Market Opportunities

The Java language as it has been defined by Sun Microsystems lacks the necessary mechanisms to allow programmers to reliably describe their real-time execution requirements. PERC provides these mechanisms in a framework that is compatible with execution of traditional Java programs. NewMonics seeks to establish PERC as a foundation for the creation of reusable real-time software components. NewMonics is currently involved in licensing discussions with a number of real-time operating system companies and in open standardization discussions with the Software Architecture Forum of the European Union's Open Microprocessor systems Initiative.

PERC offers numerous benefits to developers of both embedded real-time software and Internet applications. NewMonics expects PERC virtual machines to be found in environments as diverse as manufacturing plant automation, autonomous space craft, in-vehicle navigation systems, interactive television devices, and the so-called network computer.

Conclusions

Java brings many exciting new capabilities to the Internet. Additionally, Java as a programming language offers important benefits over alternative programming languages. However, Java lacks critical capabilities for the embedded real-time marketplace. To satisfy the needs of embedded real-time developers, NewMonics has developed a set of standard extensions to Sun's Java and is marketing an integrated implementation under the PERC product name.

References

1. Sun Microsystems Inc., The Java Language Environment: A White Paper.1995, Sun Microsystems, Inc.: Mountain View, CA.

2. Nilsen, Real-Time Java (v. 1.1). 1996, Iowa State University: Ames, Iowa.


Copyright 1996, All Rights Reserved, Dr. Kelvin Nilsen, NewMonics Inc.

21st, The VXM Network, https://vxm.com

s