《算法之美》—进程互斥软件算法(Lamport面包店算法和Eisenberg算法)

实现进程互斥的软件的结构框架是：

Framework

         Repeat

                   entry section

                   critical section

                   exit section

                   remainder section

         Until false

进程互斥的软件实现算法有：Lamport面包店算法和Eisenberg算法。这两种算法均假定系统中进程的个数有限，如n个。

1）Lamport面包店算法

(1)—面包店按由小到大的次序发放 码，且两个或两个以上的顾客有可能得到相同 码（要使顾客的 码不同，需互斥机制）；

(2)—若多个顾客抓到相同 码，则按顾客名字的字典次序排序（假定顾客没有重名）。

计算机系统中，顾客相当于进程，每个进程有一个唯一的标识，用Pi表示，对于Pi和Pj，若有i<j，即Pi先进入临界区，则先为Pi服务。

面包店算法的基本思想：首先设置一个发 器，按由小到大的次序发放 码。进程进入临界区前先抓取一个 码，然后按 码从小到大的次序依次进入临界区。若多个进程抓到相同的 码则按进程编 依次进入。

实现面包店算法所需的数据结构：

int choosing[n]; //表示进程是否正在抓 ，初值为0。若进程i正在抓 ，则choosing[i]=1.

int number[n];       //记录进程抓到的 码，初值为0。若number[i]=0，则进程i没有抓

伪代码如下：

// declaration & initial values of global variables

Choosing, Number: array [1..N] of integer = {0};

// logic used by each process…

// where “(a, b)＜(c, d)”

// means “(a＜c) or ((a == c) and (b＜d))”

Process(i) {      //注意：此处测试的是进程Pi

　while (true) {

　     Choosing[i] = 1;

　     Number[i] = 1 + max(Number[1],…,Number[N]);

　     Choosing [i] = 0;

　     for (j=1; j＜=N; ++j) {

　              while (Choosing[j] != 0) {//保证编 较小的进程先进入临界区

　              // wait until process j receives its number

　              }

　              while ((Number[j]!=0) && ((Number[j],j) ＜(Number[i],i))) { //进程Pj是其他线程

　              // wait until processes with smaller numbers

　              // or with the same number, but with higher

　              // priority, finish their work

　              }

　     }

　     // critical section…

　     Number[i] = 0;

　     // non-critical section…

　}

}