28 - Multithreading Lite

By the end of this chapter, the reader will be able to:

In the Olden Days, it wasn't unusual for operating systems to be single-tasking... or at best, co-operatively multitasking. Single-tasking means that the operating system can deal with only one task at a time. Co-operative multitasking means that although the operating system can have more than one program running at a time, only one of them can actually be doing anything... the rest sit idle until spurned into action by the gentle carresses of your fingers on the keyboard.

Most home operating systems at one time followed this structure:

• DOS
• Macintosh System 7 and earlier
• Windows 2.11 and earlier

This was a significant weakness - you couldn't be writing a word document whilst listening to an MP3, for example. The limitations of the operating system were such that the system couldn't support multiple programs running at once, limiting the usefulness of computers as genuine tools for increasing productivity.

However, such limitations are rarely encountered in modern (or even semi-modern) operating systems, where pre-emptive multitasking is the norm. Genuine multi-tasking is something that can be achieved only on multiprocessor systems, but most operating systems nowadays can do a passable imitation that is suitable for the vast majority of consumer requirements.

Pre-emptive multi-tasking works by sharing out a processor's limited resources between multiple programs - a technique called time-slicing. The operating system does a little bit of work on one program, then a little bit of work on another, and then another, and so on, until it comes back to the original program and starts the whole process all over again. The most common strategy for handling this distribution of CPU cycles is often known as round robin, and seeks to balance the competing demands for processor power of running applications.

Each of these running programs is known as a process, and processes that are running together within the round robin scheme are known as concurrent processes:

Fig 28.1: Four Concurrent Processes

In this diagram, we see four processes that each have an equal share of the processor 'pie'. If the processor can execute a million cycles in a second, we can reasonable expect that each process will have a quarter of a million cycles every second within which to do its processing.

Processes can be weighted to have higher priorities, which means they get a bigger share of the pie in comparison to all the other concurrent processes:

Fig 28.2: Three Concurrent Processes with Process Two Given Higher Priority

In this diagram, Process 2 has been set to a higher priority, and so will get about 50% of the processing time, whereas process 1 and process 3 will each gain about 25%.

Individual processes each have their own memory locations, and these are (ideally) protected against the tampering of other processes. This is something that is dealt with by the process management routines of the operating system. Obviously some operating systems are better at this than others.

This framework is flexible, but sometimes we want to extend it by allowing individual processes to perform more than one task at a time. Each process has a thread of execution (or just thread) that represents the flow of processing through a program. Some programming languages, like Java, support the building of multi-threaded applications. Effectively, we apply the time-slicing concept to each process - imagine we had a birthday party where there was only one cake but four families. Each family gets an equal slice of the pie, but then their slice has to be further sliced to ensure that everyone within the family gets a fair share.

Fig 28.3: Process Broken up into Threads

The overall framework of how threads actually work is massively complicated and well beyond the scope of this book. We will touch only briefly on some of the more simple aspects of the theory and practise.

The applications and applets we have written up until this point have been single threaded - all of the work has been handled in the event thread which deals with triggering the appropriate method when events occur. However, there is a problem with this, in that we can write code that hogs the processor and makes our program entirely unresponsive. Consider this very simple example:

Fig 28.4: Storyboard

import javax.swing.*; import java.awt.*; import java.awt.event.*; public class Count extends JFrame implements ActionListener { public JButton go, stop; public JLabel counter; public JPanel buttons; boolean increment; int countVar; ... public void actionPerformed (ActionEvent e) { if (e.getSource() == go) { increment = true; incrementCounter(); } else { increment = false; } } public void incrementCounter() { while (increment == true) { countVar += 1; counter.setText ("Counter is " + countVar); if (countVar > 100) { countVar = 0; } } } }

The looping is based on the increment boolean variable. If we press the go button, it is set to true and incrementCounter is called. IncrementCounter will loop until increment is set to false.

We press go, and we get the following screen:

Fig 28.5: Screenshot

We can see that the go button has clearly been pressed - but we never get to see the number displayed, and the application becomes completely unresponsive. We can never click on stop to set the increment variable to false because the application simply doesn't have any processing time to deal with the event handling. Our incrementCounter method is completely hogging all the resources for the process.

