锁定任意键的处理程序

Question

我有代码实现任意键的"锁定处理程序".给定a 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替换最旧的访问元素(此代码应与作为监视器的最旧元素同步).但是我不知道怎么回调会说我超出限制.

请分享你的想法.

PS

我重读了这个任务,现在我发现我有限制,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调用方法之后handle.它检查映射中是否存在此密钥的锁定,因此它会创建新锁并获取它.
4. 线程#1释放锁定,因此线程#2获取它.
   因此,对于等号键,可以并行调用线程#2和线程#3.但不应该允许它.

为了避免这种情况,在映射清除之前,我们应该阻止任何线程获取锁,而waitset的所有线程都没有获取并释放锁.看起来需要足够复杂的同步,这将导致算法运行缓慢.也许我们应该在地图大小超过某些有限值时不时清除地图.

我浪费了很多时间,但不幸的是我没有想法如何实现这一目标.

Answer 1

你并不需要尝试的大小限制为某个任意值-事实证明,你能做到这种"锁处理程序"的成语,而只有存储正是当前锁定的映射按键的数量.

我们的想法是使用一个简单的约定:成功地将映射添加到映射计为"锁定"操作,并将其删除计为"解锁"操作.这巧妙地避免了在某些线程仍然锁定其他竞争条件时删除映射的问题.

此时,value映射中的映射仅用于阻止使用相同密钥到达的其他线程,并且需要等到映射被删除.

这是一个示例¹,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动态编写,未编译且未经测试,但该想法有效.