Почему потерянные обновления происходят с volatile на x86?

Question

Я попытался запустить следующий код с 'count' как volatile:

ExecutorService e = Executors.newFixedThreadPool(2);
for (int i=0; i<2; i++)
{
    e.execute(new Runnable(){
        public void run() {
            for (int i=0; i<1000000; i++)
            count++;
            }
        }
    );
}
e.shutdown();
e.awaitTermination(1, TimeUnit.DAYS);
System.out.println(count);

count обычно заканчивается менее чем 1 000 000.

Я работаю на процессоре x86 - IntelCore 2 Duo E8400 с точкой доступа 1.6.24.Обычный аргумент потерянного обновления для оператора ++, используемого с изменчивой переменной, с целью достижения атомарного обновления, выглядит следующим образом: оба потока 1 и 2 читают значение 0 для v, оба увеличивают его на 1 и записывают значение 1.

Этот аргумент, похоже, распадается при использовании volatile на x86, поскольку:

1) Каждый доступ к переменной volatile проходит через иерархию кэша ЦП.JVM может генерировать ассемблерный код для многократного доступа к энергозависимой памяти без промежуточной загрузки / сохранения из памяти, только если он может доказать, что к энергозависимой переменной осуществляется доступ из одного потока, что здесь не так.

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

Чего мне здесь не хватает?

Answer 1

Вам не хватает того факта, что ++ не является атомарной операцией.

Если вы переписываете свой код как:

for (int i=0; i<1000000; i++)
    int tmp = count;
    tmp = tmp + 1;
    count = tmp;
}

это делает это яснее? Здесь не требуется информация о модели памяти или строках кэша - все, что нам нужно, - это два потока, которые читают одно и то же значение, выполняют независимую работу, а затем оба снова сохраняют свое вычисленное значение.

Answer 2

count++; - это проблема ЛЮБОГО современного процессора, для этого необходимо count загрузить в регистр, где его можно увеличить (так как никакой процессор не может работать непосредственно с ОЗУ), а затем сохранить его обратно в ОЗУ

используйте AtomicInteger и используйте incrementAndGet

или вообще цикл Atomic CompareAndSwap (здесь используется AtomicFieldUpdater , который работает только на полях экземпляра) - это самый быстрый способ гарантировать, что обновление всегда происходит (это уязвимо для проблемы ABA хотя)

do{
    int old=count.get(this);
    int newval=old+1;
}while(!count.compareAndSet(this,old,newval));

Answer 3

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

Попробуйте вместо этого подумать об этом.

 Value is loaded from memory into register.
 Register is incremented.
 Value is written back.

Между этими операциями будет некоторый промежуток времени, поэтому на самом деле это будет тот же код, что и:

 Value is loaded from memory into register.
 Do a lot of time-consuming things
 Register is incremented.
 Do a lot of time-consuming things
 Value is written back.

Answer 4

Вам не хватает этой возможности:

1) Переменная является общей для обоих кэшей ЦП.

2) Оба процессора считывают значение.

3) Оба процессора добавляют один к значению, получая одинаковый результат.

4) CPU0 получает исключительную переменную в свой кэш и записывает увеличенное значение.

5) CPU1 получает переменную, исключающую CPU0, и записывает то же самое увеличенное значение, которое уже содержалась в строке кэша.

Хотя volatile не позволяет вам читать устаревшие значения, он не обеспечивает атомарности.