基于面向服務架構的工業(yè)軟件的任務調(diào)度算法

寧明超，張俊勃，陳戈

（華南理工大學 電力學院，廣州 510641）

0 引言

隨著信息技術的發(fā)展及其與工業(yè)領域的融合，各類工業(yè)軟件已經(jīng)廣泛用于工業(yè)生產(chǎn)過程的控制和管理［1］。現(xiàn)有工業(yè)軟件大多采用面向服務架構（Service-Oriented Architecture，SOA），軟件被拆分為多個粗粒度、松耦合的服務，服務間通過網(wǎng)絡通信［2］。基于SOA 的軟件收到用戶請求后，相應服務實例會對請求進行處理，完成處理后向用戶返回結果。本文將每個請求的處理過程稱為一個任務。

與大多數(shù)商業(yè)軟件相比，工業(yè)軟件對實時性和可靠性的要求非常高［3］。實時性指軟件對請求作出迅速響應的能力；可靠性指軟件在規(guī)定時間內(nèi)完成相應任務的能力，與任務的按時完成率呈正相關。任務的完成過程需要占用服務實例的計算資源，包括中央處理器（Central Processing Unit，CPU）、內(nèi)存、磁盤輸入輸出（Input and Output，IO）、網(wǎng)絡帶寬［4］。然而，工業(yè)軟件中通常存在大量待處理任務，而服務實例的可用計算資源有限，無法同時處理所有任務，導致部分任務難以被快速處理，甚至不能按時完成，造成經(jīng)濟損失甚至安全事故［5］。因此，設計一種高效的任務調(diào)度方法將任務合理地分配給服務實例處理，是保障工業(yè)軟件實時性和可靠性的重要需求［6］。

任務調(diào)度方法需要結合應用場景的特點設計。在工業(yè)場景中，不同任務的重要程度對工業(yè)系統(tǒng)的影響不同［7］。軟件需要優(yōu)先處理重要任務，同時盡可能多地處理非重要任務。因此，重要程度是任務的屬性之一，需要設計合適的方法進行評估。而任務的處理需要占用服務實例的部分計算資源，這就是任務的資源需求量屬性。此外，任務還具有到達時間、處理時長和截止時間的屬性，而截止時間限制了任務的完成時間。例如，在輸電線路故障處理場景中［8］，線路可能由于絕緣老化、鳥獸跨接、氣象條件等因素突然發(fā)生短路故障（到達時間）；不同故障對電力系統(tǒng)危害程度不同（重要程度）；故障處理軟件需要在規(guī)定時間內(nèi)盡快完成故障處理（截止時間）。在工廠生產(chǎn)管理系統(tǒng)中［9］，生產(chǎn)計劃根據(jù)銷售訂單的到來而制定（到達時間），不同生產(chǎn)計劃的重要程度不同（重要程度），生產(chǎn)計劃的執(zhí)行有截止時間限制，工廠必須在訂單規(guī)定的交貨時間之前完成相應產(chǎn)品的生產(chǎn)（截止時間）。此外，故障處理和生產(chǎn)計劃的制定都需要在一段時間內(nèi)占用服務實例的部分計算資源（處理時長、資源需求量）。

上述部分屬性還具有隨機性和時變性，屬性間存在一定的耦合關系。首先，任務的到達時間是隨機的，同一任務在多次處理過程中使用的資源量和處理時長會在一定范圍內(nèi)隨機波動；其次，任務的重要程度隨等待時間的增加而變高；再次，任務在臨近截止時間時，重要程度會大幅增加。例如，在上述輸電線路故障處理場景與工廠生產(chǎn)管理系統(tǒng)中，故障發(fā)生時間和銷售訂單的到達時間隨機，且故障處理任務和訂單處理任務的重要程度都隨處理時間的增加而變高，在臨近截止時間時會大幅增加。

通過上述分析可知，工業(yè)軟件的任務具有多重屬性，部分屬性具有隨機性、時變性且相互耦合。基于這些任務特點，可以對任務調(diào)度方法進行設計。針對工業(yè)軟件的實時性要求，任務調(diào)度方法也需要具備實時性，保證隨機到來的新任務能被快速分配給服務實例處理；同時，為滿足工業(yè)軟件的可靠性要求，每個服務需要設置多個實例，且每個服務實例應能并行處理多項任務。因此，是否具有實時性，以及服務實例的處理能力也是任務調(diào)度方法需要考慮的因素，本文將從這兩個角度出發(fā)，分析現(xiàn)有任務調(diào)度方法的適用性。

是否具有實時性指調(diào)度方法能否實時作出決策，如果能則稱為在線方法，否則稱為離線方法。離線方法適用于任務信息在調(diào)度前已經(jīng)確定的場景。例如，文獻［10］中提出一種考慮截止時間和時隙可用性約束的離線方法，文獻［11］中提出一種考慮截止時間約束的基于蟻群優(yōu)化算法的離線方法，均實現(xiàn)了對非實時任務的高效調(diào)度。在線方法適用于任務不斷到來的場景，主要有基于優(yōu)化算法和基于優(yōu)先級排序的兩種解決思路：前者將調(diào)度問題建模為最優(yōu)化問題，從解空間中搜索最優(yōu)解，根據(jù)最優(yōu)解分配任務［12-13］；后者只需計算所有待處理任務的優(yōu)先級并排序，根據(jù)優(yōu)先級順序調(diào)度任務［14-15］。由于求解優(yōu)化問題的計算量較大，故前者的調(diào)度決策耗時較長；而優(yōu)先級通常由函數(shù)表達式計算得到，計算量較小，故后者的調(diào)度決策耗時較短。因此，基于優(yōu)先級排序的方法應用更廣泛，其中常用的方法有先來先服務（First Come First Serve，F(xiàn)CFS）方法［16-17］、最早截止時間優(yōu)先（Earliest Deadline First，EDF）方法［18-19］、最小松弛度優(yōu)先（Least Laxity First，LLF）方法［20-21］和固定優(yōu)先級調(diào)度（Fixed Priority Scheduling，F(xiàn)PS）方法［22］等。在工業(yè)軟件中，任務隨機到來，數(shù)量多且具有截止時間限制，因此適合采用基于優(yōu)先級排序的在線調(diào)度方法。

按照服務實例的處理能力不同，可將現(xiàn)有方法分為單線程和多線程方法。單線程方法中的每個服務實例只能同時處理一個任務，而多線程方法中的每個服務實例可以同時處理多個任務。在單線程方法的研究中，文獻［15］中考慮的云服務平臺提供多種類型的服務實例，服務實例在任何時刻最多只能執(zhí)行一個任務；文獻［23］中提出了一種云計算服務的調(diào)度算法，該算法選擇期望效用最高的待處理任務進行處理，只有在當前任務處理完成或被丟棄時，才能處理下一個任務。在多線程方法的研究中，文獻［9］中利用服務容量衡量服務實例的處理能力，在滿足容量約束的條件下，每個服務實例可以同時處理多個任務；文獻［24］中研究了基礎設施即服務（Infrastructure as a Service，IaaS）系統(tǒng)的任務調(diào)度問題，該場景中每臺服務器是一個服務實例，可以同時承載多臺虛擬機任務，因此每個服務實例可以同時處理多個任務。顯然，在具有大量任務且任務有截止時間限制的工業(yè)場景中，應選擇能實現(xiàn)任務并行處理的多線程方法。

綜上，工業(yè)軟件的任務調(diào)度問題具有以下特點：1）具有重要程度屬性，重要程度具有時變性且與截止時間相互耦合；2）實時性要求高，需要對任務進行實時調(diào)度；3）可靠性要求高，服務實例應具有并行處理多任務能力。在現(xiàn)有的任務調(diào)度方法中，文獻［10-11］中的方法屬于離線方法，不適用于任務實時到達的工業(yè)場景，不能滿足實時性要求；文獻［12-13］中的方法雖然為在線方法，但由于采用優(yōu)化方法求解調(diào)度問題，調(diào)度決策耗時較長，也不能滿足高實時性要求；文獻［15，23］中的方法屬于單線程方法，每個服務實例不具備并行處理任務能力，不能滿足高可靠性要求；同時，現(xiàn)有方法都沒有融合工業(yè)場景的特點，沒有考慮任務重要程度的時變性以及重要程度與截止時間的耦合。由此可見，現(xiàn)有方法都不能同時滿足上述三個特點。

因此，本文同時考慮了工業(yè)軟件任務調(diào)度問題的三個特點并進行建模，主要工作包括：建立任務重要程度模型，設計用于評估任務重要程度的效用函數(shù)；建立任務模型；建立服務實例具有并行處理能力的資源模型。在此基礎上，本文提出了一種適用于基于SOA 的工業(yè)軟件的任務調(diào)度算法——基于重要程度排序的調(diào)度算法（Importance Ranking-based Scheduling Algorithm，IRSA）。該算法屬于基于優(yōu)先級排序的在線的多線程方法，根據(jù)重要程度對任務進行排序，按照重要程度遞減的順序?qū)⑷蝿辗峙浣o服務實例處理。為提升IRSA 的調(diào)度效率，本文設計了資源預留機制［12］，當所有服務實例的資源都不足以處理當前效用值最高的任務時，將某一服務實例未來可用的資源預留給該任務。考慮到有些任務在任何情況下都需要被立即處理，將這類任務稱為緊急任務，相應地將非緊急任務稱為普通任務。為保障緊急任務在所有服務實例的資源不足時仍然可以被立即處理，本文設計了搶占式調(diào)度機制［25］，通過搶占其他普通任務的資源，使緊急任務得到優(yōu)先處理。同時，本文采用Golang 實現(xiàn)了IRSA，并在基于SOA 的電網(wǎng)調(diào)度控制軟件中對其進行仿真測試，實驗結果表明，IRSA 可以實現(xiàn)高效的任務調(diào)度，在多項性能指標上顯著優(yōu)于其他對比算法。

