Сначала вам нужно решить, чего вы хотите достичь, и какими возможными способами инструкции различных потоков могут чередоваться, чтобы предотвратить это.
Оператор инкремента в C ++x обычно реализуется как считывание значения i из памяти в регистр; увеличить регистр; записать значение в память:
r<sub>1</sub> ← x<sub>global</sub>
r<sub>1</sub> ← r<sub>1</sub> + 1
x<sub>global</sub> ← r<sub>1</sub>
Таким образом, значение x global увеличивается на единицу.
Если у вас есть два потока параллельно, то они могут разрушительно чередоваться
initial x<sub>global</sub> = 99
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
r<sub>2</sub> ← x<sub>global</sub>
compare r<sub>2</sub> 100
r<sub>1</sub> ← r<sub>1</sub> + 1 == 100
r<sub>2</sub> ← r<sub>2</sub> + 1 == 100
x<sub>global</sub> ← r<sub>1</sub> == 100
x<sub>global</sub> ← r<sub>2</sub> == 100
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
stop
r<sub>2</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
stop
final x<sub>global</sub> = 100
Таким образом, значение x global увеличивается на единицу, несмотря на то, что оба потока увеличивают его.
(Я исключаю эффекты кэширования, которые означают, что чтение переменной в потоке 2 может вести себя так, как если бы оно происходило до записи в потоке 1, даже если запись в потоке 1 происходит до чтения в время настенных часов. Приобретение и освобождение мьютексов в pthreads вызывает барьеры памяти, которые заставляют все чтения вести себя так, как будто они произошли после, и записи вести себя так, как если бы они произошли до получения или выпуска.)
(приведенное выше эквивалентно for ( int r; ( r = x ) < 100; x = r + 1 ), а не for (; x < 100; x = x + 1 ), который может иметь дополнительное чтение x и, следовательно, имеет другую точку, где потоки могут вмешиваться)
Аналогичным образом, приращение на один поток может уничтожить приращение другого потока, позволяя потокам завершиться с i <100: </p>
initial x<sub>global</sub> = 98
r<sub>2</sub> ← x<sub>global</sub>
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
r<sub>1</sub> ← r<sub>1</sub> + 1 == 99
x<sub>global</sub> ← r<sub>1</sub>
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
r<sub>1</sub> ← r<sub>1</sub> + 1 == 100
x<sub>global</sub> ← r<sub>1</sub>
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
stop
compare r<sub>2</sub> 100
r<sub>2</sub> ← r<sub>2</sub> + 1 == 99
x<sub>global</sub> ← r<sub>2</sub>
...
final x<sub>global</sub> = 99
Таким образом, второе приращение левого потока перезаписывается приращением первого, и оно заканчивается с глобальным видимым значением x <100. </p>
Вы, вероятно, знаете все это и, возможно, захотите использовать механизм для защиты от него.
Я говорю «может», поскольку ваши требования не ясны - поток выше завершается, когда x достигнет 100; требования не говорят, что там не сказано.
Итак, поскольку ни один поток не завершится без записи x global & larr; 100, требование фактически может быть выполнено без какой-либо блокировки, но x может быть увеличено n* в 100 раз, а не в 100 раз. (если ограничение было больше байта, то запись x может быть неатомарной на некоторых платформах, что может привести к бесконечному циклу, если байты из разных потоков смешаны вместе, но для ограничения в 100 не будет )
Один из методов - использовать мьютекс , который блокирует запуск других потоков, когда один поток удерживает блокировку мьютекса. Если блокировка получена до того, как x global будет прочитана и не снята до тех пор, пока x global не будет записана, то чтение и запись потока не могут чередоваться.
initial x<sub>global</sub> = 98
lock (mutex)
mutex locked
lock(mutex)
blocked
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
r<sub>1</sub> ← r<sub>1</sub> + 1 == 99
x<sub>global</sub> ← r<sub>1</sub>
release ( mutex )
mutex locked
r<sub>2</sub> ← x<sub>global</sub>
compare r<sub>2</sub> 100
r<sub>2</sub> ← r<sub>2</sub> + 1 == 100
x<sub>global</sub> ← r<sub>2</sub>
release ( mutex )
lock (mutex)
mutex locked
r<sub>1</sub> ← x<sub>global</sub>
compare r<sub>1</sub> 100
release ( mutex )
stop
...
final x<sub>global</sub> = 100
Помимо pthreads, вы можете использовать операцию сравнения и замены вашей платформы (__sync_val_compare_and_swap в gcc ), которая принимает адрес, старое значение и новое значение, и атомарно устанавливает память по адресу к новому значению, если оно было равно старому значению. Это позволяет вам написать логику как:
for ( int v = 0; v < 100; ) {
int x_prev = __sync_val_compare_and_swap ( &x, v, v + 1 );
// if the CAS succeeds, the value of x has been set to is x_prev + 1
// otherwise, try again from current last value
if ( x_prev == v )
v = x_prev + 1;
else
v = x_prev;
}
Так что если
initial x<sub>global</sub> = 98
initial v<sub>1</sub> = 0
initial v<sub>2</sub> = 0
cmp v<sub>1</sub> 100
x_prev<sub>1</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 98 ( set fails with x == 98 )
cmp v<sub>2</sub> 100
x_prev<sub>2</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 98 ( set fails with x == 98 )
v<sub>1</sub> ← x_prev<sub>1</sub> = 98 // x_prev != v
v<sub>2</sub> ← x_prev<sub>2</sub> = 98
cmp v<sub>2</sub> 100
x_prev<sub>2</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 98 ( set succeeds with x == 99 )
v<sub>2</sub> ← x_prev<sub>2</sub> + 1 = 99 // as x_prev == v
cmp v<sub>1</sub> 100
x_prev<sub>1</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 99 ( set fails with x == 99 )
v<sub>1</sub> ← x_prev<sub>1</sub> = 99 // as x_prev != v
cmp v<sub>1</sub> 100
x_prev<sub>1</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 99 ( set succeeds with x == 100)
v<sub>1</sub> ← x_prev<sub>1</sub> + 1 = 100 // as x_prev == v
cmp v<sub>2</sub> 100
x_prev<sub>2</sub> ← CASV ( x<sub>global</sub>, v<sub>1</sub>, v<sub>1</sub> + 1 ) = 100 ( set fails with x == 100 )
v<sub>2</sub> ← x_prev<sub>2</sub> = 100 // as x_prev != v
cmp v<sub>1</sub> 100
cmp v<sub>2</sub> 100
stop
stop
В каждом цикле x global будет атомно быть установленным в значение r 1 + 1, если и только если его предыдущее значение было r 1 ; в противном случае для r 1 будет установлено значение x global , проверенное во время операции CASV. Это уменьшает количество временных блокировок, удерживаемых в большинстве реализаций (хотя все еще требуется блокировка шины памяти на время операции CAS, только эти операции будут сериализованы. Поскольку выполнение CAS дорого на многоядерных процессорах, оно, вероятно, выиграло не намного лучше для такого простого случая, как этот.)