ROS2 多線程執(zhí)行器上DAG 任務的優(yōu)先級分配方法

紀 東 魏陽杰 李宇溪 王 義

1（東北大學計算機科學與工程學院 沈陽 110819）

2（醫(yī)學影像智能計算教育部重點實驗室（東北大學）沈陽 110819）

隨著機器人和自動駕駛行業(yè)的發(fā)展，為了能夠?qū)崿F(xiàn)產(chǎn)品的快速迭代，代碼復用性和模塊化的需求變得日益強烈.目前行業(yè)內(nèi)已經(jīng)提出在許多軟件平臺（中間件）引入了模塊化和可適應的功能，從而使構(gòu)建相關(guān)系統(tǒng)變得更加容易.其中，機器人操作系統(tǒng)（robot operating system，ROS）在機器人行業(yè)中扮演著至關(guān)重要的角色，它以軟件模塊化和可組合性來加速機器人軟件開發(fā)的過程.2017 年第2 代ROS2 發(fā)布[1]，ROS2 提供了強大的實時能力，以支持實時機器人軟件.例如，ROS2 采用數(shù)據(jù)分發(fā)服務（data distribution service，DDS）來進行實時數(shù)據(jù)的端到端交換，并且可以部署在實時操作系統(tǒng)之上.與ROS2 實時性能相關(guān)的核心組件是執(zhí)行器，它協(xié)調(diào)底層操作系統(tǒng)（operating system，OS）線程中工作負載的執(zhí)行.ROS2 有2 個內(nèi)置執(zhí)行器：一個是按順序執(zhí)行工作負載的單線程執(zhí)行器，另一個是跨多個線程分配工作負載執(zhí)行的多線程執(zhí)行器.近些年，有幾項工作[2-6]研究了ROS2 單線程執(zhí)行器的建模和實時性能.結(jié)果表明，ROS2 執(zhí)行器的調(diào)度行為與以往實時調(diào)度研究中的調(diào)度行為有很大不同.而隨著現(xiàn)代機器人應用程序變得越來越復雜，通常需要在多線程執(zhí)行器上實現(xiàn)它們，以充分挖掘多核處理器的計算能力，這就需要新的分析技術(shù).

本文旨在研究ROS2 多線程執(zhí)行器上運行的以有向無環(huán)圖（directed acyclic graph，DAG）為特征的并行任務的執(zhí)行行為，通過配置任務內(nèi)結(jié)點的調(diào)度順序，降低ROS2 上應用程序執(zhí)行時間.DAG 調(diào)度問題是2 個眾所周知的NP 難問題的組合：最小完工時間問題[7]和裝箱問題[8].其目標是找到一個最短的最長完工時間的調(diào)度順序.然而，在調(diào)度并行DAG 任務時，在某個時間點，該任務的許多頂點都符合執(zhí)行條件，并且數(shù)量多于可用核數(shù)，因此需要提出一種優(yōu)先級分配方法來指定這些頂點的執(zhí)行順序.但現(xiàn)有的調(diào)度算法，如文獻[9-12]在這種情況下沒有指定相關(guān)執(zhí)行順序.有的研究者通過求解一個具有分支定界[13-14]的整數(shù)規(guī)劃問題來找到執(zhí)行順序，但是無法解決大多數(shù)實際規(guī)模的問題.而啟發(fā)式方法（如最高級別優(yōu)先、最長工作時間、關(guān)鍵路徑和隨機優(yōu)先級[15]）為任務分配優(yōu)先級，屬于迭代型優(yōu)化算法.當問題規(guī)模很大時，大量的迭代搜索仍然會導致較大的計算耗時.此外，當問題發(fā)生變化時，通常需要重新搜索解決方案或調(diào)整啟發(fā)式規(guī)則以獲得更好的結(jié)果，但這會增加計算成本.

最近，工業(yè)界和學術(shù)界對尋找使用機器學習的自適應數(shù)據(jù)驅(qū)動調(diào)度算法的興趣激增.本文基于自適應學習的思路，針對ROS2 多線程執(zhí)行器和特殊的調(diào)度方式，提出了基于強化學習與蒙特卡洛樹搜索（Monte Carlo tree search，MCTS）的優(yōu)先級分配方法，通過在模擬平臺進行反復交互，逐步學習DAG 的拓撲結(jié)構(gòu)和執(zhí)行狀態(tài)，以及DAG 中每個頂點的運行時間和硬件資源使用情況.在此基礎(chǔ)上，本方法利用策略價值網(wǎng)絡在搜索樹中逐步探索DAG 中任務執(zhí)行先后順序，目的是最小化最大完工時間.

本文的主要貢獻包括3 個方面：

1）對ROS2 上任務的執(zhí)行方式進行了全面和深入的分析和研究，尤其對于多線程執(zhí)行器的調(diào)度機制進行了詳細建模.

2）針對ROS2 上特殊的調(diào)度機制，本文開發(fā)了一套用于模擬ROS2 執(zhí)行行為的模擬器，用于驗證和追蹤不同調(diào)度方法下程序的執(zhí)行狀態(tài)，并可提供詳盡的模擬結(jié)果.

