RWLock implements a reader/writer lock using two snoopy semaphores, r and w, and an atomic counter, na. The number of threads waiting on r is the number of readers waiting on the lock, and similarly for w and writers. The value of na is the number of threads currently active in the lock.

The site pick() determines if a reader or a writer should be granted access next. pick uses definite snoop (snoopD) on r and w to determine is there are readers or writers waiting; if both are waiting, one is picked at random; if neither are waiting, pick blocks (using blocking snoop) until either a reader or writer is waiting; otherwise whatever kind of thread is waiting is granted access.

The lock has a manager that grants access based on pick. The invariant of the manager is that no writer is running; so readers can proceed immediately. However writers must block until all readers have completed (by blocking on na until it is zero). Correctness is easy to see because only one manager is running and it only allows writers if no other threads are active and makes sure writers finish before granting any other access. Fairness is trivial in all cases except when readers and writers are waiting. In this case randomization guarantees that eventually both will be granted access.

This implementation is equivalent to the implementation using two additional counters and an additional semaphore in Misra's book. The counters are used to provide the same information as snoopD (if a thread is waiting) and the semaphore provides blocking in place of blocking snoop.

The code with a test case is shown below.

def class RWLock() =
    val r = Semaphore(0)
    val w = Semaphore(0)
    val na = Counter(0)

    def startread() = r.acquire()
    def startwrite() = w.acquire()
    def end() = na.dec()
    
    def pick() = 
        def h(true, false) = true
        def h(false, true) = false
        def h(true, true) = Random(2) = 0
        def h(false, false) = x <x< (w.snoop() >> false | r.snoop() >> true)

        val rw = r.snoopD() >> true ; false
        val ww = w.snoopD() >> true ; false
        h(rw, ww)

    repeat(lambda() =  
        if( pick() ) then
          na.inc() >> r.release()
        else
          na.onZero() >> na.inc() >> w.release() >> na.onZero()
          )
          

val l = RWLock()

l.startread() >> Println("reading 1") >> Rwait(2000) >> Println("read done 1") >> l.end() |
l.startread() >> Println("reading 2") >> Rwait(200) >> Println("read done 2") >> l.end() |
l.startread() >> Println("reading 3") >> Rwait(2000) >> Println("read done 3") >> l.end() |
l.startread() >> Println("reading 4") >> Rwait(200) >> Println("read done 4") >> l.end() |
l.startwrite() >> Println("write 1") >> Rwait(200) >> Println("write done 1") >> l.end() |
l.startwrite() >> Println("write 2") >> Rwait(200) >> Println("write done 2") >> l.end()

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 05-Mar-2013 17:37 by Arthur Peters