金庆的专栏

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  423 随笔 :: 0 文章 :: 454 评论 :: 0 Trackbacks
公平队列的实现

(金庆的专栏)

 公平队列(Fair Queuing)是一种调度算法,与先进先出队列不同,
 公平队列分成几个子队列,每个子队列公平地得到处理。
 
 例如上海地铁站充值窗口有两个,一个站外,一个站内,由同一位服务人员受理,
 服务人员会轮流处理两个窗口的请求,两个窗口的队列将公平地得到处理。
 
 公平队列应用于路由器,保证不同的数据流得到公平处理。
 
 Zeromq的消息处理也应用了公平队列,不会因为高数据量的连接阻塞其他连接的处理。
 
 在网游服务器中,公平队列应用于消息的处理,解决场景局部拥挤造成整服都卡的问题。
 例如消息处理按地图排队,这样某个地图的消息拥塞不会影响其他地图的消息处理。
 
 fair_queue 仿 std::priority_queue 实现
 
  1  
  2  /* Fair queue gives each sub queue a fair share.
  3  Author: Jin Qing ( http://blog.csdn.net/jq0123 )
  4  
  5  Example:
  6  fair_queue<int, int> fq;
  7  fq.push(1, 11);
  8  fq.push(1, 12);
  9  fq.push(1, 13);
 10  fq.push(2, 21);
 11  VERIFY(11 == fq.top()); fq.pop();
 12  VERIFY(21 == fq.top()); fq.pop();
 13  VERIFY(12 == fq.top()); fq.pop();
 14  VERIFY(13 == fq.top()); fq.pop();
 15  */
 16  
 17  #ifndef _FAIR_QUEUE_H_
 18  #define _FAIR_QUEUE_H_
 19  
 20  #include <queue>
 21  #include <boost/assert.hpp>
 22  #include <boost/unordered_map.hpp>
 23  
 24  // TEMPLATE CLASS fair_queue
 25  template<class _Kty, class _Ty>
 26  class fair_queue
 27  {
 28  public:
 29      typedef _Kty key_type;
 30      typedef _Ty value_type;
 31      
 32 protected:
 33     typedef std::queue<velue_type> sub_queue_type;
 34     typedef boost::unordered_map<key_type, sub_queue_type> map_type;
 35     typedef std::queue<sub_queue_type *> ordered_queue_type;
 36     typedef boost::unordered_map<sub_queue_type *, key_type> reversed_map_type;
 37     
 38 public:
 39     fair_queue() {};
 40     
 41     bool empty() const
 42     {   // test if queue is empty
 43         return m.empty();
 44     }         
 45     
 46     const value_type & top() const
 47     {   // return top element
 48         BOOST_ASSERT(!empty());
 49         BOOST_ASSERT(q.front());
 50         return q.front()->front();
 51     }
 52     
 53     value_type top()
 54     {   // return mutable top element
 55         BOOST_ASSERT(!empty());
 56         BOOST_ASSERT(q.front());
 57         return q.front()->front();
 58     }
 59     
 60     void push(const key_type & k, const value_type & v)
 61     {   // insert value in k sub queue
 62         map_type::iterator itr = m.find(k);
 63         if (itr != m.end())
 64         {
 65             BOOST_ASSERT(!(*itr).second.empty());
 66             (*itr).second.push(v);
 67             return;
 68         }
 69         // new sub queue
 70         sub_queue_type * sub_queue = &m[k];
 71         sub_queue->push(v);
 72         BOOST_ASSERT(1 == sub_queue->size());
 73         q.push(sub_queue);
 74         rm[sub_queue] = k;
 75         BOOST_ASSERT(q.size() == rm.size());
 76         BOOST_ASSERT(m.size() == q.size());
 77     }
 78     
 79     void pop()
 80     {   // erase top element
 81         BOOST_ASSERT(!empty());
 82         BOOST_ASSERT(!q.empty());
 83         sub_queue_type * sub_queue = q.front();
 84         q.pop();
 85         BOOST_ASSERT(sub_queue);
 86         sub_queue->pop();
 87         if (!sub_queue->empty())
 88         {
 89             // move to the end
 90             q.push(sub_queue);
 91             return;
 92         }
 93         
 94         // erase empty sub queue
 95         const key_type & k = rm[sub_queue];
 96         m.erase(k);
 97         rm.erase(sub_queue);
 98         BOOST_ASSERT(q.size() == rm.size());
 99         BOOST_ASSERT(m.size() == q.size())
100     }
101     
102 protected:
103     map_type m;  //container
104     ordered_queue_type q;  // to order the queues
105     reversed_map_type rm;  // to delete key in m
106         
107  };
108  
109  #endif  // _FAIR_QUEUE_H_
110  
111 
 
posted on 2013-11-25 18:09 金庆 阅读(1065) 评论(0)  编辑 收藏 引用 所属分类: 1. C/C++2. 网游开发

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理