Linux での同期方式の徹底調査

カーネルのアトミック、スピンロック、そしてミューテックスについて

読者のみなさんは Linux® の教育を受けるなかで並行性やクリティカル・セクション、そしてロックについて学んだことと思いますが、これらの概念をカーネル内でどのように使っていますか? この記事ではアトミック演算子、スピンロック、リーダー/ライター・ロック、カーネルのセマフォーを含め、2.6 カーネルで使用できる数々のロック機構について概要を説明します。さらに、安全かつ効率的なカーネルのコードを作成する上で、どこにそれぞれの機構を適用するのが最もふさわしいかを探ります。

M. Tim Jones (mtj@mtjones.com), Consultant Engineer, Emulex

M. Tim JonesM. Tim Jones は組み込みソフトウェアのエンジニアであり、『GNU/Linux Application Programming』や『AI Application Programming』(現在、第 2 版)、それに『BSD Sockets Programming from a Multilanguage Perspective』などの著者でもあります。技術的な経歴は静止軌道衛星用のカーネル開発から、組み込みシステム・アーキテクチャーやネットワーク・プロトコル開発まで、広範にわたっています。また、コロラド州ロングモン所在のEmulex Corp. の顧問エンジニアでもあります。


developerWorks 貢献著者レベル

2007年 10月 31日

この記事では、Linux カーネルで使用できる数々の同期 (ロック) 機構について検討します。ここでは 2.6.23 カーネルから利用可能になった方式の多くを対象としたアプリケーション・プログラム・インターフェース (API) を紹介しますが、API の詳細を掘り下げる前に、解決対象とする問題を理解しておく必要があります。

並行性とロック

同期方式が必要になるのは、並行性という特性が存在する場合です。並行性が存在するとは、2 つ以上のプロセスが同時期に実行され、これらのプロセス間で相互作用が行われる可能性がある場合 (同じリソースのセットを共有するなど) を意味します。

複数のスレッドが同じ CPU を共有し、プリエンプションによって競合条件が発生するユニプロセッサー (UP) ホストでは並行性が生まれます。プリエンプションとは、あるスレッドを実行できるように他のスレッドを一時的に休止させることによって CPU をユーザーに意識させずに共有することです。競合条件が発生するのは、複数のスレッドが 1 つの共有データ項目を操作する場合で、スレッドの実行タイミングによってその結果は変わってきます。一方、マルチプロセッサー (MP) マシンにも並行性は存在し、各プロセッサーで同時に実行されるスレッドが同じデータを共有します。しかし MP の場合にはスレッドが同時に実行されるため、そこには真の並列性があります。UP の場合、並列性はプリエンプションによって実現されるものです。いずれのモードにしても、並行性には難題が伴います。

Linux カーネルは MP と UP 両方の並行性をサポートします。カーネル自体が動的なため、競合条件はさまざまな形で発生する可能性があります。Linux カーネルはさらに、対称型マルチプロセッシング (SMP) として知られるマルチプロセッシングもサポートします。SMP についての詳細は、記事の終わりにある「参考文献」セクションを参照してください。

競合条件の問題に対処するために生み出されたのが、クリティカル・セクションという概念です。クリティカル・セクションは複数からのアクセスに対して保護されたコードの一部で、このコード部分では共有データや共有サービス (ハードウェア周辺装置など) を操作することができます。クリティカル・セクションは排他制御の原則に基づいて動作するためです (スレッドがクリティカル・セクションに入っている間は、それ以外のすべてのスレッドはクリティカル・セクションに入ることができません)。

クリティカル・セクション内で生じる問題は、デッドロック状態です。例えば、互いに異なるリソースを保護する 2 つのクリティカル・セクションがあり、それぞれのリソースにロックを使用できるとします (この例ではロック A、ロック B と呼びます)。ここで、これらのリソースにアクセスする必要がある 2 つのスレッドについて考えてみてください。スレッド X はロック A を取得し、スレッド Y はロック B を取得します。両方のスレッドがロックを保持している間に、それぞれがもう一方のスレッドが保持するロックを獲得しようと試みたとしたらどうなるでしょう (つまり、スレッド X はロック B を、スレッド Y はロック A を獲得しようとするということです)。この場合、どちらのスレッドにとっても必要とするリソースがもう一方のスレッドで確保されているため、2 つのスレッドはデッドロック状態となってしまいます。デッドロックに対する 1 つの単純なソリューションは、スレッドを完了させられるように常に同じ順序でロックを取得することです。これ以外のソリューションには、デッドロック状態の検出が必要となります。表 1 に、この記事で使用する並行性に関する重要な用語の定義を記載します。

