靜態(tài)負載分配

靜態(tài)負載分配《分布式系統(tǒng)》(九20112負載分配分布式系統(tǒng)的資源管理模塊，主要實現(xiàn)合理和透明地在處理器之間重新分配系統(tǒng)負載，以達到系統(tǒng)的綜合性能最優(yōu)。（最小的總體系統(tǒng)執(zhí)行時間最大的總體系統(tǒng)輸出）大致分為靜態(tài)負載分配和動態(tài)負載分配2大類情況。靜態(tài)負載分配：進程運行前進行處理器分配，運行中不作調整，直到運行結束；（確定性分配）動態(tài)負載分配：進程運行中動態(tài)進行處理器分配，且可以不斷調整；（負載均衡）第2頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20113負載分配分類進程和處理器在負載分配時是M:N（多對多）的關系。有多種負載分配算法分類：負載分配局部全局靜態(tài)動態(tài)分散式控制集中式控制協(xié)作非協(xié)作最優(yōu)次優(yōu)近似啟發(fā)式單個處理器上多個進程對時間片的分配。先完成全局進程對處理器的分配，再在處理器內進行局部分配。進程執(zhí)行以前的編譯階段完成進程對處理器的分配。進程在系統(tǒng)中執(zhí)行時才作分配。得到一個最優(yōu)的結果。得到一個次優(yōu)的結果。搜索一個解空間的子集，尋找到一個較好的解。使用某些特殊參數(shù)，近似地對真實系統(tǒng)建模。決策工作被分配給不同的處理器。決策工作由一個處理器完成。不同處理器間有協(xié)同操作。各處理器獨立做出決策。第3頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20114負載分配分類其它的負載分配算法分類：單個和多個應用程序搶占式的和非搶占式的自適應的和非自適應的第4頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20115靜態(tài)負載分配根據先驗知識在執(zhí)行前調度一個任務（進程）集合，使它們總體上在各個目標PE上有最小的執(zhí)行時間（代價）。靜態(tài)負載分配問題也稱為任務調度問題，它涉及到3方面的要素：處理器互連、任務劃分和任務分配。負載分配有時即使加入執(zhí)行開銷和通信開銷等假設仍然是一個NP完全問題，很難求得一個明確的最優(yōu)解，我們總是用各種方法試圖求得一個次優(yōu)的解，或者加入一些特殊的約束以求得最優(yōu)解。第5頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20116任務（進程）的圖模型表示－任務優(yōu)先圖任務優(yōu)先圖G是一個有向無環(huán)圖（DAG）xy任務優(yōu)先順序x：任務在處理器上的執(zhí)行代價y：在不同處理器上啟動后續(xù)任務所需的時間（處理器間通信代價）第6頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20117任務的圖模型表示－任務相互關系圖2個處理器的情況x,yz,z’任務通信x,y：任務在不同的處理器上的執(zhí)行代價z,z’：在不同處理器上和在相同處理器上的任務間通信代價（通常z’可忽略）第7頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20118處理器互連a)Illiac網格方案（16個PE的系統(tǒng)）

2維節(jié)點度數(shù)：4

網絡直徑：n-1（n元）（常規(guī)2維網格的一半）第8頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九20119處理器互連b)圓環(huán)方案（16個PE的系統(tǒng)）

2維節(jié)點度數(shù)：4

網絡直徑：2n/2第9頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201110處理器互連c)超立方體方案（16個PE的系統(tǒng)）節(jié)點度數(shù)：n

網絡直徑：nn維，每維2個節(jié)點

n維立方體是2個n-1維立方體互連而成。第10頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201111處理器互連d)WK網絡方案（16個PE的系統(tǒng)）1層WK網絡2層WK網絡節(jié)點度數(shù)：4

網絡直徑：

n-1n層的WK網絡由4個(n-1)層的WK子網絡組成，每個子網絡是一個虛擬節(jié)點。第11頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201112任務劃分將一個大的任務（應用程序）分解成一些小的子任務類，每個子任務類作為分配給同一個PE執(zhí)行。也稱任務聚類。根據子任務類中基本任務單元（粒度）的大小，任務劃分算法可分成：細粒度、中粒度、和粗粒度。粒度太大，會降低并行度；粒度太小，子任務進程的切換和它們間的通信代價會增加。任務劃分的主要目標是盡可能地增加并行度和降低通信代價（尋找一個適中的粒度）。第12頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201113任務劃分大體上有三種方法的任務劃分：水平或垂直劃分：根據任務優(yōu)先圖的關鍵路徑（最長路徑）垂直進行或任務分層水平進行；通信延遲最小劃分：將通信頻繁的基本任務節(jié)點歸成一類，讓其在同一個PE上執(zhí)行，以最大限度地降低通信代價。此方法需要顧及并行任務串行化所帶來的損失。任務復制：通過在PE上復制任務來降低通信代價，同時保留任務的并行性。此方法會增加PE的儲存空間開銷和PE間同步的開銷。通常任務劃分的子任務類數(shù)目等于PE的個數(shù)，以簡化后續(xù)的任務分配。第13頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201114任務劃分－線性和非線性任務劃分后，如果至少有一個子任務類中包含兩個獨立的任務，則劃分是非線性的；否則劃分是線性的（所有獨立的任務被劃分在不同的任務類中）。如：T1T2T3d1d2a)線性劃分T1T2T3d1d2b)非線性劃分第14頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201115任務劃分－衡量劃分任務優(yōu)先圖可以認為是許多分叉和合并操作的集合：a)分叉c1xv1l1b)合并c2v2l2cnvnln…c1v1l1c2v2l2cnvnln…x分叉x（或合并x）的粒度是：g(x)=min{ck}/max{lk} 0

kn0

kn任務優(yōu)先圖G的粒度是：g(G)=min{g(x)}

xG第15頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201116任務劃分－衡量劃分如果g(x)>1（g(G)>1），合并或分叉（或圖G）就是粗粒度的，否則操作或圖就是細粒度的。如下圖的非線性劃分是粗粒度的（g(x)=2）。432T1T2T311第16頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201117任務劃分－衡量劃分可以證明，如果任務優(yōu)先圖G是粗粒度的，則其任何非線性的子任務類都可以轉換（再劃分）成具有更少或相等執(zhí)行時間的線性分類。即：粗粒度的任務優(yōu)先圖其線性劃分性能優(yōu)于任何非線性劃分。然而，如果任務優(yōu)先圖G是細粒度的，可能存在，也可能不存在一個非線性劃分優(yōu)于線性劃分。第17頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201118任務劃分－衡量劃分例：432T1T2T311a)線性劃分432T1T2T311b)非線性劃分b)是粗粒度的，其非線性劃分b)的執(zhí)行時間是9，線性劃分a)的執(zhí)行時間是7；若將通信代價1變?yōu)?，則b)是細粒度的，其非線性劃分b)的執(zhí)行時間是9，線性劃分a)的執(zhí)行時間是10。4444第18頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201119任務分配將任務劃分后的子任務類分配給PE的過程。在n個子任務類和n個PE間作映射分配，共有Cnn=n!種分配方法，根據PE的存儲容量、處理能力和PE間的通信距離各映射分配方法會產生較大差異的效果。為了減少任務分配的復雜性，可以作一些假設：PE的存儲容量無限每個PE有相同的處理能力忽略通信距離所造成的網絡擁塞等。第19頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201120任務調度（靜態(tài)負載分配）方法基于任務優(yōu)先圖的任務調度算法（算法1）任務優(yōu)先圖是一棵樹（算法2）只有兩個處理器基于任務相互關系圖的任務調度任務調度評測使用其它模型和技術的任務調度Stone網絡流量技術實現(xiàn)最優(yōu)任務調度算法實時定期任務調度速率單調優(yōu)先調度期限驅動調度第20頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201121基于任務優(yōu)先圖的任務調度對任務優(yōu)先圖，可以用G=(V，A)來描述，其中V是節(jié)點的集合，表示任務集；A是弧線的集合，表示任務間的優(yōu)先關系。如：u、v是V中的節(jié)點（任務），(u,v)是A中的弧線鏈接。對于每個節(jié)點（任務）和鏈接都定義了代價函數(shù)w，其中w(u)(0,)表示任務u在處理器上執(zhí)行的時間代價（所有處理器是相同的），w(u,v)=(l,l’)是鏈接的代價，其中l(wèi)’是在同一處理器內的通信時間代價，l是處理器間的通信時間代價（u和v分配在不同處理器）。w(u)w(u,v)uv第21頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201122基于任務優(yōu)先圖的任務調度幾點約束：處理器的處理能力是相同的。不考慮處理器互連，即忽略網絡擁塞，也即處理器間的通信代價對所有處理器是一樣的。相對l，l’是非常小的，可以忽略，因此w(u,v)=l。w(u)w(u,v)uv第22頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201123基于任務優(yōu)先圖的任務調度甘特圖（GanttChart）任務分配表示：橫坐標是處理器，縱坐標是時間，方塊是任務的開始、持續(xù)和結束時間。T1T2T3T4T5時間0第23頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201124基于任務優(yōu)先圖的任務調度任務優(yōu)先圖的甘特圖（GanttChart）任務分配表示例：T1T3時間1221T11424T2T3T4T51122T2T5T412a)任務優(yōu)先圖b)2個處理器的甘特圖第24頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201125基于任務優(yōu)先圖的任務調度 在不同處理器上分配任務時，通信的開銷對任務調度有較大影響，如：T1T2T3ddT1da)任務優(yōu)先圖b)調度結果1T2T3T1T2T3c)調度結果2T1T1T2T3d)調度結果3第25頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201126基于任務優(yōu)先圖的任務調度只有當通信代價較小時，將任務分配到不同的處理器是比較合適的（圖c）；任務調度總是盡量將任務分配到不同的處理器以增加并行度，同時盡量降低通信的開銷，然而二者有時是無法滿足的矛盾，需要某種程度的折中；有時采用任務復制的方法實現(xiàn)可以得到一個很好的效果（圖d）。第26頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201127基于任務優(yōu)先圖的兩個最優(yōu)調度算法為了實現(xiàn)最優(yōu)，兩個算法各自有約束條件：（算法1）任務優(yōu)先圖是一棵樹。（算法2）只有兩個處理器。 而且兩個算法都假設通信代價可以忽略和優(yōu)先圖中每個任務節(jié)點的執(zhí)行時間是一樣的。兩個算法都是最高級優(yōu)先方法，即根據任務節(jié)點的等級來選擇分配節(jié)點。第27頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201128最優(yōu)調度算法1具體算法：任務節(jié)點的等級等于它到根節(jié)點的距離加1，等級越高，優(yōu)先級就越高；相同等級的節(jié)點中，所有先導節(jié)點都已執(zhí)行的節(jié)點先被選中；若有多個節(jié)點符合條件2，則隨機選擇。T1T2T3T4T5T6T7T8T9T10T11T12T13第28頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201129最優(yōu)調度算法1在3個處理器上實現(xiàn)的例：T1T2T3T4T5T6T7T8T9T10T11T12T13T1T4T6T8T11T13T2T5T9T12T3T7T10時間0a)任務優(yōu)先圖b)算法實現(xiàn)的甘特圖第29頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201130最優(yōu)調度算法1使用一個就緒隊列實現(xiàn)算法：就緒隊列按優(yōu)先級排列那些可以被選擇分配給處理器的任務節(jié)點。T1T2T3T4T5T6T7T8T9T10T11T12T13就緒隊列狀態(tài)：(T1,T2,T3,T4,T5,T7,T9,T10,T12)

