一種可重構任務處理系統、調度器及任務調度方法

2023-12-07 07:23:21 1

專利名稱：一種可重構任務處理系統、調度器及任務調度方法
技術領域：
本發明涉及計算機通信技術領域，特別涉及一種可重構任務處理系統、調度器及任務調度方法。

背景技術：
在嵌入式技術中，計算任務可以通過硬體來實現，也可以利用微處理器通過軟體來實現。硬體實現快速、高效，但是一旦設計完成後，系統將難以更改。軟體實現靈活，但是性能卻不高。隨著硬體技術的不斷進步，可重構技術成為當前的研究熱點之一，而動態可重構技術由於其具有可編程性，即提供了大量的可編程邏輯單元，並同時具備部分可重構功能，因此填補了傳統軟體設計和硬體設計之間的鴻溝，兼顧了軟體的靈活和硬體的性能優勢，並成功應用到了神經網絡、圖像信息處理、路由交換等多個領域。
現有典型的可重構任務處理系統，如圖1所示，包括調度器11、布局器12和資源管理器13和可重構器件14，所述調度器11、布局器12和資源管理器13集成在CPU15中，其中，調度器11隻負責任務的接收和維護已調度成功的任務；布局器12是系統的核心，負責對所述調度器11接收到的任務進行布局處理，並更新資源管理器13的狀態。在上述調度處理過程中，所述調度器11的功能十分簡單，而布局器12本身功能相對複雜。在以布局器12為核心的調度處理過程中，調度器11對任務的調度過程只能支持簡單的先到先服務(FirstCome First Serviced，FCFS)調度模式，即根據任務的到達先後順序，依次對任務進行資源預約調度過程。對於正在運行的任務和預約的任務，由於該系統不支持對任務的搶佔調度過程，其調度結果不可被後續任務搶佔，因而任務的調度順序與任務的到達順序相一致。
在對任務的實時調度過程中，由於事先無法確知前後任務之間的相關性，對於後到達但時間緊迫的任務，該FCFS調度處理模式無法使得該類任務優先處理，因而現有任務調度系統無法提供區分服務的調度模式；對於後到達但優先級較高的任務，現有的調度系統同樣不能提供高優先級任務優先調度。
從上述實現過程可以看出，現有調度系統存在的問題是，系統模塊功能劃分不合理，所支持的FCFS調度服務模式合理性較差，由於前後任務的調度過程相互獨立，不利於任務之間通過協作進行資源利用優化。由於任務的調度順序取決於該任務的到達次序，先到達任務將優先佔用資源，不利於反映任務自身的服務屬性，無法滿足支持不同任務調度需求的多樣性，無法根據任務的不同需求提供差異化服務，降低了任務調度效率。


發明內容
本發明實施例提供一種可重構任務處理系統、調度器及任務調度方法，為不同需求的任務提供差異化服務，提高預約任務的調度效率。
為解決上述技術問題，本發明實施例提供一種可重構任務處理系統，包括調度器、布局器和資源管理器，其中， 所述調度器，用於提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL，並將所述PPTL發送給所述布局器，以及，根據接收到的所述布局器反饋的布局結果對等待調度隊列中的任務進行調度，根據調度結果向所述資源管理器發送資源狀態更新信息； 所述布局器，用於在接收到所述PPTL後，根據所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到該任務的啟動時間及對應的資源，並向所述調度器反饋布局結果； 所述資源管理器，用於在接收到所述調度器發送的資源狀態更新信息時，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間。
相應的，本發明還提供一種調度器，包括 計算單元，用於提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度； 生成單元，用於利用活動事件隊列AEQ提取出在所述任務鬆弛度內的活動時刻，生成PPTL，並將所述任務的寬度、高度及PPTL發送給所述布局器； 調度單元，用於接收所述布局器反饋的布局結果，並根據所述布局結果對等待調度隊列中的任務進行調度，如果調度失敗，則刪除對應的業務，如過調度成功，則存儲該任務； 調度結果維護單元，用於對所述調度單元調度成功的任務，在運行任務ETQ隊列和預約任務PTQ隊列中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ隊列進行更新；並根據調度結果向所述資源管理器發送資源狀態更新信息。
相應的，本發明孩提一種可重構任務調度方法，包括 調度器提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL，並向布局器發送所述PPTL； 調度器接收布局器發送的根據所述PPTL得到的所述任務的啟動時間及對應的資源； 調度器根據所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行調度，並維護調度成功的任務的啟動時刻和布局區域，控制資源管理器中資源狀態的更新。
由上述技術可知，本發明在可重構系統結構上，以調度器作為系統核心，在調度任務時，能夠以緊迫度區分服務，維護任務隊列。調度器負責更新資源管理器狀態，直接刪除以前的調度結果，將先到先服務模式，修改為搶佔調度。布局器在資源器控制下進行布局，降低了布局器的設計複雜度，使布局器能夠專門負責空閒區域搜索過程。在資源管理方式上採用資源切片鍊表的資源管理方法，用離散的切片表示資源的狀態，避免在不同時刻維護相同的資源分布矩陣，從而有效降低了系統的存儲空間。由於PPTL表中的活動時刻對應於資源切片的起始時刻，使得布局過程只在該數據結構的存活時間的起始時刻進行布局，從而實現離散預約調度過程，避免了重複預約操作，提高了預約調度效率。