表 1. 並行性に関する重要な定義
用語定義
競合条件複数のスレッドがリソースを同時に操作することにより、一貫性のない結果が生じる状態
クリティカル・セクション共有リソースへのアクセスを調整するコード・セグメント
排他制御共有リソースへの排他的アクセスを確実にするソフトウェア特性
デッドロック複数のプロセスと複数のリソース・ロックが原因でプロセスが生産性の高い処理を行えなくなる特殊な状態

Linux の同期方式

多少の理論と解決対象の問題を理解できたところで、Linux が並行性と排他制御をサポートするさまざまな方法に目を向けてみましょう。排他制御を実現するために初期の頃に使われていたのは、割り込みを無効にするという方法でしたが、このような形式でのロックは (カーネル内でロックをトレースできるとしても) 非効率的です。さらに、この方法は拡張性に乏しく、他のプロセッサーでの排他制御は保証しません。

以降のロック機構についての検討で最初に説明するのは、単純な変数 (カウンターおよびビットマスク) を保護するアトミック演算子です。次に、SMP アーキテクチャーの場合に効率的なビジー・ウェイトによるロックとして、単純なスピンロックとリーダー/ライター・スピンロックを取り上げます。そして最後に、アトミック API をベースにビルドされたカーネルのミューテックスについて検討します。


アトミック操作

Linux カーネルでの最も単純な同期手段はアトミック操作です。アトミックとは、API 関数のなかにクリティカル・セクションが含まれていることを意味します。この場合、呼び出し自体にロックが備わることになるため、ロックは必要ありません。C 言語ではアトミック操作を保証できないことから、Linux は基礎となるアーキテクチャーに依存してアトミック操作を提供します。アーキテクチャーはそれぞれ大幅に異なるため、アトミック関数の実装もさまざまです。ほぼ完全にアセンブリー言語で提供されるものもあれば、C 言語を用いて local_irq_save および local_irq_restore で割り込みを無効にするものもあります。

以前のロック方式

カーネルにロックを実装する方法として、ローカル CPU のハード割り込みを無効にするのは間違いです。割り込みを無効にする local_irq_save ルーチン、そして前に有効だった割り込みをリストアする local_irq_restore ルーチンがあり、実際に使用されてもいますが (アトミック演算子が使用することもあります)、これらの関数は推奨されません。この 2 つのルーチンはリエントラントであるため、互いのコンテキスト内で呼び出される可能性があります。

アトミック演算子は、保護する必要のあるデータが例えばカウンターのように単純な場合に最適です。アトミック API は単純でありながらも、さまざまな状況に使用できる数多くの演算子があります。ここで、この API を使用する例を紹介しましょう。

アトミック変数を宣言する方法は、ただ単に atomic_t 型の変数を宣言するだけです。この構造体には、単一の int 要素が含まれます。宣言したアトミック変数は、ATOMIC_INIT シンボリック定数を使って確実に初期化してください。リスト 1 の場合、アトミック・カウンターはゼロに設定されます。アトミック変数は実行時に atomic_set 関数を使って初期化することもできます。

リスト 1. アトミック変数の作成と初期化
atomic_t my_counter ATOMIC_INIT(0);

... or ...

atomic_set( &my_counter, 0 );

アトミック API はさまざまな使用状況を網羅する一連の豊富な関数をサポートします。例えば、atomic_read でアトミック変数の内容を読み取ったり、atomic_add で変数に特定の値を加算したりすることもできます。変数を単純にインクリメントするというもっとも一般的な操作は、atomic_inc で行います。さらに、加算操作とインクリメント操作の逆を行う減算演算子もあります。リスト 2 に、これらの関数の使用例を記載します。

