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 Q & A


November 1996: Java Q&A

How Do Threads Work and

How Can I Create a

General-Purpose Event ?

Cliff Berg

Cliff, vice president of technology of Digital Focus, can be contacted at [email protected] To submit questions, check out the Java Developer FAQ Web site at http://www.digitalfocus.com/faq/.


Most modern operating systems allow application programmers to create separate lightweight processes, usually called "threads," to take advantage of a computer's multiprocessor architecture, or simply to allow multiple operations to occur simultaneously. Web applications are good candidates for multiprocessing because the limited bandwidth of the user's communication line mandates that the application not wait while information is being transferred. Netscape would be unusable, for example, if it forced users to wait until an entire page of information were downloaded, graphics and all, before giving users the opportunity to interrupt or otherwise interact with the program.

Java's built-in language support for thread programming therefore is a major advantage over other languages for creating web applications, or any applications in which multithreading is important. Since threads are language supported, users can rely on a well thought out and robust model for thread programming that is fully integrated with the language's other features, including Java's exception handling. Also, because users do not have to call operating-system thread-library functions directly, a Java thread program can be written to be operating-system independent.

Scheduler

The primary way of scheduling an event using the Java thread mechanisms is to create a thread and put it into a wait state for a specified period of time. When the thread comes out of its wait state, it can then execute a callback on an object that was passed to it when the wait began.

In designing the Scheduler class presented here, I considered two approaches. The first (which I ultimately used) was to assign a thread to an event at the time of scheduling. In this approach, when the method schedule() is called, a thread is immediately assigned and put into a wait state.

A second approach was to create a separate scheduler thread (independent of the main program thread) that would enqueue future events and run threads when those events occurred. In this approach, schedule() does not assign a thread immediately when it is called, but instead inserts the event into an ordered list. The scheduler thread must then set a timer to wake the scheduler up when the next event in the list is due. This approach has some advantages for some applications. For example, since a thread resource is not assigned until it needs to execute, there is no limit to the number of future events that can be scheduled at any one time. In most uses of threads, however, this is not a consideration, and so I leave that implementation to the reader.

A callback in Java involves defining an interface that specifies the callback method's name and argument signature. Example 1 defines an interface called "Schedulable." Users of the Scheduler class must provide an implementation for this interface in their code. When the program calls the scheduler's schedule() method and passes the object that implements Schedulable; the scheduler will arrange for a thread to call onEvent() for this object at the appropriate time. The onAbort() method is called when the scheduler is garbage collected, which may be asynchronous relative to the thread's processing.

To minimize the overhead of creating a thread every time an event is to be scheduled, Scheduler creates and maintains a pool of threads. These threads are kept in a wait state, waiting to be assigned to a task. The behavior of these threads is defined by the EventThread class, which is a subclass of the Java Thread class.

Consider two versions of the Java Thread class constructor; one that takes no arguments, and one that takes an Object argument. If the first version is used, the thread class's run() method is called automatically when the thread is started. If the second version is used, then the Object argument's run() method is called instead. In the latter case, the Object must implement the Runnable interface, which defines the signature of the run() method. I use the first form.

A thread is started by calling its start() method. You cannot call run() directly, because even though you have a Java Thread object, the thread's execution context has not actually been set up yet. When you call start(), a true thread is created, and control is passed to the run() method in the context of that thread.

Synchronization

The primary mechanism to achieve synchronization in Java is a monitor, which is used to coordinate access to an object method or block of code that is labeled as synchronized. When an execution thread enters a synchronized section of code, the Java run time gives the monitor to that thread; any other thread that attempts to enter any synchronized code belonging to the same object instance is put into a blocked state until the monitor is released.

There are several synchronization problems that must be solved with the Scheduler class. First, you must guarantee that schedule() is not called until all the threads in the thread pool are created, initialized, and in an identical and well-defined state, waiting to be called. The EventThread's run() method calls wait() after it starts (see Listing One), which puts the thread into a wait state. However, you cannot guarantee that this will occur before your main thread (or some other thread) calls schedule(), because you do not have any direct control over the time allocated to these threads. Even if you are running in a time-sliced environment, you should not assume that the lines of code between your call to start() and the thread's call to wait() will execute before you make your first call to schedule() from the main thread. Instead, you must guarantee that this will happen.

