程式語言/併發語言

併發程式設計是一種計算機程式設計技術，它允許同時執行操作 - 可以在一臺計算機上或多個系統之間進行。在後一種情況下，使用分散式計算這個術語。多處理器機器透過利用這種程式設計方式來提高效能。

併發程式設計現在是讓 CPU 密集型程式執行速度提高一倍的唯一方法。（歷史上，另一種流行的方法是等待幾年，直到出現時鐘速度提高一倍的 CPU，但這種趨勢在大約 2003 年結束）。^[1]^[2]

在並行程式設計中，單個任務被拆分為多個子任務，這些子任務可以相對獨立地計算，然後聚合起來形成一個單一的連貫解決方案。並行程式設計最適合於可以輕鬆分解成獨立任務的任務，例如純粹的數學問題，例如因式分解。

實現並行程式設計的一種方法是透過分散式計算，這是一種資訊處理方法，其中工作由透過通訊網路連線的獨立計算機執行。

互斥

定義: 由 E.W. Dijkstra 在 1965 年正式定義和解決 [D65]。

我們有一組程序，它們在程式碼的兩個部分之間反覆交替：非臨界區和臨界區 (CS)。問題是要提供一種同步演算法，以嘗試和退出協議的形式執行，分別在 CS 之前和之後立即執行。

非臨界區
嘗試協議
臨界區
退出協議

，以便以下屬性成立

互斥

沒有兩個程序同時處於它們的 CS 中。

無鎖死

如果一個程序進入嘗試協議，那麼它最終會進入 CS。

無不必要的延遲

嘗試進入其臨界區的程序只能被正在執行其臨界區的另一個程序或其他嘗試進入其臨界區的程序阻止。

有限退出

如果一個程序進入退出協議，那麼它會在有限數量的自身步驟內進入非臨界區。

互斥的解決方案

根據 [Y03]，互斥有數千種解決方案，有些是由聰明的人員發明的，有些是透過計算機的暴力方法找到的。

以下是一些著名的解決方案
Dijkstra 演算法: 第一次嘗試。; 根據 [K66][D67]，該演算法允許單個計算機在爭奪訪問許可權時可能需要無限期等待。
Lamport 麵包店演算法

為了便於理解，我們從使用修改後的原始麵包店演算法的 2 個程序開始

對於 2 個程序

Process p0 {
    // non-critical section
    // entry protocol
    turn0 = 1;
    turn0 = turn1 + 1;
    while( turn1 != 0 && turn0 > turn1);
    //critical section
    turn0 = 0;
  }
  
  Process p1 {
    // non-critical section
    // entry protocol
    turn1 = 1;
    turn1 = turn0 + 1;
    while( turn0 != 0 && turn1 >= turn0);
    //critical section
    turn1 = 0;
  }

非正式證明

假設 p0 試圖進入其臨界區，而 p1 處於其非臨界區。然後，p0 獲得訪問許可權，因為 turn1 為 0；
假設 p0 試圖進入其臨界區，而 p1 處於其臨界區。然後，p0 會忙等待，因為 turn 1 不為 0，並且 turn0 被設定為大於 turn1。當 p1 完成其臨界區時，它將 turn1 設定為 0。有兩種子情況。在每種情況下，p0 都將進入其臨界區。
- 如果 p1 在 p0 測試 turn1 時（即，turn1 為 0）正在其非臨界區中執行，那麼 p0 將進入其臨界區。
- 另一方面，p1 可能會完成其非臨界區，並將其 turn1 設定為 turn0+1 作為其進入協議的一部分。當 p0 重新測試此條件時，它將發現它為假，因為 turn1 大於 turn0。因此，p0 將進入其臨界區。
假設 p0 和 p1 幾乎同時開始執行其進入協議，並且每個都完成了它們的第一個賦值語句；因此，每個 turn 變數都是 1。進一步假設，例如，p0 完成了它的第二個賦值語句，並在 p1 執行它的第二個賦值語句之前評估了它的條件；因此，turn0 是 2，而 turn1 是 1。然後 p0 將等待，而 p1 繼續執行並將 turn1 設定為 3。請注意，一個程序將其 turn 變數設定為 1 會迫使另一個程序等待，直到第一個程序完成為 turn 變數選擇其值。
假設 p0 和 p1 與上例中的情況相同。它們完成了它們的第一個賦值語句，這些語句將每個 turn 變數設定為 1。現在假設第二個賦值語句的執行在機器指令級別交錯。然後，可以發生以下執行順序
- p0 讀取 turn1 的值 (1)；
- p1 讀取 turn0 的值 (1)；
- p0 新增 1 並將結果 (2) 儲存到 turn0 中；
- p1 新增 1 並將結果 (2) 儲存到 turn1 中；

雖然 turn 變數具有相同的值。p1 將推遲到 p0，因為它的條件使用 >= 而 p0 的條件使用 >。

為什麼使用下劃線程式碼？

下劃線程式碼的必要性可能並不明顯。

有關深入討論，請參閱 UCDAVIS：麵包店演算法。

對於 N 個程序

// declaration and initial values of global variables
  Entering: array [1..N] of bool = {false};
  Number: array [1..N] of integer = {0};
      
  lock(integer i)
  {
    Entering[i] = true;
    Number[i] = 1 + max(Number[1], ..., Number[N]);
    Entering[i] = false;
    for (j = 1; j <= N; j++) {
      // Wait until thread j receives its number:
      while (Entering[j]) { /* nothing */ }
      // Wait until all threads with smaller numbers or with the same
      // number, but with higher priority, finish their work:
      while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) {
      /* nothing */
      }
    }
  }
  unlock(integer i) { Number[i] = 0; }
  
  Thread(integer i) {
    while (true) {
        lock(i);
        // The critical section goes here...
        unlock(i);
        // non-critical section...
    }
  }

在虛擬碼中，存在以下形式的比較(a, b) < (c, d)

它等效於(a < c) or ((a == c) and (b < d))

為什麼稱它為麵包店演算法？

Lamport 設想一家麵包店，在入口處有一個號碼機。因此，每個顧客都會獲得一個唯一的號碼。當顧客進入商店時，號碼會增加 1。一個全域性計數器顯示當前正在服務的顧客的號碼。所有其他顧客必須在佇列中等待，直到麵包師完成為當前顧客服務並顯示下一個號碼。購物完畢後，顧客會失去其號碼，然後可以做任何事情，但不能在沒有獲得新號碼的情況下購物。

參考文獻

待辦事項
提及 C. A. R. Hoare 及其在併發程式設計方面的研究

↑ Herb Sutter. "免費午餐已經結束：軟體中併發性的根本轉變"。
↑ Ian Emmons. "多處理器最佳化：微調對大型資料集合的併發訪問"。

[D65]Dijkstra, E.W.，併發程式控制中問題的解決方案。1965

[D67]deBruijn, N.G.，關於併發程式控制中問題的一些補充意見。1967

[K66]Knuth, D.E.，關於併發程式控制中問題的一些補充意見。1966

[O04]Ronald Olsson, Aaron Keen，JR 程式語言，擴充套件 Java 中的併發程式設計。2004

[Y03]Yoah Bar-David, Gadi Taubenfeld，自動發現互斥演算法。2003

特定語言中的併發程式設計

進一步閱讀

"並行程式設計" 來自 CiteSeer 的引用

[1] Herb Sutter. "免費午餐已經結束：軟體中併發性的根本轉變"。

[2] Ian Emmons. "多處理器最佳化：微調對大型資料集合的併發訪問"。

[1]

[2]