[ruby-list:6845] Re: Mutex/ConditionVariable/Queue

In message <[e-mail]>
[e-mail] (Shugo Maeda) writes:

> |  ですね. ちょっと例としては違ったか.... もっとも「その条件変数の追加
> |  とメソッドのオーバライドが必要」というのが問題だ, というのが 
> |  inheritance anomaly の問題意識なのですが.
> 
> ?
> 条件変数を追加するのは継承のせいではなくて違う条件で待つためですよね?

  つまり, 「継承によって増えた同期条件に関する同期コードを実装するため
  に, 継承もとのメソッドを再定義する必要がある」わけです.

  # SizedQueue を Queue を継承して作った場合, push も pop も再定義しな
  # ければならない....書き方が悪かったですね.

  メソッドに条件変数の扱いが埋め込まれているため, 新しい同期条件をいれ
  ると少なくともメソッドの同期条件のコードを書き直さなければならない.
  今の言語だとそれはメソッドを再定義することに相当する, と.

  で, 「ACT++ 風の behavior abstraction」で何がうれしいかと言うと,

    class Queue
      # オブジェクトは behavior に含まれるメソッドのみを受理し,
      # 他は遅延する.
      def next_behavior
        if @que.empty?
          behavior = [:push]
        else
          behavior = [:push, :pop]
        end
      end
    
      def push
          :
        # become はオブジェクトの behavior を変更する.
        become next_behavior
      end
    
      def pop
          :
        becom next_behavior
      end
    end
    
    class SizedQueue<Queue
      def next_behavior
        if @que.empty?
          behavior = [:push]
        elsif @que.full?
          behavior = [:pop]
        else
          behavior = [:push, :pop]
        end
      end
    end

  という感じで条件が増えても同期コード（next_behavior）だけ書き直せば
  済むという所にあるわけです.

  # これだと同期するコード以外は書けなくて, もとの Queue のような 
  # non-blocking 動作を実現できませんが.

> |> Mutexをモジュールに書き直そうと思うので、そっちではネスト
> |> できるようにしようと思います。
> |
> |  reentrant mutex? スレッドが分岐する場合にはどうしましょうか. 複数の
> |  コールを並行して行なう場合.
> 
> すみません、意味がわかりませんでした。

  こちらこそすみません. 全然関係ない話で混乱させてしまったようで.
  Reentrant mutex っていうのは見たまま「再入可能な mutex」というだけな
  んですよ. 基本的に同一スレッドによる再入を可能にする.

  「スレッドが分岐する」とかいう話はまあたいした意味は無くて,

    # グラフトラバーサルの一部. グラフ上の値の和を求める.
    class Node
      def query
        @mutex.synchronize {
          if @visited
            0
          else
            @visited = true
            # par_collect は並列に collect をするぐらいのつもり.
            res = @neighbors.par_collect {|n| n.query}
            # reduce は.... res の値の和を取っているつもり
            @value + res.reduce(:+)
          end
        }
      end
    end

  なんていうコードがあった時（いや, par_collect とか reduce なんて 
  Ruby にはありませんが (^^;）, par_collect で作られたスレッドも再入で
  きないとグラフに閉路があった時困る, という話なんです.

  # 「グラフトラバーサルぐらいだったら mutex でじゅうぶんわかりやすく
  # 書けるね」という話もあるんで, 研究をまとめるのが大変, と.

  メソッドコールをオブジェクトをまたがる論理的なスレッドの移動と考える
  と, par_collect のところで論理的なスレッドが分岐していることになる, 
  と.

> lockではmutex.owner==Thread.currentな時はカウンタをインクリメント
> して、unlockではカウンタが0になるまでロックを解放しない、というこ
> とをしたいだけなのですが。

  で, スレッドが分岐しないのならこれで何の問題もない, と.

  # うーむ, 無関係な話で手間をとらせてしまった....

======================================================================
  柳川 @ 情報システム学研究科 . 電気通信大学
  [e-mail]                          February 28, 1998
He knows most who speaks least.