Что произойдет, если два процесса в разных процессорах попытаются получить блокировку ровно в одно и то же время
Итак, я читаю о синхронизации и читаю различные алгоритмы, такие как спин-блокировки, семафоры и мьютексы, чтобы избежать состояния гонки.
Однако эти алгоритмы не могут предотвратить состояние гонки в SMP, когда множественные процессы обращаются к данным в одно и то же время.
Например, предположим, что поток 1 в процессоре A выполняет блокировку (mutex1); отзывать (1000); разблокировать (mutex1);
и поток 2 в процессоре B выполняет блокировку (mutex1); депозит (1000); депозит (1000); разблокировать (mutex1);
Когда оба потока работают точно в одно и то же время, оба потока будут одновременно находиться в критической секции.
Единственное решение (должно быть на аппаратном уровне) состояло бы в том, чтобы каждый процессор работал немного в стороне друг от друга, но это противоречит цели параллелизма.
Есть ли какая-либо поддержка на аппаратном уровне, чтобы избежать такой ситуации, когда несколько процессоров пытаются получить блокировку в одно и то же время?
(это не проблема атомарности, а проблема точного параллелизма, и мне интересно, как SMP справляется с этим).
5 ответов
Весь смысл мьютекса в том, что даже если два ядра попытаются получить его одновременно, одно из них будет заблокировано, пока другое не освободит его. Мьютекс, который позволял двум ядрам одновременно удерживать этот мьютекс, был бы полностью сломан и бесполезен для его единственной цели.
Где-то в аппаратном обеспечении есть арбитр шины, который позволяет только одному ядру управлять шиной, которая связывает эти два ядра. Если у любого из ядер уже есть память, хранящая мьютекс в частном кэше, это ядро победит. В противном случае, какой бы автобус ни получил первым, победит.
Арбитр шины может работать разными способами, но обычно он будет вращаться. Таким образом, если ядра имеют значения 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®-системы Curt Schimmel для современных архитектур: симметричная многопроцессорная обработка и кэширование для программистов ядра. Разные аппаратные архитектуры предоставляют разные низкоуровневые инструменты для синхронизации доступа к данным, в том числе некоторые архитектуры практически без посторонней помощи. Книга Шиммеля предлагает алгоритмы, которые могут работать даже на этих архитектурах.
Я хотел бы легко найти свою копию, чтобы подвести итог содержания.
Вы можете предотвратить это, используя атомарные инструкции, такие как 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
Это классическая тупиковая проблема. Я не уверен насчет аппаратной поддержки (но я почти уверен, что она поддерживается на аппаратном уровне), однако, я могу привести пример решения проблемы взаимоблокировки в базах данных. Если вы знаете все зависимости, которые вы знаете, какую зависимость нужно "убить", таким образом, команды данного узла не будут работать, но система победит тупик, а другие узлы не выйдут из строя. Я думаю, что тот же подход должен быть на аппаратном уровне.