Как сделать блокировку с несколькими чтениями / одиночной записью из более простых примитивов синхронизации?

Мы обнаружили, что у нас есть несколько точек в нашем коде, где параллельные чтения данных, защищенных мьютексом, довольно распространены, в то время как записи встречаются редко. Наши измерения, по-видимому, говорят о том, что использование простого мьютекса серьезно препятствует производительности кода, считывающего эти данные. Итак, нам нужен многоточечный / однозадачный мьютекс. Я знаю, что это может быть построено поверх простых примитивов, но прежде чем я попытаюсь это сделать, я скорее попрошу существующие знания:

Что такое одобренный способ создания блокировки с несколькими чтениями / одиночной записью из простых примитивов синхронизации?

У меня есть идея, как это сделать, но я предпочел бы, чтобы ответы были непредвзятыми из-за того, что я (возможно, ошибочно) придумал. (Примечание. То, что я ожидаю, объясняет, как это сделать, возможно, в псевдокоде, а не в полноценной реализации. Я, конечно, могу написать код сам.)

Предостережения:

  • Это должно иметь разумную производительность. (То, что я имею в виду, потребует двух операций блокировки / разблокировки для каждого доступа. Теперь это может быть недостаточно, но многие из них вместо этого кажутся необоснованными.)

  • Обычно чтение более многочисленное, но записи важнее и чувствительны к производительности, чем чтение. Читатели не должны голодать писателям.

  • Мы застряли на довольно старой встроенной платформе (проприетарный вариант VxWorks 5.5) с довольно старым компилятором (GCC 4.1.2) и повышаем уровень 1.52 – за исключением большинства частей boost, основанных на POSIX, потому что POSIX не полностью реализован на этой платформе. Доступные в принципе блокирующие примитивы представляют собой несколько семафоров (двоичные, подсчетные и т. Д.), Поверх которых мы уже создали мьютексы, переменные условий и мониторы.

  • Это IA32, одноядерный.

Кажется, что в качестве примитивов синхронизации у вас есть только 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. 

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

 class RWLock { public: RWLock() : shared() , readerQ(), writerQ() , active_readers(0), waiting_writers(0), active_writers(0) {} void ReadLock() { std::unique_lock lk(shared); while( waiting_writers != 0 ) readerQ.wait(lk); ++active_readers; lk.unlock(); } void ReadUnlock() { std::unique_lock lk(shared); --active_readers; lk.unlock(); writerQ.notify_one(); } void WriteLock() { std::unique_lock lk(shared); ++waiting_writers; while( active_readers != 0 || active_writers != 0 ) writerQ.wait(lk); ++active_writers; lk.unlock(); } void WriteUnlock() { std::unique_lock 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; }; 

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

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 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 lk(mut_, try_to_lock); if (lk.owns_lock() && state_ == 0) { state_ = write_entered_; return true; } return false; } void shared_mutex::unlock() { { lock_guard _(mut_); state_ = 0; } gate1_.notify_all(); } // Shared ownership void shared_mutex::lock_shared() { unique_lock 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 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 _(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_ даже если у читателей есть право собственности. Но как только прошлые gate1_ , у писателя все еще нет собственности. Сначала он должен пройти мимо gate2_ . Писатель не может пройти мимо gate2_ до gate2_ пор, пока все читатели с собственностью не откажутся от него. Напомним, что новые читатели не могут пройти мимо gate1_ пока писатель ждет в gate2_ . И ни один новый писатель не может пройти мимо gate1_ пока писатель ждет в gate2_ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Один алгоритм для этого, основанный на семафорах и мьютексах, описан в « Параллельном управлении с читателями и писателями» ; PJ Courtois, F. Heymans и DL Parnas; Исследовательская лаборатория MBLE; Брюссель, Бельгия .

Это упрощенный ответ, основанный на моих заголовках 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); } } }; 

Поведение

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

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

В конце streamов Write Lock – Reader и один stream для записи будут гоняться, чтобы узнать, какой из них начинается.

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

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

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

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

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

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

  • Можно ли использовать мьютекс в многопроцессорном случае в Linux / UNIX?
  • Подождите, пока флаг = true
  • C # версия синхронизированного ключевого слова java?
  • Различия между неявным, явным и текучим
  • Синхронизация IPC с общей памятью (без блокировки)
  • Убедитесь, что синхронизированные блокировки Java выполнены в порядке?
  • Пример / учебник Mutex?
  • Как сделать мой ArrayList streamобезопасным? Другой подход к проблеме в Java?
  • Почему не логично синхронизировать логику?
  • Коллекции. Синхронизированный список и синхронизация
  • Как работает блокировка?
  • Давайте будем гением компьютера.