Вступление
Специфика проекта, в котором я работаю, такова, что с одной стороны не допускается использование сторонних библиотек (за небольшим исключением), а с другой акцент делается на очень глубокую оптимизацию кода. Вот и приходится зачастую изобретать велосипед в виде собственных реализаций.
В ходе данной публикации я хочу поделиться идеей реализации хорошо известного примитива синхронизации readers-writer lock на основе, так называемых атомарных операций. Как известно, readers-writer lock призван решать проблему синхронизации доступа к разделяемому ресурсу таким образом, чтобы избегать одновременных чтения и записи, но, при этом позволять параллельное чтение сколь угодно большому количеству потоков.
Поиск решения
Изначально я отнёсся к задаче довольно легкомысленно, но как оказалось зря. Начну с того что после просмотра доступных ресурсов я так и не нашёл реализации, которая бы мне понравилась. Как оказалось, самой большой проблемой было заблокировать приходящих «читателей» и «писателей» таким образом, чтобы они не остались в этом состоянии навсегда. Если, к примеру, организовать ожидание используя condition variables, то очень легко попасть в ситуацию, когда приходящий поток должен быть заблокирован, но пока происходит блокировка, поток обладавший ресурсом заканчивает работу с ним и сигнал о завершении, посылаемый им, не достигает адресата. Тот в свою очередь успешно завершает переход в состояние «wait» и на этом реализация терпит фиаско. Проблема на самом деле разрешима путём введения дополнительной логики, но в моём случае такая реализация в итоге получилась даже медленнее чем бессмысленный и беспощадный lock каждого входящего потока. Я конечно не претендую на то, что это абсолютная истина и возможно я что-то упустил, но стал искать другие возможности… Всё это время не покидало чувство, что проблему можно решить используя гораздо более простые механизмы interlocked variable access, с помощью которых я несколько ранее довольно элегантно разделался с double check locking оптимизацией. Итак я стал думать в этом направлении и в итоге получилось следующее…
Реализация
В проекте требуется поддержка систем QNX (собственно на которую ориентирован продукт) и Windows (эмуляция, отладка и.т.п.). Поскольку вторая намного более популярна, то C++ реализацию я приведу именно для неё. Впрочем на одном моменте переноса на POSIX я остановлюсь. Итак:
Болванка класса
class CRwLock
{
public:
CRwLock();
void readLock();
void writeLock();
void readUnlock();
void writeUnlock();
private:
static const LONG WRITER_BIT = 1L << (sizeof(LONG) * 8 - 2);
LONG mWriterReaders;
};
С набором функций всё очевидно и на мой взгляд не требует комментариев. Поговорим о единственном поле класса mWriterReaders:
- Последний не знаковый бит отдан под признак наличия одного единственного «писателя» и должен быть установлен, когда он владеет ресурсом. Собственно для работы с ним и заведена константа WRITER_BIT
- Остальные будут использоваться как простое целое число разрядностью 30 бит. В них будет записываться количество потоков читающих ресурс (при не установленном бите «писателя») или ожидающих чтения (при одновременно установленном бите «писателя» соответственно).
Конструктор класса
CRwLock::CRwLock()
: mWriterReaders(0)
{
}
Призван выполнить единственную задачу — установить начальное состояние, соответствующее отсутствию кого-либо владеющего ресурсом, или проще говоря сбрасывая все биты в 0.
Блокировка на чтение
Как вы уже вероятно догадались, я собираюсь вовсю использовать атомарные операции над единственной целочисленной переменной чтобы достичь нашей цели.
void CRwLock::readLock()
{
if(::InterlockedExchangeAdd(&mWriterReaders, 1) >= WRITER_BIT)
{
while(::InterlockedCompareExchange(&mWriterReaders, 0, 0) >= WRITER_BIT)
{
Sleep(0);
}
}
}
На входе сразу добавляем себя к читателям и одновременно проверяем есть ли кто-то выполняющий запись (это так если бит пишущего потока установлен, а следовательно само число больше либо равно этому значению). Если да, то мы должны ждать окончания операции записи вместе с остальными. Для этого я выбрал вариант spin блокировки в ходе которой проверяется тот самый бит «писателя» и как только он сброшен все кто ждёт чтения получают доступ (данная реализация отдаёт приоритет читающим потокам, но об этом чуть позже).
Здесь я бы хотел остановиться на вопросе так называемого busy wait, когда ожидающий поток активно потребляет ресурсы CPU. В данном случае я пошёл на компромисс добавив инструкцию Sleep(0), передающую оставшуюся часть времени, от выделенной процессу, в распоряжение планировщика, который может выдать её другим потокам в зависимости от их приоритета. Другими словами время не прожигается в холостую, а может быть использовано с пользой. С другой стороны острота реакции со стороны ждущего потока на изменение состояния флагов притупляется, что в случае моей конфигурации железа потоков и выполняемых ими операций выразилось в примерно 10% увеличении времени работы тестовой программы. Но ни в коем случае не стоит забывать, что система в целом конечно выигрывает имея в своём распоряжении свободный CPU.
В случае POSIX вместо Sleep(0) можно использовать sched_yield
Блокировка на запись
void CRwLock::writeLock()
{
while(::InterlockedCompareExchange(&mWriterReaders, WRITER_BIT, 0) != 0)
{
Sleep(0);
}
}
Требующий записи поток должен ждать до тех пор пока все не освободят ресурс (абсолютный ноль) и только потом он устанавливает читающим себя. Отсюда и приоритет читающих — даже переходя в состояние ожидания при существующем пишущем потоке они заранее гарантированно имеют приоритет перед такими же заблокированными «писателями».
Снятие блокировки
void CRwLock::readUnlock()
{
::InterlockedExchangeAdd(&mWriterReaders, -1);
}
void CRwLock::writeUnlock()
{
::InterlockedExchangeAdd(&mWriterReaders, -WRITER_BIT);
}
Простой декремент в случае с чтением и сброс бита в случае с записью.
Вместо послесловия
Хочу сказать, что в моём случае я получил хороший результат по производительности по сравнению с использованием критических секций, который при этом предсказуемо ведёт себя при изменении соотношения пишущих и читающих потоков.
Буду рад вашей критике и комментариям.
Автор: AndreyDobrovolskiy
