5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 13

言語実装 Advent Calendar 2025

@miura1729(Hideki Miura)

競合解消のためのたった一つのアホなやりかた

5
Last updated at Posted at 2025-12-12

この記事は言語実装 Advent Calendar 2025　13日目の記事です。

プロローグ

　Rustという言語があります1。 Rustはスレッド間で共有しているデータは必ず

Arc::new(Mutex::new(0))

のようにMutexというスマートポインタを経由してアクセスしなければなりません。そうしないとコンパイルエラーになります。一方、実際にデータをアクセスするときは、

counter.lock().unwrap()

のようにlockメソッドでロックを取らないとこれまたコンパイルエラーになります。ありがちなロックを取らないでデータをアクセスして再現しないバグに苦しむみたいないことが防止できるのです。素晴らしい、賢い。でも、こう思わないでしょうか？

ロックが必要だと分かっているなら、とっととロックを入れんかい。
ちんたら人に指図してるんじゃねーよ。このすっとこどっこい

このもっともな意見を検証するため、実際に自動でロックを入れる処理系を作ってみました。Rubyで
はたしてRustは本当にすっとこどっこいなのか、検証する旅が始まります。

処理の概要

実際に処理系がどうなっているか簡単に説明します。詳細を説明すると本当に退屈なので概要だけ。

処理系は筆者がずっと作り続けているmruby-meta-circular(以下mmc)を拡張する形で実装しました。mmcは抽象解釈で型やエスケープ情報を得て、それを使ってRubyのプログラムを効率的なC言語に変換します。詳しくはこの辺を見てください。
https://qiita.com/miura1729/items/86018639e649089fa7dc

effect解析

ロックを自動的に入れるには次のような情報が必要です

　* オブジェクトがどのスレッドから読まれるのか
　* オブジェクトがどのスレッドから書かれるのか

いくら共有されていても何も使って無かったり、みんなが読んでいるだけの場合、ロックは要らないわけです。このようにオブジェクトがどう共有されているかだけではなく、どう使われているかを知る必要があります。その為にはメソッドなどがどういう副作用(effect)を及ぼすかを調べる必要があり、これがeffect解析といいます。Juliaなどeffect解析を行う処理系が最近は増えてきました。
mmcでは変数に格納されている型を決定するために型レベルで抽象実行するのですが、その際に実行したメソッドが副作用を持っていた場合はそれを記録することでeffectの情報を得ます。
effectは次のような種類が現在あってこの先増えると思います。例えば、I/O関係とかまだありませんし。

　 　
effectの種類
名前 説明
:iv_read インスタンス変数の読みこみ
:iv_write インスタンス変数の書き込み(通常モード)
:iv_write_lockfree インスタンス変数の書き込み(ロックフリーモード)
:iv_write_nolock インスタンス変数の書き込み(ロック無しモード)
:lambda Procオブジェクト(ブロック)の生成
:modify オブジェクトの破壊的変更
:arrayset 配列・ハッシュテーブルの要素の書き換え
:arrayset 配列のpopなど配列が空になる可能性のある副作用

どのスレッドからアクセスされているか得る

抽象解釈を行って型が決定できると、そのご褒美にメソッドの呼び出し関係の木が得られます。そんな物は抽象解釈がなくてもプログラムをパースすれば出来るだろ？って思われるかもしれませんがRubyにはポリモフィズムがあるので型が決定していないと不可能です。
呼び出し木さえあれば、Thread.newに渡したブロックを辿ればどのメソッドがどのスレッドから呼ばれているか分かります2。
あとはメソッドごとにそのメソッドのeffectからどのオブジェクトが共有しているのかを判定します。判定アルゴリズムはヒューリステックで複雑なのでここでは説明しません。興味のある人はここを見てください。
https://github.com/miura1729/mruby-meta-circular/blob/9cc525cbe1268412dc93a46cbb178c8490223a25/mrblib/typeinf.rb#L296-L392

型の内部表現

理由は分からないのですが、型システムがどうなっているか気になる人が多い様に感じます。mmcはRubyでしかも勝手に型付けするので型を気にしなくてもいいのですが、一応説明しておきます。
型にはいろいろな情報を持っていてそれによって効率的なコード生成やロックの自動挿入を実現しています。ロックの自動挿入で重要なのは次のようなものです。
　* どのスレッドからアクセスされているか　@thread
　* ロックされているか @lock

@threadのサイズが2以上で@lockがfalseの場合は、排他制御が必要になります。C言語レベルのオブジェクトの構造はMutexでWrapした形になり、型の表記も Mutex<Foo>みたいな表示になります3。排他制御を行うにはエスケープする必要があるからUNBOXINGなものは存在しません。

Mutex

複数のスレッドからアクセスされ、しかも一つ以上のスレッドから書きこまれる場合は排他制御が必要になります。排他制御はMutexによって行いMutexはRustのMutexスマートポインタと同様な構造で実装します。ただし、Rubyにはスマートポインタという概念はないのでオブジェクトでWrapする形になります。
mmcのベースにさせてもらっているmrubyには、DATAオブジェクトというCの構造体をWrapしてあたかもRubyのオブジェクトとして扱うデータ型があるのでこれを使います。このDATAオブジェクトで、Pthreadのmutexと排他制御するオブジェクト本体の構造体をWrapしています。また、オブジェクト本体をインスタンス変数にも格納します。こうすることでGCのマーキングも勝手にやってくれます。

型変換

mmcではオブジェクトはエスケープ解析をつかって可能な限りスタックに割り当てられるので、同じクラスでもBOX化されていたりされていなかったり、ヒープに入っていたりスタックに入っていたりと違う構造の物が入り乱れます。また、もともとRubyはto_iとかto_sとか型変換を多用する文化です。
そいうわけでmmcでは型変換を行うAPIがあって、型変換が必要な所はすべてこれを使っています。

gen_type_conversion(ccgen, dstt, srct, src, tup, node, ti, history, oreg, ireg = nil)

沢山引数がありますが、基本的にはsrctの型を返すコードsrcをdsttに変換するコードを返すというメソッドです。これでCのフォーマットのintをmrubyのフォーマットのFixnumに変換出来たりするのですが、dsttに:rvalue（mrubyの標準オブジェクト)、srctにMutexみたいな型(ここでは:rvalue_mutexと表現される)を入れると、Mutexオブジェクトが持つMutexをlockし、中身を取出すコードが返ってきます。つまり、コンパイラの中でもMutexとかを心配しなくても型の事だけを考えていれば排他制御のコードが出てくるのです。ちなみにlockするコードはこんな感じです.srcに”v2772"を渡すとこんな文字列が返ってきます。一応、式なので式の中で自由に使えます。

({
  struct mutex_wrapper *mutex = (struct mutex_wrapper *)DATA_PTR(v2772);
  {
pthread_mutex_t *mut = (&mutex->mp);
pthread_mutex_lock(mut);
}

  mrb_value tmp = mutex->obj;
  
  tmp;
})

心配性の方はどこでunlockをするんだろう？って思われたと思います。そこで効いてくるのが最後の引数iregです。これはもともとのMutexオブジェクトが入っていたレジスタオブジェクトかnilを渡します。mmcでは値が入るものはすべてレジスタとして統一的に扱っています。型だとかどの命令で作られたか(mmcは内部的にSSAを使っているので例外を除いて作成元は1つです)とか色々な情報を持っているのですが、その中にどの命令で参照されているのかという物もあります。この命令列の中で最後に実行される命令の直後にunlockのコードをいれます(フックを登録します)。nilなら今コンパイル中の命令の直後にunlockが入ります。

例1 角谷予想

