Linux named pipes: not as FIFO as thought

Question

In short:

mkfifo fifo; (echo a > fifo) &; (echo b > fifo) &; cat fifo

What I expected:

a
b

since the first echo … > fifo should be the first to have opened the file, so I expect that process to be the first to write to it (with its open unblocking first).

What I get:

b
a

To my surprise, this behaviour also happened when opening two separate terminals to do the writing in definitely independent processes.

Am I misunderstanding something about the first-in, first-out semantics of a named pipe?

Stephen suggested adding a delay:

#!/usr/bin/zsh
delay=$1
N=$(( $2 - 1 ))
out=$(for n in {00..$N}; do
  mkfifo /tmp/fifo$n
  (echo $n > /tmp/fifo$n) &
  sleep $delay
  (echo $(( $n + 1000 )) > /tmp/fifo$n )&
  # intentionally using `cat` here to not step into any smartness
  cat /tmp/fifo$n | sort -C || echo +1
  rm /tmp/fifo$n
done)
echo "$(( $res )) inverted out of $(( $N + 1 ))"

Now, this works 100% correct (delay = 0.1, N = 100).

Still, running mkfifo fifo; (echo a > fifo) &; sleep 0.1 ; (echo b > fifo) &; cat fifo manually almost always yields the inverted order.

In fact, even copying and pasting the for loop itself fails about half of the time. I'm very confused about what's happening here.

Answer 1

This has nothing to do with FIFO semantics of pipes, and doesn’t prove anything about them either way. It has to do with the fact that FIFOs block on opening until they are opened for both writing and reading; so nothing happens until cat opens fifo for reading.

since the first echo should be first.

Starting processes in the background means that you don’t know when they will actually be scheduled, so there’s no guarantee that the first background process will do its work before the second one. The same applies to unblocking blocked processes.

You can improve the odds, while still using background processes, by artificially delaying the second one:

rm fifo; mkfifo fifo; echo a > fifo & (sleep 0.1; echo b > fifo) & cat fifo

The longer the delay, the better the odds: echo a > fifo blocks waiting to finish opening fifo, cat starts and opens fifo which unblocks echo a, and then echo b runs.

However the major factor here is when cat opens the FIFO: until then, the shells block trying to set up the redirections. The output order seen ultimately depends on the order in which the writing processes are unblocked.

You’ll get different results if you run cat first:

rm fifo; mkfifo fifo; cat fifo & echo a > fifo & echo b > fifo

That way, opening fifo for writing will tend not to block (still, without guarantees), so you’ll see a first with a higher frequency than in the first setup. You’ll also see cat finishing before echo b runs, i.e. only a being output.

Answer 2

Pipes are first-in first-out. Your problem is that you misunderstand when the “in” happens. The “in” event is writing, not opening.

Removing useless punctuation, your code is:

echo a > fifo & echo b > fifo &

This runs the commands echo a > fifo and echo b > fifo in parallel. Whatever gets in first will get out first, but it's a roughly equal race as to which one gets in first.

If you want a to be read before b, you have to arrange to write it before b. This means you have to wait until echo a > fifo is done before you start echo b > fifo.

{ echo a > fifo; echo b > fifo; } & cat fifo

If you want to dig further, you need to distinguish between the elementary operations that happen under the hood. echo a > fifo combines three operations:

1. Open fifo for writing.
2. Write two characters (a and a newline) to the file.
3. Close the file.

You can arrange for these operations to happen at different times:

(
    exec >fifo     # 1. open
    sleep 1
    echo a         # 2. write
    sleep 1
)                  # 3. close

Likewise, cat foo combines an open, a read and a close operation. You can separate them:

(
    exec <fifo     # 1. open
    sleep 1
    read line      # 2. read
    echo $line
    sleep 1
)                  # 3. close

(The read shell builtin might actually make multiple read system calls, but that's not important right now.)

Fifos are actually not quite pipes. They're more like potential pipes. The fifo is a directory entry, and a pipe object is created when a process opens the fifo for reading. If a process opens the fifo for writing while no pipe exists, the open call blocks until a pipe is created. Furthermore, if a process opens the fifo for reading, this operation also blocks until a process opens the fifo for writing (unless the reader opens the pipe in non-blocking mode, which is not convenient from the shell). As a consequence, the first open-for-reading and the first open-for-writing on a named pipe will return at the same time.

Here's a shell script that puts this knowledge in action.

#!/bin/sh
tick () { sleep 0.1; echo tick; echo 0.1; }
mkfifo fifo
{
    exec <fifo; echo >&2 opened for reading;
    echo a; echo >&2 wrote a
} & writer=$!
tick
{
    exec >fifo; echo >&2 opened for writing;
    exec cat >&2;
} & reader=$!
wait $writer
kill $reader
rm fifo

Note how both openings happen at the same time (as near as we can observe). And the write can only happen after that.

Note: there is actually a race condition in the script above — but it's not related to the pipes. The echo >&2 commands are racing against cat >&2 to write to the terminal, and so you might see a from cat before opening for writing and wrote a. If you want to have a more precise view of the timing, you can trace the system calls. For example, under Linux:

mkfifo fifo
strace -f -P fifo sh -c '…'

Now if you put two writers, both writers will block at the opening step until the reader arrives. It doesn't matter who starts the open call first: pipes are first-in-first-out for data, not for open attempts. Whoever writes first is what matters. Here's a script to experiment with this.

#!/bin/sh
mkfifo fifo
{
    exec >fifo; echo >&2 opened for writing a
    sleep $1
    echo a; echo >&2 wrote a
} & writer_a=$!
{
    exec >fifo; echo >&2 opened for writing b
    sleep $2
    echo b; echo >&2 wrote b
} & writer_b=$!
sleep 0.2
cat fifo & reader=$!
wait $writer_a
wait $writer_b
kill $reader
rm fifo

Call the script with two arguments: the wait time for reader a and the wait time for writer b. The reader comes online after 0.2 seconds. If both wait times are less than 0.2 seconds, both writers will try to write as soon as the writers come online, and it's a race. On the other hand, if the wait times are more than 0.2, whoever comes first gets output first.

$ ./c 0.1 0.1
# Order of "opened for writing": random
# Order of "a"/"b": random
# Order of "wrote": random, might not match a/b due to echo racing against each other
$ ./c 0.3 0.4
# Order of "opened for writing": random
# Order of "wrote": a then b
# Order of "a"/"b": a then b