10

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.

3
  • 1
    Your last test isn’t the same as mine, because your sleep delays cat as well as echo. I’m only delaying echo. Jan 6 at 13:05
  • Ah I see that point, but yeah, if your test would not be fixing things, hell would break loose, that's for sure. Jan 6 at 13:07
  • Another problem (which isn't apparent in this simple example) is that the writes are not atomic. a\nb\n and b\na\n are the two results you expect to see, but ab\n\n and ba\n\n may also possible, if one writer interrupts the other mid-write. You need to synchronize writes to the same pipe (which in shell means using something like flock).
    – chepner
    Jan 7 at 14:07

2 Answers 2

46

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.

13
  • Hi! I think your answer writing and my clarifying edit had (ironically) concurrent behaviour; I specified: 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). However, I can not confirm that delays increase the likelihood of things being in order. In fact, I took seconds to type "echo b> fifo" in that new terminal that I opened for just that purpose, and it reliably comes out with the b first. Let me write a test case... Jan 6 at 12:34
  • great, the moment I paste the same code into a text file and run it as script, it works reliably... Jan 6 at 12:54
  • so the point is that I wonder about the randomness of the unblocking of openat, I guess Jan 6 at 13:08
  • 1
    The randomness of unblocking is the randomness of scheduling in the end... Jan 6 at 13:12
  • 1
    right, of course it doesn't help to just have cat & first, we'd need to wait for it to actually open the fifo... exec 9<fifo first and then cat <&9 at the end? Or just doing it from a C program where you can just open() the fifo... Not that it's too easy to see if the echos end up blocking on the open anyway, since the delay's going to be short.
    – ilkkachu
    Jan 6 at 13:22
32

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
2
  • 1
    Hm, yes, This is an excellent! explanation. Wish I could do more than upvoteright now. The explanations being very illustrative, and the core info leads this whole thing: Your problem is that you misunderstand when the “in” happens. The “in” event is writing, not opening. Jan 6 at 13:59
  • 2
    Excellent answer, and I love this clear explanation: "Fifos are actually not quite pipes. They're more like potential pipes." Jan 7 at 10:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.