Different OS, Different Support

This lesson discusses support provided by some other operating systems, specifically Linux.

We'll cover the following

You have thus far seen one type of support that an OS can provide in order to build a more efficient lock in a thread library. Other OS’s provide similar support; the details vary.

Futex

For example, Linux provides a futex which is similar to the Solaris interface but provides more in-kernel functionality. Specifically, each futex has associated with it a specific physical memory location, as well as a per-futex in-kernel queue. Callers can use futex calls (described below) to sleep and wake as need be.

Specifically, two calls are available. The call to futex_wait(address, expected) puts the calling thread to sleep, assuming the value at address is equal to expected. If it is not equal, the call returns immediately. The call to the routine futex_wake(address) wakes one thread that is waiting on the queue. The usage of these calls in a Linux mutex is shown below.

Press + to interact
void mutex_lock (int *mutex) {
  int v;
  /* Bit 31 was clear, we got the mutex (the fastpath) */
  if (atomic_bit_test_set (mutex, 31) == 0)
    return;
  atomic_increment (mutex);
  while (1) {
    if(atomic_bit_test_set (mutex, 31) == 0) {
      atomic_decrement (mutex);
      return;
    }
      /*We have to waitFirst make sure the futex value
         we are monitoring is truly negative (locked). */
      v = *mutex;
      if (v >= 0)
        continue;
      futex_wait (mutex, v);
  }
}
void mutex_unlock (int *mutex) {
  /* Adding 0x80000000 to counter results in 0 if and
     only if there are not other interested threads */
  if (atomic_add_zero (mutex, 0x80000000))
    return;
    
  /* There are other threads waiting for this mutex,
     wake one of them up.  */
  futex_wake (mutex);
}

This code snippet from lowlevellock.h in the nptl library (part of the gnu libc library)“glibc 2.9 (include Linux pthreads implementation)” by Many authors… Available here: http://ftp.gnu.org/gnu/glibc. In particular, take a look at the nptl subdirectory where you will find most of the pthread support in Linux today. is interesting for a few reasons. First, it uses a single integer to track both whether the lock is held or not (the high bit of the integer) and the number of waiters on the lock (all the other bits). Thus, if the lock is negative, it is held (because the high bit is set and that bit determines the sign of the integer).

Second, the code snippet shows how to optimize for the common case, specifically when there is no contention for the lock. With only one thread acquiring and releasing a lock, very little work is done (the atomic bit test-and-set to lock and an atomic add to release the lock).

See if you can puzzle through the rest of this “real-world” lock to understand how it works. Do it and become a master of Linux locking, or at least somebody who listens when a course tells you to do something.

Get hands-on with 1400+ tech skills courses.