TW200813845A - Resource-based scheduler - Google Patents

Description

200813845 九、發明說明： 【發明所屬之技術領域】 本發明係關於對電腦卫作的排程。敎言之，本發明之 具體實施例係關於基於特定工作 卞之貝源利用率標準及對該 等工作欲使用的電腦資 胸貝，原之利用率來將電腦工作排程。 【先前技術】 現今之電腦作業系統（0/s)利用 y』用夕任務排程器來提供多 Ο ϋ 個電腦工作（例如程序）同時運行之外觀。有許多不同的排 程演算法，但一般而言，其概念係將一稱為量子的較小時 間片段賦予一程序之一線程而接著 牧々賊予该程序之另一線程 或另一程序等。該量子之县声彳 ^ 長度很小，一般在20至120毫秒 範圍内。由於人對時間之减知 A知因而看起來該等工作係同 時運行。 中央處理單元（CPU)傾向於係多數雷 少裂免細系統中最快的組 件，而其他電腦資源（例如，磾片 朱月1/0、網路I/O以及甚至記 憶體）傾向於慢得多。例如，芒 夕例々右就來自該碟片之資料傳輸 及該CPU内的資料傳輸來測量，碟片1/〇可能比該⑽慢— 百萬倍。因此，該CPU常常等待此等較慢的資源。例如， 一三千兆赫的CPU在等待一磁碟 磁碟機於一以毫秒測量的平均 存取時間擷取資料時常常一直閒置。 由於數個不同4常常針對相同f源進行競爭，因此工 作常常互相碰撞，從而導致該等工作中之一或多個工作減 緩。從使用者的觀點來看，工作 乍亚才里自身表現為無回應的 應用程式、不穩定的游標移動及緩慢呈__。 121652.doc 200813845 Γ Ο 節流係用以使得此等負面影響最小化之一技術。節流防 止應帛&式或工作使用超過一戶斤分配數量之資源。節流 類型包括碟片1/0節流、CPU節流及網路節流。例如，CPU 即桃可以包括針對_應用程式建立―目標CPU利用率限制 以及在該應用程式超過該目標限制之情況下強迫該應用程 式停止工作。應用節流之電腦資源有時係用於維護應用程 式或不太重要的電腦工作。儘管節流具有優點，但其他工 作及應用程式並不完全明白該電腦工作之資源使用率。 由於電腦實源之浪費一般係以24小時為週期，因而以上 問題f至更加複雜。例如，多數桌面利用不到5%的電腦 可用資源，而高流量伺服器常常利用約2〇%。甚至利用8〇 至9〇%資源的電腦仍有1 〇至20%的可用資源。 純復並利用此原本會損失的資源，需要—種允許在一 用打；或多個工作而不明顯影響其他工作或應 =技術不應讓使用者的時間消耗在該工作 的排耘上，其亦不應對在 統的互動產生負面影響。 α字使用者與該電腦系 本節中說明之方法係可以追求之 思或追求之方法。因此，若無另外指示，對二二已構 之任何方法，皆不應僅憑其係 =本即所說明 先前技術。 於本即中便將其假定為 【發明内容】 基於解說的目的，在以下說明中將提 以便於充分理解本發I但是 =細郎， 右無此等特定細 121652.doc 200813845 、 亦了以貝^本發明。在其他實例下，熟知的結構及裝 置係採用方塊圖形式顯示，以便避免給本發明造成不必要 的混淆。 概觀 Ο Ο 大多數電腦不會在整個時間段皆利用其所有資源容量。 即使對於一天二十四小時、一周七天的看起來係高使用率 之電腦，以及每天僅開啟一部分時間之電腦，實際情況一 般皆如此。因此會浪費電腦時間及資源。例如，在一二十 w j時週期，向負荷使周以及活動中具有短暫峰值之一電 腦系統一般可能僅使用其資源的約5至20%。 二:據本發明之一具體實施例，基於對一資源之利用率及 该電腦工作所具有之一關於該資源的利用率標準來對一電 腦工作進行排程。例如，L作可能有—利用率標 準、，其—碟片1/0資源具有6则可用容量以便對該電腦工 作=排程。在此具體實施例中，若該碟片ι/〇資源之可 用谷里小於60%，則不對該電腦工作進行排程。 广具體實施例巾，一基於資源之排程器陶)將每一 電細工作放到數個不同的基於資源之排程工作列表中的至 少-工作列表上。料基於資源之排程工作列表包括作不 限^-碟請排程工作列表、CPU排程工作列表及網路 呈工作列表。因此，-特定的排程工作列 待使用该特^資源之電腦工作。在此具體實施例中， ::工作：的每-工作皆具有與該特定資源相關之一;;用 4準4 RBSit擇該等f源中的—資源作為接下來將具 121652.doc 200813845 有-所排程之電腦工作。在一具體實施例中，該選擇係基 於該資源之一優先權。例如’ 一碟片"〇資源可能具有比 =pu資源更高的優先權。在―具體實施例中，指定為較 j貝原之貝源所獲知之優先權比指定為較快資源之資源更 南0 * 在選擇欲排程的資源後，該RBS從對應於該選定資源的 作列表中選擇該等電腦工作之—電腦工作以供執行。在 …體K轭例中，该RBS基於將該資源的可用容量與該等 包响工，乍的利用率標準匹配之—標準來選擇該電脂工作。 但是，該RBS還使料他„，例如該料腦玉作之優先 輕電月自工作之所需執行順序、將電腦工作放在該工作列 表上的順序等。 w應庄思’在—具體實施例中，該咖允許在即使每—電 腦工作料需要的其他資源正在供其他κ完全或部分） 利用但紅作欲利料資源係（完全或部分）可用時便藉由 對該電腦卫作進行排程來高效率地利用多個電腦資源而減 小對該等其他工作執行之衝擊。 【實施方式】 圖1A係依據本發明之—具體實施例具有基於資源之排程 f作列表12G的—基於資源之排程器⑽S)10G之-圖式。 :RBS 100基於不同電腦資源之可用容量對電腦工作 則瞻性的排程。作為範例’不同的資源可以包括但不限 於.CPU、碟片1/〇、網路1/〇、視訊、記憶體、鍵盤、網 121652.doc 200813845 路貝源等。本文所使用的術語，，電腦工作π或,,工作，,包括但 不限於-電腦程序、—線程、一微工作(下文將說明)或； 執行的電腦碼之任何部分。該咖ΗΗ)可以允許每一電月， 工作接收其資源要求而不與任何其他工作對資源的要求： 撞。在一具體實施例中，該RBS 100能夠決定何時僅部分 利用-特定資源，並將未利用的部分分配給一選定工作， 而對已經利用該資源的任何其他工作之衝擊降到 Ο 度。 牡一具體實施例中，兮"R R Q，Λ Λ W h 吻RBS丄00蚋到各種不同資源來將 電腦工作排程。該等不同資源可能或可能不在與RBS100 相同的電腦系統上°例如’在-具體實施例中，該RBS 1 〇 0將電腦工作排程為系丨田 一— 丨㈣為㈣-經由網路存取之資源。作為 -特定範例，可以經由該網際網路存取該資源。 /此，在一具體實施例中，該RBS 100接收欲存取各種 資源之電腦工作並就應將該等電腦玉作中的哪_工作排程 為利用㈣資源中的哪—資源以及應將該等電腦工作排程 於何時作出排程決策。 電腦資源利用率 、該RBS⑽輸人資源利用率資訊1G5，其描述各種電腦資 原之利用率。s亥利用率可以與_間隔或一指定點相關。該 利用率可以係在一指定間隔期間之一平均利用率。例如， 可以將-資源之利科指定為在—指定時間間隔期間之一 平均利用率。作為一特定範例’利用率為鄕之—CPU資 源可以與-最近時間間隔期間之平均利用率相關。在一具 121652.doc -10- 200813845 體實施例中，以量子來測量該間隔。 在-具體實施财，該制率 用率可炉伤其你笙β + 歎子°例如’該利 用革了此絲於切在-指定時間，輯㈣ 如，若-資源有"X”個操作等待執行，則該利 ; ”x”。作為一資源之一基於數字的利用率之 係 利用率係基於欲利用一特定資源之請求之數目。^例’該 Ο Ο -具體實施例中’該利用率係基於每—程序欲利2特= 貝源之请求之總數。基於數字的利用率可以與— 隔相關。例如，在一具體實施例中，其於赵〜”’ 3曰 率係基於等待在-特定時間期ϋ+ι _用 间間隔期間執仃的操作之平均數 目。在另一具體實施例中，基於數字之資 等待在H點執行的操作數目。…肖率係基於 在一具體實施例中，該RBS100基於該資源利用率⑽來 來資源利用率。例如’基於欲利用— 以及可能基於其他因素），對未來資源利用率作出 。十。：為另-乾例，基於-特定資源之百分比利用率 以及可能基於其他因素），對未來資源利用率作出一估 計。 電腦工作利用率標準 該咖100還輸入針對欲排程工作之利用率標準】心該 =用率標準118係關於該等資源。例如，可以使用資源 私界，其中該RBS 100僅在其他工作的資源利用率低於該 臨，之情況下才對一電腦工作進行排程。使用資源臨界之 一範例係在碟片1/0具有小於6〇%的可用容量之情況下該 121652.doc 200813845 片I/O。在— 面（API)，以 標準11 8。在 RBS 1 00僅將一特定電腦工作排程為使用該碟 具體實施例中，該RBS 100具有一應用程式介 供一擁有該電腦工作之應用程式提供利用率 此提供一範例性API。

