Java多线程【Java面试题】

Java多线程【Java面试题】

Java多线程【Java面试题】

• • 一、创建线程的方式？
  • • 1、继承Thread类创建
    • 2、通过Runnable接口创建线程类
    • 3、使用Callable和Future创建线程
  • 二、线程是状态
  • 三、Java 多线程加锁的方式
  • • • 1.可重入锁
      • 2.可中断锁
      • 3.公平锁
      • 4.读写锁
  • 四、DeplayQueue延时无界阻塞队列
  • 五、并发（Collection）队列-非阻塞队列
  • 六、非阻塞算法CAS
  • 七、`ConcurrentlinkedQueue`非阻塞无界链表队列

一、创建线程的方式？ 1、继承Thread类创建

通过继承Thread并且重写其run()，run方法中即线程执行任务。创建后的子类通过调用 start() 方法即可执行线程方法。

通过继承Thread实现的线程类，多个线程间无法共享线程类的实例变量。（需要创建不同Thread对象，自然不共享）

**
 * 通过继承Thread实现线程
 */
public class ThreadTest extends Thread{
　　
　　private int i = 0 ;

    @Override
    public void run() {
        for(;i<50;i++){
            System.out.println(Thread.currentThread().getName() + " is running " + i );
        }
    }
    public static void main(String[] args) {
        for(int j=0;j<50;j++){
        	if(j=20){
                new ThreadTest().start() ;
                new ThreadTest().start() ;
            }
        }
    }
}

2、通过Runnable接口创建线程类

该方法需要先 定义一个类实现Runnable接口，
并重写该接口的 run() 方法，此run方法是线程执行体。
接着创建 Runnable实现类的对象，作为创建Thread对象的参数target，此Thread对象才是真正的线程对象。
通过实现Runnable接口的线程类，是互相共享资源的。

public class RunnableTest implements Runnable {
    private int i ;
    @Override
    public void run() {
        for(;i<50;i++){
            System.out.println(Thread.currentThread().getName() + " -- " + i);
        }
    }
    public static void main(String[] args) {
        for(int i=0;i<100;i++){
            System.out.println(Thread.currentThread().getName() + " -- " + i);
            if(i==20){
                RunnableTest runnableTest = new RunnableTest() ;
                new Thread(runnableTest,"线程1").start() ;
                new Thread(runnableTest,"线程2").start() ;
            }
        }
    }
}

3、使用Callable和Future创建线程

从继承Thread类和实现Runnable接口可以看出，上述两种方法都不能有返回值，且不能声明抛出异常。

而Callable接口则实现了此两点，Callable接口如同Runable接口的升级版，其提供的call()方法将作为线程的执行体，同时允许有返回值。

但是Callable对象不能直接作为Thread对象的target，因为Callable接口是 Java 5 新增的接口，不是Runnable接口的子接口。

对于这个问题的解决方案，就引入 Future接口，此接口可以接受call() 的返回值，RunnableFuture接口是Future接口和Runnable接口的子接口，可以作为Thread对象的target 。

并且， Future 接口提供了一个实现类：FutureTask 。

FutureTask实现了RunnableFuture接口，可以作为 Thread对象的target。

public class CallableTest {
    public static void main(String[] args) {
        CallableTest callableTest = new CallableTest() ;
        //因为Callable接口是函数式接口，可以使用Lambda表达式
        FutureTask task = new FutureTask((Callable)()->{
           int i = 0 ;
           for(;i<100;i++){
               System.out.println(Thread.currentThread().getName() + "的循环变量i的值 ：" + i);
           }
           return i;
        });
       for(int i=0;i<100;i++){
           System.out.println(Thread.currentThread().getName()+" 的循环变量i ： + i");
           if(i==20){
               new Thread(task,"有返回值的线程").start();
           }
       }
       try{
           System.out.println("子线程返回值 ： " + task.get());
        }catch (Exception e){
           e.printStackTrace();
        }
    }
}

二、线程是状态

①初始(NEW)：新创建了一个线程对象，但还没有调用start()方法。

