Как функции блокировки и разблокировки мьютекса предотвращают переупорядочение ЦП?

Насколько мне известно, вызов функции действует как барьер компилятора, но не как барьер процессора.

В этом руководстве говорится следующее:

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

Я предполагаю, что приведенная выше цитата говорит о переупорядочивании ЦП, а не о переупорядочении компилятора.

Но я не понимаю, как блокировка и разблокировка мьютекса заставляет ЦП давать этим функциям семантику получения и освобождения.

Например, если у нас есть следующий код C:

pthread_mutex_lock(&lock);
i = 10;
j = 20;
pthread_mutex_unlock(&lock);

Вышеупомянутый код C транслируется в следующие (псевдо) инструкции по сборке:

push the address of lock into the stack
call pthread_mutex_lock()
mov 10 into i
mov 20 into j
push the address of lock into the stack
call pthread_mutex_unlock()

Что же мешает процессору переупорядочить mov 10 into i и mov 20 into j на значение выше call pthread_mutex_lock() или ниже call pthread_mutex_unlock()?

Если это инструкция call, которая не позволяет процессору переупорядочить, то почему в приведенном мною руководстве создается впечатление, что именно функции блокировки и разблокировки мьютексов предотвращают переупорядочение процессора, почему в приведенном мною руководстве не сказано, что любой вызов функции предотвратит переупорядочение процессора?

У меня вопрос об архитектуре x86.


