Несколько потоков, обращающихся к одной переменной

Question

Я нашел этот вопрос в учебнике, который я читаю. Решение также приводится ниже. У меня возникли проблемы с пониманием того, насколько минимальным может быть 2. Почему не мог нить читать 0, все остальные потоки выполняются, и он пишет 1? И независимо от того, является ли это 1 или 2, последняя запись потока должна по-прежнему заполнять свой собственный цикл?

int n = 0; 
int main(int argc, char **argv) { 
for (i = 0; i < 5; i++) { 
int tmp = n; 
tmp = tmp + 1; 
n = tmp; 
} 
return 0; 
} 

Если один поток побежал это приложение, можно было бы ожидать окончательный выхода будет 5. Что делать, если 5 потоков запускали тот же самый цикл в параллели? Какие являются самыми большими и наименьшими значениями, которые могут иметь n? Самый большой должен быть самопомощным: 25, с 5 приращениями из 5 потоков. Тем не менее, рассуждать о наименьшем возможном значении сложнее. Подсказка: n может быть меньше 5, но вам решать, почему.

Решение:

с пятью нитей запуска этих пять-итерация цикла, и без какой-либо защиты от параллельного доступа, самое низкое значение, которое может достигать п равно два. Понимание того, как достичь этого результата, проще всего при работе назад от конечного результата. Для конечного вывода, равного двум, поток должен иметь значение 1 из n, увеличивать его, а затем записывать два. Это означает, что другой поток написал один, подразумевая, что он также изначально читает ноль (который также является стартовым значением для n). Это объясняет поведение двух из пяти потоков. Тем не менее, для выполнения этого поведения, результаты остальных трех потоков должны быть перезаписаны . Для этого можно выполнить два действительных исполнения. Либо 1) все три потока начались и завершили выполнение между первым нулевым нулем и записью первого нуля, или 2) все три потока началось и завершило выполнение между последней прочитанной нитью и , записывающей два. Оба порядка выполнения действительны.

Answer 1

Предполагая, что каждый поток имеет локальный i (т. Е. Каждый поток будет работать для 5 итераций, несмотря ни на что), давайте попробуем получить 1 в качестве результата. Это означало бы, что в последней строке для записи значения нужно было бы прочитать 0 для n на своей 5th итерации. Единственный способ, которым это могло случиться, - это если нить нигде не записана в n в начале 5-й итерации этого потока, но для этого потока будет на 5-й итерации, что сам поток должен быть записан в n, поэтому это невозможно.

Таким образом, наименьший возможный результат равен 2, что может произойти, например, следующим образом: последний поток для записи n завершил 4 итерации, затем другой поток пишет 1, последний поток читает 1 в начале 5-го итерации, все остальные потоки завершить все свои итерации до последней нитки, и, наконец, последняя нить завершает свою 5 итерацию Записывая 2.

Отказ от ответственности: Я, отвечая на концептуальную вопрос о многопоточности - как и другие отметили отсутствие атомарности может привести к неопределенному поведению и произвольным результатам, если представленный код C был использован как есть.Основываясь на вопросе о «самоочевидном» случае с наибольшим числом случаев, я предполагаю, что автор учебника либо не осознает этого, либо использует псевдо-код типа C, чтобы проиллюстрировать эту концепцию. Если первое, то правильный ответ будет заключаться в том, что книга неверна, но я думаю, что ответ в последнем случае также является образовательным.

Answer 2

Дело в том, что поток использует один и тот же экземпляр данных. Кроме того, предполагается, что все остальные потоки выполняются с одинаковой скоростью выполнения.

Поэтому, как каждая нить огибает петлю (получение к i++ части for), они все приращение i почти одновременно, так как если бы код был написан:

for (i = 0; i < 5; i++, i++, i++, i++, i++) 
    ... 

по крайней мере в крайний случай, который дает минимальное количество итераций.

Answer 3

Простое понимание для добавления: Добавление, вычитание и т. Д. На C с помощью оператора + более чем на одну операцию. Вниз на уровне сборки операция + состоит из нескольких инструкций. Если несколько потоков должны были обращаться к одной переменной, и есть плохая чередование этих инструкций, конечный результат может быть ужасно неправильным результатом -> это еще одна причина, по которой нам нужны такие вещи, как мьютексы, семафоры и переменные условия.

Answer 4

Наибольшее должно быть самопомощи: 25, с 5 приращениями из 5 нитей.

Совершенно и совершенно неправильно. Как бы то ни было, это никогда не следует слушать (по крайней мере, о вещах, связанных с потоками), периоде.

int tmp = n; 
tmp = tmp + 1; 
n = tmp; 

Представьте себе процессор, который не имело никаких операций инкремента, но был эффективной «добавить 10» операции и эффективный «вычитает девять» операции. На таком процессоре tmp = tmp + 1; может быть оптимизирован до tmp += 10; tmp -= 9;. Компилятор также мог бы полностью оптимизировать tmp, работая на n.

Так что этот код может стать эквивалентом:

n += 10; 
n -= 9; 

Теперь представьте это происходит: Все пяти нитей добавить 10, так n сейчас 50. Первый поток читает 50, остальные четыре нити вычесть- . Первая нить вычитает 9 из 50, которые она считывает и записывает 41. Поэтому, когда все сделано, n составляет 41.

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

если каждый поток записывает 1, то конечное значение не может быть магически что-то еще

также целиком и полностью ложными. Рассмотрим процессор, который пишет 1, сначала записывая 0, а затем увеличивая значение. Если это происходит на двух ядрах, конечным результатом может быть 2. Этот учебник был написан кем-то, кто принципиально не понимает потоков и неопределенного поведения.

(Я предполагаю, что этот учебник не ограничен каким-то особым контекстом, в котором то, что он говорит, является истинным. Например, он может использовать код «C-like» как форму языка ассемблерной нейтральности и он может делать предположения о платформах, в которых выровненные целые числа имеют конкретные гарантии. Но если это так, то, что он учит, не переводит код C вообще и будет применяться только к людям, которые записывают код сборки на процессорах, правила которых соответствуют предположениям учебника .)