Lock order and deadlock

Hart 1 holds spinlock A and calls acquire(&B). At the same moment hart 2 holds B and calls acquire(&A). Nothing else holds A or B. What happens in this kernel?

Two processes deadlock on two sleep-locks (each holds one inode lock and waits for the other’s). Compared with a deadlock on two spinlocks, what does the rest of the machine see?

Which of these mistakes does xv6 turn into a panic at run time?

kexit and kwait each need wait_lock and some p->lock at the same time. Read the comment. Which nesting does this kernel use?

A leaf lock is one that no code acquires anything else while holding (so it can never be part of a cycle). Which of these are leaves in this kernel?

True or false: kexit acquires wait_lock (line 347) and then its own p->lock (line 355), but releases wait_lock first (line 360). Releasing in that order breaks the lock-ordering discipline and could deadlock.

bget finds the cached block on line 66. Why does it release bcache.lock (line 68) before waiting for the buffer’s sleep-lock (line 69)?

kexit calls wakeup(p->parent) on line 353 while holding wait_lock. How many different p->lock spinlocks does that single wakeup call acquire (one after another)?

allocproc returned np with np->lock held. Click the line that keeps kfork from holding a p->lock while it waits for wait_lock.

Between line 294 and line 300, kfork holds no lock on the new child at all. Why is that safe?

Put the steps of kexit (from line 347 on) in the order they happen.

Suppose someone moved acquire(&p->lock) (line 355) up to just before wakeup(p->parent) (line 353), so the exiting process holds its own lock during the wakeup. What happens?

sys_unlink holds the parent directory dp locked and may then lock the entry ip inside it. Click the line that stops it from ever locking a parent while holding its child.

In create, when the name already exists, line 281 unlocks the parent dp before line 282 locks the existing ip. Which input would hang the process if the two lines were swapped (lock ip while still holding dp)?

cat called exit(0) (a system call). kexit has just executed line 360, release(&wait_lock), and is about to call sched on line 363. What is the state of its hart?

rm x decrements x’s link count and iupdate writes the inode through the log. Put the waits and locks of this path in the order they are taken (outermost first). When the inode’s block is new to this transaction, log_write calls bpin, and at that moment all five are in effect at once.

Each place below avoids a deadlock in a different way. Match each one with its technique.

namex locks a directory, looks up the next name, and then (line 720) unlocks it before the next iteration locks the entry it found. Why not keep the directory locked while locking the next one?

True or false: if a process calls ilock on an inode whose lock it already holds, xv6 panics, just as acquire does for a spinlock.

In this kernel, which of these locks are ever acquired while the acquiring hart holds a p->lock?

Suppose bget's lines 68 and 69 were swapped, so it calls acquiresleep(&b->lock) while still holding bcache.lock, and the buffer is held by another process. Inside acquiresleep, the process reaches sleep and then sched. What is mycpu()->noff when sched checks it on line 487?

rm drops the last reference to an unlinked inode, so iput calls acquiresleep(&ip->lock) on line 362 while holding itable.lock. Inside acquiresleep, at line 32 the call to myproc runs its own push_off. What is noff at that moment (inside myproc, before its pop_off)?

Imagine filewrite called ilock before begin_op. The log already holds 15 blocks from this group (LOGBLOCKS is 30, MAXOPBLOCKS 10), and rm x on another hart is inside its own transaction (outstanding 1) and about to lock x. The writer locks x, then calls begin_op. What happens?

A modified kernel deletes kfork's lines 294 and 300, so it takes wait_lock while holding the half-built child’s np->lock. Under a fork/exit stress test it froze. The other hart in the cycle never names that child’s lock in its code. Which code took the child’s lock on the other side?

True or false: if you draw a graph of lock classes (an edge A → B whenever some path holds a lock of class A while acquiring one of class B), this kernel’s graph has no cycle.