1 問題建模

本章對工業(yè)軟件的任務調(diào)度問題進行建模，包括任務模型、資源模型和任務重要程度模型。為定量評價調(diào)度算法的性能，還提出了性能評估模型。

1.1 任務模型

將系統(tǒng)中正在處理和等待處理的任務表示為集合X={x1，x2，…，xp}，其中：p是任務的數(shù)量，隨時間動態(tài)變化。將X中的任務xi建模為xi={ai，di，Ii}，其中：ai表示系統(tǒng)接收到xi的時間；di表示xi的截止時間，系統(tǒng)需要在di之前完成對xi的處理；Ii表示xi的固有重要程度，與xi對應業(yè)務的重要程度相關，一般根據(jù)專家經(jīng)驗或知識給定。

1.2 資源模型

資源需求量是任務的一種關鍵屬性，它指任務在處理過程中需要消耗的服務實例的計算資源量。將xi消耗的資源量表示為ri（kk=1，2，3，4），分別表示CPU、內(nèi)存、磁盤IO 和網(wǎng)絡帶寬。所有能處理xi的服務實例組成了xi的服務實例池，表示為SP(xi)。對于任務x1和x2，若SP(x1)=SP(x2)，則稱x1與x2的類型相同。服務實例分為主實例和備用實例；當任務較少、主實例的剩余資源充足時，任務會被分配到主實例處理；當任務較多、主實例的剩余資源不足以處理緊急任務時，緊急任務會被分配到備用實例處理。

與SP(xi)相關的參數(shù)定義如下：sxi，m表示SP(xi)中第m個服務實例，m=1，2，…，|SP(xi)|，其中：|SP(xi)|是所有能處理xi的服 務實例的數(shù)量；R(sxi，m，k)表示sxi，m的第k類資源可用量。若x1，x2，…，xn與xi的類型相同，在滿足式（1）所示的服務實例資源約束時，sxi，m可以同時處理這n個任務。

假設SP(xi)中所有服務實例的可用資源量和處理任務的能力都相同，則它們處理xi的時間相同。

通常將所有服務實例部署在多臺物理機上，將第l臺物理機表示為PMl，與PMl相關的參數(shù)定義如下：sPMl，j表示部署在PMl上的第j個服務實例，j=1，2，…，u，u是部署在PMl上的服務實例數(shù)量；R(PMl，k)表示PMl的第k類資源可用量。

假設sxi，m部署在PMl上，由于服務實例使用的資源都來源于物理機，將任務xi分配給服務實例sxi，m處理時，除了需要滿足式（1）外，還需要滿足式（2）所示的物理機資源約束：

1.3 任務的重要程度模型

在工業(yè)軟件中，不同任務的重要程度不同。任務的重要程度越高，錯過截止時間對工業(yè)系統(tǒng)的影響越大，越需要盡早處理。任務的重要程度主要與固有重要程度和松弛度相關，本文設計了包含這兩個因素的效用函數(shù)，采用效用值表示重要程度。任務的效用值越大，則重要程度越高。

1）固有重要程度。

固有重要程度是任務的固定屬性，與對應業(yè)務的重要程度相關，通常根據(jù)專家經(jīng)驗或知識給定。例如，在工廠生產(chǎn)管理系統(tǒng)中，對于查詢設備信息和下達生產(chǎn)計劃兩項業(yè)務，后者比前者更重要，對應任務的固有重要程度更高。

將任務xi的固有重要程度表示為I(xi)，取值為［1，5］的整數(shù)，數(shù)值越大表示固有重要程度越高。本文將固有重要程度為5 的任務稱為重要任務，該類任務屬于緊急任務，需要被優(yōu)先快速處理。

2）松弛度。

任務的松弛度指任務在滿足截止時間的條件下可以延遲處理的最大時間。任務xi的松弛度計算如下：

其中：deadline(xi)表示xi的截止時間；duration(xi)表示xi的預估處理時長；timenow表示當前時間。由式（3）可知，松弛度隨著時間的推移而減小。松弛度為非負數(shù)時，任務可以延遲處理，且松弛度越小，任務越需要被盡快處理；松弛度為負數(shù)時，任務錯過截止時間。本文將松弛度小于閾值的任務也歸類為緊急任務。