c x86 assembly mutex memory-barriers
person user8426277    schedule 20.06.2018    source источник
comment
Почему вы не восстановили и не отредактировали свою предыдущую версию этого: stackoverflow.com/questions/50948788/? Это тот же вопрос с небольшими изменениями, и комментарий Мартина по-прежнему применим.   -  person Peter Cordes    schedule 20.06.2018
comment
Я предполагаю, что приведенная выше цитата говорит о переупорядочивании ЦП, а не о переупорядочении компилятора. Конечно, блокировка / разблокировка мьютекса pthread ДОЛЖНА гарантировать, что компилятор не изменит порядок инструкций, которые он защищает. Таким образом, цитата говорит о переупорядочении как компилятора, так и процессора - они одинаково важны с точки зрения мьютекса pthread.   -  person nos    schedule 20.06.2018
comment
Именно реализации pthread_mutex_lock() и pthread_mutex_unlock() реализуют свои обещания относительно упорядочивания во время выполнения. ЦП, которые выполняют такое переупорядочение, также имеют инструкции для его модуляции, и функции блокировки / разблокировки мьютексов используют их (среди прочего).   -  person John Bollinger    schedule 20.06.2018
comment
@JohnBollinger: Я уже упоминал об этом в своем ответе. Я выделил это, потому что это важный момент, почему функции мьютексов являются особенными.   -  person Peter Cordes    schedule 20.06.2018
comment
И я уже поддержал ваш ответ, @PeterCordes, и я отказался писать один из моих собственных. Но ваш ответ настолько информативен, что даже с выделением этого момента легко упустить из виду этот момент - который, я думаю, является ключевым - внутри.   -  person John Bollinger    schedule 20.06.2018
comment
@JohnBollinger: Это честно, это определенно ключевой момент. Я начал писать, прежде чем очень внимательно прочитать вопрос, поэтому я, вероятно, ответил на некоторые вещи, которые вопрос не задает явно. Похоже, неплохая идея охватить кучу связанных тем. (И я начал с переупорядочивания компилятора, потому что я только что смотрел еще один вопрос и ответ по этому поводу .: P)   -  person Peter Cordes    schedule 20.06.2018
comment
Я написал свой ответ, потому что, хотя ответ @PeterCordes великолепен, я думал, что этот вопрос также заслуживает одного небольшого ответа, просто сосредоточившись на узкой вещи, которую, как я думал, задавал OP: как компилятор / среда выполнения / реализация предотвращают переупорядочение процессора (а не переупорядочение компилятора) . Ответ прост: реализация включает барьеры, препятствующие переупорядочению ЦП. ОП прокомментировал мой ответ, который раскрывает их первоначальное недоразумение: это переупорядочение могло произойти вокруг call, как если бы это была любая другая инструкция. Не может. Переупорядочивание происходит против динамической трассировки.   -  person BeeOnRope    schedule 20.06.2018
comment
Я также новичок в переупорядочивании процессоров, поэтому, хотя я, несомненно, не могу дать лучшего ответа, чем здесь эксперты, я лучше понимаю, о чем спрашивал ОП, потому что при чтении этого абзаца у меня было такое же недоумение. Он не спрашивал, как pthread_mutex_lock/pthread_mutex_unlock реализует барьер ЦП, но почему эти функции мьютекса обязаны реализовывать указанный барьер ЦП из значения мьютекса. Ниже я дам свой ответ на первый вопрос (Что теперь мешает ...), по-новичку для новичков, ...   -  person zzzhhh    schedule 12.06.2021
comment
... во-первых, в общем, pthread_mutex_lock() - это не что иное, как последовательность инструкций, так что, в общем, опять же, ЦП не подозревает, что это настолько особенная функция, что переупорядочивание памяти процессора запрещено. Итак, вообще говоря, в третий раз ничто не может помешать процессору переупорядочить mov 10 into i на выше call pthread_mutex_lock(). В результате возникает естественный вопрос. Теперь позвольте мне ответить ниже, начиная со значения мьютекса. ...   -  person zzzhhh    schedule 12.06.2021
comment
... Все мы знаем, что значение mutex - указать критический раздел, как написано во всех учебниках по OS / параллельному программированию. Критическая секция должна выполняться не более чем одним потоком. Итак, если код типа mov 10 into i переупорядочен выше call pthread_mutex_lock() в потоке 1, поток 2 может запускать критическую секцию в этой точке, потому что поток 1 еще не получил мьютекс, что является нарушением значения мьютекса. Вы можете найти множество примеров сбоев, вызванных запуском кода критической секции двумя потоками одновременно. ...   -  person zzzhhh    schedule 12.06.2021
comment
... Итак, в общем, мьютекс предотвращает переупорядочение памяти. Это объясняет, почему pthread_mutex_lock() должен служить барьером для памяти. Конечно, простое наименование функции mutex_lock или что-то в этом роде не означает, что она будет функционировать как получение мьютекса; мы должны это реализовать. Фактически, мы должны реализовать не только традиционное получение мьютексов, о котором написано во многих учебниках, но и семантику получения. Как сказано в следующем абзаце предыдущей статьи, каждая реализация блокировки ... должна обеспечивать эти гарантии. ...   -  person zzzhhh    schedule 12.06.2021
comment
... Итак, с корневой точки зрения, барьер памяти вставлен call pthread_mutex_lock() исключительно из соображений добросовестности и уважения семантики мьютекса. На практике вполне вероятно, что программисту не удалось записать барьер памяти ЦП в функции, но он добавил его позже в качестве исправления ошибки, или случайно использовал некоторые инструкции, которые автоматически реализуют барьер, даже не зная об этом программисту. Эти детали реализации подробно описаны в ответах экспертов, поэтому повторяться не буду. Тот же аргумент можно применить для pthread_mutex_unlock(), чтобы соблюсти семантику выпуска.   -  person zzzhhh    schedule 12.06.2021

Ответы (2)


arrow_upward
8
arrow_downward

Короткий ответ заключается в том, что тело вызовов pthread_mutex_lock и pthread_mutex_unlock будет включать необходимые зависящие от платформы барьеры памяти, которые не позволят ЦП перемещать доступ к памяти в критическом разделе за его пределы. Поток инструкций переместится из вызывающего кода в функции lock и unlock с помощью инструкции call, и именно эту динамическую трассировку инструкций вы должны учитывать в целях переупорядочения, а не статическую последовательность, которую вы видите в листинге сборки.

В частности, на x86 вы, вероятно, не найдете явных, автономных барьеров памяти внутри этих методов, поскольку у вас уже есть Инструкции с lock префиксом, чтобы выполнить фактическую блокировку и разблокировку атомарно, и эти инструкции подразумевают полный барьер памяти, который предотвращает переупорядочение ЦП, которое вас беспокоит.

Например, в моей системе Ubuntu 16.04 с glibc 2.23, pthread_mutex_lock реализован с использованием lock cmpxchg (сравнение и обмен), а pthread_mutex_unlock реализован с использованием lock dec (декремент), оба из которых имеют полную семантику барьера.

