Talk:Readers–writer lock

Pseudocode

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 $P_{c}$ 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

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

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

"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

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)

Mutex/cv implementation is broken

The mutex/cv implementation holds the mutex while the reader is reading. This means it doesn't even support multiple concurrent readers which is the entire point of a readerS/writer lock. JoelKatz (talk) 01:17, 14 October 2019 (UTC)

Below is a simplistic C++ implementation. Untested. 75.149.30.179 (talk) 15:33, 16 October 2019 (UTC)

    class ReaderWriterLock : public NonCopyable {
    public:
        void acquire_read() {
            std::unique_lock<std::mutex> hold{mu};

            while (! is_ok_to_read()) {
                cv.wait(hold);
            }

            num_current_readers += 1;
        }

        void release_read() {
            std::unique_lock<std::mutex> hold{mu};
            num_current_readers -= 1;
            cv.notify_all();
        }

        void acquire_write() {
            std::unique_lock<std::mutex> hold{mu};

            num_writers_waiting += 1;
            while (! is_ok_to_write()) {
                cv.wait(hold);
            }
            num_writers_waiting -= 1;

            is_locked_for_writing = true;
        }

        void release_write() {
            std::unique_lock<std::mutex> hold{mu};
            is_locked_for_writing = false;
            cv.notify_all();
        }

    private:
        bool is_ok_to_read() {
            return (! is_locked_for_writing) && (num_writers_waiting == 0);
        }

        bool is_ok_to_write() {
            return (! is_locked_for_writing) && (num_current_readers == 0);
        }

        bool is_locked_for_writing = false;
        unsigned num_current_readers = 0;
        unsigned num_writers_waiting = 0;

        std::mutex mu;
        std::condition_variable cv;
    };

The code looks good to me. I've just put a pseudocode version of it on the page. Hope I haven't messed up anything… BlauerFuchs (talk) 22:22, 8 January 2020 (UTC)