②运行(RUNNABLE)：Java线程中将就绪（ready）和运行中（running）两种状态笼统的成为“运行”。
线程对象创建后，其他线程(比如main线程）调用了该对象的start()方法。
该状态的线程位于可运行线程池中，等待被线程调度选中，获取cpu 的使用权，此时处于就绪状态（ready）。
就绪状态的线程在获得cpu 时间片后变为运行中状态（running）。

③阻塞(BLOCKED)：表线程阻塞于锁。

④等待(WAITING)：进入该状态的线程需要等待其他线程做出一些特定动作（通知或中断）。

⑤超时等待(TIME_WAITING)：该状态不同于WAITING，它可以在指定的时间内自行返回。

⑥终止(TERMINATED)：表示该线程已经执行完毕。

三、Java 多线程加锁的方式

1. synchronized关键字

2. Java.util.concurrent包中的lock接口和ReentrantLock实现类

这两种方式实现加锁。
1）Lock不是Java语言内置的，synchronized是Java语言的关键字，因此是内置特性。
Lock是一个类，通过这个类可以实现同步访问；

2）Lock和synchronized有一点非常大的不同，采用synchronized不需要用户去手动释放锁，当synchronized方法或者synchronized代码块执行完之后，系统会自动让线程释放对锁的占用；
而Lock则必须要用户去手动释放锁，如果没有主动释放锁，就有可能导致出现死锁现象。

总结来说，Lock和synchronized有以下几点不同：

1）Lock是一个接口，而synchronized是Java中的关键字，synchronized是内置的语言实现；

2）synchronized在发生异常时，会自动释放线程占有的锁，因此不会导致死锁现象发生，而Lock在发生异常时，如果没有主动通过unLock()去释放锁，则很可能造成死锁现象，因此使用Lock时需要在finally块中释放锁；

3）Lock可以让等待锁的线程响应中断，而synchronized却不行，使用synchronized时，等待的线程会一直等待下去，不能够响应中断； （I/O和Synchronized都能相应中断，即不需要处理interruptionException异常）

4）通过Lock可以知道有没有成功获取锁，而synchronized却无法办到。

5）Lock可以提高多个线程进行读 *** 作的效率。

在性能上来说，如果竞争资源不激烈，两者的性能是差不多的，而当竞争资源非常激烈时（即有大量线程同时竞争），此时Lock的性能要远远优于synchronized。
所以说，在具体使用时要根据适当情况选择。

1.可重入锁

如果锁具备可重入性，则称作为可重入锁。
像synchronized和ReentrantLock都是可重入锁，可重入性在我看来实际上表明了锁的分配机制：
基于线程的分配，而不是基于方法调用的分配。

举个简单的例子，当一个线程执行到某个synchronized方法时，比如说method1，而在method1中会调用另外一个synchronized方法method2，此时线程不必重新去申请锁，而是可以直接执行方法method2。

class  MyClass {
     public  synchronized  void  method1() {
         method2();
     }
     public  synchronized  void  method2() {
     }
}

上述代码中的两个方法method1和method2都用synchronized修饰了，假如某一时刻，
线程A执行到了method1，此时线程A获取了这个对象的锁，而由于method2也是synchronized方法，假如synchronized不具备可重入性，此时线程A需要重新申请锁。

但是这就会造成一个问题，因为线程A已经持有了该对象的锁，而又在申请获取该对象的锁，这样就会线程A一直等待永远不会获取到的锁。

2.可中断锁

可中断锁：顾名思义，就是可以相应中断的锁。
在Java中，synchronized就不是可中断锁，而Lock是可中断锁。
如果某一线程A正在执行锁中的代码，另一线程B正在等待获取该锁，可能由于等待时间过长，线程B不想等待了，想先处理其他事情，我们可以让它中断自己或者在别的线程中中断它，这种就是可中断锁。

在前面演示lockInterruptibly()的用法时已经体现了Lock的可中断性。

3.公平锁

公平锁即尽量以请求锁的顺序来获取锁。
比如同是有多个线程在等待一个锁，当这个锁被释放时，等待时间最久的线程（最先请求的线程）会获得该所，这种就是公平锁。

非公平锁即无法保证锁的获取是按照请求锁的顺序进行的。
这样就可能导致某个或者一些线程永远获取不到锁。

在Java中，synchronized就是非公平锁，它无法保证等待的线程获取锁的顺序。

而对于ReentrantLock和ReentrantReadWriteLock，它默认情况下是非公平锁，但是可以设置为公平锁。

另外在ReentrantLock类中定义了很多方法，比如：

isFair() //判断锁是否是公平锁

isLocked() //判断锁是否被任何线程获取了

isHeldByCurrentThread() //判断锁是否被当前线程获取了

hasQueuedThreads() //判断是否有线程在等待该锁

在ReentrantReadWriteLock中也有类似的方法，同样也可以设置为公平锁和非公平锁。

不过要记住，ReentrantReadWriteLock并未实现Lock接口，它实现的是ReadWriteLock接口。

4.读写锁

读写锁将对一个资源（比如文件）的访问分成了2个锁，一个读锁和一个写锁。

正因为有了读写锁，才使得多个线程之间的读 *** 作不会发生冲突。

ReadWriteLock就是读写锁，它是一个接口，ReentrantReadWriteLock实现了这个接口。

可以通过readLock()获取读锁，通过writeLock()获取写锁。

ReadWriteLock， ReadWriteLock也是一个接口，在它里面只定义了两个方法：

四、DeplayQueue延时无界阻塞队列

在谈到DelayQueue的使用和原理的时候，我们首先介绍一下DelayQueue，
DelayQueue是一个无界阻塞队列，只有在延迟期满时才能从中提取元素。
该队列的头部是延迟期满后保存时间最长的Delayed元素。

DelayQueue阻塞队列在我们系统开发中也常常会用到，
例如：缓存系统的设计，缓存中的对象，超过了空闲时间，需要从缓存中移出；
任务调度系统，能够准确的把握任务的执行时间。

我们可能需要通过线程处理很多时间上要求很严格的数据，如果使用普通的线程，
我们就需要遍历所有的对象，一个一个的检查看数据是否过期等，
首先这样在执行上的效率不会太高，其次就是这种设计的风格也大大的影响了数据的精度。

一个需要12：00点执行的任务可能12：01才执行，
这样对数据要求很高的系统有更大的弊端。由此我们可以使用DelayQueue。

下面将会对DelayQueue做一个介绍，然后举个例子。
并且提供一个Delayed接口的实现和Sample代码。
DelayQueue是一个BlockingQueue，其特化的参数是Delayed。

（不了解BlockingQueue的同学，先去了解BlockingQueue再看本文）

Delayed扩展了Comparable接口，比较的基准为延时的时间值，Delayed接口的实现类getDelay的返回值应为固定值（final）。

DelayQueue内部是使用PriorityQueue实现的。

DelayQueue=BlockingQueue+PriorityQueue+Delayed

DelayQueue的关键元素BlockingQueue、PriorityQueue、Delayed。
可以这么说，DelayQueue是一个使用优先队列（PriorityQueue）实现的BlockingQueue，优先队列的比较基准值是时间。

他们的基本定义如下

public interface Comparable {
    public int compareTo(T o);
}
public interface Delayed extends Comparable {
    long getDelay(TimeUnit unit);
}
public class DelayQueue implements BlockingQueue {
    private final PriorityQueue q = new PriorityQueue();
}

DelayQueue 内部的实现使用了一个优先队列。
当调用 DelayQueue 的 offer 方法时，把 Delayed 对象加入到优先队列 q 中。如下：

public boolean offer(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E first = q.peek();
        q.offer(e);
        if (first == null || e.compareTo(first) < 0)
            available.signalAll();
        return true;
    } finally {
        lock.unlock();
    }
}

