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

Ответ 1

Из текста благодарности:

Я даже не уверен, могу ли я доказать правильность представленного решения Boost, которое кажется более сложным, чем линейное.

Решение Boost не может затормозить, потому что оно никогда не ждет, когда уже держит замок. Все блокировки, но первые, приобретаются с помощью try_lock. Если какой-либо вызов try_lock не может получить свою блокировку, все ранее приобретенные блокировки освобождаются. Кроме того, в реализации Boost новая попытка начнется с блокировки, не получившей предыдущее время, и сначала будет ждать, пока она будет доступна; это разумное дизайнерское решение.

Как правило, всегда лучше избегать блокировки вызовов, удерживая блокировку. Поэтому решение с try-lock, если возможно, является предпочтительным (на мой взгляд). В качестве особого следствия, в случае блокировки, система в целом может застрять. Представьте себе, что последний замок (например, самый большой адрес) был получен потоком, который затем был заблокирован. Теперь представьте себе, что какой-то другой поток нуждается в последнем замке и еще одном замке, и из-за заказа он сначала получит другой и будет ждать последней блокировки. То же самое может произойти со всеми другими замками, и вся система не продвинется, пока не будет освобождена последняя блокировка. Конечно, это экстремальный и довольно маловероятный случай, но он иллюстрирует неотъемлемую проблему с порядком блокировки: чем выше номер блокировки, тем более косвенным воздействием блокировки при ее приобретении.

Недостатком решения на основе try-lock является то, что он может вызвать оживление, и в крайнем случае вся система может застрять хотя бы на некоторое время. Поэтому важно иметь некоторую резервную схему, которая делает паузы между попытками блокировки более длительными со временем и, возможно, рандомизированными.

Ответ 2

Иногда блокировка A должна быть получена до блокировки B. Блокировка B может иметь либо более низкий, либо более высокий адрес, поэтому вы не можете использовать сравнение адресов в этом случае.

Пример. Когда у вас есть древовидная структура данных, а потоки пытаются читать и обновлять узлы, вы можете защитить дерево, используя блокировку чтения-записи за node. Это работает только в том случае, если ваши потоки всегда получают блокировки сверху вниз root-to-leave. В этом случае адрес блокировок не имеет значения.

Вы можете использовать только сравнение адресов, если это не имеет значения, когда блокировка сначала приобретается. Если это так, сравнение адресов является хорошим решением. Но если это не так, вы не можете этого сделать.

Я предполагаю, что ядро ​​Linux требует, чтобы некоторые подсистемы были заблокированы перед другими. Это не может быть сделано с использованием сравнения адресов.

Ответ 3

"Сравнение адресов" и подобные подходы, хотя и используются довольно часто, являются особыми случаями. Они отлично работают, если у вас есть

• механизм блокировки для получения
• два (или более) "элемента" того же типа или уровня иерархии
• любая стабильная схема упорядочения между этими элементами

Например: у вас есть механизм для получения двух "учетных записей" из списка. Предположим, что доступ к списку заблокирован. Теперь у вас есть указатели на оба элемента и вы хотите их заблокировать. Поскольку они "братья и сестры", вам нужно выбрать, какой из них нужно заблокировать. Здесь подход с использованием адресов (или любой другой стабильной схемы упорядочения, такой как "идентификатор учетной записи" ) в порядке.

Но связанный текст Linux говорит о "иерархиях блокировок". Это означает, что они не связаны между "братьями и сестрами" (одного и того же типа), но между "родителями" и "детьми", которые могут быть разных типов. Это может происходить и в реальных древовидных структурах, а также в других сценариях. Продуманный пример: для загрузки программы вы должны

• заблокировать файл inode,
• заблокировать таблицу процессов
• заблокировать память назначения

Эти три замка не являются "братьями и сестрами" не в ясной иерархии. Замки также не принимаются непосредственно один за другим - каждая подсистема будет принимать блокировки по свободной воле. Если вы рассматриваете все случаи, когда эти три (и более) подсистемы взаимодействуют, вы видите, что нет четкого, стабильного порядка, о котором вы можете думать.

Библиотека Boost находится в той же ситуации: она стремится предоставлять общие решения. Поэтому они не могут принимать точки сверху и должны вернуться к более сложной стратегии.

Ответ 4

Один сценарий, когда сравнение адресов завершится неудачей, - это использование шаблона прокси. Вы можете делегировать блокировки одному и тому же объекту, и адреса будут разными.

Рассмотрим следующий пример

template<typename MutexType>
class MutexHelper
{
    MutexHelper(MutexType &m) : _m(m) {}
    void lock() 
    {
     std::cout <<"locking ";
     m.lock();
    }

    void unlock() 
    {
     std::cout <<"unlocking ";
     m.unlock();
    }

    MutexType &_m;
};

если функция

template<typename MutexType1,typename MutexType2,typename MutexType3>
void lock(MutexType1& m1,MutexType2& m2,MutexType3& m3);

будет фактически использовать адрес, чтобы сравнить следующий код ca, создающий тупик.

Mutex m1;
Mutex m1;

thread1

MutexHelper hm1(m1);
MutexHelper hm2(m2);

lock(hm1, hm2);

thread2:

MutexHelper hm2(m2);
MutexHelper hm1(m1);
lock(hm1, hm2);

EDIT:

Это интересный поток, который имеет некоторый свет в реализации boost:: lock thread-best-practice-to-lock-multiple-mutexes

Сравнение адресов не работает для межпроцессных общих мьютексов (называемых объектами синхронизации).