Concurrent Programming CS 598 Class Notes

Lecture Notes for Concurrent Programming

17 July 2003 - Locking Structures

Locking Structures

Tracking State
- Bounded Queues
State Variables
Conflict Sets
Subclassing
- Readers and Writers
- Layering Guards
Inheritance Anomalies
Nested Locking

Bounded Queues

Consider the bounded buffer

class BoundedQueue

  private final Object q[]
  private int size

  synchronized Object get()
    while (size == 0) wait()
    // take o from queue.
    notifyAll();
    return o

  synchronized void put(Object o)
    while (size == q.length) wait()
    // put o on queue.
    notifyAll();

Why notifyALL()?
Why call notifyALL() every time?

Tracking State

Threads modify queue state, changing the conditions.
- Putters may change not empty; getters may change not full.
Other threads block until conditions are true.
- Putters wait for not full; getters wait for not empty.
Which threads should re-evaluate the conditions?
- The waiting thread must always re-evaluate the condition.
- How about the modifying thread?

State Variables

Call notifyAll() only when waiting threads are possible.

class BoundedQueue private BQ bq synchronized Object get() while q.empty() wait() if q.get(o) notifyAll() return o synchronized void put(Object o) while q.full() wait() if q.put(o) notifyAll()

class BQ private Object q[] private int size boolean empty() return size == 0 boolean full() return size == q.len boolean put(o) // put o in q return size == 1 boolean get(o) // take o from q. return size == q.len - 1

Encapsulate and separate concerns.
- Concurrency and queue manipulations.

Conflict Sets

Partition object state into cohesive subsets.
- Each method accesses all variables in one subset.
Each partition can now be accessed concurrently.
Problems arise when partitions overlap.
- The corresponding methods can't execute concurrently.
- This is not fatal, but it reduces concurrency.

Implementing Conflict Sets

Each partition needs its own mutex.
Each partition may need its own wait set.
- Needing wait sets may indicate a partitioning problem.
- Condition variables make good wait sets.

Bounder Buffer Conflict Sets

Can you use conflict sets to improve bounded buffer concurrency?
Two queues avoids conflicts between putters and getters.
- But not among putters, nor among getters.
The putters and getters eventually have to meet.
- Getting the swap right requires a bit of care.

Conflict Set Variants and Extensions

Optimistic variants abort a conflicting method if a conflict occurs.
- This allows for overlapping or finer grained partitions.
- Detecting conflicts and aborting methods can be a pain though.
The method access behavior can get quite complicated, even with partitioning.
- Exactly ten bees followed by one bear.
Be careful to avoid leaning unnecessarily on internal object state.
- Doing so makes the design and implementation brittle.
- Extending a bounded buffer with priority, for example.
Look to generalized conflict patterns.
- The swapping-data partition pattern, for example.
- Readers-writers synchronization is another example.

Subclassing

In theory, object-oriented systems make everything wonderful.
- Including concurrency control and synchronization.
In practice, finding that magic plus sign has been hard.
- Inheritance makes interference control difficult.
- Particularly 80s-style code-sharing inheritance.
90s-style behavioral subclassing is more suited to combining concurrency and object-oriented systems.
- Each object has its own, well defined responsibilites.
- Inter-object relations are minimal and abstract.
Disciplined subclassing can simplify synchronization designs.
- The Template Pattern, for example.
- Make sure you're using behavioral and not structural inheritance.

A Readers-Writers Template

A readers-writers synchronization template.

abstract class RWTemplate private int ar, aw, wr, ww protected abstract void doRead() protected abstract void doWrite()

public void read() beforeRead() try doRead() finally afterRead() public void write() beforeWrite() try doWrite() finally afterWrite()
private synchronized void beforeRead() ++wr while (aw + ww != 0) wait --wr ++ar private synchronized void afterRead() --ar notifyAll()

There could be a lot of these, based on policy.
- Policies involving concurrency, timely access, fairness.

Layering Guards

Synchronization can be added as a child class too.

Useful for adapting existing classes for concurrent execution.

class Queue Object get() { ... } void put(Object o) { ... }

class ConcQueue synchronized Object get() return super.get() synchronized void put(Object o) super.put(o)

This is not behavioral inheritance (subtype polymorphism).
- The parent and child class methods behave differently.

Layering Difficulties

Inheritance and concurrency don't mix easily.
- Without care, there are too many paths to interference.
```
Queue q = new ConcQueue()
```
Re-coding parent methods for child notifications.
- A bad sequential action may be a good concurrent action.
- Removing from an empty queue.
Re-adapting concurrent behavior.
- A child wants behavior different from its parent.
- This is a cue to refactor your design.
Insufficient parental state maintenance.
- The parent's state machine is simpler than is the child's.
Losing subtype polymorphism.
- This is probably unavoidable.
In general, parents synchronize and children do.

Nested Locking

Here is some code for the honey bear's picnic:

synchronized void bearEnter() 
  potFull.wait()
  assert beesInPot == 0

What's wrong?

Keep a sharp eye out for nested locking.
- Java makes this hard because some nested locking is o.k.

Nested locking can be avoided by narrowing the scope of the critical section.

void bearEnter() 
  potFull.wait()
  synchronized (this) 
    assert beesInPot == 0

Points to Remember

Locking Structures
Bounded Queues
Tracking State
State Variables
Conflict Sets
Implementing Conflict Sets
Variants and Extensions
Subclassing
Readers and Writers
Layering Guards
Inheritance Anomalies
Nested Locking

This page last modified on 17 July 2003.