For many programs, this isn't a problem. If you have a process that is going to compute pi to ten million decimal places when you press a button, you'd expect it to take a while. Provided you don't need to do anything else with that application while it is computing the value, it's fine.

However, if you have an application that has processor intensive code and is also expected to be responsive, it is an issue. Alas, it is an issue that affects us personally since we've been working so much with GUI applications - these are expected to be responsive. Either we limit ourselves to writing programs that have little processing associated with them, or we find a way to solve this problem.

The application of a multithreaded approach to the application will ensure a satisfactory solution. Multithreading works by providing multiple threads of execution through our program - so we can have one thread that deals with handling events and things, and another that deals with processing. In this way, our application will still be responsive and processing can go on while our application is doing other things (albeit at a slower rate). Sounds like something that would be useful to adopt for our program above!

One of the fundamental classes of the Java programming language is the Thread class. Thread handling is not an 'extra' in Java, it is something that has been programmed into the very bones of the language.

You may remember the Thread class as a way to delay the execution of a program for a short period of time by using its sleep method. It's much more useful than just this - we can also create classes that extend Thread, which is a similar thing to creating a class that extends JApplet or JFrame... it provides a context for execution.

In the thread architecture, we make use of a method called run to deal with the processing that is to be associated with a particular thread. This is similar to init/paint in an applet or main in an application. All of the code that belongs to the main execution of the thread goes here, and when the run method has finished executing the thread will terminate.

We trigger a thread running by calling the start method on the thread from whatever code creates an instance of our class. The start method deals with creating a new thread, and as a standard part of its execution it will invoke the run method.

Java also provides a stop method that terminates execution of a thread. Use of this is not encouraged, for reasons that are beyond the remit of this chapter. Instead, we base the continuing execution of a thread on the state of some internal variable. We then provide a method that changes the state of that variable. Instead of making a reference to the standard stop method, we instead invoke the termination method we write ourselves to kill (or terminate) a thread.

Let's look at the example of our counter above as a multi-threaded application. First we need a class that extends Thread and will deal with the processing:

import javax.swing.*; public class CounterThread extends Thread { public JLabel myOutput; int countVar; boolean increment; public CounterThread (JLabel bing) { myOutput = bing; countVar = 0; increment = true; } public void run() { while (increment == true) { countVar += 1; myOutput.setText ("Counter is " + countVar); if (countVar > 100) { countVar = 0; } } } public void endThread() { increment = false; } }

Then in the actionPerformed of our application we need to create an instance of the thread and call the start method on it when the go button is pressed. When stop is pressed, we call endThread to terminate the execution. We need a class wide variable of type CounterThread which we will call myThread:

CounterThread myThread; ... public void actionPerformed (ActionEvent e) { if (e.getSource() == go) { myThread = new CounterThread (counter); myThread.start(); } else { myThread.endThread(); } }

Now, when we run this application we get the effect we would have expected from the original attempt - the counter increments until we press stop, at which point it stops. Fairly simple stuff - such a shame that we needed to get our hands dirty with multithreading to actually implement it.

We can deal with unresponsive programs of this type by ensuring our event handling thread simply spawns off a new thread when we're about to do some serious processing. We then let Java worry about when threads are to be executed and when others are to be swapped out.

In the example above, we created a class that extended Thread in order to make use of the multi-threaded architecture - but as we've discussed previously, only one class can be extended through Java's inheritance model. This means that if we're already extending a class, we can't make use of multithreading using this particular framework.

Java provides a second way of implementing multi-threading within an application by proving an interface called Runnable. This interface requires only that a run method be implemented in the class, but it does require a slightly more complex syntax to invoke the running of a thread.

Within the class that is to be multithreaded, we need to create a new object of type Thread, and pass it our class as a parameter. The constructor for the Thread class requires that its parameter is of a certain format. As long as our class implements the Runnable interface, it will be a valid parameter.

Our class will have no start method by default, so we will need to provide a way to start the thread running. Let's look at our example above written using this framework instead:

