Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

JVM Languages

Java and Embedded Real-Time Control


Java Sourcebook 96: Java and Real-Time Control

Java and Embedded Real-Time Control

Extending the language for real-time applications

Kevin Nilsen

Kelvin, a former research scientist at Iowa State University's Center for Advanced Technology Development, is currently president of NewMonics Inc. He can be contacted at [email protected].


Java was initially intended to be an implementation language for PDAs. Subsequently, development effort was retargeted to the needs of set-top boxes, CD-ROM software, and ultimately, the World Wide Web. Java is currently attracting most of its attention as a medium for portable distribution of software over the Internet. However, Java is much more than simply a language for adding animations to web pages.

In many ways, Java is a better language than C and C++, two of the most popular languages for current implementation of embedded real-time systems. If Java could be extended in ways that would allow it to support the cost-effective creation of portable, reliable real-time applications, this programming language would realize a much larger audience than just those implementing web applications. Some of the near-term applications for which a real-time dialect of Java would be especially well suited include PDAs, digital diagnosis (medical instrumentation, automotive repair, electronics equipment), robotics, weather monitoring and forecasting, emergency and service vehicle dispatch systems, in-vehicle navigation systems, home and business security systems, military surveillance, radar and sonar analysis, air traffic control, and various telephone and Internet packet-switching applications.

As defined and implemented by Sun, Java is not entirely appropriate for this domain. By extending the Java language and libraries in ways that are compatible with Sun's original specifications, it is possible to create a language standard that better serves the needs of embedded-system developers. PERC, short for "Portable Executive for Reliable Control" (and developed by my company, NewMonics), is just such an extension. The PERC dialect of the Java language provides standard real-time libraries and special syntax extensions to allow you to describe real-time resource requirements. The PERC run-time environment provides real-time scheduling, on-the-fly schedulability analysis, and real-time garbage collection.

Code Reuse versus Embedded Real-time Constraints

One of the primary benefits of the object-oriented paradigm is that previously developed code can be easily incorporated into future products. For embedded-systems programmers, these benefits are manifest in a variety of situations. For instance, when a new product is first designed, developers can build on code provided in the language's standard libraries or in libraries purchased from third parties. New objects with semantics that closely resemble existing objects are declared by simply inheriting from the original object definitions. Or, when an existing product is modified, the new functionality can often be added without dealing directly with the previously developed implementation. Instead, the new system simply inherits all of the functionality of the original system, then replaces or adds particular methods to achieve improved functionality.

But reuse in an embedded real-time environment is especially difficult, because you need to take time and memory considerations into account whenever code is reused. This is why Java without the PERC extensions is not entirely appropriate for embedded real-time systems. Shortcomings are in the areas of garbage collection, task scheduling, task synchronization, and run-time analysis.

Garbage Collection. In a real-time application, it is important that memory will be available for new objects when they need to be allocated. Further, it is important that background garbage collection not impose long delays at unpredictable times. This would interfere with your ability to demonstrate compliance with real-time constraints. Current Java implementations do not address issues such as

  • Scanning. To distinguish live objects from garbage, most Java implementations use a partially conservative scanning technique in which memory words containing values that represent legal memory addresses are assumed to represent pointers. Since these words may actually hold integer or floating-point values, the use of conservative scanning techniques may cause the garbage collector to accidentally treat dead objects as live, resulting in memory leaks.
  • Fragmentation. Because most Java implementations use partially conservative garbage-collection techniques, it is not possible to relocate all live objects in order to defragment the memory heap. Over time, the cumulative effects of fragmentation make it difficult to allocate the large objects. This is especially troublesome for embedded systems that are expected to operate reliably for weeks at a time.
  • Scheduling. In Sun's Java implementation, garbage collection is implemented as a low-priority background thread. If all application threads are I/O bound, this approach works well because garbage collection is performed during times that the CPU would otherwise be idle. However, if any application tasks are CPU-bound, the garbage collector is not scheduled for execution until the system runs out of memory. The first allocation request that cannot be satisfied from the existing free pool triggers a stop-and-wait garbage collection of the entire system, forcing suspension of all other tasks in the system.

