Lecture Notes for Concurrent Programming

7 August 2002 - Readers-Writers KWIC Access

Readers-Writers KWIC Access

• The Readers-Writers Problem

• The Trivial Database Clients

• Use an Explicit Queue

• The Queue

• The Database Queue

The Readers-Writers Problem

• Give readers and writers access to a database.

  • Readers allow shared access.

  • Each Writer requires exclusive access.

• Access should be concurrent, fair, and timely.

  • At least as many readers sharing as possible.

  • There should be no starvation and no unexpected delays.

  • Changes should appear as soon a possible, consistent with other requirements.

The Generic Database

• Both the access protocols and database itself are parameters.

  
  class KWICDB 
  implements KWICDBInterface
  
    private DBWriterClient writerClient
    private DBReaderClient readerClient
    private KWICDatabase kwicdb
  
    public String [] 
    query(String keywords[]) 
      readerClient.enter()
      String [] entries = kwicdb.get(keywords)
      readerClient.exit()
      return entries
  
    public void 
    write(String description)
      writerClient.enter()
      kwicdb.put(description)
      writerClient.exit()
  
  

  • The reader and writer clients implement access protocols.

• This is known as the strategy pattern.

Generic Database Clients

• The clients determine the access protocols.

  
  abstract class DBClientTemplate
  
    protected  DatabaseAccess dba
    abstract boolean databaseSafe()
    abstract void databaseWait()
    abstract void databaseEnter()
    abstract void databaseExit()
  
    DBClientTemplate(DatabaseAccess dba)
      this.dba = dba
  
    void enter()
      dba.mutex.lock()
      if (!databaseSafe()) databaseWait()
      databaseEnter()
  
    void exit()
      try dba.mutex.lock()
      catch (InterruptedException ie)
        Thread.currentThread().interrupt()
      databaseExit()
  
  

  See the complete code.

• For this problem there are reader and writer clients.

  • Readers and writers have different protocols.

• Clients work on database access state.

The Trivial Database Client

• Implements pure database mutual exclusion.

  • Readers and writers do the same thing.

  
  class DBClient
  extends DBClientTemplate
  
    DBClient(DatabaseAccess dba)
      super(dba)
  
    boolean databaseSafe()
      return true
  
    void databaseWait() 
      assert false
  
    void databaseEnter() {
      }
  
    void databaseExit()
      dba.mutex.unlock()
  
    void exit()
      databaseExit()
  
  

• The database access state is the mutex.

  class DatabaseAccess
    Mutex lock = new Mutex(Mutex.unlocked)
  

Problems With The Trivial Solution

• There are many problems.

  • No concurrency.

    • Pure mutual exclusion.

  • Possible starvation.

    • No fairness.

    • No timeliness.

• Doing better requires reader-writer discrimination.

  • But only one wait set.

Condition Variables

• Use condition variables for readers and writes.

Condition Variable Problems

• Atomic unlock ‘n' block is hard to implement.

  • No connection between the instance mutex and the condition variable.

  • Risk missing condition signals.

• Readers can overtake writers.

• Writer release fairness.

Handoff Condition Variables

• Use baton passing to avoid atomic unlock ‘n' block.

Using Handoff Condition Variables

• The database access state.

  class DatabaseAccess
    Mutex mutex = new Mutex(Mutex.unlocked)
  
    HandoffConditionVariable
      emptyDatabase = new HandoffConditionVariable(mutex)
      noWriterInDB = new HandoffConditionVariable(mutex)
  
    boolean writerInDB = false
    int readersInDB = 0
  

Condition Variable Clients

class DBReaderClient
extends DBClientTemplate

  boolean databaseSafe()
    return !dba.writerInDB

  void databaseWait() 
    dba.emptyDatabase.pause()

  void databaseEnter()
    dba.readersInDB++
    if dba.noWriterInDB.waiting()
      dba.noWriterInDB.resume()
    else 
      dba.mutex.unlock()

  void databaseExit()
    dba.readersInDB--

    if dba.emptyDatabase.waiting()
      dba.emptyDatabase.resume()
    else if dba.noWriterInDB.waiting()
      dba.noWriterInDB.resume()
    else 
      dba.mutex.unlock()

