fbpx
维基百科

Lamport面包店算法

二月 19, 2023

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

算法

类比

Lamport把这个并发控制算法非常直观地类比为顾客去面包店采购。面包店一次只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，按照次序安排他们在前台登记一个签到号码。该签到号码逐次增加1。顾客根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0。 如果完成购买的顾客要再次进店购买，就必须重新排队。

这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。

进入临界区

已经拿到排队签到号码的线程，要轮询检查自己是否可以进入临界区。即检查n个线程中，自己是否具有最小的非0排队签到号码；或者自己是具有最小的非0排队签到号码的线程中，id号最小的。

可以用伪代码表示上述检查: 

(a, b) < (c, d)

等价于: 

(a < c) or ((a == c) and (b < d))

非临界区

一旦线程在临界区执行完毕，需要把自己的排队签到号码置为0，表示处于非临界区.

算法实现

定义

  • 数组Entering[i]为真，表示进程i正在获取它的排队登记号；
  • 数组Number[i]的值，是进程i的当前排队登记号。如果值为0，表示进程i未参加排队，不想获得该资源。规定这个数组元素的取值没有上界。
  • 正在访问临界区的进程如果失败，规定它进入非临界区，Number[i]的值置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[i]，只读取其它线程的这两个数据项。

这个算法不需要基于硬件的原子(atomic)操作实现，即它可以纯软件实现。

使用Entering数组是必须的。假设不使用Entering数组，那么就可能会出现这种情况：设进程i的优先级高于进程j(即i<j)，两个进程获得了相同的排队登记号(Number数组的元素值相等)。进程i在写Number[i]之前，被优先级低的进程j抢先获得了CPU时间片，这时进程j读取到的Number[i]为0，因此进程j进入了临界区. 随后进程i又获得CPU时间片，它读取到的Number[i]与Number[j]相等，且i<j，因此进程i也进入了临界区。这样，两个进程同时在临界区内访问，可能会导致数据腐烂(data corruption)。算法使用了Entering数组变量，使得修改Number数组的元素值变得“原子化”，解决了上述问题。

具体实现时，可以把上述伪代码中的忙等待(busy wait)，换成交出线程的执行权，例如yield操作.

参见

外部链接

  • Wallace Variation of Bakery Algorithm （页面存档备份，存于互联网档案馆） which overcomes limitations of Javascript language
  • Lamport's Bakery Algorithm （页面存档备份，存于互联网档案馆）
  • by a.in.the.k

参考文献

  1. ^ Original Paper (PDF). [2012-09-02]. （原始内容 (PDF)于2007-04-18）. 
  • On his publications page （页面存档备份，存于互联网档案馆）, Lamport has added some remarks regarding the algorithm.

二月 19, 2023
lamport面包店算法, 此條目需要編修, 以確保文法, 用詞, 语气, 格式, 標點等使用恰当, 2012年9月2日, 請按照校對指引, 幫助编辑這個條目, 幫助, 討論, 是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法, 由莱斯利, 兰波特发明, 目录, 算法, 类比, 进入临界区, 非临界区, 算法实现, 定义, 伪代码, 讨论, 参见, 外部链接, 参考文献算法, 编辑类比, 编辑, lamport把这个并发控制算法非常直观地类比为顾客去面包店采购, 面包店一次只能接待一位顾客的采购, 已知有. 此條目需要編修 以確保文法 用詞 语气 格式 標點等使用恰当 2012年9月2日 請按照校對指引 幫助编辑這個條目 幫助 討論 Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法 由莱斯利 兰波特发明 1 目录 1 算法 1 1 类比 1 2 进入临界区 1 3 非临界区 2 算法实现 2 1 定义 2 2 伪代码 2 3 讨论 3 参见 4 外部链接 5 参考文献算法 编辑类比 编辑 Lamport把这个并发控制算法非常直观地类比为顾客去面包店采购 面包店一次只能接待一位顾客的采购 已知有n位顾客要进入面包店采购 按照次序安排他们在前台登记一个签到号码 该签到号码逐次增加1 顾客根据签到号码的由小到大的顺序依次入店购货 完成购买的顾客在前台把其签到号码归0 如果完成购买的顾客要再次进店购买 就必须重新排队 这个类比中的顾客就相当于线程 而入店购货就是进入临界区独占访问该共享资源 由于计算机实现的特点 存在两个线程获得相同的签到号码的情况 这是因为两个线程几乎同时申请排队的签到号码 读取已经发出去的签到号码情况 这两个线程读到的数据是完全一样的 然后各自在读到的数据上找到最大值 再加1作为自己的排队签到号码 为此 该算法规定如果两个线程的排队签到号码相等 则线程id号较小的具有优先权 进入临界区 编辑 已经拿到排队签到号码的线程 要轮询检查自己是否可以进入临界区 即检查n个线程中 自己是否具有最小的非0排队签到号码 或者自己是具有最小的非0排队签到号码的线程中 id号最小的 可以用伪代码表示上述检查 a b lt c d 等价于 a lt c or a c and b lt d 非临界区 编辑 一旦线程在临界区执行完毕 需要把自己的排队签到号码置为0 表示处于非临界区 算法实现 编辑定义 编辑 数组Entering i 为真 表示进程i正在获取它的排队登记号 数组Number i 的值 是进程i的当前排队登记号 如果值为0 表示进程i未参加排队 不想获得该资源 规定这个数组元素的取值没有上界 正在访问临界区的进程如果失败 规定它进入非临界区 Number i 的值置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 lt 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 amp amp Number j j lt 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 只读取其它线程的这两个数据项 这个算法不需要基于硬件的原子 atomic 操作实现 即它可以纯软件实现 使用Entering数组是必须的 假设不使用Entering数组 那么就可能会出现这种情况 设进程i的优先级高于进程j 即i lt j 两个进程获得了相同的排队登记号 Number数组的元素值相等 进程i在写Number i 之前 被优先级低的进程j抢先获得了CPU时间片 这时进程j读取到的Number i 为0 因此进程j进入了临界区 随后进程i又获得CPU时间片 它读取到的Number i 与Number j 相等 且i lt j 因此进程i也进入了临界区 这样 两个进程同时在临界区内访问 可能会导致数据腐烂 data corruption 算法使用了Entering数组变量 使得修改Number数组的元素值变得 原子化 解决了上述问题 具体实现时 可以把上述伪代码中的忙等待 busy wait 换成交出线程的执行权 例如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参考文献 编辑 Original Paper PDF 2012 09 02 原始内容存档 PDF 于2007 04 18 On his publications page 页面存档备份 存于互联网档案馆 Lamport has added some remarks regarding the algorithm 取自 https zh wikipedia org w index php title Lamport面包店算法 amp oldid 71758049, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。