LMT NEW PBS作業(yè)調(diào)度運算系統(tǒng)對多隊列作業(yè)的運算

章魚小丸子LIC

              LMT NEW PBS作業(yè)調(diào)度運算系統(tǒng)對多隊列作業(yè)的運算
    在網(wǎng)格環(huán)境下,如何將分布的計算資源整合起來,根據(jù)不同用戶提交的作業(yè)請求,充分利用網(wǎng)格中的資源,合理調(diào)度作業(yè),提高系統(tǒng)的利用率,一直是網(wǎng)格計算要解決的核心問題。作業(yè)調(diào)度系統(tǒng)正是解決以上問題的功能部件,其基本功能是接受用戶的作業(yè)請求,根據(jù)用戶作業(yè)特征,對作業(yè)隊列進行排序,從全局資源池中選取合適的資源,對作業(yè)進行資源分配,并監(jiān)督用戶作業(yè)的執(zhí)行�？梢娋W(wǎng)格作業(yè)在真正執(zhí)行前要進行一系列的處理,比如請求解析、資源選擇、作業(yè)調(diào)度和最終提交,目前的大多數(shù)作業(yè)調(diào)度系統(tǒng)一般采用先來先服務( First2Come, First2Service,FCFS)策略,這就帶來了以下缺點:
1)缺乏靈活性,無法滿足用戶的某些特殊需求;
2)缺乏統(tǒng)一的組織管理,作業(yè)在進行處理的過程中如果出錯,將無法找到其準確的位置,從而影響到進一步的處理。
    為此,可以把處理作業(yè)的過程按照功能劃分成若干個階段,每個階段對應一個處理隊列,這些隊列首尾相連,就構成了一個多隊列結構;另外,為了便于對作業(yè)的管理,可以設置一個控制中心,它負責將用戶的作業(yè)請求封裝成一個對象,同時可以靈活地控制作業(yè)對象在各個處理隊列的入隊和出隊等操作,以上就是多隊列作業(yè)處理環(huán)境的設計思想。
1　作業(yè)處理環(huán)境的設計
1. 1　作業(yè)處理環(huán)境的框架結構
    作業(yè)處理環(huán)境由作業(yè)控制中心和多隊列結構構成,在處理作業(yè)的過程中,作業(yè)處理環(huán)境還需要與網(wǎng)格服務系統(tǒng)中的其他服務和數(shù)據(jù)庫進行交互。

                            圖1　作業(yè)處理環(huán)境框架
1. 2　作業(yè)處理環(huán)境的組成
1. 2. 1　作業(yè)控制中心
作業(yè)控制中心由作業(yè)控制器、作業(yè)對象工廠和作業(yè)對象組成。
作業(yè)控制器( Job Controller) 　作業(yè)控制器有三個功能:
一是接收用戶的調(diào)用請求,包含作業(yè)提交、控制、查詢等;
二是初始化作業(yè)處理環(huán)境,即啟動多隊列結構中的每個處理隊列所對應的線程;
三是協(xié)調(diào)、控制作業(yè)對象工廠和處理隊列處理用戶作業(yè)請求。
    作業(yè)對象工廠(Job Object Factory) 　負責創(chuàng)建、管理作業(yè)對象。包括對作業(yè)對象的查詢、銷毀以及作業(yè)對象的持久化與恢復等。作業(yè)對象的持久化是指將作業(yè)運行時信息封裝在作業(yè)對象里,通過序列化將其存儲在數(shù)據(jù)庫中。系統(tǒng)通過作業(yè)對象的持久化與恢復,適時保存作業(yè)信息,支持作業(yè)的檢查點恢復。作業(yè)對象工廠的設計借鑒了編程模式中的工廠模式[ 5 ]。
作業(yè)對象(Job Object) 　為了方便對作業(yè)請求進行處理,可以將作業(yè)請求封裝成一個對象,一個作業(yè)對象有如下幾個特點: 1)作業(yè)對象代表用戶作業(yè),包含與作業(yè)有關的所有信息,貫穿于作業(yè)處理的全過程; 2)所有的作業(yè)處理都是基于作業(yè)對象進行的; 3)作業(yè)處理各環(huán)節(jié)、各模塊間通過作業(yè)對象保存,傳遞信息; 4)作業(yè)處理相關環(huán)節(jié)通過作業(yè)對象相互調(diào)用。
    作業(yè)對象由兩類信息組成:
作業(yè)請求信息　與請求相關的信息,即作業(yè)描述文檔。包括一般信息、執(zhí)行信息、屬性信息、數(shù)據(jù)信息、擴展信息等內(nèi)容。
    作業(yè)處理信息　與作業(yè)處理過程的相關信息。包括作業(yè)ID號、作業(yè)狀態(tài)、業(yè)提交次數(shù)等用于作業(yè)處理的信息。作業(yè)對象中包含了與整個作業(yè)處理過程相關的所有信息,這些信息的充分性既保證了作業(yè)能夠被完整地處理,又使作業(yè)保持了高度的獨立性。
1. 2. 2　多隊列結構
    多隊列結構由四個處理隊列構成,分別是:預處理隊列　負責對作業(yè)進行預處理,最終為每個到達的作業(yè)篩選出可用的資源地址。
調(diào)度隊列　負責對所有到達的作業(yè)按照其可用資源地址進行重新排隊,各個作業(yè)對象被排隊到新的子隊列中。然后,對于每個子隊列,系統(tǒng)采用多策略的模式進行調(diào)度,最終篩選出每個子隊列中優(yōu)先級最高的作業(yè)。
    資源選擇隊列　負責對由上一個隊列選出的作業(yè)進行資源選擇,最終為每個作業(yè)選擇最合適的執(zhí)行地址。
提交隊列　負責將每個作業(yè)提交到執(zhí)行地址上執(zhí)行。
    關于多隊列結構還要說明以下幾點:
1)每個處理隊列本身是一個線程,線程一旦啟動起來就可以自動處理作業(yè)。為了規(guī)范管理作業(yè)處理環(huán)境中的每個處理隊列,系統(tǒng)設計了一個隊列模板,定義了一些基本操作,比如入隊、出隊等,所有的處理隊列都是在隊列模板的基礎上創(chuàng)建的。
2)作為作業(yè)對象的容器,處理隊列以線程池的形式建立,具有負載平衡的能力,即可以根據(jù)設置線程池容量的大小來控制隊列中作業(yè)對象的數(shù)目,當作業(yè)對象數(shù)目達到容量上限時,新來的作業(yè)對象將被排隊等待。處理隊列為線程池中的每個作業(yè)對象創(chuàng)建一個處理進程,負責對作業(yè)進行具體的處理。
3)每個處理進程都包含一條處理鏈,處理鏈是一系列處理動作的集合,每個處理動作負責對作業(yè)對象進行特定的處理。通過修改配置文件JMSConfig,可以靈活添加或刪除特定的處理動作,從而實現(xiàn)了可插入的軟件設計方法。
1. 3　處理隊列的工作原理
    作業(yè)處理環(huán)境在處理作業(yè)對象前首先要進行初始化,初始化工作負責把四個處理隊列首尾相接形成一個多隊列的作業(yè)處理環(huán)境,并且把每個處理隊列的線程都啟動起來,線程一旦啟動就可以自動運行。每個處理隊列一旦啟動,就會等待作業(yè)對象的加入。由于四個處理隊列都是從相同的隊列模板產(chǎn)生的,所以它們有著相似的處理流程。圖2給出了處理隊
列的一般工作流程。
    作業(yè)的入隊、出隊操作很簡單,就是加入和離開一個哈希表并更新數(shù)據(jù)庫。處理隊列采用了循環(huán)結構對作業(yè)對象進行批量處理,每間隔一段時間就從哈希表中依次讀取一定數(shù)量的作業(yè)放入到線程池中,檢查當前線程池中的作業(yè)數(shù)量,只要線程池不發(fā)生上溢,就按照FCFS的原則為每個作業(yè)創(chuàng)建一個處理進程。處理進程負責具體的處理工作,它會調(diào)用一個名字叫做HandlerChain的處理鏈來決定要采用的處理動作。
