A Failed Attempt: Just Using Loads/Stores

This lesson discusses how the use of loads and stores to implement locks, falls short.

We'll cover the following

To move beyond interrupt-based techniques, we will have to rely on CPU hardware and the instructions it provides us to build a proper lock. Let’s first try to build a simple lock by using a single flag variable. In this failed attempt, you’ll see some of the basic ideas needed to build a lock, and (hopefully) see why just using a single variable and accessing it via normal loads and stores is insufficient.

Press + to interact
typedef struct __lock_t { int flag; } lock_t;
void init(lock_t *mutex) {
  // 0 -> lock is available, 1 -> held
    mutex->flag = 0;
}
void lock(lock_t *mutex) {
  while (mutex->flag == 1)  // TEST the flag
    ; // spin-wait (do nothing)
    mutex->flag = 1; // now SET it!
}
void unlock(lock_t *mutex) {
  mutex->flag = 0;
}

In this first attempt (in the code widget above), the idea is quite simple: use a simple variable (flag) to indicate whether some thread has possession of a lock. The first thread that enters the critical section will call lock(), which tests whether the flag is equal to 1 (in this case, it is not), and then sets the flag to 1 to indicate that the thread now holds the lock. When finished with the critical section, the thread calls unlock() and clears the flag, thus indicating that the lock is no longer held.

If another thread happens to call lock() while that first thread is in the critical section, it will simply spin-wait in the while loop for that thread to call unlock() and clear the flag. Once that first thread does so, the waiting thread will fall out of the while loop, set the flag to 1 for itself, and proceed into the critical section.

Unfortunately, the code has two problems: one of correctness, and another of performance.

Correctness problem

The correctness problem is simple to see once you get used to thinking about concurrent programming. Imagine the code interleaving in the figure below; assume flag=0 to begin.

As you can see from this interleaving, with timely (untimely?) interrupts, you can easily produce a case where both threads set the flag to 1 and both threads are thus able to enter the critical section. This behavior is what professionals call “bad” – we have obviously failed to provide the most basic requirement: providing mutual exclusion.

Performance problem

The performance problem, which you will see more later on, is the fact that the way a thread waits to acquire a lock that is already held: it endlessly checks the value of the flag, a technique known as spin-waiting. Spin-waiting wastes time waiting for another thread to release a lock. The waste is exceptionally high on a uniprocessor, where the thread that the waiter is waiting for cannot even run (at least until a context switch occurs)! Thus, as we move forward and develop more sophisticated solutions, we should also consider ways to avoid this kind of waste.

Get hands-on with 1400+ tech skills courses.