Создание собственной SPIN-блокировки

← →
Quazi © (2009-09-04 11:54) [0]

Нужно сделать собственную быструю блокировку типа ReadWrite (много читателей, один писатель) с ReEnter-ом. Т.е. поток, получивший блокировку на запись, может получать блокировку чтения или записи повторно. Идея:
переменная типа long volatile разбирается на 3 части:
1 байт: кол-во блокировок на Read
2 байт: кол-во блокировок на Write
последнее слово: TID (ID потока, установившего блокировку на запись или 0, если блокировки на запись не стоит).
Работа с этими 3-мя полями атомарна (т.е. меняются все поля сразу), с использованием Interlocked-функций (конкретно: InterlockedCompareExchange), поэтому и используется long.
Потенциальная проблема: TID это DWORD, и в WORD оно не лезет :)). Но на практике, я ни когда не встречал PID более 0xFFF и WORD можно использовать.
Вопрос: можно ли использовать WORD для хранения TID на 32-х битных OS? Как формируется TID?

← →
Leonid Troyanovsky © (2009-09-04 13:01) [1]

> Quazi © (04.09.09 11:54)

> Нужно сделать собственную быструю блокировку типа ReadWrite
> (много читателей, один писатель) с ReEnter-ом. Т.е. поток,
> получивший блокировку на запись, может получать блокировку
> чтения или записи повторно.

Одной блокировки здесь мало.
Если читателей много, то они просто не дадут вклиниться писателю.

> Работа с этими 3-мя полями атомарна (т.е. меняются все поля
> сразу), с использованием Interlocked-функций (конкретно:
> InterlockedCompareExchange), поэтому и используется long.

На основе InterlockedCompareExchange можно соорудить
массу "легких" собс-ручных объектов синхронизации.

См. например
http://msdn.microsoft.com/en-us/magazine/cc302329.aspx

Экономить на полях смысла не вижу, доступ к обычным полям
защищать собс-ручным аналогом крит секции.

--
Regards, LVT.

← →
Quazi © (2009-09-04 15:07) [2]

>Экономить на полях смысла не вижу, доступ к обычным полям
>защищать собс-ручным аналогом крит секции.

Смысл экономить есть, т.к. одна атомарная операция занимает около 100(!!!) тактов процессора, и на время работы этой операции, все остальные процессора не могут обратиться к памяти, т.к. шина блокирована. блокировка крит-секции (или собственный аналог) предполагает цикл с атомарной операцией на блокировку и 1-у атомарную операцию на освобождение. Между ними операции по установку или не установке основной блокировки (со всеми ее параметрами). Проблемы этого подхода (в моем случае):
1) Объем кода, защищенного блокировкой, сопоставим с объемом кода самой блокировки.
2) Блокировка ставиться и освобождается очень часто из многих (3-6) потоков. Они дружно начнут проводить большую часть времени в цикле получения блокировки.
Чтобы избавиться от всех этих проблем, я и делаю простую блокировку на Interlocked-функциях.

← →
Leonid Troyanovsky © (2009-09-04 17:31) [3]

> Quazi © (04.09.09 15:07) [2]

> памяти, т.к. шина блокирована. блокировка крит-секции (или
> собственный аналог) предполагает цикл с атомарной операцией
> на блокировку и 1-у атомарную операцию на освобождение.

И при освобождении не одна операция, а цикл.

> 1) Объем кода, защищенного блокировкой, сопоставим с объемом
> кода самой блокировки.

Попытайся повысить гранулярность.

> 2) Блокировка ставиться и освобождается очень часто из многих
> (3-6) потоков. Они дружно начнут проводить большую часть
> времени в цикле получения блокировки.

Либо ожидание в ядерном режиме, либо непрерывный цикл опроса -
другого, IMHO, не дано. "Быстрая" подразумевает второе.
И чего ради жалеть процессоры? Они же железные.

> Чтобы избавиться от всех этих проблем, я и делаю простую
> блокировку на Interlocked-функциях.

Ссылку-то изучил?

И еще, не надо строить никаких предположенией относительно
диапазонов значений для ThreadId. Помнится, что на rsdn.ru
сообществу с не без труда удалось доказать, что оный
не может быть 0.

Мда, и 255 блокировок - это много или мало?
А на кой, во-ще, потребовались множественные блокировки
для коллективов читателей?

--
Regards, LVT.

← →
Leonid Troyanovsky © (2009-09-04 17:37) [4]

> Leonid Troyanovsky © (04.09.09 17:31) [3]

> для коллективов читателей?

И еще, если уж читателей много, то одним ID, все равно, не обойтись.

--
Regards, LVT.

← →
Quazi © (2009-09-04 17:56) [5]

>И при освобождении не одна операция, а цикл.
Там можно оптимизировать до одной операции, с гарантией правильного выполнения.

>> 1) Объем кода, защищенного блокировкой, сопоставим с объемом
>> кода самой блокировки.
>Попытайся повысить гранулярность.

Увы...

>Либо ожидание в ядерном режиме, либо непрерывный цикл опроса -
>другого, IMHO, не дано. "Быстрая" подразумевает второе.
>И чего ради жалеть процессоры? Они же железные.

