- PVSM.RU - https://www.pvsm.ru -

Эффективная реализация Readers–writer lock на основе «Interlocked Variable Access»

Вступление

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

В ходе данной публикации я хочу поделиться идеей реализации хорошо известного примитива синхронизации readers-writer lock [1] на основе, так называемых атомарных операций. Как известно, readers-writer lock призван решать проблему синхронизации доступа к разделяемому ресурсу таким образом, чтобы избегать одновременных чтения и записи, но, при этом позволять параллельное чтение сколь угодно большому количеству потоков.

Поиск решения

Изначально я отнёсся к задаче довольно легкомысленно, но как оказалось зря. Начну с того что после просмотра доступных ресурсов я так и не нашёл реализации, которая бы мне понравилась. Как оказалось, самой большой проблемой было заблокировать приходящих «читателей» и «писателей» таким образом, чтобы они не остались в этом состоянии навсегда. Если, к примеру, организовать ожидание используя condition variables [2], то очень легко попасть в ситуацию, когда приходящий поток должен быть заблокирован, но пока происходит блокировка, поток обладавший ресурсом заканчивает работу с ним и сигнал о завершении, посылаемый им, не достигает адресата. Тот в свою очередь успешно завершает переход в состояние «wait» и на этом реализация терпит фиаско. Проблема на самом деле разрешима путём введения дополнительной логики, но в моём случае такая реализация в итоге получилась даже медленнее чем бессмысленный и беспощадный lock каждого входящего потока. Я конечно не претендую на то, что это абсолютная истина и возможно я что-то упустил, но стал искать другие возможности… Всё это время не покидало чувство, что проблему можно решить используя гораздо более простые механизмы interlocked variable access [3], с помощью которых я несколько ранее довольно элегантно разделался с double check locking [4] оптимизацией. Итак я стал думать в этом направлении и в итоге получилось следующее…

Реализация

В проекте требуется поддержка систем 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 блокировки [5] в ходе которой проверяется тот самый бит «писателя» и как только он сброшен все кто ждёт чтения получают доступ (данная реализация отдаёт приоритет читающим потокам, но об этом чуть позже).

Здесь я бы хотел остановиться на вопросе так называемого 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

Источник [6]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/news/47569

Ссылки в тексте:

[1] readers-writer lock: http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock

[2] condition variables: http://en.wikipedia.org/wiki/Condition_variable#Waiting_and_signaling

[3] interlocked variable access: http://msdn.microsoft.com/en-us/library/windows/desktop/ms684122(v=vs.85).aspx

[4] double check locking: http://en.wikipedia.org/wiki/Double-checked_locking

[5] spin блокировки: http://ru.wikipedia.org/wiki/Spinlock

[6] Источник: http://habrahabr.ru/post/200924/