Ответ 1

Кажется, что в качестве примитивов синхронизации у вас есть только mutex и condition_variable. поэтому я пишу здесь блокнот читателя, который голодает читателями. он использует один мьютекс, два условных_переменных и три целых числа.

readers - readers in the cv readerQ plus the reading reader
writers - writers in cv writerQ plus the writing writer
active_writers - the writer currently writing. can only be 1 or 0.

Это голодает читатели таким образом. Если есть несколько авторов, которые хотят писать, читатели никогда не получат возможность прочитать, пока все авторы не напишут. Это связано с тем, что более поздние читатели должны проверять переменную writers. В то же время переменная active_writers гарантирует, что за один раз может писать только один писатель.

class RWLock {
public:
    RWLock()
    : shared()
    , readerQ(), writerQ()
    , active_readers(0), waiting_writers(0), active_writers(0)
    {}

    void ReadLock() {
        std::unique_lock<std::mutex> lk(shared);
        while( waiting_writers != 0 )
            readerQ.wait(lk);
        ++active_readers;
        lk.unlock();
    }

    void ReadUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --active_readers;
        lk.unlock();
        writerQ.notify_one();
    }

    void WriteLock() {
        std::unique_lock<std::mutex> lk(shared);
        ++waiting_writers;
        while( active_readers != 0 || active_writers != 0 )
            writerQ.wait(lk);
        ++active_writers;
        lk.unlock();
    }

    void WriteUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --waiting_writers;
        --active_writers;
        if(waiting_writers > 0)
            writerQ.notify_one();
        else
            readerQ.notify_all();
        lk.unlock();
    }

private:
    std::mutex              shared;
    std::condition_variable readerQ;
    std::condition_variable writerQ;
    int                     active_readers;
    int                     waiting_writers;
    int                     active_writers;
};

Ответ 2

На первый взгляд я подумал, что признал этот ответ тем же алгоритмом, который представил Александр Терехов. Но после изучения я считаю, что он ошибочен. Два писателя могут одновременно подождать m_exclusive_cond. Когда один из этих авторов просыпается и получает эксклюзивный замок, он устанавливает exclusive_waiting_blocked = false на unlock, тем самым устанавливая мьютекс в непоследовательное состояние. После этого мьютекс, скорее всего, будет закрыт.

N2406, который сначала предложил std::shared_mutex, содержит частичную реализацию, которая повторяется ниже с обновленным синтаксисом.

class shared_mutex
{
    mutex    mut_;
    condition_variable gate1_;
    condition_variable gate2_;
    unsigned state_;

    static const unsigned write_entered_ = 1U << (sizeof(unsigned)*CHAR_BIT - 1);
    static const unsigned n_readers_ = ~write_entered_;

public:

    shared_mutex() : state_(0) {}

// Exclusive ownership

    void lock();
    bool try_lock();
    void unlock();

// Shared ownership

    void lock_shared();
    bool try_lock_shared();
    void unlock_shared();
};

// Exclusive ownership

void
shared_mutex::lock()
{
    unique_lock<mutex> lk(mut_);
    while (state_ & write_entered_)
        gate1_.wait(lk);
    state_ |= write_entered_;
    while (state_ & n_readers_)
        gate2_.wait(lk);
}

bool
shared_mutex::try_lock()
{
    unique_lock<mutex> lk(mut_, try_to_lock);
    if (lk.owns_lock() && state_ == 0)
    {
        state_ = write_entered_;
        return true;
    }
    return false;
}

void
shared_mutex::unlock()
{
    {
    lock_guard<mutex> _(mut_);
    state_ = 0;
    }
    gate1_.notify_all();
}

// Shared ownership

void
shared_mutex::lock_shared()
{
    unique_lock<mutex> lk(mut_);
    while ((state_ & write_entered_) || (state_ & n_readers_) == n_readers_)
        gate1_.wait(lk);
    unsigned num_readers = (state_ & n_readers_) + 1;
    state_ &= ~n_readers_;
    state_ |= num_readers;
}

bool
shared_mutex::try_lock_shared()
{
    unique_lock<mutex> lk(mut_, try_to_lock);
    unsigned num_readers = state_ & n_readers_;
    if (lk.owns_lock() && !(state_ & write_entered_) && num_readers != n_readers_)
    {
        ++num_readers;
        state_ &= ~n_readers_;
        state_ |= num_readers;
        return true;
    }
    return false;
}

