09队列:队列在线程池等有限资源池中的应用.pdf
《09队列:队列在线程池等有限资源池中的应用.pdf》由会员分享,可在线阅读,更多相关《09队列:队列在线程池等有限资源池中的应用.pdf(22页珍藏版)》请在三一文库上搜索。
1、09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 09|队列:队列在线程池等有限资源池中的应用 我们知道,CPU资源是有限的,任务的处理速度与线程个数并不是线性正相关。相反,过多的线程反而会导致CPU频繁切换,处理性能下降。所以,线程池的大 小一般都是综合考虑要处理任务的特点和硬件环境,来事先设置的。 当我们向固定大小的线程池中请求一个线程时,如果线程池中没有空闲资源了,这个时候线程池如何处理这个请求?是拒绝请求还是排队请求?各种处理策略又 是怎
2、么实现的呢? 实际上,这些问题并不复杂,其底层的数据结构就是我们今天要学的内容,队列(queue)。 如何理解“队列”? 队列这个概念非常好理解。你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队。先进者先出,这就是典型的“队列”。 我们知道,栈只支持两个基本操作:入栈push()和出栈pop()。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队enqueue(),放一个数据到 队列尾部;出队dequeue(),从队列头部取一个元素。 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在
3、线程池等有限资源池中的应用.html2019/1/15 15:35:21 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 所以,队列跟栈一样,也是一种操作受限的线性表数据结构。 队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、 阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。比如高性能队列Disruptor、Linux环
4、形缓存,都用到了循环并发队 列;Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。 顺序队列和链式队列 我们知道了,队列跟栈一样,也是一种抽象的数据结构。它具有先进先出的特性,支持在队尾插入元素,在队头删除元素,那究竟该如何实现一个队列呢? 跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列, 用链表实现的队列叫作链式队列。 我们先来看下基于数组的实现方法。我用Java语言实现了一下,不过并不包含Java语言的高级语法,而且我做了比较详细的注释,你应该可以看懂。 /
5、 用数组实现的队列 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 Stringcapacity; n = capacity; / 入队 public boolean enqueue(String item) / 如
6、果tail = n 表示队列已经满了 if (tail = n) return false; itemstail = item; +tail; return true; / 出队 public String dequeue() / 如果head = tail 表示队列为空 if (head = tail) return null; / 为了让其他语言的同学看的更加明确,把-操作放到单独一行来写了 String ret = itemshead; +head; return ret; 比起栈的数组实现,队列的数组实现稍微有点儿复杂,但是没关系。我稍微解释一下实现思路,你很容易就能明白了。 对于栈来
7、说,我们只需要一个栈顶指针就可以了。但是队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。 abcdhead0tail4 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 你可以结合下面这幅图来理解。当 、 、 、 依次入队之后,队列中的指针指向下标为 的位置,指针指向下标为 的位置。 当我们调用两次出队操作之后,队列中head指针指向下标为2的位置,tail指针仍然指向下标为4的位置。 09|队列:队列在线程池等有限
8、资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 你肯定已经发现了,随着不停地进行入队、出队操作,head和tail都会持续往后移动。当tail移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数 据了。这个问题该如何解决呢? 你是否还记得,在数组那一节,我们也遇到过类似的问题,就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎么解决的吗?对,用数据搬 移!但是,每次进行出队操作都相当于删除数组下标为0的数据,要搬移整个队列中的数据,这样出队操作的时间
9、复杂度就会从原来的O(1)变为O(n)。能不能优化 一下呢? 实际上,我们在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中触发一次数据的搬移操作。借助这个思想,出队函数dequeue()保 持不变,我们稍加改造一下入队函数enqueue()的实现,就可以轻松解决刚才的问题了。下面是具体的代码: / 入队操作,将item放入队尾 public boolean enqueue(String item) / tail = n表示队列末尾没有空间了 if (tail = n) / tail =n / 数据搬移 for (int i = head; i next= new_nod
10、e, tail = tail-next;出队时,head = head-next。我将具体的代码放到GitHub上,你可以自己试着实现一下,然后再去GitHub上跟我实现的代码对比下,看写得对不对。 循环队列 我们刚才用数组来实现队列的时候,在tail=n时,会有数据搬移操作,这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢?我们来看看循环队 列的解决思路。 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 循环队列,顾名思义,它长得
11、像一个环。原本数组是有头有尾的,是一条直线。现在我们把首尾相连,扳成了一个环。我画了一张图,你可以直观地感受一下。 我们可以看到,图中这个队列的大小为8,当前head=4,tail=7。当有一个新的元素a入队时,我们放入下标为7的位置。但这个时候,我们并不把tail更新为8,而是 将其在环中后移一位,到下标为0的位置。当再有一个元素b入队时,我们将b放入下标为0的位置,然后tail加1更新为1。所以,在a,b依次入队之后,循环队列中 的元素就变成了下面的样子: 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等
12、有限资源池中的应用.html2019/1/15 15:35:21 通过这样的方法,我们成功避免了数据搬移操作。看起来不难理解,但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有bug的循环队列 的实现代码,我个人觉得,最关键的是,确定好队空和队满的判定条件。 在用数组实现的非循环队列中,队满的判断条件是tail = n,队空的判断条件是head = tail。那针对循环队列,如何判断队空和队满呢? 队列为空的判断条件仍然是head = tail。但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图,你可以看一下,试着总结一下规律。 09|队列:队列在线程池等有限资源池中的
13、应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 就像我图中画的队满的情况,tail=3,head=4,n=8,所以总结一下规律就是:(3+1)%8=4。多画几张队满的图,你就会发现,当队满时,(tail+1)%n=head。 你有没有发现,当队列满时,图中的tail指向的位置实际上是没有存储数据的。所以,循环队列会浪费一个数组的存储空间。 Talk is cheap,如果还是没怎么理解,那就show you code吧。 public class CircularQueue / 数组
14、:items,数组大小:n private String items; private int n = 0; 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 / head表示队头下标,tail表示队尾下标 private int head = 0; private int tail = 0; / 申请一个大小为capacity的数组 public CircularQueue(int capacity) items = new Stringcap
15、acity; n = capacity; / 入队 public boolean enqueue(String item) / 队列满了 if (tail + 1) % n = head) return false; itemstail = item; tail = (tail + 1) % n; return true; / 出队 public String dequeue() / 如果head = tail 表示队列为空 if (head = tail) return null; String ret = itemshead; head = (head + 1) % n; return r
16、et; 阻塞队列和并发队列 前面讲的内容理论比较多,看起来很难跟实际的项目开发扯上关系。确实,队列这种数据结构很基础,平时的业务开发不大可能从零实现一个队列,甚至都不会 直接用到。而一些具有特殊特性的队列应用却比较广泛,比如阻塞队列和并发队列。 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据 才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 09 队列 线程 有限 资源 中的 应用
链接地址:https://www.31doc.com/p-5529979.html