2

可以说我有一个Set和另一个Queue。我想检查set如果它，contains(Element)如果不是。我想原子地完成这两个步骤。add(element)queue

一种明显的方法是使用synchronized块或Lock.lock()/unlock()方法。在线程争用下，这些将导致上下文切换。是否有任何简单的设计策略可以以非阻塞方式实现这一目标？可能正在使用一些原子结构？

4

4 回答 4

1

我不认为你可以依赖任何机制，除了你自己指出的那些，仅仅因为你在两个结构上运行。

对一个数据结构上的并发/原子操作有很好的支持（例如 ConcurrentHashMap 中的“如果不存在则放置”），但是对于一系列操作，您会被锁或同步块卡住。

于 2012-04-17T17:40:36.690 回答
1

由于争用案例是相关案例，您应该查看“自旋锁”。他们不会放弃 CPU，而是在一个标志上旋转，期望标志很快就会被释放。

但是请注意，真正的自旋锁在 Java 中很少有用，因为正常Lock情况非常好。请参阅此博客，其中有人第一次在 Java 中实现了自旋锁，结果发现经过一些更正（即在使测试正确之后）自旋锁与标准的东西相当。

于 2012-04-17T18:06:45.130 回答
1

对于某些操作，您可以使用所谓的“安全序列”，其中并发操作可能会重叠而不会发生冲突。例如，您可能能够将成员添加到集合（理论上）而无需同步，因为同时添加相同成员的两个线程在概念上不会相互冲突。

但是查询一个对象然后有条件地对另一个对象进行操作是一个复杂得多的场景。 如果您的序列是查询集合，然后有条件地将成员插入集合并插入队列，则查询和第一次插入可以替换为同步而不会停止的“比较和交换”操作（可能在内存访问级别除外)，然后可以根据第一次操作的成功将成员插入队列，只需要同步队列插入本身。但是，此序列留下了另一个线程可能使插入失败并且仍然找不到队列中的成员的情况。

于 2012-04-17T18:06:55.753 回答
1

您可以使用java.util.concurrent.ConcurrentHashMap来获得您想要的语义。他们有一个putIfAbsent原子插入。然后，您实际上尝试将一个元素添加到映射中，如果成功，您知道执行插入的线程是唯一拥有的线程，然后您可以安全地将项目放入队列中。这里的另一个重要点是 ConcurrentMap 上的操作确保了“先发生”语义。

ConcurrentMap<Element,Boolean> set = new ConcurrentHashMap<Element,Boolean>();
Queue<Element> queue = ...;

void maybeAddToQueue(Element e) {
    if (set.putIfAbsent(e, true) == null) {
        queue.offer(e);
    }
}

请注意，地图的实际值类型（布尔值）在这里并不重要。

于 2012-04-17T19:01:45.760 回答