в Java время идёт слева направо
May. 1st, 2012 04:15 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sassa_nfВ связи с:
1. Семафор не отпускается теми, кто ушёл из while лупа через return. Как быть?
А в этом и прикол. Семафоры можно отпускать из другого потока. Главное, чтобы количество acquire было равно количеству release.
2. Не проигнорирует ли while луп изменения w, который не volatile?
3. Не считает ли while луп значения массива a слишком рано, ибо ++w может случиться до a[w...]=result, ибо w не volatile?
О, вот это были бы хорошие вопросы от читавших JCIP.
На самом деле чтение w можно optimize out только если чтение в последующей итерации while можно reorder со всей предыдущей итерацией цикла, включая условие. В данном цикле есть как минимум rr.get(), с которым нельзя reorder ничего, что выполняется после него в program order.
Ответ на вопрос (3) из assertions ниже. Если w объявить volatile, то ++w означает наличие volatile store, что есть дороже, чем просто store. Это не имело бы никакого значения, если s.release() состоял из одних только stores с volatile store в конце, ибо на TSO платформе цепочку из смеси volatile stores и stores можно заменить на цепочку из stores с одним volatile store в конце.
Неубывающие счётчики - это очень занятная конструкция. Пусть w - это количество contenders, которым можно выходить из while через return когда-либо в будущем; тогда rr - это количество contenders, которые уже вышли через return когда-либо в прошлом.
Правильность алгоритма зиждется на таких assertions:
0. Liveness: Количество acquire строго равно количеству release
Кагбэ, очевидно.
1. Mutual exclusion-1: Contenders наблюдают только готовые результаты
Не смотря на то, что a[w]=result и ++w могут быть reordered, нас интересует только факт, что rr.get()+1 содержит готовый результат. Все contenders смотрят только на ту ячейку. Пока contenders было меньше, чем w, они не увидят, что ячейка пуста / не увидят старое значение, всё ещё хранящееся там. Нового contender допускаем в while только после того, как правильное значение сохранено в массиве.
2. Mutual exclusion-2: Не более одного потока пользуется тем же значением result (Использование result однопоточное)
Ну, мы пускаем в цикл while не больше contenders, чем w+1. Каждый из них учтиво относится к CAS failure и не пользуется оптимистично считанным result.
3. Mutual exclusion-3: Не более одного потока находится в цикле for (Логика compute_it однопоточная)
3.а. Пока поток находится в for, все contenders, достигшие while, обнаружат w != rr.get().
Естественно, ибо пока в for, мы release только после ++w.
3.б. После того, как поток покинул for, последний contender, оставшийся в while, обнаружит w == rr.get().
Естественно, ибо w поменялось на один раз меньше, чем было release. Contenders в каком-то порядке по одному смогут увеличить rr на единицу, пока rr не станет равно w. Последний contender обнаружит rr.get() == w.
4. Количество contenders, говорите? А как быть с integer wrap-around и отрицательными значениями?
Правильная мысль. По-хорошему нужен был бы long, которого хватит на годы непрерывной работы / пока не сделают 128-битную платформу, но здесь можно обойтись и int, т.к. разница между w и rr не превышает a.length. То есть, из w != rr.get() можно заключать, что мы говорим о числах из "одной эпохи".
5. Так а где баг?
А в w != rr.get() у нас две переменных. В 3.a обсуждён только неубывающий w. А вот w по отношению к rr.get() может находиться в любом отношении, ибо rr меняется независимо от w.
Правильно будет while((r=rr.get()) != w) и для этого какой-нибудь лампорт когда-то какую-то статью, наверное, написал. Неформально же - это что-то типа так:
поскольку в Java время идёт слева направо, нужно сначала проверить прошлое (помните? "rr - количество contenders, покинувших while в прошлом"), а уж потом будущее ("w - количество contenders, которым можно покинуть while в будущем").
AtomicInteger rr =...
int w;
Semaphore s =... ;// not a semaphore, but a lock that can tell if it's contended
T[] a = ...
public T p() {
T result;
int r;
s.acquire();
while(w != (r=rr.get())) {
result = a[r & (a.length-1)];
if (rr.compareAndSet(r,r+1)) return result;
}
for(;;) {
result = compute_it();
if (!s.contended() || rr.get()+a.length == w) break;
a[w & (a.length-1)] = result;
++w;
s.release();
}
s.release();
return result;
}1. Семафор не отпускается теми, кто ушёл из while лупа через return. Как быть?
А в этом и прикол. Семафоры можно отпускать из другого потока. Главное, чтобы количество acquire было равно количеству release.
2. Не проигнорирует ли while луп изменения w, который не volatile?
3. Не считает ли while луп значения массива a слишком рано, ибо ++w может случиться до a[w...]=result, ибо w не volatile?
О, вот это были бы хорошие вопросы от читавших JCIP.
На самом деле чтение w можно optimize out только если чтение в последующей итерации while можно reorder со всей предыдущей итерацией цикла, включая условие. В данном цикле есть как минимум rr.get(), с которым нельзя reorder ничего, что выполняется после него в program order.
Ответ на вопрос (3) из assertions ниже. Если w объявить volatile, то ++w означает наличие volatile store, что есть дороже, чем просто store. Это не имело бы никакого значения, если s.release() состоял из одних только stores с volatile store в конце, ибо на TSO платформе цепочку из смеси volatile stores и stores можно заменить на цепочку из stores с одним volatile store в конце.
Неубывающие счётчики - это очень занятная конструкция. Пусть w - это количество contenders, которым можно выходить из while через return когда-либо в будущем; тогда rr - это количество contenders, которые уже вышли через return когда-либо в прошлом.
Правильность алгоритма зиждется на таких assertions:
0. Liveness: Количество acquire строго равно количеству release
Кагбэ, очевидно.
1. Mutual exclusion-1: Contenders наблюдают только готовые результаты
Не смотря на то, что a[w]=result и ++w могут быть reordered, нас интересует только факт, что rr.get()+1 содержит готовый результат. Все contenders смотрят только на ту ячейку. Пока contenders было меньше, чем w, они не увидят, что ячейка пуста / не увидят старое значение, всё ещё хранящееся там. Нового contender допускаем в while только после того, как правильное значение сохранено в массиве.
2. Mutual exclusion-2: Не более одного потока пользуется тем же значением result (Использование result однопоточное)
Ну, мы пускаем в цикл while не больше contenders, чем w+1. Каждый из них учтиво относится к CAS failure и не пользуется оптимистично считанным result.
3. Mutual exclusion-3: Не более одного потока находится в цикле for (Логика compute_it однопоточная)
3.а. Пока поток находится в for, все contenders, достигшие while, обнаружат w != rr.get().
Естественно, ибо пока в for, мы release только после ++w.
3.б. После того, как поток покинул for, последний contender, оставшийся в while, обнаружит w == rr.get().
Естественно, ибо w поменялось на один раз меньше, чем было release. Contenders в каком-то порядке по одному смогут увеличить rr на единицу, пока rr не станет равно w. Последний contender обнаружит rr.get() == w.
4. Количество contenders, говорите? А как быть с integer wrap-around и отрицательными значениями?
Правильная мысль. По-хорошему нужен был бы long, которого хватит на годы непрерывной работы / пока не сделают 128-битную платформу, но здесь можно обойтись и int, т.к. разница между w и rr не превышает a.length. То есть, из w != rr.get() можно заключать, что мы говорим о числах из "одной эпохи".
5. Так а где баг?
А в w != rr.get() у нас две переменных. В 3.a обсуждён только неубывающий w. А вот w по отношению к rr.get() может находиться в любом отношении, ибо rr меняется независимо от w.
Правильно будет while((r=rr.get()) != w) и для этого какой-нибудь лампорт когда-то какую-то статью, наверное, написал. Неформально же - это что-то типа так:
поскольку в Java время идёт слева направо, нужно сначала проверить прошлое (помните? "rr - количество contenders, покинувших while в прошлом"), а уж потом будущее ("w - количество contenders, которым можно покинуть while в будущем").
