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

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

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

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

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

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

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

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

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

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

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

while (target != value) target = value;

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

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

Я хотел бы легко найти свою копию, чтобы обобщить содержание.

Вы можете предотвратить это, используя атомарные инструкции, такие как 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

 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

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