金利0無利息キャッシング – キャッシングできます

 | 

2009-09-20

軽量スレッドブームだと思うので、そこらへんの情報をまとめてみる

20:54 | 軽量スレッドブームだと思うので、そこらへんの情報をまとめてみる - 金利0無利息キャッシング – キャッシングできます を含むブックマーク はてなブックマーク - 軽量スレッドブームだと思うので、そこらへんの情報をまとめてみる - 金利0無利息キャッシング – キャッシングできます

近年(でもないか)、言語内に実装された軽量スレッド/軽量プロセスを利用することで、OSが提供するスレッド機能の限界を超えた数の並列処理を行うことが容易に出来るようになって来ています。PerlのCoro、RubyのFiber、Erlangのプロセスなどです。Perlについては少し詳しく解説しますが、他の言語については知らないことが多いですので、適当だったり大雑把だったりするでしょう。

10年前とは何が違うか?

  • マルチコアCPUが一般的になった。
  • 今後もCPUのコア数は増加する傾向にある。
  • C10K問題が知られるようになった。Webプログラマにさえも。
    • 「1コネクション:1スレッド」のプログラミングモデルは分かりやすい
    • が、カーネルスレッドは数千、数万のスレッドを生成できない。
    • A: マルチスレッドを捨てる B: 軽量スレッドを使う

スレッドの実装レイヤーでの対比

  • ユーザーレベルかカーネルレベルか?
    • ユーザー空間で実装されているかカーネル空間で実装されているかの対比
  • グリーンスレッドかネイティブスレッドか?
    • VMがスケジュールするかOSがスケジュールするかの対比
  • プリエンプティブかノンプリエンプティブか?
    • 勝手に切り替わるか、明示的に切り替えるのかの対比
参考文献

コルーチンとウェブアプリケーションスケーラビリティ

M:Nスレッドに関する議論

M:Nスレッドというのはカーネルレベルスレッドとユーザーレベルスレッドの数が非対称なスレッドモデルを指す。4コアのCPUを使っている場合、10個のユーザーレベルスレッドを4個のカーネルレベルスレッドで実行する、とか。

http://www.hyuki.com/yukiwiki/wiki.cgi?TheC10kProblem#i17

スレッドライブラリを実装するのには選択肢がある: 全てのスレッド処理をカーネルで行う (これを 1:1 スレッドモデルという.) か, 一部をユーザ空間に持ってくるかだ. (これを M:N スレッドモデルという.) ある時点では M:N スレッドの方が高性能だと考えられていた. しかし正しく動かすにはあまりに複雑だったため, やがて人々は離れていった.

  • NGTP: IBMの開発していたLinux上でのM:Nスレッドの実装
    • NGTP のチームはそのコードをサポートのみのモードに移行すると発表した. その理由は彼らいわく "それがコミュニティを支援する最良の道だ" と感じたからとのこと
  • FreeBSDではKSEという実装があったが削除された
  • Solaris 2 から Solaris 8 まで デフォルトのスレッドライブラリは M:N モデルを採用していた. しかし Solaris 9 は 1:1 モデルのスレッドをデフォルトとした
  • http://www.namikilab.tuat.ac.jp/~sasada/prog/nptl.html
    • M:Nモデルは「処理が複雑。保守性が悪い。効率が悪い。」

などなど。アプリケーションや言語処理系は(余計なことを考えずに)OS標準のスレッドモデル(ネイティブスレッド)を使用し、OSが「より効率の良いスレッドモデル」を実装するというアプローチがあります。一時期、M:Nスレッドモデルは多数のスレッドを生成する際に高性能だと考えられていましたが、今は廃れています。もちろんネイティブスレッドを改良する試みがありますが、1:1のスレッドモデルが主流となりました。現行のOSではM:Nスレッドモデルは主流ではありません。なので「ネイティブスレッド」と言った場合は、1スレッド=1カーネルスレッドというスレッドモデルを指すと考えて良いでしょう。

現実問題として現在のカーネルスレッドは、大量に生成した際にパフォーマンスが劣化します。カーネルスレッドを作り放題という未来は当面やってこないでしょう。なので数千のスレッドを作成するようなアプリケーションの場合、ユーザーレベルで実装された軽量スレッドが必要になります。OSのレイヤーでのM:Nスレッドへの取り組みは廃れましたが、それに代わって言語処理系やアプリケーションのレイヤーでのM:Nスレッドのアプローチは普及しているのではないか、と考えています。(実際そういうことをやっているので)

LLにおけるグリーンスレッド VS ネイティブスレッド

