1

マルチスレッドの影響を受けるアルゴリズムの実行時間はどのように指定されていますか?

たとえば、CompareAndSet ループが満たされない場合があります (非常に不運な場合)。

AtomicReference<ContainerOfItems> oldContainer;

void AddItem(Item aItem)
{
    ContainerOfItems newContainer;

    do
    {
        newContainer = null;
        newContainer = new ContainerOfItems();
        newContainer.CopyContents(oldContainer);
        newContainer.Add(aItem);
    }
    while (!CompareAndSet(oldContainer, newContainer));

    oldContainer = null;
}

この例 (Java によく似ていますが、実際には疑似コードです) では、CopyContents 操作に時間がかかり、oldContainer が他のスレッドに置き換えられCompareAndSetて失敗する可能性があります。このコードの実行時間は?

4

1 に答える 1

1

このコードの実行時間は?

copyContents(...)プログラムの全体的な実行時間は、所要時間と、エラーの原因となる競合状態が発生する頻度の予測に大きく依存しますcompareAndSet(...)。これは、同時に実行されているスレッドの数によって異なります。

ただし、Big-O に関しては、ループの回数compareAndSet(...)は問題にならないのではないかと思います。たとえば、 のcopyContents(...)実行に O(N) 時間かかる場合、 を完了するために平均で 3 回ループするcompareAndSet(...)必要があり、N 回実行してすべての項目を追加すると、O(N^2) になります --定数のために 3 が脱落します。

また、同時実行性を暗示しているため、アルゴリズムがマルチスレッド化されるため、ファクター速度も向上しますが、それも一定のファクター改善にすぎず、Big-O には影響しません。copyContents(...)したがって、Big-O は、Big-O の倍数 (私が推測する) N を見ることで計算できます。

于 2012-08-21T13:55:24.867 に答える