DelayQueue 的 take 方法，把优先队列 q 的 first 拿出来（peek），如果没有达到延时阀值，则进行 await处理。如下：

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        for (; ; ) {
            E first = q.peek();
            if (first == null) {
                available.await();
            } else {
                long delay = first.getDelay(TimeUnit.NANOSECONDS);
                if (delay > 0) {
                    long tl = available.awaitNanos(delay);
                } else {
                    E x = q.poll();
                    assert x != null;
                    if (q.size() != 0)
                        available.signalAll(); //wake up other takers return x;
                }
            }
        }
    } finally {
        lock.unlock();
    }
}

● DelayQueue 实例应用

Ps：为了具有调用行为，存放到 DelayDeque 的元素必须继承 Delayed 接口。Delayed 接口使对象成为延迟对象，它使存放在 DelayQueue 类中的对象具有了激活日期。

该接口强制执行下列两个方法。

一下将使用 Delay 做一个缓存的实现。

其中共包括三个类Pair、DelayItem、Cache

● Pair 类：

public class Pair {
    public K first;
    public V second;
    public Pair() {
    }
    public Pair(K first, V second) {
        this.first = first;
        this.second = second;
    }
}

以下是对 Delay 接口的实现：

import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
public class DelayItem implements Delayed {
    
    private static final long NANO_ORIGIN = System.nanoTime();
    
