一種通信設備軟體子系統的消息調度方法
2023-10-30 17:14:17
專利名稱：一種通信設備軟體子系統的消息調度方法
技術領域：
本發明涉及通信設備軟體子系統中消息的組織和調度，特別是涉及大型通信設備軟體子系統的一種快速高效的消息調度方法。
一個分布式消息映射表可由n個被稱為消息映射子表的數據結構組成，其中的消息映射子表可以是集中式消息映射子表，又可以是分布式消息映射子表。因為消息註冊表是由程式設計師在編程時定義、輸入數據並提供空間。因此，註冊消息的接口數據在消息註冊表中的相對位置是隨機的。消息號與消息接口數據在消息註冊表中的存儲位置之間不存在確定的對應關係。如果不對消息註冊表進行預加工，直接使用消息註冊表的存儲空間生成消息映射表，雖然能高效地利用存儲空間，但是在消息調度程序定位消息在消息映射表中的位置時，唯一能使用的方法是對消息號進行逐一的匹配比較。查找的效率依賴於查找過程中所進行的比較次數。對一個規模為n的消息映射表，其平均查找長度為n/2。隨著消息映射表規模的增大，軟體子系統的調度效率急劇下降。採用上述方案的現有技術，如微軟的Visual C++的MFC編程框架的消息映射處理機制，以及C和C++語言中編譯器對Switch-Case語句的處理，均存在查找效率低的問題。
現在來說明微軟的Visual C++的MFC編程框架的消息映射處理機制和C、C++語言中編譯器對Switch-Case子系統的處理。從VisualC++提供MFC編程框架源碼可以看到MFC編程框架維護著一個分布式的消息映射表，當MFC的消息調度框架接收到一個消息時，在消息映射表中通過比較匹配查找到該消息對應的消息處理函數的入口，依此進行調度。位於消息映射表位置k的消息接口在調度時需經過k次比較。當消息規模不大或者系統對效率不敏感時，這種匹配方法是可以接受的。但是當系統要求高效率調度時，使用這種匹配方法顯然是不合適。從編譯後的彙編代碼可以看到C、C++語言的編譯器把Switch-Case子系統認為是if-else的另一種表示方式。在這裡存在一個抽象的分布式的消息映射表。系統通過比較匹配查找到相應的Case入口。當Case分支數不多時，系統調度的效率可以接受。但是當系統要求高效率調度時，使用這種匹配方式對Switch-Case子系統進行調度顯然不合適。而且，以上兩個例子還有一個不容易注意到的缺陷即在實際應用中，每一個消息、每一個Case分支被使用的頻率是不同的，因此，難以為每一個實際的系統提供最佳的調度策略。
在大型通信設備中還存在不同處理機之間的消息在交互時出現的字節順序問題。如x86是低字節在低地址(小模式)，PPC是高字節在高地址(大模式)。將字節順序問題完全交給應用層解決不僅程序效率低，而且容易出錯。在以上描述中，x86表示Intel公司386、486、pentium系列的處理器晶片。PPC表示Motorola、IBM的PowerPC系列的處理器晶片。在這兩種處理器晶片之間進行通信，就存在字節順序問題。例如，對內存中按12 34 56 78方式排列的數據，x86認為是0x78563412，PPC則認為是0x12345678。傳統的處理方法是將數據轉換成網絡序(大模式)進行交互，數據到達後，在各處理器上再根據自身字節順序跟網絡序的差異進行轉換。因此當兩邊都是小模式處理器晶片時，就存在冗餘的轉換。而且程式設計師常常會因為遺忘對字節順序的處理而導致數據辨認出錯本發明的上述技術問題是這樣解決的，構造一種通信設備軟體子系統的消息調度方法，包括以下步驟1)對一個規模為n的分布式的原始消息註冊表，申請一個大小為n的指針n的指針數組並根據規模n確定一個可以接受的衝突鍊表的最大長度L＜n；2選擇一個哈希函數對其消息號或消息關鍵字產生一個處於[1，n]區間的哈希地址；3掃描原始的消息註冊表，對每一個消息關鍵字產生其哈希地址，以該產生的哈希地址作為前邊申請的指針數組的索引，把該索引對應的指針指向該消息關鍵字對應消息的接口表項的存儲地址，如果發生兩個或多個索引指向同一個接口表項的則以鍊表方式解決；4如果哈希化後消息映射表的衝突鍊表的長度小於預定長度L，則消息註冊表的哈希化成功，否則返回步驟2。
在按照本發明提供的方法中，還包括以下步驟1)收到一個消息時，以該消息的關鍵字為依據，根據前述步驟確定的所述哈希函數計算出該消息關鍵字的哈希地址；2)依據計算出的該哈希地址獲得消息處理入口進行相應的消息處理，如果該哈希地址存在衝突鍊表，則進行比較匹配，找到與消息關鍵字對應的消息處理過程入口則進行相應消息處理；3)將該消息的使用記數加1，比較該消息接口與它在衝突鍊表的前一個消息接口的使用記數，如果大於則進行優化，調整其在衝突鍊表中的位置，等待下一個消息進行調度。
在按照本發明提供的方法中，還包括以下步驟對每個消息接口保存一個使用記數的記錄，以及每次該消息接口被調度時，該使用記數的值加1，如果當前消息接口的使用記數大於其衝突鍊表中前一個消息接口的使用記數，則將這兩個消息接口在衝突鍊表中的位置進行互換，只到當前消息接口的使用記數不大於處於其衝突鍊表前的消息接口的使用記數。
在上述按照本發明提供的方法中，還包括以下步驟在應用層定義並註冊消息的字節消息交換函數；由調度系統判斷源處理機與本地處理機的字節順序是否一致，如果不一致則調用應用層註冊的所述字節消息交換函數來完成字節轉換。
在上述按照本發明提供的方法中，用程式設計師提供的消息註冊表的存儲空間來存放消息映射表。
在按照本發明的另一個方面提供的一種適用於通信設備軟體子系統的消息調度方法中，包括以下步驟1)備份消息註冊表，把原始消息註冊表的所有表項設置為未使用，備份消息註冊表的所有表項為「未哈希」；2)根據規模數n，確定一個可以接受的衝突鍊表的最大長度L；3)選擇一個哈希函數使其對消息註冊表中消息號產生的哈希地址出現在[1，n]區間；4)第一次掃描備份消息註冊表，以消息號的哈希地址為索引在原始的消息註冊表中存儲該消息接口，並加上佔用標誌，同時在備份消息消息表中把該消息接口加上哈希成功標誌，當發生哈希地址衝突時，略過該消息接口的處理，留待第二次掃描加以處理；5)第二次掃描備份消息註冊表，在原始消息註冊表中找到未用的表項空間用於存儲備份消息註冊表中未哈希成功的消息接口數據，並把該表項附加到相應的衝突鍊表中，生成一個集中式的進程的哈希消息映射表；6)如果所述哈希消息映射表衝突鍊表的最大長度小於L，則哈希化成功，釋放備份的存儲空間，否則，重置原始消息註冊表為未使用，重置備份消息註冊表為未哈希，返回到步驟(2)。
在上述按照本發明提供的方法中，還包括以下步驟1)收到一個消息時，以該消息的關鍵字為依據前述步驟確定的所述哈希函數計算出該消息關鍵字的哈希地址；2)依據計算出的該哈希地址獲得消息處理入口進行相應的消息處理，如果該哈希地址存在衝突鍊表，則進行比較匹配，找到與消息關鍵字對應的消息處理過程入口則進行相應消息處理；3)將該消息的使用記數加1，比較該消息接口與它在衝突鍊表的前一個消息接口的使用記數，如果大於則進行優化，調整其在衝突鍊表中的位置，等待下一個消息進行調度。
在上述按照本發明提供的方法中，還包括以下步驟對每個消息接口保存一個使用記數的記錄，以及每次該消息接口被調度時，該使用記數的值加1；如果當前消息接口的使用記數大於其衝突鍊表中前一個消息接口的使用記數，則將這兩個消息接口在衝突鍊表中的位置進行互換，只到當前消息接口的使用記數不大於處於其衝突鍊表前的消息接口的使用記數。
在上述按照本發明提供的方法中，還包括以下步驟在應用層定義並註冊消息的字節消息交換函數；由調度系統判斷源處理機與本地處理機的字節順序是否一致，如果不一致則調用應用層註冊的所述字節消息交換函數來完成字節轉換。
在上述按照本發明提供的方法中，用程式設計師提供的消息註冊表的存儲空間來存放所述消息映射表。
實施上述按照本發明提供的通信設備軟體子系統的消息調度方法，對任意規模的消息映射表，只需有限的步驟即可找到消息處理過程和字節轉換函數的入口，降低了字節順序轉換出錯的機會，既快速又高效，適合於大型通信設備軟體子系統的消息調度。
圖2是集中式消息註冊表的示意圖。
圖3是分布式消息註冊表哈希化生成的分布式消息映射表的結構示意圖。
圖4是集中式消息註冊表的哈希化生成集中式消息映射表的結構示意圖。
圖5是說明按照本發明方法進行消息調度方法的流程圖。
圖6是集中式消息註冊表哈希化為消息映射表的流程圖。
圖7是分布式消息註冊表哈希化為消息映射表的流程圖。
圖8是本發明一個實施例的通信產品中實時作業系統平臺的快速高效的進程消息調度中的實現流程圖。
對於集中式的消息註冊表，本方法提供了更優的哈希消息映射表生成方法，不需佔用任何額外空間。在哈希化中形成的備份的消息註冊表在消息映射表生成後會被釋放。因此，只需在生成哈希消息映射表的過程中變換消息接口在消息註冊表的存儲位置即可，如圖2所示集中式註冊表經過本發明方法的哈希化形成的哈希化的集中式映射表的結構情況如圖4所示。由於採用一種二次掃描的方法將集中式的消息註冊錶轉換成哈希化的集中式消息映射表，完全避免了存儲空間的浪費。本發明方法採用這種二次掃描技術進行哈希化的具體過程步驟如圖6所示。首先在框601中，備份消息註冊表，把原消息註冊表的所有表項設置為未使用，備份消息註冊表的所有表項為未哈希。根據規模n確定一個可以接受的衝突鍊表的最大長度L；在框602中，對規模為n的消息註冊表，選擇一個哈希函數使其對消息註冊表中消息號產生的哈希地址出現在[1，n]區間；在框603中，第一次掃描備份的消息註冊表，以消息號的哈希地址為索引在原消息註冊表中存儲該消息接口，並加上佔用標誌，同時在備份消息註冊表中把該消息接口加上哈希成功標誌，當發生哈希地址衝突時，略過該消息接口的處理，留待第二次掃描加以處理；在框604中，第二次掃描備份的消息註冊表，解決哈希地址衝突問題，在原始消息註冊表中找到未用的表項空間用於存儲備份消息註冊表中的消息接口數據。並把該表項附加到相應的衝突鍊表中，生成哈希消息映射表。因為在原始消息註冊表中，只要有一個哈希地址衝突，依據抽屜原則，那麼必然存在一個表項空間富餘，因此，不會有空間浪費和不足的問題；在框605中，評價該哈希消息映射表衝突鍊表的最大長度，滿足要求，則成功，釋放備份的空間；否則，重置原始消息註冊表為未使用，重置備份消息註冊表為未哈希。返回到框602。
對於分布式的消息註冊表，採用鍊表方式處理衝突，只需要一個額外的指針數組空間即可生成哈希的分布式的消息映射表。由於採用鍊表方式解決哈希地址衝突，因此，對於分布式的消息註冊表，軟體子系統只需申請一個額外的指針數組空間，通過指針指向原始的消息註冊表的表項，不需移動任何數據，即可快速高效的生成哈希表，，例如，
圖1所示分布式消息註冊表，經過哈希化後形成的分布式消息映射表如圖3所示。而將圖1所示分布式註冊表的哈希化為如圖3所示分布式消息映射表的過程步驟如圖7所示。
在框701中，對一個規模為n的分布式的原始消息註冊表，申請一個大小為n的指針數組並根據規模n確定一個可以接受的衝突鍊表的最大長度；在框702中，選擇一個哈希函數對其消息號產生的哈希地址，哈希地址在[1，n]區間；在框703中，掃描原始的消息註冊表，對每一個消息關鍵字產生其哈希地址，以該哈希地址為前邊申請的指針數組的索引，把該索引對應的指針指向該消息關鍵字對應消息的接口表項，如果發生衝突以鍊表方式解決；而在框704中，評估哈希化後消息映射表的衝突鍊表的長度小於預定長度，則消息註冊表的哈希化成功，否則返回到框703。
對於分布式的進程消息註冊表中的消息規模龐大的集中式註冊子表，本方法也可以採用集中式消息註冊表的處理辦法，以儘量減小存儲空間的浪費。
本發明方法嚴格限制衝突鍊表的長度，以獲得最佳的調度性能。為此，本發明方法採用自適應選用哈希函數對每組用戶定義的接口生成哈希地址的辦法以防止某組消息接口數據哈希化後，衝突數過多而影響系統消息調度的性能。
由於在實際應用中，消息的發生頻率各不相同，為進一步提高系統消息調度的實際性能，可採用動態優化哈希地址衝突的消息接口在鍊表中的位置的辦法，使用頻率高的接口放在衝突鍊表的前邊，減少系統對衝突鍊表中的消息接口進行調度時，實際進行匹配比較的次數，達到快速調度的目的。
為解決大型通信設備中存在的不同處理機之間的消息的交互時會存在字節順序問題。本方法由應用層與調度系統協同解決。應用層定義並註冊消息的字節交換函數。由調度系統根據源處理機的字節順序與本地處理機是否一致來決定是否調用應用層註冊的消息交換函數來完成字節轉換。
在實施本發明的方法時，具體可以在軟體編程階段，應用層的程式設計師註冊消息處理函數和字節轉換函數的入口。在軟體子系統初始化階段，對軟體子系統上層應用的程式設計師編程時提供原始的消息註冊表進行哈希化處理，充分利用原始的消息註冊表的存儲空間生成進程哈希消息映射表。同時，可以由調度系統根據源處理機的字節順序與本地處理機是否一致來決定是否調用應用層註冊的消息交換函數來完成字節轉換。即，如果源處理機與本地處理機的字節順序一致，則無須字節交換，否則，調用應用層註冊的消息交換函數來完成字節交換，從而最大限度減少因為程式設計師的遺忘而導致的程序錯誤。
按照本發明的通信設備軟體子系統的調度過程如圖5所示，它是根據圖6或圖7生成的消息映射表進行的。具體是在軟體子系統的運行階段，當消息調度系統接收到一個消息時(框501)，利用哈希函數計算出該消息對應的消息處理過程入口的存儲位置(框502)，進行消息調度(框503)，同時採用實際運行時的頻率統計，優化調整衝突鍊表中消息接口的順序(框504)，提高調度的實際效率，完成後等待下一個消息進行調度(框505)。
本方法應用實施例之一某通信產品的實時作業系統平臺中的快速高效進程消息調度機制。作業系統上層應用的程式設計師提供一個集中式消息註冊表，在作業系統的進程初始化階段，用二次掃描的方法完成消息註冊表的哈希化生成一個集中式的進程哈希消息映射表。如附圖8，(1)先備份消息註冊表，把原始消息註冊表801的所有表項設置為未使用，備份消息註冊表802的所有表項為未哈希。根據規模n此處為14，確定一個可以接受的衝突鍊表的最大長度4；(2)選擇一個哈希函數使其對消息註冊表中消息號產生的哈希地址出現在[1，14]區間，此處哈希函數為消息號mod 14；(3)第一次掃描備份的消息註冊表，以消息號的哈希地址為索引在原始的消息註冊表中存儲該消息接口，並加上佔用標誌，同時在備份消息註冊表中把該消息接口加上哈希成功標誌，當發生哈希地址衝突時，略過該消息接口的處理，留待第二次掃描加以處理，第一次掃描後的原始消息註冊表和備份消息註冊表如803和804指出；(4)第二次掃描備份的消息註冊表，解決哈希地址衝突問題，在原始消息註冊表中找到未用的表項空間用於存儲備份消息註冊表中未哈希成功的消息接口數據。並把該表項附加到相應的衝突鍊表中，生成一個集中式的進程的哈希消息映射表，如805指出；(5)評價該哈希消息映射表衝突鍊表的最大長度，滿足要求，則成功，釋放備份消息映射表806的空間。否則，重複(2)步驟。
當作業系統的進程消息調度系統接收到一個消息時，利用哈希函數計算出該消息對應的消息處理過程入口的存儲位置，進行消息調度，同時採用實際運行時的頻率統計，優化調整衝突鍊表中消息接口的順序，提高調度的實際效率。
本發明方法應用實施例之二在C、C++編譯器中，當需要對大規模的Switch-Case調度系統進行優化時，編譯器生成一個集中式的消息映射表，用二次掃描的方法完成消息映射表的哈希化。替換原來的調度代碼，插入一段調度和優化代碼，當調度系統接收到一個消息時，利用哈希函數計算出該消息對應的消息處理過程入口的存儲位置，進行消息調度，同時採用實際運行時的頻率統計，優化調整衝突鍊表中消息接口的順序，提高調度的實際效率。
權利要求
1.一種適用於通信設備軟體子系統的消息調度方法，其特徵在於，包括以下步驟1)對一個規模為n的分布式的原始消息註冊表，申請一個大小為n的指針n的指針數組並根據規模n確定一個可以接受的衝突鍊表的最大長度L＜n；2)選擇一個哈希函數對其消息號或消息關鍵字產生一個處於[1，n]區間的哈希地址；3)掃描原始的消息註冊表，對每一個消息關鍵字產生其哈希地址，以該產生的哈希地址作為前邊申請的指針數組的索引，把該索引對應的指針指向該消息關鍵字對應消息的接口表項的存儲地址，如果發生兩個或多個索引指向同一個接口表項的則以鍊表方式解決；4)如果哈希化後消息映射表的衝突鍊表的長度小於預定長度L，則消息註冊表的哈希化成功，否則返回步驟2)。
2.根據權利要求1所述方法，其特徵在於，還包括以下步驟1)收到一個消息時，以該消息的關鍵字為依據，根據前述步驟確定的所述哈希函數計算出該消息關鍵字的哈希地址；2)依據計算出的該哈希地址獲得消息處理入口進行相應的消息處理，如果該哈希地址存在衝突鍊表，則進行比較匹配，找到與消息關鍵字對應的消息處理過程入口則進行相應消息處理；3)將該消息的使用記數加1，比較該消息接口與它在衝突鍊表的前一個消息接口的使用記數，如果大於則進行優化，調整其在衝突鍊表中的位置，等待下一個消息進行調度。
3.根據權利要求1所述的方法，其特徵在於，包括以下步驟對每個消息接口保存一個使用記數的記錄，以及每次該消息接口被調度時，該使用記數的值加1，如果當前消息接口的使用記數大於其衝突鍊表中前一個消息接口的使用記數，則將這兩個消息接口在衝突鍊表中的位置進行互換，只到當前消息接口的使用記數不大於處於其衝突鍊表前的消息接口的使用記數。
4.根據權利要求1-3中任一項所述方法，還包括以下步驟在應用層定義並註冊消息的字節消息交換函數；由調度系統判斷源處理機與本地處理機的字節順序是否一致，如果不一致則調用應用層註冊的所述字節消息交換函數來完成字節轉換。
5.根據權利要求1-3中任一項所述方法，其特徵在於，用程式設計師提供的消息註冊表的存儲空間來存放消息映射表。
6.一種適用於通信設備軟體子系統的消息調度方法，其特徵在於，包括以下步驟1)備份消息註冊表，把原始消息註冊表的所有表項設置為未使用，備份消息註冊表的所有表項為「未哈希」；2)根據規模數n，確定一個可以接受的衝突鍊表的最大長度L；3)選擇一個哈希函數使其對消息註冊表中消息號產生的哈希地址出現在[1，n]區間；4)第一次掃描備份消息註冊表，以消息號的哈希地址為索引在原始的消息註冊表中存儲該消息接口，並加上佔用標誌，同時在備份消息消息表中把該消息接口加上哈希成功標誌，當發生哈希地址衝突時，略過該消息接口的處理，留待第二次掃描加以處理；5)第二次掃描備份消息註冊表，在原始消息註冊表中找到未用的表項空間用於存儲備份消息註冊表中未哈希成功的消息接口數據，並把該表項附加到相應的衝突鍊表中，生成一個集中式的進程的哈希消息映射表；6)如果所述哈希消息映射表衝突鍊表的最大長度小於L，則哈希化成功，釋放備份的存儲空間，否則，重置原始消息註冊表為未使用，重置備份消息註冊表為未哈希，返回到步驟(2)。
7.根據權利要求6所述方法，其特徵在於，還包括以下步驟1)收到一個消息時，以該消息的關鍵字為依據前述步驟確定的所述哈希函數計算出該消息關鍵字的哈希地址；2)依據計算出的該哈希地址獲得消息處理入口進行相應的消息處理，如果該哈希地址存在衝突鍊表，則進行比較匹配，找到與消息關鍵字對應的消息處理過程入口則進行相應消息處理；3)將該消息的使用記數加1，比較該消息接口與它在衝突鍊表的前一個消息接口的使用記數，如果大於則進行優化，調整其在衝突鍊表中的位置，等待下一個消息進行調度。
8.根據權利要求1所述的方法，其特徵在於，包括以下步驟對每個消息接口保存一個使用記數的記錄，以及每次該消息接口被調度時，該使用記數的值加1；如果當前消息接口的使用記數大於其衝突鍊表中前一個消息接口的使用記數，則將這兩個消息接口在衝突鍊表中的位置進行互換，只到當前消息接口的使用記數不大於處於其衝突鍊表前的消息接口的使用記數。
9.根據權利要求6-8中任一項所述方法，還包括以下步驟在應用層定義並註冊消息的字節消息交換函數；由調度系統判斷源處理機與本地處理機的字節順序是否一致，如果不一致則調用應用層註冊的所述字節消息交換函數來完成字節轉換。
10.根據權利要求6-8任何一項所述方法，其特徵在於，用程式設計師提供的消息註冊表的存儲空間來存放所述消息映射表。
全文摘要
本發明涉及通信設備軟體子系統中消息的組織和調度，特別是涉及大型通信設備軟體子系統的一種快速高效的消息調度方法。該方法包括將原始消息註冊表構造成集中或分布式消息映射表，在構造過程中尋找並確定消息號或消息關鍵字與其存放地址的對應關係，當這種對應關係採用哈希函數方式表示時，產生地址衝突時，採用可動態優化的鍊表來解決。利用本發明提供的通信設備軟體子系統的消息調度方法，對任意規模的消息映射表，只需有限的步驟即可找到消息處理過程和字節轉換函數的入口，降低了字節順序轉換出錯的機會，既快速又高效，適合於大型通信設備軟體子系統的消息調度。
文檔編號H04Q3/545GK1399476SQ0112632
公開日2003年2月26日 申請日期2001年7月20日 優先權日2001年7月20日
發明者吳晨, 李遠威 申請人:深圳市中興通訊股份有限公司上海第二研究所