In what order do piped commands run?

Question

I've never really thought about how the shell actually executes piped commands. I've always been told that the "stdout of one program gets piped into the stdin of another," as a way of thinking about pipes. So naturally, I thought that in the case of say, A | B, A would run first, then B gets the stdout of A, and uses the stdout of A as its input.

But I've noticed that when people search for a particular process in ps, they'd include grep -v "grep" at the end of the command to make sure that grep doesn't appear in the final output. This means that in the command ps aux | grep "bash" | grep -v "grep", which means that ps knew that grep was running and therefore is in the output of ps. But if ps finishes running before its output gets piped to grep, how did it know that grep was running?

flamingtoast@FTOAST-UBUNTU: ~$ ps | grep ".*"
PID TTY          TIME CMD
3773 pts/0    00:00:00 bash
3784 pts/0    00:00:00 ps
3785 pts/0    00:00:00 grep

Answer 1

The order the commands are run actually doesn't matter and isn't guaranteed. Leaving aside the arcane details of pipe(), fork(), dup() and execve(), the shell first creates the pipe, the conduit for the data that will flow between the processes, and then creates the processes with the ends of the pipe connected to them. The first process that is run may block waiting for input from the second process, or block waiting for the second process to start reading data from the pipe. These waits can be arbitrarily long and don't matter. Whichever order the processes are run, the data eventually gets transferred and everything works.

Answer 2

Piped commands run concurrently. When you run ps | grep …, it's the luck of the draw (or a matter of details of the workings of the shell combined with scheduler fine-tuning deep in the bowels of the kernel) as to whether ps or grep starts first, and in any case they continue to execute concurrently.

This is very commonly used to allow the second program to process data as it comes out from the first program, before the first program has completed its operation. For example

grep pattern very-large-file | tr a-z A-Z

begins to display the matching lines in uppercase even before grep has finished traversing the large file.

grep pattern very-large-file | head -n 1

displays the first matching line, and may stop processing well before grep has finished reading its input file.

If you read somewhere that piped programs run in sequence, flee this document. Piped programs run concurrently and always have.