文档章节

悠然乱弹:关于优先队列

悠悠然然
 悠悠然然
发布于 2014/03/09 09:37
字数 1928
阅读 2874
收藏 99

背景分析

说到优先队列,熟悉jdk的朋友可能就知道,从jdk1.5开始,jdk中就提供了优先队列类,具体的做法就是实现了可比较的接口之后,就可以过比较使得优先级高的对象先出队列,从而体现“优先”性。

一般的情况下,这么做当然也都是没有问题的。

我们假设现在有这么一个应用场景:

你到银行去办一项业务,但是由于办业务的人多,由于金卡,银卡,钻石卡的用户不停的来,这样队列中的普通用户们就一直没有办理业务的机会。你和其它的普通用户的怒火一点一点的升起来,最后小宇宙爆发,估计够大堂经理受的。同样,如果今天如果来的都是钻石卡用户,那些金卡同志们也会一直没有机会输业务,他们同样会小宇宙爆发的。

OK,我们再来假设另外一个场景。比如在证券交易所,有些交易用户是大客户,一般来说,大客户享受有更好的交易条件,假设我们制订一个规则,就是帐户金额(单位万元)取log10之后,即为其优先级。

假设有一天交易量远远超过计算机的处理能力,结果就会发现,小散们几乎没有交易机会。反过来又影响了大客户们的利益。最后所有的客户都不满意:大客户想买/卖小散们的单,小散们由于优先级太低,根本没有机会交易。最后就表现为撮合效率非常低,客户满意度同样非常低。

OK,通过上面的两个场景,就会发现我们简单的利用优先队列来处理有优先级的问题,实际上在许多场景下是不合理或不现实的。

这个时候必须给出可行的解决方案,即体现高端客户的优先权,又要照顾到低优先级别的用户的权利,给他们也有充分的执行机会,两者需要兼顾。

解决方案

上一节,有说到,常用优先队列在解决上面的问题的时候,就会有问题,高者恒高,低者恒低导致所有参与者与管理者都不希望出现的情况。这个时候矛盾就很难调和了,用优先队列吧,有上面说的问题;不用优先队列吧,又体现不出差异化服务--差异化服务本身不是目的,差异化服务看中的是客户兜兜里的真金白银才是真的。

因此解决方案就要既照顾到高优先级的优先权,也照顾给优先级者以阳光普照。这个时候,高优先级者非常开心,因为他花钱了,买到了优先服务的权利,低优先级的用户虽然慢了点,但是服务还是可用的==这个时候这些用户无法识别自己被给予了二等公民待遇,但是考虑到自己在用免费服务或者自己的存款很少等,也就可以接受。最近一段时间滴滴和快滴明显就有这个问题,所有的出租车都去抢在线叫单(高优先级),导致许多不用滴滴和快滴的用户(低优先级)叫不到车,从而引发了许多人的批评。

那也这个时候,可以给出一个方案,那就是优先级提升方案,即在一定条件下触发一个策略计算器,对系统中的用户的优先级进行提升。

这样,随着任务的等级不断的提升,总是可以升级到最高级的,这样就肯定有执行机会了。当然,由于低优先级的人离最高等级有点远,因此升级时间会比较长。

于是马上行动,编写优先级提升算法,改完一执行,效率那是相当的低,把大量的时间都花到优先级提升上了。所以,理想是丰满的,现实是骨感的这句话又得到了验证。

创建具有16个元素的优先队列数组,分别对应0-15共16级的优先队列,新任务到来时,根据优先级,分别添加到对应优先级的队列末尾,任务处理线程会不断从高优先级到低优先级扫描,找到第一个需要处理的任务,并进行处理。另外,每次处理一个业务,会把所有的任务请求的延迟计数器加1,如果延迟计数器达到某一设定值,则提高其优先级,以避免在高优先级任务多时,低优先级请求一直得不到处理的情况发生。

