![]() |
A7. Threads
In this section, you will learn:
IntroductionThe ability of a program to concurrently execute multiple regions of code provides capabilities that are difficult or impossible to achieve with strictly sequential languages. Sequential object-oriented languages send messages (make method calls) and then block or wait for the operation to complete. Programmers are already familiar with concurrent processes, possibly without recognizing them. For example, operating systems usually have many processes running to handle printing, updating the display, receiving mail from the network, and so on. In contrast, most programming languages do not promote the use of concurrent operation within one application. At best, programmers have access to a few library calls to launch and control multiple operations. Java provides language-level and library support for threads--independent sequences of execution within the same program that share the same code and data address space. Each thread has its own stack to make method calls and store local variables. Most applications that use threads are a form of simulation or have a graphical user interface, but threads in general have the following advantages over sequential programming:
Spawning a ThreadTo spawn a Java thread, follow these steps: 1. Create your class, making it implement Runnable. class Animation implements Runnable { ... } 2. Define a method within your class with this signature: public void run() { // when this exits, thread dies } This method will be called when the thread starts up. Elsewhere, you may: 3. Create an instance of your class. Animation a = new Animation(); 4. Create a new thread attached to your new instance. Thread t = new Thread(a); 5. Start the thread attached to your object. t.start(); As a simple example, consider the following runnable class that continuously prints a string to standard out. class Jabber implements Runnable { String str; public Jabber(String s) { str = s; } public void run() { while ( true ) { System.out.println(str); } } } Class Jabber can be used in the following way: class JabberTest { public static void main(String[] args) { Jabber j = new Jabber("MageLang"); Jabber k = new Jabber("Institute"); Thread t = new Thread(j); Thread u = new Thread(k); t.start(); u.start(); } }
Magercise
Controlling Thread ExecutionThread execution may be controlled after creation with methods of Thread such as:
To illustrate the stop() method and to provide a useful mechanism, consider the following WatchDog class that launches a thread, but kills it if the thread lives too long (deadlocked perhaps?). class WatchDog implements Runnable { public WatchDog(Runnable r, int ms) { Thread t = new Thread(r); t.start(); try {Thread.sleep(ms);} catch (InterruptedException e) {} t.stop(); } } The following main program shows how to use the watchdog: public class KillThread { public static void main(String[] args) { Analysis a = new Analysis(); WatchDog w = new WatchDog(a, 1000); } } Here is the simple runnable class that will be killed. class Analysis implements Runnable { public void run() { while ( true ) { System.out.println("analyze..."); } } } Without the watchdog, a thread would run forever running on this object. Thread SafetyThreads are an extremely useful programming tool, but can render programs difficult to follow or even nonfunctional. Consider that threads share the same data address space and, hence, can interfere with each other by interrupting critical sections (so-called "atomic operations" that must execute to completion). For example, consider that a write operation to a database must not be interrupted by a read operation because the read operation would find the database in an incorrect state. Or, perhaps more graphically, consider the analogy of two trains that need to share the same resource (run on the same stretch of track). Without synchronization, a disaster would surely occur the next time both trains arrived at nearly the same time. The state of a running program is essentially the value of all data at a given instant. The history of a program's execution then is the sequence of states entered by a program. For single-threaded application there is exactly one history, but multi-threaded applications have many possible histories-- some of which may contain a number of incorrect states due to interference of threads. The prevention of interference is called mutual exclusion and results primarily from synchronization, which constrains all possible histories to only those containing exclusively good states. Condition synchronization refers to threads waiting for a condition to become true before continuing; in other words, waiting for the state to become valid or correct before proceeding. In Java language terms, synchronized methods or code blocks have exclusive access to the member variables of an object resulting in atomic code blocks. A safe program is one that has been synchronized to prevent interference, but at the same time avoids deadlock, the discussion of which we defer to a future section. In this section, we dive into more detail concerning synchronization and condition synchronization, but begin with a short background discussion of the thread synchronization model used by Java. MonitorsIn the mid-1960's, E. Dijkstra invented the notion of a semaphore for implementing mutual exclusion and signaling events and defined P and V operations to specify critical sections. Unfortunately, semaphores are very low-level elements and programs written with them are hard to read as both condition synchronization and mutual exclusion are specified with the same mechanism. In the early 1970's, Tony Hoare defined monitors, which provided a structured approach to exclusion and condition synchronization. Monitors were eventually included in Concurrent Pascal, Modula, and Mesa (at Xerox PARC) [And91]. A number of the PARC researchers that worked on the Cedar/Mesa project now work at JavaSoft. Naturally, the Java thread synchronization mechanism, which is monitor-based, evolved from Cedar/Mesa. A monitor is chunk of data that can only be accessed through a set of routines. This type of encapsulation is expressed as an object in today's terminology, although monitors were designed like modules rather than instances of a class. A monitor's access routines are guaranteed to execute in a mutually exclusive manner. Java relaxes this constraint slightly to allow a class' methods to be explicitly specified as synchronized, which always execute to completion. Monitors use condition variables plus wait and signal statements to provide condition synchronization. An accessor routine waits on a condition variable until awakened by another thread executing a signal statement on that variable. Java has a simpler, more efficient, condition synchronization scheme. A thread executes a wait() in a method of some object and blocks until awakened. A call to notifyAll() awakens all threads waiting on a signal for that object--there is no way to specify that only certain threads are to be awakened (a call to notify() wakes up a single waiting thread). One can say that a monitor access routine acquires a lock on that monitor, which it releases upon returning from that method. In this way, mutual exclusion is implicitly achieved. Only synchronized Java methods acquire a lock on an object. A call to wait() releases the lock, but will reacquire it as it is awakened by a notifyAll(). notifyAll() does not yield execution nor release its hold on an object's lock. The only way to release a lock is by waiting or returning from a synchronized method. As a final detail, we note that some operations are considered atomic and, hence, do not require synchronization of any kind. In Java, only assignments to primitives except long and double are considered atomic. Mutual ExclusionMutual exclusion is the simple idea that certain code blocks cannot be interrupted once begun; i.e., they execute to completion. Java allows instance methods, class methods, and blocks of code to be synchronized. All may be considered to be synchronized using the lock of some object. For example, consider the following two synchronized instance methods. class DataBase { public synchronized void write(Object o, String key) {...} public synchronized void read(String key){...} public void getVersion() {...} } Java ensures that once a thread enters either method, another thread may not interrupt it to execute the other method. Notice that method getVersion() is not synchronized and, therefore, may be called by any thread even if another thread has the lock on the same object. Synchronized methods may call other synchronized methods (even those of other objects) and may call non-synchronized methods.
Magercise
Non-method code blocks may be synchronized via an object also. For example, let's rewrite the DataBase class to be nonsynchronized: class DataBase { ... public void write(Object o, String key) {...} public void read(String key){...} public void getVersion() {...} } Code may still access a database in a safe manner by locking the call site rather than the method definition. Assume the following definition: DataBase db = new DataBase(); If one thread executes: synchronized (db) { db.write(new Employee(), "Jim"); } another thread may execute the following safely: synchronized (db) { db.read("Jim"); } Once a write operation has been started, a read cannot proceed and once a read has been started, a write may not proceed. Class methods may also be synchronized even though they do not operate on an object, however, each object has a reference to its class definition object (of type Class). Class methods gain the lock of their class definition object for mutual exclusion. Thinking of class method locks in this manner allows us to generalize, saying that all methods and all code blocks synchronize on a per-object basis. As an example, consider how you might restrict access to a system resource such as a printer, by using per-class synchronization. You might define the following class: class HPLaser { private static Device dev = ...; static synchronized print(String s) {...} } Then, if a thread is executing this: HPLaser.print("Help! I'm trapped in this PC!"); another thread may not execute this: HPLaser.print("We're not in Kansas anymore");
Magercise
Condition SynchronizationCondition synchronization delays the execution of a thread until a condition is satisfied whereas mutual exclusion delays the execution of a thread until it can acquire a lock. Normally, this condition signifies the completion of another task or that the object state is now valid again and it is safe to proceed. Conditional delays would be easy to specify, but inefficient to implement as: await(condition) statement; Java chooses a simpler mechanism where the programmer must loop according to the condition around a wait: while ( !condition ) do wait(); We use a while-loop instead of an if-statement because there is no way to restrict a notifyAll() to a particular condition. This thread may wake up even though a different condition has changed. Also, after waking, a thread still may find the condition unsatisfied because another thread had awakened ahead of it. To awaken a waiting thread, have another thread call notifyAll(). For example, consider the simple problem of reading information from a blocking queue where you want read operations to block waiting for information. class BlockingQueue { int n = 0; ... public synchronized Object read() { // wait until there is something to read while (n==0) wait(); // we have the lock and state we're seeking n--; ... } public synchronized void write(Object o) { ... n++; // tell threads to wake up--one more object notifyAll(); } } Notice that only one read can occur simultaneously because read() is synchronized. Because the read operation is destructive (removes an element), it is proper that only one simultaneous read occurs. Returning to the database read/write problem from above, we note that reads do not have side effects and there is no theoretical reason to restrict access to a single simultaneous read. The "readers and writers" problem is well known and is solved by having an object control access to the database so that the read/write methods do not have to be synchronized.
Magercises
Thread LivenessThe notion that your program will not lock up and eventually do something useful is called the liveness property. In sequential programming, this property is equivalent to termination. In a multi-threaded environment, this property implies that your program will stop responding or processing before a desired result is achieved. There are a number of reasons why a multi-threaded program will fail liveness:
Thread safety often conflicts with the goal of liveness. To produce thread-safe code, programmers are tempted to simply put synchronized on every publicly-visible method. Unfortunately, a well thought out thread-safety scheme could induce deadlock.
Magercise
DeadlockDeadlock can occur even for simple problems. For example, consider a class that computes prime numbers in a given range--a multi-processor computer could then run a thread on each object to compute primes in parallel. Each object knows of the other prime computation peer objects, hence, any object can return a composite list of primes from the peers. For simplicity, assume there are only two such prime number computation objects and that both have references to each other in order to report the primes: class ComputePrime { private int[] primes; private int lower, upper; private ComputePrime peer; public ComputePrime(int low, int high) { lower = low; upper = high; primes = new int[high-low+1]; } public void setPeer(ComputePrime p) { peer = p; // who am I associated with? } public synchronized int[] getPrimes() { return primes; } public synchronized String getAllPrimes() { int[] peerPrimes = peer.getPrimes(); // return merge of peerPrimes with primes } } To see the potential for deadlock, assume that we have the following two peer clients: ComputePrime c1 = new ComputePrime(2,100); ComputePrime c2 = new ComputePrime(101,200); c1.setPeer(c2); c2.setPeer(c1); If one thread executes c1.getAllPrimes(), but is interrupted by another thread that executes c2.getAllPrimes(), deadlock will occur. The following sequence highlights the problem:
Ensuring Safety and LivenessThe following techniques can be used to promote safety and liveness (in order of increasing probability of success):
For the average programmer, the common approach will be to use case analysis to guide algorithm design and using known patterns where possible, thus, trying to build in thread safety and liveness. Testing can then be used to (hopefully) catch unforeseen problems and to gain confidence that you have correctly implemented a task. The class library supplied by Sun is thread safe. Unfortunately, this does not guarantee that the code you write using the library is thread safe as deadlock is easy to achieve if you are not careful. In this section, we provide a few tips for building in thread safety. Restricted UniversesOne of the most common techniques for providing thread safety while promoting efficiency and without endangering liveness is to create restricted universes within which you know exactly which threads are executing. Consider a recursive-descent parser for the Java language. The parser object will have a series of mutually-recursive methods, one for every rule in the grammar; e.g., class JavaParser { public synchronized void compilationUnit() {} public synchronized void expression() {} public synchronized void statement() {} public synchronized void method() {} public synchronized void declaration() {} ... } The methods are all synchronized because you can begin parsing at any one of the rule-methods--having multiple threads walking the same parser object would cause serious interference with input pointers and so on. While synchronizing all the methods provides safety, it unnecessarily slows down the overall parser because synchronized methods are slower than unsynchronized methods. The solution is to restrict the universe in which the parser object can exist, allowing the parser object to assume that at most one thread can ever run on it. A containment object (sometimes called a facade, sentinel, or broker) can provide a synchronized interface to the parser, which would then not need to be synchronized. If you needed to access the main starting symbol compilationUnit() and also rule-method expression(), the following containment object would provide thread safe access without slowing down the parser. class JavaParserSentinel { JavaParser parser; public JavaParserSentinel(JavaParser p) { parser = p; } public synchronized void compilationUnit() { parser.compilationUnit(); } public synchronized void expression() { parser.expression() { } }
Magercise
"Red Flags" And HintsThere are a number of common situations in which thread safety or liveness are in jeopardy. Here are a few:
Recall that from our Java parser example, one can be sure that objects contained within and solely accessed by thread safe code do not need to be synchronized. As a final suggestion, remember that if the member variables written to by one thread are not read by another thread and vice-versa, no interference can occur. Further, local variables cannot be accessed from a different thread and, hence, are by definition disjoint.
Magercises
Further Reading and ReferencesStudents will find Concurrent Programming in Java useful. (Written by Doug Lea published in the Java Series from Addison-Wesley, Menlo Park, CA, 1996). Some of the fundamental concepts summarized here are explored in great detail in the following textbook: [And91] Concurrent Programming: Principles and Practice by Gregory Andrews, Addison-Wesley, Menlo Park, CA, 1991. |
Copyright © 1996-1997 MageLang Institute. All Rights Reserved. |