import javax.swing.*; public class CounterThread implements Runnable { public JLabel myOutput; int countVar; boolean increment; Thread myThread = new Thread (this); public CounterThread (JLabel bing) { myOutput = bing; countVar = 0; increment = true; } public void run() { while (increment == true) { countVar += 1; myOutput.setText ("Counter is " + countVar); if (countVar > 100) { countVar = 0; } } } public void endThread() { increment = false; } public void startMe() { myThread.start(); } }

Our updated actionPerformed method looks almost the same, but since there is no Start method provided in CounterThread, it has to instead call our new startMe method:

public void actionPerformed (ActionEvent e) { if (e.getSource() == go) { myThread = new CounterThread (counter); myThread.startMe(); } else { myThread.endThread(); } }

Other than that, the code for our application is unchanged, and we've left ourselves free to extend from another class whilst still making use of multithreading.

Using separate threads to deal with complex functionality is a useful technique, and one that by itself justifies the existence of a chapter on multi-threading in this book. Usually though when we make use of multithreading we want to use more than one extra thread to really harness the power of the framework.

For complex programs, the threads will often be working together to meet some common end, breaking a problem down into chunks and processing them independently before pooling the results.

Consider a web-based banking system... each customer dealing with their account is likely to be implemented a single thread that deals with people on an individual basis. However, any changes the customer makes to the state of their account and to the state of the bank itself is going to have to be reflected through all threads, so they will share a central bank object that handles actual transactions. This is a common structure for multi-user applications.

However, we have a problem in that we cannot determine in advance what thread is going to be executed and when. This is something that gets handled by the Java Virtual Machine, which is responsible for swapping threads into and out of execution.

We can assign a priority to a thread using the setPriority method to give it more importance when processing time is being scheduled. This is a strategy that is almost guaranteed to go very wrong very quickly unless you know exactly what you're doing.

We also have no idea when a thread is going to be swapped out of execution. It can happen in the middle of variable access, for example... if this occurs while two processes are accessing a common data source, corruption can occur. Consider the following example where two threads are accessing a single method:

int number = 0; public void adjustNumber (int num) { int temp = number; temp = number + num; number = temp; }

Thread one is scheduled and calls the method with a parameter of 10, and then executes the first two lines of code before it is swapped out. Then Thread two comes in with a parameter of 20, and completes the whole method before being swapped out. Thread one is swapped back in, and completes the rest of the method:

Fig 28.6: Thread Scheduling

In the end, when number should really be 30, it ends up being 10. Disaster!

Let's look at the same idea with a more complex example. We're going to look at an example of a bank with a number of threads accessing a common data object. We create twenty threads, and each thread is designated as either a depositor or a withdrawer. There will be an equal number of each, so ten depositors, and ten withdrawers.

Each thread will initiate multiple transactions with the account object, depositing or withdrawing 100 each time. Then, the balance of the bank will be displayed.

Since there are equal numbers of withdrawing and depositing threads, and they are each dealing with the same amount of money and an equal number of transactions, the balance of the bank should end up being what it started off at. First of all, we need a class that represents our bank.

Our bank object is going to be shared between all threads - there will only ever be a single instance of this class, regardless of how many threads are going to be executing. In this way, we ensure that there is a common data structure that allows for communication (of a sort) between different threads.

So first of all, we need to implement our Bank class:

public class Bank { int balance; public Bank (int b) { balance = b; } public void adjustBalance (int b) { int newBalance; if (b > 0) { System.out.println ("Depositing."); newBalance = balance + b; } else { System.out.println ("Withdrawing."); newBalance = balance + b; } System.out.println ("Current balance: " + balance); balance = newBalance; System.out.println ("New Balance " + balance); } public int getBalance() { return balance; } }

And then a bank access thread:

public class BankAccessThread extends Thread { Bank myBank; boolean deposit; int rep; public BankAccessThread (Bank b, boolean d, int r) { myBank = b; deposit = d; rep = r; } public void run() { for (int i = 0; i < rep; i++) { if (deposit) { myBank.adjustBalance (100); } else { myBank.adjustBalance (-100); } } } }

And then finally, something that ties them all together into an application:

