併發程序設計

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)