3）提出了基于強化學習和蒙特卡洛樹搜索的ROS2 多線程執(zhí)行器以DAG 表征的任務優(yōu)先級配置方法.并對隨機生成的測試用例進行了分析，結(jié)果表明提出的優(yōu)先級配置方案相比基準測試方法能夠找到更優(yōu)的方案，進而縮短了任務的總執(zhí)行時間.

1 相關(guān)工作

為了提高ROS[16-17]的實時性能，研究者們已經(jīng)開展了大量工作.Casini 等人[2]對ROS2 執(zhí)行器進行了形式化建模和分析，特別是對單線程執(zhí)行器的調(diào)度行為進行了建模，為后續(xù)分析奠定了基礎(chǔ).Tang 等人[3]改進了響應時間分析技術(shù)并提出了優(yōu)先級分配方法以優(yōu)化響應時間.文獻[5]通過考慮實際執(zhí)行時間的差異并進一步探索 ROS2 中的調(diào)度特性來改進文獻[2]的問題.文獻[18]為ROS2 框架提出了一種基于鏈式結(jié)構(gòu)的新的優(yōu)先級驅(qū)動的調(diào)度器，并對提出的調(diào)度器進行了端到端延遲分析.目前，針對ROS2 系統(tǒng)的分析，現(xiàn)有工作都集中在單線程執(zhí)行器的分析上，而對于多線程執(zhí)行器的調(diào)度行為和優(yōu)先級的設置問題，還沒有相關(guān)工作研究.本文基于這個原因，開展了ROS2 多線程執(zhí)行器上的研究分析.

在多線程或者多核平臺上提高并行處理能力的主要方式是設計有效的任務調(diào)度算法.近年來，研究者對于DAG 系統(tǒng)進行了深入的分析，采用了不同的調(diào)度策略，包括全局調(diào)度[19-22]和聯(lián)合調(diào)度[9,23-24].例如，Zhao 等人[25]探索了DAG 結(jié)構(gòu)中的并行性和依賴關(guān)系，并基于并發(fā)提供者和消費者模型提出了優(yōu)先級分配方法和響應時間界限.Pathan 等人[26]提出了一種利用任務內(nèi)優(yōu)先級分配來提高資源利用率的方法，并利用準備時間和結(jié)點響應時間的思想來減少任務內(nèi)干擾.He 等人[27-28]開發(fā)并設計啟發(fā)式方法以確定并行任務的優(yōu)先級策略，提出了一種計算具有任意優(yōu)先級分配的DAG 任務響應時限的分析方法.還有很多關(guān)于在具有任務內(nèi)優(yōu)先級分配的多處理器平臺上的調(diào)度技術(shù)，他們的目標是減少端到端響應時間.文獻[15,29]考慮了DAG 靜態(tài)調(diào)度算法的優(yōu)先級分配.Kwok 等人[30]提出了一種基于任務圖的關(guān)鍵路徑，將任務圖分配給全連接多處理器的靜態(tài)調(diào)度算法.

Fig.1 Illustration of ROS2圖 1 ROS2 示意圖

通過在多個處理器上調(diào)度大量任務來最小化執(zhí)行時長被認為是一個NP 難問題.因此，為了獲得接近最優(yōu)的解決方案，研究者也在嘗試使用基于機器學習的啟發(fā)式方法.例如，文獻[31-32]使用機器學習來學習作業(yè)結(jié)點的近似最優(yōu)排序.但這些研究沒有考慮由DAG 定義的作業(yè)之間的依賴性，也沒有在分配執(zhí)行器和其他資源時利用DAG 拓撲.強化學習（reinforcement learning，RL）作為一種重要的機器學習算法，越來越受到關(guān)注.強化學習是一個與未知環(huán)境反復交互以獲得最優(yōu)解[33]的學習過程.基于強化學習的任務調(diào)度，既考慮短期價值，又考慮長期價值.因此，使用強化學習進行任務調(diào)度相比啟發(fā)式等算法，陷入局部最優(yōu)解的可能性降低.Lee 等人[34]提出了一種使用圖卷積網(wǎng)絡來處理復雜的相互依賴的DAG 任務結(jié)構(gòu)，并使用策略梯度方法開展了關(guān)于優(yōu)先級的調(diào)度策略的研究，以最小化DAG 任務的執(zhí)行時間.Decima[35]使用強化學習來選擇DAG 作業(yè)的排序以及執(zhí)行器的分配.但強化學習方法的好壞受到獎勵函數(shù)、特征提取、探索過程等多個因素的影響，例如強化學習的獎勵函數(shù)無法兼顧策略安全性與穩(wěn)定性，對于給連續(xù)任務分配優(yōu)先級的問題，策略梯度估計的方差會隨時間的推移被放大，并且策略的探索與輸出也難以預測和約束.本文受強化學習在調(diào)度任務的啟發(fā)，提出了基于強化學習的蒙特卡洛樹搜索方法，該方法不僅可以利用訓練的策略網(wǎng)絡指導搜索過程，提高樹搜索的性能，還可以通過擴展樹形結(jié)構(gòu)模擬各種可能的未來軌跡進行評估，從而選擇更有前景的方向來探索最佳策略，最終達到最小化任務執(zhí)行時間的目的.

2 背景介紹

