日期:2014-05-16  浏览次数:20648 次

急求 公平的兼顾优先级的任务分发算法!!
想做一个任务分发算法,任务区分优先级(大概可以分为140个级别),希望优先级高的任务尽可能先执行,但是又要兼顾优先级低的任务能够也得到执行。并发时任务个数在几十万。目前自己有两个想法:
(1)添加任务时根据任务的优先级给每个任务对应一个执行优先级,每个任务还携带一个等待时间的属性,当任务等待时间超过阈值时,其执行优先级升高一级,然后按照执行优先级排序,执行任务时直接从队列队首取下一个任务执行就行。
  缺点:链表操作太频繁,每次添加任务都要遍历链表、排序,任务数很大时效率很低;
(2)对所有优先级分段,每一段归为一类大的优先级任务(比如0~~10级的任务都入同一个队列,11~~30级的任务入另一个队列),在这个队列中任务的优先级一样,按照队列的优先级和执行次数来均衡每个队列执行情况。
  缺点:如果某个队列中的任务很多时,反而会有后来的低优先级的任务被先执行。

呵呵,菜鸟级的水平,以上自己的初步想法,可行性有待验证,哪位大师有更好的想法请不吝指教,谢谢!

------解决方案--------------------
两种方法结合起来好

分成14个队列-10级一个队列--有新任务直接放在相应队列尾
当某个任务等待超时时,拿出来放在高一个优先级的队列尾部

优点:新任务插入方便
缺点:10个级别一个队列,队列内优先级模糊区分