在一具體實施例中，該利用率標準118係基於時間。讓 利用率標準118基於一百分比係一基於時間之標準之一範 例。在一具體實施例中，該利用率標準118係基於數字轭 基於數字之利用率標準118之—範例係等待利用一特定資 源來執行之操作數目。基於數字之利周率標準118之另一 範例係所接收的欲使用一資源之請求數目。例如，一特定 程序之利用率標準丨㈣基於欲使用—特定f源之請求數 目° 在-具體實施例中，該RBS 1〇〇儲存歷史利用率資訊 116。該歷史利用率資訊116描述該等工作之—或多個工作 先月)資源利用率。例如’儲存一電腦工作利用過30%的 網路⑽資源之事實以供將來參考。在—具體實施例中， 4RBS 1〇〇使用该歷史利用率資訊ιι6來決定用於對一電腦 工作進行排歡利料標準。例如，基於該電^作先前 對特疋貝源之一或多次利用，該RBS 1〇〇決定一電腦工 作針對該特定資源具有_”χ”百分比之利用率標準。該娜 ⑽接著在對該電腦工作進㈣料使用關用率標準。 Θ UBS 1GG還輸人該等欲排程工作之可執行碼⑽，該 R B S⑽分析該可執行碼⑽來決定利用率標準。 延緩排程決策 121652.doc -12- 200813845 在-具體實施例中，可以延緩關於是 作利用一特定資源之決定。例如，一特定電腦工 且古4 4 1 荷疋#電腦工作可以 /、有允許在该基於資源之排程器甚至 該特定雷日似丁 Α 考置是否欲排程 :t工作之前便伺服來自其他電腦工作的指定數 Μ求之一利用率標準。在一具體實施例 用座古仏 价田 右0哀貝源之利 二^於—㈣，則獅咏緩執㈣以電腦工作 特疋電腦工作指定可以在排程該特定以 Ο Ο 來自其他電腦工作之請求數目。在一具體實 习服，亥數目之請求後，接τ4ι㈣特定電腦n 另一具體實_中，在Μ服請求後，該RBS^: 2 許該特定電腦工作擁有該資源。 疋 :-具體實施例中’該基於資源之排程器 以無延遲滿足的資源請求之一正規工作列表以及針對= L緩的貝源4求之1緩工作列表。請求係放在节延 緩列表上時，該延遲列表中的每—項目可以該當前請^編 為戮記。可以基於應首先伺服哪一延緩請求來將此等延 緩請求排序。在—具體實_中，有多個延緩工作列表 與該正規列表相對’當該RBS決定開始—新請求時，、該 RBS可能首先查看該延緩列表以弄清是否有任何請求即將 過期而因此接下來取走該等請求。 基於資源之排程工作列表 在-具體實施例中，該RBS 100針對一電腦工作可能經 排程而使用的每一資源具有一基於資源之排程工作歹:： 120。例如，該RBS 100具有一 cpu資源工作列表12〇⑴、 121652.doc -13 - 200813845 碟片I/O工作列表120(2)、一網路ι/ο工作列表poo)及J: 他資源工作列表12_。其他資源工作列表=二括^ 不限於一網路資源工作列表、一視訊資源工作列表、一鍵 盤貧源工作列表。每一工作列表12〇包含對應於該資源而 • 荨待利用"亥為源之工作。為了不混淆該圖式，在圖1Α中並 未描述所有可能的基於資源之排程工作列表。在一具體實 施例中，一特定工作列表係針對利用一資源組合之電腦工 〇 作。在一具體實施例中，針對一特定資源有兩個或更多工 作列表，其中每一工作列表到應於一不同優先權υ例如， 具有一高優先權之電腦工作屬於一工作列表，而一中等優 先權在另工作列表上荨專。一工作列表可以係排序或不 排序。 在一具體實施例中，該RBS 1〇〇基於該可執行碼1〇8之分 析來決定將一電腦工作放在哪一工作列表上。例如，在一 具體實施例中，該RBS 100檢查該電腦工作之可執行碼1〇8 U 中的指令以決定該電腦工作需要什麼資源。 在一具體實施例中，當有一足夠數量之一電腦資源可供 使用時，該RBS 1〇〇將該資源給予對應於該資源的工作列 • 表中之電腦工作之一。例如，排程邏輯112基於該資源之 . 可用容量及該等電腦工作之利用率標準來選擇該工作列表 上的電腦工作之一。可以使用其他選擇標準。該等選擇標 準包括但不限於將工作添加到該工作列表之順序、電腦工 作優先權（例如，程序優先權、線程優先權）以及將該資源 之可用容量與該等工作之資源需要匹配。該選擇可以係基 121652.doc -14- 200813845 於此等標準之任何組合以及未明確提到的其他標準。

