The synchronized block is an example of a synchronization primitive. A construct that allows different threads to exchange information. Importantly, multiple synchronized blocks can compose. This composition is achieved by nesting different synchronized blocks. Let's see how this works. Assume that we have a class account that represents bank accounts. Each account is initialized with a certain amount of money. This amount is stored in a private variable. The account class has a method transfer which is used to transfer some amount n to a target account. Note that many invocations of transfer could occur in parallel. To implement the transfer method, you do not want to have a single global object for the synchronized statement. This would be a bottleneck for parallelism in the system, especially if many transfers occur in parallel. Instead, we will use more fine grained synchronization. We will start a synchronized block both on the source account and the target account. This will make sure that the code in the nested block is executed atomically, both for the threads using the source account, this, and threads using the target account. For example, a thread running the transfer method first obtains a monitor on the account A1 and then obtains a monitor on the account A2. Once it has monitors of both objects, it can transfer the amount n from A1 to A2. In parallel, another thread can do the same thing with accounts A3 and A4. Let's see this in a demo. In this demo, we will paste the entire snippet of the code and then explain it. We first define the account class as shown in the slides. Then, we declare a method startThread, which given two accounts a and b and an amount n, starts a new thread which transfers the amount n by calling transfer with the argument 1 n times. The thread is then started and returned. We then instantiate two accounts, a1 and a2. We then start two threads, t and s, and wait for their completion. The thread t transfers an amount of 150,000 from the account a1 to the account a2, and the thread s does the opposite. It transfers from account a2 to a1. Unfortunately, this program never completes. The program is blocked and waiting on the first join. This is because the threads t and s never actually complete, so the join blocks the main thread. Why did this happen? In the previous demo we saw an example of a deadlock. Deadlock is a scenario in which two or more threads compete for resources. And each of the threads waits for the others to finish without releasing the already acquired resources. Here the resource might be monitor ownership, which is required for the synchronized statement. In our example, after having created two accounts, two separate threads invoke the transfer method, but in reverse order. In the first case the source account is the account a, and in the second case the source account is the account b. The two threads start the synchronize statement on these accounts in different order. The first thread enters the synchronized block on the a, and the second thread enters the synchronized block on b. At this point, the first thread blocks until the monitor on object b becomes available and vice versa. Neither thread makes progress and a deadlock occurs. So how can we fight deadlocks? One way to do this is to ensure that resources, in our case, monitor ownerships, are acquired in the same order. Doing so eliminates the possibility that two threads get mutually blocked on each other's resources. This approach assumes that we can order different resources in some way. How can we do that in the case of account objects? A simple way to achieve ordering is to assign unique IDs to different accounts. We're in luck. The getUniqueUid method that we defined earlier is just what we need for the job. We use it to compute a unique ID for every account object. We then define a private lock and transfer method that always does the transfer by calling synchronized on the this object first, and then on the target. The public transfer method takes care of the ordering. It checks which of the two accounts has a smaller UID and does the locking in that order. If target has a larger UID it reverses the arguments and passes a negative amount, n. You can now modify the bank account class yourself to convince yourself that this solution works. The last topic that we will briefly visit in this lecture is the memory model. A memory model is a set of rules that describes how threads interact when accessing shared memory. It answers questions such as, if some thread writes some value to a memory location, what are the preconditions that the other threads see the value that was written? Specifically, the Java memory model is the memory model for the JVM run time. As such, it affects both Scala and Java. The Java Memory Model has multiple precisely defined rules. We will not cover all of these rules in this course, as we will only rely on a small subset of them in our examples. The two rules that we will remember for the purposes of this course are the following. Two threads writing to separate locations in memory do not need synchronization. For example, if thread T1 writes to this memory location, and thread T2 writes to this one, they don't need to synchronize their writes in order to write the values correctly. There's no need for a synchronized statement in this case. The second rule is, a thread X that calls join on another thread Y is guaranteed to observe all the writes by thread Y after join returns. So for example, if thread Y writes to this memory location, and thread X calls join onto thread Y, then when join returns, thread X will see all the rights by thread Y. Without calling join, there is no guarantee that the thread X will actually see this write by the time it does the read. In summary, the parallelism constructs in the remainder of the course are implemented in terms of two major constructs. Threads, which introduce the parallelism into the application, and synchronization primitives such as synchronized, which allow parallel computations to exchange information. As a final remark, know that we will not be using threads and the synchronized primitive directly in the remainder of the course. However, it is important to understand how things work under the hood. Often, you will find yourself debugging a parallel program or investigating an implementation of a higher level framework. In these cases, you will find the knowledge about threads and synchronization useful.
