Как сделать блокировку множественного чтения / однократной записи из более простых примитивов синхронизации?
Мы обнаружили, что в нашем коде есть несколько мест, где одновременное чтение данных, защищенных мьютексом, довольно распространено, в то время как записи редки. Наши измерения показывают, что использование простого мьютекса серьезно снижает производительность кода, считывающего эти данные. Так что нам нужен мьютекс с несколькими операциями чтения / записи. Я знаю, что это может быть построено поверх простых примитивов, но прежде чем попробовать себя в этом, я бы скорее попросил существующие знания:
Каков одобренный способ создать блокировку множественного чтения / однократной записи из более простых примитивов синхронизации?
У меня есть идея, как это сделать, но я бы предпочел, чтобы ответы были непредвзятыми из-за того, что я (вероятно, ошибочно) придумал. (Примечание: я ожидаю объяснения, как это сделать, вероятно, в псевдокоде, а не полноценной реализации. Я, конечно, могу написать код сам.)
Предостережения:
-
Это должно иметь разумную производительность. (То, что я имею в виду, потребовало бы двух операций блокировки / разблокировки для каждого доступа. Теперь это может быть недостаточно, но вместо этого необходимость во многих из них представляется необоснованной.)
-
Обычно чтения являются более многочисленными, но записи более важны и чувствительны к производительности, чем операции чтения. Читатели не должны голодать писателей.
-
Мы застряли на довольно старой встраиваемой платформе (частный вариант VxWorks 5.5) с довольно старым компилятором (GCC 4.1.2) и boost 1.52 — за исключением большинства частей boost, полагающихся на POSIX, потому что POSIX не полностью реализован на этой платформе. Доступные в основном блокирующие примитивы — это несколько видов семафоров (двоичные, счетные и т. Д.), Поверх которых мы уже создали мьютексы, переменные условий и мониторы.
-
Это IA32, одноядерный.
Решение
Кажется, у вас есть только mutex и condition_variable в качестве примитивов синхронизации. поэтому, я пишу здесь замок читателя-писателя, который голодает читателей. он использует один мьютекс, два conditional_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;
};
Другие решения
На первый взгляд мне показалось, что я узнал этот ответ как тот же алгоритм, который ввел Александр Терехов. Но изучив его, я считаю, что он несовершенен. Два автора могут одновременно ждать 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() может быть реализовано с помощью атомарного магазина. И т.д. Эти оптимизации здесь не показаны, потому что их гораздо сложнее правильно реализовать, чем это простое описание.
Одновременное чтение данных, защищенных мьютексом, встречается довольно часто, в то время как запись выполняется редко
Это звучит как идеальный сценарий для Пользовательское пространство 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 и всех драйверов устройств можно положиться. Вы даже можете сделать задачу записи наиболее приоритетной во всей системе, если хотите, даже выше, чем у всех драйверов устройств!
Чтобы помочь себе в этом, также подумайте, чем занимается каждый из ваших потоков. VxWorks позволяет вам указать, что задача использует / не использует FPU. Если вы используете родные подпрограммы VxWorks TaskSpawn вместо pthread_create, то у вас есть возможность указать это. Это означает, что если ваш поток / задача не выполняет математических операций с плавающей запятой, и вы сказали об этом при вызове TaskSpawn, время переключения контекста будет еще быстрее, поскольку планировщик не потрудится сохранить / восстановить состояние FPU.
Это реальная возможность стать лучшим решением для платформы, на которой вы разрабатываете. Он играет на сильных сторонах ОС (быстрые семафоры, быстрое переключение контекста) без добавления дополнительного кода для воссоздания альтернативного (и, возможно, более элегантного) решения, обычно встречающегося на других платформах.
В третьих, застрял со старым GCC и старым Boost. По сути, я не могу помочь в этом, кроме предложений о низкой стоимости звонка WindRiver и обсуждения покупки обновления. Лично, когда я программировал для VxWorks, я использовал собственный API VxWork, а не POSIX. Итак, код не был очень переносимым, но он оказался быстрым; В любом случае POSIX — это просто слой поверх нативного API, и это всегда будет тормозить процесс.
При этом семафоры подсчета и мьютекса POSIX очень похожи на семафоры подсчета и мьютекса в VxWork. Это, вероятно, означает, что слой POSIX не очень толстый.
Общие замечания о программировании для VxWorks
отладка Я всегда стремился использовать инструменты разработки (Tornado), доступные для Solaris. Это, безусловно, лучшая многопоточная среда отладки, с которой я когда-либо сталкивался. Зачем? Он позволяет запускать несколько сеансов отладки, по одному для каждого потока / задачи в системе. В результате вы получаете окно отладки для каждого потока, и вы индивидуально и независимо отлаживаете каждый из них. Перешагните через операцию блокировки, это окно отладки будет заблокировано. Переместите фокус мыши в другое окно отладки, перешагните через операцию, которая освободит блок, и наблюдайте, как первое окно завершает свой шаг.
В итоге вы получаете много окон отладки, но это лучший способ отладки многопоточных программ. Это очень легко писать действительно сложные вещи и видеть проблемы. Вы можете легко исследовать различные динамические взаимодействия в вашем приложении, потому что у вас был простой и мощный контроль над тем, что каждый поток делает в любое время.
По иронии судьбы версия Tornado для Windows не позволила вам сделать это; одно жалкое одиночное окно отладки на систему, как и в любой другой скучной старой IDE, такой как Visual Studio и т. д. Я никогда не видел, чтобы даже современные IDE были настолько близки к тому, чтобы быть такими же хорошими, как Tornado в Solaris для многопоточной отладки.
Жесткие диски Если ваши читатели и писатели используют файлы на диске, учтите, что VxWorks 5.5 довольно старый. Такие вещи, как NCQ, не будут поддерживаться. В этом случае мое предложенное решение (обрисованное в общих чертах выше) может быть лучше выполнено с одним семафором мьютекса, чтобы не допустить, чтобы несколько читателей споткнулись друг о друга в своей борьбе за чтение разных частей диска. Это зависит от того, что именно делают ваши читатели, но если они читают непрерывные данные из файла, это позволит избежать смещения головки чтения / записи туда-сюда по поверхности диска (очень медленно).
В моем случае я использовал этот трюк для формирования трафика через сетевой интерфейс; каждая задача отправляла данные разного рода, и приоритет задачи отражал приоритет данных в сети. Это было очень элегантно, ни одно сообщение не было фрагментировано, но важные сообщения получили львиную долю доступной пропускной способности.
Как всегда, лучшее решение будет зависеть от деталей. Спин-блокировка чтения-записи может быть тем, что вы ищете, но другие подходы, такие как чтение-копирование-обновление, как предложено выше, могут быть решением — хотя на старой встроенной платформе может быть проблема с использованием дополнительной памяти. При редких записях я часто организую работу, используя систему задач, так что записи могут происходить только тогда, когда нет чтений из этой структуры данных, но это зависит от алгоритма.
Один алгоритм для этого, основанный на семафорах и мьютексах, описан в Параллельное управление с читателями и писателями; П.Дж. Куртуа, Ф.Хейманс и Д.Л. Парнас; Исследовательская лаборатория 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);
}
}
};
Хорошо, есть некоторая путаница в поведении этого алгоритма, так что вот как он работает.
Во время блокировки записи — И читатели, и писатели заблокированы.
В конце блокировки записи — Читатель темы и один автор темы будет гонка чтобы увидеть, какой из них начинается.
Во время блокировки чтения — Писатели заблокированы. Читатели также заблокированы если и только если Писатель заблокирован.
При выпуске финального Read Lock — Читатель темы и один автор темы будет гонка чтобы увидеть, какой из них начинается.
это мог заставить читателей голодать писателей, если процессор часто переключает контекст на m_shared_cond нить перед m_exclusive_cond во время уведомления, но я подозреваю, что проблема теоретическая, а не практическая, так как это алгоритм Boost.
Теперь, когда Microsoft открыла исходный код .NET, вы можете посмотреть на их ReaderWriterLockSlim реализация.
Я не уверен, что вам доступны более простые примитивы, которые они используют, некоторые из них также являются частью библиотеки .NET, и их код также доступен.
Microsoft потратила довольно много времени на улучшение производительности своих механизмов блокировки, так что это может стать хорошей отправной точкой.