17

わかりましたので、同期について読んでいます。競合状態を回避するために、スピンロック、セマフォ、ミューテックスなどのさまざまなアルゴリズムを読みました。

ただし、これらのアルゴリズムでは、複数のプロセスがまったく同時にデータにアクセスする場合、SMP の競合状態を防ぐことはできません。

たとえば、プロセッサ A のスレッド 1 が lock(mutex1); を実行するとします。撤回(1000); ロックを解除 (mutex1);

プロセッサ B のスレッド 2 は lock(mutex1) を実行します。預金(1000); 預金(1000); ロックを解除 (mutex1);

両方のスレッドが正確に同時に実行される場合、両方のスレッドが同時にクリティカル セクションになります。

唯一の解決策 (ハードウェア レベルである必要があります) は、各プロセッサを互いに少しずらして実行することですが、並列処理の目的を無効にします。

複数のプロセッサがまったく同時にロックを取得しようとする状況を回避するためのハードウェア レベルのサポートはありますか?

(これはアトミック性の問題ではなく、正確な並列性の問題であり、SMP がそれをどのように処理するのか疑問に思います)。

4

5 に答える 5

19

ミューテックスの要点は、2 つのコアが同時にそれを取得しようとしても、もう一方が解放するまで、そのうちの 1 つがブロックされることです。2 つのコアがそのミューテックスを同時に保持できるようにするミューテックスは、完全に壊れており、その唯一の意図された目的には役に立たないでしょう。

ハードウェアのどこかに、2 つのコアをリンクするバスを 1 つのコアだけが制御できるようにするバス アービトレータがあります。いずれかのコアがプライベート キャッシュにミューテックスを保持するメモリを既に持っている場合、そのコアが優先されます。それ以外の場合は、最初にバスに乗った人が勝ちます。

バス アービトレータはさまざまな方法で機能しますが、通常はローテーションします。したがって、コアが 0、1、2、および 3 であり、コア 2 が最後にバスを持っていた場合、バスは次に必要な場合はコア 3 に移動し、そうでない場合はコア 0 に移動し、そうでない場合はコア 1 に移動します。それ以外の場合は、コア 2 に戻ります。どのバスが関与しているか (2 つのコアの L2 キャッシュ間での競合か、メモリ自体をめぐる競合かなど) に応じて、コアの一部が他のコア グループに対してユニットとして競合し、サブ競合する場合があります。どの特定のコアが最初に取得されるか。

1 つのコアが既にバスを制御している可能性があるため、完全に優先されます。通常、アービトレータは、コアが先に進むことを許可しない無駄なハンドオフを回避するために、コアがいくつかのトランザクションにバスを使用し続ける限り、バスを継続的に保持することを許可します。

正確な詳細は、コアがどのように配置されているか、どのコアがどの状態でキャッシュにロックを持っているか、誰が最後にバスを持っていたか、バス アービトレータがタイムスライス、ラウンド ロビン、またはその他を使用しているかどうかなど、多数の要因によって異なります。他のメカニズムなど。しかし、1 つのコアだけがロックを取得することを保証しない実装は、ひどく壊れていると見なされます。

于 2011-10-23T01:19:17.500 に答える
3

メモリバリアを調べたいと思うかもしれません。

http://en.wikipedia.org/wiki/Memory_barrier

この場合、ロックで使用される内部値に複数のプロセッサが一度にアクセスできないように、ロックはメモリ バリアを使用します。

一部のアーキテクチャでは、これを可能にするために、1 つを除くすべてのコアをロックすることもできます。たとえば、x86 は、命令に追加されると、その命令中のメモリへのアクセスをロックする LOCK プレフィックスを備えています。(例: LOCK ADD EAX、レジスタへのアトミック インクリメントの場合は 1)

LOCK またはアトミック命令をサポートしないアーキテクチャは、比較と交換、またはテストと設定/交換を使用します。通常、高レベルでは次のように見える小さな命令ループが含まれます

while (target != value) target = value;

これは複数回実行されるようには見えないかもしれませんが、命令間で値がその下から変更されないようにします。このアプローチの欠点は、ターゲットでの競合が多い場合、必要以上のクロック サイクルを消費する可能性がありますが、十分に高速に発生する傾向があるため、実際には目立たないことです。

于 2011-10-23T00:58:07.433 に答える
1

Curt Schimmel の最新アーキテクチャ向け UNIX® システム: Symmetric Multiprocessing and Caching for Kernel Programmersを強くお勧めします。ハードウェア アーキテクチャが異なれば、データへのアクセスを同期するためのさまざまな低レベル ツールが提供されます。Schimmel の本には、これらのアーキテクチャでも機能するアルゴリズムが記載されています。

内容を要約するコピーを簡単に見つけられるといいのですが。

于 2011-10-23T01:10:25.807 に答える
0

これは、TLS や XCHG などのアトミックな命令を使用して防ぐことができます。

命令の原子性をどのように保証しますか?

命令を実行する前にすべての割り込みを無効にし、命令の実行後にすべてを有効にすることができます。プロセッサ 1 で割り込みを無効にしてもプロセッサ 2 には影響しないため、これはマルチコア システムでは役に立ちません。 .

したがって、これらの命令を使用してセマフォを実装すると、SMP で問題が発生することはありません。

TSLを使用したmutex_lockおよびmutex_unlockの実装:

 mutex_lock:
    TSL REGISTER, MUTEX ; copy mutex to register and sets mutex
    CMP REGISTER, #0    ; compare mutex to zero
    JZE ok              ; if zero return
    CALL thread_yield   ; else: mutex is busy, schedule another thread
    JMP mutex_lock      ; try again later
 ok: RET

 mutex_unlock:
    MOVE MUTEX,#0       ; free mutex
    RET

TSL に関する情報は、http: //en.wikipedia.org/wiki/Test-and-setで見つけることができます 。

あなたを助けることができる良い本：

于 2011-10-23T01:27:02.140 に答える
-1

これは古典的なデッドロック問題です。ハードウェア サポートについてはよくわかりませんが (ただし、これがハードウェア レベルでサポートされていることはほぼ確実です)、データベースのデッドロック問題の解決策の例を示すことができます。すべての依存関係がわかっている場合、どの依存関係を「強制終了」する必要があるかがわかっている場合、この方法では、指定されたノードのコマンドは失敗しますが、システムはデッドロックを解消し、他のノードは失敗しません。ハードウェアレベルでも同じアプローチが必要だと思います。

于 2011-10-23T01:01:31.893 に答える