カーネルレベル <-> ユーザーレベルを行ったりきたりしないので、一般的にはユーザーレベルで実装されたスレッドのほうが切り替えコストが軽い、と考えられているが、LLのインタプリタレベルで実装されているスレッドはそんなに効率が良くなかったりする。ネイティブスレッドを使用するとマルチコア性能を生かせるはずだが、何か色々理由があって上手くいかなかったりする。そんな現状である。個人的にはLLを使ってる人はマルチコア使い切りたいとか、あんまり考えてないと思うし、そんな必要もないと思う。何も考えずに使えるほうが重要。

Perl
  • Perlスレッドの歴史 http://search.cpan.org/~dapm/perl-5.10.1/lib/Thread.pm#HISTORY
  • 5.005のスレッドはデータが共有される。色々問題があって廃止。
    • 全てのデータは共有される。スレッド固有にしたい変数は宣言する。
  • 5.6でithreadが登場、win32環境におけるforkエミュレーションのために書かれたコードだ。
    • 全てのデータがコピーされる。共有したい変数を明示的に共有する。
  • 5.10では5.005のスレッドは廃止、ithreadが標準となった。色々問題がある。
  • Perlのithreadは全データをコピーするからforkよりも生成が遅く、メモリ消費量も多い。
  • XSモジュールはスレッドセーフを意識していなければ使えない。
Python

GILを無くす試み

Ruby
  • 1.8のスレッドは移植性が高いが、効率が悪い。

http://www.loveruby.net/ja//rhg/book/thread.html

以上がrubyのスレッド切り替えの実装だ。どう考えても軽くはない。大量に malloc() realloc()して大量にmemcpy()してsetjmp() longjmp()した挙句スタックをのばすために関数を呼びまくるのだから「死ぬほど重い」と表現しても問題あるまい。しかしその代わりにOS依存のシステムコール呼び出しもなければアセンブラもSparcのレジスタウィンドウ関連のみだ。これならば確かに移植性は高そうである。

http://www.infoq.com/jp/news/2009/08/future-ruby-gc-gvl-gil

  • Ruby1.9はネイティブスレッドを使用するようになった。
  • しかしPythonと同様、同時実行されるスレッドを制限するための、GVL(Giant VM lock)という仕組みがある。
  • GVLを削除するのは難しい、VMを複数実行するMVMアプローチが研究されている。

対称型と非対称型

http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%AB%E3%83%81%E3%83%97%E3%83%AD%E3%82%BB%E3%83%83%E3%82%B7%E3%83%B3%E3%82%B0

マルチプロセッシングシステムでは、全CPUが等価の場合といくつかのCPUが特別な用途に使われる場合がある。

これはハードウェアレベルでの話を指していますが、マルチスレッドプログラミングの手法においても同じ概念が通用します。非対称型では、役割によって余っているCPUが出てくるため、究極的には対称型の方がCPUを使いきれるということになります。

  • 対称型: 全てのスレッドが同じ役割を持つ。
  • 非対称型: 役割ごとにスレッドを作成する。

サーバーを書く場合には次のように区別できるでしょう。

  • 対称型: 1リクエストを処理するためのコードを書いて、マルチスレッド化する。
  • 非対称型: I/O処理、プロトコル処理、レスポンス生成などの特定の役割ごとにスレッドを作る。

対称型と非対称型では、必要となるスレッド数が異なります。

  • 対称型は、同時処理するリクエストに応じてスレッドを生成する必要があります。
  • 非対称型は、役割ごとに並列処理したい件数のスレッドを生成します。
    • 少数のスレッドで多量のリクエストを同時に処理したいケース(生成可能なスレッド数に上限がある場合や、スレッドが増えた場合のパフォーマンス劣化がある場合)では、非対称型を選択するメリットがあります。

内部的には非対称型のスレッドモデルを使用して、アプリケーション開発者から見た場合には対称型のモデルでコードを書けばよい、というアプローチもあるでしょう。この場合、アプリケーション開発者は全てのスレッドが同じように振舞うようにコードを書き、言語処理系やライブラリが特定の機能を別のスレッドで行うようになります。

  • Erlangにはasync thread poolという機能があります。実装がどうなってるのかは知りません。
  • http://www.mikage.to/erlang/#toc_5
  • PerlのIO::AIOモジュールも内部で専用のスレッドを作ります。

AIOの利用、ReactorパターンとProactorパターンの対比

