Рекурсивная реализация shared_mutex

Мне показалось, что я нуждаюсь в мьютексе читателей-писателей. С поддержкой C ++ 17 TR2, еще недоступной в нашем компиляторе, я решил реализовать std::shared_mutex , чтобы у нас был простой путь обновления к реализации STL, как только мы получим поддержку C ++ 17, вместо того, чтобы катавать собственный API.

Я помещаю все классы, предназначенные для реализации или дополнения функций STL в namespace xtd short для "eXtended sTD". Причина в том, что когда /если будет получена надлежащая поддержка, мы можем просто обменять xtd на std и запустить реализацию STL.

В дополнение к std::shared_mutex нам также нужен мьютекс Reader-Writer, который позволяет рекурсивную блокировку для авторов. Читатели всегда рекурсивны. Это реализовано как xtd::recursive_shared_mutex, этот класс не имеет эквивалента в стандартном C ++, но имеет тот же API, что и std::shared_mutex с некоторыми расширениями.

В приведенном ниже коде я использую пользовательский класс под названием xtd::fast_recursive_mutex, этот класс является полностью совместимым, заменяющим замену для std::recursive_mutex , но он использует CRITICAL_SECTION для окон для более быстрой блокировки, чем std::recursive_mutex (по крайней мере, на нашем компиляторе).

Мне интересен обзор правильности и любой грубой неэффективности классов.

XTD /shared_mutex.hpp

#pragma once
#include "fast_recursive_mutex.hpp"
#include <condition_variable>

namespace xtd {

    namespace detail {
        class shared_mutex_base {
        public:
            shared_mutex_base() = default;
            shared_mutex_base(const shared_mutex_base&) = delete;
            ~shared_mutex_base() = default;

            shared_mutex_base& operator = (const shared_mutex_base&) = delete;

        protected:
            using unique_lock = std::unique_lock < xtd::fast_recursive_mutex >;
            using scoped_lock = std::lock_guard < xtd::fast_recursive_mutex >;

            xtd::fast_recursive_mutex m_mutex;
            std::condition_variable_any m_exclusive_release;
            std::condition_variable_any m_shared_release;
            unsigned m_state = 0;

            void do_exclusive_lock(unique_lock& lk);
            bool do_exclusive_trylock(unique_lock& lk);
            void do_lock_shared(unique_lock& lk);
            bool do_try_lock_shared(unique_lock& lk);
            void do_unlock_shared(scoped_lock& lk);

            void take_exclusive_lock();
            bool someone_has_exclusive_lock() const;
            bool no_one_has_any_lock() const;
            unsigned number_of_readers() const;
            bool maximal_number_of_readers_reached() const;
            void clear_lock_status();
            void increment_readers();
            void decrement_readers();

            static const unsigned m_write_entered = 1U << (sizeof(unsigned)*CHAR_BIT - 1);
            static const unsigned m_num_readers = ~m_write_entered;
        };
    }

    /// <summary> A shared_mutex implemented to C++17 STL specification.
    /// 
    /// This is a Readers-Writer mutex with writer priority. Optional native_handle_type and
    /// native_handle members are not implemented.
    /// 
    /// For detailed documentation, see: http://en.cppreference.com/w/cpp/thread/shared_mutex. </summary>
    class shared_mutex : public detail::shared_mutex_base {
    public:
        shared_mutex() = default;
        shared_mutex(const shared_mutex&) = delete;
        ~shared_mutex() = default;

        shared_mutex& operator = (const shared_mutex&) = delete;

        /// <summary> Obtains an exclusive lock of this mutex. </summary>
        void lock();

        /// <summary> Attempts to exclusively lock this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock();

        /// <summary> Unlocks the exclusive lock on this mutex. </summary>
        void unlock();

        /// <summary> Obtains a shared lock on this mutex. Other threads may also hold a shared lock simultaneously. </summary>
        void lock_shared();

        /// <summary> Attempts to obtain a shared lock for this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock_shared();

        /// <summary> Unlocks the shared lock on this mutex. </summary>
        void unlock_shared();
    };

