Порядок программы в параллельном куске кода - PullRequest
Новая
       52

Порядок программы в параллельном куске кода

0 голосов
/ 12 января 2019

Учитывая следующий кусок кода:

int x = 0; co x:= x + 1 || x := x - 1 oc

Видимо возможные значения x = {0, -1, 1}.

Я пытался понять, как это может произойти, и я читал об атомных зазубринах, которые, когда они случаются, случаются только они. В книге приведен пример того, что мы можем разбить оператор x := x + 1 на атомарные операторы типа.

READ X (R1) INC WRITE (W1)

и

x := x - 1 в:

READ X (R2) DEC WRITE (W2)

и это говорит о том, что INC WRITE и READ inc ведут себя так, как будто они атомарные, и я действительно не понимаю, почему безопасно делать такое предположение?

Тогда, видимо, этот программный порядок возвращает значение -1: R1 -> R2 -> W1 -> W2, которое я не понимаю, почему?

Насколько я понимаю, нам кажется, что мы читаем значение x, затем читаем его снова, затем увеличиваем его на единицу, а затем уменьшаем на единицу, и не должно ли это быть равным 0?

Спасибо за помощь.

1 Ответ

0 голосов
/ 12 января 2019

Проблема с параллелизмом заключается в том, что вы не можете контролировать порядок одновременного доступа. Итак, мы делаем следующие предположения:
- x - это глобальная переменная, доступная различным потокам
- x ++ и x-- выполняются независимыми потоками.

Как указано в вашей книге, выполнение операции чтения-изменения-записи в общей переменной представляет собой трехэтапный процесс:
1 / считайте var в процессор reg
2 / изменить процессор рег
3 / запись процессора в регистр
Каждое из этих отдельных действий соответствует инструкции процессора и, следовательно, является атомным . Но глобальная операция чтения-изменения-записи не разделяется и может быть разделена другими параллельными действиями.

Теперь рассмотрим параллельные операции 

 Thread A                          Thread B
 1/ read x->regA                   a/ read x->regB
 2/ regA++                         b/ regB-- 
 3/ write regA->x                  c/ write regB

Внутри потока порядок действий 123 или abc будет соблюдаться, но между потоками A и B возможен любой относительный порядок.

С 123abc мы получаем ожидаемый результат. x изменяется на 1 потоком A, затем читается потоком B, уменьшается и, наконец, x = 0
То же самое для abc123

Но другие заказы приведут к другим результатам. Например: 1a2b3c 

 Thread A                          Thread B
 1/ read x->regA=0                   
                                   a/ read x->regB=0
 2/ regA++=1                       
                                   b/ regB--=-1 
 3/ write regA->x=1
                                   c/ write regB->x=-1

И, наконец, х = -1.

Но при заказе 1abc23 мы получим x = 1. 

 Thread A                          Thread B
 1/ read x->regA=0                   
                                   a/ read x->regB=0
                                   b/ regB--=-1 
                                   c/ write regB->x=-1
 2/ regA++=1    
 3/ write regA->x=1

Поскольку все ордера могут быть достигнуты, результат будет \ in {-1,0,1}

Единственный способ получить детерминированный результат - использовать атомарные инструкции чтения-изменения-записи. Все современные процессоры имеют средства для этого (fetch-and-add или load-connected / store-cond), и в этом случае последовательности 123 или abc не могут быть разделены. Единственный возможный порядок будет 123abc или abc123, и оба приведут к детерминированному результату x = 0.

...