一番理解しやすい未解決問題と紹介されがちな角谷予想(コラッツ予想)という未解決問題があります。問題は単純で
　　* 偶数なら2で割る
　　* 奇数なら3倍して1足す
　を繰り返すと最終的に1になるかという問題です。すべての数で1になるのかは分かっていないのですが、普通に出てくるような数だと成り立つことが分かっています。私が疑問に思ったのは、何回くらいステップを繰り返すんだろう？ってことです。計算するプログラムを書いてみました。
各数について1になるステップ数を計算して配列に入れて行きます。27の様に111ステップ必要な物もあるので結構バラツキがあります。
本体はこんな感じ

def kakutani(n, res)
 re = res[n]
 if re.nil? then
   nn = n
   if nn & 1 == 0 then
     nn = nn >> 1
   else
     nn = nn * 3 + 1
   end

   r = kakutani(nn, res) + 1
   res[n] = r
   return r
 else
   return re
 end
end

resは結果の配列で初期値はnilで結果がも止まるとその結果が入ります。すでに分かっている数に辿りついたらそれ以上はステップを辿らなくてもいいわけです。

このメソッドを必要な値まで順番に呼び出せば欲しい結果が得られますが、これを並列化してみましょう。
並列化と言ってもスレッドを作る以外の特別なことはありません。

まず結果がどこまで求まったか管理するカウンタが必要になります。ステップ数を求める過程で結果の配列がどんどん埋まりますので、単純にインクリメントするのではなく、結果の配列をスキャンする必要があります。これをクラスとして定義することにしました。

class Count
  def initialize
    @c = 2
  end

  def skip_cnt(res)
    while res[@c]
      @c += 1
    end
    n = @c
    @c += 1
    n
  end

  def c
    @c
  end
end

skip_cntメソッドでまだ結果の無い数までカウンタを進めます。cメソッドで現在の現在のカウンタの値を得ます。
これらを使ってマルチスレッドで角谷予想のステップ数を求めるメインルーチンがこれです

def main
  c = Count.new
  r = {}
  r[0] = 0
  r[1] = 0
  ths = []

  2.times do |tn|
    ths.push  MMC_EXT::Thread.new(c, r, tn) {|cnt, res, tn|
      n = cnt.c
      while n < 8000
        n = cnt.skip_cnt(res)
        kakutani(n, res)
      end
    }
  end

  ths.each do |th|
    th.join
  end
end

へんなモジュールの修飾が付いていますが、このプログラムの使い方レベルではRubyのThread#newと同じ仕様です。
カウンタのインスタンス変数@cと結果を格納する配列がスレッド間で共有されているので普通ならこのプログラムは動かないですが、どこが共有されているか解析してロックが入るのでちゃんと動くわけです。
ただし、さすがにマルチスレッドで動かすには粒度が細かすぎるので1スレッドで計算した方が速いです。

Lock Free

パフォーマンスが出なかったので、小細工に走りました。
お気づきの人もいるかもしれませんが、Countクラスで競合するのは@c += 1(二箇所ある)だけです。
こういうのはアトミック加算命令をつかえばlock freeで行えるので、lock freeの命令を出すモードを作りました。

class Count
  include MMC_EXT::LockPolicy::LockFree

  def initialize
    @c = 1
  end

  def skip_cnt(res)
    @c += 1
    pp "skip"
    while res[@c]
      pp @c
      @c += 1
    end
    pp @c
    @c
  end

  def c
    @c
  end
end

こんな感じで

include MMC_EXT::LockPolicy::LockFre

を入れると、可能ならばアトミック命令を使ってlock freeに変換します。アトミック命令でコンパイル出来るメソッドしか使っていないなど条件がシビアでほとんど使えないですが。冪等性を判定してCASを使うコードを出すことが可能かもしれませんが、いまはやっていません。

モジュールをincludeするインタフェースにしたのは、CLOS MOPの様に将来はユーザがロック戦略をカスタマイズするようにしたいからです。型推定やコールグラフのトラバース、コード生成などのタイミングでフックメソッドを呼び出して必要なコード生成のポリシーをカスタマイズする。LockPolicy::*はそのメソッド群の集合体。まあ、無理でしょうね...

