Насколько эффективна блокировка разблокированного мьютекса? Какова стоимость мьютекса?

На низкоуровневом языке (C, C ++ или любой другой): у меня есть выбор между наличием нескольких мьютексов (например, что дает мне pthread или того, что предоставляет нативная системная библиотека) или одного для объекта.

Насколько эффективно блокировать мьютекс? Т.е. сколько там ассемблерных инструкций и сколько времени они занимают (в случае, если мьютекс разблокирован)?

Сколько стоит мьютекс? Действительно ли проблема иметь много мьютексов? Или я могу просто добавить столько переменных мьютекса в мой код, сколько у меня есть intпеременных, и это не имеет значения?

(Я не уверен, насколько сильно различаются разные аппаратные средства. Если таковые имеются, я также хотел бы узнать о них. Но в основном меня интересует обычное аппаратное обеспечение.)

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

Сообщение в блоге WebKits (2016) о блокировке очень связано с этим вопросом и объясняет различия между спин-блокировкой, адаптивной блокировкой, futex и т. Д.

У меня есть выбор между наличием нескольких мьютексов или одного для объекта.

Если у вас много потоков и доступ к объекту происходит часто, то множественные блокировки увеличат параллелизм. За счет ремонтопригодности, поскольку большее количество блокировок означает больше отладки блокирующего устройства

Насколько эффективно блокировать мьютекс? Т.е. сколько там ассемблерных инструкций и сколько времени они занимают (в случае, если мьютекс разблокирован)?

Точные инструкции на ассемблере являются наименьшими накладными расходами мьютекса - гарантии когерентности памяти и кэша являются основными накладными расходами. И реже берется конкретная блокировка - лучше.

Мьютекс состоит из двух основных частей (упрощенное): (1) флаг, указывающий, заблокирован ли мьютекс или (2) очередь ожидания.

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

Блокировка разблокированного мьютекса действительно дешева. Разблокировка мьютекса без конфликтов тоже дешевая.

Сколько стоит мьютекс? Действительно ли проблема иметь много мьютексов? Или я могу просто добавить столько мьютекс-переменных в мой код, сколько у меня есть переменных типа int, и это не имеет значения?

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

Резюме. Блокировки пользовательского пространства (и мьютексы в частности) дешевы и не подвержены каким-либо системным ограничениям. Но слишком много из них заклинаний кошмара для отладки. Простая таблица:

1. Меньше блокировок означает больше конфликтов (медленные системные вызовы, задержки ЦП) и меньший параллелизм
2. Меньше блокировок означает меньше проблем отладки многопоточности.
3. Больше блокировок означает меньше раздоров и более высокий параллелизм
4. Чем больше блокировок, тем больше шансов попасть в неразрушимые тупики.

Должна быть найдена и сохранена сбалансированная схема блокировки для применения, как правило, с балансировкой № 2 и № 3.

(*) Проблема с менее часто блокируемыми мьютексами заключается в том, что если у вас слишком много блокировок в приложении, это приводит к тому, что большая часть межпроцессорного / основного трафика освобождает память мьютекса из кэша данных других процессоров, чтобы гарантировать когерентность кэша. Сброс кеша подобен легким прерываниям и прозрачно обрабатывается центральными процессорами, но они вводят так называемые задержки (поиск «остановка»).

А задержки - это то, что заставляет код блокировки работать медленно, часто без какого-либо явного указания, почему приложение работает медленно. (Некоторые арки предоставляют статистику трафика между процессорами / ядрами, некоторые нет.)

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

Я хотел знать то же самое, поэтому я измерил это. На моем компьютере (8-ядерный процессор AMD FX (tm) -8150 с тактовой частотой 3,612361 ГГц) блокировка и разблокировка разблокированного мьютекса, который находится в отдельной строке кэша и уже кэширован, занимает 47 тактов (13 нс).

