Fetch-And-Add

Let's look at one last hardware primitive for building locks, the fetch-and-add instruction.

We'll cover the following

One final hardware primitive is the fetch-and-add instruction, which atomically increments a value while returning the old value at a particular address. The C pseudocode for the fetch-and-add instruction looks like this:

Press + to interact
int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

TIP: LESS CODE IS BETTER CODE (LAUER’S LAW)

Programmers tend to brag about how much code they wrote to do something. Doing so is fundamentally broken. What one should brag about, rather, is how little code one wrote to accomplish a given task. Short, concise code is always preferred; it is likely easier to understand and has fewer bugs. As Hugh Lauer said when discussing the construction of the Pilot operating system: “If the same people had twice as much time, they could produce as good of a system in half the code.”“Observations on the Development of an Operating System” by Hugh Lauer. SOSP ’81, Pacific Grove, California, December 1981. A must-read retrospective about the development of the Pilot OS, an early PC operating system. Fun and full of insights. We’ll call this Lauer’s Law, and it is well worth remembering. So next time you’re bragging about how much code you wrote to finish the assignment, think again, or better yet, go back, rewrite, and make the code as clear and concise as possible.

Ticket lock

In this example, we’ll use fetch-and-add to build a more interesting ticket lock, as introduced by Mellor-Crummey and Scott“Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors” by John M. Mellor-Crummey and M. L. Scott. ACM TOCS, Volume 9, Issue 1, February 1991. An excellent and thorough survey on different locking algorithms. However, no operating systems support is used, just fancy hardware instructions.. The lock and unlock code is given in the code excerpt below.

Press + to interact
typedef struct __lock_t {
    int ticket;
    int turn;
} lock_t;
void lock_init(lock_t *lock) {
  lock->ticket = 0; 
  lock->turn = 0;
}
void lock(lock_t *lock) {
  int myturn = FetchAndAdd(&lock->ticket);
  while (lock->turn != myturn)
    ; // spin
}
void unlock(lock_t *lock) {
    lock->turn = lock->turn + 1;
}

Instead of a single value, this solution uses a ticket and turn variable in combination to build a lock. The basic operation is pretty simple: when a thread wishes to acquire a lock, it first does an atomic fetch-and-add on the ticket value; that value is now considered this thread’s “turn” (myturn). The globally shared lock->turn is then used to determine which thread’s turn it is; when (myturn == turn) for a given thread, it is that thread’s turn to enter the critical section. Unlock is accomplished simply by incrementing the turn such that the next waiting thread (if there is one) can now enter the critical section.

Note one important difference with this solution versus our previous attempts: it ensures progress for all threads. Once a thread is assigned its ticket value, it will be scheduled at some point in the future (once those in front of it have passed through the critical section and released the lock). In our previous attempts, no such guarantee existed. For example, a thread spinning on test-and-set could spin forever even as other threads acquire and release the lock.

Get hands-on with 1400+ tech skills courses.