编程语言/并发语言

并发编程是一种计算机编程技术，它允许同时执行操作 - 可以在一台计算机上或多个系统之间进行。在后一种情况下，使用分布式计算这个术语。多处理器机器通过利用这种编程方式来提高性能。

并发编程现在是让 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]