public class ProblemThreads { public static void main (String args[]) { BankAccessThread myThreads[]; int startBal = 200; Bank myBank = new Bank (startBal); int num = 20; boolean deposit; myThreads = new BankAccessThread[num]; for (int i = 0; i < num; i++) { if (i % 2 == 0) { deposit = true; } else { deposit = false; } myThreads[i] =new BankAccessThread (myBank, deposit, 10); myThreads[i].start(); } } }

We start the balance of the bank off at 200, and then run this application. At each transaction, the bank prints out what its new balance is... so after the last transaction we know what the end balance of the bank will be, which is 200. And yet, what actually gets displayed is:

New Balance -800

Yikes! That's not even a little bit right! Obviously the problem of threads being swapped into and out of execution during variable access isn't something that occurs very rarely - it's something that will happen quite often in any given multi-threaded application. Even if we set the application up so that there are only two threads executed, we still end up with:

New Balance -400

That's no good at all!

The output of the adjustBalance method is also revealing. The output should follow this structure:

Depositing/Withdrawing
Current Balance X
New Balance Y
Depositing/Withdrawing
Current Balance X
New Balance Y

But when we run our application and select a random chunk of the output, we can see that the output isn't following this pattern at all:

Depositing.
Current balance: 400
New Balance 500
New Balance -200

Something is wrong in the city of Gotham, little friend. We need to find out what. To the Javamobile!

This particular problem is an example of a concept called the race condition, which occurs when:

1. Multiple processes access the same common data source
2. The outcome of any execution is based on the order in which the threads are executed.

Code that has race condition methods is very likely to malfunction... so it is lucky that Java provides us with a means of solving the problem through a new keyword - synchronized.

The problem is that method calls are not treated as being atomic, which means that a thread can be interrupted in the middle of doing something that has to be done as a holistic whole. The synchronized keyword allows us to tell Java that a particular method is to be treated as a single, atomic unit and that no more than one thread should be accessing it at any one time.

When a thread enters a synchronized method, it puts a lock on it. When any other thread attempts to enter the method, it is rejected and put into a state called blocked. So consider our synchronized adjustBalance method:

synchronized public void adjustBalance (int b) { int newBalance; if (b > 0) { System.out.println ("Depositing."); newBalance = balance + b; } else { System.out.println ("Withdrawing."); newBalance = balance + b; } System.out.println ("Current balance: " + balance); balance = newBalance; System.out.println ("New Balance " + balance); }

If we then compile our program again and execute it, we get the following output at the end:

Depositing.
Current balance: 100
New Balance 200

And this is exactly what we want. Even the text output is in atomic chunks just like we'd expect it to be. Our race condition problem has been solved!

In the process, we've introduced the possibility of a new kind of error - that of deadlock. This occurs when one thread has a lock on a method, and is waiting on another thread to release its lock on another method. This is fine, provided that the second thread isn't also waiting on the first thread to release its lock... if it is, neither can proceed because they are blocking each other.

Consider for example if our adjustBalance method has a check to ensure that the balance of the bank cannot go below 0. If our Thread has a lock on this method, it will never allow another thread to enter and adjust the balance to a positive value. It can never proceed with its own execution, and no other thread can gain access to alter the state of the bank so that it is in a suitable condition for the first thread to proceed.

To solve this, we use the wait method of a thread to cause it to temporarily release its lock on a method and enter a state of readiness until it is reawakened. This means that other threads will then have the chance of altering the state of the data and allowing the first thread to continue.

The wait method throws a mandatory acknowledgement exception in the form of an InterruptedException:

When a thread enters the wait state, it will remain waiting until another thread awakens it. Threads can be awakened through the use of a method called notifyAll, which nudges all of the sleeping threads and gets them to attempt access again.

while (newBalance < 0) { System.out.println ("Waiting."); try { wait(); } catch (InterruptedException ex) { } } notifyAll();

All of this is a very brief and shallow introduction to a subject of enormous depth and complexity. Most of this stuff you will not need to deal with until developing very complex programs such as multi-user games or servers or such.

We needed to discuss multithreading to provide a way to solve our 'unresponsive program' problem that we saw at the very start of the chapter. Simply spawning off a new thread to deal with complex functionality is a very useful technique that allows for us to build genuinely responsive and useful programs. The rest of the chapter is outlining the context in which this can be done, and indicating some of the problems should you think 'ah-ha, I can also use this for <insert complex functionality here>'!