Вот второе я и делаю.

>Ссылку-то изучил?
Изучил. Ничего нового. У Рихтера это описано бог знает когда. Я пошел еще дальше.

>И еще, не надо строить никаких предположенией относительно
>диапазонов значений для ThreadId. Помнится, что на rsdn.ru
>сообществу с не без труда удалось доказать, что оный
>не может быть 0.
Вот в этом у меня и вопрос. Причем только для 32-OS. В 64-OS я использую QWORD и туда DWORD лезет легко.

>Мда, и 255 блокировок - это много или мало?
Достаточно. Потоков не более 16. 16 блокировок на каждый поток.

>А на кой, во-ще, потребовались множественные блокировки
>для коллективов читателей?
Потому что есть еще коллектив писателей, но пишут они редко, а вот читают часто. В итоге, читатели друг-другу не мешают и спокойно работают.

>И еще, если уж читателей много, то одним ID, все равно, не обойтись.
Обойтись. Читатели не сохраняют свои TID. Он им не нужен. Только сам факт, что читатель сейчас работает (тупой счетчик, если 0, значит писатель может поставить свою блокировку).

Если интересно, могу код выложить (VC++ 2008) того, что получилось. Может пригодиться.

← →
Quazi © (2009-09-04 17:59) [6]

//Реинтерабельная SPIN-блокировка ReadWrite #pragma intrinsic (_InterlockedExchangeAdd) #define InterlockedExchangeAdd _InterlockedExchangeAdd #ifdef _WIN64 #pragma intrinsic (_InterlockedExchangeAdd64) #define InterlockedExchangeAdd64 _InterlockedExchangeAdd64 #pragma intrinsic (_InterlockedDecrement64) #define InterlockedDecrement64 _InterlockedDecrement64 #endif #ifdef _WIN64 #define RWLOCKVALUE __int64 #define MyInterlockedCompareExchange _InterlockedCompareExchange64 #define MyInterlockedAdd InterlockedExchangeAdd64 #define LOCK_MASK_READ 0xFFFF000000000000 #define LOCK_MASK_WRITE 0x0000FF0000000000 #define LOCK_MASK_TID 0x000000FFFFFFFFFF #define LOCK_WRITE 0x0000010000000000 #define LOCK_READ 0x0001000000000000 #else #define RWLOCKVALUE long #define MyInterlockedCompareExchange _InterlockedCompareExchange #define MyInterlockedAdd InterlockedExchangeAdd #define LOCK_MASK_READ 0xFF800000 #define LOCK_MASK_WRITE 0x007F0000 #define LOCK_MASK_TID 0x0000FFFF #define LOCK_WRITE 0x00010000 #define LOCK_READ 0x00800000 #endif #define RWLOCK RWLOCKVALUE volatile #define LOCK_UNREAD ~(LOCK_READ-1) __forceinline void LockForWrite(RWLOCK *lock){ RWLOCKVALUE thread=pthread_self(); RWLOCKVALUE val=*lock; if ((val & LOCK_MASK_TID)==thread){//Повторная блокировка MyInterlockedAdd(lock, LOCK_WRITE);//Просто добавляем еще одну блокировку return; }; thread|=LOCK_WRITE; for(;;){//Первичная блокировка, и повторной она никогда не станет, т.к. это наш поток RWLOCKVALUE tmp=val & LOCK_MASK_READ; val=tmp | thread; val=MyInterlockedCompareExchange(lock, val, tmp); if (val==tmp) break; }; for (;;) { if (!(*lock & LOCK_MASK_READ)) return; }; }; __forceinline void LockForRead(RWLOCK *lock){ RWLOCKVALUE thread=pthread_self(); RWLOCKVALUE val=*lock; if ((val & LOCK_MASK_TID)==thread){//Повторная блокировка MyInterlockedAdd(lock, LOCK_READ);//Просто добавляем еще одну блокировку return;//Значение не может измениться, т.к. наш поток владеет локом эксклюзивно }; for (;;) {//Первичная блокировка, и повторной она никогда не станет, т.к. это наш поток RWLOCKVALUE tmp=val & LOCK_MASK_READ; val=tmp+LOCK_READ; val=MyInterlockedCompareExchange(lock, val, tmp); if (val==tmp) break; }; }; __forceinline void SwitchToRead(RWLOCK *lock){ ASSERT((*lock & LOCK_MASK_WRITE)); RWLOCKVALUE tmp=*lock; RWLOCKVALUE val=tmp-LOCK_WRITE+LOCK_READ; if (!(val & LOCK_MASK_WRITE)){//Последняя блокировка val&=LOCK_MASK_READ; }; MyInterlockedCompareExchange(lock, val, tmp);//Значение не может измениться, т.к. наш поток владеет локом эксклюзивно }; __forceinline void UnLockWrite(RWLOCK *lock){ ASSERT((*lock & LOCK_MASK_WRITE)); RWLOCKVALUE tmp=*lock; RWLOCKVALUE val=tmp-LOCK_WRITE; if (!(val & LOCK_MASK_WRITE)){//Последняя блокировка val&=LOCK_MASK_READ; }; MyInterlockedCompareExchange(lock, val, tmp);//Значение не может измениться, т.к. наш поток владеет локом эксклюзивно }; __forceinline void UnLockRead(RWLOCK *lock){ ASSERT((*lock & LOCK_MASK_READ)); MyInterlockedAdd(lock, LOCK_UNREAD); };