    /// <summary> This is a non-standard class which is essentially the same as `shared_mutex` but
    /// it allows a thread to recursively obtain write locks as long as the unlock count matches
    /// the lock-count. </summary>
    class recursive_shared_mutex : public detail::shared_mutex_base {
    public:
        recursive_shared_mutex() = default;
        recursive_shared_mutex(const recursive_shared_mutex&) = delete;
        ~recursive_shared_mutex() = default;

        recursive_shared_mutex& operator = (const recursive_shared_mutex&) = delete;

        /// <summary> Obtains an exclusive lock of this mutex. For recursive calls will always obtain the
        /// lock. </summary>
        void lock();

        /// <summary> Attempts to exclusively lock this mutex. For recursive calls will always obtain the
        /// lock. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock();

        /// <summary> Unlocks the exclusive lock on this mutex. </summary>
        void unlock();

        /// <summary> Obtains a shared lock on this mutex. Other threads may also hold a shared lock simultaneously. </summary>
        void lock_shared();

        /// <summary> Attempts to obtain a shared lock for this mutex. </summary>
        /// <returns> true if it the lock was obtained, false otherwise. </returns>
        bool try_lock_shared();

        /// <summary> Unlocks the shared lock on this mutex. </summary>
        void unlock_shared();

        /// <summary> Number recursive write locks. </summary>
        /// <returns> The total number of write locks. </returns>
        int num_write_locks();

        /// <summary> Query if this object is exclusively locked by me. </summary>
        /// <returns> true if locked by me, false if not. </returns>
        bool is_locked_by_me();

    private:
        std::thread::id m_write_thread;
        int m_write_recurses = 0;
    };
}

shared_mutex.cpp

#include "pch/pch.hpp"
#include "xtd/shared_mutex.hpp"

#include <thread>

namespace xtd {

    // ------------------------------------------------------------------------
    // class: shared_mutex_base
    // ------------------------------------------------------------------------
    namespace detail {

        void shared_mutex_base::do_exclusive_lock(unique_lock &lk){
            while (someone_has_exclusive_lock()) {
                m_exclusive_release.wait(lk);
            }

            take_exclusive_lock(); // We hold the mutex, there is no race here.

            while (number_of_readers() > 0) {
                m_shared_release.wait(lk);
            }
        }

        bool shared_mutex_base::do_exclusive_trylock(unique_lock &lk){
            if (lk.owns_lock() && no_one_has_any_lock()) {
                take_exclusive_lock();
                return true;
            }
            return false;
        }

        void shared_mutex_base::do_lock_shared(unique_lock& lk) {
            while (someone_has_exclusive_lock() || maximal_number_of_readers_reached()) {
                m_exclusive_release.wait(lk);
            }
            increment_readers();
        }

        bool shared_mutex_base::do_try_lock_shared(unique_lock& lk) {
            if (lk.owns_lock() && !someone_has_exclusive_lock() &&
                !maximal_number_of_readers_reached()) {
                increment_readers();
                return true;
            }
            return false;
        }

        void shared_mutex_base::do_unlock_shared(scoped_lock& lk) {
            decrement_readers();

            if (someone_has_exclusive_lock()) { // Some one is waiting for us to unlock...
                if (number_of_readers() == 0) {
                    // We were the last one they were waiting for, release one thread waiting
                    // for
                    // all shared locks to clear.
                    m_shared_release.notify_one();
                }
            }
            else {
                // Nobody is waiting for shared locks to clear, if we were at the max
                // capacity,
                // release one thread waiting to obtain a shared lock in lock_shared().
                if (number_of_readers() == m_num_readers - 1)
                    m_exclusive_release.notify_one();
            }
        }

        void shared_mutex_base::take_exclusive_lock() { m_state |= m_write_entered; }

        bool shared_mutex_base::someone_has_exclusive_lock() const {
            return (m_state & m_write_entered) != 0;
        }

        bool shared_mutex_base::no_one_has_any_lock() const { return m_state != 0; }

        unsigned shared_mutex_base::number_of_readers() const {
            return m_state & m_num_readers;
        }

        bool shared_mutex_base::maximal_number_of_readers_reached() const {
            return number_of_readers() == m_num_readers;
        }

        void shared_mutex_base::clear_lock_status() { m_state = 0; }

        void shared_mutex_base::increment_readers() {
            unsigned num_readers = number_of_readers() + 1;
            m_state &= ~m_num_readers;
            m_state |= num_readers;
        }