To achieve this, implement a simple handshake. Each time Scheduler's constructor creates and starts a thread, it calls wait() itself. It does this inside of a code block that is synchronized on the newly created EventThread object's monitor, so your call to wait() is saying, "go to sleep, and wait until I am notified of a change in the state of the monitor." When wait() is called, all monitors held by the thread executing the wait() call are released temporarily, pending the return from the wait(). This allows the wait() method to act as a gate: Calling wait() opens the gate for other threads in synchronized methods to execute.

The call to the thread's start() method is inside of the synchronized block as well, guaranteeing that the new thread will block when it encounters a synchronized method. You have synchronized the run() method so that the thread will block when it enters run(), because the Scheduler constructor holds the thread's monitor. The thread will remain blocked until the monitor is released when the Scheduler enters its wait state.

Once the scheduler executes its own wait() and releases the thread monitor, the thread can then proceed with its run() method. The first thing run() does is call notify(). This sends a signal to a waiting thread (the scheduler), saying, "start trying to get this monitor again." The monitor is not available yet, however, because the thread has not released it. It will not release it until it goes into another wait state. run() does exactly that: After calling notify() it immediately goes into a wait state and waits to be scheduled for some task. Thus the thread is now in a well-defined state. The scheduler does not resume until this state has been achieved.

A scheduler client schedules events by calling the schedule() method, which does two things: allocates a thread from the thread pool and calls that thread's schedule() method, EventThread.schedule(). This latter method is synchronized to protect the thread's state variables--schedule() may be called from other threads, at any time. However, it is also synchronized for another reason.

When schedule() is called, it sets the thread's control variables, including a delay-time value, and then wakes the thread up, by calling notify() and giving the thread back its monitor. This works because this code, while it is inside of the EventThread class, is actually being called from another (possibly the main) thread. This is a case of re-entrancy. It is true that there is a thread of execution associated with the thread object; however, that does not mean that other threads cannot execute the thread object's methods. Since the thread's schedule() method is synchronized, the thread executing the schedule() method will release its monitor on the thread object when it completes, thereby allowing the thread object's own execution thread to grab the monitor.

Figure 1 shows the various execution thread paths in different colors as they pass through the system's objects. Note that the blue path, which represents the scheduler's activities, passes through EventThread methods, while the red path, which represents the pool thread's activities, passes through its own methods, and through some methods belonging to the scheduler. In the figure, when the blue path through the thread object's notify() call completes, the monitor is released by the blue execution thread; this allows Thread-1 (the red path) to return from its wait() call, so that it can enter wait(delay).

The thread then waits for the time period specified in the delay control variable that was set by schedule(). When the delay time is up, the thread wakes back up, and calls the onEvent() callback. After the callback has completed, the thread then returns the thread object to the thread pool. To do this, it must call the scheduler's deallocateThread() method, which is synchronized to guarantee the integrity of the thread pool data structures, since deallocateThread() is being called asynchronously by each thread in the thread pool. After deallocating itself, the thread then returns to the start of its run loop, and re-enters the first wait state, ready to be scheduled again.

There may be some confusion about the number of different methods Java provides for changing a thread's state, in particular for putting a thread into a passive mode. The methods available are: wait(), sleep(), and suspend(). wait() is an Object method whose purpose is to synchronize the release of an object's monitor with the thread's change of state. Its actual affect is to release the monitor owned by the execution thread calling wait() and then to go into a blocked state, all in one atomic operation.

The sleep() and suspend() methods, on the other hand, do not perform any synchronization with regard to monitors. In fact, on some platforms, the suspend() method does not guarantee the suspension of the specified thread before the method returns.