ϋ 不採用基於資源之排程工作列表的基於資源之排程器 在一具體實㈣中，該RBS 1〇〇不使用對應於各種電腦 資源之排程工作列表。參考圖⑺，該咖1〇〇隨時而不按 特定順序接收將電腦工作排程之請求。例如，由於一應用 程式需要執行—或多個電腦卫作’因此該應用程式:該 RBS 1〇〇傳送一請求以對—或多個電腦工作進行排程。該 RBS 1〇〇決定或係獲知一特定電腦工作欲使用哪一或哪些 資源。資源範例包括-處理器3〇4、.儲存裝置3 怒 <、、、只✓丨、呑占 312、輸入裝置314及網路通信介面318及一經由網路存 取之網路資源182。 該RBS 100決定或係獲知該特定資源之利用率。該 1〇〇還決定或係獲知該電腦工作所具有的與該特定資源相 關之利用率標準。基於該特定資源之利用率及該利用率標 準，該RBS 1〇〇決定是否欲將該特定電腦工作排程為利= 該特定資源。例如，若該網路通信介面318之利用率達到 一電腦工作之利用率標準，則RBS 1〇〇將該電腦工作排程 為使用該網路通信介面318來執行。若否，則該RBs 1〇〇不 將該電腦工作排程為使用該網路通信介面3丨8。實際上， 當該網路通信介面318之利用率達到一電腦工作之利用率 標準時，該RBS 1 〇〇可以等待並排程該電腦工作。 優先化資源 在一具體μ轭例中，基於排程目的對該等電腦資源進行 優先化。例如，可以基於一資源之相對速度對cpu、碟片 121652.doc -15 - 200813845 1/〇、網路卯及其他資源進行分級。例如，可能將一碟片 卯滅為與-CPU資源相比之一更慢資源，而因此賦予其 -更高優先權。同樣，該網路1/0資源可能比該碟片卯更 快但比該CPU更慢。因此，可以將比該CPU更高但比該碟 片/0更低之優先權給予該網路資源。若該RBs刚對更慢 資源加以考量並以一更高優先權對此等資源進行排程，則 可以使得針對諸如-CPU之類更快資源之延遲最小化。 基於應用程式之範例 下面係在一應周程式中基於資源之排程之—範例。例 如，制、用程式可以係一磁碟重組工具或一病毒掃描器。 在此祀例中，電腦工作A係置於該碟片1/〇排程工作列表 120(2)之頂部而具有一 6〇%碟片1/〇可用容量之利用率標 準，而電腦工作B(其在該碟片1/〇排程工作列表12〇(2)上僅 次於電腦工作A)具有一 2〇%碟片1/〇可用容量之利用率標 準。若該碟片LO具有30%之可用容量，則該RBS ι〇〇不會 對電腦工作A進行排程，因為該碟片1/〇沒有足夠的可用容 量。但是，可以對電腦工作B進行排程。在此情況下，該 RBS 1〇〇藉由將一適當的電腦工作（電腦工作b)排程為利用 該碟片I/O而非浪費該碟片1/〇來使用該3〇%的碟片ι/〇可用 谷里。若該RBS 100將該碟片1/0資源給予電腦工作a(其需 要60%的碟片1/〇)，則此可能已經引起一電腦工作碰撞， 因為應分配超過100〇/〇的碟片J/0資源。 基於核心位準資源之排程器 在一具體實施例中，在該核心位準將該RBS 100實施於 121652.doc -16- 200813845 -o/s中。在此—具體實施例中，該核心位準咖IQ。完全 瞭解請求執行的電腦卫作（例如線程）之整個卫作列表。因 1匕’該RBS1GG可以基於資源可心來對該執行進行排 序:而無需決定任何資源之百分比利用率。此係由於該 ΜΗ)已㈣全控制各種資源之排程。無需測量其便已 、、二知道，因為其係該等資源之分配者。 程序流程 圖2係解說依據本發明之一具體實施例用於基於資源之 ㈣之二程序2GG之步驟之—流程圖m說明以一特 疋順序祝明程序200之步驟。但是，料步驟可以一不同 順序發生。此外’可以將步驟重複多二欠。在步驟202中， 该MS 100接收—或多個工作之利用率標準。例如，一應 用，式將4㈣率標準提供給該咖⑽。該應用程式可 以針對不同電腦工作 .,.,# ^ 乍晶疋不同私準。该應用程式無需指定 、'十^八電腦工作之利用率標準。

