9

への関数呼び出しの形式で要求を処理するマルチスレッド C++ プログラムがあるとしhandleRequest(string key)ます。への各呼び出しhandleRequestは個別のスレッドで発生し、 には任意の数の可能な値がありkeyます。

次の動作が必要です。

  • の同時呼び出しhandleRequest(key)は、 の値が同じ場合にシリアル化されkeyます。
  • グローバルなシリアライゼーションは最小限に抑えられます。

の本体は次のhandleRequestようになります。

void handleRequest(string key) {
    KeyLock lock(key);
    // Handle the request.
}

質問:必要な動作を得るためにどのように実装KeyLockしますか?

単純な実装は、次のように開始できます。

KeyLock::KeyLock(string key) {
    global_lock->Lock();
    internal_lock_ = global_key_map[key];
    if (internal_lock_  == NULL) {
        internal_lock_  = new Lock();
        global_key_map[key] = internal_lock_;
    }
    global_lock->Unlock();
    internal_lock_->Lock();
}

KeyLock::~KeyLock() {
    internal_lock_->Unlock();
    // Remove internal_lock_ from global_key_map iff no other threads are waiting for it.
}

...しかし、それには各リクエストの最初と最後にグローバル ロックが必要であり、リクエストLockごとに個別のオブジェクトを作成する必要があります。への呼び出し間の競合が高い場合はhandleRequest問題にならない可能性がありますが、競合が少ない場合は多くのオーバーヘッドが発生する可能性があります。

4

6 に答える 6

12

質問にあるものと同様のことを行うことができますが、単一の global_key_map の代わりに複数 (おそらく配列またはベクトル) を使用します。どれが使用されるかは、文字列の単純なハッシュ関数によって決定されます。

そうすれば、単一のグローバル ロックの代わりに、複数の独立したロックに分散できます。

これは、メモリ アロケーターでよく使用されるパターンです (パターンに名前があるかどうかはわかりませんが、名前があるはずです)。リクエストが来ると、割り当てがどのプールから来るかが何かによって決定され (通常はリクエストのサイズですが、他のパラメーターも考慮に入れることができます)、そのプールだけをロックする必要があります。別のプールを使用する別のスレッドから割り当て要求が届いた場合、ロックの競合は発生しません。

于 2008-10-03T18:38:17.573 に答える
2

おそらく、必要なものはどこにあるでしょう。必要なミューテックスのタイプはstd::map<std::string, MutexType>どこにありますか。MutexType他のスレッドが同時に挿入していないことを確認するために、マップへのアクセスを別のミューテックスでラップする必要があるでしょう (また、ミューテックスがロックされた後に再度チェックを実行して、別のスレッドがマップを追加していないことを確認することを忘れないでください)。ミューテックスを待っている間にキーを押してください!)。

同じ原則が、クリティカル セクションなどの他の同期方法にも適用できます。

于 2008-10-03T18:39:45.573 に答える
2

プラットフォームによって異なりますが、私が試す 2 つの手法は次のとおりです。

  • オブジェクト名 = キーの名前付きミューテックス/同期オブジェクトを使用する
  • キー名で共有不可能な一時ファイルを作成しようとするファイルシステムベースのロックを使用します。すでに存在する (= 既にロックされている) 場合、これは失敗し、ポーリングして再試行する必要があります。

どちらの手法も、OS の詳細に依存します。実験して、どれが機能するかを確認してください。.

于 2008-10-03T18:39:14.467 に答える
2

粒度を上げてキー範囲全体をロックする

これは、Mike B の回答のバリエーションです。いくつかの流動的なロック マップを使用する代わりに、単一のキーではなくキー範囲に適用されるロックの単一の固定配列を使用します。

簡単な例: 起動時に 256 個のロックの配列を作成し、キーの最初のバイトを使用して取得するロックのインデックスを決定します (つまり、「k」で始まるすべてのキーは によって保護されlocks[107]ます)。

