茶年 · 中文维基百科

Lamport面包店算法

Wikipedia · 2026-04-07 维基百科 👁 1 阅读

Lamport面包店算法（）由莱斯利·兰波特发明，是用于解决多个线程并发访问共享单用户资源时的互斥问题的一种算法。

算法
类比说明
兰波特将该并发控制算法直观地类比为顾客去面包店采购的场景。在此场景中，面包店一次只能接待一位顾客。假设有 N 位顾客要进入面包店采购，他们需要按照先来后到的顺序在前台抽取签到号码，号码依次递增（每次加1）。顾客根据签到号码从小到大的顺序依次结账购买。完成购买后，顾客的签到号码归零；若需再次购买，则必须重新排队抽号。

该类比中的“顾客”相当于计算机体系中的“线程”，而“入店购货”则相当于线程进入临界区并独占访问共享资源。由于计算机体系的特点，可能会出现两个线程获得相同签到号码的情况。这是因为两个线程可能几乎同时申请排队号码，在读取已发出的签到号码时，读到了完全相同的数据，随后各自在此基础上加1作为自己的签到号码。为解决这一问题，该算法规定：如果两个线程的签到号码相等，则线程ID号较小的线程具有优先权。

进入临界区
获得排队签到号码的线程需要轮询检查自身是否可以进入临界区。具体而言，它会检查在所有 n 个线程中，自己是否持有最小的非零签到号码；或者在持有相同最小非零签到号码的线程中，自己的线程ID是否为最小。

上述检查逻辑可用伪代码表示如下：
比较元组 (a, b)
等价于：
(a

非临界区
线程在临界区执行完毕后，需将自身的排队签到号码置为0，以表示其退回非临界区状态。

算法实现
定义

  • 数组 Entering[i] 为真（true），表示线程 i 正在获取排队登记号；
  • 数组 Number[i] 的值为线程 i 当前的排队登记号。若值为0，表示线程 i 未参加排队，即不请求该资源。该数组元素的取值理论上没有上界；
  • 若正在访问临界区的线程发生故障或异常终止，规定其自动进入非临界区状态（即 Number[i] 置为0），以免影响其他线程访问该互斥资源。

伪代码
// 声明全局变量并赋初值
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

讨论
每个线程仅负责写入属于自己的 Entering[i] 与 Number[i] 变量，而对其他线程的这两个数据项仅执行读取操作。

该算法的一大特点是无需依赖硬件级别的原子操作（atomic），完全可以通过纯软件层面实现。

引入 Entering 数组是不可或缺的。假设不使用该数组，可能会出现如下竞态条件：设线程 i 的优先级高于线程 j（即 i ），且两者获得了相同的排队登记号。线程 i 在将数值写入 Number[i] 之前，优先级较低的线程 j 抢先获得了 CPU 时间片；此时线程 j 读取到的 Number[i] 仍为0，因此线程 j 误认为自己有权进入临界区。随后，线程 i 重新获得 CPU 时间片，它读取到的 Number[i] 与 Number[j] 相等，且满足 i 的优先权条件，于是线程 i 也进入了临界区。如此一来，两个线程同时在临界区内操作共享资源，极易导致数据腐烂（Data corruption）。Entering 数组变量的引入，相当于将修改 Number 数组元素值的操作“原子化”，从而有效规避了上述问题。

在具体实现时，可以将伪代码中的忙等待（busy wait）优化为主动交出线程的执行权（例如使用 yield 操作系统调用），以提升系统资源的利用率。

参见

  • Peterson算法
  • Szymanski算法
  • 信号量

外部链接

参考文献

#带有伪代码示例的条目 #并发控制算法

评论 (0)

  • 还没有评论，来抢沙发吧。