# Is it possible to solve the critical section problem with an atomic subtract operation?

In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation:

int sub(int &x, int val){
x -= val;
return x;
}


The homework was already due and nobody in my class could come up with a solution. The professor's solution does not even work. Here it is:

int x = 1; //let x be a shared variable between threads
entry(){
int loop = sub(x, 1);
while(loop < 0){
loop = sub(x, 1);
}
}

exit(){
x = 1;
}


This solution suffers from the fact that the critical section may be very long, and thus x may loop all the way back around to positive values and eventually become zero before another thread calls exit(). I do not believe it is possible to solve the CS problem because this implementation of sub() does not return the original value of x, but the new value with val subtracted. The professor is convinced that it is possible, even though neither he nor the TA could come up with a proper answer.

• How long exactly do you think the critical region might take? A 1GHz computer that is busy-looping decrementing a 64-bit counter from zero will take nearly 300 years to underflow the counter. That seems pretty safe to me. – David Richerby Sep 24 '14 at 0:11
• That's fair. But, given a better suited atomic instruction, the problem could be avoided altogether. So yes, on a realistic computer it would not be a problem, but I want to know if the problem can be completely solved or not. Plus our professor thinks it's possible to solve without the underflow problem and I wanted to see what a solution would look like. – PeevedStudent Sep 24 '14 at 0:34
• @DavidRicherby I do agree: a solution that depends on computers being slow does not feel right. – Raphael Sep 24 '14 at 7:20
• @DavidRicherby Remind me not to hire you do design a space probe. Or anything with a 32-bit processor. And anyway if you care about realism, your objection should be about the choice of primitive (I've never heard of a platform where atomic subtraction was a primitive), not about the very realistic concern about overflowing the counter. – Gilles Sep 24 '14 at 8:29
• @Gilles Yes, a 32-bit counter could underflow in a couple of seconds, which is obviously unacceptable. I explicitly said "64-bit counter" and "300 years". – David Richerby Sep 24 '14 at 9:11

If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing test-and-test-and-set operation with atomic-fetch-and-decrement.

So, for example, if you have 32-bit integers and less than 4 billion threads the following should work:

initialize: x = 0

acquireLock:
repeat:
while x != 0:
# do nothing
tmp = atomicFetchAndDecrement(x) # (decrements x and returns *new* value of x)
until tmp == -1

releaseLock:
x = 0


Each thread only decrements the counter once for each time that it sees the counter get reset to 0, so the value of x never becomes smaller than -numberOfThreads.

The real value of fetch-and-increment is that you can make critical sections that are "fair" in the sense that threads are given the lock in the order in which they first request it. Like this:

initialize: nextTicket = 0; current = 0

acquireLock:
myTicket = atomicFetchAndDecrement(nextTicket)       # (decrements and then returns *new* value)
myTicket = myTicket + 1                # make up for the weird atomicFetchAndDecrement semantics
while current != myTicket:
# do nothing

releaseLock:
current = current - 1                  # does not need to be atomic, releaser is only writer


Again, with 32-bit integers this works as long as the number of threads is less than $2^{32}$.