(T4,T5,T7,T9,T10,T12)

(T6,T9,T10,T12)

(T8,T12)

(T11)

(T13)等級54321第30頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201131最優(yōu)調度算法2具體算法：將k個終止節(jié)點依次標記為1~k（標記越大，優(yōu)先級越高）；尋找所有后續(xù)節(jié)點均被標記的節(jié)點；根據這些節(jié)點的后續(xù)節(jié)點排列的字典升序依次標記這些節(jié)點；重復2、3直到所有節(jié)點標記完畢；根據優(yōu)先級的高低順序依次將任務分配給2個處理器。11T9910T107T116T6T78T84T45T521T1T23T3第31頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201132最優(yōu)調度算法2例的標記結果：T1,T2,T3,T4,T5,T6,T11,T8,T7,

T10,T9

11T9910T107T116T6T78T84T45T521T1T23T3T9T7T11T5T3T1T10T8T6T4T2a)任務優(yōu)先圖b)算法實現(xiàn)的甘特圖(2個處理器)時間0第32頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201133最優(yōu)調度算法2本算法有問題的！思考為什么需要是2個處理器的限制？還需要加入什么限制，算法才沒有問題？提示比如：任務優(yōu)先圖中，去掉T10，算法會出現(xiàn)錯誤。第33頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201134基于任務相互關系圖的任務調度假設任務關系圖由無向圖Gt=(Vt，Et)表示，其中Vt是任務節(jié)點集合，Et是邊集合。處理器關系圖由無向圖Gp=(Vp，Ep)表示，其中Vp是處理器集合，Ep是邊集合（處理器間的通信通道）。一般來說，如果任務劃分已經完成，則|Vt|