    final static long now() {
        return System.nanoTime() - NANO_ORIGIN;
    }
    
    private static final AtomicLong sequencer = new AtomicLong(0);

    
    private final long sequenceNumber;

    
    private final long time;
    private final T item;
    public DelayItem(T submit， long timeout) {
        this.time = now() + timeout;
        this.item = submit;
        this.sequenceNumber = sequencer.getAndIncrement();
    }
    public T getItem() {
        return this.item;
    }
    public long getDelay(TimeUnit unit) {
        long d = unit.convert(time - now()， TimeUnit.NANOSECONDS); return d;
    }
    public int compareTo(Delayed other) {
        if (other == this) // compare zero onLY if same object return 0;
            if (other instanceof DelayItem) {
                DelayItem x = (DelayItem) other;
                long diff = time - x.time;
                if (diff < 0) return -1;
                else if (diff > 0) return 1;
                else if (sequenceNumber < x.sequenceNumber) return -1;
                else
                    return 1;
            }
        long d = (getDelay(TimeUnit.NANOSECONDS) - other.getDelay(TimeUnit.NANOSECONDS));
        return (d == 0) ?0 :((d < 0) ?-1 :1);
    }
}

以下是 Cache 的实现，包括了 put 和 get 方法

import javafx.util.Pair;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Cache {
    private static final Logger LOG = Logger.getLogger(Cache.class.getName());
    private ConcurrentMap cacheObjMap = new ConcurrentHashMap();
    private DelayQueue>> q = new DelayQueue>>();
    private Thread daemonThread;

    public Cache() {

        Runnable daemonTask = new Runnable() {
            public void run() {
                daemonCheck();
            }
        };
        daemonThread = new Thread(daemonTask);
        daemonThread.setDaemon(true);
        daemonThread.setName("Cache Daemon");
        daemonThread.start();
    }

    private void daemonCheck() {
        if (LOG.isLoggable(Level.INFO)) LOG.info("cache service started.");
        for (; ; ) {
            try {
                DelayItem> delayItem = q.take();
                if (delayItem != null) {
                    // 超时对象处理
                    Pair pair = delayItem.getItem();
                    cacheObjMap.remove(pair.first, pair.second); // compare and remove
                }
            } catch (InterruptedException e) {
                if (LOG.isLoggable(Level.SEVERE)) LOG.log(Level.SEVERE, e.getMessage(), e);
                break;
            }
        }
        if (LOG.isLoggable(Level.INFO)) LOG.info("cache service stopped.");
    }

    // 添加缓存对象
    public void put(K key, V value, long time, TimeUnit unit) {
        V oldValue = cacheObjMap.put(key, value);
        if (oldValue != null) q.remove(key);
        long nanoTime = TimeUnit.NANOSECONDS.convert(time, unit);
        q.put(new DelayItem>(new Pair(key, value), nanoTime));
    }

    public V get(K key) {
        return cacheObjMap.get(key);
    }
}

测试 main 方法：

// 测试入口函数
public static void main(String[] args) throws Exception {
    Cache cache = new Cache();
    cache.put(1, "aaaa", 3, TimeUnit.SECONDS);
    Thread.sleep(1000 * 2);
    {
        String str = cache.get(1);
        System.out.println(str);
    }
    Thread.sleep(1000 * 2);
    {
        String str = cache.get(1);
        System.out.println(str);
    }
}

输出结果为：

aaaa

null

我们看到上面的结果，如果超过延时的时间，那么缓存中数据就会自动丢失，获得就为 null。

