任务调度之调度算法( 二 ) _调度算法

时间轮类似于钟表，上面有时分秒的刻度，秒针一秒一秒的跳，对应到秒级任务，如果刻度跨度为毫秒则可以实现毫秒调度。每一个刻度后面都连接着当前秒应该执行的任务，系统每次都调度当前时间指针下的任务。其数据结构就可以看成「数组+链表」的实现，时间轮是一种算法思想，在各开发语言中没有对应的实现，HashMap、Dict 也可以满足要求。XXL-JOB 就是使用的 ConcurrentHashMap<Integer,List<Integer>> 。时间轮相比于 DelayQueue 怎么样呢，又存在哪些问题，该怎么解决呢？

有序性

时间轮靠时间指针调度，不存在任务排序，每次都是取出当前刻度下的任务。每次都是O(1)，假如当前时刻下有多个任务，当前队列需要全部弹出。

线程安全

与 DelayQueue 不同，时间轮每个刻度下都是一个独立的队列，各队列的存取互不影响，可以通过线程安全的队列来实现，所以存取的并发性能比 DelayQueue 高很多。

避免空轮询

时间轮的本质是随着时间的推移，不断的轮询当前时间刻度下的任务，与 DelayQueue 不同，即使时间轮为空时，依然轮询，会产生空轮询。在 XXL-JOB 里就存在这种问题，幸好一般情况下，都是秒级调度，空轮询也没有大影响。但如果是毫秒级调度，空轮询是会影响系统性能的，比如 epoll CPU100% 的bug 和 Netty 空轮询bug 。

任务去重

需要保证在一个时间刻度下，一个任务不能出现两次，不然可能会多次调度。

时间轮实现

理想中的时间轮是能够满足以上 4 点要求，revolver 通过跳跃表数组实现基本结构ConcurrentSkipListSet<Integer>[]，ConcurrentSkipListSet 是一个基于跳跃表实现的无锁的线程安全的、有序列、去重的列表表，向列表put元素并排序的时间复杂度是O(logN)，ReentrantLock + condition + AtomicInteger 计数器避免空轮询。
当任务数=0 时，调用 condition.await() take 被阻塞，当元素个数从无变成有的时候，调用 condition.signal()，也是一个典型的生产者消费者模型。