圖1為現有技術中可重構任務處理系統的結構示意圖； 圖2為本發明提供的一種可重構任務處理系統的結構示意圖； 圖3為本發明提供的在ETQ中的控制塊內容及其排序的示意圖； 圖4為本發明提供的在PTQ中的控制塊內容及其排序的示意圖； 圖5為本發明提供的控制塊在ETQ和PTQ中的狀態轉換的示意圖； 圖6為本發明提供的控制塊按發生時刻先後排序的AEQ的示意圖 圖7為本發明提供的資源切片中的CLB資源狀態示意圖 圖8為本發明提供的在不同時刻但資源分布相同的兩個資源切片的示意圖； 圖9為本發明提供的資源切片鍊表形成的三維資源空間的示意圖； 圖10為本發明提供的一種可重構任務調度方法的流程圖； 圖11為本發明中提供的PPTL表的生成過程的示意圖； 圖12為本發明提供的ETQ、PTQ、AEQ和PPTL狀態轉換的示意圖； 圖13為本發明提供的一種支持緊迫度區分的搶佔調度的流程圖； 圖14為本發明提供的一種基於時域資源切片的布局過程的示意圖； 圖15為本發明提供的一種基於PPTL表的預約調度實現過程的流程圖。

具體實施例方式 下面我們將結合附圖，對本發明的實施方案進行詳細描述。
請參閱圖2，為本發明提供的一種可重構任務處理系統的結構示意圖，所述系統包括調度器21、布局器22和資源管理器23和可重構器件24，所述調度器21、布局器22和資源管理器23集成在CPU25中，其中，所述調度器21，用於提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表(PPTL，Potential Placing Time List)，並將所述PPTL發送給所述布局器22，以及，根據接收到的所述布局器反饋的布局結果對等待調度隊列中的任務進行調度，根據調度結果向所述資源管理器23發送資源狀態更新信息；所述布局器22，用於在接收到所述PPTL後，根據所述PPTL中的各個時刻對所述資源管理器23提供的資源進行布局搜索，得到該任務的啟動時間及對應的資源，並向所述調度器22反饋布局結果；所述資源管理器23，用於在接收到所述調度器發送的資源狀態更新信息時，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間。
可選的，所述調度器具體包括計算單元、生成單元和調度結果維護單元，其中，所述計算單元，用於提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度；所述生成單元，用於利用活動事件隊列(AEQ，Activity EventQueue)提取出在所述任務鬆弛度內的活動時刻，生成PPTL，並將所述任務的寬度、高度及PPTL發送給所述布局器；所述調度結果維護單元，用於接收所述布局器反饋的布局結果，並根據所述布局結果對等待調度隊列中的任務進行刪除或存儲；對於調度成功的任務，在運行任務隊列(ETQ，Executing TaskQueue)和預約任務隊列(PTQ，Planning Task Queue)中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ進行更新；並根據調度結果向所述資源管理器發送資源狀態更新信息。
其中，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息的過程具體包括當任務布局成功時，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息，控制所述資源管理器將任務布局區域的所有資源的狀態標註為非空閒狀態，防止該區域被後續任務佔用；在刪除任務時，控制所述資源管理器將被刪除任務布局區域內的資源狀態更新為空閒，使後續任務可預約該區域內資源。
可選的，所述調度器還可以包括活動事件隊列AEQ，用於存儲任務時間發生時刻以及在該時刻發生的事件個數，所述任務發生時刻是指任務運行啟動和運行結束事件的發生時刻，在AEQ中的活動事件按照發生時刻順序存儲在AEQ中，對於在同時刻發生的多個事件只需一個控制塊進行維護。
可選的，所述布局器可以包括布局搜索單元和布局搜索結果反饋單元，所述布局搜索單元，用於在接收到所述任務的寬度、高度和PPTL後，利用空閒矩陣資源匹配的搜索方式，對所述PPTL中的離散分布時刻依次進行布局，並對所述資源管理器提供的三維搜索空間進行空閒區域搜索，得到該任務的啟動時間及對應的資源，其中，所述三維搜索為三維資源長方體，所述三維資源長方體是指二維資源面積和時間維組成的具有時空特性的三維抽象資源模型；所述布局搜索結果反饋單元，用於向所述調度器反饋該任務的啟動時間及對應的資源。
其中，所述布局搜索單元對所述資源管理器提供的三維搜索空間進行空閒區域搜索的過程具體包括所述布局搜索單元在所述資源管理器提供的三維搜索空間的各個時刻的資源切片中可容納該任務的連續空閒區域，當空閒區域搜索成功後，將該空閒區域垂直掃描，以使該空閒區域在後續時間內仍保持空閒狀態，且該空閒區域能被任務連續佔用e時間，其中e為任務的運行時間。
可選的，所述資源管理器具體用於，採用資源切片鍊表的資源管理方式，在接收到所述調度器發送的資源狀態更新信息時，利用資源切片對應的二維矩陣中的權值來更新任務布局區域內的資源的使用狀態，並將資源切片按時間先後順序依次排列，維護不同時刻的資源使用狀態，為所述布局器匹配資源提供三維的搜索空間。
在該實施例中，系統在接收到任務後，通常將任務抽象為矩形，由時空屬性參數(w，h，a，e，d)分別表示任務矩形的寬度、高度，任務的到達時刻、執行時間、截止時刻；在調度器接收到任務時，保存該業務，提取該任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的PPTL表，利用PPTL表控制布局器直只在該表中的時刻進行布局，當任務布局失敗時，調度器丟棄該任務；當布局成功時，調度器根據布局器返回的布局結果，控制資源管理器進行資源態的更新。
同時，調度器還需要維護各任務的狀態，具體包括運行任務隊列ETQ、預約任務隊列PTQ和活動事件隊列AEQ，其中，所述ETQ用於維護當前所有正在運行任務的控制塊，運行任務的控制塊表示為 (i，v(t，fi)，p(xi1，yi1，xi2，yi2)，r(wi，hi，ai，ei，di)) 其中，i表示該運行任務的編號，t表示當前時刻，fi為任務的運行結束時刻，p(xi1，yi1，xi2，yi2)表示任務Ti當前正在器件中的運行區域，且滿足fi≥t和di≥fi，在ETQ中，任務控制塊按任務的結束時刻升序排列，具體如圖3所示，為本發明提供的在ETQ中的控制塊內容及其排序的示意圖。
所述PTQ用來保存已預約調度成功但未啟動運行的已預約任務控制塊表示為(i，v(sj，fj)，p(xj1，yj1，xj2，yj2)，r(wj，hj，aj，ej，dj))，其中i表示該預約任務的編號，sj為調度後得到的預約啟動時刻，fj為任務的運行結束時刻，p(xj1，yj1，xj2，yj2)表示任務Tj將在[sj，fj-1]時間內所佔用的資源區域，基於在PTQ中維護的預約調度結果，保證p(xj1，yj1，xj2，yj2)區域內的資源在[sj，fj-1]時間內不被其它任務佔用，PTQ中的任務控制塊按任務的預約啟動時刻sj升序排列，如圖4所示，為本發明提供的在PTQ隊列中的控制塊內容及其排序的示意圖，在該圖中，空白方格表示新任務，左斜方格表示運行任務控制塊，右斜方格表示預約任務控制塊。
當系統時間到某任務的預約啟動時刻時，該任務的控制塊將從PTQ轉移到ETQ中，表示該任務從預約狀態變為運行狀態，如圖5所示，為本發明提供的控制塊在ETQ和PTQ中的狀態轉換的示意圖；AEQ主要用來存儲活動事件發生時刻的列表，所述活動事件是指任務的啟動和結束事件，任務活動事件按照事件發生的先後順序存儲在AEQ中，其控制塊中包括事件發生時刻ti和事件發生個數n(ti)，如圖6所示，為本發明提供的控制塊按發生時刻先後排序的AEQ的示意圖。
在該實施例中，布局器，利用調度器發送的任務長度、寬度和PPTL表，在資源管理中進行布局搜索，即按照PPTL表中的各個時刻依次進行布局搜索，也就是說，在各時刻的布局搜索過程中，當在第一時刻布局成功時，表示該任務直接基本調度(BS Basic Scheduling)調度成功；當在後續時刻任務布局成功時，表示該任務預約成功；若任務在所有時刻都布局失敗，表示該任務調度失敗。當任務布局完成以後，布局器將布局結果發送各調度器，對布局成功任務，其布局結果包括運行啟動時刻和布局區域，若任務布局失敗，布局器向調度器發送布局失敗消息，調度器丟棄該任務。
在該實施例中，布局器主要基於PPTL表進行離散預約調度過程，利用資源管理器提供的三維資源模型，在各時刻的資源切片中搜索可容納該任務的連續空閒區域，若在資源切片搜索空閒區域失敗，則在PPTL表中的下一時刻再進行空閒區域搜索；若在資源切片中搜索空閒區域成功，則將該空閒區域垂直掃描，以保證該區域在後續時間內仍保持空閒狀態，使任務可連續佔用該空閒區域e時間。若垂直掃描失敗，表示該任務所搜索的空閒區域無效，此時進行搜索下一空閒區域。
也就是說，布局器採用空閒矩陣資源匹配的搜索方法，利用PPTL表中的離散分布時刻，在各時刻依次進行布局，從而對三維資源長方體空間進行空閒區域搜索。所述的三維資源立方體是指二維資源面積和時間維組成的具有時空特性的三維抽象資源模型，即對於一個連續時間範圍內，資源狀態相同的切片用一個切片表示，表示為S([ti，ti+1-1])，其中S表示一個二維矩陣，反映了可重構資源的使用狀態；[t，ti+1-1]表示該切片的存活時間範圍，資源切片鍊表按照時間先後順序排列在鍊表上，從而形成三維的可重構資源模型，即三維抽象資源模型。利用三維資源模型不僅能表示任務所佔面積的空間屬性，還能刻畫任務運行的時間屬性。其搜索的過程為首先在資源切片中進行空白區域搜索，當空閒區域搜索成功以後，將該空白區域垂直掃描，判定該空白區域是否能被任務連續佔用e時間，其中e為任務的運行時間。
此外，布局器利用PPTL表在資源管理器中進行布局時，可以採用AEAP(As earlier as possible)原則，任務依次在該表的各時刻進行布局，當任務在某時刻布局成功時，則無需在後續時刻再進行布局，使任務在「儘早」的時間內預約調度成功。其中，布局器基於PPTL的布局過程中，由於PPTL表中的各時刻對應於資源切片的存活時間初始時刻，避免了在存活時間內的布局過程，有利於加快任務預約調度速度。
本實施例中的資源管理器，是以基於二維矩陣的資源切片邏輯數據結構管理可重構資源，資源切片對應一個二維矩陣M[x][y]，以m[x][y]表示矩陣中的基本組成元素，表示二維坐標為(x，y)的資源邏輯單元CLB資源，且x和y分別滿足1≤x≤W和1≤y≤H，其中W為器件中的CLB列數，而H為器件中的CLB列數。在二維矩陣中利用m的權值表示該CLB資源的使用狀態。由於每個CLB資源在同一時刻只能處於佔用或空閒狀態之一，在資源切片中將m的權值定義為0或1，當m[x][y]＝0時，表示坐標為(x，y)的CLB未被任務佔用，正處於空閒狀態；當m[x][y]＝1時，表示坐標為(x，y)的CLB被任務佔用，正處於佔用狀態，具體如圖7所示，為本發明提供的資源切片中的CLB資源狀態示意圖。在該圖中的T1、T2和T3為任務佔用狀態的資源切片。
在該本發明實施例中，對於一個連續時間範圍內，資源狀態相同的資源切片用一個資源切片表示，具體如圖8所示，為本發明提供的在不同時刻但資源分布相同的兩個資源切片的示意圖；所述資源切片為S(ti，ti+1-1])表示，其中，[t，ti+1-1]表示該資源切片有效的時間範圍，表示在該時間的資源分布中該資源切片中的二維矩陣。將資源切片按時間先後順序依次排列，維護在不同時刻的資源使用狀態，從而為布局器匹配資源提供三維資源搜索空間，所述三維資源搜索空間如圖9所示，為本發明提供的資源切片鍊表形成的三維資源空間的示意圖。
資源管理器根據任務的調度結果進行更新管理。當增加新任務的調度結果時，需要在資源管理器中增加新的資源切片進行維護；在搶佔調度過程中，當刪除部分任務的調度結果時，將需刪除部分資源切片，同時對資源管理器中的資源切片進行合併；當系統時間大於資源切片的存活時間後，將該切片將從資源管理器中刪除。也就是說，資源管理器根據任務的調度結果進行更新，當維護新任務的布局結果時，對於存活時間在任務運行時間內的資源切片，在其維護的二維矩陣中，將任務布局區域內的資源狀態更新為佔用狀態；當任務的運行啟動時間或運行結束時刻在某資源切片的存活時間內，則該資源切片將分裂為兩個新的資源切片，將任務運行啟動時刻或運行結束時刻所在的資源切片中的布局區域進行資源狀態更新，而另一切片中維護的二維矩陣維持不變。在執行任務調度結果的刪除過程時，將該任務所涉及的資源切片進行資源狀態更新，將被刪除任務的布局區域內的資源狀態更新為空閒狀態。
對於未啟動的預約任務，由於其調度結果利用軟體維護，包括PTQ、AEQ和資源管理器維護的調度結果，通過失效預約任務的調度結果，使後續任務可佔用預約任務失效後釋放的資源。即將預約失效任務的控制塊從在PTQ中刪除；同時在AEQ中將失效任務的運行啟動和結束時刻維護的活動事件總數減1，若活動事件總數減1後為0時，表示在該時刻維護的控制塊無效，將其從AEQ中刪除；在資源管理器中將失效任務的布局區域內的資源狀態，從佔用狀態修改為空閒狀態。
當任務到達系統後，加入等待調度隊列，當新任務直接預約調度失敗時，將新任務與預約任務比較緊迫度大小，若不存在緊迫度較小的預約任務時，該任務無法進行搶佔調度，將該任務丟棄；若存在緊迫度較小的預約任務，將此類預約任務的調度結果失效，新任務在此基礎上進行搶佔調度，若搶佔調度成功，維護任務的調度結果，並對各失效任務進行重新調度，若搶佔調度失敗，對於預約失效任務，直接恢復其先前的調度結果，將避免對失效任務的再調度過程。
在預約任務的失效過程中，分先後順行對其調度結果進行刪除，首先刪除預約任務在AEQ和資源管理器中的調度結果，當新任務搶佔失敗成功時，再將其在PTQ中的維護結果刪除；當新任務搶佔調度失敗時，利用失效任務在PTQ中未刪除的調度結果，直接在AEQ和資源管理器中恢復失效任務的調度結果。
由此可見，在本發明提供的系統中，以調度器為核心，布局器和資源管理器分別在調度器控制下完成任務布局過程和資源狀態更新過程，其中布局器根據調度器發送的潛在布局時刻表PPTL，在各個時刻依次進行布局。資源管理器根據調度器發送的資源狀態更新信息，當任務調度成功時，將該任務布局區域內的資源狀態更新為佔用狀態，表示該區域內的資源已被佔有；當調度器刪除某任務的調度結果時，利用調度器發送的資源狀態更新信息，將任務原布局區域的資源狀態更新為空閒，表示該區域內的資源未被佔用。通過刪除先前已調度任務的調度結果，即失效已調度任務的布局結果，使其釋放其所佔資源，後續到達任務根據任務的服務屬性決定該任務是否對先前任務進行搶佔調度，從而實現不同任務在調度過程中的區分服務，即為不同需求的任務提供差異化服務，提高任務的調度效率。
基於上述方法的實現過程，本發明實施例還提供一種可重構任務調度方法，其流程圖詳見圖10，所述方法包括 步驟1001調度器提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL； 步驟1002調度器接收布局器發送的根據所述PPTL得到的所述任務的啟動時間及對應的資源； 步驟1003調度器根據所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行調度，並維護調度成功的任務的啟動時刻和布局區域，控制資源管理器中資源狀態的更新。
可選的，所述方法還可以包括布局器根據接收到的所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到所述任務的啟動時間及對應的資源，並將所述任務的啟動時間及對應的資源發送給調度器。
其中，在步驟1001中，所述調度器提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL具體包括 提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度，利用活動事件隊列AEQ提取出在所述任務鬆弛度內的活動時刻，生成PPTL。
布局器根據接收到的所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到所述任務的啟動時間及對應的資源，並將所述任務的啟動時間及對應的資源發送給調度器 可選的，所述布局器根據所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到所述任務的啟動時間及對應的資源具體包括 布局器根據所述任務的寬度、高度和PPTL，利用空閒矩陣資源匹配的搜索方式，對所述PPTL中的離散分布時刻依次進行布局，並對所述資源管理器提供的三維搜索空間進行空閒區域搜索，得到該任務的啟動時間及對應的資源，其中，所述三維搜索為三維資源長方體，所述三維資源長方體是指二維資源面積和時間維組成的具有時空特性的三維抽象資源模型。
其中，所述布局器對所述資源管理器提供的三維搜索空間進行空閒區域搜索具體包括所述布局器在所述資源管理器提供的三維搜索空間的各個時刻的資源切片中可容納該任務的連續空閒區域，當空閒區域搜索成功後，將該空閒區域垂直掃描，以使該空閒區域在後續時間內仍保持空閒狀態，且該空閒區域能被任務連續佔用e時間，其中e為任務的運行時間。
在步驟1003中，所述調度器根據所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行調度，並維護調度成功的任務的啟動時刻和布局區域，控制資源管理器中資源狀態的更新具體包括 調度器所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行刪除或存儲；對於調度成功的任務，在運行任務隊列ETQ和預約任務隊列PTQ中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ進行更新；並根據調度結果控制所述資源管理器進行資源狀態的更新；資源管理器根據所述調度任務，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間。
其中，所述資源管理器根據所述調度結果，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間具體包括所述資源管理器採用資源切片鍊表的資源管理方式，在接收到所述調度器發送的資源狀態更新信息時，利用資源切片對應的二維矩陣中的權值來更新任務布局區域內的資源的使用狀態，並將資源切片按時間先後順序依次排列，維護不同時刻的資源使用狀態，為所述布局器匹配資源提供三維的搜索空間。
在該實施例中，任務到達系統後，系統將該任務加入等待調度隊列，調度器首先對任務直接進行預約調度，將任務抽象為矩形，由時空屬性參數(w，h，a，e，d)分別表示任務矩形的寬度、高度，任務的到達時刻、執行時間、截止時刻，計算任務的鬆弛時間範圍[a，d-e]，並利用AEQ中維護的活動事件發生時刻，提取出在[a，d-e]內的活動事件發生時刻，作為PPTL表中的各布局時刻，其中a時刻為PPTL表中的首個布局時刻，如圖11所示，為本發明中提供的PPTL表的生成過程的示意圖；布局器根據輸入的任務的時空屬性參數和PPTL表，在資源管理器中對任務進行布局，若任務直接在a時刻布局成功，表示該任務直接調度成功，布局器向調度器返回布局結果，調度器將調度結果在運行任務隊列ETQ和AEQ中進行維護，同時根據布局區域和任務的結束時刻在資源管理器中進行資源狀態維護；若任務後續時刻布局成功，表示該任務預約調度成功，布局器向調度器返回布局結果，調度器將調度結果在預約任務隊列表PTL和AEQ中進行維護，同時根據布局區域、預約啟動時刻和結束時刻在資源管理器中進行資源狀態維護；當任務後續時刻都布局失敗時，布局器向調度器返回失敗消息，由調度器決定該任務將進行搶佔調度，其中ETQ、PTQ、AEQ和PPTL的狀態轉換，如圖12所示，為本發明提供的ETQ、PTQ、AEQ和PPTL狀態轉換的示意圖。
在當前時刻t，對於新到達任務和已預約任務，將兩任務在t時刻的緊迫度(urgency)表示為