這里面有幾點要進行說明。
1)所謂“上溢”在數(shù)據(jù)結構[ 8 ]中泛指隊滿還入隊的操作,在作業(yè)處理環(huán)境中是指處理隊列的線程池的容量達到上限的情況。之所以加上這個判斷條件是為了保持容器的負載平
衡,提高系統(tǒng)的處理效率。
2)雖然四個隊列的結構相似,但是它們所完成的功能卻完全不同,這就決定了在各自的處理鏈中要采用不同的處理動作。為了屏蔽這種內(nèi)在的差異,系統(tǒng)采用了讀取配置文件JMSConfig的方法。這樣做有兩點好處,一是保證了操作形式上的統(tǒng)一性,幾個處理隊列都是通過讀取這個配置文件來決定要采用的處理動作;二是保證了配置上的靈活性,可以根據(jù)用戶的需要動態(tài)修改配置文件,添加或刪除所需的處理方法,從而實現(xiàn)了一種可插入的軟件設計技術。
3)這個流程是前三個處理隊列工作的一般流程,但調(diào)度隊列在各個處理環(huán)節(jié)上采用了特殊的處理方法,這是由它的功能決定的。
4)作業(yè)控制中心接收到用戶的調(diào)用請求后,就可以控制作業(yè)進出某個隊列被相應地處理。作業(yè)對象一般情況下要依次經(jīng)過四個處理隊列的處理,實際運行當中,每個處理隊列都處于活動狀態(tài)等待處理作業(yè),但并不是每個作業(yè)對象在任何情況下都要被這四個隊列做依次處理,要根據(jù)作業(yè)控制中心下達的指令來確定。
    比如作業(yè)控制器接收到的用戶請求是作業(yè)終止,首先會根據(jù)作業(yè)號在數(shù)據(jù)庫查詢得到該作業(yè)所處的位置,然后就會下達作業(yè)終止命令,強制該作業(yè)從當前所處的隊列中出隊,并將實時信息保存到數(shù)據(jù)庫中。如果接收到的是用戶作業(yè)重啟的請求,作業(yè)控制器就會根據(jù)作業(yè)號從數(shù)據(jù)庫中查詢該作業(yè)對象的信息,然后下達作業(yè)重啟的命令,強制該作業(yè)從原來的暫停位置重新做入隊操作。

                             圖2　處理隊列的一般工作流程
2　作業(yè)處理環(huán)境的實現(xiàn)
2. 1　作業(yè)控制中心的實現(xiàn)
作業(yè)控制中心的工作流程如圖3所示。
    作業(yè)控制中心接收用戶提交的各種作業(yè)請求,下面以提交作業(yè)為例,介紹一下作業(yè)提交的步驟。首先,通過作業(yè)對象工廠把這個作業(yè)請求封裝成一個作業(yè)對象。通過調(diào)用作業(yè)工廠的初始化方法,完成對作業(yè)對象的初始化工作:包括初始化作業(yè)的ID號、作業(yè)的初始優(yōu)先級、初始狀態(tài)、安全身份等。其次,將作業(yè)對象序列化,調(diào)用數(shù)據(jù)庫存取接口完成作業(yè)對象存入數(shù)據(jù)庫操作。第三,由作業(yè)控制中心轉(zhuǎn)發(fā)指令。作業(yè)控制中心接收到用戶提交的調(diào)用指令后,首先初始化作業(yè)處理環(huán)境,然后根據(jù)作業(yè)對象的狀態(tài)將作業(yè)對象入隊到相應隊列,由于本次接受到的是作業(yè)提交指令,所以控制中心將作業(yè)對象入隊到預處理隊列。
    注意,如果控制中心接收到用戶銷毀作業(yè)指令的話,會根據(jù)待銷毀作業(yè)對象的ID號,從數(shù)據(jù)庫中取出相應的作業(yè)對象,查看該作業(yè)的狀態(tài)信息,判斷作業(yè)所在的處理隊列,然后命令作業(yè)做出隊操作。

                 圖3　作業(yè)控制中心的工作流程
2. 2　預處理隊列的實現(xiàn)
    預處理隊列的處理分為三個步驟:入隊操作、循環(huán)處理和出隊操作。其中,入隊和出隊的操作比較簡單,循環(huán)處理是關鍵。圖4給出了預處理隊列的工作流程。

                         圖4　預處理隊列的工作流程