The disadvantage of using sleep() is that There is no way to abort a sleep except by the elapse of the specified sleep time. Calling interrupt() has no affect on a sleeping thread, even though you must wrap a sleep() call in a try block that catches InterruptedException. (The sleep method is like a college roommate of mine from decades ago: once asleep, he would sleep until he was ready to wake up, and nothing could interrupt that sleep!)

The notify() method does not actually relinquish the monitor. It merely notifies any thread in a wait (queued) state to unfreeze itself in the object's monitor queue. The enqueued thread then continues to wait, until the current thread releases the monitor by going into a wait state or exiting a critical section.

Only thoughtful application design can prevent deadlock: Java does not protect you from a bad design, and provides no automatic deadlock detection or prevention. I have safeguarded against deadlock by synchronizing access to the thread pool, so that clients calling schedule can be guaranteed that you will never try to schedule a thread that is not available. The schedule() method blocks until it obtains the target thread's monitor. However, you know that the target thread is in a wait state, or it would not be marked as available, and waiting threads cannot hold monitors. Thus, you never block on a thread that holds a monitor. Still, this does not mean that a user program could not cause a deadlock by carelessly or purposefully misusing the scheduler.

Rescheduling

Rescheduling an event is an important capability. For example, less-important pending events may need to be rescheduled to occur after a more important event has completed.

To unschedule an event, you interrupt the thread from its timed wait state by throwing it an exception. To accomplish this, you call the thread's stop() method and pass it an InterruptedException. The exception handler in the thread's run() method catches this exception and sends control to the start of the run loop where it re-enters the wait state. You then issue another schedule operation. This entire sequence of events must be synchronized with a wait() operation, so that you can once again guarantee that the thread is in a wait state before you attempt the call to schedule().

For infinitely recurring events, you take a shortcut. You permanently allocate a thread for the event and prevent the thread from ever entering the first wait state again once it leaves it: Also, you never return the thread to the pool. In this way, once a recurring event is scheduled, it continues to happen forever, each time after the specified interval, until it is rescheduled.

The duration of the onEvent() callback is not known or taken into account in scheduling recurring events. The time between executions is actually the specified time delay plus the time to execute the method. For applications in which the delay must be precise, it may be necessary to modify the algorithm to calculate true elapsed time. If onEvent() takes longer than the delay, you can either throw out events whose time has passed or execute them sequentially until the events are caught up.

Thread Priority

It may be desirable to modify the priority at which the callback is run. To accommodate this, the schedule() method has a priority argument. When you run the callback, you simply save the current priority, set the thread priority to the desired value, and when the callback returns, restore the old value.

Some operating systems use priority as a means of synchronization. For example, in VAX VMS, the system's interrupt routines each have assigned priorities, and the system relies on these priorities to ensure that things happen in the right order. You could have used priority-based synchronization for the scheduler application, but unfortunately, there are inconsistencies in the way thread priorities are handled on different operating systems, and some Java implementations are vulnerable to this inconsistency. For example, in the Solaris environment, lower-priority threads can run when a higher-priority thread has used up its time slice. This violates the Java thread priority model, which requires that if there are n available processors in the system, n highest priority threads will be running on them at any given time. A program that relies on thread priorities may work on some platforms, but not on others. This technique should therefore be avoided.

There is another difficulty with priority. The Java model requires that once a thread owns a monitor, it is guaranteed to keep the monitor until it enters a wait state or otherwise releases it. Yet on some platforms, a higher priority thread may grab the monitor, forcing the monitor owner to enter a blocked state without calling notify() or releasing the monitor, thereby violating the critical section. This is because on some platforms, a higher-priority thread has the right to grab resources held by lower-priority threads. For this reason, you should use priorities carefully. A workaround for this is to make sure that sections of code that raise their priority do not call any synchronized methods. Fortunately this is a known problem, and it is anticipated that those few platforms that have this problem will be corrected.

Finally, some platforms do not implement the normal range of Java priorities (1 through 10). For example, on Windows 95/NT, priority levels of 4, 5, and 6 appear to map to the same internal thread priority value. You should therefore not rely on specific priority levels; you should make priority changes of at least two or more and you should also should use the MIN_PRIORITY, NORM_PRIORITY, and MAX_PRIORITY constants.