リスト 2. 単純計算を行うアトミック関数
val = atomic_read( &my_counter );

atomic_add( 1, &my_counter );

atomic_inc( &my_counter );

atomic_sub( 1, &my_counter );

atomic_dec( &my_counter );

アトミック API は他にも一般的な使用状況を多数サポートします。その一例は、演算兼テスト・ルーチンです。このルーチンでは、アトミック変数を操作した後にテストすることができます (すべてが 1 つのアトミック操作として実行されます)。atomic_add_negative は特殊な関数で、この関数でアトミック変数に加算すると、その結果が負の値である場合には true が返されます。この関数は、アーキテクチャーに依存するセマフォー関数の一部がカーネル内で使用します。

以下の関数の多くは変数の値を返しませんが、atomic_add_returnatomic_sub_return については別です。この 2 つの関数は、演算後に結果の値を返します (リスト 3 を参照)。

リスト 3. 演算兼テストを行うアトミック関数
if (atomic_sub_and_test( 1, &my_counter )) {
  // my_counter is zero
}

if (atomic_dec_and_test( &my_counter )) {
  // my_counter is zero
}

if (atomic_inc_and_test( &my_counter )) {
  // my_counter is zero
}

if (atomic_add_negative( 1, &my_counter )) {
  // my_counter is less than zero
}

val = atomic_add_return( 1, &my_counter ));

val = atomic_sub_return( 1, &my_counter ));

使用しているアーキテクチャーが 64 ビット長の型 (BITS_PER_LONG が 64 ) をサポートする場合は、long_t atomic 操作を使用することができます。使用可能な long 型の操作については、linux/include/asm-generic/atomic.h を参照してください。

アトミック API にはビットマスク操作のサポートも備わっているため、前述の算術演算の他、セット演算およびクリア演算もあります。これらのアトミック操作は、SCSI をはじめとする多くのドライバーが使用します。ビットマスクのアトミック操作で使用できるのは 2 つの操作 (マスクのセットとマスクのクリア) のみです。そのため算術演算とは多少使い方が異なり、指定するのは値、そして操作の実行対象とするビットマスクとなります (リスト 4 を参照)。

リスト 4. ビットマスクのアトミック関数
unsigned long my_bitmask;

atomic_clear_mask( 0, &my_bitmask );

atomic_set_mask( (1<<24), &my_bitmask );

アトミック API のプロトタイプ

アトミック操作の実装はアーキテクチャーに依存します。アーキテクチャーごとの実装については、./linux/include/asm-<arch>/atomic.h を参照してください。

スピンロック

スピンロックは、ビジー・ウェイトによるロックを使って排他制御を保証する特殊な手法です。スレッドはロックが使用可能であればロックを取得し、排他制御アクションを行ってからロックを解放します。ロックが使用できない場合は、ロックが使用可能になるまでスレッドがビジー・ウェイト状態になります。ビジー・ウェイト状態は非効率的なように思えるかもしれませんが、実際には、スレッドをスリープ状態にしてロックが使用可能になった時点でウェイクアップさせるよりも時間を短縮することができます。

スピンロックは実のところ SMP システムでしか役に立ちませんが、最終的にはコードは SMP システムで実行されることになるので、スピンロックを UP システムに追加するのは正しいことです。

スピンロックには、フル・ロックとリーダー/ライター・ロックという 2 つのタイプがあります。まずはフル・ロックのほうから説明します。

最初に単純な宣言で新しいスピンロックを作成します。このスピンロックはその場で初期化するのでも、spin_lock_init を呼び出して初期化するのでも構いません。リスト 5 のどのバージョンを使っても同じ結果が得られます。

リスト 5. スピンロックの作成と初期化
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;

... or ...

DEFINE_SPINLOCK( my_spinlock );

... or ...

spin_lock_init( &my_spinlock );

スピンロックが定義されると、さまざまなロックのバージョンを使用できるようになります。それぞれのバージョンが、それぞれ異なるコンテキストで役立ちます。

最初のバージョンは、リスト 6 に示す spin_lockspin_unlock です。これは最も単純なバージョンで、割り込みを無効にはしませんが、完全なメモリー・バリアを組み込みます。このバージョンは、割り込みハンドラーとこのロックとの間で相互作用が行われないことを前提とします。

