Double Queue(双端队列)

特点

ArrayDeque

基于数组，本质上是一个SlidingWindow，性能比LinkedList或者树性能更强。`

// push A B C into deque
value                A B C
index head(min) 1 2  . . .  tail(max)

录入

分别作为Stack与Quque

addFirst: push
addLast: offer, add

迭代

与数组一样，从head开始到tail，满足栈的先进后出与队列的先进先出。

此外还有双端链表LinkedList，请在其它章节进行了解。

OkHttp内部请求队列实现

(本部分基于git checkout tags/parent-3.9.1版本分析)

在okhttp内部，采用了ArrayDeque实现请求的排队，它主要有如下两个对象

AsyncCall extend NamedRunnable: 对Runnable的封装，非HTTP请求
RealCall extend Call: 真正的HTTP请求

同步请求场景

同步请求是按照顺序阻塞调用的，内部维护了排队队列

// 线程不安全，但是入队与出队加了synchronized锁，自动扩容
private final Deque<RealCall> runningSyncCalls = new ArrayDeque<>();

请求侧如下

// okhttp3.RealCall#execute
 try {
 	 //　enque the element to tail
   client.dispatcher().executed(this);
   // blocking IO works
   Response result = getResponseWithInterceptorChain();
   if (result == null) throw new IOException("Canceled");
   return result;
 } catch (IOException e) {
   eventListener.callFailed(this, e);
   throw e;
 } finally {
   // poll the head element: 注意它是head元素，删除的不一定是刚刚入队的this
   client.dispatcher().finished(this);
 }

同步队列主要用于多个线程阻塞调用OkHttp时Call的引用计数，方便某些场景下执行cancelAll，事实上把这个Queue删除，同步请求也照样能使用的。

异步请求场景

异步请求中维护了两个Runnable队列，虽然Deque可以自动扩容，但是下面通过外置条件控制了running状态，注意异步请求中由于readyAsyncCalls不一定是排序，当某个Host请求多后，少的Host会优先。

/** Ready async calls in the order they'll be run. */
private final Deque<AsyncCall> readyAsyncCalls = new ArrayDeque<>();
/** Running asynchronous calls. Includes canceled calls that haven't finished yet. */
private final Deque<AsyncCall> runningAsyncCalls = new ArrayDeque<>();

入队实现如下

synchronized void enqueue(AsyncCall call) {
  // 某些并行MAX条件
 	if (runningAsyncCalls.size() < maxRequests && runningCallsForHost(call) < maxRequestsPerHost) {
 	  runningAsyncCalls.add(call);
    // 执行 AsyncCall.run()
    // 它的finally中也会执行 finished(runningAsyncCalls, call, true); 进行出队
    // 因此当请求没有达到并行MAX条件时，与阻塞调用类似
 	  executorService().execute(call);
 	} else {
    // 我们只分析这里
 	  readyAsyncCalls.add(call);
 	}
 }

当请求达到了并行MAX条件时，就会涉及排队了。当某个请求完成后，将调用finished

// okhttp3.Dispatcher#finished(java.util.Deque<T>, T, boolean)
// 通过同步锁实现控制两个队列的原子操作
synchronized (this) {
  // 将运行的队列移除，由于是异步，这里**并非**移动的是第一个元素，而是最差N次循环数组才能找
  if (!calls.remove(call)) throw new AssertionError("Call wasn't in-flight!");
  // 通过判断MAX条件，for循环查找尽可能将 readyAsyncCalls 移动到 runningCalls
  promoteCalls();
  runningCallsCount = runningCallsCount();
}

值得注意的是，readyAsyncCalls并不是完全按照先进先出实现排序，而是外部包装了maxRequestsPerHost判断，因此同样是排队，Host少的就是比Host的快，同时PerHost还保持着排序

声明：网上的OkHttp3源码分析【任务队列】 是我以前写的，但是有疏漏（这里并不是移动ready的tail到running的head，而是N次查找），所以我全删了，网上未经授权抄的我救不了啦，要有批判思维。

我们可以参考这些思路去做自己的多参数场景（比如MQ基于IP分发），实现比优先队列更加灵活的排队调度

OJ题目: cooling interval

https://leetcode.com/problems/task-scheduler/