Load-Linked and Store-Conditional

Let's visit yet another pair of instructions that can be used to build locks: load-linked and store-conditional.

We'll cover the following

Some platforms provide a pair of instructions that work in concert to help build critical sections. On the MIPS architecture“MIPS R4000 Microprocessor User’s Manual” by Joe Heinrich. Prentice-Hall, June 1993. Available: http://cag.csail.mit.edu/raw/documents/R4400 Uman book Ed2.pdf. The old MIPS user’s manual. Download it while it still exists., for example, the load-linked and store-conditional instructions can be used in tandem to build locks and other concurrent structures. The C pseudocode for these instructions is as found in the code excerpt below. Alpha, PowerPC, and ARM provide similar instructions“Load-Link, Store-Conditional” by Many authors… en.wikipedia.org/wiki/Load- Link/Store-Conditional. Can you believe we referenced Wikipedia? But, we found the information there and it felt wrong not to. Further, it was useful, listing the instructions for the different architectures: ldl l/stl c and ldq l/stq c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM). Actually Wikipedia is pretty amazing, so don’t be so harsh, OK?.

Press + to interact
int LoadLinked(int *ptr) {
    return *ptr;
}
int StoreConditional(int *ptr, int value) {
    if (no update to *ptr since LoadLinked to this address) {
        *ptr = value;
        return 1; // success! 
    } else {
        return 0; // failed to update
    }
}

The load-linked operates much like a typical load instruction, and simply fetches a value from memory and places it in a register. The key difference comes with the store-conditional, which only succeeds (and updates the value stored at the address just load-linked from) if no intervening store to the address has taken place. In the case of success, the store-conditional returns 1 and updates the value at ptr to value; if it fails, the value at ptr is not updated and 0 is returned.

A challenge

As a challenge to yourself, try thinking about how to build a lock using load-linked and store-conditional. Then, when you are finished, look at the code below which provides one simple solution. Do it! You can see the solution by pressing the “Show Code” button below.

The lock() code is the only interesting piece. First, a thread spins waiting for the flag to be set to 0 (and thus indicate the lock is not held). Once so, the thread tries to acquire the lock via the store-conditional; if it succeeds, the thread has atomically changed the flag’s value to 1 and thus can proceed into the critical section.

Note how the failure of the store-conditional might arise. One thread calls lock() and executes the load-linked, returning 0 as the lock is not held. Before it can attempt the store-conditional, it is interrupted and another thread enters the lock code, also executing the load-linked instruction, and also getting a 0 and continuing. At this point, two threads have each executed the load-linked and each is about to attempt the store-conditional. The key feature of these instructions is that only one of these threads will succeed in updating the flag to 1 and thus acquire the lock. The second thread to attempt the store-conditional will fail because the other thread updated the value of flag between its load-linked and store- conditional, and thus have to try to acquire the lock again.

In a class a few years ago, undergraduate student David Capel suggested a more concise form of the above, for those of you who enjoy short-circuiting boolean conditionals. See if you can figure out why it is equivalent. It certainly is shorter!

Press + to interact
void lock(lock_t *lock) {
  while (LoadLinked(&lock->flag) ||
        !StoreConditional(&lock->flag, 1))
      ; // spin
}

Get hands-on with 1400+ tech skills courses.