Now that we have the base logic of the CPUScheduler written correctly, we need to make sure the CPUScheduler class is itself thread safe and that we haven’t introduced any race conditions into the scheduler by having incorrectly synchronized data. We’ll go through this process in a series of stages because the example illustrates the necessary steps that you must take in designing any class to work with multiple threads.

At first glance, there don’t appear to be any variables that need synchronization: the only instance variable that needs to be protected is the variable threads, and all changes to the threads variable occur via methods of the CircularList class that are already synchronized. But what would happen if you called the remove-Thread() method and removed the thread that the CPUScheduler has marked as the current thread? It would be an error for the CPUScheduler to change the priority of this thread once it has been removed from the threads list, so the removeThread() method must somehow inform the CPUScheduler that the current thread has been removed.

This means that the variable current must become an instance variable so that both the run() and removeThread() methods can access it. We can then synchronize access to that variable. Here’s the new CPUScheduler class:

public class CPUScheduler extends Thread {
    ...
    private Thread current;
    public void removeThread(t) {
        t.setPriority(5);
        threads.delete(t);
        synchronized(this) {
                              if (current == t)
                                  current = null;
                          }
    }
    ...
    public void run() {
        ...
        try {
            Thread.sleep(timeslice);
        } catch (InterruptedException ie) {};
        synchronized(this) {
                              if (current != null)
                                  current.setPriority(2);
                          }
    }
}

Alternatively, we could make the run() and removeThread() methods themselves synchronized:

public synchronized void run() {
        ...
    }

    public synchronized void removeThread(Thread t) {
        ...
    }

As we’ve seen, making the run() method synchronized is typically a bad idea, so we’ll reject this idea for now, but we’ll be revisiting this decision soon.

We’ve synchronized all the variables of our CPUScheduler, but we’re still not protected from threads that exit while they are under our control.

In particular, the run() method changes the priority of a thread, which is a valid operation only if a thread is in the runnable state. What happens if the thread that we’ve assigned to level 4 exits its run() method while our CPUScheduler is sleeping? When the CPUScheduler wakes up, it tries to set the priority of that thread, which is now in the exiting state, to 2—an operation that generates an exception. Similarly, if the thread that is running decides to call the stop() method of one of the priority 2 threads in the CPUScheduler’s list, then the next time the CPUScheduler selects that thread and sets its priority, we’ll get an exception.

So we need to place all the calls to the setPriority() method inside a try/catch clause in order to be alerted to these types of situations. This means we must modify our code everywhere we call the setPriority() method:

public void removeThread(Thread t) {
        try {
                              t.setPriority(5);
                          } catch(Exception e) {}
        threads.delete(t);
        synchronized(this) {
            if (current == t)
                current = null;
        }
    }

    public void run() {
        while (shouldRun) {
            ...
            try {
                                  current.setPriority(4);
                              } catch (Exception e) {
                                  removeThread(current);
                              }
            ...
            synchronized(this) {
                if (current != null)
                    try {
                                          current.setPriority(2);
                                      } catch (Exception e) {
                                          removeThread(current);
                                      }
            }
            ...
        }
    }

Note that in in the run() method, when the exception is thrown we need to remove the thread from the list of threads we’re interested in, which means that we must also use the catch clause in the removeThread() method.

We’ve made the methods of the CPUScheduler thread-safe, but what about the class itself? What if two threads try to create a CPUScheduler? This would be very confusing: we’d end up with two scheduling threads that would compete with each other to schedule other threads. So we need to allow only one instance of the class to be instantiated. We’ll do this by creating a static variable in the class and testing it to make sure that an instance of the CPUScheduler class doesn’t already exist. Because we can’t make the constructor itself synchronized, we’ll also need to introduce a synchronized method to access this static variable. Thus the constructor and related code for the class now look like this:

public class CPUScheduler extends Thread {
    private static boolean initialized = false;
                      private synchronized static boolean isInitialized() {
                          if (initialized)
                              return true;
                          initialized = true;
                          return false;
                      }

    public CPUScheduler(int t) {
        if (isInitialized())
                              throw new SecurityException("Already initialized");
        threads = new CircularList();
        timeslice = t;
    }
}

If all the threads under its control exit, the CPUScheduler itself exits. In a program where the tasks are well defined at the beginning of execution—like the TestThread class we’ve looked at so far—that might be fine. But what if we wanted to add the CPUScheduler to our TCPServer? As presently written, the CPUScheduler wouldn’t work for that case: as soon as no clients were connected to the TCPServer, the CPUScheduler would exit, and any further clients that connected to the server would not be timesliced.

Instead, we need to make the CPUScheduler a daemon thread and adjust the logic of its run() method. This should make sense: the CPUScheduler is only useful when there are other threads in the program that it can schedule. In the TCP-Server case, there will always be at least one other thread in the program: the listener thread of the TCPServer. That listener thread creates other threads for the CPUScheduler to manipulate as clients connect to the server. The implementation of our timesliced TCPServer to perform calculations looks like this:

import java.net.*;
import java.io.*;

public class CalcServer {
    public static void main(String args[]) {
        CalcRequest r = new CalcRequest();
        try {
            r.startServer(3535);
        } catch (Exception e) {
            System.out.println("Unable to start server");
        }
    }
}

class CalcRequest extends TCPServer {
    CPUScheduler scheduler;
    CalcRequest() {
        scheduler = new CPUScheduler(100);
        scheduler.start();
    }

    void doCalc(Socket s) {
    }

    public void run(Socket s) {
        scheduler.addThread(Thread.currentThread());
        doCalc(s);
    }
}

Every time the run() method of the CalcRequest class is called, it is called in a new thread, so we need to add that thread to the CPUScheduler that was created in the constructor of the class. As long as the CPUScheduler doesn’t exit when there are no threads to schedule (which now means simply that no client is currently connected), we’ll have a timesliced calculation server. During an active session of our CalcServer, we’ll have these threads:

We can gracefully shut down the CalcServer by setting the shouldRun flag of the server to false; eventually the client threads complete their calculation and exit. When all the client threads have exited, only the daemon CPUScheduler thread remains in the program, and the program terminates.

We need to change the CPUScheduler so that instead of returning when there are no threads to be scheduled, it simply waits for more threads. Here’s the entire code for the modified CPUScheduler class (we’ll show the entire class here, since at this point, we have a complete implementation):

public class CPUScheduler extends Thread {
    private CircularList threads;
    private Thread current;
    private int timeslice;
    private static boolean initialized = false;
    private boolean needThreads;

    private static synchronized boolean isInitialized() {
        if (initialized)
            return true;
        initialized = true;
        return false;
    }

    public CPUScheduler(int t) {
        if (isInitialized())
            throw new SecurityException("Already initialized");
        threads = new CircularList();
        timeslice = t;
        setDaemon(true);
    }

    public synchronized void addThread(Thread t) {
        t.setPriority(2);
        threads.insert(t);
        if (needThreads) {
                              needThreads = false;
                              notify();
                          }
    }

    public void removeThread(Thread t) {
        threads.delete(t);
        synchronized(this) {
            if (t == current)
                current = null;
        }
    }

    public synchronized void run() {
        setPriority(6);
        while (true) {
            current = (Thread) threads.getNext();
            while (current == null) {
                                  needThreads = true;
                                  try {
                                      wait();
                                  } catch (Exception e) {}
                                  current = (Thread) threads.getNext();
                              }
            try {
                current.setPriority(4);
            } catch (Exception e) {
                removeThread(current);
                continue;
            }
            try {
                wait(timeslice);
            } catch (InterruptedException ie) {};
            if (current != null) {
                try {
                    current.setPriority(2);
                } catch (Exception e) {
                    removeThread(current);
                }
            }
        }
    }
}

