Java mulithreading-是否有一种方法可以在读取和写入的地图中同步/锁定特定值

Question

我想实现一种可以在Java中使用线程在Java中并行完成的TOPO-SORT算法。具体而言，本文中找到的算法。

此问题的本算法的重要部分是，我们为每个节点存储的时间表值已更新如下：如果线程遇到图中的一个节点，则将读取其当前值。如果线程具有较高的值，它将替换并继续。否则它将停止。

我需要能够在一个原子操作中对特定节点进行写入和阅读。我想将值表示为映射中的值(对于每个节点(。但是，从我看到Java中地图的同步技术看来，似乎只锁定在写作上，或者锁定整个地图。如果整个地图被锁定，则性能也可能是单线螺纹。如果读取未锁定，我可以得到错误的行为。

我的目标是仅锁定特定索引。如果两个线程想读取和更新不同的节点，则可以，但是如果两个线程遇到相同的节点，我需要确保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

如果您的密钥集为静态，则可以简单地使用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。Java 8添加了许多并发方法，使您想要的东西相对直接。例如，如果您的触发代码相对较快，则可以简单地使用compute()：

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

当然，您始终可以构建一种价值类型，该价值类型将int与锁配对，但这仅对学校工作有用。实际上，锁非常昂贵，您绝对不希望内部循环中任何锁。