POSIX準拠シェルスクリプトでマルチコアの能力を活用する並列処理の実装（最大並列数あり、GNU Parallel, xargsなし）

## はじめに

シェルスクリプトで並列処理を行う場合、一般的には GNU Parallel か xargs を使うのではないかと思います。しかし GNU Parallel はその名の通り GNU が提供しているツールですし xargs も並列数を指定する `-P` オプションは POSIX で規定されてないので動作する環境が限られます。また、これらは外部コマンドであるためシェル関数を呼び出すことが出来ないという制限もあります。これをシェルスクリプトのみで実装することで、環境依存すること無く並列処理を実現することが出来ます。

**補足 続編記事も書きました。**

- [POSIX準拠シェルスクリプトでfind -print0やxargs -0を使わずにスペースや改行が含まれたファイル名を処理する](https://qiita.com/ko1nksm/items/9088042a9d64381ca07b)
- [続・POSIX準拠シェルスクリプトでマルチコアの能力を活用する並列処理の実装（名前付きパイプ版）](https://qiita.com/ko1nksm/items/a37c7651b2c32db766f0)

## 実装

実は最大並列数の制限がなければジョブ（標準入力からの一行単位のデータ）の数だけバックグラウンドプロセスを起動すればいいのでかなり簡単に実装できます。ですが普通は嫌ですよね？ということで最大並列数を制限する処理を入れています。また通常の利用で必要になりそうな CTRL-C と TERM シグナルへの対応もしています。

```sh
#!/bin/sh

set -eu

[ "${ZSH_VERSION:-}" ] && setopt shwordsplit

MAX_PROC=4 # 最大並列数

# INT(CTRL-C)、TERM による終了処理
terminate() {
  trap '' TERM
  kill -TERM 0
  exit "$1"
}
trap "terminate 130" INT
trap "terminate 143" TERM
# trap : CONT

# 並列で実行される処理
func() {
  echo "sleep $1"
  sleep "$1"
  # kill -CONT $$
}

proc=0 pids=''
while :; do
  # 最大並列数までプロセスを起動する
  while [ "$proc" -lt "$MAX_PROC" ] && IFS= read -r line; do
    func "$line" &
    pids="$pids $!" proc=$((proc + 1))
  done
  [ "$proc" -eq 0 ] && break
  sleep 1 # wait $pids 2>/dev/null ||:

  # 終了してないプロセスを調べる
  living_pids='' proc=0
  for i in $pids; do
    kill -0 "$i" 2>/dev/null || continue
    living_pids="$living_pids $i" proc=$((proc + 1))
  done
  pids=$living_pids
done
```

実行方法

```console
$ seq 10 | sh test.sh
```

## コード解説

コードの上の方からわかりづらそうな部分のコードの解説をします。さほど行数もないのでどこのことかはすぐに分かると思います。

```sh
[ "${ZSH_VERSION:-}" ] && setopt shwordsplit
```

zsh ではデフォルトで単語分割を行わないようになってるので、これを他のシェル（POSIX）の挙動に変更しています。

```sh
terminate() {
  trap '' TERM
  kill -TERM 0
  exit "$1"
}
trap "terminate 130" INT
trap "terminate 143" TERM
```

INT (CTRL-C を押されたとき)シグナルまたは TERM シグナルが送られてきた時の終了処理で、子プロセス全てを停止させています。

本来であれば端末から CTRL-C を押した時はプロセスグループ全てのプロセスに対して INT シグナルが送信されるので子プロセスも終了します。しかしバックグラウンドとして起動したプロセスの場合は INT シグナル（および QUIT シグナル）が無視（`SIG_IGN`）に設定されるため子プロセスは終了しません。

https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_11

> If job control is disabled (see the description of set -m) when the shell executes an asynchronous list, the commands in the list shall inherit from the shell a signal action of ignored (SIG_IGN) for the SIGINT and SIGQUIT signals. 

そのためこのスクリプトが属するプロセスグループに対して TERM シグナルを送る（`kill -TERM 0`）ことで子プロセスを停止します。TERM シグナルは自分自身にも送られてくるので、それによって自分自身が停止しないように送信前に`TERM` シグナルのシグナルハンドラを無視（`trap '' TERM`）に変更してから処理を行なっています。

TERM シグナルの場合は一般的に親プロセスだけに送られてくる場合が多いと思われるので、その場合に子プロセスを停止させています。

子プロセスを停止した後は INT シグナル（シグナル番号 2）の場合は 130、TERM シグナル（シグナル番号 15）の場合は 143 という終了ステータスでプロセスを終了します。この終了ステータスはシグナル番号に、シグナルで終了したという意味の 128 を加えた値です。

```sh
func() {
  echo "sleep $1"
  sleep "$1"
  # kill -CONT $$
}
```

実際に行う処理で必要な処理に置き換えてください。出力結果をジョブの順番通りに表示したい場合は、この関数内で一時ファイルに出力してから適切なタイミングで出力するなどの処理を追加する必要があるでしょう。

```sh
  while [ "$proc" -lt "$MAX_PROC" ] && IFS= read -r line; do
    func "$line" &
    pids="$pids $!" proc=$((proc + 1))
  done
  [ "$proc" -eq 0 ] && break
```

ジョブ（＝標準入力から受け取ったデータ）を MAX_PROC （最大並列数）の数までバックグラウンドプロセスとして起動します。もしジョブが一つもない場合は終了します。

```sh
sleep 1 # wait $pids 2>/dev/null ||:
```

この実装は一秒ごとに生きてるプロセスを調べて最大並列数以下なら追加でプロセスを起動しています。そのための待ち時間です。（ダサいですか？次の章の「制限」を参照してください。）

```sh
  living_pids='' proc=0
  for i in $pids; do
    kill -0 "$i" 2>/dev/null || continue
    living_pids="$living_pids $i" proc=$((proc + 1))
  done
  pids=$living_pids
```

生きているプロセスを調べて情報（`pids`, `proc` 変数）を更新しています。`kill -0 "$i"` で指定したプロセスの生存確認ができます。なお `kill` コマンドはほとんどのシェルでビルトインコマンドなのでここの処理に実行コストはほとんどかかりません。

**おまけ** 分かりづらいって言われそうだから普通に書いたけどこんな風に書いてみたい。（`while` の中に長いコードを入れられます。）

```sh
while
  while [ "$proc" -lt "$MAX_PROC" ] && IFS= read -r line; do
    ...
  done
  [ "$proc" -gt 0 ]
do
  sleep 1 # wait $pids 2>/dev/null ||:
  living_pids='' proc=0
  for i in $pids; do
    ...
  done
  pids=$living_pids
done
```

## 制限

この実装は 1 秒間隔で生きてるプロセスをチェックしているので、1 つのジョブが終了し、次のジョブが起動するまで最大で 1 秒間の待ち時間があります。上記のコードの三箇所のコメントを外して（うち `sleep` の行は コメントの `wait` に置き換える）シグナルを使うことでこれを改善しジョブが終わったらすぐに次のジョブを起動するようにすることができます。

これを実現するために `wait` 中に `trap` しているシグナルを受け取ると `wait` が中断されるという仕様を利用します。（一部 `wait` が中断されない場合があります。下記の追記を参照してください。）

https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_11

> When the shell is waiting, by means of the wait utility, for asynchronous commands to complete, the reception of a signal for which a trap has been set shall cause the wait utility to return immediately with an exit status >128, immediately after which the trap associated with that signal shall be taken.

`wait` は引数で指定した複数の PID すべてが終了するのを待ちます。しかしジョブは一般的に一つずつ終了するため全てを待つわけには行きません。bash では `wait -n` でいずれかのプロセスが終了するまで待つことが出来るのでよりスマートに実装できるのですが、他のシェルでは使えませんし当然 POSIX にも規定されていません。そのため各プロセスの処理が終了した時に `wait` を中断させるためのシグナル（`kill -CONT $$`）を送信しています。

CONT シグナルを使用しているのは、近い意味を持っており無害そうだからで CONT シグナルでなければいけない理由はありません。子プロセスが終了したときは CHLD シグナルが自動的に送信されるはずなのでこれを使えば自分で `kill -CHLD  $$` を実行しなくて良いと思ったのですが一部のシェル（dash, yash）でしか動きませんでした。どうやら、bash, zsh, ksh, mksh, posh では送られてきたシグナルが CHLD の場合は `wait` が中断されないようです。

また厳密に言えば子プロセスの処理の完了を意味するシグナル（`KILL -CONT $$`）を通知してから `kill -0 "$i"` でプロセスの存在チェックをするまでの間に、子プロセスが終了していないと正しく動作しない可能性があります。これが発生する確率は低いと思いますし `wait $pids` の後に `sleep 0` でも入れればより発生しづらくなりますが不安は残ります。（なるべくシンプルなコードで解決したいのですが少し面倒そうです・・・。）

シグナル版は多少不安が残るので `sleep` 版の方が安定すると思います。並列処理を必要とするような処理なら 1 秒程度は誤差だと思いますし 0.1 秒（POSIX では秒単位ですが）にするのもありでしょうし大きな制限にはならないでしょう。

補足ですがシェルスクリプトでのシグナル受信は取りこぼしが発生します。短時間で多数のシグナルが送られてきた場合、全てを捕捉できるとは限りません。

#### 追記 2021-03-10

ksh と mksh では `wait` を中断するために `wait` に指定したプロセスの数だけシグナルを送信する必要があるようです。また mksh はそれだけではうまく反応せず、間に外部プロセス呼び出しが必要でした。つまり以下のようなコードにすれば動作しているような感じですが不安は残ります。

```sh
func() {
  echo "sleep $1"
  sleep "$1"
  # kill -CONT $$
  i=0
  while [ "$i" -lt "$MAX_PROC" ] && i=$((i+1)); do
    env true
    kill -CONT $$
  done
}
```

また zsh では以下のような問題があります。（細かいバージョンまでは調べていません。）

- 4.3.2 以前 シグナルを送信してもすべての `wait` している全てのプロセスが終了しない限り `wait` は終了しません。
- 4.3.6 上記の不具合は修正されていますが、`wait` に指定したプロセスの数だけシグナルを送信する必要があります。
- 4.3.17 上記の不具合は修正されています。（ [Release Notes](http://zsh.sourceforge.net/releases.html) より 4.3.15 で修正された？）
- 5.0.7 `wait` しているプロセスを `kill` すると `pid N is not a child of this shell` というエラーメッセージが出力されます。
- 5.3.1 上記すべての問題はないようです。

## 余談

この記事は書きかけで放置していた記事を急遽書き上げたものでいつもより検証不足です。（バグがないといいんですが・・・）きっかけは Gigazine に掲載された「[コアを多数搭載するCPUは「POSIX」によって能力を制限されているとの指摘](https://gigazine.net/news/20210227-posix-parallel-shells-xargs/)」に記事に対して、POSIX 準拠の範囲のシェルスクリプトだけで並列処理は実装できるよと、つい[ツイート](https://twitter.com/ko1nksm/status/1365807983154716674)してしまったからです。

オリジナルの記事「[Parallel shells with xargs: Utilize all your cpu cores on UNIX and Windows](https://www.linuxjournal.com/content/parallel-shells-xargs-utilize-all-your-cpu-cores-unix-and-windows)」（xargsによる並列シェル: UNIX と Windows で CPU コアを全て活用する）は GNU 版 xargs の紹介にすぎず、本当に言いたいことは「POSIX で規定しているコマンドは GNU 実装に比べて機能不足だ。しかし POSIX では最低限の機能しか規定してないから多くの UNIX はそれ以上の実装を放棄してる。UNIX に実装させるためにも POSIX コマンドの機能は改定すべきだ。」なのだと思います。POSIX "コマンド"の機能不足についてであれば私は異論は全くありません。しかし POSIX に違反した実装は禁止されていても、POSIX を超えた機能を実装してはいけないという決まりはないはずです。機能不足なのは主に UNIX（BSD、macOS含む） のコマンド実装の問題です。またオリジナルの記事のスレッドや自作スクリプトの細かい話は完全に蛇足でしょう。ベンチマークの結果はたまたまマルチプロセスの方がわずかに（2.5%程度）良かっただけの話で、マルチスレッドとマルチプロセスのどちらがいいかはトレードオフの問題ですし `gzip` と `pigz` という実装が違うコマンドを比較しておりこの程度の差ではマルチスレッド vs マルチプロセスの参考になるとは思えません。また POSIX 版の `xargs` が NULL 文字を扱えない問題は `od` コマンドを使って 8 進数（または 16 進数）文字列に変換して処理することで解決できます。（続編 「[POSIX準拠シェルスクリプトでfind -print0やxargs -0を使わずにスペースや改行が含まれたファイル名を処理する](https://qiita.com/ko1nksm/items/9088042a9d64381ca07b)」）


さらに Gigazine の記事では、POSIX.2（コマンドとユーティリティ）の話ではなく（私が蛇足と考える）POSIX スレッドの話がメインになってしまってるので、POSIX （つまりC言語等から呼び出す OS のシステムコール）全体の問題のように見えてしまいます。「POSIXスレッド」と「プロセス単位での並列処理」を比べてますが、そもそも「プロセス単位での並列処理」も POSIX の機能です。POSIX.2（コマンドとユーティリティ）は POSIX の一部でしかありません。**POSIX「コマンド」が貧弱なのは事実ですが POSIX 全体には当てはまりません。** オリジナルの記事も微妙ですが Gigazine の記事によって何が問題となってるのかさらに意味がわからなくなっています。

という話を発端に、POSIX 準拠シェルでもシェルスクリプトを書けば並列処理でマルチコアを活用できるよということでこの記事を書きました。実際に POSIX シェルとコマンドだけでどこまで出来るかやってきてわかった事ですが、不便ではあるけれど大抵のことは実現できてしまうので POSIX シェルとコマンドはよくこれほど最小と言える機能にまで絞り込んだものだと感心しています。端末からコマンドを叩いてさくっと何かをしたい場合は、POSIX コマンドだけを使うなら大変ですが、コードを書くならばこの記事のように POSIX 準拠のシェルスクリプトでもマルチコアを活用できますし（POSIX インターフェースをフルに使える）C 言語やその他のプログラム言語を使えばいいのです。

ただ一つ勘違いしてほしくないのは、私は POSIX シェルスクリプトでマルチコアを活用できるのは事実なのでそう言いましたが、常に POSIX シェルとコマンドだけを使うべきだとは言っていません。そもそも何のために POSIX コマンドだけでやろうとするのでしょうか？ POSIX コマンドだけを使えば多くの環境でそのまま動作する可能性が高いのは事実ですが、低機能な分開発コストが高くなるのも事実なので、トレードオフの問題として本当に必要な場合にだけやるべき事です。それにたとえ POSIX にないコマンドや言語を使ったとしても、その多くは UNIX にも移植されているでしょう？ つまりオープンソース等で多くの環境に移植されているコマンドや言語を使っていれば POSIX で規定されていなくても事実上どこでも動くわけです。例えば GNU 版の xargs は Homebrew で findutils をインストールすることで macOS でも gxargs として使用できます。逆に特定のベンダーが開発した商用コマンドを使ったりすると POSIX 準拠のシェルスクリプトであっても許可された環境や契約の元でしか動かないもの（つまりベンダーロックイン）となります。不特定の環境で動作させる必要があるツールなら依存するコマンドは少ない方が良いですが、自社開発システムなどではパッケージをインストールすれば事足りるはずです。

> UNIX系のOSに共通する機能の呼び出し方法などを定めたPOSIXは、「POSIXに準拠するならばどんな環境でも動作する」ことを保証する規格です。

現実を見ましょう。Java の Write Once, Test Anywhere と同じで POSIX に準拠したところで、POSIX 未定義の動作、POSIX による異なる実装の許容、仕様変更、意図的な POSIX 非準拠の実装、実装のバグ等があるのであらゆる場所でテストしなければ動くことは保証できません。重要なのはテストすることです。シェルスクリプトもちゃんとテストしていますか？

さて余談がメインとなりつつあるので、ここらで切り上げることにします。

**関連記事** [パイプを使って高速化したシェルスクリプトを並列実行すると逆に遅くなる謎現象について](https://qiita.com/ko1nksm/items/4b2103e9fa4aa9c4be07)