課題内容-level1-
シェルの実装例は、yaccで書いた簡単なシェルのインタプリタである。
構文は、パイプ、リダイレクト、()、;、&を含んでいる。
これをコンパイルして、実行してみよう。
Makefileがあるので、それを読んで、どのようなファイルが yaccにより自動生成されるか調べる。
closeを行っている部分を全てコメントアウトして、何が起きるかを観察せよ。 （#define close(a)などとするのも簡単）また、何故、そのようになるかを説明せよ。
このシェルは、waitを実装していない。waitを実装して、 （構文の変更が必要である）テスト用のスクリプトを作り動作を示すこと。
Makefileがあるので、それを読んで、どのようなファイルが yaccにより自動生成されるか調べる。
closeを行っている部分を全てコメントアウトして、何が起きるかを観察せよ。 （#define close(a)などとするのも簡単）また、何故、そのようになるかを説明せよ。
このシェルは、waitを実装していない。waitを実装して、 （構文の変更が必要である）テスト用のスクリプトを作り動作を示すこと。
Makefileについて
実際にmakeを行うとshell.c、my-shellという２つのファイルが生成される。
Makefileでは、shell.yからshell.cを生成する指定になっているが、
この部分にyaccが使われる。
yaccが生成したファイル「shell.c」は「shell.y」と比べると、 （diffの実行結果参照）構文規則を記述した部分が消え、 代わりにyygrowstack()やyyparse()が追加されている。 yygrowstack()とyyparse()は構文規則をC言語化した関数で、 生成された「shell.c」は、完全にC言語が解釈できるファイルとなる。
以下に、shell.yとshell.cの違いをしらべる為に使用した diffコマンドの出力を載せる。
「diff shell.c shell.y」の実行結果
yaccが生成したファイル「shell.c」は「shell.y」と比べると、 （diffの実行結果参照）構文規則を記述した部分が消え、 代わりにyygrowstack()やyyparse()が追加されている。 yygrowstack()とyyparse()は構文規則をC言語化した関数で、 生成された「shell.c」は、完全にC言語が解釈できるファイルとなる。
以下に、shell.yとshell.cの違いをしらべる為に使用した diffコマンドの出力を載せる。
「diff shell.c shell.y」の実行結果
closeを消してみる
ソース内には、全てで10個のclose()が使われている。
「#define close(a)」として、全てのclose()が機能しないようにし、
実行してみた。
すると、特定条件下でパイプを利用したときに、 処理が終了せずプロンプトが戻ってこない事がわかった。
戻ってこなくなるのは、grep、less、catなどをパイプの受け取り側に した場合である。
上記の例では、lsはパイプを通じてデータをcatに送り、catが 標準出力にその内容を出力したところで処理が止まっている。 つまり処理が停止している原因として、catが終了できないか、cat終了後に 親プロセスがプロンプトに戻れない（どこかで処理がつっかえてる）か というのが考えられる。
さらにこの現象は、ソース中の以下の場所をコメントアウトしただけでも再現する。 このclose()は、パイプを使用したときに親プロセスがパイプに書き込むための ファイルディスクリプタを閉じている部分になる。
ここで、パイプの書き込み側ディスクリプタに関するmanの記述を見てみる。
（原文）
If all file descriptors referring to the write end of a pipe have been closed, then an attempt to read(2) from the pipe will see end-of-file (read(2) will return 0).
（日本語訳 - JM Projectより）
パイプの書き込み側を参照しているファイル・ディスクリプタが すべてクローズされた後で、そのパイプから read(2) を行おうとした場合、 end-of-file (ファイル末尾) が見える (read(2) は 0 を返す)。
とある。逆に言えば書き込み側を参照しているディスクリプタを全てクローズ されていなければ読み出し側を参照しているディスクリプタからはEOFを 見つける事ができないという事である。
先ほどの例では、親プロセスが所持しているパイプへの書き込み用ディスクリプタが 、使用されないにもかかわらず閉じられていなかった。このディクスリプタが 残り続けているおかげで、パイプの受け取り側につながっているコマンドは、 パイプからEOFを見つける事ができなくなる。
もし、そのコマンドがEOFを見つける事で終了するようなものであるなら、 EOFが見つからないのでその間ずっとパイプをread()し続ける事になる。
catやlessは入力の受け取りにread()を使っていると思われるので、 先の例ではEOFを見つけられずに終了する事ができない。
これが、「ls | cat」等のコマンドを実行したときにプロンプトに戻れなくなる 原因である。
実際にコメントアウトする事による挙動の変化が確認できたのは 先のclose()一つだけである。各close()をコメントアウトする事に関して ソースを読んだ段階で予想される問題を、各close()の役割とともに 以下のリンク先に示す。加えて、元のソースには無かったが、 いくつか追加するべきだと思われる場所にclose()を追加したので、 それも示す。
-->各close()の説明へ
すると、特定条件下でパイプを利用したときに、 処理が終了せずプロンプトが戻ってこない事がわかった。
戻ってこなくなるのは、grep、less、catなどをパイプの受け取り側に した場合である。
[nw0439] j04039% ./my-shell % ls | cat makefile my-shell shell.c shell.diff shell.y shell.y~ C-c C-c <---break signal(emacs) [nw0439] j04039% ls | cat
上記の例では、lsはパイプを通じてデータをcatに送り、catが 標準出力にその内容を出力したところで処理が止まっている。 つまり処理が停止している原因として、catが終了できないか、cat終了後に 親プロセスがプロンプトに戻れない（どこかで処理がつっかえてる）か というのが考えられる。
さらにこの現象は、ソース中の以下の場所をコメントアウトしただけでも再現する。 このclose()は、パイプを使用したときに親プロセスがパイプに書き込むための ファイルディスクリプタを閉じている部分になる。
パイプのバグの原因と思われるclose()
142 case '|':
143 /* パイプの場合。
144 * パイプを用意し、fork()で子プロセスを作る。*/
145 pipe(pfd);
146 if((pid = fork()) != 0){
147 save_in = dup(0);
148 dup2(pfd[0],0);
149 close(pfd[1]); <--ここ
150 command(d->right);ここで、パイプの書き込み側ディスクリプタに関するmanの記述を見てみる。
（原文）
If all file descriptors referring to the write end of a pipe have been closed, then an attempt to read(2) from the pipe will see end-of-file (read(2) will return 0).
（日本語訳 - JM Projectより）
パイプの書き込み側を参照しているファイル・ディスクリプタが すべてクローズされた後で、そのパイプから read(2) を行おうとした場合、 end-of-file (ファイル末尾) が見える (read(2) は 0 を返す)。
とある。逆に言えば書き込み側を参照しているディスクリプタを全てクローズ されていなければ読み出し側を参照しているディスクリプタからはEOFを 見つける事ができないという事である。
先ほどの例では、親プロセスが所持しているパイプへの書き込み用ディスクリプタが 、使用されないにもかかわらず閉じられていなかった。このディクスリプタが 残り続けているおかげで、パイプの受け取り側につながっているコマンドは、 パイプからEOFを見つける事ができなくなる。
もし、そのコマンドがEOFを見つける事で終了するようなものであるなら、 EOFが見つからないのでその間ずっとパイプをread()し続ける事になる。
catやlessは入力の受け取りにread()を使っていると思われるので、 先の例ではEOFを見つけられずに終了する事ができない。
これが、「ls | cat」等のコマンドを実行したときにプロンプトに戻れなくなる 原因である。
実際にコメントアウトする事による挙動の変化が確認できたのは 先のclose()一つだけである。各close()をコメントアウトする事に関して ソースを読んだ段階で予想される問題を、各close()の役割とともに 以下のリンク先に示す。加えて、元のソースには無かったが、 いくつか追加するべきだと思われる場所にclose()を追加したので、 それも示す。
-->各close()の説明へ
waitの実装
waitは、シェルがバックグラウンドで走らせている全てのジョブの終了を
待つコマンドである。
元プログラムは、「&」を利用してコマンドをつないでも親プロセスが子プロセスの 終了を待つため（waitpid）、子プロセスが終了するまでプロンプトが戻ってこない。 また、子プロセスの出力が標準出力から変更されていないので出力がそのまま出る。 見た目にもバックグラウンド処理になっていない。
なので、まず「&」を利用したときにバックグラウンド処理を行うように 修正する。
「&」を使って挟んだ二つのコマンドは、左側がバックグラウンド処理の対象になる。 また、プロンプトの再表示はバックグラウンド処理の終了を待たないので、 フォアグラウンドで行われるプロセスがプロンプトの再表示までを担当することになる。
この二つの処理をそれぞれ親プロセスと子プロセスで受け持つ。
子プロセスは親プロセスの状態を引き継いでいるのでどちらのプロセスが どちらを担当しても実行に問題は無いが、waitの実装まで考えると 親プロセスからプロンプトが戻ってくる方が都合が良い。 （waitpidのオプションで簡単に指定できるため） 元のプログラムでは親プロセスが左のコマンド、子プロセスが右のコマンドに なっているので、これを逆にする。
子プロセスがバックグラウンド処理を担当する事になったが、 このままでは子プロセスの処理結果も標準出力に出てしまっており、 バックグラウンド処理というには都合が悪い。
なので、子プロセス処理の入出力をNULLデバイスに接続する。 エラー出力はバックグラウンドでも標準出力に出るのが普通なので残しておく。 これでフォアグラウンドでの処理はバックグラウンドに影響せず、 バックグラウンド処理の結果は標準出力には出なくなった。
ここで子プロセスを回収する為にwaitpidをそのまま使うと、 親プロセスが待機してしまう。それでは本末転倒なので親プロセスは 基本的に子をwaitしない。ただし、親プロセスより先に終了した子プロセスは 親プロセスがプロンプトを表示する前に回収するチャンスがある。 なので、waitpidに無待機オプション（WNOHANG）をつけて実行し、 その段階で回収できるものだけは回収するようにする。
waitされなかった子プロセスはこの段階ではゾンビ化してしまう。 親プロセスはプロンプトへ戻っているので、特定の子プロセスの為に waitを実行する事ができない。（できなくはないが、あるかどうか わからない小ゾンビのために毎回waitを行うのはもったいない）。 なので、バックグラウンド処理とセットで実行される事が多い 「wait」コマンドに、ゾンビ回収の機能を追加する事にする。
「&」によるコマンドのバックグラウンドでの実行は実装できたので、 「wait」コマンドの実装に入る。要件は
「シェルがバックグラウンドで走らせている全プロセスの終了を待つコマンドを、 シェル自身が行う処理として実装する」
であるが、バックグラウンド処理の実装時に子プロセスがゾンビ化したまま残る 現象が発生したので、「ゾンビ化した全子プロセスを回収する」事も 含めるとする。
「wait」というコマンドをシェルが認識しなければ行けないので、 トークンの切り出し時に切り出した文字列が「wait」かどうかを判断する。 「wait」だと判断されたらトークンを「w」として切り出す。
新しいトークンができたので、それに合わせて構文規則も修正する。
「wait」は普通のコマンドと同じように引数をとれるようにする。
（ただし今回は引数は意味をなさない）
追加する構文自体はトークン「f」とそれにつく引数を「expr」にまとめるものと 同じものを使い、ノードのtypeを「w」とする。
これで、後にcommand()内で「wait」と入力された場合を識別できる
ようになる。
command()内では、処理するノードのタイプを見て処理をわけている。 これが「wait」の場合は「w」となっているはずなので、対応するswich～caseを 追加してその中に処理を書き込む。
ここでは全てのバックグラウンドプロセス（またはそのゾンビプロセス）を 回収するのが目的なので、whileの無限ループとif～breakを使用している。 実際にプロセスを待つwaitpidは第一引数に-1（全てのプロセスが対象）を指定し、 返り値が-1（子プロセスが存在しない）になるまで繰り返す。
waitpidは既にゾンビ化したプロセスでもそれが子プロセスであれば対象とするので、 これで全ての子プロセスが終了するまで待機できる事になる。
元プログラムは、「&」を利用してコマンドをつないでも親プロセスが子プロセスの 終了を待つため（waitpid）、子プロセスが終了するまでプロンプトが戻ってこない。 また、子プロセスの出力が標準出力から変更されていないので出力がそのまま出る。 見た目にもバックグラウンド処理になっていない。
なので、まず「&」を利用したときにバックグラウンド処理を行うように 修正する。
「&」バックグラウンド処理の実装
バックグラウンド処理本体
176 case '&':
177 /* 親プロセスはコマンドの右側（フォアグランドプロセス）を実行して
178 * プロンプトに戻る。子プロセスはコマンドの左...
179 * を出力と入力をNULLデバイスにして実行する。
180 * 親が子を看取ってないので、子プロセス自体はゾンビ化する。 */
181 if((pid = fork()) != 0){
182 fprintf(stderr,"start pid %d\n",pid);
183 command(d->right);
184 waitpid(pid,NULL,WNOHANG);//既にゾンビになってるならとりあえず回収
185 return;
186 }else{
187 if(SHELL_DEBUG) fprintf(stderr,"forked pid %d\n",getpid());
188 /* 入出力をNULLデバイスに（エラー出力は残す） */
189 save_in = dup(0);
190 save_out = dup(1);
191 int nulldev = open("/dev/null",O_RDWR);
192 dup2(nulldev,0);
193 dup2(nulldev,1);
194 command(d->left);
195 /* 入出力を元に戻し、ディスクリプタを閉じる */
196 dup2(save_in,0);
197 dup2(save_out,1);
198 close(save_in);
199 close(save_out);
200 close(nulldev);
201 exit(0);
202 }「&」を使って挟んだ二つのコマンドは、左側がバックグラウンド処理の対象になる。 また、プロンプトの再表示はバックグラウンド処理の終了を待たないので、 フォアグラウンドで行われるプロセスがプロンプトの再表示までを担当することになる。
この二つの処理をそれぞれ親プロセスと子プロセスで受け持つ。
子プロセスは親プロセスの状態を引き継いでいるのでどちらのプロセスが どちらを担当しても実行に問題は無いが、waitの実装まで考えると 親プロセスからプロンプトが戻ってくる方が都合が良い。 （waitpidのオプションで簡単に指定できるため） 元のプログラムでは親プロセスが左のコマンド、子プロセスが右のコマンドに なっているので、これを逆にする。
子プロセスがバックグラウンド処理を担当する事になったが、 このままでは子プロセスの処理結果も標準出力に出てしまっており、 バックグラウンド処理というには都合が悪い。
なので、子プロセス処理の入出力をNULLデバイスに接続する。 エラー出力はバックグラウンドでも標準出力に出るのが普通なので残しておく。 これでフォアグラウンドでの処理はバックグラウンドに影響せず、 バックグラウンド処理の結果は標準出力には出なくなった。
ここで子プロセスを回収する為にwaitpidをそのまま使うと、 親プロセスが待機してしまう。それでは本末転倒なので親プロセスは 基本的に子をwaitしない。ただし、親プロセスより先に終了した子プロセスは 親プロセスがプロンプトを表示する前に回収するチャンスがある。 なので、waitpidに無待機オプション（WNOHANG）をつけて実行し、 その段階で回収できるものだけは回収するようにする。
waitされなかった子プロセスはこの段階ではゾンビ化してしまう。 親プロセスはプロンプトへ戻っているので、特定の子プロセスの為に waitを実行する事ができない。（できなくはないが、あるかどうか わからない小ゾンビのために毎回waitを行うのはもったいない）。 なので、バックグラウンド処理とセットで実行される事が多い 「wait」コマンドに、ゾンビ回収の機能を追加する事にする。
「wait」コマンドの実装
「&」によるコマンドのバックグラウンドでの実行は実装できたので、 「wait」コマンドの実装に入る。要件は
「シェルがバックグラウンドで走らせている全プロセスの終了を待つコマンドを、 シェル自身が行う処理として実装する」
であるが、バックグラウンド処理の実装時に子プロセスがゾンビ化したまま残る 現象が発生したので、「ゾンビ化した全子プロセスを回収する」事も 含めるとする。
「wait」というコマンドをシェルが認識しなければ行けないので、 トークンの切り出し時に切り出した文字列が「wait」かどうかを判断する。 「wait」だと判断されたらトークンを「w」として切り出す。
「wait」トークンの切り出し
403 value[i]='\0';
404 if(!(strcmp(value,"wait"))){
405 last_token = 'w';
406 }else{
407 last_token = 'f';
408 }
409 return last_token;追加する構文自体はトークン「f」とそれにつく引数を「expr」にまとめるものと 同じものを使い、ノードのtypeを「w」とする。
構文規則修正
72 | expr '>' '>' file { $$ = make_file($1, $4->value,2);}
73 | cmd {$$ = new_node('w',make_args($1,NULL...
74 | cmd {arg_count=0;}
75 args \{$$ = new_node('w',make_args($1,$3,arg_...
～中略～
83 file : 'f' { $$ = new_node('f',value,NULL,NULL);}
84 cmd : 'w' { $$ = new_node('w',value,NULL,NULL);}
85 args : arg { $$ = $1 ; }command()内では、処理するノードのタイプを見て処理をわけている。 これが「wait」の場合は「w」となっているはずなので、対応するswich～caseを 追加してその中に処理を書き込む。
「wait」コマンドの実体
166 case 'w':
167 if(SHELL_DEBUG) fprintf(stderr,"exec wait\n");
168 while(1){
169 if((pid = waitpid(-1,errstat,0)) != -1){
170 printf("done %d\n",pid);
171 }else{
172 break;
173 }
174 }
175 return;
176 case '&':ここでは全てのバックグラウンドプロセス（またはそのゾンビプロセス）を 回収するのが目的なので、whileの無限ループとif～breakを使用している。 実際にプロセスを待つwaitpidは第一引数に-1（全てのプロセスが対象）を指定し、 返り値が-1（子プロセスが存在しない）になるまで繰り返す。
waitpidは既にゾンビ化したプロセスでもそれが子プロセスであれば対象とするので、 これで全ての子プロセスが終了するまで待機できる事になる。
動作確認
バックグラウンド動作の確認
[%j04039] echo background & echo foreground start pid 472 foreground [%j04039]
どちらのコマンドも単体だと出力を返してくるはずだが、 フォアグラウンドで実行されているプロセスのみが 標準出力へ出力を返している。
親が先に終了、子プロセスがゾンビ化、waitで回収
[%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.01 ./my-shell [%j04039] sleep 10 & sleep 5 start pid 459 <-------------------------バックグラウンド処理開始 [%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.01 ./my-shell 459 p2 S+ 0:00.00 ./my-shell <--プロセスはまだ生きている 461 p2 S+ 0:00.01 sleep 10 [%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.01 ./my-shell 459 p2 Z+ 0:00.00 (my-shell) <--プロセスがゾンビ化 [%j04039] wait done 459 <-------------------------waitを実行して回収 [%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.02 ./my-shell <--親プロセスのみ [%j04039]
sleepコマンドに与える引数をずらす事で親のプロセスのsleep処理が 先に終了するようにし、子プロセスの状態を見てみる。 子プロセスに与えたsleepコマンドが終了するまでは子プロセスが そのまま存在しており、sleepコマンドの終了とともに子プロセスが ゾンビ化しているのがわかる。 その後のwaitでゾンビプロセスの回収を行っている。
子が先に終了、子プロセス回収済み
[%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.02 ./my-shell [%j04039] sleep 5 & sleep 10 start pid 468 [%j04039] ps PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.02 ./my-shell <--親プロセスのみ [%j04039]
sleepコマンドに与える引数をずらす事で子のプロセスのsleep処理が 先に終了するようにしてみる。 親プロセスは先に子プロセスが終了していた場合はプロンプトを表示する前に waitpidを実行するので、子プロセスもそれがゾンビ化したものも残っていない。
複数の子プロセスの回収
[%j04039] sleep 10 & start pid 542 [%j04039] sleep 20 & start pid 544 [%j04039] sleep 1 & start pid 546 [%j04039] ps ; wait PID TT STAT TIME COMMAND 453 p2 Ss 0:00.07 -bin/tcsh -i 457 p2 S+ 0:00.09 ./my-shell 542 p2 S+ 0:00.00 ./my-shell <--子プロセス（実行中） 543 p2 S+ 0:00.01 sleep 10 544 p2 S+ 0:00.00 ./my-shell <--子プロセス（実行中） 545 p2 S+ 0:00.01 sleep 20 546 p2 Z+ 0:00.00 (my-shell) <--子プロセス（ゾンビ） done 546 <------------------------------ゾンビ回収 done 542 <------------------------------子プロセス回収 done 544 <------------------------------子プロセス回収 [%j04039]
複数のプロセスをバックグラウンドで実行し、それぞれの終了するタイミングを ずらして、waitで回収してみた。 waitを実行する直前の段階で２つの子プロセスが残っており、 一つがゾンビ化している。
waitが実行されると、先にゾンビ化しているプロセスを回収し、 残り２つの生きている子プロセスが終了する順に回収しているのがわかる。