リスト 6. スピンロックの lock および unlock 関数
spin_lock( &my_spinlock );

// critical section

spin_unlock( &my_spinlock );

次に挙げるバージョンは、リスト 7 の irqsaveirqrestore のペアです。spin_lock_irqsave 関数はスピンロックを獲得し、ローカル・プロセッサーでの割り込みを無効にします (SMP の場合)。spin_unlock_irqrestore 関数はスピンロックを解放し、(flags 引数を使用して) 割り込みをリストアする関数です。

リスト 7. ローカル CPU の割り込みを無効にしたスピンロック
spin_lock_irqsave( &my_spinlock, flags );

// critical section

spin_unlock_irqrestore( &my_spinlock, flags );

spin_lock_irq/spin_unlock_irq は、spin_lock_irqsave/spin_unlock_irqrestore を変形したあまり安全ではないバージョンです。このバージョンでは割り込み状態について仮定をするため、使用しないようにしてください。

最後に紹介するのは、カーネルのスレッドがボトムハーフによりデータを共有する場合に使用できるスピンロックのバージョンです。ボトムハーフとは、割り込み処理を据え置き、後でデバイス・ドライバーに処理させるための方法です。このバージョンのスピンロックは、ローカル CPU でのソフト割り込みを無効にします。そのため、softirq、タスクレット、ボトムハーフはローカル CPU で実行されなくなります。このバージョンは、リスト 8 のとおりです。

リスト 8. ボトムハーフを操作するためのスピンロック関数
spin_lock_bh( &my_spinlock );

// critical section

spin_unlock_bh( &my_spinlock );

リーダー/ライター・スピンロック

多くの場合、データへのアクセスはライターよりもリーダーによって指示される回数のほうが上回っています (データへのアクセスは、書き込みよりも読み取りのために行われるほうが多いためです)。このようなモデルをサポートするために作成されたのが、リーダー/ライター・ロックです。このモデルで興味深いのは、複数のリーダーが同時にデータにアクセスすることはできますが、ライターの場合は 1 度に 1 つしかデータにアクセスすることができないという点です。つまり、ライターがロックを確保している場合には、リーダーはクリティカル・セクションに入ることができません。一方、1 つのリーダーだけがロックを確保しているのであれば、他のリーダーもクリティカル・セクションに入ることができます。リスト 9 は、このモデルの例です。

リスト 9. リーダー/ライター・スピンロック関数
rwlock_t my_rwlock;

rwlock_init( &my_rwlock );

write_lock( &my_rwlock );

// critical section -- can read and write

write_unlock( &my_rwlock );


read_lock( &my_rwlock );

// critical section -- can read only

read_unlock( &my_rwlock );

ボトムハーフおよび割り込み要求 (IRQ) を保存するためのリーダー/ライター・スピンロックの形は、ロックが必要な状況に応じても変わってきます。ロックの用途が、実際にはリーダー/ライター・ロックである場合、リーダーとライターを区別しない標準スピンロックではなく上記のスピンロックを使用しなければならないのは明らかです。


カーネルのミューテックス

カーネルでは、セマフォーの振る舞いを実現する手段としてミューテックスを使用することができます。カーネルのミューテックスはアトミック API をベースに実装されていますが、これはカーネルのユーザーには見えません。ミューテックスは単純なものですが、忘れてはならないルールがいくつかあります。それは、1 度に 1 つのタスクしかミューテックスを保持できないこと、そしてそのタスクだけがミューテックスをアンロックできることです。また、ミューテックスの再帰的ロックや再帰的アンロックは不可能なため、ミューテックを割り込みコンテキスト内で使用することはできません。しかしながらミューテックスは現行カーネルのセマフォー・オプションより高速でコンパクトなので、ニーズに合うのであればミューテックスが理想的です。

ミューテックスは、DEFINE_MUTEX マクロを使って 1 回の操作で作成および初期化します。このマクロを使うと、新規ミューテックスが作成され、その構造体が初期化されます。ミューテックスの実装は ./linux/include/linux/mutex.h に記載されているので参照してください。

