40

非常に小さなクリティカル セクションを保護するためにスピン ロックを使用しています。競合が発生することはめったにないため、スピン ロックは通常のミューテックスよりも適切です。

私の現在のコードは次のとおりで、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 回、スピン ロックをロックしようとしているスレッドが他に 1 つまたは 2 つある可能性があります。

4

11 に答える 11

22

私には元気そうです。ところで、これは、争われている場合でもより効率的な教科書の実装です。

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}
于 2009-09-05T14:50:23.653 に答える
18

だから私は疑問に思っています：

* Is it correct?

言及された文脈では、私はそう言うでしょう。

* Is it optimal?

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

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

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

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

  • 競合が発生した場合は、何か、semop、または必死になって愚かな眠りが必要です。これで得られるパフォーマンスが本当に必要な場合は、futex の提案がおそらく適切です。パフォーマンスが必要な場合は、このコードを維持するのに十分な費用がかかります。多くの調査が必要です。

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

* on compare and swap

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

于 2009-10-13T17:29:50.623 に答える
4

次の CAS 実装は x86_64 で正しいものでしょうか。i7 X920 ラップトップ (fedora 13 x86_64、gcc 4.4.5) ではほぼ 2 倍高速です。

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");
}
于 2010-11-24T20:55:20.027 に答える
4

ご質問への回答:

  1. 私には問題ないように見えます
  2. OS が GCC をサポートしている (そして GCC に機能が実装されている) と仮定します。これは、すべての x86 オペレーティング システムで動作するはずです。GCC のドキュメントでは、特定のプラットフォームでサポートされていない場合に警告が生成されることが示唆されています。
  3. ここには x86-64 固有のものは何もないので、理由がわかりません。これは、GCC がサポートするすべてのアーキテクチャをカバーするように拡張できますが、非 x86 アーキテクチャでこれを実現するためのより最適な方法があるかもしれません。
  4. ケースで使用__sync_lock_release()する方が少し良いかもしれません。unlock()これは、1 回の操作でロックを減らし、メモリ バリアを追加するためです。ただし、競合がめったにないというあなたの主張を前提としています。私には良さそうです。
于 2009-09-05T14:02:21.263 に答える
3

Linuxの最近のバージョンを使用している場合は、 futex（「高速ユーザースペースミューテックス」）を使用できる場合があります。

適切にプログラムされたfutexベースのロックは、ロックが競合している場合を除いて、システムコールを使用しません。

スピンロックを使用して最適化しようとしている競合のないケースでは、futexはカーネルのシステムコールを必要とせずにスピンロックのように動作します。ロックが競合している場合、待機はビジー待機なしでカーネルで行われます。

于 2009-09-05T16:29:20.530 に答える
2

正しさについてコメントすることはできませんが、質問の本文を読む前に、質問のタイトルが赤旗を立てました。同期プリミティブは、正確さを保証するのが非常に困難です...可能であれば、適切に設計/保守されたライブラリ、おそらくpthreadsまたはboost::threadを使用する方がよいでしょう。

于 2009-09-05T14:22:35.437 に答える
1

いくつかの間違った仮定があります。

まず、SpinLock は、リソースが別の CPU でロックされている場合にのみ意味があります。リソースが同じ CPU でロックされている場合 (ユニプロセッサ システムでは常にそうです)、リソースをロック解除するためにスケジューラを緩和する必要があります。スケジューラが自動的にタスクを切り替えるため、現在のコードはユニプロセッサ システムで動作しますが、リソースの無駄です。

マルチプロセッサ システムでも同じことが起こりますが、タスクはある CPU から別の CPU に移行する可能性があります。つまり、タスクが別の CPU で実行されることが保証されている場合は、スピン ロックの使用は適切です。

第 2 に、ミューテックスのロックは、ロックが解除されたときに高速 (スピンロックと同程度) です。ミューテックスのロック (およびロック解除) は、ミューテックスが既にロックされている場合にのみ遅く (非常に遅く) なります。

したがって、あなたの場合、ミューテックスを使用することをお勧めします。

于 2014-07-25T09:37:50.587 に答える
0

改善点の1つは、TATAS（テストアンドテストアンドセット）を使用することです。CAS操作の使用は、プロセッサにとって非常にコストがかかると考えられているため、可能であれば回避することをお勧めします。もう1つは、優先順位の逆転に悩まされないようにすることです（優先順位の高いスレッドがロックを取得しようとし、優先順位の低いスレッドがロックを解放しようとした場合はどうなりますか？たとえば、Windowsでは、この問題は最終的に次のように解決されます。スケジューラーは優先順位のブーストを使用しますが、過去20回の試行でロックの取得に成功しなかった場合に備えて、スレッドのタイムスライスを明示的に放棄できます（たとえば..）

于 2009-09-05T14:45:16.813 に答える
0

x86 (32/64) の特定のケースでは、ロック解除コードにメモリ フェンスはまったく必要ないと思います。x86 では並べ替えは行われませんが、ストアは最初にストア バッファーに格納されるため、他のスレッドが表示されるのを遅らせることができます。また、ストアを実行してから同じ変数から読み取るスレッドは、まだメモリにフラッシュされていない場合、ストア バッファーから読み取ります。したがって、必要なのは、asmコンパイラの並べ替えを防ぐためのステートメントだけです。1 つのスレッドが他のスレッドの観点から必要以上に長くロックを保持するリスクがありますが、競合を気にしないのであれば、それは問題ではありません。実際、pthread_spin_unlock私のシステム（linux x86_64）ではそのように実装されています。

pthread_spin_lock私のシステムは、 usinglock decl lockvar; jne spinloop;の代わりに usingも実装していますがxchg(これは__sync_lock_test_and_setuses です)、実際にパフォーマンスの違いがあるかどうかはわかりません。

于 2013-03-03T18:52:36.750 に答える
0

ロック解除手順にはメモリ バリアは必要ありません。除外への割り当ては、x86 で dword アライメントされている限りアトミックです。

于 2009-09-05T15:15:31.833 に答える