本節(jié)主要介紹了ROS2 體系結(jié)構(gòu)以及其執(zhí)行流程和調(diào)度機制.

2.1 ROS2 體系結(jié)構(gòu)

如圖1 展示了ROS2 的體系結(jié)構(gòu)，ROS2 應用程序通常由節(jié)點組成，每個節(jié)點都是負責一個單一的用途模塊，多個節(jié)點相互組合協(xié)同，從而簡化了代碼結(jié)構(gòu)和提高了代碼重用性.節(jié)點是發(fā)布和接收消息的主體，使用發(fā)布—訂閱范例相互通信：節(jié)點在主題上發(fā)布消息，通過通信層數(shù)據(jù)分發(fā)服務DDS 將消息廣播給訂閱主題的節(jié)點.節(jié)點通過激活回調(diào)來處理每個消息，從而對傳入消息做出反應.為了部署ROS應用程序，需要將各個節(jié)點分布到主機，然后映射到操作系統(tǒng)進程.ROS2 中的執(zhí)行器用于協(xié)調(diào)操作系統(tǒng)進程中節(jié)點回調(diào)的執(zhí)行.ROS2 提供了2 個內(nèi)置的執(zhí)行器：一個是在單個線程中執(zhí)行回調(diào)的順序執(zhí)行器，另一個是在多個線程中處理回調(diào)的并行執(zhí)行器.

一個執(zhí)行器中同一節(jié)點內(nèi)的回調(diào)可以屬于某個回調(diào)組.回調(diào)組有2 種類型：互斥或可重入.在運行時，不同類型回調(diào)組中的回調(diào)根據(jù)特定規(guī)則進行調(diào)度（將在3.2 節(jié)介紹）.回調(diào)也可能屬于不同的節(jié)點，默認情況下，同一節(jié)點中未指定給任何回調(diào)組的回調(diào)被視為位于互斥回調(diào)組中.

Fig.2 The workflow of a thread in a ROS2 multi-threaded executor圖 2 ROS2 多線程執(zhí)行器中線程的工作流

2.2 多線程執(zhí)行器的調(diào)度方法

本節(jié)介紹了ROS2 Foxy Fitzroy[36]中多線程執(zhí)行器下的調(diào)度行為，該行為基于對源代碼和相關(guān)文檔的仔細檢查[1-2,37]，并通過使用跟蹤工具 ROS2_tracing[4]進行的大量實驗進行了驗證.

回調(diào)是程序設計者可以處理的最小調(diào)度實體.圖2 闡述了當回調(diào)被激活后，線程調(diào)度回調(diào)的工作流.執(zhí)行器中的所有線程都維護一個公共集wait_set，以記錄有可用消息的回調(diào).wait_set由互斥鎖mutex保護，線程在訪問wait_set之前必須持有鎖.也就是說，wait_set在任何時候最多只能由一個線程訪問和修改；否則，線程將被阻塞，等待鎖被釋放.當持有鎖時，線程通過固定順序搜索不同類別的回調(diào)來尋找要執(zhí)行的回調(diào).

正如在文獻[2-3,5]中介紹的那樣，回調(diào)的優(yōu)先級（即執(zhí)行時選擇執(zhí)行的順序）由2 個級別決定：1）回調(diào)類型.不同回調(diào)類型具有不同的優(yōu)先級，回調(diào)分為計時器、訂閱、服務和客戶4 種類型.總的來說，4 種回調(diào)類型的優(yōu)先級順序，如圖2 所示，依次是計時器、訂閱、服務和客戶.2）注冊順序.同一類型回調(diào)的優(yōu)先級取決于它們的注冊順序，較早注冊的回調(diào)具有更高的優(yōu)先級，這樣每個回調(diào)就靜態(tài)分配一個唯一的優(yōu)先級.在執(zhí)行回調(diào)之前，還要進一步查驗是否受到互斥影響.對于可重入模式的互斥組，可以直接進入執(zhí)行階段；而對于互斥回調(diào)組需要查驗標志位can_be_taken_from，以確定是否可以執(zhí)行.只有當can_be_taken_from=true 時，才能選擇屬于互斥回調(diào)組的回調(diào)；否則，線程將跳過此回調(diào)并繼續(xù)查驗下一個回調(diào).當選擇此組中的回調(diào)執(zhí)行時，標志設置為false，然后在回調(diào)執(zhí)行完成后設置為true.

一旦成功選擇回調(diào)，線程就會釋放鎖，并從就緒集中移除.之后，ROS2 通過判斷標志位yield_before_execute來決定所選回調(diào)是否可以立即執(zhí)行.如果設置yield_before_execute=true，線程將把處理器交付給操作系統(tǒng)，直到操作系統(tǒng)再次調(diào)度它；否則，線程開始以非搶占方式執(zhí)行回調(diào).在本文中，由于本文內(nèi)容不關(guān)注ROS2 和操作系統(tǒng)之間的交互，本文只考慮yield_before_execute=false 的情況，這也是默認配置.

