队列和线程使用的总结和思考

queue-with-thread

18年很大一部分工作在参与开发公司一个项目服务端的开发,过程中出乎我意料的是很多场景使用到队列来解决问题,在这里总个总结。移动端开发过程中,需要自己去实现队列或直接操作线程的场景其实不多,很少有直观的印象;这次服务端的开发过程中,发现其实很多地方都是相通的,能联想到Android应用中的场景,有些队列的实现,也参考了Android MessageQueue的逻辑。

让我们先从队列开始吧。

因涉及公司项目,去掉了实例的部分。

队列(Queue)

队列这种数据结构具有先进先出的特点,出队顺序等于入队顺序,两个操作符:offerpop分别是入队(添加元素到队尾)、出队(移除队首元素)。

在不同场景中,队列的操作可以扩展,比如:遍历(iterate)、插入(add)等;队列的特性也可以扩展,比如支持同步(多线程)、支持阻塞(block)取等。此外,还有双向队列(Deque)可以选用。

队列在Java中的实现有基本的LinkedList,也有基于AbstractQueue的阻塞队列等。队列一般基于链表实现,因为链表便于扩展和移除元素。

线程(Thread)

因为线程是CPU分配资源的最小单位,所以单个线程的逻辑,不会被同时多次执行。线程是代码执行的上下文之一。当我们需要并行执行任务加快执行效率时,就要启动多个线程;对任务来说,切换线程就是切换了执行上下文。

适当的多个线程并行执行能提高任务的执行效率,但也需要注意一些问题,常见的问题就是多个线程同时访问公共数据导致多执行或者漏执行,我们可以在临界区(公共数据)周围使用同步技术(比如加锁)来解决。

线程启动之后必要要执行一个任务(这个任务可能什么都不做,但也是个任务),当需要把一个任务分配到一个新的线程时,可以在开启线程时指定,但如果线程已经在执行了,就不能直接把任务丢给线程说”Hey buddy,帮我执行下这个任务“了。

JDK线程池在运行时,就是在内部创建了多个线程,当添加任务时,由某个空闲的线程去执行。这些线程其实一直在执行、等待的状态间进行切换,事实上每个线程内部都执行了一个无限循环(死循环),在循环内去检查是否有新的任务,如果有的话就执行,否则进入等待状态。

那么这些线程到哪里检查是否有新的任务呢?答案是线程池内部维护了一个阻塞队列,如果有多个线程空闲,会一直从队列中阻塞获取,直到获取到任务。多个线程的分配逻辑是随机的。

这里能窥探到将任务分配到线程的一种方式:线程一直在运行,使用阻塞队列保存任务并且通过是否为空来控制线程的空闲状态。

结合使用的场景

基于前面的介绍,我们可以这样定义工作线程:一个线程,维护着一个阻塞任务队列,线程启动后无限循环的从队列中阻塞获取任务并且执行;如果没有获取到任务,则进入等待状态。

1. 基本消息队列(生产者-消费者模型)

一个线程作为生产者,产生任务并将任务添加到消费者的任务队列(生产者可能不知道是消费者的队列);另一个工作线程作为消费者,执行队列中的任务。

使用消息队列可以将生产者和消费者解耦,生产者无需知道消费者是否存在以及任务如何执行,只需要定义并分发任务即可。

后续介绍的场景都是基于基本消息队列演进而来。

2. 快速消息队列(单生产者-多消费者模型)

将工作线程的数量增加,可以快速执行完队列中的任务,这在任务的生成速度非常快时很有用。假设每秒生成一个任务,每个任务执行时间要2s,这样每2秒都会新增一个延迟执行的任务,并且会无限增加(不考虑线程切换消耗)。如果把工作线程的数量增加到2个,那么理论上每个线程都能被立刻执行,不会产生堆积。

这个模式可以将串行任务转换成并行任务。

实际案例

  1. 网络请求分发到多线程处理。

3. 顺序消息队列(多生产者-单消费者模型)

如果有多个生产者产生任务(比如一个对外提供接口的服务在接收请求),但是任务的执行顺序非常重要,那么可以使用单个工作线程,让该线程接收多个线程的任务,依赖队列有序的性质,可以保证执行顺序和添加顺序一致。

这个模式可以将并行任务转换成串行任务。

实际案例:

  1. Android应用内多个子子线程通过主线程Handler向主线程添加任务。比如在多个子线程中调用LiveData.postData(),最终LiveData.setData()都会在主线程的消息队列中被执行。

4. 延迟消息队列(任务重排序,支持延迟执行)

有的消息我们希望延迟一段时间后执行,我们可以使用Timer等定时方法完成,但如果我们希望在工作线程内执行,再使用Timer就会显得臃肿。既然工作线程可以有执行、空闲两个状态,那么通过控制工作线程空闲状态的持续时间,就可以对任务进行延迟控制

队列中保存的任务,需要增加「预期执行时间」这个属性,并且在向队列中添加任务时,按照预期执行时间的先后,对任务进行排序。工作线程在获取到任务时,先进行检查,判断队首的任务是否到了执行时间,如果没有到执行时间,那么进入空闲状态,等待时间差值后重复执行获取任务的逻辑。

实际案例

  1. Android的MessageQueue和Looper,就采用了类似的执行逻辑。

5. 限流队列(限制任务执行频率)

如果要对某个任务的执行频率进行限制,并在达到限制时延迟执行,限流队列就是合适的方案。限流的实现逻辑和延迟消息队列非常像,在”延迟执行“这件事上采用相同的原理。不同的是延迟消息队列根据任务的预期执行时间进行延迟,而限流队列的依据,是当前时刻已经执行了多少任务,是否达到了限制

为了实现时间窗口模式的限流,需要额外有一个历史队列来存储时间窗口内的任务的执行时间。在执行任务之前,检查历史队列,是否达到了限制。如果没有达到限制,那么可以直接执行,反之,将延迟时间设置为到下个时间窗口的时间差,延迟重复执行获取任务的逻辑。任务执行完成后将时间存入历史队列。

历史队列的数据也要及时清理,可以在检查是否达到限制之前,先从头清理时间窗口之外的数据,之后再进行检查。

总结

以上是对使用到队列的部分场景进行的整理,希望对你有所帮助。关于这个话题,如果你有什么看法和思考,欢迎和我讨论。