void
shared_mutex::unlock_shared()
{
    lock_guard<mutex> _(mut_);
    unsigned num_readers = (state_ & n_readers_) - 1;
    state_ &= ~n_readers_;
    state_ |= num_readers;
    if (state_ & write_entered_)
    {
        if (num_readers == 0)
            gate2_.notify_one();
    }
    else
    {
        if (num_readers == n_readers_ - 1)
            gate1_.notify_one();
    }
}

Алгоритм получен из старой публикации группы новостей Александра Терехова. Он не голодает ни читатели, ни писатели.

Есть два "ворот", gate1_ и gate2_. Читатели и писатели должны пройти gate1_ и могут быть заблокированы при попытке сделать это. После того, как читатель прошел мимо gate1_, он заблокировал мьютекс. Читатели могут пройти мимо gate1_, пока не будет максимального количества читателей с правом собственности, и до тех пор, пока писатель не получил прошлое gate1_.

Только один писатель за один раз может пройти мимо gate1_. И писатель может пройти мимо gate1_, даже если у читателей есть право собственности. Но как только прошлое gate1_, у писателя все еще нет собственности. Сначала он должен пройти мимо gate2_. Писатель не может пройти мимо gate2_, пока все читатели с собственностью не откажутся от него. Напомним, что новые читатели не могут пройти мимо gate1_, пока писатель ждет в gate2_. И ни один новый писатель не может пройти мимо gate1_, пока писатель ждет в gate2_.

Характер, который как читатели, так и писатели блокируются в gate1_ с (почти) идентичными требованиями, наложенными на то, чтобы пройти мимо него, делает этот алгоритм справедливым как для читателей, так и для писателей, и не голодает.

"состояние" мьютекса намеренно хранится в одном слове, чтобы предположить, что частичное использование атомистики (как оптимизация) для определенных изменений состояния является возможностью (т.е. для неуправляемого "быстрого пути" ). Однако эта оптимизация здесь не показана. Например, если поток писателя мог бы атомически изменить state_ от 0 до write_entered, тогда он получает блокировку без блокировки или даже блокировки/разблокировки mut_. И unlock() может быть реализовано с помощью атомного хранилища. И т.д. Эти оптимизации не показаны здесь, потому что они намного сложнее реализовать правильно, чем это простое описание заставляет его звучать.

Ответ 3

Параллельные чтения данных, защищенных мьютексом, довольно распространены, в то время как записи редко встречаются

Это звучит как идеальный сценарий для User-space RCU:

URCU похож на своего аналога Linux-ядра, обеспечивая замену блокировки считывателя-записи, среди других применений. Это сходство продолжается, когда считыватели не синхронизируются напрямую с обновлениями RCU, что делает коды кода чтения RCU чрезвычайно быстрыми, в то же время позволяя читателям RCU делать полезный вперед прогресс даже при одновременном запуске с установками RCU - и наоборот.

Ответ 4

Как всегда лучшее решение будет зависеть от деталей. Блокировка от записи-записи может быть тем, что вы ищете, но другие подходы, такие как чтение-копирование-обновление, как было предложено выше, могут быть решение - хотя на старой встроенной платформе может возникнуть проблема использования дополнительной памяти. С помощью редких записей я часто организую работу с помощью системы задач, так что записи могут возникать только тогда, когда нет чтения из этой структуры данных, но это зависит от алгоритма.

Ответ 5

Есть несколько хороших трюков, которые вы можете сделать, чтобы помочь.

Во-первых, хорошая производительность. VxWorks отличается очень хорошим временем переключения контекста. Независимо от того, какое решение блокировки вы используете, скорее всего, это семафоры. Я бы не побоялся использовать семафоры (множественное число) для этого, они довольно хорошо оптимизированы в VxWorks, а быстрое время переключения контекста помогает имитировать ухудшение производительности при оценке многих состояний семафора и т.д.

Также я бы забыл использовать семафоры POSIX, которые просто будут накладываться поверх собственных семафоров VxWork. VxWorks предлагает собственные подсчеты, двоичные и мьютексы семафоров; используя тот, который подходит, делает все это немного быстрее. Иногда бинарные могут быть весьма полезными; вывешенный во много раз, никогда не превышать значение 1.

Во-вторых, пишет более важное значение, чем чтение. Когда у меня было такое требование в VxWorks и я использовал семафор для контроля доступа, я использовал приоритет задачи, чтобы указать, какая задача важнее и должен получить первый доступ к ресурсу. Это работает неплохо; буквально все в VxWorks - это задача (ну, поток), как и любая другая, включая все драйверы устройства и т.д.