3）效用函數(shù)。

任務的重要程度由上述兩個因素共同決定，且與固有重要程度呈正相關，與松弛度呈負相關。其中，松弛度為負數(shù)的任務已經(jīng)錯過截止時間，可以認為它的重要程度不再隨松弛度的減小而增加。根據(jù)這些關系，本文設計了用于評估任務重要程度的加權效用函數(shù)，如式（4）所示：

其中：utility(xi)表示xi的效用值，代表xi的重要程度；w1、w2為權重系數(shù)，滿足式（5）的關系；f1(xi)和f2(xi)分別表示固有重要程度和松弛度對任務重要程度的影響，分母的作用是對任務的固有重要程度進行歸一化。當松弛度laxity(xi)為非負數(shù)且較大時，任務具有較大的處理時間裕度，f2(xi)的值較小；當松弛度不斷減小趨向于0 時，任務離截止時間越來越近，f2(xi)的值逐漸增加并趨向于1，且增加的速度不斷變快；當松弛度為負數(shù)時，任務已經(jīng)錯過截止時間，f2(xi)的值恒為1。由于f2(xi)∈(0，1]，不需要進行歸一化。

1.4 性能評估模型

在工業(yè)軟件中，重要任務對系統(tǒng)的影響較大，而非重要任務對系統(tǒng)的影響較小。為提高軟件可靠性，一般要求優(yōu)先處理重要任務，同時盡可能多地處理非重要任務。因此，評估調(diào)度算法的性能時，首要關注的是重要任務的處理情況，其次是非重要任務的處理情況。其中，處理情況包括任務的按時完成情況和等待時間。此外，還需要關注所有任務的總體處理情況，一般以響應時間作為依據(jù)。本文引入5 種指標評估調(diào)度算法的性能表現(xiàn)。其中：M1、M3用于評價算法對重要任務的分配效率，M2、M4用于評價算法對非重要任務的分配效率，M5用于評價算法對所有任務的總體分配合理性。所有指標均假設被調(diào)度任務的數(shù)量是n。

1）M1：重要任務的按時完成比例，即在截止時間之前完成的重要任務占所有重要任務的比例。計算公式如下：

其中：N1（xi）表示xi是否為按時完成的重要任務；N2(xi)表示xi是否為重要任務；finishAt(xi)表示xi的完成時間。

2）M2：非重要任務的按時完成比例，即在截止時間之前完成的非重要任務占所有任務的比例。計算公式如下：

其中：N3(xi)表示xi是否為按時完成的非重要任務，N4（xi）表示xi是否為非重要任務。

3）M3：重要任務的平均等待時間，即所有重要任務的等待時間的平均值。計算公式如下：

其中：WT1(xi)表示重要任務xi的等待時間；startAt(xi)表示xi的開始處理時間；arriveAt(xi)表示xi的到達時間。

4）M4：非重要任務的平均等待時間，即所有非重要任務的等待時間的平均值。計算公式如下：

其中：WT2(xi)表示非重要任務xi的等待時間。

5）M5：任務的平均響應時間，即所有任務的響應時間的平均值。計算公式如下：

2 IRSA設計

本文提出一種適用于工業(yè)場景的調(diào)度器框架，以及基于重要程度排序的調(diào)度算法（IRSA），并設計了資源預留機制和搶占式調(diào)度機制以提高算法的調(diào)度效率。

2.1 調(diào)度器框架

調(diào)度器框架如圖1 所示。調(diào)度器具有任務分配功能和輔助功能。任務分配功能由算法1 實現(xiàn)，通過正常分配、資源預留和搶占式調(diào)度三個子算法（算法2～4）的協(xié)同配合將任務分配給服務實例處理。算法1～4 共同組成了IRSA，它們的詳細邏輯將在2.2 節(jié)介紹。輔助功能負責任務分配過程的相關輔助工作，主要包括任務預處理、任務池更新、信息監(jiān)控，具體如下。

圖1 調(diào)度器框架Fig.1 Framework of scheduler

1）任務預處理。調(diào)度器在接收到任務后，根據(jù)式（4）計算任務的效用值，并將其存入任務池。

2）任務池更新。由于任務池中任務的效用值會隨時間動態(tài)變化，調(diào)度器需要定時更新它們的效用值信息。

3）信息監(jiān)控。調(diào)度器需要監(jiān)控各種信息來作出任務分配決策，包括服務實例的健康狀態(tài)信息和資源信息、物理機的資源信息等。

2.2 IRSA

在工業(yè)軟件中，任務可以分為普通任務和緊急任務，服務實例可以分為主實例和備用實例。考慮到緊急任務的到來具有隨機性且需要被盡快處理，本文規(guī)定備用實例只用于處理緊急任務，制定了以下任務分配原則：

