皮特森算法

2018-12-1423:48:10 评论 2,350 views

Peterson's Algorithm = 皮特森算法

皮特森算法为单标志法和双标志法后检查的结合。

为防止两个进程(假设为:P0 P1)为进入临界区而无限期等待,又设置变量 turn,每个进程在设置自己标志后再设置 turn 标志。这时,再同时检测另一个进程的状态标志和不允许进入标志,这样可以保证当进程同时要求进入临界区,只允许一个进程进入临界区。

伪代码如下:
P0 进程:

//flag[0]=true, 表示P0进程想进入临界区;
//turn=1, 表示P1你先进入吧(礼让一下);
flag[0] = TRUE; turn = 1;           //进入区

//如果此时检测到P1已经进入临界区,且上面一句礼让了给了P1,那么此时P0进程等待;
//如果此时检测到P1还没有想进入临界区(flag[1]=false),则此while条件不满足即P0可以进入临界区:
while(flag[1] && turn == 1);        //进入区

critical section;                   //临界区伪代码

//表示P0此时不想进入临界区了:
flag[0] = FALSE ;                   //退出区

P1 进程:

//flag[1]=true, 表示P1进程想进入临界区;
//turn=0, 表示P0你先进入吧(礼让一下);
flag[1] = TRUE; turn = 0;           //进入区

//如果此时检测到P0已经进入临界区,且上面一句礼让了给了P0,那么此时P1进程等待;
//如果此时检测到P0还没有想进入临界区(flag[0]=false),则此while条件不满足即P1可以进入临界区:
while(flag[0] && turn == 0);        //进入区

critical section;                   //临界区伪代码

//表示P1此时不想进入临界区了:
flag[1] = FALSE;                    //退出区

本算法的基本思想是:单标志法和双标志法算法的结合。
优点:利用 flag标志 解决临界资源的互斥访问,而利用 turn标志 解决“饥饿”现象。
缺点:并不能解决“让权等待”原则;

历史上的今天
12月
14

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: