スピン ロックの実装は正しく最適ですか?

StackOverflow https://stackoverflow.com/questions/1383363

質問

非常に小さな重要なセクションを保護するためにスピン ロックを使用しています。競合が発生する とても ほとんどの場合、通常のミューテックスよりもスピン ロックの方が適切です。

私の現在のコードは次のとおりで、x86 と GCC を前提としています。

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

それで私は疑問に思っています:

  • このコードは正しいですか?相互排除は正しく保証されていますか?
  • すべての x86 オペレーティング システムで動作しますか?
  • x86_64でも動作しますか？すべてのオペレーティング システムで?
  • 最適ですか？
    • コンペアアンドスワップを使用したスピンロックの実装を見てきましたが、どちらが優れているのかわかりません。
    • GCC アトミック組み込みドキュメントによると (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html）もあります __sync_lock_release. 。私はメモリバリアの専門家ではないので、代わりにこれを使用してもよいかどうかわかりません。 __sync_synchronize.
    • 競合がない場合に最適化しています。

私は気にしない まったく 争いについて。他に 1 つ、おそらく 2 つのスレッドが数回に 1 回スピン ロックをロックしようとしている可能性があります。 日々.

役に立ちましたか？

解決

それで私は疑問に思っています:

* Is it correct?

前述の文脈では、私は「はい」と言えます。

* Is it optimal?

それは含蓄のある質問です。車輪を再発明することで、他の実装によって解決された多くの問題も再発明することになります。

  • ロックワードにアクセスしようとしていない場合、失敗すると無駄なループが発生すると予想されます。

  • ロック解除で完全なバリアを使用するには、リリース セマンティクスのみが必要です (そのため、__sync_lock_release を使用して、Itanium では mf の代わりに st1.rel を取得し、powerpc では lwsync を取得します...)。本当に x86 または x86_64 だけを気にするのであれば、ここで使用されるバリアの種類はそれほど重要ではありません (ただし、HP-IPF ポートのために Intel の Itanium にジャンプする必要がある場合は、これは望ましくないでしょう)。

  • 通常廃棄ループの前に置くはずのpause()命令がありません。

  • 望んでいる争いがあるとき 何か, 、セモップ、あるいは絶望的に愚かな眠りさえあります。これで得られるパフォーマンスが本当に必要な場合は、futex の提案がおそらく良いでしょう。パフォーマンスが必要な場合は、これで十分です 維持する このコードについては、多くの研究が必要です。

解放バリアは必要ないというコメントがあったことに注意してください。これは、x86 でも当てはまりません。リリース バリアは、「バリア」の周囲で他のメモリ アクセスをシャッフルしないようにコンパイラへの指示としても機能するからです。使用した場合に得られるものと非常によく似ています アズム ("" :::"メモリ" ）。

* on compare and swap

x86 では、sync_lock_test_and_set は暗黙のロック プレフィックスを持つ xchg 命令にマップされます。間違いなく最もコンパクトな生成コード (特に「ロック ワード」に int の代わりにバイトを使用した場合)、ただし、LOCK CMPXCHG を使用した場合と同じくらい正確です。比較と交換の使用は、より複雑なアルゴリズムに使用できます (失敗時に最初の「待機者」のメタデータへのゼロ以外のポインターをロックワードに入れるなど)。

他のヒント

私には罰金を検索します。ところで、ここでも競合する場合には、より効率的である教科書の実装です。 

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

あなたの質問に答えて:

  1. 私には大丈夫そうに見えます
  2. OS が GCC をサポートしていると仮定します (GCC には機能が実装されています)。これはすべての x86 オペレーティング システムで動作するはずです。GCC のドキュメントには、特定のプラットフォームでサポートされていない場合に警告が生成されることが示唆されています。
  3. ここには x86-64 に特化したものは何もないので、なぜそうしないのかわかりません。これを拡張してカバーすることができます どれでも GCC がサポートするアーキテクチャですが、非 x86 アーキテクチャでこれを実現するより最適な方法がある可能性があります。
  4. を使用すると少し良いかもしれません __sync_lock_release() の中に unlock() 場合;これにより、1 回の操作でロックがデクリメントされ、メモリ バリアが追加されます。ただし、論争がめったにないというあなたの主張を前提とすると、私には良さそうです。
以下のCASの実装はx86_64の上の正しいものである場合は、

私は疑問に思います。 それは私のi7のX920ノートパソコン（フェドーラ13 x86_64版、GCC 4.4.5）にほぼ倍速くなります。

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

は1つの改良は、 TATAS の（テスト・アンド・テストを使用して示唆しています） - および - セット。それが可能な場合は、それらを避けるために、より良いですので、CAS操作を使用すると、プロセッサのための非常に高価と考えられています。 もう一つは、あなたがたとえば、この問題は、最終的によりによって解決されます上のWindows？優先度の高いスレッドが低い優先度の試行でのスレッドがロックを解放する一方でロックを取得しようとするとどのような場合には（優先順位の逆転に苦しむしません作ります優先順位のブーストを使用して、スケジューラは、しかし、あなたは明示的にあなたがあなたの最後の20回の試行でロック獲得に成功しなかった場合には、あなたのスレッドのタイムスライスを放棄することができます（たとえば...）

あなたのロック解除手続きは、メモリバリアを必要としません。除外への割り当てがあればのx86上に整列DWORDよう原子である。

のx86（32/64）の具体的なケースでは、私はあなたがロック解除コード内のすべてのメモリフェンスを必要とは思いません。その店は、ストアバッファにし、それらを他のスレッドのために遅延させることができる見えるようになるので、最初に置かれ以外のx86は、任意の並べ替えを行いません。それはまだメモリにフラッシュされていない場合やストアを行い、その後、同じ変数から読み取ったスレッドは、そのストアバッファから読み込まれます。あなたが必要とするすべてのようにコンパイラreorderingsを防ぐためにasm文です。あなたは、他のスレッドの観点から、わずかに長く必要以上にロックを保持している一つのスレッドのリスクを実行しますが、問題ではないはずの競合を気にしない場合。実際には、pthread_spin_unlockは、私のシステム（Linuxのx86_64版）にそのように実装されています。

私のシステムも実装がpthread_spin_lockを使用しての代わりに、（用途をlock decl lockvar; jne spinloop;ものです）xchgを使用して__sync_lock_test_and_setますが、パフォーマンスの違いが実際にあるかどうかはわかりません。

いくつかの間違った前提があります。

まず、スピンロックがressourceが他のCPUにロックされている場合にのみ意味があります。 ressourceは（常にユニプロセッサ・システム上のケースである）同じCPU上でロックされている場合は、注文のロック解除ressourceにスケジューラを緩和する必要があります。あなたは、現在のコードは、スケジューラがautomaticalyタスクを切り替えますので、ユニプロセッサシステム上で動作しますが、それressourceの無駄ます。

マルチプロセッサシステムで、同じ事缶happendsが、タスクは別のCPUから移動してもよいです。要するに、スピンロックの使用は、あなたのタスクは、異なるCPU上で実行されることをgarantee場合は、正しいです。

ロック解除されたとき、

は第二に、ミューテックスをロックする（早くスピンロックされるように）高速です。ミューテックスが既にロックされている場合にのみ（非常に遅い）ミューテックスをロック（ロック解除）が遅い。

だから、あなたのケースでは、私はミューテックスを使用することをお勧めします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top