自主望遠(yuǎn)鏡調(diào)度算法探索

1、自主望遠(yuǎn)鏡調(diào)度算法探索 李建 2011-11-12 貴陽Outline調(diào)度系統(tǒng)的作用影響望遠(yuǎn)鏡調(diào)度的因素調(diào)度方法的分類“分配調(diào)度”方法評(píng)分因素及計(jì)算公式“分配調(diào)度”流程關(guān)于調(diào)度系統(tǒng) 調(diào)度系統(tǒng)是自主望遠(yuǎn)鏡的重要部分 決定“自主化的程度” 觀測任務(wù)安排；資源分配均衡 觀測任務(wù)調(diào)度過程中，最小調(diào)度單元稱為作業(yè)（job）影響望遠(yuǎn)鏡調(diào)度的因素 外部因素 內(nèi)部因素影響望遠(yuǎn)鏡調(diào)度的因素 外因：觀測時(shí)影響觀測質(zhì)量的客觀因素 天氣：雨、雪、霧、風(fēng) 角度：緯度越高，穿過大氣層的路徑越小，大氣層產(chǎn)生的散射和變形越小，觀測結(jié)果最佳 月相 影響望遠(yuǎn)鏡調(diào)度的因素 內(nèi)因：影響作業(yè)隊(duì)列順序的內(nèi)

2、部因素主要是“效率”和“政策” “效率”因素：優(yōu)先處理天體目標(biāo)在相同天區(qū)的觀測任務(wù)，合并相似的觀測任務(wù)，只執(zhí)行一次觀測計(jì)劃，以減少望遠(yuǎn)鏡的回轉(zhuǎn)時(shí)間 “政策”因素：包括允許管理員繞過作業(yè)隊(duì)列，并優(yōu)先得到望遠(yuǎn)鏡的觀測響應(yīng)調(diào)度方法的分類調(diào)度方法分類 四個(gè)不同的調(diào)度類型（ Thomas Granzer 2004）: 1)queue scheduling 隊(duì)列調(diào)度 每個(gè)觀測階段為一個(gè)jobs清單，由robot順序執(zhí)行。 不可預(yù)知的延遲（如聚焦時(shí)間、快速定向時(shí)間、天氣因素）就會(huì)使jobs丟失觀測。 不能實(shí)時(shí)插入jobs，不能改寫剩余的調(diào)度隊(duì)列。調(diào)度方法分類 2）Critical Path Scheduli

3、ng 關(guān)鍵路徑調(diào)度 這是一個(gè)尊重所有job依賴關(guān)系依賴關(guān)系的調(diào)度方式，確保最少的依賴的job先調(diào)度，多依賴的job后調(diào)度。天文觀測很少有這樣的依賴關(guān)系，很少使用這種方法，這不是一個(gè)合適的調(diào)度方法。3）Optimal Scheduling 優(yōu)化調(diào)度 這種方法需要大量的計(jì)算，來建立一個(gè)合適的時(shí)間表，以創(chuàng)造一個(gè)最好的調(diào)度方式。但是，預(yù)先算好的調(diào)度表還是不能對(duì)不可預(yù)知的變化作出反應(yīng)。調(diào)度方法分類 4）Dispatch Scheduling 分配調(diào)度 這種類型的調(diào)度器為每個(gè)作業(yè)（job）計(jì)算出一個(gè)分?jǐn)?shù)（score），放在調(diào)度池（pool）中，每次選擇分?jǐn)?shù)最高的執(zhí)行。 這種方法解決了不可預(yù)知的因素所帶來的

4、影響，因?yàn)檎{(diào)度不是固定的。 然而，由于調(diào)度的不固定，預(yù)知robot下一步要做什么是很困難的。而且需要一個(gè)能夠改變優(yōu)先級(jí)的評(píng)分算法（scoring algorithm）。調(diào)度方法分類 Liverpool Telescope、STELLA、BRT項(xiàng)目采取了“分配調(diào)度”的方法 Hubble telescope 由于有一個(gè)更好的可以預(yù)見的環(huán)境，使用了“優(yōu)化調(diào)度”的方法 改進(jìn)的調(diào)度方式： 環(huán)狀隊(duì)列，雙隊(duì)列，多種調(diào)度方式結(jié)合關(guān)于“分配調(diào)度”方式分配調(diào)度程序需求 分配調(diào)度程序應(yīng)滿足以下要求： 所有等待處理的job，必須進(jìn)行每隔幾分鐘進(jìn)行評(píng)估、定分 每個(gè)job必須結(jié)合多種因素（factor）的評(píng)價(jià)、計(jì)算出唯一

5、的一個(gè)分?jǐn)?shù) 因素有加權(quán)值，反應(yīng)因素的重要程度。允許管理員控制每個(gè)因素的加權(quán)值 軟件以模塊化的方式來編寫，這樣在新增因素、刪除舊的因素時(shí)scheduler能及時(shí)響應(yīng)分配調(diào)度程序需求 當(dāng)robot要求job時(shí)，scheduler不能有延遲 -job必須立刻準(zhǔn)備好 在調(diào)度池內(nèi)，設(shè)置為immediate標(biāo)志的job，必須優(yōu)先考慮分配望遠(yuǎn)鏡時(shí)間，不論其分?jǐn)?shù)有多少 scheduler應(yīng)該準(zhǔn)許手動(dòng)模式加入特殊事件，系統(tǒng)管理員將分配job的觀測時(shí)間。需要進(jìn)行評(píng)分的因素（Score Factors） Score Factors 一些被確定為影響job的總體評(píng)分的因素： job目標(biāo)達(dá)到天空中最高點(diǎn)的時(shí)刻 job目

6、標(biāo)落入地平的時(shí)刻 job間的相對(duì)距離（是否可以和其它觀測任務(wù)合并） job預(yù)先設(shè)置的優(yōu)先級(jí)值 job要求的觀測時(shí)間 job一直在等待觀測的時(shí)間量Score Factor的計(jì)算公式Score Factor的計(jì)算公式Window merit(觀測窗口因素值)一個(gè)計(jì)算score的示例布爾測試 對(duì)一個(gè)job執(zhí)行scheduling算法以前，可以執(zhí)行一系列布爾測試，可以減少計(jì)算時(shí)間 計(jì)算出目標(biāo)的高度和方位角，是否滿足？ Job是否過了觀測時(shí)間？ 目標(biāo)是否符合相機(jī)的操作范圍？ 是否以正常（非特殊事件）的模式工作？分配調(diào)度流程示例上一次觀測上一次觀測任務(wù)完成任務(wù)完成從從request pool提提取一條任務(wù)請(qǐng)求取一條任務(wù)請(qǐng)求通過通過bool測試？測試？NY第第1個(gè)評(píng)個(gè)評(píng)分模塊分模塊第第2個(gè)評(píng)個(gè)評(píng)分模塊分模塊第第N個(gè)評(píng)個(gè)評(píng)分模塊分模塊分?jǐn)?shù)加權(quán)求分?jǐn)?shù)加權(quán)求和和完成所完成所有請(qǐng)求？有請(qǐng)求？選取最高分選取最高分的任務(wù)執(zhí)行的任務(wù)執(zhí)行NYScheduler小結(jié) 考慮到上述所有因素，調(diào)度過程是一項(xiàng)復(fù)雜的任務(wù)。完全考慮到所有的因素，和它們之間的沖突是不實(shí)際的； Scheduler是保證資源公平的分配一個(gè)最優(yōu)化的解決方案； 是各方面因素的妥協(xié)的結(jié)果。 普