person BeeOnRope    schedule 20.06.2018
comment
Короткий ответ заключается в том, что тело вызовов pthread_mutex_lock и pthread_mutex_unlock будет включать необходимые зависящие от платформы барьеры памяти, которые не позволят процессору перемещать доступ к памяти внутри критического раздела за его пределы. Я не делаю этого. Не понимаю, почему тело этих функций имеет значение, я имею в виду, что i = 10; может быть выполнен до выполнения pthread_mutex_lock(&lock);, и поэтому то, что находится внутри критического раздела, было перемещено за пределы критического раздела. Или такое переупорядочение разрешено не на всех архитектурах ЦП? - person user8426277; 20.06.2018
comment
@ user8426277 - потому что это динамический поток инструкций, который (в основном) имеет значение для переупорядочения. ЦП не выполняет call как отдельную инструкцию, а затем переходит к следующей инструкции в порядке источника / сборки, он переходит в тело функции pthread. Итак, для целей анализа вы можете представить себе, что все тело вызовов lock и unlock как бы встроено в сборку в том месте, где появляется инструкция call. Если бы это было не так, мьютексы и многие другие механизмы синхронизации было бы невозможно реализовать в виде простых вызовов функций! - person BeeOnRope; 20.06.2018
comment
@ user8426277 - Я обновил свой вопрос, чтобы было понятнее. Суть в том, что на уровне сборки вы не можете говорить о том, какие типы переупорядочения возможны при call, jmp или любом другом изменении потока управления, потому что вам нужно знать, что происходит в месте перехода. - person BeeOnRope; 20.06.2018
comment
x86 call выполняет хранилище релизов (подталкивает адрес возврата), поэтому, если вы хотите быть педантичным, call сам действительно имеет эффект. Но не больше, чем любые обычные хранилища внутри функции. Но да, очень хорошее обновление, я думаю, это может быть в основе того, чего не хватает OP. - person Peter Cordes; 20.06.2018
comment
@PeterCordes Я никогда не говорю, что call не имеет эффекта релиза, не так ли? Я говорю, что вам нужно знать, что находится внутри call, чтобы знать обо всем влиянии call на трассировку инструкций. Конечно, call сам может иметь некоторую семантику упорядочения, такую ​​как те, которые связаны с хранением в стеке, но это практически непригодно для использования и является IMO полным отвлекающим маневром (и другой ответ хорошо покрывает это: -). Обратите внимание, что при освобождении-получении говорится о местоположении: lock часть мьютекса не синхронизируется с push адресом возврата в другом потоке, поэтому этот выпуск не очень полезен. - person BeeOnRope; 20.06.2018
comment
Я просто имел в виду, что в ответ на вы не можете говорить о том, какие типы переупорядочения возможны в _1 _... во втором комментарии. Я не предлагаю вам чрезмерно усложнять этот ответ этим, потому что я уже делал это в своем: P Согласился, что это полная отвлекающая манера, и упорядочивающая память часть call совершенно не важна, потому что другие потоки не смотрят на ваш стек вызовов. - person Peter Cordes; 20.06.2018
comment
@PeterCordes - ну да, мне интересно, придет ли кто-нибудь и скажет что-то подобное, и я наполовину подумал о повышении цены, например, отметив, что сам call может предотвратить некоторые переупорядочения, но тело может затем предотвратить больше < / i> переупорядочивание. Тем не менее, я на самом деле не думаю, что имеет смысл говорить, что call имеет семантику выпуска (что, возможно, подразумевает, что вам не нужно хранить в стороне реализации unlock): release имеет смысл, когда говорит о конкретном местоположении, а в случае call это анонимное местоположение в стеке. - person BeeOnRope; 20.06.2018
comment
Ага, это хороший анализ того, почему это не имеет смысла или полезности. Не имеет значения, где находится хранилище call в глобальном порядке, просто хранятся вне критической секции по сравнению с блокировкой мьютекса или внутри. Я знал, что веду себя педантично, но не осознавал, насколько это бесполезно. Если мы говорим о части инструкций, не связанной с хранением, то это еще один вопрос о неправильном порядке выполнения и упорядочении памяти. - person Peter Cordes; 20.06.2018
comment
... потому что в каком смысле запрашивающая сторона (вызов lock) может синхронизироваться с магазином, подразумеваемым call? Я не думаю, что это возможно. Я не вижу, как можно полагаться на так называемую семантику выпуска магазина. [‹- эта часть моего комментария соперничала с вашим последним ответом]. Поэтому нам не следует думать о хранилищах релизов как о каком-то типе барьера памяти: размещение фиктивного хранилища с семантикой выпуска не дает ничего значимого. Это полезно только для чего-то, что потребляет его ценность, для установления типа отношений «случилось раньше» или как вы хотите об этом думать. - person BeeOnRope; 20.06.2018
comment
@BeeOnRope ЦП не выполняет вызов как одну инструкцию, а затем переходит к следующей инструкции в порядке источника / сборки, он переходит в тело функции pthread Я не имел в виду в мой вопрос в комментариях, что я думал, что ЦП выполнит pthread_mutex_lock(&lock);, а затем сразу после этого ЦП выполнит i = 10;, не переходя сначала к телу функции. Я имел в виду: что, если ЦП полностью проигнорирует pthread_mutex_lock(&lock); и вместо этого сначала выполнит i = 10;, а затем после этого ЦП выполнит pthread_mutex_lock(&lock);. - person user8426277; 22.06.2018
comment
@ user8426277 - правильно, я понял. Я же говорю, что ЦП не меняет порядок в листинге на уровне сборки. Вы представляете себе сборку типа call mutex_lock; store 10 to I; и спрашиваете, что произойдет, если ЦП переупорядочит хранилище до call? Ответ заключается в том, что это был неправильный взгляд на это с самого начала: ЦП не переупорядочивает статическую сборку, которую вы найдете на диске в двоичном файле, он работает с потоком dynamic. инструкций, поэтому вам нужно мысленно отследить выполнение и записать этот поток. - person BeeOnRope; 22.06.2018
comment
В этом случае результат прост: вы просто получаете инструкции, которые являются частью тела функций lock и unlock, заменяющих инструкцию вызова. Затем вы можете поговорить о переупорядочении по этому списку инструкций - это то, что я называю динамической трассировкой. - person BeeOnRope; 22.06.2018
comment
Ой! в этом случае, является ли цель барьера памяти внутри функции pthread_mutex_lock(&lock); - предотвратить переупорядочение i = 10; на код, который устанавливает / блокирует переменную мьютекса внутри функции pthread_mutex_lock(&lock);? - person user8426277; 22.06.2018
comment
@user - правильно. Как следствие, это также не позволяет ему полностью выйти за пределы функции блокировки. - person BeeOnRope; 22.06.2018