結局、マルチスレッドの方が遅いのに変わりはありませんでした。

例2 サンタクロース問題

排他制御だけあってもマルチスレッドプログラミングは出来ません。スレッド間の同期が必要になります。排他制御だけでも排他制御された共有領域でひたすらスピンロックすれば可能ですが、とても効率の悪い物になります。そこでスレッドの同期を普通のRubyのプログラムとして違和感のない様な仕様を考えました。それは、スレッド間で配列を共有しスタックやキューのように使う仕様です。
これまで説明した方法で共有された配列のアクセスにはロックがかかり配列が壊れることはありません。さらに配列だけの特別な仕様として、空の配列をpopしようとすると配列に別のスレッドが何かデータを入れるまで待つようにしました(もちろん、スピンロックではないCPU時間を使わない方法で)。空配列からpopした人はあまりいないでしょうし、スレッドで共有されていなければ通常のnilが返ってくるpopです。
これによって丁度アクターモデルの様なプログラミングが出来ます。アクターモデルというにはQueueが見ていたりと汚いのでもう一段ライブラリが必要ですが。
普通はQueueみたいなデータ構造を用意するわけですが、普通の配列を使うメリットとしてpushとunshiftを使い分けることで、擬似的に優先度を表現できることです。次に説明するサンタクロース問題でこの特徴が生きます。
サンタクロース問題とはこんな感じの問題です

  • サンタクロースと9人の小人と2７匹のトナカイがいます
  • 小人は最初寝ていて起きるとサンタクロースの家に行きます
  • トナカイはその辺をうろついていて気が向くとサンタクロースの家に行きます
  • サンタクロースは普段寝ているのですが、小人が3人集まるかトナカイが9匹集まると起されます(良く寝る人たちだ)
  • 小人が3人集まるとプレゼントを作って、トナカイが9匹集まるとプレゼントを配りに行きます
  • 仕事が終わった小人やトナカイはどこかに行ってしまいます
  • 全員仕事が終わるとこの問題は終わりです
  • 小人とトナカイが同時に揃ったらトナカイの方を優先します

可愛い問題ですが、実際解くと結構ハードです。Beutiful Codeという本でHaskellの偉い人がネタにする程度には難しそうです
https://www.oreilly.co.jp/books/9784873113630/
解法はいろいろあるのですが、今回はメッセージパッシングっぽい方法をとります。

  • トナカイ・小人はそれぞれ独立したスレッドを用意します
  • サンタは次の3つのスレッドからなります
    　　+ トナカイを相手するスレッド
    　　+ 小人を相手するスレッド
    　　+ 全体をまとめるスレッド
    小人のスレッドはこんな感じになります
   hobbitmail = []
   hobbitlist = Array.new
   9.times do |i|
     hobbitlist.push MMC_EXT::Thread.new(hobbitmail, i) {|mail, id|
       sleep((rand*10).to_i)
       pp "hobbit wake up #{id}"
       reply = [id, []]
       mail.push reply
       reply[1].pop
       pp "Hobbit Work done #{id}"
     }
  end

hobbitmailという配列がサンタと小人のやり取りをしています。
puishメソッドで配列を入れると、サンタ側がpopで待っていてメッセージを受け取ります。
ここで特記すべきことは、メッセージに配列を渡すことができることです。こうやって配列を入れ子にして送ると、ここに結果を返すことができます。Futureオブジェクトという言葉を知っていれば、まさにその機能が特別な言語仕様を増やすことなく実現できるのです。
サンタ側ではこんな感じの処理になっています

    3.times do
      reps = []
      3.times do |i|
        a = hobbitmail.pop
        reps.push a
      end
      mess =  "HoHo Let's make present\n"
      main.unshift mess

      reps.each do |ele|
        ele[1].push 1
        nil
      end
    end

