Program halts: atomics example run

help
1 
use std::sync::atomic::{
    AtomicBool, AtomicUsize,
    Ordering::{Acquire, Relaxed, Release},
};

static COUNTER: AtomicUsize = AtomicUsize::new(0);
static GIVER: AtomicUsize = AtomicUsize::new(10);
static BOOL: AtomicBool = AtomicBool::new(false);

fn main() {
    std::thread::scope(|s| {
        for _ in 0..10 {
            s.spawn(|| {
                let v = GIVER.load(Relaxed);
                let load = COUNTER.load(Relaxed);
                COUNTER.store(load + v, Relaxed);
                BOOL.store(true, Release);
            });
            s.spawn(|| {
                while BOOL
                    .compare_exchange_weak(true, false, Acquire, Relaxed)
                    .is_err()
                {}
                GIVER.fetch_sub(1, Relaxed);
            });
        }
    });
    let c = COUNTER.load(Relaxed);
    println!("{}", c);
}

I have used Acquire Release pair to establish a happens-before relationship such that the first thread (in a single iteration) should execute everything first and then the second thread will continue but, my program as the description says, halts...so what's wrong here?

2

The next iteration of for does not wait for the old threads to finish their work (you'd need join for that).

Let's name threads spawned by the top spawn call as A, and the bottom one as B. Your program can have ...,A(9),A(10),B(9),B(10) scheduled; A(9) allows B to run, A(10) happens to do a no-op, B(9) consumes this permission, and B(10) has no opportunity to run. This is called a "lost wakeup" and would be solved by

while BOOL.compare_exchange_weak(false, true, Release, Relaxed) {}

P.S.

                let load = COUNTER.load(Relaxed);
                COUNTER.store(load + v, Relaxed);

this code is not a single atomic operation and thus is not equivalent to COUNTER.fetch_add(v, Relaxed).

3 Likes
3

yeah, that makes sense.

could you please elaborate a bit more on like how we can use this to solve the problem?

yeah, right. But if we properly synchronize and make sure that x happens before y then in that case this is not a problem, right? my thinking is like if x happens before y then nothing from y can execute in between x...can we use Acquire and Release combo in general to say this?

4

this is a longer explanation of what @ProgramCrafter just said :

let's make it simpler with 2 so we can say everything that happens. if it can lock with 2 it obviously can lock with 10.

you start with your 4 threads A(0), A(1),B(0), B(1).

BOOL is false.

the Bs do an underteminate amount of failed checks, while the As modify GIVER and COUNTER.

then A(0) sets BOOL to true
immedately after A(1) also sets BOOL to true
then B(1) succeeds at setting at setting BOOL from true to false.
it removes 1 from GIver
and B(0) keeps witing for BOOL to be set to false, which will never happen.

every happens-before relationship was correctly ensured.
but the B(0) thread is looping forever nonetheless.

this is of course just one scenario, and is not particualrly likely with just 2 threads.

but the more threads you add, the more likely this is to happen.

what are x and y supposed to be here ?
especially "in between x" makes little sense to me. atomic operations can happen before or after each other and opether operations, but but nothing can happen "between" one atomic operation.