問題タブ [lockless]

ロックレス キューの実装を使用して、事前に割り当てられた一連のバッファーへのポインターを格納しているときに、あるスレッドがバッファーの使用を開始している間に、一部のバッファーが 1 つのスレッドによってまだ書き込まれていることがわかりました。バッファーの書き込みと読み取りをメモリバリアで既に保護していますが、機能していないようです。

スレッド 1 ループ:

スレッド 2 ループ:

しばらくすると出力として「失敗」が表示されます。これは、スレッド 2 が A および B ブロックの順序付けられていない実行を確認することを意味します。これらを順番にやっていきたいと思います。どうすれば修正できますか？(time_diff は常に正の数を返すと仮定します)

キューのソース: http://pastebin.com/raw.php?i=PFBzMPPF

ソース全体: https://docs.google.com/file/d/0B8gY3VVJJr1IMktobnhYelBva2c/edit?usp=docslist_api

私はロックレスの c++11 fifo バッファに取り組んできました。そして、私はほとんどそれを手に入れました。しかし、1つの小さな詳細が私を良くしました。バッファには、次が指すヘッドがあります。

タイプの：

そして、農産物があります：

そして消費します：

機能。

すべてうまくいくようです。しかし、私は1つの欠陥があると考えています。.a の実行中にすべてのノードが消費された場合produce。データは最後の要素に追加されます。要素は既に削除されていますが。

より正確には、この行が実行された場合:

ロードされたノードはゼロではありませんでした。最後のノードの次の要素が変更されます。その間にノードが削除されているかどうかに関係なく。ポインタが共有されているため、プロデュース関数が実行されている限り、ノードは物理的に削除されません。

ただし、メイン ポインターは NULL に設定されます。したがって、プロデュース関数が終了するとすぐに、新しいノードが削除されます。

誰かがこの問題の解決策を知っているでしょうか:)？

この長い投稿を前もってお詫びしますが、おそらくお分かりのように、私はかなり長い間これについて考えてきました。頭が爆発する前に、他の人からの意見が必要だと感じています :-)

私は、次の基準をすべて満たすゲーム エンジンを構築するさまざまな方法を、しばらくの間実験してきました。

• オブジェクトの更新とオブジェクトのレンダリングの完全な分離
• 完全決定論
• 個々の速度での更新とレンダリング
• 共有リソースをブロックしない

オブジェクトの更新とオブジェクトのレンダリングの完全な分離

オブジェクトの更新とオブジェクトのレンダリングを分離することは、グラフィックス API にデータを送信し、バッファーをスワップしながら、リソースを最適に使用するために不可欠なようです。CPU の複数のコアを使用するために完全な並列処理を確保したい場合でも、この分離を管理する必要があるようです。

完全決定論

多くのゲーム タイプ、特にマルチプレイヤー バージョンでは、完全な決定論を保証する必要があります。そうしないと、プレイヤーは同じゲームのさまざまな状態を経験することになり、ゲーム ロジックが事実上壊れてしまいます。ゲームのリプレイにも決定論が必要です。また、同じ開始条件と入力が与えられた場合、シミュレーションの各実行が毎回同じ結果を生成することが重要な他の目的にも役立ちます。

個々の速度での更新とレンダリング

シミュレーションをレンダリング速度 (さまざまなモニターのリフレッシュ レート、グラフィックス アダプターの速度など) に依存させることはできないため、これは実際には完全な決定論の前提条件です。最適な状態では、更新速度は特定の固定間隔 (たとえば、1 秒あたり 25 回の更新 - 更新の種類によってはそれより短い間隔) に設定する必要があり、レンダリング速度は、クライアントのモニターのリフレッシュ レート/グラフィック アダプターが許可する速度に設定する必要があります。

これは、更新速度よりも高いレンダリング速度を許可する必要があることを意味します。それは無駄のように聞こえますが、追加されたレンダリング サイクルが無駄にならないようにするための既知のトリック (内挿/外挿) があります。

ただし、更新速度よりも遅いレンダリング速度も許可する必要がありますが、これが実際に更新サイクルの無駄になる場合でも、少なくとも追加された更新サイクルがすべてユーザーに表示されるわけではありません。ただし、これは、クライアントの 1 つでのレンダリングが何らかの理由で突然遅くなった場合でも、スムーズなマルチプレイヤー エクスペリエンスを確保するために必要です。

共有リソースをブロックしない

上記の他の基準を実装する場合は、レンダリングが更新を待機することを許可しないこと、またはその逆を許可しないことにも従う必要があります。もちろん、2 つの異なるスレッドがリソースへのアクセスを共有し、1 つのスレッドがこれらのリソースの一部を更新している場合、ブロッキングが発生しないことを保証することは不可能です。ただし、このブロッキングを最小限に抑えることは可能です。たとえば、更新されたオブジェクトのキューと以前にレンダリングされたオブジェクトのキューの間でポインター参照を切り替える場合などです。

そう...

ここにいるすべての熟練した人々への私の質問は次のとおりです。私はあまりにも多くを求めていますか?

私は多くのサイトでこれらのさまざまなトピックのアイデアについて読んでいます。しかし、私が見た提案からは常に、どちらかの部分が除外されているようです。その理由は、妥協せずにすべてを手に入れることができないからかもしれません。

私はこの一見一般的なクエストをずっと前にこのスレッドで考えていたときに始めました: ループ戦略のレンダリングについての考え

当時の私の最初の素朴な仮定は、更新と読み取りが同時に発生しても問題にならないというものでした。この変動オブジェクトの状態は非常に小さいため、あるオブジェクトが他のオブジェクトよりも一歩先を行っていても気付かないはずだからです。

今は少し賢くなりましたが、それでも時々混乱します。

