如何理解“队列”？

image.png

  • 循环队列
  • 阻塞队列
  • 并发队列

顺序队列和链式队列

  • 队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾

数组实现:

image.png

链表实现:

image.png

循环队列

image.png

要想写出没有 bug 的循环队列的实现代码，最关键的是，确定好队空和队满的判定条件

  • (tail+1)%n=head
  • (3+1)%8=4

image.png

阻塞队列和并发队列

阻塞队列:

  • Go 的带缓冲 channel 就是一个阻塞队列

image.png

image.png

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

基于 cas 的无锁队列.

解答开篇

第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理

  • 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
  • 基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。

精选留言

城

1.分布式应用中的消息队列，也是一种队列结构
2.考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。
个人浅见，请批评指正

  1. 作者回复: 👍