[發(fā)明專利]一種實(shí)時(shí)多任務(wù)調(diào)度方法和裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201210551909.7
• 申請(qǐng)日: 2012-12-18
• 公開(kāi)（公告）號(hào): CN103870327A
• 公開(kāi)（公告）日: 2014-06-18
• 發(fā)明（設(shè)計(jì)）人: 范東睿;葉笑春;王達(dá);張浩
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司;中國(guó)科學(xué)院計(jì)算技術(shù)研究所
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48
• 代理公司: 北京中博世達(dá)專利商標(biāo)代理有限公司 11274
• 代理人: 申健

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

本發(fā)明涉及計(jì)算機(jī)領(lǐng)域，尤其涉及一種實(shí)時(shí)多任務(wù)調(diào)度方法和裝置。

背景技術(shù)

在通用的硬件系統(tǒng)及其配套操作系統(tǒng)中，往往按照分時(shí)的原則進(jìn)行任務(wù)調(diào)度，調(diào)度算法強(qiáng)調(diào)任務(wù)的公平性，盡量讓不同任務(wù)公平的輪流占用CPU(Central?Processing?Unit，中央處理器)計(jì)算資源，而現(xiàn)實(shí)中，很多應(yīng)用具有特定的實(shí)時(shí)性要求，即要求在規(guī)定的時(shí)間內(nèi)完成任務(wù)，并對(duì)隨機(jī)發(fā)生的外部事件做出響應(yīng)和處理。對(duì)于這類應(yīng)用，普通的強(qiáng)調(diào)任務(wù)公平性的軟硬件調(diào)度算法難以滿足要求，必須采用具有實(shí)時(shí)性保證的任務(wù)調(diào)度算法。

現(xiàn)有技術(shù)中，有如下解決實(shí)時(shí)性問(wèn)題的技術(shù)方案：

采用LLF(Least?Laxity?First，最小裕度優(yōu)先)算法，其中，所述裕度指的是執(zhí)行完該任務(wù)還剩余的空閑時(shí)間，假設(shè)在t時(shí)刻，一個(gè)任務(wù)剩余部分的執(zhí)行時(shí)間為X，其截止期限(絕對(duì))為D，則該任務(wù)的空閑時(shí)間(裕度)為L(zhǎng)＝D-t-X。在所述LLF算法中，一個(gè)任務(wù)的優(yōu)先級(jí)由所述裕度大小決定，裕度越小，優(yōu)先級(jí)越高；如果存在任務(wù)相同的裕度時(shí)，則截止時(shí)間靠前的任務(wù)的優(yōu)先級(jí)高，先被執(zhí)行，并且只有所述裕度≥0時(shí)任務(wù)才可以調(diào)度，否則被夭折。

但是，在所述LLF算法中，在進(jìn)行所述裕度值計(jì)算時(shí)，D、t都可以準(zhǔn)確獲得，但是任務(wù)的剩余執(zhí)行時(shí)間卻難準(zhǔn)確估計(jì)。而且由于不同的硬件平臺(tái)配置不同，相同的程序在不同硬件平臺(tái)上運(yùn)行的時(shí)間也不同，因此在任務(wù)創(chuàng)建時(shí)，很難準(zhǔn)確估計(jì)任務(wù)實(shí)際所需的運(yùn)行時(shí)間，當(dāng)任務(wù)實(shí)際所需的運(yùn)行時(shí)間不準(zhǔn)確時(shí)，將導(dǎo)致在所述LLF算法中，對(duì)任務(wù)剩余執(zhí)行時(shí)間X的計(jì)算也不準(zhǔn)確，最終使得優(yōu)先級(jí)的計(jì)算不準(zhǔn)確，從而影響實(shí)時(shí)任務(wù)調(diào)度算法的實(shí)際效率。

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

本發(fā)明的實(shí)施例提供一種實(shí)時(shí)多任務(wù)調(diào)度方法和裝置，能夠動(dòng)態(tài)校正線程的裕度值，獲得更加準(zhǔn)確的任務(wù)優(yōu)先級(jí)，進(jìn)而提高實(shí)時(shí)多任務(wù)調(diào)度的準(zhǔn)確性。

為達(dá)到上述目的，本發(fā)明的實(shí)施例采用如下技術(shù)方案：

