42

私たちのコードには、ミューテックスによって保護されたデータの同時読み取りがかなり一般的であり、書き込みはめったに行われない場所がいくつかあることがわかりました。私たちの測定によると、単純なミューテックスを使用すると、そのデータを読み取るコードのパフォーマンスが大幅に低下するようです。したがって、必要なのは複数読み取り/単一書き込みミューテックスです。これがより単純なプリミティブの上に構築できることはわかっていますが、これを試す前に、既存の知識を求めたいと思います。

単純な同期プリミティブから複数読み取り/単一書き込みロックを構築する承認済みの方法は何ですか?

私はそれを作る方法を知っていますが、私が（おそらく間違って）思いついたことに偏りのない答えが欲しい. （注：私が期待しているのは、おそらく完全な実装ではなく、疑似コードでの方法の説明です。確かに自分でコードを書くことができます。）

警告:

  • これには、妥当なパフォーマンスが必要です。(私が念頭に置いていることは、アクセスごとに 2 つのロック/ロック解除操作が必要になることです。これでは十分ではないかもしれませんが、代わりに多くの操作が必要になるのは不合理に思えます。)

  • 一般に、読み取りはより多くなりますが、書き込みは読み取りよりも重要であり、パフォーマンスに影響されます。読者は作家を飢えさせてはなりません。

  • 私たちは、かなり古い組み込みプラットフォーム (VxWorks 5.5 の専有バージョン)、かなり古いコンパイラ (GCC 4.1.2)、およびブースト 1.52 に固執しています。ただし、POSIX は完全には実装されていないため、POSIX に依存するブーストのほとんどの部分を除きます。そのプラットフォームで。基本的に使用可能なロック プリミティブは、いくつかの種類のセマフォ (バイナリ、カウンティングなど) であり、その上にミューテックス、条件変数、およびモニターが既に作成されています。

  • これはIA32、シングルコアです。

4

8 に答える 8

19

同期プリミティブとしてミューテックスと condition_variable しかないようです。したがって、ここにリーダー/ライター ロックを記述します。これにより、リーダーが飢えます。1 つのミューテックス、2 つの conditional_variable、3 つの整数を使用します。

readers - readers in the cv readerQ plus the reading reader
writers - writers in cv writerQ plus the writing writer
active_writers - the writer currently writing. can only be 1 or 0.

このように読者を飢えさせます。書きたい書き手が複数いる場合、書き手全員が書き終わるまで、読者は読む機会を得られません。これは、後の読者がwriters変数をチェックする必要があるためです。同時に、active_writers変数は一度に 1 つのライターだけが書き込みできることを保証します。

class RWLock {
public:
    RWLock()
    : shared()
    , readerQ(), writerQ()
    , active_readers(0), waiting_writers(0), active_writers(0)
    {}

    void ReadLock() {
        std::unique_lock<std::mutex> lk(shared);
        while( waiting_writers != 0 )
            readerQ.wait(lk);
        ++active_readers;
        lk.unlock();
    }

    void ReadUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --active_readers;
        lk.unlock();
        writerQ.notify_one();
    }

    void WriteLock() {
        std::unique_lock<std::mutex> lk(shared);
        ++waiting_writers;
        while( active_readers != 0 || active_writers != 0 )
            writerQ.wait(lk);
        ++active_writers;
        lk.unlock();
    }

    void WriteUnlock() {
        std::unique_lock<std::mutex> lk(shared);
        --waiting_writers;
        --active_writers;
        if(waiting_writers > 0)
            writerQ.notify_one();
        else
            readerQ.notify_all();
        lk.unlock();
    }

private:
    std::mutex              shared;
    std::condition_variable readerQ;
    std::condition_variable writerQ;
    int                     active_readers;
    int                     waiting_writers;
    int                     active_writers;
};
于 2015-01-24T01:59:57.883 に答える
5

ミューテックスによって保護されたデータの同時読み取りはかなり一般的ですが、書き込みはまれです

これは、ユーザー空間 RCUの理想的なシナリオのように思えます。

URCU は Linux カーネルの対応物に似ており、他の用途の中でも特にリーダー/ライター ロックの代わりを提供します。この類似性は、リーダーが RCU アップデーターと直接同期しない場合にも続きます。したがって、RCU 読み取り側のコード パスが非常に高速になり、さらに、RCU アップデーターと同時に実行されている場合でも、RCU リーダーが有用な前進を行うことができます (逆も同様です)。

于 2015-01-23T11:01:35.040 に答える
2

いつものように、最善の解決策は詳細に依存します。読み取り/書き込みスピン ロックが探しているものかもしれませんが、上記で提案した読み取り-コピー-更新などの他のアプローチが解決策になる可能性があります。ただし、古い組み込みプラットフォームでは、使用される余分なメモリが問題になる可能性があります。まれな書き込みでは、タスキング システムを使用して、そのデータ構造からの読み取りがない場合にのみ書き込みが発生するように作業を調整することがよくありますが、これはアルゴリズムに依存します。

