Locks and modularity

When designing a system we desire clean abstractions and good modularity. We'd like a caller not to have to know how a callee implements a particular function. We'd like to hide locking behavior in this way -- for example, it would be nice if the lock on each file-system inode was the private business of methods on inodes.

It turns out it's hard to use locks in a modular way. Two problems come up that require non-modular global knowledge: multi-module invariants and deadlock.

First, multi-module invariants. You could imagine the code implementing directories exporting various operations like dir_lookup(d, name), dir_add(d, name, inumber), and dir_del(d, name). These directory operations would each acquire the lock on d, do their work, and release the lock. Then higher-level code could implement operations like moving a file from one directory to another (one case of the UNIX rename() system call):

move(olddir, oldname, newdir, newname){
  inumber = dir_lookup(olddir, oldname)
  dir_del(olddir, oldname)
  dir_add(newdir, newname, inumber)
}

move(olddir, oldname, newdir, newname){
  acquire(olddir.lock)
  acquire(newdir.lock)
  inumber = dir_lookup(olddir, oldname)
  dir_del(olddir, oldname)
  dir_add(newdir, newname, inumber)
  release(newdir.lock)
  release(olddir.lock)
}

The above code is ugly in that it exposes the implementation of directories to move(), but (if all you have is locks) you have to do it this way.

The second big problem is deadlock. Notice that move() holds two locks. What would happen if one process called move(dirA, ..., dir B, ...) while another process called move(dirB, ..., dir A, ...)?

In an operating system the usual solution is to avoid deadlocks by establishing an order on all locks and making sure that every thread acquires its locks in that order. For the file system the rule might be to lock the directory with the lowest inode first. Picking and obeying the order on all locks requires that modules make public their locking behavior, and requires them to know about other module's locking. This can be painful and error-prone.

Fine-grained locks usually make both of these problems worse.

Some terms

Locks are a way to implement "mutual exclusion", which is the property that only one CPU at a time can be executing a certain piece of code. This is also called "isolation atomicity".

The code between an acquire() and a release() is sometimes called a "critical section."

The more general idea of ensuring one thread waits for another when neccessary for correctness is called "coordination." People have invented a huge number of coordination primitives; locks are just one example, which we use because they are simple. We'll see some more coordination primitives next.

Spin Lock Subtleties

                           -------------
                          | Main Memory |  (containing l->locked)
                           -------------
                                  |
                                  |
        --------|-----------------|----------------|------
        --------|-----------------|----------------|------   Bus
        --------|-----------------|----------------|------
                |                                  |
                |                                  |
              cache0                             cache1
             --------                           --------
             | CPU0 |                           | CPU1 |
             --------                           --------