如果在查詢過程中，沒有發(fā)現(xiàn)可以執(zhí)行的回調(diào)，那么線程將進入更新階段（此時仍然持有鎖）.在經(jīng)過一些列初始化后，如在rcl層和rmw層的句柄重置和實體收集等，之后等待新的消息到來并更新wait_set（如果有可更新的）.在等待函數(shù)wait_for設置中，還可以通過設置一定的時間限制timeout（默認情況無等待時長約束），即如果到達一定時間仍無法更新到新的回調(diào)，則線程將釋放鎖并變?yōu)榭臻e.

3 任務執(zhí)行模型

本節(jié)將介紹抽象出來的ROS2 多線程執(zhí)行器的相關(guān)行為的模型.

3.1 負載模型

描述并行任務最通用的模型之一是有向無環(huán)圖模型，該模型允許將任務表示為一系列子任務，這些子任務描述了潛在的并行計算，以及表示子任務的執(zhí)行順序的約束情況.本文考慮在具有M個相同核的系統(tǒng)上執(zhí)行應用程序.程序以有向無環(huán)圖G=(V,E)的形式表示，其中V表示回調(diào)集合，E∈V×V表示受到執(zhí)行約束的回調(diào)對之間的邊的集合.每個回調(diào)vi執(zhí)行需要一定的時間，其最壞執(zhí)行時間（worst case execution time，WCET）用ei表示.一條邊(vi,vi′)表示回調(diào)vi和vi′的優(yōu)先關(guān)系，即vi′只能在vi執(zhí)行完畢后才開始執(zhí)行.沒有傳入（傳出）邊的頂點稱為源點（匯點）.在不喪失一般性的情況下，本文假設G只有一個源點（表示為vsrc）和一個匯點（表示為vsink）.在G有多個源點或匯點的情況下，可以添加一個具有零WCET 的虛擬源點或匯點，以符合本文的假設.另外，每個回調(diào)屬于一個唯一的回調(diào)組，本文使用G(vi)表示vi所屬組的索引，如果G(vi)=0，表示vi屬于可重入組.

路徑λ=[vλ1,vλ2,…,vλk]是一個有限的回調(diào)序列，其中(vλi,vλi+1)∈E，i∈{1,2,…,k-1}.如果路徑同時包含源點和匯點，則稱為完整路徑.路徑長度是路徑中結(jié)點的執(zhí)行時間之和，即完整路徑中路徑長度最長的路徑稱為關(guān)鍵路徑，本文使用L表示關(guān)鍵路徑的工作負載，即僅關(guān)鍵路徑中結(jié)點的WCET之和.在執(zhí)行過程中，G會釋放無限序列的實例.周期 T是 G的2 個連續(xù)實例的釋放時間之間的最小間隔.DAG有一個相對的最后期限D(zhuǎn)，在時刻r釋放的G實例必須在時刻r+D之前完成，也就是說最長路徑的工作負載之和L≤r+D，在本文中主要考慮了滿足這種約束條件下的任務執(zhí)行模式，稱為可調(diào)度的G.L的負載之和為本文優(yōu)化的DAG 總執(zhí)行時間，即最長完工時間makespan.

3.2 調(diào)度模型

在運行時，G中源點后的回調(diào)實例首先被釋放，而G中的其他回調(diào)實例將在前任實例的輸入消息可用時才被釋放.被釋放的回調(diào)vi的實例能否執(zhí)行還取決于回調(diào)組的情況：

1）vi屬于互斥回調(diào)組.vi所在的回調(diào)組中沒有回調(diào)（包含vi）的實例正在執(zhí)行時，表示處于準備就緒狀態(tài)；否則，vi將被阻塞.

2）vi屬于可重入回調(diào)組.vi在釋放后始終處于就緒狀態(tài).

執(zhí)行器維護一個就緒集合Ω，它記錄了可以執(zhí)行的就緒回調(diào).執(zhí)行器可以選擇Ω中的就緒回調(diào)進行執(zhí)行.從上面的描述中可以看到，同一互斥回調(diào)組中回調(diào)的回調(diào)實例不能并行執(zhí)行，而可重入回調(diào)組中回調(diào)的多個回調(diào)實例可能并行執(zhí)行.另外，回調(diào)實例準備就緒后不會立即添加到Ω.相反，只有在Ω中沒有符合條件的回調(diào)且線程空閑時，才能將就緒回調(diào)實例添加到Ω.此外，當更新Ω時，首先設置Ω=?，然后將所有當前就緒的回調(diào)實例添加到Ω.即在同一時刻（通常稱為輪詢點）Ω中加入了一組回調(diào)實例.

在執(zhí)行階段，M個線程逐個選擇Ω中符合條件的回調(diào)實例，并以非搶占方式執(zhí)行.而選擇合格回調(diào)實例的順序取決于它們的優(yōu)先級.每個回調(diào)都有一個固定且唯一的優(yōu)先級，其所有實例都繼承該優(yōu)先級.當選擇執(zhí)行回調(diào)實例時，回調(diào)實例將從Ω中刪除.

