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.

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}$.

StackExchange Computer Science Q#30245, answer score: 4