1）將普通任務只分配給主實例處理，若主實例的剩余資源不足，則延遲對它們的處理。

2）將緊急任務分配給主實例處理，若主實例的剩余資源不足，則分配給備用實例處理。若備用實例的剩余資源也不足，則搶占主實例中普通任務所占用的資源，使該主實例滿足緊急任務的資源需求。

根據(jù)上述任務分配原則，本文提出了一種適用于2.1 節(jié)所提框架的在線調(diào)度算法（IRSA），如算法1 所示。其中：TP表示任務池，用于存放所有待分配的任務；WP表示等待任務池，用于存放所有分配失敗、等待再次分配的任務。隨著時間的推移，WP中任務由于松弛度不斷減小，可能由普通任務變成緊急任務。因此，調(diào)度器需要定時檢測WP中是否有緊急任務出現(xiàn)，如果有，則將它們轉移到TP中，防止這些任務因長時間存放在WP中而錯過截止時間。

算法1 IRSA。

2.2.1 正常分配算法

在正常分配過程中，調(diào)度器將任務xi與SP(xi)中的主實例進行資源匹配，判斷服務實例的資源是否滿足需求，如果匹配成功則將xi分配給該主實例處理。如果匹配失敗且xi是緊急任務，則將它與SP（xi）中的備用實例進行資源匹配；如果匹配成功則分配給該備用實例處理，否則跳過該任務的分配，任務xi的正常分配過程結束。

在分配的過程中，需要保證主實例之間的負載均衡，因此調(diào)度器會將xi分配給剩余資源最多的服務實例處理。然而，xi的處理需要使用四類資源（CPU、內(nèi)存、磁盤IO、網(wǎng)絡帶寬），且每類資源的需求量通常不同。因此，調(diào)度器需要先計算xi所需各類資源量占服務實例總資源量的比例，其中占比最高的資源稱為主導資源，然后將xi分配給主導資源剩余最多的服務實例處理。

當所有主實例的資源都不足時，緊急任務才會被分配給備用實例處理。為保證資源需求量較大的緊急任務可以被成功分配給備用實例處理，調(diào)度器不對備用實例做負載均衡，而是使用盡可能少的備用實例去處理緊急任務。例如，SP（xi）中有s1和s2兩個備用實例，調(diào)度器通常將緊急任務xi分配給s1，當s1的資源不足時才將xi分配給s2。

正常分配算法的具體邏輯如算法2 所示，其中SI表示服務實例集合，用于臨時存放滿足要求的服務實例信息。

算法2 正常分配算法。

2.2.2 資源預留算法

WP用于存放暫時沒有足夠資源去處理的任務。考慮到TP中如果存在一些效用值更低且資源需求量更少的任務，則這些任務可能會先被分配給服務實例處理，導致WP中高效用值的任務不能得到優(yōu)先處理。為避免這一情況發(fā)生，本文設計了資源預留算法，為WP中高效用值的任務預留服務實例，被預留的實例不能用于處理其他非預留任務，直到預留任務被分配出去。

為保證高效用值的任務被優(yōu)先處理，同時不影響緊急任務的處理，任務按效用值遞減的順序被預留給實例，其中預留實例都屬于主實例，且每個實例只能被預留給一個任務。例如，假設WP中x1、x2、x3是按效用值遞減排序的同一類型的任務，即SP（x1）=SP（x2）=SP（x3），且SP（x1）中有兩個主實例s1和s2，則只有x1和x2可以被預留給實例s1和s2。

在資源預留過程中，調(diào)度器會根據(jù)任務所需資源、服務實例正在處理的任務資源量、開始處理時間和預估處理時長來分配預留實例，將預估最短時間內(nèi)可以滿足任務需求的主實例預留給對應任務。例如，假設x1有兩個主實例s1和s2，如果預估s1的剩余資源在5 s 后可以滿足x1的需求，預估s2的剩余資源在10 s 后可以滿足x1的需求，則將s1預留給x1。

資源預留算法的具體邏輯如算法3 所示，其中TS表示任務集合，用于臨時存放任務信息；length表示可以分配預留實例的任務數(shù)量。

算法3 資源預留算法。

2.2.3 搶占式調(diào)度算法

為保證緊急任務能被盡早處理，當SP（xi）中所有服務實例的資源都不能滿足緊急任務xi的處理需求時，調(diào)度器將進行搶占式調(diào)度，終止SP（x）i中某個主實例對普通任務的處理，搶占這些任務所占用的資源，使xi能被分配給該主實例處理。