Cleanup

Cleanup is not fun, which is why Java has a built-in garbage collector. Usually you don't have to worry about it. However, garbage collection does not help deallocate non-memory resources such as files and sockets; nor is it orderly.

When the Scheduler is garbage collected, the system calls its finalize() method, as it would for any object. In Scheduler.finalize() you explicitly call stop() for every thread in the thread pool. This ensures that all threads are killed before you exit. One caveat is that the call to stop() is asynchronous with the threads' execution, so there is no telling what any one thread is doing when it is abruptly stopped. Fortunately, you can trap the stop call, do your cleanup, and then proceed with the stop. You do this by wrapping the thread's onEvent() call in a try block that catches the ThreadDeath error. The catch clause calls Schedulable's onAbort() method, which gives the client object an opportunity to gracefully terminate execution. It then re-throws the ThreadDeath error, which kills the thread's execution context.

Summary

The multithreaded event scheduler presented here will work on any Java platform. The ability to write portable multithreaded programs is a major advantage. Multithreading is often a requirement of high-performance systems, but also adds complexity. Language support for threading reduces the complexity considerably. This provides an argument for using Java for performance-intensive applications. Native Java language compilers are starting to become available, making fast execution a reality for Java, with performance comparable to C++. With usability, platform-independence, and performance, Java may well become the general-purpose language of choice.

Example 1: The Schedulable Interface

interface Schedulable
{
  public void onEvent(Object arg);
  public void onAbort();
}

Figure 1: Threads of control.

Listing One

/* Scheduler.java -- A scheduler for scheduling asynchronous future events. 
 * Provides for specifying event execution priority, and for recurring events.
 */

/** Callback object interface. */

interface Schedulable
{
    public void onEvent(Object arg);
    public void onAbort();
}
/** A scheduler for scheduling asynchronous future events. For each scheduled 
 * event, a thread is allocated from a thread pool, and then the thread waits 
 * until the event time has arrived. The thread then invokes onEvent() on the 
 * specified object. When onEvent() completes, the thread is returned to the 
 * thread pool. There are also provisions for specifying an event execution 
 * priority; and for recurring events. If an event is recurring, its thread is
 * permanently allocated, and is never returned to the thread pool.
 */

class Scheduler
{
    protected EventThread[] threads; // the thread pool
    protected boolean[] allocated;   // allocation flag for each thread

    /* Constructor. Parameter specifies how large thread pool should be. */

