Каков правильный способ реализации барьера потока и сброса барьера в C?

Я попытался реализовать простой барьер в своем коде, который выглядит так:

void waitOnBarrier(int* barrier, int numberOfThreads) {
    atomicIncrement(barrier); // atomic increment implemented in assembly
    while(*barrier < numberOfThreads);
}

И затем в коде есть использование барьера:

int g_barrier = 0; // a global variable

waitOnBarrier(&g_barrier, someKnownNumberOfThreads);

Пока все хорошо, но где я должен обнулить переменную g_barrier? Если я напишу что-то вроде

g_barrier = 0;

сразу после вызова waitOnBarrier у меня возникнет проблема, если один из потоков выйдет из барьера быстрее других и аннулирует g_barrier, в то время как все остальные потоки продолжают выполняться инструкции цикла, так что в конце концов они застрянут на барьере навсегда.

Объяснение: waitOnBarrier скомпилируется примерно так (псевдокод):

1: mov rax, numberOfThreads
2: mov rbx, [barrier]
3: cmp rax, rbx
4: jmp(if smaller) to 2

Итак, если у нас есть 2 потока, синхронизирующихся на барьере, и thread_1 медленный где-то в инструкции 3 или 4, в то время как более быстрый thread_2 достигает барьера, проходит его и переходит к Поток аннулирования g_barrier. Это означает, что после того, как thread_1 достигнет инструкции 2, он увидит нулевое значение на [барьере] и навсегда застрянет на барьере!

Вопрос в том, как мне обнулить g_barrier, какое место для него в коде "достаточно далеко", чтобы я мог быть уверен, что к тому времени все потоки покинули барьер? Или есть более правильный способ реализовать барьер?


c multithreading x86 barrier
person user1483597    schedule 07.10.2014    source источник
comment
Есть ли причина, по которой вы не хотите использовать библиотеку синхронизации потоков, поставляемую с вашей операционной системой?   -  person ArjunShankar    schedule 07.10.2014
comment
Да, мой код работает в определенной среде, а не в обычной ОС.   -  person user1483597    schedule 07.10.2014
comment
И есть ли особая причина для реализации этого без блокировки?   -  person ArjunShankar    schedule 07.10.2014
comment
Начиная с C11, C имеет атомарные типы как часть языка, и компиляторы начинают его реализовывать. Если ваш компилятор этого не делает, я думаю, что все же стоит использовать концепции, которые предлагает этот стандарт. В частности, вы должны использовать что-то похожее на atomic_flag с операциями проверки и установки для реализации ожидания занятости. Не изобретайте велосипед и сделайте свой код перспективным.   -  person Jens Gustedt    schedule 07.10.2014

Ответы (4)


arrow_upward
3
arrow_downward

Барьеры на самом деле довольно сложно реализовать, основная причина в том, что новые официанты могут начать прибывать до того, как все старые официанты получат возможность выполнить, что исключает любую простую реализацию на основе подсчета. Мое предпочтительное решение состоит в том, чтобы сам объект барьера просто указывал на «текущий экземпляр барьера», который существует в стеке первого потока, достигающего барьера, и который также будет последним потоком, который покинет барьер (поскольку он не может покинуть, пока другие потоки все еще ссылаются на его стек). Очень хороший пример реализации с точки зрения примитивов pthread (которые могут быть адаптированы к примитивам блокировки C11 или тому, с чем вам приходится работать) включен в ответ Майкла Берра на мой прошлый вопрос по теме:

https://stackoverflow.com/a/5902671/379897

Да, это выглядит как много работы, но написание реализации барьера, которая действительно удовлетворяет контракту барьера, нетривиальна.

person R.. GitHub STOP HELPING ICE    schedule 07.10.2014

arrow_upward
1
arrow_downward

Я столкнулся с этим вопросом, пытаясь сделать что-то подобное, поэтому я решил поделиться своим решением, если кто-то еще сочтет его полезным. Он реализован на чистом C++11 (к сожалению, не на C11, поскольку многопоточная часть стандарта пока не поддерживается в gcc и msvc).

По сути, вы поддерживаете два счетчика, использование которых чередуется. Ниже приведена реализация и пример использования:

    #include <cstdio>
    #include <thread>
    #include <condition_variable>

    // A barrier class; The barrier is initialized with the number of expected threads to synchronize
    class barrier_t{
        const size_t count;
        size_t counter[2], * currCounter;
        std::mutex mutex;
        std::condition_variable cv;

    public:
        barrier_t(size_t count) : count(count), currCounter(&counter[0]) {
            counter[0] = count;
            counter[1] = 0;
        }
        void wait(){
            std::unique_lock<std::mutex> lock(mutex);
            if (!--*currCounter){
                currCounter += currCounter == counter ? 1 : -1;
                *currCounter = count;
                cv.notify_all();
            }
            else {
                size_t * currCounter_local = currCounter;
                cv.wait(lock, [currCounter_local]{return *currCounter_local == 0; });
            }
        }
    };

    void testBarrier(size_t iters, size_t threadIdx, barrier_t *B){
        for(size_t i = 0; i < iters; i++){
            printf("Hello from thread %i for the %ith time!\n", threadIdx, i);
            B->wait();
        }
    }

    int main(void){
        const size_t threadCnt = 4, iters = 8;
        barrier_t B(threadCnt);
        std::thread t[threadCnt];   
        for(size_t i = 0; i < threadCnt; i++) t[i] = std::thread(testBarrier, iters, i, &B);
        for(size_t i = 0; i < threadCnt; i++) t[i].join();
        return 0;
    }
person André Harder    schedule 18.03.2015

arrow_upward
0
arrow_downward

Не сбрасывайте переменную barrier обратно на ноль.

Когда любой из потоков собирается выйти, атомарно уменьшите переменную barrier на единицу.

Ваш барьер выглядит так, как будто вы не хотите, чтобы количество созданных рабочих потоков упало ниже numberOfThreads.

person Raunak Mukhia    schedule 07.10.2014
comment
Вопрос заключается в попытке реализовать барьер, при котором каждый поток ждет, пока все потоки не достигнут барьера, после чего все они продолжают работу. Ваша идея атомарного декремента не помогает для такого рода барьера, потому что потоки все равно могут пропустить пробуждение. - person Peter Cordes; 24.01.2019

arrow_upward
0
arrow_downward

Попробуйте реализовать Барьерное решение, которое объясняется в этой книге:

Маленькая книга семафоров

person Tal.Bary    schedule 07.10.2014