Lamport面包店算法
算法
类比
Lamport把这个并发控制算法非常直观地类比为顾客去面包店采购。面包店一次只能接待一位顾客的采购。已知有n位顾客要进入面包店采购,按照次序安排他们在前台登记一个签到号码。该签到号码逐次增加1。顾客根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0。 如果完成购买的顾客要再次进店购买,就必须重新排队。
这个类比中的顾客就相当于线程,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点,存在两个线程获得相同的签到号码的情况,这是因为两个线程几乎同时申请排队的签到号码,读取已经发出去的签到号码情况,这两个线程读到的数据是完全一样的,然后各自在读到的数据上找到最大值,再加1作为自己的排队签到号码。为此,该算法规定如果两个线程的排队签到号码相等,则线程id号较小的具有优先权。
进入临界区
已经拿到排队签到号码的线程,要轮询检查自己是否可以进入临界区。即检查n个线程中,自己是否具有最小的非0排队签到号码;或者自己是具有最小的非0排队签到号码的线程中,id号最小的。
可以用伪代码表示上述检查:
等价于:
非临界区
一旦线程在临界区执行完毕,需要把自己的排队签到号码置为0,表示处于非临界区.
算法实现
定义
数组Entering[i]为真,表示进程i正在获取它的排队登记号;
数组Number[i]的值,是进程i的当前排队登记号。如果值为0,表示进程i未参加排队,不想获得该资源。规定这个数组元素的取值没有上界。
正在访问临界区的进程如果失败,规定它进入非临界区,Number[i]的值置0,即不影响其它进程访问这个互斥资源。
伪代码
// declaration and initial values of global variablesEntering:array[1..NUM_THREADS]ofbool={false};Number:array[1..NUM_THREADS]ofinteger={0};1lock(integeri){2Entering[i]=true;3Number[i]=1+max(Number[1],...,Number[NUM_THREADS]);4Entering[i]=false;5for(j=1;j<=NUM_THREADS;j++){6// Wait until thread j receives its number:7while(Entering[j]){/* nothing */}8// Wait until all threads with smaller numbers or with the same9// number, but with higher priority, finish their work:10while((Number[j]!=0)&&((Number[j],j)<(Number[i],i))){/* nothing */}13}14}1516unlock(integeri){17Number[i]=0;18}1920Thread(integeri){21while(true){22lock(i);23// The critical section goes here...24unlock(i);25// non-critical section...26}27}
讨论
每个线程只写它自己的Entering[i]、Number[i],只读取其它线程的这两个数据项。
这个算法不需要基于硬件的原子(atomic)操作实现,即它可以纯软件实现。
使用Entering数组是必须的。假设不使用Entering数组,那么就可能会出现这种情况:设进程i的优先级高于进程j(即i),两个进程获得了相同的排队登记号(Number数组的元素值相等)。进程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算法
信号量
参考文献
On hispublications page, Lamport has added some remarks regarding the algorithm.
免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。
- 有价值
- 一般般
- 没价值