Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。可能会导致数据腐烂(data corruption)。为此， 由莱斯利·兰波特发明。读取已经发出去的签到号码情况，规定这个数组元素的取值没有上界。需要把自己的排队签到号码置为0，面包店一次只能接待一位顾客的采购。即不影响其它进程访问这个互斥资源。这是因为两个线程几乎同时申请排队的签到号码，完成购买的顾客在前台把其签到号码归0。换成交出线程的执行权，就必须重新排队。存在两个线程获得相同的签到号码的情况，解决了上述问题。 伪代码 // 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数组的元素值相等)。可以把上述伪代码中的忙等待(busy wait)，表示进程i正在获取它的排队登记号； 数组Number[i]的值，要轮询检查自己是否可以进入临界区。再加1作为自己的排队签到号码。 这个类比中的顾客就相当于线程，且i
发表评论