Несинхронизированный доступ к памяти и многопоточная гонка?

Question

[Mercury13]

Здравствуйте. Программа (точнее, хорошо отлаженная её часть) недавно продемонстрировала гонку. Намеренно повторить не удалось — вероятно, глюк очень редкий. В связи с этим вопрос.


Сложное вычисление разбивается между несколькими процессорами. Для ускорения работы используется несинхронизированный кэш (грубо говоря, массив double'ов) с такой логикой.

double &x = кэш[i];<br/>
if (isnan(x)) then кэш[i]=вычислить(i);<br/>
return x;<br/>

Возможны ли многопоточные гонки при параллельном чтении и записи double'а в одну и ту же ячейку? Как лучше ошибку обойти?

Comments

[Mercury13]

Архитектура x86 (32-битная). Конкретно процессор — AMD Phenom x4. Выравнивание стандартное — скажем, 4 байта. Считаем, что функция «вычислить» реентарабельна (по крайней мере, так должно быть в идеале — она ничего не пишет, только делает что-то из r/o входных данных). Двойная блокировка тут непригодна, надежда только на атомарность, и мой вопрос как раз в этом: а насколько атомарны операции «записать double» и «считать double»?

А с кодом чуть-чуть ошибся, но вроде нефатально:

double &x = кэш[i];
if (isnan(x)) x=вычислить(i);
return x;


[VenomBlood]

Если 4 байта — то неатомарны.

[VenomBlood]

Точнее если 4 байта, то (по крайней мере на intel, что пишет amd — надо искать) атомарность не гарантируется. Блокируйте шину, если не можете обеспечить 8байт выравнивание, или используйте примитивы компилятора, обеспечивающие атомарные действия.

[VenomBlood]

Если, конечно, компилятор их имеет.

Answer 1

[VenomBlood]

Касательно представленного куска:
Вопервых — надо понять, являются ли в вашем случае операции манипулирования double — атомарными с заблокированной шиной, для этого нужно знать архитектуру процессора, на котором все это пускается и видеть дизассембл представленного кода.
Во вторых надо убедиться в том, что сама функция вычислить(...) — является реентерабельной.
В третих — с чего вы вообще взяли что это гонка?

Исходя из представленного кода — можно только предложить обернуть его в double checked locking, но вообще то, что оно до сих пор не обернуто говорит или о том, что первые два пункта уже проделаны (что сомнительно, ибо в таком случае понятно, что в представленном коде нет гонки), или о том, что нифига этот код ни «хорошо отлаженный».

Answer 2

[TheHorse]

Могу посоветовать модернизацию:

double &x = кэш[i];
if (isnan(x)) then
{
кэш[i]=1; // чтоб зазря для одного i много потоков не делали вычислить(i);
кэш[i]=вычислить(i);
}
return x;

А по поводу гонок — в чем проявилась гонка? Присваивание и чтение вроде как атомарные операции…

Comments

[VenomBlood]

Плохо, плохо, очень плохо! Если поток потеряет квант после выполнения кэш[i]=1, и получивший управление поток обратится к тому-же элементу кеша — будет попа.
Чтобы небыло лишних вычислений и была безопасность — нужно делать double checked locking.

[TheHorse]

— будет попа. в чем-же попа? управляющий поток поймет, что кеш занят и нет смысла на нем останавливатся и пойдет себе куда шел.

[TheHorse]

*останавливаться

[VenomBlood]

Какой-какой поток? Исходя из вопроса там все потоки, производящие вычисления — равноправны. И более того — как это он поймет, что кеш занят? И еще более того — кеш то не занят, занят один элемент из кеша.

[TheHorse]

управляющий поток — сори, термин не верный. Поток который получил управление.
кэш[i]=1 — чтобы любой другой поток не стал считать вычислить(i) для этого i.
Поймет он это потому, что isnan(x) — будет false. без этого множество потоков полезут
в один и тот-же i т.к. isnan(x) — будет true т.к. записи в кеш[i] не будет т.к. она будет
только после длинной вычислить(i).
Так почему там будет попа, объесните, не понимаю.

[VenomBlood]

Объясняю.
Поток1: кэш[k] = 1;
Поток2: isnan(x) // false, x == 1
Поток2: return 1;
…
Поток1: кэш[k] = вычислить(k) // Допустим кэш[k] == 10
Поток1: return 10

И получается что второй поток вернул чушь, данные с потолка, называйте как хотите, в лучшем случае — приложение упадет, в худшем — вычисления будут неверны.

[TheHorse]

Ох, блин, только заметил, что там return… виновен по всем статьям.
Нужен больший кусок кода чтоб мыслить…

Answer 3

[lesha_penguin]

Если данные невыровненны, то могут быть любые фокусы, атомарность не гарантируется.