Friday, February 25, 2011

Chapter 60: Synchronization

We have been using the term synchronizing multiple times over the course of the previous chapters. We have never cared to stop and explain what the term synchronizing or synchronization means. Well, here we are. This full chapter is dedicated to synchronization and how to synchronize our code.

So, lets get started!!!

Why do we need Synchronization?

Threads are a powerful concept that we explained in the previous few chapters. Just as in the case of any programming scenario, the code works on a set of data and processes it. Lets imagine a scenario:

Assume that I have borrowed Rs. 10000/- from you and another Rs. 10000/- from an anonymous Mr. X last month. Now, both of you are chasing me for the money and I give you cheques worth the money I owe you guys, each worth Rs. 10000/- so, now I have given cheques worth Rs. 20000/- for payment. Unfortunately for you both, my account has a balance of only Rs. 12000/- and fortunately for me the banking application of my bank does not care about synchronization. So here is what will happen in a hypothetical situation wherein both the cheques are going to be submitted for payment at the same time.

Bank A (Your bank) and Bank B (Mr. X’s bank) have both submitted the cheques for payment to my bank today morning at two different branches.

A teller is processing your cheque at branch 1 and another teller is processing Mr. X’s cheque at branch 2. Both the tellers are simultaneously initiating the cheque clearance activity. Here is how it works:

Step 1: Teller 1 initiates a transfer at 10:30 AM and Teller 2 initiates a transfer at 10:30 AM as well
Step 2: Teller 1’s system checks my bank balance at 10:31 AM and approves the payment because my account has Rs. 12,000 and Teller 2’s system does the same at the same time and approves the payment because the money in my account is more than the value of the cheque I have given.
Step 3: Since both systems feel that there is enough balance in my account, they successfully make the payment.

2 cheques, each worth Rs. 10000/- got paid even though I had only Rs. 12000/- in my bank. Though I am happy about it, clearly the bank is not.

Guess what went wrong here?

There is no synchronization between the two tellers. Practically speaking, two tellers in two different branches don't need to talk to one another before processing a cheque but the banks application should handle such a situation.

All this happened because, the system allowed data related to one persons account to be accessed by two different processes(threads) and also allowed the data to be modified by both those processes at the same time.

This problem is known as a “race condition,” where multiple threads can access the same Car (typically an object’s instance variables), and can produce corrupted data if one thread “races in” too quickly before an operation that should be “atomic” has completed.

Practically speaking, only one of the cheques should have been cleared (whichever teller clicked “Transfer Funds” button first in milliseconds) and the other guys cheque must have bounced. This is exactly what would have happened if the first thread took a lock on the data and processed it, while all other threads that want access to the same data are in line “waiting”. So, by the time the second teller clicked “Transfer funds” his process would have to wait until Teller 1’s transfer is complete and then, the check balance logic would have come back stating “Hey buddy, this bum does not have enough cash to pay this cheque. Bounce this bad boy, will you?”
Now, I guess you know why we need synchronization (Only if you own a bank) but still, we now appreciate the need for synchronization. Lets now look at the details of implementation of this concept.

Preventing the Overpayment of Cheques:

So what can be done? The solution is actually quite simple. We must ensure that the two steps of the transfer—checking the balance and making the transfer—are never split apart. We need them to always be performed as one operation, step 1 and step 2! We call this an “atomic operation” because the operation, regardless of the number of actual statements (or underlying byte code instructions), is completed before any other thread code that acts on the same data.
You can’t guarantee that a single thread will stay running throughout the entire atomic operation. But you can guarantee that even if the thread running the atomic operation moves in and out of the running state, no other running thread will be able to work on the same data. In other words, If Teller 1 falls asleep after checking the balance, we can stop Teller 2 from checking the balance until after Teller 1 wakes up and completes her transfer.

So how do you protect the data? You must do two things:
• Mark the variables private.
• Synchronize the code that modifies the variables.

Remember, you protect the variables in the normal way using an access control modifier. It’s the method code that you must protect, so that only one thread at a time can be executing that code. You do this with the synchronized keyword.

