C++STL shared_mutex implementation and analysis

Shared_mutex profile

The shared_mutex class is a synchronization primitive that can be used to protect shared data from being accessed simultaneously by multiple threads.

Unlike other mutex types that facilitate exclusive access, Shared_mutex has two access levels:

  • Sharing – Multiple threads can share ownership of the same mutex.

  • Exclusivity – Only one thread can own a mutex.

The public methods of the shared_mutex class include:

STD ::shared_mutex was introduced in the C++17 standard, and a more complete description of STD ::shared_mutex can be found at cppreference.com.

Shared_mutex semantic

For non-C ++ standards, a more understandable name for Shared_mutex is read-write lock.

Mutex is more basic than read/write locks, so let’s start with mutex (STD ::mutex in the C++ standard).

Mutex blocks all other threads trying to enter the critical section. This critical section typically involves accessing or updating one or more data shared by these threads. Sometimes, however, we can distinguish between reading something and modifying something. This is also one of the scenario conditions for using read/write locks.

For the difference between acquiring a read-write lock for reading or acquiring a read-write lock for writing, the rules are as follows:

  • As long as no thread holds a given read-write lock for writing, any number of threads can hold that read-write lock for reading.
  • A read-write lock can be assigned for write only if no thread holds a given read-write lock for read or write.

Put another way, as long as no thread is modifying a given piece of data, any number of threads can have read access to that data. The current thread can modify a given data only if no other thread is reading or modifying it.

Applications that read data more frequently than they modify it could benefit from switching to read/write locks instead of mutex locks. Allowing more than one reader to exist at any given time provides a higher degree of concurrency, while protecting the data from interference by any other reader or writer while one writer is modifying it. This is one of the reasons why you should use read/write locks.

This shared access to a given resource is also called a shared-exclusive lock, where a read/write lock is acquired and used for reading is called a shared lock. The shared_mutex::lock_shared method is the same as the shared_mutex::lock method. Obtaining a read/write lock for a write is called an exclusive lock. One might wonder why the method for an exclusive lock is shared_mutex::lock instead of shared_mutex::lock_unique. The reason for this is to be consistent with the lock method name of STD ::mutex. The reason for this is to make the template classes STD ::lock_guard and STD ::unique_lock reusable in shared_mutex. The details are not covered here.

Shared_mutex implementation

Next, we’ll implement a Shared_mutex class ourselves. Complete engineering code: Github Gitee

1. Data structure of class shared_mutex

Shared_mutex contains the following member variables:

class shared_mutex {
private:
    std::mutex              mutex;
    std::condition_variable read;       // wait for read
    std::condition_variable write;      // wait for write
    int                     r_active;   // readers active
    int                     w_active;   // writer active
    int                     r_wait;     // readers waiting
    int                     w_wait;     // writers waiting
// ...
};
Copy the code
  • A mutex used to serialize access to member variables.
  • Two independent condition variables, one for read and one for write.
  • To be able to determine if there are waiting threads on the condition variable, we will save the number of active reader threads (r_active) and a flag indicating the number of active writer threads (w_active).
  • We also retain the number of threads waiting for reads (r_wait) and the number of threads waiting for writes (w_wait).

W_active is an int, but it’s a bool, because there can only be one active thread, but it doesn’t really make a difference whether we use bool or int for memory alignment.

2. Construction and destruction of shared_mutex class.

The first is the constructor:

shared_mutex::shared_mutex() :r_active(0), w_active(0), r_wait(0), w_wait(0) {}Copy the code

The mutex, read, and write member variables call the default constructor, and the shared_mutex object is unlocked when constructed.

Then there is the destructor:

shared_mutex::~shared_mutex()
{
    assert(r_active == 0);
    assert(w_active == 0);
    assert(r_wait == 0);
    assert(w_wait == 0);
}
Copy the code

There is nothing to say, just a few assertions.

3. Shared_mutex class to obtain/release the shared lock (read lock) related methods.

The first is the lock_shared method, which obtains the shared lock (read lock) for the read operation.

void shared_mutex::lock_shared(a)
{
    std::unique_lock<std::mutex> lock(mutex);
    if (w_active) {
        r_wait++;
        while (w_active) {
            read.wait(lock);
        }
        r_wait--;
    }
    r_active++;
}
Copy the code
  • If no writer threads are currently active, we register the r_active member variable, update the active reader thread count +1, and return from the lock_shared method to indicate success in obtaining the shared lock.
  • If a writer thread is currently active (w_active non-0), we register the r_WAIT member variable, update the number of waiting readers +1, and wait on the read condition variable (until the writer thread releases the lock and wakes up the current thread via the read condition variable).
  • In addition, to simplify the implementation, we do not consider the case of thread wait being cancelled on read condition variables, in which case r_wait will not be -1, resulting in data inconsistency. For the treatment of this situation, you can refer to the relevant books, here is not repeated.

Then there is the try_lock_shared method:

bool shared_mutex::try_lock_shared(a)
{
    std::lock_guard<std::mutex> lock(mutex);
    if (w_active) {
        return false;
    } else {
        r_active++;
        return true; }}Copy the code

The code logic is similar to lock_shared except that:

  • When a writer thread is active, it returns false directly, instead of a block on the read condition variable.
  • Returns true if the shared lock (read lock) was acquired successfully.

Finally, the unlock_shared method:

void shared_mutex::unlock_shared(a)
{
    std::lock_guard<std::mutex> lock(mutex);
    r_active--;
    if (r_active == 0 && w_wait > 0) {
        write.notify_one();
    }
}
Copy the code

This function essentially reverses the effect of lock_shared or try_lock_shared by reducing the number of active reader threads (r_active). If there are no active reader threads and at least one thread is waiting for a write, the write condition variable is notified to wake up one of them.

4. Shared_mutex class get/release exclusive lock (write lock) related methods.

The first is the Lock method, which obtains the exclusive lock (write lock) for the write operation.

void shared_mutex::lock(a)
{
    std::unique_lock<std::mutex> lock(mutex);
    if (w_active || r_active > 0) {
        w_wait++;
        while (w_active || r_active > 0) {
            write.wait(lock);
        }
        w_wait--;
    }
    w_active = 1;
}
Copy the code

This function is much like lock_shared, except for the predicate condition that waits on the write condition variable.

  • If any writer or reader threads are currently active, we register the w_WAIT member variable, update the number of waiting writers +1, and wait on the write condition variable (until either a writer thread releases the lock, or all reader threads release the lock and wake up the current thread via the write condition variable).
  • Otherwise, we register the w_active member variable, the writer flag of the update activity is 1 (true), and return from the lock method indicating that the exclusive lock was acquired successfully.
  • In addition, to simplify the implementation, we do not consider the case of thread wait being cancelled while writing the conditional variable, in which case w_wait will not be -1, causing data inconsistencies. For the treatment of this situation, you can refer to the relevant books, here is not repeated.

Then there is the try_lock method:

bool shared_mutex::try_lock(a)
{
    std::lock_guard<std::mutex> lock(mutex);
    if (w_active || r_active > 0) {
        return false;
    } else {
        w_active = 1;
        return true; }}Copy the code

The code logic lock is similar, except that:

  • If the read/write lock is currently in use (either by a reader thread or a writer thread), it will return false directly, instead of a block on the read condition variable.
  • Returns true if the exclusive lock (write lock) was acquired successfully.

Finally, the unlock method:

void shared_mutex::unlock(a)
{
    std::unique_lock<std::mutex> lock(mutex);
    w_active = 0;
    if (r_wait > 0) {
        read.notify_all(a); }else if (w_wait > 0) {
        write.notify_one();
    }
}
Copy the code

This function is called by a thread to release the write lock.

  • It is always available when a writer thread releases the read/write lock; If any threads are waiting, one of them must be woken up.
  • The implementation here is “read-first”, first finding the reader thread that is waiting. If so, the read condition variable is broadcast to wake them up.
  • If there are no waiting reader threads, but more than one writer thread is waiting, wake up one of them by notifying the write condition variable.
At this point, the complete implementation of the Shared_mutex class is covered.

Shared_mutex example

Next, we use an example of the shared_mutex class to introduce the shared_mutex share-exclusive feature.

First, let’s give a complete example code:

#include <iostream>
#include <string>
#include <chrono>
#include <iomanip>
#include <thread>
#include <shared_mutex>
#include "shared_mutex.hpp"

mini_stl::shared_mutex rwlock;

void thread1(a);
void thread2(a);

inline
std::ostream& operator<<(std::ostream &os,
        const std::chrono::time_point<std::chrono::system_clock> &t)
{
    const auto tt (std::chrono::system_clock::to_time_t(t));
    const auto loct (std::localtime(&tt));
    return os << std::put_time(loct, "%c");
}

inline
std::chrono::time_point<std::chrono::system_clock> gf_time(a)
{
    return std::chrono::system_clock::now(a); }inline
void sleep(int nsecs)
{
    std::this_thread::sleep_for(std::chrono::seconds(nsecs));
}

