Earlier, we defined thread safety for a data type or a function as behaving correctly when used from multiple threads, regardless of how those threads are executed, without additional coordination.
Here’s the general principle: the correctness of a concurrent program should not depend on accidents of timing.
We talked about strategies 1-3 earlier. In this reading, we’ll finish talking about strategy 4, using synchronization to implement your own data type that is safe for shared-memory concurrency.
The correctness of a concurrent program should not depend on accidents of timing.
Since race conditions caused by concurrent manipulation of shared mutable data are disastrous bugs — hard to discover, hard to reproduce, hard to debug — we need a way for concurrent modules that share memory to synchronize with each other.
Locks are one synchronization technique. A lock is an abstraction that allows at most one thread to own it at a time. Holding a lock is how one thread tells other threads: “I’m changing this thing, don’t touch it right now.”
Locks have two operations:
Using a lock also tells the compiler and processor that you’re using shared memory concurrently, so that registers and caches will be flushed out to shared storage. This avoids the problem of reordering, ensuring that the owner of a lock is always looking at up-to-date data.
Our first example of shared memory concurrency was a bank with cash machines. The diagram from that example is on the right.
The bank has several cash machines, all of which can read and write the same account objects in memory.
Of course, without any coordination between concurrent reads and writes to the account balances, things went horribly wrong.
To solve this problem with locks, we can add a lock that protects each bank account. Now, before they can access or update an account balance, cash machines must first acquire the lock on that account.
In the diagram to the right, both A and B are trying to access account 1. Suppose B acquires the lock first. Then A must wait to read and write the balance until B finishes and releases the lock. This ensures that A and B are synchronized, but another cash machine C is able to run independently on a different account (because that account is protected by a different lock).
When used properly and carefully, locks can prevent race conditions. But then another problem rears its ugly head. Because the use of locks requires threads to wait ( acquire blocks when another thread is holding the lock), it’s possible to get into a a situation where two threads are waiting for each other — and hence neither can make progress.
In the figure to the right, suppose A and B are making simultaneous transfers between two accounts in our bank.
A transfer between accounts needs to lock both accounts, so that money can’t disappear from the system. A and B each acquire the lock on their respective “from” account: A acquires the lock on account 1, and B acquires the lock on account 2. Now, each must acquire the lock on their “to” account: so A is waiting for B to release the account 2 lock, and B is waiting for A to release the account 1 lock. Stalemate! A and B are frozen in a “deadly embrace,” and accounts are locked up.
Deadlock occurs when concurrent modules are stuck waiting for each other to do something. A deadlock may involve more than two modules: the signal feature of deadlock is a cycle of dependencies, e.g. A is waiting for B which is waiting for C which is waiting for A. None of them can make progress.
You can also have deadlock without using any locks. For example, a message-passing system can experience deadlock when message buffers fill up. If a client fills up the server’s buffer with requests, and then blocks waiting to add another request, the server may then fill up the client’s buffer with results and then block itself. So the client is waiting for the server, and the server waiting for the client, and neither can make progress until the other one does. Again, deadlock ensues.
In the Java Tutorials, read:
Let’s see how to use synchronization to implement a threadsafe ADT.
You can see all the code for this example on GitHub: edit buffer example. You are not expected to read and understand all the code. All the relevant parts are excerpted below.
Suppose we’re building a multi-user editor, like Google Docs, that allows multiple people to connect to it and edit it at the same time. We’ll need a mutable datatype to represent the text in the document. Here’s the interface; basically it represents a string with insert and delete operations:
/** An EditBuffer represents a threadsafe mutable string of characters * in a text editor. */ public interface EditBuffer < /** * Modifies this by inserting a string. * @param pos position to insert at (requires 0 @param ins string to insert */ public void insert(int pos, String ins); /** * Modifies this by deleting a substring * @param pos starting position of substring to delete * (requires 0 @param len length of substring to delete * (requires 0 public void delete(int pos, int len); /** * @return length of text sequence in this edit buffer */ public int length(); /** * @return content of this edit buffer */ public String toString(); >A very simple rep for this datatype would just be a string:
public class SimpleBuffer implements EditBuffer < private String text; // Rep invariant: // text != null // Abstraction function: // represents the sequence text[0]. text[text.length()-1]The downside of this rep is that every time we do an insert or delete, we have to copy the entire string into a new string. That gets expensive. Another rep we could use would be a character array, with space at the end. That’s fine if the user is just typing new text at the end of the document (we don’t have to copy anything), but if the user is typing at the beginning of the document, then we’re copying the entire document with every keystroke.
A more interesting rep, which is used by many text editors in practice, is called a gap buffer. It’s basically a character array with extra space in it, but instead of having all the extra space at the end, the extra space is a gap that can appear anywhere in the buffer. Whenever an insert or delete operation needs to be done, the datatype first moves the gap to the location of the operation, and then does the insert or delete. If the gap is already there, then nothing needs to be copied — an insert just consumes part of the gap, and a delete just enlarges the gap! Gap buffers are particularly well-suited to representing a string that is being edited by a user with a cursor, since inserts and deletes tend to be focused around the cursor, so the gap rarely moves.
/** GapBuffer is a non-threadsafe EditBuffer that is optimized for * editing with a cursor, which tends to make a sequence of inserts * and deletes at the same place in the buffer. */ public class GapBuffer implements EditBuffer < private char[] a; private int gapStart; private int gapLength; // Rep invariant: // a != null // 0 // 0 // Abstraction function: // represents the sequence a[0]. a[gapStart-1], // a[gapStart+gapLength]. a[length-1]In a multiuser scenario, we’d want multiple gaps, one for each user’s cursor, but we’ll use a single gap for now.
Recall our recipe for designing and implementing an ADT:
In all these steps, we’re working entirely single-threaded at first. Multithreaded clients should be in the back of our minds at all times while we’re writing specs and choosing reps (we’ll see later that careful choice of operations may be necessary to avoid race conditions in the clients of your datatype). But get it working, and thoroughly tested, in a sequential, single-threaded environment first.
Now we’re ready for the next step:
This part of the reading is about how to do step 4. We already saw how to make a thread safety argument, but this time, we’ll rely on synchronization in that argument.
And then the extra step we hinted at above:
Locks are so commonly-used that Java provides them as a built-in language feature.
In Java, every object has a lock implicitly associated with it — a String , an array, an ArrayList , and every class you create, all of their object instances have a lock. Even a humble Object has a lock, so bare Object s are often used for explicit locking:
Object lock = new Object();You can’t call acquire and release on Java’s intrinsic locks, however. Instead you use the synchronized statement to acquire the lock for the duration of a statement block:
synchronized (lock) < // thread blocks here until lock is free // now this thread has the lock balance = balance + 1; // exiting the block releases the lock >Synchronized regions like this provide mutual exclusion: only one thread at a time can be in a synchronized region guarded by a given object’s lock. In other words, you are back in sequential programming world, with only one thread running at a time, at least with respect to other synchronized regions that refer to the same object.
Locks are used to guard a shared data variable, like the account balance shown here. If all accesses to a data variable are guarded (surrounded by a synchronized block) by the same lock object, then those accesses will be guaranteed to be atomic — uninterrupted by other threads.
Because every object in Java has a lock implicitly associated with it, you might think that simply owning an object’s lock would prevent other threads from accessing that object. That is not the case. Acquiring the lock associated with object obj using
synchronized (obj)
in thread t does one thing and one thing only: prevents other threads from entering a synchronized(obj) block, until thread t finishes its synchronized block. That’s it.
Locks only provide mutual exclusion with other threads that acquire the same lock. All accesses to a data variable must be guarded by the same lock. You might guard an entire collection of variables behind a single lock, but all modules must agree on which lock they will all acquire and release.
When you are writing methods of a class, the most convenient lock is the object instance itself, i.e. this . As a simple approach, we can guard the entire rep of a class by wrapping all accesses to the rep inside synchronized (this) .
/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */ public class SimpleBuffer implements EditBuffer < private String text; . public SimpleBuffer() < synchronized (this) text = ""; checkRep(); > > public void insert(int pos, String ins) < synchronized (this) text = text.substring(0, pos) + ins + text.substring(pos); checkRep(); > > public void delete(int pos, int len) < synchronized (this) text = text.substring(0, pos) + text.substring(pos+len); checkRep(); > > public int length() < synchronized (this) return text.length(); > > public String toString() < synchronized (this) return text; > > >
Note the very careful discipline here. Every method that touches the rep must be guarded with the lock — even apparently small and trivial ones like length() and toString() . This is because reads must be guarded as well as writes — if reads are left unguarded, then they may be able to see the rep in a partially-modified state.
This approach is called the monitor pattern. A monitor is a class whose methods are mutually exclusive, so that only one thread can be inside an instance of the class at a time.
Java provides some syntactic sugar for the monitor pattern. If you add the keyword synchronized to a method signature, then Java will act as if you wrote synchronized (this) around the method body. So the code below is an equivalent way to implement the synchronized SimpleBuffer :
/** SimpleBuffer is a threadsafe EditBuffer with a simple rep. */ public class SimpleBuffer implements EditBuffer < private String text; . public SimpleBuffer() < text = ""; checkRep(); > public synchronized void insert(int pos, String ins) < text = text.substring(0, pos) + ins + text.substring(pos); checkRep(); > public synchronized void delete(int pos, int len) < text = text.substring(0, pos) + text.substring(pos+len); checkRep(); > public synchronized int length() < return text.length(); > public synchronized String toString() < return text; > >
Notice that the SimpleBuffer constructor doesn’t have a synchronized keyword. Java actually forbids it, syntactically, because an object under construction is expected to be confined to a single thread until it has returned from its constructor. So synchronizing constructors should be unnecessary.
In the Java Tutorials, read:
