亚洲欧美在线aaa,加勒比av一区二区,一本色道久久综合亚洲精品不

公平隊列的實現(xiàn)

公平隊列的實現(xiàn)

（金慶的專欄）

公平隊列（Fair Queuing）是一種調(diào)度算法，與先進先出隊列不同，
公平隊列分成幾個子隊列，每個子隊列公平地得到處理。

例如上海地鐵站充值窗口有兩個，一個站外，一個站內(nèi)，由同一位服務(wù)人員受理，
服務(wù)人員會輪流處理兩個窗口的請求，兩個窗口的隊列將公平地得到處理。

公平隊列應(yīng)用于路由器，保證不同的數(shù)據(jù)流得到公平處理。

Zeromq的消息處理也應(yīng)用了公平隊列，不會因為高數(shù)據(jù)量的連接阻塞其他連接的處理。

在網(wǎng)游服務(wù)器中，公平隊列應(yīng)用于消息的處理，解決場景局部擁擠造成整服都卡的問題。
例如消息處理按地圖排隊，這樣某個地圖的消息擁塞不會影響其他地圖的消息處理。

fair_queue 仿 std::priority_queue 實現(xiàn)

  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 金慶閱讀(1077) 評論(0) 編輯收藏引用所屬分類: 1. C/C++ 、2. 網(wǎng)游開發(fā)

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: How are dtLinks created in NavMesh C++ parameter passing rules Naming Conventions for Accessors Visual Studio 2019 Compiler Hangs Fbx File Format Identifier 查找內(nèi)存錯誤 std::thread 中的異常會丟失調(diào)用棧用賦值代替 protobuf CopyFrom() vs2017 linux 編譯輸出改成 vs 格式為 LiteIDE 添加選中標記

網(wǎng)站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

金慶的專欄

公告

留言簿(12)

隨筆分類(502)

隨筆檔案(423)

相冊

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