在硬性實時系統中軟體組件的出棧調度的製作方法
2023-05-10 07:06:31 3
專利名稱：在硬性實時系統中軟體組件的出棧調度的製作方法
技術領域：
本發明涉及一種在硬性實時系統中調度組件的方法，所述硬性實時系統用於處理時間相關的數據元流。本發明還涉及一種硬性實時系統，用於處理時間相關的數據元流。
在實時軟體系統中，其中組件的數目大於可用處理器的數目，組件競爭以得到處理時間，並且要求可靠又快速地調度組件。在本文中，把在其生成輸出的時間是必要的任何軟體系統稱為實時軟體系統。從實時軟體系統的輸入時間到其輸出時間的滯後-即延遲必須小到足以可接受的時間性。硬性實時軟體系統必須在有限的時間間隔內響應外部產生的輸入。在本文中的軟體系統一般是用若干互連的組件來構造的，並且在組件之間的唯一交互作用是通過它們的接口來實現的，所述組件不共享狀態信息。
在這種系統中，調度器採用滿足在系統級上的實時約束來向組件分配處理間隔。調度組件由兩個階段組成，隨著時間的推移不斷地重複所述兩個階段。首先，確定可調度的組件集，繼而根據該集並且依照某種優先化模式，選擇實際上將在處理器上執行的組件的子集(在每個處理器上執行一個組件)。
已知一些優先化模式。
·循環模式-快照(snapshot)由可調度的組件集組成。任意地排序該集並且逐個選擇所述組件。在服務所有可調度的組件之後，更新可調度的組件集。
·固定優先級模式-每個組件將具有確定的固定優先級。從可調度的組件集來選擇具有最高優先級的組件。接下來，更新所述可調度的組件集，並且根據該新的集來選擇具有最高優先級的組件，諸如此類。
·靈活優先級模式-每個組件將得到隨著時間的推移可以改變的優先級。從可調度的組件集來在那時選擇具有最高優先級的組件。接下來，更新所述可調度的組件集並且重新計算所述組件的優先級。從該新的集中選擇具有最高優先級的組件，諸如此類。
·基於優先級的先發(pre-emptive)調度-該調度方法可以與固定或靈活的優先級方法組合起來。當具有較高優先級的組件在處理具有較低優先級的組件期間變得可調度的時，可以中斷對後者組件的處理以便首先服務具有較高優先級的組件。
·流水線或壓棧(push)調度-任意地排序有向組件圖的源。逐個處理可調度的源，但是在每個步驟之後，更新可調度的集並且數據儘可能通過所述圖壓棧。當由於處理源而導致沒有任何組件可以被調度時，處理下一可調度源。
這裡考慮的問題是發現有效的優先化模式，其能夠從可調度的組件集中來選擇最佳的可調度組件。所述的最佳意味著最小的埠到埠的延遲。
US2002/0062435描述了具有多個流以便處理多個線程的多流送處理器，和具有用於一個或多個流的優先級代碼的優先級記錄的指令調度器。在一些實施例中，優先級代碼確定相對訪問資源以及哪個流在任意時間點具有訪問權。在其它實施例中，優先級被動態地確定並且實時地改變，這可以按照諸如晶片內處理統計之類的各種準則、通過執行一個或多個優先級算法、依照流負載通過來自晶片外的輸入或這些的組合來完成。
US 6,195,701描述了一種用於同步並調度多數據流和實時任務的方法。由觸發條件例如流送過程的狀態來確定調度準則。然後再把這種狀態與流的時間標記和系統時間相關。該文獻沒有解決通過執行組件調度使用一個處理器來執行流送和控制流送的問題。
同時，人們發現上述數據處理沒有遵照可用於系統的最高輸出率。現有技術一般可能向在數據隊列中下一個數據分配可用的處理資源。這意味著如果在處理流水線中被分配相等處理優先級的兩個數據流等候處理資源，那麼首先處理排在第一的數據流。在某些應用中這可能是不方便的，比如在產生輸出之前，在處理樹結構中的處理操作可能被鎖定相當長的一段時間。隨著處理樹深度的增加，這種不方便會明顯加大。
本發明的目的是提供一種用於調度的方法，其適於實現系統的硬性實時操作並且解決上述問題。
這由在硬性實時系統中調度可調度的組件的方法來獲得，所述硬性實時系統用於處理時間相關的數據元流，其中可調度的組件數目大於可用的用於處理所述組件的處理器的數目，並且其中每個所述組件具有至少一個輸入和一個輸出，其特徵在於所述方法包括如下連續地執行的步驟-為每個可調度的組件確定能夠有助於所述硬性實時系統的輸出的最早時間，-調度能夠在總的最早時間有助於所述實時系統的輸出的可調度組件。
這意味著如果存在有助於所述輸出的可調度的組件，那麼不會把處理時間花費在那些無助於產生輸出的可調度的組件。
在實施例中，如果一定數目的可調度的組件在相同的總最早時間有助於所述實時系統的輸出，那麼使用壓棧調度來執行所述數目的組件的調度。在這種情況下壓棧調度引入了比其它調度方法更少的關聯轉換。最小化關聯轉換還支持低的埠到埠的延遲。
在另一實施例中，為每個組件指定預定義的時間間隔的長度，並且當來自時間相關的、加時間戳的數據元流的預定義的時間間隔的加時間戳數據元在一個組件的所有輸入都可用時，所述組件就是可調度的。與時間框(time box)調度的組合允許確定以某種方式對輸出的最早的貢獻(contribution)，該貢獻易於重新計算。
在具體實施例中，通過定義所述預定義的時間間隔的開始時間和結束時間，並且通過檢查數據已經被前一組件處理之前的時間是否比所述預定義的時間間隔的結束時間要新，來確定所述加時間戳數據元的所述預定義時間間隔的可用性。這允許以容易的方式來檢測組件是否是可調度的。
在實施例中，通過下列步驟來執行確定所述組件能夠有助於所述輸出的最早時間的步驟-識別所述數據元必須由其處理的隨後組件的可能路徑以便從所述組件達到所述系統的輸出，-通過從所述預定義的時間間隔的開始時間中減去為在所述路徑中每個所述隨後組件指定的每個預定義時間間隔的長度，來確定每個可能的路徑的最早貢獻時間。
-把所述組件能夠有助於所述輸出的最早時間確定為最早的、所確定的貢獻時間。
這是用於採用不向任何輸出或用於到達輸出的路徑給出優先選擇的方式，來定義『最早貢獻』的方式。
在具體實施例中，通過下列步驟來執行確定所述組件能夠有助於所述輸出的最早時間的步驟-識別所述數據元必須由其處理的隨後組件的路徑以便從所述組件到達所述系統的輸出，其中，-通過從所述預定義時間間隔的開始時間中減去為在所述路徑中的每個所述隨後組件指定的每個預定義時間間隔的長度來為每個可能的路徑確定最早貢獻時間，其中至少某些所述預定義的時間間隔已經被減去位移值。
-把所述組件能夠有助於所述輸出的最早時間選擇為最早的、所確定的貢獻時間。
這允許採用容易的方式來決定哪個可調度的組件在最早的時間點能夠有助於輸出，加入使用位移量來強迫數據流過所述系統的話。
本發明還涉及一種用於處理時間相關的數據元流的硬性實時系統，所述系統包括一定數目的組件和一定數目的用於處理組件的處理器，所述組件的數目大於處理器的數目，每個所述組件具有至少一個輸入和至少一個輸出，所述系統包括用於為每個可調度的組件確定所述組件能夠有助於所述硬性實時系統的輸出的最早時間的裝置；和用於調度在總的最早時間能夠有助於所述實時系統的輸出的可調度組件的裝置。
本發明可以被用於實時系統，諸如在處理(MPEG2，MPEG4)和未處理領域中視頻和音頻處理系統。進一步的實時系統可以是圖像處理、圖象識別、工業自動化、模式識別和雷達和無線電通信。
下面，參照附圖將要描述本發明的優選實施例，其中
圖1舉例說明了在兩個組件之間的連接器，圖2總體上舉例說明了用於定義組件的可調度性和執行調度的組件的過程步驟，圖3是舉例說明怎樣決定是否可以為具體組件分配當前時間框的流程圖，圖4舉例說明了每個連接器的當前時間框的位移量，圖5舉例說明了當確定組件的可調度性時調度器怎樣使用所述時間框，
圖6舉例說明了用於解釋調度可調度的組件的硬性實時系統，圖7a-7g舉例說明了逐步地調度在圖6的系統中的組件。
下面，將要描述使用本發明，其用於時間框驅動調度在用於流處理的硬性實時系統中的軟體組件。首先，將要描述時間框驅動調度，並且隨後將描述依照本發明可以怎樣來調度所述可調度的組件。
一個系統是一個執行確定的任務的設備，其中所述設備執行該任務的方式可以受管理和控制的影響。在優選實施例中，將把確定的任務限制在數據流的硬性實時處理。一個組件是系統的自我包含的部分，執行『原子』性的子任務，即認為不用更進一步地細分所述子任務。用於進一步劃分子任務或不劃分子任務的動機是基於在再復用器、編碼器等應用領域中的經驗。加時間戳的數據元是數據在流中的表示。假定流送數據具有數據內容和時間信息。使用該時間信息來排序所述數據元並且使所述數據與時間相關。時間框是加時間戳數據元的預定義的時間間隔。
在依照本發明的系統內，使用算法時間。最後，再次把為輸出流產生的時間信息與實際時間相關。從系統時間到算法時間的轉換例如可以由置於系統輸入和系統輸出的常規時間過濾器來執行。
圖1舉例說明了在兩個組件之間的連接器；所述連接器是所述系統的自我包含的部分。由連接器105把源組件101連接到接收端組件103。連接器105的動態由在連接器105上的若干元組成，包括數據元和生成前的時間spc(即數據已經由源組件生成之前的時間)。用算法時間si標記數據元並且可以由於調度在連接器源端的源組件而追加到連接器。調度源組件還為具體連接器更新生成前的時間。當調度在連接器的接收端組件時，所述組件可以通過處理數據元來刪除數據元。為每個組件定義當前時間框，所述時間框具有開始時間和結束時間。為了調度組件，一個時間框在所述組件的輸入端對於所有連接器必須是滿的，這意味著在所述時間框的開始時間和結束時間之間的時間間隔中具有時間戳si的所有數據元是已就緒/已存在，或換句話說所述生成前的時間比當前時間框的結束時間要新。
圖2總體上解釋了用於定義組件的可調度性和執行調度組件的過程步驟，所述過程包括為所述組件的每個連接器分配時間框和執行調度組件的步驟。在201中，把當前時間框分配給所述組件。這通過定義將要由所述組件處理的下一數據元的時間間隔的開始時間和結束時間來完成。所述調度器例如可以執行分配當前時間框。當在具體連接器上的數據元就緒時，意味著已經由源組件處理了所述數據元，那麼在當前時間框內的所述數據就是已就緒的。對於組件的每個輸入連接器，所述當前時間框必須是滿的，以便使組件是可調度的。在203中，已經調度所述組件並且由所述組件消耗並處理在所有連接器的數據元，所述數據元位於當前時間框的邊界內。所處理的數據元現在在所述組件的輸出已就緒，並且更新每個輸出連接器的生成前的時間spc。在201中，把新的當前時間框分配給所述組件。這通過為所述組件定義新的開始時間來完成，所述新的開始時間等於前一時間框的結束時間。
圖3是舉例說明怎樣決定是否可以為具體組件分配當前時間框的流程圖。根據組件類型依照兩種方案來作出上述決定。第一類型是Δs組件，而第二類型是#n組件。如果所述組件是Δs組件301，那麼檢查303當前算法時間CS是否大於加上預定義時間間隔Δs-即時間框長度的當前時間框的開始時間BS。當前時間框的開始時間等於前一時間框的結束時間。如果這為真，那麼可以定義所述時間框並且將其分配給所述組件305，如果為假，那麼就不能夠定義任何時間框！TB也沒有時間框可以分配307，這是因為自從所述組件上一次處理在時間框中的數據元以來還沒有經過足夠的時間。當所述組件是#n組件309時，那麼首先檢查311在具體的連接器一#n連接器上是否存在可用的預定義數目的數據元。如果這為真，那麼可以定義305時間框TB，在該時間框中，它的開始時間是前一時間框的結束時間，並且它的結束時間是在具體連接器上可用的最新數據元的時間戳。如果不為真，那麼檢查313當前算法時間是否大於當前時間框加上位移值d的開始時間。如果這為真，那麼數據元就緒並且可以定義305時間框，如果為假，那麼就不能夠定義任何時間框！TB，因為在第n個連接器還不存在？？？足夠的數據元。總體上，Δs組件將能處理在它們當前時間框中變化輕微的數據量，而#n組件將從被指定為#n連接器的輸入中獲取相同的數據量。
在實施例中，如在圖4中舉例說明，對於每個連接器而言，分配到組件的當前時間框在時間上是可以發生位移。在401，1中，舉例說明了具有若干輸入(I1..In)和三個輸出(Q1，Q2，Q3)的組件。把時間框TB分配給具有開始時間BS和結束時間ES的組件，如由403所示。在該例子中，輸出Q1沒有位移；Q2具有正位移而Q3具有負位移。通過增加輸出的位移來把某個輸出連接器的生成前的時間直接連結到時間框的結束時間spCQ＝ES(TB)+ΔdQ其中CQ是附於所述組件輸出Q的連接器，spCQ為連接器CQ的生成前的時間，se(TB)為時間框TB的結束時間，用所述時間框TB來調度組件401，而ΔdQ是組件輸出Q的位移。
使用圖5來描述當確定組件的可調度性時所述調度器怎樣使用時間框。通過檢查所述組件的每個輸入連接器來確定可調度性，並且如果連接器的生成前的時間spc等於或大於所述組件的時間框的結束時間ES，那麼該連接器使所述組件適於被調度503。否則，所述組件就還沒有就緒以便被調度505。如前所述，組件的每個輸入連接器必須符合要求，以便才能夠使得該組件符合調度的要求。
已經描述了組件如何依照時間框驅動調度變得可調度，下面將要描述依照本發明實施例怎樣選擇要調度的組件，以及怎樣依照靈活優先級模式來排序可調度的組件。
所有可調度的組件獲得基於調度所述組件能夠有助於輸出的時間點的靈活優先級，向可能最早有助於輸出的組件給予最高優先級。在每個步驟之後，更新可調度的組件集並且重新計算可調度的組件的優先級。藉此通過圖來使得數據出棧(pull)，其中首先處理較早有助於最後結果的組件。如果一個以上的組件具有最高優先級，那麼對它們應用壓棧調度。
一種計算一個確定的組件可能有助於所述輸出的最早時刻的方法是使用從所述組件到輸出的路徑，繼而把最早時刻計算為新的時間框的開始時間減去在從所述組件到所述輸出的路徑上所有時間框的時間長度。通過執行該計算來計算最早可能的時間。假定當調度一個組件時在一個時間框中正被處理的的第一加時間戳的數據元，等於在所述路徑中下一組件的時間框中的遺漏的、加時間戳的數據元。對於在到輸出的路徑中的每個組件執行所述假設，藉此可以得到所述組件可能有助於所述輸出的最早時刻。
在若干組件是可調度之時，使用下列公式來找到哪個組件可能在最早時間有助於輸出並且藉此調度所述組件Min{spX-ΔsXp|p是從組件X到輸出的路徑}spX是組件X的生成前的時輸，其等於組件X的當前時間框的開始時間，而ΔsXp是與在從組件X到輸出的路徑p上的組件的每個時間框相關聯的每個預定義的時間間隔的長度？？之和。在具體實施例中，可以有時間延遲並且藉此在所述路徑中的兩個或更多組件之間的連接中可以有時間位移。在這種情況下應該按照如下減去沿著路徑p的總位移ΔdXpMin{spX-(ΔsXp-ΔdXp)}如果依照上述應該調度兩個組件，意味著調度這兩個組件可能在相同的最早時間有助於輸出，那麼使用出棧調度來確定調度哪個組件。
在圖6中舉例說明了硬性實時系統的例子，用於解釋在依照上述的系統中調度所述可調度的組件。所述系統由均為Δs組件的4個組件A、B、C和D組成，其中組件A是經由連接器601連接到組件B的輸入組件，組件B經由連接器603連接到組件C，所述組件C是輸出組件，而組件D是經由連接器605連接到輸出組件C的輸入組件。在每個連接器都舉例說明了時間框607、609、611和613，並且連同每個時間框一起還示出了時間間隔ΔsA、ΔsB、ΔsC、ΔsD，其舉例說明了與每個時間框相關聯的預定義的時間間隔的長度。輸入組件A和D接收恆定的數據流，並且因此總是存在有足夠的數據元來填充時間框607和時間框611。這還意味著組件A和D總是可調度的。
在下面，使用圖7a-7f來解釋組件A、B，C和D的調度。在所有的圖中，每個組件A、B、C和D連同與組件A、B、C和D相關聯的預定義的時間間隔的時間間隔ΔsA、ΔsB、ΔsC、ΔsD一起示出了。此外，時間線700舉例說明了算法時間s，而且對於每個組件A、B、C、D，把生成前的時間分別表示為spA、spB、spC和spD，並且依照時間框調度的一般屬性，每個組件的生成前的時間等於與所述組件相關聯的當前時間框的開始時間。最初，所有時間框的開始時間是相同的並且被標記為點。
在圖7a中，最初已經調度組件A，A和D這而這曾經都是可調度的並且通過使用壓棧調度選擇了A。
已經由組件A處理在時間間隔701中的數據元，並且生成前的時間spA增加。在調度組件A之後，足夠的數據可以用來調度組件A、組件B和組件D。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC在這種情況下，B和D這二者都能夠在相同的最早時間有助於輸出，因此使用壓棧調度並且調度組件B。
在調度由在時間軸B的時間間隔702舉例說明的組件B之後，生成前的時間spB增加。足夠的數據可以用來調度組件A、組件B和組件D。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC組件D可能在最早時間有助於輸出，因此如由時間間隔703所舉例說明，調度組件D。在時間軸D，生成前的時間spD增加。
在圖7b中，仍然足夠的數據僅僅可用來調度組件A、B和D。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC這次，組件B可能在最早時間有助於輸出，因此如時間間隔704所舉例說明來調度組件B。
然後還可以再調度組件A、B和D，並且通過使用上述計算，如由時間間隔705所舉例說明，再次調度組件D。
如在圖7c中舉例說明，現在有足夠的數據可以用來調度組件C，因此組件A、B、C和D都是可調度的。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC
組件CspC組件C可能在最早時間有助於輸出，因此如由時間間隔706所舉例說明來調度組件C。
如從圖7d中所見，現在足夠的數據僅僅可以用來調度組件A、B和D，使那些組件是可調度的。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC組件B可能在最早時間有助於輸出，因此如時間間隔707所舉例說明來調度組件B。
在圖7e中，足夠的數據可以用來調度組件A、B和D，使那些組件是可調度的。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspC-ΔsC組件D可能在最早時間有助於輸出，因此如由時間間隔708所舉例說明，調度組件D。
在圖7f中，足夠的數據可以用來調度組件A、B和D，使那些組件可調度的。通過計算產生最小數值或最早時間來確定調度哪個組件組件AspA-(ΔsB+ΔsC)組件BspB-ΔsC組件DspD-ΔsC組件B可能在最早時間有助於輸出，因此如時間間隔709所舉例說明來調度組件B。
如在圖7g中舉例說明，現在有足夠的數據可以用來調度組件C，因此組件A、B、C和D都是可調度的。通過計算產生最小數值或最早時間來確定調度哪個組件組件ASpA-(ΔsB+ΔsC)組件BSpB-ΔsC組件DSpD-ΔsC
組件CSpC組件C可能在最早時間有助於輸出，因此如由時間間隔710所舉例說明來調度組件C。
調度可以與上述相似繼續進行。
權利要求
1.一種用於在硬性實時系統中調度可調度的組件的方法，所述硬性實時系統用於處理時間相關的數據元流，其中可調度的組件的數目大於可用的處理器的數目，所述處理器用於處理所述組件，其中每個所述組件具有至少一個輸入和一個輸出，其特徵在於所述方法包括如下連續執行的步驟-為每個可調度的組件確定所述組件能夠有助於所述硬性實時系統的輸出的最早時間，-調度能夠在總的最早時間有助於所述實時系統的輸出的所述可調度的組件。
2.如權利要求1所述的方法，其中如果一定數目的可調度的組件在相同的總最早時間有助於所述實時系統的輸出，那麼使用壓棧調度來執行所述數目的組件的調度。
3.如權利要求1或2所述的方法，其中為每個組件指定一個預定義的時間間隔的長度，並且當來自所述時間相關的、加時間戳的數據元流的所述預定義的時間間隔的加時間戳的數據元在一個組件的所有輸入端都可用之時，所述組件就是可調度的。
4.如權利要求3所述的方法，其中通過定義所述預定義的時間間隔的開始時間和結束時間，並且檢查數據已經被前一組件處理之前的時間在何時比所述預定義的時間間隔的結束時間要新，來確定所述加時間戳的數據元的所述預定義時間間隔的可用性。
5.如權利要求3或4所述的方法，其中通過下列步驟來執行確定所述組件能夠有助於所述輸出的最早時間的步驟-識別所述數據元必須由其處理的隨後組件的可能路徑，以便從所述組件達到所述系統的輸出，-通過從所述預定義的時間間隔的開始時間中減去為在所述路徑中的每個所述隨後組件指定的每個預定義時間間隔的長度，來為每個可能的路徑確定最早貢獻時間；-把所述組件能夠有助於所述輸出的最早時間確定為最早的、確定的貢獻時間。
6.如權利要求3或4所述的方法，其中通過下列步驟來執行確定所述組件能夠有助於輸出的最早時間的步驟-識別所述數據元必須由其處理的隨後組件的路徑，以便從所述組件到達所述系統的輸出，-通過從所述預定義時間間隔的開始時間中減去為在所述路徑中的每個所述隨後組件指定的每個預定義時間間隔的長度來為每個可能的路徑確定最早貢獻時間，其中至少某些所述預定義的時間間隔已經被減去位移值；-把所述組件能夠有助於所述輸出的最早時間確定為最早的、確定的貢獻時間。
7.一種用於處理時間相關的數據元流的硬性實時系統，所述系統包括一定數目的組件和一定數目用於處理組件的處理器，所述組件數目大於所述處理器數目，每個所述組件具有至少一個輸入和至少一個輸出，所述系統包括用於為每個可調度的組件確定所述組件能夠有助於所述硬性實時系統的輸出的最早時間的裝置，和用於調度在總的最早時間能夠有助於所述實時系統的輸出的可調度組件的裝置。
全文摘要
本發明涉及一種在硬性實時系統中確定何時調度組件的方法，所述硬性實時系統用於處理時間相關的數據元流。組件的數目大於用於處理所述組件的可用處理器的數目，並且每個組件具有至少一個輸入和至少一個輸出。通過確定一個組件能夠有助於所述系統的輸出的最早時間，並且通過調度在所述最早時間能夠有助於所述輸出的所述組件來調度組件。本發明還涉及一種硬性實時系統，用於處理時間相關的數據元流，其具有用於執行上述調度的裝置。
文檔編號G06F9/48GK1720504SQ200380104807
公開日2006年1月11日 申請日期2003年10月31日 優先權日2002年12月3日
發明者A·德邦傑, S·T·德克 申請人:皇家飛利浦電子股份有限公司