最適なスループットを維持するには、キーの分布と競合率を分析する必要があります。このアプローチの利点は、動的割り当てがゼロであり、クリーンアップが簡単なことです。また、2 段階のロックも回避できます。欠点は、時間の経過とともにキーの配布が偏った場合に競合がピークに達する可能性があることです。

于 2008-10-03T22:18:07.410 に答える
0 
      /**
      * StringLock class for string based locking mechanism
      * e.g. usage
      *     StringLock strLock;
      *     strLock.Lock("row1");
      *     strLock.UnLock("row1");
      */
      class StringLock    {
      public:
          /**
           * Constructor
           * Initializes the mutexes
           */
          StringLock()    {
              pthread_mutex_init(&mtxGlobal, NULL);
          }
          /**
           * Lock Function
           * The thread will return immediately if the string is not locked
           * The thread will wait if the string is locked until it gets a turn
           * @param string the string to lock
           */
          void Lock(string lockString)    {
              pthread_mutex_lock(&mtxGlobal);
              TListIds *listId = NULL;
              TWaiter *wtr = new TWaiter;
              wtr->evPtr = NULL;
              wtr->threadId = pthread_self();
              if (lockMap.find(lockString) == lockMap.end())    {
                  listId = new TListIds();
                  listId->insert(listId->end(), wtr);
                  lockMap[lockString] = listId;
                  pthread_mutex_unlock(&mtxGlobal);
              } else    {
                  wtr->evPtr = new Event(false);
                  listId = lockMap[lockString];
                  listId->insert(listId->end(), wtr);
                  pthread_mutex_unlock(&mtxGlobal);
                  wtr->evPtr->Wait();
              }
          }
          /**
          * UnLock Function
          * @param string the string to unlock
          */
          void UnLock(string lockString)    {
              pthread_mutex_lock(&mtxGlobal);
              TListIds *listID = NULL;
              if (lockMap.find(lockString) != lockMap.end())    {
                  lockMap[lockString]->pop_front();
                  listID = lockMap[lockString];
                  if (!(listID->empty()))    {
                      TWaiter *wtr = listID->front();
                      Event *thdEvent = wtr->evPtr;
                      thdEvent->Signal();
                  } else    {
                      lockMap.erase(lockString);
                      delete listID;
                  }
              }
              pthread_mutex_unlock(&mtxGlobal);
          }
      protected:
          struct TWaiter    {
              Event *evPtr;
              long threadId;
          };
          StringLock(StringLock &);
          void operator=(StringLock&);
          typedef list TListIds;
          typedef map TMapLockHolders;
          typedef map TMapLockWaiters;
      private:
          pthread_mutex_t mtxGlobal;
          TMapLockWaiters lockMap;
      };
于 2009-01-05T03:57:42.973 に答える
0

それについて考えた後、別のアプローチは次のようになります。

  • で、実際の作業を行う をhandleRequest作成します。Callback
  • multimap<string, Callback*> global_key_mapミューテックスで保護された を作成します。
  • スレッドは、それkeyがすでに処理されていることを確認すると、それを に追加しCallback*てglobal_key_map戻ります。
  • それ以外の場合は、コールバックをすぐに呼び出してから、その間に表示された同じキーのコールバックを呼び出します。

このようなものを実装しました：

LockAndCall(string key, Callback* callback) {
    global_lock.Lock();
    if (global_key_map.contains(key)) {
        iterator iter = global_key_map.insert(key, callback);
        while (true) {
            global_lock.Unlock();
            iter->second->Call();
            global_lock.Lock();
            global_key_map.erase(iter);
            iter = global_key_map.find(key);
            if (iter == global_key_map.end()) {
                global_lock.Unlock();
                return;
            }
        }
    } else {
        global_key_map.insert(key, callback);
        global_lock.Unlock();
    }
}

これには、そうでなければキーロックを待っているスレッドを解放するという利点がありますが、それを除けば、私が質問に投稿した素朴な解決策とほとんど同じです.

ただし、Mike B と Constantin の回答と組み合わせることができます。

于 2008-10-03T22:47:16.133 に答える