System information. By design, the Java run-time environment does not allow applications to determine how much memory they require or how much total memory is available in the execution environment. This makes it difficult for programmers to determine whether their applications can expect to run reliably.

Memory budgets. In Java, it is common for multiple activities to be running in an execution environment, so it is important for the system's run-time support to enforce memory budgets on each application. But the standard Java libraries provide no ability to request or enforce memory budgets.

Real-time scheduling. The traditional Java environment lacks mechanisms for real-time task scheduling. Applications can request to sleep for a specified number of milliseconds before continuing their execution, but there is no guarantee that the task will be suspended no longer than the requested amount of time--and there is no guarantee that the task will have the highest priority at the time it is made ready for execution. Also, there is no way for a Java task to determine how many other tasks are running on the system, their relative priorities, and the portion of CPU time that they consume. Thus, there is no way to assure that a task will have sufficient CPU time to execute within its real-time constraints.

Synchronization. When it comes to task synchronization, Java uses monitors (identified by the synchronized keyword) to protect critical sections of code from simultaneous access by multiple tasks. Once a task has entered into the monitor that corresponds to a particular object, no other task can access that object's monitor code until the first task has exited the monitor. Note that in order to analyze the time required to perform certain actions, a real-time developer must know how long each task might have to wait for entry to monitors. The information required to perform this analysis is not generally available. That information is basically of three types:

  • Number and priority of competing tasks. In the highly dynamic Java execution environment, the number and priorities of other tasks that desire to share access to an object are difficult to determine and may vary throughout the execution of a task. Thus, it is difficult to determine how many other tasks might be ahead of a task in the queue awaiting access to a shared object's monitor.
  • Time spent within monitors. Java imposes no restrictions on the complexity of code contained within a synchronized method. The code may comprise unbounded loops, dynamic method invocations, and nested entry into other monitors. Newly loaded class libraries may include synchronized statements that lock particular objects. Thus, it is nearly impossible to determine how much time each competing task might spend within a monitor.
  • Priority inversion. Java's standard libraries fail to specify the scheduling model and fail to specify protocols for avoiding priority inversion. This means that real-time programmers would not be able to analyze blocking behaviors even if they had perfect knowledge of the implementations of all the tasks that comprise the combined system workload.

Introspection. Since the time and memory requirements of Java programs are not known until the bytecodes have been loaded into the executing environment, the environment must provide mechanisms to support run-time analysis of the following resource requirements:

  • CPU time. Java's standard libraries fail to provide a protocol whereby newly loaded tasks could determine how much CPU time they require to execute reliably on the host platform.
  • Memory. Java's standard libraries lack mechanisms to enable applications to determine how much memory is required to represent particular objects in the local execution environment.
  • Workload. Java's standard libraries provide no mechanism to enable applications to determine the total system-memory capacity or to determine how much CPU time and memory are required by the other tasks concurrently executing on the host machine.

Although not as fundamental as the aforementioned problems, design tradeoffs made in most current Java implementations have been biased by priorities and mindsets that are inconsistent with the needs of embedded real-time system development. Their economies differ significantly from those of traditional desktop-application developers. For example, current Java implementations are not space efficient. Many use a 32-bit word to represent a Java byte. And the choice to use partially conservative garbage collection was biased by a working environment in which memory is abundant and where high-speed disk drives make virtual memory readily available.

Another example of the tension between desktop and embedded real-time developers is the use of dynamic compilation. In order to achieve high performance, Sun suggests that selected code segments be translated from Java bytecodes to native machine language. Determination of the segments to translate is based on recent execution history. Routines that prove themselves to be "hot spots" are translated on the fly. The interruptions required to perform translation, which occur at unpredictable times, complicate analysis of task execution times.

Standard PERC Libraries

PERC is designed to let you develop reliable portable real-time software components. As space does not allow for a complete description of the proposed extensions, I will provide only an overview of work that is under progress. For more complete descriptions, see my paper "Real-Time Java (v.1.1)" at http://www.newmonics.com, and my article "Issues in the Design and Implementation of Real-Time Java" (Java Developer's Journal, 1996. 1(1)).