五、并发（Collection）队列-非阻塞队列

● 非阻塞队列

首先我们要简单的理解下什么是非阻塞队列：

与阻塞队列相反，非阻塞队列的执行并不会被阻塞，无论是消费者的出队，还是生产者的入队。在底层，非阻塞队列使用的是 CAS(compare and swap)来实现线程执行的非阻塞。

● 非阻塞队列简单 *** 作， 与阻塞队列相同，非阻塞队列中的常用方法，也是出队和入队。

● offer()：Queue 接口继承下来的方法，实现队列的入队 *** 作，不会阻碍线程的执行，插入成功返回 true； 出队方法：

● poll()：移动头结点指针，返回头结点元素，并将头结点元素出队；队列为空，则返回 null；

● peek()：移动头结点指针，返回头结点元素，并不会将头结点元素出队；队列为空，则返回 null；

六、非阻塞算法CAS

首先我们需要了解悲观锁和乐观锁

悲观锁：假定并发环境是悲观的，如果发生并发冲突，就会破坏一致性，所以要通过独占锁彻底禁止冲突发生。

有一个经典比喻，“如果你不锁门，那么捣蛋鬼就回闯入并搞得一团糟”，所以“你只能一次打开门放进一个人，才能时刻盯紧他”。

乐观锁：假定并发环境是乐观的，即虽然会有并发冲突，但冲突可发现且不会造成损害，所以，可以不加任何保护，等发现并发冲突后再决定放弃 *** 作还是重试。

可类比的比喻为，“如果你不锁门，那么虽然捣蛋鬼会闯入，但他们一旦打算破坏你就能知道”，所以“你大可以放进所有人，等发现他们想破坏的时候再做决定”。

通常认为乐观锁的性能比悲观所更高，特别是在某些复杂的场景。

这主要由于悲观锁在加锁的同时，也会把某些不会造成破坏的 *** 作保护起来；
而乐观锁的竞争则只发生在最小的并发冲突处，如果用悲观锁来理解，就是“锁的粒度最小”。

但乐观锁的设计往往比较复杂，因此，复杂场景下还是多用悲观锁。
首先保证正确性，有必要的话，再去追求性能。

乐观锁的实现往往需要硬件的支持，多数处理器都都实现了一个CAS指令，实现“Compare And Swap”的语义（这里的swap是“换入”，也就是set），构成了基本的乐观锁。

CAS包含3个 *** 作数：

需要读写的内存位置V

进行比较的值A

拟写入的新值B

当且仅当位置V的值等于A时，CAS才会通过原子方式用新值B来更新位置V的值；
否则不会执行任何 *** 作。

无论位置V的值是否等于A，都将返回V原有的值。
一个有意思的事实是，“使用CAS控制并发”与“使用乐观锁”并不等价。

CAS只是一种手段，既可以实现乐观锁，也可以实现悲观锁。

乐观、悲观只是一种并发控制的策略。

七、ConcurrentlinkedQueue非阻塞无界链表队列

ConcurrentlinkedQueue是一个线程安全的队列，基于链表结构实现，是一个无界队列，理论上来说队列的长度可以无限扩大。
与其他队列相同，ConcurrentlinkedQueue也采用的是先进先出（FIFO）入队规则，对元素进行排序。
当我们向队列中添加元素时，新插入的元素会插入到队列的尾部；而当我们获取一个元素时，它会从队列的头部中取出。
因为ConcurrentlinkedQueue是链表结构，所以当入队时，插入的元素依次向后延伸，形成链表；而出队时，则从链表的第一个元素开始获取，依次递增；

值得注意的是，在使用ConcurrentlinkedQueue时，如果涉及到队列是否为空的判断，切记不可使用size()==0的做法，因为在size()方法中，是通过遍历整个链表来实现的，在队列元素很多的时候，size()方法十分消耗性能和时间，只是单纯的判断队列为空使用isEmpty()即可。

