基於鍊表的隊列調度方法與裝置的製作方法
2023-07-11 10:08:26
專利名稱：基於鍊表的隊列調度方法與裝置的製作方法
技術領域：
本發明涉及隊列調度技術，尤其涉及一種基於鍊表的多種調度技術混合的隊列調 度方法與裝置。
背景技術：
隊列調度，即隊列通過某種觸發檢查(比如接收到授權觸發等)，仲裁隊列的出 隊條件，按照一定的規則調度隊列有序的出隊。常用的調度算法主要有輪詢(RR，Round Robin)調度算法和嚴格優先級(SP，Strict Priority)調度算法。輪詢調度算法的實現原理是按照一定的順序逐個、循環輪詢隊列出隊。在每個時 鍾周期調度一個隊列出隊，然後在下一個時鐘周期輪詢下一個隊列調度出隊。而嚴格優先 級調度算法是給隊列設定不同的優先級，每次調度最高優先級的隊列出隊，低優先級的隊 列只有在高優先級隊列不滿足出隊條件後才能得到出隊調度。目前，針對多優先級、多隊列輸出調度時，通常的處理方法是對相同優先級的隊列 用一個先入先出(FIFO，First Input First Output)隊列進行緩存排隊，然後在不同優先 級排隊FIFO間採用SP嚴格優先級調度輸出。由於FIFO的原理是先進先得到服務，同一隊列可以反覆進入FIFO排隊，在某一隊 列流量較大時，就會反覆出現在FIFO中排隊，這就會使得同一優先級中低流量的隊列很長 一段時間都得不到服務，只有等到高流量的隊列反覆出隊很多次後才能輪到。這就體現不 出對於同一優先級隊列應該公平輪詢出隊的思想，造成了出隊不公。另一個問題是當隊列 較多時，FIFO會出現溢出的風險，為避免出現這種現象，需要配置較大的FIFO隊列，這將耗 費相當巨大的RAM資源。出隊隊列數和隊列優先級較多的情況如隊列數為32K個，隊列優 先級為6個，為避免溢出現象的出現，出隊排隊就至少需要6個深度為32K的FIFO，這無疑 耗費了大量的RAM資源，但上述所配置的RAM資源中的很大一部分並不能被使用，也造成了 嚴重的資源浪費。
發明內容
有鑑於此，本發明的主要目的在於提供一種基於鍊表的隊列調度方法與裝置，在 保證嚴格優先級調度算法的同時，能保證同一優先級的隊列被公平地調度。為達到上述目的，本發明的技術方案是這樣實現的一種基於鍊表的隊列調度方法，包括設置排隊鍊表中的地址數不少於隊列數，並按隊列所屬優先級將所述排隊鍊表劃 分為不同的排隊子鍊表，其中，所述排隊子鍊表中的地址數不少於所述排隊子鍊表所對應 優先級下的所有隊列數；為各隊列設置標識其是否在所述排隊鍊表中排隊的排隊鍊表標識 符；以及在將符合排隊條件的隊列添入所述排隊鍊表之前，根據所述隊列的排隊鍊表標識 符判斷所述隊列是否已在所述排隊鍊表中排隊，若已排隊則不作添入處理，若未排隊則將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部，並將所述隊列的排隊鍊表標 識符修改為已在所述排隊鍊表中排隊的標識。優選地，所述方法還包括在所述排隊鍊表中選擇優先級最高的非空排隊子鍊表進行隊列調度，優先級最高 的非空排隊子鍊表調度完畢後選擇次優先級的非空排隊子鍊表進行隊列調度。優選地，排隊子鍊表進行隊列調度時，由鍊表的頭部開始，按鍊表指針指示進行隊 列調度。優選地，所述方法還包括優先級相同的已出隊的隊列與待入隊的隊列均符合排 隊條件時，優先將已出隊的隊列添入所述排隊鍊表中。優選地，所述排隊鍊表標識符為1比特，0標識已在所述排隊鍊表中排隊，1標識未 在所述排隊鍊表中排隊；或者，0標識未在所述排隊鍊表中排隊，1標識已在所述排隊鍊表 中排隊。優選地，每個隊列號對應於排隊鍊表中的一個地址。一種基於鍊表的隊列調度裝置，包括設置單元，用於設置排隊鍊表中的地址不少於總隊列的數目，以及，為各隊列設置 標識其是否在所述排隊鍊表中排隊的排隊鍊表標識符；劃分單元，用於按隊列所屬優先級將所述排隊鍊表劃分為不同的排隊子鍊表，其 中，所述排隊子鍊表中的地址不少於所述排隊子鍊表所對應優先級下的所有隊列數；判斷單元，用於在將符合排隊條件的隊列添入所述排隊鍊表之前，根據所述隊列 的排隊鍊表標識符判斷所述隊列是否已在所述排隊鍊表中排隊，若已排隊則不作添入處 理，若未排隊則觸發添入單元；添入單元，用於將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部， 並觸發標識修改單元；以及標識修改單元，用於將所述隊列的排隊鍊表標識符修改為已在所述排隊鍊表中排 隊的標識。優選地，所述裝置還包括調度單元，用於在所述排隊鍊表中選擇優先級最高的排隊子鍊表進行隊列調度， 優先級最高的排隊子鍊表調度完畢後選擇次優先級最高的排隊子鍊表進行隊列調度。優選地，所述調度單元排隊子鍊表進行隊列調度時，由鍊表的頭部開始，按鍊表指 針指示進行隊列調度。優選地，所述添入單元在優先級相同的已出對的隊列與入對的隊列均符合排隊條 件時，優先將已出對的隊列添入所述排隊鍊表中。優選地，每個隊列號對應於排隊鍊表中的一個地址。本發明中，按隊列數量設置排隊鍊表的地址數，使排隊鍊表的地址數不少於隊列 數量，再在排隊鍊表中按隊列的優先級設置不同的排隊子鍊表，隊列入對時，按隊列優先級 選擇對應的排隊子鍊表，在添入排隊子鍊表之前，判斷該隊列是否已在排隊子鍊表中排隊， 若排隊則不再添入到排隊子鍊表中，否則添入。調度時，在排隊鍊表中選取優先級最高的非 空排隊子鍊表，從鍊表的頭部開始，按鍊表指針指示進行隊列調度，所選的非空排隊子鍊表 中的隊列調度完畢後，選取次級優先級的非空排隊子鍊表進行隊列調度。本發明在處理同
5優先級隊列時，按先入先出的方式進行調度，但對於已在排隊鍊表中排隊的隊列而言，不可 能再被添入到排隊鍊表中，這樣保證了同優先級隊列調度時的公平性。
圖1為本發明基於鍊表的隊列調度方法的流程圖；圖2本發明隊列添入排隊子鍊表的結構示意圖；圖3為本發明基於鍊表的隊列調度裝置的組成結構示意圖。
具體實施例方式本發明的基本思想是按隊列數量設置排隊鍊表的地址數，使排隊鍊表的地址數 不少於隊列數量，再在排隊鍊表中按隊列的優先級設置不同的排隊子鍊表，隊列入對時，按 隊列優先級選擇對應的排隊子鍊表，在添入排隊子鍊表之前，判斷該隊列是否已在排隊子 鍊表中排隊，若排隊則不再添入到排隊子鍊表中，否則添入。調度時，在排隊鍊表中選取優 先級最高的非空排隊子鍊表，從鍊表的頭部開始，按鍊表指針指示進行隊列調度，所選的非 空排隊子鍊表中的隊列調度完畢後，選取次級優先級的非空排隊子鍊表進行隊列調度。本 發明在處理同優先級隊列時，按先入先出的方式進行調度，但對於已在排隊鍊表中排隊的 隊列而言，不可能再被添入到排隊鍊表中，這樣保證了同優先級隊列調度時的公平性。為使本發明的目的、技術方案和優點更加清楚明白，以下舉實施例並參照附圖，對 本發明進一步詳細說明。圖1為本發明基於鍊表的隊列調度方法的流程圖，如圖1所示，本發明基於鍊表的 隊列調度方法包括以下步驟步驟101 設置排隊鍊表中的地址數不少於隊列數，並按隊列所屬優先級將所述 排隊鍊表劃分為不同的排隊子鍊表，其中，所述排隊子鍊表中的地址數不少於所述排隊子 鍊表所對應優先級下的所有隊列數；為各隊列設置標識其是否在所述排隊鍊表中排隊的排 隊鍊表標識符。根據系統中所有隊列的數目設置排隊鍊表的地址數，以前述背景技術中32K個隊 列為例，則設置排隊鍊表的地址數至少為32K個，排隊鍊表的地址需要至少15bit的字符來 承載，即每個隊列需有一個對應的排隊鍊表的地址，以在將隊列作添入處理時有存放該隊 列的地址。對於排隊鍊表，再按隊列優先級的不同設置為不同的排隊子鍊表，以對相應優先 級的隊列進行排隊時，將相應優先級的隊列添入到對應優先級的排隊子鍊表中，排隊子鏈 表中的地址數不能少於該優先級下的所有隊列數，以將該優先級下的所有隊列均能在相應 的排隊子鍊表中進行排隊。本發明中，隊列主要是指所屬用戶不同的數據隊列。最好的方 式是排隊子鍊表中的地址數與所有隊列一一對應。同時，為各隊列設置標識其是否在所述排隊鍊表中排隊的排隊鍊表標識符，該排 隊鍊表標識符為1比特的字符，其中，0標識已在所述排隊鍊表中排隊，1標識未在所述排隊 鍊表中排隊；或者，0標識未在所述排隊鍊表中排隊，1標識已在所述排隊鍊表中排隊。本發 明中，隊列的排隊鍊表標識符地址與隊列的序號相對應，以方便查找隊列對應的排隊鍊表 標識符。步驟102 在將符合排隊條件的隊列添入所述排隊鍊表之前，根據所述隊列的排
6隊鍊表標識符判斷所述隊列是否已在所述排隊鍊表中排隊，若已排隊則不作添入處理，若 未排隊則將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部，並將所述隊列的 排隊鍊表標識符修改為已在所述排隊鍊表中排隊的標識。設置完排隊鍊表後，即判斷哪些隊列符合排隊條件，對於符合排隊條件的隊列，將 其添入到排隊鍊表中，具體的，在添入排隊鍊表之前，需要確定隊列的優先級，然後，再查看 該隊列的排隊鍊表標識符，確定該隊列是否已在排隊鍊表中排隊，若已排隊，則不再處理該 隊列，即不再將該隊列添入到排隊鍊表中，而如果未在排隊鍊表中排隊，則將該隊列添入與 該隊列優先級對應的排隊子鍊表中。以下通過具體的示例詳細說明。假設依次A 隊的隊列號是35，13，0，8，0，6，1，64，0，3，55，30，20，80，9， 101，...等等。其中，0，1，3號隊列屬於第一優先級(最高優先級)，6，8，9屬於第二優先級， 13，20，30，35屬於第三優先級，80，64，55，101屬於第四優先級。假設各個隊列均滿足排隊 條件。35號隊列是最先入隊的，查詢排隊鍊表標識符地址35 (排隊鍊表標識符地址與隊列 序列完全對應，這將非常方便對隊列排隊鍊表標識符的查找)的內容，發現是0(假設0標 識隊列未在排隊鍊表中排隊)時，將35號隊列添入排隊鍊表中，同時，把該地址的排隊鍊表 標識符修改為1 (標識隊列已在排隊鍊表中排隊)。查詢排隊鍊表標識符地址35為1時，就 表明該隊列已經在鍊表中排隊，不再處理該隊列的入隊。按照入隊順序，後面的隊列13號， 0號，8號，0號等依次查詢排隊鍊表標識符。0號隊列第二次查詢排隊鍊表標識符時，發現 已經在鍊表裡面了，將不再將其添入到排隊鍊表中。排隊鍊表的地址數與隊列號(隊列數)是對應的，每個隊列均有排隊的地址。本 發明在將隊列添入排隊鍊表中時，是按隊列的優先級將該隊列添入到對應優先級的排隊子 鍊表中。仍以前述編號的隊列為例，第一優先級的排隊子鍊表中將依次添入隊列號為0號， 1號，3號的隊列。圖2本發明隊列添入排隊子鍊表的結構示意圖，如圖2所示，排隊子鍊表 地址0就是鍊表首地址，存放的是0號隊列號，1號地址中存放的是1號隊列號，3號地址中 存放的是3號隊列，由於排隊子鍊表中只添入了 3個隊列，地址3指針的下一跳地址就是鏈 表尾地址，內容為空。在將隊列添入到排隊子鍊表中時，從排隊子鍊表的尾地址開始存放隊 列，前述的列號為0號，1號，3號的隊列添入排隊子鍊表時，在0號添入時，由於此時第一優 先級的排隊子鍊表為空，地址0就是鍊表尾地址，將0號隊列存儲於地址0中，此時，地址1 就是鍊表尾地址，將1號隊列再添入地址1中。如圖2所示，對於第二優先級的隊列如前述 8、6、9號隊列，仍按前述方法添入到排隊子鍊表中，對於第二優先級的排隊子鍊表，首地址 可以是地址8，地址8的下一跳為地址6，存儲6號隊列，而地址6的下一跳為地址9，用於存 儲9號隊列。存儲的隊列嚴格按照排隊子鍊表中的地址指針進行即可，首地址存儲首個添 入的隊列，之後所有的隊列依序存儲到排隊子鍊表的尾地址中。本發明最優的實現方式是地址數與隊列數是相等的，此時，隊列數和地址數一一 對應。本發明中，只要避免同一個地址對應不同的隊列即可。本發明僅以第一、二優先級的隊列添入排隊子鍊表為例進行了說明，其餘優先級 的隊列添入相應優先級的排隊子鍊表的方式與此完全相同，這裡不再贅述。本發明還包括在所述排隊鍊表中選擇優先級最高的非空排隊子鍊表進行隊列調 度，優先級最高的非空排隊子鍊表調度完畢後選擇次優先級的非空排隊子鍊表進行隊列調 度。在排隊子鍊表中進行隊列調度時，首先從排隊子鍊表的頭部輸出，再按排隊子鍊表頭部指針的指示調度下一隊列出隊，直到排隊子鍊表為空。仍以前述的隊列為例，如第一優先級隊列輸出順序依次為0號，1號，3號，...，在 第一優先級對應的排隊子鍊表中的隊列調度完畢後，查找出當前優先級最高的非空排隊子 鍊表，如是第二優先級排隊子鍊表，其隊列輸出依次為8號，6號，9號，...，接著是第三優先 級排隊子鍊表，其隊列輸出依次為35號，13號，30號，20號，等等。圖3為本發明基於鍊表的隊列調度裝置的組成結構示意圖，如圖3所示，本發明基 於鍊表的隊列調度裝置包括設置單元30、劃分單元31、判斷單元32、添入單元33和標識修 改單元34，其中，設置單元30用於設置排隊鍊表中的地址不少於總隊列的數目，以及，為各 隊列設置標識其是否在所述排隊鍊表中排隊的排隊鍊表標識符；劃分單元31用於按隊列 所屬優先級將所述排隊鍊表劃分為不同的排隊子鍊表，其中，所述排隊子鍊表中的地址不 少於所述排隊子鍊表所對應優先級下的所有隊列數；判斷單元32用於在將符合排隊條件 的隊列添入所述排隊鍊表之前，根據所述隊列的排隊鍊表標識符判斷所述隊列是否已在所 述排隊鍊表中排隊，若已排隊則不作添入處理，若未排隊則觸發添入單元33;添入單元33 用於將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部，並觸發標識修改單元 34 ；標識修改單元34用於將所述隊列的排隊鍊表標識符修改為已在所述排隊鍊表中排隊 的標識。如圖3所示，本發明基於鍊表的隊列調度裝置還包括調度單元35，用於在所述排 隊鍊表中選擇優先級最高的排隊子鍊表進行隊列調度，優先級最高的排隊子鍊表調度完畢 後選擇次優先級最高的排隊子鍊表進行隊列調度。。本領域技術人員應當理解，調度單元35是為優化本發明基於鍊表的隊列調度裝 置的技術方案而設置的，並非實現本發明技術方案的必要部件。本領域技術人員應當理解，本發明圖3所示的基於鍊表的隊列調度裝置是為實現 圖1所示的基於鍊表的隊列調度方法而設計的，圖3所示裝置中的各處理單元及處理模塊 的實現功能可參照圖1所示的方法中的相關描述而理解，各單元及各模塊的功能可通過運 行於處理器上的程序而實現，也可通過相應的邏輯電路而實現。以上所述，僅為本發明的較佳實施例而已，並非用於限定本發明的保護範圍。
8
權利要求
一種基於鍊表的隊列調度方法，其特徵在於，包括設置排隊鍊表中的地址數不少於隊列數，並按隊列所屬優先級將所述排隊鍊表劃分為不同的排隊子鍊表，其中，所述排隊子鍊表中的地址數不少於所述排隊子鍊表所對應優先級下的所有隊列數；為各隊列設置標識其是否在所述排隊鍊表中排隊的排隊鍊表標識符；以及在將符合排隊條件的隊列添入所述排隊鍊表之前，根據所述隊列的排隊鍊表標識符判斷所述隊列是否已在所述排隊鍊表中排隊，若已排隊則不作添入處理，若未排隊則將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部，並將所述隊列的排隊鍊表標識符修改為已在所述排隊鍊表中排隊的標識。
2.根據權利要求1所述的方法，其特徵在於，所述方法還包括 在所述排隊鍊表中選擇優先級最高的非空排隊子鍊表進行隊列調度，優先級最高的非 空排隊子鍊表調度完畢後選擇次優先級的非空排隊子鍊表進行隊列調度。
3.根據權利要求2所述的方法，其特徵在於，排隊子鍊表進行隊列調度時，由鍊表的頭 部開始，按鍊表指針指示進行隊列調度。
4.根據權利要求1所述的方法，其特徵在於，所述方法還包括優先級相同的已出隊的 隊列與待入隊的隊列均符合排隊條件時，優先將已出隊的隊列添入所述排隊鍊表中。
5.根據權利要求1所述的方法，其特徵在於，所述排隊鍊表標識符為1比特，0標識已 在所述排隊鍊表中排隊，1標識未在所述排隊鍊表中排隊；或者，0標識未在所述排隊鍊表 中排隊，1標識已在所述排隊鍊表中排隊。
6.根據權利要求1所述的方法，其特徵在於，每個隊列號對應於排隊鍊表中的一個地址。
7.一種基於鍊表的隊列調度裝置，其特徵在於，包括設置單元，用於設置排隊鍊表中的地址不少於總隊列的數目，以及，為各隊列設置標識 其是否在所述排隊鍊表中排隊的排隊鍊表標識符；劃分單元，用於按隊列所屬優先級將所述排隊鍊表劃分為不同的排隊子鍊表，其中，所 述排隊子鍊表中的地址不少於所述排隊子鍊表所對應優先級下的所有隊列數；判斷單元，用於在將符合排隊條件的隊列添入所述排隊鍊表之前，根據所述隊列的排 隊鍊表標識符判斷所述隊列是否已在所述排隊鍊表中排隊，若已排隊則不作添入處理，若 未排隊則觸發添入單元；添入單元，用於將所述隊列添入所述隊列優先級對應的排隊子鍊表的鍊表尾部，並觸 發標識修改單元；以及標識修改單元，用於將所述隊列的排隊鍊表標識符修改為已在所述排隊鍊表中排隊的 標識。
8.根據權利要求7所述的裝置，其特徵在於，所述裝置還包括調度單元，用於在所述排隊鍊表中選擇優先級最高的排隊子鍊表進行隊列調度，優先 級最高的排隊子鍊表調度完畢後選擇次優先級最高的排隊子鍊表進行隊列調度。
9.根據權利要求8所述的裝置，其特徵在於，所述調度單元排隊子鍊表進行隊列調度 時，由鍊表的頭部開始，按鍊表指針指示進行隊列調度。
10.根據權利要求7所述的裝置，其特徵在於，所述添入單元在優先級相同的已出對的隊列與入對的隊列均符合排隊條件時，優先將已出對的隊列添入所述排隊鍊表中。
11.根據權利要求7所述的裝置，其特徵在於，每個隊列號對應於排隊鍊表中的一個地址。
全文摘要
本發明公開了一種基於鍊表的隊列調度方法，包括設置排隊鍊表中的地址數不少於隊列數，並按隊列所屬優先級將排隊鍊表劃分為不同的排隊子鍊表，其中，排隊子鍊表中的地址數不少於排隊子鍊表所對應優先級下的所有隊列數；為各隊列設置標識其是否在排隊鍊表中排隊的排隊鍊表標識符；在將符合排隊條件的隊列添入排隊鍊表之前，根據隊列的排隊鍊表標識符判斷隊列是否已在排隊鍊表中排隊，若已排隊則不作添入處理，若未排隊則將隊列添入隊列優先級對應的排隊子鍊表的鍊表尾部，並將隊列的排隊鍊表標識符修改為已在排隊鍊表中排隊的標識。本發明同時公開了一種基於鍊表的隊列調度裝置。本發明保證了同優先級隊列調度時的公平性。
文檔編號H04L12/56GK101902487SQ20091008563
公開日2010年12月1日 申請日期2009年5月26日 優先權日2009年5月26日
發明者廖慶磊, 廖智勇, 賴偉 申請人:中興通訊股份有限公司