про барьер, которого не было
Dec. 14th, 2012 01:56 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfВот зачем, спрашивается, на x86 нужен барьер после volatile store? Оно ж и так будет eventually видимо, и видимо в нужном порядке.
А вот пример.
Один поток делает так:
Второй поток делает так:
Если x и y - не volatile (а точнее в нашем случае JVM неправильно оптимизировало volatile store), то z.get(), y==null и x != null могут обогнать соответствующие строки, в которых устанавливаются, казалось бы не имеющие отношения к ним переменные x и y соответственно. Возможный вариант развития событий: x != null расчитан до y=blahblah, поэтому во втором потоке y=blahblah выполняется, а цикл CAS - нет; одновременно первый поток обнаруживает z.get()==null и y==null и успешно устанавливает z в x. В итоге никто и никогда не обнаружит, что y расчитано.
Если x и y - volatile, и между ними и последующим volatile load, как и положено, стоит сериализация + барьер, то либо первый поток завершает CAS успешно, обнаружив y == null, либо успешно, обнаружив y != null, либо не успешно, в случае, когда второй поток успешно установил z в y.
В случае с установкой вторым потоком z в y корректность тривиально демонстрируется: все, кто увидят z==y, увидят то же, что и второй поток - т.е. x != null, а потому заключает, что вычислены и x, и y. Поэтому интереснее другие случаи, т.е. когда второй поток не выполнял цикл, т.е. обнаружил x == null.
Если второй поток обнаружил x == null, значит, первый поток выполнит x=blah после того, как второй поток выполнил y=blahblah. Отсюда заключаем, что первый поток выполнит проверку y==null после y=blahblah, и установит z в y без конкурентов - поэтому цикл здесь не нужен. Корректность опять очевидна - все, кто обнаруживают z == y, умозаключают, что вычислены и x, и y, точно как это видно первому потоку.
Наиболее интересен, по-моему, следующий случай: первый поток обнаружил y == null, и успешно выполнил CAS, но при этом второй поток одновременно успел выполнить y=blahblah. На некоторый конечный промежуток времени внешний наблюдатель увидит z==x, что корректно. Конечность этого промежутка времени следует из того, что поскольку второй поток закончит y=blahblah после того, как первый поток закончил x=blah (это так, поскольку первый поток видел y==null после x=blah), то второй поток увидит x != null и в цикле с CAS установит z в значение y.
Какие тут выгоды? Ну, это лишь кусок алгоритма. Мы добиваемся того, что потоки могут завершать вычисление без CAS, ограничиваясь проверкой условия с помощью volatile load. Во-вторых, мы добиваемся того, что только один поток занимается CAS в цикле, остальные do not retry и не теребят кэш.
А вот пример.
Один поток делает так:
x=blah; if (z.get()==null) z.compareAndSet(null, y == null? x: y);Да-да, никаких циклов, просто один CAS.
Второй поток делает так:
y=blahblah; if (x != null) while ((tmp=z.get()) != y && !z.compareAndSet(tmp, y));То есть, два потока кооперативно устанавливают значение z: в значение x, пока значение y ещё не вычислено, либо в значение y, когда оно уже известно; причём, из z==y должно следовать, что x уже вычислено - как бы, x is known before y is known.
Если x и y - не volatile (а точнее в нашем случае JVM неправильно оптимизировало volatile store), то z.get(), y==null и x != null могут обогнать соответствующие строки, в которых устанавливаются, казалось бы не имеющие отношения к ним переменные x и y соответственно. Возможный вариант развития событий: x != null расчитан до y=blahblah, поэтому во втором потоке y=blahblah выполняется, а цикл CAS - нет; одновременно первый поток обнаруживает z.get()==null и y==null и успешно устанавливает z в x. В итоге никто и никогда не обнаружит, что y расчитано.
Если x и y - volatile, и между ними и последующим volatile load, как и положено, стоит сериализация + барьер, то либо первый поток завершает CAS успешно, обнаружив y == null, либо успешно, обнаружив y != null, либо не успешно, в случае, когда второй поток успешно установил z в y.
В случае с установкой вторым потоком z в y корректность тривиально демонстрируется: все, кто увидят z==y, увидят то же, что и второй поток - т.е. x != null, а потому заключает, что вычислены и x, и y. Поэтому интереснее другие случаи, т.е. когда второй поток не выполнял цикл, т.е. обнаружил x == null.
Если второй поток обнаружил x == null, значит, первый поток выполнит x=blah после того, как второй поток выполнил y=blahblah. Отсюда заключаем, что первый поток выполнит проверку y==null после y=blahblah, и установит z в y без конкурентов - поэтому цикл здесь не нужен. Корректность опять очевидна - все, кто обнаруживают z == y, умозаключают, что вычислены и x, и y, точно как это видно первому потоку.
Наиболее интересен, по-моему, следующий случай: первый поток обнаружил y == null, и успешно выполнил CAS, но при этом второй поток одновременно успел выполнить y=blahblah. На некоторый конечный промежуток времени внешний наблюдатель увидит z==x, что корректно. Конечность этого промежутка времени следует из того, что поскольку второй поток закончит y=blahblah после того, как первый поток закончил x=blah (это так, поскольку первый поток видел y==null после x=blah), то второй поток увидит x != null и в цикле с CAS установит z в значение y.
Какие тут выгоды? Ну, это лишь кусок алгоритма. Мы добиваемся того, что потоки могут завершать вычисление без CAS, ограничиваясь проверкой условия с помощью volatile load. Во-вторых, мы добиваемся того, что только один поток занимается CAS в цикле, остальные do not retry и не теребят кэш.