问题:因为一般情况下大多数,低优先级的任务远多于高优先级的任务,因此,在查找第一个任务时,需要做一个循环对优先队列数据进行遍历,并确定队列是否为空,直到找到一个存在的任务或发现所有的队列为空。如果找到了需要处理的任务,还要对所有的低优先级任务的延迟计数器加1,并把达到提升优先级的任务进行优先级提升。

存在的问题

在没有任务时,对优先队列数组进行空转;在高优先级任务较少时,有大量的优先队列计数器加1操作及,优先级提升操作,对系统的性能影响较大。

优化方案

主要进行了三个方面的改进进:
1. 对优先队列数据结构进行调整
考虑到处理一个任务请求的时间远大于添加一个任务请求到队列的时间,因此增加一个时间段的概念,即把一个任务处理周期内的同一优先级的任务作为一个优先级提升单位。即如果需要增加延迟计数器或提升优先级,则一同进行操作,这样就把每一个元素都需要进行的操作变成了一组任务请求共同操作,大大减少了处理量。设处理周期时间段平均任务数为n,则可以节省(n-1)的计数器加 和优先级提升的时间。
2. 对优先级提升级别进行限制
为了便于高优先级的绝对处理,避免大量低优先任务请求升到高优先级后影响到高优先级任务的处理,因此可以保留几个高优先级别,不允许进行任务提升。
3. 对提取任务请求进行优化
原有的轮询方式在任务较少或高优先级任务较少时,会导致大量的无用判断,消耗了大量的CPU,因此,增加了一个请求队列指针,指向一个具有最高优先级的时间片段请求队列的队头。如果为空,则表示没有任务请求,否则直接提取任务进行处理即可。通过此优化把轮讯任务的时间减少到无。

总结

通过以上优化,可以大大优化优先队列的处理性能,同时又提供了高级特性满足一些高级应用需求。


© 著作权归作者所有

共有 人打赏支持
悠悠然然

悠悠然然

粉丝 2396
博文 184
码字总数 360373
作品 14
杭州
架构师
私信 提问
加载中

评论(16)

frank21
frank21
用概率的方法最简单靠谱。
YiYang
YiYang

引用来自“悠悠然然”的评论

引用来自“YiYang”的评论

问个问题啊 如果队列中总是优先级别高的任务 那么是不是队列中的优先级别任务等同于虚设了

那只是解决极端情况的问题,比如双十一

那对于这种极端情况怎么处理呢
悠悠然然
悠悠然然

引用来自“YiYang”的评论

问个问题啊 如果队列中总是优先级别高的任务 那么是不是队列中的优先级别任务等同于虚设了

那只是解决极端情况的问题,比如双十一
YiYang
YiYang
问个问题啊 如果队列中总是优先级别高的任务 那么是不是队列中的优先级别任务等同于虚设了
靠编程而活
靠编程而活
个人感觉关于等待时间+优先级来确定弹出队列还是有一定的欠缺,假如一个人背着一麻袋零钞去银行存钱,如果是第一个处理,这个窗口将没有机会再去处理后面的任务,如果是一般的任务量等待时间+优先级完全可以。这个估计要看下操作系统的优先级设计了!
悠悠然然
悠悠然然

引用来自“田左俭”的评论

我觉得可以依据等待时间和优先级,通过一定的算法来决定是否出列。

有道理,抓住根本了,佩服佩服
LoveCupid
LoveCupid
我觉得可以依据等待时间和优先级,通过一定的算法来决定是否出列。
黄亿华
黄亿华

引用来自“悠悠然然”的评论

引用来自“黄亿华”的评论

看了后半段,我觉得lz跟@夕水溪下 的思路是相似的,就是多个优先级队列。

之前遇到过类似的问题,解决方法相对粗暴一点:将任务加入的时间乘以权重后,与任务本身的优先级,计算一个最终优先级,然后放入PriorityQueue。这样其实也起到了自动提权的效果,好处是无需动态更新优先级。

