5.3. Readers-Writers

Here we present an Orc solution to the readers-writers problem. Briefly, the readers-writers problem involves concurrent access to a mutable resource. Multiple readers can access the resource concurrently, but writers must have exclusive access. When readers and writers conflict, different solutions may resolve the conflict in favor of one or the other, or fairly. In the following solution, when a writer tries to acquire the lock, current readers are allowed to finish but new readers are postponed until after the writer finishes. Lock requests are granted in the order received, guaranteeing fairness. Normally, such a service would be provided to Orc programs by a site, but it is educational to see how it can be implemented directly in Orc.

{- A solution to the readers-writers problem -}

{- Queue of lock requests -}
val m = Channel()
{- Count of active readers/writers -}
val c = Counter()

{- Process requests in sequence -}
def process() =
  {- Grant read request -}
  def grant((false,s)) = c.inc() >> s.release()
  {- Grant write request -}
  def grant((true,s)) =
    c.onZero() >> c.inc() >> s.release() >> c.onZero()
  {- Goal expression of process() -}
  m.get() >r> grant(r) >> process()

{- Acquire the lock: argument is "true" if writing -}
def acquire(write) =
  val s = Semaphore(0)
  m.put((write, s)) >> s.acquire()

{- Release the lock -}
def release() = c.dec()

-------------------------------------------------

{- These definitions are for testing only -}
def reader(start) = Rwait(start) >>
  acquire(false) >> Println("START READ") >>
  Rwait(1000) >> Println("END READ") >>
  release() >> stop
def writer(start) = Rwait(start) >>
  acquire(true) >> Println("START WRITE") >>
  Rwait(1000) >> Println("END WRITE") >>
  release() >> stop

Let(
    process()  {- Output:     -}
  | reader(10) {- START READ  -}
  | reader(20) {- START READ  -}
               {- END READ    -}
               {- END READ    -}
  | writer(30) {- START WRITE -}
               {- END WRITE   -}
  | reader(40) {- START READ  -}
  | reader(50) {- START READ  -}
               {- END READ    -}
               {- END READ    -}
  {- halt after the last reader finishes -}
  | Rwait(60) >> acquire(true)
)

{-
OUTPUT:EXAMPLE
END READ
START WRITE
END WRITE
START READ
START READ
END READ
END READ
signal
-}

The lock receives requests over the channel m and processes them sequentially with the function grant. Each request includes a boolean flag which is true for write requests and false for read requests, and a Semaphore which the requester blocks on. The lock grants access by releasing the semaphore, unblocking the requester.

The counter c tracks the number of readers or writers currently holding the lock. Whenever the lock is granted, grant increments c, and when the lock is released, c is decremented. To ensure that a writer has exclusive access, grant waits for the c to become zero before granting the lock to the writer, and then waits for c to become zero again before granting any more requests.