U 據本發明之—具體實施例，該應用程式將參數傳送至 ⑽以控制資源利用率。資源利用率之控制包括但不 乂碟請、咖及網路。例如，該應用程式可以請求 個資源或其他資源之臨界位準之任何組合未決之 電 作。此外，該應用程式可以針對不同 電月旬工作指定不 例，該庫用" 準。例如，依據-具體實施 @應用耘式針 — 位準。㈣，π、 U作指定—不同的資源臨界 可以進行細粒資源管理。 在步驟204中，該咖1〇〇決定一或多個工作之利用率標 121652.doc -17- 200813845 準具體實施例中，該RBS 1〇〇決定一電腦工作對一 f疋貝源之預期利用率，其中該利用率標準係基於該預期 貝原利用率。在一具體實施例中，該RBS 1 00藉由檢查該 特疋電腦工作中66 #人4¾、4? & 肀的扣τ末決疋一特定電腦工作之預期利用 ^在具體實施例中，該RBS 1〇〇讓該預期利用率基於 一所儲存的值，該值描述該特定電腦X作對該資源之先前 利用率。 T心元刖 Ο 在步驟2 0 6中，將雷丁 a、工 將電驷工作添加到基於資源之排程工作 =表。例如，將—特定程序，或者至少係—特定程序之線 放在至少—基於資源之排程卫作列表上。由於更多工 作。月求排程’因此將其添加到基於資源之排程工作列表。 在 具體實施例中，將爽白'^少T* rn 以自4多不同電腦工作之請求放在 口亥工作列表上。在一 ”體^例中，可藉由將—電腦工作 =利用—特定資源來滿足料請求。在—具體實施例 ^基於該電腦工作之優先權將一電腦工作插入該工作列 二：位置。在—具體實施例中，由於-程序之線程之 執仃順序可能很重要，因此 因此電^工作（例如線程）在該工作 表上係定位成保持所需執行順序。 在步驟208中，選蔣 擇一特疋的電腦資源供利用。例如， μ BS 1〇〇可以決定已指一 更高優先權。作為—特定，電知貝源應具有- 資诉, 特疋耗例，該RBS 1〇〇選擇該碟片Ϊ/0 貝源。但是，該選擇 裎…<« 係基於其他因素’例如線程流 每:工作優先權(例如’程序優先權、線程優先權)、 列表上等待執行的工作（例如，線程）數目及一工 121652.doc •18- 200813845 作（例如，線程或程序）所需要的其他資源之可用性。 率在I驟210中，該RBS刚決定該選定電腦資源之利用 夂该利用率可以係基於一最近間隔期間的活動。例如， 個二：率可以係基於任何方便的測量，例如’最後的·、，' 子或-最近時間週期。但是，該利用率無需基於—間 同歹，)如，该利用率可能係基於等待在 的操作數目。 ^门點執仃 Ο

I 依據本發明之-具體實施例’當該RBS 100計算資源 用率時，所測量者係除與-特定應用程式相關的工作= 之工=之資源利用率。將該CPU利用率臨界設定為20〇/。之 、範例係用於解§兒。若在允許執行與一特定應用程式相

關的電腦工作之箭pmT 則CPU利用率低於20%，則當該等電腦工 作執盯時cpu利用率可以增加至超過2〇%。在此範例十， 並不將此超過20%之增加考量為對cpu資源利用率之違 反。類似原理可應用於網路、碟片1/〇資源及其他資源。 在一具體實施例中，該㈣_估計在-未來時間間隔 期間該選定電腦眘. 貝/原之利用率。該RBS 100可以基於該資 源之最近利用率來估計未來利用率。作為一特定範例，測 量（或以其他方式復A、 式侍知）一網路ι/〇之最近利用率。基於最近 的、罔路I/O利用對在不遠的將來網路㈤之利用率作一 估計。該估計亦可以係基於其他因素。

在步驟212中’該RBs 1〇〇在對應於該選定資源的工作列 表上選擇Θ等電腦工作之一電腦工作。該rbs⑽將供執 订的k疋電^工作排程為使用該選定電腦資源。該RBS 121652.doc 19 200813845 土於對忒特疋資源之利用率及針對該特定電腦資源的 工作列表上該等電腦工作中之至少_電腦卫作之利用率標 2來：行該選擇。例如，若該選定資源之利用率為6〇%而 一特定電腦卫作之利用率標準係該選定資源具有小於4〇% • 之利用率，則不對該特定電腦工作進行排程，因為不滿足 . 該利用率標準。在此情況下，該RBS 100可以選擇另一電 腦工:並在其利科標準允許該選定資源、具有6〇%的利用 f) 率之情況下對該電腦工作進行排程。 藉由重複程序200的步驟之至少某些步驟以便到電腦工 作一個接一個地進行排程，該RBS決定針對電腦工作之一 排程順序。 在步驟214中，該RBS 1〇〇儲存針對剛執行的電腦工作之 ^源利用率資訊。該RBS 100可以隨後使用此資源利用率 二貝5孔來決定針對該電腦工作之利用率標準。 微工作 G 在一具體實施例中，該RBS 1〇〇對微工作進行排程。在 -具體實施例中’微工作之尺寸允許在一所分配時間内完 成一特定的微工作’在該所分配時間期間該特定微工作擁 . f —用於執行該處理卫作之資源。在-具體實施例中，每 • 一微工作之尺寸使其將在其所分配時間内完成。但是，有 可能該等微工作中的某些微工作過大而無法在其所分配時 間内完成執行。 在一具體實施例中，該所分配時間係一量子。量子係一 賦予電腦碼之一部分的時間片段(例如，一線程），在該時 121652.doc >20- 200813845 間片段期間該碼部分 用不同#子。hh 不同的作業系統使 . 9派給一特定碼部分之量子可以美於 運仃時間期間的愔汐A ^ 里丁 j以基於 0 h况而改變。例如，一 小分配給一線程的量子只+。产 了此、加或減 期將分配給一電腦 暴於預

Ah , 乍的里子尺寸將該電腦工作分成料工 作。在另-具體實施例中 #刀成楗工 子尺寸脾# φ 中基於已刀配給一電腦工作的量 子尺寸將该電腦工作分成微工 Γ '\ ί 運行時間期間作出關认 在運仃時間之前或 工作分割出去之決ι將該電腦工作之哪些部分作為微 依據一具體實施例， .最小)的工作單元，Α 作係實質上較小(例如， 丨F平7L，其可以係一 時安全地允許在執行中作早几而完成而同 全地允許在執行中作 ：了-微工作執行。安 作之執行而不會影響 g特… 果。 々有5亥專祕工作之執行而產生之結 一微工作可以你 \ 、 線程之一部分。例如，一续条。叮' ^ 分成多個微工作。可 、’复長可以係 m . ^ ,Α, „ 木取與一線程的排程類似之方弋氺 對此“工作進行排 方式來 /丨山 但疋’如前所述，在一且挪— 例中，若在期間一微工 ，、體貫施 作夺雍有一處理資源之一旦 時間週期期間允許執 、 里子或其他 行。 亥破工作，則該微工作將完成其執 工作在任—時間可能僅需要很少數量的:〜 如，CPU時間、記情 的貝源（例 u體分配）。在任一時間此g 使用可能產生一隱密予1匕類最小的資源 4矛王序。讓該等微工作保持較小，從而 121652.doc -21 - 200813845 允。午名電恥工作一次僅使用少量的電腦資源。因此，依據 =發明之-具體實施例，執行—微工作消耗數量相當小的 貝源以至於不會明顯影響該電腦系統中其他應用程式之性 能0

範例API ( Ο 本發明之-具體實施例係用以允許一應用程式指定各種 資源利用率參數之—API。在—具體實施例中，該rbs ι〇〇 具有此— API。應用程式可以使用該Αρι來指定針對電腦工 作（例士私汴、旅狂、微工作或其他碼部分）之利用率標 準。该乾例API具有以下針對cpu、碟片及網路之資源臨 界參數。 • CPU利用率臨界 φ未決碟片I/O計數臨界 •網路利用率臨界 疋以上參數。例如，針對一使 使用一網路臨界。但是，對於 該網路臨界可以為零。因此， 可以針對每一電腦工作指 用該網路之電腦工作，可以 不使用該網路之電腦工作， 依據本發明之一具體實施例提供細粒資源管理。 60%之情況下執行 界因素之任何組合 作為-特㈣例，該應隸切以請純在該CPU利用 率低於50%而該1/()碟片制率低於鄉而網路流量低於 —特定電腦工作。可以使用該等資源臨 ，亦包括因素根本不存在。依據本發明 之一具體實施例，該CPU利用率臨界在RBS對該cpu的使 用（相對於任何其他工作對該CPU的使用）之間區分。 121652.doc -22- 200813845 以下兩個參數係用於指定一期間將測量利用率之間隔。 φ CPU利用率窗口 。 •網路利用率窗口 該CPU利用率窗口參數定義一期間計算cpu利用率之時 • 間窗口。例如，將最後η毫秒期間的CPU利用率平均。兮 _ 網路利用率窗口定義一期間計算網路利用率之時間窗口 ^ =等參數可能在該RBS 100内部。但是，一應用程二二以 〇 超越此等參數。未決碟片在任何時間點皆為絕對，而 因此不必對其進行計算w 可以將-強制閒置時間參數從該應用程式傳遞至該綱 以控制隨時間展開該等電腦工作之方式。該強制閒置時間 參數係可選的。此外，在使用時，該強制閒置參數之值可 •強制閒置時間

U 該RBS記錄”閒置時間"，其係定義為在已執行所有電腦 工作後之系統閒置時間。例如’應'用程式可以藉由該哪 將電腦工作—起列在工作列表上。當在基於資源之工作列 表120上沒有任何電心料，該RBS等待該指定強制閒 置時間經過而接著喚醒並授權該（等）應用程式執行額外工 作。例如，—磁碟重組工具可能首先執行若干電腦工作以 j兹碟機進仃磁碟重組’接著係藉由該咖電腦工作排 程器而暫停。在該指定強制閒置時間過後，該RBS調用該 磁碟重組工具授權額外工作。例如，該磁碟重組工具可能 執仃- /月理工例如釋放記憶體。強制閒置時間可以係 121652.doc -23 - 200813845 一可以藉由一應用程式來調整之預設參數。 乂下，數係關於在資源利用率高於一臨界時 電腦工作。 寻待執行一 •等待時間 •最大等待時間 若該咖決定該資源利用率目前過高而無法執行 η ο 則該咖等待該指定等待時間經過而接著重新檢: 貝率。每次在咖決定該資源制率過高時，可以 ::::::間參數，—增加該等待時間 2^至與該最大特時間。該應用程式以在其初次 調整此等參數。應用私式可以在其運行時間期間 當該範例祀使用時間（例％，ms)來指定各種參數時， 可以使用諸如量子之類其他測量。 變化 、在一具體實施例t，該彻係—作㈣統之一部 分。在另-具體實施例中，該RBs 1〇〇係一獨立應用程 式’其輔助針對用於其他應用程式的電腦工作進行排程。 在另-具體實施例中，該RBS丨⑼係整合進—應用程式並 針對該特定應用程式進行排程。例如，該rbs 2⑼可以係 整5進一磁碟重組工具或一病毒偵測程式。 在-具體實施例中，若該RBS 1〇〇在該作業系統之外部 執行，則該RBS Π)0對其自身資源利用率進行自我限制。 例如，該RBS 100監視其自己的資源利用率而若其自己的 121652.doc -24- 200813845 資源利用率變得過高，則該RBS 100向該作業系統作出一 請求以將對該RBS 100之排程停止一時間週期。 其他範例 以下範例解說該RBS 1〇〇可採取的操作方式。但是，节 刪_並非必需如&等範例中之說明進行為二 範例’該RBS 1GG針對用於—特定應用程式的多個電腦工 作進行排程。此等電腦工作中的某些工作可能需要碑片 1/〇。該哪_可以分析碟片利用率作為將該等電腦工作 排程之一條件1碟片利周率過高，則該㈣100_直， 待到碟片利用率下降再對該應用程式之一特定的電腦工： 進订排程。該RBS⑽繼續監視該碟片ι/〇利用率，而允許 在若無其他應用程式欲存取碟片I/Q之情況下對另一電腦 工作進行排程。但是，在此且告 隹此八肢只施例中，若另一應用程 式仅利用碟片1/〇，則該RBS 1〇〇 ^ 卜兀汗對另一電腦工作進 Ο 仃排程。因此，其他應用程式可以利用該碟片1/0。 作為另一範例，該RBS 1〇〇 八 、亡旦 _ 刀析、，，罔路活動。若網路 ^置過咼，則該RBS 1〇〇不會 ,^ 7 , L里减級之刚對該應用程 式之任何電腦工作進行排程。 RRo 1ηΛ,. ^ 右凋路夏足夠低，則該 RBS 1 00將電腦工作排 祐##烟狄— 七、執仃。该100繼續檢查以 霍保A、、，罔路流量保持足夠低。 則可以對另—電腦m 料量㈣足夠低， 古目^ 岛作進订排程。但是，若流量變得過 爭鉍Λ袖- 退订排程以供執行。在此等 最後兩個靶例中，該 並非必需。 乍了以係-微工作。但是，此 121652.doc -25- 200813845 硬體概觀 圖3係解說一可針斜料从每 丁對性地貫施本發明之一具體實施 電腦系統300之一方塊圖。 、 J的 乃尾圖。私序200之步驟係作為指令 於系統300的電腦可讀敌M鱗 电包」印取媒體之一或多個媒體上並執行於 電腦系統300之處理器上。電 、 电月匈系、、先300包括一匯流排3〇2 或其他用以傳達資訊之通俨機 铖構，以及一與匯流排3〇2 合用以處理資訊之虑王5哭、Q A /1 -- 貝冬爽理态304。電腦系統300還包括一主

Ο 憶體306，例如一隨機存取印橋 蜗仔取.己憶體（RAM)或其他動態儲存 裝置，其係耗合至匯流排302用以儲存欲藉由處理器3〇4來 執行二資訊及指令。主記憶體鳩還可心在執行欲藉由 處理為304來執打的指令期間儲存暫時變數或其他中間資 讯。電腦系統300進一步包括一唯讀記憶體（r〇m)3〇8或耦 合至匯流排302用以儲存用於處理器3〇4的靜態資訊及指令 之其他靜態儲存裝置。提供—儲存裝置3糊如—磁碟二 光碟）並將其耦合至匯流排3 〇2以儲存資訊及指令。該電腦 ^統3〇0可具有任何數目之處理器3〇4。例如，在一具體實 加例中’電腦系統300係-多處理器系統。該處理器州可 以具有任何數目之核心。在一具體實施例中，該處理器 304係—多核心處理器304。電腦系統3〇〇可用於一 機器。 、王 電腦系統300可以係經由匯流排3〇2耦合至一顯示器 312例如一陰極射線管（CRT),以向一電腦使用者顯示資 訊。包括文數及其他鍵之一輸入裝置314係耦合至匯流排 302，以將資訊及命令選擇傳達至處理器3〇4。其他類型的 121652.doc -26- 200813845 使用者輸入裝置係游標控制器3 16，例如用以將方向資訊 及命令選擇傳達至處理器304並用以控制顯示器312上的游 標移動之一滑鼠、一軌跡球或游標方向鍵。此輸入裝置一 般在兩軸上（一第一軸（例如χ)與一第二軸（例如y))具有兩個 自由度，從而允許該裝置指定在一平面内的位置。 f ϋ 本發明係關於實施本文所述技術之電腦系統3〇〇之使 用。依據本發明之一具體實施例，回應於處理器3〇4執行 ，含於主記憶體306中的一或多個指令之一或多個序列， 藉由電腦系統300來執行該些技術。T以將此類指令從另 一機器可讀取㈣（例如儲存裝置31〇)讀人主記憶體3〇6。 包含於主記憶體则中的指令序列之執行促使處理器3〇4執 仃本文所說明之程序步驟。在替代性具體實施例中，可以 =硬：電路來替代軟體指令或與軟體指令組合以實施本 ^月。因此，本發明之具體實施例不限於硬 之任何特定組合。 纷汉秋體 本文所使用的術語”機械可讀取媒體,,表示參 -機器以-特定方式進行操作的資料冑=使 提供指實施例中，例如在向處理器 據： 時涉及到各種機器可讀取婢體此 揮發性媒體及傳輸媒體==限於非揮發性媒體、 或磁碟，例如儲存農置31〇揮= 媒體包括’例如，光碟 體，例如主記情體3〇: 愈性媒體包括動態記憶 己U體3〇6。傳輸媒體 光纖，其中包括包含匯流排302傳=電境、銅線及 攻。傳輪媒體亦可以採 121652.doc -27· 200813845 ===式’例如在無線電波及紅外_通信 該媒體所承载的和八：有此類媒體必須係有形的，以使得 實體機構來偵測。〜夠错由將該等指令讀入-機器之- 一般形式的機哭> 性磁碟、硬碟取媒體包括，例如，-軟碟、-軟 贡或任何其他磁性媒體、一 CD-ROM、 任何其他光學媒體 i妯每μ ^ 卞片紙帶、具有孔圖案的任何 其他貫體媒體、—Ram、 EPROM、任何 A # u 、- EPR0M、-快閃 , ^ ^己嗯體晶片或匣、如下文所述之一載 ’ ” 電腦從中讀取之任何其他媒體。 在將一或多個指今 _ ..^ 或夕個序列載送到處理器3 04以 Γ订時可能涉及各種形式之機器可讀取媒體。例如，最 Ο :叮以在一通程電腦之-磁碟上實施該等指令。該遠程電 可乂將忒等私令載入其動態記憶體並使用一數據機來透 過了電話線傳送該等指♦。電腦系統300之-區域數據機 可、在。亥電話線上接收該資料並使用一紅外線發射器將該 資料轉換為一紅外線信號。一紅外線偵測器可以接收在該 紅外線信號中載送之資料而適當的電路可以將該資料放在 匯•排302上。g流排3〇2將該資料載送至主記憶體服， 處理器304彳文该主記憶體3〇6擷取並執行該等指令。視需要 可以將主記憶體306接收之指令在處理器3〇4執行之前或之 後儲存於儲存裝置310上。 電腦系統300還包括一耦合至匯流排3〇2之通信介面 318。通^介面318提供耗合至一網路鏈路3 2〇之一雙向資 121652.doc •28- 200813845 料通k，該網路鏈路320係連接至一區域網路322。例如， 通k "面3 1 8可以係一整合式服務數位網路（udn)卡或一 數據機，用於提供與一對應類型電話線之一資料通信連 接。作為另一範例，通信介面318可以係一區域網路（Lan) 卡用於提供與一相容LAN之一資料通信連接。還可以實施 無線鏈路。在任何此類實施方案中，通信介面318傳送並 Ο

