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(...)并不重要。例如，如果 acopyContents(...)需要 O(N) 时间来运行，平均它必须循环 3 次才能完成compareAndSet(...)，而你运行它 N 次来添加所有项目，它是 O(N^2) -- 3 由于常数而退出。

此外，因为您暗示并发，也会有一个因素速度的提高，因为算法将是多线程的，但这也只是一个恒定的因素改进，不会影响 Big-O。因此，可以通过查看 Big-O 的copyContents(...)次数（我假设）N来计算 Big-O。

于 2012-08-21T13:55:24.867 回答