其中t＜s≤d-e，s為任務的預約啟動時刻。新任務在其到達時刻與預約任務比較緊迫度大小，若存在緊迫度較小的預約任務，將預約任務的調度結果失效，其失效過程包括 在AEQ中刪除活動事件發生時刻記錄，並在資源管理器器中將失效任務的布局區域內資源狀態更新為空閒，對PTQ中維護的預約任務控制塊暫不刪除，當完成緊迫度較小任務的失效過程以後，新任務在此基礎上進行調度，包括生成PPTL表，並將PPTL表和任務面積屬性發送給布局器，由布局器對任務進行布局處理，當任務在某時刻布局成功時，表示該任務搶佔調度成功，布局器返回調度結果，調度器對調度結果進行維護，同時刪除預約失效任務在PTQ中的控制塊，並對各失效任務重新進行調度；若新任務的搶佔調度過程失敗，則布局器返回布局失敗信息，則調度器將新任務從等待隊列中刪除，同時利用各失效任務在PTQ中維護的控制塊，包括布局區域，預約啟動時刻和結束時刻，分別對AEQ和資源管理器進行更新，從而使失效任務恢復為正常的預約任務，避免了對失效任務的再調度過程。利用緊迫度差異實現不同任務的區分服務，使緊迫度交大的任務優先調度，使任務的調度更加合理，有利於提高任務調度的整體成功率 也就是說，本發明中的任務調度是基於PPTL表的離散預約過程，並支持對預約任務的搶佔調度，具體實現過程包括系統接收任務後，將該任務加入等待調度隊列，首先對任務直接進行預約調度，將任務抽象為矩形，由時空屬性參數(w，h，a，e，d)分別表示任務矩形的寬度、高度，任務的到達時刻、執行時間、截止時刻；新任務到達後，調度器保存該任務，並利用任務的時空屬性對任務首先直接進行預約調度，若該任務能直接調度成功，則新任務無需進行搶佔調度，若新任務直接調度不成功，根據緊迫度大小，決定新任務是否對已預約任務進行搶佔調度，對緊迫度較小的任務通過將其調度結果失效，新任務在此基礎上進行調度，並可佔用失效任務釋放的資源，若搶佔調度成功，維護新任務的調度結果，同時將失效任務再重新調度，若搶佔預約失敗，調度器丟棄新任務，同時恢復失效任務的調度結果，避免對失效任務再重新調度。在調度過程(包括搶佔調度過程)中，調度器利用其內部維護的活動事件隊列AEQ，提取出在任務鬆弛度內的活動時刻生成PPTL表，調度器將任務的長度、寬度和PPTL表發送給布局器。布局器利用資源管理器，在PPTL表中的各時刻依次進行布局，若任務在PPTL表中的所有時刻布局失敗，則布局器向調度器返回失敗結果，調度器將該任務從等待調度隊列中刪除；若任務在PPTL表中的某時刻布局成功，則將該時刻作為任務的運行啟動時刻，布局器向調度器返回任務的啟動時刻和布局區域，調度器根據布局結果(包括運行啟動時刻和布局區域)，對自身維護的運行任務隊列ETQ和預約任務隊列PTQ進行更新，並利用任務的運行啟動和運行結束時刻對AEQ隊列進行更新，同時對資源管理器中的資源狀態進行維護，將布局區域內的資源狀態更新為佔用狀態。在支持搶佔調度時，需失效部分預約任務的調度結果，其操作包括對PTQ和AEQ進行更新，同時在資源管理器中將失效任務布局區域內的資源狀態修改為空閒狀態，新任務在此基礎上進行調度，包括生成PPTL表，以及在該表中的各時刻依次布局。任務在其啟動時刻被下載運行，同時開始佔用其布局區域內的資源，當任務運行結束後，其佔用的資源將被釋放。本發明從系統結構上支持完整的任務調度和布局過程，並特別增加對搶佔調度的支持功能，實現不同任務之間的區分調度服務。
由此可知，本發明在可重構系統結構上，以調度器作為系統核心，在調度任務時，能夠以緊迫度區分服務，維護任務隊列，體現了不同任務的服務差異，使緊迫度高的任務優先調度運行，提高了系統調度任務的合理性和成功率。調度器根據任務的時空屬性，生成PPTL表，用於控制任務在資源管理器中的布局過程；同時調度器直接控制資源管理器更新資源使用狀態，利用直接在在資源管理器中添加或刪除任務的調度結果，即刪除以前的調度結果，將現有的先到先服務模式，修改為引入搶佔調度模式；布局器在資源器控制下進行布局，即只對PPTL表中的時刻進行布局，降低了布局器的設計複雜度，使布局器能夠專門負責空閒區域搜索過程，提高了布局操作效率。
在資源管理器中，採用了基於資源切片鍊表的資源管理方式，用離散的切片表示資源的狀態，使得連續的資源狀態能夠用離散的資源切片表示，避免在不同時刻維護相同的資源分布矩陣，從而降低了資源管理的空間、時間複雜度，同時為任務布局過程操作提供了三維資源搜索空間。由於PPTL表中的活動時刻對應於資源切片的起始時刻，使得布局過程只在該數據結構的存活時間的起始時刻進行布局，從而實現離散預約調度過程，避免了重複預約操作，提高了預約調度效率。
為了便於本領域技術人員的理解，下面以支持緊迫度區分的搶佔調度實現過程為例，具體圖13所示，為本發明提供的一種支持緊迫度區分的搶佔調度的流程圖，包括 步驟1301對於在aj時刻到達的新任務Tj(wj，hj，aj，ej，dj)，判斷Tj在aj時刻直接進行BS調度是否成功，若成功，執行步驟1310，若不成功，則執行步驟1302； 步驟1302對任務進行PS調度，判斷該任務是否調度成功，若否，執行步驟1303，若是，則執行步驟1310； 步驟1303對新任務和閾值內的已預約任務執行步驟1304； 步驟1304分別計算各任務的緊迫度大小，並比較新任務的uj與各個已預約任務的ui大小，若存在已預約任務的ui＜uj，則執行步驟1305，若否，則執行步驟1309； 步驟1305在AEQ隊列和資源管理器中將Ti的調度結果失效，判斷Tj在此基礎上進行搶佔調度是否成功，若Tj調度成功，執行步驟1306，若不成功，則執行步驟1307； 步驟1306維護Tj的調度結果，同時將Ti在PTQ隊列中的任務塊刪除，對所有Ti執行步驟1308； 步驟1307利用Ti在PTQ中的控制塊，在AEQ和資源管理器中恢復Ti的調度結果，並對Tj執行步驟1309； 步驟1308按緊迫度從大到小順序依次進行調度，若調度成功，則保存調度結果，若失敗，直接丟棄該任務，當所有Ti都完成調度時，結束本次調度過程。
步驟1309丟棄該任務，結束本次調度過程。
步驟1310在PTQ、AEQ和資源管理器維護任務的調度結果，結束本次調度過程。
在本發明中，布局過程可以分為1.空閒區域搜索過程；2.空閒區域的垂直掃描過程，具體的實現過程如下 在搜索空閒區域過程中，採用了簡單的BL(Bottom Left)掃描法，從二維矩陣的左下角開始，依次沿x軸和y軸搜索空閒區域，將以(j，k)為基點的矩形區域表示為(j，k，j+w-1，k+h-1)，則在該區域內各CLB資源權值之和表示為

