7

データ構造がどのように「非ブロッキング」になるかを理解するのに苦労しています。

「ノンブロッキング」ハッシュテーブルを作成しているとします。ある時点で、ハッシュテーブルがいっぱいになりすぎるため、より大きなテーブルに再ハッシュする必要があります。

これは、グローバルリソースであるメモリを割り当てる必要があることを意味します。したがって、データ構造自体で発生する可能性のある問題に関係なく、ヒープのグローバルな破損を防ぐために、何らかのロックを取得する必要があるようです。
しかし、それはあなたがあなたのメモリを割り当てる間、他のすべてのスレッドがブロックしなければならないことを意味します...

ここで何が欠けていますか？
（どのように）同じことをしている別のスレッドをブロックせずにメモリを割り当てることができますか？

4

4 に答える 4

4

非ブロッキング設計の 2 つの例は、楽観的設計とトランザクション メモリです。

これの考え方は - ほとんどの場合、ブロッキングは冗長です - 2 つの OP が互いに中断することなく同時に発生できるためです。ただし、2 つの OP が同時に発生し、それが原因でデータが破損した場合は、以前の状態にロールバックして再試行できます。

これらの設計にはまだロックが存在する可能性がありますが、データがロックされる時間は大幅に短くなり、OP の影響が発生する重要な時間にのみ制限されます。

于 2012-05-30T07:41:15.787 に答える
2

ほとんどの戦略には、共通する1つの基本的なパターンがあります。成功するまで、ループ内でコンペアアンドスワップ（CAS）操作を使用します。

たとえば、リンクリストで実装されたスタックについて考えてみましょう。CASと並行して作成するのは簡単なので、リンクリストの実装を選択しましたが、他の方法もあります。Cのような擬似コードを使用します。

Push(T item)
{
  Node node = new Node(); // allocate node memory
  Node initial;
  do
  {
    initial = head;
    node.Value = item;
    node.Next = initial;
  }
  while (CompareAndSwap(head, node, initial) != initial);
}

Pop()
{
  Node node;
  Node initial;
  do
  {
    initial = head;
    node = initial.Next;
  }
  while (CompareAndSwap(head, node, initial) != initial);
  T value = initial.Value;
  delete initial; // deallocate node memory
  return value;
}

上記のコードCompareAndSwapには、メモリアドレスの値を新しい値に置き換えて古い値を返す非ブロッキングアトミック操作があります。古い値が期待値と一致しない場合は、ループをスピンしてすべてを再試行します。

于 2012-05-30T15:29:05.013 に答える
2

いくつかの定義、追加情報、および非ブロッキング、ロックフリー、待機フリーの用語を区別するために、次の記事を読むことをお勧めします（長すぎるため、ここでは関連する箇所をコピーしません）。

ノンブロッキング、ロックフリー、ウェイトフリーの定義

于 2012-05-30T07:54:08.063 に答える
0

非ブロッキングとは、無期限に待機しないということであり、まったく待機しないということではありません。ノンブロッキング アルゴリズムを使用してヒープも実装されている限り、その上に他のノンブロッキング アルゴリズムを実装できます。

于 2012-05-30T07:46:51.513 に答える