任意键的锁定处理程序

Question

我有为任意键实现“锁定处理程序”的代码。给定一个key，它确保一次只能有一个线程可以process（或等于）该键（这意味着调用该externalSystem.process(key)调用）。

到目前为止，我有这样的代码：

public class MyHandler {
    private final SomeWorkExecutor someWorkExecutor;
    private final ConcurrentHashMap<Key, Lock> lockMap = new ConcurrentHashMap<>();

    public void handle(Key key) {
        // This can lead to OOM as it creates locks without removing them
        Lock keyLock = lockMap.computeIfAbsent( 
            key, (k) -> new ReentrantLock()
        );
        keyLock.lock();
        try {
            someWorkExecutor.process(key);
        } finally {
            keyLock.unlock();
        }
    }
}

我知道这段代码可能导致，OutOfMemoryError因为没有清晰的地图。

我考虑如何制作地图，该地图将累积有限数量的元素。当超过限制时，我们应该用new替换最旧的访问元素（此代码应与最旧的元素作为监视器同步）。但是我不知道如何进行回调，这将告诉我超出限制。

请分享您的想法。

聚苯乙烯

我重新阅读了任务，现在我发现我的局限性是handle不能调用8个以上线程的方法。我不知道这对我有什么帮助，但我刚才提到了。

PS2

通过@Boris提出了Spider的一种很好而简单的解决方案：

} finally {
      lockMap.remove(key);
      keyLock.unlock();
}

但是在鲍里斯（Boris）注意到我们的代码不安全之后，我们就认为它不是线程安全的，因为它破坏了行为：
让研究3个具有相同键的线程被调用：

1. 线程＃1获取了锁，现在之前 map.remove(key);
2. 线程＃2使用等号调用，因此它在线程＃1释放锁时等待。
3. 然后执行线程＃1 map.remove(key);。在此线程＃3之后调用method handle。它检查映射中是否缺少该密钥的锁，因此它将创建新的锁并获取它。
4. 线程1释放了锁，因此线程2获得了该锁。
   因此，可以为equals键并行调用线程＃2和线程＃3。但这是不允许的。
   

为了避免这种情况，在清除映射之前，我们应该阻止任何线程来获取锁，而waitwait中的所有线程都不会获取并释放锁。看起来需要足够复杂的同步，这将导致算法工作缓慢。当地图大小超过某个限制值时，也许我们应该不时清除地图。

我浪费了很多时间，但不幸的是我不知道如何实现这一目标。

Answer 1

您无需尝试将大小限制为任意值-事实证明，您可以完成这种“锁定处理程序”惯用语，而仅存储当前在映射中锁定的键的 确切 数目。

这个想法是使用一个简单的约定：成功地 将 映射 添加
到映射计数为“锁定”操作，而将其删除则作为“解锁”操作。巧妙地避免了在某些线程仍处于锁定状态和其他竞争条件的情况下删除映射的问题。

此时，value映射中的in仅用于阻止使用相同密钥到达的其他线程，并且需要等待直到删除映射为止。

这是一个示例1，其中包含CountDownLatch而不是Lock作为地图值：

public void handle(Key key) throws InterruptedException {
    CountDownLatch latch = new CountDownLatch(1);

    // try to acquire the lock by inserting our latch as a
    // mapping for key        
    while(true) {
        CountDownLatch existing = lockMap.putIfAbsent(key, latch);
        if (existing != null) {
            // there is an existing key, wait on it
            existing.await();
        } else {
            break;
        }
    }

    try {
        externalSystem.process(key);
    } finally {
        lockMap.remove(key);
        latch.countDown();
    }
}

在此，映射的生存期只有保持锁定的时间。映射将永远不会有比同时请求不同密钥更多的条目。

与您的方法的区别在于，不会“重用”映射-
每个handle调用都会创建一个新的闩锁和映射。由于您已经在进行昂贵的原子操作，因此这实际上不太可能会变慢。另一个缺点是，在有许多等待线程的情况下，当闩锁递减计数时，
所有 线程 都会 被唤醒，但是只有一个线程能够成功放入新的映射并因此获得锁-其余的则重新进入新锁的睡眠状态。

您 可以
构建此版本的另一个版本，该版本在线程进入并等待现有映射时重新使用映射。基本上，解锁线程只是对等待线程之一进行“切换”。只有一个映射将用于等待相同键的整个线程集-
它按顺序移交给每个线程。该大小仍受限制，因为没有更多线程在等待给定的映射，因此仍将其删除。

要实现这一点，您CountDownLatch可以用一个可以计算等待线程数的映射值代替。当线程进行解锁时，它首先检查是否有线程在等待，如果有，则唤醒它进行切换。如果没有线程在等待，它将“销毁”对象（即设置一个标志，表明该对象不再在映射中）并将其从映射中删除。

您需要在适当的锁定下进行上述操作，并且有一些棘手的细节。在实践中，我发现上面简短而甜美的示例非常有用。

1即时编写，未经编译且未经测试，但该想法有效。