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

Question

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

Однако эти алгоритмы не могут предотвратить состояние гонки в SMP, когдамножественные процессы обращаются к данным в одно и то же время.

Например, предположим, что поток 1 в процессоре A выполняет блокировку (mutex1);отзывать (1000);разблокировать (mutex1);

и поток 2 в процессоре B запускает блокировку (mutex1);депозит (1000);депозит (1000);unlock (mutex1);

Когда оба потока работают ТОЧНО В ТО ЖЕ ВРЕМЯ, оба потока будут одновременно находиться в критической секции.

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

Существует ли какая-либо поддержка на аппаратном уровне, чтобы избежать такой ситуации, когда несколько процессоров пытаются получить блокировку в одно и то же время?

(это не проблема атомарности, а проблема точного параллелизма, и мне интересно, как SMP справляется с этим).

Answer 1

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

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

Арбитр шины может работать разными способами, но обычно он вращается.Таким образом, если ядра имеют значения 0, 1, 2 и 3, а ядро ​​2 имеет последнюю шину, то шина затем перейдет к ядру 3, если оно этого захочет, в противном случае ядро ​​0, если оно этого захочет, или ядро ​​1, если оно этого захочет,в противном случае вернемся к ядру 2. В зависимости от того, какая именно шина задействована (будь то битва между L2-кэш-памятью двух ядер или за саму память или что-то в этом роде), некоторые ядра могут конкурировать как единое целое с другими группами ядер, а затем подчиняться.для которого конкретное ядро ​​получает его первым.

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

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

Answer 2

Возможно, вы захотите взглянуть на барьеры памяти.

http://en.wikipedia.org/wiki/Memory_barrier

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

Некоторые архитектуры также допускают блокировку всех ядер, кроме 1, чтобы учесть это.Например, x86 имеет префикс LOCK, который при добавлении к инструкциям блокирует доступ к памяти во время этой инструкции.(например: LOCK ADD EAX, 1 для атомарного приращения в регистр)

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

while (target != value) target = value;

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

Answer 3

Я настоятельно рекомендую UNIX®-системы Курта Шиммеля для современных архитектур: симметричная многопроцессорная обработка и кэширование для программистов ядра .Разные аппаратные архитектуры предоставляют разные низкоуровневые инструменты для синхронизации доступа к данным, в том числе некоторые архитектуры с почти нет помощью.Книга Шиммеля содержит алгоритмы, которые могут работать даже на этих архитектурах.

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

Answer 4

Вы можете предотвратить это, используя атомарные инструкции, такие как TLS и XCHG.

Как обеспечить атомарность инструкции?

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

Итак, если вы внедрите семафоры с помощью этих инструкций, у вас не возникнет проблем с SMP.

Реализация mutex_lock и mutex_unlock с использованием TSL:

 mutex_lock:
    TSL REGISTER, MUTEX ; copy mutex to register and sets mutex
    CMP REGISTER, #0    ; compare mutex to zero
    JZE ok              ; if zero return
    CALL thread_yield   ; else: mutex is busy, schedule another thread
    JMP mutex_lock      ; try again later
 ok: RET

 mutex_unlock:
    MOVE MUTEX,#0       ; free mutex
    RET

Вы можетенемного информации о TSL можно найти здесь: http://en.wikipedia.org/wiki/Test-and-set

Хорошая книга, которая может вам помочь: http://www.amazon.com/Modern-Operating-Systems-Andrew-Tanenbaum/dp/0136006639/ref=sr_1_sc_1?ie=UTF8&qid=1319333818&sr=8-1-spell

Answer 5

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