接收電性、電磁或光學信號，該等信號載送表示各類資訊 之數位資料流。 ' ，..罔路鏈路.-般透過_或多個網路提供與其他實料震 置之資料通信。例如，網路鏈路32()可以透過區域網路奶 提供與-主機電腦324或與藉由一網際網路服務提供者 (ISP)326來操作的資料設備之—連接。isp咖進而透過全 ^封I貝料itL網路（現在_般稱為"網際網路”似）來提供 貝料通k服務。區域網路322及網際網路328皆使用載送數 位資料流之電性、電磁或光學信號。透過各種網路的信號 “在罔路鏈：320上與透過通信介面318的信號係傳輸該資 吕fl之載波之範例性形式，盆 /、將该數位負料載送至電腦夺统 300並從電腦系統3〇〇載送該數位資料。 糸、·先 電腦系統3 0 〇可以读讲纟 透匕、獨路、網路鏈路32〇及通 息與接，包括程式碼。在 可能透物 路322及Μ介面318發送—針對—應用 該接收碼可以伤扃甘敁^ Α又碼。 …接收時藉由處理器304來執行，及/ 或儲存於儲存裴置31() 木钒仃，及/ 中或其他非揮發性儲存器中以供隨 121652.doc -29· 200813845 :執仃。以此方式’電腦系統30。可以獲得 "的 應用程式碼。 蚁仔一載波形式的 在前述說明書中，已泉 多特定細節來說明太^ 7因不同貫施方案而變化的諸 明#何彳 "月之具體實施例。因此，關於本發 /3 1系何内容以及申 指亍μ # + σ子本I明作何預期之唯一而排他的 子曰不付係由此申缚查 項之特定^ D…之tf求項集合’其採取此類請求