也是一种植奇妙的解题方案,就是那个算法怎么设计的?

代码:https://gist.github.com/code4craft/9478016
其实很简单,就是重写一下compareTo方法,不过感觉也够用了!
whaon
whaon
mark
悠悠然然
悠悠然然

引用来自“黄亿华”的评论

看了后半段,我觉得lz跟@夕水溪下 的思路是相似的,就是多个优先级队列。

之前遇到过类似的问题,解决方法相对粗暴一点:将任务加入的时间乘以权重后,与任务本身的优先级,计算一个最终优先级,然后放入PriorityQueue。这样其实也起到了自动提权的效果,好处是无需动态更新优先级。

也是一种植奇妙的解题方案,就是那个算法怎么设计的?
Velocity宏定义的坑与解决办法

使用Velocity,当然就免不了要使用宏,或者说使用Velocity而不使用其宏,就相当于废了Velocity一半以上的武功,非常可惜的。 怎么使用Velocity的宏呢,才最大程度的发挥其作用但是又避免掉入...

悠悠然然
2014/04/14
0
2
悠然乱弹:聊聊模块化

序言 熟悉了TINY相关开源内容的同学都有一个印象,那就是Tiny框架的目录分得非常细,比如Tiny工程的目录结构是下面的样子的: 比如TinyUiEnterprise项目的目录结构是这样的: 再比如,我们开...

悠悠然然
2016/01/08
3.1K
23
悠然乱弹:螺旋矩阵和蛇型矩阵的悠然版实现

螺旋矩阵和蛇型矩阵,是两个比较有趣的矩阵,有许多的公司面试题中有出现,这两个题的答案也有许多种,简单问一下度娘,就各自有N种实现,来源也非常丰富,比如CSDN、ITEYE、等等,当然也包括...

悠悠然然
2015/04/04
0
17
【算法系列 三】 Quene

拓扑排序问题(HDU 1285) import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer; public class Main{static int[] i......

Hosee
2016/03/01
90
0
OSChina 开源周刊 40 期 —— 2015 年五大移动端设计趋势

每周技术抢先看,总有你想要的! 移动开发 【博客】Android 4.4 的 init 进程详解 【博客】Android4.4的zygote进程 前端开发 【翻译】在 Microsoft Edge 提供快速的 JavaScript 性能 服务端开...

OSC编辑部
2015/06/28
4.8K
2

没有更多内容

加载失败,请刷新页面

加载更多

Mariadb二进制包安装,Apache安装

安装mariadb 下载二进制包并解压 [root@test-a src]# wget https://downloads.mariadb.com/MariaDB/mariadb-10.2.6/bintar-linux-glibc_214-x86_64/mariadb-10.2.6-linux-glibc_214-x86_64.t......

野雪球
今天
3
0
ConcurrentHashMap 高并发性的实现机制

ConcurrentHashMap 的结构分析 为了更好的理解 ConcurrentHashMap 高并发的具体实现,让我们先探索它的结构模型。 ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEnt...

TonyStarkSir
今天
3
0
大数据教程(7.4)HDFS的java客户端API(流处理方式)

博主上一篇博客分享了namenode和datanode的工作原理,本章节将继前面的HDFS的java客户端简单API后深度讲述HDFS流处理API。 场景:博主前面的文章介绍过HDFS上存的大文件会成不同的块存储在不...

em_aaron
昨天
4
0
聊聊storm的window trigger

序 本文主要研究一下storm的window trigger WindowTridentProcessor.prepare storm-core-1.2.2-sources.jar!/org/apache/storm/trident/windowing/WindowTridentProcessor.java public v......

go4it
昨天
7
0
CentOS 生产环境配置

初始配置 对于一般配置来说,不需要安装 epel-release 仓库,本文主要在于希望跟随 RHEL 的配置流程,紧跟红帽公司对于服务器的配置说明。 # yum update 安装 centos-release-scl # yum ins...

clin003
昨天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部