【软件实现方法】

软件实现方法，是在进入区设置和检查一些标志，来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后，在退出区修改标志

单标志法

单标志法其通过设置一个公用整型变量 turn，来指示被允许进入临界区的进程编号，从而确保每次只允许一个进程进入临界区，例如，当 turn=0 时，允许进程 $P_0$ 进入临界区

int turn;
void init() {
    turn = 0;
}
void P0() {            //P0进程
    while (turn != 0); //进入区
    critical section;  //临界区
    turn = 1;          //退出区
    remainder section; //剩余区
}
void P1() {            //P1进程
    while (turn != 1); //进入区
    critical section;  //临界区
    turn = 0;          //退出区
    remainder section; //剩余区
}

但该算法违反了空闲让进原则，其要求两个进程交替进入临界区，如果某个进程不再进入临界区，那么另一个进程也无法进入临界区

例如，$P_0$ 进入临界区并从临界区离开，那么此时临界区是空闲的，但 $P_1$ 并没有进入临界区的打算，trun=1 会一直成立，$P_0$ 会被 while 死循环困住，无法进入临界区

双标志先检查法

双标志先检查法的基本思想是在每一个进程访问临界区资源前，先检查临界资源是否正在被访问，若正被访问，该进程需要等待，若未被访问，该进程才可进入临界区

该方法设置了一个 flag[i] 标志，标识第 $i$ 个进程 $P_i$ 是否已经进入临界区，若 flag[i]=ture，表示 $P_i$ 已经进入临界区，若 flag[i]=false，表示 $P_i$ 未进入临界区

bool flag[2];
void init() {
    flag[0] = false;
    flag[1] = false;
}
void P0() {            //P0进程
    while (flag[1]);   //1 进入区
    flag[0] = true;    //2
    critical section;  //3 临界区
    flag[0] = false;   //4 退出区
    remainder section; //剩余区
}
void P1() {            //P1进程
    while (flag[0]);   //5 进入区
    flag[1] = true;    //6
    critical section;  //7 临界区
    flag[1] = false;   //8 退出区
    remainder section; //剩余区
}

按 $1$、$5$、$2$、$6$、$3$、$7\dots$ 的顺序，可能会导致 $P_0$、$P_1$ 同时访问临界区，违反了忙则等待原则

这是因为先检测对方进程状态标志后，再设置自己的标志，由于检测和放置中可插入另一个进程到达时的检测操作，从而可能造成两个进程分别检测后同时进入临界区

双标志后检查法

双标志后检查法先设置自己的标志为 true 后，再检测对方的标志，若对方标志为 true，则进程等待，否则进入临界区

bool flag[2];
void init() {
    flag[0] = false;
    flag[1] = false;
}
void P0() {            //P0进程
    flag[0] = true;    //1 进入区
    while (flag[1]);   //2
    critical section;  //3 临界区
    flag[0] = false;   //4 退出区
    remainder section; //剩余区
}
void P1() {            //P1进程
    flag[1] = true;    //5 进入区
    while (flag[0]);   //6
    critical section;  //7 临界区
    flag[1] = false;   //8 退出区
    remainder section; //剩余区
}

按 $1$、$5$、$2$、$6\dots$ 的顺序，可能会导致 $P_0$、$P_1$ 都无法进入临界区，导致出现饥饿现象，违反了空闲让进和有限等待原则

Peterson 算法

Peterson 算法结合了单标志法、双标志后检查法，若双方都想进入临界区，会尝试让进程彼此谦让

每个进程先设置自己的 flag[i] 标志，表示 $P_i$ 是否进入临界区，用于解决互斥；又设置了 turn 标志，表示优先让哪个进程进入，用于解决饥饿

bool flag[2];
int turn;
void init() {
    turn = 0;
    flag[0] = false;
    flag[1] = false;
}
void P0() {            //P0进程
    flag[0] = true;    //进入区
    turn = 1;
    while (flag[1] && turn == 1);   
    critical section;  //临界区
    flag[0] = false;   //退出区
    remainder section; //剩余区
}
void P1() {            //P1进程
    flag[1] = true;    //进入区
    turn = 0;
    while (flag[0] && turn == 0);   
    critical section;  //临界区
    flag[1] = false;   //退出区
    remainder section; //剩余区
}

可以发现，Peterson 算法在进入区中，是先主动争取，然后主动谦让，最后再检查对方是否想进入临界区，己方是否谦让

其遵循了空闲让进、忙则等待、有限等待原则，但违反了让权等待原则，可能会造成忙等

【硬件实现方法】

许多计算机中提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换，利用这些特殊的硬件指令，可以解决临界区问题。

进入临界区往往与其标志有关，我们可以将标志看做一个初始时开启的锁：锁开启时，允许进入，且进入后关闭锁；锁关闭时，必须等待

中断屏蔽法

中断屏蔽法是实现互斥的最简单的方法，其利用了开关中断指令实现互斥

在进入锁测试前关闭中断，直到完成锁测试并上锁后才能打开中断，这样进程在临界区执行期间，系统不响应中断，从而也就不会引发调度

但关中断的方法具有许多缺点，例如：滥用关中断权力、关中断时间过长影响系统效率、不适用于多 CPU 系统等

while (true) {
    关中断;            //进入区
    critical section; //临界区
    开中断;            //退出区
    remainder section //剩余区
}

TSL 指令

TSL 指令是一条硬件指令：Test-and-Set-Lock 指令，其是用硬件实现的原子操作，在读出指定标志后，会将标志设为真，整个检查、上锁过程一气呵成

该指令一般性描述如下：

bool TSL (bool *lock) { //lock表示临界区是否被上锁
    bool old = *lock;   //存放lock原来的值
    *lock = true;       //无论之前是否加锁，都上锁
    return old;         //返回lock原来的值
}

TSL 指令可以看做一个函数过程，其执行过程是不可分割的，即其是一条原语，其中 lock 具有两种状态：

*lock=false 时：表示该资源空闲
*lock=true 时：表示该资源正被使用

用 TSL 指令管理临界区时，现为每个临界资源设置一个布尔变量 lock，由于变量 lock 代表了该资源的状态，故可以将其看作一把锁

利用 TSL 指令实现互斥的循环进程结构描述如下：

while (true) {
    while(TS(&lock)); //进入区
    critical section; //临界区
    lock = false;       //退出区
    remainder section //剩余区
}

该方法实现简单，适合多处理机，但不满足让权等待原则，无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令

swap 指令

swap 指令即对换指令，其同样是由硬件实现的原子操作，用于交换两个字的内容，其处理过程描述如下：

void swap (bool *a, bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

使用对换指令可以简单有效地实现互斥，其方法是为每个临界资源设置一个初值为 false 的全局布尔变量 lock，在每个进程中再利用一个局部布尔变量 key，利用 swap 进行交换来实现互斥

利用 swap 指令实现互斥的循环进程结构描述如下：

while (true) {
    bool key = true; //进入区
    while(key)
        swap(&lock, &key);
    critical section; //临界区
    lock = false;//退出区
    remainder section //剩余区
}

该方法与 TSL 指令方法一样，实现简单，适合多处理机，且不满足让权等待原则

Alex_McAvoy

实现临界区互斥的基本方法