Concurrent Programming CS 598 Class Notes

Lecture Notes for Concurrent Programming

1 July 2003 - Java Synchronization

Java Synchronization

Class Instance Synchronization
Mutual Exclusion
Conditional Synchronization

Class Instance Synchronization

Every class instance has a binary semaphore acting as a mutex.
The class-instance mutex is hidden from direct access.
- The mutex is accessed indirectly via synchronized code blocks.
A synchronized code block locks on entry and unlocks on exit.
- A block-structured approach to synchronization.
- The code in the block becomes a critical region.
- Any code-block exit, including exceptions, unlocks the mutex.
- This is similar to the constructor-destructor idiom.
Class methods can be synchronized, as can arbitrary code blocks.

Synchronized Blocks

Any code block can be protected in a synchronized block.
synchronized (class-instance) { code-block }

There need be no relation between class-instance and code-block.

class blob {
  private int cnt;
  void addOne(Object o) {
    synchronized (o) { cnt++; }
    }

This is legal, but dumb, code.

Synchronized Class Methods

A synchronized method can be implemented with a synchronized block.
```
void f() {
  synchronized (this) {
    // f's body
    }
  }
```
A synchronized method locks on entry and unlocks on exit.
- Any exit will do: return, exception.
- By default, methods are unsynchronized.
The keyword synchronized indicates a synchronized method.
- Synchronization is not inherited.
- Synchronization can't be specified in an interface.
A class may have both synchronized and unsynchronized methods.
- Be careful when you do this.

Mutex Behavior

Mutex unblocking is arbitrary.
- Thread priority is ignored.
- Thread starvation is possible.
Mutex locking is re-entrant (or recursive).
- A thread can relock any mutex it holds.
```
class counter

  private int counter = 0

  public synchronized int 
  increase()
    System.out.println(value())
    count++

  public synchronized void 
  value() 
    return count
```
- Lock-unlock pairs are nested; inner unlocks don't effect outer locks.
- increase() still holds the lock after the value() call.

Mutual Exclusion

Implementing mutual exclusion with synchronized code is hard.
- Controlling access to shared state is hard.
- Synchronizing all access code is easy to get wrong.
Non-private class fields are unprotectable.
- Protected and package-private access is as bad as public access.
- Any thread can access the field at any time.
Subclasses can circumvent mutual exclusion in the parent.
- Synchronization is not inherited.
- The need for mutual exclusion is, usually in non-obvious ways.
- Not to mention the other classes in the package.
Because class instances are non-atomic, just readers need mutually exclusive acess too.

Conditional Synchronization

Binary semaphores hold waiters until a predicate is (or could be) true.

Implementing binary semaphores in Java.

synchronized void
get() {
  // wait until count is positive.
  count--
  }

How to implement get()?
- Spin waiting? while (count < 1) { }?
The waiting thread needs to leave the method, but not its place in the method.
- Leaving the method releases the lock.
- Keeping its place means it can return where it left off.
Threads need a back porch they can hang out, waiting to return.

The Wait Set

The back porch is called the wait set.
- As with the mutex, a class instance has one wait set.
- Wait-set waiters are separate from the mutex waiters.
A single wait set per class instance will cause some pain.
- Providing you own wait sets will cause some pain too.

Waiting and Notifying

The Object methods wait(), notify(), and notifyAll() manipulate the wait set.
wait() moves the calling thread to the wait set.
- The calling thread releases the mutex.
notify() moves a thread, if any, from the wait set to the mutex.
- The notified thread re-acquires the mutex before continuing.
- The notify is not remembered; if missed, it's gone.
notifyAll() moves all threads from the wait set to the mutex.
- Each must relock the mutex to continue.

Wait Set Gotchas

wait(), notify(), and notifyAll() must be called from within a synchronized block.

void bad() 
  while (!condition) wait()  // what wait set?

synchronized void good()
  while (!condition) wait()

There's only one wait set per class instance.

class TroubleAlert 

  synchronized void whenYellow 
    while (alert != yellow) wait()

  synchronized void whenOrange
    while (alert != Orange) wait()

  void setYellow
    alert = yellow
    notify()

Which waiter wakes up?
Solving this is tricky (unless you use notifyAll(), which is expensive).

Using Wait Sets

notify() unblocks an arbitrary thread in the wait set.
- No fairness, no priority, no nuttin'.
Wait-set blocked threads may spontaneously unblock.
- Allowed by the JVM spec and useful for some hardware.
Contention among notifyAll() threads is high.
- They all requeue at the class-instance mutex.
There is only one wait set per class instance.
- All conditions look the same to the wait set.
- notify() may unblock the wrong thread; tends to deadlock.
- notifyAll() is more important than it should be.
- This is coarse-grained locking.

Conditional Synchronization and Interference

An unblocked thread may not immediately regain the mutex.
- Beware the thief in the night.
- Passing the baton doesn't help here.
  - The stone and bowl are out of reach.
The signaled condition may no longer be true when it does.
Upon regaining the instance, the waiter must recheck the condition.
Bad:
- Another thread can beat the waiter to the mutex.
Good:
- Once the waiter is in, mutual exclusion keeps buffer_full true.

Conditional Synchronization Example

A One slot buffer.

class buffer
  private boolean buffer_full = false
  private Object buffer

  public synchronized void
  put(Object o)

    while (buffer_full) wait()

    buffer = 0
    buffer_full = true

    notify()

  public synchronized Object
  get()

    while (!buffer_full) wait()

    Object o = buffer
    buffer_full = false

    notify()
    return o

See the complete code.

Points to Remember

Each class instance has its own mutex.
- Only one lock for the whole class instance.
Mutexes are accessed indirectly through synchronized code.
- Either blocks or methods.
Mutex behavior needs to be worked around.
- Optional use, weak semantics.
wait(), notify(), and notifyAll() provide conditional synchronization.

This page last modified on 1 July 2003.