Почему код, изменяющий общую переменную между потоками, по-видимому, НЕ страдает от состояния гонки?

107

Я использую Cygwin GCC и запускаю этот код:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

unsigned u = 0;

void foo()
{
    u++;
}

int main()
{
    vector<thread> threads;
    for(int i = 0; i < 1000; i++) {
        threads.push_back (thread (foo));
    }
    for (auto& t : threads) t.join();

    cout << u << endl;
    return 0;
}

Собран с линии: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Он печатает 1000, что правильно. Однако я ожидал меньшего числа из-за того, что потоки перезаписывают ранее увеличенное значение. Почему этот код не страдает от взаимного доступа?

Моя тестовая машина имеет 4 ядра, и я не накладываю ограничений на программу, о которой я знаю.

Проблема сохраняется при замене содержимого общего доступа fooчем-то более сложным, например

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
мафу
источник
66
У процессоров Intel есть удивительная внутренняя логика «сбивания» для сохранения совместимости с очень ранними процессорами x86, используемыми в системах SMP (например, в машинах с двумя Pentium Pro). Многие условия отказа, которые, как нас учат, возможны, на машинах x86 практически никогда не происходят. Скажем, ядро ​​возвращается для записи uв память. ЦП на самом деле будет делать удивительные вещи, например, замечать, что строка памяти для uне находится в кеше ЦП, и перезапускает операцию увеличения. Вот почему переход от x86 к другим архитектурам может открыть глаза!
Дэвид Шварц
1
Может, все еще слишком быстро. Вам нужно добавить код, чтобы гарантировать, что поток уступит, прежде чем он что-либо сделает, чтобы гарантировать, что другие потоки будут запущены до его завершения.
Rob K
1
Как уже отмечалось, код потока настолько короткий, что его вполне можно выполнить до того, как следующий поток будет поставлен в очередь. Как насчет 10 потоков, которые помещают u ++ в цикл из 100 подсчетов. И небольшая задержка до начала цикла (или глобальный флаг «go», чтобы запустить их все одновременно)
RufusVS
5
Фактически, многократное порождение программы в цикле в конечном итоге показывает, что она ломается: что-то вроде while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;вывода 999 или 998 в моей системе.
Daniel Kamil

Ответы:

266

foo()настолько короток, что каждый поток, вероятно, заканчивается еще до того, как будет создан следующий. Если вы добавите сон на случайное время foo()до u++, вы можете начать видеть то, что ожидаете.