圖3 闡述了使用2 個線程在ROS2 系統(tǒng)上運行DAG 程序執(zhí)行的示例.該程序由7 個回調(diào)組成（源點和匯點不考慮在內(nèi)），圓形符號表示程序中的回調(diào)，箭頭表示回調(diào)之間的依賴關(guān)系，其中回調(diào)v4，v6，v7屬于同一互斥回調(diào)組，其他回調(diào)屬于可重入回調(diào)組.所有回調(diào)的優(yōu)先級和最壞情況執(zhí)行時間如圖3（b）所示.向上菱形符號表示DAG 實例釋放時刻，釋放周期為6，其中表示第i個回調(diào)的第j個實例.我們通過設置2 種不同的優(yōu)先級來展示優(yōu)先級對DAG 任務執(zhí)行的影響，其中優(yōu)先級1 的結(jié)果如圖3（c），優(yōu)先級2 的結(jié)果如圖3（e）.對應的每個輪詢點的Ω中的回調(diào)實例如圖3（d）（f）所示，集合的內(nèi)容由任務依賴關(guān)系和線程更新Ω時刻所決定.例如，在時刻 2執(zhí)行完后線程T1空閑，且此時Ω為空，則線程T1將就緒的和更新到Ω.比較2 種優(yōu)先級配置的運行結(jié)果可發(fā)現(xiàn)，盡管只是對v2和v4優(yōu)先級進行了互換就導致了整個系統(tǒng)由可調(diào)度變成了不可調(diào)度的情況，觀察圖3（c）（e）可發(fā)現(xiàn)，DAG 中最長路徑的一次實例的執(zhí)行時長也由 6變成了9.原因就是在時刻2，在優(yōu)先級2 的配置下，v2先于v4執(zhí)行，又因互斥組的原因?qū)е铝藇6和v7的延后執(zhí)行.這說明合理設置優(yōu)先級以及DAG 中回調(diào)的約束關(guān)系對程序運行和執(zhí)行時長的重要性.

Fig.3 Example of task scheduling under ROS2 multithread executor圖 3 ROS2 多線程執(zhí)行器下的任務調(diào)度示例

4 提出的方法

本節(jié)描述了優(yōu)先級配置方法，包括馬爾可夫決策過程（Markov decision process，MDP）模型和帶有RL智能體的MCTS 算法.圖4 說明了整體架構(gòu)及其主要組件.該方法遵循通用的強化學習框架，關(guān)鍵組件為環(huán)境狀態(tài)、動作、獎勵和模擬環(huán)境.智能體按照典型的Actor-Critic 算法執(zhí)行訓練，并結(jié)合MCTS 方法計算得到最優(yōu)方案.執(zhí)行過程從初始化狀態(tài)開始，根據(jù)跟蹤的文件數(shù)據(jù)1 獲取下一時刻的環(huán)境狀態(tài)，并以簡明的形式提取狀態(tài)特征2，并反饋到RL 智能體以生成可行的動作結(jié)果3，最后，計算該動作的獎勵4并返回給智能體進行訓練.由于大多數(shù)調(diào)度任務的執(zhí)行性能指標只能在整個回調(diào)序列被調(diào)度后才能計算，因此在獎勵計算期間，本方案將每個單獨動作的中間獎勵保持為0，只計算完成回調(diào)序列中的最后一項回調(diào)后的最終獎勵.一旦安排了整個DAG 回調(diào)執(zhí)行序列，本方案就會建立一個包含優(yōu)先級特征的執(zhí)行軌跡.

4.1 馬爾可夫決策過程

本節(jié)從馬爾可夫決策過程的角度討論了在ROS2系統(tǒng)下DAG 的執(zhí)行方式.一般來說，MDP 具有一組狀態(tài)、一組動作、獎勵函數(shù)和狀態(tài)轉(zhuǎn)移概率.

1）狀態(tài).首先，本文方法封裝了當前時刻t、核的工作狀態(tài)以及回調(diào)間的互斥約束關(guān)系.為了通過順序選擇來調(diào)度DAG 任務，狀態(tài)還需要關(guān)于隨時間演變的子任務分區(qū)的信息，即處于該狀態(tài)下滿足當前依賴關(guān)系的就緒回調(diào)集合Ω和已經(jīng)執(zhí)行完的回調(diào)集合.而這些狀態(tài)信息是通過模擬器按ROS2 的執(zhí)行策略和DAG 約束條件，隨時間變化模擬得到的.

Fig.4 Frame diagram of reinforcement learning-based priority assignment method圖 4 基于強化學習的優(yōu)先級分配方法框架圖

2）動作.動作行為表示時刻t在就緒集合Ω中選擇一個回調(diào)進行執(zhí)行.本文將擁有N個回調(diào)程序的動作，選擇操作a編碼為一個離散空間{0,1,…,N}，當a=m時表示選擇第m個回調(diào)，如果滿足約束條件，則將回調(diào)掛載到空閑核上，此動作并不占用實際的執(zhí)行時間.如果a=0，則表示對掛載的回調(diào)進行處理，將占用核上資源并產(chǎn)生執(zhí)行時間.

3）獎勵.為了學習得到最合理的優(yōu)先級配置，以最小化DAG 工作流完成時間作為最優(yōu)策略獎勵參數(shù).我們將程序完成時的總累積獎勵設置為負的工作流完成時間，即vi的-makespan.而在任務未完成時的動作選擇獎勵為0.因此，最大化強化學習模型的回報相當于最小化工作流完成時間.獎勵函數(shù)的定義為

