L8

Locks and modularity

Recall that achieving good modularity is the mecca of software design. Ideally, a caller should not worry about how callee performs locking. Unfortunately, it's hard to use locks in a modular way due to

Multi-module invariants
Deadlock

Multi-module invariants refer to scenarios where a logically atomic application operation that spans multiple modules. A classic example is the bank transfer operation, where transferring money from account A to account B should has before-after-atomicity with respect to other operations on account A and account B.

A similar example of multi-module invariant in the OS context is to move a file across directories. See the pseudocode below:

move(olddir, oldname, newdir, newname){
  inumber = dir_lookup(olddir, oldname) //lookup the i-node number of the file to be moved
  dir_del(olddir, oldname) //remove the file name to inumber mapping in the old dir
  dir_add(newdir, newname, inumber) //add the file name to inumber mapping in the new dir
}

In your typical modular implementation, the directory functions dir_* need to hold locks to ensure reads/writes to a single directory has before-after-atomicity.

The above move() code is simple, but does not guarantee that the move operation has before-after-atomicity with respect to othe read/write operations on the directories. For example, there's a period of time when the file is visible in neither directory.

The code below fixes it, but requires that the directory locks not be hidden inside the dir_* operations.

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()

The second problem is deadlock. What if one process called move("A", ..., "B", ...) while another called move("B", "A",...)

Deadlocks

The wait-for graph:

The nodes in a waitfor graph are locks and threads.
When a thread acquires a lock, add a directed edge from the lock node to the thread node.
When a thread must wait for a lock, add another directed edge from the thread node to the lock node.
If the wait-for graph contains a cycle, a deadlock has occured.

Draw wait-for graph for operations move("A", ..., "B") and move ("B",...,"A")

Ways to avoid deadlock, lock ordering

Every lock/mutex has a different order and acquire locks in increasing order

move(olddir, oldname, newdir, newname){
  if (strcmp(olddir.name, newdir.name) < 0) {
    firstlock = olddir.lock
    secondlock = newdir.lock
  }else if (strcmp(olddir.name, newdir.name) > 0) {
    firstlock = newdir.lock
    secondlock = olddir.lock
  }else{
    return;
  }
  acquire(firstlock)
  acquire(secondlock)
  inumber = dir_lookup(olddir, oldname)
  dir_del(olddir, oldname)
  dir_add(newdir, newname, inumber)
  release(secondlock)
  release(firstlock)
}

Tools for catching race conditions

Eraser's idea:

accesses to shared variables are protected by locks
Every access is protected by at least one lock
Access unprotected by any lock --> an error

Challenge: what lock protects which variable?

have to infer programmer's intentions.
Eraser's intuition: One of the locks are held at time of access

The lockset algorithm

C(v): a set of candidate locks for protect v
Initialize C(v) to the set of all locks
On access to v by thread t, refine C(v)
- C(v) = C(v) \intersect locks_held(t)
- If C(v) = {}, report error

Why does it work?

What are the practical problems w/ the algorithm?

Initialization (when shared data is accessed by only one thread)
read-shared data (shared data is read-only)
read/write locks (multiple readers can proceed simultaneously, writers are exclusive)
benign races (programmers rely on h/w-level atomic operations such as atomic read of variables)

The lockset algorithm is very influential (e.g. Helgrind)

Lec 8: Synchronization III

Locks and modularity

Deadlocks

Tools for catching race conditions