Concurrency

Run tasks in parallel
- Time slicing
- Multiple processors
Moore's law is coming to an end—single processors cannot be improved at the historical rate
Multicore is here to stay
Programming languages are poorly equipped for concurrency
Case study: Java

Java Thread Basics

Construct thread from Runnable: run method runs in new thread

Runnable r = new MyRunnable();
Thread t = new Thread(r);
t.start();

Threads can call Thread.sleep(millis) if they have nothing to do

Throws InterruptedException. Catch it in the outermost level of run:

public class MyRunnable implements Runnable {
   public void run() {
      try {
         while (...) {
            do work            
            Thread.sleep(...);
         }      
      } catch (InterruptedException e) {}
      clean up 
   }
}

Race Condition

Threads can access shared variables
Race condition: outcome depends on thread scheduling
Example: Multiple threads deposit, withdraw money from bank account
BankAccount.java DepositRunnable.java BankAccountThreadRunner.java WithdrawRunnable.java
Bank balance should always be zero at program end, but sometimes it isn't

Race Condition Scenario

Locks

public class BankAccount {
   . . .
   private Lock balanceChangeLock = new ReentrantLock();
}

Only one thread can acquire lock at the same time

public void deposit(double amount) {
   balanceChangeLock.lock();
   try {
      access shared resources
   } finally {
      balanceChangeLock.unlock();
   }
}

Conditions

Cannot evaluate shared state without acquiring lock

What if evaluation shows that thread needs to wait?

balanceChangeLock.lock();
try {
   while (balance < amount) // cannot withdraw
      // wait
 . . .

Can't wait while holding lock—nobody can deposit
Solution: wait on conditon
Requires cooperation from other thread to signal

Conditions 2

Condition is associated with lock

public class BankAccount {
   . . .
   private Condition sufficientFundsCondition = balanceChangeLock.newCondition();
}

Call await when thread can't proceed

while (balance < amount) 
   sufficientFundsCondition.await();

Blocks thread until it is signaled, releasing lock

Depositing thread must call signalAll

balance += amount;
sufficientFundsCondition.signalAll();

Waiting threads are unblocked, contend for lock
Signal is no guarantee for success
- Deposit might not have been sufficient
For efficiency, can have different condition objects

Monitor

Per Brinch Hansen and Tony Hoare, 1970s
Class with only private fields
Each object has an associated lock
All methods are locked by that lock
Consequence: Only one thread at a time has access to private fields
Lock can have any number of conditions

Programming language gives some syntactic sugar, e.g.

public monitor BankAccount {
   double balance; // automatically private
   public void deposit() { ... } // automatically acquires lock

Intrinsic Locks

Since Java 1.0
Every object (!) has one intrinsic lock and one intrinsic condition

Use synchronized to acquire/release the intrinsic lock

public synchronized void deposit(double amount) {
   balance += amount;
   notifyAll();
}

wait and notifyAll methods in Object (!) operate on intrinsic condition

public synchronized void withdraw(double amount) throws InterruptedException {
   while (balance < amount) wait();
   balance -= amount;
}

Synchronized block:
```
synchronized (anObj) { . . . }
```

Java Intrinsic Lock ≠ Monitor

Fields are not required to be private.
Methods are not required to be synchronized.
The intrinsic lock is available to clients.
Per Brinch Hansen: “It is astounding to me that Java’s insecure parallelism is taken seriously by the programming community, a quarter of a century after the invention of monitors and Concurrent Pascal. It has no merit.” [Java’s Insecure Parallelism, ACM SIGPLAN Notices 34:38–45, April 1999.]