族谱网 头条 人物百科

Lamport面包店算法

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:591
转发:0
评论:0
算法类比Lamport把这个并发控制算法非常直观地类比为顾客去面包店采购。面包店一次只能接待一位顾客的采购。已知有n位顾客要进入面包店采购,按照次序安排他们在前台登记一个签到号码。该签到号码逐次增加1。顾客根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0。如果完成购买的顾客要再次进店购买,就必须重新排队。这个类比中的顾客就相当于线程,而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点,存在两个线程获得相同的签到号码的情况,这是因为两个线程几乎同时申请排队的签到号码,读取已经发出去的签到号码情况,这两个线程读到的数据是完全一样的,然后各自在读到的数据上找到最大值,再加1作为自己的排队签到号码。为此,该算法规定如果两个线程的排队签到号码相等,则线程id号较小的具有优先权。进入临界区已经拿到排队签到号码的线程,要轮询检查自己是否可以进入临界区。即检查n...

算法

类比

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.


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 算法
历史算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法,线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法:刘徽割圆术。自唐代以来,历代更有许多专门论述“算法”的专著:唐代:《一位算法》一卷,《算法》一卷;宋代:《算法绪论》一卷、《算法秘诀》一卷;最著名的是杨辉的《杨辉算法》;元代:《丁巨算法》;明代:程大位《算法统宗》清代:《开平算法》、《算法一得》、《算法全书》。而英文名称“Algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی‎,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世...
· Paxos算法
问题和假设分布式系统中的节点通信存在两种模型:共享内存(Sharedmemory)和消息传递(Messagespassing)。基于消息传递通信模型的分布式系统,不可避免的会发生以下错误:进程可能会慢、被杀死或者重启,消息可能会延迟、丢失、重复,在基础Paxos场景中,先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致,保证不论发生以上任何异常,都不会破坏决议的一致性。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就...
· CYK算法
相关参数定义G=(V,ΣΣ-->,S,P){\displaystyle~G=(V,\Sigma,S,P)}是一个上下文无关文法对于任意字符串w=σσ-->1...σσ-->n∈∈-->ΣΣ-->∗∗-->{\displaystylew=\sigma_{1}...\sigma_{n}\in\Sigma^{*}},定义w[i,j]=σσ-->i...σσ-->j,1≤≤-->i≤≤-->j≤≤-->n{\displaystylew[i,j]=\sigma_{i}...\sigma_{j},~1\leqi\leqj\leqn}对于任意选择的i,j{\displaystyle~i,j},定义Vi,j={X∈∈-->V|X⇒⇒-->∗∗-->w[i,j]}{\displaystyleV_{i,j}=\{X\inV~|...
· 双鱼算法
概要双鱼算法有128、192、256位三种密钥长度可供选择,块大小为128位,可以看作是布鲁斯·施奈尔1993年开发的Blowfish算法的延伸版本。技术上使用与Blowfish类似的计算方法,但是考虑到主要面向于网络应用,提高了更大密钥算法的速度。与Blowfish算法一样,双鱼算法无须授权即可使用。参考资料
· Kosaraju算法
简介该算法主要用于枚举图中每一个强连通分量内的所有顶点。该算法可由以下四部分组成:对有向图G{\displaystyleG}取逆,得到G{\displaystyleG}的反向图GR{\displaystyleG^{R}}利用深度优先搜索求出GR{\displaystyleG^{R}}的逆后排序对G{\displaystyleG}按照上述逆后排序的序列进行深度优先搜索同一个深度优先搜索递归子程序中访问的所有顶点都在同一个强连通分量内Java代码实现publicclassKosarajuAlgorithm{privateboolean[]marked;privateint[]id;privateintcount=-1;privateStackreversePostOrder;publicKosarajuAlgorithm(DigraphG){//G.V()返回有向图G的边数marked=new...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信