Concurrent Programming CS 598 Class Notes

Lecture Notes for Concurrent Programming

20 August 2002 - Code Review 2

Solution 1

private Object mutex = new Object()

query

  synchronized mutex
    if (!running) return
    workingR++

  recieve = db.readDb(keywords)

  synchronized mutex
    workingR--
    if workingR == 0
      mutex.notify()

write

  synchronized mutex
    while workingR > 0
      try mutex.wait()
      catch (InterruptedException ex) return
    if (!running) return
    workingW++

    db.writeDb(description)

    workingW--
    mutex.notify()

Comments on Solution 1

Doesn't provide exclusive access for writers.

write

  synchronized mutex
    while workingR > 0
    while workingR + workingW > 0
      try mutex.wait()
      catch (InterruptedException ex) return

Writer starvation.

Solution 2

BinarySemaphore 
  bsMutex = new BinarySemaphore(false)
  bsReads = new BinarySemaphore(false)
  bsWrite = new BinarySemaphore(false)

readerAccess

  bsMutex.getAccess()

  if nActiveWriters > 0
    waitingR++
    bsMutex.giveAccess()
    bsReads.giveAccess()  // should be bsReads.getAccess()

  workingR++

  pass()

  String[] returnSet = get(keywords)

  bsMutex.getAccess()
  workingR--

  pass()

  return returnSet

Passing the Baton

private void pass()

  if waitingR + workingW > 0 && waitingW > 0 

    dRatio = (WaitingR + WorkingR)/waitingW

    if dRatio >= THRESHOLD
      iBalance = READERS
    else if 1 / dRatio) >= THRESHOLD
      iBalance = WRITERS
    else
      iBalance = OKAY

  if workingW + waitingW == 0 && WaitingR > 0
    allowReader()

  else if workingW + workingR == 0 && waitingW > 0
    allowWriter()

  else if workingW + workingR == 0 && 
          waitingW > 0 && WaitingR > 0
    if iBalance != WRITERS
      allowWriter()
    else if iBalance != READERS
      allowReader()

  else if workingR > 0 && waitingW > 0
    iBalance = READERS

  else
    bsMutex.giveAccess()

Passing the Baton Simply

pass

  if workingW == 0 && waitingR > 0
    waitingR--
    bsReads.giveAccess()

  else if workingW + workingR == 0 && waitingW > 0
    waitingW--
    bsWrite.giveAccess()

  else
    bsMutex.giveAccess()

Pass the baton clearly too.

readerAccess

  bsMutex.getAccess()

  if nActiveWriters > 0
    waitingR++
    bsMutex.giveAccess()
    bsReads.giveAccess()  // should be bsReads.getAccess()
    waitingR--

  // etc

pass

  if workingW == 0 && waitingR > 0
    waitingR--
    bsReads.giveAccess()

  // etc

Solution 3

public final class RwMonitor

  private int workingR = 0
  private int workingW = 0
  private int waitingR = 0
  private final LinkedList writer_list = new LinkedList()

public synchronized void request_query()
  if workingW == 0 && writer_list.size() == 0
    ++workingR
 else
    ++waitingR
    wait()

public synchronized void query_accomplished()
   --workingR
   if workingR == 0 signal_writers()

public void request_write()
  Object wl = new Object()
  synchronized wl
    synchronized(this)
      if writer_list.size() == 0 && workingR + workingW == 0
        ++workingW
        return
      writer_list.addLast(wl)
    wl.wait()

public synchronized void write_accomplished()
  --workingW
  if (waitingR > 0) signal_readers()
  else signal_writers()

Signalling Workers

private void signal_readers()

  workingR = workingR + waitingR
  waitingR = 0
  cleanup()
  notifyAll()

private void signal_writers()

  if writer_list.size() > 0
     Object old = writer_list.removeFirst()
     ++workingW
     synchronized(old) 
       old.notify()
  cleanup()

public void cleanup()
  if workingR + workingW == 0 && t1.getend()
    t1.setrun(false)
    db = null

Solution 3 Comments

workingR is not always kept current.

synchronized request_query
  if workingW + writer_list.size() > 0
    ++waitingR
    wait()
  ++workingR

request_write() suffers from slipped notifies.
- Use a mutex lock instead of an Object.
- Nesting object locks is probably not right.
  - Can't unlock two instance locks atomically.
  - One way leads to deadlock, the other to slipped notifies.

Solution 4


private Object lock = new Object()
private int workingR = 0
private int workingW = 0

query

  synchronized(lock)
    while workingW == 1
      lock.wait()
    workingR++

  db.readDB(keywords)

  synchronized(lock)
    workingR--
    if (workingR == 0) lock.notify()

write

  synchronized(lock)
    while workingR > 0 || workingW > 0
      lock.wait()
    workingW = 1

  db.writeDb(description)

  synchronized(lock)
    workingW = 0
    lock.notify()

Solution 4 Comments

Allows reader overtaking for readers and writers.

Points to Remember

Control interference.
- Correctness, not performance, is the main concern.
Keep it simple.
- Less chance to err; more obvious errors.
Minimize and isolate global use.
- Reduce and simplify inteference arguments.
Favor safety over liveness.
- Consentrate on mutual exclusion, not reader concurrency.
- Doing nothing is better than doing something wrong.

This page last modified on 20 August 2002.