Из-за синхронизации между двумя ядрами (я использовал CPU # 0 и # 1), я мог вызывать пару блокировки / разблокировки только один раз каждые 102 нс в двух потоках, то есть один раз каждые 51 нс, из чего можно сделать вывод, что это занимает примерно 38 ns восстановить после того, как поток выполнит разблокировку, прежде чем следующий поток сможет снова его заблокировать.

Программу, которую я использовал для исследования этого, можно найти здесь: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Обратите внимание, что у него есть несколько жестко заданных значений, специфичных для моего блока (xrange, yrange и rdtsc overhead), поэтому вам, вероятно, придется поэкспериментировать с ним, прежде чем он будет работать для вас.

График, который он производит в этом состоянии:

Это показывает результаты теста производительности в следующем коде:

uint64_t do_Ndec(int thread, int loop_count)
{
  uint64_t start;
  uint64_t end;
  int __d0;

  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx");
  mutex.lock();
  mutex.unlock();
  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx");
  asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc");
  return end - start;
}

Два вызова rdtsc измеряют количество часов, которое требуется для блокировки и разблокировки «мьютекса» (с накладными расходами в 39 часов для вызовов rdtsc на моем ящике). Третий ассм - это петля задержки. Размер цикла задержки на 1 счет меньше для потока 1, чем для потока 0, поэтому поток 1 немного быстрее.

Вышеуказанная функция вызывается в узком цикле размером 100 000. Несмотря на то, что функция немного быстрее для потока 1, оба цикла синхронизируются из-за вызова мьютекса. Это видно на графике из того факта, что количество тактов, измеренных для пары блокировка / разблокировка, немного больше для потока 1, чтобы учесть более короткую задержку в цикле под ним.

На приведенном выше графике нижняя правая точка представляет собой измерение с задержкой loop_count, равной 150, а затем, следуя точкам внизу, влево, loop_count уменьшается на единицу для каждого измерения. Когда она становится 77, функция вызывается каждые 102 нс в обоих потоках. Если впоследствии loop_count уменьшается еще больше, то больше невозможно синхронизировать потоки, и мьютекс начинает фактически блокироваться большую часть времени, что приводит к увеличению количества тактов, необходимых для блокировки / разблокировки. Также из-за этого увеличивается среднее время вызова функции; так что точки сюжета теперь идут вверх и вправо снова.

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

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

Попробуйте заблокировать мьютексы как можно короче. Единственная причина поместить их, скажем, вне цикла, состоит в том, что этот цикл зацикливается быстрее, чем один раз каждые 100 нс (или, скорее, число потоков, которые хотят запустить этот цикл одновременно, 50 нс) или когда 13 нс раз размер цикла больше задержки, чем задержка, которую вы получаете из-за конфликта.

РЕДАКТИРОВАТЬ: я получил гораздо больше знаний по этому вопросу сейчас и начинаю сомневаться в заключении, которое я представил здесь. Прежде всего, CPU 0 и 1 оказываются гиперпоточными; Несмотря на то, что AMD утверждает, что имеет 8 реальных ядер, безусловно, есть что-то очень подозрительное, потому что задержки между двумя другими ядрами намного больше (то есть 0 и 1 образуют пару, как и 2 и 3, 4 и 5, и 6 и 7 ). Во-вторых, std :: mutex реализован таким образом, что он немного вращает блокировки перед тем, как фактически выполнять системные вызовы, когда не удается немедленно получить блокировку для мьютекса (что, без сомнения, будет очень медленным). Итак, что я измерил здесь, так это абсолютную наиболее идеальную ситуацию, и на практике блокировка и разблокировка могут занять значительно больше времени на блокировку / разблокировку.

В итоге мьютекс реализован с использованием атомики. Чтобы синхронизировать атомы между ядрами, должна быть заблокирована внутренняя шина, которая замораживает соответствующую строку кэша на несколько сотен тактов. В случае, если блокировка не может быть получена, системный вызов должен быть выполнен, чтобы перевести поток в спящий режим; это, очевидно, очень медленно (системные вызовы порядка 10 микросекунд). Обычно это на самом деле не проблема, потому что этот поток все равно должен спать - но это может быть проблемой с высокой конкуренцией, когда поток не может получить блокировку в течение времени, когда он обычно вращается, и так делает системный вызов, но CAN возьмите замок вскоре после этого. Например, если несколько потоков блокируют и разблокируют мьютекс в узком цикле и каждый из них удерживает блокировку в течение 1 микросекунды или около того, тогда они могут быть сильно замедлены тем фактом, что их постоянно усыпляют и снова просыпают. Кроме того, после того, как поток спит и другой поток должен его разбудить, этот поток должен выполнить системный вызов и задерживается ~ 10 микросекунд; таким образом, эта задержка происходит при разблокировке мьютекса, когда другой поток ожидает этот мьютекс в ядре (после вращения потребовалось слишком много времени).

Это зависит от того, что вы на самом деле называете «мьютексом», режимом ОС и т. Д.

Как минимум это стоимость операции с блокировкой памяти. Это относительно тяжелая операция (по сравнению с другими примитивными командами ассемблера).

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

Например, на процессоре Intel Core Duo, Windows XP. Операция с блокировкой: занимает около 40 тактов процессора. Вызов режима ядра (т.е. системный вызов) - около 2000 циклов ЦП.

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

Стоимость будет варьироваться в зависимости от реализации, но вы должны иметь в виду две вещи:

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

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

В обоих случаях инструкции относительно эффективны.

Что касается того, следует ли предоставлять один мьютекс для массивной структуры данных или иметь много мьютексов, по одному на каждый его раздел, это балансирование.

Имея один мьютекс, вы имеете более высокий риск конфликта между несколькими потоками. Вы можете уменьшить этот риск, имея мьютекс на раздел, но вы не хотите попадать в ситуацию, когда поток должен заблокировать 180 мьютексов для выполнения своей работы :-)

Я абсолютно новичок в pthreads и mutex, но я могу подтвердить из экспериментов, что стоимость блокировки / разблокировки мьютекса почти равна нулю, когда нет конкуренции, но когда есть конфликты, цена блокировки чрезвычайно высока. Я запустил простой код с пулом потоков, в котором задачей было просто вычислить сумму в глобальной переменной, защищенной блокировкой мьютекса:

y = exp(-j*0.0001);
pthread_mutex_lock(&lock);
x += y ;
pthread_mutex_unlock(&lock);

С одним потоком программа суммирует 10 000 000 значений практически мгновенно (менее одной секунды); с двумя потоками (на MacBook с 4 ядрами), та же самая программа занимает 39 секунд.