Comments 31
У меня есть ряд вопросов и замечаний:
- Почему инициализация переменных происходит в теле конструктора, а не в списке инициализации?
- Какой смысл существования bool isNotWaiting? Она вроде как попадает в private, в логике класса нигде не задействована, метода для чтения — не имеет. Так и зачем она? Как обеспечена консистентность между этим флагом и состоянием барьера?
- Почему вместо банального атомарного инкремента threadsWaiting++ вы используете помпезный вызов fetch_add(1)?
- Аналогичный вопрос по поводу store.
- И где хоть какое-то сравнение производительности с той же pthread?
1. При написании статьи я опирался на использование стандарта C++11 для параллельного программирования. Поэтому некоторые другие возможности языка C++11 я не использовал.
2. isNotWaiting используется в логике класса. Собственно, на её значении и строится условная переменная, а именно она используется в условии выхода из сна: waitVariable.wait(lock,[&]{ return isNotWaiting;});, при этом изменение её на true приведёт к тому, что потоки пойдут дальше.
3-4. В данном случае действительно можно использовать обычный инкремент, однако я лишь хотел явно указать на атомарный характер этих операций.
2. isNotWaiting используется в логике класса. Собственно, на её значении и строится условная переменная, а именно она используется в условии выхода из сна: waitVariable.wait(lock,[&]{ return isNotWaiting;});, при этом изменение её на true приведёт к тому, что потоки пойдут дальше.
3-4. В данном случае действительно можно использовать обычный инкремент, однако я лишь хотел явно указать на атомарный характер этих операций.
Ваш код написан вроде как в расчете на скорость. Так вот, неиспользование списка инициализации формально означает двойную работу — сначала будет выполнено присваивание значений по умолчанию, а потом — присваивание в теле конструктора. Возможно, что это уберет оптимизатор. А возможно, не уберет.
Про переменную мне теперь все понятно.
Хорошо бы сравниться с реализацией в манере спинлока — когда процесс, подойдя к барьеру, начинает вертеться на счетчике этого барьера до момента его обнуления. В определенном смысле, это более отзывчивый вариант.
Про переменную мне теперь все понятно.
Хорошо бы сравниться с реализацией в манере спинлока — когда процесс, подойдя к барьеру, начинает вертеться на счетчике этого барьера до момента его обнуления. В определенном смысле, это более отзывчивый вариант.
Со мной связался некто stepanovdenis91g, и просил передать, что возможно, в данном коде возникает еще и состояние гонки:
Я автору намекал на то, что консистентность между предикатом и условием никак не обеспечена, но он пропустил это мимо ушей.
Здравствуйте, вы недавно оставляли комментарий к статье про барьер на С++11 (http://habrahabr.ru/post/246947).
Мне кажется, что реализация автора при неудачных обстоятельствах вызывает race condition. Конкретно, если после проверки isNotWaiting в предикате и до вызова wait на unique_lock произойдет вызов notify_all в другом потоке.
В качестве примера: coliru.stacked-crooked.com/a/026144ca755fbde8
К сожалению, на хабре я не зарегистрирован и связаться с автором не могу. Не могли бы вы передать это сообщение автору оригинальной статьи?
Я автору намекал на то, что консистентность между предикатом и условием никак не обеспечена, но он пропустил это мимо ушей.
Если говорить про condition variable из pthread, так там рекомендуется выполнять pthread_cond_signal с захваченным мьютексом. Не знаю, как с этим в С++11?
Кроме того, исходя из логики вашего barrier::wait, мьютекс лочится для всех потоков, кроме последнего, который всех разблокирует. Считаю, что игра не стоит свеч и мы можем себе позволить лочить мьютекс всегда, и отказаться от атомарных операций в реализации.
Кроме того, исходя из логики вашего barrier::wait, мьютекс лочится для всех потоков, кроме последнего, который всех разблокирует. Считаю, что игра не стоит свеч и мы можем себе позволить лочить мьютекс всегда, и отказаться от атомарных операций в реализации.
Атомарные операции приятны тем, что мы можем не обращаться к IPC и не осуществлять никаких контекстных переключений, используя их.
Да, вы конечно правы, но мы же сейчас обсуждаем конкретный пример логики в barrier::wait, а там необходимо захватить мьютекс, такие требования для std::condition_variable::wait.
Кстати я не знаю деталий реализации С++11, но немного интересовался, как все внутри pthread реализовано. Так вот, мьютекс реализован как спин-лок + futex, если мы укладываемся в ограничение по числу итераций на спинлоке, операция блокирования мьютекса целиком выполняется в юзерспейсе (если нет, уходим в ядро по futex_wait).
Кстати я не знаю деталий реализации С++11, но немного интересовался, как все внутри pthread реализовано. Так вот, мьютекс реализован как спин-лок + futex, если мы укладываемся в ограничение по числу итераций на спинлоке, операция блокирования мьютекса целиком выполняется в юзерспейсе (если нет, уходим в ядро по futex_wait).
Этим я пытаюсь указать автору на то, что стоило бы посмотреть на возможность реализации барьера как вариации на тему спинлока, если речь идет о попытках поймать производительность за хвост.
Также замечаю, что коль скоро у нас речь пошла о изобретении примитива синхронизации, стоило бы хотя бы заикнуться о взаимодействии с барьерами памяти. Потому как синхронизация-барьеры, они как Ленин и Партия (или, как волны — частицы, кому что ближе). Здесь же этот вопрос оставлен на умолчания C++11.
Также замечаю, что коль скоро у нас речь пошла о изобретении примитива синхронизации, стоило бы хотя бы заикнуться о взаимодействии с барьерами памяти. Потому как синхронизация-барьеры, они как Ленин и Партия (или, как волны — частицы, кому что ближе). Здесь же этот вопрос оставлен на умолчания C++11.
UFO just landed and posted this here
И вообще я за то, чтобы не использовать префикс is, если нет 99% уверенности, что флажок не будут обращать. Потому что
not isSomething читается стрёмно.Дополню эти безусловно положительные идеи тем, что флаг можно оставить без «is» (при правильном проектировании, флаг в любом случае будет недоступен снаружи класса), а вот геттер можно обозвать isSomething, а инвертирующий геттер — isNotSomething
В таком случае, на идею с инвертированием самого содержимого флага стоит смотреть под таким углом — если семантическое инвертирование приводит к тому, что нам в дальнейшем приходится все время этот флаг обращать — лучше от этого обращения отказаться, дабы не обогревать атмосферу.
В таком случае, на идею с инвертированием самого содержимого флага стоит смотреть под таким углом — если семантическое инвертирование приводит к тому, что нам в дальнейшем приходится все время этот флаг обращать — лучше от этого обращения отказаться, дабы не обогревать атмосферу.
P. S. Несложно из приведённого кода догадаться, что это «одноразовый» барьер: как только через него пройдут все потоки, вы не сможете повторно использовать этот же экземпляр класса в качестве барьера.
Несложно упростить код до многоразового:
class barrier {
const unsigned int threadCount;
std::atomic<unsigned int>threadsWaiting;
std::condition_variable waitVariable;
std::mutex mutex;
public:
barrier(unsigned int n) : threadCount(n) {
threadsWaiting = 0;
}
barrier(const barrier &) = delete;
void wait() {
std::unique_lock<std::mutex> lock(mutex);
if (threadsWaiting.fetch_add(1) >= threadCount - 1) {
threadsWaiting.store(0);
waitVariable.notify_all();
}
else {
waitVariable.wait(lock);
}
}
};
barrier(const barrier &) = delete;
а где
barrier& operator=(const barrier &) = delete;
?
а где
barrier& operator=(const barrier &) = delete;
?
Было бы интересно, если бы:
1) реентерабельность (в данном случае — повторное использование, иначе не интересно)
2) сравнение с каким-нибудь #pragma omp barrier, например
3) free-lock барьер (атомики + CAS) и сравнение с ним
Сравнение — несколько потоков, крутящие цикл, с небольшими вычислениями и барьером. Критерий — время исполнения.
1) реентерабельность (в данном случае — повторное использование, иначе не интересно)
2) сравнение с каким-нибудь #pragma omp barrier, например
3) free-lock барьер (атомики + CAS) и сравнение с ним
Сравнение — несколько потоков, крутящие цикл, с небольшими вычислениями и барьером. Критерий — время исполнения.
Классическая задача под такое — метод простой итерации.
Фактически, нужны два прямоугольных массива. В каждом прогоне барьера содержимое внутренних точек второго массива считается как одна четверть от суммы верхнего-нижнего-левого-правого соседей соответствующего элемента первого массива.
Значение на границе — ну можно константы задать по верхней и нижней, а по левой и правой — копировать значения из внутренних точек, лежащих у границы (B[0,i]=A[1,i]; B[N-1,i]=A[N-1,i];)
После прохождения барьера массивы меняются ролями и все повторяется.
Это как раз практический пример, когда нужно использовать барьер.
Фактически, нужны два прямоугольных массива. В каждом прогоне барьера содержимое внутренних точек второго массива считается как одна четверть от суммы верхнего-нижнего-левого-правого соседей соответствующего элемента первого массива.
Значение на границе — ну можно константы задать по верхней и нижней, а по левой и правой — копировать значения из внутренних точек, лежащих у границы (B[0,i]=A[1,i]; B[N-1,i]=A[N-1,i];)
После прохождения барьера массивы меняются ролями и все повторяется.
Это как раз практический пример, когда нужно использовать барьер.
Метод простой итерации
1) нелинейный. Решаем уравнение f(x)=0, можем его привести к виду (можно по-разному)
x = g(x)+b.
Пишем итерационный процесс x^{k+1} = g(x^k)+b
2) СЛАУ. Ищем решение системы Ax=b, приводим к виду x = Bx + c
Итерационный процесс: x^{k+1} = Bx^k + c
3) То же самое. Связано с нестационарными задачами на установление, или (оно же) явная схема Эйлера по одной из переменных.
Ваша интерпретация, может быть, имеет место, но сходу не соображу, как. В любом случае, при распараллеливании умножения матрицы на вектор в конце каждой итерации требуется барьер. А потом еще один — на определение невязки (или разницы между итерациями). Так что да, согласен, в качестве тестовой задачи подходит.
1) нелинейный. Решаем уравнение f(x)=0, можем его привести к виду (можно по-разному)
x = g(x)+b.
Пишем итерационный процесс x^{k+1} = g(x^k)+b
2) СЛАУ. Ищем решение системы Ax=b, приводим к виду x = Bx + c
Итерационный процесс: x^{k+1} = Bx^k + c
3) То же самое. Связано с нестационарными задачами на установление, или (оно же) явная схема Эйлера по одной из переменных.
Ваша интерпретация, может быть, имеет место, но сходу не соображу, как. В любом случае, при распараллеливании умножения матрицы на вектор в конце каждой итерации требуется барьер. А потом еще один — на определение невязки (или разницы между итерациями). Так что да, согласен, в качестве тестовой задачи подходит.
Моя интерпретация — это ваше 2. СЛАУ получается применением метода конечных разностей или контрольного объема к уравнению вида 
, которое может служить для моделирования стационарной теплопроводности.
Если аккуратно выполнить все шаги МКР или МКО, составится СЛАУ, решение которой простой итерацией и будет фактически состоять в том процессе, что я описал выше.
, которое может служить для моделирования стационарной теплопроводности.Если аккуратно выполнить все шаги МКР или МКО, составится СЛАУ, решение которой простой итерацией и будет фактически состоять в том процессе, что я описал выше.
ну да, получится пятидиагональная матрица (в прямоугольной области, с ортогональной или топологически эквивалентной ортогональной, сеткой, с определенной нумерацией). Я так понимаю, еще и с краевыми условиями первого рода. Зря мне кажется, вы слишком уж геометрически это все интерпретируете в данном случае (я про суммы сверху-снизу-справа-слева), тогда бы уж h^2 куда-то… а то и (h_x)^2, (h_y)^2 :)
В такой постановке шаг культурненько сократится в процессе построения метода.
ГУ только первого рода задать конечно же можно, но будет не интересно (если силком не рвать значения на границах конечно же. Но появление разрывов в ГУ автоматически потребует нерегулярной сетки и вся простота сразу исчезнет — МКО и МКР на нерегулярной сетке превращаются в мучение. Конечно, на помощь придет метод конечных элементов, но у нас же иллюстративный пример).
Поэтому в той схеме счета, что я предложил, условия двух родов — на верхней и нижней границах температура задана (условие первого рода), на боковых — задано отсутствие теплового потока (условие второго рода).
Это соответствует тонкой однородной пластине, теплоизолированной по бокам и термостатированной по двум другим бокам. Решение такой задачи известно — будет линейное изменение температуры от верха до низа.
ГУ только первого рода задать конечно же можно, но будет не интересно (если силком не рвать значения на границах конечно же. Но появление разрывов в ГУ автоматически потребует нерегулярной сетки и вся простота сразу исчезнет — МКО и МКР на нерегулярной сетке превращаются в мучение. Конечно, на помощь придет метод конечных элементов, но у нас же иллюстративный пример).
Поэтому в той схеме счета, что я предложил, условия двух родов — на верхней и нижней границах температура задана (условие первого рода), на боковых — задано отсутствие теплового потока (условие второго рода).
Это соответствует тонкой однородной пластине, теплоизолированной по бокам и термостатированной по двум другим бокам. Решение такой задачи известно — будет линейное изменение температуры от верха до низа.
Шаг сократится, если он одинаков в обоих направлениях. А теперь для разнообразия представьте себе сетку, топологически эквивалентную ортогональной, но в прямоугольной трапеции. Метод конечных объемов при этом в мучение не превращается, между прочим. Ну и переход от оператора Лапласа к тепловому потоку — это не очень математично :) мало ли, что за процесс. Тем более, что в реальных тепловых задачах оператор Лапласа в чистом виде встретить затруднительно.
Пример со стационарной задачей теплопроводности у меня иллюстративный, а потому — максимально упрощенный. Специально для того, чтобы показать студентам, как при обрастании матмодели уточнениями, соответствующая программа и математическое описание также начинают обрастать.
Про мучения с методами — я написал, что неприятности будут, если условия на границе будут с разрывами [если на границе задавать условие первого рода, то это будет одна константа на всю границу. И в итоге в нашей задаче мы получим всю область забитую этой константой] (Если же устроить разные константы на границе, необходимо будет у границы сетку сгустить. Без этого, рваные ГУ на границе очень легко могут испортить все решение).
А вы приводите пример с границей, которая все еще остается по сути прямоугольником, по этой причине, для нее и МКО работает относительно безболезненно.
О граничных условиях — я описывал пример физической задачи, которая в итоге приводит к такому алгоритму. И в этом примере описал ГУ в терминах задачи. На математическом языке это будет означать, что производная по нормали к границе будет равна нулю.
Про мучения с методами — я написал, что неприятности будут, если условия на границе будут с разрывами [если на границе задавать условие первого рода, то это будет одна константа на всю границу. И в итоге в нашей задаче мы получим всю область забитую этой константой] (Если же устроить разные константы на границе, необходимо будет у границы сетку сгустить. Без этого, рваные ГУ на границе очень легко могут испортить все решение).
А вы приводите пример с границей, которая все еще остается по сути прямоугольником, по этой причине, для нее и МКО работает относительно безболезненно.
О граничных условиях — я описывал пример физической задачи, которая в итоге приводит к такому алгоритму. И в этом примере описал ГУ в терминах задачи. На математическом языке это будет означать, что производная по нормали к границе будет равна нулю.
атомики плюс локфри список заснувших потоков с узлами на их стеках: кто последний пришёл, тот всех по списку будит.
Идея хорошая, но как исключить гонку при пробуждении? Как отловить последнего?
Это каждый поток должен при декременте убеждаться, что именно его декремент привел к получению 0. А затем бежать по соседям — будить. Так не проще ли всем сразу по окончании начинать вертеться на спинлоке, ожидая обнуления, а потом сразу двигать дальше.
Без лишне сущности — персонального списка заснувших потоков.
Это каждый поток должен при декременте убеждаться, что именно его декремент привел к получению 0. А затем бежать по соседям — будить. Так не проще ли всем сразу по окончании начинать вертеться на спинлоке, ожидая обнуления, а потом сразу двигать дальше.
Без лишне сущности — персонального списка заснувших потоков.
Атомарный декремент позволяет узнать, кто именно обнулил ;-)
А спинлок хорош, если мамой клянёшься, что все потоки придут более-менее одновременно, и никто не затупит.
А спинлок хорош, если мамой клянёшься, что все потоки придут более-менее одновременно, и никто не затупит.
А покажите примерчик, который узнает, кто именно обнуляет переменную.
Узнать кто именно обнуляет/достигает максимума — просто. Сложнее остановить последующий декремент/инкремент остальными потоками.
Например
#include <iostream>
#include <vector>
#include <thread>
#include <atomic>
std::atomic<bool> ready(false);
std::atomic<unsigned int> counter(0);
unsigned int MAX_COUNTER = 10000000;
const size_t MAX_THREADS = 50;
void f()
{
while (!ready) {
std::this_thread::yield();
}
while (counter < MAX_COUNTER) {
if (++counter == MAX_COUNTER) {
std::cout << "winner thread #" << std::this_thread::get_id() << std::endl;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<std::thread> threads;
for (size_t i = 0; i < MAX_THREADS; ++i)
threads.push_back(std::thread(f));
ready = true;
for (auto& th : threads) th.join();
std::cout << "counter val = " << counter << std::endl;
getchar();
return 0;
}
Sign up to leave a comment.
Создание барьера синхронизации с использованием C++11