Process 3: Pipe sizes and interrupts

Overview

In this lecture, we discuss the primary system calls shells use to arrange inter-process communication.

Full lecture notes — Textbook readings

pipe illustration

Pipe privacy

• The pipe API naturally isolates pipes, preventing unexpected messages
• Contrast file system files
  • Can be read or written by name; any process can modify a file by name
• Pipes are unnamed: a process can only access pipe ends listed in its file descriptor table
  • Generally requires that a parent process create the pipe, then pass to child processes through cloning the environment
  • (Although file descriptors can be sent in messages too)

Pipe throughput

• Why are pipes high-throughput?
  • The in-kernel buffer supports batching
  • Bytes written to a pipe are buffered in the kernel until read
• How many bytes?
  • pipesizer

childpipe and dangling ends

Pipe end-of-file

• A read from a pipe returns end-of-file when all file descriptors for the write end are closed
• A write to a pipe terminates the writer when all file descriptors for the read end are closed (more later)
• Pipe hygiene: Clean up pipe ends when no longer needed

Multi-stage pipelines

Pipe philosophy

• The pipe abstraction, and especially its instantiation in shells, is a innovation in modular programming

• Pipes are a key enabler of the “Unix philosophy” of minimalist, modular software

• The idea of a pipe predates Unix!

  

  Source

  “Expect the output of every program to become the input to another, as yet unknown, program. Don't clutter output with extraneous information. Avoid stringently columnar or binary input formats. Don't insist on interactive input.” … “This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.”

  Source

Literate programming

• Literate programming: a program is developed alongside a series of small essays that describe the program’s operation
• Modern “notebook” programming, like iPython or Observable, derive from literate programming in that they integrate programs with documentation
• Designed for monoliths, not components: the program is the documentation
  • A reusable component has a separate interface

The literate programming challenge (1986)

“Given a text file and an integer k, print the k most common words in the file (and the number of their occurrences) in decreasing frequency.”

Jon Bentley; source

Donald Knuth’s solution

Source

Doug McIlroy’s critique

tr -cs A-Za-z '\n' |
tr A-Z a-z |
sort |
uniq -c |
sort -rn |
head -n $1

“The … shell script was written on the spot and worked on the first try. … Knuth has shown us here how to program intelligibly, but not wisely. I buy the discipline. I do not buy the result. He has fashioned a sort of industrial-strength Faberge egg—intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start.”

Source

Process hierarchy: manyfork and zombie processes

Pipes and relay races

• Let’s define a coordination problem involving two processes
• Run echo and grep in parallel; grep should read what echo wrote
• The natural solution is a pipe, but are other solutions possible?

Relay race attempt 1

$ /bin/echo Handoff | grep H

https://www.thestar.com/sports/olympics/2016/08/18/why-the-us-womens-4x100-relay-team-ran-by-themselves-on-the-track.html

Relay race attempt 2

$ /bin/echo Handoff > handoff.txt & grep H handoff.txt

https://www.dailymail.co.uk/sport/olympics/article-2185586/London-Olympics-2012-Great-Britain-looking-overcome-baton-woes-relays.html

https://www.stabroeknews.com/2016/08/19/sports/u-s-grasp-second-chance-4x100-relay/

Explanation

• In /bin/echo Handoff | grep H, the two programs run in parallel
  • They attempt to synchronize using a pipe
  • But reading from an empty pipe blocks the caller!
  • grep always reads what echo wrote
• In /bin/echo Handoff > handoff.txt & grep H handoff.txt, the two programs run in parallel
  • They attempt to synchronize using a file, handoff.txt
  • But handoff.txt can be read or written at any time
  • Maybe grep reads before echo writes!

Race condition

• A race condition is a bug that can manifest depending on timing
  • (More generally, it’s any unexpected system behavior dependent on scheduling, but the term generally refers to bugs.)

Reasoning about race conditions

• Which actions can occur in parallel?
• Which actions act as barriers for others, enforcing orders among actions?

Relay race barriers and parallel actions

• /bin/echo Hello | grep H
• Pipe end-of-file acts as a barrier
  • grep will not exit before pipe end-of-file
  • Pipe end-of-file will not occur before /bin/echo prints
  • So grep will always see /bin/echo
• Pipe semantics naturally impose the barrier here
• But are all coordination problems suitable for pipes?

Racer

• Parent process starts a child
• Child does work for work_time, then exits
• Child should finish by timeout
• If child finishes before timeout, parent prints quick
• If child does not finish before timeout, parent prints SLOW
• Questions
  • Possible race conditions?

racer-poll

• Reliable, but uses 100% CPU to wait
  • Not a valuable use of CPU

Racer arguments

• -w TIME: child work time is TIME (default 0.5 sec)
• -t TIME: parent timeout is TIME (default 0.75 sec)
• -V: verbose output

Polling and blocking

• Blocking: Process waits for communication
• Polling: Process checks repeatedly for communication
• Advantage of polling: Fewer race conditions
• Advantage of blocking: Lower CPU usage

Signals

• A signal is the process control analogue for an operating system interrupt
• Represent events that might occur at unpredictable times and/or need to interrupt long-running computations
  • Control-C ⟶ SIGINT
  • kill -9 ⟶ SIGKILL
  • Null pointer reference ⟶ SIGSEGV
  • A child process exited ⟶ SIGCHLD

Signal system calls

• sigaction establishes a signal handler

void handle_signal(int signal_number) {
    // do something to handle the signal
}

...
struct sigaction sa;
sa.sa_handler = handle_signal; // or SIG_IGN or SIG_DFL
sigemptyset(&sa.sa_mask);
sa.sa_flags = 0;
sigaction(SIGINT, &sa, nullptr);

• kill(pid_t pid, int sig) sends a signal
  • Some signals are generated automatically

When can a signal be delivered?

• In between any two instructions in the program
• Also interrupts certain system calls
  • System call may return early (e.g., a short read)
  • System call may return having done no work: errno == EINTR
• man 7 signal for more
  • “Interruption of system calls…” for list of system calls that can return EINTR
  • Also documented on system call manual pages

racer-block

• Unreliable!
• If child exits immediately, signal is delivered before sleep, and therefore does not interrupt sleep

racer-blockvar

• Still unreliable! (though less unreliable)
• Signal might delivered between any two instructions!

Race conditions!

• Can you use synchronous IPC to solve this race condition?

racer-selfpipe

• Process opens pipe to itself
• Signal handlers, for either SIGALRM (timeout) or SIGCHLD (child exit), write to pipe
• read will either succeed right away or be interrupted by a signal
  • Reliable timeout!