Create a function that will block until it was called by more than n/2 threads (pseudocode)

Question

There are n threads. I'm trying to implement a function (pseudo code) which will directly block if it's called by a thread. Every thread will be blocked and the function will stop blocking threads if it was called by more than n/2 threads. If more than n/2 threads called the function, the function will no longer block other threads and will immediately return instead.

I did it like this but I'm not sure if I did the last part correctly where the function will immediately return if more than n/2 threads called it? :S

(Pseudocode is highly appreciated because then I have a better chance to understand it! :) )

int n = total amount of threads
sem waiter = 0
sem mutex = 1
int counter = 0

function void barrier()
    int x
    P(mutex)
    if counter > n / 2 then
        V(mutex)
        for x = 0; x <= n / 2; x++;
            V(waiter)
        end for
    end if
    else
        counter++
        V(mutex)
        P(waiter)
    end else
end function

Answer 1

What you describe is a non-resetting barrier. Pthreads has a barrier implementation, but it is of the resetting variety.

To implement what you're after with pthreads, you will want a mutex plus a condition variable, and a shared counter. A thread entering the function locks the mutex and checks the counter. If not enough other threads have yet arrived then it waits on the CV, otherwise it broadcasts to it to wake all the waiting threads. If you wish, you can make it just the thread that tips the scale that broadcasts. Example:

struct my_barrier {
    pthread_mutex_t barrier_mutex;
    pthread_cond_t barrier_cv;
    int threads_to_await;
};

void barrier(struct my_barrier *b) {
    pthread_mutex_lock(&b->barrier_mutex);
    if (b->threads_to_await > 0) {
        if (--b->threads_to_await == 0) {
            pthread_cond_broadcast(&b->barrier_cv);
        } else {
            do {
                pthread_cond_wait(&b->barrier_cv, &b->barrier_mutex);
            } while (b->threads_to_await);
        }
    }
    pthread_mutex_unlock(&b->barrier_mutex);
}

Update: pseudocode

Or since a pseudocode representation is important to you, here's the same thing in a pseudocode language similar to the one used in the question:

int n = total amount of threads
mutex m
condition_variable cv
int to_wait_for = n / 2

function void barrier()
    lock(mutex)

    if to_wait_for == 1 then
        to_wait_for = 0
        broadcast(cv)
    else if to_wait_for > 1 then
        to_wait_for = to_wait_for - 1
        wait(cv)
    end if

    unlock(mutex)
end function

That's slightly higher-level than your pseudocode, in that it does not assume that the mutex is implemented as a semaphore. (And with pthreads, which you tagged, you would need a pthreads mutex, not a semaphore, to go with a pthreads condition variable). It also omits the details of the real C code that deal with spurrious wakeup from waiting on the condition variable and with initializing the mutex and cv. Also, it presents the variables as if they are all globals -- such a function can be implemented that way in practice, but it is poor form.

Note also that it assumes that pthreads semantics for the condition variable: that waiting on the cv will temporarily release the mutex, allowing other threads to lock it, but that a thread that waits on the cv will reacquire the mutex before itself proceeding past the wait.

Answer 2

A few assumptions I am making within my answer:

• P(...) is analogous to sem_wait(...)
• V(...) is analogous to sem_post(...)
• the barrier cannot be reset

---

I'm not sure if I did the last part correctly where the function will immediately return if more than n/2 threads called it

The pseudocode should work fine for the most part, but the early return/exit conditions could be significantly improved upon.

Some concerns (but nothing major):

• The first time the condition counter > n / 2 is met, the waiter semaphore is signaled (i.e. V(...)) (n / 2) + 1 times (since it is from 0 to n / 2 inclusive), instead of n / 2 (which is also the value of counter at that moment).
• Every subsequent invocation after counter > n / 2 is first met will also signal (i.e. V(...)) the waiter semaphore another (n / 2) + 1 times. Instead, it should early return and not re-signal.

These can be resolved with a few minor tweaks.

int n = total count of threads
sem mutex = 1;
sem waiter = 0;
int counter = 0;
bool released = FALSE;

function void barrier() {
    P(mutex)
    // instead of the `released` flag, could be replaced with the condition `counter > n / 2 + 1`
    if released then
        // ensure the mutex is released prior to returning
        V(mutex)
        return
    end if

    if counter > n / 2 then
        // more than n/2 threads have tried to wait, mark barrier as released
        released = TRUE
        // mutex can be released at this point, as any thread acquiring `mutex` after will see that `release` is TRUE and early return
        V(mutex)
        // release all blocked threads; counter is guaranteed to never be incremeneted again
        int x
        for x = 0; x < counter; x++
            V(waiter)
        end for
    else
        counter++
        V(mutex)

        P(waiter)
    end else
}