int main(int argc, char *argv[])
{
    std::thread thr1, thr2;

    rwlock.lock_shared(a);/* parent read locks entire file */
    std::cout << gf_time() < <": parent has read lock" << std::endl;

    thr1 = std::thread(&thread1);
    thr2 = std::thread(&thread2);

	/* 4parent */
    sleep(5);
    rwlock.unlock_shared(a); std::cout <<gf_time() < <": parent releases read lock" << std::endl;

    thr1.join(a); thr2.join(a);return 0;
}

void thread1(a)
{
    sleep(1);
    std::cout << gf_time() < <": first child tries to obtain write lock" << std::endl;
    rwlock.lock(a);/* this should block */
    std::cout << gf_time() < <": first child obtains write lock" << std::endl;
    sleep(2);
    rwlock.unlock(a); std::cout <<gf_time() < <": first child releases write lock" << std::endl;
}

void thread2(a)
{
    /* 4second child */
    sleep(3);
    std::cout << gf_time() < <": second child tries to obtain read lock" << std::endl;
    rwlock.lock_shared(a); std::cout <<gf_time() < <": second child obtains read lock" << std::endl;
    sleep(4);
    rwlock.unlock_shared(a); std::cout <<gf_time() < <": second child releases read lock" << std::endl;
}
Copy the code

In this example code, we have two reader threads (main and thread2) and one writer thread (thread1). Compile and run our program, and we can see the following output (not always the same for CPU scheduling) :

11/27/21 14:00:16: parent has read lock
11/27/21 14:00:17: first child tries to obtain write lock
11/27/21 14:00:19: second child tries to obtain read lock
11/27/21 14:00:19: second child obtains read lock
11/27/21 14:00:21: parent releases read lock
11/27/21 14:00:23: second child releases read lock
11/27/21 14:00:23: first child obtains write lock
11/27/21 14:00:25: first child releases write lock
Copy the code

To make it easier to see how the program is running, we give a sequence diagram (this is one of the typical sequences considering CPU scheduling, but it does not prevent us from analyzing read/write lock characteristics) :

  • 1 to 2: The main thread calls lock_shared to obtain the read lock. The main thread succeeds in obtaining the read lock because no other thread occupies the read lock.
  • 3~5: The main thread creates two child threads, thread1 and thread2, respectively, and sleeps for 5 seconds after the main thread succeeds in creating the child thread.
  • 6, 8: After thread1 has slept for 1 second, the rwlock function of thread1 is blocked because the main thread holds the read lock. The w_wait of the rwlock is 1.
  • 7, 9, 10, 11: The r_active of thread2 is 2, the r_active of thread2 is 2, and the sleep of thread2 is 4 seconds later.
  • 12~13: the main thread wakes up from sleep 5 seconds later and calls unlock_shared to release the read lock. R_active is reduced by 1.
  • 14 ~ 15: R_active = 0; w_wait = 1; w_wait = 1; w_wait = 1; w_wait = 1; This is because the thread1 thread blocks on step 8, and the write condition variable is told to wake up the thread1 thread.
  • 16 to 19: the thread1 thread returns from the wait for the write condition variable, checks that no other thread is holding the write lock, and holds the write lock successfully. The w_active of the rwlock is 1. A thread1 thread sleeps for 2 seconds and calls UNLOCK to release the write lock. In this case, unlock checks first to see if there is a reader waiting, and then checks again to see if there is a writer waiting.

As you can see, our current implementation of the Shared_mutex class is a reader-first policy.

The shared_mutex writer is preferred

Next, we show you how to rewrite the existing shared_mutex class to be writer-first. Complete engineering code: Github Gitee

1. Adjust the lock_shared logic

To implement writer-first, requests from new readers must be blocked when there are waiting writers (w_wait>0), not just when there are active writers (as we have already implemented).

void shared_mutex::lock_shared(a)
{
    std::unique_lock<std::mutex> lock(mutex);
    if (w_active || w_wait > 0) {			// <<<<<< Change logic to support write priority
        r_wait++;
        while (w_active || w_wait > 0) {	// <<<<<< Change logic to support write priority
            read.wait(lock);
        }
        r_wait--;
    }
    r_active++;
}
Copy the code
2. Adjust the try_lock_shared logic

Also, this function must be modified to implement writer-first, returning false when a writer thread is active, or when a writer thread is waiting.

bool shared_mutex::try_lock_shared(a)
{
    std::lock_guard<std::mutex> lock(mutex);
    if (w_active || w_wait > 0) {			// <<<<<< Change logic to support write priority
        return false;
    } else {
        r_active++;
        return true; }}Copy the code