4）轉(zhuǎn)移概率.在MDP 中，過渡狀態(tài)是確定性的，即對于一個狀態(tài)和動作，下一個狀態(tài)是沒有隨機性的.這是因為調(diào)度操作不執(zhí)行任務，它只影響調(diào)度策略并更改任務的排列（優(yōu)先級順序）.當采用強化學習處理大規(guī)模組合優(yōu)化問題時，這種設置很常見[38].

4.2 MCTS 過程

MCTS 是一種最佳優(yōu)先搜索算法，由Coulom 在2006 年引入[39]，用于在圍棋中找到好的決策，但也可用于不同的MDP，如集群資源調(diào)度[35]、生產(chǎn)調(diào)度[40].使用MCTS 可以有效地搜索決策的空間，MCTS 由4個部分組成：選擇、擴展、模擬和回溯.在本文中，我們使用訓練好的策略網(wǎng)絡來指導MCTS 過程，即在搜索過程中使用經(jīng)過強化學習訓練的智能體給出最有希望的動作，在縮小搜索空間的同時使MCTS 可以更有效地找到任務的執(zhí)行順序.具體步驟有5 個：

1）選擇階段.在算法的初始階段，蒙特卡洛樹中只有一個初始結(jié)點.這一步從根結(jié)點開始，逐樹探索下一個最有希望的子結(jié)點，以保持探索和利用之間的平衡.一般情況下，使用上置信界（upper confidence bound，UCB）作為每個結(jié)點優(yōu)劣的評價標準，即

2）擴展階段.如果選擇最有希望的結(jié)點不是終止結(jié)點，則通過一個未探索的動作來擴展搜索樹.在這個階段，可用的子結(jié)點是就緒任務隊列中的一組動作或處理動作（a=0）.

3）模擬階段.在經(jīng)典的MCTS 方法中，擴展后的搜索樹中添加了新結(jié)點，選擇一個新結(jié)點作為模擬的開始，其中移動一般由隨機策略選擇，并進行快速模擬到游戲結(jié)束及獲得結(jié)果.然而，大量的決策維度導致搜索算法開銷很大，無法獲得有希望的結(jié)果.所以本文使用經(jīng)過訓練的強化學習智能體來替換隨機策略.

4）回溯階段.在模擬結(jié)束時，根據(jù)模擬的makespan結(jié)果，從葉結(jié)點到根結(jié)點的訪問路徑上的所有結(jié)點，使用反向傳播方式更新當前動作序列的值.對于每個結(jié)點，該值被更新為當前負makespan和新makespan的最大值，表示為

5）迭代預算.MCTS 算法重復上面4 個步驟來增加搜索樹的規(guī)模，直到計算資源耗盡.最后，MCTS 將選擇導致最高可能值的操作.受文獻[41]啟發(fā)，迭代次數(shù)被設置為資源預算.值得注意的是，本方案還為每個級別的預算設計了一個適當?shù)乃p函數(shù)，在DAG 調(diào)度問題中，當向下遍歷搜索樹時，搜索空間呈指數(shù)下降.因此，可用的決策減少，然后隨著樹的深入，將迭代的上限設置為

其中di是樹的當前深度，binitial和bmin分別表示初始和最小迭代預算.

5 實驗和評估

本節(jié)評估了提出的優(yōu)先級分配方法，通過生成隨機任務集和使用離散事件模擬器模擬多線程執(zhí)行器的執(zhí)行來評估本文設計的方法.

5.1 實驗參數(shù)

該實驗通過隨機生成的DAG 任務進行評估，任務集和測試集生成遵循在各種現(xiàn)有可調(diào)度性分析論文中使用的相同程序，例如文獻[42-43]，以便在可調(diào)度性測試和模擬結(jié)果之間進行比較.生成各種DAG的具體輸入?yún)?shù)有：1）回調(diào)數(shù)N；2）線程數(shù)M；3）DAG的長度L；4）結(jié)點的最大出度maxout；5）結(jié)點的最大入度maxin；6）DAG 的形狀參數(shù) α；7）DAG 的正則性參數(shù)β；8）任務執(zhí)行時間e；9）DAG 中的互斥組個數(shù)上限g；10）互斥組中任務個數(shù)上限u.在實驗中，這些參數(shù)的值是從給定的集合中均勻采樣得來的，其中N∈{5,10,20,30,40,50}；M∈{2,3,4}；maxout=3；maxin=3；α ∈{0.5,1.0,1.5} ；β ∈{0.0,0.5,1.0,2.0}；每個回調(diào)的最壞執(zhí)行時間e在[1,100]隨機采樣；互斥組個數(shù)在{0,1,2,…,g}隨機選擇，g=N/10；互斥組內(nèi)回調(diào)個數(shù)在{1,2,…,u}隨機選擇，其中u=（N/10）+1.通過上述設置，可以獲得大量具有不同屬性的任務流，從而防止對特定調(diào)度方法的偏見.