任務在處理過程中需要占用一定資源，且被終止任務在下一次分配給服務實例時，需要重新處理。因此，調(diào)度器終止任務會產(chǎn)生一定代價，需要對終止任務的代價進行評估，優(yōu)先選擇代價低的搶占方式。例如，調(diào)度器執(zhí)行搶占式調(diào)度時需要終止主實例sq中的普通任務xj，代價為：

其中：rjk為xj消耗的資源量；startAt(xj)表示xj的開始處理時間；bk為權重系數(shù)，根據(jù)實際需要確定。

為滿足xi的資源需求，sq可能需要終止多個任務。為盡可能降低終止任務的代價，在滿足xi的資源需求條件下，調(diào)度器首先需要找出使sq終止代價總和最小的任務組合；然后，對每個主實例的最小代價和進行比較，得到代價和最小的服務實例smin-cost；最后，終止該實例中代價和最小的任務，并將xi分配給smin-cost處理。

搶占式調(diào)度算法的具體邏輯如算法4 所示，其中SC用于存放每個任務的終止代價。

算法4 搶占式調(diào)度算法。

3 實驗與結果分析

本文在電力系統(tǒng)調(diào)控業(yè)務場景中對IRSA 的有效性進行了測試。首先驗證了2.2 節(jié)中三種任務分配流程（正常分配、資源預留、搶占式調(diào)度）的正確性；然后在不同任務到達率下，對IRSA 以及目前廣泛應用的FCFS 算法、EDF 算法、LLF 算法和FPS 算法的性能表現(xiàn)進行了測試，驗證IRSA 的優(yōu)越性。其中，F(xiàn)PS 算法中任務的優(yōu)先級為固有重要程度。所有算法均采用Golang 編碼，運行環(huán)境為：Intel Core i7-7700HQ@2.80 GHz 四核CPU、8GB RAM 和Windows 10 操作系統(tǒng)。

3.1 案例背景

電力系統(tǒng)是負責電能生產(chǎn)、輸送、分配的系統(tǒng)，它的安全穩(wěn)定運行對工業(yè)生產(chǎn)制造和人們?nèi)粘Ｉ钪陵P重要。電網(wǎng)調(diào)度控制軟件是應用于該場景的一類工業(yè)軟件，主要負責計劃檢修、電網(wǎng)調(diào)度恢復和查詢業(yè)務。其中：計劃檢修業(yè)務是指按照停電檢修單對電網(wǎng)設備進行檢修操作；電網(wǎng)調(diào)度恢復業(yè)務是指當電網(wǎng)發(fā)生設備故障或異常等事故時，調(diào)度員對電網(wǎng)進行調(diào)度恢復的過程；查詢業(yè)務是指各種數(shù)據(jù)查詢操作，例如查詢開關狀態(tài)、全網(wǎng)電壓分布情況等。

上述三類業(yè)務具有以下特征：1）業(yè)務發(fā)生的時間隨機，停電檢修單的到來、事故的發(fā)生以及查詢操作都是隨機的；2）業(yè)務具有截止時間限制，例如，事故發(fā)生后，調(diào)度員需要在規(guī)定時間內(nèi)采取有效措施進行調(diào)度恢復；3）業(yè)務具有重要程度屬性，例如，被檢修設備的重要性越高，檢修單的重要程度也越高；4）業(yè)務的重要程度隨等待時間的增加而變高，例如，事故等待處理的時間越長，危害性越大，重要程度也會越高。

電力系統(tǒng)中的各種應用軟件由不同廠家開發(fā)，軟件之間一般以服務的方式進行交互。考慮到電網(wǎng)調(diào)度控制軟件不僅需要與其他軟件進行大量交互，例如數(shù)據(jù)采集與監(jiān)控系統(tǒng)、電網(wǎng)高級應用軟件等，同時需要具備較高的可靠性和可擴展性，該類軟件適合采用SOA 架構進行設計。本文考慮的電網(wǎng)調(diào)度控制軟件由7 個服務組成，各服務對應的業(yè)務功能如下：服務A 負責對停電檢修單進行審批操作，審批通過后生成操作票，其中操作票是指檢修設備的詳細操作指令；服務B 負責對操作票進行校核操作，并將通過校核的操作票下發(fā)給廠站執(zhí)行；服務C 負責對數(shù)據(jù)采集與監(jiān)控系統(tǒng)傳輸過來的報文進行解析、識別和校核，確認是否發(fā)生跳閘事故；服務D 負責對故障進行診斷和評估；服務E 負責通知配電網(wǎng)調(diào)度員進行轉電操作；服務F 負責通知變電站運維人員進行現(xiàn)場檢查；服務G 負責查詢開關狀態(tài)和全網(wǎng)電壓分布情況等。

3.2 案例設計

