Talk:Readers–writer lock

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Stub-class)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Stub-Class article Stub  This article has been rated as Stub-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
Note icon
This article has been automatically rated by a bot or other tool as Stub-Class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.

Pseudocode[edit]

We need a pseudocode implementation of this concept. --203.173.190.36 (talk) 01:29, 22 March 2008 (UTC)

Done. QVVERTYVS (hm?) 12:40, 17 November 2015 (UTC)
The implementation you added was incorrect. Msnicki (talk) 16:45, 17 November 2015 (UTC)
@Msnicki: care to point out what is incorrect about it? QVVERTYVS (hm?) 18:45, 17 November 2015 (UTC)
Both "lock" operations you've added busy wait on w and C while holding m. How is the other thread supposed to get in to do a release? If either thread decides to wait for any reason, it must release the lock on the structure, then reacquire it when it wakes up. Properly designed, c.f., the 1995 Hamilton and Zimmerman implementations, references to which you deleted, the reader should never have to wait, if it can take the lock at all, all it need do is increment the number of readers. Only the writer may have to wait, giving up the lock when it discovers there are readers, going to sleep on signal that all the readers have left, before reacquiring the lock and trying again. I don't have access to the source you're citing but my guess is that something's gotten lost in the translation. Is this pseudocode something you're closely paraphasing (do we have the rights?) or something you've made up (WP:OR)? Msnicki (talk) 19:09, 17 November 2015 (UTC)
Wait is not a busy-wait, it's the standard "wait" operation that all implementations of condition variables support, summarized in our article as:

wait c, m, where c is a condition variable and m is a mutex (lock) associated with the monitor. This operation is called by a thread that needs to wait until the assertion is true before proceeding. While the thread is waiting, it does not occupy the monitor. The function, and fundamental contract, of the "wait" operation, is to do the following steps:

(1) Atomically: (a) release the mutex m, (b) move this thread from the "ready queue" to c's "wait-queue" (a.k.a. "sleep-queue") of threads, and (c) sleep this thread. (Context is synchronously yielded to another thread.) (2) Once this thread is subsequently notified/signalled (see below) and resumed, then automatically re-acquire the mutex m.

Such a "wait" operation is available in POSIX, Java, Go, or anywhere else where condition variables are available. QVVERTYVS (hm?) 19:22, 17 November 2015 (UTC)
Regarding the paraphrasing, I added two more sources that present the exact same algorithm. QVVERTYVS (hm?) 22:35, 17 November 2015 (UTC)

merge[edit]

I suggest merging read/write lock pattern into readers-writer lock. They are so closely related that I think a good article on one of them will duplicate most of the information in a good article on the other one. --68.0.124.33 (talk) 14:54, 17 October 2008 (UTC)

+1. It looks like the text from read/write lock pattern has already been merged in, though some copy editing work looks appropriate. Jordan Brown (talk) 00:36, 2 March 2010 (UTC)

Title of the article[edit]

This title is unfamiliar to me, though perhaps that just marks me as some kind of dinosaur. I know this as either of the more descriptive "multiple readers / single-writer lock" or "shared read lock". If it were just up to me, I'd rename the page. But I'm curious to know how others feel. Msnicki (talk) 19:58, 15 May 2011 (UTC)

Also, for some reason the dash/hyphen/whatever chosen for the title results in an address with %E2%80%93 in it. I figure perhaps a copy-and-paste error since other articles (e.g. S-CRY-ed) have a "regular" dash in them. Sorry I'm being pretty vague. RobI (talk) 19:08, 17 February 2012 (UTC)

Fair RWlock with 1 mutex for readers[edit]

"Faster Fair Solution for the Reader-Writer Problem" http://arxiv.org/ftp/arxiv/papers/1309/1309.4507.pdf It's fair. It (mostly) requires only 1 mutex for readers. — Preceding unsigned comment added by 149.5.33.26 (talk) 13:47, 8 October 2014 (UTC)

Incorrect implementation[edit]

g can't be a mutex; it needs to be a binary semaphore, so that it can be acquired by one thread (i.e. the first reader) and released by another (i.e. the last reader) — Preceding unsigned comment added by 194.138.12.171 (talk) 08:41, 5 July 2016 (UTC)

I agree with this important observation: g can't be a mutex, it should be a semaphore. The page should be updated. Interestingly, in C++11, the standard library does not provide semaphores. Implementing a semaphore in C++11 is easy, using a condition variable. That solution for this Readers-Writer example renders the first solution remarkably like the second. --Jvanehv (talk) 08:55, 17 February 2017 (UTC)