[發明專利]優先化任務之間的有效切換

無效

• 申請號: 200580040884.2
• 申請日: 2005-11-24
• 公開（公告）號: CN101065728A
• 公開（公告）日: 2007-10-31
• 發明（設計）人: M·J·M·海里格斯;E·尤哈斯
• 申請（專利權）人: 皇家飛利浦電子股份有限公司
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/45
• 代理公司: 永新專利商標代理有限公司
• 代理人: 王英

技術領域

本發明涉及用于執行任務調度，從而在優先化任務之間提供有效切換的處理器裝置、方法和計算機程序產品。

背景技術

就計算機的常規發展狀況而言，任務切換指令序列導致了在任務之間的切換上耗費了大量的時間。將耗費在任務之間的切換上的時間稱為任務變更處理開銷。所述開銷是寄存器存儲和恢復所用的時間，并且其包括其他延遲，例如，確定任務優先級和任務執行論證所用的時間。因而，無法將這些時間段用于有效的處理當中。在很多新型計算機或處理器系統中，這樣的中斷和任務變更處理開銷占用幾十到幾百周期。

在消費者應用中，例如，必須對某些外圍數據進行實時處理，而對其他一些任務則能夠以傾盡能力的方式處理。因此，程序由高優先級任務和低優先級任務構成，并且要執行相關分析，以導出任務之間的時間相關性。通常提供主處理器用于運行普通任務，而用協處理器以時間/能力有效的方式運行專門任務，而且必須通過主處理器上運行的任務將其配置為在前。其目的在于使相關程序得到最短等待執行的時間。

圖2(a)示出了程序的例子及其大部分并行執行。以順序程序語言，例如C語言寫下初始程序。其包括高優先級任務HPi、低優先級任務LPi和能夠在獨立協處理器上運行的任務CPi。編譯-時間相關性分析確定了任務的局部順序，如圖2(b)的例子所示。根據圖2(b)，低優先級任務LP1能夠立即啟動，并且對其他任務不具有任何依賴性，而低優先級任務LP7則依賴于高優先級任務HP4的執行。可以從圖2(b)所示的時間順序匯集高優先級任務HP2、HP4、HP6、HP8、HP10和協處理器任務CP3、CP5、CP9和CP10的相關性，其中，所述示意圖中的每一下方任務均取決于上方任務，因而不能在完成上方任務之前執行。

圖2(c)示出了這一程序的預期執行流。如果可以獲得任何能夠在一般或主處理器上執行的高優先級任務，那么應當立即開始執行。如果還沒有有待執行的高優先級任務，那么主處理器能夠將其時間用在執行低優先級任務上。將這樣的調度稱為搶先調度，例如，在L.Peterson等人的“Operating?System?Concepts”，Addison?Wesley，1986中對這樣的調度給出了說明。

可以將所述相關分析簡化為這樣一種分析，其中，按照C程序的順序對高優先級任務和協處理器任務排序，并盡快使低優先級任務按照這一順序并行設置。

但是，由于通常在編譯時不知道任務的延遲，因而不能將執行追蹤有效地編寫在單線程匯編程序中。

圖3示出了兩個不同執行追蹤的例子，所述的兩個不同的執行追蹤源自于同一程序及其相關分析，并且是由協處理器CP3和CP5的不同運行時延遲導致的。具體而言，圖3(a)示出了第一執行追蹤，其中，以短運行時延遲執行協處理器任務CP3和CP5，從而能夠在較早的階段執行高優先級任務。與之形成對比的是，圖3(b)示出了第二執行追蹤，其中，協處理器任務CP3和CP5占用了更多的周期，因而主處理器需要等待更長的時間來執行低優先級任務LP1，并在較晚的階段執行高優先級任務HP6、HP8和HP10。

因此，不能預先確定執行追蹤，并且任務切換應當是運行時活動。操作系統將根據可得的任務以它們的優先級為基礎將所述任務分配給處理器。為了實現這一點，通常采用堆或優先級隊列存儲任務及其優先級。例如，在T.H.Cormen等人的“Introduction?to?algorithms”，MIT?Press，1990中對其進行了說明。這一提議的缺點在于，向/從這樣的結構存儲/檢索任務要占用大量的處理周期。與任務的數量相比，其將任務切換的適用性限制在了由很多周期構成的大粒度任務上，因為如若不然，任務切換開銷將變得顯著，甚至與程序的順序執行相比可能導致周期的損失。

但是，在具有細粒度的域或應用中，這一方法將不起作用，因而希望獲得優選具有零周期的任務切換。

發明內容

因此，本發明的目的在于提供一種改進的任務調度方案，通過其能夠在沒有存儲和檢索成本缺點的情況下執行并行任務切換。

這一目的是通過根據本發明的處理器裝置、和任務調度方法。