15

集約的なネットワーク アプリケーション用に、ロックフリーのシングル プロデューサー、シングル コンシューマー キューを実装しています。独自の個別のキューで作業を受け取る多数のワーカー スレッドがあり、それらはキューから取り出されて処理されます。

これらのキューからロックを削除すると、高負荷時のパフォーマンスが大幅に向上しましたが、キューが空のときにブロックされなくなり、CPU 使用率が急上昇しました。

何かを正常にデキューできるか、強制終了/中断されるまで、スレッドを効率的にブロックするにはどうすればよいですか?

4

6 に答える 6

16

Linux を使用している場合は、Futexの使用を検討してください。これは、ミューテックスのようなカーネル呼び出しではなくアトミック操作を使用することにより、非ロック実装のパフォーマンスを提供しますが、何らかの条件が真ではない (ロック競合など) ためにプロセスをアイドル状態に設定する必要がある場合は、次に、適切なカーネル呼び出しを行ってプロセスをスリープ状態にし、将来のイベントで再び起動します。基本的には、非常に高速なセマフォのようなものです。

于 2011-05-22T18:44:00.977 に答える
9

Linux では、futexを使用してスレッドをブロックできます。ただし、Futex は扱いにくいことに注意してください。

更新: 条件変数は futex よりもはるかに安全に使用でき、移植性も高くなります。ただし、条件変数はミューテックスと組み合わせて使用​​されるため、厳密には結果はロックフリーではなくなります。ただし、主な目標がパフォーマンス (グローバルな進行の保証ではない) であり、ロックされた部分 (つまり、スレッドのウェイクアップ後にチェックする条件) が小さい場合は、詳細を確認しなくても満足のいく結果が得られる可能性があります。フューテックスをアルゴリズムに統合する際の機微。

于 2011-05-22T18:45:01.003 に答える
7

Windows を使用している場合、futex を使用することはできませんが、Windows Vista にはKeyed Eventsと呼ばれる同様のメカニズムがあります。残念ながら、これは公開された API (NTDLL ネイティブ API) の一部ではありませんが、Windows の将来のバージョンで変更される可能性があるという警告を受け入れる限り、使用できます (また、Windows で実行する必要はありません)。 Vista より前のカーネル)。上でリンクした記事を必ず読んでください。これがどのように機能するかのテストされていないスケッチです。

/* Interlocked SList queue using keyed event signaling */

struct queue {
    SLIST_HEADER slist;
    // Note: Multiple queues can (and should) share a keyed event handle
    HANDLE keyed_event;
    // Initial value: 0
    // Prior to blocking, the queue_pop function increments this to 1, then
    // rechecks the queue. If it finds an item, it attempts to compxchg back to
    // 0; if this fails, then it's racing with a push, and has to block
    LONG block_flag;
};

void init_queue(queue *qPtr) {
    NtCreateKeyedEvent(&qPtr->keyed_event, -1, NULL, 0);
    InitializeSListHead(&qPtr->slist);
    qPtr->blocking = 0;
}

void queue_push(queue *qPtr, SLIST_ENTRY *entry) {
    InterlockedPushEntrySList(&qPtr->slist, entry);

    // Transition block flag 1 -> 0. If this succeeds (block flag was 1), we
    // have committed to a keyed-event handshake
    LONG oldv = InterlockedCompareExchange(&qPtr->block_flag, 0, 1);
    if (oldv) {
        NtReleaseKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    }
}

SLIST_ENTRY *queue_pop(queue *qPtr) {
    SLIST_ENTRY *entry = InterlockedPopEntrySList(&qPtr->slist);
    if (entry)
        return entry; // fast path

    // Transition block flag 0 -> 1. We must recheck the queue after this point
    // in case we race with queue_push; however since ReleaseKeyedEvent
    // blocks until it is matched up with a wait, we must perform the wait if
    // queue_push sees us
    LONG oldv = InterlockedCompareExchange(&qPtr->block_flag, 1, 0);

    assert(oldv == 0);

    entry = InterlockedPopEntrySList(&qPtr->slist);
    if (entry) {
        // Try to abort
        oldv = InterlockedCompareExchange(&qPtr->block_flag, 0, 1);
        if (oldv == 1)
            return entry; // nobody saw us, we can just exit with the value
    }

    // Either we don't have an entry, or we are forced to wait because
    // queue_push saw our block flag. So do the wait
    NtWaitForKeyedEvent(qPtr->keyed_event, (PVOID)qPtr, FALSE, NULL);
    // block_flag has been reset by queue_push

    if (!entry)
        entry = InterlockedPopEntrySList(&qPtr->slist);
    assert(entry);

    return entry;
}

また、 Slim Read Write locks とCondition Variablesを使用して、ロックレス高速パスで同様のプロトコルを使用することもできます。これらはキー付きイベントのラッパーであるため、キー付きイベントを直接使用するよりも多くのオーバーヘッドが発生する可能性があります。

于 2011-05-23T01:40:05.333 に答える
1

条件付き待機を試しましたか？キューが空になったら、新しいジョブを待ち始めます。ジョブをキューに入れるスレッドは、シグナルを発火する必要があります。このようにして、キューが空の場合にのみロックを使用します。

https://computing.llnl.gov/tutorials/pthreads/#ConditionVariables

于 2011-05-22T18:49:01.217 に答える
1

sigwait() 関数を使用して、スレッドをスリープ状態にすることができます。pthread_kill でスレッドを起こすことができます。これは、条件変数よりもはるかに高速です。

于 2011-06-15T20:15:00.363 に答える
0

待機中にスリープを追加できます。希望する最大の待機時間を選択してから、次のようにします（pthread構文を覚えていないため、擬似コード）。

WAIT_TIME = 100; // Set this to whatever you're happy with
while(loop_condition) {
   thing = get_from_queue()
   if(thing == null) {
       sleep(WAIT_TIME);
   } else {
       handle(thing);
   }
}

100ミリ秒のスリープのような短いものでも、CPU使用率を大幅に下げる必要があります。ただし、コンテキストの切り替えによって、ビジーウェイトよりも悪化するのはいつかはわかりません。

于 2011-05-22T18:40:13.863 に答える