We can solve all of Teller 2 and Teller 1’s problems by adding one word to the code. We mark the makeTransfer() method synchronized as follows:
private synchronized void makeTransfer(int amt) {
if (acct.getBalance() >= amt) {
System.out.println(Thread.currentThread().getName() +
" is going to Transfer");
try {
Thread.sleep(500);
} catch(InterruptedException ex) { }
acct.Transfer(amt);
System.out.println(Thread.currentThread().getName() +
" completes the transfer");
} else {
System.out.println("Not enough in account for "
+ Thread.currentThread().getName()
+ " to Transfer " + acct.getBalance());
}
}

Now we’ve guaranteed that once a thread (Teller 1 or Teller 2) starts the transfer process (by invoking makeTransfer()), the other thread cannot enter that method until the first one completes the process by exiting the method. The new output shows the benefit of synchronizing the makeTransfer() method:

Teller 2 is going to Transfer
Teller 2 completes the transfer
Teller 1 is going to Transfer
Teller 1 completes the transfer
Teller 2 is going to Transfer
Teller 2 completes the transfer
Teller 1 is going to Transfer
Teller 1 completes the transfer
Teller 2 is going to Transfer
Teller 2 completes the transfer
Not enough in account for Teller 1 to Transfer 0
Not enough in account for Teller 2 to Transfer 0
Not enough in account for Teller 1 to Transfer 0
Not enough in account for Teller 2 to Transfer 0
Not enough in account for Teller 1 to Transfer 0

Notice that now both threads, Teller 1 and Teller 2, always check the account balance and complete the transfer before the other thread can check the balance.

Synchronization and Locks

How does synchronization work? The Answer is simple “With locks”. Every object in Java has a built-in lock that only comes into play when the object has synchronized method code. When we enter a synchronized non-static method, we automatically acquire the lock associated with the current instance of the class whose code we’re executing. Acquiring a lock for an object is also known as getting the lock, or locking the object, locking on the object, or synchronizing on the object. We may also use the term monitor to refer to the object whose lock we’re acquiring. Technically the lock and the monitor are two different things, but here we refer to the same thing by those two words.

Since there is only one lock per object, if one thread has picked up the lock, no other thread can pick up the lock until the first thread releases or returns the lock. This means no other thread can enter the synchronized code until the lock has been released. Typically, releasing a lock means the thread holding the lock, in other words, the thread currently in the synchronized method exits the synchronized method. At that point, the lock is free until some other thread enters a synchronized method on that object. Remember the following key points about locking and synchronization:

• Only methods (or blocks) can be synchronized, not variables or classes.
• Each object has just one lock.
• Not all methods in a class need to be synchronized. A class can have both synchronized and non-synchronized methods.
• If two threads are about to execute a synchronized method in a class, and both threads are using the same instance of the class to invoke the method, only one thread at a time will be able to execute the method. The other thread will have to wait until the first one finishes its work. In other words, once a thread acquires the lock on an object, no other thread can enter any of the synchronized methods in that class for that object.
• If a class has both synchronized and non-synchronized methods, multiple threads can still access the class’s non-synchronized methods! If you have methods that don’t access the data you’re trying to protect, then you don’t need to synchronize them. Synchronization can cause a hit in some cases, so you should be careful not to overuse it.
• If a thread goes to sleep, it holds any locks it has—it doesn’t release them.
• A thread can acquire more than one lock. For example, a thread can enter a synchronized method, thus acquiring a lock, and then immediately invoke a synchronized method on a different object, thus acquiring that lock as well. As the methods complete, locks are released again. Also, if a thread acquires a lock and then attempts to call a synchronized method on that same object, no problem. The JVM knows that this thread already has the lock for this object, so the thread is free to call other synchronized methods on the same object, using the lock the thread already has.
• You can synchronize a block of code rather than a method.
Because synchronization does hurt concurrency, you don’t want to synchronize any more code than is necessary to protect your data. So if the scope of a method is more than needed, you can reduce the scope of the synchronized part to something less than a full method to just a block.

We call this, strangely, a synchronized block, and it looks like this:
class TestSyncdBlocks {
public void doSomething() {
System.out.println("not synchronized");
synchronized(this) {
System.out.println("synchronized");
}
}
}

When a thread is executing code from within a synchronized block, including any method code invoked from that synchronized block, the code is said to be executing in a synchronized context.

When you synchronize a method, the object used to invoke the method is the object whose lock must be acquired. But when you synchronize a block of code, you specify which object’s lock you want to use as the lock, so you could, for example, use some third-party object as the lock for this piece of code. That gives you the ability to have more than one lock for code synchronization within a single object.