1)入隊操作。將作業(yè)對象放入一個名字叫作queue的哈希表中,同時更新數(shù)據(jù)庫中作業(yè)對象的狀態(tài)信息,表明此時作業(yè)處在預處理隊列階段。更新數(shù)據(jù)庫的目的是防止系統(tǒng)突然掉電等意外情況的發(fā)生,從而方便作業(yè)對象的重啟。
2)循環(huán)處理。該循環(huán)處理結構負責定期對加入到本隊列的作業(yè)對象按照FCFS的原則進行批量處理,其工作按照
圖2中所示的一般工作流程進行。本隊列共采用了五個處理動作。
需求解析　負責解析作業(yè)對象中的作業(yè)描述文本,將文本中要求使用的軟硬件環(huán)境信息和資源地址信息解析出來。
權限檢查　通過調(diào)用虛擬社會組織(Virtual Organization,VO)服務提供的接口,獲得用戶有權使用的資源地址向量,和上一步取得的用戶要求使用的資源地址向量取交集,并以此更新作業(yè)對象的可用資源地址向量值。
類型檢查　負責判斷作業(yè)是否是應用類型作業(yè),如果是則調(diào)用應用服務接口直接獲得可用的資源地址信息;否則,進入下一步。
有效性檢查　調(diào)用全局信息服務接口,獲得滿足作業(yè)執(zhí)行軟、硬件環(huán)境要求且在當前網(wǎng)格環(huán)境中可使用的資源地址向量。再和前面取得的資源地址取交集,并以此更新作業(yè)可
用的資源地址向量值。
合法性檢查　對更新過的作業(yè)的資源地址向量的大小進行判斷檢查。作業(yè)對象經(jīng)過以上處理動作處理后,攜帶著的是最新的可用資源地址。
3)出隊操作。出隊操作完成的任務是:將作業(yè)對象從哈希表中刪除,然后,攜帶著必要的信息自動入隊到下一個處理隊列中。
2. 3　調(diào)度隊列的實現(xiàn)
在本層隊列,網(wǎng)格作業(yè)在各個服務節(jié)點的執(zhí)行次序?qū)⒈蛔罱K確定,所以此模塊的設計是作業(yè)處理流程中最關鍵的步驟。圖5給出了調(diào)度隊列的工作流程。

                       圖5　調(diào)度隊列的工作流程
調(diào)度隊列負責把所有入隊的作業(yè)對象重新排隊,它的排隊規(guī)則是以作業(yè)對象攜帶的可用資源地址為索引項,把作業(yè)對象排隊到各個子隊列相應的位置。這意味著資源地址與子隊列是一對一的關系。每個子隊列都包含一個列表,列表里存儲著一組有著共性的作業(yè)對象,這個共性指的就是擁有相同的資源地址。也就是說,擁有相同的資源地址的作業(yè)對象都排隊到同一個子隊列中。系統(tǒng)根據(jù)相應的策略對每個子隊列所包含的作業(yè)對象進行調(diào)度,在調(diào)度的過程中,采用了多策略的調(diào)度模式。
重新排隊的特性使得本層隊列的設計不同于其他三個處理隊列,作業(yè)對象在調(diào)度隊列中的處理步驟也是由入隊、循環(huán)處理和出隊構成。
1)入隊操作。主要是完成重新排隊的工作。每入隊一個作業(yè)對象,系統(tǒng)首先檢查它所攜帶的可用資源地址(URL) ,根據(jù)這些地址創(chuàng)建一個哈希表(QueueTable) 。該表以作業(yè)對象的URL為索引,鍵值是子隊列( JMSQueue)對象。一旦發(fā)現(xiàn)某個作業(yè)對象有新的資源地址,就為此地址創(chuàng)建一個子隊列。
某個作業(yè)對象進入作業(yè)調(diào)度隊列時可能攜帶著多個可用資源地址,系統(tǒng)根據(jù)這些URL值將其分別排隊到相應的子隊列中。一個子隊列可以包含多個作業(yè)對象,而一個作業(yè)對象也可以存儲在多個子隊列中,子隊列和作業(yè)對象是多對多的關系。圖6給出了一種可能的作業(yè)排隊情形。

                        圖6　作業(yè)在子隊列中的排隊示意圖
