对分布式计算和存储等技术非常感兴趣，也希望硕士阶段能继续攻读这个课题，在大四开始入门。如果在这方面有好的建议也请告诉我，帮我指路，thanks。
今天先从分布式计算的临界区控制开始，在分布式计算当中多个进程（可能来自不同主机）可能同时访问同一资源，如何对它们进行临界区控制就成为了一个问题。
一、进程互斥算法
第一个分布式算法是dijkstra（话说更多人应该知道的是他的最短路径算法吧，其实他很厉害因为“死锁”也是他在这一时期提出来的）在1965年提出的进程互斥（mutual exclusion）算法：多进程在同一时刻共享一个资源，但是只有一个进程可以一直使用资源——这个可以进入一部分核心的称为临界区（critical section）。
进程共享存储模型：原子操作的读/写寄存器；进程同时还共享两组变量，状态集(status:{idle、get-turn、check}，初始化为idle)和编号(turn：{1,2,...,n}，初始化随机，不太懂turn如何翻译)。当一个进程准备进入临界区时先运行如下操作（说人话）：
第一步先把进程状态变成get-turn；第二步一直循环直到进程状态变为check，循环的内容是如果当前turn不为进程对应的编号，那么不仅把当前的turn改为进程的编号而且把当前turn对应的进程的状态改为idle，进程本身的状态改成check，然后检查是否有其他进程状态为check，是的话把自己的状态改成get-turn；第三步执行临界区代码；第四步进程状态改为idle。这样互斥资源分配的任务就完成了。
dijkstra进程互斥算法伪代码
那么如何讨论这个算法的正确性呢？首先，没有两个及以上进程可以同时存在于临界区。假设有两个进程同时为check状态，但是这和for循环和repeat-until循环的功能是矛盾的；其次，假设若干进程可以访问临界区，但是这和while循环的功能是矛盾的，因为第一个进入临界区的进程status为check，那么其他进程会被卡在while循环里面。
dijkstra 算法的优缺点：
- 优点：进程之间并行；有界共享寄存器
- 缺点：多进程读/写原子操作寄存器；饥饿问题；无容错性（没有等待资源释放）
二、分布式共享内存模型
如果具象化临界区的话，那么我们建立一个共享模型（DSM，distributed shared memory），由若干个进程和数个共享存储构成。对于（原子）共享模型来说，一个共享存储单元称为一个共享对象（shared object），每个共享对象都有一个类型（type），它提供以下特性：
- 对象可以取值
- 对象上可以施加操作
- 值可以被任何操作返回
- 对象的新的值可以是任何操作的结果
- （可选）对象有初始值
- （可选）进程和它们在对象上允许的操作
举个共享对象的例子：读写寄存器，暂时称它为R。它的值为整数；操作是读写；读返回值为寄存器当前值，写不返回；读不赋值，写赋新值。寄存器对读不限制，但是单进程或多进程写有区别。
再进一步，我们把多个进程和多个共享对象组成一个计算模型。那么每个进程都需要一个状态机，并且有一组状态集，在状态集中有一个初始态。一组变量（var1，var2，...）用来表现这些状态。每个状态q相当于一组特定的值变量（q.var1，q.var2，...），每个关于进程p的q状态都有三个特别的域：q.obj，下一个要操作的对象，可以为空；q.op：q.obj将进行的操作；http://q.in：输入q.op的参数。
所以，进程的状态转换是一个函数q' = f（q，v）。关于整个系统的配置可以概括为：所有进程的状态和所有共享对象的值，记为一个向量vector(q1，q2，...，qn，v1 , ...，vm)，这个向量标记了整个系统的当前状态，称它为配置C（configuration），但是所有进程都有初始态，所有共享对象都有初始值。
原子步骤（atomic step）s是在状态q的进程p。如果q.obj不为空，那么这就是一个通信步骤（computation step）因为通过了共享对象，反之q.obj为空，那么这就是一个本地步骤（local step）因为不通过共享对象。如果说s是进程动态转换的步骤，那么进程处于某个时刻的静态就是C。给定一个系统中的C，对应的s可能被数个进程使用。步骤s在C下有一个参数s.proc表明哪些进程正在进行步骤，并且仅由它改变状态q，可能是改变q.obj。
那么，计算模型的执行可以叙述为C0，s1，C1，s2，C2，...
- 步骤sj的输入是配置Cj-1
- 步骤sj的输出是配置Cj
- C0是初始配置
- 执行可以有限，也可以无限
- 如果希望把这个模型变成异步模型，则同一进程的两个步骤之间的步骤数没有限制
- 可允许的执行：在一个无限执行中，每个进程都有一个无限的步骤数；对有限执行来说，终止状态qe的模型如下：qe.obj = null, f（qe，v）= qe
计算模型的轮转调度如下：
计算模型有如下几个特点：
- 进程互斥：在每个执行的每个配置中，至多一个进程在临界区；
- 逐步进行（无死锁）：在每个可允许的执行中，如果一些进程在trying section的配置中，稍后一个配置会决定哪些进程可以进入临界区；
- 无饥饿问题：在每个可允许的执行中，如果一些进程在trying section的配置中，稍后一个配置会决定哪些 相同 进程可以进入临界区；
借鉴Microsoft的PPT，只叙述了DSM的结构，关于DSM的其他方面，这篇博文参考MIT课程写的较清晰[1]
三、Bakery 算法
1974年，Lamport等人在上述两个方法上改进，提出了bakery算法。Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。[2]
Bakery算法伪代码
面包店算法的优缺点：
- 优点：公平——没有饥饿问题；只用单进程写多进程读寄存器；只需要安全寄存器
- 缺点：无边界计数器；非wait-free
所谓lock-free和wait-free算法 是指对于共享的数据并非对其加锁来控制访问，而是多个线程并行的访问。通过该算法可以达到对共享对象并发的读写而不会破坏对象本身。所谓lock-free是指对于线程不加锁，让系统执行所有的步骤。lock-free提到的不加锁是指不使用类似于互斥锁或者信号量之类的排他机制。因为一旦对线程加锁的话，当线程执行中断时，那么对于这个系统来说运行也中断了。所谓wait-free是指，不管其他线程执行什么操作，线程无论有什么操作都能在有限的步骤里面完成。所以对于算法来说达到lock-free不一定能达到wait-free，但是达到wait-free的算法一定是lock-free的。 [3]
（如有转载请注明作者与出处，欢迎建议和讨论，thanks）
参考
- ^https://www.jianshu.com/p/28ed78afebb2
- ^CSDN博客 https://blog.csdn.net/pizi0475/article/details/17649949
- ^https://www.jianshu.com/p/baaf53d69b51