文档章节

悠然乱弹:关于优先队列

悠悠然然
 悠悠然然
发布于 2014/03/09 09:37
字数 1928
阅读 2870
收藏 99
点赞 7
评论 16

背景分析

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

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

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

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

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

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

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

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

解决方案

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

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

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

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

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

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

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

存在的问题

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

优化方案

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

总结

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


© 著作权归作者所有

共有 人打赏支持
悠悠然然

悠悠然然

粉丝 2372
博文 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
图的创建,深度优先遍历,广度优先遍历。

图的储存结构: 由于广度优先需要用到队列关于队列部分:队列的链式储存以及循环队列 图的常用函数: 测试函数: 结果截图: 参考书:数据结构

奔跑的码农
2016/06/01
555
0
OSChina 开源周刊 40 期 —— 2015 年五大移动端设计趋势

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

OSC编辑部
2015/06/28
4.8K
2
有向图----有向环检测和拓扑排序

上一篇:有向图的深度优先和广度优先遍历 优先级限制下的调度问题:给定一组需要完成的任务,以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何安排并完成所有任...

Superheros
2017/12/21
11
0
关于PriorityQueue 二叉堆的问题

场景:最近在研究java中的队列,当研究到优先队列的时候去读 PriorityQueue的源码的时候发现一种数据结构,我数据结构这块基本上上是空白,所以让我晦涩难懂啊,于是我查阅了大量资料以及手动...

skyline520
2013/06/01
0
0
OSChina 技术周刊第九期 —— 每周技术精选,值得一看!

每周技术抢先看,总有你想要的! 移动开发 【翻译】介绍 Visual Studio 的 Android 模拟器 【博客】手机腾讯网mt框架之mtwebapp示例解析。 【博客】《Android深入透析》之常用设计模式经验谈...

OSC编辑部
2014/11/16
3.8K
4
android:persistent="true"

@悠然红茶 你好,想跟你请教个问题:关于你说的android:persistent="true"这个属性 我想请问下 如果说非系统签名的应用push到system下边如果说一旦被disable 如何来复活...

Colin133
2016/08/05
152
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

SpringBoot | 第十章:Swagger2的集成和使用

前言 前一章节介绍了mybatisPlus的集成和简单使用,本章节开始接着上一章节的用户表,进行Swagger2的集成。现在都奉行前后端分离开发和微服务大行其道,分微服务及前后端分离后,前后端开发的...

oKong
今天
2
0
Python 最小二乘法 拟合 二次曲线

Python 二次拟合 随机生成数据,并且加上噪声干扰 构造需要拟合的函数形式,使用最小二乘法进行拟合 输出拟合后的参数 将拟合后的函数与原始数据绘图后进行对比 import numpy as npimport...

阿豪boy
今天
1
0
云拿 无人便利店

附近(上海市-航南路)开了家无人便利店.特意进去体验了一下.下面把自己看到的跟大家分享下. 经得现场工作人员同意后拍了几张照片.从外面看是这样.店门口的指导里强调:不要一次扫码多个人进入....

周翔
昨天
1
0
Java设计模式学习之工厂模式

在Java(或者叫做面向对象语言)的世界中,工厂模式被广泛应用于项目中,也许你并没有听说过,不过也许你已经在使用了。 简单来说,工厂模式的出现源于增加程序序的可扩展性,降低耦合度。之...

路小磊
昨天
156
1
npm profile 新功能介绍

转载地址 npm profile 新功能介绍 npm新版本新推来一个功能,npm profile,这个可以更改自己简介信息的命令,以后可以不用去登录网站来修改自己的简介了 具体的这个功能的支持大概是在6这个版...

durban
昨天
1
0
Serial2Ethernet Bi-redirection

Serial Tool Serial Tool is a utility for developing serial communications, custom protocols or device testing. You can set up bytes to send accordingly to your protocol and save......

zungyiu
昨天
1
0
python里求解物理学上的双弹簧质能系统

物理的模型如下: 在这个系统里有两个物体,它们的质量分别是m1和m2,被两个弹簧连接在一起,伸缩系统为k1和k2,左端固定。假定没有外力时,两个弹簧的长度为L1和L2。 由于两物体有重力,那么...

wangxuwei
昨天
0
0
apolloxlua 介绍

##项目介绍 apolloxlua 目前支持javascript到lua的翻译。可以在openresty和luajit里使用。这个工具分为两种模式, 一种是web模式,可以通过网页使用。另外一种是tool模式, 通常作为大规模翻...

钟元OSS
昨天
2
0
Mybatis入门

简介: 定义:Mybatis是一个支持普通SQL查询、存储过程和高级映射的持久层框架。 途径:MyBatis通过XML文件或者注解的形式配置映射,实现数据库查询。 特性:动态SQL语句。 文件结构:Mybat...

霍淇滨
昨天
2
0
开发技术瓶颈期,如何突破

前言 读书、学习的那些事情,以前我也陆续叨叨了不少,但总觉得 “学习方法” 就是一个永远在路上的话题。个人的能力、经验积累与习惯方法不尽相同,而且一篇文章甚至一本书都很难将学习方法...

_小迷糊
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部