此發佈形式，包括任何隨後所作的校正。本文針對 此類味求項中所包含的 n t p 幻竹D°而明確提出的任何定義應支配 申：，圍中所使用的此類術語之意義。因此凡請求 比虛明確表述的限制、元件、特性、特徵、優點或屬性 日白^以任何方式限制此類請求項之範嘴。因此應將本說 曰及圖式視為解說而非限制意義。 【圖式簡單說明】 ϋ 附圖之各圖式中藉由範例方式而非限制方式來解說本發 -中相似的茶考數字代表相似的元件，而其中： 圖1A係依據本發明之一具體實施例具有基於資源之排程 工作列表的一基於資源之排程器之一圖式。 圖1B係依據本發明之另一具體實施例一基於資源之排程 器之一圖式。 圖2係依據本發明之一^且辦音# y 1 , ^ ^ /、篮貫施例之基於資源之排程之 一流程圖。 圖3係解说一可針對性地實施本發明之一具體實施例的 電腦系統之一方塊圖。 【主要元件符號說明】 121652.doc -30- 200813845 100 基於資源之排程器（RBS) 105 資源利用率資訊 108 可執行碼 112 排程邏輯 116 歷史利用率資訊 118 利用率標準 120 基於資源之排程工作列表 120(1) CPU資源工作列表 120(2) 碟y ί/’ο工作歹丨j表 120(3) 網路I/O工作列表 120(n) 其他資源工作列表 182 網路資源 184 網路 300 電腦系統 302 匯流排 304 處理器 306 主記憶體 308 唯讀記憶體（ROM) 310 儲存裝置 312 顯示器 314 輸入裝置 316 游標控制器 318 網路通信介面 320 網路鏈路 121652.doc -31 - 200813845 322 區 域 網 路 324 主 機 電 腦 326 網 際 網 路服務提供者（ISP) 328 網 際 網 路 330 祠 服 器

U 121652.doc -32-

Claims (1)

