Как эти две функции, выполняемые параллельно, могут выдавать маловероятный результат?

Question

У меня есть две эти функции, выполняемые параллельно:

int x = 10 // a common variable

void P1(){                   void P2(){
   while(1){                    while(1){
   x--;                         x--;
   x++;                         x++;
   if(x!=10)                    if(x!=10)
      printf("x=%d",x);             printf("x=%d",x);
   }                            }
}                             }

parbegin P1(); P2();
parend

Функции иногда выводят x=8, что не представляется возможным.

Связано ли это с тем, что операции x-- и x++ фактически переводятся в 3 инструкции в машинном коде (см. Символ c декодирование сборки)?

LD    R0, X             // LOAD into R0 the value of x
INCR  R0 (or DECR R0)   // { INCR | DECR }-increase/decrease the value of R0 by 1
STO   R0, X             // STORE the new value back to x

Если да,
, то каков порядок инструкций, чтобы был сгенерирован вывод "x=8"?

Если нет,
, тогда почему иногда печатается x=8?

Answer 1

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

* * * * * * * *. операции загрузки, операции уменьшения и операции сохранения. Таким образом, если x-- получает приоритет перед другим потоком, результат может быть таким, как если бы оператор x-- вообще не выполнялся. Но это не даст 8, это фактически приведет к тому, что x не достигнет значения, столь же низкого, как 8.

Однако то же самое верно и для оператора x++: упреждение может привести к тому, что x++ никогда не произойдет, поэтому в этом случае x не сможет превысить 9, поэтому потребуется всего один успешный x--, чтобы понизить его до 8.

Итак, если отменено больше x++ с, чем x-- с, то вполне возможно, что x станет 8. На самом деле, в вашем примере кода вполне возможно, что x может получить любое значение, о котором вы только можете подумать.

Answer 2

Да, это потому, что x++ и x-- не являются атомами c операциями. Если одна из этих операций прервана, другой поток мог изменить значение x, поэтому поток, выполняющий операцию увеличения или уменьшения, сохраняет результат, который вычисляется из устаревшего значения x.

Вот возможное чередование, которое приводит к печати x=9, x=8, x=9. В этом конкретном перемежении операции приращения в P1 и P2 начинаются с одного и того же значения x, и поэтому они оба записывают один и тот же результат, так что x эффективно увеличивается только один раз.

P1          P2          x
                        10
LD R0, x                10
DECR R0                 10
ST R0, x                10→9
            LD R0, x    9
            DECR R0     9
            ST R0, x    9→8
            LD R0, x    8
LD R0, x                8
INCR R0                 8
ST R0, x                8→9
            INCR R0     9
            ST R0, x    9→9
            print       9
            GOTO loop   9
            LD R0, x    9
            DECR R0     9
            ST R0, x    8
print                   8
GOTO loop
            LD R0, x    8
            INCR R0     8
            ST R0, x    8→9
            print       9
            GOTO loop   9

Обратите внимание, что в этом чередовании тело l oop выполняется три раза (один раз в P1 и один раз в P2), а конечное значение x не равно 10. Аналогичная последовательность может повторяться, и значение x может оказаться сколь угодно низким. Симметрично, это могло бы в конечном итоге быть сколь угодно высоким.

Вот еще одно перемежение, где достигается 8 с одной итерацией в каждом потоке. В этом случае операция уменьшения в P2 фактически отменяет приращение в P2. С этим перемежением самый первый вывод - x=8, за которым следует x=9.

P1          P2          x
                        10
LD R0, x                10
DECR R0                 10
ST R0, x                10→9
            LD R0, x    9
            DECR R0     9
LD R0, x                9
INCR R0                 9
ST R0, x                9→10
            ST R0, x    10→8
            LD R0, x    8
print                   8
GOTO loop
            INCR R0     8
            ST R0, x    8→9
            print       9
            GOTO loop   9

Вот еще одно перемежение, где вывод начинается с x=8, x=7, x=6. Здесь все операции приращения оказываются эффективно отмененными одновременным уменьшением. Это может go навсегда.

P1          P2          x
                        10
LD R0, x                10
DECR R0                 10
ST R0, x                10→9
            LD R0, x    9
            DECR R0     9
LD R0, x                9
INCR R0                 9
ST R0, x                9→10
            ST R0, x    10→8
            LD R0, x    8
print                   8
GOTO loop               8
LD R0, x                8
DECR R0                 8
            INCR R0     8
            ST R0, x    8→9
ST R0, x                9→7
LD R0, x                7
            print       7
            GOTO loop   7
            LD R0, x    7
INCR R0                 7
ST R0, x                8
            DECR R0     8
            ST R0, x    8→6
print                   6
GOTO loop               6

Answer 3

Q : "... почему иногда печатает x=8?"

Потому что это очень пример побочного продукта выполнения несогласованных параллельных операций в CRCW -PRAM-абстрактной вычислительной машине, как было объяснено в элементарной теории параллельной обработки:

parbegin P1(); P2();
parend;

, как определено выше, не делает ничего, кроме неограниченных и принципиально конфликтующих CRCW-операций над общими x (то есть преимущественно - поэтому независимо от того, какой компилятор считался используемым, какие приемы компиляции считались введенными в действие, и какой целевой кремний предполагалось использовать для загрузки и запуска такого продукта выполнения кода (будь то RISC / CIS C? Является ли он суперскалярным или нет? Является ли он конвейерным? Будут ли они выполняться по порядку / не по порядку? Et c.) - проблема начинается с того, как был разработан императивно постулированный код (как это было), а не как код-repres Развитие и трансформация эволюционировали или как целевое кремниевое устройство на самом деле работает на самом нижнем уровне в конце.

Ответственность за предотвращение столкновений всегда была на стороне автора, не так ли?

Код, разработанный как есть, выше «разделяет» доступ к x, как при чтении, так и при записи, ограничен ничто - таким образом, главным образом бесплатно -толкнуть всякий раз, когда внешнее влияние " порядок -шагов" искажается (не соответствует ожидаемому последовательность шагов [do +1 <_almost_right_after_> -1 was done], которая, как считается, поддерживает x=10 инвариант (на который она не способна, даже в абстрактном, идеально синхронном, идеальном компьютере CRCW-PRAM)

Как было объяснено в возрасте go, в условиях Бернштейна ( см. Теория и примеры ), все всего - [CONCURRENT] (тем более True- [PARALLEL]) единиц выполнения кода должны стр Контролируйте порядок , в котором общие переменные (x, в коде макета выше) считываются и обновляются.