CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 7 of 8 · 4 min read

Hidden deadlocks

Deadlocks with one lock: fork and signal handlers

Two more deadlocks need only one mutex. In both, the missing second party is hidden.

Fork with a held lock. When a program with several threads calls fork, the child gets a copy of the memory, but only one thread: the one that called fork. If another thread of the parent held a mutex at that moment, the child inherits a mutex that is marked as locked, and its owner does not exist in the child. Nobody can ever unlock it. In the test, a helper thread held a mutex for 2 s, and the main thread forked at 0.2 s. The parent's helper released the lock after 2 s, but in the child it was never released. After 3 s the child was still waiting. The same thing happens with the locks inside malloc and printf, which is why a child of a multithreaded program should call exec at once, or use only simple calls before it does. The pthread_atfork function lets a library take its locks before fork and release them in both processes.

A signal handler that takes a lock. A signal can interrupt a thread at any instruction. If the thread holds a mutex and the handler asks for the same mutex, the handler waits for the very thread it interrupted. A test took the lock in main, set an alarm for 1 s, and called sleep. The handler printed that it wanted the lock, and then the program never printed anything again, until the timeout killed it. The cure is to do only a few safe things in a handler: set a flag, or call functions that POSIX lists as async-signal-safe, and leave the real work to the main thread. Taking a mutex is not on that list.

In plain words: Both cases show a general point. A tool that draws wait-for graphs of threads cannot find them, because the party that would release the lock is not in the picture. They are found by knowing the rule.

Async-signal-safe function

An async-signal-safe function is a function that may be called from a signal handler without risk, because it does not use any lock or shared state that the interrupted code could be holding; POSIX gives a list of them.

Example: write is async-signal-safe, while printf and pthread_mutex_lock are not.

Interview angle

"A server hangs with no processor use. What do you check?" Look at the threads: if they all sleep in lock waits, find the owners and look for a cycle (page 1). If one thread sleeps inside a call that was made in a signal handler or after a fork, suspect the hidden cases of this page. Mention that high processor use with no progress points to a livelock.

Check yourself: 1. Why does a child created by fork in a multithreaded program inherit a lock that nobody can release? 2. Why did the signal-handler test hang with only one lock? 3. Name one function that is safe to call in a handler and one that is not.

Words you will meet

Word Meaning
Livelock Threads keep reacting to each other and use processor time, but make no progress
Starvation A ready thread is passed over again and again
Aging Raising a thread's priority as it waits
Priority inversion A high-priority thread delayed by a lower one that holds its lock
Priority inheritance The lock holder borrows the priority of the highest waiter
Communication deadlock Processes waiting for each other's messages or channel space
Async-signal-safe Callable from a signal handler without risk
pthread_atfork Registers functions to run around a fork

Quick notes

  • Starvation is the condition in which a thread that is ready to run, or waiting for a resource, is passed over again and again so that it makes no progress, while other threads continue to run.
  • A livelock is a condition in which threads keep changing state in response to each other, and so use processor time, but none of them makes progress toward finishing its work.
  • Aging is a method that raises the priority of a thread the longer it waits, so that every thread is eventually served and starvation is prevented.
  • Priority inversion is a situation in which a high-priority thread is delayed by a lower-priority thread that holds a lock it needs, and a thread of medium priority delays the.
  • A communication deadlock is a deadlock in which each process in a set waits for a message, or for room in a channel, that only another process in the set can provide.
  • An async-signal-safe function is a function that may be called from a signal handler without risk, because it does not use any lock or shared state that the interrupted code could be holding; POSIX gives a list of them.