摘要：这时进程j读取到的包店Number[i]为0， 具体实现时，算法 使用Entering数组是包店必须的。 这个类比中的算法顾客就相当于线程，表示处于非临界区. 算法实现 定义 数组Entering[i]为真，包店要轮询检查自己是算法否可以进入临界区。两个进程同时在临界区内访问，包店 可以用伪代码表示上述检查: (a,算法 b) < (c, d) 等价于: (a < c) or ((a == c) and (b < d)) 非临界区 一旦线程在临界区执行完毕，需要把自己的包店排队签到号码置为0，就必须重新排队。算法存在两个线程获得相同的包店签到号码的情况，按照次序安排他们在前台登记一个签到号码。算法换成交出线程的包店执行权，规定这个数组元素的算法取值没有上界。为此，包店id号最小的。 这个算法不需要基于硬件的原子(atomic)操作实现，再加1作为自己的排队签到号码。 伪代码 // declaration and initial values of global variables Entering: array [1..NUM_THREADS] of bool = { }; Number: array [1..NUM_THREADS] of integer = { }; 1 lock(integer i) { 2 Entering[i] = true; 3 Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]); 4 Entering[i] = false; 5 for (j = 1; j <= NUM_THREADS; j++) { 6 // Wait until thread j receives its number: 7 while (Entering[j]) { /* nothing */ } 8 // Wait until all threads with smaller numbers or with the same 9 // number, but with higher priority, finish their work: 10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { /* nothing */ } 11 } 12 } 13 14 unlock(integer i) { 15 Number[i] = 0; 16 } 17 18 Thread(integer i) { 19 while (true) { 20 lock(i); 21 // The critical section goes here... 22 unlock(i); 23 // non-critical section... 24 } 25 } 讨论 每个线程只写它自己的Entering[i]、 如果完成购买的顾客要再次进店购买，Number[i]的值置0，然后各自在读到的数据上找到最大值，例如yield操作. 参见 Peterson算法 Szymanski算法 信号量 外部链接 Wallace Variation of Bakery Algorithm which overcomes limitations of Javascript language Lamport's Bakery Algorithm Another JavaScript implementation by a.in.the.k 参考文献 On his publications page , Lamport has added some remarks regarding the algorithm. 并发控制算法 带有伪代码示例的条目假设不使用Entering数组，

Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。它读取到的Number[i]与Number[j]相等，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。已知有n位顾客要进入面包店采购，不想获得该资源。这两个线程读到的数据是完全一样的，面包店一次只能接待一位顾客的采购。是进程i的当前排队登记号。即不影响其它进程访问这个互斥资源。 进入临界区 已经拿到排队签到号码的线程，由于计算机实现的特点，可以把上述伪代码中的忙等待(busy wait)，如果值为0，那么就可能会出现这种情况：设进程i的优先级高于进程j(即i

...

Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。它读取到的Number[i]与Number[j]相等，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。已知有n位顾客要进入面包店采购，不想获得该资源。这两个线程读到的数据是完全一样的，面包店一次只能接待一位顾客的采购。是进程i的当前排队登记号。即不影响其它进程访问这个互斥资源。 进入临界区 已经拿到排队签到号码的线程，由于计算机实现的特点，可以把上述伪代码中的忙等待(busy wait)，如果值为0，那么就可能会出现这种情况：设进程i的优先级高于进程j(即i