Multithreading has a number of benefits, although not all of them relate to us as developers at this time. All we need to take away from this chapter is that we can ensure costly executions are handled in their own thread, which leaves our main code free to deal with responding to user input.

It also means that complex tasks can be handled concurrently, albeit at a slower pace. Depending on what the tasks are, this may be somewhat more efficient than dealing with each task sequentially. For example, with user input the biggest bottleneck in terms of efficiency is the user. The computer sits there idle for 95% of its time waiting for those slow meaty fingers to type another key. If there is only one process, then what is being wasted is 95% of the CPU cycles that were assigned. If we use multi-threading, other threads can be making use of the time that the event thread is hanging idle for processing other tasks.

However, there are problems, mainly related to the scheduling of threads. We have no way of ensuring that threads are executed in a particular order, which makes debugging much, much harder. We can't write test cases in the same way, because an error may occur only when two threads interact in a particular context... and if those two threads only interact in that way 1% of the time, reproducing the problem is a difficult task, which is to say nothing of fixing it.

All of your code has to be thread-safe, meaning that methods must be synchronized, which comes at a considerable cost in efficiency. It adds an additional complexity to development in that there has to be thread management code for ensuring threads don't continue to consume resources beyond their useful life-span.

Oh, and it makes debugging much, much harder. I know I've already said that, but it's a point that bears repeating.

For some kinds of problem, there is an easier way of providing some of the benefits of multithreading without delving into the minefield of interacting threads. Java provides a Timer class that allows for time delayed code to be executed. We can use this to break up complex problems into chunks that get processed sequentially. In this way we ensure that the CPU isn't shackled to one extremely expensive operation for too long at a time.

This comes with its own problem - if the time it takes to execute the code that goes with the timer is longer than the interval between 'ticks', it leads to the program becoming backlogged which causes inconsistent behaviour.

There are two Timer classes. One exists as part of java.util, the other exists as part of the Swing architecture. We'll look at the latter, since the former is a little more complex to set up.

The class is called Timer (obviously), and it takes two parameters for its constructor. The first is the number of milliseconds between ticks (the interval), and an object to act as an ActionListener. The Timer causes the actionPerformed method of the ActionListener object to be triggered every <interval> number of milliseconds:

Timer myTimer = new Timer (1000, this);

The timer will only begin to tick when you call the start method on it. You can stop its execution with the stop method.

Let's look at our original counter example, and recast it so that we are using timers. We won't implement exactly the same functionality - we are going to tick away at a slow, sedate pace instead of the frantic cycling of numbers that we have observed above - now that we have the timer in our toolkit, we may as well use it sensibly:

import javax.swing.*; import java.awt.*; import java.awt.event.*; public class TimerExample extends JFrame implements ActionListener { private Timer myTimer; ... public TimerExample() { ... myTimer = new Timer (1000, this); } public void actionPerformed (ActionEvent e) { if (e.getSource() == go) { myTimer.start(); } else if (e.getSource() == stop) { myTimer.stop(); } else if (e.getSource() == myTimer) { counterVar += 1; counter.setText ("" + counterVar); } } }

There is always a trade-off in these kind of things - what you gain in simplicity, you lose in flexibility. For many applications, the Timer is a suitable way of ensuring that a single piece of code doesn't hog too much of the processing time, and also has the benefit that it allows for events to be triggered at regular intervals, allowing for things like game engines to be coded.

It can be very difficult to visualise in your head what is happening with threads, so let's set up a simple horse racing game that works via multi-threading (and timers). I have no artistic ability at all, so the horses will just be represented by coloured ovals. We'll use a similar distribution of responsibilities in this game as we did with the shape drawing case study - our horses will be responsible for drawing themselves, and we'll have a model that deals with setting up all the instances and drawing each o the horses.

The main difference here is that our horses will be threads, and our model will setup each of the threads when the race is started:

import java.awt.*; public class Horse extends Thread { private int x, y; int endPoint; private Color col; public Horse (int nx, int ny, int e, Color c) { x = nx; y = ny; endPoint = e; col = c; } public void moveHorse() { x = x + 1; try { sleep (5); } catch (InterruptedException e) { } } public void drawHorse (Graphics g) { g.setColor (col); g.fillOval (x, y, 10, 10); } public void run() { while (x < endPoint) { moveHorse(); } } }

