特集
2003/06/27 00:48 更新

UNIX USER 2003年7月号特別企画より転載
Native POSIX Thread Library for Linux

新しいスレッドライブラリ「Native POSIX Thread Library for Linux」について、Red HatのUlrich DrepperとIngo Molnarが発表した論文の内容を簡単に紹介する。
標準的なLinuxスレッドの実装

UNIX USER今日、標準的に使われているLinuxスレッドの背後にある考え方は、「プロセス間のコンテクスト切り替えが、1つのカーネルスレッドで各ユーザースレッドを扱うのに十分なほど高速である」というものだ。スレッドレジスタは使用せず、局所的なメモリはスタック上に置かれる。

　また、シグナルやそのほかの管理を正しく行うためには、管理スレッドが必要となる。カーネル内に利用できる同期プリミティブが存在しないため、実装にはシグナルを利用するしかない。

これまでの改善と問題点

　スレッドライブラリは、これまでにもABI（Application Binary Interface）とカーネルという2つの領域で改善されてきた。

　新しいABI拡張ではスレッドレジスタが導入され、スレッドデータのアクセス時間が改善された。このような変更が容易かどうかはアーキテクチャに依存し、必要な機能がプロセッサになければスタックに頼るしかない。IA-32では、セグメントレジスタ%fsと%gsが使用される。セグメントのベースアドレスは記述子テーブルに格納されるため、OSからしかアクセスできず、記述子テーブルを変更する操作、たとえばプロセス間でのコンテクスト切り替えは遅くなってしまう。セグメントレジスタは8192通りの値しか持てないため、スレッド数の上限も制約を受ける。

　カーネル2.4までに行われた変更は、IA-32のセグメントレジスタを利用する機能を安定させることと、cloneシステムコールの改善だ。しかし、依然として管理スレッドの必要性を完全に排除するまでには至っていない。

　このように、既存の実装には数多くの問題が残っている。主なものはリスト1のとおりだ。

リスト1：既存の実装の問題点
・管理スレッドはボトルネックになるだけでなく、管理スレッドが終了すると残りのスレッドを手作業で後始末する必要がある
・シグナル機構はPOSIX仕様に準拠していない。プロセス全体にシグナルを送信する方法もない
・シグナルを使って同期プリミティブを実現しているため、速度が犠牲になり、複雑な管理が必要
・SIGSTOPやSIGCONTでマルチスレッドのプロセスを停止/再開できない
・スレッドごとに異なるプロセスIDを持つため、ほかのPOSIXスレッド実装と互換性がない
・IA-32では8192個というスレッド数の制限がある
・/procはすべてのスレッドを表示するため、スレッド数の多い（数百から数千）プロセスには役立たない
・カーネルのサポートがないため、シグナルの実装が難しい
・シグナルによる同期プリミティブの実装は見苦しい

新しい実装の目標

　新しい実装の目標は、完全な書き直しによってABI互換を実現することだ。要求事項としては、次のものがある。

・POSIX準拠
　ほかのプラットフォームとのソースコード互換性を実現するため、最新のPOSIX標準に準拠する。

・SMPの有効利用
　マルチプロセッサシステムの能力を最大限に利用できれば、各CPUにスレッドを分割することで線形の速度向上が得られる。

・生成コストの低減
　低コストでスレッドを生成できれば、小さな仕事にもスレッドが使用できる。

・リンクコストの低減
　スレッドを使わないプログラムがスレッドライブラリとリンクされた際、大きな影響を受けないようにする。

・バイナリ互換性
　POSIX準拠となる点を除いて、Linuxスレッドとバイナリ互換を保持する。

・ハードウェアスケーラビリティ
　プロセッサ数の増加によって管理コストを増大させない。

・ソフトウェアスケーラビリティ
　スレッドやオブジェクトの個数に上限を持たせない。

・マシンアーキテクチャサポート
　大規模なマシンを効率的にサポートするには、システム寄りのコードにおいてアーキテクチャの詳細な情報を取得する必要がある。

・NUMAサポート
　将来のマシンで利用される「非均質メモリアーキテクチャ」（NUMA）を考慮した設計とする。

・C++との統合
　C++の例外処理と同様に、スレッド終了時にもオブジェクトのデストラクタが呼び出されることが期待される。

設計上の決定事項

　実装を行う前に決定すべき事項がいくつかある。

●1対1とM対Nの選択

　ユーザーレベルのスレッドのみによる実装ではSMPを活用できないため、カーネルスレッドの必要性に議論の余地はない。問題はカーネルスレッドとユーザースレッドの関係である。従来の1対1モデルでは、1つのユーザースレッドに1つのカーネルスレッドが対応する。一方、M対Nモデルでは、カーネルスレッドとユーザースレッドの数は直接対応せず、利用可能なカーネルスレッドに対してユーザースレッドをスケジュールする。

　カーネル開発者の多数意見は、「M対NモデルはLinuxカーネルに適さない」というものだ。変更にかかるコストが高すぎ、コンテクスト切り替えも容易ではない。また、ユーザーレベルのスケジューリングが必要とされる問題の多くは、Linuxカーネルにとって切実なものではない。さらに、M対N実装のために必要なコードの保守コストも無視できない。

●シグナルの取り扱い

　M対Nモデルを使用すると、カーネルによるシグナルの取り扱いを単純化できる。というのも、シグナルの発行許可をカーネルが決定するには、すべてのスレッドのシグナルマスクを調査する必要があるが、M対Nモデルでカーネルスレッドの数が抑えられれば、調査をユーザーレベルで実行できるからだ。

