While loop in a method gets stuck. Adding an assignment of a field to itself fixes the issue

Question

Starting our Semaphore project, I gave my students a bad version of the p() method:

proc p() {
    while (this.tokens <= 0) {
        sleep(1);
        writeln("Tokens: ", this.tokens);
    }
    this.tokens -= 1;
}

I give them some additional code to test it which increments the number of tokens (using the v() method) in another thread. You can see the number of tokens increasing (above 0) but the code does not exit the while loop.

On a whim, I added an assignment statement:

proc p() {
    while (this.tokens <= 0) {
        this.tokens = this.tokens;
        sleep(1);
        writeln("Tokens: ", this.tokens);
    }
    this.tokens -= 1;
}

This solves the problem in the test runs (though it's even less thread-safe). Why does the original while loop get stuck and why does adding this assignment solve it?

Answer 1

Assuming p() and v() are being called from different tasks, there's no guarantee that writes to the non-atomic this.tokens in one task will ever be seen by a different task.

One solution would be to make tokens atomic and have something like:

proc p() {
  while (this.tokens.read() <= 0) {
    sleep(1);
    writeln("Tokens: ", this.tokens.read());
  }
  this.tokens.sub(1);
}

When tokens is not atomic, the compiler is free to assume that tokens won't be modified by other tasks, so it's probably transforming your code into something like:

var tokenTemp = this.token;
while (tokenTemp <= 0)
...

and inserting the write to token prevents that hoisting. That said, even with the write to token, it's still invalid/illegal/undefined code and could easily be tripped by some compiler/processor reordering in the future.

The code is illegal because it violates Chapel's Memory Consistency Model (MCM). Specifically, it's a data race, and Chapel only ensures sequential consistency for data-race-free programs.

The Memory Consistency Model is defined in the language spec (chapter 30 in https://chapel-lang.org/docs/1.16/_downloads/chapelLanguageSpec.pdf). It has a good and pretty accessible introduction paragraph. That said, since it's a language specification, the rest of the chapter is pretty dry and technical, so it's probably not the best place for developers to learn from.

For a shorter overview take a look at https://chapel-lang.org/CHIUW/2015/hot-topics/01-Ferguson.pdf (especially slide 10).

Beyond that, Chapel's memory model is based on C11/C++11, Java, UPC, and others. There's a host of great and accessible articles out there if you look for "C++11 memory model", "data race free program", or "sequential consistency"