成批系統

成批系統由成批實用程式、成批守護程式、程式設計庫等部分組成，是一種將在缺少大型計算機的情況下利用潛在的大量CPU時間資源處理很大的計算作業的軟體系統。

基本介紹

• 中文名：成批系統
• 外文名：batch system
• 主控制程式：成批守護程式
• 系統組成：成批實用程式、成批守護程式等
• 並行算法：二次篩選算法、FFT算法
• 套用學科：計算機科學、系統科學、通信工程

系統組成

成批守護程式

成批守護程式是成批系統的主控制程式。它在後合中運行，對用戶是完全透明的、存在於網路上的全部機器上，並負有若干責任。batchd程式在每一次系統被保護時都被自動調用，因此在系統使用期間持續不斷地運行。

它的主要作用有：

1. 維護網路上的成批佇列
   
2. 控制活動作業當機器“被使用”時這些是暫停的活動作業，當機器成為自出時重新開始被暫停的作業。單個工作站擁有者能控制他們的機器“被使用”的定義。
   
3. 用作命令和多道程式設計陣接口的一個服務程式。所有用戶緩和程式命令都直接與成批守護程式進行通信。
   
4. 在機器之間傳遞狀態信息
   

在建立成批守護程式時有如下幾個主要設計標準：

1. 程式必須是小的，以便不占甩各種不同系統上的存貯空間。
   
2. 程式必須不使用過多的CPU時間
   
3. 程守必須能夠提供有關網路上一既定機器的當前狀態信息。這是通過對考慮的機器查詢其狀態實現的。每一守護程式都維護它自己的整個網路“被使用“的映象。
   
4. 用來交換狀悉信息的數錯包必須是小的，以便不占用太多的網路頻寬。
   
5. 只要用戶在網路中的某個系統上有戶頭，就必須允許用戶把作業提交到系統上，甚至提交到甩戶沒有戶頭的系統上。
   
6. 成批守護程式必須利用Unix太網插口，這樣多重作業就可用網路互相傳送報文。
   

在由成批守護程式保的狀態信息中．有登記到每一系統的用戶數和過去的一分鐘內每一系統的負載平均埴，由守護程貯存的其他數據包括開始負載、停止負載，一作業是否活動，排成佇列的命令數和被服務的最後一個作業。開始和停止負載參數甩來表示直在何時使作業處於睡眠狀態或換醒作業的負載平均值這兩個參數為確定“被使用”的狀態提供最重要的控制機構。’

成批守護程式在每一工作站上大約要求每天用一分鐘CPU時間，並駐留在長度只為4k的程申內。這對SUN計算機是小的。它不尊用外部程式，它的多內部例程或成批守護程式是唯一的，它根據要求對其數據結結進行動態貯存分配。因此，我們能夠使守護程療保持小和不引人注目。

對每個工作站來說，該站上守護程式每隔三分鐘更新一次狀態信息。這種更新在機器之間不是同步化的，這將迫使中央機花費資源來拉制同步化。因此，當有人請求一特定機器狀態時，就向該機器發出詢問，適當的數據就被返回對狀態信息、排隊作業和詢問佇列的實際請求根步發生，因此請求的總頻寬要求可蹦忽略不計。廣播信息本能為更快地存取狀態信息創造條件。

成批實用程式

用戶級接口的基本設計原理是把一FIFO作業佇列與網路上的每一工作站聯繫起來，並為用戶提供作業系統接口級的命令，後者將：

1. 用給定的軟體和軟體特性確定一自由處理機的名字在可被規定的特性中，有機器類型、最小存貯要求、機器是否有一個局部磁碟、硬體浮點和操柞系統版本。
   
2. 把作業提交到確定機器上。如果機器可”被使用”，用戶可規定若干包括郵寄通知在內的選擇，如作業何時結束或如何處理一個作業等。
   
3. 檢查一給定處理機上的佇列。
   
4. 檢查一給定處理機的作業狀態和成批參數。
   
5. 從一佇列去掉一個作業或停止一個活動的作業
   

只要相應工作站是自由的，成批守護程式就將運行一給定佇列中的第一個作業。把一命令加到一佇列上是通過BATCH命令來實現的。其主要變元是要排隊的命令。該命令可以是任何有效的、非互動的UNIX命令或外殼原率(如帶有其變元的程式名)，這些命令與輔助的UNIX指令(如I/O再定向、管線、改變工作目錄的命令等)結合在一起。也提供了一個選擇當前是自由的工作站的命令。這一命令具有允許一用戶選擇一帶有某些特性的系統的選擇。如果沒有說明任何變元，則系境將選擇任何可用的自由主機。

為了使系統管理者能完全控制成批守護程式和排隊系統參數，提供了一個實用程式batchc。其功能包括(但不僅限於)改變使用參數、啟動/停止佇列和開始/停止系統。

遠程命令多道程式設計庫

遠程命令庫是一組C子例程和一個帶預定義務數的包含檔案。也可用另一個包含檔案和一個附加子倒程式來啟動進程遷移。這些允許程式設計師和利用成批系統的能力。而且也含有同步化和通信進程，後者允許程式在不同的主機上運行來彼此進行通信。這就為系統提供了多道程式設計能力。

支撐命令庫的基本概念是引入一抽象數據類型(操作rcmd)，它將描述一個並行運行在一遠程主機上的進程。數據結構是整個命令庫的中心。通過使remd與每一運行進程相聯繫，就能獲得對一自由系統的排他存取，在多重進程間進行通信，使運行在不同主機上的進程同步化．監視遠程進程的狀態，並終止和處置遠程進程。這一數據結構包含一遠程系統需要用來維護一運行在單獨系統上的作業和與之通信的全部信息。還有四種對成批守護程式為內部的其他數據結構，用來維護網路、控制佇列和保持狀態信息，這些結構對用戶是隱藏的，但可由成熟的程式設計師利用。

遠程命令庫存例程允許程式設計師把網路作為各種拓樸結構中的一個鬆散耦合的MIMD機器來處理。在那些己編寫了程式的拓撲結構中，有一種基形配置(STAR)和一種蝴蝶傳式配置(BOWTIE)(見圖)。其他研究人員業己發現，星形配置可在鬆散耦合的網路中工作得十分好。重要的是指出，每一遠程命令的運行都與其他命令無關，它們已被起動並正由命令控制這一事實對他們各自都是整個透明的。

實現的拓撲培構

通過說明rcmd的一個數組並使該數組的每一元素與一近程處理機相聯，就可利用多合機器。爾後就可通過向該數組中加下標來使用特定機器。庫存例程被用來確定兩終端上的一個自由主機。該例程把主機名作為一個字元串返回，同時保留主機供使用．以便另一個用戶這時不能利用它。這一簡單設備避免了自由機器間的競爭問題。

成批系統並行算法

最容易實現的的拓撲結構是星形配置。這種配置下，中央主機維護全部衛星處理機及其rcmd通過使主機向每一衛星處理機傳送它們將與通信的其他衛星處理機的名字，網路的拓撲結構可在運行時動態地配置。甚至可在一組程式運行時通過使主機重新定義拓撲結構和改變拓撲結構，然而向衛星處理機傳送報文來解除舊的通信鏈路並建立新的通信鏈路。

目前為止，成批系統已實現了兩種並行算法。

二次篩選算法

第一種算法是二次篩選算法，這種算法用來對大整數進行因式分解，其柘朴結構是一個星形配置。但該算法大量使用CPU時間，占用數以千計的CPU小時來運行。算法流控制由一中央主機(根據來自一遠程處理機的要求)向該處理機傳送唯一的整數構成。主機保存一組已在一找上預先計算的整數，以便在收到請求時立即傳送這些值。爾後遠程處理機根據該唯一整數執行成組計算並以格式串形式把輸出數據送回中央主機，主機隨後存貯這種數據。當足夠的數據已被累積後，主機就關掉衛星處理機並根據累積數據計算因式分解。