We must sleep the thread after each move, otherwise the threads move too fast for the human eye to see. Our horses are set up by the model:

import java.util.*; import java.awt.*; public class HorseRace { ArrayList<Horse> horses; int endPoint; public HorseRace (int e) { horses = new ArrayList<Horse>(); endPoint = e; addHorse (Color.RED); addHorse (Color.BLUE); addHorse (Color.GREEN); addHorse (Color.CYAN); addHorse (Color.BLACK); } public void addHorse (Color col) { Horse tmp; int y = (horses.size() * 50) + 50; tmp = new Horse (30, y, endPoint, col); horses.add (tmp); } public void drawHorses (Graphics g) { Horse tmp; for (int i = 0; i < horses.size(); i++) { tmp = horses.get (i); tmp.drawHorse (g); } } public void startRace() { Horse tmp; for (int i = 0; i < horses.size(); i++) { tmp = (Horse) horses.get (i); tmp.start(); } } }

We'll handle all of the drawing in a separate JPanel. We have no user interface here, so all of the functionality, including setting up the model, can be placed in here.

We'll use a timer to deal with repainting the panel - the horses cannot communicate back to the panel when they have moved, so we'll just periodically update the display:

import javax.swing.*; import java.awt.*; import java.awt.event.*; public class DrawingPanel extends JPanel implements ActionListener { HorseRace theRace; Timer myTim; public DrawingPanel() { myTim = new Timer (100, this); myTim.start(); } public void paintComponent (Graphics g) { super.paintComponent (g); if (theRace != null) { theRace.drawHorses (g); } } public void actionPerformed (ActionEvent e) { if (theRace == null) { theRace = new HorseRace (this.getWidth() -100); theRace.startRace(); } repaint(); } }

It might look a bit strange that we setup our HorseRace object in the actionPerformed, but it simply won't work if we set it up in the constructor - when the constructor is called, our panel has no width and so the endPoint used as the constructor parameter is set at -100.

Lastly we need the application itself:

import javax.swing.*; import java.awt.*; import java.awt.event.*; public class DerbyDay extends JFrame { DrawingPanel draw; public DerbyDay() { draw = new DrawingPanel(); add (draw, BorderLayout.CENTER); } public static void main (String args[]) { DerbyDay mainWindow = new DerbyDay(); mainWindow.setSize (1500, 500); mainWindow.setVisible (true); } }

Now, we compile and execute this program to get a simple horse-racing game. It's not very interesting, because Java attempts to schedule all of the threads equally and so they all pass the finish line at the same time. If we watch carefully we can see some tiny perturbations where one horse is a little bit ahead of the others, but that soon fixes itself:

Fig 28.7: Derby Day Screenshot

We can make the race more interesting by changing the priorities of the threads when they are created:

public void startRace() { Horse tmp; for (int i = 0; i < horses.size(); i++) { tmp = (Horse) horses.get (i); tmp.setPriority ((int) (Math.random() * 10) + 1); tmp.start(); } }

Fig 28.8: Randomly Determined Priorities

In this way we can explore the effect different priority changes have on the running of Java threads. Give it a try - you may find it quite surprising.

Multithreading is one of the most complex aspects of Java, and as can be expected it is also one of the most powerful. It is not important at this point that you understand how to use it in all its glory for your own programs - as long as you can use the Timer class and spawn off an occasional thread to deal with very complex functionality, you are familiar with all of the multithreading you can reasonably be expected to deal with at this point.

The largest problem perhaps with multithreading is how difficult it is to envision what is genuinely going on inside a multithreaded application. We may know the underlying theory, but the complexities of the thread scheduling algorithms used by the Java Virtual Machine ensures that we will never have a truly representative view of what is happening internally.

Nonetheless, provided we are willing to sacrifice so much of our control to the black magic voodoo of the JVM, we can find multi-threading to be a valuable ally in our quest to rid the world of insoluble programming problems. Three cheers for multi-threading!

Further Reading

The following table details further reading on the topic in this chapter, and also any external resources that you may find useful.