[發明專利]一種最大優先級隊列的設計方法

在審

• 申請號: 201410228594.1
• 申請日: 2014-05-28
• 公開（公告）號: CN103986668A
• 公開（公告）日: 2014-08-13
• 發明（設計）人: 范明彬;張在貴
• 申請（專利權）人: 浪潮電子信息產業股份有限公司
• 主分類號: H04L12/865
• 分類號: H04L12/865;H04L12/863
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 姜明

技術領域

本發明是一種優先級隊列設計方法，本優先級隊列設計方法用于解決在數據通信過程中，因系統處理大量數據不及時，導致網絡擁塞的問題。通過該設計方法，實現優先級隊列與配額的結合應用。

技術背景

隊列是一種滿足先進先出（FIFO）的數據結構，數據從隊列頭部取出，新的數據從隊列尾部插入，數據之間是平等的，不存在優先級的。這個就類似于普通老百姓到火車站排隊買票，先來的先買票，每個人之間是平等的，不存在優先的權利，整個過程是固定不變的。而優先級隊列可以理解為在隊列的基礎上給每個數據賦一個權值，代表數據的優先級。與隊列類似，優先級隊列也是從頭部取出數據，從尾部插入數據，但是這個過程根據數據的優先級而變化的，總是優先級高的先出來，所以不一定是先進先出的。這個過就類似于買火車票時候軍人比普通人優先買，雖然軍人來的晚，但是軍人的優先級比普通人高，總是能夠先買到票。通常優先級隊列用在操作系統中的多任務調度，任務優先級越高，任務優先執行（類似于出隊列），后來的任務如果優先級比以前的高，則需要調整該任務到合適的位置，以便于優先執行，整個過程總是使得隊列中的任務的第一任務的優先級最高。

配額在本專利中是指對于優先級隊列中的子優先級隊列每次可發送的數據長度。

發明內容

一種優先級隊列設計方法，本發明涉及一種最大優先級隊列的設計實現方法，該優先級隊列在出隊時，總是對應優先級最大的數據出隊。該方法同時將配額與優先級隊列緊密的結合在一起，使得該優先級更智能的處理數據隊列，從而提高數據處理的效率。

（1）該設計方法主要有兩個隊列組成，一級優先級隊列（queue）和子隊列（subqueue），每個一級優先級隊列數據包含一個子隊列，一級隊列為優先級隊列，使得高優先級的數據可以提前出列，子隊列用來控制配額大小，使得該隊列中所有數據不會因為優先級過低而處于一直等待的狀態。?

（2）本方法的設計思想為：數據入隊可選擇從前入隊或者從尾部入隊兩種方式，當優先級隊列中的數據出隊時，首先從queue中優先級最高的數據出隊，遍歷該subqueue?配額token大小，若其配額大于數據長度，則直接出隊。并根據子隊列（subqueue）優先級和數據長度重新計算其余子隊列的配額大小；若子隊列（subqueue）中的配額小于其數據長度，則按照嚴格的優先級進行出隊，并動態計算各個子隊列中配額的大小（根據本次所發的數據長度和子隊列的優先級等進行計算）。

（3）根據（2）的設計思想，設計queue的數據結構如下：

map<unsigned,?SubQueue>?Queue?

其中unsigned為該數據的優先級，SubQueue為子優先級隊列。

根據（2）的設計思想和queue數據結構，設計subqueue的數據結構如下：

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

其中K為標示該連接唯一的ID，unsigned為數據的配額（token）大小，在數據中則為數據的字節長度。T為具體的數據。

根據前面的設計方法，設定其計算配額（token）的方法，默認配額均為0，配額的計算公式如下：

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

其中token為優先級隊列中當前數據的配額大小，priority為當前優先級數據的優先級大小，msg_len為當前出隊的數據長度，total_priority為當前優先級隊列總的優先級大小之和。

本發明的優異效果如下：提出優先級隊列的優化方案，實現優先級隊列與配額的結合應用，解決在數據通信過程中，因系統處理大量數據不及時導致網絡擁塞的問題，同時提高了系統的承載能力和處理能力，充分發揮系統的性能，有效提高系統在長時間高負載的下的承載能力和數據處理能力，該優先級隊列在出隊時，總是對應優先級最大的數據出隊，同時將配額與優先級隊列緊密的結合在一起，使得該優先級更智能的處理數據隊列，從而提高數據處理的效率。

附圖說明

圖1是數據入隊方式；?

圖2是數據出隊方式。

具體實施方式

下面參照附圖，對本發明的內容以一個具體實例來描述實現這一設計方法的實現過程。

正如發明內容中所描述的，本發明是一種優先級隊列的設計方法，它與配額緊密的結合在一起，從而更加智能的處理隊列中的數據，防止優先級別低的數據一直處于等待狀態。