Роб К
источник
51
Это действительно изменило результат ожидаемым образом.
mafu
49
Отмечу, что это в целом неплохая стратегия для выставления гоночных условий. Вы должны иметь возможность вставлять паузу между любыми двумя операциями; если нет, то есть состояние гонки.
Matthieu M.
Недавно у нас была именно эта проблема с C #. Код обычно почти никогда не дает сбоев, но недавнее добавление промежуточного вызова API внесло достаточную задержку, чтобы заставить его постоянно меняться.
Obsidian Phoenix
@MatthieuM. Разве у Microsoft нет автоматизированного инструмента, который делает именно это, как метода обнаружения состояний гонки и обеспечения их надежной воспроизводимости?
Мейсон Уиллер
1
@MasonWheeler: Я почти работаю исключительно на Linux, так что ... не знаю :(
Matthieu M.
59

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

В частности, на машинах X86 и AMD64 условия гонки в некоторых случаях редко вызывают проблемы, поскольку многие инструкции являются атомарными, а гарантии согласованности очень высоки. Эти гарантии несколько снижаются в многопроцессорных системах, где префикс блокировки необходим для того, чтобы многие инструкции были атомарными.

Если на вашем компьютере инкремент является атомарной операцией, он, скорее всего, будет работать правильно, даже если в соответствии со стандартом языка это Undefined Behavior.

В частности, я ожидаю, что в этом случае код может быть скомпилирован для атомарной выборки и добавления инструкцию (ADD или XADD в сборке X86), которая действительно является атомарной в однопроцессорных системах, однако в многопроцессорных системах не гарантируется, что она будет атомарной, а блокировка потребуется сделать это так. Если вы работаете в многопроцессорной системе, появится окно, в котором потоки могут вмешиваться и давать неверные результаты.

В частности, я скомпилировал ваш код в сборку с помощью https://godbolt.org/ и foo()компилировал в:

foo():
        add     DWORD PTR u[rip], 1
        ret

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

Валити
источник
41
Важно помнить, что «работа по назначению» - это допустимый результат неопределенного поведения.
Марк
3
Как вы указали, эта инструкция не является атомарной на SMP-машине (а это все современные системы). Даже inc [u]не атомарно. LOCKПрефикс требуется , чтобы сделать инструкции действительно атомарной. OP просто везет. Напомним, что даже если вы говорите ЦП «добавить 1 к слову по этому адресу», ЦП все равно должен извлекать, увеличивать, сохранять это значение, а другой ЦП может делать то же самое одновременно, в результате чего результат будет неверным.
Джонатон Рейнхарт,
2
Я проголосовал против, но затем я перечитал ваш вопрос и понял, что ваши утверждения атомарности предполагают использование одного процессора. Если вы отредактируете свой вопрос, чтобы прояснить его (когда вы говорите «атомарный», дайте ясно понять, что это только в случае одного процессора), то я смогу снять свое голосование против.
Джонатон Рейнхарт
3
Проголосовали против, я нахожу это утверждение немного неуместным: «Особенно на машинах X86 и AMD64 условия гонки в некоторых случаях редко вызывают проблемы, поскольку многие инструкции являются атомарными, а гарантии согласованности очень высоки». Абзац должен начинаться с явного предположения, что вы фокусируетесь на одном ядре. Несмотря на это, многоядерные архитектуры в настоящее время де-факто являются стандартом для потребительских устройств, и я бы счел это крайним случаем, чтобы объяснить последнее, а не первое.
Патрик
3
О, определенно. x86 имеет массу возможностей обратной совместимости ... чтобы убедиться, что неправильно написанный код работает в максимально возможной степени. Когда Pentium Pro представил исполнение вне очереди, это было действительно большим событием. Intel хотела убедиться, что установленная база кода работает без необходимости перекомпиляции специально для их нового чипа. x86 начинался как ядро ​​CISC, но внутренне превратился в ядро ​​RISC, хотя с точки зрения программиста он все еще представляет и ведет себя во многих отношениях как CISC. Для получения дополнительной информации см. Ответ Питера Кордеса здесь .
Коди Грей
20

Я думаю, дело не в том, если вы заснете до или после u++. Скорее, операция u++преобразуется в код, который - по сравнению с накладными расходами на порождение потоков, вызывающих foo- выполняется очень быстро, так что вероятность перехвата маловероятна. Однако если «продлить» операцию u++, то состояние гонки станет гораздо более вероятным:

void foo()
{
    unsigned i = u;
    for (int s=0;s<10000;s++);
    u = i+1;
}

результат: 694


Кстати: я тоже пробовал

if (u % 2) {
    u += 2;
} else {
    u -= 1;
}

и это давало мне большинство раз 1997, но иногда 1995.

Стефан Лехнер
источник
1
Я ожидал бы, что от любого ненадежного компилятора вся функция будет оптимизирована для одного и того же. Я удивлен, что это не так. Спасибо за интересный результат.
Vality
Это совершенно правильно. Необходимо выполнить многие тысячи инструкций, прежде чем следующий поток начнет выполнение рассматриваемой крошечной функции. Когда вы приближаете время выполнения в функции к накладным расходам на создание потока, вы видите влияние состояния гонки.
Джонатон Рейнхарт
@Vality: Я также ожидал, что он удалит ложный цикл for при оптимизации O3. Это не так?
user21820
Как else u -= 1вообще можно было казнить? Даже в параллельной среде значение никогда не должно не подходить %2, не так ли?
mafu
2
из вывода, похоже, else u -= 1выполняется один раз, когда в первый раз вызывается foo (), когда u == 0. Остальные 999 раз u является нечетным и u += 2выполняется, что приводит к u = -1 + 999 * 2 = 1997; т.е. правильный вывод. Состояние гонки иногда приводит к перезаписи одного из + = 2 параллельным потоком, и вы получаете 1995.
Люк,
7

Он действительно страдает от состояния гонки. Положите usleep(1000);перед тем u++;в fooи я вижу разный вывод (<1000) каждый раз.

юф
источник
6
  1. Вероятный ответ , почему состояние гонки не проявляется для вас, хотя это действительно существует, является то , что foo()так быстро, по сравнению со временем, которое требуется , чтобы начать нить, что каждая нить заканчивается до следующего может даже начать. Но...

  2. Даже с вашей исходной версией результат зависит от системы: я пробовал по-вашему на (четырехъядерном) Macbook, и за десять запусков я получил 1000 трижды, 999 шесть раз и 998 один раз. Так что гонка несколько редка, но явно присутствует.

  3. Вы скомпилировали с '-g', что позволяет избавиться от ошибок. Я перекомпилировал ваш код, все еще без изменений, но без символа '-g', и гонка стала гораздо более явной: я получил 1000 один раз, 999 три раза, 998 дважды, 997 дважды, 996 один раз и 992 один раз.

  4. Re. предложение добавить сон - это помогает, но (а) фиксированное время сна оставляет потоки по-прежнему искаженными по времени начала (в зависимости от разрешения таймера), и (б) случайный сон распределяет их, когда мы хотим, чтобы притянуть их ближе друг к другу. Вместо этого я бы закодировал их так, чтобы они ожидали сигнала запуска, чтобы я мог создать их все, прежде чем позволить им приступить к работе. С этой версией (с или без '-g') я получаю результаты повсюду, начиная с 974 и не выше 998:

    #include <iostream>
    #include <thread>
    #include <vector>
    using namespace std;
    
    unsigned u = 0;
    bool start = false;
    
    void foo()
    {
        while (!start) {
            std::this_thread::yield();
        }
        u++;
    }
    
    int main()
    {
        vector<thread> threads;
        for(int i = 0; i < 1000; i++) {
            threads.push_back (thread (foo));
        }
        start = true;
        for (auto& t : threads) t.join();
    
        cout << u << endl;
        return 0;
    }
dgould
источник
Просто примечание. -gФлаг не каким - либо образом «делают ошибки исчезают.» -gФлаг на обоих GNU и лязг компиляторов просто добавляет символы отладки в скомпилированный двоичный файл. Это позволяет вам запускать диагностические инструменты, такие как GDB и Memcheck, в ваших программах с некоторыми удобочитаемыми выводами. Например, когда Memcheck запускается над программой с утечкой памяти, он не сообщит вам номер строки, если программа не была построена с использованием -gфлага.
MS-DDOS
Конечно, скрытие ошибок от отладчика обычно больше связано с оптимизацией компилятора; Я должен был попробовать, и сказал, «используя -O2 вместо из -g». Но при этом, если вы никогда не испытывали радости от поиска ошибки, которая проявлялась бы только при компиляции без нее -g, считайте, что вам повезло. Это может случиться с некоторыми из самых неприятных и тонких ошибок сглаживания. Я уже видел его, хотя и не в последнее время , и я мог поверить , что может быть , это было причудой старого проприетарного компилятора, поэтому я верю, условно, о современных версиях GNU и Clang.
dgould
-gне мешает вам использовать оптимизацию. например, gcc -O3 -gделает тот же asm gcc -O3, но с метаданными отладки. Однако gdb скажет "оптимизировано", если вы попытаетесь распечатать некоторые переменные. -gможет изменить относительное расположение некоторых вещей в памяти, если что-то из добавляемых им вещей является частью .textраздела. Это определенно занимает место в объектном файле, но я думаю, что после связывания все это оказывается на одном конце текстового сегмента (а не в разделе) или вообще не является частью сегмента. Возможно, это может повлиять на то, где что-то отображается для динамических библиотек.
Питер Кордес,