public class ConcurrentlinkedQueueTest {
    public static int threadCount = 10;
    public static ConcurrentlinkedQueue queue = new ConcurrentlinkedQueue();
    static class Offer implements Runnable {
        public void run() {
            //不建议使用 queue.size()==0，影响效率。可以使用!queue.isEmpty()
            if (queue.size() == 0) {
                String ele = new Random().nextInt(Integer.MAX_VALUE) + "";
                queue.offer(ele);
                System.out.println("入队元素为" + ele);
            }
        }
    }
    static class Poll implements Runnable {
        public void run() {
            if (!queue.isEmpty()) {
                String ele = queue.poll();
                System.out.println("出队元素为" + ele);
            }
        }
    }
    public static void main(String[] agrs) {
        ExecutorService executorService = Executors.newFixedThreadPool(4);
        for (int x = 0; x < threadCount; x++) {
            executorService.submit(new Offer());
            executorService.submit(new Poll());
        }
        executorService.shutdown();
    }
}

一种输出：

入队元素为313732926

出队元素为313732926

入队元素为812655435

出队元素为812655435

入队元素为1893079357

出队元素为1893079357

入队元素为1137820958

出队元素为1137820958

入队元素为1965962048

出队元素为1965962048

出队元素为685567162

入队元素为685567162

出队元素为1441081163

入队元素为1441081163

出队元素为1627184732

入队元素为1627184732

ConcurrentlinkedQuere类图

如图ConcurrentlinkedQueue中有两个volatile类型的Node节点分别用来存在列表的首尾节点，其中head节点存放链表第一个item为null的节点，tail则并不是总指向最后一个节点。Node节点内部则维护一个变量item用来存放节点的值，next用来存放下一个节点，从而链接为一个单向无界列表。

public ConcurrentlinkedQueue(){
    head=tail=new Node(null);
}

如上代码初始化时候会构建一个 item 为 NULL 的空节点作为链表的首尾节点。

Offer *** 作offer *** 作是在链表末尾添加一个元素，下面看看实现原理。