若

時，表示在(j，k，j+w-1，k+h-1)區域內的權值都為0，可得到在該區域內的資源都處於空閒狀態；若

時，表示在該區域內的部分或全部資源處於非空閒狀態。
對於由資源切片組成的三維資源模型，在資源切片面S(ti)中，將在該切片中存在的空閒區域表示為 若

時，表示存在以(ji，ki)為基點的空閒區域，則空閒區域掃描成功；若

表示在S(ti)中不存在面積合適的空閒區域，則該任務在ti時刻的空閒區域掃描失敗。
對在S(ti)中搜索到的空閒區域(ji，ki，ji+w-1，ki+h-1)，只表明該區域在ti時刻處於空閒狀態，為防止該區域在將來時刻被其它任務預約，必須保證該空閒區域在[ti，ti+e-1]時間內都被任務佔用。通過沿z軸方向對該空閒區域進行垂直掃描，形成一個以(ji，ki，ti)為基點的三維長方體模型，則長方體中的所有權值之和表示為

若

時，表示該長方體模型中的所有CLB資源都處於空閒狀態，即在(ji，ki，ji+w-1，ki+h-1)區域內的CLB資源在[ti，ti+e-1]時間內都為空閒狀態，則認為該任務在ti時刻調度成功；若

時，表示(ji，ki，ji+w-1，ki+h-1)區域內的資源在[ti+1，ti+e-1]時間內不都處於空閒狀態，則該空閒區域無效，需重新搜索下一空閒區域(ji+1，ki+1，ji+1+w-1，ki+1+h-1)，然後再進行垂直掃描。若在資源切片面S(ti))中搜索的空閒區域都無效，認為該任務在ti時刻的布局過程失敗。
在本調度系統中，資源管理器由資源切片組成，在任務布局過程中，對於在同一資源切片中維護的矩形區域，由於資源分布在存活時間內的各時刻都相同，對同一資源切片，只需垂直掃描其在初始時刻的資源分布，則將基於資源切片的任務模型表示為