これはI/Oのパフォーマンスに関する話になります。例えばファイルディスクリプタにデータを書き込む場合だと

  • Reactorパターンでは「writableになるのを待つ、書き込めるだけ書き込む」というのを全ての書き込みが終わるまで繰り返します。
  • Proactorパターンでは、カーネルに転送を任せて、転送が完了した時点でイベントが発生します。

AIO_*システムコールを使います。

  • 極端な話、1byteずつしかデータを送れないデバイスがあったとして
    • Reactorパターンで1MB送ろうとした場合、100万回(100万 * n)のコンテキストスイッチが発生する。
    • Proactorパターンの場合は、カーネルに1MBのデータを送っておいて、と依頼して終わったらユーザーモードに処理が戻る。コンテキストスイッチは最小限で済みます。

どちらが優れているか?

  • ユーザーモードとカーネルモードのコンテキストスイッチのコスト。
  • 加えて: イベント駆動モデルで書いている場合は、関数呼び出しのコスト。
  • 加えて: スレッドモデルで書いている場合は、スレッド or 軽量スレッドのコンテキストスイッチのコスト。

が、発生することになります。

このコストが無視できないほど大きい場合、Proactorパターンの優位性が大きくなる、ということになるでしょう。

Perlの場合

AnyEventを使ったI/O処理は基本的にReactorパターンです。が、IO::AIO + AnyEvent::AIO or Coro::AIOを用いることで、Proactorパターンを用いることも可能です。

  • IO::AIO http://search.cpan.org/perldoc?IO::AIO
  • これも作者はMarc Lehmannです
  • Perlbalでも使われています。ただしIO::AIOが使えない環境ではAIO_*システムコールを使わずに単にエミュレートしています(Perlbal::AIOを参照)

AIOシステムコールはすぐに完了しますが、処理が実際にいつ完了するのか分かりません。IO::AIOではIO::AIO::poll_filenoを監視することで、AIOが完了したタイミングを知ることが出来ます。

  • イベントが発生するとIO::AIO::poll_filenoがreadableになります。
  • IO::AIO::poll_cbを呼び出すと、イベントに紐付いたcallbackを実行します。

という仕組みになっているようです。AnyEvent::AIOがやってくれます。IO::AIOはaio_*を発行するための専用のスレッド(Perlのスレッドではなく、ネイティブスレッド)を立ち上げて、そこで処理をします。このスレッドはPerlからは見えません。

他の言語の場合
  • 未調査

共有ステート並行処理とメッセージ渡し並行処理の対比

これは、手続き型言語と関数型言語の対立に近いと思います。いわゆる通常のマルチスレッドは前者です。後者はErlangScalaのActor、メッセージパッシングを用いた並列処理を指します。

  • 関数型の副作用がないという特徴はActorモデルと相性が良い。
  • 同じ関数に同じ引数を渡したら同じ結果が返ってくる。

メッセージパッシングを用いた並行処理は「スレッドが物理的に別のマシンであっても」同様に動作します。

Perlの場合
  • AnyEvent::MP - multi-processing/message-passing framework
  • JSONでデータを受け渡しします。
  • Coro::MPも予定されているようですが、まだありません。
Rubyの場合
  • RubyにRevactorというライブラリがあります。
  • 内部でrevというlibevのRubyバインディングを使用しています。

マルチスレッドプログラミングはどこに向かうか?

自分はOS開発者でも言語開発者でもないので、現状でもっとも現実的な選択肢を選ぶようにしています。

そんなわけで現在は、次のようなアプローチを取っています。

  • シングルスレッド + I/O多重化 + イベント駆動 + (AIOを使ったI/O処理専用スレッド)
  • Prefork + Coroによる軽量スレッド
    • forkしたプロセスは一定時間経過するか、指定件数を処理したら終了します。
    • もしメモリリークがあった場合に、メモリ使用量が肥大化するため
  • マルチコア性能を生かすためのネイティブスレッド or 単にfork
  • ユーザーレベルで実装された軽量スレッド
  • ライブラリで提供される用途特化型スケジューラー

これらを目的に応じて適度に使い分けていけばいいんじゃないですかね。長文乙。

KatyKaty2013/01/19 09:56Such an impressive aneswr! You've beaten us all with that!

drsmprpndadrsmprpnda2013/01/20 10:27h8TRp4 <a href="http://drgemmwkpleo.com/">drgemmwkpleo</a>

ojclmetlhjojclmetlhj2013/10/27 02:21knhzttvcufdi, <a href="http://www.yocyomrcft.com/">gqlwrahlyt</a> , [url=http://www.oyrssjsnqe.com/]rmxlvkbepf[/url], http://www.muexzxcipd.com/ gqlwrahlyt

 |