Actor 網(wǎng)絡和Critic 網(wǎng)絡使用相同的配置，即寬度均為128 網(wǎng)絡的隱藏層神經(jīng)網(wǎng)絡.使用了tanh 激活功能.softmax 函數(shù)為Actor 網(wǎng)絡的輸出層中的動作空間生成一系列概率.受近端策略優(yōu)化（proximal policy optimization，PPO）[44]良好性能的影響，本文應用PPO來訓練調(diào)度器.Actor 網(wǎng)絡和Critic 網(wǎng)絡的學習率分別設置為3×10-4和1×10-3，折扣率γ=0.99，裁剪范圍系數(shù)為0.2.訓練數(shù)據(jù)和測試數(shù)據(jù)來自由隨機參數(shù)生成的1 000 個DAG.在MCTS 實現(xiàn)中，本文使用預先訓練的PPO 智能體作為指導，binitial=100和bmin=10.

所有實驗都是基于Python 3.6.13，torch 1.7.0 和gym 0.19.0 環(huán)境實施，并在具有128 GB 內(nèi)存的 Intel?Xeon?Bronze 3104 CPU@1.70 GHz 和具有CUDA 11.1 NVIDIA geforce rtx 3090 GPU 的ubuntu 18.04.6 LTS 系統(tǒng)上進行訓練和測試.

5.2 基準測試方法

對于本文的多線程執(zhí)行器模型，DAG 任務在M個同構(gòu)處理器上執(zhí)行，則核數(shù)M和回調(diào)數(shù)N設置為數(shù)據(jù)規(guī)格，并包含在測試數(shù)據(jù)集中.也就是說，在測試階段，從數(shù)據(jù)集采樣的每個DAG 任務被配置在M個處理器的系統(tǒng)上運行.本文的模型旨在最小化單個DAG 任務的完成時間.因此，本文通過模擬器環(huán)境測量了各個調(diào)度方法的最長完工時間并將其用作評估指標.比較的方法有：

1）隨機方法（Random）.在動作空間中隨機采樣動作，在存在空閑核的情況下，如果采樣的動作無效，如受到回調(diào)間約束關(guān)系和互斥關(guān)系而無法執(zhí)行，則重新選擇動作.如果發(fā)現(xiàn)此時沒有空閑的核掛載該就緒回調(diào)，則將當前動作變更為0.