私の希望をすべて叶える方法の最も有望で詳細な説明は次のとおりです 。http://blog.slapware.eu/game-engine/programming/multithreaded-renderloop-part1/レンダラーが待機なしでレンダリング用の新しいキューを常に選択できるようにします (ポインター参照の切り替え中のおそらくマイクロ秒を除く)。同時に、アップデーターは、次の状態ツリーを構築するために必要な 2 つのキュー (次の状態を作成/更新するための 1 つのキューと、前の状態を読み取るための 1 つのキュー) に常にアクセスできます。良い）。

私は最近、これのサンプル実装を作成する時間を見つけました。これは非常にうまく機能しますが、2 つの問題があります。

• 1 つは、関連するすべてのオブジェクトへの複数の参照を処理する必要があるという小さな問題です。
• もう 1 つはもっと深刻です (私があまりにも困窮している場合を除きます)。そしてそれは、内挿ではなく外挿を使用して、画面のリフレッシュ レートが速い場合に、視覚的に快適な状態の表現を維持するという事実です。どちらの方法も、しっかりと計算されたオブジェクトの状態から逸脱した状態を示す仕事をしますが、予測が現実を表していない場合、外挿ははるかに目に見えるアーティファクトを生成するように私には思えます. 私の立場はこれによってサポートされているようです : http://gafferongames.com/networked-physics/snapshots-and-interpolation/ 2 つの既知の状態の間の中間状態を計算するために、レンダラーは常に 2 つのキューに読み取りアクセスできる必要があります。

そこで私は、slapware-blog で提案されている 3 状態モデルを拡張して、外挿ではなく内挿を利用することをいじっていました。同時に、複数参照構造を単純化しようとしました。出来そうな気もしますが、値段が高いのではないかと思います。必要なすべての目標を達成するために

• レンダラーによって排他的に保持される 2 つのキュー (または状態) (これらは、読み取り専用の目的で別のスレッドによって使用される可能性がありますが、レンダリング中に更新または切り替えられることはありません
• 現在のシーンのレンダリングが完了すると、レンダラーに切り替える準備ができている最新の更新された状態を持つ 1 つのキュー (または状態)
• 次のフレームがアップデーターによって構築/更新される 1 つのキュー (または状態)
• 最後に構築/更新されたフレームのコピーを含む 1 つのキュー (または状態)。これはレンダラーに最後に送信された状態と同じであるため、このキュー/状態は、前の状態を読み取るためのアップデータと、状態をレンダリングするためのレンダラーの両方からアクセスできる必要があります。

つまり、この設計をスムーズに、ロックなしで、決定論的に実行し続けることができるように、レンダリング ステートのコピーを常に 4 つ保持する必要があります。

私はこれを考えすぎているのではないかと恐れています。したがって、私を地面に引き戻すようにアドバイスしたり、改善できること、デザインの批評、またはこれらの目標を達成する方法を説明する優れたリソースへの参照、またはこれがなぜそうでないのかについてのアドバイスがあれば良いアイデアです - お願いします:-)

だから、私が持っているstruct A { int val1; int val2}; としますstd::queue<A> fifo

2 つのスレッド、リーダー スレッド: A からすべてのコンテンツを読み取り、それをクリアします。書き込みスレッド: 一度に 1 つの A をキューに書き込みます。

std::queue は、1 つのリーダーと 1 つのライターでロックレススレッド セーフな fifo コンテナーを維持するのに十分ですか? そうでない場合、他の stl コンテナーは機能しますか? dequeue は、std::queue の基礎となるデフォルトです。

ldrex/strexこの値は、(素晴らしい)同期プリミティブを使用するデータ構造がメモリ内でどのように配置されるかに影響するため、興味があります。

ARMv7-M アーキテクチャ リファレンスには次のように書かれています。

タグ付きメモリ ブロックのサイズは、排他予約グラニュールと呼ばれます。Exclusives 予約グラニュールは、次の間で実装定義されています。

• == 2 を使用した実装では、1 つの単語
• == 11 の実装では 512 語。

したがって、STM32F407 などの特定の実装では、使用されている値を見つけることができるはずです。しかし、私が調べたさまざまな文書では、できません。

誰か知っていますか？また、どうやって見つけましたか？

Albahari の Threading in C#を読んでいるときに、「ロック フリー アップデート」パターンSpinWaitがサイクルの最後に a を使用していることに気付きました。

spinWait.SpinOnce()最後の呼び出しに注意してください。この呼び出しは、シングルスレッド環境でスレッドを生成するためだけに必要ですか、それとも別の目的がありますか?

複数のリーダー スレッドと 1 つのライター スレッドがあり、リーダーが少し古いデータを読み取ることができるシナリオでは、以下に示すように、最も基本的な形式の疑似コードでロックレス制御フローを作成しました。

MAX_READING_DURATIONへの呼び出しが完了するまでにかかる最大時間と、 への呼び出しがread()完了するまでにかかるMIN_WRITING_DURATION最小時間を呼び出してみましょうwrite()。

現在、shared_pointerアトミックであることが保証されている限りMAX_READING_DURATION < ELEMENT_COUNT(ARRAY) * MIN_WRITING_DURATION、このスキームは完全に安全です。

それとも私は何かを見落としていますか？そうでない場合は、これはよく知られていることだと確信しており、適切な用語を知りたいので、このアプローチを他の人に説明/推奨するときにそれを使用できます。

Linux カーネルのロックレス リストを理解しようとしています。これは llist.h で定義されています。リストを定義するために、なぜ 2 つの構造体があるのですか。

次のノードへのポインターを持つ構造体を 1 つだけ持たないのはなぜですか? これは、カーネルでの二重リンク リストの実装に似ています。