並行程序設計

能同時執行兩個以上運算或邏輯操作的程序設計方法。所謂並行性，嚴格地説，有兩種含義：一是同時性，亦即平行性，指兩個或多個事件在同一時刻發生;二是併發性，指兩個或多個事件在同一時間間隔內發生。程序並行性分為控制並行性和數據並行性。並行程序的基本計算單位是進程。並行程序有多種模型，包括： 共享存儲; 分佈存儲 (消息傳遞); 數據並行;面向對象。與並行程序設計相適應的硬件也有不同類型，如多處理機，向量機，大規模並行機和機羣系統等，相應有不同的並行程序設計方法。具體解題效率還與並行算法有關 ^[2]  。

並行編程類型逐漸匯聚於兩類:用於PVP,SMP和DSW的共享變量的單地址空間模型和用於MPP和機羣的消息傳遞的多地址空間模型. ^[3] 

並行編程模型逐漸匯聚於三類標準模型:數據並行(如:HPF),消息傳遞(如:MPI和PVM),和共享變量(如OpenMp).

人們希望高性能的並行機應是 具有單一系統映像的巨大的工作站,使得很多用户都能利用增強處理能力和儲存容量來運行多個串行作業,這就是所謂的串行程序並行系統SPPS.

當我們在實際的並行機上設計並行程序時,絕大部分均是採用擴展Fortran和C語言的辦法,有三種擴展的辦法:一是庫函數法:除了串行語言所包含的庫函數外,一組新的支持並行性和交互操作的庫函數(如MPI消息傳遞庫和POSIXPthreads多線程庫)引入到並行程序設計中。二是新語言結構法:採用某些新的語言結構來幫助並行程序設計以支持並行性和交互操作(如Fortran 90 中的聚集數組操作); 三是編譯製導法:程序設計語言保持不變,但是將稱之為編譯製導的格式註釋引入到並行程序中.

為了對實際的或邏輯的並行性編程，必須有一 些用以建立(create)與消滅(destroy ) (即， 設立與終止)進程的一些手段和用於這些進程彼此 間通信與同步的一種方法。許多系統與語言提供了 這樣的並行程序設計設施。顯式地提供這樣一些機 構的操作系統是DEC PDP-11與DEC VAX 計算機上的UNIX(q.v)系統。並行Pascal與 Modula都運行在DEC PDP-11上，Mesa語言 是在Xerox開發的，Ada (q.v.)語言是為美 國國防部開發的，它們都是含有並行程序設計結構的現代程序設計語言的例子 ^[4]  。

FORK與JOIN語句是一組可用於動態地建 立與消滅進程的語句。用於説明並行性的靜態設施 是cobegin/coend結構。它具有如下形式：

cobegin S₁//S₂//…//S_ncoend

它表示(可能是複合的)語句S₁、S₂、……與S_n可並行執行。

同步機構有TEST AND SET這樣的機器 語言指令，它不可分割地執行下列操作序列： 檢查 一個存儲單元為0還是1，把檢查結果存儲在一個寄存器中，使該單元置位為1; 對於實現鎖定或象 對信號量的Dijkstra P與V操作這樣的低級同步原語，TEST AND SET是方便的。在較高級是監督程序。這一設施用來説明表示一資源的共享數據 結構與定義用於獲得、釋放與存取該資源的過程; 監督程序容許封閉與調度可被若干進程使用的資源 目標。

獲得同步的另一種常用的方法是通過信息發送原語。簡單的例子是send(p，m)與receive (p，m)。send(p.m)導致信息m傳送到進 程p，receive(p.m)等待來自進程p的信息， 把該信息插入m中。因為它並不依賴通過公用存儲器中的共享變量進行通信，信息傳遞對於分佈式計算是有用的，在分佈式計算中，各任務通過通信線路連接。

仍在進行精煉與測試的Ada語言具有把過程調 用與信息發送兩者結合起來的通信與同步語句。在 兩個進程之間的通信通常進行如下。

一個進程用含有輸入與輸出參數的任務入口調 用來調用另一個進程，而被調用的進程發出一個等 待這樣一個調用的accept語句;accept語句還包 括一個任意的語句序列，該語句序列作為接受此任 務入口調用時出現的集結的一部分執行。在這個交互作用之後，調用進程與被調用進程兩者可再並行 執行。Ada還提供一個選擇等待語句，在其中有 在處於“開路”的一組accept語句之間的不確定 選擇(即，如果發出一個相應的任務入口調用，其中一個集結是可能的)。

作為並行程序設計的一個例子，我們給出對於 一個公用緩衝問題的解決方法。假設我們要為一個 二進程系統編程，其中一個進程是生產者進程，它 把一些記錄添加到一個存儲區，另一進程是消費者 進程，它把這些記錄移走。生產者進程可以是一個 與輸入設備關聯的進程，它把輸入記錄添加到存儲 緩衝器中，而消費者進程負責檢索記錄並處理它 們;另一方面，生產者進程可產生用於與一輸出設 備關聯的消費者進程的輸出記錄。

公用緩衝區有N個記錄(N≥1)的存儲。主 要問題是使緩衝器的處理同步，因而：

1.如果有空間的話，生產者進程可以只添加 一個記錄到緩衝器;如果存在一個記錄的 話，消費者進程可以只移走一個記錄。

2.一次僅一個進程可處理緩衝區。

我們假設生產者進程與消費者進程兩者均是 “永遠”循環的循環進程。採用信號量與cobegin/ coend，程序的輪廓如下：

Semaphore empty(N)，{緩衝器中空槽的 數目，初始為N}

full(0)，{緩衝器中滿記 錄的數目，初 始為0}

lock(1); {在緩衝器處理期 間，保證互斥}

Cobegin producer：

loop

begin produce Next Record;

P(empty); {只有在緩衝器中 可得到一個空槽 的情況下才進 行}

P(lock); {設置鎖定到0，避 免緩衝器被Consumer存取}

Add Record To Buffer;

V(lock); {設置鎖定到1，允 許被producer 或Consumer存 取}

V(full) {增加緩衝器中滿 記錄的數目

end consumer：

loop begin P(full); {只有在緩衝器中 有一個滿記錄時 進行}

P(lock); {對producer鎖 住緩衝器}

Take Record From Buffer;

V(lock); {緩衝器開鎖}

V(empty); {增加緩衝器中可 用槽的數目}

process Record end Coend