3. Adjust the unlock logic

To implement writer-first, simply reverse the order of the two IF tests, waking up a waiting writer thread (if any) and then looking for a waiting reader thread.

void shared_mutex::unlock(a)
{
    std::unique_lock<std::mutex> lock(mutex);
    w_active = 0;
    if (w_wait > 0) {					// <<<<<< Change logic to support write priority
        write.notify_one(a); }else if (r_wait > 0) {			// <<<<<< Change logic to support write priority
        read.notify_all();
    }
}
Copy the code
At this point, we’ve transformed Shared_Mutex from a reader-first policy to a writer-first policy.

We can compile and run the previous example code again using the shared_mutex class of the writer-first policy to see the print-out:

11/27/21 14:00:46: parent has read lock
11/27/21 14:00:47: first child tries to obtain write lock
11/27/21 14:00:49: second child tries to obtain read lock
11/27/21 14:00:51: parent releases read lock
11/27/21 14:00:51: first child obtains write lock
11/27/21 14:00:53: first child releases write lock
11/27/21 14:00:53: second child obtains read lock
11/27/21 14:00:57: second child releases read lock
Copy the code

Did you notice anything different? As usual, we give the sequence diagram:

  • 1 to 2: The main thread calls lock_shared to obtain the read lock. The main thread succeeds in obtaining the read lock because no other thread occupies the read lock.
  • 3~5: The main thread creates two child threads, thread1 and thread2, respectively, and sleeps for 5 seconds after the main thread succeeds in creating the child thread.
  • 6, 8: After thread1 has slept for 1 second, the rwlock function of thread1 is blocked because the main thread holds the read lock. The w_wait of the rwlock is 1.
  • 7, 9: When the main thread is holding the read lock, the thread1 thread is waiting for the write operation (w_wait = 1), so the lock_shared function of the thread2 thread is also blocked. The r_wait of rwlock is 1.
  • 10 ~ 11: The main thread wakes up 5 seconds after sleep, and unlock_shared is called to release the read lock. R_active is reduced by 1, so r_active is 0.
  • 12, 13, 14, 15: The thread1 thread returns from the wait for the write condition variable, checks that no other thread is holding the write lock, and holds the write lock successfully. The w_active of the rwlock is 1. A thread1 thread sleeps for 2 seconds and calls UNLOCK to release the write lock. In this case, unlock checks first to see if there are any writers waiting, and then checks again to see if there are any readers waiting. Since the thread2 thread is waiting on the read condition variable (r_wait is 1), the read condition variable is told to wake up the thread2 thread.
  • 16 to 19: a thread2 thread returns from the wait of the read condition variable, checks that no other thread is holding the read lock, and holds the r_active+1 of the rwlock. The thread2 thread then sleeps for 2 seconds and calls unlock_shared to release the read lock.

As you can see, the shared_mutex class we overwrite is writer-first.

An aside:

1. What is reader first?

Even if the writer sends out a request to write, other readers are allowed to continue reading as long as there are still readers reading, until all readers have finished reading before writing

  • The next reader can go directly to the critical section, while the writer who is already waiting continues to wait until there are no more readers.
  • Readers are not mutually exclusive, writers are mutually exclusive, can only write one, can read multiple,
  • Readers and writers are mutually exclusive, and if a writer writes, no one can read
  • If the read access is very frequent, the writing process may not be able to access the file
2. What is writer First?

If a writer requests to write a file, those who have started reading the file can continue to read the file. However, if another reader requests to read the file, the file cannot be read and can be read only after all the writers have written the file

  • The writer thread takes precedence over the reader thread.
  • The reader thread queue should be blocked when a writer arrives.
  • The reader process should be blocked while a writer is writing or while blocking a queue until the reader process is released when all the writer processes have finished writing.
  • The reader process should be able to read the file simultaneously when there is no writer process.
3. Shared_mutex in C++17 is read or write first.

As far as I know, the C++17 standard does not define the shared_mutex implementation policy as read or write first. It is up to the compiler vendor, i.e., implementation-defined. This is much like POSIX’s read-write lock interface (pthread_rwlock_* related interface). I ran an experiment with two random versions of g++, and the results showed that:

  • In GCC version 9.3.0, shared_mutex is read first
  • In the implementation of GCC Version 10.2.0, shared_mutex is write-first
4. References
  • UNIX Network Programming Volume 2: Interprocess Communications, Second Edition
  • Programming With POSIX Threads
  • Readers who write problem (fair readers preferred writing is preferred, speaking, reading and writing) : www.cnblogs.com/wwqdata/p/1…