See the complete code.

• The writer is similar.

init() and term()

• init() prevents database entry and exit.

• term() Allows database exit and prevents entry.

• Define database clients that have these behaviors

  class DBInvalidWriterClient 
  extends DBWriterClient
  
    void enter() 
    throws InterruptedException
      throw new Error("The database is not accepting clients.")
  
    // exit() inherited from DBWriterClient.
  

  • DBInvalidReaderClient is defined similarly.

• This approach doesn't prohibit database exit before init().

  • That should never happen, but who knows?

  • The ultra-paranoid would define two more pre-init() classes that explode on exit too.

Implementing init() and term()

• The database starts off with invalid clients.

• init() changes them to valid clients.

• term() changes them back to invalid clients.

  class KWICDB 
  implements KWICDBInterface
  
    private DatabaseAccess dba = new DatabaseAccess()
  
    private DBClientTemplate 
      invalidWriterClient = new DBInvalidWriterClient(dba)
      invalidReaderClient = new DBInvalidReaderClient(dba)
      readerClient = invalidReaderClient
      writerClient = invalidWriterClient
  
    public KWICDBInterface init()
      readerClient = new DBReaderClient(dba)
      writerClient = new DBWriterClient(dba)
      return this
  
    public void term()
      readerClient = invalidReaderClient
      writerClient = invalidWriterClient
  

  See the complete code.

• Notice how the database-access state is shared between clients.

• This solution is independent of all other details.

Improving on Handoff Condition Variables

• Starvation is still possible.

  • Java's release (lack of) policy.

• FIFO wait sets can solve this problem.

  • A wait set with a FIFO release policy.

• Two wait sets can solve reader overtaking.

  • The outer wait set collects the incoming.

  • The inner wait set releases into the database.

  • They switch inner for outer after release.

• This is getting complicated - is there an easier way?

The Readers-Writers Queue

• Readers and writers queue up.

  

• Fair under liveness.

• Multiple reader releases provide concurrency.

  • A leaving reader looks back and releases the next reader.

• Safety is easy.

  • A leaving writer doesn't look back.

  • A leaving reader doesn't release the next writer.

• No release complexity.

  • It's queue release.

  • Only one point of release, not two or three.

Queue Timeliness

• Timeliness is easy too.

  • Queue ordering provides expected behavior.

• It's also easy to augment timeliness.

  • Use sinking writes to slightly bias writers over readers.

    • A writer sinks past readers in the queue.

    • Readers get bypassed at most once for fairness.

      

The Readers-Writers Queue

• The standard queue interface.

  class QueueElement 
  
    Mutex delay(Mutex.locked)
  
    boolean isReader
    boolean byPassed = false
    QueueElement next = null
  

• The mutex starts off locked to avoid missed notifies.

• The database access state adds a queue and a mutex.

  class DatabaseAccess 
  
    Mutex mutex = new Mutex(Mutex.unlocked)
    Queue waiters = new Queue()
  
    boolean writerInDB = false
    int readersInDB = 0
  

  • Instance locks cause the multiple release problem.

Reader Queue Protocols

• Database safety doesn't change.

• Database entry requires a look back.

  class DBReaderClient
  
    void entry()
  
      dba.mutex.lock()
  
      if !dba.waiters.empty() || dba.writerInDB
        QueueElement qe = dba.waiters.enq(true)
  
        dba.mutex.unlock()
        qe.delay.lock()
        dba.mutex.lock()
  
        if dba.waiters.head() != null
  	if dba.waiters.head().isReader
  	  dba.waiters.deq().delay.unlock()
  
      readersInDB++
  
      dba.mutex.unlock()
  

Reader Exit Protocol

• Reader exit is almost the same.

  • Release the writer (if any) at the queue head.

  • A reader at the queue head is released by the previous reader.

    void exit()
  
      dba.mutex.lock()
  
      if --readersInDB == 0 
        if dba.waiters.head() != null 
          if dba.waiters.head().isWriter
            dba.waiters.deq().delay.unlock()
  
      dba.mutex.unlock
  

Writer Protocols