hobbitmail.popで配列になにか入るまで待ちます。待ちはMutexをlockすることで行います。小人側が配列にpushしたらMutexをunlockします。サンタはpopした後、配列が空ならMutexをlockします。空と判断してMutexをロックする間にpushしたら？って思われるかもしれませんが、配列そのものの排他制御のMutexが別にあってそれを掛けた状態で行いますので大丈夫です。つまり、途中で空になりえる配列などは何か値が入るまで待つものと全体の排他制御の2つのMutexを持っています。これはMutexオブジェクトとは違う、MutexEmptyLockオブジェクトという別のクラスになります。
こんな感じで小人から来たメッセージをとりあえず配列に入れて3人集まったらサンタ本体に知らせて、そのあと小人に仕事が終わったことを知らせます。3人集まっていないのに小人を解放するようなズルはしていません。

サンタクロース問題の全リストです。複雑に共有関係をもった多数のスレッドを生成する100行くらいのプログラムではそれほどいらいらすることなくCに変換できます。ただ、GCの並列化にバグが残っていてすんなり動かないです。ただ、Darty&Quickハックで何とか完走したのでロック関係のバグは無いと思います。

def main
 pp "START"
 # Santa hobbit dev.
 m = []
 hobbit = MMC_EXT::Thread.new(m) do |main|
   hobbitmail = []
   hobbitlist = Array.new
   9.times do |i|
     hobbitlist.push MMC_EXT::Thread.new(hobbitmail, i) {|mail, id|
       sleep((rand*10).to_i)
       pp "hobbit wake up #{id}"
       reply = [id, []]
       mail.push reply
       reply[1].pop
       pp "Hobbit Work done #{id}"
     }
   end

   3.times do
     reps = []
     3.times do |i|
       a = hobbitmail.pop
       reps.push a
     end
     mess =  "HoHo Let's make present\n"
     main.unshift mess

     reps.each do |ele|
       ele[1].push 1
       nil
     end
   end
   main.unshift nil

   hobbitlist.each do |th|
     th.join
   end
 end

 # Santa tonakai dev.
 tonakai = MMC_EXT::Thread.new(m) do |main|
   tonakaimail = []
   tonakailist = []
   27.times do |i|
     tonakailist.push MMC_EXT::Thread.new(tonakaimail, i) {|mail, id|
       sleep((rand*10).to_i)
       pp "tonakai wake up #{id}"
       reply = []
       mail.push reply
       reply.pop
       pp "Tonakai Work done #{id}"
     }
   end

   3.times do
     reps = []
     9.times do |i|
       a = tonakaimail.pop
       reps.push a
     end
     mess = "HoHo Let's send present\n"
     main.push mess

     reps.each do |ele|
       ele.push 1
       nil
     end
   end
   main.unshift nil

   tonakailist.each do |th|
     th.join
   end
 end

 cnt = 2
 sleep(1)
 while cnt > 0
   mess = m.pop
   pp "foo"
     pp mess
   if mess then
   else
     cnt = cnt - 1
   end
 end

 hobbit.join
 tonakai.join
 pp "OK"
 nil
end

例3 カウンタ

サンタクロース問題も書けてすっかり有頂天になってロックはすべて自動的に挿入できると思っていたころに、次のようなリプライを頂きました。

こういう記法を許さず、共有された領域はのアクセスはすべてメソッド内で完結させるルールにすればいいのですが、Rubyではsetter/readerを多用するのでかなり不自然な記述を強いることになりそうです。また、保守的にロックを掛けるとちっとも並列度の上がらないGILみたいなことになることは明らかです。

マニュアルlock

とりあえず、マニュアルでlockを掛けるメソッドを作りました。また、勝手にlockを掛けないよう余計なことをしないようにするモードを用意しました。
例えば、カウンターを考えてみましょう。

class Count
   include MMC_EXT::LockPolicy::NoLock
#  include MMC_EXT::LockPolicy::LockFree

  def initialize
    @c = 0
  end

  def cnt=(v)
    @c = v
  end

  def cnt
    @c
  end
end

この定義のうち、

include MMC_EXT::LockPolicy::NoLock

