State Dependent Action

(Lea - Chapt. 4)

Overview of the problem

• Objects may have either external (messages) or internal (state) triggering conditions

· "Safety concerns for classes with state-dependent actions revolve around the considerations necessary to complete a design so that you take into account all possible combinations of messages and states," (Lea)

• Actions may have state-based preconditions and postconditions which are unattainable (what do you do then?)

Alternative policies

"check-and-act (or pessimistic) policies"

• Inaction
• Balking
• Guarded suspension

"try and see (or optimistic) policies"

• Provisional action
• Rollback/Recovery
• Retry

Considerations in determining a reasonable policy for a "host" object

• Internal computability of preconditions
• External computability of preconditions (external visibility)
• Cost of computing preconditions
• Acceptability of request (requesting too much or too few resources?)
• Byproducts of assessing preconditions (are precondition checks stateless?)
• Resource contention (does “host” know all resources you need?)
• Acceptability of indefinite suspension (now or never?)
• Productivity of suspension (why not busy-wait?)
• Acceptability of failure (can failure lead to unsafe conditions?)
• Computability of failure
• Acceptability of false alarms
• Recoverability
• Client recovery

Representing State

• Need access to state information at "method entry" to carry-out policy (if you wait until you have changed state, you may have to rollback the state of the object)
• "Interfaces are useful vehicles for informally or semi-formally specifying the desired behavioral contract of sets of operations and the policies governing their use.” (Lea) (good place to specify invariants)
• Invariants may help you to structure the object synchronization code
• <await(Boolean -> Statement>
• Predicates are frequently used to specify logical states

• implicit variables, role variables, and state objects
• automatic scheduling from formal properties (Mizuno)

Guarded Suspension

• executable predicates (<await(Boolean -> Statement>)

• localized schedulers

• waits

public class GuardedClass { //generic code sketch
  protected boolean cond_ = false;
  protected synchronized void awaitCond() {
    while (!cond) {try(wait();) catch (InterruptedException ex) {}
    }
  }
  public synchronized void guardedAction() {
awaitCond();  // actions
  }
}

• busy-waits

protected void spinWaitUntilCond() {
  while (!cond_)
Thread.currentThread().yield();
}

• Interruptions
• catching an interrupt is much like getting control back from a "wait"

· possible actions:

o ignore by re-evaluation and re-waiting

o terminate thread

o exit the method (passing exception to next level up)

o perform cleanup

o user intervention

• Notifications

· liveness: wakeup waiting threads when conditions change

o encapsulate assignments in public method and notifyAll

o may cause too many notifications

o notifyAll is expensive operation

o "best practice" is to place notify and notifyAll as last operation in method (remember: notify is "notify and continue")

public class BoundedCounterV1 implements BoundedCounter {
  protected long count_ = MIN;
  public synchronized long value() { return count_; }
  public synchronized void inc() { awaitIncrementable(); setCount(count_ + 1);
  }
  public synchronized void dec() {
awaitDecrementable();
setCount(count_ - 1);
  }
  protected synchronized void setCount(long newValue) {
    count_ = newValue;
notifyAll(); // wake up any thread depending on new value
  }
  protected synchronized void awaitIncrementable() {
    while (count_ >= MAX)
      try { wait(); } catch(InterruptedException ex) {};
  }
  protected synchronized void awaitDecrementable() {
    while (count_ <= MIN)
      try { wait(); } catch(InterruptedException ex) {};
  }
}

• Notification with "notify()" (less time than notifyAll())

public class GuardedClassV2 {
  protected boolean cond_ = false;
  protected int nWaiting_ = 0; //count waiting threads
  protected synchronized void awaitCond() {
    ++nWaiting; // count waiting threads
    try { wait(); } catch { InterruptedException ex) {}
    --nWaiting; // no longer waiting
  }
  protected synchronized void signalCond() {
    if (cond_) //simulate notifyAll
     for (int i = nWaiting_; i > 0 ; --i)
      notify();
  }
}

• notify can also be used in a cascading fashion (each thread "notify"s the next one on the lock) as in the Alarm Clock of C.A.R. Hoare

Tracking State in Objects

• notifyAll for every state change is extremely expensive but quite robust
• logical state analysis should result in fewer unnecessary "notify"s
• transitions only made out of "top" and "bottom" in following
• The following example of a BoundedCounter illustrates this logical state analysis and can be used to implement Bounded Buffers

State	Condition	inc	dec
top	value == MAX	no	yes
middle	MIN < value < MAX	yes	yes
bottom	value == MIN	yes	no

Tracking State Variables

• Adding a "checkstate" method to do the re-evaluation of the conditions after each update
• Adding an explicit "state" variable

public class BoundedCounterVSW implements BoundedCounter {
  static final int BOTTOM = 0;
  static final int MIDDLE = 1;
  static final int TOP = 2;
  protected int state_ = BOTTOM; // the state variable
  protected long count_ = MIN;
  public synchronized long value() { return count_; }
  public synchronized void inc() {
    while (state_ == TOP)
      try { wait(); } catch(InterruptedException ex) {};
    ++count_;
checkState();
  }
  public synchronized void dec() {
    while (state_ == BOTTOM)
      try { wait();} catch(InterruptedException ex) {};
    --count_;
checkState();
  }
  protected synchronized void checkState() {
int oldState = state_;
    if (count_ == MIN) state_ = BOTTOM;
    else if (count_ == MAX) state_ = TOP;
    else state_ = MIDDLE;
    if (state_ != oldState &&
      (oldState == TOP || oldState == BOTTOM))
notifyAll();
  }
}

Balking

• Balking is a form of "check and see"
• A balking method checks to see if the preconditions hold. If so, it continues, else it returns a negative response to the caller.
• It does not make a prediction whether the preconditions will ever be true.
• Implementing Balking:

• Be aware of needs of client (caller) and do any cleanup, throw any exceptions, and send failure responses
• Check and return failure conditions
• Make public accessors available which the client can use to assess state (only as an indicator, because it could change before the client calls again)

public class BalkingBoundedCounter {
  protected long count_ = BoundedCounter.MIN;
  public synchronized long value() { return count_; }
  public synchronized void inc() throws CannotIncrementException {
    if (count_ >= BoundedCounter.MAX)
      throw new CannotIncrementException();
    else
      ++count_;
  }
  public synchronized void dec() throws CannotDecrementException {
    if (count_ <= BoundedCounter.MIN)
      throw new CannotDecrementException();
    else
      --count_;
  }
}

Optimistic Policies

• Try to fill a request without first checking preconditions to see if it can be satisfied.
• Many scheduling operations need to do some computation before deciding which (highest priority) thread to schedule. Thus, the state of the system may have changed, so you have to "undo" or "reset" computations already done before you "notify" or "resume" selected thread.
• Example: ("accept suchthat bool_expr by arith_expr")
• Optimistic control has its roots in data base updating, fault-tolerance, and design for testability
• Features of optimistic control techniques

1. a means of detecting failure
2. a policy for dealing with failure
3. a mechanism to deal with the consequences of failure

1. provisional action: only update copies and do not make them permanent until it is known that there has not been a failure (data base updating)
2. rollback/recovery: update the state variables, but keep enough information around to "rollback" their values to the proper state prior to the "fault" (optimistic distributed simulation)