其中s布局掃描起始時刻，ti為資源切片的起始時刻，如圖14所示，為本發明提供的一種基於時域資源切片的布局過程的示意圖。在該圖中，若

時，表示在資源切片S(ti)中存在空白矩形(ji，ki，ji+w-1，ki+h-1)，且該空白矩形在[si，si+e-1]時間內垂直掃描成功，則認為該任務在si時刻調度成功，si為任務的預約啟動時刻，其中si＞a；若

時，表示任務在[a，slatest]時間內的各時刻都布局失敗，則該任務在[a，slatest]時間內預約調度失敗。
在本發明中，基於PPTL表的預約調度實現過程的流程圖如圖15所示，具體包括 步驟1501在PPTL表中第一個時刻對任務進行布局，若布局成功，轉步驟1504，否則，轉步驟1502； 步驟1502將第一個布局時刻從PPTL表中刪除，並判斷當前PPTL表是否為空，如果為空，轉步驟1506，否則，轉步驟1503； 步驟1503在PPTL表中的第一個時刻對任務進行布局，若布局成功，轉步驟1505，否則，轉步驟1502； 步驟1504BS調度成功，在ETQ隊列中維護該運行任務的調度結果，結束本次調度過程。
步驟1505PS調度成功，在PTQ隊列中維護該預約任務的調度結果，結束本次調度過程。
步驟1506表示預約調度失敗，丟棄該任務，結束本次調度過程。
通過以上的實施方式的描述，本領域的技術人員可以清楚地了解到本發明可藉助軟體加必需的通用硬體平臺的方式來實現，當然也可以通過硬體，但很多情況下前者是更佳的實施方式。基於這樣的理解，本發明的技術方案本質上或者說對現有技術做出貢獻的部分可以以軟體產品的形式體現出來，該計算機軟體產品可以存儲在存儲介質中，如ROM/RAM、磁碟、光碟等，包括若干指令用以使得一臺計算機設備(可以是個人計算機，伺服器，或者網絡設備等)執行本發明各個實施例或者實施例的某些部分所述的方法。
以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以作出若干改進和潤飾，這些改進和潤飾也應視為本發明的保護範圍。
權利要求
1.一種可重構任務處理系統，其特徵在於，包括調度器、布局器和資源管理器，其中，
所述調度器，用於提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL，並將所述PPTL發送給所述布局器，以及，根據接收到的所述布局器反饋的布局結果對等待調度隊列中的任務進行調度，根據調度結果向所述資源管理器發送資源狀態更新信息；
所述布局器，用於在接收到所述PPTL後，根據所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到該任務的啟動時間及對應的資源，並向所述調度器反饋布局結果；
所述資源管理器，用於在接收到所述調度器發送的資源狀態更新信息時，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間。
2.根據權利要求1所述的系統，其特徵在於，所述調度器包括
計算單元，用於提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度；
生成單元，用於利用活動事件隊列AEQ提取出在所述任務鬆弛度內的活動時刻，生成PPTL，並將所述任務的寬度、高度及PPTL發送給所述布局器；
調度單元，用於接收所述布局器反饋的布局結果，並根據所述布局結果對等待調度隊列中的任務進行調度，如果調度失敗，則刪除對應的業務，如過調度成功，則存儲該任務；
調度結果維護單元，用於對所述調度單元調度成功的任務，在運行任務隊列ETQ和預約任務隊列PTQ中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ進行更新；並根據調度結果向所述資源管理器發送資源狀態更新信息。
3.根據權利要求2所述的系統，其特徵在於，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息具體包括
當任務布局成功時，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息，控制所述資源管理器將任務布局區域的所有資源的狀態標註為非空閒狀態，防止該區域被後續任務佔用；在刪除任務時，控制所述資源管理器將被刪除任務布局區域內的資源狀態更新為空閒，使後續任務可預約該區域內資源。
4.根據權利要求2所述的系統，其特徵在於，所述調度器還包括
活動事件隊列AEQ，用於存儲任務時間發生時刻以及在該時刻發生的事件個數，所述任務發生時刻是指任務運行啟動和運行結束事件的發生時刻，在AEQ中的活動事件按照發生時刻順序存儲在AEQ中，對於在同時刻發生的多個事件只需一個控制塊進行維護。
5.根據權利要求2所述的系統，其特徵在於，所述布局器包括
布局搜索單元，用於在接收到所述任務的寬度、高度和PPTL後，利用空閒矩陣資源匹配的搜索方式，對所述PPTL中的離散分布時刻依次進行布局，並對所述資源管理器提供的三維搜索空間進行空閒區域搜索，得到該任務的啟動時間及對應的資源，其中，所述三維搜索為三維資源長方體，所述三維資源長方體是指二維資源面積和時間維組成的具有時空特性的三維抽象資源模型；
布局搜索結果反饋單元，用於向所述調度器反饋該任務的啟動時間及對應的資源。
6.根據權利要求5所述的系統，其特徵在於，所述布局搜索單元對所述資源管理器提供的三維搜索空間進行空閒區域搜索具體包括
所述布局搜索單元在所述資源管理器提供的三維搜索空間的各個時刻的資源切片中可容納該任務的連續空閒區域，當空閒區域搜索成功後，將該空閒區域垂直掃描，以使該空閒區域在後續時間內仍保持空閒狀態，且該空閒區域能被任務連續佔用e時間，其中e為任務的運行時間。
7.根據權利要求1至6任一項所述的系統，其特徵在於，所述資源管理器具體用於，採用資源切片鍊表的資源管理方式，在接收到所述調度器發送的資源狀態更新信息時，利用資源切片對應的二維矩陣中的權值來更新任務布局區域內的資源的使用狀態，並將資源切片按時間先後順序依次排列，維護不同時刻的資源使用狀態，為所述布局器匹配資源提供三維的搜索空間。
8.一種調度器，其特徵在於，包括
計算單元，用於提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度；
生成單元，用於利用活動事件隊列AEQ提取出在所述任務鬆弛度內的活動時刻，生成PPTL，並將所述任務的寬度、高度及PPTL發送給所述布局器；
調度單元，用於接收所述布局器反饋的布局結果，並根據所述布局結果對等待調度隊列中的任務進行調度，如果調度失敗，則刪除對應的業務，如過調度成功，則存儲該任務；
調度結果維護單元，用於對所述調度單元調度成功的任務，在運行任務隊列ETQ和預約任務隊列PTQ中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ進行更新；並根據調度結果向所述資源管理器發送資源狀態更新信息。
9.根據權利要求8所述的調度器，其特徵在於，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息具體包括
當任務布局成功時，所述調度結果維護單元根據調度結果向所述資源管理器發送資源狀態更新信息，控制所述資源管理器將任務布局區域的所有資源的狀態標註為非空閒狀態，防止該區域被後續任務佔用；在刪除任務時，控制所述資源管理器將被刪除任務布局區域內的資源狀態更新為空閒，使後續任務可預約該區域內資源。
10.根據權利要求8或9所述的調度器，其特徵在於，所述調度器還包括
活動事件隊列AEQ，用於存儲任務時間發生時刻以及在該時刻發生的事件個數，所述任務發生時刻是指任務運行啟動和運行結束事件的發生時刻，在AEQ中的活動事件按照發生時刻順序存儲在AEQ中，對於在同時刻發生的多個事件只需一個控制塊進行維護。
11.一種可重構任務調度方法，其特徵在於，包括
調度器提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL，並向布局器發送所述PPTL；
調度器接收布局器發送的根據所述PPTL得到的所述任務的啟動時間及對應的資源；
調度器根據所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行調度，並維護調度成功的任務的啟動時刻和布局區域，控制資源管理器中資源狀態的更新。
12.根據權利要求11所述的方法，其特徵在於，還包括
布局器根據接收到的所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到所述任務的啟動時間及對應的資源，並將所述任務的啟動時間及對應的資源發送給調度器。
13.根據權利要求11或12所述的方法，其特徵在於，所述調度器提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成該任務布局的潛在布局時刻表PPTL具體包括
提取出接收到的任務的寬度、高度，計算所述任務的鬆弛度，利用活動事件隊列AEQ提取出在所述任務鬆弛度內的活動時刻，生成PPTL。
14.根據權利要求12所述的方法，其特徵在於，所述布局器根據所述PPTL中的各個時刻對所述資源管理器提供的資源進行布局搜索，得到所述任務的啟動時間及對應的資源具體包括
布局器根據所述任務的寬度、高度和PPTL，利用空閒矩陣資源匹配的搜索方式，對所述PPTL中的離散分布時刻依次進行布局，並對所述資源管理器提供的三維搜索空間進行空閒區域搜索，得到該任務的啟動時間及對應的資源，其中，所述三維搜索為三維資源長方體，所述三維資源長方體是指二維資源面積和時間維組成的具有時空特性的三維抽象資源模型。
15.根據權利要求14所述的方法，其特徵在於，所述布局器對所述資源管理器提供的三維搜索空間進行空閒區域搜索具體包括
所述布局器在所述資源管理器提供的三維搜索空間的各個時刻的資源切片中可容納該任務的連續空閒區域，當空閒區域搜索成功後，將該空閒區域垂直掃描，以使該空閒區域在後續時間內仍保持空閒狀態，且該空閒區域能被任務連續佔用e時間，其中e為任務的運行時間。
16.根據權利要求11所述的方法，其特徵在於，所述調度器根據所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行調度，並維護調度成功的任務的啟動時刻和布局區域，控制資源管理器中資源狀態的更新具體包括
調度器所述任務的啟動時間及對應的資源對等待調度隊列中的任務進行刪除或存儲；對於調度成功的任務，在運行任務隊列ETQ和預約任務隊列PTQ中建立對應的控制塊，維護該任務的啟動時刻和布局區域；根據該任務的啟動時刻和運行結束時刻對AEQ進行更新；並根據調度結果控制所述資源管理器進行資源狀態的更新；
資源管理器根據所述調度任務，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間。
17.根據權利要求16所述的方法，其特徵在於，所述資源管理器根據所述調度結果，更新任務布局區域內的資源狀態，並為所述布局器提供三維的搜索空間具體包括
所述資源管理器採用資源切片鍊表的資源管理方式，在接收到所述調度器發送的資源狀態更新信息時，利用資源切片對應的二維矩陣中的權值來更新任務布局區域內的資源的使用狀態，並將資源切片按時間先後順序依次排列，維護不同時刻的資源使用狀態，為所述布局器匹配資源提供三維的搜索空間。
全文摘要
本發明涉及一種可重構任務處理系統、調度器及方法，所述系統包括調度器，用於提取接收到的任務的時空屬性參數，計算該任務的鬆弛度，生成任務布局的潛在布局時刻表PPTL，並將PPTL發送給布局器，以及根據接收到的布局器反饋的布局結果對等待調度隊列中的任務進行調度，根據調度結果向資源管理器發送資源狀態更新信息；布局器，用於在接收到PPTL後，根據PPTL中的各個時刻對資源管理器提供的資源進行布局搜索，得到該任務的啟動時間及對應的資源，並向調度器反饋布局結果；資源管理器，用於在接收到調度器發送的資源狀態更新信息時，更新任務布局區域內的資源狀態，並為布局器提供三維的搜索空間。以提高任務的調度效率。
文檔編號G06F9/50GK101710292SQ200910259580
公開日2010年5月19日 申請日期2009年12月21日 優先權日2009年12月21日
發明者汪斌強, 黃萬偉, 蘭巨龍, 曹曉磊, 李德華, 李鵬, 王保進, 於婧 申請人:中國人民解放軍信息工程大學