面包店算法

转自维基百科http://zh.wikipedia.org/wiki/Lamport%E9%9D%A2%E5%8C%85%E5%BA%97%E7%AE%97%E6%B3%95

Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明^[1]。

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

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

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

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

等价于:

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

• 数组Entering[i]为真，表示进程i正在获取它的排队登记 ；
• 数组Number[i]的值，是进程i的当前排队登记 。如果值为0，表示进程i未参加排队，不想获得该资源。规定这个数组元素的取值没有上界。
• 正在访问临界区的进程如果失败，规定它进入非临界区，Number[i]的值置0，即不影响其它进程访问这个互斥资源。

每个线程只写它自己的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操作.

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33885 人正在系统学习中