主機也負責維護遠程處理機。它經常檢查網路的狀態，看一看是否有任何處理機已停止工作(必要時重新起動它們)，同時看一看是否有更多的處理機己成為自由的．這種算法充分利用全部自由的遠程處理機，二次篩選算法在如下幾個方面對鬆散耦合網路是理想的。

l，算法的劃分用了一種非常自然的方法。因此可同時在許多處理機上運行它。

2、它具有很少的I/0要求和很少的處理機到處理機的通信。它的低開銷導致多重處理機上的線性加速。

3、這種算法是高度存貯密集的，在許多處理機之間對它進行劃分提供了大量增加的實存貯器。算法內的基本CPU密集循環涉及通過一長度位元組數組進行篩選。可用以實現這一點的速度依度依賴於任何可用超高速快取器容量的程度大大超過它依賴於處理機速度的程度，在多重處理機之間對算法進行劃分，不僅提供了更多的存貯器，而且提供多重超高速快取器。我們已在一個Alliant—E型計算機上實現了二次篩選算法，該機具有多重的緊密耦合的向量化處理機。即使它的每一處理機都能獨立處理共享存貯器，但只有一個中央數據超高速快取器，這導致了在處理機間對該超高速快取器的爭用，使得它對這種算法的有效性低於多重SUN的有效性。

FFT算法

第二種算法是一個通過在多重處理機之間劃分的頻率算法進行十中抽一來計算非常大的FFT（離散傅氏變換的快速算法）的程式。這種算法要求在處理機之間進行大量的數據傳送。實現這種劃分的目的是使衛星處理機數必須是2的乘方。中央主機調整算法的每一階段，並負責通知各個衛星處理機何時與其他衛星處理交換數據和何時執行算法的每一階段。

系統是用如下方法設計的：如果使2個處理機並行工作，則大小為m(m>n)的FFT就要求只在頭n個階段中在衛星處理機之間傳送數據。在此之後，每一處理機從其他處理機自動繼續進行，直到計算結束為止。爾後主機把來自全部衛星處理機的結束收集在一起。圖示出一個在四個處理機之間劃分的16點FFT的數據流。

FFT算法

算法的每一階段由“蝶式運算”(即成對韻加法點和用一適當的單位根乘以結果)構成。圖示出在算法的每一階段哪些點被結合在一起。每一衛星處理機都在每一階段執行相同數目的蝶式運算，因此在處理機之間計算負載是完全均衡的。在每一斷段結束時，主機都從每一衛星處理機接收一條它已結束其計算的報文。

系統問題

系統的首要問題是網路的頻寬，由成批系統運行的程式是CPU密集的，但它們確實為網路增加了一些負載。在一個帶很重負載網路的環境中，這種附加負載可能是引人注目的。對FFT程式所教的試驗表明，網路很容易由一種甚至只帶中等I/O要求的並行程式設計過載。

第二個大問題是由與日鐘時間的同步化問題引起的“被使用”參數是在白天期間改變的。如果一系統將崩潰並在幾個小時內不能恢復，則其日鐘時間可能成為不正確的。

如果在該系統被重新加上保護罩時日鐘不被復住，則它往往引起一個問題，由於這個問題成批守護程式不知遭當日的正確時間，並將不正確地接通參數。

性能檢測標準

在遠程成批系統中，人們一般都將考慮諸如佇列長度，等待時間、作業平均長度和自內機器的百分比利用率這樣的性能測量。

就我們特定的計算要求來說，這些測量或多或少是不相干的。我們一般只使一兩個很大的並行作業運行，這些作業可占用數以千計的CPU小時。在這樣一個環境中，唯一的真正性自目測量是測量CPU時間的百分比(這種時間是由系統使其成為可用的，否則將是不可用的)。

另一個性能測量將是確定系統將如何按比例增加到(比方說)一個有1000個工作站組成的網路。但若不做實際試驗，這將是很難確定的。