首页 > 其他分享 >队列:队列在线程池等有限资源池中的应用

队列:队列在线程池等有限资源池中的应用

时间:2022-08-17 13:23:40浏览次数:80  
标签:head 程池 队列 入队 池中 tail 线程 数组

目录

当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又是怎么实现的呢?

如何理解“队列”?

  1. 先进者先出,这就是典型的“队列”结构。
  2. 支持两个操作:入队enqueue(),放一个数据到队尾;出队dequeue(),从队头取一个元素。
  3. 和栈一样,队列也是一种操作受限的线性表。

image

顺序队列和链式队列

  1. 跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列

// 用数组实现的队列
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;
  }
}
  1. 队列需要两个指针:一个是 head 指针,指向队头;一个是 tail 指针,指向队尾。
  2. 随着不停地进行入队、出队操作,head 和 tail 都会持续往后移动。当 tail 移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。
    实际上,我们在出队时可以不用搬移数据。如果没有空闲空间了,只需要在入队时,再集中触发一次数据的搬移操作。出队函数 dequeue() 保持不变,我们稍加改造一下入队函数 enqueue() 的实现,当队列的 tail 指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head 到 tail 之间的数据,整体搬移到数组中 0 到 tail-head 的位置。
  3. 基于链表的实现,同样需要两个指针:head 指针和 tail 指针。分别指向链表的第一个结点和最后一个结点。入队时,tail->next= new_node, tail = tail->next;出队时,head = head->next。

循环队列

  1. 循环队列,原本数组是有头有尾的,是一条直线。把首尾相连,扳成了一个环。
  2. 在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,需要像环一样的循环队列。
  3. 要想写出没有 bug 的循环队列的实现代码,最关键的是,确定好队空和队满的判定条件。
    1)队列为空的判断条件仍然是 head == tail。
    2)当队满时,(tail+1)%n=head。 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

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;
  }
}

当队列满时,图中的 tail 指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。

阻塞队列和并发队列

阻塞队列

  1. 阻塞队列就是在队列基础上增加了阻塞操作。
  2. 在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
  3. 基于阻塞队列实现的“生产者 - 消费者模型”,可以有效地协调生产和消费的速度:
    当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列很快就会满了。这个时候,生产者就阻塞等待,直到“消费者”消费了数据,“生产者”才会被唤醒继续“生产”。

并发队列

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

线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?各种处理策略又是如何实现的呢?

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

  1. 基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。
  2. 基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。
    (除了前面讲到队列应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。

// 用数组实现的队列
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;
  }
}

对于栈来说,我们只需要一个栈顶指针就可以了。但是队列需要两个指针:一个是 head 指针,指向队头;一个是 tail 指针,指向队尾。

总结:在正常情况下,队列的入队和出队操作时间复杂度都是O(1),在进行“数据搬移”改造的情况下,入队的时间复杂度我是这么分析的:

如果队尾没有满,可以直接入队,时间复杂度为O(1)。

如果队尾已满的情况下,就必须进行数据搬移了,tail=n,搬移的时间复杂度为O(n).

总体情况来看,tail的可能是0n的任意值,在0n-1的时候队列入队的时间复杂度都是O(1),不需要搬移直接入队即可;只有当tail=n的时候时间复杂度才迅速飙升为O(n),即需要进行n次搬移,此时n次的搬移如果均摊到0~n-1这n次上,其实总体的均摊复杂度还是O(1)。

标签:head,程池,队列,入队,池中,tail,线程,数组
From: https://www.cnblogs.com/xiayuxue/p/16594801.html

相关文章

  • 消息队列对比
    RabbitMQ轻量、开箱即用对消息堆积支持差,大量消息积压时,性能会急剧下降性能差,每秒钟可以处理几万到十几万条消息由Erlang开发RocketMQ(设计参考了Kafka,ali->Apa......
  • Redis实现延迟队列
     一、延迟队列进入该队列的消息会被延迟消费的队列,一般的队列,进入队列后会进行排队依次消费掉二、使用场景需要进行延迟消费的场景,本文举例为某本书籍更新了章节,待内......
  • 1020 胖胖的牛牛 优先队列 bfs 转向时上上次xy与当前xy都不同
     链接:https://ac.nowcoder.com/acm/problem/208246来源:牛客网题目描述每逢佳节胖三斤,牛牛在过去的节日里长胖了,连拐弯都困难,甚至会卡在门上......
  • java线程池源码阅读
    说明简单理解和使用可以参考:https://www.cnblogs.com/LQBlog/p/8735356.html类图接口Executor接口publicinterfaceExecutor{/***代表提交了一个任......
  • 定时任务cron表达式时间失效问题(未按表达式时间运行) 配置定时任务线程池或者同步解
    例如定时任务方法上的注解 cron表达式是这样会的:@Async//异步@Scheduled(cron="059***?")//表达式每小时的59分执行一次@DataSource(DataSourceTy......
  • 641. 设计循环双端队列
    原题链接https://leetcode.cn/problems/design-circular-deque/题目设计实现双端队列。实现MyCircularDeque类:MyCircularDeque(intk):构造函数,双端队列最大为k......
  • 232.implement-queue-using-stacks 用栈实现队列
    当stOut为空时,将stIn中所有元素push到stOut#include<stack>usingstd::stack;classMyQueue{public:stack<int>stIn;stack<int>stOut;MyQueue()......
  • 死信队列
    1、死信的来源队列中的消息可能会变成死信消息(dead-lettered),进而当以下几个事件任意一个发生时,消息将会被重新发送到一个交换机:消息被消费者使用basic.reject或basic.n......
  • 2022-08-04 第六组 李俊琦 锁与线程池
    今日重点LockSupport工具类Lock锁synchronized和Lock的区别并发编程三大特征JVS并发编程包线程池参数的意义(重要)学习内容LockSupport工具类线程阻塞的工具类,所有......
  • 双端队列简单实现
    设计循环双端队列classMyCircularDeque{privateint[]elements;privateintrear,front;privateintcapacity;publicMyCircularDeque(intk......