悠然乱弹:关于优先队列
悠然乱弹:关于优先队列
悠悠然然 发表于4年前
悠然乱弹:关于优先队列
  • 发表于 4年前
  • 阅读 2847
  • 收藏 99
  • 点赞 7
  • 评论 16

腾讯云 十分钟定制你的第一个小程序>>>   

背景分析

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

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

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

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

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

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

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

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

解决方案

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

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

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

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

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

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

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

存在的问题

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

优化方案

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

总结

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


共有 人打赏支持
悠悠然然
粉丝 2253
博文 171
码字总数 352094
作品 14
评论 (16)
夕水溪下
后面的部分没有看完,我没做过此方面的处理,但是对你说的银行的场景比较感兴趣。要是我去处理,我会这么做:

1.有几种类型的用户,我会初始化几个队列,比如有钻石、白金、普通,我初始化3个队列分别存放来配对的3种用户
2.后台定一个概率,或者比例,比如说3个钻石后会处理2个白金的业务然后处理1个普通的业务
悠悠然然

引用来自“夕水溪下”的评论

后面的部分没有看完,我没做过此方面的处理,但是对你说的银行的场景比较感兴趣。要是我去处理,我会这么做:

1.有几种类型的用户,我会初始化几个队列,比如有钻石、白金、普通,我初始化3个队列分别存放来配对的3种用户
2.后台定一个概率,或者比例,比如说3个钻石后会处理2个白金的业务然后处理1个普通的业务

EN应用场景确实,这么做也是一个不错的选择,在技术上就是把他们给予相互隔离的通道以提供服务。
传统的银行业也就这么做的,他们给VIP有专门的VIP室,窗口多,VIP人数少,所以就快。外面的普通窗口客户多,窗口少,结果就慢。
但是这样带来一个问题,有可能一天没有VIP,里面的VIP室是空着的,而外面的普通窗口人满为患。
也有可能反之。
所以对于资源最大利用方面也有不利因素。
夕水溪下

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

引用来自“夕水溪下”的评论

后面的部分没有看完,我没做过此方面的处理,但是对你说的银行的场景比较感兴趣。要是我去处理,我会这么做:

1.有几种类型的用户,我会初始化几个队列,比如有钻石、白金、普通,我初始化3个队列分别存放来配对的3种用户
2.后台定一个概率,或者比例,比如说3个钻石后会处理2个白金的业务然后处理1个普通的业务

EN应用场景确实,这么做也是一个不错的选择,在技术上就是把他们给予相互隔离的通道以提供服务。
传统的银行业也就这么做的,他们给VIP有专门的VIP室,窗口多,VIP人数少,所以就快。外面的普通窗口客户多,窗口少,结果就慢。
但是这样带来一个问题,有可能一天没有VIP,里面的VIP室是空着的,而外面的普通窗口人满为患。
也有可能反之。
所以对于资源最大利用方面也有不利因素。

您可能理解错了,如果没有VIP,那我去VIP的队列里拿的时候没有,就直接去普通用户的队列里拿
悠悠然然

引用来自“夕水溪下”的评论

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

引用来自“夕水溪下”的评论

后面的部分没有看完,我没做过此方面的处理,但是对你说的银行的场景比较感兴趣。要是我去处理,我会这么做:

1.有几种类型的用户,我会初始化几个队列,比如有钻石、白金、普通,我初始化3个队列分别存放来配对的3种用户
2.后台定一个概率,或者比例,比如说3个钻石后会处理2个白金的业务然后处理1个普通的业务

EN应用场景确实,这么做也是一个不错的选择,在技术上就是把他们给予相互隔离的通道以提供服务。
传统的银行业也就这么做的,他们给VIP有专门的VIP室,窗口多,VIP人数少,所以就快。外面的普通窗口客户多,窗口少,结果就慢。
但是这样带来一个问题,有可能一天没有VIP,里面的VIP室是空着的,而外面的普通窗口人满为患。
也有可能反之。
所以对于资源最大利用方面也有不利因素。

您可能理解错了,如果没有VIP,那我去VIP的队列里拿的时候没有,就直接去普通用户的队列里拿

明白,这个方案在实际情况下是经常会用到的,我们上次有个线程池也是这样搞的。
但是实际处理逻辑会要复杂一些的
夕水溪下

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

引用来自“夕水溪下”的评论

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

引用来自“夕水溪下”的评论

后面的部分没有看完,我没做过此方面的处理,但是对你说的银行的场景比较感兴趣。要是我去处理,我会这么做:

1.有几种类型的用户,我会初始化几个队列,比如有钻石、白金、普通,我初始化3个队列分别存放来配对的3种用户
2.后台定一个概率,或者比例,比如说3个钻石后会处理2个白金的业务然后处理1个普通的业务

EN应用场景确实,这么做也是一个不错的选择,在技术上就是把他们给予相互隔离的通道以提供服务。
传统的银行业也就这么做的,他们给VIP有专门的VIP室,窗口多,VIP人数少,所以就快。外面的普通窗口客户多,窗口少,结果就慢。
但是这样带来一个问题,有可能一天没有VIP,里面的VIP室是空着的,而外面的普通窗口人满为患。
也有可能反之。
所以对于资源最大利用方面也有不利因素。

您可能理解错了,如果没有VIP,那我去VIP的队列里拿的时候没有,就直接去普通用户的队列里拿

明白,这个方案在实际情况下是经常会用到的,我们上次有个线程池也是这样搞的。
但是实际处理逻辑会要复杂一些的

嗯嗯,我考虑的可能没有业务场景。
黄亿华
看了后半段,我觉得lz跟@夕水溪下 的思路是相似的,就是多个优先级队列。

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

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

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

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

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

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

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

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

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

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

代码:https://gist.github.com/code4craft/9478016
其实很简单,就是重写一下compareTo方法,不过感觉也够用了!
LoveCupid
我觉得可以依据等待时间和优先级,通过一定的算法来决定是否出列。
悠悠然然

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

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

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

引用来自“YiYang”的评论

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

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

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

引用来自“YiYang”的评论

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

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

那对于这种极端情况怎么处理呢
frank21
用概率的方法最简单靠谱。
×
悠悠然然
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: