第一次尝试

爱斯基摩人的小屋协议执行环境：门和小屋很小，每次只能容纳一个人进入，小屋内有一个标志黑板。

进程申请进入临界区时，必须首先进入小屋并检查黑板标志是否能进入临界区。

• 是，离开小屋，进入临界区，执行完毕，退出临界区，并返回小屋，修改黑板标志为其他进程。

• 否，反复进入小屋，检查黑板标志，直到标志是自己。

int turn = 0; // 共享的全局变量

// Process 0
{
    ...
    while (turn != 0); // turn不等于0时什么也不做
    <critical section>; // 临界区
    turn = 1;
    ...
}

// Process 1
{
    ...
    while (turn != 1); // turn不等于1时什么也不做
    <critical section>; // 临界区
    turn = 0;
    ...
}

解析：保证了互斥但存在问题。进程"忙等"进入临界区，若黑修改失败，其他进程永久阻塞。

第二次尝试

爱斯基摩人的小屋协议执行环境：每个人有一个自己的小屋，但看别人的标志，以确定是否进入临界区。

每个人只能检查，但不能修改他人的黑板标志。

若某人申请进入临界区，首先检查对方黑板是否为“false”

• 是，修改自己小屋黑板值为“true”，进入临界区执行，执行完毕，恢复黑板值为“false”。

• 否，反复进入小屋，检查黑板标志，直到标志是“false”。

bool flag[2]; // 共享全局变量

// Process 0
{
    ...
    while(flag[1]);
    flag[0]=true;
    <critical section>;
    flag[0]=false;
    ...
}

// Process 1
{
    ...
    while(flag[0]);
    flag[1]=true;
    <critical section>
    flag[1]=false;
    ...
}

解析：若进程执行完临界区，恢复自己标志为"false"失败，则其他进程永久阻塞。

第三次尝试

在检查其他进程之前，希望进到临界区，则设置自己flag=true。

当设置标志为真后，如果其他进程在临界区，则本进程阻塞，直到其他进程释放临界区为止。

bool flag[2]; // 共享的全局变量

// Process 0
{
    ...
    flag[0]=true; // 与二区别：提到while前
    while(flag[1]);
    <critical section>;
    flag[0]=false;
    ...
}

// Process 1
{
    ...
    flag[1]=true; // 与二区别：提到while前
    while(flag[0]);
    <critical section>;
    flag[1]=false;
    ...
}

解析：如果两个进程在执行while之前都把flag设置成true，那么每个进程都会以为对方进入了临界区，使自己处于阻塞，从而导致死锁。

第四次尝试

第四次尝试主要思想是将标志重置，不会发生死锁。

实现过程：

• 希望进到临界区，则设置自己标志为：flag=true。

• 如果其他进程在临界区，则将本进程标志置为flag=false，稍后又置为true，这一过程重复到能进入临界区为止。

bool flag[2]; // 共享的全局变量

// Process 0
{
    ...
    flag[0]=true;
    while(flag[1])
    {
        flag[0]=false;
        <delay for a short time>;
        flag[0]=true;
    } // 通过这个等待解决三的问题
    <critical section>;
    flag[0]=false;
    ...
}

// Process 1
{
    ...
    flag[1]=true;
    while(flag[0])
    {
        flag[1]=false;
        <delay for a short time>;
        flag[1]=true;
    } // 通过这个等待解决三的问题
    <critical section>;
    flag[1]=false;
    ...
}

解析：检查其它进程，然后重置，再检查，再重置……

重置序列可以无限延伸，任何一个进程都不能进入自己的临界区。（这种现象称为：互斥礼让）

解决"互斥礼让"方法一

为了解决"互斥礼让"问题的第一种算法，其主要思想是：需要两个变量turn和flag，再控制执行顺序，先判flag，再判turn。

1. turn指出应该哪一个进入临界区

   turn=0 表示P0可以进入临界区 turn=1 表示P1可以进入临界区

2. flag指出当前哪一个在临界区

   flag=0 表示P0当前在临界区 flag=1 表示P1当前在临界区

bool flag[2];
int turn; // 准许进入临界区标志变量
while(1)
{
    flag[0]=false;
    flag[1]=false;
    turn=0; // 设P0进程在临界区
    {
        p0; p1;
    }
}

procedure p0;
while(1)
{
    flag[0]=true; // 初值为真，p0希望进入临界区
    while(flag[1]) // 查p1进程标志
    {
        if(turn==1) // turn为1，表明p1进程在临界区
        {
            flag[0]=false;
            while(turn==1); // 当turn为1表明p0不能进入临界区，阻塞
            flag[0]=true; // 设标志为真，p0进入临界区
        }
        <critical section>; // 如果turn=0，则p0可进入临界区执行
        turn=1; // 执行结束，p0退出临界区，则p1进程可进临界区
        flag[0]=false; // 表明p0不在临界区
        ...
    }
}

procedure p1;
while(1)
{
    flag[1]=true; // 初值为真，p1希望进入临界区
    while(flag[0]) // 查p0进程标志
    {
        if(turn==0) // turn为0，表明p0进程在临界区
        {
            flag[1]=false;
            while(turn==0); // 当turn为0表明p1不能进入临界区，阻塞
            flag[1]=true; // 设标志为真，p1进入临界区
        }
        <critical section>; // 如果turn=1，则p1可进入临界区执行
        turn=0; // 执行结束，p1退出临界区，则p0进程可进临界区
        flag[1]=false; // 表明p1不在临界区
        ...
    }
}

解析（分析p0的执行）

1. flag[0] = true; // 设自己为真

2. 执行while(flag[1])语句有两种情况

   • 当flag[1] == false，p0进入临界区，执行结束

     • 置turn = 1; flag[0] = false;

   • 当flag[1] == true，检查turn的值，turn的值又有两种情况

     • turn == 1，p1在临界区，p0处于"忙等"
     • turn == 0，P1已退出（但还未修改flag的值），p0立即进入

解决"互斥礼让"方法二

简单的互斥方案：turn解决同时的冲突，Flag指示进程是否在临界区。对两参量同时控制，交替进入临界区执行。

bool flag[2];
int turn;

while(1)
{
    flag[0]=false;
    flag[1]=false;
    turn=1; // 假设p1进程可先进临界区
    {
        p0; p1;
    }
}

procedure p0;
while(1)
{
    flag[0]=true;
    turn=1;
    while(flag[1] && turn==1);
    <critcal section>;
    flag[0]=false;
    ...
}

procedure p1;
while(1)
{
    flag[1]=true;
    turn=0;
    while(flag[0] && turn==0);
    <critical section>;
    flag[1]=false;
    ...
}

解析（分析p0的执行）

1. flag[0] = true; // 阻止P1进入临界区

2. 执行while(flag[1])

   • 当flag[1] == false时，p0进入，执行完成，置flag[0] = false;
   • 当flag[1] == true时，p0阻塞，等待P1退出