|Vp|，我們進行映射分配M：Vt

Vp及執(zhí)行時間估計： 設w(u)和w(u,v)分別是節(jié)點u和連接(u,v)的代價。 處理器p

Vp的計算負載：Comp(p)=w(u)|M(u)=p uVt

通信負載：Commp(p)=w(u,v)|M(u)=pM(v) (u,v)Et第34頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201135基于任務相互關系圖的任務調度一個應用程序總的計算和通信負載：Comp=

Comp(p)=

w(u)|M(u)=p pVp pVpuVtComm=1/2

Comm(p)=1/2

w(u,v)|M(u)=pM(v) pVp pVp(u,v)Et總的程序執(zhí)行時間估計：T＝max{Comp(p)+Comm(p)},pVp

是依據每個PE的執(zhí)行速度設定的調節(jié)比例；是依據每個通信信道的通信速度和通信進程間的距離設定的調節(jié)比例。第35頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201136基于任務相互關系圖的任務調度理想情況下，任務關系圖中相鄰的節(jié)點應被分配在相鄰的處理器上，以減少處理器間長距離的通信。因此，評估映射質量的一個指標是任務關系圖Gt的邊映射到處理器圖Gp的邊的數(shù)目，這個數(shù)目稱為映射的勢，映射的勢

Gt的邊數(shù)，映射的勢越大則越理想。第36頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201137基于任務相互關系圖的任務調度下例中，映射的勢是8（共13條邊）映射的勢并不能完全反映出映射的質量，這主要表現(xiàn)在勢以外的邊所對應的處理器的距離。（圖中虛線的距離）134562789123456798第37頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201138基于任務相互關系圖的任務調度P203使用嵌入技巧來衡量利用任務相互關系圖分配任務到處理器關系圖時的理想程度。其目標：發(fā)現(xiàn)一個嵌入，有最小膨脹、最大擴大和最小擁塞。即上圖中，虛線的數(shù)目最少，且最短；任務節(jié)點到處理器節(jié)點的數(shù)目最多；經過一個處理器邊（通信鏈路）的任務邊數(shù)最小。*書中錯誤：（P203,第8行）嵌入的負載，是Gt分配給Gp中任意……第38頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201139網絡流量技術實現(xiàn)最優(yōu)任務調度Stone網絡流量算法：一個在雙處理器且處理器有不同處理能力的系統(tǒng)中對任務相互關系圖的最優(yōu)調度算法。圖的分割、帶權分割：tsd分割為圖中邊的子集：1)刪除這些邊后使圖不連通；2)這些邊的任何子集都不滿足上一點。帶權圖的分割為帶權分割。分割后的2部分中各包含s和t的分割，稱為s-t分割或s-t帶權分割。第39頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201140網絡流量技術實現(xiàn)最優(yōu)任務調度網絡的分割、帶權分割：邊的流量不能超過邊的容量，網絡的流量不能超過分割的容量；除起始節(jié)點和終止節(jié)點，節(jié)點的流入流量等于節(jié)點的流出流量；起始節(jié)點只有流出，終止節(jié)點只有流入。ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第40頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201141網絡流量技術實現(xiàn)最優(yōu)任務調度Ford-Fulkerson最大流-最小割理論：最小的帶權分割就是最大的網絡流量。（根據容量圖）ts1,17,51,15,55,43,36,32,22,22,26,49,66,1第41頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201142網絡流量技術實現(xiàn)最優(yōu)任務調度確定了最大的網絡流量就確定了最小的帶權分割。確定網絡最大流量的算法：使網絡流量最大化的進程方法。從任意一種流開始，尋找可能存在的增加路徑（augmentingpath），在該路徑上：對于前向鏈接，它有富余的容量；對于后向鏈接，它有反向的流量。消除這些增加路徑：對于前向鏈接，增大實際的流量；對于后向鏈接，減少反向的流量。直到網絡中沒有增加路徑為止。此時，網絡的流量最大，它的一個分割（其各鏈接邊的容量等于實際流量）就是最小帶權分割。第42頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201143網絡流量技術實現(xiàn)最優(yōu)任務調度利用網絡最大流量就是圖的最小帶權分割技術，實現(xiàn)對2個處理器的最優(yōu)任務分配。任務相互關系圖T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893在2個處理器上的執(zhí)行代價，-表示不能在該處理器上執(zhí)行。在不同處理器上的通信代價。第43頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201144網絡流量技術實現(xiàn)最優(yōu)任務調度分別將2個處理器作為s和t加入任務關系圖中，增加s和t到各任務的邊（共2n條），邊的權值為任務在該處理器上的執(zhí)行代價，形成任務分配圖。T2(4,5)T1(3,-)T4(7,4)T3(2,7)4893T2T1T44892tT3s3445-773任務相互關系圖任務分配圖第44頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201145網絡流量技術實現(xiàn)最優(yōu)任務調度利用網絡最大流量算法在網絡流量圖中尋找最大網絡流量（以s為起點、t為終點，初始實際流量設為0）。T2T1T44,08,09,02,0tT3s3,04,04,05,0-,07,07,03,0第45頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201146網絡流量技術實現(xiàn)最優(yōu)任務調度得到的最大網絡流量，就是最小網絡分割，也即任務的最優(yōu)分配。最小分割的權重（各分割邊的權之和）即任務分配后的最小代價（執(zhí)行代價和通信代價）之和。T2T1T44,08,39,02,2tT3s3,34,44,45,4-,67,27,73,0如圖的最小代價是16，分配方案是T1、T2、T3、T4均在一個處理器s上執(zhí)行。最小分割第46頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201147網絡流量技術實現(xiàn)最優(yōu)任務調度前述是一個利用網絡最大流算法得到最小分割的方法，適合在計算機環(huán)境下編程實現(xiàn)。人工計算相當麻煩?。?！一個可行的人工計算方法：（“笨”的、窮盡的方法）T1T2T44892tT3s4345-773(34)(38)(33)(16)可能的分割(分配)：T1*T1T2*T1T3T1T4T1T2T3T1T2T4*T1T3T4T1T2T3T4*比較各種分割的權重。第47頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201148實時定期任務調度實時定期任務（Ti）定期（間隔周期ti）出現(xiàn)，每次運行時間為ci，在下一次出現(xiàn)前（期限，即n*ti），前一次任務必須運行結束（實時）。處理器的整體利用率：

