Core Java. Lecture #10

Concurrent execution

Where can we benefit from concurrency?

Where can we NOT benefit from [increasing] concurrency?

Amdahl’s law

Amdahl’s Law

In fact, it’s even worse!

\[\Large N = 4, E = 6\]	\[\Large N = 5, E = 10\]	\[\Large N = 6, E = 15\]	\[\Large N = 7, E = 21\]

In fact, it’s even worse!

USL plot

Intermediate conclusions

Part 1. Why do you need synchronization and how is it achieved

Multithreading in Java (from the very first version!)

class CalcSquare extends Thread {
    final int argument;
    int result;
    CalcSquare(int argument) {
        this.argument = argument;
    }
    @Override
    public void run() {
        //"complex" calculations
        result = argument * argument;
    }
}

Run parallel computing via Thread API

CalcSquare t1 = new CalcSquare(2);
CalcSquare t2 = new CalcSquare(3);
t1.start();
t2.start();
t1.join();
t2.join();
System.out.printf("%d, %d%n", t1.result, t2.result);
//otput: 4, 9

Problems with shared state

Race condition Stale values Reordering

Race condition

class DumbCounter {
  int count;
  void increment(){
    count++;
  }
}

DumbCounter c1 = new DumbCounter();
IntStream.range(0, 1000000).forEach(i->c1.increment());

DumbCounter c2 = new DumbCounter();
IntStream.range(0, 1000000).parallel().forEach(i->c2.increment());

System.out.printf("%d, %d%n", c1.count, c2.count);

//1000000,??????

Stale values

class DumbWayToFallAsleep implements Runnable {
  private boolean asleep;

  public void setAsleep(boolean asleep){
    this.asleep = asleep;
  }

  @Override
  public void run() {
    while (!asleep){
      //countSomeSheep
      //WILL WE FALL ASLEEP?
    }
  }
}

Reordering

class PossibleReordering {
  static int x = 0, y = 0, a = 0, b = 0;
  public static void main(String... args)
                throws InterruptedException {
    //another method of starting a thread (you won't use it as well)
    Thread one = new Thread(() -> {
        a = 1; x = b;
    });
    Thread two = new Thread(() -> {
        b = 1; y = a;
    });
    one.start(); two.start();
    one.join();  two.join();
    System.out.printf("%d,%d", x, y);
    //??,??
  }
}

Thread one, Thread two

Thread one = new Thread(() -> {
    a = 1; x = b;
});
Thread two = new Thread(() -> {
    b = 1; y = a;
});

         x  y  a  b

a = 1;   0  0  1  0
x = b;   0  0  1  0
b = 1;   0  0  1  1
y = a;   0  1  0  0

Thread two, Thread one

Thread one = new Thread(() -> {
    a = 1; x = b;
});
Thread two = new Thread(() -> {
    b = 1; y = a;
});

         x  y  a  b

b = 1;   0  0  0  1
y = a;   0  0  0  1
a = 1;   0  0  1  1
x = b;   1  0  1  1

Threads interleaved

Thread one = new Thread(() -> {
    a = 1; x = b;
});
Thread two = new Thread(() -> {
    b = 1; y = a;
});

         x  y  a  b

a = 1;   0  0  1  0
b = 1;   0  0  1  1
x = b;   1  0  1  1
y = a;   1  1  1  1
or
y = a;   0  1  1  1
x = b;   1  1  1  1

Intermediate conclusions

Memory model

int aVariable = 42;

Happens-before

Program order rule

Thread start & thread termination rule

volatile keyword

Fix stale value using volatile

class NotSoDumbWayToFallAsleep implements Runnable {
  private volatile boolean asleep;

  public void setAsleep(boolean asleep){
    this.asleep = asleep;
  }

  @Override
  public void run() {
    while (!asleep){
      //countSomeSheep
      //...
    }
  }
}

final fields

Non-atomic operations: final is not good, volatile will not save us

class DumbCounter {
  int count;
  void increment(){
    count++;
  }
}

void dumbMoneyTransfer(
  int from, int to, int amount){

    accounts[from]-=amount;
    accounts[to]+=amount;
}

Unsynchronized execution

Synchronized execution

Locks

//Reentrant is so called because
//the same thread is allowed to enter again
private ReentrantLock bankLock = new ReentrantLock();

void moneyTransfer(int from, int to, int amount) {
  bankLock.lock();
  try {
    accounts[from]-=amount;
    accounts[to]+=amount;
  } finally {
    bankLock.unlock();
  }
}

JMM Monitor Lock Rule

What’s the problem here?

while (accounts[from] < amount) {
    //wait ....
}

bankLock.lock();
try {
  transfer funds ...
} finally {
  bankLock.unlock();
}

What’s the problem here?

bankLock.lock();
try {
  while (accounts[from] < amount) {
    wait ....
  }
  transfer funds ...
} finally {
  bankLock.unlock();
}

Condition Objects

private ReentrantLock bankLock = new ReentrantLock();
private Condition sufficientFunds = bankLock.newCondition();

void moneyTransfer(int from, int to, int amount) {
  bankLock.lock();
  try {
    while (accounts[from] < amount)
      sufficientFunds.await();

    accounts[from]-=amount;
    accounts[to]+=amount;

    sufficientFunds.signalAll();
  } finally {
    bankLock.unlock();
  }
}

Condition Objects: What happens?

Question

Correct condition waiting pattern

while (!okToProceed())
  condition.await();

Intrinsic lock

Same with intrinsic lock

//enter intrinsic lock on *this*
synchronized void moneyTransfer(int from, int to, int amount) {
    while (accounts[from] < amount)
      wait(); //wait on intrinsic object's lock condition

    accounts[from]-=amount;
    accounts[to]+=amount;

    notifyAll(); //notify all threads waiting on the condition
}

synchronized block

private Object lock = new Object();
void moneyTransfer(int from, int to, int amount) {
  synchronized (lock) {
    while (accounts[from] < amount)
      lock.wait();

    accounts[from]-=amount;
    accounts[to]+=amount;

    lock.notifyAll();
  }
}

Intermediate conclusions for intrinsic conditions

Now we understand the meaning of all the possible thread states

Intermediate conclusions for all of the above

Part 2. Deadlocks

Deadlock: A Simple Example

Wrong order of blocking

class LeftRightDeadlock {
  private final Object left = new Object();
  private final Object right = new Object();
  void leftRight() {
    synchronized (left) {
      synchronized (right) {
        doSomething();
      }
    }
  }
  void rightLeft() {
    synchronized (right) {
      synchronized (left) {
        doSomethingElse();
      }
    }
  }
}

(Sometimes?) wrong order of blocking

void transferMoney(Account fromAccount, Account toAccount,
                     int amount) throws InsufficientFundsException {
  synchronized (fromAccount) {
    synchronized (toAccount) {
      if (fromAccount.getBalance() < amount)
        throw new InsufficientFundsException();
      else {
        fromAccount.debit(amount);
        toAccount.credit(amount);
      }
    }
  }
}

Conclusions

Part 3. Thread-safe data structures

Non-blocking algorithms

Atomics

Atomic operations in atomic variable classes

getAndSet(newValue)    compareAndSet(expect, update)

incrementAndGet()      decrementAndGet()

getAndIncrement()      getAndDecrement()

getAndAdd(delta)       addAndGet(delta)

getAndUpdate(updateFunction)
updateAndGet(updateFunction)

getAndAccumulate(x, accumulatorBiFunction)
accumulateAndGet(x, accumulatorBiFunction)

Thread-safe collections