6.3Peterson方法解决临界区问题

6.3Peterson 方法解决临界区问题

Peterson解决方案适用于两个进程错的执行临界区与剩余区的情况。

假设两个进程是 P₀ 和P₁ ，同时为了方便，当使用P_i时，另外一个进程使用P_j表示，即 j == 1 - i 。

Perterson 解决方案要求两个进程共享两个数据项：

int turn;
boolean flag[2];


其中，flag表示哪个进程准备进入临界区，或者说哪个进程有了进入临界区的需求，例如flag[i] == true，则说明进程P_i有需求进入临界区。turn则表示，哪一个进程可以进入临界区，如turn == 1 ，则说明现在p₁可以进入临界区。

有关于Peteson解决方法的具体实现，有谦让式和争夺式两种。

一、谦让式

//课本上提供的进程i的结构
do {
flag[i] = true ;
turn = j ;
while (flag[j] && turn == j);//在进程i能够执行前会在这里无限循环
//临界区
flag[i] = false ;
//剩余区
} while (true)


为什么说这种方式是谦让式，我们可以具体的看一下两个进程在进入区的代码：

//进程i的进入区代码
flag[i] = true ;
turn = j ;
while (flag[j] && turn == j);
//进程j的进入区代码
flag[j] = true ;
turn = i ;
while (flag[i] && turn == i);


每个进程在需要进入临界区时，会先把自己对应的flag设定为 true ，表示自己需要进入临界区。然后却把 turn 设定为对方，即把进入临界区的机会“谦让”给对方，所以称为谦让式。

对于该方法的分析：

对于进程P_i ，假设它准备进入临界区，他会把自己的flag设定为true，然后把turn设定为j，将进入临界区机会让给进程j，然后便是重点：

• 假如这时进程 j 没有进入临界区需求，即此时i、j 进程没有并发执行，那么flag[j] == false，则 进程 i 就会顺利进入临界区，相当于是谦让给对方，但对方不需要，就有拿回来了。


• 假设这时进程 j 正在临界区中，那么这时会有 flag[j] == true && turn == j ，进程 i 会先在while中无限循环，等待进程 j 完成，把flag[j] 设定为 false。


• 假如这时进程 j 也需要进入临界区，即此时i、j 进程并发执行。那么在这时进程 j 也会有这样的操作，把自己的flag设定为 true ，同时把turn设定为对方，把进入临界区的机会让给对方。那么，双方谦让肯定存在顺序。假设是进程 i 先谦让，那么机会会先交给进程 j 然后又谦让回来，进程 i 进入临界区，进程 j 等待。反之，假设进程 i 后谦让，那么机会最终还是要让给进程 j 的。


• 那么我们不难推出结论，无论以上的指令是以什么次序执行的，总会有且只有一个进程获得了从对方那里让来的进入临界区的机会，而这个进程本身必然是先进行谦让的那个。


• 在这种谦让式的peterson中，先谦让的必然是先进入临界区。

二、抢夺式

#define FALSE 0
#define TRUE 1
#define N 2 /* 进程数量 */

int turn; /* 现在轮到谁？*/
int interested[N]; /* 所有值初始化为0（FALSE）*/
void enter_region(int process) /* 进程是0或1 */
{
int other; /* 其他进程号 */
other = 1 - process; /* 另一方进程 */
interested[process] = TRUE; /* 表名所感兴趣的 */
turn = process; /* 设置标志 */
while(turn == process && interested[other] ==TRUE); /* 空语句 */
}
void leave_region(int process) /* 进程：谁离开？*/
{
interested[process] = FALSE; /* 表示离开临界区 */
}


// 关键代码
interested[process] = TRUE;
turn = process;
while(turn == process && interested[other] == TRUE);


抢占式代码和谦让式有点不一样但原理是相同的：

在抢占式，用process表示自己进程，用other表示另一个。interested[] 和flag[] 相同作用。

抢占式中，进程 i 准备进入临界区，他会把自己的interested设定为true，然后把turn设定为process，也就是自己，将进入临界区机会抢到自己手上，剩下的分析和谦让式相同。

总结

无论是谦让式还是抢夺式，他们都满足了解决临界问题的三个要求：

1. 互斥


2. 进步


3. 有限等待