`
uule
  • 浏览: 6351986 次
  • 性别: Icon_minigender_1
  • 来自: 一片神奇的土地
社区版块
存档分类
最新评论

LinkedBlockingQueue + 单向链表基本结构

 
阅读更多

LinkedBlockingQueue是一个单向链表结构的队列,也就是只有next,没有prev。如果不指定容量默认为Integer.MAX_VALUE。通过putLock和takeLock两个锁进行同步,两个锁分别实例化notFull和notEmpty两个Condtion,用来协调多线程的存取动作。其中某些方法(如remove,toArray,toString,clear等)的同步需要同时获得这两个锁,此时存或者取操作都会不可进行,需要注意的是所有需要同时lock的地方顺序都是先putLock.lock再takeLock.lock,这样就避免了可能出现的死锁问题。

takeLock实例化出一个notEmpty的Condition,putLock实例化一个notFull的Condition,两个Condition协调即时通知线程队列满与不满的状态信息。

 

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {

    /**
     * 节点数据结构
     */
    static class Node<E> {
        /** The item, volatile to ensure barrier separating write and read */
        volatile E item;
        Node<E> next;
        Node(E x) { item = x; }
    }

    /** 队列的容量 */
    private final int capacity;

    /** 持有节点计数器 */
    private final AtomicInteger count = new AtomicInteger(0);

    /** 头指针 */
    private transient Node<E> head;

    /** 尾指针 */
    private transient Node<E> last;

    /** 用于读取的独占锁*/
    private final ReentrantLock takeLock = new ReentrantLock();

    /** 队列是否为空的条件 */
    private final Condition notEmpty = takeLock.newCondition();

    /** 用于写入的独占锁 */
    private final ReentrantLock putLock = new ReentrantLock();

    /** 队列是否已满的条件 */
    private final Condition notFull = putLock.newCondition();

    private void signalNotEmpty() {
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lock();
        try {
            notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
    }

    private void signalNotFull() {
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            notFull.signal();
        } finally {
            putLock.unlock();
        }
    }
       //插入数据到链尾
    private void insert(E x) {
        last = last.next = new Node<E>(x);
    }
       //从链头取数据
    private E extract() {
        Node<E> first = head.next;
        head = first;
        E x = first.item;
        first.item = null;
        return x;
    }

    private void fullyLock() {
        putLock.lock();
        takeLock.lock();
    }

    private void fullyUnlock() {
        takeLock.unlock();
        putLock.unlock();
    }

    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node<E>(null);  //注意初始化时head/last地址相同,数据都为null
					// 其实就相当于只有一个节点
    }

   ...
}

 这里仅仅展示部分源码,主要的方法在后面的分析中列出。分析之前明确一个最基本的概念。天天念叨着编写线程安全的类,什么是线程安全的类?那就是类内共享的全局变量的访问必须保证是不受多线程形式影响的。如果由于多线程的访问(改变,遍历,查看)而使这些变量结构被破坏或者针对这些变量操作的原子性被破坏,则这个类的编写不是线程安全的。 


    明确了这个基本的概念就可以很好的理解这个Queue的实现为什么是线程安全的了。在LinkedBlockingQueue的所有共享的全局变量中,final声明的capacity在构造器生成实例时就成了不变量了。而final声明的count由于是AtomicInteger类型的,所以能够保证其操作的原子性。剩下的final的变量都是初始化成了不变量,并且不包含可变属性,所以都是访问安全的。那么剩下的就是Node类型的head和last两个可变量。所以要保证LinkedBlockingQueue是线程安全的就是要保证对head和last的访问是线程安全的。 

    首先从上面的源码可以看到insert(E x),extract()是真正的操作head,last来入队和出对的方法,但是由于是私有的,所以不能被直接访问,不用担心线程的问题。实际入队的公开的方法是put(E e),offer(E e)和offer(E e, long timeout, TimeUnit unit)。put(...)方法与offer(...)都是把新元素加入到队尾,所不同的是如果不满足条件put会把当前执行的线程扔到等待集中等待被唤醒继续执行,而offer则是直接退出,所以如果是需要使用它的阻塞特性的话,不能直接使用poll(...)。 
    
    put(...)方法中加入元素的操作使用this.putLock来限制多线程的访问,并且使用了可中断的方式: 

  1. public void put(E e) throws InterruptedException {  
  2.         if (e == nullthrow new NullPointerException();  
  3.         int c = -1;  
  4.         final ReentrantLock putLock = this.putLock;  
  5.         final AtomicInteger count = this.count; //----------------a  
  6.         putLock.lockInterruptibly();//随时保证响应中断 //--------b  
  7.         try {  
  8.             //*****************************(1)*********************************  
  9.             try {  
  10.                 while (count.get() == capacity)  
  11.                     notFull.await();  
  12.             } catch (InterruptedException ie) {  
  13.                 notFull.signal(); // propagate to a non-interrupted thread  
  14.                 throw ie;  
  15.             }  
  16.            //*****************************end*********************************  
  17.             insert(e);//真正的入队操作  
  18.            //********************(2)**********************  
  19.             c = count.getAndIncrement();  
  20.             if (c + 1 < capacity)  
  21.                 notFull.signal();  
  22.             //******************end**********************  
  23.         } finally {  
  24.             putLock.unlock();  
  25.         } //-------------------------c  
  26.         if (c == 0//---------------d  
  27.             signalNotEmpty();  
  28. }  


代码段(1)是阻塞操作,代码段(2)是count递增和唤醒等待的操作。两者之间的insert(e)才是入队操作,其实际是操作的队尾引用last,并且没有牵涉到head。所以设计两个锁的原因就在这里!因为出队操作take(),poll()实际是执行extract()仅仅操作队首引用head。增加了this.takeLock这个锁,就实现了多个不同任务的线程入队的同时可以进行出对的操作,并且由于两个操作所共同使用的count是AtomicInteger类型的,所以完全不用考虑计数器递增递减的问题。假设count换成int,则相应的putLock内的count++和takeLock内的count--有可能相互覆盖,最终造成count的值被腐蚀,故这种设计必须使用原子操作类。 
      我之前说过,保证类的线程安全只要保证head和last的操作的线程安全,也就是保证insert(E x)和extract()线程安全即可。那么上面的put方法中的代码段(1)放在a,b之间,代码段(2)放在c,d之间不是更好?毕竟锁的粒度越小越好。单纯的考虑count的话这样的改变是正确的,但是await()和singal()这两个方法执行时都会检查当前线程是否是独占锁的那个线程,如果不是则抛出java.lang.IllegalMonitorStateException异常。而这两段代码中包含notFull.await()和notFull.signal()这两句使得(1),(2)必须放在lock保护块内。这里说明主要是count本身并不需要putLock或者takeLock的保护,从   

  1. public int size() {  
  2.         return count.get();  
  3. }  


可以看出count的访问是不需要任何锁的。而在put等方法中,其与锁机制的混用很容易造成迷惑。最后put中的代码d的作用主要是一个低位及时通知的作用,也就是队列刚有值试图获得takeLock去通知等待集中的出队线程。因为c==0意味着count.getAndIncrement()原子递增成功,所以count > 0成立。类似作用的代码: 

  1. if (c == capacity)  
  2.        signalNotFull();  


在take和poll中也有出现,实现了高位及时通知。 
    分析完了put,对应的offer,take,poll方法都是类似的实现。

 

public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        final AtomicInteger count = this.count;
        if (count.get() == capacity)
            return false;
        int c = -1;
        final ReentrantLock putLock = this.putLock;
        putLock.lock();
        try {
            if (count.get() < capacity) {
                insert(e);
                c = count.getAndIncrement();
                if (c + 1 < capacity)
                    notFull.signal();
            }
        } finally {
            putLock.unlock();
        }
        if (c == 0)
            signalNotEmpty();
        return c >= 0;
    }

 

 

public E take() throws InterruptedException {
        E x;
        int c = -1;
        final AtomicInteger count = this.count;
        final ReentrantLock takeLock = this.takeLock;
        takeLock.lockInterruptibly();
        try {
            try {
                while (count.get() == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to a non-interrupted thread
                throw ie;
            }

            x = extract();
            c = count.getAndDecrement();
            if (c > 1)
                notEmpty.signal();
        } finally {
            takeLock.unlock();
        }
        if (c == capacity)
            signalNotFull();
        return x;
    }
 

下面看看遍历队列的操作: 

  1. public Object[] toArray() {  
  2.         fullyLock();  
  3.         try {  
  4.             int size = count.get();  
  5.             Object[] a = new Object[size];  
  6.             int k = 0;  
  7.             for (Node<E> p = head.next; p != null; p = p.next)  
  8.                 a[k++] = p.item;  
  9.             return a;  
  10.         } finally {  
  11.             fullyUnlock();  
  12.         }  
  13. }  


这个方法很简单主要是要清楚一点:这个操作执行时不允许其他线程再修改队首和队尾,所以使用了fullyLock去获取putLock和takeLock,只要成功则可以保证不会再有修改队列的操作。然后就是安心的遍历到最后一个元素为止了。 

    另外在offer(E e, long timeout, TimeUnit unit)这个方法中提供了带有超时的入队操作,如果一直不成功的话,它会尝试在timeout的时间内入队: 

  1. for (;;) {  
  2.      ...//入队操作  
  3.      if (nanos <= 0)  
  4.          return false;  
  5.      try {  
  6.           nanos = notFull.awaitNanos(nanos);  
  7.      } catch (InterruptedException ie) {  
  8.            notFull.signal(); // propagate to a non-interrupted thread  
  9.            throw ie;  
  10.      }  
  11. }  


其内部循环使用notFull.awaitNanos(nanos)方法反复的计算剩余时间的大概值用于实现延时功能。nanos<=0则放弃尝试,直接退出。 

    整体而言,LinkedBlockingQueue的实现还是很清晰的。这些看似复杂的数据结构的实现实质都是多线程的基础的综合应用。就好像数学中千变万化的难题其实都是基础公式的组合一样,如果有清晰的基础认知,还是能找到自己分析的思路的。

来源:http://yanxuxin.iteye.com/blog/582162

 

 

JDK:

方法区别:

 

 boolean offer(E e) 

          将指定元素插入到此队列的尾部(如果立即可行且不会超出此队列的容量),在成功时返回 true,如果此队列已满,则返回 false。 

 boolean offer(E e, long timeout, TimeUnit unit) 

          将指定元素插入到此队列的尾部,如有必要,则等待指定的时间以使空间变得可用。 

 void put(E e) 

          将指定元素插入到此队列的尾部,如有必要,则等待空间变得可用。 


 E peek() 

          获取但不移除此队列的头;如果此队列为空,则返回 null。 

 E poll() 

          获取并移除此队列的头,如果此队列为空,则返回 null。 

 E poll(long timeout, TimeUnit unit) 

          获取并移除此队列的头部,在指定的等待时间前等待可用的元素(如果有必要)。 

 E take() 

          获取并移除此队列的头部,在元素变得可用之前一直等待(如果有必要)。 


 boolean remove(Object o) 

          从此队列移除指定元素的单个实例(如果存在)。 

 int size() 

          返回队列中的元素个数。 


 Object[] toArray() 

          返回按适当顺序包含此队列中所有元素的数组。 

T[]  toArray(T[] a) 

          返回按适当顺序包含此队列中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。 

 String toString() 

          返回此 collection 的字符串表示形式。 


 

 

问题思考:为什么需要用两个锁?

 

单向链表数据结构:

 

package tags;

import java.util.Iterator;

/*
 * 单向链表从头部插数据,从尾部取数据
 * @author Robby
 */
public class SingleLinked<E> {

	class Node<E>{
		volatile E item;
		Node<E> next;
		Node(E x){
			item = x;
		}
	}
	
	private Node<E> head;
	private Node<E> last;
	private static int count;
	
	SingleLinked(){
		last = head = new Node<E>(null);
			//初始化head/last,此时这两个地址相同,其实就是一个节点
	}
	
	private void insert(E e){
		Node<E> newNode = new Node<E>(e);
		last.next = newNode;
		last = last.next;
		count++;
	}
	
	private E extract(){
		//Node<E> first = head.next; //head为null
		//E e = first.item;
		head = head.next;   //只一句就可以
		//first.item = null;
		count--;
		return null;
	}
	
	private void remove(E e){
		if(e == null) return;
		Node<E> pre = head;  //这两个变量用于记录e的节点和前节点
		Node<E> current = head.next;
		/*for(Node<E> p = current; p != null; p = p.next){
			if(p.item.equals(e)){
				pre.next = current.next;
				count--;
				break;
			}
			pre = p;
			current = p.next;
		}*/
		while(current != null){
			if(current.item.equals(e)){
				pre.next = current.next;
				count--;break;
			}
			pre = current;
			current = current.next;
		}
	}
	
	public E peek(){  //从头部弹出一个数据
		Node<E> first = head.next;
		if(first == null) return null;
		return first.item;
	} 
	
	public Object[] toArray(){
		if(count == 0) return null;
		Object[] o = new Object[count];
		int i = 0;
		for(Node<E> p = head.next; p!=null; p = p.next){
			o[i++] = p.item;
		}
		return o;
	}
	
	public void clear(){
		head.next = null;
	    last = head;
		count = 0;
	}
	
	//遍历方法是通过新建一个Iterator实现的
	public Iterator<E> iterator(){
		return new Itr();
	}
	
	private class Itr implements Iterator{

		private Node<E> current;
		private E element;
		
		Itr(){
			current = head.next;
			element = current.item;
		}
		
		public boolean hasNext() {
			return current != null;
		}

		public E next() {
			E e = element;
			current = current.next;
			if(current != null)
				element = current.item;
			return e;
		}

		public void remove() {
			
		}
		
	}
	
	
	public String toString(){
		Object[] o = toArray();
		String str = "";
		if(o == null) return str;
		for(Object ob : o){
			str += ob != null && !ob.toString().equals("") ? ob.toString()+"," : "";
		}
		return str.substring(0,str.length() - 1);
	}
	
	
	
	@SuppressWarnings("unchecked")
	public  static void main(String[] args){
		SingleLinked slink = new SingleLinked();
		slink.insert(1);
		System.out.println("count:"+count+" |"+slink.toString());
		slink.insert(2);
		System.out.println("count:"+count+" |"+slink.toString());
		slink.insert(3);
		System.out.println("count:"+count+" |"+slink.toString());
		
		slink.extract();
		System.out.println("count:"+count+" |"+slink.toString());
		slink.insert(5);
		System.out.println("count:"+count+" |"+slink.toString());
		//slink.extract();
		//System.out.println("count:"+count+" |"+slink.toString());
		
		//slink.clear();
		/*slink.remove(3);
		System.out.println("count:"+count+" |"+slink.toString());
		slink.remove(5);
		System.out.println("count:"+count+" |"+slink.toString());
		slink.remove(2);
		System.out.println("count:"+count+" |"+slink.toString());*/
		Iterator it = slink.iterator();
		while(it.hasNext()){
			System.out.print(it.next()+" ");
		}
	}
	
}

 基本结构其实并不复杂,LinkedBlockingQueue是在此基础上加入了多线程的实现。

 

 

 

分享到:
评论

相关推荐

    linkedblockingqueue

    1. 链表结构:`LinkedBlockingQueue`内部由两个节点类`Node`组成,一个表示元素,另一个表示等待的线程。这种设计使得插入和移除操作的时间复杂度为O(1)。 2. 阻塞机制:`LinkedBlockingQueue`通过`Lock`和`...

    JDK容器学习之Queue:LinkedBlockingQueue

    与数组结构的`ArrayBlockingQueue`不同,`LinkedBlockingQueue`使用单向链表实现,这使得插入和删除操作的效率相对较高,因为它们只需要修改相邻节点的引用。链表的头节点`head`不包含有效数据,而尾节点`last`保存...

    并发容器之ArrayBlockingQueue和LinkedBlockingQueue实现原理详解

    ArrayBlockingQueue和LinkedBlockingQueue是Java并发容器中两个常用的阻塞队列实现,分别基于数组和链表存储元素。它们都继承自AbstractQueue类,并实现了BlockingQueue接口,提供了线程安全的队列操作。 ...

    几个常用的数据结构(1.0)

    ArrayList基于动态数组,适合随机访问,而LinkedList基于双向链表,适合频繁的插入和删除操作。选择哪种实现取决于具体的应用需求。 3. **HashMap**:HashMap是一种键值对的数据结构,它允许快速查找、添加和删除...

    并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue用法

    `ConcurrentLinkedQueue` 是 Java 并发包 `java.util.concurrent` 提供的一个高性能的线程安全队列实现,基于链表结构,它适用于对吞吐量有较高要求的场景。`ConcurrentLinkedQueue` 不提供容量限制,并且在队列为空...

    LinkedBlockingQueue 和 ConcurrentLinkedQueue的区别.docx

    在Java并发编程中,队列是一种重要的数据结构,尤其在多线程环境下的任务调度和数据传递中扮演着关键角色。LinkedBlockingQueue和ConcurrentLinkedQueue是Java并发包中两个常用的线程安全队列,它们各有特点,适用于...

    LinkedBlockingQueuejava.pdf

    Java中的`LinkedBlockingQueue`是`java.util.concurrent`包下的一种线程安全的阻塞队列,它是基于链表结构实现的,具有很好的性能表现。这种队列在多线程环境下的并发操作中被广泛使用,因为它允许生产者线程向队列...

    详细分析Java并发集合LinkedBlockingQueue的用法

    链表的头节点head和尾节点last是在LinkedBlockingQueue对象创建的时候被初始化的,head节点不存储数据,它指向的下一个节点才真正存储了链表中第一个数据,而last节点确实储存了链表最后一个数据。 二、插入和删除...

    元素唯一的LinkedBlockingQueue阻塞队列

    在Java并发编程中,`LinkedBlockingQueue`是一种基于链表结构的阻塞队列,它在多线程环境下的性能表现优秀,常用于实现生产者消费者模型。这个队列的一个关键特性是其内部节点的链接方式,即每个元素都是一个节点,...

    生产者/消费者模式 阻塞队列 LinkedBlockingQueue

    LinkedBlockingQueue是一个基于链表结构的阻塞队列,它实现了BlockingQueue接口,具备线程安全的特性。队列内部通过双向链表维护元素顺序,这使得插入和删除操作具有O(1)的时间复杂度。同时,作为阻塞队列,当生产者...

    阻塞队列阻塞队列阻塞队列

    LinkedBlockingQueue是基于链表结构实现的阻塞队列,其内部节点为Node类,包含元素值和指向下一个节点的引用。与ArrayBlockingQueue不同,LinkedBlockingQueue的容量可以是Integer.MAX_VALUE(即无界队列),也可以...

    构建高性能服务(一)ConcurrentSkipListMap和链表构建高性能Java Memcached

    跳跃列表的基本思想是将数据分成多个层次,每个层次都是一个有序的链表。较低层次的链表包含较少的元素,但查找速度更快。当我们搜索一个元素时,会从最高层开始,如果找到的元素不在当前层,则下移到下一层继续查找...

    java中LinkedBlockingQueue与ArrayBlockingQueue的异同

    2. **数据结构**:`LinkedBlockingQueue`内部基于链表结构实现,每次插入或删除元素都会创建或销毁`Node`对象,对于大量数据操作,可能会增加垃圾回收的压力。而`ArrayBlockingQueue`使用固定大小的数组,插入和移除...

    队列写入mysql实例

    `LinkedBlockingQueue`基于链表实现,因此插入和删除操作的时间复杂度为O(1),具有很好的性能。在本实例中,它将作为数据缓冲区,存储待写入MySQL的数据。 接着,Redis是一款非常流行的内存数据结构存储系统,它...

    数据结构(java)

    "数据结构(java)"这个主题涵盖了Java实现的各种常见数据结构,包括数组、链表、栈、队列、树、图、哈希表等,这些都是编程中不可或缺的基础工具。 1. **数组**:数组是最基础的数据结构,它允许我们存储相同类型...

    数据结构面试专题.docx

    - **数组**:是最基本的数据结构,它在内存中以连续的方式存储元素,可以通过下标快速访问。数组适用于需要快速查找但插入和删除效率低的情况。 - **栈**:是一种后进先出(LIFO)的数据结构,常用于递归、函数...

    jdk的数据结构分析1

    - **LinkedBlockingQueue**:基于链表实现,可设置无限容量。 6. **Map**:Map接口存储键值对,HashMap和ConcurrentHashMap是两种常见的实现: - **HashMap**:非同步,提供快速的查找,基于哈希表实现。 - **...

Global site tag (gtag.js) - Google Analytics