Standard Real-time API

The PERC real-time API includes mechanisms that enable you to analyze and measure the times required to execute particular code segments, to analyze the memory required to represent particular objects, and to abstract access to persistent objects represented by flash or battery-backed RAM. Real-time applications are structured as activities, each of which is comprised of one or more real-time tasks. Each task is comprised of essential and optional components. PERC provides on-the-fly analysis capabilities to enable activities to negotiate for the resources to execute both components. It is the PERC programmer's responsibility to decide how much of each task is essential and how much is optional. In general, it is much less costly to provide the resources required of optional components than to provide guaranteed resources for essential functionality. PERC programmers should take these economic factors into account.

A typical execution environment would have multiple real-time activities executing at any given time. For example, one activity might be displaying a full-motion television-like news feed while another takes responsibility for tracking the user's pen motions and a third maintains a video conference connection. Each activity is accompanied by configure() and negotiate() methods.

Before a new real-time activity is executed, it is "introduced" to the local real-time executive. The executive, in turn, invokes the activity's configure() method, which was provided by its developers. It is the responsibility of this method to determine the activity's resource needs in the local execution environment. This consists of measuring each task's CPU-time requirements and computing the combined memory needs of all the tasks that comprise the real-time activity. The configure() method returns a representation of the activity's minimum and desired resource allocations to the executive.

Once the configure() method has returned, the executive endeavors to satisfy the activity's resource requests. The executive proposes a resource budget to the real-time activity by invoking the activity's negotiate() method. Since the real-time executive may propose to budget fewer resources than were requested by the activity, the activity has the option of rejecting the proposed budget. If the proposed budget is rejected, the real-time executive may decide not to allow the new activity to be added to the system workload. Alternatively, the executive may reclaim resources previously allocated to other activities (by renegotiating their resource budgets), then propose a revised budget to the new activity by once again invoking its negotiate() method.

Syntax Extensions to Java

Developers who use C or C++ must rely on prerun-time analysis and operating-system services to enforce real-time constraints. This is undesirable for a number of reasons:

  • The source code alone is not sufficient to represent the functional and real-time semantics of the software. The real-time constraints are scattered among specification documents, developer logs, and automated scripts that perform analysis of execution-time requirements.
  • Often, the operating-system services are not part of the ANSI C standard. Use of these services makes the code nonportable among operating systems.
  • Since the operating-system services are seen by the programming-language compiler as subroutines that are outside its domain of analysis, the compiler is generally unable to inline or otherwise optimize their implementations.

For these reasons, we have incorporated two special syntaxes into the design of PERC. These syntaxes are designed to simplify programming, ease the burden of software maintenance, and improve implementation efficiency.

Rather than rely entirely on the use of synchronized code segments (for which blocking times are difficult to analyze), PERC provides a mechanism known as an "atomic statement." The body of an atomic statement is executed either to completion or not at all. To the programmer, an atomic statement resembles the disabling of interrupts. However, the implementation may differ. In particular, a hard-real-time implementation of PERC might verify that sufficient CPU time remains in the current time slice to complete execution of the atomic statement before allowing control to enter into the atomic statement's body. Without this check, the inability to interrupt the atomic statement might push all other tasks in the system off schedule.

PERC requires the body of an atomic statement to be execution-time analyzable. The PERC standard defines a subset of Java for which it is possible, through on-the-fly analysis, to determine worst-case execution times. For single processor implementations, the use of an atomic statement for real-time synchronization scales much more easily than the use of synchronized statements, because there is no need to analyze blocking times. If a particular task has been granted CPU time to execute, then it also has access to whatever atomic statements may lie along its execution path.

A second syntax introduced for the purpose of enabling programmers to describe real-time requirements is a "timed statement." The control clause of a timed statement represents an upper bound on the amount of CPU time the body of the timed statement is allowed to execute, including the CPU time inherited by other tasks that happen to own access to critical monitors at times that this task desires access. If the body of the timed statement is still executing at the end of its allotted time, the body is aborted by raising a timeout exception.

