作者：Edsger W. Dijkstra 1965
原文：https://www.di.ens.fr/~pouzet/cours/systeme/bib/dijkstra.pdf

dijkstra.pdf

问题

假设有N个计算机，每个计算机内部都有一个进程，方便起见，可以认为这些进程都是在不断地循环执行一段逻辑。在每个执行周期内都有一个“critical-section”，需要以某种方式对这些计算机进行编程，以确保任意时刻这个N个进程中只有一个会处于“critical-section”。为了实现临界区的互斥执行，这些计算机相互之间可以通过一个共享存储模块进行通信。针对该存储模块的一个以word为单位的读写操作可以认为是原子的，比如当有两个或更多的计算机试图同时读写同一个存储单元时，这些操作会以未知顺序依次完成。

解决的代码

  1. k != i 时，需要尝试抢占。
    1. 目的是，谁先(或者最终)设置了 k = i, 谁就先开始尝试后面的步骤;.
    2. 这一步会因为代码执行顺序，可能会有多个人判断到 k == i ，需要其它检查手段。
  2. k == i 时，说明可以检查。
    1. 设置自己 c[i] = false 。
    2. 检查其他人是否也进入到这一步，也就是 c[j] == false 。如果发现有其他人进来了，说明可能不是最后一个设置 k = i ，需要重头判断。
  3. 经过多次的检查判断，只有最后一个设置 k = i 人才能进入 critical section 。
  4. 执行结束后， 还原 b[i] = true, c[i] = true 。唤醒其他人。
  1. ; common store
  2. Boolean array b, c[l:N]; integer k;
  4. ; 1 <= k <= N , b[i], c[i] 只会被 ith computer 设置，并且可以被其它 computer 观察到。
  5. ; b, c 数组默认设置为 true 。k 的值初始值不重要。
  7. ； ith computer 的代码如下：
  9. integer j;
  10. LiO: b[i] := false;
  11. Li1: if k <> i then
  12. Li2: begin c[i] := true;
  13. Li3:     if b[k] then k := i;
  14.          goto Li1;
  15.      end
  16.      else
  17. Li4: begin c[i] := false;
  18.          for j := 1 step 1 until N do
  19.              if j <> i and not c[j] then goto Li1;
  20.      end ;
  21.      critical section;
  22.      c[i] := true; b[i] := true;
  23.      remainder of the cycle in which stopping is allowed;
  24.      goto Li0;

1. 不会有两个进程进入临界区(critical section)

可能的执行顺序(i和j交换后可以得到另外三种执行序列)：
c[i] = false c[j] = false read c[j] read c[i]
c[i] = false read c[j] c[j] = false read c[i]
c[i] = false c[j] = false read c[i] read c[j]
c[i] = false read c[i] read c[j] c[j] = false
对于所有可能的执行顺序，不可能设置自己为false后，还能看到别人的为true。

2. 证明它不会出现“after you”-“after you”这种被无限阻塞的情况。

在进程k退出 critical section，执行 b[k]=true 时，其他进程会看到b[k]为true，然后执行 k:= i ，至少执行一次，当然 k:=i 会被执行多次(多个进程同时看到b[k]为true)，但是每个进程最多只执行一次k:=i，因为下次再执行时(k进程没有执行完critical secion前)，会看到 b[k] 为false ，只有一个进程执行到 Li4 。

3. 同时进入 Li4 判断的时机

  1. 上一次执行的进程是k，刚刚执行完成，但是没有执行到 Li0。

  2. k != i, i进程执行并进入到 Li3 ，判断 b[k] 为 true，即将执行 k := i 。

  3. 此时进程k立即执行，并一直走到了 Li4 ，为避免歧义，给这个进程k起别名为 k1。

  4. 进程i开始执行 k := i ，从Li1 执行，判断 k == i，(k被重新赋值了)，并执行到 Li4 ，此时就有两个进程了。