Java 多线程 - 有没有办法同步/锁定映射中的特定值以进行读取和写入？

Question

我想要实现一种拓扑排序算法，该算法可以使用线程在 Java 中的图形上并行完成。具体是在这篇论文中找到的算法here .

对于这个问题，这个算法的重要部分是我们为每个节点存储的调度值更新如下:如果一个线程遇到图中的一个节点，它将读取它的当前值。如果线程具有更高的值，它将替换它并继续。否则它会停在那里。

我需要能够在一个原子操作中对特定节点进行写入和读取。我想将该值表示为映射中针对 int 键 id(对于每个节点)的值。但是，据我所知，Java 中 map 的同步技术似乎要么只锁定写入，要么锁定整个 map 。如果整个 map 都被锁定，性能还不如单线程。如果读取未锁定，我会得到错误的行为。

我的目标是只锁定一个特定的索引。如果两个线程想要读取和更新不同的节点，那没问题，但是如果两个线程遇到同一个节点，我需要确保每个操作 read -> check -> update or stop原子地发生。我希望避免的具体情况是:

Thread_1 (val 5) read g_1 -> value is 3, trigger update
Thread_2 (val 4) read g_1 -> value is 3, trigger update
Thread_1 (val 5) lock and update g_1 -> g_1 value is 5
Thread_2 (val 4) lock and update g_1 -> g_1 value is 4

相反，我想做的是:

Thread_1 (val 5) lock g_1
Thread_2 (val 4) wait for g_1
Thread_1 (val 5) read g_1 -> value is 3, update g_1 -> g_1 value is 5
Thread_1 (val 5) release g_1
Thread_2 (val 4) lock g_1
Thread_2 (val 4) read g_1 -> value is 5, do nothing
Thread_2 (val 4) release g_1

Answer 1

如果您的 key 集是静态的，那么您可以简单地使用 AtomicInteger值。你可以使用 compareAndSet像这样:

atomicValue = map.get(key);
while (true) {
    value = atomicValue.get();
    if (value < myThreadNumber) {
        if (value.compareAndSet(value, myThreadNumber) {
            // successfully increased the thread number
            triggerUpdate();
            break;
        } // else value update failed, loop back to try again.
    } else {
        break;
    }
}

或者，您可以使用 ConcurrentHashMap它不会锁定整个 map 。 Java 8 增加了很多并发方法，让你想要的东西相对直接。例如，如果您的触发代码相对较快，那么您可以简单地使用 compute() :

map.compute(key, (key, value) -> {
    if (value < myThreadNumber) {
        triggerUpdate();
        return myThreadNumber;
    }
    return value; // no changes
})

当然，您始终可以构造一个值类型，将您的 int 与锁配对，但这仅对学校作业有用。在实践中，锁是如此昂贵，你肯定不希望在你的内部循环中使用任何锁。