n

ci/ti

i=0第48頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201149實時定期任務調度實時定期任務調度2個算法（單處理器，多個獨立實時定期任務）速率單調優(yōu)先調度有高速率（間隔周期小）要求的任務有高優(yōu)先權；優(yōu)先權是固定分配的。期限驅動調度離結束期限最近的任務有高優(yōu)先權；優(yōu)先權是動態(tài)分配的。2個算法都是基于優(yōu)先權和搶占式的。第49頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201150實時定期任務調度一個實時定期任務集合是可調度的，說明任務集中所有任務的期限要求都可以滿足。在不同的實時定期任務調度算法下，一個實時定期任務集可能可調度，可能不可調度。可以證明：對期限驅動算法，一個任務集可調度的充分條件是：

n

處理器的整體利用率

ci/ti1

i=0對速率單調算法，一個任務集可調度的充分條件是：

n

處理器的整體利用率

ci/tin(21/n-1)

i=0

n為任務個數(shù)：如n=1時，限度為1；n=2時，限度為0.828，n=3時，限度為0.779。第50頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201151實時定期任務調度如：2個實時定期任務開始于同一時間

T1：c1=3,t1=5 T2：c2=3,t2=8

整體利用率是0.975，如下圖：T1T200c1c2510858調度點t1t2

對速率單調算法，系統(tǒng)是不可調度的；對期限驅動算法，系統(tǒng)是可調度的。225第51頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201152實時定期任務調度但前述條件是充分條件，而非必要條件，如

T1：c1=3,t1=5 T2：c2=2,t2=7

整體利用率是0.887，高于0.828，但對速率單調算法，系統(tǒng)仍是可調度的。如下圖：T1T200c1c2510757t1t2第52頁,共56頁，2024年2月25日，星期天《分布式系統(tǒng)》(九201153實時定期任務調度所有任務的期限點組成系統(tǒng)的調度點（但在最長的第一個期限內）。在不同的調度點，任務集可能可以調度，可能不可以調度。只要有一個調度點，任務集可以調度，則整個任務集就是可以調度的。（例）3個任務的任務集：

T1：c1=40,t1=100 T2：c2=50,t2=150