第一方面，提供了一種實(shí)時(shí)多任務(wù)調(diào)度方法，該方法包括：

確定對(duì)當(dāng)前調(diào)度的線程進(jìn)行裕度校正；

根據(jù)所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度和所述當(dāng)前調(diào)度的線程已經(jīng)執(zhí)行的時(shí)間，獲取所述當(dāng)前調(diào)度的線程的剩余執(zhí)行時(shí)間，其中，所述執(zhí)行進(jìn)度為所述當(dāng)前調(diào)度的線程已經(jīng)完成任務(wù)的比例；

根據(jù)所述當(dāng)前調(diào)度的線程的剩余執(zhí)行時(shí)間以及所述當(dāng)前調(diào)度的線程的截止時(shí)間，獲取所述當(dāng)前調(diào)度的線程的裕度；

根據(jù)所述當(dāng)前調(diào)度的線程的裕度，確定所述線程的優(yōu)先級(jí)，并根據(jù)所述線程的優(yōu)先級(jí)重新確定優(yōu)先級(jí)隊(duì)列；

根據(jù)所述重新確定的優(yōu)先級(jí)隊(duì)列，依次調(diào)度所述隊(duì)列中的線程。

在第一種可能的實(shí)現(xiàn)方式中，根據(jù)第一方面，所述確定對(duì)當(dāng)前調(diào)度的線程進(jìn)行裕度校正具體包括：

判斷所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度是否等于預(yù)設(shè)的任務(wù)比例；

若所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度等于所述預(yù)設(shè)的任務(wù)比例，確定對(duì)所述當(dāng)前調(diào)度的線程進(jìn)行裕度校正。

在第二種可能的實(shí)現(xiàn)方式中，根據(jù)第一方面，所述確定對(duì)當(dāng)前調(diào)度的線程進(jìn)行裕度校正具體包括：

判斷所述當(dāng)前調(diào)度的線程已經(jīng)執(zhí)行的時(shí)間是否等于預(yù)設(shè)的時(shí)間；

若所述當(dāng)前調(diào)度的線程已經(jīng)執(zhí)行的時(shí)間等于所述預(yù)設(shè)的時(shí)間，確定對(duì)所述當(dāng)前調(diào)度的線程進(jìn)行裕度校正。

第二方面，提供了一種實(shí)時(shí)多任務(wù)調(diào)度裝置，所述裝置包括第一確定單元、第二確定單元、第一獲取單元、第二獲取單元、調(diào)度單元；

所述第一確定單元，用于確定對(duì)當(dāng)前調(diào)度的線程進(jìn)行裕度校正；

所述第一獲取單元，用于根據(jù)所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度和所述當(dāng)前調(diào)度的線程已經(jīng)執(zhí)行的時(shí)間，獲取所述當(dāng)前調(diào)度的線程的剩余執(zhí)行時(shí)間，其中，所述執(zhí)行進(jìn)度為所述當(dāng)前調(diào)度的線程已經(jīng)完成任務(wù)的比例；

所述第二獲取單元，用于根據(jù)所述當(dāng)前調(diào)度的線程的剩余執(zhí)行時(shí)間以及所述當(dāng)前調(diào)度的線程的截止時(shí)間，獲取所述當(dāng)前調(diào)度的線程的裕度；

所述第二確定單元，用于根據(jù)所述當(dāng)前調(diào)度的線程的裕度，確定所述線程的優(yōu)先級(jí)，并根據(jù)所述確定的優(yōu)先級(jí)重新確定優(yōu)先級(jí)隊(duì)列；

所述調(diào)度單元，用于根據(jù)所述重新確定的優(yōu)先級(jí)隊(duì)列，依次調(diào)度所述隊(duì)列中的線程。

在第一種可能的實(shí)現(xiàn)方式中，根據(jù)第二方面，所述第一確定單元確定對(duì)當(dāng)前調(diào)度的線程進(jìn)行裕度校正具體包括：

判斷所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度是否等于預(yù)設(shè)的任務(wù)比例；

若所述當(dāng)前調(diào)度的線程的執(zhí)行進(jìn)度等于所述預(yù)設(shè)的任務(wù)比例，確定對(duì)所述當(dāng)前調(diào)度的線程進(jìn)行裕度校正。