Can competing atomic operations starve one another?

Question

Imagine a program with two threads. They are running the following code (CAS refers to Compare and Swap):

// Visible to both threads
static int test;

// Run by thread A
void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

// Run by thread B
void bar()
{
    while(1) {
        // Perpetually atomically write rand() into the test variable
        atomic_write(&test, rand());
    }
}

Is it possible for thread B to perpetually cause thread A's CAS to fail such that 0xdeadbeef is never written to 'test'? Or does natural scheduling jitter mean that in practice this never happens? What if some work was done inside thread A's while loop?

Answer 1

As a theoretical matter, yes. If you could manage somehow to get the two threads running in lockstep like this

    time     thread A     thread B
    ----     --------     --------
     ||       CAS
     ||                   atomic_write
     ||       CAS
     \/                   atomic_write

Then CAS would never return true.

In practice this will never happen when threads share a CPU/Core, and is unlikely to happen when threads are running on different CPUs or Cores. In practice it's incredibly unlikely to happen for more than few cycles, and astronomically unlikely to happen for more than a scheduler quantum.

And that's if this code

void foo()
{
    // Check if value is 'test' and swap in 0xdeadbeef
    while(!CAS(&test, test, 0xdeadbeef)) {}
}

does what it appears to do, which is to fetch the current value of test, and compare it to test to see if it has changed. In the real world iterations of CAS would be separated by code that did actual work. The volatile keyword would be needed to insure that the compiler fetched test before calling CAS rather than assuming that a copy it might still have in a register would still be valid.

Or the value that you would be testing against wouldn't be the current value of test, but rather some sort of last known value.

In other words, this code example is a test of the theory, but you wouldn't use CAS like this in practice, so even if you could get this to fail, it doesn't necessarily tell you how it could fail when used in real world algorithms.

Answer 2

Starvation surely can happen in such cases. Quoting the wikipedia page,

It has also been shown that the widely-available atomic conditional primitives, CAS and LL/SC, cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads. Wait-free algorithms are therefore rare, both in research and in practice.

(See the link from the page in question for the mathematical proof).