于 2015-01-23T11:19:01.077 に答える
1

セマフォとミューテックスに基づくこのアルゴリズムの 1 つは 、「リーダーとライターによる同時制御」で説明されています。PJ クルトワ、F. ヘイマンズ、DL パルナス。MBLE研究所; ブリュッセル、ベルギー。

于 2015-01-23T18:44:26.600 に答える
0

Microsoft が .NET ソース コードを公開したので、 ReaderWRiterLockSlim の実装を見ることができます。

それらが使用するより基本的なプリミティブが利用できるかどうかはわかりませんが、それらのいくつかは .NET ライブラリの一部でもあり、それらのコードも利用できます。

Microsoft は、ロック メカニズムのパフォーマンスを改善するためにかなりの時間を費やしてきたので、これは良い出発点になる可能性があります。

于 2015-01-30T08:18:19.573 に答える
0

これは、Boost ヘッダーに基づいた簡単な回答です (Boost を承認済みの方法と呼びます)。条件変数とミューテックスのみが必要です。Windows プリミティブは説明的で非常に単純だと思うので、Windows プリミティブを使用して書き直しましたが、これは疑似コードと見なします。

これは非常に単純な解決策であり、mutex のアップグレードや try_lock() 操作などをサポートしていません。必要に応じて追加できます。また、厳密には必要ではない割り込みを無効にするなど、いくつかのフリルを取り除きました。

また、チェックアウトする価値がありますboost\thread\pthread\shared_mutex.hpp（これはそれに基づいています）。人間が読める形式です。

class SharedMutex {
  CRITICAL_SECTION m_state_mutex;
  CONDITION_VARIABLE m_shared_cond;
  CONDITION_VARIABLE m_exclusive_cond;

  size_t shared_count;
  bool exclusive;

  // This causes write blocks to prevent further read blocks
  bool exclusive_wait_blocked;

  SharedMutex() : shared_count(0), exclusive(false)
  {
    InitializeConditionVariable (m_shared_cond);
    InitializeConditionVariable (m_exclusive_cond);
    InitializeCriticalSection (m_state_mutex);
  }

  ~SharedMutex() 
  {
    DeleteCriticalSection (&m_state_mutex);
    DeleteConditionVariable (&m_exclusive_cond);
    DeleteConditionVariable (&m_shared_cond);
  }

  // Write lock
  void lock(void)
  {
    EnterCriticalSection (&m_state_mutex);
    while (shared_count > 0 || exclusive)
    {
      exclusive_waiting_blocked = true;
      SleepConditionVariableCS (&m_exclusive_cond, &m_state_mutex, INFINITE)
    }
    // This thread now 'owns' the mutex
    exclusive = true;

    LeaveCriticalSection (&m_state_mutex);
  }

  void unlock(void)
  {
    EnterCriticalSection (&m_state_mutex);
    exclusive = false;
    exclusive_waiting_blocked = false;
    LeaveCriticalSection (&m_state_mutex);
    WakeConditionVariable (&m_exclusive_cond);
    WakeAllConditionVariable (&m_shared_cond);
  }

  // Read lock
  void lock_shared(void)
  {
    EnterCriticalSection (&m_state_mutex);
    while (exclusive || exclusive_waiting_blocked)
    {
      SleepConditionVariableCS (&m_shared_cond, m_state_mutex, INFINITE);
    }
    ++shared_count;
    LeaveCriticalSection (&m_state_mutex);
  }

  void unlock_shared(void)
  {
    EnterCriticalSection (&m_state_mutex);
    --shared_count;

    if (shared_count == 0)
    {
      exclusive_waiting_blocked = false;
      LeaveCriticalSection (&m_state_mutex);
      WakeConditionVariable (&m_exclusive_cond);
      WakeAllConditionVariable (&m_shared_cond);
    }
    else
    {
      LeaveCriticalSection (&m_state_mutex);
    }
  }
};

行動

さて、このアルゴリズムの動作には混乱があるので、その仕組みを次に示します。

書き込みロック中- リーダーとライターの両方がブロックされます。

書き込みロックの終了時- リーダー スレッドと 1 つのライター スレッドが競合して、どちらが開始するかを確認します。

読み取りロック中- ライターはブロックされます。ライターがブロックされている場合にのみ、リーダーもブロックされます。

最後の読み取りロックの解放時に、リーダー スレッドと 1 つのライター スレッドが競合して、どちらが開始するかを確認します。

これにより、プロセッサーが during 通知の前に頻繁にコンテキストをスレッドに切り替えると、リーダーがライターを飢えさせる可能性がありますが、Boost のアルゴリズムであるため、この問題は理論的なものであり、実用的ではないと思います。m_shared_condm_exclusive_cond

于 2015-01-23T19:42:13.320 に答える