が余計なことをしないようにするための指示です。先程説明したLockFreeと同じような概念です。
lockメソッドはこんな感じで使います

  th = MMC_EXT::Thread.new(cntins) {|cnt|
    cnt.lock do |c|
      c.cnt = c.cnt + 1
      pp c.cnt
    end
  }

cntのMutexをlockした中身がcに入ります。余談ですが、mmcの型システムではcとcntは別の型です。ロックしたかのフラグを持っています。

おまけの機能として、違う順番でlockしたら警告が出るようにしました。

  th = MMC_EXT::Thread.new(c, r1) {|cnt, res|
    cnt.lock do |c|
      res.lock do |r|
       c.cnt = c.cnt + 1
        pp c.cnt
      end
    end
  }
  th2 = MMC_EXT::Thread.new(c, r1) {|cnt, res|
    res.lock do |r|
      cnt.lock do |c|
        c.cnt = c.cnt + 1
        pp c.cnt
      end
    end
  }

みたいなコードだと、thとth2でロックする順番が違います。こういう場合、デッドロックになりえるので警告します。別のメソッドでも呼び出し履歴を見るので警告します(そもそもRubyのブロックってメソッド呼び出しみたいなものですし)。

ヒューリステックなロックアルゴリズム

やはり、マニュアルでロックを掛けるのは負けたように感じるので、場合を限定して自動的にロックが挿入できるようにしてみました。
基本的にこういう考え方でロックを挿入できるか判定します

  • 長期間ロックを掛けたままにすることは稀
  • アトミックな領域が必要になるのは、インスタンス変数や配列の要素を読みこんで、何か処理をして、それを再び同じ場所に書き込むという動作の時

たとえば、今問題になっているアクセサを使ってインクリメントするなんてのはこのパターンにあてはまります。この考えをもとにこういうアルゴリズムでロックを掛けるかを判定します。

  1. あるメソッドが、インスタンス変数の読みこみ4のeffectを持っているメソッドを読んでいること。ただし、書き込みのeffectは持っていないこと(持っていればこのメソッドでアトミック領域が完結している可能性が高いから)
  2. 1と同じオブジェクトでインスタンス変数の書き込みのeffectを持っているメソッドを呼び出していること。ただし、読みこみのeffectは持っていないこと

このような条件を持つオブジェクトをレシーバーとする最初のメソッド呼び出し時にそのレシーバーのオブジェクトにロックを掛けます。本当は1で参照された値が2で書きこまれているかデータフローを追った方がいいのですがさすがにコンパイルが重くなりそうなので端折りました。

マニュアルロックとこのヒューリステックなロックは混在させることが出来ます。複数のロックポリシーで作ったカウンタを同時に動作させてちゃんと動くとなかなか達成感があります。出力は単に数字が順番に並ぶだけですけど。

この方法ではうまくいかないプログラムが書けるのは自明なんですが、そのプログラムがうまく行くのは自明ではありません。結局、このアプローチが良かったのかどうかはまだまだ分からないと言うことです。いろいろなサンプルプログラムを作って実証する(おそらくヒューリスティクの方針が変わっていく)必要があります。

まとめ

自動的にlockを入れるのは有望そうなアプローチではあるのですが、プログラマが考えるアトミックな領域がコンパイラからは完全に分からないのなら、Rustのようにマニュアルのlockが必要なのかなと思いいます。ただ、事実上問題ないというレベルにまでコンパイラが推定できる可能性もありそうです。

エピローグ

　最初に提示したRustはすっとこどっこいか？という疑問ですが、分かりませんでした。　いかがですか？

  1. 筆者はアンチRustです ↩

  2. ブロックがProcオブジェクトとになっている場合も可能だと思いますが、試していません。 ↩

  3. 型を表示するのはRubyの言語仕様から外れる特別な方法が必要(またはプログラムにprintを入れる)ですけど ↩

  4. これ書いていて　a[2] = a[2] + 1みたいなコードに対応していないことに気づいた。直せるので後で直す(納期は明記しない、ライフハック) ↩

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?