[發(fā)明專(zhuān)利]一種基于時(shí)間片段的任務(wù)調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201611113867.3
• 申請(qǐng)日: 2016-12-07
• 公開(kāi)（公告）號(hào): CN106598717B
• 公開(kāi)（公告）日: 2019-06-11
• 發(fā)明（設(shè)計(jì)）人: 何俊樺;王艷;朱潔
• 申請(qǐng)（專(zhuān)利權(quán)）人: 陜西尚品信息科技有限公司
• 主分類(lèi)號(hào): G06F9/48
• 分類(lèi)號(hào): G06F9/48
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明公開(kāi)了一種基于時(shí)間片段的任務(wù)調(diào)度方法。其實(shí)現(xiàn)方法是：系統(tǒng)檢測(cè)到有新任務(wù)到達(dá)或有任務(wù)結(jié)束時(shí)，立即對(duì)所有任務(wù)的任務(wù)參數(shù)重新初始化，然后將各個(gè)任務(wù)拆分成執(zhí)行時(shí)間片段長(zhǎng)短合理的子任務(wù)，并確定這些子任務(wù)的執(zhí)行順序以及執(zhí)行這些子任務(wù)的處理器，最后更新任務(wù)調(diào)度表，根據(jù)新的任務(wù)調(diào)度表調(diào)度任務(wù)執(zhí)行，并將任務(wù)執(zhí)行完成的結(jié)束信息及時(shí)反饋給前述的任務(wù)參數(shù)初始化部分，促使它生成新的任務(wù)調(diào)度表。本發(fā)明可用于同構(gòu)多處理器系統(tǒng)。

技術(shù)領(lǐng)域

本發(fā)明屬于操作系統(tǒng)領(lǐng)域，尤其涉及到一種基于時(shí)間片段的任務(wù)調(diào)度方法，可用于同構(gòu)多處理器系統(tǒng)。

背景技術(shù)

任務(wù)調(diào)度方法是在設(shè)計(jì)高性能的多處理器系統(tǒng)時(shí)必須考慮的關(guān)鍵性問(wèn)題。隨著全球能源緊缺的加劇，如何降低處理器能耗已經(jīng)引起越來(lái)越多的關(guān)注。因此，一個(gè)好的任務(wù)調(diào)度方法可以使系統(tǒng)在保證服務(wù)質(zhì)量的同時(shí)，還能在盡可能低的額定功率下運(yùn)行，以達(dá)到節(jié)能目的。

現(xiàn)有的背景技術(shù)，通常采用如圖1所示的開(kāi)環(huán)調(diào)度方法。多個(gè)任務(wù)進(jìn)入多處理器系統(tǒng)時(shí)，系統(tǒng)會(huì)根據(jù)各個(gè)任務(wù)的大小為每個(gè)任務(wù)估計(jì)一個(gè)執(zhí)行時(shí)間。當(dāng)一個(gè)任務(wù)在某個(gè)處理器上執(zhí)行時(shí)，將在估計(jì)執(zhí)行時(shí)間內(nèi)一直占用這個(gè)處理器。鑒于估計(jì)執(zhí)行時(shí)間都是基于最壞情況給出的，故而任務(wù)實(shí)際上常常比估計(jì)執(zhí)行時(shí)間要提前完成，之后剩余的這段時(shí)間內(nèi)，即使處理器上并沒(méi)有任務(wù)在運(yùn)行，卻仍然要以前面執(zhí)行任務(wù)時(shí)的運(yùn)行頻率運(yùn)行，這時(shí)，不僅剩余的這段時(shí)間被白白浪費(fèi)掉了，而且還會(huì)產(chǎn)生不必要的能耗。

任務(wù)的估計(jì)執(zhí)行時(shí)間與實(shí)際執(zhí)行時(shí)間相差越大，說(shuō)明系統(tǒng)環(huán)境的不確定性越大，系統(tǒng)浪費(fèi)的能耗也就越大。因而，需要找到一種任務(wù)調(diào)度方法，來(lái)克服系統(tǒng)環(huán)境的不確定性帶來(lái)的能源浪費(fèi)。

發(fā)明內(nèi)容

本發(fā)明提出一種基于時(shí)間片段的任務(wù)調(diào)度方法，利用已完成任務(wù)的反饋信息來(lái)實(shí)時(shí)調(diào)整系統(tǒng)的任務(wù)調(diào)度表，使系統(tǒng)一直處于最佳工作狀態(tài)，從而達(dá)到減小總能耗的目的。

為實(shí)現(xiàn)上述目的，本發(fā)明的技術(shù)方案包括：

一種基于時(shí)間片段的任務(wù)調(diào)度方法，包括以下步驟：

步驟一：每當(dāng)系統(tǒng)監(jiān)測(cè)到有新任務(wù)到達(dá)或者有任務(wù)執(zhí)行結(jié)束時(shí)，系統(tǒng)中的任務(wù)參數(shù)進(jìn)行初始化；

步驟二：對(duì)任務(wù)拆分，并確定任務(wù)執(zhí)行時(shí)間片段；

步驟三：確定任務(wù)的執(zhí)行順序，并輸出任務(wù)調(diào)度表；

步驟四：系統(tǒng)實(shí)時(shí)更新任務(wù)調(diào)度表，按照時(shí)間片段的先后順序，依次控制各處理器執(zhí)行任務(wù)。

進(jìn)一步根據(jù)所述基于時(shí)間片段的任務(wù)調(diào)度方法，步驟一中每當(dāng)系統(tǒng)監(jiān)測(cè)到有新任務(wù)到達(dá)或者有任務(wù)執(zhí)行結(jié)束時(shí)，系統(tǒng)中的任務(wù)參數(shù)進(jìn)行初始化；

系統(tǒng)中的任務(wù)總數(shù)為N，以1,2,...,N對(duì)系統(tǒng)中的任務(wù)進(jìn)行編號(hào)，編號(hào)組成的集合表示為I，I＝{1,2,...,N}，則系統(tǒng)中所有任務(wù)的集合可以表示為T(mén)，T＝{T_i|i∈I}；b_i表示任務(wù)的到達(dá)時(shí)間，x_i表示任務(wù)的估計(jì)最少執(zhí)行時(shí)間，d_i表示任務(wù)的執(zhí)行時(shí)限，則集合T中任一任務(wù)T_i用T_i＝(b_i,x_i,d_i)表示；若任務(wù)T_i在b_i時(shí)刻到達(dá)，則它必須在接下來(lái)的d_i時(shí)間內(nèi)完成，即截止時(shí)刻為b_i+d_i；

x_i為處理器在最壞情況下以最大頻率執(zhí)行該任務(wù)時(shí)所需的時(shí)間，故而任務(wù)的實(shí)際最少執(zhí)行時(shí)間y_i要比x_i小，設(shè)γ_i為實(shí)際執(zhí)行時(shí)間估計(jì)系數(shù)，則有y_i＝γ_ix_i，0＜γ_i≤1，γ_i越小，系統(tǒng)中任務(wù)參數(shù)的不確定性越大。