負載均衡調度方法和裝置的製作方法
2023-06-03 20:13:51 3
專利名稱：負載均衡調度方法和裝置的製作方法
技術領域：
本發明涉及計算枳4喿作系統中的任務調度領域，更具體地，涉 及一種負載均衡調度方法和裝置。
背景技術：
隨著微處理器才支術的發展，多核，超線程已經成為發展主流， 目前，X86、 PPC、 MIPS、 ARM等主流商用處理器體系都已經推出， 或正在計劃推出多核、超線程的商用處理器，這些處理器的多核結 構都是基於對稱多處理器體系的，即各處理單元沒有主次之分，都 是平等的。相對於普通單核體系的處理器來說，具備多核和超線程 特性的處理器具備多個#1行單元，可以同時運行多個任務，這和單 核處理器一個時間只能運行一個任務的情況完全不同，為了支持多 核，超線程處理器的這種特性，需要在4喿作系統的任務調度上做相 應i殳計，以充分發4軍處理器的這種並4於處理能力。
在目前已經商用的作業系統中，也提供了對多處理器系統的支 才寺，比如Linux、 BSD、 Windows等。在這些作業系統中，會定時 統計系統中各處理器的利用率，當不同處理器之間的利用率差別超 過一定閾值時，就將啟動任務遷移的操作，將任務從比較忙的處理 器上遷移到比較閒的處理器上。但是，這些作業系統主要是為傳統 的伺服器設計，在調度上更注重調度的公平性，資源在各個進程之 間的均tf分配。在電信、電力、航空航天等領域的嵌入式系統中，大量用到了 各種樣t處理器，隨著處理器糹支術的發展，使用於這些領域上的樣吏處 理器性能也在不斷^是高，具有多核，超線程特性的處理器已經或即 將進入應用。對於在這些領域的嵌入式系統上運行的業務應用來說， 一般要求作業系統提供強實時性，強效率等特性，對於高優先級的
任務，必須優先運行；由此可見，現有的才乘作系統對多核，超線程 處理器的支持方式不能完全滿足許多嵌入式系統的需要，具有如下 缺點
1、 其負載均衡方法不是基於優先級均衡的方法，在整個對稱多 處理器系統中，各處理器上的運行隊列優先級不均衡，不能確保系 統內的每一個處理器上運行任務的優先級都比等待任務的優先級要 高，會出現高優先級的任務在一個處理器上等待，而比它優先級低 的任務卻在其它處理器得到運行；
2、 無法有效支持互斥信號量的優先級繼承，在現有糹喿作系統的 支持才莫式下，由於無法4呆證在整個系統空間的優先級一致性，所以 對互斥信號量的優先級繼承只能在處理器內部實現，無法在整個對 稱多處理器系統內實J見；以及
3、 其均衡操作的時機不是基於優先級的，是按照各處理器的運 行效率來觸發的，無法滿足高優先級任務必須在系統中得到及時4丸 行的要求。
發明內容
為了解決現有技術中的問題，本發明提出了 一種負載均衡調度 方法，用於在嵌入式實時對稱多處理器系統中，通過一個負載均衡 監控才莫塊和^立於所述嵌入式實時對稱多處理器系統中的各個處理單
元的多個負載均4軒處理才莫塊，Y吏對稱多處理器系統中的各個處理單元之間達到均4軒，即，保證系統中各處理器中優先級均衡，並在系 統各處理器出現不均#f情況時，通過主動和—皮動的兩種方式在系統 內的處理器間進行任務的遷移，使系統隨時保持均衡。
根據本發明的一個方面，提供了一種負載均衡調度方法，其包
括以下步驟步驟一，啟動周期運行的負載均4軒監控才莫塊來監控多
處理器系統中各個處理單元的任務優先級的分布，並且當監控到各
差值超過預設閾值時，負載均衡監控模塊確定源處理單元、目的處 理單元、和所要執行的任務調度的優先級，並向相關負載均衡處理
模塊均發起負載均衡調度消息；以及步驟二，在接收到負載均衡調 度消息後，相關負載均衡處理模塊根據各個處理單元的任務優先級 的分布以及各個處理單元之間的關係來執行任務調度，從而使對稱 多處理器系統中的各個處理單元之間達到均4軒。
在步每聚一之前，該方法還包^舌步-驟a,在多處理器系統初始 化後，為處理單元中的每個建立一個任務優先級隊列表；步驟b， 為每個處理單元的各個優先糹及生成一個^i"應的空《連表頭並》i:在4壬務 優先級隊列表中；步驟c，讀取多處理器系統的配置信息以及各個 處理單元的信息，建立各個處理單元之間的樹形關係結構層次圖； 以及步驟d,才艮據樹形關係結構層次圖，確定在各個處理單元之間 進行任務調度的一又重。
在上述步驟c中，還包括將樹形關係結構層次圖分為三個層 次，其中，第一層次為超線程處理單元，第二層次為同一個晶片內 部的多核處理單元，以及第三層次為不同晶片^旦^f吏用同一內存的多 晶片處理單元。
另外，在步驟一中，在定時啟動負載均衡監控模塊之後，執行 以下處理負載均4lf監控才莫塊遍歷每個處理單元，並獲得每個處理單元的任務優先級隊列表，以獲得各個處理單元在當前任務優先級
上的任務數量；才艮據各個處理單元在當前任務優先級上的任務^:量， 獲得各個處理單元在當前任務優先級上的任務數量之間的最大差 值，將最大差值與預設閾值進行比較；當最大差值大於預設閾值時， 將在當前任務優先級上的任務數量最多的處理單元確定作為將要進 行任務調度的源處理單元；根據源處理單元在當前任務優先級上的 任務數量以及樹形關係結構層次圖，確定在當前任務優先級上，源 處理單元與各個層次上的處理單元之間的任務悽t量的最大差^直；以 及將最大差值小於預設閾值並且任務數量最少的處理單元確定為目 的處理單元。
在步驟一中還執行以下處理負載均衡監控模塊將目的處理單 元、源處理單元、以及任務調度的優先級通知給相關負載均衡處理 模塊，並向相關負載均衡處理模塊發起負載均# 調度消息。
在本發明中，負載均衡調度消息至少包括源處理單元信息、 目的處理單元信息、以及所要執行的任務調度的優先級信息。
在步驟二中，執行以下處理在接收到負載均衡調度消息後， 源處理單元的負載均4軒處理才莫塊解析出源處理單元信息、目的處理 單元信息、以及所要執行的任務調度的優先級信息；計算源處理單 元、目的處理單元在所要執行的任務調度的優先級上的任務數量的 平均值，以確定源處理單元的任務悽t量與平均值的差值；4艮據差值， 源處理單元的負載均tf處理才莫塊鎖定源處理單元，並乂人4壬務優先糹及
任務；源處理單元的負載均;斷處理才莫塊將任務/人源處理單元的4壬務
的負載均4軒處理才莫塊向目的處理單元的負載均4軒處理才莫塊發起負載 均tf調度消息。另外，在步驟二中，還執行以下處理在接收到負載均衡調度
消息後，目的處理單元的負載均4軒處理才莫塊鎖定目的處理單元，並
將任務加入到目的處理單元的任務優先級隊列表中；目的處理單元 的負載均4軒處理才莫塊解除對目的處理單元的鎖定。
根據本發明的另 一個方面，還提供了 一種負載均衡調度裝置， 其包括負載均衡監控模塊，用於經過周期啟動運行來監控多處理 器系統中各個處理單元的任務優先級的分布，並且當監控到各個處
超過預設閾值時，確定源處理單元、目的處理單元、和所要執行的 任務調度的優先級，並向相關負載均衡處理模塊均發起負載均衡調 度消息；以及多個負載均^f處理才莫塊，位於各個處理單元內，與負 載均衡監控模塊相連，用於在接收到負載均衡調度消息後，根據各
行任務調度，從而使對稱多處理器系統中的各個處理單元之間達到 均衡。
另外，該裝置還包括初始化才莫塊，用於初始化多處理器系統， 並為處理單元中的每個建立一個4壬務^尤先級隊列表，為每個處理單 元的各個4尤先級生成一個對應的空糹連表頭並^L在4壬務^尤先級隊列表 中，讀耳又多處理器系統的配置信息以及各個處理單元的4言息，建立 各個處理單元之間的樹形關係結構層次圖，以及根據樹形關係結構
因此，採用本發明，使用系統中優先級分布來做負載均衡的基 本指標，而不是以處理器的空閒率作為負載均4軒的指標。與傳統方 法相比，本發明具有實時響應性能好，負載均衡監控時的計算開銷 小，更適合於嵌入式系統應用。
系來執本發明的其它特徵和優點將在隨後的說明書中闡述，並且，部 分地從說明書中變得顯而易見，或者通過實施本發明而了解。本發 明的目的和其他優點可通過在所寫的說明書、^又利要求書、以及附 圖中所特別指出的結構來實現和獲得。
附圖用來提供對本發明的進一步理解，並且構成說明書的 一部 分，與本發明的實施例一起用於解釋本發明，並不構成對本發明的
限制。在附圖中
圖l是根據本發明的負載均衡調度方法的流程形層次的結構示意圖3是本發明的負載均衡調度方法所涉及的多處理單元多任務 優先》及隊列表的示意圖4是根據本發明的負載均衡調度裝置的框圖5是在圖4中所示的負載均4軒監控才莫塊中所#1行的處理的流 禾呈示意圖；以及
圖6是在圖4中所示的負載均tf處理模塊實體中所執行的任務 遷移處理的流禾呈示意圖。
具體實施例方式
以下結合附圖對本發明的優選實施例進行說明，應當理解，此 處所描述的優選實施例僅用於i兌明和解釋本發明，並不用於限定本 發明。應了解，本發明的實現主要在於兩個模塊負載均4軒監控衝莫塊
和負載均衡處理模塊。其中，負載均衡監控模塊被設置為定時運行， 運行時將檢查整個系統中各處理器的任務負荷狀況，如果出現了任 務負載不均衡的情況，它將在系統內進行分級搜索，搜索出源處理 單元，目的處理單元和待遷移任務優先級，並爿年這些信息通知相應 的負載均4軒處理才莫塊的實體。負載均tf處理才莫塊在每個處理單元上 都有實體，當它收到監控模塊的通知後，會使用收到的任務遷移信 息，將負荷較重的源處理單元中的任務轉移到負荷較輕的目的處理 單元中。
圖1是根據本發明的負載均^f調度方法的流程圖。如圖1所示，
包4舌以下步4聚
S102 ，啟動周期運行的負載均衡監控模塊來監控多處理器系統 中各個處理單元的4壬務伊乙先鄉及的分布，並且當監控到各個處理單元 的任務優先級的分布不均tf且任務優先級的分布的最大差值超過預 i殳閾值時，負載均tf監控才莫塊確定源處理單元、目的處理單元、和 所要執行的任務調度的優先級，並向相關負載均衡處理模塊均發起 負載均tf調度消息；以及
S104，在接收到負載均衡調度消息後，相關負載均衡處理模塊
系來執行任務調度，從而使對稱多處理器系統中的各個處理單元之 間達到均4軒。
在S102之前，本方法還包括步驟a,在多處理器系統初始化 後，為處理單元中的每個建立一個4壬務優先i^隊列表；步驟b，為 每個處理單元的各個優先級生成一個對應的空《連表頭並放在任務優 先級隊列表中；步驟c，讀取多處理器系統的配置信息以及各個處 理單元的信息，建立各個處理單元之間的樹形關係結構層次圖；以
13及步驟d,根據樹形關係結構層次圖，確定在各個處理單元之間進 行任務調度的權重。
在步驟C中，將樹形關係結構層次圖分為三個層次，其中，第 一層次為超線程處理單元，第二層次為同一個晶片內部的多核處理 單元，以及第三層次為不同晶片4旦4吏用同一內存的多晶片處理單元。
在步驟d中，設定第一層次間的任務調度的權重小於第二層次 間的任務調度的權重，以及設定第二層次間的 <壬務調度的權重小於 第三層次間的任務調度的權重。
在S102中，在定時啟動負載均衡監控才莫塊之後，執行以下處 理負載均衡監控模塊遍歷每個處理單元，並獲得每個處理單元的 任務優先級隊列表，以獲得各個處理單元在當前任務優先級上的任 務數量；根據各個處理單元在當前任務優先級上的任務數量，獲得 各個處理單元在當前任務優先級上的任務數量之間的最大差值，將 最大差值與預設閾值進行比較；當最大差值大於預設闞值時，將在 當前任務優先級上的任務數量最多的處理單元確定作為將要進4亍任 務調度的源處理單元；才艮據源處理單元在當前4壬務<尤先級上的4壬務 悽t量以及樹形關係結構層次圖，確定在當前任務優先級上，源處理
最大差值小於預設閾值並且任務數量最少的處理單元確定為目的處 理單元。
另外，在S102中還執行以下處理負載均衡監控模塊將目的 處理單元、源處理單元、以及4壬務調度的4尤先》及通知》會相關負載均 衡處理模塊，並向相關負載均衡處理模塊發起負載均衡調度消息。
在本發明，負載均衡調度消息至少包括源處理單元信息、目 的處理單元信息、以及所要執行的任務調度的優先級信息。在S104中，執行以下處理在接收到負載均衡調度消息後， 源處理單元的負載均衡處理才莫塊解析出源處理單元信息、目的處理 單元信息、以及所要執行的任務調度的優先級信息；計算源處理單 元、目的處理單元在所要執行的任務調度的優先級上的任務數量的 平均值，以確定源處理單元的任務數量與平均值的差值；根據差<直， 源處理單元的負載均tf處理才莫塊鎖定源處理單元，並從任務優先紐^
任務；源處理單元的負載均tf處理才莫塊將任務乂人源處理單元的〗壬務 優先》及隊列表中刪除並解除對源處理單元的鎖定；以及源處理單元 的負載均tf處理才莫塊向目的處理單元的負載均#^處理才莫塊發起負載 均《軒調度消息。
在S104中，還4;M亍以下處理在接收到負載均^t調度消息後， 目的處理單元的負載均tf處理才莫塊鎖定目的處J裡單元，並將4壬務加 入到目的處理單元的4壬務伊乙先》及隊列表中；目的處理單元的負載均 4軒處理才莫塊解除對目的處理單元的鎖定。
圖2是本發明的負載均衡調度方法所涉及的對稱多處理單元樹 形層次的結構示意圖，以及圖3是本發明的負載均衡調度方法所涉 及的多處理單元多任務優先級隊列表的示意圖。接下來將結合圖2 和圖3本發明的方法進行詳細描述。應了解，本發明的實現主要包 括了如下的步驟。
步驟一，作業系統初始化時，首先建立系統中各處理單元的多 優先級任務隊列頭表(如圖3所示)，該隊列頭表的優先級從高到低， 每個處理單元都有自己的一個多優先級任務隊列頭表，初始時，為 每個優先級生成一個空的《連表頭放在這個隊列頭表中，以後系統生
對系統配置信息，處理器信息的讀取，建立對稱多處理器體系中各 處理單元之間關係的 一個樹形層次結構，該結構的第 一層次為共用高速緩存和部分寄存器的超線程單元，第二層次為同一晶片內部的 多核單元，第三層次為同一系統內，不同晶片，4吏用同一套內存的 多晶片單元。
如圖3所示，描述了多優先級任務隊列表的詳細結構。每個處
理單元都有自己的一個優先級隊列表，按從高到低的順序排列，表 裡每一項存放的是相應優先級任務隊列的隊列頭指針，如果該優先
級沒有任務，當然該表項所指向的任務隊列為空。當任務在不同的 處理單元中遷移時，主要就是對這些隊列的才喿作， 一關殳是從源處理 單元指定優先級的任務隊列中刪除指定數量的4壬務，然後再將這些 任務掛4妄到目的處理單元的相應優先級的任務隊列中去。該結構在 作業系統初始化時建立，由作業系統的任務調度器使用，本實施例 所描述的方法會在負載均#f處理時4吏用到這個結構。
步驟二，利用步驟一建立的樹形關係結構(如圖2所示)，可以 建立在各處理單元間估文線程遷移的代價，在樹形結構的第 一層次的 遷移代價最小，第二層次較高，第三層次最高。
如圖2所示，在只於稱多處理體系的系統中，各處理單元之間關 系的一個4對形結構圖，通過該圖，可以建立系統內各處理單元之間 的相互關係，為在負載均^f時進4亍目的處理單元4叟索時奠定基礎。 當任務在處理單元間遷移時，會給系統的高速鄉爰存、內存頁表都帶 來一定開銷。一4殳來i兌，在兩個同一處理核內的超線考呈單元之間遷 移，開銷最小；其次，是在同一晶片的兩個核之間，在同一對稱多 處理器系統內的兩個晶片之間的遷移，相對來i兌開銷最大。
在圖2中，描述了本發明根據對稱多處理系統的實際所建立的 一個對應的樹形結構，該樹形結構乂人下到上共分三層，第一層是由 超線程單元節點，在同一處理核內的超線程單元都^皮劃為一組，掛 ，接在同一個處理核的父節點下；第二層是處理核節點，在同一個晶片內的處理核都被被劃為一組，掛接在同一個處理晶片父節點下； 第三層是晶片節點，在系統內的所有處理晶片都是一組，都掛4妄在 共同的父節點系統節點下。該結構在作業系統初始化時建立，本發 明所描述的方法會在負載均衡監控時使用到這個結構。
步驟三，啟動負載監控模塊，將其掛接在^m作系統的定時中斷 中。該才莫塊^皮定時調用，並按照優先級從高到4氐進行如下基本處理 流程
首先，它遍歷系統中，在當前處理優先》及上，每一個處理單元 的運行任務隊列，取得各處理器單元在當前處理優先級上的lt量分 布；
然後，耳又得各處理單元在在當前處理優先《及上的任務數量分布 的最大差值，先將該差值與預置的闊值比較，如果小於閾值，則不 估文處理，直接退出，估文下一優先級的處理，否則，當差值超過闊值 時，則耳又在該優先級上任務最多的處理單元為需要移出任務的源處 理單元，再繼續下面的步芬聚來尋找移入任務的目的處理單元；
以及在該優先級上的最大任務差值，開始在樹形關係結構的第 一層
次組內4叟索，獲耳又與源處理單元在第一層次ia內的^火伴處理單元在 該優先級的任務分布，如果在第一層次的組內處理單元間遷移部分 任務，可以使得遷移後的最大任務差值小於閾值，則完成對目的處
理單元的4臾索，否則，繼續4叟索；
第四，在樹形關係結構的第二層次組內4叟索，^^與源處理單元
二層次的組內處理單元間遷移部分4壬務，可以-使得該優先級的最大 任務差值小於閾值，則完成對目的處理器的搜索，否則，繼續糹叟索；第五，在系統內^叟索，耳又在該優先級任務悽t量最少的處理單元
為目的處理單元；
最後，將找到的源處理單元，目的處理單元，遷移4壬務的優先
糹及這三個信息，並通知源處理單元上的負載均# 處理才莫^:。
步-驟四.啟動負載均tf處理才莫塊，並在系統內的每一個處理單 元啟動一個負載均衡^莫塊的實體，該實體被分配為系統的最高優先 級，確保可以在系統中被最優先執行。當該模塊的一個實體被負載 均4耔監控一莫塊啟動後，將會有源處理單元，目的處理單元，和遷移 任務優先級這三個信息，然後開始做任務遷移，該模塊的任務遷移
主要有如下幾個步-驟
首先，在源處理單元的實體會獲if又源處理單元和目的處理單元 在遷移優先級的總任務數，除2得出一個平均數，確定要遷移的任 務數為源處理單元任務數與平均數的差值；
然後，該實體獲取源處理單元的執行權，鎖定源處理單元的任 務運行隊列，從遷移優先級的任務隊列尾部取出足夠數目的任務， 並將這些任務從任務隊列中刪除。並通知目的處理器上的負載均衡 處理才莫塊實體；
第三，在目的處理單元的負載均tf處理才莫塊實體會獲取目的處 理單元的執行權，鎖定目的處理單元的任務運行隊列，將在上一個 步驟中取出的任務依次加入到遷移優先級任務隊列的尾部，完成任 務遷移。
圖4是根據本發明的負載均tf調度裝置400的框圖。如圖6所 示，該裝置包括負載均4軒監控才莫塊402,用於經過周期啟動運行 來監控多處理器系統中各個處理單元的任務優先級的分布，並且當布的最大差值超過預i殳閾值時，確定源處理單元、目的處理單元、 和所要執行的任務調度的優先級，並向相關負載均衡處理模塊均發
起負載均衡調度消息；以及多個負載均衡處理才莫塊404,位於各個 處理單元內，與負載均衡監控模塊402相連，用於在接收到負載均 衡調度消息後，才艮據各個處理單元的任務優先級的分布以及各個處 理單元之間的關係來執行任務調度，從而使對稱多處理器系統中的 各個處理單元之間達到均4軒。
才艮據本發明的裝置還包括初始化模塊406,用於初始化多處 理器系統，並為處理單元中的每個建立一個任務優先級隊列表，為 每個處理單元的各個4尤先糹及生成一個^"應的空《連表頭並方丈在4壬務<尤 先級隊列表中，讀取多處理器系統的配置信息以及各個處理單元的 信息，建立各個處理單元之間的樹形關係結構層次圖，以及根據樹 形關係結構層次圖，確定在各個處理單元之間進行任務調度的權重。
在本發明中，樹形關係結構層次圖分為三個層次，其中，第一 層次為超線一呈處理單元，第二層次為同一個晶片內部的多核處理單 元，以及第三層次為不同晶片4旦^_用同 一 內存的多晶片處理單元。
負載均4軒調度消息至少包括源處理單元信息、目的處理單元 信息、以及所要執行的任務調度的優先級信息。
圖5是在圖4中所示的負載均衡監控模塊402中所執行的處理 的流程示意圖，以及圖6是在圖4中所示的負載均tf處理模塊實體 404中所才丸4亍的任務遷移處理的流程示意圖。衝妻下來結合圖5和圖6 對圖4所示的負載均衡調度裝置的各個模塊進行詳細描述。
如圖5所示，示出了負載均4軒監控才莫塊的詳細處理流程。應了 解，負載均衡模塊一般掛接在系統中的定時中斷，在系統中只存在 一個實體，負責對系統內負載均衡情況進行監視，在發現系統內有負載不均衡的情況時，它會在系統內進行搜索，搜索出目的處理器、 源處理器、不均tf的優先級、並將這些信息傳遞給負載均衡處理才莫
塊實體處理。具體地，在負載均衡監控才莫塊中衝丸行如下處理
S502,當負載均衡監控才莫塊被定時調用時，它遍歷系統中每一 個處理單元的多^尤先》及運^H壬務隊列(如圖3所描述)，耳又得每一優 先級在各處理單元上的任務悽t量；
S504，按照優先級順序，從高優先級開始處理，利用S502取 得的各處理單元上該優先級的任務分布^:據，耳又得當前處理優先級 上各處理單元的任務數量的最大差值；
S506,將S504取得的最大差值與預置的閾值比較，如果小於 閾值，則直接跳轉到S516,否則，當差值超過閾值時，則取在該優 先級上任務最多的處理單元為需要移出任務的源處理單元，再繼續 下面的步驟來尋找移入任務的目的處理單元；
S508,耳又得源處理單元上當前處理優先級的任務悽t,取得S504 獲得的當前處理優先級上的最大任務差值，在樹形關係結構的第一 層次組內4叟索，舉d尋與源處理單元在第 一層次同 一組內在當前處理 優先糹及的4壬務H量最少的一個iU半處理單元，耳又源處理單元和這個 夥伴處理單元在當前處理優先級的任務數量均值，計算出源處理單 元在當前處理優先級的任務悽t量與該均值的差值，用最大任務差值 減去這個差值，所得值如果小於閾值，則以夥伴處理單元為目的處 理單元，完成對目的處理單元的4臾索，3兆轉到S514,否則，繼續 S510;
S510,在^"形關係結構的第二層次組內4臾索，耳又與源處理單元 在第二層次組內的在當前處理優先級的任務數量最少的一個夥伴處 理單元，耳又源處理單元和這個^火伴處理單元在當前處理優先級的任務數量均值，計算出源處理單元在當前處理優先級的任務數量與該 均值的差值，用最大任務差值減去這個差值，所得值如果小於閾值，
則完成3於目的處理器的4臾索，逸W爭到S514，否則，繼續S512;
S512，在樹形關係結構的第三層次組內也即整個系統內搜索， 取得在當前處理優先級的任務數量最少的一個夥伴處理單元為目的 處J裡單元，繼續S514;
S514，將目的處理單元/源處理單元/遷移^尤先;及通知相應負載 均衡處理模塊實體；以及
S516，判斷所有優先級是否處理完畢，如果處理完畢，模塊退 出處理，否則，返回到S504。
接下來執行如圖6所示的在負載均衡處理模塊中執行的處理的 流程。與負載均衡監控模塊不同，負載均衡模塊有多個實體，在系 統內的每個處理單元都有一個實體，這個實體一4殳是處理單元內的 一個最高優先級任務的形式出現，這樣以確保該實體能在所有的任 務中被最優先執行。該模塊主要負責任務遷移工作，該工作的完成 需要源處理單元的負載均衡才莫塊實體和目的處理單元的負載均衡模 塊處理實體協同完成，每個處理單元上的負載均衡模塊實體的功能 都完全相同，都能完成作為源處理單元或目的處理單元時所需的工 作。每個處理單元上的負載均4軒實體在任務遷移時扮演的角色，完 全由負載監控系統在負載監控處理時得到的結果來確定。具體地， 負載均#f處理才莫塊實體間協同完成任務遷移的處理流程如下
S602 ，在源處理單元上的實體獲耳又到負載監控才莫塊傳來的任務 遷移消息，該消息包含了源處理單元、目的處理單元和遷移優先糹及 等任務遷移必要信息，源處理單元的負載均衡處理實體會從收到的 消息解析出源處理單元、目的處理單元和遷移優先級這些信息，然
21後，計算出源處理單元和目的處理單元在遷移優先級上的任務悽文量
均值，乂人而確定在遷移優先級上要遷移的任務^:為源處理單元任務 悽t與均值的差值；
S604,該實體獲耳又源處理單元的衝丸4亍權，鎖定源處理單元的4壬 務隊列，從遷移優先級的任務隊列尾部取出足夠數目的任務，並將 這些任務AU壬務隊列中刪除，解除鎖定，通知目的處理器上的負載 均4軒處理才莫塊實體；以及
S606，在目的處理單元的負載均tf處理才莫塊實體會獲耳又目的處 理單元的執行權，鎖定目的處理單元的任務運行隊列，將在S604 中取出的任務依次加入到遷移優先級任務隊列的尾部，解除鎖定， 完成任務遷移。
應了解，本發明主要是對對稱多處理器系統的任務進行均4軒， 主要的功能是在整個多處理器系統中均衡調配，使得系統中的各處 理執行單元的任務處理負荷保持均衡，使系統中不致出現一個處理 器負載很重，而另外的處理器卻4艮空閒的情況。
綜上所述，採用本發明，使用了系統中優先級分布來做負載均 衡的基本指標，而不是以處理器的空閒率作為負載均衡的指標，從 而具有實時響應性能好，負載均衡監控時的計算開銷小，更適合於 嵌入式系統應用。
以上僅為本發明的優選實施例而已，並不用於限制本發明，對 於本4貞i或的^支術人員來"i兌，本發明可以有各種更改和變4匕。凡在本 發明的精神和原則之內，所作的任何修改、等同替換、改進等，均 應包含在本發明的保護範圍之內。
權利要求
1. 一種負載均衡調度方法，用於在嵌入式實時對稱多處理器系統中，通過一個負載均衡監控模塊和位於所述嵌入式實時對稱多處理器系統中的各個處理單元的多個負載均衡處理模塊，使對稱多處理器系統中的各個處理單元之間達到均衡，其特徵在於，包括以下步驟步驟一，啟動周期運行的負載均衡監控模塊來監控所述多處理器系統中各個處理單元的任務優先級的分布，並且當監控到所述各個處理單元的任務優先級的分布不均衡且所述任務優先級的分布的最大差值超過預設閾值時，所述負載均衡監控模塊確定源處理單元、目的處理單元、和所要執行的任務調度的優先級，並向相關負載均衡處理模塊均發起負載均衡調度消息；以及步驟二，在接收到所述負載均衡調度消息後，所述相關負載均衡處理模塊根據所述各個處理單元的任務優先級的分布以及所述各個處理單元之間的關係來執行所述任務調度，從而使所述對稱多處理器系統中的各個處理單元之間達到均衡。
2. 根據權利要求1所述的方法，其特徵在於，在所述步驟一之前， 還包括步-驟a,在所述多處理器系統初始4匕後，為所述處理單元 中的每個建立一個任務優先級隊列表；步驟b，為每個處理單元的各個優先級生成一個對應的空 鍊表頭並》文在所述任務優先級隊列表中；步驟c，讀取所述多處理器系統的配置信息以及所述各個 處理單元的信息，建立所述各個處理單元之間的樹形關係結構層次圖；以及步驟d,根據所述樹形關係結構層次圖，確定在所述各個 處理單元之間進行任務調度的權重。
3. 根據權利要求2所述的方法，其特徵在於，在所述步驟c中， 還包括將所述樹形關係結構層次圖分為三個層次，其中，第一層次為超線程處理單元，第二層次為同一個芯 片內部的多核處理單元，以及第三層次為不同晶片但4吏用同一 內存的多晶片處理單元。
4. 根據權利要求2所述的方法，其特徵在於，在所述步驟一中， 在定時啟動所述負載均衡監控模塊之後，執行以下處理所述負載均4軒監控才莫塊遍歷每個處理單元，並獲得所述每 個處理單元的^f壬務優先l及隊列表，以獲^尋所述各個處理單元在 當前任務優先級上的任務數量；才艮據所述各個處理單元在當前任務優先級上的任務悽丈量， 獲得所述各個處理單元在當前任務優先級上的任務數量之間 的最大差值，將所述最大差值與所述預設閾值進行比較；當所述最大差值大於所述預設閾值時，將在所述當前任務 優先級上的任務數量最多的處理單元確定作為將要進行任務 調度的源處理單元；才艮據所述源處理單元在所述當前4壬務優先級上的任務 量以及所述;f對形關係結構層次圖，確定在所述當前任務優先級的最大差值；以及將所述最大差值小於所述預設閾值並且任務數量最少的 處理單元確定為所述目的處5裡單元。
5. 根據權利要求4所述的方法，其特徵在於，在所述步驟一中還 寺丸4亍以下處理所述負載均tf監控才莫塊將所述目的處理單元、所述源處理 單元、以及所述任務調度的優先級通知給所述相關負載均衡處 理才莫塊，並向所述相關負載均4軒處理才莫塊發起所述負載均4軒調 度消息。
6. 根據權利要求5所述的方法，其特徵在於，所述負載均衡調度 消息至少包括源處理單元信息、目的處理單元信息、以及所 要執行的任務調度的優先級信息。
7. 根據權利要求6所述的方法，其特徵在於，在所述步驟二中， 衝丸4亍以下處J裡在"l妄收到所述負載均4耔調度消息後，所述源處理單元的負 載均糹軒處理才莫塊解析出所述源處理單it/[言息、所述目的處理單 元信息、以及所要一丸行的任務調度的優先級信息；計算所述源處理單元、所述目的處理單元在所述所要糹丸4亍 的任務調度的優先級上的任務數量的平均值，以確定所述源處 理單元的任務數量與所述平均值的差值；才艮據所述差值，所述源處理單元的負載均^耔處理^^莫塊鎖定 所述源處理單元，並從所述任務優先級隊列表的所述所要執行 的任務調度的優先級的隊列尾部取出足夠數量的任務；所述源處理單元的負載均糹軒處理才莫塊將所述任務乂人所述 處J裡單元的鎖定；以及所述源處理單元的負載均#f處理才莫塊向所述目的處理單 元的負載均衡處理模塊發起所述負載均衡調度消息。
8. 根據權利要求7所述的方法，其特徵在於，在所述步驟二中， 還衝丸4亍以下處理在接收到所述負載均衡調度消息後，所述目的處理單元的 負載均4軒處理才莫塊鎖定所述目的處理單元，並將所述任務加入所述目的處理單元的負載均tf處J裡才莫塊角罕P佘對所述目的 處理單元的鎖定。
9. 一種負載均衡調度裝置，其特徵在於，包括負載均衡監控才莫塊，用於經過周期啟動運行來監控所述多 處理器系統中各個處理單元的任務優先級的分布，並且當監控優先級的分布的最大差值超過預設閾值時，確定源處理單元、 目的處理單元、和所要#^亍的任務調度的優先級，並向相關負 載均衡處理模塊均發起負載均衡調度消息；以及多個負載均衡處理模塊，位於各個處理單元內，與所述負 載均衡監控模塊相連，用於在接收到所述負載均衡調度消息處理單元之間的關係來才丸4亍所述任務調度，乂人而4吏所述對稱多 處理器系統中的各個處理單元之間達到均tf 。
10. 根據權利要求9所述的裝置，其特徵在於，還包括初始4匕才莫塊，用於初始4匕所述多處理器系統，並為所述處 理單元中的每個建立一個任務優先級隊列表，為每個處理單元 的各個優先級生成一個對應的空鍊表頭並》i:在所述任務優先 級隊列表中，讀取所述多處理器系統的配置信息以及所述各個處理單元的信息，建立所述各個處理單元之間的杉於形關係結構 層次圖，以及才艮據所述樹形關係結構層次圖，確定在所述各個 處理單元之間進4亍4壬務調度的4又重。
全文摘要
本發明提供了一種負載均衡調度方法和裝置，其中，該方法包括以下步驟步驟一，啟動周期運行的負載均衡監控模塊來監控多處理器系統中各個處理單元的任務優先級的分布，並且當監控到各個處理單元的任務優先級的分布不均衡且任務優先級的分布的最大差值超過預設閾值時，負載均衡監控模塊確定源處理單元、目的處理單元、和所要執行的任務調度的優先級，並向相關負載均衡處理模塊均發起負載均衡調度消息；以及步驟二，在接收到負載均衡調度消息後，相關負載均衡處理模塊根據各個處理單元的任務優先級的分布以及各個處理單元之間的關係來執行任務調度，從而使對稱多處理器系統中的各處理單元上任務負荷達到均衡。
文檔編號G06F9/46GK101458634SQ20081000083
公開日2009年6月17日 申請日期2008年1月22日 優先權日2008年1月22日
發明者蔣鯤鵬 申請人:中興通訊股份有限公司