※ 左右のカーソルキーでもページ繰りができます(但しブラウザ依存)
藤原 克則 ( FUJIWARA Katsunori )
受託開発主体の独立系ソフトウェアハウス数社を経て、現在フリーランス。
前職で、 HPC ( High Performance Computing ) 系システムのために Solaris 向けファイルシステムを実装したのを機に、 OpenSolaris 勉強会に参加。
「lsを読まずにプログラマを名乗るな!」、 「入門TortoiseHg+Mercurial」とか 「俺のコードのどこが悪い?―コードレビューを攻略する40のルール」、 「アセンブラで読み解くプログラムのしくみ」(電子書籍) といった書籍の執筆や、 技術系ウェブ媒体への記事の寄稿も。
ホームページ以外にも、 はてなダイアリー (id:flying-foozy) 等で情報発信中。 Twitter アカウント (@flyingfoozy) は細々と運用中。
本資料は、 "Solaris Internals" の第17章を、 各段落毎に「ワンフレーズ」化すること基本としています。
「ワンフレーズ」化対象の段落を識別するために、 以下のような識別情報表記を使用します。
[{章/節番号}/{通し段落番号}]@p.{ページ番号}
例えば、"[9.2.6/2]@p.465" は、 以下で始まる 「465 ページに配置されている、9.2.6 節における第2段落」 を指します。
As shown in the example, the program's address space comprises ...
列挙の各項目も1段落として扱います。 単一の列挙項目が複数の段落から構成されている場合は、 構成要素の段落を、それぞれ個別の段落として扱います。
識別情報の構成要素は、 紙媒体の "Solaris Internals Second Edition" を元にしています。
なお、個人的に興味深いと思った点に関しては、 勝手に掘り下げた話を展開します。
書籍の正誤情報は、 Solaris Internals サイトの、 Errata 情報を参照してください。
[17/1]@p.xxx
本章では、カーネルのコア機能に関する議論の続きとして、 Solaris カーネルで実装されている同期オブジェクトを調査します。
[17.1/1]@p.xxx
今日存在するマルチプロセッサシステムは、 性能と、 ソフトウェア/ハードウェアの複雑度の間で、 様々なトレードオフを提供しています。 現在 Solaris がサポートしているマルチプロセッサアーキテクチャは、 Symmetric Multi Processor (SMP) 且つメモリ共有アーキテクチャです。 このアーキテクチャでは、 全てのプロセッサが、 同一のメモリアドレス空間で、 単一のカーネルを共有します。 このようなアーキテクチャをサポートするためには、 クリティカルなデータの data integrity, coherency および状態を保つために、 これらへのアクセスを同期する必要があります。 特定のカーネルデータ構造や変数に対して「排他」を定義し、 それらを読み書きするコードに「排他」の獲得を要求することで、 アクセスを同期します。 クリティカルなデータへのアクセスが完了した時点で、 「排他」は解放されなければなりません。
[17.1/2]@p.xxx
同期機能とそのI/Fは、 デバイスドライバ、ディスパッチャ、 プロセス/スレッドのサポート処理、 ファイルシステム等々、 殆ど全てのカーネルサブシステムで使用されます。 同期オブジェクトやその実装に関する洞察は、 マルチプロセッサシステムにおける性能のスケーラビリティといった、 Solaris カーネルの強みを理解するための鍵となります。 スケーラビリティにおいて同等に重要な要素として、 可能な限りの全体排他の回避があげられます。 カーネルにおける排他による同期の利用は、 データ完全性を損なわない範囲で、 獲得が必要とされる排他を最小化する観点を持ちつつ、 カーネルエンジニアリングにおける開発プロセスの一部として、 常に吟味される必要があります。
[17.1/3]@p.xxx
これまで、 幾つかの並列マルチプロセッサシステムの構築方法が登場してきました。 そのため、 実装に関わる問題点を伝える上で、 文脈を示す必要があります。 はじめに、 今日商業的に利用可能な、 複数の並行システムのアーキテクチャの概要に触れた上で、 マルチプロセッサアーキテクチャを Solaris カーネルでサポートする上で、 固有の話題に踏み込んでいきます。
[17.2/1]@p.xxx
Sun が提供しているマルチプロセッサシステムは、 Synmetric Mutil Processor (SMP) システムです。 SMP システムでは、 システム上の全ての CPU は互いに同等の peer-to-peer の関連性を持ちます。 カーネルコードや割り込み処理の実行を、 単一のプロセッサでのみ実施するための、 「マスタープロセッサ」といったものは存在せず、 全てのプロセッサは等価です。 SMP という略語は、 物理アドレス空間やカーネルの仮想アドレス空間に対して、 システム上の全プロセッサが単一のビューを共有するアーキテクチャを指す、 Shared memory Muti Processor の意味にも拡張可能です。 言い換えるなら、 全てのプロセッサが、 単一のカーネルイメージを共有しています。 Sun が提供するマルチプロセッサシステムは、 両方の SMP の定義に合致します。
[17.2/2]@p.xxx
別なマルチプロセッサアーキテクチャでは、 アドレス指定対象メモリのビューが異なります。 Massively Parallel Processor (MPP) システムは、 比較的少数のプロセッサ/ある程度のローカルメモリ/I/O 等から構成される 「ノード」を、 複数束ねた上に構築されます。 各ノードは、 それぞれが OS の複製を保持することで、 固有の物理/仮想アドレス空間を持ちます。 あるノードのアドレス空間は、 他のノードからは参照することができません。 各ノードは、高速/低遅延のインターコネクトで接続され、 ノード間の通信は、 最適化されたメッセージパッシング I/F 経由で実施されます。 MPP アーキテクチャは、 ノード横断での並列化を実現するために、 新たなプログラミングモデルを必要とします。
Wikipedia 曰く、 「京」のような大規模クラスターマシンも MPP の範疇に含める模様。
[17.2/3]@p.xxx 〜 [17.2/4]@p.xxx
MPP システムでは、 ノードを跨ぐとアドレス空間のビューが異なるため、 異なるノード上で動作するスレッド間でメモリを共有できず、 結果として共有メモリモデルは機能しません。 そのため、 システム上の複数ノード横断でスケールさせるためには、 カーネルのメッセージパッシング API を使用する必要があります。
各ノード毎の I/O コントローラを、 別ノードから利用可能にするのは容易ではないことから、 非統一な性質を持つ I/O 関連のアーキテクチャ由来の問題も発生します。 MPP システムの中には、 カーネルによって仮想的に統一された I/O 空間を、 ノードを跨いで提供するものもありますが、 別ノード上の I/O デバイスへのアクセスの際に、 実際の遅延は異なるままです。
[17.2/5]@p.xxx
NUMA (Non Uniform Memory Access) と ccNUMA (cache coherent NUMA) アーキテクチャは、 MPP システムが持つ、 プログラミングモデルの問題に取り組んでいます。 少数のプロセッサ/ローカルメモリ/I/O 等から構成される小規模ノードを、 ノード間インターコネクトで接続するという、 ハードウェアアーキテクチャ的視点から、 NUMA システムは MPP と似ています。 NUMA/ccNUMA や MPP システムは、 必ずしも小規模ノード (4 個以下のプロセッサ) で構成される必要はありません。 多くのシステムが、小規模ノードから構成されていますが、 ノード規模に関するアーキテクチャ上の制限は存在しません。
当時の SPARC プロセッサは、 確かに CPU あたりのコア数は 4 が主流だが、 現在販売されている SPARC プロセッサは、 SPARC T シリーズ (8core/CPU) や、 SPARC64 X シリーズ (16core/CPU)、 SPARC64 XII シリーズ (12core/CPU) などがある。
[17.2/6]@p.xxx
NUMA/ccNUMA システムの OS は、 単一のシステムイメージを提供しており、 各ノードはシステム全体のメモリ空間のビューを参照できます。 この方式では、 共有メモリのモデルが維持されます。 メモリアクセススピードが統一されていない特性が、 プラットフォームの性能や潜在的スケーラビリティにおいて、 問題の要因となります。 NUMA/ccNUMA システムにおいて、 あるプロセッサノード上で動作しているスレッドが、 ページフォルトを生じた場合、 ページフォルト解消に要する遅延は、 物理メモリが同一ノード上にあるか、 インターコネクト越しの別ノード上にあるかに依存します。 遅延の違いは大きく変化し得ます。 別ノード上で実行されるスレッド間でのメモリページの共有度合が増す程、 別ノード上のメモリによるページフォルトの解消が必要になります。 この問題は、 性能やスケーラビリティに悪影響を与えます。
NUMA 周りに関する詳細は、 前章 "Support for NUMA and CMT Hardware" を参照。
[17.2/7]@p.xxx 〜 [17.2/11]@p.xxx
3つの異なる並列処理アーキテクチャは、以下のようにまとめられます。
図 17.1 は各アーキテクチャの違いを図示しています。
[17.2/12]@p.xxx 〜 [17.2/13]@p.xxx
単一カーネルイメージを共有するマルチプロセッサの全てにおいて、 カーネルコードの実行/割り込み処理等々を実行可能にする場合、 性能のスケーラビリティを保った OS の構築における問題は、 クリティカルなデータ/状態情報へのアクセスを同期する点にあります。 スケーラビリティは一般的に、 システムに追加されるハードウェアに応じて、 処理可能量が増加する状況の達成を指します。 マルチプロセッサシステムにプロセッサを増設した場合、 他の資源 (メモリや I/O、ネットワーク帯域等) が十分であれば その分だけ処理可能量の増加が期待されます。
スケーラビリティの実現には、 カーネル処理を複数のプロセッサで実行できるようにする必要があります。 カーネル処理の実行が、 デバイスドライバ/割り込み処理/スレッド分配/ ファイルシステム/可能メモリ等々の、 いずれに相当するかは、 ある程度までは処理の内容に依存します。 並行性はスケーラビリティの鍵となります。
[17.2/14]@p.xxx
先述した並列アーキテクチャに関する議論は、 非常に込み入った話題の、 表面をわずかに引っ掻いた程度に過ぎません。 並列アーキテクチャについて議論しただけです。 この話題に関する詳細は、 [13]"Scalable Parallel Computing " (Hwang, Zu/1998), [25]"In Search of Clusters" (Pfister/1998), [27]"UNIX Systems for Modern Architectures" (Schimmel/1994) 等を参照してください。
amazon.co.jp 経由の場合、紙媒体しか入手できない模様。 流石に20世紀刊行の書籍だと、余程のニーズがなければ kindle 化は難しいか? あるいは技術系出版社の統廃合の影響? 探せば無料の PDF or ePUB 版もありそうな気はするが……
[17.2/15]@p.xxx
データ構造/カーネル変数/データ間リンク/カーネル中の状態情報の、 データ完全性の維持が技術的な難点です。 例えば、 同一リンクリスト中の同一データを参照するポインタを、 複数のプロセッサ上で実行されている複数のスレッドに対して、 同時に操作できるようにしてはいけません。 あるプロセッサで実行中のスレッドが、 クリティカルな状態情報を改変している間 (例: あるプロセッサを online 化している最中) は、 別のプロセッサによる当該情報の読み出し (例: そのプロセッサが online か否か) を抑止する必要があります。
[17.2/16]@p.xxx
このような状況でのデータ完全性を保つため、 カーネルは排他機構を実装しています。 排他機構によるデータ完全性のためには、 全てのカーネルコードに対して、 カーネル中の排他の数や種類を把握した上で、 データ読み書きに先立つ排他の階層や獲得手順を順守することが求められます。 スケーラブルなカーネルの構築におけるアーキテクチャ上の問題は、 共有メモリモデルにおけるマルチスレッド対応アプリを開発する際のそれと、 さほど違いはありません。 マルチスレッド対応アプリも、 カーネル中で使用されているのと同じ排他の機能/手法を使って、 共有データへのアクセスを同期する必要があります。 割り込みやトラップイベントのような、 その他の同期における課題が、 カーネル開発を非常に複雑にしていますが、 基本的な課題はアプリ開発におけるものと変わりありません。
要するに、 並列プログラミングは、 人類には早すぎたテクノロジーということです (笑)
そういえば、 先日 Micosoft が発表した P 言語は、 並列性記述にフォーカスしていて、 なかなか面白そうだとの噂が……
[17.3/1]@p.xxx 〜 [17.3/2]@p.xxx
排他機構の実装には、 ハードウェア固有の配慮が含まれています。 一つ目の配慮は、 排他実装に適した命令セットが提供されていることです。 二つ目の配慮は、 実行中のカーネルスレッドから、 排他状況を参照できることです。
これらの配慮が排他機構においてどのように作用するかを理解するには、 「排他」状態が、 メモリ中の特定の位置に配置されたデータ領域で表現される、 ということを心に留めておいてください。 最もシンプルな形式では、 「排他」状態はメモリ上の単一バイト領域で表現されます。 排他が獲得されている (= set/held/acquired) 状態では、 当該バイト領域は全てのビットが 1 (= 0xFF) に、 排他を獲得可能な状態では全てのビットが 0 (= 0x00) になります。 この説明は非常に初歩的なものですが、 後述する説明を理解する上で非常に重要です。
[17.3/3]@p.xxx
今日出荷されている現代的なプロセッサは、 アトミック実行が保証された、何らかの test-and-set 命令を提供しています。 多くの場合、実行される命令列は read-modify-write と表現されます。 排他情報領域のメモリに対して、 読み出しと内容改変を行った上で書き込みを行うまでが、 単一命令でアトミックに実行されます。 Ultra SPARC T1 のような RISC プロセッサの場合、 読み出しは load、書き込みは store 命令に相当します。 アトミックに実行される命令は、一貫性保証で必要とされます。 読み出し/書き込みをアトミックに実行する命令の実行中は、 他の書き込み (store) 命令は実行されません。 Mutex や RW lock 操作はアトミックでなければならず、 排他獲得の命令が完了した時点で、 「排他獲得済み」か、 「排他の可否を判定可能な情報の入手」のいずれかが、 達成できている筈です。
この文脈での byte-level は、どのレイヤを指すのだろうか? ⇒ 「ビット単位の操作ではない」という意図で、 おそらく「データアクセスサイズ」に対する言及では?
mutex や RW lock の実装自体は、 複雑な処理から構成されているので、 "mutex and RW lock operations must be atomic" は、 幾分観念的な意味での "be atomic" な感じ。
[17.3/4]@p.xxx
アトミック実行が保証された命令がない場合を想像してみましょう。 あるプロセッサ上で実行中のスレッドが、 排他情報を読み出して排他獲得の可否を判定するのと同時に、 別のプロセッサ上で実行中のスレッドが、 同一の排他に獲得処理を実行したとします。 その時点で排他が獲得可能だった場合には、 両方のスレッドが排他獲得可能だと判断して、 排他情報を書き換えてしまいます。 明らかに間違っていますが、 上記のような処理手順の結果、 複数のスレッドが同時に排他を獲得してしまいます。 アトミック実行が保証された命令によって、 このような事態を回避できます。
[17.3/5]@p.xxx 〜 [17.3/6]@p.xxx
SPARC プロセッサでは、 相互排他のためのアトミックな test-and-set を実施するメモリアクセス命令と、 メモリ操作において特定の順序性を強制する命令を実装しています (後者の詳細は後述)。 UltraSPARC (SPARC V9 命令セット) では、 アトミック実行が保証された命令として、 ldstub (load and store unsigned byte), cas (compare and swap), swap (swap byte locations) の3つを実装しています。 これらは挙動や操作データの単位の点で、 お互いが微妙に異なります。
図 17.2 は、 ldstub 命令と cas 命令の概要を示しています。 swap 命令の説明はありませんが、 この命令は、 レジスタとメモリの間で、 単純に 32bit 値の入れ替えを行います (cas 命令で比較が成功した場合の挙動と同じ)。
[17.3/7]@p.xxx 〜 [17.3/8]@p.xxx
排他処理では、 test-and-set 系命令のアセンブラ記述に引き続き、 得られた排他情報の確認処理が必要です (排他の成否等)。
例えば ldstbu 命令は、 メモリから読み出した排他情報を指定されたレジスタに格納します。 排他処理は、 得られたレジスタ値を元に、 排他獲得の成否を判定します。 レジスタ値の全てのビットが 1 (= 0xFF) の場合、 別のスレッドによって排他獲得済みなので、 排他待ち処理に分岐します。 レジスタ値の全てのビットが 0 (= 0x00) の場合、 排他獲得の成功を意味するので、 排他保持者として処理を継続します。 いずれの場合も、 メモリ上の排他情報領域は、 ldstub の動作仕様上、 全てのビットが 1 (= 0xFF) になります。 他のスレッドによって排他が獲得済みの場合、 メモリ上の値は変わりません。 排他が獲得可能な場合は、 「排他獲得済み」を表す値 (= 0xFF) になります。 排他の解放処理は、 メモリ上の全てのビットを 0 (= 0x00) にすることで、 排他が獲得可能であることを示します。
[17.3/9]@p.xxx
Solaris における排の実装は、 排他の可否判定をアセンブラ実装 (ldstub または cas 命令) で実施した後、 排他が獲得できなかった場合の処理を C 実装で実施します。
例えば、 usr/src/uts/sparc/v9/ml/lock_prim.s での mutex_enter() 実装は、 排他可否を判定した後に mutex_vector_enter() (usr/src/uts/common/os/mutex.c) に制御遷移する。
mutex_enter()
mutex_vector_enter()
ENTRY(mutex_enter) mov THREAD_REG, %o1 casx [%o0], %g0, %o1 ! try to acquire as adaptive brnz,pn %o1, 1f ! locked or wrong type membar #LoadLoad ※ 詳細後述 .mutex_enter_lockstat_patch_point: retl nop 1: sethi %hi(mutex_vector_enter), %o2 ! load up for jump to C jmp %o2 + %lo(mutex_vector_enter) nop SET_SIZE(mutex_enter)
x86 向け実装は、 usr/src/uts/intel/ia32/ml/lock_prim.s を参照 (AMD64 実装兼用)。
[17.3/10]@p.xxx
もう一つのハードウェア固有の配慮は、 実行中のプロセッサから、排他状況の変化が常に参照できる、 という点です。 マルチプロセッサシステムにおいて、 メモリ上のデータに対する一貫したビューを提供する場合、 この配慮は極めて重要です。 あるスレッドが test-and-set 命令により排他を獲得した場合、 当該排他のメモリ領域から読み出しを行う他のスレッドは、 test-and-set (あるいはそれ以降) における書き込み結果が、 読み出せなくてはなりません。 最新の排他状況は、 システムワイドに可視化されている必要があります。
[17.3/11]@p.xxx 〜 [17.3/12]@p.xxx
今時のプロセッサは、 命令パイプラインの空隙や、 データの読み出し/書き込み待ちを回避するため、 ハードウェアキャッシュ以外にも、 「load/store バッファ」のようなものを実装しています。
図 17.3 は、 今時のハイエンドプロセッサにおける、 物理メモリとプロセッサの実行ユニット間の、 階層的なデータの流れの典型例を表したものです。
[17.3/13]@p.xxx
あるプロセッサ上での load 処理は、 当該データが load/store バッファ上にある場合、 そのデータを読み込みます。 各プロセッサの load/store バッファは、 当該バッファの属するプロセッサ上からしか見えません。 あるプロセッサが、 load/store バッファへの書き込みをキャッシュ/物理メモリに書き出す前に、 他のプロセッサが当該メモリ領域の読み出しを行うかもしれません。 SMP システムでは、 キャッシュや物理メモリの一貫性が、 ハードウェアのバスプロトコルによって保証されています。 また多くの場合、キャッシュは write-through で実装されているので、 キャッシュへの書き込みはメモリの更新を意味します。 しかし load/store バッファは、 キャッシュとは別物で、 よりプロセッサの実行ユニット寄りに位置しています (= バスプロトコルによる一貫性保証の対象外)。
"Atomic SPARC: Using the SPARC Atomic Instructions" では、 図 17.3 + 後述するメモリモデル/MEMBAR 絡みの話がまとまっている。
[17.3/14]@p.xxx
プロセッサの「メモリモデル」は、 load/store の順序性に関する制約を定義します。 load/store バッファは、メモリモデルの下で実装されます。 load/store 命令の実行順序と、 メモリへの load/store 実施順序が同一になる、 sequential consistency ("strong consistency" あるいは "strong ordering" とも) モデルは、 メモリ内容の一貫性の点では利点がありますが、 キャッシュ/物理メモリへのアクセスを最適化する余地がない、 という欠点を持ちます。 現行の SPARC プロセッサは、 Total Store Ordering (TSO) モデルを実装しています。
[17.3/15]@p.xxx 〜 [17.3/17]@p.xxx
SPARC V9 仕様書では、 TSO における "Atomic load-stores" に関する記述が微妙に異なる。
ちなみに、 "be ordered with ..." に対する "be blocking with ..." の有無は重要なのか?
[17.3/18]@p.xxx
TSO モデルは、 sequential consistency モデルよりも制約が緩いものの、 RMO (Relaxed Memory Order) や PSO (Partial Store Order) といった SPARC アーキテクチャ仕様で定義されている他のモデルよりは、 制約が厳しいモデルです。 但し、 Solaris カーネルは RMO や PSO をサポートしませんし、 今日 Sun は RMO や PSO を実装したシステムを出荷していません。
TSO/PSO においては必ず保証されている筈の "Loads are blocking and ordered with respect to earlier loads" を担保する membar #LoadLoad が、 現行コードの随所で実行されているのは、 RMO のカーネルサポートも試みられていたからか?
membar #LoadLoad
例えば、SPARC 向けの gethrestime_lasttick() では、 "rely on load dependencies to effect the membar #LoadLoad" しないために、 排他情報確認の際に明示的に membar #LoadLoad を実行している。 先述した mutex_enter() のコードでも、 membar #LoadLoad を明示的に実施。
gethrestime_lasttick()
考察の続き
membar_consumer(3C) の実装では、 Spitfier MMU Errata への対処として、 遅延スロット外で membar #LoadLoad を発行している。
membar_consumer(3C)
/* * Spitfires and Blackbirds have a problem with membars in the * delay slot (SF_ERRATA_51). For safety's sake, we assume * that the whole world needs the workaround. */ : : ENTRY(membar_consumer) membar #LoadLoad retl nop SET_SIZE(membar_consumer)
カーネルコード中での membar_consumer() = membar #LoadLoad 実行の例:
membar_consumer()
/* Retrieve the operations vector for a vfs */ vfsops_t * vfs_getops(vfs_t *vfsp) { vfsops_t *op; ASSERT(vfsp != NULL); op = vfsp->vfs_op; membar_consumer(); if (vfsp->vfs_femhead == NULL && op == vfsp->vfs_op) { return (op); : :
例えば、 PSO (Partial Store Order) や RMO (Relaxed Memory Order) では、 以下のようなマルチプロセッサ上での命令列実行において、 (1) ⇒ (2) ⇒ (3) ⇒ (4) ⇒ (5) ⇒ (0) のような実行の可能性がある。
Processor 1: (0) st #1,[A] (1) st #1,[B] Processor 2: (2) ld [B],%r1 (3) st %r1,[C] Processor 3: (4) ld [C],%r1 (5) ld [A],%r2
TSO の場合は、 "Stores are ordered with respect to stores" 制約が有効であるため、 (0) ⇒ (1) の順序性が保証される。
[17.3/19]@p.xxx 〜 [17.3/21]@p.xxx
今日のプロセッサでは、 可能な限りパイプラインを埋めることによる性能向上のために、 与えられた命令列の順序を入れ替える場合があります。 そのため、 「実行中のプロセッサから、排他状況の変化が常に参照」するための、 ハードウェア固有の配慮は、 命令実行順序の制御にも適用されます。
本節で言及したハードウェア固有の配慮に関して、 表 17.1 にまとめます。
load/store バッファ、 制約の緩いメモリモデル、 排他のための test-and-set 機能等々に由来する、 メモリビューの一貫性に関する諸問題は、 プロセッサの命令セットレベルで取り上げられるものです。 Solaris における mutex lock や reader/writer lock の実装は、 アーキテクチャ依存処理の一部として、 UltraSPARC 上でなら ldstub や cas 命令、 x86 上でなら cmpxchgl 命令で実現されます。
[17.3/22]@p.xxx 〜 [17.3/23]@p.xxx
SPARC プロセッサは、 実施前後の load/store 命令のメモリアクセス順序を制約するための、 membar 命令を提供しています。 Solaris カーネルでは、 排他処理が実施された際のメモリビューの一貫性を保つために、 排他情報が更新された際に適宜 membar 命令を実行します。
メモリ操作命令の順序入れ替えは、 アクセス遅延の低減や、 インターコネクトのバンド幅の有効活用など、 メモリ操作の最適化の余地が増えるため、 sequential consistency と比較して、 制約の緩いメモリモデルに移行すればするほど、 潜在的な性能向上の可能性は高くなります。 しかし、 この性能向上は一貫性との引き換えになります。 より緩い制約のメモリモデル向けに、 プロセッサは一貫性を確保するための membar 相当の命令を提供します。 membar 相当命令の詳細は、 技術的に高度で、且つ分量のある話題ですので、 興味のある方は別途 [4] "Multiprocessor System Architectures" (Catanzaro/1994) や [27]"UNIX Systems for Modern Architectures" (Schimmel/1994) を参照してください。
[17.4/1]@p.xxx 〜 [17.4/2]@p.xxx
Solaris カーネルは、 共有データへのアクセスで同期を取るために、 数種類の同期オブジェクトを実装しています。 最も一般的な同期オブジェクトは、 相互排他 (mutual exclusion) または mutex と呼ばれるものですが、 複数の読み出しと単一の書き込みを許容する Reader/Writer ロック (rwlock)、 有限個の資源へのアクセスを制御するセマフォ (semaphore)、 ディスパッチ処理で使用される特別な mutex である dispatcher lock 等も提供されています。
それ自身は排他機能ではありませんが、 スレッドの同期に使用される状態変数 (Condition Variable) は、 カーネルにおける sleep/wakeup 機構の一部です。
[17.4/3]@p.xxx
Solaris では、 同期オブジェクトは稼働状況に応じて動的に生成されるため、 実行中のある時点で存在する同期オブジェクトの実数は、 動的に変化します。 排他オブジェクトは、 カーネル資源に対応するデータ構造にも埋め込まれているので、 スレッド/プロセスの生成、 ファイルシステムのマウント、 ファイルの生成/アクセス、 ネットワーク接続の確立等々、 カーネル資源の生成に比例して、 同期オブジェクトも動的に生成されます。
proc_t なら、 p_crlock, p_maplockw, p_pflock, p_ldtlock (x86 限定), p_lcp_lock, p_sc_lock, p_splock の 7 個、 vnode_t なら、 v_lock と v_vsd_lock の 2 個といったように、 1つの資源でも複数の mutex を持つ。
proc_t
p_crlock
p_maplockw
p_pflock
p_ldtlock
p_lcp_lock
p_sc_lock
p_splock
vnode_t
v_lock
v_vsd_lock
[17.4/4]@p.xxx
カーネル規模に応じた同期オブジェクトの動的生成は、 Solaris カーネルの強靭さの肝の1つです。 小規模システムとして稼働する際に、 使用されることのない同期オブジェクトの生成/管理のために、 時間やメモリ容量を無駄に消費することもなければ、 大規模システムとして稼働する際に、 並行性が損なわれることで、 性能がスケールしなくなることもありません。
同期オブジェクトの静的生成は、 コード上で定義された同期オブジェクトが常に生成されることから、 システム稼働の規模の大小に関わりなく、 常に同数の同期オブジェクトが生成されることになる。
そのため、 小規模システムの場合は、 「おそらく使用されないであろう同期オブジェクト」に対しても、 初期化処理や管理オーバヘッドが発生する。
[17.4.1/1]@p.xxx
排他獲得時に想定される状態には、 (1) 獲得可能 (free/available) と (2) 獲得不可 (not free/owned/held) の2種類があります。 排他が獲得可能であれば、 当該スレッドは所有権を獲得し、 排他が獲得不可であれば、 獲得可能になるまで待ち状態になります (Solaris カーネルにおける厳密な実行内容は後述)。 カーネルは、 排他待ちのスレッドのために、 turnstile (改札口) と呼ばれる待ちキュー機能を提供します。
[17.4.1/2]@p.xxx
排他によって保護された共有資源への操作が完了したなら、 スレッドは排他を解放するのですが、 その際に想定される状態は、 (1) 排他待ちスレッド (a.k.a. "waiter") がある、 (2) 待ちスレッドがない、の二種類です。 後者の場合は、単純に排他解放処理を実施しますが、 後者の場合、 Solaris カーネルでは (a) 全ての待ちスレッドを実行状態にする (= 通常は、最初に実行されたスレッドが排他を獲得)、 (b) 待ち時間の長さ/優先度等を元に、 turnstile (= 待ちキュー) から選択したスレッドのみを実行状態にする、 (c) 特定のスレッドに対して排他の所有権を譲り渡す、 という選択肢があります。
(2-c) の形態は、 おそらく door IPC における shuttle 形式のことと思われる。
[17.4.1/3]@p.xxx
効率向上、 コードフットプリント削減による高速化、 アセンブラ記述によるホットパス (hot path) の最適化、 広範な分析に基づいた最善の排他解放アルゴリズム等々、 排他の実装に盛り込まれたエンジニアリング的努力の結果に関しては、 後述します。
[17.4.2/1]@p.xxx 〜 [17.4.2/2]@p.xxx
Solaris カーネルにおける同期オブジェクトは、 sobj_ops_t を用いた関数テーブルが、 必ず定義されていて、 排他獲得待ちスレッドからリンクされます。
sobj_ops_t
sobj_ops_t は、 同期オブジェクトの型識別としても使用されます。
sobj_ops_t 構造体の確保ベースで見た場合、 Solaris カーネルの同期オブジェクトは、 以下のいずれかに分類される。 MDB 向けの表示情報定義 (usr/src/cmd/mdb/common/modules/genunix/sobj.c) も参照。
[17.4.2/3]@p.xxx 〜 [17.4.2/7]@p.xxx
sobj_ops_t 構造体が保持する以下の3つの関数は、 対応する同期オブジェクトへの待ちにより、 休止状態にあるカーネルスレッドのために呼ばれます。
owner()
unsleep()
change_pri()
各関数がどのように呼ばれるのかは、後述します。
[17.4.2/8]@p.xxx
Soalris カーネルにおける排他機能に対する研究は、 設計トレードオフの好例です。 性能最適性が求められる領域では、 簡素性は性能のために生贄にされます。 排他処理の多くは、 可読性が高い代わりに性能で劣る C 言語実装でなく、 アセンブラで実装されています。 その一方で、 性能要件が深刻でない領域では、 読み辛いアセンブラ実装や、 複雑なアルゴリズムを避けて、 C 言語による簡素な実装を採用しています。 網羅的な試験を通して、 最適な設計を選択しています。
[17.5/1]@p.xxx
相互排他 ("mutual exclusion" or "mutex") は、 読み書きの際に保護が必要な重要なデータ領域への操作を、 直列化するために使用される、 最も一般的な同期機構です。 排他を保持しているスレッド (owner) は、 保護対象に対する操作が終わり次第排他を解放し、 同じ保護対象へのアクセスを行う他のスレッドにより、 排他が獲得されます。
"critical data" と言えば "critical section"。 "critical section" と言えば Windows の XxxxCriticalSection() API (笑)
XxxxCriticalSection()
なぜ XxxxMutex API とは別に定義されているのか、 最初は理由がわからなかったけど、 プロセスローカル排他なら XxxxCriticalSection() API、 プロセス横断排他なら XxxxMutex API という使い分けだと知って「面倒臭ぇ〜」と思った記憶が…… (Solaris mutex はプロセスローカル/プロセス横断両方可能)
XxxxMutex
[17.5.1/1]@p.xxx
排他済みの mutex に対して獲得要求を発行した場合、 要求発行元スレッドには、 排他獲得待ちの選択肢として、 「スピン」 (spin) と「ブロック」 (block) の2つがあります。 「スピン」は排他が獲得できるまでループする、というもので、 「ブロック」は排他が解放されるまで待ちキューで休止状態になる (+ 排他解放時に wakeup 通知を行う)、 というものです。
[17.5.1/2]@p.xxx 〜 [17.5.1/3]@p.xxx
「スピン」の長所は、 休止状態への移行/復帰におけるコンテキストスイッチのオーバヘッドがないため、 排他獲得処理が「ブロック」よりも高速な点にあります。 その一方で、 排他獲得までのループ実行は、 有意義な処理を全く行っていないのに CPU を消費するという欠点があります。
「ブロック」の長所は、 排他が獲得できるようになるまでの間、 他のスレッドに CPU を明け渡すことができる点にあります。 その一方で、 待ちスレッドを CPU から切り離し、 他のスレッドを実行可能にするために、 コンテキストスイッチのオーバヘッドを要します。 また、 待ちスレッドが排他を獲得する際には、 スレッドを実行可能状態にした上でコンテキストの切り替え (= 実行中状態にする) が必要なので、 「スピン」と比較して、 排他解放から排他獲得までの間に幾分かの遅延があります。
[17.5.1/4]@p.xxx 〜 [17.5.1/5]@p.xxx
排他の粒度も重要な問題です。 例えば、 カーネルにおいて、 proc_t 構造体をリンクした「プロセス一覧」で、 稼働中プロセスを管理しているとします。 ある proc_t 構造体を操作する際に、 常に「プロセス一覧」を排他するような実装は、 非常に粒度の「粗い」排他であるため、 簡素で、排他実施のオーバヘッドが最小で済みます。 しかし、 一度に一スレッドしか「プロセス一覧」を操作できないため、 システムがスケールしませんし、排他の衝突が多数発生します。
"lock overhead" (= 排他「実施」のオーバヘッド) は少なく済むけど、 排他由来のオーバヘッド (= 排他解放待ちで生じるオーバヘッド) は増えてしまう、 というのが悩ましいところ。
[17.5.1/6]@p.xxx 〜 [17.5.1/7]@p.xxx
より「細かい」粒度での排他は、 例えば個々の proc_t 単位での排他になります。 この場合、 異なる proc_t への操作は並行して実施できますが、 実装は複雑化し、デッドックの可能性や、 排他実施のオーバヘッドが増加します。
Solaris では、カーネル内構造体の排他をスケールさせるために、 可能な範囲で相対的に「細かい」粒度の排他を採用しています。
[17.5.1/8]@p.xxx 〜 [17.5.1/9]@p.xxx
Solaris カーネルでは、排他獲得待ちの際に spin する mutex と、 対象排他の現所有者の状態に応じて挙動を変える adaptive な mutext の、 二種類の mutex を実装しています。 先述したように、spin/block のいずれか一方のみの採用は、 性能やスケーラビリティにおける問題を生じます。
adaptive な mutex は、 対象排他が別スレッドによって既に所有されている場合、 排他所有スレッドがプロセッサ上で実行中ならば spin で、 それ以外 (= 排他所有スレッドが休止中) なら block で、 排他の獲得を待ちます。 mutex の獲得区間は (設計方針上) 非常に短い筈なので、 実行中のスレッドが所有している排他は、 早々に解放されることが見込まれます。 そうであれば、 block に伴うコンテキスト切り替えコストの代わりに、 spin に伴う CPU 時間の消費を受け入れても、 妥当と言えます。
[17.5.1/10]@p.xxx
一方で、休止中のスレッドが排他を所有している場合、 排他が解放されるまでに最低一回のコンテキストスイッチ (= 排他所有スレッドの実行再開) が必要になるので、 排他待ちスレッドの実行を休止させて、 他のスレッドに CPU を明け渡すのは、 理にかなっています。 カーネルは、対象排他の解放時に実行を再開するまで、 block するスレッドを turnstile (= 休止キュー) に繋げます。
[17.5.1/11]@p.xxx
カーネルの dispatcher は、 スレッドの実行制御とコンテキスト切り替えを行うことから、 割り込みを防止するために、 高い Priority Interrupt Level (PIL) で実行されます。 (on SPARC) PIL 11 の dispatcher 実行に割り込める PIL 11 〜 15 割り込みの処理コードは、 コンテキスト切り替えを発生させてはなりません。 adaptive mutex は block = コンテキスト切り替えの可能性があるので、 高位割り込み処理では spin mutex の使用のみを使用しなければなりません。
[17.5.1/12]@p.xxx
コード例は、 保護対象データ構造が mutex を内包しているケースです。 mutex_init() で初期化された mutex は、 保護対象データ構造へのアクセスの都度、 mutex_enter() で獲得、 mutex_enter() で解放されます。 spin/adaptive の種別は、 mutex_init() 時点で指定されます。 adaptive な mutex としての初期化を仮定した場合、 mutex_enter() 時の spin/block 挙動は、 当該 mutex の所有スレッドの状態に依存します。
mutex_init()
例示コードでは、 「spin/adaptive の種別指定」等のための引数指定が省略されている。
[17.5.2/1]@p.xxx 〜 [17.5.2/2]@p.xxx
カーネルは、 adaptive/spin の種別に応じて、 単一の mutex_t 領域内を異なる用途で使用します。 (※ 段落統合)
mutex_t
"128-bit mutex object" は、 "64-bit mutex object" の間違い。 (errata に掲載済み)
[17.5.2/3]@p.xxx
m_owner フィールドには、 排他所有スレッドの kthread_t へのポインタ値の設定をもって、 当該 mutex が獲得済みであることも意味します。 獲得済み mutex に対して獲得要求が発行された際には、 「待ちスレッドあり」を意味する bit 0 が立てられます。
m_owner
kthread_t
ポインタが 4 バイト境界整合なので、 m_owner の waiter 情報は、 「ポインタ値の下位 2 bit は任意に使用可能」な特徴を利用している。
waiter
そういえば、 SPARC V8 の tag 付き 32bit 値って、 V9 の際に 64bit 拡張されなかったことを考えると、 あんまり有用性を見いだせなかったのかなぁ……
[17.5.2/4]@p.xxx 〜 [17.5.2/5]@p.xxx
PIL を上げて割り込みをブロックする spin での待ちループに入る前に、 割り込みレベルの保守が実施されます。 mutex 初期化時の PIL は m_minspl に、 mutex 獲得試行前の PIL は m_oldspl に格納されます。 実際の排他可否を表すビット列は m_spinlock (unsigned char) で保持されます。
m_minspl
m_oldspl
m_spinlock
mutex_init() に MUTEX_DEFAULT が指定された場合、 adaptive/spin 種別は自動判定されますが、 MUTEX_SPIN を明示的に指定することもできます。
MUTEX_DEFAULT
MUTEX_SPIN
引用されている sys/mutex_impl.h ヘッダは、 x86 アーキテクチャ向けのヘッダな模様。 「SPARC 優先」なこれまでの記述方針はどこへ? (笑)
sys/mutex_impl.h ヘッダは、 x86 アーキテクチャ向けのヘッダな模様。 「SPARC 優先」なこれまでの記述方針はどこへ? (笑)
ヘッダは、 x86 アーキテクチャ向けのヘッダな模様。 「SPARC 優先」なこれまでの記述方針はどこへ? (笑)
[17.5.2/6]@p.xxx
デバイスドライバや、 割り込みの発生/対処を行うカーネルモジュールで mutex_init() を呼び出す場合、 呼び出し引数に interrupt block cookie が追加されます (「(呼び出し元で) 追加する必要があります」ですよね?)。 LOCK_LEVEL (10 on SPARC) よりも高位の割り込み処理に相当する interrupb block cookie 指定がある場合、 mutex 種別として spin が、 それ以外の場合は adaptive が選択されます。 spin 種別が選択された場合、 m_dummylock は all-1 (= 0xff) が設定されます (詳細後述)。
LOCK_LEVEL
m_dummylock
[17.5.2/7]@p.xxx 〜 [17.5.2/8]@p.xxx
mutex_enter() は、 "# of adaptive mutex >> # of spin mutex" かつ "排他可能率 >> 排他不能率" という前提の元で、 簡素 (+ 最小) なアセンブラ実装になっています。 この条件に合致しない場合 (= 既に排他が獲得済みか、spint mutex) は、 より詳細な対応を行う mutex_vector_enter() に遷移します。 先述したように、 m_dummylock は all-1 (= 0xff) が設定されているため、 compare-and-swap でのチェックにおいて 「既に排他獲得済み」と「spint mutex」は同じ扱いになります。
既に (adaptive mutex の) 排他が獲得済みか、 spint mutex だった場合は、 mutex_vector_enter() が実行されます。 spin mutex だった場合、 PIL 情報の設定を行った上で、 排他が獲得できるまでループします。
[17.5.2/9]@p.xxx
adaptive mutex の場合、 mpstat (1M) コマンド出力の smtx カラムのために、 cpu_sysinfo.mutex_adenters を増加させた上で、 mutex_enter() 呼び出し時点からの時間経過によって、 排他が獲得可能になっていないか再度確認します (※ mutex による保護区間は短く保たれていることが前提)。 排他が獲得できたなら、そのまま処理を終了します。
cpu_sysinfo.mutex_adenters
cpu_sysinfo.mutex_adenters は、 「per-CPU 統計情報」扱い (CPU_STATS_ADDQ() マクロで加算) なので、 membar による同期等の必要はない。
CPU_STATS_ADDQ()
[17.5.2/10]@p.xxx
未だ排他が獲得できない場合は、 cpu_t 構造体を走査しつつ、 cpu_thread フィールドと、 mutex_impl_t の m_owner を比較して、 排他保有スレッドが実行中か否かを判定します。 合致するエントリがあれば、spin で排他の解放を待ち、 それ以外の場合は現行のカーネルスレッドを turnstile 待ちキューに入れて休止させます。
cpu_t
cpu_thread
mutex_impl_t
m_owner を比較して、 排他保有スレッドが実行中か否かを判定します。 合致するエントリがあれば、spin で排他の解放を待ち、 それ以外の場合は現行のカーネルスレッドを turnstile 待ちキューに入れて休止させます。
を比較して、 排他保有スレッドが実行中か否かを判定します。 合致するエントリがあれば、spin で排他の解放を待ち、 それ以外の場合は現行のカーネルスレッドを turnstile 待ちキューに入れて休止させます。
"looping through the CPU structures and testing the lock m_owner against the cpu_thread field of the CPU strcture" 絡みで以前遭遇したケースでは、 adaptive mutex の待ちチェック処理が殺到することで、 重い処理をしている訳でもないのに、 関連する CPU の稼働率が急上昇する、 といった現象が。
運の悪いことに、 SNMP エージェントによるプロセス死活監視による、 プロセス管理テーブルの全走査的な挙動と重なると、 目も当てられないことに……
基本的に O(1) よりも計算量の多い処理は、 mutex の保護対象にしてはいけない (少なくとも ADAPTIVE を選択してはいけない)。
[17.5.2/11]@p.xxx
mutex_vector_enter() において「待ち」が確定した場合、 対象 mutex に関する tunrstile の引き当てを行い、 mutex の waiters ビットを立てた時点で、 ロックオーナーが実行に戻っていれば、spin での排他解放待ちに移行します。 ロックオーナーが休止中のままなら、 自スレッドを turnstile 待ちキューに投入した上で、 休止状態に移行します。
原文では、 "if yes (= the owner is running), the code releases the (looked up) turnstile" となっているが、 ここでの release は allocate/free 的な意味での release ではく、 lock/release 的な意味での release (詳細は後述)。
[17.5.2/12]@p.xxx 〜 [17.5.2/13]@p.xxx
mutex_vector_enter() の呼び出しは、 排他の獲得か、 対象同期オブジェクトに対応する待ちキューに投入される結果となります。 いずれのケースでも lockstat(1M) 向けの情報領域に統計情報が記録されます (種別/spin 時間 or 休止時間)。
lockstat(1M) は Solaris 2.6 から導入された統計情報表示コマンドで、 kernel 内部での mutex lock や reader/write lock に関する詳細情報を表示します。
現行 lockstat の実処理は、DTrace によって実現されており、 dtrace にオプションを指定するための -x arg[=val] オプションなどが利用可能。
dtrace
-x arg[=val]
但し、 呼び出しスタックトレースの表示など、 lockstat(1M) の後方互換から逸脱する機能を使うのであれば、 直接 DTrace を使った方が簡単。
[17.5.2/14]@p.xxx
実際の処理手順を疑似コードで示します。
XXXXX 以下 17.5.2 節未稿 XXXXXXX
[17.6/1]@p.xxx 〜 [17.6/2]@p.xxx
「複数スレッドによる同時読み出しは許すが書き込みは単独スレッド限定」 といった排他制御には Reader/Writer lock が使用できます。 また、(mutex の想定と比較して) 長時間の排他を必要とするケースでは、 writer lock を使用すべきです。
初期化 (rw_init()), 獲得 (rw_enter()), 解放 (rw_exit()) など、 RW lock は Mutex lock と同等の機構を持ちます。 「排他獲得可能」状況での獲得、 「解放待ち無し」状況での解放といったケースを想定した高速なアセンブラ実装と、 それ以外の状況を処理する C 実装の組み合わで実現されている点も、 Mutex lock と同様です。
rw_init()
rw_enter()
rw_exit()
[17.6.1/1]@p.xxx 〜 [17.6.1/2]@p.xxx
Reader/Writer lock は、 実行環境のデータモデルに応じて、 32bit または 64bit の単一ワードデータ構造で実現されます。
bit 2 (wrlock) の有無によって、 排他獲得済み時の上位ビットの意味が異なります。 wrlock ビットが立っている場合 (= 書き込み排他時)、 上位ビットは排他保持スレッドの kthread_t ポインタ (= owner) が格納されます。 それ以外の場合 (= 読み出し排他時) は、 排他獲得済みスレッド数が格納されます。
書き込み排他では、 下位 3 ビットを独自利用するため、 kthread_t には最低でも 8byte 境界整合が求められるが、 実はデータモデル (ILP32/ILP64) に関わらず、 "Thread structures are 32-byte aligned" (according to thread.h)
[17.6.1/3]@p.xxx 〜 [17.6.1/5]@p.xxx
RW lock の bit 0 は排他獲得待ちスレッドが、 bit 1 は1つ以上の書き込み排他獲得待ちスレッドが存在することを意味します。 想定される最も簡易なケースは以下のいずれかです。
wrwant
[17.6.1/6]@p.xxx
書き込み排他獲得時には (1) bit 2 (wrlock) が立ち、 (2) 上位ビットに排他を獲得したスレッドの kthread_t アドレスが設定されます。 読み出し排他獲得時には、 上位ビットの排他中スレッド数に加算されます。 (a) 書き込み排他中の排他獲得失敗 (Read/Write 両方) や、 (b) 書き込み排他獲得待ち (= 読み出し排他中) による読み出し排他の獲得失敗は、 rw_enter_sleep() を呼び出します。
wrlock
rw_enter_sleep()
[17.6.1/7]@p.xxx
XXXXXXXX 17.6.1 節 #7 段落未稿 XXXXXXXX
[17.6.1/8]@p.xxx 〜 [17.6.1/12]@p.xxx
閑話休題: 想定外のケースでは以下のように処理されます。
cpu_sysinfo
[17.6.1/13]@p.xxx
XXXXXXXX 17.6.1 節 #13 段落未稿 XXXXXXXX
[17.6.1/14]@p.xxx
排他解放時の想定ケースは「排他獲得待ちがない状態」で、 書き込み排他の解放なら bit 2 (wrlock) がクリアされ、 読み出し排他の解放なら上位ビットの「排他獲得済みスレッド数」が減算されます。 想定外のケースでは、以下のように処理されます。
[17.6.1/15]@p.xxx 〜 [17.6.1/17]@p.xxx
mutex との大きな違いの1つが、 この "direct transfer of ownership of the lock" 。
mutex のような「スケジューラ任せ」での次排他獲得は、 (1) 「書き込み優先」方針が保証されない、 (2) 休止解除〜再休止のオーバーヘッドが大きい、 といった問題点が容易に想像されるので、
原文での説明の列挙順序が、待ちの (1) ある場合、 (2) ない場合、 (3) ある場合の順序なのは、ちょっと読み辛い……
[17.6.1/18]@p.xxx 〜 [17.6.1/23]@p.xxx
排他周りの残りの処理は以下の通り:
turnstile_wakeup()
上記の「書き出し優先だが、読み込みに対しても良心的」な方針は、 Solaris 2.6 から導入されました。
XXXXXX 17.7 の節概容未稿 XXXXXXX
[17.7.1/1]@p.xxx 〜 [17.7.1/2]@p.xxx
排他獲得待ちの際の turnstile_t 領域は、 システムワイドの turnstile_table 配列による、 ハッシュテーブルで管理されます。 turnstile_table 配列の各エントリは、 片方向 turnstile_t リンクの先頭を指し、 配列添え字には同期オブジェクト (synchronized object: mutex や rwlock) アドレスのハッシュ値が使用されます。
turnstile_t
turnstile_table
turnstile_table 配列要素は、 個別の排他オブジェクト (disp_lock_t) を持っているので、 ハッシュ値違いの同期オブジェクトに関する操作は、 並行して実施できます。 turnstile_t 自身は、以下のようなフィールドを持ちます。
ts_next
ts_free
ts_waiters
ts_sobj
ts_inheritor
ts_sleepq
[17.7.1/3]@p.xxx
thread_create() によるカーネルスレッド生成の際に、 kthread_t と turnstile_t 領域が対で確保され、 kthread_t.t_ts フィールドで turnstile_t が参照されます。
thread_create()
kthread_t.t_ts
kthread_t と turnstile_t が分離されていることに対する usr/src/uts/common/disp/thread.c 中のコメント:
/* * Every thread keeps a turnstile around in case it needs to block. * The only reason the turnstile is not simply part of the thread * structure is that we may have to break the association whenever * more than one thread blocks on a given synchronization object. * From a memory-management standpoint, turnstiles are like the * "attached mblks" that hang off dblks in the streams allocator. */
[17.7.1/4]@p.xxx 〜 [17.7.1/6]@p.xxx
※ 記述簡略化のため段落横断で処理手順を列挙
turnstile_lookup()
turnstile_chain_t.tc_lock
turnstile_block()
turnstile_t.ts_free
[17.7.1/7]@p.xxx 〜 [17.7.1/9]@p.xxx
CL_SLEEP
kthread_t.t_clfuncs->cl_sleep
kthread_t.t_wchan
kthread_t.t_sobj_ops
turnstile_t.ts_waiters
turnstile_t.ts_sleepq
sleepq_insert()
turnstile_t.ts_inheritor
kthread_t.t_prioinv
turnstile_t.ts_prioinv
swtch()
[17.7.1/10]@p.xxx
※ 記述簡略化のため処理手順を列挙
[17.8/1]@p.xxx 〜 [17.8/3]@p.xxx
semaphore は、複数のプロセス/スレッド間で、 有限個数の資源を共有する際の排他機能を提供します。
カウンタの観点で semaphore を見た場合、 資源数で初期化され、 資源利用前にカウンタを減算 (= P operation)、 資源利用後にカウンタが加算 (= V operation) されます。 カウンタ値 0 は「利用可能資源なし」を意味し、 他のプロセス/スレッドによる資源解放までは処理がブロックされます。
Solaris カーネルの場合、 mutex や RW lock 程には排他制約がきつくないケースで semaphore が使用されています。
[17.8/4]@p.xxx 〜 [17.8/6]@p.xxx
カーネル semaphore ksema_t (※ 実態は sema_impl_t) では、 待ちスレッドを管理する単方向リスト (s_slpq) と、 カウンタ (s_count) が管理されています。
ksema_t
sema_impl_t
s_slpq
s_count
カーネル semaphore には、 初期化処理 (sema_init())、 終了処理 (sema_destroy())、 増減操作 (sema_p()/esma_v())、 その他いくつかのユーティリティが提供されています。
sema_init()
sema_destroy()
sema_p()
esma_v()
sema_init(), sema_destory() 共に、 指定 ksema_t 領域内の初期化/クリアのみの実行で、 ksema_t 領域を確保/解放する責務は負っていません。 この振る舞いのおかげで、 他の構造体内部に埋め込まれた ksema_t 領域に対する初期化/終了処理も実施可能です (e.g. block I/O 用 buf_t は2つの sempahore を持つ)。
sema_destory()
buf_t
[17.8/7]@p.xxx
semaphore のカウンタが 0 の時に、 sema_p() が実行された場合、 システム共有資源から sleep queue が割り当てられ、 休止状態にされたスレッドが sleep queue に投入されます。 mutex/RW lock では turnstile による休止管理を行いますが、 それ以外の同期オブジェクト (semaphore 含む) は sleep queue によって休止を管理します。
[17.8/8]@p.xxx 〜 [17.8/10]@p.xxx
※ この段落での言及は大部分が 3.10.2 Sleep Queues からの引用。 しかも以下のような問題がある。
sleepq_heads
ksema_t.s_slpq
kthread_t.t_link
t_priforw
kthread_t.t_priback
sleepq_head
sema_p() 実装 (usr/src/uts/common/os/semaphore.c)
s = (sema_impl_t *)sp; /* cast from "ksema_t *sp" */ sqlp = &SQHASH(s)->sq_lock; /* address of "indexed sleepq entry" */ disp_lock_enter(sqlp); /* 簡易ロック */ while (s->s_count == 0) { thread_lock_high(curthread); SEMA_BLOCK(s, sqlp); { /* SEMA_BLOCK() での待ちリスト操作は以下の通り */ cpri = DISP_PRIO(curthread); tpp = &s->s_slpq; while ((tp = *tpp) != NULL) { if (cpri > DISP_PRIO(tp)) break; /* 自スレッドよりも優先度が低いものを検出 */ tpp = &tp->t_link; } *tpp = curthread; /* 自スレッドをリストに挿入 */ curthread->t_link = tp; } thread_unlock_nopreempt(curthread); swtch(); disp_lock_enter(sqlp); } s->s_count--; disp_lock_exit(sqlp);
※ sempahore の話は一旦置いておいて sleep queue の話
sleepq_heads でのハッシュ算出周りの実装を見るに、 同一ハッシュ値の同期オブジェクトに対する待ちスレッドが、 単一のリスト構造に乗り合わせている模様。 つまり、 t_link によるリスト中には、 異なる同期オブジェクトに対する待ち合わせスレッドが混在していることになる。
t_link
現状だと sleepq_heads は condition variable のみで使用される限定的なものなので、 「同一ハッシュ値で複数の condition variable が衝突するケースは稀」 という判断なのかな?
[17.8/11]@p.xxx 〜 [17.8/13]@p.xxx
スケジューリング設定に応じた休止処理 〜 スレッドの状態を休止 (TS_SLEEP) 状態化 〜 kthread_t.t_wchan/kthread_t.t_sobj_ops 設定を経て、 スレッドが休止キューに投入されます。
semaphore は sema_v() で解放されます。 カウンタを 1 増加させた上で、 解放待ちで休止しているスレッドがあれば、 最も長く待ち状態にあるスレッドを起こします。 semaphore は一度に1スレッドのみを起こします。
sema_v()
semaphore は相対的に少数の対象の管理に使用されています: 例えば、 buffer I/O (bio) や動的ロード可能カーネルモジュール、 デバイスドライブ等々。
※ 実行デモメインで進めるので省略