arrow_upward
6
arrow_downward

Если i и j - локальные переменные, ничего. Компилятор может хранить их в регистрах во время вызова функции, если он может доказать, что ничто за пределами текущей функции не имеет их адреса.

Но любые глобальные переменные или локальные переменные, адрес которых может храниться в глобальном, do должны быть "синхронизированы" в памяти для вызова не встроенной функции. Компилятор должен предполагать, что любой вызов функции, который он не может встроить, изменяет любую / каждую переменную, на которую он может ссылаться.

Так, например, если int i; - локальная переменная, после sscanf("0", "%d", &i); ее адрес будет ускользать от функции и компилятор затем должен будет пролить / перезагрузить его вокруг вызовов функций вместо того, чтобы хранить его в регистре с сохранением вызовов.

См. Мой ответ на Понимание изменчивой asm и изменчивой переменной, с пример того, что asm volatile("":::"memory") является барьером для локальной переменной, адрес которой экранирован функцией (sscanf("0", "%d", &i);), но не для локальных, которые все еще остаются чисто локальными. Это точно такое же поведение по той же причине.

Я предполагаю, что приведенная выше цитата говорит о переупорядочивании ЦП, а не о переупорядочении компилятора.

Речь идет о обоих, потому что оба необходимы для правильности.

Вот почему компилятор не может изменить порядок обновлений общих переменных с помощью любого вызова функции. (Это очень важно: слабая модель памяти C11 допускает много времени компиляции переупорядочивание. Сильная модель памяти x86 допускает только переупорядочивание StoreLoad и локальную пересылку хранилища.)