← →
Leonid Troyanovsky © (2009-09-04 18:01) [7]

> Quazi © (04.09.09 11:54)

> (много читателей, один писатель) с ReEnter-ом. Т.е. поток,
> получивший блокировку на запись, может получать блокировку
> чтения или записи повторно.

Не очень понятен смысл повторной блокировки.
Если писатель захватил некий эксклюзивный объект, то пока он
его не освободит может и писать и читать сколько потребуется.
Т.е., писательство эксклюзивно, читательство - зашарено.
И есть ли смысл писателю прикидываться читателем?

Про SWMR Guardian object by Jeff Richter читал?

Кроме того, можно посмотреть исходние для
TMultiReadExclusiveWriteSychronizer для версий D7+

--
Regards, LVT.

← →
Leonid Troyanovsky © (2009-09-04 18:08) [8]

> Leonid Troyanovsky © (04.09.09 18:01) [7]

Пока столько букв написал, многие вопросы прояснились.

> У Рихтера это описано бог знает когда.

Ну, дык это он самый и есть, ранний :)

> Quazi © (04.09.09 17:59) [6]

Боюсь, что внимательно изучить его смогу не раньше чем
через пару недель, бо в отпуск :)

--
Regards, LVT.

← →
Quazi © (2009-09-04 18:15) [9]

>Не очень понятен смысл повторной блокировки.
>Если писатель захватил некий эксклюзивный объект, то пока он
>его не освободит может и писать и читать сколько потребуется.
>Т.е., писательство эксклюзивно, читательство - зашарено.
>И есть ли смысл писателю прикидываться читателем?
Ситуация:
1) Список объектов, защищенный блокировкой
2) Идет цикл удаления объектов (с блокировкой), но не сразу, а путем уведомления объектов, тип "удались", чтобы он корректно завершил свою работу и потом помер "когда смог".
3) Объект при своей смерти, удаляет себя из списка, для чего ставит блокировку.
Ситуация: нет никаких гарантий, что в тот момент, когда мы говорим "помри", он не помрет и не попытается удалить себя из списков. Вот и дидлок.

>Про SWMR Guardian object by Jeff Richter читал?
От туда и ноги растут. :) Только я решил его оптимизировать под свои нужды с учетом своей специфики.

← →
Leonid Troyanovsky © (2009-09-04 18:22) [10]

> Quazi © (04.09.09 17:56) [5]

> Потому что есть еще коллектив писателей, но пишут они редко,
> а вот читают часто. В итоге, читатели друг-другу не мешают

В том-то и дело, что мешают. Писателю.
Коллектив читателей способен предовратить ему доступ
по принципу "а ну-ка, отними".

У Рихтера, во 2 издании (поздние я уж не читал) в SWMRG есть
этот баг, поправил ли он его позже не знаю.

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

--
Regards, LVT.

> Leonid Troyanovsky © (04.09.09 18:22) [10]

> Самый простой способ обхода - когда читатель установит

Тьфу-ты, писатель, sorry.

--
Regards, LVT.

> Quazi © (04.09.09 18:15) [9]

> 3) Объект при своей смерти, удаляет себя из списка, для
> чего ставит блокировку.

А зачем блокировку?
Ему достаточно асинхронно извеcтить писателя, а тот уж поменяет
ему статус с "удались" на "умер" и удалит из списка.
Хотя, реализацию такого пока представляю лишь с объектами ядра.

--
Regards, LVT.

> Leonid Troyanovsky © (04.09.09 18:33) [12]

> Хотя, реализацию такого пока представляю лишь с объектами
> ядра.

А, вот.

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

Про memory barrier & etc. в этом случае мне тоже ничего не известно.

--
Regards, LVT.

>В том-то и дело, что мешают. Писателю.
>Коллектив читателей способен предотвратить ему доступ
>по принципу "а ну-ка, отними".
Это я обрабатываю и там все хорошо.

>А зачем блокировку?
>Ему достаточно асинхронно извеcтить писателя, а тот уж поменяет
>ему статус с "удались" на "умер" и удалит из списка.
>Хотя, реализацию такого пока представляю лишь с объектами ядра.
Асинхронно дольше, и дороже, чем вызвать callback с блокировкой.

> Quazi © (04.09.09 19:17) [14]

> Асинхронно дольше, и дороже, чем вызвать callback с блокировкой.

Дык, это уже не single writer, и в этом случае, также одним ThreadId
не обойтись, IMHO.
Ну, и асинхронно, здесь в смысле: без ожидания подтверждения.
Формулировалось, скажем, в терминах объектов ядра,
см. также [13], хорошее число.

--
Regards, LVT.

Создание собственной SPIN-блокировки Найти похожие ветки