public boolean offer(E e) {
    //e 为 null 则抛出空指针异常
    checkNotNull(e);
    //构造 Node 节点构造函数内部调用 unsafe.putObject，后面统一讲
    final Node newNode = new Node(e);
    //从尾节点插入
    for (Node t = tail, p = t; ; ) {
        Node q = p.next;
        //如果 q=null 说明 p 是尾节点则插入
        if (q == null) {
            //cas 插入（1）
            if (p.casNext(null, newNode)) {
                //cas 成功说明新增节点已经被放入链表，然后设置当前尾节点（包含 head，1，3，5.。。个节点为尾节点）
                if (p != t)// hop two nodes at a time
                    casTail(t, newNode); // Failure is OK. return true;
            }
            // Lost CAS race to another thread; re-read next
        } else if (p == q)//(2)
            //多线程 *** 作时候，由于 poll 时候会把老的 head 变为自引用，然后 head 的 next 变为新 head，所以这里需要
            //重新找新的 head，因为新的 head 后面的节点才是激活的节点
            p = (t != (t = tail)) ? t : head;
        else
            // 寻找尾节点(3)
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

从构造函数知道一开始有个item为null的哨兵节点，并且head和tail都是指向这个节点。

如图首先查找尾节点，
qnull，p就是尾节点，
所以执行p.casNext通过cas设置p的next为新增节点，
这时候pt所以不重新设置尾节点为当前新节点。
由于多线程可以调用offer方法，所以可能两个线程同时执行到了（1）进行cas，
那么只有一个会成功（假如线程1成功了），成功后的链表为：

失败的线程会循环一次这时候指针为：

这时候会执行（3）所以 p=q，然后在循环后指针位置为：

所以没有其他线程干扰的情况下会执行（1）执行 cas 把新增节点插入到尾部，没有干扰的情况下线程 2 cas 会成功，然后去更新尾节点 tail，由于 p!=t 所以更新。这时候链表和指针为：

假如线程 2cas 时候线程 3 也在执行，那么线程 3 会失败，循环一次后，线程 3 的节点状态为：

这时候 p!=t ；并且 t 的原始值为 told，t 的新值为 tnew ，所以 told!=tnew，所以 p=tnew=tail

然后在循环一下后节点状态：

q==null 所以执行（1）。

现在就差 p==q 这个分支还没有走，这个要在执行 poll *** 作后才会出现这个情况。poll 后会存在下面的状态

这个时候添加元素时候指针分布为：

所以会执行（2）分支 结果 p=head，然后循环，循环后指针分布：

所以执行(1)，然后 p!=t 所以设置 tail 节点。现在分布图：

自引用的节点会被垃圾回收掉。

● add *** 作

add *** 作是在链表末尾添加一个元素，下面看看实现原理。

其实内部调用的还是 offer

public boolean add(E e) {
    return offer(e);
}

● poll *** 作

poll *** 作是在链表头部获取并且移除一个元素，下面看看实现原理。

public E poll() {
    restartFromHead:
    // 死 循 环
    for (; ; ) {
        //死循环
        for (Node h = head, p = h, q;
                ; ) {
            //保存当前节点值
            E item = p.item;
            //当前节点有值则 cas 变为 null（1）
            if (item != null && p.casItem(item， null)){
                //cas 成功标志当前节点以及从链表中移除
                if (p != h) // 类似 tail 间隔 2 设置一次头节点（2）
                    updateHead(h, ((q = p.next) != null) ? q : p);
                return item;
            }
            //当前队列为空则返回 null（3）
        else if ((q = p.next) == null) {
                updateHead(h, p);
                return null;
            }
            //自引用了，则重新找新的队列头节点（4）
            else if (p == q)
                continue restartFromHead;
            else//(5)
                p = q;
        }
    }
}
final void updateHead(Node h,Node p){
    if(h!=p&&casHead(h,p))
        h.lazySetNext(h);
}

● 当队列为空时候：

可知执行（3）这时候有两种情况，第一没有其他线程添加元素时候(3)结果为 true 然后因为 h!=p 为 false 所以直接返回 null。第二在执行 q=p.next 前，其他线程已经添加了一个元素到队列，这时候（3）返回 false，然后执行（5）p=q，然后循环后节点分布：

这时候执行（1）分支，进行 cas 把当前节点值值为 null，同时只有一个线程会成功，cas 成功 标示该节点从队列中移除了，然后 p!=h，调用 updateHead 方法，参数为 h，p;h!=p 所以把 p 变为当前链表 head 节点，然后 h 节点的 next 指向自己。现在状态为：

cas 失败 后 会再次循环，这时候分布图为：

这时候执行（3）返回 null.

现在还有个分支（4）没有执行过，那么什么时候会执行那？

这时候执行（1）分支，进行 cas 把当前节点值值为 null，同时只有一个线程 A 会成功，cas 成功 标示该节点从队列中移除了，然后 p!=h，调用 updateHead 方法，假如执行 updateHead 前另外一个线程 B 开始 poll 这时候它 p 指向为原来的 head 节点，然后当前线程 A 执行 updateHead 这时候 B 线程链表状态为：

所以会执行（4）重新跳到外层循环，获取当前 head，现在状态为：

● peek *** 作

peek *** 作是获取链表头部一个元素（只读取不移除），下面看看实现原理。

代码与 poll 类似，只是少了 castItem.并且 peek *** 作会改变 head 指向，offer 后 head 指向哨兵节点，第一次 peek 后 head 会指向第一个真的节点元素。

public E peek() {
    restartFromHead:
    for (; ; ) {
        for (Node h = head, p = h, q; ; ) {
            E item = p.item;
            if (item != null || (q = p.next) == null) {
                updateHead(h, p);
                return item;
            } else if (p == q)
                continue restartFromHead;
            else
                p = q;
        }
    }
}

● size *** 作

获取当前队列元素个数，在并发环境下不是很有用，因为使用 CAS 没有加锁所以从调用 size 函数到返回结果期间有可能增删元素，导致统计的元素个数不精确。

public int size() {
    int count = 0;
    for (Node p = first(); p != null; p = succ(p))
        if (p.item != null)
            // 最大返回 Integer.MAX_VALUE
            if (++count == Integer.MAX_VALUE) break;
    return count;
}

//获取第一个队列元素（哨兵元素不算），没有则为 null
public void Node first() {
    restartFromHead:
    for (; ; ) {
        for (Node h = head, p = h, q; ; ) {
            boolean hasItem = (p.item != null);
            if (hasItem || (q = p.next) == null) {
                updateHead(h, p);
                return hasItem ? p : null;
            } else if (p == q)
                continue restartFromHead;
            else
                p = q;
        }
    }
}
//获取当前节点的 next 元素，如果是自引入节点则返回真正头节点
public void final Node succ(Node p) {
    Node next = p.next;
    return (p == next) ? head : next;
}

● remove *** 作

如果队列里面存在该元素则删除该元素，如果存在多个则删除第一个，并返回 true，否则返回 false

public boolean remove(Object o){
    //查找元素为空，直接返回 false
    if(o==null)return false;
    Node pred=null;
    for(Node p=first();p!=null;p=succ(p)){
        E item=p.item;
        //相等则使用 cas 值 null，同时一个线程成功，失败的线程循环查找队列中其他元素是否有匹配的。
        if(item!=null&&o.equals(item)&&p.casItem(item,null)){
            //获取 next 元素
            Node next=succ(p);
            //如果有前驱节点，并且 next 不为空则链接前驱节点到 next，
            if(pred!=null&&next!=null)
                pred.casNext(p,next);
            return true;
        }
        pred=p;
    }
    return false;
}

● contains *** 作

判断队列里面是否含有指定对象，由于是遍历整个队列，所以类似 size 不是那么精确，有可能调用该方法时候元素还在队列里面，但是遍历过程中才把该元素删除了，那么就会返回 false.

public boolean contains(Object o) {
    if (o == null) return false;
    for (Node p = first(); p != null; p = succ(p)) {
        E item = p.item;
        if (item != null && o.equals(item)) return true;
    }
    return false;
}

关于ConcurrentlinkedQuere的offer方法有意思的问题：

offer 中有个 判断 t != (t = tail）假如 t=node1;tail=node2;并且 node1!=node2 那么这个判断是 true 还是 false 那，答案是 true，这个判断是看当前 t 是不是和 tail 相等，相等则返回 true 否者为 false，但是无论结果是啥执行后 t 的值都是 tail。

下面从字节码来分析下为啥。

举一个例子：

public static void main(String[] args){
        int t=2;
        int tail=3;
        System.out.println(t!=(t=tail));
}

结果为：true

我们从上面main方法的字节码文件中分析

一开始栈为空：

栈

第0行指令作用是把值2入栈栈顶元素为2

栈

第1行指令作用是将栈顶int类型值保存到局部变量t中

栈

第2行指令作用是把值3入栈栈顶元素为3

栈

第3行指令作用是将栈顶int类型值保存到局部变量tail中。

栈

第4调用打印命令

第7行指令作用是把变量t中的值入栈

栈

第8行指令作用是把变量tail中的值入栈

栈

现在栈里面的元素为3、2，并且3位于栈顶

第9行指令作用是当前栈顶元素入栈，所以现在栈内容3，3，2

栈

第10行指令作用是把栈顶元素存放到t，现在栈内容3，2

栈

第11行指令作用是判断栈顶两个元素值，相等则跳转18。由于现在栈顶严肃为3，2不相等所以返回true.

第14行指令作用是把1入栈

然后回头分析下!=是双目运算符，应该是首先把左边的 *** 作数入栈，然后在去计算了右侧 *** 作数。

● ConcurrentlinkedQuere总结

ConcurrentlinkedQueue使用CAS非阻塞算法实现使用CAS解决了当前节点与next节点之间的安全链接和对当前节点值的赋值。

由于使用CAS没有使用锁，所以获取size的时候有可能进行offer，poll或者remove *** 作，导致获取的元素个数不精确，所以在并发情况下size函数不是很有用。另外第一次peek或者first时候会把head指向第一个真正的队列元素。

下面总结下如何实现线程安全的，可知入队出队函数都是 *** 作volatile变量：head，tail。所以要保证队列线程安全只需要保证对这两个Node *** 作的可见性和原子性，由于volatile本身保证可见性，所以只需要看下多线程下如果保证对着两个变量 *** 作的原子性。

对于offer *** 作是在tail后面添加元素，也就是调用tail.casNext方法，而这个方法是使用的CAS *** 作，只有一个线程会成功，然后失败的线程会循环一下，重新获取tail，然后执行casNext方法。对于poll也是这样的。