並發程式設計
正文
由若干個可同時執行的程式模組組成程式的程式設計方法。這種可同時執行的程式模組稱為進程。進程由數據和有關的語句序列組成。組成一個程式的多個進程可以同時在多台處理器上並行執行，也可以在一台處理器上夾插執行。採用並發程式設計可以使外圍設備和處理器並行工作，縮短程式執行時間，提高計算機系統的效率。例如，在一個單處理器系統中，從磁碟讀入數據經加工後列印輸出，不採用並發程式設計時，解決這個問題的程式是循環地執行讀入一批數據，然後，加工列印輸出。執行這個程式時，磁碟機、處理器和印表機順序執行輸入、加工和輸出操作。雖然計算機的外圍設備和處理器可以並行操作，但執行上述程式時它們只能串列工作。如果採用並發程式設計，解決上述問題的程式由以下兩個進程組成。①讀盤進程：循環地執行讀入一批數據，加工後送入輸出緩衝區；②列印進程：循環地執行從緩衝區取出數據列印輸出。在列印進程執行列印輸出時只需要印表機，而不需要磁碟機和處理器。因此，在列印進程啟動印表機後，在印表機輸出的過程中可以啟動讀盤進程輸入和加工數據。執行這個程式時，處理器、磁碟機和印表機並行工作，能縮短程式執行的時間，提高計算機系統的效率。發展過程 60年代初期出現的多道程式設計是並發程式設計的萌芽。在一個多道程式設計系統中，一個計算機系統可以同時接受多個用戶程式，並讓它們交替占用處理器運行。當一道程式因為等待外圍設備而暫時不能運行時，就啟動另一道程式運行，而各道程式之間沒有關係。因此，多道程式設計能提高計算機系統的效率，但並不能縮短一道程式的執行時間。在出現多道程式設計時，人們尚不清楚並發這個概念和由此產生的如死鎖等問題。60年代初期出現的許多多道程式設計系統，根本沒有考慮死鎖問題。因此，這些系統都有不同程度的錯誤和隱患。1968年，E.W.代克斯特拉設計的作業系統T.H.E.，首次系統地表明了並發程式設計的概念和有關問題。他注意到並發進程訪問公共變數的問題，提出用PV操作解決公共變數問題。此外，他還採用層次結構方法防止死鎖。然而，T.H.E.系統是用彙編語言編寫的。到70年代，人們才開始將並發程式設計的概念引入程式設計語言中，先後出現並發PASCAL、MODULA-II和ADA等程式設計語言。與此同時，還開展了防止死鎖、死鎖檢測和同步機制的研究，提出銀行算法、按序分配等防止死鎖的算法和管程等同步機制。到80年代，並發程式設計的研究已逐漸完善，套用也日益廣泛。
基本內容 並發程式設計的主要研究內容有：同步機制、死鎖的預防和檢測，以及並發程式設計語言。
同步 在並發程式設計中，將加工後的數據送入緩衝區和從緩衝區取出數據列印輸出必須依次進行。在數據送入緩衝區前不能列印輸出，在緩衝區內的數據沒有列印輸出完畢時不能輸入；否則，一批數據可能被重複列印或者一批數據還沒有列印輸出就被新送入的數據衝掉。因此，對“送入緩衝區”和“從緩衝區取出數據”兩個操作必須加以約制，以保證它們依次執行，否則就會發生錯誤。
產生這個問題的原因是兩個進程都要訪問緩衝區，也就是說它們有一個公共變數。在並發程式設計中，各進程對公共變數的訪問必須加以約制，這種約制稱為同步。進程的同步是通過同步機制實現的。現已有多種同步機制，具有代表性的是PV操作和管程。
PV操作是最早提出的同步操作。PV操作的名稱來源於荷蘭字prolagen(企圖降低)和verhogen（升起）。PV操作是作用於信號量上的原語。所謂原語是指其執行是不會被打斷的，即一個進程在執行PV操作時，不會強行地被打斷而讓處理器去執行另一個進程。PV操作的定義是：執行P操作P(S)時，信號量S之值減1,若結果不為負數，見P(S)執行完畢；否則,執行P操作的進程暫時停止。等待釋放。執行V操作V(S)時,信號量S之值加1，若結果不大於 0，則釋放一個等待釋放的進程。有了PV操作後，上例中的問題就即可解決。
1973年，C.A.R.霍爾提出的管程是另一種重要的同步機制。管程是指一組公共數據同與其有關的操作的集合。只有引用管程中的操作才能訪問管程中的數據。一個進程引用管程中的操作時，只有在管程中的各操作均不處於活動狀態時才被回響。當管程中的一個操作被引用後，它就成為活動狀態。當管程中一個操作已執行完畢或在執行中處於等待狀態時，它就不是活動狀態。管程將公共數據同與其有關的操作集中在一起，使得並發程式設計易於理解，程式正確性也容易保證。因此，管程有助於同步機制從PV操作向前發展。它是並發程式設計趨於成熟的標誌之一。
死鎖 進程因爭奪資源而無休止地相互等待稱為死鎖。例如，進程P1占有了繪圖機而申請行式印表機，進程P2占有了行式印表機而申請繪圖機。它們都因為申請不到資源而永遠等待，這就是死鎖。解決死鎖問題有兩種途徑：一是預防死鎖，設計各種資源調度算法，防止死鎖發生；另一種途徑是檢測死鎖，當死鎖發生時能及時發現並進行排除。
語言 要有效地採用並發程式設計，必須提供並發程式設計語言。並發程式設計語言的主要特徵，是引入了進程概念。因此，用它編寫的程式包含若干可同時執行的進程。此外，並發程式設計語言還提供實現進程同步和通信的手段。
參考書目
P.B.漢森著,楊芙清等編譯:《並發程式的系統結構》，國防工業出版社,北京,1982。(Per Brinch Hansen,The Architecture of Concurrent Programs, Prentice Hall,Englewood Cliffs,New Jersey,1977.
