ReentrantReadWriteLock readLock 超过给定的时间限制

Question

我正在努力学习并发

我在玩下面的代码：

https://leetcode.com/problems/lru-cache/discuss/724784/Detailed-Explanation-with-Threadsafe-LRU-Cache-in-Java

class LRUCache {

    /**              
         Algorithm :
         
         1. Everytime when we add the node check if it exists .
            1.1 if exists then update the value .
            1.2 move this node to head.
            1.3 if the capaicity reaches then remove node from tail .
            1.4 move the current node to head.
            
         2. Everytime when we get 
            2.1 then we need to move this node to head.
            
         3. Remove the node from tail thats it.   
          
       }
    **/
    
    private int  capacity;
    private AtomicInteger  curSize = new AtomicInteger() ;
    private ConcurrentHashMap<Integer,Node> map = new ConcurrentHashMap<>();
    private Node head = new Node();
    private Node tail = new Node();
    private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if(!map.containsKey(key))
             return -1;
        Node node = map.get(key);
        // move this current Node to front
        moveToHead(node);
        return node.val;
        
    }
    
    public void put(int key, int value) {
        // The key is already present 
        Node curNode = map.get(key);
        if(curNode != null){
           // if value exist update
            curNode.val=value;
           // moveTo head , so now its used recently 
           moveToHead(curNode);
           return;
        }
        Node newNode = new Node(value,key);
        map.put(key,newNode);
        addToHead(newNode);
        if( curSize.incrementAndGet() > capacity){
            Node nodeToRemove = tail.prev;
            removeNode(nodeToRemove);
            map.remove(nodeToRemove.key);
            curSize.decrementAndGet();
        }
    }
    
    private void moveToHead(Node node){
        // remove 
        removeNode(node);
        addToHead(node);
        
    }
    
    private void removeNode(Node node){
        try{
            readWriteLock.writeLock().lock();
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
        }finally{
            readWriteLock.writeLock().unlock();
        }
    }
    
    private void addToHead(Node node){
        try{
            readWriteLock.writeLock().lock();
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }finally{
            readWriteLock.writeLock().unlock();
        }
    }
}

class Node {
   Integer val;
   Integer key; 
   Node next ;
   Node prev;
    
   public Node(int val, int key){
         this.val = val;
         this.key = key;
    } 
    
   public Node(){
       
   } 
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

我观察到 get 方法没有任何线程安全，所以我这样修改它

    public int get(int key) {
     readWriteLock.readLock().lock();

   try{
        if(!map.containsKey(key))
             return -1;
        Node node = map.get(key);
        // move this current Node to front
        moveToHead(node);
        return node.val;
       
         }finally{
            readWriteLock.readLock().unlock();
        }   
        
    }

我认为这将确保 reads 不会在 writes 进行时发生。

但是我在Leetcode 修改了get 函数后得到了Time Limit Exceeded。谁能解释一下为什么？

Answer 1

编码为死锁：
read 锁在 get 中获取，然后最终调用 moveToHead；在 removeNode 中，由 moveToHead 调用，代码尝试获取 write 锁，但是由于 read 锁已经被锁定，所以被阻止了！

参见documentation：“写入者可以获得读锁，但反之则不然”

get也在改变列表，所以write锁比较合适

^{因为没有实现纯读操作，所以不需要ReadWriteLock，只需要一个普通就足够了}

Answer 2

I'm trying to learn concurrency

I was playing around with below code:

我强烈建议你不要从这段代码中学习并发，因为它充满了各种并发错误。

来自像这样的幼稚错误：

        if(!map.containsKey(key))
             return -1;
        Node node = map.get(key);
        // move this current Node to front
        moveToHead(node);
        return node.val;

在 containsKey 之后和 get 之前，另一个线程可能会删除密钥，结果，我们会得到 node==null 和 NullPointerExcetion。

更多 java 特定错误，例如：

curNode.val=value;

这里新值被写入 val 而没有适当的同步，这会造成所谓的数据竞争（即在其他线程中读取 val 会 return 奇怪的结果）。

修复代码的最简单方法是使每个 public 方法 synchronized 并丢弃 readWriteLock.
同样在这种情况下，将 AtomicInteger 和 ConcurrentHashMap 替换为 int 和 HashMap 是合理的（您不需要 synchronized 的并发版本）。

如果你想在java学习并发，那我推荐：

Java Concurrency in Practice — 这是 java 作者之一的书，给出了在 java 中编写并发代码的简单实用规则。（不幸的是，恕我直言，它还不够深入）
学习 Java 内存模型，这是一个 part of Java Language Specification 定义当多个 java 线程访问内存中的相同数据时会发生什么。
至少学习 happens-before 规则是至关重要的。
不幸的是，我对此一无所知book/article。
The Art of Multiprocessor Programming 了解各种无锁和无等待算法（AtomicInteger 之类的算法确实存在）。

ReentrantReadWriteLock readLock 超过给定的时间限制

ReentrantReadWriteLock readLock giving time limit exceeded

java

concurrency

multithreading

lru

reentrantlock