本案例考慮14 類任務，覆蓋計劃檢修、電網(wǎng)調(diào)度恢復和查詢操作三種業(yè)務。本文為服務A、B、C、D 分別設置3 個服務實例，為服務E、F、G 分別設置2 個服務實例，其中每個服務都有1 個備用實例，其余實例為主實例，服務實例均部署在物理機PM1、PM2上。任務和服務實例的具體情況如圖2所示。其中，每個服務實例的可用資源量如下：CPU 為2 核，內(nèi)存為1 GB，磁盤IO 是50 MB/s，網(wǎng)絡帶寬是10 Mb/s。每臺物理機的可用資源量如下：CPU 為12 核，內(nèi)存為6 GB，磁盤IO 是400 MB/s，網(wǎng)絡帶寬是80 Mb/s。

圖2 軟件的任務和服務實例情況Fig.2 Tasks and service instances in software

由于運行環(huán)境的影響，同一類任務（例如圖2 中的A_1）在多次處理過程中，處理時長和消耗的資源量可能會發(fā)生小范圍波動。為反映這種波動情況，任務的預估處理時長、所需資源量等參數(shù)均為服從均勻分布的隨機變量。通過調(diào)節(jié)每100 ms 生成一個任務的概率為10%、20%、…、80%，隨機生成8 組任務，編號為1、2、…、8，各組任務的到達時間均為0～80 s，平均每秒到達任務數(shù)量為1.06、2.01、3.03、3.95、5.09、5.84、6.84、7.99。

為便于分析，按照時間順序，將各組內(nèi)任務的名稱分別設置為t1、t2、…。根據(jù)專家經(jīng)驗，將式（4）效用函數(shù)的權重系數(shù)設置為w1=0.8，w2=0.2；將式（17）代價評估函數(shù)的權重系數(shù)設置為b1=0.32，b2=0.28，b3=0.2，b4=0.2。

3.3 仿真結果與分析

使用IRSA 對隨機生成的8 組任務進行調(diào)度，根據(jù)調(diào)度結果，可繪制出每個服務實例的資源使用時序圖。如圖3 所示為IRSA 對第6 組任務調(diào)度得到的服務C 的三個實例的資源使用時序圖，由于篇幅限制，只展示0～60 s 的情況。其中，每個時序圖都包含4 個子圖，分別表示4 類資源（CPU、內(nèi)存、磁盤IO、網(wǎng)絡帶寬）的使用情況。每個子圖的橫軸表示時間，縱軸表示資源量，其最大刻度與服務實例的可用資源量相等。子圖中的每個矩形表示一個任務的處理過程，矩形的長度表示任務的處理時間，寬度表示資源使用量。為了區(qū)分不同任務的處理過程，相鄰的矩形采用不同灰度標識。為顯示服務實例的資源使用情況，一個矩形可能被拆分為多個矩形，例如圖3（a）中的t20。在這種表示方法下，圖中空白區(qū)域表示服務實例的剩余資源量。下面基于圖3 介紹三種任務的分配過程，其中：T1=3.35 s；T2=5.38 s；T3=6.60 s；任務t20、t94、t116、t142、t170、t32用H～M 表示。

圖3 服務C的3個實例的資源使用時序圖Fig.3 Sequence diagrams of resource usage for 3 instances in service C

在正常分配過程中，調(diào)度器根據(jù)負載均衡原則將任務盡可能均勻地分配給主實例處理。例如，任務t20在3.35 s 到來，它的主導資源是磁盤IO，由于該時刻sC_1的剩余磁盤IO比sC_2多，且sC_1的其他資源都可以滿足t20的需求，因此將它分配給sC_1處理。備用實例主要用于緩解主實例在負載高峰期的壓力，只有在主實例的資源占用率都很高且無法處理緊急任務時，緊急任務才會被分配給備用實例處理，例如，sC_3只在部分時段內(nèi)處理任務，其他時間都處于空閑狀態(tài)。主實例sC_1和sC_2在大部分時間的資源使用量都比較接近，且都明顯高于備用實例sC_3的資源使用量，說明負載在主實例間的分配是比較均衡的。

以任務t32為例介紹資源預留過程，t32在5.38 s 到來，從圖3（a）、（b）中可以看出，此時sC_1和sC_2的剩余內(nèi)存都無法滿足該任務的需求。由于t32是普通任務，調(diào)度器預估sC_2在更短時間內(nèi)能夠滿足該任務的資源需求，因此將sC_2預留給t32。從5.38 s 到6.60 s，sC_2被預留給t32，其他任務不能分配給sC_2處理。在6.60 s 時，sC_2的剩余資源可以滿足任務t32的需求，因此將該任務分配給sC_2處理。

