ことのはの散策

recursive and reentrant：再帰的と再入可能
　

                                                                                      上智大学　伊藤 潔

                                                                                            2005年10月２４日

　プログラムの仕組みでおもしろいものとして，recursive（再帰的）と reentrant（再入可能）があります．プログラムの実行では，プログラムを実行している主体，タスクとかプロセスと呼ばれるものを考えて，これがプログラムを実行しているという図式で考えた方がわかりやすいです ．

　recursive（再帰的）では，タスクは１つと考えていいです．ある人がコンピュータでプログラムを実行しているときは，オペレーティングシステムは，その人に対応してタスクを想定します．このタスクが，階乗計算のサブプログラム(手続きといっても良い)を実行しています．階乗計算factorialのサブプログラムは，繰り返しでも書けますが，次のような形態でプログラムすることもできます．

　 factorial(n) = { if n=1 then 1 else n*factorial(n-1)}

　この形式をrecursive（再帰的）といいます．これは「あるプログラムの中に，そのプログラムと同じものを（パラメータを変えて）呼び出す」形式です．

　「5の階乗を計算したい」タスクは，factorial(5)というプログラムを実行します．この実行の中で，途中，5*factorial(4)，4*factorial(3)，3*factorial(2)，2*factorial(1)というように，パラメータの値を1つずつ減らして，factorialを呼び出します．factorial(1)は，n=1なので，１となり，それに，2を掛けて，3を掛けて，4を掛けて，5を掛けて，というようにして，5の階乗(5!)を計算します．

　この階乗の計算のプロセス（これは過程という意味）では，サブプログラムが呼び出される度に，そのパラメータと計算途中の値や式が保持され管理されます．これらは，これを実行していたタスクの属性として保持されます．

　一方，reentrant（再入可能）では，「タスクは複数存在し，これが同一のプログラムを実行する形態」です．

　座席予約でも図書貸し出しでも，複数の互いに関係のない人達が同時に予約したり貸し出し手続きをします．

(A)サーバに座席予約のプログラムが1つしかない状況を想定します．さらに，一度に一つの客の要求しか処理できず，しかも，1件ずつ終わるまで，次の客の要求の処理ができない，としましょう．この形態では，処理中の客がゆっくり考えながら入力していても，台帳ファイルのディスクをプログラムが読んでいても，とにかく，「次の人は待て」ということになります．一人の客に一つのタスクを割り当てていると考えると，1つのタスクのみ実行中で，他は全て待ち状態で，効率が悪いです．

(B)一人の客に一つのタスクを割り当てて，さらに座席予約のプログラム（同内容でコピーしたもの）を１つずつ割り当てて実行する形態もあります．この方式では，プログラム達は，並行性（参照）を持っていますから，オペレーティングシステムは，いわゆるマルチタスク方式で，プログラムを実行します．ある客がゆっくり考えながら入力しているときは，そのプログラムが待ちになって，他のプログラムが実行されます．実行は効率がよくなりますが，人数分だけ，プログラムにメモリが必要になります．主記憶が不足したら，プログラムを出したり入れたり，効率が悪いです．

(c)一人の客に一つのタスクを割り振り，プログラムを一つで実行する形態が，reentrant（再入可能）という形態です．プログラム実行の時の必要なパラメータ，この場合，予約したい座席に関する情報は，客に対応するタスクが元々持っていますが，プログラム実行中にプログラムの中で変化する変数の値もタスクに持たせます．同一プログラムはコピーしない形のマルチタスク方式で実行します．

　座席予約のようなオンラインシステムでは，上のタスクという概念と共に，トランザクションという概念で捉えます．この辺のことは，別稿で．