[發明專利]一種工作流的任務調度方法、多工作流調度方法及其系統

在審

• 申請號: 201410089720.X
• 申請日: 2014-03-12
• 公開（公告）號: CN103914754A
• 公開（公告）日: 2014-07-09
• 發明（設計）人: 張鵬;張世鵬;李焱;朱嵬;劉慶云;譚建龍
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 北京輕創知識產權代理有限公司 11212
• 代理人: 楊立

技術領域

本發明涉及面向云計算的工作流的任務調度領域，特別是涉及一種工作流的任務調度方法，以及針對在不同時間提交的具有多優先級的多工作流調度方法及其系統。?

背景技術

工作流作為一種協作和集成支撐技術，在過去的20年里，已經在電子政務、電子商務、科學計算等領域得到了廣泛的應用。伴隨著云計算的興起，一些業界廠商的云工作流的產品也開始出現，然而，現有技術普遍忽視了針對多種QoS需求類型的多個工作流在不同時間提交到云中執行的調度問題，為此而普遍采用的一個簡單辦法是利用“順序法”，將所有的工作流放入一個隊列按順序調度，將隊列中的一個工作流利用單個工作流調度方法將其所有任務調度完畢后，再調度下一個工作流。然而，這種方法既不能充分利用資源，也存在著較大的不公平問題。針對這種不公平問題，有人提出了將多個工作流合并成一個復合工作流的方法用于處理和解決多工作流之間調度的時間不公平問題。同時，也有人提出了關于多工作流調度的時間公平性定義方法和兩個公平調度方法，Fairness-F1是其中之一，但是該方法沒有進一步考慮不同用戶在不同時間提交工作流的情況。在很多情況下，不同用戶提交工作流的時間是隨機的，不一定是在同一時間提交，系統如果讓先到達的工作流等待其他工作流到來后同時調度，顯然會降低資源利用率和工作流的吞吐量。為此，有人提出了動態的調度模型和策略，采用的方法是：將所有具備執行條件的任務根據任務的權值的大小按降序或者升序放入調度隊列?中，如果這些具備執行條件的任務來自同一個工作流，則調度隊列中的任務按降序排列，否則按升序排列，從而避免早到達的工作流中權值較小的任務得不到調度的情況。然而，這種方法仍然會造成不同程度的不公平問題，因為如果后續被提交的工作流的任務的權值總是低于那些先來工作流中未被調度的任務的權值，那么先來的工作流中的剩余任務將得不到調度，所以只適合于多個工作流之間結構和復雜程度相近的情況。針對這個問題，有人提出了對已經準備好調度的任務池中來自不同工作流的任務進行優先級權值確定的方法，同時考慮每個工作流剩余任務完成時間和數量占工作流總任務的百分比，從而達到了較好的公平性。然后，上述這些研究僅僅針對多個工作流具有相同服務質量需求類型的情況，在云計算環境下，通常會面臨多個工作流來自不同的用戶，而不同的用戶的工作流可能具有不同的服務質量需求類型。例如金融市場分析、監控系統等應用的多個任務之間存在先后約束關系，并且這些應用要求整個工作流的完成時間越短越好。如果完成時間過于滯后，執行結果將失去意義，同時，有些應用則對執行時間的要求不嚴格。因此當上述這些服務質量需求不同的多個工作流共享資源進行混合調度時，對完成時間要求的緊急程度是不一樣的，并且用戶可能會隨時提交新的工作流來要求調度執行。?

為此，本發明提出了一種工作流的任務調度方法以及多工作流調度方法和系統。?

發明內容

本發明所要解決的技術問題是提供一種工作流的任務調度方法以及多工作流調度方法和系統，用于解決在不同時間提交的具有多優先級的多工作流的調度方問題。?

本發明解決上述技術問題的技術方案如下：一種工作流的任務調度方?法，包括：?

步驟1，計算工作流中每個任務的向上權值，按向上權值的降序排序將任務放入待調度任務列表；?

其中，任意任務n_i的向上權值rank(n_i)被遞歸地定義為：?