Think Stitch
PRINCIPIA  最近の更新


プロセスの動的生成 3 : 子プロセスのマルチインスタンス

並行合成 par を fork のように使って、複数の子プロセスを実行する一般的な場合を考えます。

親プロセス P はイベント c を受けるたびにプロセス Q のインスタンスを子プロセスとして生成します。プロセス Q は仕事が完了次第終了するものとします。子プロセスの仕事をイベント a で表します。

(define-process P
  (! c
     (par '()
       P
       Q)))

(define-process Q
  (! a SKIP))

プロセス P の計算木の一例を以下に示しました。この例では子プロセスが5回生成されていて、先に生成された4つはすでに終了しています。

見ての通り、困ったことに終了した子プロセスのためのノードは、最終的に親プロセスが終了するまで回収されません。これは実質リークがあるのと同じなので、長時間システムを運用するとリソースを使い果たす危険性があります。もし子プロセスが先に生成された方から終了する傾向があれば、逐次合成 seq を使って先にツリーを畳むことができます。しかし任意の順序で終了する場合には、生きている子プロセスよりも古いノードが残されてしまうことは避けられません。

それでもまだ対処できるケースがあります。もっとも最近生成された子プロセスが終了した時点で、そこから親に向かって連続する OMEGA ノードがある場合は、その時点で畳んでしまうことができるはずです。例えば上の場合でプロセス Q が終了したならば、次のインスタンスの枝を伸ばす前にすべてのノードを畳んでしまうことができます。どのようにしたらこれが可能になるか、考えて見ます。

プロセス木を畳む方法

着目すべき重要な点は、プロセス木を畳むためには親プロセスが終了しなければならないという点です。しかし親プロセスの終了はシステムの終了ですから、単純に終了させるわけにはいきません。そこで、親プロセスの代わりに、終了してもかまわない補助のプロセスを用意することを考えます。

単純な場合

まず簡単な場合を考えます。親プロセスを P、補助するプロセスを F とします。初期状態では P と F だけがあります。

プロセス P は子プロセス生成の要求が発生したら、プロセス F に生成を依頼します。

プロセス F はこれを受けて子プロセスを生成します。これを Q1 とします。プロセス F は並行合成 par を fork のように使い、一方の子プロセスを自分の制御の継続 F1 とします。

この状態で子プロセス Q1 が終了する場合、Q1 は親プロセス P に終了通知を出してから終了します。

親プロセス P は終了通知を受けたら、対応するプロセス F1 に終了命令を出します。

プロセス F は終了命令を受けたら終了します。するとプロセス木が畳まれて初期状態に戻ることができます。

より一般的な場合

次にもっと一般的な場合を考えます。子プロセスが3つ生成された状態にいるとします。ここで2番目に生成された子プロセス Q2 が終了します。

親プロセス P は子プロセス Q2 から終了通知を受け取りますが、対応するプロセス F2 を終了させることはできません。まだ Q3 が動いているからです。親プロセスはどの子プロセスが稼働中で、どの補助プロセスを終了させることができるのか、判断できなければなりません。

次にプロセス Q3 が終了するとします。するとプロセス木の葉の方から連続する OMEGA ノードができます。

このような場合、親プロセスは枝の先の方から順番に補助プロセス F に終了命令を出して、プロセス木を畳みます。

モデリング

イベント・チャネル定義

生成可能な子プロセスの最大数を N とします。以下のように2つのイベントと2つのチャネルを定義します。子プロセスは同時に実行される可能性があるので、終了通知は個別に用意する必要があります。ここではイベントを用意する代わりに子プロセスの ID を引数とするチャネル q を用意します。

(define N 5)
(define D (map list (interval 0 N)))

(define-event a)               ; 子プロセス起動イベント
(define-channel c (k) D)       ; P から F への起動依頼
(define-channel q (k) D)       ; Q から P への完了通知
(define-event e)               ; P から F への終了命令

子プロセス Q

子プロセス Q は極端に抽象化して、終了通知を出すだけとします。これでも、複数の子プロセスが同時に終了できる場合、どれが終了するかは非決定的になります。

(define-process (Q k)
  (! q (k) SKIP))

補助プロセス F

ここが第1の難関です。逐次合成と並行合成をフルに活用します。プロセス F は展開されたプロセス木上の、対応する各ノードを表していることを再度確認しておきます。簡単な方から見ていきます。もし終了命令 e を受けた場合は SKIP で終了します。これはノードを畳む場合です。

親プロセスから子プロセスの生成要求 c が来た場合、指定されたプロセス ID で子プロセス Q を起動します。もう1つのプロセスはプロセス F の継続で、自分自身を指定します。なぜなら次の子プロセス生成を担うプロセスは、同じプロセス F だからです。さらに加えて、並行合成が終了した後のプロセスを逐次合成 seq で連結しておきます。ここでもプロセス F 自身を指定します。並行合成が終了したということは、伸ばした枝が畳まれて自分自身に戻ってきたということだからです。トリックのような作りですが、あとでシミュレーションを見るともっとよくわかると思います。

(define-process F
  (alt
    (? c (k)
       (seq
         (par '()
           (Q k)
           F)
         F))
    (! e SKIP)))

親プロセス P

親プロセスは子プロセスの稼働状況を管理するために3つのプロセスパラメータを持ちます。

  • fs は未使用プロセス ID のリストです。いわゆるフリーリストです。順序に意味はありません。
  • ps は現在稼動している子プロセスのプロセス ID リストです。順序に意味はありませんので、集合ということです。
  • pst は現在ツリー状にノードが残っている子プロセスのプロセス ID リストです。順序は葉から根に向かう順序です。先頭から出し入れするので、スタックになります。

