5

物語

どこかから定期的にデータを収集するライタースレッドがあります（リアルタイムですが、問題ではそれほど重要ではありません）。これらのデータから読み取る多くのリーダーがあります。これに対する通常の解決策は、次のように 2 つのリーダー/ライターのロックと 2 つのバッファーを使用することです。

Writer (case 1):
acquire lock 0                        
loop
    write to current buffer
    acquire other lock
    free this lock
    swap buffers
    wait for next period

または

Writer (case 2):
acquire lock 0                        
loop
    acquire other lock
    free this lock
    swap buffers
    write to current buffer
    wait for next period

問題

どちらの方法でも、他のロックの取得操作が失敗した場合、スワップは行われず、ライターは以前のデータを上書きします (ライターはリアルタイムであるため、リーダーを待つことができないため)。したがって、この場合、すべてのリーダーはそのフレームを失います。データの。

これは大したことではありませんが、リーダーは私自身のコードであり、短いので、ダブル バッファーを使用すると、この問題は解決されます。問題が発生した場合は、トリプル バッファー (またはそれ以上) にすることができます。

問題は、最小限にしたい遅延です。ケース 1 を想像してください。

writer writes to buffer0                reader is reading buffer1
writer can't acquire lock1              because reader is still reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      <- **this point**
|
|
writer wakes up, and again writes to buffer0

**この時点**で、理論的にはbuffer0、次の期間を待つのではなく、リーダーが終了した後にライターだけがスワップを実行できれば、他のリーダーはデータを読み取ることができたはずです。この場合、1 つのリーダーが少し遅れただけで、すべてのリーダーが 1 フレームのデータを見逃していましたが、問題は完全に回避できたはずです。

ケース 2 も同様です。

writer writes to buffer0                reader is idle
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)
|
|                                       reader starts reading buffer1
writer wakes up                         |
it can't acquire lock1                  because reader is still reading buffer1
overwrites buffer0

解決策を混ぜてみたので、ライターは書き込み直後にバッファーのスワップを試み、それができない場合は次のピリオドでウェイクアップした直後に試行します。だから、このようなもの：

Writer (case 3):
acquire lock 0                        
loop
    if last buffer swap failed
        acquire other lock
        free this lock
        swap buffers
    write to current buffer
    acquire other lock
    free this lock
    swap buffers
    wait for next period

遅延の問題はまだ残っています：

writer writes to buffer0                reader is reading buffer1
writer can't acquire lock1              because reader is still reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      <- **this point**
|
|
writer wakes up
swaps buffers
writes to buffer1

再び **この時点** で、すべてのリーダーが を読み始めることができますbuffer0。これは、 が書き込まれてから少し遅れbuffer0ますが、代わりに、ライターの次のピリオドまで待たなければなりません。

質問

問題は、これをどのように処理するかです。希望の周期で正確にライターを実行させたい場合は、RTAI関数を使用してその周期を待つ必要があり、私はそれを行うことができません

Writer (case 4):
acquire lock 0                        
loop
    write to current buffer
    loop a few times or until the buffer has been swapped
        sleep a little
        acquire other lock
        free this lock
        swap buffers
    wait for next period

これにより、ジッターが発生します。「数回」が「次の期間を待つ」よりも長くなる可能性があるため、ライターはその期間の開始を見逃す可能性があります。

より明確にするために、ここに私がしたいことがあります：

writer writes to buffer0                reader is reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      As soon as all readers finish reading,
|                                         the buffer is swapped
|                                       readers start reading buffer0
writer wakes up                         |
writes to buffer1

私がすでに見つけたもの

私が理解している限り、バッファーにメモリを割り当て続け、リーダーがそれらを使い果たすまでそれらを解放するread-copy-updateを見つけましたが、これは多くの理由で私には不可能です。1 つは、スレッドがカーネルとユーザー空間の間で共有されることです。次に、RTAI を使用すると、リアルタイム スレッドでメモリを割り当てることができません (スレッドが Linux のシステム コールを呼び出すことになり、リアルタイム性が損なわれるためです!)同じ理由で）

