Lecture Notes for Concurrent Programming

14 August 2003 - Polyphonic Concurrency Control Mechanisms

Outline

• Mutual exclusion and Monitors

• Call-Based Concurrency Specification

• Path Expressions

  • Syntax

  • Concurrency Control

• Polyphonic Synchronization

  • Polyphonic Syntax

  • Implementation Details

Review

• Unmediated concurrent access to shared data is bad.
  

• Synchronization techniques mediate concurrent access.

• Mutual exclusion via critical sections is a basic synchronization technique.

Mutual Exclusion

• Mutual exclusion is necessary, but is it sufficient?
  

  • Consider readers-writers synchronization.

  • Mutual exclusion is both too much and too little.

• Remember, there are two kinds of synchronization: mutual exclusion and conditional synchronization.

• Implementing critical sections is also tricky.

  • Low-level tools are hard to get right; high-level tools are expensive.

  • Protecting all accesses in critical sections can be a difficult maintenance task.

Monitors

• Monitors solve both critical-section problems.
  

  • Strict encapsulation guarantees mutual exclusion.

  • Condition variables simplify coordination.

• Monitors are not without problems.

  • They seem to have no universal semantics.

  • Nested entry calls tend toward deadlock.

  • Understanding complex coordination can be hard.

• Monitors lead the way towards using entry calls to specify acceptable concurrent execution sequences.

Call-Based Concurrency Specification

• Consider a monitor implementing a binary semaphore.

  • With put() and get() entries.

• Is the following an acceptable entry-call sequence?

  get() -> get() -> put()
  

  • No, even if the semaphore's initialized to 1.

  • get() must follow, not precede put().

• How about the following?

  put() -> put() -> get() -> get()
  

• Can we characterize all and only the legal sequences of entry calls?

  • If so, can we translate the characterization into coordination code?

Path Expressions

• Path expressions specify acceptable entry-call sequences.

  The Specification of Process Synchronization by Path Expressions by R. Campbell and N. Habermann, Proceedings of an International Symposium on Operating Systems (LCNS 16), Springer-Verlag, April 1974.

• A path expressions is a declarative specification.

  • It indicates what you want, not how to get it.

  • A path expression compiler figures out the how.

• Path expressions are related to regular expressions, which makes them familiar to most programmers.

  • And hence to state machines too.

  • But the semantics sometimes goes awry.

• Path expressions readily translate to coordination code.

  • The translation needs only binary semaphores.

  • Path expressions and binary semaphores have equivalent synchronization power.

Path-Expression Syntax

• The basic path-expression form is
  path exp

• A comma indicates concurrent execution.
  exp₀ , exp₁

  • exp₀ and exp₁ can run concurrently.

  • Many instances of either expression can be running.

• A semicolon indicates sequential execution.
  exp₀ ; exp₁

  • exp₁ begins after exp₀ finishes.

  • Only one instance of each are running.

• Parenthesis ( exp ) group and nest as they usually do.

Path-Expression Concurrency Control

• A colon limits concurrent instances to the given value.
  n : exp

  • Up to n copies of exp can be running concurrently.

  • "Ah", you may be saying to yourself, "finite state machines can't count."

• Brackets indicate unrestricted concurrency.
  [ exp ]

  • Arbitrarily many instances of exp may be running concurrently.

Semaphore Path Expressions

• The semaphore path expression

  path put() , get()
  

  is an unsatisfactory specification for semaphores. (Why?)

• The semaphore path expression

  path put() ; get()
  

  is also an unsatisfactory specification for a semaphore, but less so than the previous specification (Why?)

• The semaphore path expression

  path [ put() ] , 1 : get()
  

  should specify a binary semaphore, but not a counting semaphore (Why?)

Path-Expression Evaluation

• Path expressions have successful and influential.

  • Success has been limited to concurrent languages.

  • Influence likewise, although the relation to state machines helps.

• It is difficult to define a universal semantics.

  • In this they are like semaphores.

  • Every path-expression implementation is different from the others.

• Implementations tend towards inefficiency.

  • This is not insurmountable.

Path-Expression Properties

• Do path expressions provide liveness or safety properties?

  • They prevent something bad from happening.

  • That sounds like a safety property to me.

• Path expressions can't provide liveness properties.

  • The data can't make sure something good happens.

  • Only the users of the data can insure that.

• But, if something good happens, what does the data do?

  • The programmer still has to write code for each entry

  • This still requires private, shared state.

Path Expressions vs. Condition Variables

• Compare

  monitor OneSlotBuffer data buffer path put ; get void put(data d) buffer = d void get(data & d) d = buffer

  monitor OneSlotBuffer data buffer cond empty = true full = false void put(data d) empty.wait() buffer = d full.signal() void get(data & d) full.wait() d = buffer empty.signal()

Improving Path Expressions

• Having to write individual entry bodies is a pain.

  • The control and data are spread throughout the monitor.

  • Different uses of the same entry have to be consistent.

• Suppose we could associate code with each path expression.

  • After the path expression completes, execute the associated code.

  monitor OneSlotBuffer
  
    path put(data din) ; get(data & dout) {
      dout = din
      }
  

• Oh, and it would be nice if path expressions had an agreeable semantics, too.

Polyphonic Synchronization

• Congratulations, you've just invented polyphonic synchronization.

• First, restrict path expression syntax.

  • There is only parallel composition, no sequential composition.

    • Only commas, no semicolons.

  • Concurrent invocation is restricted to one instance.

    • Concurrency is 1 : [ exp ].

  • At most one invocation can be synchronous.

  • These restrictions are mostly technical, not essential.

• The Polyphonic semantics is based on the join calculus.

  • This is why polyphonic synchronization is not path expressions.

Polyphonic Syntax

• Extend basic object-oriented class syntax.

  • Each method can have several signatures.

    • Each signature represents an expression in comma-separated list.

    • Signature order doesn't matter.

    • The set of signatures is called a chord.

  • Concurrent expressions are marked with async.

    • And have no return value

  • The synchronous signature, if any, looks normal.

• Compare

  path put(data din) ; get(data & dout) {
    dout = din
    }
  

  to

  async put(data din) & get(data & dout) {
    dout = din
    }
  

Polyphonic Readers-Writers

class ReadersWriters

  void  writerEnter() &
  async Idle() { }

  void writerExit()
    Idle()

  void  readerEnter() &
  async idle()
    readerCount(1)

  void  readerEnter() &
  async readerCount(int n) 
    readersCount(n + 1)

  void  readerExit() &
  async readerCount(int n)
    if n = 1
      Idle()
    else
      readersCount(n - 1)

  ReadersWriters
    idle()

Implementation Details

• Devote a shared queue per class instance.

  • Queue arguments for asynchronous calls and threads blocked on synchronous calls.

• A chord is complete if each signature has been called.

  • The chord's synchronous call (if any) executes the body.

  • An all-asynchronous chord executes the body with a new thread.

• A call that doesn't complete a chord hangs on the queue.

  • An asynchronous call puts its arguments on the queue.

  • A synchronous call hangs itself on the queue.

Points to Remember

• Everything old is new again.

  • 'Twas ever thus.

• Path expressions are like regular expressions over entry calls.

  • A simple, effective approach to concurrency control.

• Polyphonic synchronication combines path expressions with code.

  • When the path completes, the code executes.

This page last modified on 14 August 2003.