DEFINE_MUTEX( my_mutex );

ミューテックス API は 5 つの関数を提供します。そのうちの 3 つはロック操作のための関数で、あとの 2 つはそれぞれアンロック操作、ミューテックスのテストを行うための関数です。まずロック関数から説明すると、最初の mutex_trylock はすぐにロックが必要な場合、またはミューテックスが使用できないときに制御を取り戻したい場合に使用します。この関数はリスト 10 のとおりです。

リスト 10. mutex_trylock によるミューテックスの獲得試行
ret = mutex_trylock( &my_mutex );
if (ret != 0) {
  // Got the lock!
} else {
  // Did not get the lock
}

ロックを待機したいという場合には、代わりに mutex_lock を呼び出します。この呼び出しは、ミューテックスが使用可能であればリターンされ、そうでなければミューテックスが使用可能になるまでスリープ状態になります。いずれの場合も、制御が戻ると呼び出し側がミューテックスを保持することになります。3 つ目のロック関数は mutex_lock_interruptible です。この関数は、呼び出し側がスリープ状態になる可能性がある場合に使用します。呼び出し側がスリープ状態になった場合に関数が返すのは -EintR です。リスト 11 に、この 2 つの呼び出しを示します。

リスト 11. スリープ状態になる可能性があるミューテックスのロック
mutex_lock( &my_mutex );

// Lock is now held by the caller.

if (mutex_lock_interruptible( &my_mutex ) != 0)  {

  // Interrupted by a signal, no mutex held

}

ミューテックスがロックされた後はミューテックスをアンロックする必要があります。そのために使用するのは mutex_unlock 関数です。この関数は、割り込みコンテキストからは呼び出すことができません。mutex_is_locked は、ミューテックスのステータスをチェックする際に呼び出します。実際には、この呼び出しはインライン関数にコンパイルされます。ミューテックスが確保 (ロック) されている場合には 1 が返され、そうでなければゼロが返されます。リスト 12 に、この 2 つの関数の使用例を示します。

リスト 12. mutex_is_locked によるミューテックスのテスト
mutex_unlock( &my_mutex );

if (mutex_is_locked( &my_mutex ) == 0) {

  // Mutex is unlocked

}

アトミック API をベースとしているミューテックス API には制約がありますが、それでもこの API は効率的なので、ニーズに合う場合は使用する価値があります。


BKL

最後に、BKL (Big Kernel Lock) について説明しておかなければなりません。カーネルでの BKL の用途は次第に少なくなってきている一方、残りの用途については維持せざるを得ないでしょう。マルチプロセッサーとしての Linux を可能にしたのは BKL ですが、よりきめの細かいロックが BKL の代わりに徐々に使われるようになっています。BKL を行うための関数は、lock_kernel および unlock_kernel です。詳細は、./linux/lib/kernel_lock.c を参照してください。


まとめ

Linux は選択肢という点でスイス・アーミー・ナイフのようになりつつありますが、ロックの手法に関しても同じことが言えます。アトミック・ロックはロック機構としてだけでなく、算術演算とビット単位の操作を同時に実現する手段としても使えます。スピンロックはロック機構 (ほとんどは SMP 用) に加え、リーダー/ライター・スピンロックも提供します。リーダー/ライター・スピンロックで特定のロックを許可できる対象は、リーダーの場合は複数のリーダーに対して、ライターの場合には単一のライターに対してのみとなります。そして比較的新しいロック機構であるミューテックスは、アトミック API をベースとした単純な API を提供します。このように、Linux にはあらゆるニーズに応じてデータを保護するためのロック方式が備わっています。

参考文献

学ぶために

製品や技術を入手するために

  • Linux Kernel Archives で最新の Linux ソースを入手してください。Linux ソース自体が、カーネルの操作に関する情報を入手する近道になります。また、資料サブディレクトリーには (古いものもありますが) 豊富な資料が紹介されています。
  • developerWorks から直接ダウンロードできる IBM トライアル・ソフトウェアを使用して、Linux で次の開発プロジェクトを構築してください。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。プロフィールで選択した情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=272875
ArticleTitle=Linux での同期方式の徹底調査
publish-date=10312007