6

これらの要件に適合するロックのない設計を探しています。

  • 単一のライターが構造体に書き込み、単一のリーダーがこの構造体から読み取ります (この構造体は既に存在し、同時読み取り/書き込みに対して安全です)
  • しかし、ある時点で、構造体は writer によって変更される必要があり、初期化、切り替え、および新しい構造体への書き込み (同じ型であるが新しい内容を持つ)
  • 次にリーダーが読み取るときに、この新しい構造に切り替えます(ライターが新しいロックフリー構造に複数回切り替えた場合、リーダーはこれらの構造を破棄し、そのデータを無視します)。
  • 構造体は再利用する必要があります。つまり、 RT の目的で、書き込み/読み取り/切り替え操作中にヒープ メモリの割り当て/解放は許可されません。

現在、これらの構造の複数のインスタンスを含むリングバッファーを実装しています。しかし、この実装は、ライターがリングバッファーに存在するすべての構造を使用すると、構造から変更する場所がなくなるという事実に悩まされています...しかし、リングバッファーの残りの部分には、読み取る必要のないデータが含まれていますリーダーによって再利用できますが、ライターは再利用できません。結果として、リングバッファはこの目的に適合しません。

ロックフリー設計のアイデア(名前または疑似実装)はありますか? この問題を検討していただきありがとうございます。

4

2 に答える 2

0

これが1つです。重要なのは、3つのバッファーがあり、リーダーが読み取り元のバッファーを予約することです。ライターは、他の2つのバッファーの1つに書き込みます。衝突のリスクは最小限です。さらに、これは拡張します。メンバー配列を、リーダーの数にライターの数を加えた数よりも1要素長くするだけです。

class RingBuffer
{
  RingBuffer():lastFullWrite(0)
  { 
    //Initialize the elements of dataBeingRead to false
    for(unsigned int i=0; i<DATA_COUNT; i++)
    {
      dataBeingRead[i] = false;
    } 
  }

  Data read()
  {
    // You may want to check to make sure write has been called once here
    // to prevent read from grabbing junk data. Else, initialize the elements
    // of dataArray to something valid.
    unsigned int indexToRead = lastFullWriteIndex;
    Data dataCopy;
    dataBeingRead[indexToRead] = true;
    dataCopy = dataArray[indexToRead];
    dataBeingRead[indexToRead] = false;
    return dataCopy;
  }

  void write( const Data& dataArg )
  {
    unsigned int writeIndex(0);

    //Search for an unused piece of data.
    // It's O(n), but plenty fast enough for small arrays.
    while( true == dataBeingRead[writeIndex] && writeIndex < DATA_COUNT )
    {
      writeIndex++;
    }  

    dataArray[writeIndex] = dataArg;

    lastFullWrite = &dataArray[writeIndex];
  }

private:
  static const unsigned int DATA_COUNT;
  unsigned int lastFullWrite;
  Data dataArray[DATA_COUNT];
  bool dataBeingRead[DATA_COUNT];
};

注：ここでの記述方法では、データを読み取るための2つのコピーがあります。参照引数を介して読み取り関数からデータを渡す場合は、それを1つのコピーに減らすことができます。

于 2010-02-25T18:32:54.797 に答える
0

あなたは正しい軌道に乗っています。

スレッド/プロセス/プロセッサ間の固定メッセージのロックフリー通信 代替テキスト

プロデューサとコンシューマが 1 つずつある場合、固定サイズのリング バッファは、スレッド、プロセス、またはプロセッサ間のロックフリー通信に使用できます。実行するいくつかのチェック:

head変数はプロデューサーによってのみ書き込まれます (書き込み後のアトミック アクションとして)

tail変数はコンシューマーによってのみ書き込まれます (読み取り後のアトミック アクションとして)

落とし穴: サイズ変数またはバッファーのフル/空のフラグの導入。これらは通常、プロデューサーとコンシューマーの両方によって作成されるため、問題が発生します。

私は通常、この目的のためにリング バッファを使用します。私が学んだ最も重要な教訓は、 のリング バッファには 個以上の要素を含めることはできないということです。このようにして、head変数とtail変数がプロデューサーとコンシューマーによってそれぞれ書き込まれます。

大きな/可変サイズのブロックの拡張 リアルタイム環境でバッファを使用するには、メモリ プール (多くの場合、リアルタイム オペレーティング システムで最適化された形式で利用可能) を使用するか、割り当てを使用から切り離します。後者は質問に合っていると思います。

拡張キュー

大きなブロックを交換する必要がある場合は、バッファー ブロックを含むプールを使用し、キューを使用してバッファーへのポインターを通信することをお勧めします。そのため、バッファ ポインタを含む 3 番目のキューを使用します。このようにして、アプリケーション (バックグラウンド) で割り当てを行うことができ、リアルタイム部分は可変量のメモリにアクセスできます。

応用

while (blockQueue.full != true)
{
    buf = allocate block of memory from heap or buffer pool
    msg = { .... , buf };
    blockQueue.Put(msg)
}

Producer:
   pBuf = blockQueue.Get()
   pQueue.Put()

Consumer
   if (pQueue.Empty == false)
   {
      msg=pQueue.Get()
      // use info in msg, with buf pointer
      // optionally indicate that buf is no longer used
   }
于 2010-02-25T16:00:51.697 に答える