Or you can synchronize on the current instance (this) as in the code above. Since that’s the same instance that synchronized methods lock on, it means that you could always replace a synchronized method with a non-synchronized method containing a synchronized block. In other words, this:

public synchronized void doSomething() {
System.out.println("synchronized");
}
is equivalent to this:
public void doSomething() {
synchronized(this) {
System.out.println("synchronized");
}
}

These methods both have the exact same effect, in practical terms. The compiled bytecodes may not be exactly the same for the two methods. The first form is shorter and more familiar to most people, but the second can be more flexible.

Static Methods and Synchronization

static methods can be synchronized. There is only one copy of the static data you’re trying to protect, so you only need one lock per class to synchronize static methods, a lock for the whole class. There is such a lock; every class loaded in Java has a corresponding instance of java.lang.Class representing that class. It’s that java.lang.Class instance whose lock is used to protect the static methods of the class (if they’re synchronized). There’s nothing special you have to do to synchronize a static method:

public static synchronized int getSomething() {
return count;
}

Again, this could be replaced with code that uses a synchronized block. If the method is defined in a class called MyClass, the equivalent code is as follows:
public static int getSomething() {
synchronized(MyClass.class) {
return count;
}
}

What’s that MyClass.class that we have used for the sync’d block? That’s called a class literal. It’s a special feature in the Java language that tells the compiler: get me the instance of Class that represents the class called MyClass. You can also do this with the following code:
public static void someMethod() {
Class cl = Class.forName("MyClass");
synchronized (cl) {
// do stuff
}
}

However that’s longer, trickier, and most importantly, not on the SCJP exam. But it’s quick and easy to use a class literal—just write the name of the class, and add .class at the end. No quotation marks needed. Now you’ve got an expression for the Class object you need to synchronize on.

What If a thread cannot get the Lock?

If a thread tries to enter a synchronized method and the lock is already taken, the thread is said to be blocked on the object’s lock. Essentially, the thread goes into a kind of pool for that particular object and has to wait there until the lock is released and the thread can again become runnable/running. Just because a lock is released doesn’t mean any particular thread will get it. There might be several threads waiting for a single lock, for example, and there’s no guarantee that the thread that has waited the longest will get the lock first.
When thinking about blocking, it’s important to pay attention to which objects are being used for locking.

• Threads calling non-static synchronized methods in the same class will only block each other if they’re invoked using the same instance. That’s because they each lock on this instance, and if they’re called using two different instances, they get two locks, which do not interfere with each other.
• Threads calling static synchronized methods in the same class will always block each other—they all lock on the same Class instance.
• A static synchronized method and a non-static synchronized method will not block each other, ever. The static method locks on a Class instance while the non-static method locks on the object instance, these actions do not interfere with each other at all.
• For synchronized blocks, you have to look at exactly what object has been used for locking. Threads that synchronize on the same object will block each other. Threads that synchronize on different objects will not.
A Synopsis of Thread related methods & Lock Availability:
Methods that give up the lock:
a. wait()

Methods that hold the lock:
a. notify()
b. join()
c. sleep()
d. yield()

When to Synchronize?

Synchronization can get pretty complicated, and you may be wondering why you would want to do this at all if you can help it. But remember the earlier “race conditions” example with Teller 1 and Teller 2 making transfers from their account. When we use threads, we usually need to use some synchronization somewhere to make sure our methods don’t interrupt each other at the wrong time and mess up our data. Generally, any time more than one thread is accessing changeable data, you synchronize to protect that data, to make sure two threads aren’t changing it at the same time. You don’t need to worry about local variables—each thread gets its own copy of a local variable. Two threads executing the same method at the same time will use different copies of the local variables, and they won’t trouble each other. However, you do need to worry about static and non-static fields, if they contain data that can be changed.

For changeable data in a non-static field, you usually use a non-static method to access it. By synchronizing that method, you will ensure that any threads trying to run that method using the same instance will be prevented from simultaneous access. But a thread working with a different instance will not be affected, because it’s acquiring a lock on the other instance. That’s what we want, threads working with the same data need to go one at a time, but threads working with different data can just ignore each other and run whenever they want to.

