Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Результативная реализация Readers–writer lock на основе «Interlocked Variable Access»

Anna | 24.06.2014 | нет комментариев

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

В ходе данной публикации я хочу поделиться идеей реализации отлично знаменитого примитива синхронизации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);
}

Примитивный декремент в случае с чтением и сброс бита в случае с записью.

Взамен послесловия

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

Буду рад вашей критике и комментариям.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB