《算法之美》---进程互斥软件算法(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...

　}

}

当进程Pi计算完max(…)+1但尚未将值赋给number[i]时，进程Pj中途插入，计算max(…)+1，得到相同的值。在这种情况下，Choosing[j]保证编号较小的进程先进入临界区。

忙式等待：上述Lamport面包店算法中，若while循环的循环条件成立，则进程将重复测试，直到条件为假。实际上，当while循环条件成立时，进程Pi不能向前推进，而在原地踏步，这种原地踏步被称为忙式等待。忙式等待空耗CPU资源，因而是低效的。

2）Eisenberg算法采用的数据结构是：

enum states {IDLE, WAITING, ACTIVE} flags[n];

int turn; //范围是(0, n-1)

int index;//范围是(0, n-1)

其中，flags[i]=IDLE：进程Pi不想进入临界区；

flags[i]=WAITING：进程Pi想进入临界区；

flags[i]=ACTIVE：进程想进或已进临界区。

flags的所有元素初值都是IDLE；

turn的初值为0到n-1之间的任一正整数，它表示允许进入临界区的进程编号；

index为每个进程拥有的一个局部变量，其初值为0到n-1之间的任一正整数。

Eisenberg算法伪代码如下：

INITIALIZATION:

shared enum states {IDLE, WAITING, ACTIVE} flags[n];

shared int turn;

int index; /* not shared! */

...

turn = 0;

...

for (index=0; index<n; index++) { //初始化为IDLE

flags[index] = IDLE;

}

ENTRY PROTOCOL (for Process i ): //注意下面代码都是针对进程Pi

repeat {

/* announce that we need the resource */

flags = WAITING;

/* scan processes from the one with the turn up to ourselves. */

/* repeat if necessary until the scan finds all processes idle */

index = turn;

while (index != i) {

if (flag[index] != IDLE) index = turn;

else index = index+1 mod n;

}

/* now tentatively claim the resource */

flags = ACTIVE;

/* find the first active process besides ourselves, if any */

index = 0;

while ((index < n) && ((index == i) || (flags[index] != ACTIVE))) {

index = index+1;

}

/* if there were no other active processes, AND if we have the turn

or else whoever has it is idle, then proceed. Otherwise, repeat

the whole sequence. */

} until ((index >= n) && ((turn == i) || (flags[turn] == IDLE)));

/* claim the turn and proceed */

turn = i;

EXIT PROTOCOL (for Process i ):

/* find a process which is not IDLE */

/* (if there are no others, we will find ourselves) */

index = turn+1 mod n;

while (flags[index] = IDLE) {

index = index+1 mod n;

}

/* give the turn to someone that needs it, or keep it */

turn = index;

/* we're finished now */

flag = IDLE;

注意：Eisenberg算法同样存在忙式等待问题。