    public Scheduler(int noOfThreads)
    {
        threads = new EventThread[noOfThreads];
        allocated = new boolean[noOfThreads];

        // Create the thread pool
        for (int i = 0; i < threads.length; i++)
        {
            allocated[i] = false;
            EventThread thread = new EventThread(this);
            threads[i] = thread;
            synchronized (thread)
            {
             thread.start(); // this will start a separate thread,
                    // which will then call wait() and block (which
                    // releases its monitor so we can get past the next line...
                try
                {
                    thread.wait();  // this blocks until the thread calls
                    // notify() and then blocks (which releases its monitor,
                    // allowing this statement to return)
                }
                catch (InterruptedException ex)
                {
                }
            }
        }
        // We can now be sure that all threads are created and are in a blocked
        // state, waiting to call notify(). That is what schedule() does.
    }
    /** Gracefully stop the threads in the thread pool. */
    public void finalize()
    {
        // Stop all the threads that are not blocked...
        for (int i = 0; i < threads.length; i++)
        {
            if (threads[i].isAlive()) threads[i].stop();
        }
    }
    /** Schedule thread to run at a future time. The Schedulable.onEvent()
         * method will be called for object after a real-time delay of "delay"
         * milliseconds. The thread's handle is returned, which we can later 
         * use to reschedule the thread. If "recurring" is true, then a new 
         * event will be scheduled automatically each time onEvent() is called.
         * This method must be synchronized in case multiple threads in an 
         * application call this method for this Scheduler object.
     */
    public synchronized EventThread schedule(long delay, Schedulable object, 
                                   Object arg, int priority, boolean recurring)
    throws
        InsufficientThreadsException
   {
        // Pick a thread from the thread pool
        EventThread thread = allocateAThread();
        if (thread == null) throw new InsufficientThreadsException();
        // Schedule an event for that thread
        thread.schedule(delay, object, arg, priority, recurring);
        // Return a unique identifier for the event
        return thread;
    }
    /** Unschedule the future event for a thread, and reschedule it. */
    public void reschedule(EventThread thread, long delay, Schedulable object, 
                                   Object arg, int priority, boolean recurring)
    throws
        InsufficientThreadsException
    {
        thread.reschedule(delay, object, arg, priority, recurring);
    }
    /** Allocate a thread from the thread pool. */
    protected EventThread allocateAThread()
    {
        for (int i = 0; i < threads.length; i++)
        {
            if (allocated[i]) continue;
            allocated[i] = true;
            return threads[i];
        }
        return null;
    }
    /** Return a thread to thread pool. This method must be synchronized 
    * in case multiple threads in an application call this method for this
    * Scheduler object, and also because threads call this to return 
    * themselves to the thread pool.
    */
    public synchronized void deallocateThread(EventThread thread)
    {
        for (int i = 0; i < threads.length; i++)
        {
            if (threads[i] == thread)
            {
                allocated[i] = false;
                return;
            }
        }
    }
}
/** A schedulable thread. */
class EventThread extends Thread
{
    protected Scheduler scheduler;    // the scheduler for this thread
    protected long delay;             // wait for this time
    protected Schedulable object;     // then call onEvent() for this object
    protected Object arg;             // a parameter for onEvent()
    protected int priority;           // execute onEvent() at this priority
    protected boolean recurring;      // reschedule the event every time

    /** The constructor. */
    public EventThread(Scheduler scheduler)
    {
        this.scheduler = scheduler;
    }
    /** The thread's run method */
    public synchronized void run()
    {
        notify();   // this notifies the scheduler, which is waiting to be
            // notified, that it should unfreeze itself in the thread's
            // monitor queue.
        for (;;)
            // ever
        {
            // Wait to be called upon; blocks until a call to schedule()
            // results in a notify()
            System.out.println(Thread.currentThread().getName() + 
                                                           " going to sleep");
            try
            {
                if (! recurring) wait();
            }
            catch (InterruptedException ex)
            {
            }
            System.out.println(Thread.currentThread().getName() +" awake now");

            // Sleep until the specified time has elapsed
            try
            {
                // This is the real wait, requested by the scheduler
                System.out.println(Thread.currentThread().getName()
                    + " waiting for " + delay + " milliseconds");
                wait(delay);
            }
            catch (InterruptedException ex)
            {
                // We are being rescheduled: abort the current sleep
                System.out.println(Thread.currentThread().getName() + " unscheduled");
                recurring = false;
                notify();
                continue;
            }
            // Do the callback, at the specified priority
            int savep = getPriority();
            setPriority(priority);
            try
            {
                object.onEvent(arg);
            }
            catch (ThreadDeath td)
            {
                object.onAbort();
                throw td;
            }
            setPriority(savep);
            // Thread's work is done; return it to the pool
            if (! recurring) scheduler.deallocateThread(this);
        }
    }
    /** Schedule a wakeup for this thread. Note that this is called from 
     * other threads, including possibly from the main thread.
     */
    public synchronized void schedule(long delay, Schedulable object, 
                                  Object arg, int priority, boolean recurring)
    {
        this.delay = delay;
        this.object = object;
        this.arg = arg;
        this.priority = priority;
        this.recurring = recurring;
        // Now, resume this thread to tell it how long to wait for
        System.out.println(
            Thread.currentThread().getName() +" waking up thread "+ getName());
        notify();
    }
    /** Reschedule this thread. */


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.