多线程互斥锁访问算法（下）——Lamport算法(面包店算法)

你好！这里是风筝的博客，

欢迎和我一起交流。

Lamport面包店算法是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport发明。

Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购：
已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到 码。该签到 码逐次加1。
根据签到 码的由小到大的顺序依次入店购货。
完成购买的顾客在前台把其签到 码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
同时进入面包店采购的两个或两个以上的顾客有可能得到相同的 码。
多个顾客如果抓到相同的 码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的。

在计算机系统中, 顾客就相当于线程，每个进程有一个唯一的标识,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到 码的情况，这是因为两个线程几乎同时申请排队的签到 码，这两个线程读到的 码是完全一样的。所以，该算法规定如果两个线程的排队签到 码相等，则线程id 较小的具有优先权。

我在看一些文章时，发现有如下描述:

但是我看了产生歧义，看了好一会才理解，应该这样写才好：

这样就好理解多了。

核心代码如下：

这就是lamport的核心算法，当我们需要访问临界区（互斥资源）时：

我们可以举例模拟一下：
有两个线程A（thread_id=1）和B（thread_id=2），
情况一：
当线程A进入enter_lock(1);，选取的 码为1（number[1]=1），此时，无其他线程占用资源。
for循环遍历时，i=1时，对应的是线程A的数据，第二个while不成立，线程A得到资源时。

情况二：
当线程A进入enter_lock(1);，选取的 码为1（number[1]=1），此时，系统调度，线程B运行，线程B得到的 码为2（number[2]=2）。
for循环遍历时，i=1时，对应的是线程A的数据，第二个while为：
while((number[1] != 0)&&( (number[1] < number[2]) || ((number[1] == number[2]) && (1 < 2)) ));
可知，while条件成立，则阻塞，待线程A释放资源时，才得以运行。

情况三：
当线程B进入enter_lock(2);，选取的 码为1（number[2]=1），此时，系统调度，线程A运行，线程A得到的 码为2（number[1]=2）。
for循环遍历时，i=2时，对应的是线程B的数据，第二个while为：
while((number[2] != 0)&&( (number[2] < number[1]) || ((number[2] == number[1]) && (2 < 1)) ));
可知，while条件成立，则阻塞，待线程B释放资源时，才得以运行。

这样，每个线程只写它自己的choosing[thread_id]、number[thread_id]，只读取其它线程的这两个数据项。
这个算法不需要基于硬件的原子(atomic)操作实现，即它可以纯软件实现。
解决了peterson算法的局限，使得多个线程能参与互斥竞争。
多线程互斥锁访问算法（上）——Peterson算法

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