架构师数据结构技术Day02-队列之LinkedList,ConcurrentLinkedQueue和LinkedBlockingQueue

系统管理员 2022-12-17 07:29 92阅读 0赞

### LinkedList,ConcurrentLinkedQueue和LinkedBlockingQueue比较 ###

*  LinkedList
 *  LinkedBlockingQueue
 *  ConcurrentLinkedQueue
 *  ConcurrentLinkedQueue和LinkedBlockingQueue比较

# LinkedList #

*  在多线程环境中,使用**LinkedList**并且没有做并发控制时会出现异常

public boolean add(E e) { 
    	// 调用linkLast方法,在List集合的尾部添加元素
    	linkLast(e);
    	retturn true;
    }
    
    void linkLast(E e) { 
    	final Node<E> l = last;
    	final Node<E> newNode = new Node<>(l, e, null);
    	if (l == null) { 
    		first = newNode;
    	} else { 
    		l.next = newNode;
    	}
    	// 在多线程的情况下,如果没有做并发控制,size的数量会远远大于实际的数量
    	size++
    	modCount++
    }

*  为了解决这样的问题,需要使用锁或者是**ConcurrentLinkedQueue**和**LinkedBlockingQueue**等支持添加元素为原子操作的队列

# LinkedBlockingQueue #

*  **LinkedBlockingQueue**中的**put()方法,是使用ReentrantLock**来实现添加元素的原子操作
 *  高并发中**Queue**的**add()** 方法和**offer()** 方法,是使用**CAS**算法实现的无锁的原子操作

public boolean add(E e) { 
    	return offer(e);
    }
    
    public boolean offer(E e) { 
    	checkNotNull(e);
    	final Node<E> newNode = new Node<E>(e);
    
    	for (Node<E> t = tail, p = t;;) { 
    		Node<E> q = p.next;
    		if (q == null) { 
    			// p是最后一个元素
    			if (p.caseNext(null, newNode)) { 
    				// 预期的CAS是一个线性点,e是队列中的元素,newNode是实时的
    				if (p != t) { 
    					// 一次跳两个节点
    					caseTail(t, newNode); 
    				}
    				return true;
    			}
    		} else if (p == q) { 
    			/* * 这种情况不会出现的列表中 * 如果尾数不变,也不会出现在列表中,这种情况下,需要跳到头部 * 所有活动的节点都从该头部开始 */
    			  p = (t != (t = tail)) ? t : head;
    		} else { 
    			// 每跳两次就检查尾数的更新情况
    			p = (p != t && t != (t = tail)) ? t : q;
    		}
    	}	
    }

# ConcurrentLinkedQueue #

*  **ConcurrentLinkedQueue**的**poll()方法,使用CAS**算法实现取元素的原子操作
 *  在对元素处理顺序要求不高的情况下,队列的消费者可以是多个,不会丢失任何数据

public E poll { 
    	restartFromHead;
    	for (; ;) { 
    		for (Node<E> h = head, p = h, q; ;) { 
    			E.item = p.item;
    			if (item != null && p.casItem(item, null)) { 
    				/* * 预期的CAS是一个线性点 * item会从队列中移除 */
    				 if (p != h) { 
    				 	// 每次跳动两个节点
    				 	updateHead(h, ((q = p.next) != null) ? q : p);
    				 	return item;
    				 }
    			} else if ((q = p.next) == null) { 
    				updateHead(h, p);
    				return null;
    			} else if (p == q) { 
    				continue restartFromHead;
    			} else { 
    				p = q
    			}
    		}
    	}
    }

# ConcurrentLinkedQueue和LinkedBlockingQueue比较 #

*  **实现机制:**
    
     *  **ConcurrentLinkedQueue**使用的是**CAS**算法
     *  **LinkedBlockingQueue**使用的是锁机制.但是**LinkedBlockingQueue**底层获取锁使用的是**CAS**算法
 *  **取元素:**
    
     *  **ConcurrentLinkedQueue**不支持阻塞的取元素方法,如果需要阻塞效果需要自行实现  
        \-**LinkedBlockingQueue**支持阻塞的**take()** 方法取元素
 *  **插入元素:**
    
     *  **ConcurrentLinkedQueue**没有锁,插入元素要比有锁的**LinkedBlockingQueue**快的多