петли в состоянии гонки

Question

2 процесса P0 и P1 работают одновременно с состоянием гонки. Я хочу рассчитать максимальные и минимальные значения, которые x мог принять во время выполнения. Начальное значение х равно 0

P0: 
for(int i=0; i<1000; i++){ 
    x++; 
    x-- ; 
    x++; 
} 

P1: 
for(int j=0; j<2000; j++){ 
    x-- ; 
    x++; 
} 

Максимальное значение должно быть 4000 и минимум должен быть -2999. Но даже после того, как я много раз пробовал, я не мог понять это. Любая помощь будет принята с благодарностью! Заранее спасибо.

Answer 1

code247,

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

Каждый пост-инкремент будет генерировать следующий код:

ld [%fp-4], %l0 
add %l0, 1, %l0 
st %l0, [%fp-4] 

Каждый постдекремент будет генерировать следующий код:

ld [%fp-4], %l0 
sub %l0, 1, %l0 
st %l0, [%fp-4] 

Теперь то, что вы изучаете с параллелизмом является то, что выше инструкции по сборке могут фактически выполняться недетерминированным образом, если вы решите не использовать mutex locks и другие concurrency control techniques.

Теперь вот как мы получаем значение 4000 для максимального значения.

Это как код будет выполняться:

P0: 
for(int i=0; i<1000; i++){ 
    x++; //lets call this step 1 
    x-- ; //step 2 
    x++; //step 3 
} 

P1: 
for(int j=0; j<2000; j++){ 
    x-- ; //step a (using letters to denote difference in processes) 
    x++; //step b 
} 

Ваш код будет выполняться следующим образом, чтобы достичь максимума:

step 1 
step a 
step b 
step 2 
step 3 

Теперь ключ здесь, заключается в определении того, что ваш reads and writes are going to be dirty. Это означает, что в приведенном выше коде сборки загруженное значение не всегда будет отражать правильное значение. Вот как это будет играть:

ld [%fp-4], %l0 //read current value of 'x' for step 1 
add %l0, 1, %l0 //performs increments 
st %l0, [%fp-4] //stores value from step 1 
ld [%fp-4], %l0 //begins read for step a 
sub %l0, 1, %l0 //performs decrement 
ld [%fp-4], %l0 //performs a DIRTY-READ for step b (notice step a hasn't finished executing) 
add %l0, 1, %l0 //performs increment 
st %l0, [%fp-4] //stores value from increment (value from decrement is now outdated and lost) (this is a dirty write) 
st %l0, [%fp-4] //stores value from decrement (this value is actually lost)(this is a dirty write) 

Из вышеприведенного выполнения, вы можете увидеть, что сборка собирается стать переплетены, и что вы не собираетесь быть сохраняющиеся правильное значение «х» на ваш стек без proper use of concurrency. Так вы получите 4000, потому что в какой-то перестановке вашей сборки вы будете последовательно обрабатывать 4 оператора инкремента последовательно, а результат ваших операторов декремента не будет правильно сохранен. Таким же образом вы получите значение -2999, выполнив свои операторы декремента последовательно, не сохраняя при этом значение x после оператора инкремента.

Пожалуйста, дайте мне знать, если у вас есть вопросы!

Answer 2

Я думаю, что минимальное значение должно быть равно -2999. Я попытаюсь показать, как это сделать.

Я предполагаю, что шаги выполняются в порядке 1,2,3, a, b (имена, которые г-н Деварш дал в одном из ответов). Теперь обратите внимание, что в конце каждого цикла должна быть операция увеличения. Для всех, кроме последней итерации, шаг 2 или шаг a может загрязнять чтение и уничтожать приращения, выполняемые (шаг b + шаг 1) или шаг b соответственно. Но в последней итерации операция декремента не может уничтожить значение приращения, которое должно произойти дальше. И, следовательно, ответ -2999, а не -3000. Надеюсь, ответ ясен. Дайте мне знать, если требуется какое-либо разъяснение.