[發(fā)明專利]一種最大優(yōu)先級隊列的設(shè)計方法

在審

• 申請?zhí)枺?/td>: 201410228594.1
• 申請日: 2014-05-28
• 公開（公告）號: CN103986668A
• 公開（公告）日: 2014-08-13
• 發(fā)明（設(shè)計）人: 范明彬;張在貴
• 申請（專利權(quán)）人: 浪潮電子信息產(chǎn)業(yè)股份有限公司
• 主分類號: H04L12/865
• 分類號: H04L12/865;H04L12/863
• 代理公司: 濟南信達專利事務(wù)所有限公司 37100
• 代理人: 姜明

1.一種最大優(yōu)先級隊列的設(shè)計方法，其特征在于具體步驟如下：

（1）將要處理的數(shù)據(jù)分成兩個隊列，一級優(yōu)先級隊列queue和子隊列subqueue，兩個隊列的每個一級優(yōu)先級隊列又包含一個子隊列，一級隊列為優(yōu)先級隊列，使得高優(yōu)先級的數(shù)據(jù)提前出列，子隊列用來控制配額大小，使得該隊列中所有數(shù)據(jù)不會因為優(yōu)先級過低而處于一直等待的狀態(tài)；

（2）數(shù)據(jù)入隊選擇從前入隊或者從尾部入隊兩種方式，當優(yōu)先級隊列中的數(shù)據(jù)出隊時，首先從一級優(yōu)先級隊列queue中優(yōu)先級最高的數(shù)據(jù)出隊，遍歷該子隊列subqueue?配額token大小，若其配額token大于數(shù)據(jù)長度，則直接出隊，并根據(jù)子隊列subqueue優(yōu)先級和數(shù)據(jù)長度重新計算其余子隊列subqueue的配額大小；若子隊列subqueue中的配額小于其數(shù)據(jù)長度，則按照嚴格的優(yōu)先級進行出隊，并動態(tài)計算各個子隊列subqueue中配額的大小，根據(jù)本次所發(fā)的數(shù)據(jù)長度和子隊列subqueue的優(yōu)先級進行計算；

（3）根據(jù)步驟（2）一級優(yōu)先級隊列queue的數(shù)據(jù)結(jié)構(gòu)設(shè)計如下：

map<unsigned,?SubQueue>?Queue?

其中unsigned為該數(shù)據(jù)的優(yōu)先級，SubQueue為子優(yōu)先級隊列；

根據(jù)步驟（2）的設(shè)計思想和一級優(yōu)先級隊列queue數(shù)據(jù)結(jié)構(gòu)，設(shè)計子隊列subqueue的數(shù)據(jù)結(jié)構(gòu)如下：

map<K,?list<pair<unsigned,?T>?>?>

其中K為標示該連接唯一的ID，unsigned為數(shù)據(jù)的配額token大小，在數(shù)據(jù)中則為數(shù)據(jù)的字節(jié)長度，T為具體的數(shù)據(jù)；

根據(jù)步驟（1）-（3）的設(shè)計方法，設(shè)定其計算配額token的方法，默認配額均為0，配額的計算公式如下：

token+=（priority*msg_len/total_priority+1）

其中token+為優(yōu)先級隊列中當前數(shù)據(jù)的配額大小，priority為當前優(yōu)先級數(shù)據(jù)的優(yōu)先級大小，msg_len為當前出隊的數(shù)據(jù)長度，total_priority為當前優(yōu)先級隊列總的優(yōu)先級大小之和。