Lamport面包店算法详解(转 侵删)

范例1:

boolean  choosing[n];表示进程是否在取号

int  number[n];记录每个进程取到的号码

这些数据结构分别初始化为false和0,为了方便,定义如下符号:

若a<c或a==c和b<d同时成立,(a,b)<(c,d)

do
{
             
  choosing[i] = true;
  number[i] = max{number[0],number[1],…,number[n-1]}+1;//选号码
  choosing[i] = false;
  for(j = 0; j<n; j++)
    {
    while (choosing[j]);
    while ((number[j] != 0) && (number[j],j)<(number[i],i));
  };

  //临界区
  number[i] = 0;
  //其余部分
}while(1);
理解:

第一个试图进入临界区的进程Pi在没有其它进程竞争时顺利进入其临界区。满足了有空就进的要求。

当有竞争者Pk(i<k),且选的号码相同时,比较进程的名称,通过语句while ((number[j] != 0) && (number[j],j)<(number[i],i));来选择进入的进程。

在Pi进程中j==i时,number[j]==number[i],且j==i所以(number[j],j)<(number[i],i)不成立,退出while语句。j==k时,number[k]==number[i],且k>i所以(number[j],j)<(number[i],i))不成立,退出while语句。对与其它非i和k的j值,number[j]!=0不成立,退出while语句。

在pk进程中j==i时,number[j]<number[k],且j<k,所以(number[j],j)<(number[i],i))成立,故进程Pk陷在该语句中,直到Pi退出临界区执行语句number[i]==0时才允许Pk进程进入其临界区。所以满足了互斥和有限等待的要求。

范例2:

计算机文献中的几种互斥算法中,所谓的Lamport面包店算法可以有效地用于多个相互竞争的控制线程,该算法中线程之间的通信只能在共享内存中进行(即,不需要诸如信号量、原子性的set-and-test之类的专门机制)。该算法的基本思想源于面包店,因为面包店需要先取号然后等候叫号。下面给出了该算法的框架,该算法可以使各线程进出临界区而不产生冲突。

     Enter, Number: array [1..N] of integer = {0};
面包店算法
面包店算法// logic used by each thread面包店算法
面包店算法// where "(a, b) < (c, d)"
面包店算法// means "(a < c) or ((a == c) and (b < d))"
  Thread(i) {
   while (true) {
    Enter [i] = 1;
    Number[i] = 1 + max(Number[1],面包店算法,Number[N]);
    Enter [i] = 0;
面包店算法    for (j=1; j<=N; ++j) {
面包店算法      while (Enter[j] != 0) {
面包店算法        // wait until thread j receives its number
面包店算法      }
面包店算法      while ((Number[j]!=0)
面包店算法         && ((Number[j],j) < (Number[i],i))) {
面包店算法        // wait until threads with smaller numbers
面包店算法        // or with the same number, but with higher
面包店算法        // priority, finish their work
面包店算法      }
面包店算法    }
面包店算法    // critical section面包店算法
面包店算法    Number[i] = 0;
面包店算法    // non-critical section面包店算法
面包店算法  }
面包店算法}

原文地址:https://www.cnblogs.com/wsw-seu/p/10530066.html