　しかし、M対Nモデルではsignalstack機能を占有することになり、また受け入れ不能なEINTRを回避するためにシステムコールにラッパーが必要となるため、オーバーヘッドが増加する。

　シグナル発行のシナリオには、さらに2つの選択がある。

  1. シグナルは専用のシグナルスレッドに対して発行される。ただし、このスレッドにすべてのシグナルが集中するという欠点があり、POSIXシグナルモデルの概念に反する
  2. ユーザーレベルのシグナルは、シグナルハンドラとは異なる上位呼び出し機構によって発行される。カーネルが複雑になるという欠点がある

　M対Nモデルのシグナル操作をユーザーレベルで実装することは可能だが、大変困難であり、多くのコードによって通常の処理が低速になる。その代わり、カーネルはPOSIXシグナル処理を実装できるという利点がある。

●ヘルパー/管理スレッドは必要か

　管理スレッドは、次のような問題によってその必要性が高くなる。

  • 致命的なシグナルに反応してプロセスを正しく終了させるには、すべてのスレッドを監視しなければならない
  • スレッドの終了後にスタックを解放する必要がある
  • スレッドがゾンビにならないように、スレッドの終了はwaitされる必要がある
  • 主スレッドがpthread_exitを呼んでも、プロセスが終了されない
  • セマフォ操作のために助けが必要なケースがある
  • 局所データの解放には管理スレッドが必要である

　カーネルの支援があれば、管理スレッドがなくてもこれらの問題は解決できる。管理スレッドは1つのCPUでのみ実行されるため、SMPやNUMAの環境ではスケーラビリティに影響してしまう。管理スレッドが存在しなければ、コンテクスト切り替えも減り、設計も単純になるわけだ。

●全スレッドのリスト

　Linuxスレッドでは、実行中の全スレッドのリストを管理していた。プロセス終了時に終了させるべきスレッドの情報を得るために使用されるが、カーネルの支援があればこのリストは不要となる。

　また、全スレッドのリストは、pthread_key_deleteを実現するためにも使用される。キーが削除された時点でスロットをクリアすることにより、続くpthread_key_createでキーの再利用が可能になる。生成カウンタを使えば、必要なデストラクタだけを実行でき、スレッドリストを使わずに済む。

　ただ、リストの管理は、完全には回避できない。forkを実現するには全スレッドの内部情報を複製する必要があり、カーネルはこれを支援できないからだ。

●同期プリミティブ

　相互排他などの同期プリミティブを実現するには、カーネルの支援が必要だ。スレッドは異なる優先順位を持つため、ビジーウェイトやsched_yieldは利用できない。利用できる唯一の手段はシグナルだが、速度や信頼性が低下するという欠点があった。幸いなことに、すべての同期プリミティブを実現できる新しい機能、futexがカーネルに追加された。

　futexのもう1つの利点は共有メモリ領域を使うことであり、そのためfutexは複数プロセスで共有可能となる。これによりPOSIX準拠となり、PTHREAD_PROCESS_SHAREDオプションも実現できる。

●メモリ割り当て

　スレッド生成コストを下げるため、次のようなメモリ割り当ての最適化が必要になる。

  • メモリブロックを併合し、主要なデータはスタックに置く
  • スタックフレームをキャッシュし、メモリブロックを再利用する。32ビットマシンではアドレス空間が限られているため、キャッシュサイズの上限を設定する必要がある
カーネルの改善

　カーネル2.5.xの初期バージョン以降で追加された変更は次のとおりである。

  • TLS（Thread Local Storage）システムコールによってGDT（Global Descriptor Table）エントリが利用できるようになり、スレッド数の制限なしに1対1モデルが実現可能となった
  • cloneシステムコールにCLONE_PARENT_SETTID、CLONE_CLEARTID、CLONE_TLSフラグが導入された。これによって、未使用メモリブロックをユーザーレベルで認識でき、またシグナルに対して安全なスレッドレジスタのロードが可能になった
  • マルチスレッドプロセスに対するPOSIXシグナル操作をカーネルで実装し、ジョブ制御も可能となった
  • プロセス全体を終了させるexit_groupが用意され、exitの処理も劇的に高速化された
  • execはプロセスIDを引き継ぐようになった
  • 資源利用率はプロセス全体について報告されるようになった
  • /procには初期スレッドのみが含まれ、カーネルはすべてのスレッドが終了するまで初期スレッドを保持する
  • 分離スレッドのサポート
  • 任意個数のスレッドを扱えるようカーネルが拡張された
  • pthread_joinは子の終了後に戻れるようになった
性能測定結果

　2種類の性能測定に関する結果を示しておく。テスト仕様の詳細と測定結果のグラフについては、原論文を参照してほしい。

●スレッドの生成と破棄にかかる時間

　トップレベルのスレッドを1〜20個生成し、それぞれについて子スレッドを1〜10個生成する200通りのテストを行った。各スレッドは何も仕事をせずにすぐに終了する。

　このテストからは、「NGPT（New Generation POSIX Threading）がLinuxスレッドの約2倍高速であり、さらにNPTLはNGPTの4倍高速である」という結果が得られた。

●競合の取り扱い

　32個のスレッドと可変個数の排他領域を生成し、スレッドがその排他領域に全体で5万回飛び込もうと試みるテストを行った。

　futexに対して最適化されたスケジューラを持つ2.4.20-2.21カーネルは、現在のところ、その変更が行われていない2.5.59カーネルより高速だが、いずれの場合もNPTLの消費時間はLinuxスレッドよりも著しく少ない（最大数十％程度）という結果が得られた。

関連記事

関連リンク

[太田 純，UNIX USER]

Copyright © ITmedia, Inc. All Rights Reserved.