Multithreading in the Java Language

The Java language has multithread support as an intrinsic part of its specification. This article introduces the Java thread object and runnable interface and then covers the use of the Java synchronization and mutual exclusion mechanisms.

One of the features of the Java language that embedded systems programmers can immediately relate to is the native multithreading support. The Java thread support is inherent in the language rather than added on as libraries as for C and C++. The primary advantage of this approach is the cross-platform portability, which, of course, is one of the main motivators of the Java language design. Besides the basic ability to multithread (or multitask), the Java language presents a uniform model of mutual exclusion that is somewhat different from the prevalent schemes used in popular RTOSs such as pSOS and VRTX. The Java model provides a design pattern for straightforward implementation of mutual exclusion for complex data structures. The pattern is easy to learn and apply to a variety of mutual exclusion situations. There is also an issue of encapsulation in an object-oriented model, which Java and C++ provide but which is not available in C. This article includes a review of the C/RTOS model, a basic explanation of Java multithreading capability, and a discussion of the mutual exclusion design pattern. The suitability of Java for real-time systems still elicits controversy, such as performance of an interpreted language and garbage collection. Java 1.0 threads also have some specific weaknesses with respect to real-time programs that are mentioned in this article. Because of the nature of Java, the philosophy here is similar to that offered by some RTOS vendors for Java support. The real-time application is partitioned into two domains: a hard real-time domain implemented directly onto the kernel, probably in assembler and C/C++, and a soft real-time domain implemented in Java. Because the Java part is soft, the focus is on reduction of programmer workload and correctness of the program, rather than optimization for speed.

The C/RTOS Model

• Ability to create, start, suspend, and kill a thread (or task)
• Ability to set the priority level of a thread
• Binary and counting semaphores for mutual exclusion
• Bounded and unbounded queues for data flow and mutual exclusion
• Ability to disable thread rescheduling
• Ability to disable hardware interrupts globally and/or on a per-task basis
• Ability to delay for a specified time
• Ability to timeout on calls that suspend the calling thread

Any successful RTOS will enable fine-grained control of task execution. In some ways, this feature distinguishes an RTOS from a multithreading system. In the hard real-time environment, designers demand to know exactly what will execute when a given sequence of events occurs, and they usually want to know how long it will take. Java does not provide this level of determinism. For mutual exclusion, most RTOSs provide some form of the counting semaphore. A binary semaphore is a counting semaphore with a limit of one. Some systems provide a mutex which is similar to a binary semaphore.

While the counting semaphore is sufficient to construct whatever mutual exclusion is required, it doesn't provide a clean and simple pattern for implementation of protected data structures. The counting semaphore works fine for simple situations where there is a single block on a resource, one thread is allowed to operate on the resource, and then the resource is released. This simple binary model fails when a more complex resource allocation problem is faced.

For example, suppose you have a database, implemented as some sort of data structure that threads access to obtain information. If the data is not available or not present, the thread wants to wait until it is. Each thread might want a different piece of data. Two mutual exclusion problems are at work here: a binary exclusion problem, for the simple right to operate on the core data structure, and a multiple exclusion problem, for handling the different threads waiting on different things from a conceptually single object (the database).

Another example is allocation of multiple identical resources. Suppose a telephone system has N number of physical outgoing trunks, and any call processing thread can use any trunk. If there are more than N threads, then sometimes a thread will have to wait until a trunk becomes available (or reject the call immediately). You might model the allocation using a linked list of available trunks. You need one binary semaphore to block access to the list structure itself and (at least) another counting semaphore plus an associated data structure to control, activate, or timeout the threads that are waiting for a trunk. Various viable schemes can implement the required mutual exclusion, but the simple, unconstrained counting semaphore does not provide a clear model for how to do it. The problem might be stated as, "There are just too many ways to do it."

Design Patterns

Multithreading in Java

Threads

When a Java program starts, a single application main thread executes. The Java runtime has some threads that execute transparently to the application programmer, such as garbage collection and I/O. Exactly what is happening in background threads is of interest to an embedded systems programmer using Java. That information must be provided by the vendor of the virtual machine. For this article, we consider those threads to be transparent.

The main thread can then spawn additional threads as desired. An interesting aspect of Java threads is the way they are actually spawned and controlled. There are two alternative ways to handle it, and which way is best is open to discussion. A class Thread encapsulates the capabilities expected of a thread, including the actual method, run, that is the executable. You can extend Thread to make a new object with a thread's capabilities. An interface, Runnable, provides a way to tack the capability to run onto any object. The best explanation I've heard on which method to choose is as follows: if you are truly extending the capabilities of the Thread class itself (new object IsA thread), then you should inherit from Thread. Instead, if your focus is on an application-specific object that happens to have the capability to run (new object HasA thread), then you should implement Runnable. If you want to implement really complex mutual exclusion/ scheduling constructs, it can be useful to have a single point in the class inheritance tree to use as a polymorphic focus. In this article, the examples inherit from Thread, and then the Thread class is used as the access point for keeping lists of the applications threads.

