[發(fā)明專利]用于對任務(wù)請求進(jìn)行調(diào)度的方法和設(shè)備

有效

• 申請?zhí)枺?/td>: 200810081343.X
• 申請日: 2008-02-25
• 公開（公告）號: CN101261592A
• 公開（公告）日: 2008-09-10
• 發(fā)明（設(shè)計(jì)）人: D·M·達(dá)利;L·A·拉斯特拉斯－蒙塔諾;彼德·弗拉納茲克
• 申請（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 中國國際貿(mào)易促進(jìn)委員會專利商標(biāo)事務(wù)所
• 代理人: 李玲

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

本發(fā)明涉及計(jì)算系統(tǒng)中的任務(wù)調(diào)度。

背景技術(shù)

計(jì)算系統(tǒng)接收來自用戶的針對任務(wù)的請求，例如，針對系統(tǒng)資源的請求以及存儲器請求，并且這些請求代表了具有不同優(yōu)先級級別的多種類型的任務(wù)。在此類系統(tǒng)中，低優(yōu)先級請求通常是在所有高優(yōu)先級請求之后進(jìn)行處理的。但是，不同的請求可能在多個周期中使用單個關(guān)鍵資源。因此，對在沒有高優(yōu)先級請求時啟動的低優(yōu)先級請求來說，該低優(yōu)先級請求仍可能延遲隨后的使用公共資源的高優(yōu)先級請求。

寫入業(yè)務(wù)是在存儲器系統(tǒng)中接收的低優(yōu)先級任務(wù)的一個示例。通常，在讀取隊(duì)列為空之前，寫入請求將被緩沖。但是，在寫入請求被調(diào)度后，它可能干擾將來的讀取請求。低優(yōu)先級存儲器請求的另一個示例是預(yù)先提取，也就是說，在預(yù)先提取中，后續(xù)指令以及被應(yīng)用或操作系統(tǒng)標(biāo)記為低優(yōu)先級的存儲器請求將被加載到一隊(duì)列中。壓縮存儲器系統(tǒng)是具有多種類型的請求的存儲器系統(tǒng)的另一個示例。在壓縮存儲器系統(tǒng)中，存儲器重組可以作為低優(yōu)先級任務(wù)執(zhí)行。但是，完成這種重組要花費(fèi)多個周期。重組很少發(fā)生并且可以被緩沖。

因此，需要能夠?qū)Ω鞣N任務(wù)請求進(jìn)行調(diào)度從而使低優(yōu)先級任務(wù)不會抑制高優(yōu)先級任務(wù)的執(zhí)行的系統(tǒng)和方法。

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

本發(fā)明涉及的是根據(jù)過去的訪問模式來預(yù)測何時調(diào)度或延遲請求較為有利的方法和系統(tǒng)，本發(fā)明包括用于預(yù)測何時可能出現(xiàn)高優(yōu)先級請求以及通過調(diào)度低優(yōu)先級請求來最小化預(yù)測到的干擾的方法和系統(tǒng)。通過減小干擾，降低了高優(yōu)先級請求的排隊(duì)延遲，并且提高了整體系統(tǒng)性能。

根據(jù)基于本發(fā)明來調(diào)度任務(wù)的一個示例性方法，維護(hù)了至少兩個隊(duì)列，用以存儲或保持要執(zhí)行的任務(wù)。適合的任務(wù)包括計(jì)算系統(tǒng)內(nèi)的資源請求，例如存儲器請求。每個隊(duì)列都與一個不同的優(yōu)先級級別相關(guān)聯(lián)，并且包含了要處理的任務(wù)，使得任一給定隊(duì)列中的每個任務(wù)的優(yōu)先級級別對應(yīng)于或者基本等同于該隊(duì)列的優(yōu)先級級別。在一個實(shí)施例中，保持了兩個隊(duì)列，即，包含一個或多個高優(yōu)先級任務(wù)的高優(yōu)先級隊(duì)列以及包含一個或多個低優(yōu)先級任務(wù)的低優(yōu)先級隊(duì)列。為了將任務(wù)安置在這些隊(duì)列中，對要處理的任務(wù)進(jìn)行識別，并且為每個已識別任務(wù)關(guān)聯(lián)一優(yōu)先級級別。然后，將每個已識別任務(wù)保存在與其關(guān)聯(lián)的優(yōu)先級相對應(yīng)的隊(duì)列中。

