Part 6 of 8 · 2 min read
Pipe deadlock
In plain words: A deadlock needs no lock. Two processes can wait for each other through a pipe. A pipe holds a limited amount of data, and a writer blocks when the pipe is full. Suppose a parent sends a large block of data to a child and only then starts to read the answer. The child reads a chunk, writes the answer into a second pipe, and reads the next chunk. If the answer pipe fills before the parent starts reading, the child blocks on its write. Then it stops reading its own input, the input pipe fills, and the parent blocks on its write. Each waits for the other to read, which neither can do.
The exact point can be calculated. The test sent N bytes with the parent writing everything first. On this machine, the capacity of a pipe was 65,536 bytes (fcntl(fd, F_GETPIPE_SZ)). The data in flight at the moment of the stall are:
parent -> [pipe 1: 65,536] -> child buffer (4,096) -> [pipe 2: 65,536] -> parent
65,536 + 4,096 + 65,536 = 135,168 bytes can be held without anyone reading
A binary search found that N = 135,168 bytes completed, and N = 135,169 hung. With 1,000 and 100,000 bytes it worked, and 200,000 hung. A test with a small input passes, and the program fails in production with a large one. The failure depends on the data size, and that makes it hard to find.
The cures are the same as for locks, in other words: change the order (read while writing, using poll or a second thread), or stop waiting (non-blocking I/O). Another cure is a single side that does all the writing, or a file instead of a pipe.
Communication deadlock
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.
Example: a parent blocked writing into a full pipe to a child that is blocked writing into a full pipe back to the parent.
Common mistake
A program that runs on small test data may deadlock on large data. If two processes talk through pipes in both directions, one of them must read while the other writes. Test with data larger than the sum of the pipe capacities.
Check yourself: 1. What is the total amount of data that the two pipes and the child buffer can hold in the test? 2. Why did 100,000 bytes work but 200,000 hang? 3. Name two ways to avoid this deadlock.