• Database safety doesn't change.

• A dequeued writer doesn't look back.

  
  class DBWriterClient
  
    void enter()
  
      dba.mutex.lock()
  
      if !dba.waiters.empty()
         || dba.writerInDB || dba.readersInDB > 0
  
        QueueElement qe = dba.waiters.enq(false)
  
        dba.mutex.unlock()
        qe.delay.lock()
        dba.mutex.lock()
  
      writerInDB = true
      dba.mutex.unlock()
  
  

• Database exit releases the queue head.

  
    void exit()
  
      dba.mutex.lock()
  
      writerInDB = false
  
      if dba.waiters.head() != null
        dba.waiters.deq().delay.unlock()
  
      dba.mutex.unlock()
  
  

Baton Passing

• Baton passing cuts down synchronization overhead.

  
  class DBWriterClient
  
    void enter()
  
      dba.mutex.lock()
  
      if !databaseSafe()
        QueueElement qe = dba.waiters.enq(true)
        dba.mutex.unlock()
        qe.delay.lock()
        dba.mutex.lock()
  
      writerInDB = true
      dba.mutex.unlock()
  
    void exit()
  
      dba.mutex.lock()
  
      writerInDB = false
  
      if dba.waiters.head() != null
        dba.waiters.deq().delay.unlock()
      else
        dba.mutex.unlock()
  
  

• Similarly for the reader.

Further Improvements

• Can we improve the queue-based solution?

  • Can we increase concurrency and minimize synchronization?

• One-reference instances reduce and make cheap synchronization.

  • But it conflicts with increased concurrency.

• Immutable instances provide infinite concurrency with no synchronization.

  • But how do writers deal with an immutable database?

    • Maybe one-reference instances can help.

• We need an immutable database for readers and a one-reference database for writers.

  • What?

The Database Queue

• Use a database queue rather than a readers-writers queue.

  • Each queue element is a description's KWIC index set.

  

• Readers traverse the queue finding matches.

• Writers build new nodes and enqueue them.

Database Queue Properties

• The queue is immutable; the queue head is not.

  • Readers can traverse without synchronization.

  • Queue head conflict is atomic.

• Each writer constructs its own queue element.

  • One active reference provides mutation without synchronization.

  • The enqueue requires synchronization.

• Queues provide maximum concurrency with minimum synchronization.

  • All threads work concurrently.

  • Readers never block, writers block only when enqueueing.

The Database Queue Implementation

• A straightforward queue implementation

  class QueueElement
  
    QueueElement next = null
    final KWICIndexEntryGroup entries
  
    QueueElement(KWICIndexEntryGroup entries)
      this.entries = entries
  
  interface QueueTraverser
  
    void forEach(KWICIndexEntryGroup entries)
  
  class Queue
  
    private QueueElement qhead = null
  
    boolean empty() { ... }
  
    void enq(QueueElement qe) { ... }
  
    QueueElement head() { ... }
  
    void traverse(QueueTraverser qt)
      QueueElement qe
      for (qe = qhead; qe != null; qe = qe.next)
        qt.forEach(qe.entries)
  

The KWIC Database

class KWICDB 

  private KWICDatabase KWICDB = new KWICDatabase()
  private boolean entryOk = false

  public KWICDBInterface init() 
    entryOk = true

  public String [] query(String keywords[])
    if entryOk return KWICDB.get(keywords)
    else throw new Error()

  public void term()
    entryOk = false

  public void write(String description)
    if entryOk KWICDB.put(description)
    else throw new Error()

• Using a boolean to implement init() and term().

Discussion

• Are you on dope?! What if there's a million nodes.

  • One million nodes or 8-million database entries - what's the difference?

  • Don't underestimate synchronization costs.

  • C₁O(n) compared to C₂O(n).

• A collapser thread can also reduce the number of nodes.

  • Runs in parallel with readers and writers.

  • Synchronization with writers is tricky.

Points to Remember

• "There is a better way. Find it." - Thomas Edison

• Be prepaired to specialize your toolkit.

  • Specialize for semantics (FIFO mutex) or for performance (handoff).

This page last modified on 13 August 2002.