进程互斥bakery算法改进的思想

开篇：润墨网以专业的文秘视角，为您筛选了一篇进程互斥bakery算法改进的思想范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 本文简要地介绍了bakery算法进程互斥思想，指出它存在的三个缺点。然后在满足进程互斥设计三要点的前提下，提出快速互斥算法，并且对它的性能和优点给出证明，指出快速算法能够很好地解决bakery算法的缺点。

关键词： bakery算法 快速算法 进程互斥 空闲让进 有限等待

1.进程互斥算法的应用背景

如今，互联网上有大量的资源供用户使用，这些资源很多都是临界资源。互联网上大量进程都要使用这些临界资源。由于临界资源共享时要互斥访问，这就使得这些进程在访问临界资源时要互斥进入自己的临界区。

进程互斥进入临界区算法设计时要注意三点：（1）互斥访问（mutual exclusion）［１］［２］［３］，即是每次只能有一个进程进入自己的临界区，同一时间不能两个或两个以上进程进入临界区。（2）空闲让进（progress），即是当没有进程在临界区执行，有一些进程要进入临界区时，只有那些不在remainder section中执行的进程有权决定谁进入临界区，并且这决定不能无限推迟。（3）有限等待（bounded waiting），即是进程从申请进入临界区到进入临界区这段时间是一段有限的时间，进程不能无限等待进入。

互联网上共享临界资源进程只有遵循以上三点，进程执行的结果才不会出错。也只有在遵循以上三点的基础上，互联网上的应用程序才能为用户提供可靠的资源访问。

目前，对进程互斥分布式算法设计主要分为三类，即（1）permission-based（e.g.Lamport，Ricart-Agrawala，Singhal，Maekawa ），思想是每一个进程在进入临界区之前要得到所有其他进程的准许。（2）token-based （Suzuki-Kazami，Raymond ，Naimi-Trehel，Neilsen-Mizuno，Chang，Singhal and Liu ），思想是整个系统有一个token，只有得到token的进程才能进入临界区。（3）Quorum based，思想是所有进程中，部分进程决定某进程是否可以进入临界区。

2.bakery算法设计的思想

Bakery算法是一种简单的处理n个进程互斥进入临界区的算法。它基于面包店里普遍使用的一种算法。顾客进入面包店的时候首先得到一个服务号码，得到最小号码的顾客首先得到服务。基于这一思想，bakery算法处理N个进程互斥时对共享变量的读写采用原子操作来实现，每个进程都拥有一个属于自己的共享变量。这个共享变量指示本进程在等待进入临界区的位置，只有当本变量指示等待队列的头部时，本进程才优先进入临界区。只有本进程才可以对属于自己的共享变量读写，别的进程只能读。Bakery算法代码如图1。

在本算法中，不同顾客可能得到同一个号码。为此，我们有定义1。

定义1：有二元组（number［i］，i）和（number［j］，j），当number［i］＜number［j］或者number［i］=number［j］并且i＜j时，有（number［i］，i）＜（number［j］，j）。

定义1的意思是：顾客i的服务号码number［i］＜顾客j的服务号码number［j］时，或者顾客i和顾客j的服务号码相等，但i＜j时，顾客i先服务。在图1中，Bakery算法满足下面三个申明。

申明（1）（进程互斥）

［?坌0…N-1 i，j，i!=j：：Z（i，j）］，where Z（i，j）：（πid［i］ on CS∧id［j］ on CS）

申明（2）（空闲让进）

［?坌0…N-1 i：：P（i）］［?坌0…N-1 i：：Q（i）］ where

P（i）：πid［i］ on CSπid［i］ at b1

Q（i）：πid［i］ at a1πid［i］ on CS

申明（3）（有限等待）

max（Time（i）boundwait）=（N-1）*（T1+T2）其中Time（i）boundwait为进程i从申请进入临界区到进入临界区的等待时间。

T1为执行a2：num［i］=max（num［0］，num［1］，…，num［N-1］）+1所用时间；

T2为执行临界区代码所用时间。

3.用快速算法对bakery算法的改进

bakery算法解决了n个进程互斥问题，满足进程互斥时三要点。但bakery算法存在以下实际的缺点。

（1）总是有进程在临界区时，进程申请进入临界区的服务号将无限变大（unbounded number）。

（2）使用的共享变量多，两个共享数组有2N个共享变量，在分布式环境下使得进程之间信息交换量增大。

（3）程进入临界区之前要和N-1个进程的服务号进行比较，不管是否有别的进程要进入临界区，这无疑会使进程的运行速度变慢。

为此我们提出了进程互斥的快速算法（fast for n processes），可以有效地解决以上bakery算法存在的问题。

为了引入快速算法，先还是引入快速算法的简单情况，两个进程的快速算法。可以把bakery算法分成六个部分：start，doorway，ticket assignment，wait section，critical section and final。Start即执行算法初始化代码，进程i在doorway处即进程i执行完了choosing［i］=true，ticket即执行Number［i］=1+max（Number［1］，...，Number［N］），wait section即互斥循环，critical section即临界区，final即出临界区善后代码。而快速算法的思想是设置gate1和gate2，只有同时得到gate1和gate2进程优先进入临界区，并且后得到者优先进入临界区。在快速算法中我们假定对共享变量的操作都是原子操作。图2是两个进程的快速算法。