Example 1 demonstrates examples of both control structure extensions. In this code, the application refines approximation x as many times as it can within a 10-ms time budget. The variable i counts the number of times x's value is refined. The significance of the atomic control structure in this code is to make sure that the body of the timed statement is not aborted between the assignment to x and the increment to i.

PERC Development Environment

Figure 1 illustrates the PERC development and execution environment. p2jpp is a preprocessor that converts the timed and atomic statements into standard Java source code. The output of p2jpp is ready for a traditional Java compiler, such as Sun's javac. Note that PERC source code can also be translated directly to Java bytecodes by Percolator (a NewMonics product). Percolator outputs bytecodes that are essentially the same as Sun's javac. However, the class files emitted by Percolator also include special attribute information to identify particular parts of the program that require real-time determinism. The PERC virtual machine uses this attribute information to assist in its analysis of worst-case execution times. This attribute also enables it to perform transformations on the bytecode that will allow the real-time program to run much faster than would be possible without the transformations.

Execution of PERC programs on a traditional Java virtual machine with accompanying PERC libraries is less efficient and less predictable than execution on a PERC virtual machine. For example, the traditional Java virtual machine

  • Does not understand the special attributes that are inserted by Percolator. As a result, it is not able to perform the transformations necessary to improve performance and determinism.
  • May be running as a task within a time-sharing system that is unable to provide any guarantee of what fraction of the system's CPU time will be dedicated to the Java virtual machine.
  • Is unable to perform schedulability analysis so it cannot guarantee tasks that they will execute within their real-time constraints.
  • Lacks the ability to distinguish among memory allocated to different real-time activities. Thus, it cannot enforce memory budgets on particular real-time tasks.
  • Probably lacks support for real-time garbage collection. There is no way for the PERC program to configure the system's garbage collector to support a guaranteed rate of new memory allocation.

Nevertheless, for applications constrained by real-time expectations, executing PERC on a traditional virtual machine offers important benefits over attempting to achieve real-time determinism without the use of PERC extensions.

In particular, application programmers are provided with standard notations in which to encode the desired real-time behavior as part of their source program. This contributes to the ease of long-term software maintenance.

Also, although the execution environment may not be able to satisfy all the desired real-time constraints, the PERC libraries are able to determine where real-time performance is falling short. This information can be used by the run-time system and the application code to dynamically adjust service quality and load balancing.

Of course, for best performance and real-time determinism, PERC bytecodes should be run on a PERC virtual machine. Note that the PERC virtual machine can run both Java and PERC code. If a workload contains a mixture of PERC and Java programs, the former are provided with their resources first, and the latter receives whatever is leftover.

Further Information

Because of space constraints, I've omitted many details about PERC. For more information, check out http://www.newmonics.com. We encourage open discussion and constructive criticism of this evolving standard. Please send comments to [email protected].

References

Arnold, K. and J. Gosling. The Java Programming Language. Reading, MA: Addison-Wesley, 1996.

------. Native Methods in The Java Programming Language. Reading, MA: Addison-Wesley, 1996.

Hoare, C.A.R. "Communicating Sequential Processes." Communications of the ACM, vol. 8, no. 8, 1978.

Nilsen, K. "Real-Time Java" (v. 1.1). Ames, IA: Iowa State University, 1996. (Available at http://www.newmonics.com):

------. "Issues in the Design and Implementation of Real-Time Java." Java Developer's Journal, vol. 1, no. 1, 1996.

Sha, L., R. Rajkumar, and J.P. Lehoczky. "Priority Inheritance Protocols: An Approach to Real-Time Synchronization." IEEE Transactions on Computers, vol. 39, no. 9, 1990.

Example 1: Examples of control structure extensions.

x = computeApproximation();
i = 0;
timed (10 ms) {
  for ( ; ; ) {
    z = refineApproximation(x);
    atomic {
          x = z;
          i++;
    }
  }
}
Figure 1: PERC development and execution environments.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.