Locks

Locks allow restricting access to different areas of the code. A part of the code that we want only one thread to have access at a given time is called a critical section. This critical section can represent access to some resource (like a printer; we don't want another process to start printing in the middle), execution of a particular function or part within the program (like an ATM transaction, there should be no interference while it occurs), or a method of a distributed data type (avoid erasing while inserting an element to a list).

Let's see the following code (without locks)

public class Printer implements Runnable {

private String document;

public Printer(String document){
this.document = document;
}

@Override
public void run() {
Random r = new Random();
//represents some preprocessing of the document
try {
Thread.sleep(1000*(r.nextInt(2)+1));
} catch (InterruptedException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
for (int i=0; i < document.length(); i++){
System.out.println("printing \"" + document.charAt(i) + "\"");
try {
Thread.sleep(1000*(r.nextInt(2)+1));
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}

public static void main(String[] args) {
Thread t1 = new Thread(new Printer("hello"));
Thread t2 = new Thread(new Printer("world"));
t1.start();
t2.start();
}

}

The main method starts two thread printing "hello" and "world" respectively. The run method of the Printer class (invoked when the threads are started), prints each letter and has some delay (imagine the physical time to actually print the letter. Then, when running this program the printing of both documents gets winded and the output letters do not form "hello" "world", but some mix of their letters.

One way to deal with this is by using locks within the for loop so that from the moment the printer starts it cannot get interrupted: (changes to the run method)

@Override

public void run() {

Random r = new Random();

//represents some preprocessing of the document

try {

Thread.sleep(1000*(r.nextInt(2)+1));

} catch (InterruptedException e1) {

// TODO Auto-generated catch block

e1.printStackTrace();

}

while (true){

boolean success = lock.tryLock();

if (success) break;

try {

Thread.sleep(1000*(r.nextInt(2)+1));

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

for (int i=0; i < document.length(); i++){

System.out.println("printing \"" + document.charAt(i) + "\"");

try {

Thread.sleep(1000*(r.nextInt(2)+1));

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

lock.unlock();

}

Now, only one thread can access the for loop at a time. 

Question to think: what would have happened had we forgotten the unlock after the loop?

PS: The goal of this post was to give a first explanation of locks (without entering into language details) Java allows using synchronized for avoiding multiple threads from entering the same method. For a discussion on the difference between locks and synchronize, there's a nice explanation here: locks vs synchronized

Synchronization primitives - CAS

CAS (compare and swap) is a synchronization primitive to deal with race conditions as presented in Race conditions . This primitive checks whether a variable has the value previously read and in case it does, CAS changes the contents of that variable - all of this is applied atomically, i.e. no other thread can interrupt this set of actions. This is usually useful when reading a value, and we want to write the value changed, to see that the value has not changed since we have read it.

For example given the code:

P(){
   do {
1.   tmp = read(x)
2.   tmp = tmp+1
3. } while (! CAS (x, tmp, tmp+1));
}

This is very similar to the code in the previous post, but now we capture the case when someone has written some different value and prevents some undesirable schedules.

For instance, let's consider the following schedule:
A.1
B.1
B.2
B.3
A.2
A.3

In the previous post A.3 wrote in x without noticing if someone else had changed x's value in the meanwhile. Now, with the CAS statement, once B has written a new value, the CAS statement fails forcing A to read the updated value before writing it incremented by one. (which is what we would expect!)

Race conditions

A race condition in parallel programs occurs when different schedules / interleavings may cause different results.
The most typical example is the following: let two threads A and B execute (each) the program P given by

P(){
1. tmp = read(x)
2. tmp = tmp+1
3. write(x,tmp) //write in x the value of tmp
}

This code is consistent with several formal representations of parallel programs where at each statement a shared variable is accessed only once. In particular, here we consider x to be the shared variable and each thread creates a temporal local variable tmp to increment it and then write it at the original location.

Now, if  the initial value of x is 0, and the schedule is A, B (i.e. first A executes all the lines, and then B), by the end x will contain the value 2 (one increment by A, another one by B)

However, in parallel programs, one of the threads may be preempted (interrupted) the other continues running, then returns.. so there are other possible execution orders for this code.
One of them is:
A.1 (A executes the first line)
B.1
B.2
B.3
A.2
A.3

what happens here when the initial value of  x is 0?
with A.1, tmp_A (tmp local to A) gets the value 0
with B.1, tmp_B also gets the value 0 (it has not been changed yet)
B.2, B.3 increments and writes the new value setting x with 1 (but tmp_A has not changed)
A.2 increments tmp_A (it was 0, now is 1)
A.3 writes this value in x

This causes the value of x by the end of this schedule to be 1.

Thus, this code (as is) is an example of a race condition. Usually synchronization primitives are used to avoid such problems, but I'll write more about these primitives later..