Thus if CPU0 access location X, a 100 times (without any intervening access to X by CPU1), the first access will result in a bus transaction (whereby X will be fetched either from the main memory, or from CPU1's cache through the cache coherence protocol). All the other 99 accesses will be served locally from cache0, without incurring a bus transaction. In a multiprocessor system, the bus often becomes a performance bottleneck (especially if the number of CPUs is high), and so reducing the number of bus transactions is an important optimization.

In our implementation of acquire() and release(), we use the atomic xchg instruction that needs to perform two memory accesses (one read and one write) in an atomic fashion. This can only be achieved by a bus transaction, because all other processors need to be informed that the two memory accesses need to be done atomically. Hence, if a CPU is spin-waiting inside a lock acquire function, it is constantly making bus transactions, which can severely affect performance.

void acquire(struct lock *l) {
  Reg = 1;
  while (xchg(Reg, &l->locked) == 1);
}
void release(struct lock *l) {
  l->locked = 0;
}

Instead, it may be better to write the code like this:

void acquire(struct lock *l) {
  Reg = 1;
  while (xchg(Reg, &l->locked) == 1) {
    while (l->locked == 1);
  }
}
void release(struct lock *l) {
  l->locked = 0;
}

Effect of Compiler/Architecture Optimizations

Compiler optimizations typically do not work well with code that can be executed concurrently. Using locks, we have ensured that the only code that can execute concurrently are the acquire() and release() functions. Let's see what could happen if the compiler tries to optimize our acquire() and release() implementation.

Register allocation of variables

a = 1;
b = a + 2;
a = a + 1;

load  a, Reg     //load 'a' from memory to register
b = Reg + 2
Reg = Reg + 1
store Reg, a     //store current value of 'a' from register to memory

Intelligent register allocation reduces the number of memory accesses, and thus reduces memory accesses. But what would happen if the l->locked variable in our acquire() function gets register allocated. It will result in an infinite loop inside acquire, causing a deadlock.

Because compiler optimizations assume sequential code, they do not play well with code that could be executed concurrently. Languages typically provide ways to tell the compiler to not optimize accesses to certain variables (for example, the volatile keyword in C). In this case, we should either write the waiting loop in assembly, or use the volatile keyword appropriately to ensure that the l->locked variable does not get register allocated.

Reordering of Memory Accesses

a = 2;
b = 3;

b = 3;
a = 2;

In our lock implementation, if the access to a shared variable gets reordered with the access to the lock variable (l->locked), our semantics get violated. For example,

acquire(l);
hits++;
release(l);

acquire(l);
release(l);
hits++;

To avoid this, it is possible to tell the compiler and the hardware to not reorder instructions. Many architectures that support out-of-order execution, also provide "fence" instructions, which can be used to instruct the hardware to not reorder memory accesses across the fence instruction. On the x86 architecture, the locked xchg instruction implicitly also acts as a fence, so our acquire implementation is correct even in the presence of memory access reordering. However, we need to explicitly insert a fence instruction in our release() implementation like this:

void acquire(struct lock *l) {
  Reg = 1;
  while (xchg(Reg, &l->locked) == 1) {
    while (l->locked == 1);
  }
}
void release(struct lock *l) {
  fence;   //assembly instruction
  l->locked = 0;
}

Spinlock implementations inside the kernel

For a multiprocessor kernel, spin locks as implemented above suffice for ensuring mutual exclusion among different CPUs. However, this still does not protect a CPU from its own interrupt handler. For example, if an interrupt can occur within a critical section, and the interrupt handler could access the shared data (which was also being accessed within the critical section), mutual exclusion would get violated. On xv6, this is true for the process table ptable, for example, where the timer handler may need to inspect the ptable and may find it in an inconsistent state, if the timer interrupt occurred in the middle of an access to the ptable. Worse, if the timer handler also tries to acquire the ptable.lock, it would result in a deadlock.

To deal with this, xv6's spinlock also disables the interrupts on a call to acquire, and reenables them on a call to release. To allow a thread to acquire multiple locks simultaneously, the interrupts are enabled and disabled in a recursive manner, as follows:

void acquire(struct lock *l) {
  Reg = 1;
  pushcli();
  while (xchg(Reg, &l->locked) == 1) {
    while (l->locked == 1);
  }
}
void release(struct lock *l) {
  fence;   //assembly instruction
  l->locked = 0;
  popcli();
}

void pushcli(void) {
  if (cpu->ncli == 0) {
    cli;
  }
  cpu->ncli++;
}
void popcli(void) {
  cpu->ncli--;
  if (cpu->ncli == 0) {
    sti;
  }
}

Spinlock implementations in the user-mode

Blocking Locks

Notice that the accesses to the ptable also need to be mutually exclusive. This is done using a spinlock (ptable.lock in the case of xv6). Hence, a blocking lock typically uses a spinlock internally. Of course, the spinlock is released, as soon as the ptable is updated.

Blocking locks at user-level

If the threads are user-level threads however, all this can be done entirely in userspace, without any kernel involvement. For user-level threads, the ptable itself will be maintained (and manipulated) at the user-level.

Locking Variations

Recursive locks

One proposal to solve this issue is to allow the same thread to acquire a lock multiple times, but still disallow different threads to acquire the lock at the same time. Here is an example implementation of recursive locks, which uses regular locks internally.

void recursive_acquire(struct rlock *rl) {
  if (rl->owner == cur_thread) {
    rl->count++;
  } else {
    acquire(&rl->lock);
    rl->count = 0;
    rl->owner = cur_thread;
  }
}
void recursive_release(struct rlock *rl) {
  rl->count--;
  if (rl->count == 0) {
    release(&rl->lock);
    rl->owner = -1;
  }
}

Recursive locks encourage the programmer to allow a critical section to begin in an inconsistent state. Consider a function foo() which acquires a lock l, and then calls another function bar(). The call to the function bar() may be synchronous (i.e., the programmer has a call chain in her program that eventually leads to bar from foo), or asynchronous (e.g., if bar() is called within an interrupt handler, and the interrupt is received within foo()). In either case, bar() may be assuming that the state is consistent when it begins its critical section. However, because the function was called in the middle of the critical section of foo(), bar may unexpectedly see inconsistent state.

foo() {
  acquire();
  ....
  bar();   //at this point, state is inconsistent
  ....
  release();
}

bar() {
  acquire();
  ....      // assumes that if acquire succeeds, the state here is consistent.
  ....
  release();
}

Try locks

bool try_acquire(struct trylock *tl) {
  Reg = 1;
  xchg(Reg, &tl->locked);
  if (Reg == 1) {
    return false;  //FAILURE
  } else {
    return true;   //SUCCESS
  }
}
void try_release(struct trylock *tl) {
  fence;
  tl->locked = 0;
}