For changeable data in a static field, you usually use a static method to access it. And again, by synchronizing the method you ensure that any two threads trying to access the data will be prevented from simultaneous access, because both threads will have to acquire locks on the Class object for the class the static method’s defined in. Once again, that’s exactly what we want.
However, what if you have a non-static method that accesses a static field? Or a static method that accesses a non-static field (using an instance)? In these cases things start to get tricky quickly, and there’s a very good chance that things will not work the way you want. If you’ve got a static method accessing a non-static field, and you synchronize the method, you acquire a lock on the Class object. But what if there’s another method that also accesses the non-static field, this time using a non-static method? It probably synchronizes on the current instance instead. Remember that a static synchronized method and a non-static synchronized method will not block each other and they can run at the same time. Similarly, if you access a static field using a non-static method, two threads might invoke that method using two different this instances. Which means they won’t block each other, because they use different locks. Which means two threads are simultaneously accessing the same static field, which is exactly the sort of thing we’re trying to prevent.

It gets very confusing trying to imagine all the weird things that can happen here. To keep things simple: in order to make a class thread-safe, methods that access changeable fields need to be synchronized.

Access to static fields should be done from static synchronized methods. Access to non-static fields should be done from non- static synchronized methods. For example:

public class ConfuseMe {
private static int staticField;
private int nonstaticField;
public static synchronized int getStaticField() {
return staticField;
}
public static synchronized void setStaticField(int staticField) {
ConfuseMe.staticField = staticField;
}
public synchronized int getNonstaticField() {
return nonstaticField;
}
public synchronized void setNonstaticField(int nonstaticField) {
this.nonstaticField = nonstaticField;
}
}

What if you need to access both static and non-static fields in a method? Well, there are ways to do that, but it’s beyond what you need for the exam. So, for now, your are off the hook and don't need to bother much about this complicated thing that's going to make our lives harder than it already is…

Thread Safe Classes

When a class has been carefully synchronized to protect its data, we say the class is “thread-safe.” Many classes in the Java APIs already use synchronization internally in order to make the class “thread-safe.” For example, StringBuffer and StringBuilder are nearly identical classes, except that all the methods in StringBuffer are synchronized when necessary, while those in StringBuilder are not. Generally, this makes StringBuffer safe to use in a multithreaded environment, while StringBuilder is not. However, even when a class is “thread-safe,” it is often dangerous to rely on these classes to provide the thread protection you need. You still need to think carefully about how you use these classes, As an example, consider the following class.

import java.util.*;
public class ThreadSafeClass {
private List names = Collections.synchronizedList(new LinkedList());
public void addName(String name) {
names.addName(name);
}
public String removeName() {
if (names.size() > 0)
return (String) names.remove(0);
else
return null;
}
}

The method Collections.synchronizedList() returns a List whose methods are all synchronized and “thread-safe” according to the java API documentation. The question is, can the ThreadSafeClass class be used safely from multiple threads? It’s tempting to think that yes, since the data in names is in a synchronized collection, the ThreadSafeClass class is “safe” too. However that’s not the case—the removeName() may sometimes throw a NoSuchElementException. What’s the problem? Doesn’t it correctly check the size() of names before removing anything, to make sure there’s something there? How could this code fail? Let’s try to use ThreadSafeClass like this:

public static void main(String[] args) {
final ThreadSafeClass nl = new ThreadSafeClass();
nl.addName("Rocky");
class NameDropper extends Thread {
public void run() {
String name = nl.removeName();
System.out.println(name);
}
}
Thread t1 = new NameDropper();
Thread t2 = new NameDropper();
t1.start();
t2.start();
}

What might happen here is that one of the threads will remove the one name and print it, then the other will try to remove a name and get null. If we think just about the calls to names.size() and names.get(0), they occur in this order:

Thread t1 executes names.size(), which returns 1.
Thread t1 executes names.remove(0), which returns Rocky.
Thread t2 executes names.size(), which returns 0.
Thread t2 does not call remove(0).
The output here is
Rocky
null

However, if we run the program again something different might happen:

Thread t1 executes names.size(), which returns 1.
Thread t2 executes names.size(), which returns 1.
Thread t1 executes names.remove(0), which returns Rocky.
Thread t2 executes names.remove(0), which throws an exception because the list is now empty.

The thing to realize here is that in a “thread-safe” class like the one returned by synchronizedList(), each individual method is synchronized. So names.size() is synchronized, and names.remove(0) is synchronized. But nothing prevents another thread from doing something else to the list in between those two calls. And that’s when unexpected things can happen.
There’s a solution here: don’t rely on Collections.synchronizedList(). Instead, synchronize the code yourself:

import java.util.*;
public class ThreadSafeClass {
private List names = new LinkedList();
public synchronized void addName(String name) {
names.addName(name);
}
public synchronized String removeName() {
if (names.size() > 0)
return (String) names.remove(0);
else
return null;
}
}

Now the entire removeName() method is synchronized, and once one thread starts it and calls names.size(), there’s no way the other thread can cut in and steal the last name. The other thread will just have to wait until the first thread completes the removeName() method.
The moral of the story is (Like in the Value Education class in School) that just because a class is described as “thread-safe” doesn’t mean it is always thread-safe. If individual methods are synchronized, that may not be enough, you may be better off putting in synchronization logic yourself. Once you do that, the original synchronization may well become redundant.

I know that we never paid attention to the Value Education class in school, but my friend, here the moral is very important and you need to pay attention in order to pass the exam. So, do me a favor, go back to the paragraph above and read it once before you move ahead to the next topic…


Deadlocks

Perhaps the scariest thing that can happen to a Java program is deadlock. Deadlock occurs when two threads are blocked, with each waiting for the one another’s lock. Neither can run until the other gives up its lock, so they’ll sit there forever.

This can happen, for example, when thread A hits synchronized code, acquires a lock B, and then enters another method that’s also synchronized. But thread A can’t get the lock to enter this synchronized code block C because another thread D has the lock already. So thread A goes off to the “waiting for the C lock” pool, hoping that thread D will finish up its work and release the lock. But thread A will wait forever, because while thread D picked up lock C, it then entered a method synchronized on lock B. Obviously, thread D can’t get the lock B because thread A has it. And thread A won’t release it until thread D releases lock C. But thread D won’t release lock C until after it can get lock B and continue. And there they are – Stubbornly waiting for the other person to give up the lock. The following example demonstrates deadlock:

1. public class DeadlockExample {
2. private static class Car {
3. public int value;
4. }
5. private Car CarA = new Car();
6. private Car CarB = new Car();
7. public int read() {
8. synchronized(CarA) { // 1
9. synchronized(CarB) {
10. return CarB.value + CarA.value;
11. }
12. }
13. }
14.
15. public void write(int a, int b) {
16. synchronized(CarB) { // 2
17. synchronized(CarA) {
18. CarA.value = a;
19. CarB.value = b;
20. }
21. }
22. }
23. }

The lines marked with //1 and //2 are the places where we might end up with a deadlock.
Assume that read() is started by one thread and write() is started by another. If there are two different threads that may read and write independently, there is a risk of deadlock at line 8 or 16. The reader thread will have CarA, the writer thread will have CarB, and both will get stuck waiting for the other.

Code like this almost never results in deadlock because the CPU has to switch from the reader thread to the writer thread at a particular point in the code, and the chances of deadlock occurring are very small. The application may work fine most of the time.

The preceding simple example is easy to fix; just swap the order of locking for either the reader or the writer at lines 16 and 17 (or lines 8 and 9). More complex deadlock situations can take a long time to figure out and even longer to solve.

Regardless of how little chance there is for your code to deadlock, the bottom line is, if you get a deadlock, you’re dead. There are design approaches that can help avoid deadlock, including strategies for always acquiring locks in a particular order.

But that’s something you don't need for the exam.

Exam Tip:
Deadlocks are almost like stubborn fighting couples. Both parties are upset with each other and are silent and not willing to talk to one another. Unless one party speaks up and apologizes the other is going to stay silent. Fortunately we humans have emotions and most often one party apologizes and then the couples are happily married again. Unfortunately threads arent human and don't have any emotions. If one waits for the other to speak up, it waits and waits and waits. So, a smart programmer will take all possible steps to ensure that doesn't happen in his code, which I am sure you will!!!


Previous Chapter: Chapter 59 - Thread Prioritoes, yield and join methods

Next Chapter: Chapter 61 - Thread Interactions

1 comment:

  1. Thanks for commenting on my post How to convert arraylist to array in java Anand. I see you have written whole book here and I can see detailed information about synchronization here. keep it up .

    Javin
    How to use synchronized block and method in java

    ReplyDelete

© 2013 by www.inheritingjava.blogspot.com. All rights reserved. No part of this blog or its contents may be reproduced or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the Author.

ShareThis

Google+ Followers

Followers