寧明超，張俊勃，陳戈

（華南理工大學(xué) 電力學(xué)院，廣州 510641）

0 引言

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

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

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

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

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

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

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

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

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

1 問題建模

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

1.1 任務(wù)模型

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

1.2 資源模型

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

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

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

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

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

1.3 任務(wù)的重要程度模型

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

1）固有重要程度。

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

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

2）松弛度。

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

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

3）效用函數(shù)。

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

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

1.4 性能評估模型

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

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

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

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

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

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

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

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

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

5）M5：任務(wù)的平均響應(yīng)時間，即所有任務(wù)的響應(yīng)時間的平均值。計算公式如下：

2 IRSA設(shè)計

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

2.1 調(diào)度器框架

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

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

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

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

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

2.2 IRSA

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

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

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

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

算法1 IRSA。

2.2.1 正常分配算法

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

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

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

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

算法2 正常分配算法。

2.2.2 資源預(yù)留算法

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

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

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

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

算法3 資源預(yù)留算法。

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

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

3.1 案例背景

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

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

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

3.2 案例設(shè)計

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

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

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

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

3.3 仿真結(jié)果與分析

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

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

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

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

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

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

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

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

當每秒任務(wù)到達數(shù)量從每秒3.95 增加到5.09 時，即從第4 組到第5 組任務(wù)，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 基于任務(wù)的重要程度進行排序，優(yōu)先分配重要任務(wù)，它的M1只降低了1.19%，然而FPS 延遲了對非重要任務(wù)的處理，導(dǎo)致M2降低了34.60%。

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

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

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

表1 第8組任務(wù)的調(diào)度結(jié)果對比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即平均響應(yīng)時間分別減少了55.83%～61.27%。這說明在任務(wù)到達率很高時，4 種對比算法的性能明顯下降，而IRSA 依然可以對任務(wù)進行合理高效的調(diào)度，在優(yōu)先保障重要任務(wù)被盡快處理的同時，兼顧非重要任務(wù)的按時完成，顯著提高了任務(wù)的響應(yīng)速度。

4 結(jié)語

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

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