1. 200813845 十、申請專利範圍： 1. -種由機器實施之方法’其包含以下步驟： 特定資源之利用率及關於該特定資 作相關之-利㈣ς特 電腦工作排程為利用該特定資源。 X將该特定 2·如請求項i之方法，其進一步包含： η (j 決定該電腦工作對該特定資源之預期利用率 利用率標準係基於該預期利用率。 ” ^ 3 ·如请求項2之方法，其φ詖冰〜 ”…m —員，月利用率之步驟白各 核查该電腦工作中的指令。 ^。 4 ·如請求項2之方法， 含： 八中s玄決定預期利用率之步驟包 存取描述該電腦卫作對該特定資源㈣前利 值；以及 干心 讓為預期利用率係基於描述先前制率之該所 值。 巧丨丁 长員1之方法’其進一步包含從一擁有該電腦工作 之應用程式接收該利用率標準。 月求項1之方法’其進一步包含將該電腦工作放在複 數個基於資源之排程工作列表之至少一工作列表上。 7·如請求項！之方法，其進一步包含： 、'十對欲排私用於執行的複數個電腦工作中的每一工 作將5亥電腦工作放在對應於複數個電腦資源的複數個 ;資源之排私工作列表之至少一工作列表上，而其中 J21652.doc 200813845 一給定的基於資源之排程工作列表勺八Α 電腦資源之電腦工作。 5等待利用該給定 8. 如請求項7之方法，其進一步包含·· 選擇欲供該複數個電腦工作之一工 電腦資源。 利用之一特定的 9. :請求項1之方法，其中決定是否欲將，牲 排程為利用該特定資源係藉由―、〜特定電腦工作 ㈣請求項1之方法’其中決定是否欲將:來t行。 排程為利用該特定資源係藉由在誓：特定電腦工作 於資源之排程器來執行。 ：：系統外部之一基 U.如請求項1之方法’其進一步包含卜 利用率。 ’、疋该特定資源之該 12. 如請求項1之方法，其進-步包含估，在 特定資源之計劃利用率。 叶在—間隔期間該 13. 如請求項12之方法，其中決 Ο 排程Λ剎田兮44 、疋欲將該特定電腦工作 為㈣特定資源係基於 之該計劃利用率及該利用率標準。^繼特… 14. 如請求項！之方法，Α中決 排程為利用該 、疋否欲將該特定電腦工作 利用车= ”係進—步基於另—資源之 利用率及關於該另一資湄而命兮从 利用率標準。 ^特定電腦工作相關之- 15·如請求項丨之方法，i ^ 4i ^ 八Μ特疋貝源之該利用率係基於 。亥特疋賁源之一利用時間數量。 16·如請求項i之方法，苴次 /、中Μ特疋貝源之該利用率係基於 121652.doc 200813845 欲使用該特定資源的請求之一數目。 1 7 · —種由機器貫施之方法，其包含以下步驟： 將複數個電腦工作中的每-工作放在對應於複數個電 腦資源的複數個基於資源之排程工作列表之至少一工作 列表上，其中_給定的基於資源之排程卫作列表包含電 腦工作，該等電腦工作中的每—工 1户白具有一關於該給 定資源之利用率標準； 選擇欲供該複數個電腦工作之—工作利用之 電腦資源；以及 疋的 基於該特定電腦資源之利用率 之兮工心主[ 千及針對该特义電腦資源 之该#列表上的該等電腦工作中 4丨丨田、玄> 4®、社 / 电細工作之該 利用率軚準，選擇該等電腦工作之一 電腦資源。 #來利用該特定 18. 如請求項17之方法，其進一 複數個電腦資源之每—資源。3將-優先權指派給該 19. 如請求項18之方法，其中選擇_特定電腦 數個電腦工作之一工作4jJ …、奴忒複 個電腦資源之# ,Γ 步驟係基於指派給該複數 电細貝源之母一貪源之該優先權。 20·如請求項18之方法，盆 腦資源係基於該複數個電腦資^之^^給該複數個電 21·如請求項17之方法，其 人 ^ Τ 擇该專電腦工作之一τ Α十 利用該特定電腦資源之步驟係 作來 腦資源之該工作列表上的4於針對該特定電 -優先權。電腦工作中至少-工作之 121652.doc 200813845 22. 項17之方法，其中選擇該等電腦卫作之-工作在 Μ Β隔期間利用該特定電腦資源包含： 識別針對該特定資湄 貝硃之忒工作列表上的該等電 之一工作；以及 作 若ϋ亥特疋資源之所估計利用率— 腦工作的該㈣率標準之二滿足·特定電 旱之了用谷量’則將該特定電腦工 作排％以供使用該特定資源來執行。 Ο u 23. 如請求項17之方法’其進一步包含： 2定—第―電腦卫作對該特定-貞源之預期利用率，乂 用率。 作之忒利用竿標準係基於該預期利 24·如請求項23之方法，i中 於志—μ 疋預期利用率之步驟包含 双一忒第一電腦工作中的指令。 25.:請求項23之方法，其中該決定預期利用率之步驟包 之存：描述該第一電腦工作對該特定資源的先前利用率 之一值：以及 讓該預期利用率基於描述先前利 請求項一，其"包;:革=所儲存值。 工柞夕& /匕3攸一擁有該第一電腦 作之應用程式接收該利用率標準。 27.如請求们7之方法，其中選擇該等電腦卫 利用該特定電腦資源係藉由—作業系統來財—作來 I:;請求項17之方法’其中選擇該等電腦工作7之一工作來 利用該特定電腦資源之步驟係藉由在—作業系統外部之 121652.doc 200813845 一基於資源之排程器來執行。 29.如請求項17之方法，其 利用率。 ^ 乂匕含決定該特定資源之該 3〇·如請求項17之方法，其 排程為利用該特定資持之：：否欲將該特定電腦工作 利用率及關於該另-資 V基於另1源之 利用率標準。 原而與遠特定電腦工作相關之一 Ο Ο 31. -種承載一或多個指令序列 令在藉由-或乡個w自可碩取媒體，該等指 7 M电幻匈處理器杳站，一 士， ^ 腦處理器實施以下步驟： 仃吋足1 一或多個電 基於一特定資源之利 ^ ^ 定電腦工作相關之—利用率=於5 源而與一特 電腦工作排程為利用該特定:=。’決定是否欲將該特定 32. 如請求項31之電腦可讀取 、體，其中该決定是否说兮 特定電腦工作排程為利 κ h人將该 ^ 用s玄特疋-貝源之步驟係進一步A 於另一貧源之利用率 乂 土 ， 關於遠另-資源而與該特定電腦 工作相關之一利用率標準。 3 3 · —種系統，其包含： 一或多個電腦處理器，以及； 一電腦可讀取媒體，苴 ”你Μ通#方式耦合至該一或該 等多個電腦處理器，1中 ' 、 /、中该電腦可讀取媒體在其上面儲 存有一或多個所儲存的扣 吞的心令序列，該等指令在藉由該一 或該等多個電腦處理哭水 里裔末執行時促使該一或該等多個電 腦處理器執行以下操作： 121652.doc 200813845 /於—特定資源之利用率及關於該以資源而斑一特 疋電腦工作相關之一利用率 電腦工作排程為利用該特定…欲將該以 月求M 33之系統’其中該決定是否欲將該特定電腦工 作排程為利用該特定資源之步驟係進—步基於另一資源 之利用率及關於該另-資源而與該特定電腦 一利用率標準。 4關您 Ο u % —種由機器實施之方法，其包含以下步驟： 一從，數個電腦工作接收請求，其中每―睛求需要利用 特疋為源來滿足該請求；以及 基於該特定資源之利用率及該等電腦工作之每一工作 所具有的關於該特定資源之利用率標準，決定供 腦工作利用該特定資源之一排程順序。 36. 如請求項35之方法’其中該等請求之至少—部分需要利 用另-資源來滿足該請求；而其中決定供該等電 利用該特定資源之-排程順序之步驟係進_步基於與該 部分請求相關的該等電腦工作所具有的關於該另一= 之利用率標準。 Ά你 37. 如請求項35之方法，其中該特定f源之朗㈣係基於 该特定資源之一利用時間數量。 、 38. 如請求項35之方法，其中該特定資源之該利用率係 需要利用該特定資源來滿足該請求之該等請求之數目土。' ^求項35之方法’其中決定供該等電腦卫作利用該特 疋貢源之一排程順序係藉由—作業系統來執行。 121652.doc 200813845 4〇·如請求項35之方法，1 該特定資源之μ/ 等電腦工作利用 美二二:順序係藉由在-作業系統外部之- 基於貝源之排程器來執行。 < 41·種由機器實施之方法，i包人 /、巴含以下步驟： 從複數個電腦工作接收 ^ 泉，其中母一請求需要利用 複數個資源中的一或多 月“利用 、 一飞夕個貝源來滿足該請求， 選擇一特定資源以供_電 电月包工作經排程後利用；以及 Ο 基於s亥特定資源之利用、玄， 引用率及需要利用該特定資源的該 等電腦工作之每一電聪工 1F Γλ「具有的關於該特定資源之 利用率才示準’決定針對需要 要矛j用该特定資源的該等電腦 工作之一排程順序。 121652.doc