Синхронизация, многопоточность

Тема в разделе "WASM.ZEN", создана пользователем Mika0x65, 1 ноя 2010.

  1. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Мое почтение всем.

    Читаю сейчас одну книгу, в ней есть пример синхронизации нескольких потоков. Требуется дождаться, пока все потоки (их число известно) начнут выполняться. Код основного потока:

    Код (Text):
    1. nOtherCPUs = KeNumberProcessors - 1;
    2. InterlockedCompareExchange(&nCPUsLocked, nOtherCPUs, OtherCPUs);
    3. while(nCPUsLocked != nOtherCPUs)
    4. {
    5.     InterlockedCompareExchange(&nCPUsLocked, nOtherCPUs, nOtherCPUs);
    6. }
    Каждый поток, который нас интересует делает 'InterlockedIncrement(&ncPUslocked);'.

    Вопрос: а нужна ли ф-ия InterlockedCompareExchange в этом случае? Ведь InterlockedIncrement сделает LOCK, соответственно, пока запись в nCPUsLocked не завершится, основной поток не сможет прочитать значение переменной. Или я не прав?
     
  2. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Почему не может прочитать? Interlocked функции не усыпляют потоки, они синхронизируют доступ к ресурсу.
     
  3. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Речь не идет про успыление. Допустим, поток выполняет 'lock add [nCPUsLocked], 1', в этот момент основной поток выполняет 'cmp dword [nCPUsLocked], 2'. LOCK нужен для того, чтобы заблокировать шину на все время выполнения инструкции 'add', т.к. она (в зависимости от адреса и размера переменной) может записывать данные в память частями. leo, наверное, плевался бы от такого объяснения, но это как я себе представляю. По приведенному выше коду получается, что чтение переменной тоже сделано с префиксом LOCK. Вопрос в том, нужен ли он там? Я бы сократил код так:
    Код (Text):
    1. nOtherCPUs = KeNumberProcessors - 1;
    2. while(nCPUsLocked != nOtherCPUs)
    3.     ;
    Т.е. мне кажется, что LOCK'а при записи значения переменной достаточно.
     
  4. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Предположим что запись происходит частями, но тогда и чтение тоже может происходить частями.
     
  5. onSide

    onSide New Member

    Публикаций:
    0
    Регистрация:
    18 июн 2008
    Сообщения:
    476
    Чтение и запись (разрдность шины данных)-бит всегда атомарны.
    В данном случае это скорее хороший тон + в целях обучения. Потому что у InterlockedCompareExchange 2 и 3 параметры одинаковые. Следовательно она не производит изменение данных. Если бы параметры были разные, надо было всегда юзать InterlockedCompareExchange. Ее легче юзать, чтобы потом при поддержке не было гемора, вдруг вам потребуется изменить эти значения.
     
  6. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    onSide
    Не уверен что всегда так. На x86 да, на alpha как известно генерится исключение при доступе к невыровненной памяти и там иногда нужно читать двойным и более заходами, да и как схитрится компилятор тоже не понятно.
     
  7. onSide

    onSide New Member

    Публикаций:
    0
    Регистрация:
    18 июн 2008
    Сообщения:
    476
    Booster
    Ну да, на других архитектурах всякое может быть, я за х86 говорил)
     
  8. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    [deleted]
     
  9. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Booster
    Да. И одного LOCK при записи с моей т.з. будет достаточно, чтобы избежать ситуации, когда чтение прочитает часть записанной переменной. Но все же хочется уточнить.

    l_inc
    Не совсем так. Барьер остался немного за пределами описания: суть в том, что пока все потоки не известят о себе, выполнение основного потока не продолжается -- он вертится в spinlock'е.

    Понятно, что происходит как чтение, так и запись. А производительность все же страдает: из-за лишнего(?) LOCK в цикле шина будет занята почем зря, что сказывается не очень хорошо (Таненбаум, кстати, об это писал).

    А насчет сериализации собственно и вопрос: LOCK критически необходим при чтении или нет? Лишний раз блокировать шину тоже не хочется. Интересуюсь в принципе (это не конкретная задача), чтобы знать, нужен LOCK или нет. Эх, leo бы сюда...
     
  10. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    onSide
    По-моему данная проблема может быть и на x86. Так как процессор может читать невыровненную память в несколько заходов, то несколько процессоров могут и писать и читать в несколько заходов одновременно. На однопроцессорной машине конечно всё проще.
     
  11. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Mika0x65
    Interlocked функции это нечто большее чем просто LOCK, так как они и читают и записывают. Но в принципе если у вас память выровнена, то можете спокойно читать int, на уровне контроллера памяти одиночные запросы чтения/записи атомарны.
     
  12. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Mika0x65
    The LOCK prefix can be prepended only to the following instructions and only to those
    forms of the instructions where the destination operand is a memory operand: ADD,
    ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB,
    SUB, XOR, XADD, and XCHG. If the LOCK prefix is used with one of these instructions
    and the source operand is a memory operand, an undefined opcode exception (#UD)
    may be generated. An undefined opcode exception will also be generated if the LOCK
    prefix is used with any instruction not in the above list. The XCHG instruction always
    asserts the LOCK# signal regardless of the presence or absence of the LOCK prefix.
    The LOCK prefix is typically used with the BTS instruction to perform a read-modifywrite
    operation on a memory location in shared memory environment.
    The integrity of the LOCK prefix is not affected by the alignment of the memory field.
    Memory locking is observed for arbitrarily misaligned fields.
     
  13. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    x86 гарантирует атомарность выполнения команды mov для выравненных данных. Соотв-но префикс LOCK используется только для команд, которые должны одновременно выполнять чтение и запись операнда, а для команд, выполняющих только чтение (включая cmp, test и любые команды типа add r,m в которых память является источником, а не приемником) префикс LOCK не применим.
    Резюме - для гарантии атомарности чтения переменной достаточно обеспечить выравнивание ее адреса (причем высоокуровневые компиляторы делают это автоматом, если конечно им не мешать своими опциями выравнивания)
     
  14. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    Black_mirror
    leo
    Что-то вас немного не туда понесло. Я знаю, что LOCK можно добавлять только к некоторым инструкциям и что для выравненных данных операция происходит атомарно. Однако раз пошла такая пьянка, задам еще один вопрос: для операции read-modify-write по выравненному адресу LOCK тоже не требуется? Поясню ситуацию на примере: два ядра (или процессора) одновременно выполняют 'inc dword [0]'. Может ли создаться ситуация, когда ядро0 делает read(атомарно), затем ядро1 делает read(атомарно), затем оба ядра увеличивают значение на единицу и по-очереди атомарно записывают результат в память? Т.е. значение после двух инструкций 'inc' на разных ядрах увеличивается только на единицу? Т.е. для read-modify-write атомарность поддерживается на все время выполнения инструкции или только для операций read/write?

    И вернемся к исходному вопросу. Немного переформулирую его: при условии, когда на одном ядре происходит запись данных с префиксом LOCK, а на другом ядре в этот же момент происходит происходит чтение этих же данных, нужен ли префикс LOCK для чтения? Или достаточно одного LOCK'а при записи данных и второе ядро будет смиренно ждать, пока первое не завершит операцию? И будет ли нормально работать мое изменение кода:
    Код (Text):
    1. nOtherCPUs = KeNumberProcessors - 1;
    2. while(nCPUsLocked != nOtherCPUs)
    3.     ;
    ?
     
  15. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Mika0x65
    Это тебя не туда понесло :)
    Тебе и по русски и по аглицки объяснили, что по отдельности операции чтения и записи (выравненных операндов) атомарны, а любые связки типа read-modify-write ес-но не атомарны, т.к. состоят из отдельных микроопераций чтения и записи, поэтому для таких связок и нужен LOCK, который захватывает шину и запрещает другим потокам читать\изменять переменную, пока данная связка не выполнится целиком.
    Т.е. при одновременном выполнении на двух ядрах операции inc без префикса lock возможна ситуация, когда в итоге переменная изменится только на 1, а не на 2 как положено, а с префиксом - невозможна

    Перечитай #12 - он не просто не нужен, а невозможен\невалиден\ошибочен для операций чистого чтения или чистой записи.
    Если же один из потоков выполняет валидную locked-операцию, например, lock inc = InterlockedIncrement, то на время ее выполнения происходит захват шины и другие ядра не могут ничего ни записать, ни прочитать пока не произойдет разблокировка.

    Простое же чтение\проверка nCPUsLocked как в #14 по любому безопасны независимо от того, как производится запись в эту переменную (т.е. lock нужен именно для безопасного инкремента переменной из разных потоков, а простое чтение по любому производится атомарно и соотв-но никаих искажений тут быть не может - либо прочитаешь значение до инкремента, либо после него)
     
  16. Mika0x65

    Mika0x65 New Member

    Публикаций:
    0
    Регистрация:
    30 июл 2005
    Сообщения:
    1.384
    leo
    Из #12 не следует, что связки read-modify-write без LOCK не атомарны. Ну или я плохо намеки понимаю :). Насчет #13 я только сейчас понял: я не рассматривал 'add m, r' как read-modify-write.

    Я вовсе не собирался лепить LOCK инструкции 'mov', например. Вопрос был в том, надо ли использовать cmpxchg (или какую-нибудь LOCKable инструкцию) для чтения или достаточно 'cmp/test/etc'. Как я теперь понимаю, достаточно.
    Вот здесь хочется уточнить. Допустим, у нас два ядра, одно делает 'mov m, r', другое 'mov r, m' на один и тот же невыравненный адрес. Как я себе представлял раньше, запись в этом случае разобьется на несколько циклов шины, и может происходить, например, побайтово. Т.е. возможна ситуация:

    1. Цикл шины пишет старший байт dword'а в m.
    2. Цикл шины считывает старший байт dword'а.
    3. Цикл шины считывает второй байт dword'а.
    4. Цикл шины считывает первый байт dword'а.
    5. Цикл шины считывает нулевой байт dword'а.
    6. Несколько циклов шины дописывают остальные байты dword'а.

    В результате имеем некорректное значение r после операции 'mov r, m'. Но, получается,
    что такая ситуация невозможна?

    Небольшой итог: префикс LOCK нужен для совместных операций read-modify-write и не обязателен для операций типа read-modify-write/read и read-modify-write/write (в случае, когда read/write цикличны).
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Mika0x65
    Невозможна такая ситуация. Одинарный доступ к памяти будет разбиваться на две части там, где он пересекает границу кэша.

    Честно говоря, я тоже так и не увидел ответа. И мне тоже кажется, что leo и Black_mirror не на тот вопрос отвечают. Так что в принципе я присоединяюсь к вопросу о том, зачем в приведенном коде используется вызов InterlockedCompareExchange. Насколько я понимаю, этим достигается не более, чем сериализация доступа на чтение с точки зрения всех процессоров. Но зачем?
     
  18. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    l_inc
    Потому-что это более общий подход, не зависящий от архитектуры и внутренних особенностей. В реале он не обязателен.
     
  19. onSide

    onSide New Member

    Публикаций:
    0
    Регистрация:
    18 июн 2008
    Сообщения:
    476
    Я вроде в #5 все написал)
     
  20. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    onSide
    Вы также написали, что доступ к памяти на x86 всегда атомарен, что, прошу прощения, значительно снизило мою оценку достоверности выданной Вами информации. :)

    Booster
    Если этой версии будет больше подтверждений, придётся её принять.