The POSIX specification does not mandate parallelism explicitly for commands in a pipeline. However, in practice the semantics of a pipeline necessitate concurrency at the very least.

Suppose we have \texttt {cmd}_1 | \texttt {cmd}_2 where \texttt {cmd}_1 produces an infinite amount of output (e.g., cat /dev/urandom) and \texttt {cmd}_2 consumes a finite amount of input (e.g., hxd-xxd -l100). What is the result of running this pipeline with the default POSIX shell options?

$ dash -c "cat /dev/urandom | hxd.xxd -l100"
00000000: 5033 7981 ae44 d475 074c 5361 0a9e 3828  P3y..D.u.LSa..8(
00000010: f88c 1f9e 3b0e bcde 528a f78c b1e4 7195  ....;...R.....q.
00000020: 16f2 8325 c90b 9310 539c af04 8289 c3a0  ...%....S.......
00000030: 57c5 680a 2c81 a999 71b6 708e 95df e720  W.h.,...q.p....
00000040: 004c 407a 8365 9448 65c6 b435 bed2 4084  .L@z.e.He..5..@.
00000050: 62ea 96ab 2b23 0385 f9d2 fc30 d090 1719  b...+#.....0....
00000060: 68d1 c514                                h...
cat: write error: Broken pipe

There are three factors that influence the pipeline's execution behaviour (i.e. what is done about the commands that are run and the exit status we return).

1. pipefail: With pipefail set to false (the default), the exit status of the pipeline is entirely decided upon by the exit status of the rightmost command (above \texttt {cmd}_2). With pipefail, the pipe will exit with 0 if all commands exit with 0; otherwise the non-zero exit status of the rightmost command is taken.

2. !: If the pipeline begins with ! then this inverts the exit code in the way you might expect.

3. All commands must terminate.

Whilst in theory \texttt {cmd}_1 does not terminate, the termination of \texttt {cmd}_2 closes the reading end of the pipe resulting in the Broken pipe system error.

Let's replace \texttt {cmd}_1 with the following compound command that also produces, left to its own devices, infinite output on stdout.

while echo "some bytes"; do
  :
done | hxd.xxd -l100

In this example, we no longer have the luxury of being able to fork and exec. The compound command (the while loop) forces our hand -- we must rely on the internal execution logic of the shell to keep it going. How then do we prevent \texttt {cmd}_1 from blocking our shell from spawning \texttt {cmd}_2?

For most shells, this is where they might fork themselves and allow the while loop to execute in the child. The parent continuing on. Alternatively, the work could continue on in a separate thread (in OCaml parlance, domain). Fibers (green threads, coroutines etc.) are only possible if there are a sufficient number of co-operative yields (which can be hard to track: any control flow or shell built-in would need to ensure they periodically yield to the other commands in the pipeline).

With that being said, it would seem we have workarounds to ensure the parallel aspects of pipelines are possible to build without forking the shell state itself.

Command reentrancy deals with the fact that commands in a pipeline run in subshells. In practice, this means any \texttt {cmd}_i should not impact the execution environment of any other \texttt {cmd}_j. Commands may certainly interfere with one another: a rogue rm might remove a file that some other command was about to read or was in the middle of reading!

\S 2.13 of the POSIX shell specification describes the execution environment. In Merry we lift this into the ctx type making it completely immutable; the only way to update the context is to destructively declare new fields, e.g., { ctx with cwd = "/home/bactrian" }. All shell built-ins work directly from the context as opposed to any state that might also be kept by the process itself (e.g., we do not call getcwd(3) to expand PWD, but instead read it from the context).

Most state is handled nicely by this functional implementation of the shell; except open (or not) file descriptors. The exec built-in is particularly thorny in this regard:

If exec is specified with no operands, any redirections associated with the exec command shall be made in the current shell execution environment.

So, exec 3>&1 says "in the current execution environment map file descriptor 3 to stdout" and exec > /dev/null says "in the current execution environment map stdout to /dev/null. This is often used to silence anything writing to stdout.

info () {
  echo "INFO: $1" >&3
}

exec 3>&1 > /dev/null
info "Starting up server..."
echo "Some noisy program spamming STDOUT"
info "All is quiet..."

If we are not running shell built-ins inside new child processes, then we must lift the file descriptor table into the context as well and disallow any two built-ins to run in parallel. Consider this example:

exec < ./hello.txt

while read line; do
  echo "Got $line" >&2
done | (exec < ./world.txt; cat)

If we allow exec to change the set of open file descriptors of the shell process directly, then individual commands in the pipeline are no longer re-entrant. The pipeline here is not being used to pipe bytes from one command to another, but instead to expose concurrency and the subshell behaviour.

The second exec < ./world.txt has no impact on the currently opened file on stdin, the while loop continues to read ./hello.txt. This is straightforward to implement with fork as you can dup2 any files you need. The bookkeeping and isolation is all provided by the POSIX process semantics. Without fork, the file descriptors would have to be saved and restored on every suspension and resumption to provide an illusion of isolation.

We could relax our rule to "disallow any two built-ins to run in parallel" by taking a lock on the file descriptor table, but considering the lock is held from the point of resumption until the next suspension it might not achieve very much in practice.

Some of the intricacies of scheduling are also covered in Michael Greenberg's An executable and formal semantics of the POSIX shell.

To motivate the question, consider the following two pipelines:

(1) while true; do echo 5; done | true

(2) while true; do echo 5; done | { read x; echo $((x+42)); }

Both pipelines spawn two processes, both of which use shell builtins exclusively: neither of these pipelines needs to make an execve system call (though some systems may implement true or echo as executables, Smoosh and most shells build them in).

Scheduling is an opaque part of the POSIX specification. Indeed, as we have argued here, there is no semantics for scheduling. Here is a similar pipeline run through a script that straces for clone and fork calls on various shells:

% ./test/check_fork.sh "while echo 5; do : ; done | true"
bash  3
dash  3
yash  1 
zsh   1
ksh   1
ash   3

It might make an interesting use case for effects in OCaml -- whilst we can certainly piggyback on Eio's existing suspension mechanisms, this is slightly different in that we need to ensure some preconditions are true before resuming certain computations. Fiber-local state is insufficient as programs implicitly depend on global state of the process (in particular the FD table). In this sense, we need some form of suspension-resumption hooks.