4

マルチスレッド プログラミングでは、2 つ以上のスレッド/タスク間のデータ転送の同期を表すさまざまな用語を見つけることができます。

正確に言えば、あるアルゴリズムは次のとおりです。

1)Lock-Free
2)Wait-Free
3)Wait-Freedom

Lock-free の意味は理解できますが、同期アルゴリズムが Wait-Free または Wait-Freedom であると言えるのはいつですか? マルチスレッド同期用のコード (リング バッファ) をいくつか作成しましたが、Lock-Free メソッドを使用していますが、

  1. アルゴリズムは、このルーチンの最大実行時間を予測します。
  2. このルーチンを最初に呼び出すスレッドは、一意の参照を設定します (このルーチンの内部)。
  3. 同じルーチンを呼び出している他のスレッドがこの参照をチェックし、設定されている場合は、最初に関与したスレッドの CPU ティック カウント (測定時間) をカウントします。その時間が長い場合、関連するスレッドの現在の作業が中断され、彼のジョブがオーバーライドされます。
  4. 最後にタスクスケジューラから割り込まれた（リポーズされた）ためにジョブを終了していないスレッドは、自分に属していない場合は参照を確認し、再度ジョブを繰り返します。

したがって、このアルゴリズムは実際にはロックフリーではありませんが、使用中のメモリロックはなく、関連する他のスレッドは、再配置されたスレッドのジョブをオーバーライドする前に一定時間待機する (または待機しない) ことができます。

RingBuffer.InsertLeft関数を追加:

function TgjRingBuffer.InsertLeft(const link: pointer): integer;
var
  AtStartReference: cardinal;
  CPUTimeStamp    : int64;
  CurrentLeft     : pointer;
  CurrentReference: cardinal;
  NewLeft         : PReferencedPtr;
  Reference       : cardinal;
label
  TryAgain;
begin
  Reference := GetThreadId + 1;                 //Reference.bit0 := 1
  with rbRingBuffer^ do begin
TryAgain:
    //Set Left.Reference with respect to all other cores :)
    CPUTimeStamp := GetCPUTimeStamp + LoopTicks;
    AtStartReference := Left.Reference OR 1;    //Reference.bit0 := 1
    repeat
      CurrentReference := Left.Reference;
    until (CurrentReference AND 1 = 0)or (GetCPUTimeStamp - CPUTimeStamp > 0);
    //No threads present in ring buffer or current thread timeout
    if ((CurrentReference AND 1 <> 0) and (AtStartReference <> CurrentReference)) or
      not CAS32(CurrentReference, Reference, Left.Reference) then
      goto TryAgain;
    //Calculate RingBuffer NewLeft address
    CurrentLeft := Left.Link;
    NewLeft := pointer(cardinal(CurrentLeft) - SizeOf(TReferencedPtr));
    if cardinal(NewLeft) < cardinal(@Buffer) then
      NewLeft := EndBuffer;
    //Calcolate distance
    result := integer(Right.Link) - Integer(NewLeft);
    //Check buffer full
    if result = 0 then                  //Clear Reference if task still own reference
      if CAS32(Reference, 0, Left.Reference) then
        Exit else
        goto TryAgain;
    //Set NewLeft.Reference
    NewLeft^.Reference := Reference;
    SFence;
    //Try to set link and try to exchange NewLeft and clear Reference if task own reference
    if (Reference <> Left.Reference) or
      not CAS64(NewLeft^.Link, Reference, link, Reference, NewLeft^) or
      not CAS64(CurrentLeft, Reference, NewLeft, 0, Left) then
      goto TryAgain;
    //Calcolate result
    if result < 0 then
      result := Length - integer(cardinal(not Result) div SizeOf(TReferencedPtr)) else
      result := cardinal(result) div SizeOf(TReferencedPtr);
  end; //with
end; { TgjRingBuffer.InsertLeft }

ここでRingBufferユニットを見つけることができます: RingBuffer、CAS 関数: FockFreePrimitives、およびテスト プログラム: RingBufferFlowTest

4

2 に答える 2

1

私はこれに取り組むつもりですが、正式に訓練されたわけではなく、それが宿題であるかどうかは本当に気にしません.opが尋ねるのは「どのアルゴリズム」を決定するかです.実行タプルを含む - まさにシステムプログラミングがとりわけ対処しなければならない種類のもの

  1. 1) アルゴリズムは、このルーチンの最大実行時間を予測します。

データセットのサイズと、データセットに適用されるデータ構造の「O」を決定する必要があります。これには、予期せぬ瞬間に大混乱を引き起こす「退化したケース」（計画していなかったもの）が含まれる可能性があります。したがって、これ以上の詳細は省きますが、既知の障害モードがあり、「週末を台無しにする」ことなく回復する優れた「一般的なケース」のアプローチを選択しますあなたが尋ねる種類の質問に対処する書面。

  1. 2) 最初にこのルーチンを呼び出すスレッドは、一意の参照を設定します。これは、このルーチン内にあることを意味します。

ここにはいくつかの言語の壁がありますが、あなたが求めているのは、コード実行パス (一連の命令) がそのデータセットへの「一意の」「参照」で始まるということだと思います。したがって、一意の参照とはまさにそれを意味します。標準辞書でその定義を読み直してください。（陳腐にするつもりはありません。それは私がここで見ているものです）

  1. 3) 同じルーチンを呼び出している他のスレッドは、この参照をチェックし、設定されている場合は、最初に関与したスレッドの CPU ティック カウント (測定時間) をカウントします。その時間が長い場合、関連するスレッドの現在の作業が中断され、彼のジョブがオーバーライドされます。

参照カウント。よく勉強してください - 読んでコーディングを続けてください。それを解決します。期限切れのスレッドの完了を中断すると、目に見えない障害モードが発生します。正直なところ、（スレッドまたはプロセスの）実際のスケジューリングを行うことは、そのタスクに対応するように設計されたハードウェアでのみ正しく行われます。「アセンブリの最適化」の投稿は、これが可能なレベルで機能します。「AVL」ゼロページアルゴリズムの研究をお勧めします。ある時点で、プロセッサとスケジューリングを行う一連の命令は、問題の定義により、ある値に対して排他的ロックを取得する必要があります。一般的な秘訣は、ロックする 2 つの項目を取得しようとする 2 つのスレッドを持たないことです。他の命令ポインターからの干渉なしにオンにします。

これは困難な場合があります。特に、プログラマーではない人がプログラミング ショップに対して権限を持っている場合はそうです。

  1. 4) 最後にタスクスケジューラから割り込まれた (リポーズされた) ためにジョブを終了しなかったスレッドは、自分に属していない場合は参照を確認して、再度ジョブを繰り返します。

これは、スケジューラーのタスクです。

于 2009-10-24T20:56:47.243 に答える
1

（私は宿題の質問であるという仮定に基づいてこの質問に答えています。そうでない場合は、あなたが抱えている問題の詳細を教えてください）

Non-blocking synchronizationに関するウィキペディアの記事を読み始める必要があります。これにより、いくつかの優れた背景情報と、言及した用語の定義が提供されます。

于 2009-09-21T09:20:16.710 に答える