VxWorks также разрешает инверсии приоритетов (то, что ненавидит Линус Торвальдс). Поэтому, если вы реализуете свою блокировку с помощью семафора (-ов), вы можете полагаться на планировщик ОС, чтобы переключать считыватели с более низким приоритетом, если они блокируют писателя с более высоким приоритетом. Это может привести к значительному упрощению кода, и вы также используете большую часть ОС.

Итак, потенциальное решение состоит в том, чтобы иметь один семафор VxWorks, который защищает ресурс, инициализированный значением, равным числу читателей. Каждый раз, когда читатель хочет прочитать, он принимает семафор (уменьшая счет на 1. Каждый раз, когда чтение выполняется, он помещает семафор, увеличивая счет на 1. Каждый раз, когда писатель хочет писать, он принимает семафор n (n = количество читателей) и отправляет его в n раз, когда это делается. Наконец, сделайте задачу писателя более приоритетной, чем любой из читателей, и полагайтесь на быстрое время переключения контекста и инверсию приоритета.

Помните, что вы программируете на ОС реального времени, а не на Linux. Взятие/публикация собственного семафора VxWorks не предполагает такой же объем времени выполнения, как и аналогичный акт для Linux, хотя даже Linux в наши дни очень хорош (я использую PREEMPT_RT в настоящее время). Планировщик VxWorks и все драйверы устройств могут полагаться на поведение. Вы даже можете сделать свой писатель самым высоким приоритетом во всей системе, если хотите, выше, чем все драйверы устройств!

Чтобы помочь вам, также подумайте, что это такое, что делает каждый из ваших потоков. VxWorks позволяет указать, что задача не использует FPU. Если вы используете собственные подпрограммы VxWorks TaskSpawn вместо pthread_create, тогда вы получите возможность указать это. Это означает, что если ваш поток/задача не выполняет математику с плавающей запятой, и вы так сказали в своем вызове TaskSpawn, время переключения контекста будет еще быстрее, потому что планировщик не потрудился сохранить/восстановить состояние FPU.

Это разумный шанс стать лучшим решением на платформе, на которой вы разрабатываете. Он играет в сильные стороны ОС (быстрые семафоры, быстрое время переключения контекста), не вводя дополнительный код для воссоздания альтернативного (и, возможно, более элегантного) решения, обычно встречающегося на других платформах.

В-третьих, застрял со старым GCC и старым Boost. В принципе, я не могу помочь, кроме предложений с низкой стоимостью, связанных с подключением WindRiver и обсуждением покупки обновления. Лично говоря, когда я программировал VxWorks, я использовал собственный API VxWork, а не POSIX. Хорошо, поэтому код не очень портативен, но он оказался быстрым; POSIX - это всего лишь слой поверх встроенного API, и это всегда будет замедлять работу.

Тем не менее, подсчеты POSIX и семафоры мьютексов очень похожи на родные подсчеты VxWork и семафоры мьютексов. Вероятно, это означает, что слой POSIX не очень толстый.

Общие замечания о программировании для VxWorks

ОтладкаЯ всегда стремился использовать инструменты разработки (Tornado) для Solaris. Это, безусловно, лучшая многопоточная среда отладки, с которой я когда-либо сталкивался. Зачем? Он позволяет запускать несколько сеансов отладки, по одному для каждого потока/задачи в системе. В результате вы получаете отладочное окно для каждого потока, и вы индивидуально и независимо отлаживаете каждый из них. Перейдите к операции блокировки, это окно отладки блокируется. Переместите фокус мыши в другое окно отладки, перейдите к операции, которая освободит блок и посмотрит, как первое окно завершит свой шаг.

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

По иронии судьбы версия Windows Tornado не позволяла вам это делать; один отвратительный одиночный отлаживающий окна для каждой системы, как и любая другая скучная старая среда разработки, такая как Visual Studio и т.д. Я никогда не видел, чтобы даже современные IDE приходили куда ближе, чем к Tornado на Solaris для многопоточной отладки.

HardDrives Если ваши читатели и писатели используют файлы на диске, подумайте, что VxWorks 5.5 довольно старый. Такие вещи, как NCQ, не будут поддерживаться. В этом случае мое предлагаемое решение (описанное выше) может быть лучше сделано с помощью одного семафора мьютекса, чтобы остановить несколько считывателей, сбивающих друг друга в их борьбе за чтение разных частей диска. Это зависит от того, что именно делают ваши читатели, но если они читают смежные данные из файла, это позволит избежать перетаскивания головки чтения/записи на поверхность диска (очень медленно).

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

Ответ 6

Один алгоритм для этого, основанный на семафорах и мьютексах, описан в Параллельное управление с помощью Readers and Writers; P.J. Courtois, F. Heymans и D.L. Парнас; Исследовательская лаборатория MBLE; Брюссель, Бельгия.

Ответ 7

Это упрощенный ответ, основанный на моих заголовках Boost (я бы назвал Boost одобренным способом). Он требует только переменных условий и мьютексов. Я переписал его с помощью примитивов Windows, потому что считаю их описательными и очень простыми, но рассматриваю это как псевдокод.

Это очень простое решение, которое не поддерживает такие функции, как обновление mutex или try_lock(). Я могу добавить их, если захочу. Я также извлек некоторые изгибы, такие как прерывание прерываний, которые не являются абсолютно необходимыми.

Кроме того, стоит проверить boost\thread\pthread\shared_mutex.hpp (основываясь на этом). Он читается человеком.

class SharedMutex {
  CRITICAL_SECTION m_state_mutex;
  CONDITION_VARIABLE m_shared_cond;
  CONDITION_VARIABLE m_exclusive_cond;

  size_t shared_count;
  bool exclusive;

  // This causes write blocks to prevent further read blocks
  bool exclusive_wait_blocked;

  SharedMutex() : shared_count(0), exclusive(false)
  {
    InitializeConditionVariable (m_shared_cond);
    InitializeConditionVariable (m_exclusive_cond);
    InitializeCriticalSection (m_state_mutex);
  }

  ~SharedMutex() 
  {
    DeleteCriticalSection (&m_state_mutex);
    DeleteConditionVariable (&m_exclusive_cond);
    DeleteConditionVariable (&m_shared_cond);
  }

  // Write lock
  void lock(void)
  {
    EnterCriticalSection (&m_state_mutex);
    while (shared_count > 0 || exclusive)
    {
      exclusive_waiting_blocked = true;
      SleepConditionVariableCS (&m_exclusive_cond, &m_state_mutex, INFINITE)
    }
    // This thread now 'owns' the mutex
    exclusive = true;

    LeaveCriticalSection (&m_state_mutex);
  }

  void unlock(void)
  {
    EnterCriticalSection (&m_state_mutex);
    exclusive = false;
    exclusive_waiting_blocked = false;
    LeaveCriticalSection (&m_state_mutex);
    WakeConditionVariable (&m_exclusive_cond);
    WakeAllConditionVariable (&m_shared_cond);
  }

  // Read lock
  void lock_shared(void)
  {
    EnterCriticalSection (&m_state_mutex);
    while (exclusive || exclusive_waiting_blocked)
    {
      SleepConditionVariableCS (&m_shared_cond, m_state_mutex, INFINITE);
    }
    ++shared_count;
    LeaveCriticalSection (&m_state_mutex);
  }

  void unlock_shared(void)
  {
    EnterCriticalSection (&m_state_mutex);
    --shared_count;

    if (shared_count == 0)
    {
      exclusive_waiting_blocked = false;
      LeaveCriticalSection (&m_state_mutex);
      WakeConditionVariable (&m_exclusive_cond);
      WakeAllConditionVariable (&m_shared_cond);
    }
    else
    {
      LeaveCriticalSection (&m_state_mutex);
    }
  }
};

Поведение

Хорошо, есть некоторая путаница в поведении этого алгоритма, так вот как это работает.

Во время блокировки записи - блокируются как читатели, так и писатели.

В конце блокировки записи - потоки чтения и один поток писем будут гоняться, чтобы узнать, какой из них начинается.

Во время блокировки чтения. Писатели заблокированы. Читатели также блокируются, если и только если Writer заблокирован.

При выпуске финальной строки Read Lock - нити Reader и один поток записи будут гоняться, чтобы узнать, какой из них начинается.

Это может привести к тому, что читатели начнут голодать, если процессор часто переключается на поток m_shared_cond до m_exclusive_cond во время уведомления, но я подозреваю, что эта проблема является теоретической и нецелесообразной, поскольку алгоритм Boost.

Ответ 8

Теперь, когда Microsoft открыла исходный код .NET, вы можете посмотреть их ReaderWRiterLockSlim.

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

Microsoft потратила довольно много времени на повышение производительности своих механизмов блокировки, поэтому это может быть хорошей отправной точкой.