2）短任務優(yōu)先方法（shortest job first,SJF）.該方法首先在就緒集合Ω中根據(jù)最壞執(zhí)行時間按降序?qū)卣{(diào)進行排序，然后選擇第1 個回調(diào)作為下一個動作.同隨機方法，如果發(fā)現(xiàn)此時沒有空閑的核掛載在就緒回調(diào)，則將當前動作變更為0.因為增加了核的狀態(tài)判斷，所以本方法相比于隨機選擇動作的方法，在對空閑核的利用上會表現(xiàn)得更有優(yōu)勢.

3）PPO.使用PPO 算法訓練的網(wǎng)絡，根據(jù)環(huán)境狀態(tài)選擇下一個可執(zhí)行的回調(diào).

4）沒有PPO 的MCTS（MCTS_N）.為了驗證強化學習對MCTS 調(diào)度程序的關(guān)鍵影響，分別對有和沒有PPO 智能體的MCTS 進行了消融實驗.

5.3 模擬環(huán)境

為了評估本文提出的方法，本工作需要搭建與執(zhí)行環(huán)境交互的平臺.雖然可以直接以ROS2 真實系統(tǒng)作為交互環(huán)境，但由于ROS2 的性能依賴于系統(tǒng)的調(diào)度策略且受限于系統(tǒng)資源狀態(tài)，如果直接在ROS2系統(tǒng)中訓練會存在訓練時間長以及參數(shù)測量不準等潛在問題.為了解決此問題，本文實現(xiàn)了一個基于ROS2 執(zhí)行策略的gym[45]調(diào)度模擬器，模擬器對于DAG 調(diào)度方法至關(guān)重要，為智能體和環(huán)境之間的交互提供平臺.該模擬器可以模擬M個同構(gòu)處理器的ROS2 系統(tǒng)執(zhí)行行為，并精確計算每個DAG 任務按給定優(yōu)先級順序下的最大完工時間.回調(diào)序列和執(zhí)行器的設置參數(shù)被輸入至模擬器，以模擬ROS2 處理平臺如何執(zhí)行回調(diào).在初始化步驟，初始化回調(diào)序列、執(zhí)行器狀態(tài)和就緒回調(diào)集合等.然后，按優(yōu)先級對就緒回調(diào)進行排序.模擬器從就緒回調(diào)逐個選擇回調(diào)實例，并根據(jù)所選回調(diào)實例的約束情況決定執(zhí)行步驟，如掛載到相應的空閑核上并記錄此時狀態(tài)等.最后，模擬器根據(jù)核上回調(diào)的執(zhí)行時長，并按降序排列，更新模擬時間以確定下一個調(diào)度時刻，并更新核的工作狀態(tài).模擬器重復上述過程，直到所有作業(yè)都分配給執(zhí)行器，最后算出DAG 任務的最大完工時間.

5.4 實驗評估與分析

圖5 展示了優(yōu)先級分配方法與基準測試在不同DAG 尺寸下隨機選取的100 組測試集數(shù)據(jù)的最長完工時間情況.表1 展示了增加核數(shù)區(qū)分后的實際平均結(jié)果.

Fig.5 Performance of makespan in different DAG sizes圖 5 不同DAG 尺寸下的最大完工時間性能

從表1 可以看出，本文所提出的優(yōu)先級分配方法明顯優(yōu)于其他所有方法，且隨著回調(diào)數(shù)N和核數(shù)M的增加效果更加明顯.其中由于隨機方法選擇動作的不確定性，對核的利用不佳，執(zhí)行時長最長且波動范圍最大.SJF 直接在就緒集合選擇回調(diào)，再選擇執(zhí)行動作，所以整體來說核的利用率更高，運行時間相對較短.PPO 的執(zhí)行時間略高于SJF，這是因為雖然本文對DAG 約束關(guān)系進行了表征，但仍然在某些情況不能完全涵蓋，如雖然當前存在空閑核，但由于互斥原因，在Ω集合中選擇的回調(diào)無法執(zhí)行，這給PPO的訓練過程帶來了偏差，而且隨著核數(shù)減少，復雜的約束關(guān)系將變得更加明顯.

Table 1 Average makespan with Different Methods表 1 不同方法的平均最長完工時間

加入MCTS 后，MCTS_N 和MCTS 方法的最長完工時間makespan好于Random,SJF,PPO 三種方法.通過消融實驗，也說明了PPO 在幫助MCTS 快速搜索相關(guān)結(jié)點的前提下，帶來了更好的計算結(jié)果，并且隨著結(jié)點數(shù)越多，核數(shù)越多，可選擇的動作越多，可操作的空間越豐富時，其效果越明顯.除此之外，本文以核數(shù)為4 的ROS2 模擬系統(tǒng)為例，對提出方法的求解過程帶來的時間開銷進行了測量.本文隨機選取了測試集中DAG 結(jié)點數(shù)為30 的50 個組進行測量，其中PPO 測試的平均makespan為238.59，平均時間開銷為843 ms.對不同資源限制配置下的MCTS 和MCTS_N 計算時間也進行了測量，如表2 所示.

Table 2 Execution Time Analysis for MCTS Method表 2 MCTS 方法執(zhí)行時間分析

從表2 可以看到MCTS 在PPO 的幫助下，雖然同樣配置下的運行時間要高于MCTS_N，但makespan的結(jié)果要優(yōu)于MCTS_N，而且隨著binitial的增加，makespan效果趨于更好的結(jié)果.橫向比較這2 種方法，MCTS在binitial=10和bmin=5時就能達到很好的效果，運行時間和運行結(jié)果都好于在更高迭代預算情況下MCTS_N的結(jié)果.這說明引入的神經(jīng)網(wǎng)絡有效地指導了MCTS的探索過程，提高了MCTS 的執(zhí)行效率.

本文還對2 個核10 個回調(diào)的DAG 進行了針對性的案例研究：在設置優(yōu)先級時，由于ROS2 采用的是在輪詢點一次性放入多個就緒回調(diào)到Ω的方式，并且只有Ω為空時線程才能再次更新的機制.優(yōu)先級設置的分析可以簡化為只考慮在2 次更新階段之間的時間段能夠進入Ω的回調(diào)的優(yōu)先級關(guān)系.但需要注意的是，不同的優(yōu)先級設置，會導致Ω中的回調(diào)在更新點時刻并不是一成不變的.通過實驗觀察到的現(xiàn)象是：1）如果Ω中回調(diào)均為可重入模式，本文提出的方法會傾向于將執(zhí)行時長最長的回調(diào)置于較高優(yōu)先級，然后依次類推.其目的是盡量防止執(zhí)行時間較長的回調(diào)被阻塞.2）如果Ω中存在屬于互斥組的回調(diào)，方法會傾向于將屬于回調(diào)組的且執(zhí)行時間最長的回調(diào)置成較高的優(yōu)先級.盡量將可能帶來后續(xù)影響的任務提前執(zhí)行，以提高并行的概率，防止如圖3（e）所示的互斥影響.雖然在本文中沒有進一步研究這種規(guī)律的深層原因，但這些發(fā)現(xiàn)可以通過形式化的方式進行進一步論證，這樣不僅可以使基于強化學習的方法更具有可解釋性，也可以從實踐角度作為一個較好的優(yōu)先級設計技巧去簡化復雜的調(diào)度分析過程.在未來工作中，我們將進一步分析和解決這個問題.

6 結(jié) 論

本文提出了一種基于強化學習和MCTS 的在ROS2 調(diào)度機制下的優(yōu)先級配置方法，即設計回調(diào)的執(zhí)行順序.該方法通過使用PPO 訓練策略價值網(wǎng)絡指導MCTS 方法尋找最佳的方案以最小化DAG 形式表示的回調(diào)集合的最大完工時間.基于這種方法，在深入研究了ROS2 執(zhí)行模式前提下，搭建了模擬平臺，并通過實驗驗證了本文所提出的方法相比基準測試方法更具優(yōu)勢.在未來的工作中，將專注于優(yōu)化所提出的方法和進一步擴展，例如使用圖卷積神經(jīng)網(wǎng)絡表征環(huán)境狀態(tài)，支持單個DAG 擴展到支持多個DAG 的分析，優(yōu)化DAG 中回調(diào)組的設置.

作者貢獻聲明：紀東提出了算法思路和實驗方案并撰寫論文；魏陽杰和王義提出指導意見；李宇溪修改論文.