In the constructor, we’ve set the thread to be a daemon thread—the point of this adjustment. Note that we also changed the run() method so that when we try to retrieve a thread from the list, we loop until one is available. If no thread is in the list, we wait until one is available, which requires that we add a flag to the addThread() method to signify whether it should notify the CPUScheduler thread that a thread has been added.

In addition, note that we’ve changed the run() method itself to a synchronized method and replaced the call to the sleep() method with a call to the wait() method. This is one example of the exception to the general rule that the run() method should not be synchronized: since we actually spend more time waiting in this method than executing code, its quite okay to synchronize the run() method, since it will release the lock whenever it waits for something to happen.

What happens in our scheduler if the currently running thread blocks? Let’s see what would happen to our TestThread program if the currently running thread suddenly entered the blocked state. We’d start out with the threads in a state like this:

                  PRIORITY 2:  t3 -> t1 -> NULL
PRIORITY 4:  t2 -> NULL
   BLOCKED:  CPUScheduler -> NULL

Thread t2 is the currently running thread, executing its calculations while the CPUScheduler is sleeping. If t2 now enters the blocked state for some reason, we end up with threads in this state:

                  PRIORITY 2:  t3 -> t1 -> NULL
PRIORITY 4:  NULL
   BLOCKED:  t2 -> CPUScheduler -> NULL

This means that t3 becomes the currently running thread, even though it’s at priority 2. When the CPUScheduler wakes up, it resets the priority of t2 to 2, sets the priority of t3 to 4, and goes back to sleep, leaving our threads in this state:

                  PRIORITY 2:  t1 -> NULL
PRIORITY 4:  t3 -> NULL
   BLOCKED:  t2 -> CPUScheduler -> NULL

Everything is okay again, but at some point it will be t2’s turn to be priority 4. Since the CPUScheduler has no way of determining that t2 is blocked, it sets the priority of t2 to 4. The Java scheduler again selects one of the threads at priority 2 to be the currently running thread.

Our code was correct: the threads involved all got some timeslice in which to run. But there was a short period of time during which the CPUScheduler slept, the priority 4 thread blocked, and a priority 2 thread became the currently running thread. In effect, this priority 2 thread stole some CPU time; it could do this because there was a time gap between when the priority 4 thread blocked and the priority 6 thread woke up.

It’s probably not a crisis that this happened, since once the CPUScheduler woke up, we got back to the thread state we wanted. We could have prevented this CPU stealing from happening if somehow we knew when the priority 4 thread had blocked. However, on a native-thread platform, we cannot prevent a lower-priority thread from running at some point anyway, which is really just a variation of the behavior that we’re discussing here. So solving this problem is not something that we’ll be able to do in an absolute sense.

It is conceivable that on a green-thread platform, we could create a new thread within the CPUScheduler class at priority 3. When the priority 4 thread blocks, this priority 3 thread would become the currently running thread; this priority 3 thread could inform the priority 6 thread that it should wake up and perform some scheduling. Note that on a native-thread platform this does not work: the priority 3 thread might still run even if the priority 4 thread has not blocked, and on a Windows platform, priority 3 and 4 share the same underlying operating system priority. Altering the priority levels of the threads to avoid this overlap—by, for example, running the scheduler at priority 8 and the target thread at priority 6—is a possibility, but we’ve seen that putting a CPU-intensive thread above the default priority level (especially the level at which the system GUI thread runs) is not always a good idea. And this does not prevent the priority 3 thread from running when the target thread is not blocked.

Even on a green-thread platform, this problem is impossible to solve in the general case. If all the threads to be scheduled were to block, then the priority 3 thread would continually run, consuming a lot of CPU resources but performing no real work. In the first edition of this book, we showed how to overcome that problem by suspending the priority 3 thread, but now the suspend() method has been deprecated, so that solution is no longer an option. And since the benefit provided by such a solution would be very marginal, we’re not too worried that such a solution does not exist.

The moral of the story is what we’ve said all along: Java’s scheduling mechanisms give you some control over how threads are scheduled, but that control is never absolute.