Если операция записи происходит во время монопольного доступа к кешу, почему происходит гонка данных?

Я читал о протоколе MESI и не могу понять, почему возникает гонка за данные, если у нас есть монопольный доступ к каждой операции записи, что, следовательно, делает недействительными строки кеша в кешах других ядер? в этом примере:

CYCLE # CORE 1                        CORE 2
0   reg = load(&counter);   
1   reg = reg + 1;                reg = load(&counter);
2   store(&counter, reg);         reg = reg + 1;
3                                 store(&counter, reg);

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


x86-64 instructions cpu atomic mesi
person shota silagadze    schedule 29.04.2019    source источник
comment
Вы путаете C ++ и оборудование с MESI. C ++ не имеет MESI. В нем говорится, что гонки данных - это UB. Аппаратное обеспечение может иметь MESI, а гонка данных может иметь определенное поведение. Это все еще UB в C ++, даже если он скомпилирован для этой платформы.   -  person nwp    schedule 29.04.2019
comment
Я упрощу вопрос: в моем понимании, учитывая протокол MESI на аппаратном уровне, не существует цепочки событий, которая привела бы к увеличению переменной всего на 1. Можете ли вы сказать мне, как это может произойти, если операция увеличения (записи) на оборудовании выполняется во время монопольного доступа к строке кэша? Таким образом, если одно ядро ​​увеличивает переменную, оно делает недействительным значение для кеша другого ядра, и это ядро ​​будет увеличивать только что полученное значение (то есть 1), и в конце мы должны получить значение 2   -  person shota silagadze    schedule 29.04.2019
comment
Я недостаточно знаю вашу платформу, чтобы ответить на этот вопрос, но могу сказать, что вам следует удалить тег C ++, потому что он не имеет ничего общего с C ++. Вероятно, вам придется более подробно указать платформу, например x86, прежде чем вы получите ответ, который не зависит от него.   -  person nwp    schedule 29.04.2019
comment
Гонка за данными - это концепция модели памяти C / C ++. Существует общий запрет для программиста и универсальное разрешение для реализации C / C ++ предполагать, что обычные объекты не изменяются под его носом другими потоками (или обработчиками сигналов). . Гонки не вызывают плохого поведения на уровне процессора. (В Java нет такого общего запрета, допустимые программы могут иметь гонку данных, но на поведение таких программ может повлиять юридическая оптимизация.)   -  person curiousguy    schedule 01.05.2019
comment
нет цепочки событий, которая привела бы к увеличению переменной всего на 1. Итак, у вас действительно есть вопрос о возможном состоянии гонки, а не о гонке данных. В C / C ++ одновременные модификации атомарных объектов могут иметь состояние гонки, но не создают гонку данных. Любая конфликтующая модификация чего-либо может создать состояние гонки. У вас есть состояние гонки, когда один процесс переименовывает файл в каталоге D, а другой перечисляет D и открывает файлы. У вас может быть состояние гонки, когда вы выполняете несколько независимых SQL-запросов, если база данных также изменена другим клиентом.   -  person curiousguy    schedule 01.05.2019
comment
Не могли бы вы перефразировать свой вопрос, чтобы избежать запутанной гонки данных, и выразить это исключительно в терминах атомарности операции чтения-изменения-записи?   -  person curiousguy    schedule 01.05.2019

Ответы (1)


arrow_upward
4
arrow_downward

Если я правильно понял, MESI здесь просто отвлекающий маневр:

0   reg = load(&counter);

counter теперь загружен в регистр ЦП.

1   reg = reg + 1;                reg = load(&counter);

Первый процессор увеличил значение, второй загрузил старое.

2   store(&counter, reg);         reg = reg + 1;

Первый процессор сохраняет значение, второй увеличивает его устаревшее.

3                                 store(&counter, reg);

Второй процессор сохраняет результат расчета на основе устаревшего значения.

Пока должно быть ясно. Теперь, как это изменится, если добавление состояний MESI:

0   reg = load(&counter);

counter находится в кэше ЦП 1, помеченном как E.

1   reg = reg + 1;                reg = load(&counter);

counter по-прежнему находится в кэше ЦП 1, но также загружается в кэш ЦП 2. Поэтому обе строки кеша необходимо пометить как S.

2   store(&counter, reg);         reg = reg + 1;

Теперь counter сохраняется в кеше. Таким образом, кэш ЦП 1 должен быть помечен как M, а кэш ЦП 2 становится недействительным (помечен как I).

3                                 store(&counter, reg);

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

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

Добавим заключительную деталь: после операции кэш ЦП 2 будет помечен как M, а кэш ЦП 1 I.

person Aconcagua    schedule 29.04.2019
comment
Спасибо, я понял, я не помнил, что во время признания недействительным переменная могла быть в регистре и, следовательно, не была аннулирована и там. Итак, насколько я понимаю, MESI не касается согласованности данных в программе, а только между кешами процессора и порядком вещей, верно? - person shota silagadze; 29.04.2019
comment
@shotasilagadze: согласованные кеши не превращают отдельные операции чтения + добавления + записи в атомарное приращение RMW. Но это означает, что два разных потока не могут долгое время читать разные значения одной и той же переменной. Также: Будут ли две атомные записи в разные места в разных потоках всегда отображаться в одном порядке другими потоками? - изменение порядка IRIW, когда 2 читателя не согласны в порядке сохранения из двух других потоков обычно не может происходить только с MESI, только если некоторые потоки могут видеть хранилища до того, как они станут видимыми глобально. - person Peter Cordes; 29.04.2019
comment
@shotasilagadze: но гораздо проще, наличие буфера хранилища (например, модель памяти x86 TSO) означает, что поток может видеть свои собственные хранилища, прежде чем они станут глобально видимыми, поэтому preshing.com/20120515/memory-reordering-caught-in-the-act - person Peter Cordes; 29.04.2019