通過入隊操作,每個進入調(diào)度隊列的作業(yè)對象其實有了兩個排隊順序,一個是在整個調(diào)度隊列這個大隊列中的排隊順序,另一個是在以資源地址作為索引項的子隊列這樣的小隊列中的排隊順序。
2)循環(huán)處理。調(diào)度隊列的線程一旦被啟動,就采用一種循環(huán)處理的結構,定期對本隊列中的每個子隊列進行調(diào)度。調(diào)度過程中采用的是一種多策略的調(diào)度模式,采用了兩種算法來調(diào)整子隊列中作業(yè)的優(yōu)先級。調(diào)度隊列的調(diào)度鏈類包含四個處理動作�；�于用戶滿意度的優(yōu)先級調(diào)整　算法借助效用函數(shù)理論,根據(jù)實際調(diào)度過程中用戶的等待心理,構造了用戶不滿意度曲線,這條曲線最終確定了作業(yè)的優(yōu)先級隨時間變化的趨勢,算法的好處是使作業(yè)優(yōu)先級的調(diào)整符合用戶的心理。
基于調(diào)度頻率的優(yōu)先級調(diào)整( FrequencyPriorityAdjust2Algorithm) 　算法根據(jù)作業(yè)的調(diào)度頻率調(diào)整其優(yōu)先級,通過降低某些阻塞型作業(yè)的優(yōu)先級,使各類作業(yè)有了公平競爭的環(huán)境,提高了計算資源的利用率。
作業(yè)選擇　為每個子隊列選擇出優(yōu)先級最高的作業(yè),并把子隊列所對應的URL作為作業(yè)的最終執(zhí)行地址Endpoint。
可用性檢查　對于每個子隊列選擇出的作業(yè),把它的調(diào)度次數(shù)加1,然后調(diào)用全局信息服務,檢查它的Endpoint是否處于可用狀態(tài)。如果可用,就把該作業(yè)對象出隊;如果不可用,就重新參加調(diào)度。
基于用戶滿意度的優(yōu)先級調(diào)整和基于調(diào)度頻率的優(yōu)先級調(diào)整分別采用了兩種調(diào)度算法,經(jīng)過這兩個調(diào)度動作,每個子隊列中作業(yè)的優(yōu)先級已經(jīng)被調(diào)整完畢,系統(tǒng)要求每個子隊列中只有優(yōu)先級最高的作業(yè)(即作業(yè)選擇)才能被下一個處理動作(即可用性檢查)進行處理。
作業(yè)選擇的任務就是按照作業(yè)優(yōu)先級的大小為每個子隊列選擇出優(yōu)先級最高的作業(yè)作以標記,并且把子隊列的索引值作為此作業(yè)對象的一個候選地址,這個索引值就是圖6中哈希表的URL,這些被標記的作業(yè)便擁有了得到真正執(zhí)行的權利。
并不是每個子隊列選擇出來的被標記的作業(yè)都能得到真正執(zhí)行,這些被選擇的作業(yè)所攜帶的所有的候選地址此時在網(wǎng)格范圍內(nèi)不一定可用,必須進行檢查。系統(tǒng)設計了可用性檢查處理動作,通過調(diào)用信息服務提供的接口,對每個子隊列選擇出的作業(yè)的候選地址的有效性進行檢查,那些網(wǎng)格無法滿足的作業(yè)將重新在子隊列中排隊等待調(diào)度,只有通過檢查的作業(yè)對象才能順利地做出隊操作。
3)出隊操作。經(jīng)過四個處理動作的處理后,每個子隊列中優(yōu)先級最高并且其執(zhí)行地址確實能被網(wǎng)格系統(tǒng)滿足的作業(yè), 分別從大隊列(調(diào)度隊列)和每個小隊列(子隊列)做出隊操作,并自動入隊到下一個隊列即資源選擇隊列。
2. 4　資源選擇隊列和提交隊列的實現(xiàn)
這兩個模塊的設計思路與預處理隊列模塊基本相同,唯一不同之處在于所采用的處理動作不一樣。從調(diào)度隊列出隊后的每個作業(yè)可能包含多個候選地址,
例如圖6中的作業(yè)a,如果經(jīng)過調(diào)度后它在子隊列JMSQueue1和JMSQueue2都可能是優(yōu)先級最高的作業(yè),那么它就包含兩個候選地址URL1和URL2。資源選擇隊列的主要任務就是針對入隊的每個作業(yè)對象,在候選地址中選取其最適合的資源地址作為作業(yè)的最終執(zhí)行地址。然后,作業(yè)出隊并自動入隊到下一個隊列即提交隊列。提交隊列負責把進入該層的作業(yè)提交到最終執(zhí)行地址上真正執(zhí)行。
經(jīng)過四個處理隊列的處理,作業(yè)對象就完成了在作業(yè)處理環(huán)境的流程,或者繼續(xù)留在調(diào)度系統(tǒng)參加排隊,或者得到最終的執(zhí)行。
3　結語
本文提出了一種基于多隊列思想來構建作業(yè)處理環(huán)境的思路,由作業(yè)控制中心和多隊列結構組成的作業(yè)處理環(huán)境,采用分階段的方式處理網(wǎng)格作業(yè)。它的特點是:由四個處理隊列構成的多隊列結構將作業(yè)的處理流程劃分成幾個階段,每個階段完成特定的功能,它們彼此聯(lián)系而又相互區(qū)別;作業(yè)控制中心負責統(tǒng)一管理作業(yè)對象在多隊列結構中的操作,它的存在使得系統(tǒng)對作業(yè)處理流程的控制更加靈活。