7

昨日、高速スピンロックの書き方についてこの質問を投稿しました。Cory Nelsonのおかげで、私の質問で説明した他の方法よりも優れた方法を見つけたようです。この命令を使用してCMPXCHG、ロックが0であり、それによって解放されているかどうかを確認します。CMPXCHG「BYTE」で動作しWORDますDWORD。命令はでより速く動作すると思いBYTEます。しかし、私は各データ型を実装するロックを作成しました。

inline void spin_lock_8(char* lck)
{
    __asm
    {
        mov ebx, lck                        ;move lck pointer into ebx
        xor cl, cl                          ;set CL to 0
        inc cl                              ;increment CL to 1
        pause                               ;
        spin_loop:
        xor al, al                          ;set AL to 0
        lock cmpxchg byte ptr [ebx], cl     ;compare AL to CL. If equal ZF is set and CL is loaded into address pointed to by ebx
        jnz spin_loop                       ;jump to spin_loop if ZF
    }
}
inline void spin_lock_16(short* lck)
{
    __asm
    {
        mov ebx, lck
        xor cx, cx
        inc cx
        pause
        spin_loop:
        xor ax, ax
        lock cmpxchg word ptr [ebx], cx
        jnz spin_loop
    }
}
inline void spin_lock_32(int* lck)
{
    __asm
    {
        mov ebx, lck
        xor ecx, ecx
        inc ecx
        pause
        spin_loop:
        xor eax, eax
        lock cmpxchg dword ptr [ebx], ecx
        jnz spin_loop
    }
}
inline spin_unlock(<anyType>* lck)
{
    __asm
    {
        mov ebx, lck
        mov <byte/word/dword> ptr [ebx], 0
    }
}

次に、次の擬似コードを使用してロックをテストしました(lcm-pointerは常に4で割り切れるアドレスを指すことに注意してください)。

<int/short/char>* lck;
threadFunc()
{
    loop 10,000,000 times
    {
        spin_lock_8/16/32 (lck);
        spin_unlock(lck);
    }
}
main()
{
    lck = (char/short/int*)_aligned_malloc(4, 4);//Ensures memory alignment
    start 1 thread running threadFunc and measure time;
    start 2 threads running threadFunc and measure time;
    start 4 threads running threadFunc and measure time;
    _aligned_free(lck);
}

4つのスレッドを実行できる2つの物理コアを備えたプロセッサ(Ivy Bridge)で、ミリ秒単位で測定された次の結果が得られました。

           1 thread    2 threads     4 threads
8-bit      200         700           3200
16-bit     200         500           1400
32-bit     200         900           3400

データは、すべての関数の実行に同じ時間がかかることを示しています。ただし、複数のスレッドlck == 0で16ビットを使用するかどうかを確認する必要がある場合は、大幅に高速化できます。何故ですか?lck私はそれが?の配置と関係があるとは思いません。

前もって感謝します。

4

2 に答える 2

2

1234 個のスレッドと 16 個の CPU があるとします。1 つのスレッドがスピンロックを取得すると、OS がタスク スイッチを実行します。これで 16 個の CPU があり、それぞれが残りの 1233 スレッドの 1 つを実行し、OS がスピンロックを解放できる唯一のスレッドに CPU 時間を戻すのに時間がかかるにもかかわらず、すべてが非常に無意味な方法でスピンします。これは、基本的に OS 全体が (すべての CPU が完全に停止した状態で) 数秒間ロックアップする可能性があることを意味します。これは非常に遅れています。それで、どうやってそれを修正しますか?

ユーザー空間でスピンロックを使用しないことで修正します。スピンロックは、タスク スイッチを無効にできる場合にのみ使用してください。また、カーネルのみがタスク スイッチを無効にできる必要があります。

具体的には、ミューテックスを使用する必要があります。現在、ミューテックスは最初にスピンしてから、スレッドをあきらめてロックを待機させることができます。(典型的な/低競合の場合) これは役に立ちますが、ミューテックスのままであり、スピンロックではありません。

次; 正常なソフトウェアの場合、(パフォーマンスにとって) 重要なことは、ロックの競合を回避し、競合のないケースが高速であることを確認することです (競合がなければ、優れたミューテックスはタスク スイッチを引き起こしません)。競合/無関係なケースを測定しています。

ついに; あなたのロックは悪いです。プレフィックスの過度の使用を避けるために、lockプレフィックスなしで取得できるかどうかをテストし、取得できるlock場合にのみプレフィックスを使用する必要がありlockます。Intel (およびおそらく他の多くの人々) は、この戦略を「テスト; その後 (テストと設定)」と呼んでいます。さらに、pause(または、10 年前の命令をサポートしないほど悪いアセンブラーの場合は「rep nop」) の目的を理解できませんでした。

半分まともなスピンロックは次のようになります。

acquire:
    lock bts dword [myLock],0   ;Optimistically attempt to acquire
    jnc .acquired               ;It was acquired!
.retry:
    pause
    cmp dword [myLock],0        ;Should we attempt to acquire again?
    jne .retry                  ; no, don't use `lock`
    lock bts dword [myLock],0   ;Attempt to acquire
    jc .retry                   ;It wasn't acquired, so go back to waiting
.acquired:
    ret

release:
    mov dword [myLock],0        ;No lock prefix needed here as "myLock" is aligned
    ret

また、ロック競合の可能性を適切に最小限に抑えることができなかった場合は、「公平性」に注意する必要があり、スピンロックを使用しないでください。「不公平な」スピンロックの問題は、運が良ければ常にロックを取得するタスクもあれば、不運でロックを取得できないタスクもあるということです。これは、激しく競合するロックでは常に問題でしたが、最新の NUMA システムでは、より起こりやすい問題になっています。この場合、少なくともチケットロックを使用する必要があります。

チケットロックの基本的な考え方は、タスクが到着した順序でロックを取得することを保証することです (「おそらく非常に悪い」ランダムな順序ではありません)。完全を期すために、チケット ロックは次のようになります。

acquire:
    mov eax,1
    lock xadd [myLock],eax           ;myTicket = currentTicket, currentTicket++

    cmp [myLock+4],eax               ;Is it my turn?
    je .acquired                     ; yes
.retry:
    pause
    cmp [myLock+4],eax               ;Is it my turn?
    jne .retry                       ; no, wait
.acquired:
    ret

release:
    lock inc dword [myLock+4]
    ret

tl;dr; そもそもジョブ (スピンロック) に間違ったツールを使用するべきではありません。ただし、間違ったツールを使用することに固執する場合は、少なくとも間違ったツールを適切に実装してください... :-)

于 2012-12-23T13:11:37.853 に答える