C, C ++ несинхронизированные потоки, возвращающие странный результат

Question

Хорошо, у меня есть этот вопрос в одном, касающемся тем.

есть два несинхронизированных потока, работающих одновременно и использующих глобальный ресурс "int num" Первый:

    void Thread()
{ 
    int i;
    for ( i=0 ; i < 100000000; i++ )
    {
        num++;
        num--;
    }
}

второй:

    void Thread2()
{ 
    int j;
    for ( j=0 ; j < 100000000; j++ )
    {
        num++;
        num--;      
    }
}

Вопрос гласит: каковы возможные значения переменной «num» в конце программы. теперь я бы сказал, что 0 будет значением num в конце программы, но попробуйте запустить этот код, и вы увидите, что результат довольно случайный и я не могу понять почему?

Полный код:

 #include <windows.h>
    #include <process.h>
    #include <stdio.h>

    int static num=0;

   void Thread()
    { 
        int i;
        for ( i=0 ; i < 100000000; i++ )
        {
            num++;
            num--;
        }
    }

   void Thread2()
    { 
        int j;
        for ( j=0 ; j < 100000000; j++ )
        {
            num++;
            num--;      
        }
    }

    int main()
    {
        long handle,handle2,code,code2;
        handle=_beginthread( Thread, 0, NULL );
        handle2=_beginthread( Thread2, 0, NULL );

        while( (GetExitCodeThread(handle,&code)||GetExitCodeThread(handle2,&code2))!=0 );

        TerminateThread(handle, code );
        TerminateThread(handle2, code2 );

        printf("%d ",num);
        system("pause"); 
    }

Answer 1

num++ и num-- не должны быть атомарными операциями. Чтобы взять num++ в качестве примера, это, вероятно, реализовано так:

int tmp = num;
tmp = tmp + 1;
num = tmp;

, где tmp хранится в регистре процессора.

Теперь предположим, что num == 0, оба потока пытаются выполнить num++, а операции чередуются следующим образом:

Thread A        Thread B
int tmp = num;
tmp = tmp + 1;
                int tmp = num;
                tmp = tmp + 1;
num = tmp;
                num = tmp;

Результат в конце будет num == 1, хотя он должен был быть увеличен в два раза. Здесь один шаг теряется; точно так же можно потерять и декремент.

В патологических случаях все приращения одного потока могут быть потеряны, что приведет к num == -100000000, или могут быть потеряны все приращения одного потока, что приведет к num == +100000000. Там может быть даже более экстремальные сценарии.

Тогда есть и другие дела, потому что num не объявлен как изменчивый. Поэтому оба потока предполагают, что значение num не изменяется, если только оно не изменяет его. Это позволяет компилятору оптимизировать весь цикл for, если он чувствует себя таким склонным!

Answer 2

Возможные значения для num включают все возможные значения int, а также значения с плавающей запятой, строки и JPEG носовых демонов.Как только вы вызываете неопределенное поведение , все ставки отключаются.

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

Следующие стандарты C и C ++ будут включать атомарные типы, к которым можно безопасно получить доступ из нескольких потоков без какого-либо API синхронизации.

Answer 3

Вы говорите о потоках, работающих одновременно, что на самом деле может не иметь места, если в вашей системе только одно ядро. Предположим, у вас есть более одного.

В случае, если несколько устройств имеют доступ к основной памяти либо в виде процессоров, либо для управления шинами, либо DMA, они должны быть синхронизированы. Это обрабатывается префиксом блокировки (неявным для инструкции xchg). Он получает доступ к физическому проводу на системной шине, который, по существу, сигнализирует всем присутствующим устройствам об отсутствии. Это, например, часть функции Win32 EnterCriticalSection.

