好玩的网站列表

CPU资源有限，任务的处理速度和线程个数并不是线性正相关的。相反的，过多的线程会导致CPU频繁切换，处理性能下降。因此，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

当我们向固定大小的线程池中请求一个线程的时候，如果线程池中没有空闲资源，如何处理这个请求呢？ —–> 队列

操作受限的线性表。

1. 理解队列

• 基本操作
  • 入队 enqueue() 入栈 push()
  • 出队 dequeue() 出栈 pop()
• 操作受限的线性表数据结构
• 带有一些特性的队列
  • 循环队列
  • 阻塞队列
  • 并发队列
  • 顺序队列 - 数组实现
  • 链式队列 - 链式队列

在很多偏底层系统，框架，中间件的开发当中，起到关键性作用。比如高性能disruptor,Linux环形缓存，都用到了循环并发队列; Java Concurrent并发包利用ArrayBlockingQueue来实现公平锁。

// 用数组实现的队列
public class ArrayQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public ArrayQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 如果 tail == n 表示队列已经满了
    if (tail == n) return false;
    items[tail] = item;
    ++tail;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    // 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
    String ret = items[head];
    ++head;
    return ret;
  }
}

2. 基于链表的队列实现方法

• 两个指针
  • head指针 - 指向第一个结点
  • tail指针 - 指向最后一个结点

3. 循环队列

用数组实现的队列，在tail = n的时候，会有数据搬移操作。这样入队性能就会受到影响。循环队列的可以解决这个问题。

• 如何确认队空和队满
  • 队空 head == tail
  • 队满 (tail+1)%n = head

public class CircularQueue {
  // 数组：items，数组大小：n
  private String[] items;
  private int n = 0;
  // head 表示队头下标，tail 表示队尾下标
  private int head = 0;
  private int tail = 0;

  // 申请一个大小为 capacity 的数组
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入队
  public boolean enqueue(String item) {
    // 队列满了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出队
  public String dequeue() {
    // 如果 head == tail 表示队列为空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

4. 阻塞队列和并发队列

• 阻塞队列
  • 在队列基础上增加了阻塞操作
  • 队列为空的时候，从队头取数据会被阻塞
  • 如果队列已经满了，那么插入数据的操作会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回
  • 生产者 消费者模型 相当于
  • 基于阻塞队列，我们可以通过协调生产者和消费者的个数来提高数据的处理效率
  • 我们可以通过配置多几个的消费者，来应对一个生产者
• 并发队列
  • 实现方法
    • 在enquue()和dequeue()方法上加锁
    • 基于CAS原子操作

5. 对比基于数组和基于链表实现的队列

• 基于链表的实现方式
  • 可以实现一个支持无限排队的无界队列
  • 可能会导致过多的请求排队等待
  • 请求处理的响应时间会长很多
  • 因此对于响应时间比较敏感的系统来说，基于链表实现的无限排队的线程池就不是很合适了
• 基于数组实现的有界队列
  • 队列大小是有限的
  • 超过一定数量以后，请求就会被拒绝
  • 队列的大小设置就会是个trade off了

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com