词条 | 面包店算法 |
释义 | 算法目的用于解决多线程同步 算法思想该算法的基本思想源于顾客在面包店中购买面包时的排队原理. 顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和Pj, 如果有i<j, 则先为Pi服务, 即Pi先进入临界区 算法代码boolean choosing[n];表示进程是否在取号 int number[n];记录每个进程取到的号码 这些数据结构分别初始化为false和0,为了方便,定义如下符号: 若a<c或a==c和b<d同时成立,(a,b)<(c,d) do { choosing[i] = true; number[i] = max{number[0],number[1],…,number[n-1]}+1;//选号码 choosing[i] = false; for(j = 0; j<n; j++) { while (choosing[j]); while ((number[j] != 0) && (number[j],j)<(number[i],i)); }; //临界区 number[i] = 0; //其余部分 }while(1); |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。