先に定義全体を示しておきます。選択 alt の節は3つあります。これを順に見ていきます。

(define-process (P pst ps fs)
  (alt
    (! a
       (if (null? fs)
           (P pst ps fs)
           (let ((k (car fs)))
             (! c (k)
                (P (cons k pst) (cons k ps) (cdr fs))))))
    (? q (k)
       (P pst (remv k ps) fs))
    (if (and (not (null? pst))
             (not (memv (car pst) ps)))
        (! e
           (P (cdr pst) ps (cons (car pst) fs)))
        STOP)))

最初の節は子プロセスの起動のための節です。子プロセスの起動イベント a を受けたら、未使用のプロセス ID があるかどうかを調べます。もし空きがない場合は何もしません。これはいまは問題にしません。未使用 ID がある場合はそれを k とします。補助プロセス F に起動依頼を出し、pst, ps それぞれに k を登録します。同時に未使用リスト fs から外しておきます。

    (! a
       (if (null? fs)
           (P pst ps fs)
           (let ((k (car fs)))
             (! c (k)
                (P (cons k pst) (cons k ps) (cdr fs))))))

第2の節は子プロセスからの終了通知処理です。プロセス ID k の子プロセスが終了したら、 ps から取り除いておきます。ここでは pst も fs も触らず、プロセス F との通信も行いません。

    (? q (k)
       (P pst (remv k ps) fs))

最後の節はプロセス F への終了命令処理です。もし pst が空ならば子プロセスは存在しません。そうでなければ少なくとも1つはノードがあり、(car pst) がもっとも最近生成したプロセスの ID です。しかしそれが生きているかどうかは pst からはわかりません。子プロセスからの終了通知は ps に反映させてあるので、(car pst) が ps に含まれていれば、もっとも最近生成した子プロセスがまだ動いています。したがってプロセス木を畳むことはできません。もし (car pst) が ps に含まれていなかったら、終了しています。そこで対応するプロセス F、つまり休眠していない、動いている唯一の F に終了命令 e を発行します。もし e が受け取られたら、pst の先頭の ID を取り除き、未使用リスト fs に戻しておきます。

この処理のポイントは、終了命令 e を提示しているときにも子プロセスの起動要求が発生したり、子プロセスが終了したりするということです。子プロセスの起動要求を先に受け取った場合には、プロセス木を畳む前に、つまり OMEGA のあるノードの先に新しい子プロセスのノードを伸ばすことになります。子プロセスの起動依頼者から見て、プロセス木を畳む処理は実質待ちなしと見なすことができるので、畳む方を優先することもできます。ここでは簡単な解を選びました。このコードはガードの例になっています。

    (if (and (not (null? pst))
             (not (memv (car pst) ps)))
        (! e
           (P (cdr pst) ps (cons (car pst) fs)))
        STOP)))

システムプロセス SYSTEM

親プロセス P と補助プロセス F を並行合成してシステムプロセス SYSTEM を作ります。

(define-process SYSTEM
  (par (list c q e)
    (P '() '() (interval 0 N))
    F))

シミュレーション

単純な場合

まず子プロセスを1つ生成して、すぐに終了する場合を見てみます。

起動依頼 a を受け、未使用 ID 0 を選びます。次にプロセス F にチャネル c で起動依頼を出します。

プロセス F は起動依頼を受けて子プロセス (Q 0) を生成します。この際、逐次合成 seq と並行合成 par の各ノードが作られます。親プロセス P はプロセス ID 0 を pst, ps それぞれに登録します。

子プロセス Q が終了通知を出します。親プロセス P はこれを受けて、プロセス ID 0 を ps から取り除きます。

子プロセス Q が終了します。ノードが OMEGA になりました。

この状態で、親プロセス P は (car pst) = 0 が ps に含まれていないことを発見し、プロセス F に終了命令 e を発行します。プロセス F はこれを受けて終了します。プロセス P は受理されたことを見てプロセス ID 0 を pst から取り除き、未使用 ID リストに戻します。

プロセス F が終了すると、終了した子プロセス Q と合わせて par が終了します。ここで par ノードが畳まれます。これによって seq が F に移行します。ここがプロセス F 定義の要部分です。

より一般的な場合

次に、より一般的な場合について見てみます。子プロセスを3回生成した後の状態を示します。子プロセスは3つとも動いている状態です。このことは ps に ID が3つ登録されていることからわかります。遷移リストを見ると、どの子プロセスも終了できることがわかります。

ここではまず子プロセス (Q 1) の終了通知 q.1 が選ばれた場合を見ていきます。親プロセス P はこれを受けて、プロセス ID 1 を ps から取り除きます。

子プロセス (Q 1) が終了します。この時点では (car pst)=2 が ps に含まれているので、親プロセスはこれ以上何もしません。

次に子プロセス (Q 2) の終了通知 q.2 が受け取られたとします。ID 2 が ps から取り除かれます。結果、(car pst)=2 は ps に含まれなくなったので、プロセス F への終了命令 e が提示されます。遷移リストにイベント e があるのがわかります。同時に、起動要求 a と子プロセス (Q 0) の終了通知 q.0 も受け取れることがわかります。

子プロセス (Q 2) が終了します。

プロセス F が終了命令 e を受け取ります。

プロセス F が終了します。

ここでノードが1段階畳まれます。ここで、(car pst)=1 もまた ps に含まれていないので、再びプロセス F に終了命令 e が提示されます。プロセス (Q 1) は先に終了していたからです。

プロセス F が終了命令 e を受け取ります。

プロセス F が終了します。

ノードがまた1段階畳まれて、生きている子プロセスだけになりました。

2013/08/03
© 2013,2014,2015 PRINCIPIA Limited