調(diào)度器檢查系統(tǒng)中是否有任何任務(wù)可供調(diào)度以進(jìn)行處理。如果可以調(diào)度任務(wù)，則根據(jù)包含了每個隊(duì)列的關(guān)聯(lián)優(yōu)先級級別的因數(shù)、每個隊(duì)列的當(dāng)前狀態(tài)以及已調(diào)度任務(wù)的歷史，來調(diào)度隊(duì)列中保存的任務(wù)，以供處理或者推遲到以后。此外，可以根據(jù)多個預(yù)先定義的調(diào)度規(guī)則來調(diào)度該任務(wù)，其中這些規(guī)則預(yù)測是調(diào)度任務(wù)還是延遲任務(wù)較有利。這些調(diào)度規(guī)則包括基于隊(duì)列狀態(tài)的規(guī)則，例如對包含在超出預(yù)定閾值標(biāo)準(zhǔn)的隊(duì)列內(nèi)的任務(wù)進(jìn)行調(diào)度，以及基于在給定隊(duì)列中包含的任務(wù)的數(shù)量來調(diào)度任務(wù)。在一個實(shí)施例中，每個隊(duì)列與至少一個預(yù)先定義的閾值標(biāo)準(zhǔn)相關(guān)聯(lián)，并且這些閾值標(biāo)準(zhǔn)包括但不局限于：隊(duì)列中的任務(wù)數(shù)量、隊(duì)列中最早任務(wù)的經(jīng)時、以及這二者的組合。一旦被調(diào)度，那么任務(wù)將會根據(jù)該調(diào)度被處理或執(zhí)行。

在一個實(shí)施例中，維護(hù)了包含多個離散的順序時段或槽的日志。每個時段代表基本相等的預(yù)定時間長度，并且每個時段包含與給定優(yōu)先級級別相關(guān)聯(lián)的在該時段中接收的任務(wù)列表或集合。此外，在與給定優(yōu)先級級別相關(guān)聯(lián)的當(dāng)前時段中接收的任務(wù)被記錄或保存在當(dāng)前時段或當(dāng)前槽中。當(dāng)當(dāng)前時段屆滿時，將當(dāng)前時段或當(dāng)前槽傳送到日志，并且從日志中去除最早的時段或最早的槽。為了根據(jù)多個預(yù)先定義的調(diào)度規(guī)定中的一個或多個規(guī)則來調(diào)度任務(wù)，創(chuàng)建了多個采樣日志。每個采樣日志包含與所維護(hù)的時段日志相對應(yīng)的多個離散的順序時段或采樣槽，并且每個采樣日志中的各時段包含預(yù)定數(shù)量的任務(wù)。因此，每個采樣日志是任務(wù)的采樣歷史日志。為每個采樣日志關(guān)聯(lián)一給定規(guī)則。將所維護(hù)的日志與采樣日志相比較，當(dāng)發(fā)現(xiàn)匹配時，執(zhí)行與采樣日志相關(guān)聯(lián)的規(guī)則。

本發(fā)明的示例性實(shí)施例包括一種用于對計(jì)算系統(tǒng)內(nèi)要處理的任務(wù)請求進(jìn)行調(diào)度的方法。根據(jù)該方法，維護(hù)包含計(jì)算系統(tǒng)內(nèi)要處理的多個任務(wù)請求的列表。這些任務(wù)請求包括計(jì)算系統(tǒng)內(nèi)的資源請求，例如存儲器請求。在一個實(shí)施例中，在至少兩個隊(duì)列中維護(hù)任務(wù)請求的列表。每個隊(duì)列都與一個不同的優(yōu)先級級別相關(guān)聯(lián)，并且包含了所述多個任務(wù)請求中的一個或多個任務(wù)請求。任一給定隊(duì)列中的每個任務(wù)請求的關(guān)聯(lián)優(yōu)先級級別與該隊(duì)列的所述不同優(yōu)先級級別基本相同。在另一個實(shí)施例中，維護(hù)了兩個隊(duì)列，即，包含一個或多個高優(yōu)先級任務(wù)請求的高優(yōu)先級隊(duì)列，以及包含一個或多個低優(yōu)先級任務(wù)請求的低優(yōu)先級隊(duì)列。