We cannot hope to cover every aspect of class Thread and interface Runnable here. A good place to start for more info is the Javasoft tutorial on threads at http://www.javasoft.com /books/Series/Tutorial/java/threads.

Extends Thread

class AppThread1 extends Thread {
public void run() {
}
}

If the thread needs some parameters when it starts up, a new constructor can be defined that accepts the parameters and stores them in member variables. If each new object needs thread specific data that is accessible only by the thread itself, member variables can be declared. This method is a lot easier than passing parameters to a new thread and maintaining thread-specific data in most RTOS apps written in C:

class Appthread2 extends Thread {
int thread_specific_data;
public Appthread2(int x) {
thread_specific_data = x;
}
public void run() {
// use thread_specific_data when I am running
}
}

Control

I checked the priority issue by writing a Java program with three threads. T1 and T2 simply increment a variable in an infinite loop without sleeping or waiting. T3 reads and prints the current value of each of the other two, and sleeps a while. T1 is at MIN_PRIORITY (1), T2 is at NORM_PRIORITY (5), and T3 is at MAX_PRIORITY (10). If priorities work as they should, the value of T1 shouldn't get incremented at all, because T2 would always run until preempted by T3 for the printout. But when tested, T2 got a higher count than T1, but T1 did increment. From a real-time programmer's viewpoint, priorities in Java 1.0 aren't completely useful. Sun Microsystems is expected to soon release the Embedded Java specification, which addresses the Java subset implementation for embedded programmers. Advance information in the press has said that the first revision of Embedded Java won't fix the determinism problems, but that Sun Microsystems is addressing the issues through consultation with RTOS vendors and plans to fix the problem in the future.

Sleep: A thread can delay a specified amount of time with the sleep method, with a delay specified in milliseconds. Suspend/Resume: The execution of a thread can be suspended and resumed in a manner similar to what RTOSs provide, but typically mutual exclusion, waiting, and sleeping are used rather than explicit suspend/resume calls.

Grouping: Java allows logical grouping of threads with access control across thread groups. Java provides the POSIX style join and daemon mechanisms to provide additional levels of execution control. These mechanisms can associate threads in different ways so that an application can be viewed at a higher level, with groups of threads providing different discrete functions.

Mutual Exclusion

Synchronized: The synchronized keyword is used to establish a critical section (or monitor in Hoare). A critical section is an indivisible execution unit with respect to Java threads but not hardware interrupts. Synchronized can be used in several ways, either as the modifier on a class method declaration or as a guarding statement within a method. In either case, synchronized means that the critical section associated with the current object context is locked before proceeding and unlocked when the operation is complete. If a thread enters a critical section on the same object twice, it won't block. Only different threads will block. This prevents that type of deadlock or the required complicated code needed to avoid them. The implicit mutex in every Object is used to establish the critical section.

If a method is synchronized, then the critical section is locked at the beginning of the method and unlocked at the end. This established the entire method as a critical section. The declaration looks like:

synchronized void MethodName() {...

If a statement is guarded, then it looks like the following:

synchronized (expression) statement.

In this case, the keyword operates on the expression, which must resolve to a reference to an object. The critical section is established with reference to that object. However, some people discourage the use of the synchronized statement because it violates the object-oriented paradigm. The statement form uses an object's internal mutex outside the context of the object, so that transparency of the object is lost.

There is no way to access the Object mutex other than via the synchronized statement. You can't explicitly lock it and unlock in separate statements. This limitation actually has a couple of advantages. There will never be an instance where an object is locked and then is not unlocked. You won't have system hangs because a coder forgot to match up the locks and unlocks, used the wrong semaphore, or the dynamic operation of the system produced a scenario of unmatched locks and unlocks that wasn't anticipated. Secondly, this scheme means the code is still provable, as described by Hoare.

The standard resource conflict deadlocks can still occur if there are two synchronized objects and they are accessed by different threads in the wrong order.

Wait: The condition variable associated with an object is accessed through the wait, notify, and notifyAll methods of class Object in the API for java.lang.object.

A synchronized method can call wait inside the established monitor. When wait is called, it automatically releases the mutex and suspends the thread on the condition variable associated with the object through which the particular method is being called. The purpose of this is to suspend the thread until some condition about the object changes. In order for other operations to take place in synchronized methods of the object, the mutex must be released. Because the waiting thread is no longer accessing the object, it can't cause a mutual exclusion problem.

When the wait method returns (explained below), part of its return operation is to reacquire the mutex on the object. If it can't, it will queue up with other threads waiting on the mutex until it gets control of it.

The wait call can have a timeout, specified in milliseconds, or in milliseconds and nanoseconds (which I doubt does anything in current implementations). The timeout is indispensable for real-time programming.

Notify: A synchronized method can call notify when the condition of the object changes such that any waiting threads may need to retry an operation. The notify method released a single waiting thread. Since the method calling notify is synchronized, the waiting thread will not return from the corresponding wait statement until the notify method has returned and released the mutex.

The notify call is used in one-at-a-time situations, such as waiting on an empty FIFO queue until an entry is inserted. When one entry comes in, one waiting thread, the next in FIFO order, can return from its wait call and get the element.

NotifyAll: A synchronized method can call notifyAll which will notify all threads waiting on a particular object. Then all the threads can start up, one at a time (because of the critical section) and retry their operation.

The notifyAll call can be used to notify multiple tasks of events in an event driven system, like an event flag. Or, for complex data structures, it provides an easy way to let all waiting threads retry their operation when it isn't easy to figure out which particular thread of several may need to wake up in response.

Mutual Exclusion Design Pattern

The format of a pattern description is laid out in Gamma and has been widely accepted in the OOP community as an effective way of documenting a pattern. The pattern description covers what the pattern is supposed to do (intent), why it is doing it (motivation), where to use it (applicability), and how to implement it (structure, participants, collaborations, consequences and implementation).

Intent: The intent of this pattern is to provide thread safe access to an object with the capability for threads to wait for changes of condition in the object and respond to the change.

Motivation: In multithreaded programs, certain objects represent limited system resources that must be allocated among competing threads. Such allocation must be performed in a thread safe manner and, to support an event-driven paradigm, threads requesting a resource must be able to wait for the resource to become available. In real-time systems, timeouts on the waiting operation are required to meet system requirements and provide error recovery. For example, a telephony system may need to allocate outgoing trunk hardware to incoming call requests that are represented by a thread. There are more physical incoming lines than outgoing trunks. Incoming requests are willing to wait a certain amount of time to be allocated a trunk, but not forever.

Applicability: Use the monitor/condition variable pattern when:

• A system resource, represented by an object, is limited relative to the number of client threads that need access to the object and there is more than one instance of the resource object
• If there are equal numbers of resources and client threads but for some reason the resources may not be permanently allocated to particular threads
• Instead of resource allocation, client threads need to wait for a complex condition (such as a bit string) to have a certain value
• Client threads allocate an object, use it for some period of time, then return it to the allocator
• Threads waiting for a resource object need to wait for an object to become available rather than simply poll for availability
• A variation of the pattern is used if threads request specific instances of the resource rather than any instance of the resource This pattern is not used when there is a single instance of the resource and the client threads can use a binary critical section to provide thread safe access.

Structure: The structure is illustrated in Figure 1.

Participants:

• Controller. Provides the methods that use the monitor/condition variable mechanism to control allocation and deallocation of the resources
•  Pool. Representation of the resource as a collection class. May provide a way to find specific instances of the resource
• Instance. Individual instances of the resource. Collaborations:
• Resource stores the Instances as required by the particular application
• Controller accesses Resource to get and put Instances

Consequences: The monitor/condition variable pattern has the following benefits and drawbacks:

• Simple to implement in comparison with semaphore-based schemes
• All resource allocation mechanisms within an application can have a uniform interface to client threads regardless of the actual representation of the resource pool
• For the "specific instance" variation, when an resource is "put," all waiting threads must awaken and compete for the object, resulting in more thread rescheduling than might be necessary. A more complex implementation could have threads waiting on the particular instances rather than the entire pool

Implementation: The monitor/condition variable pattern works as follows. Some number of SET or PUT methods can change the state of the object. Some number of PEND or GET operations wait for changes of state of the object. All methods are synchronized to provide binary mutual exclusion for operation on the representation (the monitor). The wait/notify or wait/notifyAll methods are used to implement the condition variable.

GET/PEND:
• Start monitor with implicit binary lock (synchronized)
• WHILE (CONDITION is not true)ŭin other words, WHILE (resource is not available)
• Call the wait method. Within the wait call the thread atomically exits the critical section and suspends waiting for a notify call to resume it. The calling thread does not exit the method
• ENDIF
• ENDWHILE
• End the monitor with implicit binary unlock via return, with the appropriate object or status indication

PUT/SET:
• Start monitor with implicit binary lock (synchronized)
• If set operation cannot be performed, return an error
• Set the condition or put the object into the pool
• notify or notifyAll waiting threads that the condition has changed. (For notify, the thread that has been waiting the longest is resumed. It tries to acquire the monitor and suspends because the current thread is in the monitor. For notifyAll, all threads waiting are resumed and all block on the monitor)
• End the monitor with implicit binary unlock via return
• In turn, the (or every) thread that has been resumed will acquire the monitor and return from its wait statement and retry its operation

BoundedQueue. Listing 1 uses the wait and notify methods. A bounded queue provides a FIFO mechanism for message passing. A thread can GET or PUT an entry into the queue. When a GET operation is executed, the calling thread is returned the oldest object in the queue. If no object is available, the calling thread waits (with or without a timeout). When a PUT operation is executed, the calling thread passes in a new object, which is placed in the queue in FIFO order. If the queue is full when the PUT operation is executed, the calling thread gets an error indication. The bounding is necessary for deterministic operation in a real-time environment. The PUT operation can also wait until there is room in the queue rather than indicate an error, but this behavior is not implemented in this example.

import java.util.Vector;
// the BoundedQueue class that implements
// wait/notify
public class BoundedQueue {
// the resource pool object
Vector m_vect;
// the max size of the bounded queue
int m_size;
// construct with specified size
public BoundedQueue(int size) {
// create the vector with initial capacity
// equal to the bounded size
m_vect = new Vector(size);
// save the size for bounding
m_size = size;
}
// print queue data for debug
public synchronized void Print() {
int i;
// print current queue data
System.out.println("Current size : " + m_vect.size());
System.out.println("Current capacity : " + m_vect.capacity());
// print all elements in the queue
for(i=0;i System.out.print(m_vect.elementAt(i).toString() + " ");
}
System.out.println("");
}
// wait for a queue element without timeout
// input : none
// output : first Integer object in queue
public synchronized Integer Get() {
Integer i;
// wait for an element and return it
while(m_vect.isEmpty() == true) {
try {
wait();
}
catch(InterruptedException e) {
// don't handle for simplicity
}
}
// at this point there has to be an
// available element
i = (Integer)m_vect.firstElement();
m_vect.removeElement(i);
return i;
}
// wait for a queue element with a timeout
// input : none
// output : first Integer object in queue or null
// if the queue was empty
public synchronized Integer Get(long timeout) {
Integer i;
// wait for an element and return it
if (m_vect.isEmpty() == true) {
try {
// wait once with timeout
wait(timeout);
}
catch(InterruptedException e) {
// don't handle for simplicity
}
}
// one try to get an element, then give up
if (m_vect.isEmpty() == false) {
i = (Integer)m_vect.firstElement();
m_vect.removeElement(i);
}
else {
// indicate timeout with null value
i = null;
}
return i;
}
// insert an element
// input : Integer object
// output : true if element inserted
// false if queue is full
public synchronized boolean Put(Integer i) {
// check for upper bound
if (m_vect.size() >= m_size) {
// vector is full, return an error
// no insertion
return false;
}
// insert the element as an object
m_vect.addElement(i);
// notify first waiting thread
notify();
// element is inserted
return true;
}
}


EventFlag. Listing 2 shows a variation in which the change of condition may activate more than one thread, and uses the wait and notifyAll methods. An integral event flag variable provides a bit string that can be set by any thread. When bits in the event flag change, all waiting threads are given an opportunity to reevaluate the current state and continue to wait, or return.

// the EventFlag class that implements wait/notifyAll
public class EventFlag {
int m_flag; // the bit string flag
// read current flag value without wait
// input : none
// output : current flag value
public synchronized int Get()
{
return m_flag;
}
// wait for event flag match
// input : flag - bits to match
// output : current flag value or 0 if thread is interrupted
public synchronized int Get(int flag) {
// wait until bits match
while (m_flag != flag) {
try {
wait();
}
catch(InterruptedException e) {
// thread was interrupted
return 0;
}
}
// return the current unmasked flag value
return m_flag;
}
// set bits in the flag
// input : flag - bits to set
// output : current flag value
public synchronized int Set(int flag) {
m_flag = flag;
// notify all waiting threads to retry
notifyAll();
// yield to let waiters execute to
// recheck the condition
Thread.currentThread().yield();
return m_flag;
}
}

A Clear Pattern

The native support of the Monitor/Condition variable methodology makes it easy to write thread safe classes. The methodology provides a clear design pattern for implementing mutual exclusion and thread safe support of shared resources.

David Howard is a principal software engineer at Sierra Nevada Corp., a defense electronics firm. He has 15 years experience in embedded systems programming, including five years at Ready Systems working on the VRTX operating system kernel.