在搶占式調(diào)度過程中，調(diào)度器需要終止一些普通任務，以保證緊急任務能夠按時完成。在圖3（a）、（b）中，虛線框表示被終止的任務。例如，緊急任務t116在18.29 s 到來，此時服務C 的3 個實例的剩余資源都無法滿足該任務的需求，因此調(diào)度器終止sC_1對普通任務t94的處理，并將t116分配給sC_1處理。同理，調(diào)度器在28.26 s 終止了sC_1對普通任務t142的處理，并將緊急任務t170分配給sC_1處理。

對于隨機生成的8 組任務，應用IRSA 和4 種對比算法進行調(diào)度，得到各類性能指標如圖4 所示。

圖4 不同算法的性能比較Fig.4 Performance comparison of different algorithms

由圖4 可知，在第1～4 組任務中，即每秒任務到達數(shù)量較少時，服務實例的資源在絕大多數(shù)時間都可以同時滿足所有待處理任務的需求。因此，除了FCFS 在第3、4 組中M1為89.58%和79.69%，所有算法在5 個指標上的表現(xiàn)基本相同，任務的按時完成率都大于96%。

當每秒任務到達數(shù)量從每秒3.95 增加到5.09 時，即從第4 組到第5 組任務，F(xiàn)CFS、EDF 和LLF的M1分別降低了55.88%、65.48% 和64.29%，而IRSA 只降低 了1.19%；FCFS、EDF 和LLF的M2分別降低了74.62%、72.05% 和72.89%，而IRSA 只降低了8.24%；由于FPS 基于任務的重要程度進行排序，優(yōu)先分配重要任務，它的M1只降低了1.19%，然而FPS 延遲了對非重要任務的處理，導致M2降低了34.60%。

在第5～8 組任務中，即每秒任務到達數(shù)量較多時，服務實例的資源難以同時滿足所有待處理任務的需求，IRSA 的性能表現(xiàn)顯著優(yōu)于FCFS、EDF 和LLF，且隨著任務到達率的增加，IRSA 在各指標上的優(yōu)勢都越來越明顯。本文根據(jù)工業(yè)軟件中任務的特點，在1.3 節(jié)中建立了任務重要程度模型，將固有重要程度為5 的任務和松弛度小于閾值的任務都歸類為緊急任務。由于IRSA 根據(jù)效用值遞減的順序?qū)θ蝿者M行調(diào)度，非重要任務在松弛度小于閾值之前就已經(jīng)得到處理，避免了大量非重要任務轉變?yōu)榫o急任務，因此IRSA 在優(yōu)先保障重要任務被盡快處理的同時，也使非重要任務得到了更快的處理，有效提升了任務的總體響應速度。

而FPS 始終優(yōu)先分配重要任務，使大量非重要任務長期處于等待狀態(tài)，直到松弛度小于閾值時轉變?yōu)榫o急任務。因此，在第5～8 組任務中，F(xiàn)PS在M2、M4和M5上的表現(xiàn)顯著差于IRSA；在第7～8 組任務中，重要任務的數(shù)量較多，服務實例難以及時處理大部分重要任務，因此FPS在M1和M3上的表現(xiàn)顯著差于IRSA。

當每秒任務到達數(shù)量增至7.99 時，即第8 組任務中，所有算法的性能表現(xiàn)如表1 所示。

表1 第8組任務的調(diào)度結果對比Tab.1 Comparison of scheduling results for 8th group of tasks

由表1 可知，相較于對比算法，IRSA的M1提高了14.40～88.80 個百分點，M2提高了38.96～55.66 個百分點，M3減少了55.62%～97.93%，M4減少了63.92%～73.70%，M5即平均響應時間分別減少了55.83%～61.27%。這說明在任務到達率很高時，4 種對比算法的性能明顯下降，而IRSA 依然可以對任務進行合理高效的調(diào)度，在優(yōu)先保障重要任務被盡快處理的同時，兼顧非重要任務的按時完成，顯著提高了任務的響應速度。

4 結語

針對基于SOA 的工業(yè)軟件的任務調(diào)度問題，本文設計了一個用于評估任務重要程度的效用函數(shù)，提出了IRSA。IRSA 根據(jù)重要程度對所有任務排序，按重要程度遞減的順序依次將任務分配給服務實例處理，同時引入了資源預留機制和搶占式調(diào)度機制，在提高任務的處理效率的同時保障了緊急任務得到優(yōu)先快速處理。

實驗結果表明，IRSA 的各項指標均顯著優(yōu)于目前廣泛應用的FCFS、EDF、LLF 和FPS 算法，尤其是在任務到達率較高時，IRSA 能夠大幅降低重要任務的等待時間，保障絕大部分重要任務被按時完成，同時使非重要任務得到更快的處理，顯著提升了任務的總體響應速度。關于未來的研究工作，還有一些問題有待進一步解決，包括尋找效用函數(shù)的最優(yōu)權重值，估計任務的處理時長和所需資源量等。