Таким образом, в случае, когда два ядра на одном чипе обращаются к одной и той же позиции, результат будет неопределенным, что может показаться странным, учитывая некоторую синхронизацию, поскольку они совместно используют один и тот же кэш L3 (если он есть). Кажется логичным, но так не работает. Зачем? Потому что похожий случай возникает, когда у вас два ядра на разных чипах (у меня нет общего кэша L3). Вы не можете ожидать, что они будут синхронизированы. Ну, вы можете рассмотреть все другие устройства, имеющие доступ к основной памяти. Если вы планируете синхронизацию между двумя чипами ЦП, вы не можете остановиться на этом - вам нужно выполнить полную синхронизацию, которая блокирует все устройства с доступом и для обеспечения успешной синхронизации всем остальным устройствам нужно время, чтобы распознать, что синхронизация имеет было запрошено, и это занимает много времени, особенно если устройству был предоставлен доступ, и он выполняет операцию мастеринга шины, которую необходимо разрешить завершить. Шина PCI будет выполнять операции каждые 0,125 мкс (8 МГц), и учитывая, что ваши процессоры работают в 400 раз, вы смотрите на МНОГО состояний ожидания. Затем учтите, что может потребоваться несколько тактов PCI.

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

Подводя итог: общая синхронизация, которая бы справилась с вашей ситуацией, сделала бы ваш компьютер бесполезным из-за того, что ему всегда приходилось ждать, пока последнее устройство зарегистрировалось, и все в порядке с синхронизацией. Лучше разрешить его, чтобы он был необязательным и вставлял состояния ожидания только тогда, когда разработчик определил, что это абсолютно необходимо.

---

Это было так весело, что я немного поиграл с примером кода и добавил спин-блокировки, чтобы посмотреть, что произойдет. Компоненты спин-блокировки были

// prototypes

char spinlock_failed (spinlock *);
void spinlock_leave (spinlock *);

// application code

while (spinlock_failed (&sl)) ++n;
++num;
spinlock_leave (&sl);

while (spinlock_failed (&sl)) ++n;
--num;
spinlock_leave (&sl);

spinlock_failed был построен вокруг инструкции "xchg mem, eax". Как только он потерпел неудачу (не установив спинлок, <=> удалось его установить), spinlock_leave присваивает ему значение «mov mem, 0». «++ n» подсчитывает общее количество попыток.

Я изменил цикл до 2,5 млн. (Потому что с двумя потоками и двумя спин-блокировками на цикл я получаю 10 млн. Спин-блокировок, с которыми легко и удобно работать) и рассчитал последовательности с количеством rdtsc на двухъядерном Athlon II M300 @ 2 ГГц и вот что я нашел

• Запуск одного потока без синхронизации (кроме основной петли) и замки (как в оригинальном примере) 33748884 <=> 16,9 мс => 13,5 циклов / цикл.
• Запуск одного потока, другого ядра нет попытка заняла 210917969 циклов <=> 105,5 мс => 84,4 циклов / цикл <=> 0,042 мкс / цикл. Для спин-блокировки потребовалось 112581340 циклов <=> 22,5 цикла на спин-блокированная последовательность. Тем не менее, требуется самый медленный спинлок 1334208 циклы: это 667 нас или только 1500 каждую секунду.

Таким образом, добавление спин-блокировок, не затронутых другим процессором, добавило несколько сотен процентов к общему времени выполнения. Конечное значение в num было 0.

• Запуск двух потоков без спинлок прошло 171157957 циклов <=> 85,6 мс => 68,5 циклов / цикл. Num содержал 10176.
• Две нитки со спинлок взяли 4099370103 <=> 2049 мс => 1640 циклы / цикл <=> 0,82 us / loop. для спин-блокировки 3930091465 циклов=> 786 циклов на спин-блокированную последовательность. Самый медленный спинлок требуется 27038623 циклов: вот 13,52 мс или только 74 каждую секунду. Num содержит 0.

Между прочим, циклы 171157957 для двух потоков без спин-блокировок очень выгодно сравниваются с двумя потоками с спин-блокировками, у которых было удалено время спин-блокировки: 4099370103-3930091465 = 169278638 циклов.

Для моей последовательности соревнование спин-блокировки вызвало 21-29 миллионов попыток на поток, что составляет 4.2-5.8 попыток на спин-блокировку или 5.2-6.8 попыток на спин-блокировку. Добавление спин-блокировки привело к штрафу за время выполнения в 1927% (1500 / 74-1). Самый медленный спин-блокировка требовал 5-8% всех попыток.

Answer 4

Как сказал Томас, результаты непредсказуемы, потому что ваш прирост и убыль не атомарны. Вы можете использовать InterlockedIncrement и InterlockedDecrement, которые являются атомарными, чтобы увидеть предсказуемый результат.

• Доступ с блокировкой переменной (MSDN)