また、より高い頻度でバッファーのスワップを試行する追加のスレッドを用意することも考えましたが、それはあまり良い考えではないように思えます。まず、それ自体がライターと同期する必要があります。次に、これらのライター/リーダーの多くがさまざまな部分で並行して動作しているため、ライターごとに 1 つの余分なスレッドが多すぎるように思われます。すべてのライターに対して 1 つのスレッドというのは、各ライターとの同期に関して非常に複雑に思えます。

4

5 に答える 5

3

リーダー/ライター ロックに使用している API は何ですか? pthread_rwlock_timedwrlockのような時間制限のあるロックはありますか? はいの場合、次のコードのように、問題の解決策だと思います。

void *buf[2];

void
writer ()
{
  int lock = 0, next = 1;

  write_lock (lock);
  while (1)
    {
      abs_time tm = now() + period;

      fill (buf [lock]);
      if (timed_write_lock (next, tm))
        {
          unlock (lock);
          lock = next;
          next = (next + 1) & 1;
        }
      wait_period (tm);
    }
}


void
reader ()
{
  int lock = 0;
  while (1)
    {
      reade_lock (lock);
      process (buf [lock]);
      unlock (lock);
      lock = (lock + 1) & 1;
    }
}

ここで何が起こるかというと、次のピリオドが来る前に確実にウェイクアップする限り、ライターがロックを待つか、次のピリオドを待つかは問題ではありません。絶対タイムアウトにより、これが保証されます。

于 2011-11-10T09:27:50.517 に答える
1
  • キューを使用する (FIFO リンク リスト)
  • リアルタイム ライターは、常にキューの最後に追加 (エンキュー) します。
  • リーダーは常にキューの先頭から削除 (デキュー) します
  • キューが空の場合、リーダーはブロックされます

編集して動的割り当てを回避する

おそらく循環キューを使用します...組み込みの __sync アトミック操作を使用します。 http://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html#Atomic-Builtins

  • 循環キュー (FIFO 2d 配列)
    • 例: byte[][] Array = new byte[MAX_SIZE][BUFFER_SIZE];
    • 開始インデックス ポインターと終了インデックス ポインター
  • Writer は Array[End][] のバッファを上書きします
    • Writer は、最後までループした場合に Start をインクリメントできます
  • Reader は Array[Start][] からバッファを取得します
    • Start == End の場合、Reader はブロックします
于 2011-10-18T15:10:29.317 に答える
1

ライターを待たせたくない場合は、おそらく他の誰かが保持している可能性のあるロックを取得すべきではありません。ただし、書き込みが実際に書き出されることを確認するために、何らかの同期を実行する必要があります。通常、ほとんどの同期呼び出しにより、メモリフラッシュまたはバリア命令が実行されますが、詳細はメモリモデルによって異なりますあなたのCPUとスレッドパッケージの実装。

より適切な同期プリミティブが他にないかどうかを調べますが、プッシュが押し寄せた場合は、ライターをロックし、他の誰も使用していないロックを解除します。

読み手は、時々何かを見逃してもよいように準備しておく必要があり、何かを見逃したときにそれを検出できなければなりません。妥当性フラグと長いシーケンス カウントを各バッファに関連付け、ライターに「妥当性フラグのクリア、シーケンス カウントのインクリメント、同期、バッファへの書き込み、シーケンス カウントのインクリメント、有効性フラグの設定、同期」などを実行させます。リーダーがシーケンス カウントを読み取り、同期し、有効性フラグが true であることを確認し、データを読み取り、同期し、同じシーケンス カウントを再読み取りする場合、データが文字化けしていない可能性があります。

これを行う場合は、徹底的にテストします。私にはもっともらしいように見えますが、コンパイラからメモリモデルまでのすべての特定の実装では機能しない可能性があります。

別のアイデア、またはこれを確認する方法は、チェックサムをバッファに追加し、最後に書き込むことです。

http://www.rossbencina.com/code/lockfreeなどのロックフリーアルゴリズムの検索も参照してください。

これを行うには、ライターが眠っている読者に信号を送る方法が必要になるでしょう。これには Posix セマフォを使用できる場合があります。たとえば、特定のシーケンス番号に到達したとき、またはバッファが有効になったときに、特定のセマフォで sem_post() を呼び出すようにリーダにライタに依頼させます。

于 2011-10-18T17:56:45.660 に答える