pthread_mutex_lock, будучи не встроенным вызовом функции, заботится о переупорядочении во время компиляции, и тот факт, что он выполняет операцию locked, атомарный RMW, также означает, что он включает полный барьер памяти во время выполнения на x86. (Но не сама инструкция call, а просто код в теле функции.) Это придает ей семантику.

Для разблокировки спин-блокировки требуется только хранилище релизов, а не RMW, поэтому в зависимости от деталей реализации функция разблокировки может не быть барьером StoreLoad. (Это все еще нормально: он предотвращает выпадение всего в критическом разделе. Нет необходимости останавливать появление последующих операций до разблокировки. См. Джефф Прешинг статья, объясняющая семантику получения и выпуска)

На слабо упорядоченном ISA эти функции мьютекса будут запускать инструкции барьера, такие как ARM dmb (барьер памяти данных). Обычные функции не работают, поэтому автор этого руководства прав, указывая на то, что эти функции являются особенными.

Теперь, что мешает ЦП переупорядочить mov 10 в i и mov 20 в j, чтобы было выше call pthread_mutex_lock()

Это не важная причина (потому что на ISA со слабым упорядочением pthread_mutex_unlock будет запускать инструкцию барьера), но на самом деле это правда на x86, что хранилища нельзя даже переупорядочить с помощью инструкции call не говоря уже о фактической блокировке / разблокировке мьютекса, выполняемой телом функции перед возвратом функции.

x86 имеет строгую семантику упорядочивания памяти (хранилища не меняют порядок с другими хранилищами), а call - хранилище (отправка адреса возврата).

Таким образом, mov [i], 10 должен появиться в глобальном хранилище между хранилищами, выполняемыми инструкцией call.

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

person Peter Cordes    schedule 20.06.2018
comment
Вызов функции, не являющейся встроенным, не обязательно, чтобы предотвратить переупорядочение во время компиляции во время вызова. Например, если единица трансляции имеет статические переменные файловой области, и компилятор может доказать, что их адреса недоступны для вызова, тогда компилятор может изменить порядок доступа к этим переменным во время вызова, даже если эти переменные могут получить доступ более чем к одному потоку. - person Arch D. Robison; 22.06.2018
comment
@ ArchD.Robison: Компилятор может доказать, что только если единственные функции, которые касаются static var, сами являются static, а не вызываются из каких-либо функций, отличных от static, и не имеют адреса функции, переданной ни одной функции черного ящика. В противном случае он должен предположить, что неизвестная функция может вызвать обратно в эту единицу трансляции, чтобы в конечном итоге достичь функции, которая читает или записывает статическую переменную. Функции создания потоков и обработчиков сигналов представляют собой черный ящик, поэтому невозможно запустить другой поток, выполняющий функцию static, без доступа к статической переменной var, выходящей из единицы трансляции. - person Peter Cordes; 22.06.2018
comment
@PeterCordes Если у вас есть набор переменных V, которыми манипулируют только функции F1, которые вызываются только набором функций F2, и ни одна из них не может быть названа вне TU, и никакая другая функция внутри TU не принимает адрес, чтобы поместить ее в объект, доступный где-то еще ... в конце концов, V, F1, F2 ... вообще бесполезны. - person curiousguy; 24.06.2018
comment
@ ArchD.Robison Предположительно, в реальной программе статические переменные могут быть косвенно доступны из main. - person curiousguy; 24.06.2018
comment
@curiousguy: Хорошее замечание. Если это TU, содержащий main, то, возможно, компилятор сможет доказать, что эти переменные могут использоваться только основным потоком (если он оптимизирован на основе UB для повторного вызова main изнутри программы). Я не думаю, что есть случаи, когда вызов функции, не являющейся встроенной, может не упорядочить какие-либо переменные, которые фактически используются совместно. - person Peter Cordes; 24.06.2018
comment
Я согласен с анализом @PeterCordes. Я забыл рассмотреть возможность обратного звонка. - person Arch D. Robison; 25.06.2018
comment
если он сможет доказать, что ничто за пределами текущей функции не имеет своего адреса. Есть ли для этого название? Функция частных переменных? - person curiousguy; 04.11.2019
comment
@curiousguy: en.wikipedia.org/wiki/Escape_analysis - это название проверки. Я не знаю широко распространенного названия переменных, отвечающих этим критериям. Я бы сказал, что переменная не ускользнула. - person Peter Cordes; 04.11.2019