Implementing write-preferring R/W lock

Question

I have a mutex library, and am trying to implement a write-preferring lock. I am looking at this example:

https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock

I understand the read-preferring lock, but I don't understand the write-preferring lock. Can someone explain how to implement that?

Specifically, I don't understand this part:

While w:
  wait c, m

I also don't understand if the flag w is universal, or just a different flag per process. I assume it's the former.

For example, here we see the algorithm for getting a read-lock:

Lock m (blocking).
While (w or r > 0):
  wait c, m
Set w to true.
Unlock m.

but what does wait c, m mean? It can't mean waiting to get a lock on both c and m, because we already locked m in step 1.

And also, for Set w to true - does that mean w has to be set to true in all processes or just this process?

I translated the wikipedia article write-preferring lock to here: https://github.com/ORESoftware/live-mutex/blob/dev/docs/write-preferring-rw-lock.md — , Jun 29 '18 at 23:07
Given my translation, another thing that confuses me is that it seems like every operation has to get a lock on m. That means that readers will block readers which is not that ideal. — , Jun 29 '18 at 23:07

Chris Slothouber · Accepted Answer · 2018-07-10T16:54:06.437

The Wikipedia article referenced in your question has a subscript note that states:

This is the standard "wait" operation on condition variables, which, among other actions, releases the mutex m.

Standard "wait" on conditional variable functions typically accept two parameters: a conditional variable and a mutex. The mutex m is released by the "wait" function and the thread sleeps until c is signaled. The m lock is re-acquired (which could involve waiting if a lock has been acquired elsewhere) once c is signaled and the thread proceeds.

Setting the (global) flag w to true indicates a write lock is currently claimed by a write thread.

Mutex m is locked only while negotiating the critical section of setting or releasing read/write states by modifying condition variable c, integer r (number of readers waiting), flag w (writer waiting).

The pseudo-code you posted for acquiring a read-lock (which is actually getting a write-lock, thus the Set w to true) uses both a mutex (m) and a conditional variable (c). First, it attempts to attain an exclusive lock on the mutex m in order to modify the relevant inputs in an atomic fashion. Once this is achieved, it calls wait c, m if w (write lock) or r (readers waiting) are non-zero.

To summarize:

the "wait" function accepts two parameters: c and m. It releases m and sleeps until receiving a signal on c.
the mutex m is locked when setting or releasing a read- or write-lock.

Implementing write-preferring R/W lock

1 Answers1