        void shared_mutex_base::decrement_readers() {
            unsigned num_readers = number_of_readers() - 1;
            m_state &= ~m_num_readers;
            m_state |= num_readers;
        }
    }

    // ------------------------------------------------------------------------
    // class: shared_mutex
    // ------------------------------------------------------------------------
    static_assert(std::is_standard_layout<shared_mutex>::value,
                  "Shared mutex must be standard layout");

    void shared_mutex::lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_exclusive_lock(lk);
    }

    bool shared_mutex::try_lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_exclusive_trylock(lk);
    }

    void shared_mutex::unlock() {
        {
            std::lock_guard<xtd::fast_recursive_mutex> lg(m_mutex);
            // We released an exclusive lock, no one else has a lock.
            clear_lock_status();
        }
        m_exclusive_release.notify_all();
    }

    void shared_mutex::lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_lock_shared(lk);
    }

    bool shared_mutex::try_lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_try_lock_shared(lk);
    }

    void shared_mutex::unlock_shared() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        do_unlock_shared(_);
    }

    // ------------------------------------------------------------------------
    // class: recursive_shared_mutex
    // ------------------------------------------------------------------------
    void recursive_shared_mutex::lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        if (m_write_recurses == 0) {
            do_exclusive_lock(lk);
        }
        else {
            if (m_write_thread == std::this_thread::get_id()) {
                if (m_write_recurses ==
                    std::numeric_limits<decltype(m_write_recurses)>::max()) {
                    throw std::system_error(
                        EOVERFLOW, std::system_category(),
                        "Too many recursions in recursive_shared_mutex!");
                }
            }
            else {
                // Different thread trying to get a lock.
                do_exclusive_lock(lk);
                assert(m_write_recurses == 0);
            }
        }
        m_write_recurses++;
        m_write_thread = std::this_thread::get_id();
    }

    bool recursive_shared_mutex::try_lock() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        if ((lk.owns_lock() && m_write_recurses > 0 && m_write_thread == std::this_thread::get_id()) ||
            do_exclusive_trylock(lk)) {
            m_write_recurses++;
            m_write_thread = std::this_thread::get_id();
            return true;
        }
        return false;
    }

    void recursive_shared_mutex::unlock() {
        bool notify_them = false;
        {
            std::lock_guard<xtd::fast_recursive_mutex> lg(m_mutex);
            if (m_write_recurses == 0) {
                throw std::system_error(ENOLCK, std::system_category(),
                                        "Unlocking a unlocked mutex!");
            }
            m_write_recurses--;
            if (m_write_recurses == 0) {
                // We released an exclusive lock, no one else has a lock.
                clear_lock_status();
                notify_them = true;
            }
        }
        if (notify_them) {
            m_exclusive_release.notify_all();
        }
    }

    void recursive_shared_mutex::lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex);
        do_lock_shared(lk);
    }

    bool recursive_shared_mutex::try_lock_shared() {
        std::unique_lock<xtd::fast_recursive_mutex> lk(m_mutex, std::try_to_lock);
        return do_try_lock_shared(lk);
    }

    void recursive_shared_mutex::unlock_shared() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return do_unlock_shared(_);
    }

    int recursive_shared_mutex::num_write_locks() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return m_write_recurses;
    }

    bool recursive_shared_mutex::is_locked_by_me() {
        std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);
        return m_write_recurses > 0 && m_write_thread == std::this_thread::get_id();
    }
}

Реализация основана на эталонной реализации в этом рабочем документе .

31 голос | спросил Emily L. 6 J000000Monday15 2015, 19:06:11

1 ответ


12

Легкий материал, который вы уже знаете.

Вероятно, часть ваших автоматизированных скриптов для создания новых файлов.

#pragma once

Но для новых желающих я хотел бы указать, что более стандартные включенные охранники совместимы везде.

Не ленитесь

         std::lock_guard<xtd::fast_recursive_mutex> _(m_mutex);

Хотя это не является технически неправильным как идентификатор (_). Сколько людей, как вы думаете, хорошо знают правила о них? Также вы используете lk почти везде, зачем менять стиль в конце?

Комментарии, основанные на мнениях

Когда у вас есть стандартный конструктор /деструктор, но вы отключите копирование, я бы тоже их группировал. Я бы поставил конструктор /деструктор вместе, а затем операторы копирования вместе:

shared_mutex() = default;
shared_mutex(const shared_mutex&) = delete;
~shared_mutex() = default;

shared_mutex& operator = (const shared_mutex&) = delete;

Я бы сделал это:

shared_mutex() = default;
~shared_mutex() = default;

// Disable copy semantics.
shared_mutex(const shared_mutex&) = delete;
shared_mutex& operator = (const shared_mutex&) = delete;

Не нравится ваше состояние

Вы объединяете две части состояния в одну переменную m_state. Это делает чтение кода более сложным. Оптимизируйте для удобства чтения или добавьте еще несколько комментариев вокруг кода:

Мне потребовалось несколько минут, чтобы понять, что вы здесь делаете. Хороший комментарий был бы приятным.

            static const unsigned m_write_entered = 1U << (sizeof(unsigned)*CHAR_BIT - 1);
            static const unsigned m_num_readers = ~m_write_entered;
                            //    ^^^^^^^^^^^^^  don't like that name it needs "max" in it.

В основном, вы используете эти константы для объединения состояния в m_state, где верхний бит используется для указания исключительной блокировки, а все остальные биты используются для подсчета количества общих блокировок.

Ошибка

bool shared_mutex_base::no_one_has_any_lock() const { return m_state != 0; }
                                                                    ^^^^ Should that not be `==`?

Проблема

Вы используете m_exclusive_release для потоков, ожидающих эксклюзивной блокировки в do_exclusive_lock() и в качестве списка переполнений для потоков, пытающихся получить общую блокировку в do_lock_shared(). В зависимости от вашей семантики приоритет исключительных блокировок это может работать не так, как вы планировали.

Я ожидаю, что потоки ожидают, что эксклюзивные блокировки получат приоритет над теми, кто ждет общих блокировок; но любой ожидающий поток имеет равную возможность захватить блокировку при освобождении текущей эксклюзивной блокировки.

Таким образом, несколько, но обязательно все, потоки, ожидающие общих блокировок, могут получить блокировки до того, как поток, требующий эксклюзивной блокировки, получит возможность захватить блокировку. Таким образом, исключительная блокировка может потребоваться снова подождать.

Senario:

  • У нас есть много потоков с общими замками и достигли максимума.
  • Мы добавляем одну (или пару) более shared_locks.
    Они помещаются в очередь на m_exclusive_release.
  • Теперь у нас есть поток, который хочет эксклюзивный замок и получает его.
    Теперь ожидаем m_shared_release для всех разделяемых блокировок, которые будут выпущены.
  • Теперь у нас есть поток, который хочет эксклюзивную блокировку (но она уже сделана).
    Таким образом, этот поток помещается в список m_exclusive_release (с одним или несколькими потоками, ожидающими общей блокировки).

По мере того, как потоки с разделяемыми замками завершают свою работу, они вызывают do_unlock_shared() до тех пор, пока не останется больше разделяемых блокировок. Это вызывает вызов m_shared_release.notify_one(); и первый поток с исключительной блокировкой (ожиданиеm_shared_release) освобождается и работает нормально, пока не освободит блокировку с вызовом unlock(), который вызывает m_exclusive_release.notify_all();. Это освобождает все потоки, пытающиеся получить shared_lock и , все потоки пытаются получить эксклюзивную блокировку. Вы не можете определить, какой поток сначала получит блокировку, поэтому он случайен, если эксклюзивная блокировка находится рядом с блокировкой.

Из-за этого исключительные блокировки могут быть истощены из-за ресурсов, поскольку им, возможно, придется ждать, пока общие блокировки будут выпущены дважды, прежде чем они получат возможность запускать.

Я уверен, что вы никогда не столкнетесь с тупиковой ситуацией или фактически не исключите блокировку, но я не вижу в этом благоприятного поведения.

Дизайн

Будет ли разделяемая блокировка работать не так, как на shared_mutex, так и на recursive_shared_mutex? Не могли бы вы перевести этот код в общий базовый класс?

ответил Martin York 29 ThuEurope/Moscow2016-12-29T02:39:18+03:00Europe/Moscow12bEurope/MoscowThu, 29 Dec 2016 02:39:18 +0300 2016, 02:39:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132