断言1：（csp∧csq）是重言式（进程互斥）。

证明：反正法。假设（csp∧csq）为真。

csp（gate1=p）∨（waitq=false∧gate2=p）（1）

csq（gate1=q）∨（waitp=false∧gate2=q）（2）

由（1）、（2）得（（gate1=p）∨（waitq=false∧gate2=p））∧（（gate1=q）∨（waitp=false∧gate2=q））真，得（（gate1=p）∧（gate1=q））∨（（gate1=p）∧（waitp=false∧gate2=q））∨（（gate1=q）∧（waitq=false∧gate2=p））∨（（waitq=false∧gate2=p）∧（waitp=false∧gate2=q））……分配律

（3）为真。

式子（3）中用∨连接的每一项都是假。（gate1=p）∧（gate1=q）为假，而（gate1=p）∧（waitp=false∧gate2=q）时csp和csq不能同时成立，所以此式也为假，同理（gate1=q）∧（waitq=false∧gate2=p）为假，而（waitq=false∧gate2=p）∧（waitp=false∧gate2=q）也为假，得到矛盾。

断言2：两个进程的快速算法满足空闲让进的原则。

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文

证明：（1）当p已经执行到临界区而q刚执行（不同时执行算法时），p进入临界区。

（2）当p，q同时到达时，记late（p，gate1）为p后写gate1，记late（q，gate1）为q后写gate1，记late（p，gate2）为p后写gate2，记late（q，gate2）为q后写gate2。

（2.1）late（p，gate1）∧late（p，gate2）时，csp为真；

（2.2）late（p，gate1）∧late（q，gate2）时，csq为真；

（2.3）late（q，gate1）∧late（q，gate2）时，csq为真；

（2.4）late（q，gate1）∧late（p，gate2）时，csp为真，证明完毕。

断言3：两个进程的快速算法满足有限等待的原则。

证明：（1）当p已经执行到临界区而q刚执行（不同时执行算法时），p进入临界区。两进程直接进入临界区，不用等待其他进程。

（2）当p，q同时到达时，

（2.1）late（p，gate1）∧late（p，gate2）时，csp为真，p直接进入临界区；q阻塞在q4，等待时间为p执行临界区的时间（常数）。

（2.2）late（p，gate1）∧late（q，gate2）时，csq为真，q等待常数时间；p阻塞在p2，等待时间为q执行临界区的时间（常数）。

（2.3）late（q，gate1）∧late（q，gate2）时，csq为真，q直接进入临界区；q阻塞在q2，等待时间为p执行临界区的时间（常数）。

（2.4）late（q，gate1）∧late（p，gate2）时，csp为真，p等待常数时间，q阻塞在q2，等待时间为p执行临界区的时间（常数）。证明完毕。

快速算法n个进程情况只需对两个进程情况稍加修改，引入数组wait［n］，n个进程都竞争gate1，gate2。算法如图3。

显然，快速算法n个进程情况跟快速两个进程的情况一样，满足互斥、空闲让进、有限等待三要点，显然有下面断言。

断言4：如果csi为真，则?坌j（1…N）j≠i，csj是重言式（进程互斥）。

断言5：N个进程的快速算法满足空闲让进的原则。

证明：（1）当N个进程两两不同时到达时，各进程直接进入临界区。

（2）当N个进程同时到达时，最后写gate2的进程首先进入临界区，剩下N-1个进程最后写gate2的进程首先进入临界区。

断言6：N个进程的快速算法满足有限等待的原则。

证明：各个进程的平均等待的时间为O（N２），满足有限等待。

4.快速算法的性能和优势分析

我们对快速算法的性能和优势总结以下几点。

（1）总是有进程在临界区时，不会出现进程申请进入临界区的服务号将无限变大（unbounded number）的情况，因为快速算法n个进程情况没有用到服务号。

（2）使用的共享变量只有N个，即wait［0…N-1］，比bakery算法的2N个共享变量少N个，大大减少在分布式环境下进程之间信息交换量。

（3）bakery算法中，当没有别的进程进入临界区时，本进程进入临界区之前要和N-1个进程的服务号进行比较，而快速算法此情况下本进程直接进入临界区，提高了速度；当有N个进程竞争进入临界区时，快速算法中各个进程少max（Number［1］，...，Number［N］）操作，同时少本进程同其他进程号比较操作，大大提高了进程的执行速度。

5.结论

对bakery算法进行改进后的快速算法克服了服务号将无限变大（unbounded number）的弊端，同时减少了分布式环境进程之间的信息交换量，提高了进程的执行速度，而且满足进程互斥设计时的互斥，空闲让进、有限等待三要点。快速算法的引入将大大提高互联网上的资源共享的效率，提高互联网应用程序的运行效率。

参考文献：

［1］Chen，Y，Welch，J.Self-Stabilizing Mutual Exclusion Using Tokens in Mobile Ad Hoc Networks.Proceedings of the 6th international workshop on Discrete Algorithms and methods for mobile computing and communications，2002：34-42.

［2］Sujata Banerjee.A New Token Passing Distributed Mutual Exclusion Algorithm.Proceedings of the Intl.Conf.on Distributed Computing Systems （ICDCS），1996.

［3］Hadzilacos V.A Note on Group Mutual Exclusion，Proceedings of the 20th ACM Symposium on Principles of Distributed Computing （PODC），2001.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文